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(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 }