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 
     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_unknown_anytype:
    731   case TST_image1d_t:
    732   case TST_image1d_array_t:
    733   case TST_image1d_buffer_t:
    734   case TST_image2d_t:
    735   case TST_image2d_array_t:
    736   case TST_image3d_t:
    737   case TST_sampler_t:
    738   case TST_event_t:
    739   case TST_error:
    740     break;
    741   }
    742 
    743   for (unsigned I = 0, N = D.getNumTypeObjects(); I != N; ++I) {
    744     const DeclaratorChunk &Chunk = D.getTypeObject(I);
    745     switch (Chunk.Kind) {
    746     case DeclaratorChunk::Pointer:
    747     case DeclaratorChunk::Reference:
    748     case DeclaratorChunk::Paren:
    749       // These declarator chunks cannot contain any parameter packs.
    750       break;
    751 
    752     case DeclaratorChunk::Array:
    753     case DeclaratorChunk::Function:
    754     case DeclaratorChunk::BlockPointer:
    755       // Syntactically, these kinds of declarator chunks all come after the
    756       // declarator-id (conceptually), so the parser should not invoke this
    757       // routine at this time.
    758       llvm_unreachable("Could not have seen this kind of declarator chunk");
    759 
    760     case DeclaratorChunk::MemberPointer:
    761       if (Chunk.Mem.Scope().getScopeRep() &&
    762           Chunk.Mem.Scope().getScopeRep()->containsUnexpandedParameterPack())
    763         return true;
    764       break;
    765     }
    766   }
    767 
    768   return false;
    769 }
    770 
    771 namespace {
    772 
    773 // Callback to only accept typo corrections that refer to parameter packs.
    774 class ParameterPackValidatorCCC : public CorrectionCandidateCallback {
    775  public:
    776   virtual bool ValidateCandidate(const TypoCorrection &candidate) {
    777     NamedDecl *ND = candidate.getCorrectionDecl();
    778     return ND && ND->isParameterPack();
    779   }
    780 };
    781 
    782 }
    783 
    784 /// \brief Called when an expression computing the size of a parameter pack
    785 /// is parsed.
    786 ///
    787 /// \code
    788 /// template<typename ...Types> struct count {
    789 ///   static const unsigned value = sizeof...(Types);
    790 /// };
    791 /// \endcode
    792 ///
    793 //
    794 /// \param OpLoc The location of the "sizeof" keyword.
    795 /// \param Name The name of the parameter pack whose size will be determined.
    796 /// \param NameLoc The source location of the name of the parameter pack.
    797 /// \param RParenLoc The location of the closing parentheses.
    798 ExprResult Sema::ActOnSizeofParameterPackExpr(Scope *S,
    799                                               SourceLocation OpLoc,
    800                                               IdentifierInfo &Name,
    801                                               SourceLocation NameLoc,
    802                                               SourceLocation RParenLoc) {
    803   // C++0x [expr.sizeof]p5:
    804   //   The identifier in a sizeof... expression shall name a parameter pack.
    805   LookupResult R(*this, &Name, NameLoc, LookupOrdinaryName);
    806   LookupName(R, S);
    807 
    808   NamedDecl *ParameterPack = 0;
    809   ParameterPackValidatorCCC Validator;
    810   switch (R.getResultKind()) {
    811   case LookupResult::Found:
    812     ParameterPack = R.getFoundDecl();
    813     break;
    814 
    815   case LookupResult::NotFound:
    816   case LookupResult::NotFoundInCurrentInstantiation:
    817     if (TypoCorrection Corrected = CorrectTypo(R.getLookupNameInfo(),
    818                                                R.getLookupKind(), S, 0,
    819                                                Validator)) {
    820       std::string CorrectedQuotedStr(Corrected.getQuoted(getLangOpts()));
    821       ParameterPack = Corrected.getCorrectionDecl();
    822       Diag(NameLoc, diag::err_sizeof_pack_no_pack_name_suggest)
    823         << &Name << CorrectedQuotedStr
    824         << FixItHint::CreateReplacement(
    825             NameLoc, Corrected.getAsString(getLangOpts()));
    826       Diag(ParameterPack->getLocation(), diag::note_parameter_pack_here)
    827         << CorrectedQuotedStr;
    828     }
    829 
    830   case LookupResult::FoundOverloaded:
    831   case LookupResult::FoundUnresolvedValue:
    832     break;
    833 
    834   case LookupResult::Ambiguous:
    835     DiagnoseAmbiguousLookup(R);
    836     return ExprError();
    837   }
    838 
    839   if (!ParameterPack || !ParameterPack->isParameterPack()) {
    840     Diag(NameLoc, diag::err_sizeof_pack_no_pack_name)
    841       << &Name;
    842     return ExprError();
    843   }
    844 
    845   MarkAnyDeclReferenced(OpLoc, ParameterPack, true);
    846 
    847   return new (Context) SizeOfPackExpr(Context.getSizeType(), OpLoc,
    848                                       ParameterPack, NameLoc, RParenLoc);
    849 }
    850