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