Home | History | Annotate | Download | only in Sema 
      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       std::string CorrectedQuotedStr(Corrected.getQuoted(getLangOpts()));
    823       ParameterPack = Corrected.getCorrectionDecl();
    824       Diag(NameLoc, diag::err_sizeof_pack_no_pack_name_suggest)
    825         << &Name << CorrectedQuotedStr
    826         << FixItHint::CreateReplacement(
    827             NameLoc, Corrected.getAsString(getLangOpts()));
    828       Diag(ParameterPack->getLocation(), diag::note_parameter_pack_here)
    829         << CorrectedQuotedStr;
    830     }
    831 
    832   case LookupResult::FoundOverloaded:
    833   case LookupResult::FoundUnresolvedValue:
    834     break;
    835 
    836   case LookupResult::Ambiguous:
    837     DiagnoseAmbiguousLookup(R);
    838     return ExprError();
    839   }
    840 
    841   if (!ParameterPack || !ParameterPack->isParameterPack()) {
    842     Diag(NameLoc, diag::err_sizeof_pack_no_pack_name)
    843       << &Name;
    844     return ExprError();
    845   }
    846 
    847   MarkAnyDeclReferenced(OpLoc, ParameterPack, true);
    848 
    849   return new (Context) SizeOfPackExpr(Context.getSizeType(), OpLoc,
    850                                       ParameterPack, NameLoc, RParenLoc);
    851 }
    852 
    853 TemplateArgumentLoc
    854 Sema::getTemplateArgumentPackExpansionPattern(
    855       TemplateArgumentLoc OrigLoc,
    856       SourceLocation &Ellipsis, Optional<unsigned> &NumExpansions) const {
    857   const TemplateArgument &Argument = OrigLoc.getArgument();
    858   assert(Argument.isPackExpansion());
    859   switch (Argument.getKind()) {
    860   case TemplateArgument::Type: {
    861     // FIXME: We shouldn't ever have to worry about missing
    862     // type-source info!
    863     TypeSourceInfo *ExpansionTSInfo = OrigLoc.getTypeSourceInfo();
    864     if (!ExpansionTSInfo)
    865       ExpansionTSInfo = Context.getTrivialTypeSourceInfo(Argument.getAsType(),
    866                                                          Ellipsis);
    867     PackExpansionTypeLoc Expansion =
    868         ExpansionTSInfo->getTypeLoc().castAs<PackExpansionTypeLoc>();
    869     Ellipsis = Expansion.getEllipsisLoc();
    870 
    871     TypeLoc Pattern = Expansion.getPatternLoc();
    872     NumExpansions = Expansion.getTypePtr()->getNumExpansions();
    873 
    874     // We need to copy the TypeLoc because TemplateArgumentLocs store a
    875     // TypeSourceInfo.
    876     // FIXME: Find some way to avoid the copy?
    877     TypeLocBuilder TLB;
    878     TLB.pushFullCopy(Pattern);
    879     TypeSourceInfo *PatternTSInfo =
    880         TLB.getTypeSourceInfo(Context, Pattern.getType());
    881     return TemplateArgumentLoc(TemplateArgument(Pattern.getType()),
    882                                PatternTSInfo);
    883   }
    884 
    885   case TemplateArgument::Expression: {
    886     PackExpansionExpr *Expansion
    887       = cast<PackExpansionExpr>(Argument.getAsExpr());
    888     Expr *Pattern = Expansion->getPattern();
    889     Ellipsis = Expansion->getEllipsisLoc();
    890     NumExpansions = Expansion->getNumExpansions();
    891     return TemplateArgumentLoc(Pattern, Pattern);
    892   }
    893 
    894   case TemplateArgument::TemplateExpansion:
    895     Ellipsis = OrigLoc.getTemplateEllipsisLoc();
    896     NumExpansions = Argument.getNumTemplateExpansions();
    897     return TemplateArgumentLoc(Argument.getPackExpansionPattern(),
    898                                OrigLoc.getTemplateQualifierLoc(),
    899                                OrigLoc.getTemplateNameLoc());
    900 
    901   case TemplateArgument::Declaration:
    902   case TemplateArgument::NullPtr:
    903   case TemplateArgument::Template:
    904   case TemplateArgument::Integral:
    905   case TemplateArgument::Pack:
    906   case TemplateArgument::Null:
    907     return TemplateArgumentLoc();
    908   }
    909 
    910   llvm_unreachable("Invalid TemplateArgument Kind!");
    911 }
    912