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