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 "TypeLocBuilder.h"
     14 #include "clang/AST/Expr.h"
     15 #include "clang/AST/RecursiveASTVisitor.h"
     16 #include "clang/AST/TypeLoc.h"
     17 #include "clang/Sema/Lookup.h"
     18 #include "clang/Sema/ParsedTemplate.h"
     19 #include "clang/Sema/ScopeInfo.h"
     20 #include "clang/Sema/SemaInternal.h"
     21 #include "clang/Sema/Template.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 Determine whether it's possible for an unexpanded parameter pack to
    201 /// be valid in this location. This only happens when we're in a declaration
    202 /// that is nested within an expression that could be expanded, such as a
    203 /// lambda-expression within a function call.
    204 ///
    205 /// This is conservatively correct, but may claim that some unexpanded packs are
    206 /// permitted when they are not.
    207 bool Sema::isUnexpandedParameterPackPermitted() {
    208   for (auto *SI : FunctionScopes)
    209     if (isa<sema::LambdaScopeInfo>(SI))
    210       return true;
    211   return false;
    212 }
    213 
    214 /// \brief Diagnose all of the unexpanded parameter packs in the given
    215 /// vector.
    216 bool
    217 Sema::DiagnoseUnexpandedParameterPacks(SourceLocation Loc,
    218                                        UnexpandedParameterPackContext UPPC,
    219                                  ArrayRef<UnexpandedParameterPack> Unexpanded) {
    220   if (Unexpanded.empty())
    221     return false;
    222 
    223   // If we are within a lambda expression, that lambda contains an unexpanded
    224   // parameter pack, and we are done.
    225   // FIXME: Store 'Unexpanded' on the lambda so we don't need to recompute it
    226   // later.
    227   for (unsigned N = FunctionScopes.size(); N; --N) {
    228     if (sema::LambdaScopeInfo *LSI =
    229           dyn_cast<sema::LambdaScopeInfo>(FunctionScopes[N-1])) {
    230       LSI->ContainsUnexpandedParameterPack = true;
    231       return false;
    232     }
    233   }
    234 
    235   SmallVector<SourceLocation, 4> Locations;
    236   SmallVector<IdentifierInfo *, 4> Names;
    237   llvm::SmallPtrSet<IdentifierInfo *, 4> NamesKnown;
    238 
    239   for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
    240     IdentifierInfo *Name = nullptr;
    241     if (const TemplateTypeParmType *TTP
    242           = Unexpanded[I].first.dyn_cast<const TemplateTypeParmType *>())
    243       Name = TTP->getIdentifier();
    244     else
    245       Name = Unexpanded[I].first.get<NamedDecl *>()->getIdentifier();
    246 
    247     if (Name && NamesKnown.insert(Name).second)
    248       Names.push_back(Name);
    249 
    250     if (Unexpanded[I].second.isValid())
    251       Locations.push_back(Unexpanded[I].second);
    252   }
    253 
    254   DiagnosticBuilder DB = Diag(Loc, diag::err_unexpanded_parameter_pack)
    255                          << (int)UPPC << (int)Names.size();
    256   for (size_t I = 0, E = std::min(Names.size(), (size_t)2); I != E; ++I)
    257     DB << Names[I];
    258 
    259   for (unsigned I = 0, N = Locations.size(); I != N; ++I)
    260     DB << SourceRange(Locations[I]);
    261   return true;
    262 }
    263 
    264 bool Sema::DiagnoseUnexpandedParameterPack(SourceLocation Loc,
    265                                            TypeSourceInfo *T,
    266                                          UnexpandedParameterPackContext UPPC) {
    267   // C++0x [temp.variadic]p5:
    268   //   An appearance of a name of a parameter pack that is not expanded is
    269   //   ill-formed.
    270   if (!T->getType()->containsUnexpandedParameterPack())
    271     return false;
    272 
    273   SmallVector<UnexpandedParameterPack, 2> Unexpanded;
    274   CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseTypeLoc(
    275                                                               T->getTypeLoc());
    276   assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
    277   return DiagnoseUnexpandedParameterPacks(Loc, UPPC, Unexpanded);
    278 }
    279 
    280 bool Sema::DiagnoseUnexpandedParameterPack(Expr *E,
    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 (!E->containsUnexpandedParameterPack())
    286     return false;
    287 
    288   SmallVector<UnexpandedParameterPack, 2> Unexpanded;
    289   CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseStmt(E);
    290   assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
    291   return DiagnoseUnexpandedParameterPacks(E->getLocStart(), UPPC, Unexpanded);
    292 }
    293 
    294 bool Sema::DiagnoseUnexpandedParameterPack(const CXXScopeSpec &SS,
    295                                         UnexpandedParameterPackContext UPPC) {
    296   // C++0x [temp.variadic]p5:
    297   //   An appearance of a name of a parameter pack that is not expanded is
    298   //   ill-formed.
    299   if (!SS.getScopeRep() ||
    300       !SS.getScopeRep()->containsUnexpandedParameterPack())
    301     return false;
    302 
    303   SmallVector<UnexpandedParameterPack, 2> Unexpanded;
    304   CollectUnexpandedParameterPacksVisitor(Unexpanded)
    305     .TraverseNestedNameSpecifier(SS.getScopeRep());
    306   assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
    307   return DiagnoseUnexpandedParameterPacks(SS.getRange().getBegin(),
    308                                           UPPC, Unexpanded);
    309 }
    310 
    311 bool Sema::DiagnoseUnexpandedParameterPack(const DeclarationNameInfo &NameInfo,
    312                                          UnexpandedParameterPackContext UPPC) {
    313   // C++0x [temp.variadic]p5:
    314   //   An appearance of a name of a parameter pack that is not expanded is
    315   //   ill-formed.
    316   switch (NameInfo.getName().getNameKind()) {
    317   case DeclarationName::Identifier:
    318   case DeclarationName::ObjCZeroArgSelector:
    319   case DeclarationName::ObjCOneArgSelector:
    320   case DeclarationName::ObjCMultiArgSelector:
    321   case DeclarationName::CXXOperatorName:
    322   case DeclarationName::CXXLiteralOperatorName:
    323   case DeclarationName::CXXUsingDirective:
    324     return false;
    325 
    326   case DeclarationName::CXXConstructorName:
    327   case DeclarationName::CXXDestructorName:
    328   case DeclarationName::CXXConversionFunctionName:
    329     // FIXME: We shouldn't need this null check!
    330     if (TypeSourceInfo *TSInfo = NameInfo.getNamedTypeInfo())
    331       return DiagnoseUnexpandedParameterPack(NameInfo.getLoc(), TSInfo, UPPC);
    332 
    333     if (!NameInfo.getName().getCXXNameType()->containsUnexpandedParameterPack())
    334       return false;
    335 
    336     break;
    337   }
    338 
    339   SmallVector<UnexpandedParameterPack, 2> Unexpanded;
    340   CollectUnexpandedParameterPacksVisitor(Unexpanded)
    341     .TraverseType(NameInfo.getName().getCXXNameType());
    342   assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
    343   return DiagnoseUnexpandedParameterPacks(NameInfo.getLoc(), UPPC, Unexpanded);
    344 }
    345 
    346 bool Sema::DiagnoseUnexpandedParameterPack(SourceLocation Loc,
    347                                            TemplateName Template,
    348                                        UnexpandedParameterPackContext UPPC) {
    349 
    350   if (Template.isNull() || !Template.containsUnexpandedParameterPack())
    351     return false;
    352 
    353   SmallVector<UnexpandedParameterPack, 2> Unexpanded;
    354   CollectUnexpandedParameterPacksVisitor(Unexpanded)
    355     .TraverseTemplateName(Template);
    356   assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
    357   return DiagnoseUnexpandedParameterPacks(Loc, UPPC, Unexpanded);
    358 }
    359 
    360 bool Sema::DiagnoseUnexpandedParameterPack(TemplateArgumentLoc Arg,
    361                                          UnexpandedParameterPackContext UPPC) {
    362   if (Arg.getArgument().isNull() ||
    363       !Arg.getArgument().containsUnexpandedParameterPack())
    364     return false;
    365 
    366   SmallVector<UnexpandedParameterPack, 2> Unexpanded;
    367   CollectUnexpandedParameterPacksVisitor(Unexpanded)
    368     .TraverseTemplateArgumentLoc(Arg);
    369   assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
    370   return DiagnoseUnexpandedParameterPacks(Arg.getLocation(), UPPC, Unexpanded);
    371 }
    372 
    373 void Sema::collectUnexpandedParameterPacks(TemplateArgument Arg,
    374                    SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
    375   CollectUnexpandedParameterPacksVisitor(Unexpanded)
    376     .TraverseTemplateArgument(Arg);
    377 }
    378 
    379 void Sema::collectUnexpandedParameterPacks(TemplateArgumentLoc Arg,
    380                    SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
    381   CollectUnexpandedParameterPacksVisitor(Unexpanded)
    382     .TraverseTemplateArgumentLoc(Arg);
    383 }
    384 
    385 void Sema::collectUnexpandedParameterPacks(QualType T,
    386                    SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
    387   CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseType(T);
    388 }
    389 
    390 void Sema::collectUnexpandedParameterPacks(TypeLoc TL,
    391                    SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
    392   CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseTypeLoc(TL);
    393 }
    394 
    395 void Sema::collectUnexpandedParameterPacks(CXXScopeSpec &SS,
    396                                            SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
    397   NestedNameSpecifier *Qualifier = SS.getScopeRep();
    398   if (!Qualifier)
    399     return;
    400 
    401   NestedNameSpecifierLoc QualifierLoc(Qualifier, SS.location_data());
    402   CollectUnexpandedParameterPacksVisitor(Unexpanded)
    403     .TraverseNestedNameSpecifierLoc(QualifierLoc);
    404 }
    405 
    406 void Sema::collectUnexpandedParameterPacks(const DeclarationNameInfo &NameInfo,
    407                          SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
    408   CollectUnexpandedParameterPacksVisitor(Unexpanded)
    409     .TraverseDeclarationNameInfo(NameInfo);
    410 }
    411 
    412 
    413 ParsedTemplateArgument
    414 Sema::ActOnPackExpansion(const ParsedTemplateArgument &Arg,
    415                          SourceLocation EllipsisLoc) {
    416   if (Arg.isInvalid())
    417     return Arg;
    418 
    419   switch (Arg.getKind()) {
    420   case ParsedTemplateArgument::Type: {
    421     TypeResult Result = ActOnPackExpansion(Arg.getAsType(), EllipsisLoc);
    422     if (Result.isInvalid())
    423       return ParsedTemplateArgument();
    424 
    425     return ParsedTemplateArgument(Arg.getKind(), Result.get().getAsOpaquePtr(),
    426                                   Arg.getLocation());
    427   }
    428 
    429   case ParsedTemplateArgument::NonType: {
    430     ExprResult Result = ActOnPackExpansion(Arg.getAsExpr(), EllipsisLoc);
    431     if (Result.isInvalid())
    432       return ParsedTemplateArgument();
    433 
    434     return ParsedTemplateArgument(Arg.getKind(), Result.get(),
    435                                   Arg.getLocation());
    436   }
    437 
    438   case ParsedTemplateArgument::Template:
    439     if (!Arg.getAsTemplate().get().containsUnexpandedParameterPack()) {
    440       SourceRange R(Arg.getLocation());
    441       if (Arg.getScopeSpec().isValid())
    442         R.setBegin(Arg.getScopeSpec().getBeginLoc());
    443       Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
    444         << R;
    445       return ParsedTemplateArgument();
    446     }
    447 
    448     return Arg.getTemplatePackExpansion(EllipsisLoc);
    449   }
    450   llvm_unreachable("Unhandled template argument kind?");
    451 }
    452 
    453 TypeResult Sema::ActOnPackExpansion(ParsedType Type,
    454                                     SourceLocation EllipsisLoc) {
    455   TypeSourceInfo *TSInfo;
    456   GetTypeFromParser(Type, &TSInfo);
    457   if (!TSInfo)
    458     return true;
    459 
    460   TypeSourceInfo *TSResult = CheckPackExpansion(TSInfo, EllipsisLoc, None);
    461   if (!TSResult)
    462     return true;
    463 
    464   return CreateParsedType(TSResult->getType(), TSResult);
    465 }
    466 
    467 TypeSourceInfo *
    468 Sema::CheckPackExpansion(TypeSourceInfo *Pattern, SourceLocation EllipsisLoc,
    469                          Optional<unsigned> NumExpansions) {
    470   // Create the pack expansion type and source-location information.
    471   QualType Result = CheckPackExpansion(Pattern->getType(),
    472                                        Pattern->getTypeLoc().getSourceRange(),
    473                                        EllipsisLoc, NumExpansions);
    474   if (Result.isNull())
    475     return nullptr;
    476 
    477   TypeLocBuilder TLB;
    478   TLB.pushFullCopy(Pattern->getTypeLoc());
    479   PackExpansionTypeLoc TL = TLB.push<PackExpansionTypeLoc>(Result);
    480   TL.setEllipsisLoc(EllipsisLoc);
    481 
    482   return TLB.getTypeSourceInfo(Context, Result);
    483 }
    484 
    485 QualType Sema::CheckPackExpansion(QualType Pattern, SourceRange PatternRange,
    486                                   SourceLocation EllipsisLoc,
    487                                   Optional<unsigned> NumExpansions) {
    488   // C++0x [temp.variadic]p5:
    489   //   The pattern of a pack expansion shall name one or more
    490   //   parameter packs that are not expanded by a nested pack
    491   //   expansion.
    492   if (!Pattern->containsUnexpandedParameterPack()) {
    493     Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
    494       << PatternRange;
    495     return QualType();
    496   }
    497 
    498   return Context.getPackExpansionType(Pattern, NumExpansions);
    499 }
    500 
    501 ExprResult Sema::ActOnPackExpansion(Expr *Pattern, SourceLocation EllipsisLoc) {
    502   return CheckPackExpansion(Pattern, EllipsisLoc, None);
    503 }
    504 
    505 ExprResult Sema::CheckPackExpansion(Expr *Pattern, SourceLocation EllipsisLoc,
    506                                     Optional<unsigned> NumExpansions) {
    507   if (!Pattern)
    508     return ExprError();
    509 
    510   // C++0x [temp.variadic]p5:
    511   //   The pattern of a pack expansion shall name one or more
    512   //   parameter packs that are not expanded by a nested pack
    513   //   expansion.
    514   if (!Pattern->containsUnexpandedParameterPack()) {
    515     Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
    516     << Pattern->getSourceRange();
    517     return ExprError();
    518   }
    519 
    520   // Create the pack expansion expression and source-location information.
    521   return new (Context)
    522     PackExpansionExpr(Context.DependentTy, Pattern, EllipsisLoc, NumExpansions);
    523 }
    524 
    525 /// \brief Retrieve the depth and index of a parameter pack.
    526 static std::pair<unsigned, unsigned>
    527 getDepthAndIndex(NamedDecl *ND) {
    528   if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(ND))
    529     return std::make_pair(TTP->getDepth(), TTP->getIndex());
    530 
    531   if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(ND))
    532     return std::make_pair(NTTP->getDepth(), NTTP->getIndex());
    533 
    534   TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(ND);
    535   return std::make_pair(TTP->getDepth(), TTP->getIndex());
    536 }
    537 
    538 bool Sema::CheckParameterPacksForExpansion(
    539     SourceLocation EllipsisLoc, SourceRange PatternRange,
    540     ArrayRef<UnexpandedParameterPack> Unexpanded,
    541     const MultiLevelTemplateArgumentList &TemplateArgs, bool &ShouldExpand,
    542     bool &RetainExpansion, Optional<unsigned> &NumExpansions) {
    543   ShouldExpand = true;
    544   RetainExpansion = false;
    545   std::pair<IdentifierInfo *, SourceLocation> FirstPack;
    546   bool HaveFirstPack = false;
    547 
    548   for (ArrayRef<UnexpandedParameterPack>::iterator i = Unexpanded.begin(),
    549                                                  end = Unexpanded.end();
    550                                                   i != end; ++i) {
    551     // Compute the depth and index for this parameter pack.
    552     unsigned Depth = 0, Index = 0;
    553     IdentifierInfo *Name;
    554     bool IsFunctionParameterPack = false;
    555 
    556     if (const TemplateTypeParmType *TTP
    557         = i->first.dyn_cast<const TemplateTypeParmType *>()) {
    558       Depth = TTP->getDepth();
    559       Index = TTP->getIndex();
    560       Name = TTP->getIdentifier();
    561     } else {
    562       NamedDecl *ND = i->first.get<NamedDecl *>();
    563       if (isa<ParmVarDecl>(ND))
    564         IsFunctionParameterPack = true;
    565       else
    566         std::tie(Depth, Index) = getDepthAndIndex(ND);
    567 
    568       Name = ND->getIdentifier();
    569     }
    570 
    571     // Determine the size of this argument pack.
    572     unsigned NewPackSize;
    573     if (IsFunctionParameterPack) {
    574       // Figure out whether we're instantiating to an argument pack or not.
    575       typedef LocalInstantiationScope::DeclArgumentPack DeclArgumentPack;
    576 
    577       llvm::PointerUnion<Decl *, DeclArgumentPack *> *Instantiation
    578         = CurrentInstantiationScope->findInstantiationOf(
    579                                         i->first.get<NamedDecl *>());
    580       if (Instantiation->is<DeclArgumentPack *>()) {
    581         // We could expand this function parameter pack.
    582         NewPackSize = Instantiation->get<DeclArgumentPack *>()->size();
    583       } else {
    584         // We can't expand this function parameter pack, so we can't expand
    585         // the pack expansion.
    586         ShouldExpand = false;
    587         continue;
    588       }
    589     } else {
    590       // If we don't have a template argument at this depth/index, then we
    591       // cannot expand the pack expansion. Make a note of this, but we still
    592       // want to check any parameter packs we *do* have arguments for.
    593       if (Depth >= TemplateArgs.getNumLevels() ||
    594           !TemplateArgs.hasTemplateArgument(Depth, Index)) {
    595         ShouldExpand = false;
    596         continue;
    597       }
    598 
    599       // Determine the size of the argument pack.
    600       NewPackSize = TemplateArgs(Depth, Index).pack_size();
    601     }
    602 
    603     // C++0x [temp.arg.explicit]p9:
    604     //   Template argument deduction can extend the sequence of template
    605     //   arguments corresponding to a template parameter pack, even when the
    606     //   sequence contains explicitly specified template arguments.
    607     if (!IsFunctionParameterPack && CurrentInstantiationScope) {
    608       if (NamedDecl *PartialPack
    609                     = CurrentInstantiationScope->getPartiallySubstitutedPack()){
    610         unsigned PartialDepth, PartialIndex;
    611         std::tie(PartialDepth, PartialIndex) = getDepthAndIndex(PartialPack);
    612         if (PartialDepth == Depth && PartialIndex == Index)
    613           RetainExpansion = true;
    614       }
    615     }
    616 
    617     if (!NumExpansions) {
    618       // The is the first pack we've seen for which we have an argument.
    619       // Record it.
    620       NumExpansions = NewPackSize;
    621       FirstPack.first = Name;
    622       FirstPack.second = i->second;
    623       HaveFirstPack = true;
    624       continue;
    625     }
    626 
    627     if (NewPackSize != *NumExpansions) {
    628       // C++0x [temp.variadic]p5:
    629       //   All of the parameter packs expanded by a pack expansion shall have
    630       //   the same number of arguments specified.
    631       if (HaveFirstPack)
    632         Diag(EllipsisLoc, diag::err_pack_expansion_length_conflict)
    633           << FirstPack.first << Name << *NumExpansions << NewPackSize
    634           << SourceRange(FirstPack.second) << SourceRange(i->second);
    635       else
    636         Diag(EllipsisLoc, diag::err_pack_expansion_length_conflict_multilevel)
    637           << Name << *NumExpansions << NewPackSize
    638           << SourceRange(i->second);
    639       return true;
    640     }
    641   }
    642 
    643   return false;
    644 }
    645 
    646 Optional<unsigned> Sema::getNumArgumentsInExpansion(QualType T,
    647                           const MultiLevelTemplateArgumentList &TemplateArgs) {
    648   QualType Pattern = cast<PackExpansionType>(T)->getPattern();
    649   SmallVector<UnexpandedParameterPack, 2> Unexpanded;
    650   CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseType(Pattern);
    651 
    652   Optional<unsigned> Result;
    653   for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
    654     // Compute the depth and index for this parameter pack.
    655     unsigned Depth;
    656     unsigned Index;
    657 
    658     if (const TemplateTypeParmType *TTP
    659           = Unexpanded[I].first.dyn_cast<const TemplateTypeParmType *>()) {
    660       Depth = TTP->getDepth();
    661       Index = TTP->getIndex();
    662     } else {
    663       NamedDecl *ND = Unexpanded[I].first.get<NamedDecl *>();
    664       if (isa<ParmVarDecl>(ND)) {
    665         // Function parameter pack.
    666         typedef LocalInstantiationScope::DeclArgumentPack DeclArgumentPack;
    667 
    668         llvm::PointerUnion<Decl *, DeclArgumentPack *> *Instantiation
    669           = CurrentInstantiationScope->findInstantiationOf(
    670                                         Unexpanded[I].first.get<NamedDecl *>());
    671         if (Instantiation->is<Decl*>())
    672           // The pattern refers to an unexpanded pack. We're not ready to expand
    673           // this pack yet.
    674           return None;
    675 
    676         unsigned Size = Instantiation->get<DeclArgumentPack *>()->size();
    677         assert((!Result || *Result == Size) && "inconsistent pack sizes");
    678         Result = Size;
    679         continue;
    680       }
    681 
    682       std::tie(Depth, Index) = getDepthAndIndex(ND);
    683     }
    684     if (Depth >= TemplateArgs.getNumLevels() ||
    685         !TemplateArgs.hasTemplateArgument(Depth, Index))
    686       // The pattern refers to an unknown template argument. We're not ready to
    687       // expand this pack yet.
    688       return None;
    689 
    690     // Determine the size of the argument pack.
    691     unsigned Size = TemplateArgs(Depth, Index).pack_size();
    692     assert((!Result || *Result == Size) && "inconsistent pack sizes");
    693     Result = Size;
    694   }
    695 
    696   return Result;
    697 }
    698 
    699 bool Sema::containsUnexpandedParameterPacks(Declarator &D) {
    700   const DeclSpec &DS = D.getDeclSpec();
    701   switch (DS.getTypeSpecType()) {
    702   case TST_typename:
    703   case TST_typeofType:
    704   case TST_underlyingType:
    705   case TST_atomic: {
    706     QualType T = DS.getRepAsType().get();
    707     if (!T.isNull() && T->containsUnexpandedParameterPack())
    708       return true;
    709     break;
    710   }
    711 
    712   case TST_typeofExpr:
    713   case TST_decltype:
    714     if (DS.getRepAsExpr() &&
    715         DS.getRepAsExpr()->containsUnexpandedParameterPack())
    716       return true;
    717     break;
    718 
    719   case TST_unspecified:
    720   case TST_void:
    721   case TST_char:
    722   case TST_wchar:
    723   case TST_char16:
    724   case TST_char32:
    725   case TST_int:
    726   case TST_int128:
    727   case TST_half:
    728   case TST_float:
    729   case TST_double:
    730   case TST_float128:
    731   case TST_bool:
    732   case TST_decimal32:
    733   case TST_decimal64:
    734   case TST_decimal128:
    735   case TST_enum:
    736   case TST_union:
    737   case TST_struct:
    738   case TST_interface:
    739   case TST_class:
    740   case TST_auto:
    741   case TST_auto_type:
    742   case TST_decltype_auto:
    743 #define GENERIC_IMAGE_TYPE(ImgType, Id) case TST_##ImgType##_t:
    744 #include "clang/Basic/OpenCLImageTypes.def"
    745   case TST_unknown_anytype:
    746   case TST_error:
    747     break;
    748   }
    749 
    750   for (unsigned I = 0, N = D.getNumTypeObjects(); I != N; ++I) {
    751     const DeclaratorChunk &Chunk = D.getTypeObject(I);
    752     switch (Chunk.Kind) {
    753     case DeclaratorChunk::Pointer:
    754     case DeclaratorChunk::Reference:
    755     case DeclaratorChunk::Paren:
    756     case DeclaratorChunk::Pipe:
    757     case DeclaratorChunk::BlockPointer:
    758       // These declarator chunks cannot contain any parameter packs.
    759       break;
    760 
    761     case DeclaratorChunk::Array:
    762       if (Chunk.Arr.NumElts &&
    763           Chunk.Arr.NumElts->containsUnexpandedParameterPack())
    764         return true;
    765       break;
    766     case DeclaratorChunk::Function:
    767       for (unsigned i = 0, e = Chunk.Fun.NumParams; i != e; ++i) {
    768         ParmVarDecl *Param = cast<ParmVarDecl>(Chunk.Fun.Params[i].Param);
    769         QualType ParamTy = Param->getType();
    770         assert(!ParamTy.isNull() && "Couldn't parse type?");
    771         if (ParamTy->containsUnexpandedParameterPack()) return true;
    772       }
    773 
    774       if (Chunk.Fun.getExceptionSpecType() == EST_Dynamic) {
    775         for (unsigned i = 0; i != Chunk.Fun.NumExceptions; ++i) {
    776           if (Chunk.Fun.Exceptions[i]
    777                   .Ty.get()
    778                   ->containsUnexpandedParameterPack())
    779             return true;
    780         }
    781       } else if (Chunk.Fun.getExceptionSpecType() == EST_ComputedNoexcept &&
    782                  Chunk.Fun.NoexceptExpr->containsUnexpandedParameterPack())
    783         return true;
    784 
    785       if (Chunk.Fun.hasTrailingReturnType()) {
    786         QualType T = Chunk.Fun.getTrailingReturnType().get();
    787 	if (!T.isNull() && T->containsUnexpandedParameterPack())
    788 	  return true;
    789       }
    790       break;
    791 
    792     case DeclaratorChunk::MemberPointer:
    793       if (Chunk.Mem.Scope().getScopeRep() &&
    794           Chunk.Mem.Scope().getScopeRep()->containsUnexpandedParameterPack())
    795         return true;
    796       break;
    797     }
    798   }
    799 
    800   return false;
    801 }
    802 
    803 namespace {
    804 
    805 // Callback to only accept typo corrections that refer to parameter packs.
    806 class ParameterPackValidatorCCC : public CorrectionCandidateCallback {
    807  public:
    808   bool ValidateCandidate(const TypoCorrection &candidate) override {
    809     NamedDecl *ND = candidate.getCorrectionDecl();
    810     return ND && ND->isParameterPack();
    811   }
    812 };
    813 
    814 }
    815 
    816 /// \brief Called when an expression computing the size of a parameter pack
    817 /// is parsed.
    818 ///
    819 /// \code
    820 /// template<typename ...Types> struct count {
    821 ///   static const unsigned value = sizeof...(Types);
    822 /// };
    823 /// \endcode
    824 ///
    825 //
    826 /// \param OpLoc The location of the "sizeof" keyword.
    827 /// \param Name The name of the parameter pack whose size will be determined.
    828 /// \param NameLoc The source location of the name of the parameter pack.
    829 /// \param RParenLoc The location of the closing parentheses.
    830 ExprResult Sema::ActOnSizeofParameterPackExpr(Scope *S,
    831                                               SourceLocation OpLoc,
    832                                               IdentifierInfo &Name,
    833                                               SourceLocation NameLoc,
    834                                               SourceLocation RParenLoc) {
    835   // C++0x [expr.sizeof]p5:
    836   //   The identifier in a sizeof... expression shall name a parameter pack.
    837   LookupResult R(*this, &Name, NameLoc, LookupOrdinaryName);
    838   LookupName(R, S);
    839 
    840   NamedDecl *ParameterPack = nullptr;
    841   switch (R.getResultKind()) {
    842   case LookupResult::Found:
    843     ParameterPack = R.getFoundDecl();
    844     break;
    845 
    846   case LookupResult::NotFound:
    847   case LookupResult::NotFoundInCurrentInstantiation:
    848     if (TypoCorrection Corrected =
    849             CorrectTypo(R.getLookupNameInfo(), R.getLookupKind(), S, nullptr,
    850                         llvm::make_unique<ParameterPackValidatorCCC>(),
    851                         CTK_ErrorRecovery)) {
    852       diagnoseTypo(Corrected,
    853                    PDiag(diag::err_sizeof_pack_no_pack_name_suggest) << &Name,
    854                    PDiag(diag::note_parameter_pack_here));
    855       ParameterPack = Corrected.getCorrectionDecl();
    856     }
    857 
    858   case LookupResult::FoundOverloaded:
    859   case LookupResult::FoundUnresolvedValue:
    860     break;
    861 
    862   case LookupResult::Ambiguous:
    863     DiagnoseAmbiguousLookup(R);
    864     return ExprError();
    865   }
    866 
    867   if (!ParameterPack || !ParameterPack->isParameterPack()) {
    868     Diag(NameLoc, diag::err_sizeof_pack_no_pack_name)
    869       << &Name;
    870     return ExprError();
    871   }
    872 
    873   MarkAnyDeclReferenced(OpLoc, ParameterPack, true);
    874 
    875   return SizeOfPackExpr::Create(Context, OpLoc, ParameterPack, NameLoc,
    876                                 RParenLoc);
    877 }
    878 
    879 TemplateArgumentLoc
    880 Sema::getTemplateArgumentPackExpansionPattern(
    881       TemplateArgumentLoc OrigLoc,
    882       SourceLocation &Ellipsis, Optional<unsigned> &NumExpansions) const {
    883   const TemplateArgument &Argument = OrigLoc.getArgument();
    884   assert(Argument.isPackExpansion());
    885   switch (Argument.getKind()) {
    886   case TemplateArgument::Type: {
    887     // FIXME: We shouldn't ever have to worry about missing
    888     // type-source info!
    889     TypeSourceInfo *ExpansionTSInfo = OrigLoc.getTypeSourceInfo();
    890     if (!ExpansionTSInfo)
    891       ExpansionTSInfo = Context.getTrivialTypeSourceInfo(Argument.getAsType(),
    892                                                          Ellipsis);
    893     PackExpansionTypeLoc Expansion =
    894         ExpansionTSInfo->getTypeLoc().castAs<PackExpansionTypeLoc>();
    895     Ellipsis = Expansion.getEllipsisLoc();
    896 
    897     TypeLoc Pattern = Expansion.getPatternLoc();
    898     NumExpansions = Expansion.getTypePtr()->getNumExpansions();
    899 
    900     // We need to copy the TypeLoc because TemplateArgumentLocs store a
    901     // TypeSourceInfo.
    902     // FIXME: Find some way to avoid the copy?
    903     TypeLocBuilder TLB;
    904     TLB.pushFullCopy(Pattern);
    905     TypeSourceInfo *PatternTSInfo =
    906         TLB.getTypeSourceInfo(Context, Pattern.getType());
    907     return TemplateArgumentLoc(TemplateArgument(Pattern.getType()),
    908                                PatternTSInfo);
    909   }
    910 
    911   case TemplateArgument::Expression: {
    912     PackExpansionExpr *Expansion
    913       = cast<PackExpansionExpr>(Argument.getAsExpr());
    914     Expr *Pattern = Expansion->getPattern();
    915     Ellipsis = Expansion->getEllipsisLoc();
    916     NumExpansions = Expansion->getNumExpansions();
    917     return TemplateArgumentLoc(Pattern, Pattern);
    918   }
    919 
    920   case TemplateArgument::TemplateExpansion:
    921     Ellipsis = OrigLoc.getTemplateEllipsisLoc();
    922     NumExpansions = Argument.getNumTemplateExpansions();
    923     return TemplateArgumentLoc(Argument.getPackExpansionPattern(),
    924                                OrigLoc.getTemplateQualifierLoc(),
    925                                OrigLoc.getTemplateNameLoc());
    926 
    927   case TemplateArgument::Declaration:
    928   case TemplateArgument::NullPtr:
    929   case TemplateArgument::Template:
    930   case TemplateArgument::Integral:
    931   case TemplateArgument::Pack:
    932   case TemplateArgument::Null:
    933     return TemplateArgumentLoc();
    934   }
    935 
    936   llvm_unreachable("Invalid TemplateArgument Kind!");
    937 }
    938 
    939 static void CheckFoldOperand(Sema &S, Expr *E) {
    940   if (!E)
    941     return;
    942 
    943   E = E->IgnoreImpCasts();
    944   if (isa<BinaryOperator>(E) || isa<AbstractConditionalOperator>(E)) {
    945     S.Diag(E->getExprLoc(), diag::err_fold_expression_bad_operand)
    946         << E->getSourceRange()
    947         << FixItHint::CreateInsertion(E->getLocStart(), "(")
    948         << FixItHint::CreateInsertion(E->getLocEnd(), ")");
    949   }
    950 }
    951 
    952 ExprResult Sema::ActOnCXXFoldExpr(SourceLocation LParenLoc, Expr *LHS,
    953                                   tok::TokenKind Operator,
    954                                   SourceLocation EllipsisLoc, Expr *RHS,
    955                                   SourceLocation RParenLoc) {
    956   // LHS and RHS must be cast-expressions. We allow an arbitrary expression
    957   // in the parser and reduce down to just cast-expressions here.
    958   CheckFoldOperand(*this, LHS);
    959   CheckFoldOperand(*this, RHS);
    960 
    961   // [expr.prim.fold]p3:
    962   //   In a binary fold, op1 and op2 shall be the same fold-operator, and
    963   //   either e1 shall contain an unexpanded parameter pack or e2 shall contain
    964   //   an unexpanded parameter pack, but not both.
    965   if (LHS && RHS &&
    966       LHS->containsUnexpandedParameterPack() ==
    967           RHS->containsUnexpandedParameterPack()) {
    968     return Diag(EllipsisLoc,
    969                 LHS->containsUnexpandedParameterPack()
    970                     ? diag::err_fold_expression_packs_both_sides
    971                     : diag::err_pack_expansion_without_parameter_packs)
    972         << LHS->getSourceRange() << RHS->getSourceRange();
    973   }
    974 
    975   // [expr.prim.fold]p2:
    976   //   In a unary fold, the cast-expression shall contain an unexpanded
    977   //   parameter pack.
    978   if (!LHS || !RHS) {
    979     Expr *Pack = LHS ? LHS : RHS;
    980     assert(Pack && "fold expression with neither LHS nor RHS");
    981     if (!Pack->containsUnexpandedParameterPack())
    982       return Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
    983              << Pack->getSourceRange();
    984   }
    985 
    986   BinaryOperatorKind Opc = ConvertTokenKindToBinaryOpcode(Operator);
    987   return BuildCXXFoldExpr(LParenLoc, LHS, Opc, EllipsisLoc, RHS, RParenLoc);
    988 }
    989 
    990 ExprResult Sema::BuildCXXFoldExpr(SourceLocation LParenLoc, Expr *LHS,
    991                                   BinaryOperatorKind Operator,
    992                                   SourceLocation EllipsisLoc, Expr *RHS,
    993                                   SourceLocation RParenLoc) {
    994   return new (Context) CXXFoldExpr(Context.DependentTy, LParenLoc, LHS,
    995                                    Operator, EllipsisLoc, RHS, RParenLoc);
    996 }
    997 
    998 ExprResult Sema::BuildEmptyCXXFoldExpr(SourceLocation EllipsisLoc,
    999                                        BinaryOperatorKind Operator) {
   1000   // [temp.variadic]p9:
   1001   //   If N is zero for a unary fold-expression, the value of the expression is
   1002   //       &&  ->  true
   1003   //       ||  ->  false
   1004   //       ,   ->  void()
   1005   //   if the operator is not listed [above], the instantiation is ill-formed.
   1006   //
   1007   // Note that we need to use something like int() here, not merely 0, to
   1008   // prevent the result from being a null pointer constant.
   1009   QualType ScalarType;
   1010   switch (Operator) {
   1011   case BO_LOr:
   1012     return ActOnCXXBoolLiteral(EllipsisLoc, tok::kw_false);
   1013   case BO_LAnd:
   1014     return ActOnCXXBoolLiteral(EllipsisLoc, tok::kw_true);
   1015   case BO_Comma:
   1016     ScalarType = Context.VoidTy;
   1017     break;
   1018 
   1019   default:
   1020     return Diag(EllipsisLoc, diag::err_fold_expression_empty)
   1021         << BinaryOperator::getOpcodeStr(Operator);
   1022   }
   1023 
   1024   return new (Context) CXXScalarValueInitExpr(
   1025       ScalarType, Context.getTrivialTypeSourceInfo(ScalarType, EllipsisLoc),
   1026       EllipsisLoc);
   1027 }
   1028