SemaTemplateVariadic.cpp revision 263508 
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 "clang/AST/Expr.h"
14#include "clang/AST/RecursiveASTVisitor.h"
15#include "clang/AST/TypeLoc.h"
16#include "clang/Sema/Lookup.h"
17#include "clang/Sema/ParsedTemplate.h"
18#include "clang/Sema/ScopeInfo.h"
19#include "clang/Sema/SemaInternal.h"
20#include "clang/Sema/Template.h"
21#include "TypeLocBuilder.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        llvm::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        llvm::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      llvm::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_image1d_t:
734  case TST_image1d_array_t:
735  case TST_image1d_buffer_t:
736  case TST_image2d_t:
737  case TST_image2d_array_t:
738  case TST_image3d_t:
739  case TST_sampler_t:
740  case TST_event_t:
741  case TST_error:
742    break;
743  }
744
745  for (unsigned I = 0, N = D.getNumTypeObjects(); I != N; ++I) {
746    const DeclaratorChunk &Chunk = D.getTypeObject(I);
747    switch (Chunk.Kind) {
748    case DeclaratorChunk::Pointer:
749    case DeclaratorChunk::Reference:
750    case DeclaratorChunk::Paren:
751      // These declarator chunks cannot contain any parameter packs.
752      break;
753
754    case DeclaratorChunk::Array:
755    case DeclaratorChunk::Function:
756    case DeclaratorChunk::BlockPointer:
757      // Syntactically, these kinds of declarator chunks all come after the
758      // declarator-id (conceptually), so the parser should not invoke this
759      // routine at this time.
760      llvm_unreachable("Could not have seen this kind of declarator chunk");
761
762    case DeclaratorChunk::MemberPointer:
763      if (Chunk.Mem.Scope().getScopeRep() &&
764          Chunk.Mem.Scope().getScopeRep()->containsUnexpandedParameterPack())
765        return true;
766      break;
767    }
768  }
769
770  return false;
771}
772
773namespace {
774
775// Callback to only accept typo corrections that refer to parameter packs.
776class ParameterPackValidatorCCC : public CorrectionCandidateCallback {
777 public:
778  virtual bool ValidateCandidate(const TypoCorrection &candidate) {
779    NamedDecl *ND = candidate.getCorrectionDecl();
780    return ND && ND->isParameterPack();
781  }
782};
783
784}
785
786/// \brief Called when an expression computing the size of a parameter pack
787/// is parsed.
788///
789/// \code
790/// template<typename ...Types> struct count {
791///   static const unsigned value = sizeof...(Types);
792/// };
793/// \endcode
794///
795//
796/// \param OpLoc The location of the "sizeof" keyword.
797/// \param Name The name of the parameter pack whose size will be determined.
798/// \param NameLoc The source location of the name of the parameter pack.
799/// \param RParenLoc The location of the closing parentheses.
800ExprResult Sema::ActOnSizeofParameterPackExpr(Scope *S,
801                                              SourceLocation OpLoc,
802                                              IdentifierInfo &Name,
803                                              SourceLocation NameLoc,
804                                              SourceLocation RParenLoc) {
805  // C++0x [expr.sizeof]p5:
806  //   The identifier in a sizeof... expression shall name a parameter pack.
807  LookupResult R(*this, &Name, NameLoc, LookupOrdinaryName);
808  LookupName(R, S);
809
810  NamedDecl *ParameterPack = 0;
811  ParameterPackValidatorCCC Validator;
812  switch (R.getResultKind()) {
813  case LookupResult::Found:
814    ParameterPack = R.getFoundDecl();
815    break;
816
817  case LookupResult::NotFound:
818  case LookupResult::NotFoundInCurrentInstantiation:
819    if (TypoCorrection Corrected = CorrectTypo(R.getLookupNameInfo(),
820                                               R.getLookupKind(), S, 0,
821                                               Validator)) {
822      diagnoseTypo(Corrected,
823                   PDiag(diag::err_sizeof_pack_no_pack_name_suggest) << &Name,
824                   PDiag(diag::note_parameter_pack_here));
825      ParameterPack = Corrected.getCorrectionDecl();
826    }
827
828  case LookupResult::FoundOverloaded:
829  case LookupResult::FoundUnresolvedValue:
830    break;
831
832  case LookupResult::Ambiguous:
833    DiagnoseAmbiguousLookup(R);
834    return ExprError();
835  }
836
837  if (!ParameterPack || !ParameterPack->isParameterPack()) {
838    Diag(NameLoc, diag::err_sizeof_pack_no_pack_name)
839      << &Name;
840    return ExprError();
841  }
842
843  MarkAnyDeclReferenced(OpLoc, ParameterPack, true);
844
845  return new (Context) SizeOfPackExpr(Context.getSizeType(), OpLoc,
846                                      ParameterPack, NameLoc, RParenLoc);
847}
848
849TemplateArgumentLoc
850Sema::getTemplateArgumentPackExpansionPattern(
851      TemplateArgumentLoc OrigLoc,
852      SourceLocation &Ellipsis, Optional<unsigned> &NumExpansions) const {
853  const TemplateArgument &Argument = OrigLoc.getArgument();
854  assert(Argument.isPackExpansion());
855  switch (Argument.getKind()) {
856  case TemplateArgument::Type: {
857    // FIXME: We shouldn't ever have to worry about missing
858    // type-source info!
859    TypeSourceInfo *ExpansionTSInfo = OrigLoc.getTypeSourceInfo();
860    if (!ExpansionTSInfo)
861      ExpansionTSInfo = Context.getTrivialTypeSourceInfo(Argument.getAsType(),
862                                                         Ellipsis);
863    PackExpansionTypeLoc Expansion =
864        ExpansionTSInfo->getTypeLoc().castAs<PackExpansionTypeLoc>();
865    Ellipsis = Expansion.getEllipsisLoc();
866
867    TypeLoc Pattern = Expansion.getPatternLoc();
868    NumExpansions = Expansion.getTypePtr()->getNumExpansions();
869
870    // We need to copy the TypeLoc because TemplateArgumentLocs store a
871    // TypeSourceInfo.
872    // FIXME: Find some way to avoid the copy?
873    TypeLocBuilder TLB;
874    TLB.pushFullCopy(Pattern);
875    TypeSourceInfo *PatternTSInfo =
876        TLB.getTypeSourceInfo(Context, Pattern.getType());
877    return TemplateArgumentLoc(TemplateArgument(Pattern.getType()),
878                               PatternTSInfo);
879  }
880
881  case TemplateArgument::Expression: {
882    PackExpansionExpr *Expansion
883      = cast<PackExpansionExpr>(Argument.getAsExpr());
884    Expr *Pattern = Expansion->getPattern();
885    Ellipsis = Expansion->getEllipsisLoc();
886    NumExpansions = Expansion->getNumExpansions();
887    return TemplateArgumentLoc(Pattern, Pattern);
888  }
889
890  case TemplateArgument::TemplateExpansion:
891    Ellipsis = OrigLoc.getTemplateEllipsisLoc();
892    NumExpansions = Argument.getNumTemplateExpansions();
893    return TemplateArgumentLoc(Argument.getPackExpansionPattern(),
894                               OrigLoc.getTemplateQualifierLoc(),
895                               OrigLoc.getTemplateNameLoc());
896
897  case TemplateArgument::Declaration:
898  case TemplateArgument::NullPtr:
899  case TemplateArgument::Template:
900  case TemplateArgument::Integral:
901  case TemplateArgument::Pack:
902  case TemplateArgument::Null:
903    return TemplateArgumentLoc();
904  }
905
906  llvm_unreachable("Invalid TemplateArgument Kind!");
907}
908