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
 255     = Names.size() == 0? Diag(Loc, diag::err_unexpanded_parameter_pack_0)
 256                            << (int)UPPC
 257     : Names.size() == 1? Diag(Loc, diag::err_unexpanded_parameter_pack_1)
 258                            << (int)UPPC << Names[0]
 259     : Names.size() == 2? Diag(Loc, diag::err_unexpanded_parameter_pack_2)
 260                            << (int)UPPC << Names[0] << Names[1]
 261     : Diag(Loc, diag::err_unexpanded_parameter_pack_3_or_more)
 262         << (int)UPPC << Names[0] << Names[1];
 263
 264   for (unsigned I = 0, N = Locations.size(); I != N; ++I)
 265     DB << SourceRange(Locations[I]);
 266   return true;
 267 }
 268
 269 bool Sema::DiagnoseUnexpandedParameterPack(SourceLocation Loc,
 270                                            TypeSourceInfo *T,
 271                                          UnexpandedParameterPackContext UPPC) {
 272   // C++0x [temp.variadic]p5:
 273   //   An appearance of a name of a parameter pack that is not expanded is
 274   //   ill-formed.
 275   if (!T->getType()->containsUnexpandedParameterPack())
 276     return false;
 277
 278   SmallVector<UnexpandedParameterPack, 2> Unexpanded;
 279   CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseTypeLoc(
 280                                                               T->getTypeLoc());
 281   assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
 282   return DiagnoseUnexpandedParameterPacks(Loc, UPPC, Unexpanded);
 283 }
 284
 285 bool Sema::DiagnoseUnexpandedParameterPack(Expr *E,
 286                                         UnexpandedParameterPackContext UPPC) {
 287   // C++0x [temp.variadic]p5:
 288   //   An appearance of a name of a parameter pack that is not expanded is
 289   //   ill-formed.
 290   if (!E->containsUnexpandedParameterPack())
 291     return false;
 292
 293   SmallVector<UnexpandedParameterPack, 2> Unexpanded;
 294   CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseStmt(E);
 295   assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
 296   return DiagnoseUnexpandedParameterPacks(E->getLocStart(), UPPC, Unexpanded);
 297 }
 298
 299 bool Sema::DiagnoseUnexpandedParameterPack(const CXXScopeSpec &SS,
 300                                         UnexpandedParameterPackContext UPPC) {
 301   // C++0x [temp.variadic]p5:
 302   //   An appearance of a name of a parameter pack that is not expanded is
 303   //   ill-formed.
 304   if (!SS.getScopeRep() ||
 305       !SS.getScopeRep()->containsUnexpandedParameterPack())
 306     return false;
 307
 308   SmallVector<UnexpandedParameterPack, 2> Unexpanded;
 309   CollectUnexpandedParameterPacksVisitor(Unexpanded)
 310     .TraverseNestedNameSpecifier(SS.getScopeRep());
 311   assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
 312   return DiagnoseUnexpandedParameterPacks(SS.getRange().getBegin(),
 313                                           UPPC, Unexpanded);
 314 }
 315
 316 bool Sema::DiagnoseUnexpandedParameterPack(const DeclarationNameInfo &NameInfo,
 317                                          UnexpandedParameterPackContext UPPC) {
 318   // C++0x [temp.variadic]p5:
 319   //   An appearance of a name of a parameter pack that is not expanded is
 320   //   ill-formed.
 321   switch (NameInfo.getName().getNameKind()) {
 322   case DeclarationName::Identifier:
 323   case DeclarationName::ObjCZeroArgSelector:
 324   case DeclarationName::ObjCOneArgSelector:
 325   case DeclarationName::ObjCMultiArgSelector:
 326   case DeclarationName::CXXOperatorName:
 327   case DeclarationName::CXXLiteralOperatorName:
 328   case DeclarationName::CXXUsingDirective:
 329     return false;
 330
 331   case DeclarationName::CXXConstructorName:
 332   case DeclarationName::CXXDestructorName:
 333   case DeclarationName::CXXConversionFunctionName:
 334     // FIXME: We shouldn't need this null check!
 335     if (TypeSourceInfo *TSInfo = NameInfo.getNamedTypeInfo())
 336       return DiagnoseUnexpandedParameterPack(NameInfo.getLoc(), TSInfo, UPPC);
 337
 338     if (!NameInfo.getName().getCXXNameType()->containsUnexpandedParameterPack())
 339       return false;
 340
 341     break;
 342   }
 343
 344   SmallVector<UnexpandedParameterPack, 2> Unexpanded;
 345   CollectUnexpandedParameterPacksVisitor(Unexpanded)
 346     .TraverseType(NameInfo.getName().getCXXNameType());
 347   assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
 348   return DiagnoseUnexpandedParameterPacks(NameInfo.getLoc(), UPPC, Unexpanded);
 349 }
 350
 351 bool Sema::DiagnoseUnexpandedParameterPack(SourceLocation Loc,
 352                                            TemplateName Template,
 353                                        UnexpandedParameterPackContext UPPC) {
 354
 355   if (Template.isNull() || !Template.containsUnexpandedParameterPack())
 356     return false;
 357
 358   SmallVector<UnexpandedParameterPack, 2> Unexpanded;
 359   CollectUnexpandedParameterPacksVisitor(Unexpanded)
 360     .TraverseTemplateName(Template);
 361   assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
 362   return DiagnoseUnexpandedParameterPacks(Loc, UPPC, Unexpanded);
 363 }
 364
 365 bool Sema::DiagnoseUnexpandedParameterPack(TemplateArgumentLoc Arg,
 366                                          UnexpandedParameterPackContext UPPC) {
 367   if (Arg.getArgument().isNull() ||
 368       !Arg.getArgument().containsUnexpandedParameterPack())
 369     return false;
 370
 371   SmallVector<UnexpandedParameterPack, 2> Unexpanded;
 372   CollectUnexpandedParameterPacksVisitor(Unexpanded)
 373     .TraverseTemplateArgumentLoc(Arg);
 374   assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
 375   return DiagnoseUnexpandedParameterPacks(Arg.getLocation(), UPPC, Unexpanded);
 376 }
 377
 378 void Sema::collectUnexpandedParameterPacks(TemplateArgument Arg,
 379                    SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
 380   CollectUnexpandedParameterPacksVisitor(Unexpanded)
 381     .TraverseTemplateArgument(Arg);
 382 }
 383
 384 void Sema::collectUnexpandedParameterPacks(TemplateArgumentLoc Arg,
 385                    SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
 386   CollectUnexpandedParameterPacksVisitor(Unexpanded)
 387     .TraverseTemplateArgumentLoc(Arg);
 388 }
 389
 390 void Sema::collectUnexpandedParameterPacks(QualType T,
 391                    SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
 392   CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseType(T);
 393 }
 394
 395 void Sema::collectUnexpandedParameterPacks(TypeLoc TL,
 396                    SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
 397   CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseTypeLoc(TL);
 398 }
 399
 400 void Sema::collectUnexpandedParameterPacks(CXXScopeSpec &SS,
 401                                            SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
 402   NestedNameSpecifier *Qualifier = SS.getScopeRep();
 403   if (!Qualifier)
 404     return;
 405
 406   NestedNameSpecifierLoc QualifierLoc(Qualifier, SS.location_data());
 407   CollectUnexpandedParameterPacksVisitor(Unexpanded)
 408     .TraverseNestedNameSpecifierLoc(QualifierLoc);
 409 }
 410
 411 void Sema::collectUnexpandedParameterPacks(const DeclarationNameInfo &NameInfo,
 412                          SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
 413   CollectUnexpandedParameterPacksVisitor(Unexpanded)
 414     .TraverseDeclarationNameInfo(NameInfo);
 415 }
 416
 417
 418 ParsedTemplateArgument
 419 Sema::ActOnPackExpansion(const ParsedTemplateArgument &Arg,
 420                          SourceLocation EllipsisLoc) {
 421   if (Arg.isInvalid())
 422     return Arg;
 423
 424   switch (Arg.getKind()) {
 425   case ParsedTemplateArgument::Type: {
 426     TypeResult Result = ActOnPackExpansion(Arg.getAsType(), EllipsisLoc);
 427     if (Result.isInvalid())
 428       return ParsedTemplateArgument();
 429
 430     return ParsedTemplateArgument(Arg.getKind(), Result.get().getAsOpaquePtr(),
 431                                   Arg.getLocation());
 432   }
 433
 434   case ParsedTemplateArgument::NonType: {
 435     ExprResult Result = ActOnPackExpansion(Arg.getAsExpr(), EllipsisLoc);
 436     if (Result.isInvalid())
 437       return ParsedTemplateArgument();
 438
 439     return ParsedTemplateArgument(Arg.getKind(), Result.get(),
 440                                   Arg.getLocation());
 441   }
 442
 443   case ParsedTemplateArgument::Template:
 444     if (!Arg.getAsTemplate().get().containsUnexpandedParameterPack()) {
 445       SourceRange R(Arg.getLocation());
 446       if (Arg.getScopeSpec().isValid())
 447         R.setBegin(Arg.getScopeSpec().getBeginLoc());
 448       Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
 449         << R;
 450       return ParsedTemplateArgument();
 451     }
 452
 453     return Arg.getTemplatePackExpansion(EllipsisLoc);
 454   }
 455   llvm_unreachable("Unhandled template argument kind?");
 456 }
 457
 458 TypeResult Sema::ActOnPackExpansion(ParsedType Type,
 459                                     SourceLocation EllipsisLoc) {
 460   TypeSourceInfo *TSInfo;
 461   GetTypeFromParser(Type, &TSInfo);
 462   if (!TSInfo)
 463     return true;
 464
 465   TypeSourceInfo *TSResult = CheckPackExpansion(TSInfo, EllipsisLoc, None);
 466   if (!TSResult)
 467     return true;
 468
 469   return CreateParsedType(TSResult->getType(), TSResult);
 470 }
 471
 472 TypeSourceInfo *
 473 Sema::CheckPackExpansion(TypeSourceInfo *Pattern, SourceLocation EllipsisLoc,
 474                          Optional<unsigned> NumExpansions) {
 475   // Create the pack expansion type and source-location information.
 476   QualType Result = CheckPackExpansion(Pattern->getType(),
 477                                        Pattern->getTypeLoc().getSourceRange(),
 478                                        EllipsisLoc, NumExpansions);
 479   if (Result.isNull())
 480     return nullptr;
 481
 482   TypeLocBuilder TLB;
 483   TLB.pushFullCopy(Pattern->getTypeLoc());
 484   PackExpansionTypeLoc TL = TLB.push<PackExpansionTypeLoc>(Result);
 485   TL.setEllipsisLoc(EllipsisLoc);
 486
 487   return TLB.getTypeSourceInfo(Context, Result);
 488 }
 489
 490 QualType Sema::CheckPackExpansion(QualType Pattern, SourceRange PatternRange,
 491                                   SourceLocation EllipsisLoc,
 492                                   Optional<unsigned> NumExpansions) {
 493   // C++0x [temp.variadic]p5:
 494   //   The pattern of a pack expansion shall name one or more
 495   //   parameter packs that are not expanded by a nested pack
 496   //   expansion.
 497   if (!Pattern->containsUnexpandedParameterPack()) {
 498     Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
 499       << PatternRange;
 500     return QualType();
 501   }
 502
 503   return Context.getPackExpansionType(Pattern, NumExpansions);
 504 }
 505
 506 ExprResult Sema::ActOnPackExpansion(Expr *Pattern, SourceLocation EllipsisLoc) {
 507   return CheckPackExpansion(Pattern, EllipsisLoc, None);
 508 }
 509
 510 ExprResult Sema::CheckPackExpansion(Expr *Pattern, SourceLocation EllipsisLoc,
 511                                     Optional<unsigned> NumExpansions) {
 512   if (!Pattern)
 513     return ExprError();
 514
 515   // C++0x [temp.variadic]p5:
 516   //   The pattern of a pack expansion shall name one or more
 517   //   parameter packs that are not expanded by a nested pack
 518   //   expansion.
 519   if (!Pattern->containsUnexpandedParameterPack()) {
 520     Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
 521     << Pattern->getSourceRange();
 522     return ExprError();
 523   }
 524
 525   // Create the pack expansion expression and source-location information.
 526   return new (Context)
 527     PackExpansionExpr(Context.DependentTy, Pattern, EllipsisLoc, NumExpansions);
 528 }
 529
 530 /// \brief Retrieve the depth and index of a parameter pack.
 531 static std::pair<unsigned, unsigned>
 532 getDepthAndIndex(NamedDecl *ND) {
 533   if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(ND))
 534     return std::make_pair(TTP->getDepth(), TTP->getIndex());
 535
 536   if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(ND))
 537     return std::make_pair(NTTP->getDepth(), NTTP->getIndex());
 538
 539   TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(ND);
 540   return std::make_pair(TTP->getDepth(), TTP->getIndex());
 541 }
 542
 543 bool Sema::CheckParameterPacksForExpansion(
 544     SourceLocation EllipsisLoc, SourceRange PatternRange,
 545     ArrayRef<UnexpandedParameterPack> Unexpanded,
 546     const MultiLevelTemplateArgumentList &TemplateArgs, bool &ShouldExpand,
 547     bool &RetainExpansion, Optional<unsigned> &NumExpansions) {
 548   ShouldExpand = true;
 549   RetainExpansion = false;
 550   std::pair<IdentifierInfo *, SourceLocation> FirstPack;
 551   bool HaveFirstPack = false;
 552
 553   for (ArrayRef<UnexpandedParameterPack>::iterator i = Unexpanded.begin(),
 554                                                  end = Unexpanded.end();
 555                                                   i != end; ++i) {
 556     // Compute the depth and index for this parameter pack.
 557     unsigned Depth = 0, Index = 0;
 558     IdentifierInfo *Name;
 559     bool IsFunctionParameterPack = false;
 560
 561     if (const TemplateTypeParmType *TTP
 562         = i->first.dyn_cast<const TemplateTypeParmType *>()) {
 563       Depth = TTP->getDepth();
 564       Index = TTP->getIndex();
 565       Name = TTP->getIdentifier();
 566     } else {
 567       NamedDecl *ND = i->first.get<NamedDecl *>();
 568       if (isa<ParmVarDecl>(ND))
 569         IsFunctionParameterPack = true;
 570       else
 571         std::tie(Depth, Index) = getDepthAndIndex(ND);
 572
 573       Name = ND->getIdentifier();
 574     }
 575
 576     // Determine the size of this argument pack.
 577     unsigned NewPackSize;
 578     if (IsFunctionParameterPack) {
 579       // Figure out whether we're instantiating to an argument pack or not.
 580       typedef LocalInstantiationScope::DeclArgumentPack DeclArgumentPack;
 581
 582       llvm::PointerUnion<Decl *, DeclArgumentPack *> *Instantiation
 583         = CurrentInstantiationScope->findInstantiationOf(
 584                                         i->first.get<NamedDecl *>());
 585       if (Instantiation->is<DeclArgumentPack *>()) {
 586         // We could expand this function parameter pack.
 587         NewPackSize = Instantiation->get<DeclArgumentPack *>()->size();
 588       } else {
 589         // We can't expand this function parameter pack, so we can't expand
 590         // the pack expansion.
 591         ShouldExpand = false;
 592         continue;
 593       }
 594     } else {
 595       // If we don't have a template argument at this depth/index, then we
 596       // cannot expand the pack expansion. Make a note of this, but we still
 597       // want to check any parameter packs we *do* have arguments for.
 598       if (Depth >= TemplateArgs.getNumLevels() ||
 599           !TemplateArgs.hasTemplateArgument(Depth, Index)) {
 600         ShouldExpand = false;
 601         continue;
 602       }
 603
 604       // Determine the size of the argument pack.
 605       NewPackSize = TemplateArgs(Depth, Index).pack_size();
 606     }
 607
 608     // C++0x [temp.arg.explicit]p9:
 609     //   Template argument deduction can extend the sequence of template
 610     //   arguments corresponding to a template parameter pack, even when the
 611     //   sequence contains explicitly specified template arguments.
 612     if (!IsFunctionParameterPack) {
 613       if (NamedDecl *PartialPack
 614                     = CurrentInstantiationScope->getPartiallySubstitutedPack()){
 615         unsigned PartialDepth, PartialIndex;
 616         std::tie(PartialDepth, PartialIndex) = getDepthAndIndex(PartialPack);
 617         if (PartialDepth == Depth && PartialIndex == Index)
 618           RetainExpansion = true;
 619       }
 620     }
 621
 622     if (!NumExpansions) {
 623       // The is the first pack we've seen for which we have an argument.
 624       // Record it.
 625       NumExpansions = NewPackSize;
 626       FirstPack.first = Name;
 627       FirstPack.second = i->second;
 628       HaveFirstPack = true;
 629       continue;
 630     }
 631
 632     if (NewPackSize != *NumExpansions) {
 633       // C++0x [temp.variadic]p5:
 634       //   All of the parameter packs expanded by a pack expansion shall have
 635       //   the same number of arguments specified.
 636       if (HaveFirstPack)
 637         Diag(EllipsisLoc, diag::err_pack_expansion_length_conflict)
 638           << FirstPack.first << Name << *NumExpansions << NewPackSize
 639           << SourceRange(FirstPack.second) << SourceRange(i->second);
 640       else
 641         Diag(EllipsisLoc, diag::err_pack_expansion_length_conflict_multilevel)
 642           << Name << *NumExpansions << NewPackSize
 643           << SourceRange(i->second);
 644       return true;
 645     }
 646   }
 647
 648   return false;
 649 }
 650
 651 Optional<unsigned> Sema::getNumArgumentsInExpansion(QualType T,
 652                           const MultiLevelTemplateArgumentList &TemplateArgs) {
 653   QualType Pattern = cast<PackExpansionType>(T)->getPattern();
 654   SmallVector<UnexpandedParameterPack, 2> Unexpanded;
 655   CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseType(Pattern);
 656
 657   Optional<unsigned> Result;
 658   for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
 659     // Compute the depth and index for this parameter pack.
 660     unsigned Depth;
 661     unsigned Index;
 662
 663     if (const TemplateTypeParmType *TTP
 664           = Unexpanded[I].first.dyn_cast<const TemplateTypeParmType *>()) {
 665       Depth = TTP->getDepth();
 666       Index = TTP->getIndex();
 667     } else {
 668       NamedDecl *ND = Unexpanded[I].first.get<NamedDecl *>();
 669       if (isa<ParmVarDecl>(ND)) {
 670         // Function parameter pack.
 671         typedef LocalInstantiationScope::DeclArgumentPack DeclArgumentPack;
 672
 673         llvm::PointerUnion<Decl *, DeclArgumentPack *> *Instantiation
 674           = CurrentInstantiationScope->findInstantiationOf(
 675                                         Unexpanded[I].first.get<NamedDecl *>());
 676         if (Instantiation->is<Decl*>())
 677           // The pattern refers to an unexpanded pack. We're not ready to expand
 678           // this pack yet.
 679           return None;
 680
 681         unsigned Size = Instantiation->get<DeclArgumentPack *>()->size();
 682         assert((!Result || *Result == Size) && "inconsistent pack sizes");
 683         Result = Size;
 684         continue;
 685       }
 686
 687       std::tie(Depth, Index) = getDepthAndIndex(ND);
 688     }
 689     if (Depth >= TemplateArgs.getNumLevels() ||
 690         !TemplateArgs.hasTemplateArgument(Depth, Index))
 691       // The pattern refers to an unknown template argument. We're not ready to
 692       // expand this pack yet.
 693       return None;
 694
 695     // Determine the size of the argument pack.
 696     unsigned Size = TemplateArgs(Depth, Index).pack_size();
 697     assert((!Result || *Result == Size) && "inconsistent pack sizes");
 698     Result = Size;
 699   }
 700
 701   return Result;
 702 }
 703
 704 bool Sema::containsUnexpandedParameterPacks(Declarator &D) {
 705   const DeclSpec &DS = D.getDeclSpec();
 706   switch (DS.getTypeSpecType()) {
 707   case TST_typename:
 708   case TST_typeofType:
 709   case TST_underlyingType:
 710   case TST_atomic: {
 711     QualType T = DS.getRepAsType().get();
 712     if (!T.isNull() && T->containsUnexpandedParameterPack())
 713       return true;
 714     break;
 715   }
 716
 717   case TST_typeofExpr:
 718   case TST_decltype:
 719     if (DS.getRepAsExpr() &&
 720         DS.getRepAsExpr()->containsUnexpandedParameterPack())
 721       return true;
 722     break;
 723
 724   case TST_unspecified:
 725   case TST_void:
 726   case TST_char:
 727   case TST_wchar:
 728   case TST_char16:
 729   case TST_char32:
 730   case TST_int:
 731   case TST_int128:
 732   case TST_half:
 733   case TST_float:
 734   case TST_double:
 735   case TST_bool:
 736   case TST_decimal32:
 737   case TST_decimal64:
 738   case TST_decimal128:
 739   case TST_enum:
 740   case TST_union:
 741   case TST_struct:
 742   case TST_interface:
 743   case TST_class:
 744   case TST_auto:
 745   case TST_decltype_auto:
 746   case TST_unknown_anytype:
 747   case TST_error:
 748     break;
 749   }
 750
 751   for (unsigned I = 0, N = D.getNumTypeObjects(); I != N; ++I) {
 752     const DeclaratorChunk &Chunk = D.getTypeObject(I);
 753     switch (Chunk.Kind) {
 754     case DeclaratorChunk::Pointer:
 755     case DeclaratorChunk::Reference:
 756     case DeclaratorChunk::Paren:
 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 new (Context) SizeOfPackExpr(Context.getSizeType(), OpLoc,
 876                                       ParameterPack, NameLoc, 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   //       *   ->  1
1003   //       +   ->  int()
1004   //       &   ->  -1
1005   //       |   ->  int()
1006   //       &&  ->  true
1007   //       ||  ->  false
1008   //       ,   ->  void()
1009   //   if the operator is not listed [above], the instantiation is ill-formed.
1010   //
1011   // Note that we need to use something like int() here, not merely 0, to
1012   // prevent the result from being a null pointer constant.
1013   QualType ScalarType;
1014   switch (Operator) {
1015   case BO_Add:
1016     ScalarType = Context.IntTy;
1017     break;
1018   case BO_Mul:
1019     return ActOnIntegerConstant(EllipsisLoc, 1);
1020   case BO_Or:
1021     ScalarType = Context.IntTy;
1022     break;
1023   case BO_And:
1024     return CreateBuiltinUnaryOp(EllipsisLoc, UO_Minus,
1025                                 ActOnIntegerConstant(EllipsisLoc, 1).get());
1026   case BO_LOr:
1027     return ActOnCXXBoolLiteral(EllipsisLoc, tok::kw_false);
1028   case BO_LAnd:
1029     return ActOnCXXBoolLiteral(EllipsisLoc, tok::kw_true);
1030   case BO_Comma:
1031     ScalarType = Context.VoidTy;
1032     break;
1033
1034   default:
1035     return Diag(EllipsisLoc, diag::err_fold_expression_empty)
1036         << BinaryOperator::getOpcodeStr(Operator);
1037   }
1038
1039   return new (Context) CXXScalarValueInitExpr(
1040       ScalarType, Context.getTrivialTypeSourceInfo(ScalarType, EllipsisLoc),
1041       EllipsisLoc);
1042 }