contrib/llvm/tools/clang/lib/Sema/SemaTemplateVariadic.cpp

   1 //===------- SemaTemplateVariadic.cpp - C++ Variadic Templates ------------===/
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //===----------------------------------------------------------------------===/
   8 //
   9 //  This file implements semantic analysis for C++0x variadic templates.
  10 //===----------------------------------------------------------------------===/
  11
  12 #include "clang/Sema/Sema.h"
  13 #include "clang/AST/Expr.h"
  14 #include "clang/AST/RecursiveASTVisitor.h"
  15 #include "clang/AST/TypeLoc.h"
  16 #include "clang/Sema/Lookup.h"
  17 #include "clang/Sema/ParsedTemplate.h"
  18 #include "clang/Sema/ScopeInfo.h"
  19 #include "clang/Sema/SemaInternal.h"
  20 #include "clang/Sema/Template.h"
  21
  22 using namespace clang;
  23
  24 //----------------------------------------------------------------------------
  25 // Visitor that collects unexpanded parameter packs
  26 //----------------------------------------------------------------------------
  27
  28 namespace {
  29   /// \brief A class that collects unexpanded parameter packs.
  30   class CollectUnexpandedParameterPacksVisitor :
  31     public RecursiveASTVisitor<CollectUnexpandedParameterPacksVisitor>
  32   {
  33     typedef RecursiveASTVisitor<CollectUnexpandedParameterPacksVisitor>
  34       inherited;
  35
  36     SmallVectorImpl<UnexpandedParameterPack> &Unexpanded;
  37
  38     bool InLambda;
  39
  40   public:
  41     explicit CollectUnexpandedParameterPacksVisitor(
  42                   SmallVectorImpl<UnexpandedParameterPack> &Unexpanded)
  43       : Unexpanded(Unexpanded), InLambda(false) { }
  44
  45     bool shouldWalkTypesOfTypeLocs() const { return false; }
  46
  47     //------------------------------------------------------------------------
  48     // Recording occurrences of (unexpanded) parameter packs.
  49     //------------------------------------------------------------------------
  50
  51     /// \brief Record occurrences of template type parameter packs.
  52     bool VisitTemplateTypeParmTypeLoc(TemplateTypeParmTypeLoc TL) {
  53       if (TL.getTypePtr()->isParameterPack())
  54         Unexpanded.push_back(std::make_pair(TL.getTypePtr(), TL.getNameLoc()));
  55       return true;
  56     }
  57
  58     /// \brief Record occurrences of template type parameter packs
  59     /// when we don't have proper source-location information for
  60     /// them.
  61     ///
  62     /// Ideally, this routine would never be used.
  63     bool VisitTemplateTypeParmType(TemplateTypeParmType *T) {
  64       if (T->isParameterPack())
  65         Unexpanded.push_back(std::make_pair(T, SourceLocation()));
  66
  67       return true;
  68     }
  69
  70     /// \brief Record occurrences of function and non-type template
  71     /// parameter packs in an expression.
  72     bool VisitDeclRefExpr(DeclRefExpr *E) {
  73       if (E->getDecl()->isParameterPack())
  74         Unexpanded.push_back(std::make_pair(E->getDecl(), E->getLocation()));
  75
  76       return true;
  77     }
  78
  79     /// \brief Record occurrences of template template parameter packs.
  80     bool TraverseTemplateName(TemplateName Template) {
  81       if (TemplateTemplateParmDecl *TTP
  82             = dyn_cast_or_null<TemplateTemplateParmDecl>(
  83                                                   Template.getAsTemplateDecl()))
  84         if (TTP->isParameterPack())
  85           Unexpanded.push_back(std::make_pair(TTP, SourceLocation()));
  86
  87       return inherited::TraverseTemplateName(Template);
  88     }
  89
  90     /// \brief Suppress traversal into Objective-C container literal
  91     /// elements that are pack expansions.
  92     bool TraverseObjCDictionaryLiteral(ObjCDictionaryLiteral *E) {
  93       if (!E->containsUnexpandedParameterPack())
  94         return true;
  95
  96       for (unsigned I = 0, N = E->getNumElements(); I != N; ++I) {
  97         ObjCDictionaryElement Element = E->getKeyValueElement(I);
  98         if (Element.isPackExpansion())
  99           continue;
 100
 101         TraverseStmt(Element.Key);
 102         TraverseStmt(Element.Value);
 103       }
 104       return true;
 105     }
 106     //------------------------------------------------------------------------
 107     // Pruning the search for unexpanded parameter packs.
 108     //------------------------------------------------------------------------
 109
 110     /// \brief Suppress traversal into statements and expressions that
 111     /// do not contain unexpanded parameter packs.
 112     bool TraverseStmt(Stmt *S) {
 113       Expr *E = dyn_cast_or_null<Expr>(S);
 114       if ((E && E->containsUnexpandedParameterPack()) || InLambda)
 115         return inherited::TraverseStmt(S);
 116
 117       return true;
 118     }
 119
 120     /// \brief Suppress traversal into types that do not contain
 121     /// unexpanded parameter packs.
 122     bool TraverseType(QualType T) {
 123       if ((!T.isNull() && T->containsUnexpandedParameterPack()) || InLambda)
 124         return inherited::TraverseType(T);
 125
 126       return true;
 127     }
 128
 129     /// \brief Suppress traversel into types with location information
 130     /// that do not contain unexpanded parameter packs.
 131     bool TraverseTypeLoc(TypeLoc TL) {
 132       if ((!TL.getType().isNull() &&
 133            TL.getType()->containsUnexpandedParameterPack()) ||
 134           InLambda)
 135         return inherited::TraverseTypeLoc(TL);
 136
 137       return true;
 138     }
 139
 140     /// \brief Suppress traversal of non-parameter declarations, since
 141     /// they cannot contain unexpanded parameter packs.
 142     bool TraverseDecl(Decl *D) {
 143       if ((D && isa<ParmVarDecl>(D)) || InLambda)
 144         return inherited::TraverseDecl(D);
 145
 146       return true;
 147     }
 148
 149     /// \brief Suppress traversal of template argument pack expansions.
 150     bool TraverseTemplateArgument(const TemplateArgument &Arg) {
 151       if (Arg.isPackExpansion())
 152         return true;
 153
 154       return inherited::TraverseTemplateArgument(Arg);
 155     }
 156
 157     /// \brief Suppress traversal of template argument pack expansions.
 158     bool TraverseTemplateArgumentLoc(const TemplateArgumentLoc &ArgLoc) {
 159       if (ArgLoc.getArgument().isPackExpansion())
 160         return true;
 161
 162       return inherited::TraverseTemplateArgumentLoc(ArgLoc);
 163     }
 164
 165     /// \brief Note whether we're traversing a lambda containing an unexpanded
 166     /// parameter pack. In this case, the unexpanded pack can occur anywhere,
 167     /// including all the places where we normally wouldn't look. Within a
 168     /// lambda, we don't propagate the 'contains unexpanded parameter pack' bit
 169     /// outside an expression.
 170     bool TraverseLambdaExpr(LambdaExpr *Lambda) {
 171       // The ContainsUnexpandedParameterPack bit on a lambda is always correct,
 172       // even if it's contained within another lambda.
 173       if (!Lambda->containsUnexpandedParameterPack())
 174         return true;
 175
 176       bool WasInLambda = InLambda;
 177       InLambda = true;
 178
 179       // If any capture names a function parameter pack, that pack is expanded
 180       // when the lambda is expanded.
 181       for (LambdaExpr::capture_iterator I = Lambda->capture_begin(),
 182                                         E = Lambda->capture_end(); I != E; ++I)
 183         if (VarDecl *VD = I->getCapturedVar())
 184           if (VD->isParameterPack())
 185             Unexpanded.push_back(std::make_pair(VD, I->getLocation()));
 186
 187       inherited::TraverseLambdaExpr(Lambda);
 188
 189       InLambda = WasInLambda;
 190       return true;
 191     }
 192   };
 193 }
 194
 195 /// \brief Diagnose all of the unexpanded parameter packs in the given
 196 /// vector.
 197 bool
 198 Sema::DiagnoseUnexpandedParameterPacks(SourceLocation Loc,
 199                                        UnexpandedParameterPackContext UPPC,
 200                                  ArrayRef<UnexpandedParameterPack> Unexpanded) {
 201   if (Unexpanded.empty())
 202     return false;
 203
 204   // If we are within a lambda expression, that lambda contains an unexpanded
 205   // parameter pack, and we are done.
 206   // FIXME: Store 'Unexpanded' on the lambda so we don't need to recompute it
 207   // later.
 208   for (unsigned N = FunctionScopes.size(); N; --N) {
 209     if (sema::LambdaScopeInfo *LSI =
 210           dyn_cast<sema::LambdaScopeInfo>(FunctionScopes[N-1])) {
 211       LSI->ContainsUnexpandedParameterPack = true;
 212       return false;
 213     }
 214   }
 215
 216   SmallVector<SourceLocation, 4> Locations;
 217   SmallVector<IdentifierInfo *, 4> Names;
 218   llvm::SmallPtrSet<IdentifierInfo *, 4> NamesKnown;
 219
 220   for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
 221     IdentifierInfo *Name = 0;
 222     if (const TemplateTypeParmType *TTP
 223           = Unexpanded[I].first.dyn_cast<const TemplateTypeParmType *>())
 224       Name = TTP->getIdentifier();
 225     else
 226       Name = Unexpanded[I].first.get<NamedDecl *>()->getIdentifier();
 227
 228     if (Name && NamesKnown.insert(Name))
 229       Names.push_back(Name);
 230
 231     if (Unexpanded[I].second.isValid())
 232       Locations.push_back(Unexpanded[I].second);
 233   }
 234
 235   DiagnosticBuilder DB
 236     = Names.size() == 0? Diag(Loc, diag::err_unexpanded_parameter_pack_0)
 237                            << (int)UPPC
 238     : Names.size() == 1? Diag(Loc, diag::err_unexpanded_parameter_pack_1)
 239                            << (int)UPPC << Names[0]
 240     : Names.size() == 2? Diag(Loc, diag::err_unexpanded_parameter_pack_2)
 241                            << (int)UPPC << Names[0] << Names[1]
 242     : Diag(Loc, diag::err_unexpanded_parameter_pack_3_or_more)
 243         << (int)UPPC << Names[0] << Names[1];
 244
 245   for (unsigned I = 0, N = Locations.size(); I != N; ++I)
 246     DB << SourceRange(Locations[I]);
 247   return true;
 248 }
 249
 250 bool Sema::DiagnoseUnexpandedParameterPack(SourceLocation Loc,
 251                                            TypeSourceInfo *T,
 252                                          UnexpandedParameterPackContext UPPC) {
 253   // C++0x [temp.variadic]p5:
 254   //   An appearance of a name of a parameter pack that is not expanded is
 255   //   ill-formed.
 256   if (!T->getType()->containsUnexpandedParameterPack())
 257     return false;
 258
 259   SmallVector<UnexpandedParameterPack, 2> Unexpanded;
 260   CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseTypeLoc(
 261                                                               T->getTypeLoc());
 262   assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
 263   return DiagnoseUnexpandedParameterPacks(Loc, UPPC, Unexpanded);
 264 }
 265
 266 bool Sema::DiagnoseUnexpandedParameterPack(Expr *E,
 267                                         UnexpandedParameterPackContext UPPC) {
 268   // C++0x [temp.variadic]p5:
 269   //   An appearance of a name of a parameter pack that is not expanded is
 270   //   ill-formed.
 271   if (!E->containsUnexpandedParameterPack())
 272     return false;
 273
 274   SmallVector<UnexpandedParameterPack, 2> Unexpanded;
 275   CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseStmt(E);
 276   assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
 277   return DiagnoseUnexpandedParameterPacks(E->getLocStart(), UPPC, Unexpanded);
 278 }
 279
 280 bool Sema::DiagnoseUnexpandedParameterPack(const CXXScopeSpec &SS,
 281                                         UnexpandedParameterPackContext UPPC) {
 282   // C++0x [temp.variadic]p5:
 283   //   An appearance of a name of a parameter pack that is not expanded is
 284   //   ill-formed.
 285   if (!SS.getScopeRep() ||
 286       !SS.getScopeRep()->containsUnexpandedParameterPack())
 287     return false;
 288
 289   SmallVector<UnexpandedParameterPack, 2> Unexpanded;
 290   CollectUnexpandedParameterPacksVisitor(Unexpanded)
 291     .TraverseNestedNameSpecifier(SS.getScopeRep());
 292   assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
 293   return DiagnoseUnexpandedParameterPacks(SS.getRange().getBegin(),
 294                                           UPPC, Unexpanded);
 295 }
 296
 297 bool Sema::DiagnoseUnexpandedParameterPack(const DeclarationNameInfo &NameInfo,
 298                                          UnexpandedParameterPackContext UPPC) {
 299   // C++0x [temp.variadic]p5:
 300   //   An appearance of a name of a parameter pack that is not expanded is
 301   //   ill-formed.
 302   switch (NameInfo.getName().getNameKind()) {
 303   case DeclarationName::Identifier:
 304   case DeclarationName::ObjCZeroArgSelector:
 305   case DeclarationName::ObjCOneArgSelector:
 306   case DeclarationName::ObjCMultiArgSelector:
 307   case DeclarationName::CXXOperatorName:
 308   case DeclarationName::CXXLiteralOperatorName:
 309   case DeclarationName::CXXUsingDirective:
 310     return false;
 311
 312   case DeclarationName::CXXConstructorName:
 313   case DeclarationName::CXXDestructorName:
 314   case DeclarationName::CXXConversionFunctionName:
 315     // FIXME: We shouldn't need this null check!
 316     if (TypeSourceInfo *TSInfo = NameInfo.getNamedTypeInfo())
 317       return DiagnoseUnexpandedParameterPack(NameInfo.getLoc(), TSInfo, UPPC);
 318
 319     if (!NameInfo.getName().getCXXNameType()->containsUnexpandedParameterPack())
 320       return false;
 321
 322     break;
 323   }
 324
 325   SmallVector<UnexpandedParameterPack, 2> Unexpanded;
 326   CollectUnexpandedParameterPacksVisitor(Unexpanded)
 327     .TraverseType(NameInfo.getName().getCXXNameType());
 328   assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
 329   return DiagnoseUnexpandedParameterPacks(NameInfo.getLoc(), UPPC, Unexpanded);
 330 }
 331
 332 bool Sema::DiagnoseUnexpandedParameterPack(SourceLocation Loc,
 333                                            TemplateName Template,
 334                                        UnexpandedParameterPackContext UPPC) {
 335
 336   if (Template.isNull() || !Template.containsUnexpandedParameterPack())
 337     return false;
 338
 339   SmallVector<UnexpandedParameterPack, 2> Unexpanded;
 340   CollectUnexpandedParameterPacksVisitor(Unexpanded)
 341     .TraverseTemplateName(Template);
 342   assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
 343   return DiagnoseUnexpandedParameterPacks(Loc, UPPC, Unexpanded);
 344 }
 345
 346 bool Sema::DiagnoseUnexpandedParameterPack(TemplateArgumentLoc Arg,
 347                                          UnexpandedParameterPackContext UPPC) {
 348   if (Arg.getArgument().isNull() ||
 349       !Arg.getArgument().containsUnexpandedParameterPack())
 350     return false;
 351
 352   SmallVector<UnexpandedParameterPack, 2> Unexpanded;
 353   CollectUnexpandedParameterPacksVisitor(Unexpanded)
 354     .TraverseTemplateArgumentLoc(Arg);
 355   assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
 356   return DiagnoseUnexpandedParameterPacks(Arg.getLocation(), UPPC, Unexpanded);
 357 }
 358
 359 void Sema::collectUnexpandedParameterPacks(TemplateArgument Arg,
 360                    SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
 361   CollectUnexpandedParameterPacksVisitor(Unexpanded)
 362     .TraverseTemplateArgument(Arg);
 363 }
 364
 365 void Sema::collectUnexpandedParameterPacks(TemplateArgumentLoc Arg,
 366                    SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
 367   CollectUnexpandedParameterPacksVisitor(Unexpanded)
 368     .TraverseTemplateArgumentLoc(Arg);
 369 }
 370
 371 void Sema::collectUnexpandedParameterPacks(QualType T,
 372                    SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
 373   CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseType(T);
 374 }
 375
 376 void Sema::collectUnexpandedParameterPacks(TypeLoc TL,
 377                    SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
 378   CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseTypeLoc(TL);
 379 }
 380
 381 void Sema::collectUnexpandedParameterPacks(CXXScopeSpec &SS,
 382                                            SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
 383   NestedNameSpecifier *Qualifier = SS.getScopeRep();
 384   if (!Qualifier)
 385     return;
 386
 387   NestedNameSpecifierLoc QualifierLoc(Qualifier, SS.location_data());
 388   CollectUnexpandedParameterPacksVisitor(Unexpanded)
 389     .TraverseNestedNameSpecifierLoc(QualifierLoc);
 390 }
 391
 392 void Sema::collectUnexpandedParameterPacks(const DeclarationNameInfo &NameInfo,
 393                          SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
 394   CollectUnexpandedParameterPacksVisitor(Unexpanded)
 395     .TraverseDeclarationNameInfo(NameInfo);
 396 }
 397
 398
 399 ParsedTemplateArgument
 400 Sema::ActOnPackExpansion(const ParsedTemplateArgument &Arg,
 401                          SourceLocation EllipsisLoc) {
 402   if (Arg.isInvalid())
 403     return Arg;
 404
 405   switch (Arg.getKind()) {
 406   case ParsedTemplateArgument::Type: {
 407     TypeResult Result = ActOnPackExpansion(Arg.getAsType(), EllipsisLoc);
 408     if (Result.isInvalid())
 409       return ParsedTemplateArgument();
 410
 411     return ParsedTemplateArgument(Arg.getKind(), Result.get().getAsOpaquePtr(),
 412                                   Arg.getLocation());
 413   }
 414
 415   case ParsedTemplateArgument::NonType: {
 416     ExprResult Result = ActOnPackExpansion(Arg.getAsExpr(), EllipsisLoc);
 417     if (Result.isInvalid())
 418       return ParsedTemplateArgument();
 419
 420     return ParsedTemplateArgument(Arg.getKind(), Result.get(),
 421                                   Arg.getLocation());
 422   }
 423
 424   case ParsedTemplateArgument::Template:
 425     if (!Arg.getAsTemplate().get().containsUnexpandedParameterPack()) {
 426       SourceRange R(Arg.getLocation());
 427       if (Arg.getScopeSpec().isValid())
 428         R.setBegin(Arg.getScopeSpec().getBeginLoc());
 429       Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
 430         << R;
 431       return ParsedTemplateArgument();
 432     }
 433
 434     return Arg.getTemplatePackExpansion(EllipsisLoc);
 435   }
 436   llvm_unreachable("Unhandled template argument kind?");
 437 }
 438
 439 TypeResult Sema::ActOnPackExpansion(ParsedType Type,
 440                                     SourceLocation EllipsisLoc) {
 441   TypeSourceInfo *TSInfo;
 442   GetTypeFromParser(Type, &TSInfo);
 443   if (!TSInfo)
 444     return true;
 445
 446   TypeSourceInfo *TSResult = CheckPackExpansion(TSInfo, EllipsisLoc, None);
 447   if (!TSResult)
 448     return true;
 449
 450   return CreateParsedType(TSResult->getType(), TSResult);
 451 }
 452
 453 TypeSourceInfo *
 454 Sema::CheckPackExpansion(TypeSourceInfo *Pattern, SourceLocation EllipsisLoc,
 455                          Optional<unsigned> NumExpansions) {
 456   // Create the pack expansion type and source-location information.
 457   QualType Result = CheckPackExpansion(Pattern->getType(),
 458                                        Pattern->getTypeLoc().getSourceRange(),
 459                                        EllipsisLoc, NumExpansions);
 460   if (Result.isNull())
 461     return 0;
 462
 463   TypeSourceInfo *TSResult = Context.CreateTypeSourceInfo(Result);
 464   PackExpansionTypeLoc TL =
 465       TSResult->getTypeLoc().castAs<PackExpansionTypeLoc>();
 466   TL.setEllipsisLoc(EllipsisLoc);
 467
 468   // Copy over the source-location information from the type.
 469   memcpy(TL.getNextTypeLoc().getOpaqueData(),
 470          Pattern->getTypeLoc().getOpaqueData(),
 471          Pattern->getTypeLoc().getFullDataSize());
 472   return TSResult;
 473 }
 474
 475 QualType Sema::CheckPackExpansion(QualType Pattern, SourceRange PatternRange,
 476                                   SourceLocation EllipsisLoc,
 477                                   Optional<unsigned> NumExpansions) {
 478   // C++0x [temp.variadic]p5:
 479   //   The pattern of a pack expansion shall name one or more
 480   //   parameter packs that are not expanded by a nested pack
 481   //   expansion.
 482   if (!Pattern->containsUnexpandedParameterPack()) {
 483     Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
 484       << PatternRange;
 485     return QualType();
 486   }
 487
 488   return Context.getPackExpansionType(Pattern, NumExpansions);
 489 }
 490
 491 ExprResult Sema::ActOnPackExpansion(Expr *Pattern, SourceLocation EllipsisLoc) {
 492   return CheckPackExpansion(Pattern, EllipsisLoc, None);
 493 }
 494
 495 ExprResult Sema::CheckPackExpansion(Expr *Pattern, SourceLocation EllipsisLoc,
 496                                     Optional<unsigned> NumExpansions) {
 497   if (!Pattern)
 498     return ExprError();
 499
 500   // C++0x [temp.variadic]p5:
 501   //   The pattern of a pack expansion shall name one or more
 502   //   parameter packs that are not expanded by a nested pack
 503   //   expansion.
 504   if (!Pattern->containsUnexpandedParameterPack()) {
 505     Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
 506     << Pattern->getSourceRange();
 507     return ExprError();
 508   }
 509
 510   // Create the pack expansion expression and source-location information.
 511   return Owned(new (Context) PackExpansionExpr(Context.DependentTy, Pattern,
 512                                                EllipsisLoc, NumExpansions));
 513 }
 514
 515 /// \brief Retrieve the depth and index of a parameter pack.
 516 static std::pair<unsigned, unsigned>
 517 getDepthAndIndex(NamedDecl *ND) {
 518   if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(ND))
 519     return std::make_pair(TTP->getDepth(), TTP->getIndex());
 520
 521   if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(ND))
 522     return std::make_pair(NTTP->getDepth(), NTTP->getIndex());
 523
 524   TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(ND);
 525   return std::make_pair(TTP->getDepth(), TTP->getIndex());
 526 }
 527
 528 bool Sema::CheckParameterPacksForExpansion(
 529     SourceLocation EllipsisLoc, SourceRange PatternRange,
 530     ArrayRef<UnexpandedParameterPack> Unexpanded,
 531     const MultiLevelTemplateArgumentList &TemplateArgs, bool &ShouldExpand,
 532     bool &RetainExpansion, Optional<unsigned> &NumExpansions) {
 533   ShouldExpand = true;
 534   RetainExpansion = false;
 535   std::pair<IdentifierInfo *, SourceLocation> FirstPack;
 536   bool HaveFirstPack = false;
 537
 538   for (ArrayRef<UnexpandedParameterPack>::iterator i = Unexpanded.begin(),
 539                                                  end = Unexpanded.end();
 540                                                   i != end; ++i) {
 541     // Compute the depth and index for this parameter pack.
 542     unsigned Depth = 0, Index = 0;
 543     IdentifierInfo *Name;
 544     bool IsFunctionParameterPack = false;
 545
 546     if (const TemplateTypeParmType *TTP
 547         = i->first.dyn_cast<const TemplateTypeParmType *>()) {
 548       Depth = TTP->getDepth();
 549       Index = TTP->getIndex();
 550       Name = TTP->getIdentifier();
 551     } else {
 552       NamedDecl *ND = i->first.get<NamedDecl *>();
 553       if (isa<ParmVarDecl>(ND))
 554         IsFunctionParameterPack = true;
 555       else
 556         llvm::tie(Depth, Index) = getDepthAndIndex(ND);
 557
 558       Name = ND->getIdentifier();
 559     }
 560
 561     // Determine the size of this argument pack.
 562     unsigned NewPackSize;
 563     if (IsFunctionParameterPack) {
 564       // Figure out whether we're instantiating to an argument pack or not.
 565       typedef LocalInstantiationScope::DeclArgumentPack DeclArgumentPack;
 566
 567       llvm::PointerUnion<Decl *, DeclArgumentPack *> *Instantiation
 568         = CurrentInstantiationScope->findInstantiationOf(
 569                                         i->first.get<NamedDecl *>());
 570       if (Instantiation->is<DeclArgumentPack *>()) {
 571         // We could expand this function parameter pack.
 572         NewPackSize = Instantiation->get<DeclArgumentPack *>()->size();
 573       } else {
 574         // We can't expand this function parameter pack, so we can't expand
 575         // the pack expansion.
 576         ShouldExpand = false;
 577         continue;
 578       }
 579     } else {
 580       // If we don't have a template argument at this depth/index, then we
 581       // cannot expand the pack expansion. Make a note of this, but we still
 582       // want to check any parameter packs we *do* have arguments for.
 583       if (Depth >= TemplateArgs.getNumLevels() ||
 584           !TemplateArgs.hasTemplateArgument(Depth, Index)) {
 585         ShouldExpand = false;
 586         continue;
 587       }
 588
 589       // Determine the size of the argument pack.
 590       NewPackSize = TemplateArgs(Depth, Index).pack_size();
 591     }
 592
 593     // C++0x [temp.arg.explicit]p9:
 594     //   Template argument deduction can extend the sequence of template
 595     //   arguments corresponding to a template parameter pack, even when the
 596     //   sequence contains explicitly specified template arguments.
 597     if (!IsFunctionParameterPack) {
 598       if (NamedDecl *PartialPack
 599                     = CurrentInstantiationScope->getPartiallySubstitutedPack()){
 600         unsigned PartialDepth, PartialIndex;
 601         llvm::tie(PartialDepth, PartialIndex) = getDepthAndIndex(PartialPack);
 602         if (PartialDepth == Depth && PartialIndex == Index)
 603           RetainExpansion = true;
 604       }
 605     }
 606
 607     if (!NumExpansions) {
 608       // The is the first pack we've seen for which we have an argument.
 609       // Record it.
 610       NumExpansions = NewPackSize;
 611       FirstPack.first = Name;
 612       FirstPack.second = i->second;
 613       HaveFirstPack = true;
 614       continue;
 615     }
 616
 617     if (NewPackSize != *NumExpansions) {
 618       // C++0x [temp.variadic]p5:
 619       //   All of the parameter packs expanded by a pack expansion shall have
 620       //   the same number of arguments specified.
 621       if (HaveFirstPack)
 622         Diag(EllipsisLoc, diag::err_pack_expansion_length_conflict)
 623           << FirstPack.first << Name << *NumExpansions << NewPackSize
 624           << SourceRange(FirstPack.second) << SourceRange(i->second);
 625       else
 626         Diag(EllipsisLoc, diag::err_pack_expansion_length_conflict_multilevel)
 627           << Name << *NumExpansions << NewPackSize
 628           << SourceRange(i->second);
 629       return true;
 630     }
 631   }
 632
 633   return false;
 634 }
 635
 636 Optional<unsigned> Sema::getNumArgumentsInExpansion(QualType T,
 637                           const MultiLevelTemplateArgumentList &TemplateArgs) {
 638   QualType Pattern = cast<PackExpansionType>(T)->getPattern();
 639   SmallVector<UnexpandedParameterPack, 2> Unexpanded;
 640   CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseType(Pattern);
 641
 642   Optional<unsigned> Result;
 643   for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
 644     // Compute the depth and index for this parameter pack.
 645     unsigned Depth;
 646     unsigned Index;
 647
 648     if (const TemplateTypeParmType *TTP
 649           = Unexpanded[I].first.dyn_cast<const TemplateTypeParmType *>()) {
 650       Depth = TTP->getDepth();
 651       Index = TTP->getIndex();
 652     } else {
 653       NamedDecl *ND = Unexpanded[I].first.get<NamedDecl *>();
 654       if (isa<ParmVarDecl>(ND)) {
 655         // Function parameter pack.
 656         typedef LocalInstantiationScope::DeclArgumentPack DeclArgumentPack;
 657
 658         llvm::PointerUnion<Decl *, DeclArgumentPack *> *Instantiation
 659           = CurrentInstantiationScope->findInstantiationOf(
 660                                         Unexpanded[I].first.get<NamedDecl *>());
 661         if (Instantiation->is<Decl*>())
 662           // The pattern refers to an unexpanded pack. We're not ready to expand
 663           // this pack yet.
 664           return None;
 665
 666         unsigned Size = Instantiation->get<DeclArgumentPack *>()->size();
 667         assert((!Result || *Result == Size) && "inconsistent pack sizes");
 668         Result = Size;
 669         continue;
 670       }
 671
 672       llvm::tie(Depth, Index) = getDepthAndIndex(ND);
 673     }
 674     if (Depth >= TemplateArgs.getNumLevels() ||
 675         !TemplateArgs.hasTemplateArgument(Depth, Index))
 676       // The pattern refers to an unknown template argument. We're not ready to
 677       // expand this pack yet.
 678       return None;
 679
 680     // Determine the size of the argument pack.
 681     unsigned Size = TemplateArgs(Depth, Index).pack_size();
 682     assert((!Result || *Result == Size) && "inconsistent pack sizes");
 683     Result = Size;
 684   }
 685
 686   return Result;
 687 }
 688
 689 bool Sema::containsUnexpandedParameterPacks(Declarator &D) {
 690   const DeclSpec &DS = D.getDeclSpec();
 691   switch (DS.getTypeSpecType()) {
 692   case TST_typename:
 693   case TST_typeofType:
 694   case TST_underlyingType:
 695   case TST_atomic: {
 696     QualType T = DS.getRepAsType().get();
 697     if (!T.isNull() && T->containsUnexpandedParameterPack())
 698       return true;
 699     break;
 700   }
 701
 702   case TST_typeofExpr:
 703   case TST_decltype:
 704     if (DS.getRepAsExpr() &&
 705         DS.getRepAsExpr()->containsUnexpandedParameterPack())
 706       return true;
 707     break;
 708
 709   case TST_unspecified:
 710   case TST_void:
 711   case TST_char:
 712   case TST_wchar:
 713   case TST_char16:
 714   case TST_char32:
 715   case TST_int:
 716   case TST_int128:
 717   case TST_half:
 718   case TST_float:
 719   case TST_double:
 720   case TST_bool:
 721   case TST_decimal32:
 722   case TST_decimal64:
 723   case TST_decimal128:
 724   case TST_enum:
 725   case TST_union:
 726   case TST_struct:
 727   case TST_interface:
 728   case TST_class:
 729   case TST_auto:
 730   case TST_decltype_auto:
 731   case TST_unknown_anytype:
 732   case TST_image1d_t:
 733   case TST_image1d_array_t:
 734   case TST_image1d_buffer_t:
 735   case TST_image2d_t:
 736   case TST_image2d_array_t:
 737   case TST_image3d_t:
 738   case TST_sampler_t:
 739   case TST_event_t:
 740   case TST_error:
 741     break;
 742   }
 743
 744   for (unsigned I = 0, N = D.getNumTypeObjects(); I != N; ++I) {
 745     const DeclaratorChunk &Chunk = D.getTypeObject(I);
 746     switch (Chunk.Kind) {
 747     case DeclaratorChunk::Pointer:
 748     case DeclaratorChunk::Reference:
 749     case DeclaratorChunk::Paren:
 750       // These declarator chunks cannot contain any parameter packs.
 751       break;
 752
 753     case DeclaratorChunk::Array:
 754     case DeclaratorChunk::Function:
 755     case DeclaratorChunk::BlockPointer:
 756       // Syntactically, these kinds of declarator chunks all come after the
 757       // declarator-id (conceptually), so the parser should not invoke this
 758       // routine at this time.
 759       llvm_unreachable("Could not have seen this kind of declarator chunk");
 760
 761     case DeclaratorChunk::MemberPointer:
 762       if (Chunk.Mem.Scope().getScopeRep() &&
 763           Chunk.Mem.Scope().getScopeRep()->containsUnexpandedParameterPack())
 764         return true;
 765       break;
 766     }
 767   }
 768
 769   return false;
 770 }
 771
 772 namespace {
 773
 774 // Callback to only accept typo corrections that refer to parameter packs.
 775 class ParameterPackValidatorCCC : public CorrectionCandidateCallback {
 776  public:
 777   virtual bool ValidateCandidate(const TypoCorrection &candidate) {
 778     NamedDecl *ND = candidate.getCorrectionDecl();
 779     return ND && ND->isParameterPack();
 780   }
 781 };
 782
 783 }
 784
 785 /// \brief Called when an expression computing the size of a parameter pack
 786 /// is parsed.
 787 ///
 788 /// \code
 789 /// template<typename ...Types> struct count {
 790 ///   static const unsigned value = sizeof...(Types);
 791 /// };
 792 /// \endcode
 793 ///
 794 //
 795 /// \param OpLoc The location of the "sizeof" keyword.
 796 /// \param Name The name of the parameter pack whose size will be determined.
 797 /// \param NameLoc The source location of the name of the parameter pack.
 798 /// \param RParenLoc The location of the closing parentheses.
 799 ExprResult Sema::ActOnSizeofParameterPackExpr(Scope *S,
 800                                               SourceLocation OpLoc,
 801                                               IdentifierInfo &Name,
 802                                               SourceLocation NameLoc,
 803                                               SourceLocation RParenLoc) {
 804   // C++0x [expr.sizeof]p5:
 805   //   The identifier in a sizeof... expression shall name a parameter pack.
 806   LookupResult R(*this, &Name, NameLoc, LookupOrdinaryName);
 807   LookupName(R, S);
 808
 809   NamedDecl *ParameterPack = 0;
 810   ParameterPackValidatorCCC Validator;
 811   switch (R.getResultKind()) {
 812   case LookupResult::Found:
 813     ParameterPack = R.getFoundDecl();
 814     break;
 815
 816   case LookupResult::NotFound:
 817   case LookupResult::NotFoundInCurrentInstantiation:
 818     if (TypoCorrection Corrected = CorrectTypo(R.getLookupNameInfo(),
 819                                                R.getLookupKind(), S, 0,
 820                                                Validator)) {
 821       std::string CorrectedQuotedStr(Corrected.getQuoted(getLangOpts()));
 822       ParameterPack = Corrected.getCorrectionDecl();
 823       Diag(NameLoc, diag::err_sizeof_pack_no_pack_name_suggest)
 824         << &Name << CorrectedQuotedStr
 825         << FixItHint::CreateReplacement(
 826             NameLoc, Corrected.getAsString(getLangOpts()));
 827       Diag(ParameterPack->getLocation(), diag::note_parameter_pack_here)
 828         << CorrectedQuotedStr;
 829     }
 830
 831   case LookupResult::FoundOverloaded:
 832   case LookupResult::FoundUnresolvedValue:
 833     break;
 834
 835   case LookupResult::Ambiguous:
 836     DiagnoseAmbiguousLookup(R);
 837     return ExprError();
 838   }
 839
 840   if (!ParameterPack || !ParameterPack->isParameterPack()) {
 841     Diag(NameLoc, diag::err_sizeof_pack_no_pack_name)
 842       << &Name;
 843     return ExprError();
 844   }
 845
 846   MarkAnyDeclReferenced(OpLoc, ParameterPack, true);
 847
 848   return new (Context) SizeOfPackExpr(Context.getSizeType(), OpLoc,
 849                                       ParameterPack, NameLoc, RParenLoc);
 850 }