SemaTemplateVariadic.cpp revision 651f13cea278ec967336033dd032faef0e9fc2ec 
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
23using namespace clang;
24
25//----------------------------------------------------------------------------
26// Visitor that collects unexpanded parameter packs
27//----------------------------------------------------------------------------
28
29namespace {
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 Diagnose all of the unexpanded parameter packs in the given
201/// vector.
202bool
203Sema::DiagnoseUnexpandedParameterPacks(SourceLocation Loc,
204                                       UnexpandedParameterPackContext UPPC,
205                                 ArrayRef<UnexpandedParameterPack> Unexpanded) {
206  if (Unexpanded.empty())
207    return false;
208
209  // If we are within a lambda expression, that lambda contains an unexpanded
210  // parameter pack, and we are done.
211  // FIXME: Store 'Unexpanded' on the lambda so we don't need to recompute it
212  // later.
213  for (unsigned N = FunctionScopes.size(); N; --N) {
214    if (sema::LambdaScopeInfo *LSI =
215          dyn_cast<sema::LambdaScopeInfo>(FunctionScopes[N-1])) {
216      LSI->ContainsUnexpandedParameterPack = true;
217      return false;
218    }
219  }
220
221  SmallVector<SourceLocation, 4> Locations;
222  SmallVector<IdentifierInfo *, 4> Names;
223  llvm::SmallPtrSet<IdentifierInfo *, 4> NamesKnown;
224
225  for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
226    IdentifierInfo *Name = 0;
227    if (const TemplateTypeParmType *TTP
228          = Unexpanded[I].first.dyn_cast<const TemplateTypeParmType *>())
229      Name = TTP->getIdentifier();
230    else
231      Name = Unexpanded[I].first.get<NamedDecl *>()->getIdentifier();
232
233    if (Name && NamesKnown.insert(Name))
234      Names.push_back(Name);
235
236    if (Unexpanded[I].second.isValid())
237      Locations.push_back(Unexpanded[I].second);
238  }
239
240  DiagnosticBuilder DB
241    = Names.size() == 0? Diag(Loc, diag::err_unexpanded_parameter_pack_0)
242                           << (int)UPPC
243    : Names.size() == 1? Diag(Loc, diag::err_unexpanded_parameter_pack_1)
244                           << (int)UPPC << Names[0]
245    : Names.size() == 2? Diag(Loc, diag::err_unexpanded_parameter_pack_2)
246                           << (int)UPPC << Names[0] << Names[1]
247    : Diag(Loc, diag::err_unexpanded_parameter_pack_3_or_more)
248        << (int)UPPC << Names[0] << Names[1];
249
250  for (unsigned I = 0, N = Locations.size(); I != N; ++I)
251    DB << SourceRange(Locations[I]);
252  return true;
253}
254
255bool Sema::DiagnoseUnexpandedParameterPack(SourceLocation Loc,
256                                           TypeSourceInfo *T,
257                                         UnexpandedParameterPackContext UPPC) {
258  // C++0x [temp.variadic]p5:
259  //   An appearance of a name of a parameter pack that is not expanded is
260  //   ill-formed.
261  if (!T->getType()->containsUnexpandedParameterPack())
262    return false;
263
264  SmallVector<UnexpandedParameterPack, 2> Unexpanded;
265  CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseTypeLoc(
266                                                              T->getTypeLoc());
267  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
268  return DiagnoseUnexpandedParameterPacks(Loc, UPPC, Unexpanded);
269}
270
271bool Sema::DiagnoseUnexpandedParameterPack(Expr *E,
272                                        UnexpandedParameterPackContext UPPC) {
273  // C++0x [temp.variadic]p5:
274  //   An appearance of a name of a parameter pack that is not expanded is
275  //   ill-formed.
276  if (!E->containsUnexpandedParameterPack())
277    return false;
278
279  SmallVector<UnexpandedParameterPack, 2> Unexpanded;
280  CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseStmt(E);
281  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
282  return DiagnoseUnexpandedParameterPacks(E->getLocStart(), UPPC, Unexpanded);
283}
284
285bool Sema::DiagnoseUnexpandedParameterPack(const CXXScopeSpec &SS,
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 (!SS.getScopeRep() ||
291      !SS.getScopeRep()->containsUnexpandedParameterPack())
292    return false;
293
294  SmallVector<UnexpandedParameterPack, 2> Unexpanded;
295  CollectUnexpandedParameterPacksVisitor(Unexpanded)
296    .TraverseNestedNameSpecifier(SS.getScopeRep());
297  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
298  return DiagnoseUnexpandedParameterPacks(SS.getRange().getBegin(),
299                                          UPPC, Unexpanded);
300}
301
302bool Sema::DiagnoseUnexpandedParameterPack(const DeclarationNameInfo &NameInfo,
303                                         UnexpandedParameterPackContext UPPC) {
304  // C++0x [temp.variadic]p5:
305  //   An appearance of a name of a parameter pack that is not expanded is
306  //   ill-formed.
307  switch (NameInfo.getName().getNameKind()) {
308  case DeclarationName::Identifier:
309  case DeclarationName::ObjCZeroArgSelector:
310  case DeclarationName::ObjCOneArgSelector:
311  case DeclarationName::ObjCMultiArgSelector:
312  case DeclarationName::CXXOperatorName:
313  case DeclarationName::CXXLiteralOperatorName:
314  case DeclarationName::CXXUsingDirective:
315    return false;
316
317  case DeclarationName::CXXConstructorName:
318  case DeclarationName::CXXDestructorName:
319  case DeclarationName::CXXConversionFunctionName:
320    // FIXME: We shouldn't need this null check!
321    if (TypeSourceInfo *TSInfo = NameInfo.getNamedTypeInfo())
322      return DiagnoseUnexpandedParameterPack(NameInfo.getLoc(), TSInfo, UPPC);
323
324    if (!NameInfo.getName().getCXXNameType()->containsUnexpandedParameterPack())
325      return false;
326
327    break;
328  }
329
330  SmallVector<UnexpandedParameterPack, 2> Unexpanded;
331  CollectUnexpandedParameterPacksVisitor(Unexpanded)
332    .TraverseType(NameInfo.getName().getCXXNameType());
333  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
334  return DiagnoseUnexpandedParameterPacks(NameInfo.getLoc(), UPPC, Unexpanded);
335}
336
337bool Sema::DiagnoseUnexpandedParameterPack(SourceLocation Loc,
338                                           TemplateName Template,
339                                       UnexpandedParameterPackContext UPPC) {
340
341  if (Template.isNull() || !Template.containsUnexpandedParameterPack())
342    return false;
343
344  SmallVector<UnexpandedParameterPack, 2> Unexpanded;
345  CollectUnexpandedParameterPacksVisitor(Unexpanded)
346    .TraverseTemplateName(Template);
347  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
348  return DiagnoseUnexpandedParameterPacks(Loc, UPPC, Unexpanded);
349}
350
351bool Sema::DiagnoseUnexpandedParameterPack(TemplateArgumentLoc Arg,
352                                         UnexpandedParameterPackContext UPPC) {
353  if (Arg.getArgument().isNull() ||
354      !Arg.getArgument().containsUnexpandedParameterPack())
355    return false;
356
357  SmallVector<UnexpandedParameterPack, 2> Unexpanded;
358  CollectUnexpandedParameterPacksVisitor(Unexpanded)
359    .TraverseTemplateArgumentLoc(Arg);
360  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
361  return DiagnoseUnexpandedParameterPacks(Arg.getLocation(), UPPC, Unexpanded);
362}
363
364void Sema::collectUnexpandedParameterPacks(TemplateArgument Arg,
365                   SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
366  CollectUnexpandedParameterPacksVisitor(Unexpanded)
367    .TraverseTemplateArgument(Arg);
368}
369
370void Sema::collectUnexpandedParameterPacks(TemplateArgumentLoc Arg,
371                   SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
372  CollectUnexpandedParameterPacksVisitor(Unexpanded)
373    .TraverseTemplateArgumentLoc(Arg);
374}
375
376void Sema::collectUnexpandedParameterPacks(QualType T,
377                   SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
378  CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseType(T);
379}
380
381void Sema::collectUnexpandedParameterPacks(TypeLoc TL,
382                   SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
383  CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseTypeLoc(TL);
384}
385
386void Sema::collectUnexpandedParameterPacks(CXXScopeSpec &SS,
387                                           SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
388  NestedNameSpecifier *Qualifier = SS.getScopeRep();
389  if (!Qualifier)
390    return;
391
392  NestedNameSpecifierLoc QualifierLoc(Qualifier, SS.location_data());
393  CollectUnexpandedParameterPacksVisitor(Unexpanded)
394    .TraverseNestedNameSpecifierLoc(QualifierLoc);
395}
396
397void Sema::collectUnexpandedParameterPacks(const DeclarationNameInfo &NameInfo,
398                         SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
399  CollectUnexpandedParameterPacksVisitor(Unexpanded)
400    .TraverseDeclarationNameInfo(NameInfo);
401}
402
403
404ParsedTemplateArgument
405Sema::ActOnPackExpansion(const ParsedTemplateArgument &Arg,
406                         SourceLocation EllipsisLoc) {
407  if (Arg.isInvalid())
408    return Arg;
409
410  switch (Arg.getKind()) {
411  case ParsedTemplateArgument::Type: {
412    TypeResult Result = ActOnPackExpansion(Arg.getAsType(), EllipsisLoc);
413    if (Result.isInvalid())
414      return ParsedTemplateArgument();
415
416    return ParsedTemplateArgument(Arg.getKind(), Result.get().getAsOpaquePtr(),
417                                  Arg.getLocation());
418  }
419
420  case ParsedTemplateArgument::NonType: {
421    ExprResult Result = ActOnPackExpansion(Arg.getAsExpr(), EllipsisLoc);
422    if (Result.isInvalid())
423      return ParsedTemplateArgument();
424
425    return ParsedTemplateArgument(Arg.getKind(), Result.get(),
426                                  Arg.getLocation());
427  }
428
429  case ParsedTemplateArgument::Template:
430    if (!Arg.getAsTemplate().get().containsUnexpandedParameterPack()) {
431      SourceRange R(Arg.getLocation());
432      if (Arg.getScopeSpec().isValid())
433        R.setBegin(Arg.getScopeSpec().getBeginLoc());
434      Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
435        << R;
436      return ParsedTemplateArgument();
437    }
438
439    return Arg.getTemplatePackExpansion(EllipsisLoc);
440  }
441  llvm_unreachable("Unhandled template argument kind?");
442}
443
444TypeResult Sema::ActOnPackExpansion(ParsedType Type,
445                                    SourceLocation EllipsisLoc) {
446  TypeSourceInfo *TSInfo;
447  GetTypeFromParser(Type, &TSInfo);
448  if (!TSInfo)
449    return true;
450
451  TypeSourceInfo *TSResult = CheckPackExpansion(TSInfo, EllipsisLoc, None);
452  if (!TSResult)
453    return true;
454
455  return CreateParsedType(TSResult->getType(), TSResult);
456}
457
458TypeSourceInfo *
459Sema::CheckPackExpansion(TypeSourceInfo *Pattern, SourceLocation EllipsisLoc,
460                         Optional<unsigned> NumExpansions) {
461  // Create the pack expansion type and source-location information.
462  QualType Result = CheckPackExpansion(Pattern->getType(),
463                                       Pattern->getTypeLoc().getSourceRange(),
464                                       EllipsisLoc, NumExpansions);
465  if (Result.isNull())
466    return 0;
467
468  TypeLocBuilder TLB;
469  TLB.pushFullCopy(Pattern->getTypeLoc());
470  PackExpansionTypeLoc TL = TLB.push<PackExpansionTypeLoc>(Result);
471  TL.setEllipsisLoc(EllipsisLoc);
472
473  return TLB.getTypeSourceInfo(Context, Result);
474}
475
476QualType Sema::CheckPackExpansion(QualType Pattern, SourceRange PatternRange,
477                                  SourceLocation EllipsisLoc,
478                                  Optional<unsigned> NumExpansions) {
479  // C++0x [temp.variadic]p5:
480  //   The pattern of a pack expansion shall name one or more
481  //   parameter packs that are not expanded by a nested pack
482  //   expansion.
483  if (!Pattern->containsUnexpandedParameterPack()) {
484    Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
485      << PatternRange;
486    return QualType();
487  }
488
489  return Context.getPackExpansionType(Pattern, NumExpansions);
490}
491
492ExprResult Sema::ActOnPackExpansion(Expr *Pattern, SourceLocation EllipsisLoc) {
493  return CheckPackExpansion(Pattern, EllipsisLoc, None);
494}
495
496ExprResult Sema::CheckPackExpansion(Expr *Pattern, SourceLocation EllipsisLoc,
497                                    Optional<unsigned> NumExpansions) {
498  if (!Pattern)
499    return ExprError();
500
501  // C++0x [temp.variadic]p5:
502  //   The pattern of a pack expansion shall name one or more
503  //   parameter packs that are not expanded by a nested pack
504  //   expansion.
505  if (!Pattern->containsUnexpandedParameterPack()) {
506    Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
507    << Pattern->getSourceRange();
508    return ExprError();
509  }
510
511  // Create the pack expansion expression and source-location information.
512  return Owned(new (Context) PackExpansionExpr(Context.DependentTy, Pattern,
513                                               EllipsisLoc, NumExpansions));
514}
515
516/// \brief Retrieve the depth and index of a parameter pack.
517static std::pair<unsigned, unsigned>
518getDepthAndIndex(NamedDecl *ND) {
519  if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(ND))
520    return std::make_pair(TTP->getDepth(), TTP->getIndex());
521
522  if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(ND))
523    return std::make_pair(NTTP->getDepth(), NTTP->getIndex());
524
525  TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(ND);
526  return std::make_pair(TTP->getDepth(), TTP->getIndex());
527}
528
529bool Sema::CheckParameterPacksForExpansion(
530    SourceLocation EllipsisLoc, SourceRange PatternRange,
531    ArrayRef<UnexpandedParameterPack> Unexpanded,
532    const MultiLevelTemplateArgumentList &TemplateArgs, bool &ShouldExpand,
533    bool &RetainExpansion, Optional<unsigned> &NumExpansions) {
534  ShouldExpand = true;
535  RetainExpansion = false;
536  std::pair<IdentifierInfo *, SourceLocation> FirstPack;
537  bool HaveFirstPack = false;
538
539  for (ArrayRef<UnexpandedParameterPack>::iterator i = Unexpanded.begin(),
540                                                 end = Unexpanded.end();
541                                                  i != end; ++i) {
542    // Compute the depth and index for this parameter pack.
543    unsigned Depth = 0, Index = 0;
544    IdentifierInfo *Name;
545    bool IsFunctionParameterPack = false;
546
547    if (const TemplateTypeParmType *TTP
548        = i->first.dyn_cast<const TemplateTypeParmType *>()) {
549      Depth = TTP->getDepth();
550      Index = TTP->getIndex();
551      Name = TTP->getIdentifier();
552    } else {
553      NamedDecl *ND = i->first.get<NamedDecl *>();
554      if (isa<ParmVarDecl>(ND))
555        IsFunctionParameterPack = true;
556      else
557        std::tie(Depth, Index) = getDepthAndIndex(ND);
558
559      Name = ND->getIdentifier();
560    }
561
562    // Determine the size of this argument pack.
563    unsigned NewPackSize;
564    if (IsFunctionParameterPack) {
565      // Figure out whether we're instantiating to an argument pack or not.
566      typedef LocalInstantiationScope::DeclArgumentPack DeclArgumentPack;
567
568      llvm::PointerUnion<Decl *, DeclArgumentPack *> *Instantiation
569        = CurrentInstantiationScope->findInstantiationOf(
570                                        i->first.get<NamedDecl *>());
571      if (Instantiation->is<DeclArgumentPack *>()) {
572        // We could expand this function parameter pack.
573        NewPackSize = Instantiation->get<DeclArgumentPack *>()->size();
574      } else {
575        // We can't expand this function parameter pack, so we can't expand
576        // the pack expansion.
577        ShouldExpand = false;
578        continue;
579      }
580    } else {
581      // If we don't have a template argument at this depth/index, then we
582      // cannot expand the pack expansion. Make a note of this, but we still
583      // want to check any parameter packs we *do* have arguments for.
584      if (Depth >= TemplateArgs.getNumLevels() ||
585          !TemplateArgs.hasTemplateArgument(Depth, Index)) {
586        ShouldExpand = false;
587        continue;
588      }
589
590      // Determine the size of the argument pack.
591      NewPackSize = TemplateArgs(Depth, Index).pack_size();
592    }
593
594    // C++0x [temp.arg.explicit]p9:
595    //   Template argument deduction can extend the sequence of template
596    //   arguments corresponding to a template parameter pack, even when the
597    //   sequence contains explicitly specified template arguments.
598    if (!IsFunctionParameterPack) {
599      if (NamedDecl *PartialPack
600                    = CurrentInstantiationScope->getPartiallySubstitutedPack()){
601        unsigned PartialDepth, PartialIndex;
602        std::tie(PartialDepth, PartialIndex) = getDepthAndIndex(PartialPack);
603        if (PartialDepth == Depth && PartialIndex == Index)
604          RetainExpansion = true;
605      }
606    }
607
608    if (!NumExpansions) {
609      // The is the first pack we've seen for which we have an argument.
610      // Record it.
611      NumExpansions = NewPackSize;
612      FirstPack.first = Name;
613      FirstPack.second = i->second;
614      HaveFirstPack = true;
615      continue;
616    }
617
618    if (NewPackSize != *NumExpansions) {
619      // C++0x [temp.variadic]p5:
620      //   All of the parameter packs expanded by a pack expansion shall have
621      //   the same number of arguments specified.
622      if (HaveFirstPack)
623        Diag(EllipsisLoc, diag::err_pack_expansion_length_conflict)
624          << FirstPack.first << Name << *NumExpansions << NewPackSize
625          << SourceRange(FirstPack.second) << SourceRange(i->second);
626      else
627        Diag(EllipsisLoc, diag::err_pack_expansion_length_conflict_multilevel)
628          << Name << *NumExpansions << NewPackSize
629          << SourceRange(i->second);
630      return true;
631    }
632  }
633
634  return false;
635}
636
637Optional<unsigned> Sema::getNumArgumentsInExpansion(QualType T,
638                          const MultiLevelTemplateArgumentList &TemplateArgs) {
639  QualType Pattern = cast<PackExpansionType>(T)->getPattern();
640  SmallVector<UnexpandedParameterPack, 2> Unexpanded;
641  CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseType(Pattern);
642
643  Optional<unsigned> Result;
644  for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
645    // Compute the depth and index for this parameter pack.
646    unsigned Depth;
647    unsigned Index;
648
649    if (const TemplateTypeParmType *TTP
650          = Unexpanded[I].first.dyn_cast<const TemplateTypeParmType *>()) {
651      Depth = TTP->getDepth();
652      Index = TTP->getIndex();
653    } else {
654      NamedDecl *ND = Unexpanded[I].first.get<NamedDecl *>();
655      if (isa<ParmVarDecl>(ND)) {
656        // Function parameter pack.
657        typedef LocalInstantiationScope::DeclArgumentPack DeclArgumentPack;
658
659        llvm::PointerUnion<Decl *, DeclArgumentPack *> *Instantiation
660          = CurrentInstantiationScope->findInstantiationOf(
661                                        Unexpanded[I].first.get<NamedDecl *>());
662        if (Instantiation->is<Decl*>())
663          // The pattern refers to an unexpanded pack. We're not ready to expand
664          // this pack yet.
665          return None;
666
667        unsigned Size = Instantiation->get<DeclArgumentPack *>()->size();
668        assert((!Result || *Result == Size) && "inconsistent pack sizes");
669        Result = Size;
670        continue;
671      }
672
673      std::tie(Depth, Index) = getDepthAndIndex(ND);
674    }
675    if (Depth >= TemplateArgs.getNumLevels() ||
676        !TemplateArgs.hasTemplateArgument(Depth, Index))
677      // The pattern refers to an unknown template argument. We're not ready to
678      // expand this pack yet.
679      return None;
680
681    // Determine the size of the argument pack.
682    unsigned Size = TemplateArgs(Depth, Index).pack_size();
683    assert((!Result || *Result == Size) && "inconsistent pack sizes");
684    Result = Size;
685  }
686
687  return Result;
688}
689
690bool Sema::containsUnexpandedParameterPacks(Declarator &D) {
691  const DeclSpec &DS = D.getDeclSpec();
692  switch (DS.getTypeSpecType()) {
693  case TST_typename:
694  case TST_typeofType:
695  case TST_underlyingType:
696  case TST_atomic: {
697    QualType T = DS.getRepAsType().get();
698    if (!T.isNull() && T->containsUnexpandedParameterPack())
699      return true;
700    break;
701  }
702
703  case TST_typeofExpr:
704  case TST_decltype:
705    if (DS.getRepAsExpr() &&
706        DS.getRepAsExpr()->containsUnexpandedParameterPack())
707      return true;
708    break;
709
710  case TST_unspecified:
711  case TST_void:
712  case TST_char:
713  case TST_wchar:
714  case TST_char16:
715  case TST_char32:
716  case TST_int:
717  case TST_int128:
718  case TST_half:
719  case TST_float:
720  case TST_double:
721  case TST_bool:
722  case TST_decimal32:
723  case TST_decimal64:
724  case TST_decimal128:
725  case TST_enum:
726  case TST_union:
727  case TST_struct:
728  case TST_interface:
729  case TST_class:
730  case TST_auto:
731  case TST_decltype_auto:
732  case TST_unknown_anytype:
733  case TST_error:
734    break;
735  }
736
737  for (unsigned I = 0, N = D.getNumTypeObjects(); I != N; ++I) {
738    const DeclaratorChunk &Chunk = D.getTypeObject(I);
739    switch (Chunk.Kind) {
740    case DeclaratorChunk::Pointer:
741    case DeclaratorChunk::Reference:
742    case DeclaratorChunk::Paren:
743      // These declarator chunks cannot contain any parameter packs.
744      break;
745
746    case DeclaratorChunk::Array:
747    case DeclaratorChunk::Function:
748    case DeclaratorChunk::BlockPointer:
749      // Syntactically, these kinds of declarator chunks all come after the
750      // declarator-id (conceptually), so the parser should not invoke this
751      // routine at this time.
752      llvm_unreachable("Could not have seen this kind of declarator chunk");
753
754    case DeclaratorChunk::MemberPointer:
755      if (Chunk.Mem.Scope().getScopeRep() &&
756          Chunk.Mem.Scope().getScopeRep()->containsUnexpandedParameterPack())
757        return true;
758      break;
759    }
760  }
761
762  return false;
763}
764
765namespace {
766
767// Callback to only accept typo corrections that refer to parameter packs.
768class ParameterPackValidatorCCC : public CorrectionCandidateCallback {
769 public:
770  bool ValidateCandidate(const TypoCorrection &candidate) override {
771    NamedDecl *ND = candidate.getCorrectionDecl();
772    return ND && ND->isParameterPack();
773  }
774};
775
776}
777
778/// \brief Called when an expression computing the size of a parameter pack
779/// is parsed.
780///
781/// \code
782/// template<typename ...Types> struct count {
783///   static const unsigned value = sizeof...(Types);
784/// };
785/// \endcode
786///
787//
788/// \param OpLoc The location of the "sizeof" keyword.
789/// \param Name The name of the parameter pack whose size will be determined.
790/// \param NameLoc The source location of the name of the parameter pack.
791/// \param RParenLoc The location of the closing parentheses.
792ExprResult Sema::ActOnSizeofParameterPackExpr(Scope *S,
793                                              SourceLocation OpLoc,
794                                              IdentifierInfo &Name,
795                                              SourceLocation NameLoc,
796                                              SourceLocation RParenLoc) {
797  // C++0x [expr.sizeof]p5:
798  //   The identifier in a sizeof... expression shall name a parameter pack.
799  LookupResult R(*this, &Name, NameLoc, LookupOrdinaryName);
800  LookupName(R, S);
801
802  NamedDecl *ParameterPack = 0;
803  ParameterPackValidatorCCC Validator;
804  switch (R.getResultKind()) {
805  case LookupResult::Found:
806    ParameterPack = R.getFoundDecl();
807    break;
808
809  case LookupResult::NotFound:
810  case LookupResult::NotFoundInCurrentInstantiation:
811    if (TypoCorrection Corrected = CorrectTypo(R.getLookupNameInfo(),
812                                               R.getLookupKind(), S, 0,
813                                               Validator)) {
814      diagnoseTypo(Corrected,
815                   PDiag(diag::err_sizeof_pack_no_pack_name_suggest) << &Name,
816                   PDiag(diag::note_parameter_pack_here));
817      ParameterPack = Corrected.getCorrectionDecl();
818    }
819
820  case LookupResult::FoundOverloaded:
821  case LookupResult::FoundUnresolvedValue:
822    break;
823
824  case LookupResult::Ambiguous:
825    DiagnoseAmbiguousLookup(R);
826    return ExprError();
827  }
828
829  if (!ParameterPack || !ParameterPack->isParameterPack()) {
830    Diag(NameLoc, diag::err_sizeof_pack_no_pack_name)
831      << &Name;
832    return ExprError();
833  }
834
835  MarkAnyDeclReferenced(OpLoc, ParameterPack, true);
836
837  return new (Context) SizeOfPackExpr(Context.getSizeType(), OpLoc,
838                                      ParameterPack, NameLoc, RParenLoc);
839}
840
841TemplateArgumentLoc
842Sema::getTemplateArgumentPackExpansionPattern(
843      TemplateArgumentLoc OrigLoc,
844      SourceLocation &Ellipsis, Optional<unsigned> &NumExpansions) const {
845  const TemplateArgument &Argument = OrigLoc.getArgument();
846  assert(Argument.isPackExpansion());
847  switch (Argument.getKind()) {
848  case TemplateArgument::Type: {
849    // FIXME: We shouldn't ever have to worry about missing
850    // type-source info!
851    TypeSourceInfo *ExpansionTSInfo = OrigLoc.getTypeSourceInfo();
852    if (!ExpansionTSInfo)
853      ExpansionTSInfo = Context.getTrivialTypeSourceInfo(Argument.getAsType(),
854                                                         Ellipsis);
855    PackExpansionTypeLoc Expansion =
856        ExpansionTSInfo->getTypeLoc().castAs<PackExpansionTypeLoc>();
857    Ellipsis = Expansion.getEllipsisLoc();
858
859    TypeLoc Pattern = Expansion.getPatternLoc();
860    NumExpansions = Expansion.getTypePtr()->getNumExpansions();
861
862    // We need to copy the TypeLoc because TemplateArgumentLocs store a
863    // TypeSourceInfo.
864    // FIXME: Find some way to avoid the copy?
865    TypeLocBuilder TLB;
866    TLB.pushFullCopy(Pattern);
867    TypeSourceInfo *PatternTSInfo =
868        TLB.getTypeSourceInfo(Context, Pattern.getType());
869    return TemplateArgumentLoc(TemplateArgument(Pattern.getType()),
870                               PatternTSInfo);
871  }
872
873  case TemplateArgument::Expression: {
874    PackExpansionExpr *Expansion
875      = cast<PackExpansionExpr>(Argument.getAsExpr());
876    Expr *Pattern = Expansion->getPattern();
877    Ellipsis = Expansion->getEllipsisLoc();
878    NumExpansions = Expansion->getNumExpansions();
879    return TemplateArgumentLoc(Pattern, Pattern);
880  }
881
882  case TemplateArgument::TemplateExpansion:
883    Ellipsis = OrigLoc.getTemplateEllipsisLoc();
884    NumExpansions = Argument.getNumTemplateExpansions();
885    return TemplateArgumentLoc(Argument.getPackExpansionPattern(),
886                               OrigLoc.getTemplateQualifierLoc(),
887                               OrigLoc.getTemplateNameLoc());
888
889  case TemplateArgument::Declaration:
890  case TemplateArgument::NullPtr:
891  case TemplateArgument::Template:
892  case TemplateArgument::Integral:
893  case TemplateArgument::Pack:
894  case TemplateArgument::Null:
895    return TemplateArgumentLoc();
896  }
897
898  llvm_unreachable("Invalid TemplateArgument Kind!");
899}
900