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

   1 //===------- SemaTemplateVariadic.cpp - C++ Variadic Templates ------------===/
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //===----------------------------------------------------------------------===/
   8 //
   9 //  This file implements semantic analysis for C++0x variadic templates.
  10 //===----------------------------------------------------------------------===/
  11
  12 #include "clang/Sema/Sema.h"
  13 #include "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(
 396     NestedNameSpecifierLoc NNS,
 397     SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
 398   CollectUnexpandedParameterPacksVisitor(Unexpanded)
 399       .TraverseNestedNameSpecifierLoc(NNS);
 400 }
 401
 402 void Sema::collectUnexpandedParameterPacks(
 403     const DeclarationNameInfo &NameInfo,
 404     SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
 405   CollectUnexpandedParameterPacksVisitor(Unexpanded)
 406     .TraverseDeclarationNameInfo(NameInfo);
 407 }
 408
 409
 410 ParsedTemplateArgument
 411 Sema::ActOnPackExpansion(const ParsedTemplateArgument &Arg,
 412                          SourceLocation EllipsisLoc) {
 413   if (Arg.isInvalid())
 414     return Arg;
 415
 416   switch (Arg.getKind()) {
 417   case ParsedTemplateArgument::Type: {
 418     TypeResult Result = ActOnPackExpansion(Arg.getAsType(), EllipsisLoc);
 419     if (Result.isInvalid())
 420       return ParsedTemplateArgument();
 421
 422     return ParsedTemplateArgument(Arg.getKind(), Result.get().getAsOpaquePtr(),
 423                                   Arg.getLocation());
 424   }
 425
 426   case ParsedTemplateArgument::NonType: {
 427     ExprResult Result = ActOnPackExpansion(Arg.getAsExpr(), EllipsisLoc);
 428     if (Result.isInvalid())
 429       return ParsedTemplateArgument();
 430
 431     return ParsedTemplateArgument(Arg.getKind(), Result.get(),
 432                                   Arg.getLocation());
 433   }
 434
 435   case ParsedTemplateArgument::Template:
 436     if (!Arg.getAsTemplate().get().containsUnexpandedParameterPack()) {
 437       SourceRange R(Arg.getLocation());
 438       if (Arg.getScopeSpec().isValid())
 439         R.setBegin(Arg.getScopeSpec().getBeginLoc());
 440       Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
 441         << R;
 442       return ParsedTemplateArgument();
 443     }
 444
 445     return Arg.getTemplatePackExpansion(EllipsisLoc);
 446   }
 447   llvm_unreachable("Unhandled template argument kind?");
 448 }
 449
 450 TypeResult Sema::ActOnPackExpansion(ParsedType Type,
 451                                     SourceLocation EllipsisLoc) {
 452   TypeSourceInfo *TSInfo;
 453   GetTypeFromParser(Type, &TSInfo);
 454   if (!TSInfo)
 455     return true;
 456
 457   TypeSourceInfo *TSResult = CheckPackExpansion(TSInfo, EllipsisLoc, None);
 458   if (!TSResult)
 459     return true;
 460
 461   return CreateParsedType(TSResult->getType(), TSResult);
 462 }
 463
 464 TypeSourceInfo *
 465 Sema::CheckPackExpansion(TypeSourceInfo *Pattern, SourceLocation EllipsisLoc,
 466                          Optional<unsigned> NumExpansions) {
 467   // Create the pack expansion type and source-location information.
 468   QualType Result = CheckPackExpansion(Pattern->getType(),
 469                                        Pattern->getTypeLoc().getSourceRange(),
 470                                        EllipsisLoc, NumExpansions);
 471   if (Result.isNull())
 472     return nullptr;
 473
 474   TypeLocBuilder TLB;
 475   TLB.pushFullCopy(Pattern->getTypeLoc());
 476   PackExpansionTypeLoc TL = TLB.push<PackExpansionTypeLoc>(Result);
 477   TL.setEllipsisLoc(EllipsisLoc);
 478
 479   return TLB.getTypeSourceInfo(Context, Result);
 480 }
 481
 482 QualType Sema::CheckPackExpansion(QualType Pattern, SourceRange PatternRange,
 483                                   SourceLocation EllipsisLoc,
 484                                   Optional<unsigned> NumExpansions) {
 485   // C++0x [temp.variadic]p5:
 486   //   The pattern of a pack expansion shall name one or more
 487   //   parameter packs that are not expanded by a nested pack
 488   //   expansion.
 489   if (!Pattern->containsUnexpandedParameterPack()) {
 490     Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
 491       << PatternRange;
 492     return QualType();
 493   }
 494
 495   return Context.getPackExpansionType(Pattern, NumExpansions);
 496 }
 497
 498 ExprResult Sema::ActOnPackExpansion(Expr *Pattern, SourceLocation EllipsisLoc) {
 499   return CheckPackExpansion(Pattern, EllipsisLoc, None);
 500 }
 501
 502 ExprResult Sema::CheckPackExpansion(Expr *Pattern, SourceLocation EllipsisLoc,
 503                                     Optional<unsigned> NumExpansions) {
 504   if (!Pattern)
 505     return ExprError();
 506
 507   // C++0x [temp.variadic]p5:
 508   //   The pattern of a pack expansion shall name one or more
 509   //   parameter packs that are not expanded by a nested pack
 510   //   expansion.
 511   if (!Pattern->containsUnexpandedParameterPack()) {
 512     Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
 513     << Pattern->getSourceRange();
 514     return ExprError();
 515   }
 516
 517   // Create the pack expansion expression and source-location information.
 518   return new (Context)
 519     PackExpansionExpr(Context.DependentTy, Pattern, EllipsisLoc, NumExpansions);
 520 }
 521
 522 /// \brief Retrieve the depth and index of a parameter pack.
 523 static std::pair<unsigned, unsigned>
 524 getDepthAndIndex(NamedDecl *ND) {
 525   if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(ND))
 526     return std::make_pair(TTP->getDepth(), TTP->getIndex());
 527
 528   if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(ND))
 529     return std::make_pair(NTTP->getDepth(), NTTP->getIndex());
 530
 531   TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(ND);
 532   return std::make_pair(TTP->getDepth(), TTP->getIndex());
 533 }
 534
 535 bool Sema::CheckParameterPacksForExpansion(
 536     SourceLocation EllipsisLoc, SourceRange PatternRange,
 537     ArrayRef<UnexpandedParameterPack> Unexpanded,
 538     const MultiLevelTemplateArgumentList &TemplateArgs, bool &ShouldExpand,
 539     bool &RetainExpansion, Optional<unsigned> &NumExpansions) {
 540   ShouldExpand = true;
 541   RetainExpansion = false;
 542   std::pair<IdentifierInfo *, SourceLocation> FirstPack;
 543   bool HaveFirstPack = false;
 544
 545   for (ArrayRef<UnexpandedParameterPack>::iterator i = Unexpanded.begin(),
 546                                                  end = Unexpanded.end();
 547                                                   i != end; ++i) {
 548     // Compute the depth and index for this parameter pack.
 549     unsigned Depth = 0, Index = 0;
 550     IdentifierInfo *Name;
 551     bool IsFunctionParameterPack = false;
 552
 553     if (const TemplateTypeParmType *TTP
 554         = i->first.dyn_cast<const TemplateTypeParmType *>()) {
 555       Depth = TTP->getDepth();
 556       Index = TTP->getIndex();
 557       Name = TTP->getIdentifier();
 558     } else {
 559       NamedDecl *ND = i->first.get<NamedDecl *>();
 560       if (isa<ParmVarDecl>(ND))
 561         IsFunctionParameterPack = true;
 562       else
 563         std::tie(Depth, Index) = getDepthAndIndex(ND);
 564
 565       Name = ND->getIdentifier();
 566     }
 567
 568     // Determine the size of this argument pack.
 569     unsigned NewPackSize;
 570     if (IsFunctionParameterPack) {
 571       // Figure out whether we're instantiating to an argument pack or not.
 572       typedef LocalInstantiationScope::DeclArgumentPack DeclArgumentPack;
 573
 574       llvm::PointerUnion<Decl *, DeclArgumentPack *> *Instantiation
 575         = CurrentInstantiationScope->findInstantiationOf(
 576                                         i->first.get<NamedDecl *>());
 577       if (Instantiation->is<DeclArgumentPack *>()) {
 578         // We could expand this function parameter pack.
 579         NewPackSize = Instantiation->get<DeclArgumentPack *>()->size();
 580       } else {
 581         // We can't expand this function parameter pack, so we can't expand
 582         // the pack expansion.
 583         ShouldExpand = false;
 584         continue;
 585       }
 586     } else {
 587       // If we don't have a template argument at this depth/index, then we
 588       // cannot expand the pack expansion. Make a note of this, but we still
 589       // want to check any parameter packs we *do* have arguments for.
 590       if (Depth >= TemplateArgs.getNumLevels() ||
 591           !TemplateArgs.hasTemplateArgument(Depth, Index)) {
 592         ShouldExpand = false;
 593         continue;
 594       }
 595
 596       // Determine the size of the argument pack.
 597       NewPackSize = TemplateArgs(Depth, Index).pack_size();
 598     }
 599
 600     // C++0x [temp.arg.explicit]p9:
 601     //   Template argument deduction can extend the sequence of template
 602     //   arguments corresponding to a template parameter pack, even when the
 603     //   sequence contains explicitly specified template arguments.
 604     if (!IsFunctionParameterPack && CurrentInstantiationScope) {
 605       if (NamedDecl *PartialPack
 606                     = CurrentInstantiationScope->getPartiallySubstitutedPack()){
 607         unsigned PartialDepth, PartialIndex;
 608         std::tie(PartialDepth, PartialIndex) = getDepthAndIndex(PartialPack);
 609         if (PartialDepth == Depth && PartialIndex == Index)
 610           RetainExpansion = true;
 611       }
 612     }
 613
 614     if (!NumExpansions) {
 615       // The is the first pack we've seen for which we have an argument.
 616       // Record it.
 617       NumExpansions = NewPackSize;
 618       FirstPack.first = Name;
 619       FirstPack.second = i->second;
 620       HaveFirstPack = true;
 621       continue;
 622     }
 623
 624     if (NewPackSize != *NumExpansions) {
 625       // C++0x [temp.variadic]p5:
 626       //   All of the parameter packs expanded by a pack expansion shall have
 627       //   the same number of arguments specified.
 628       if (HaveFirstPack)
 629         Diag(EllipsisLoc, diag::err_pack_expansion_length_conflict)
 630           << FirstPack.first << Name << *NumExpansions << NewPackSize
 631           << SourceRange(FirstPack.second) << SourceRange(i->second);
 632       else
 633         Diag(EllipsisLoc, diag::err_pack_expansion_length_conflict_multilevel)
 634           << Name << *NumExpansions << NewPackSize
 635           << SourceRange(i->second);
 636       return true;
 637     }
 638   }
 639
 640   return false;
 641 }
 642
 643 Optional<unsigned> Sema::getNumArgumentsInExpansion(QualType T,
 644                           const MultiLevelTemplateArgumentList &TemplateArgs) {
 645   QualType Pattern = cast<PackExpansionType>(T)->getPattern();
 646   SmallVector<UnexpandedParameterPack, 2> Unexpanded;
 647   CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseType(Pattern);
 648
 649   Optional<unsigned> Result;
 650   for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
 651     // Compute the depth and index for this parameter pack.
 652     unsigned Depth;
 653     unsigned Index;
 654
 655     if (const TemplateTypeParmType *TTP
 656           = Unexpanded[I].first.dyn_cast<const TemplateTypeParmType *>()) {
 657       Depth = TTP->getDepth();
 658       Index = TTP->getIndex();
 659     } else {
 660       NamedDecl *ND = Unexpanded[I].first.get<NamedDecl *>();
 661       if (isa<ParmVarDecl>(ND)) {
 662         // Function parameter pack.
 663         typedef LocalInstantiationScope::DeclArgumentPack DeclArgumentPack;
 664
 665         llvm::PointerUnion<Decl *, DeclArgumentPack *> *Instantiation
 666           = CurrentInstantiationScope->findInstantiationOf(
 667                                         Unexpanded[I].first.get<NamedDecl *>());
 668         if (Instantiation->is<Decl*>())
 669           // The pattern refers to an unexpanded pack. We're not ready to expand
 670           // this pack yet.
 671           return None;
 672
 673         unsigned Size = Instantiation->get<DeclArgumentPack *>()->size();
 674         assert((!Result || *Result == Size) && "inconsistent pack sizes");
 675         Result = Size;
 676         continue;
 677       }
 678
 679       std::tie(Depth, Index) = getDepthAndIndex(ND);
 680     }
 681     if (Depth >= TemplateArgs.getNumLevels() ||
 682         !TemplateArgs.hasTemplateArgument(Depth, Index))
 683       // The pattern refers to an unknown template argument. We're not ready to
 684       // expand this pack yet.
 685       return None;
 686
 687     // Determine the size of the argument pack.
 688     unsigned Size = TemplateArgs(Depth, Index).pack_size();
 689     assert((!Result || *Result == Size) && "inconsistent pack sizes");
 690     Result = Size;
 691   }
 692
 693   return Result;
 694 }
 695
 696 bool Sema::containsUnexpandedParameterPacks(Declarator &D) {
 697   const DeclSpec &DS = D.getDeclSpec();
 698   switch (DS.getTypeSpecType()) {
 699   case TST_typename:
 700   case TST_typeofType:
 701   case TST_underlyingType:
 702   case TST_atomic: {
 703     QualType T = DS.getRepAsType().get();
 704     if (!T.isNull() && T->containsUnexpandedParameterPack())
 705       return true;
 706     break;
 707   }
 708
 709   case TST_typeofExpr:
 710   case TST_decltype:
 711     if (DS.getRepAsExpr() &&
 712         DS.getRepAsExpr()->containsUnexpandedParameterPack())
 713       return true;
 714     break;
 715
 716   case TST_unspecified:
 717   case TST_void:
 718   case TST_char:
 719   case TST_wchar:
 720   case TST_char16:
 721   case TST_char32:
 722   case TST_int:
 723   case TST_int128:
 724   case TST_half:
 725   case TST_float:
 726   case TST_double:
 727   case TST_float128:
 728   case TST_bool:
 729   case TST_decimal32:
 730   case TST_decimal64:
 731   case TST_decimal128:
 732   case TST_enum:
 733   case TST_union:
 734   case TST_struct:
 735   case TST_interface:
 736   case TST_class:
 737   case TST_auto:
 738   case TST_auto_type:
 739   case TST_decltype_auto:
 740 #define GENERIC_IMAGE_TYPE(ImgType, Id) case TST_##ImgType##_t:
 741 #include "clang/Basic/OpenCLImageTypes.def"
 742   case TST_unknown_anytype:
 743   case TST_error:
 744     break;
 745   }
 746
 747   for (unsigned I = 0, N = D.getNumTypeObjects(); I != N; ++I) {
 748     const DeclaratorChunk &Chunk = D.getTypeObject(I);
 749     switch (Chunk.Kind) {
 750     case DeclaratorChunk::Pointer:
 751     case DeclaratorChunk::Reference:
 752     case DeclaratorChunk::Paren:
 753     case DeclaratorChunk::Pipe:
 754     case DeclaratorChunk::BlockPointer:
 755       // These declarator chunks cannot contain any parameter packs.
 756       break;
 757
 758     case DeclaratorChunk::Array:
 759       if (Chunk.Arr.NumElts &&
 760           Chunk.Arr.NumElts->containsUnexpandedParameterPack())
 761         return true;
 762       break;
 763     case DeclaratorChunk::Function:
 764       for (unsigned i = 0, e = Chunk.Fun.NumParams; i != e; ++i) {
 765         ParmVarDecl *Param = cast<ParmVarDecl>(Chunk.Fun.Params[i].Param);
 766         QualType ParamTy = Param->getType();
 767         assert(!ParamTy.isNull() && "Couldn't parse type?");
 768         if (ParamTy->containsUnexpandedParameterPack()) return true;
 769       }
 770
 771       if (Chunk.Fun.getExceptionSpecType() == EST_Dynamic) {
 772         for (unsigned i = 0; i != Chunk.Fun.getNumExceptions(); ++i) {
 773           if (Chunk.Fun.Exceptions[i]
 774                   .Ty.get()
 775                   ->containsUnexpandedParameterPack())
 776             return true;
 777         }
 778       } else if (Chunk.Fun.getExceptionSpecType() == EST_ComputedNoexcept &&
 779                  Chunk.Fun.NoexceptExpr->containsUnexpandedParameterPack())
 780         return true;
 781
 782       if (Chunk.Fun.hasTrailingReturnType()) {
 783         QualType T = Chunk.Fun.getTrailingReturnType().get();
 784         if (!T.isNull() && T->containsUnexpandedParameterPack())
 785           return true;
 786       }
 787       break;
 788
 789     case DeclaratorChunk::MemberPointer:
 790       if (Chunk.Mem.Scope().getScopeRep() &&
 791           Chunk.Mem.Scope().getScopeRep()->containsUnexpandedParameterPack())
 792         return true;
 793       break;
 794     }
 795   }
 796
 797   return false;
 798 }
 799
 800 namespace {
 801
 802 // Callback to only accept typo corrections that refer to parameter packs.
 803 class ParameterPackValidatorCCC : public CorrectionCandidateCallback {
 804  public:
 805   bool ValidateCandidate(const TypoCorrection &candidate) override {
 806     NamedDecl *ND = candidate.getCorrectionDecl();
 807     return ND && ND->isParameterPack();
 808   }
 809 };
 810
 811 }
 812
 813 /// \brief Called when an expression computing the size of a parameter pack
 814 /// is parsed.
 815 ///
 816 /// \code
 817 /// template<typename ...Types> struct count {
 818 ///   static const unsigned value = sizeof...(Types);
 819 /// };
 820 /// \endcode
 821 ///
 822 //
 823 /// \param OpLoc The location of the "sizeof" keyword.
 824 /// \param Name The name of the parameter pack whose size will be determined.
 825 /// \param NameLoc The source location of the name of the parameter pack.
 826 /// \param RParenLoc The location of the closing parentheses.
 827 ExprResult Sema::ActOnSizeofParameterPackExpr(Scope *S,
 828                                               SourceLocation OpLoc,
 829                                               IdentifierInfo &Name,
 830                                               SourceLocation NameLoc,
 831                                               SourceLocation RParenLoc) {
 832   // C++0x [expr.sizeof]p5:
 833   //   The identifier in a sizeof... expression shall name a parameter pack.
 834   LookupResult R(*this, &Name, NameLoc, LookupOrdinaryName);
 835   LookupName(R, S);
 836
 837   NamedDecl *ParameterPack = nullptr;
 838   switch (R.getResultKind()) {
 839   case LookupResult::Found:
 840     ParameterPack = R.getFoundDecl();
 841     break;
 842
 843   case LookupResult::NotFound:
 844   case LookupResult::NotFoundInCurrentInstantiation:
 845     if (TypoCorrection Corrected =
 846             CorrectTypo(R.getLookupNameInfo(), R.getLookupKind(), S, nullptr,
 847                         llvm::make_unique<ParameterPackValidatorCCC>(),
 848                         CTK_ErrorRecovery)) {
 849       diagnoseTypo(Corrected,
 850                    PDiag(diag::err_sizeof_pack_no_pack_name_suggest) << &Name,
 851                    PDiag(diag::note_parameter_pack_here));
 852       ParameterPack = Corrected.getCorrectionDecl();
 853     }
 854
 855   case LookupResult::FoundOverloaded:
 856   case LookupResult::FoundUnresolvedValue:
 857     break;
 858
 859   case LookupResult::Ambiguous:
 860     DiagnoseAmbiguousLookup(R);
 861     return ExprError();
 862   }
 863
 864   if (!ParameterPack || !ParameterPack->isParameterPack()) {
 865     Diag(NameLoc, diag::err_sizeof_pack_no_pack_name)
 866       << &Name;
 867     return ExprError();
 868   }
 869
 870   MarkAnyDeclReferenced(OpLoc, ParameterPack, true);
 871
 872   return SizeOfPackExpr::Create(Context, OpLoc, ParameterPack, NameLoc,
 873                                 RParenLoc);
 874 }
 875
 876 TemplateArgumentLoc
 877 Sema::getTemplateArgumentPackExpansionPattern(
 878       TemplateArgumentLoc OrigLoc,
 879       SourceLocation &Ellipsis, Optional<unsigned> &NumExpansions) const {
 880   const TemplateArgument &Argument = OrigLoc.getArgument();
 881   assert(Argument.isPackExpansion());
 882   switch (Argument.getKind()) {
 883   case TemplateArgument::Type: {
 884     // FIXME: We shouldn't ever have to worry about missing
 885     // type-source info!
 886     TypeSourceInfo *ExpansionTSInfo = OrigLoc.getTypeSourceInfo();
 887     if (!ExpansionTSInfo)
 888       ExpansionTSInfo = Context.getTrivialTypeSourceInfo(Argument.getAsType(),
 889                                                          Ellipsis);
 890     PackExpansionTypeLoc Expansion =
 891         ExpansionTSInfo->getTypeLoc().castAs<PackExpansionTypeLoc>();
 892     Ellipsis = Expansion.getEllipsisLoc();
 893
 894     TypeLoc Pattern = Expansion.getPatternLoc();
 895     NumExpansions = Expansion.getTypePtr()->getNumExpansions();
 896
 897     // We need to copy the TypeLoc because TemplateArgumentLocs store a
 898     // TypeSourceInfo.
 899     // FIXME: Find some way to avoid the copy?
 900     TypeLocBuilder TLB;
 901     TLB.pushFullCopy(Pattern);
 902     TypeSourceInfo *PatternTSInfo =
 903         TLB.getTypeSourceInfo(Context, Pattern.getType());
 904     return TemplateArgumentLoc(TemplateArgument(Pattern.getType()),
 905                                PatternTSInfo);
 906   }
 907
 908   case TemplateArgument::Expression: {
 909     PackExpansionExpr *Expansion
 910       = cast<PackExpansionExpr>(Argument.getAsExpr());
 911     Expr *Pattern = Expansion->getPattern();
 912     Ellipsis = Expansion->getEllipsisLoc();
 913     NumExpansions = Expansion->getNumExpansions();
 914     return TemplateArgumentLoc(Pattern, Pattern);
 915   }
 916
 917   case TemplateArgument::TemplateExpansion:
 918     Ellipsis = OrigLoc.getTemplateEllipsisLoc();
 919     NumExpansions = Argument.getNumTemplateExpansions();
 920     return TemplateArgumentLoc(Argument.getPackExpansionPattern(),
 921                                OrigLoc.getTemplateQualifierLoc(),
 922                                OrigLoc.getTemplateNameLoc());
 923
 924   case TemplateArgument::Declaration:
 925   case TemplateArgument::NullPtr:
 926   case TemplateArgument::Template:
 927   case TemplateArgument::Integral:
 928   case TemplateArgument::Pack:
 929   case TemplateArgument::Null:
 930     return TemplateArgumentLoc();
 931   }
 932
 933   llvm_unreachable("Invalid TemplateArgument Kind!");
 934 }
 935
 936 Optional<unsigned> Sema::getFullyPackExpandedSize(TemplateArgument Arg) {
 937   assert(Arg.containsUnexpandedParameterPack());
 938
 939   // If this is a substituted pack, grab that pack. If not, we don't know
 940   // the size yet.
 941   // FIXME: We could find a size in more cases by looking for a substituted
 942   // pack anywhere within this argument, but that's not necessary in the common
 943   // case for 'sizeof...(A)' handling.
 944   TemplateArgument Pack;
 945   switch (Arg.getKind()) {
 946   case TemplateArgument::Type:
 947     if (auto *Subst = Arg.getAsType()->getAs<SubstTemplateTypeParmPackType>())
 948       Pack = Subst->getArgumentPack();
 949     else
 950       return None;
 951     break;
 952
 953   case TemplateArgument::Expression:
 954     if (auto *Subst =
 955             dyn_cast<SubstNonTypeTemplateParmPackExpr>(Arg.getAsExpr()))
 956       Pack = Subst->getArgumentPack();
 957     else if (auto *Subst = dyn_cast<FunctionParmPackExpr>(Arg.getAsExpr()))  {
 958       for (ParmVarDecl *PD : *Subst)
 959         if (PD->isParameterPack())
 960           return None;
 961       return Subst->getNumExpansions();
 962     } else
 963       return None;
 964     break;
 965
 966   case TemplateArgument::Template:
 967     if (SubstTemplateTemplateParmPackStorage *Subst =
 968             Arg.getAsTemplate().getAsSubstTemplateTemplateParmPack())
 969       Pack = Subst->getArgumentPack();
 970     else
 971       return None;
 972     break;
 973
 974   case TemplateArgument::Declaration:
 975   case TemplateArgument::NullPtr:
 976   case TemplateArgument::TemplateExpansion:
 977   case TemplateArgument::Integral:
 978   case TemplateArgument::Pack:
 979   case TemplateArgument::Null:
 980     return None;
 981   }
 982
 983   // Check that no argument in the pack is itself a pack expansion.
 984   for (TemplateArgument Elem : Pack.pack_elements()) {
 985     // There's no point recursing in this case; we would have already
 986     // expanded this pack expansion into the enclosing pack if we could.
 987     if (Elem.isPackExpansion())
 988       return None;
 989   }
 990   return Pack.pack_size();
 991 }
 992
 993 static void CheckFoldOperand(Sema &S, Expr *E) {
 994   if (!E)
 995     return;
 996
 997   E = E->IgnoreImpCasts();
 998   auto *OCE = dyn_cast<CXXOperatorCallExpr>(E);
 999   if ((OCE && OCE->isInfixBinaryOp()) || isa<BinaryOperator>(E) ||
1000       isa<AbstractConditionalOperator>(E)) {
1001     S.Diag(E->getExprLoc(), diag::err_fold_expression_bad_operand)
1002         << E->getSourceRange()
1003         << FixItHint::CreateInsertion(E->getLocStart(), "(")
1004         << FixItHint::CreateInsertion(E->getLocEnd(), ")");
1005   }
1006 }
1007
1008 ExprResult Sema::ActOnCXXFoldExpr(SourceLocation LParenLoc, Expr *LHS,
1009                                   tok::TokenKind Operator,
1010                                   SourceLocation EllipsisLoc, Expr *RHS,
1011                                   SourceLocation RParenLoc) {
1012   // LHS and RHS must be cast-expressions. We allow an arbitrary expression
1013   // in the parser and reduce down to just cast-expressions here.
1014   CheckFoldOperand(*this, LHS);
1015   CheckFoldOperand(*this, RHS);
1016
1017   // [expr.prim.fold]p3:
1018   //   In a binary fold, op1 and op2 shall be the same fold-operator, and
1019   //   either e1 shall contain an unexpanded parameter pack or e2 shall contain
1020   //   an unexpanded parameter pack, but not both.
1021   if (LHS && RHS &&
1022       LHS->containsUnexpandedParameterPack() ==
1023           RHS->containsUnexpandedParameterPack()) {
1024     return Diag(EllipsisLoc,
1025                 LHS->containsUnexpandedParameterPack()
1026                     ? diag::err_fold_expression_packs_both_sides
1027                     : diag::err_pack_expansion_without_parameter_packs)
1028         << LHS->getSourceRange() << RHS->getSourceRange();
1029   }
1030
1031   // [expr.prim.fold]p2:
1032   //   In a unary fold, the cast-expression shall contain an unexpanded
1033   //   parameter pack.
1034   if (!LHS || !RHS) {
1035     Expr *Pack = LHS ? LHS : RHS;
1036     assert(Pack && "fold expression with neither LHS nor RHS");
1037     if (!Pack->containsUnexpandedParameterPack())
1038       return Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
1039              << Pack->getSourceRange();
1040   }
1041
1042   BinaryOperatorKind Opc = ConvertTokenKindToBinaryOpcode(Operator);
1043   return BuildCXXFoldExpr(LParenLoc, LHS, Opc, EllipsisLoc, RHS, RParenLoc);
1044 }
1045
1046 ExprResult Sema::BuildCXXFoldExpr(SourceLocation LParenLoc, Expr *LHS,
1047                                   BinaryOperatorKind Operator,
1048                                   SourceLocation EllipsisLoc, Expr *RHS,
1049                                   SourceLocation RParenLoc) {
1050   return new (Context) CXXFoldExpr(Context.DependentTy, LParenLoc, LHS,
1051                                    Operator, EllipsisLoc, RHS, RParenLoc);
1052 }
1053
1054 ExprResult Sema::BuildEmptyCXXFoldExpr(SourceLocation EllipsisLoc,
1055                                        BinaryOperatorKind Operator) {
1056   // [temp.variadic]p9:
1057   //   If N is zero for a unary fold-expression, the value of the expression is
1058   //       &&  ->  true
1059   //       ||  ->  false
1060   //       ,   ->  void()
1061   //   if the operator is not listed [above], the instantiation is ill-formed.
1062   //
1063   // Note that we need to use something like int() here, not merely 0, to
1064   // prevent the result from being a null pointer constant.
1065   QualType ScalarType;
1066   switch (Operator) {
1067   case BO_LOr:
1068     return ActOnCXXBoolLiteral(EllipsisLoc, tok::kw_false);
1069   case BO_LAnd:
1070     return ActOnCXXBoolLiteral(EllipsisLoc, tok::kw_true);
1071   case BO_Comma:
1072     ScalarType = Context.VoidTy;
1073     break;
1074
1075   default:
1076     return Diag(EllipsisLoc, diag::err_fold_expression_empty)
1077         << BinaryOperator::getOpcodeStr(Operator);
1078   }
1079
1080   return new (Context) CXXScalarValueInitExpr(
1081       ScalarType, Context.getTrivialTypeSourceInfo(ScalarType, EllipsisLoc),
1082       EllipsisLoc);
1083 }