SemaTemplateVariadic.cpp revision dc84cd5efdd3430efb22546b4ac656aa0540b210 
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
22using namespace clang;
23
24//----------------------------------------------------------------------------
25// Visitor that collects unexpanded parameter packs
26//----------------------------------------------------------------------------
27
28namespace {
29  /// \brief A class that collects unexpanded parameter packs.
30  class CollectUnexpandedParameterPacksVisitor :
31    public RecursiveASTVisitor<CollectUnexpandedParameterPacksVisitor>
32  {
33    typedef RecursiveASTVisitor<CollectUnexpandedParameterPacksVisitor>
34      inherited;
35
36    SmallVectorImpl<UnexpandedParameterPack> &Unexpanded;
37
38    bool InLambda;
39
40  public:
41    explicit CollectUnexpandedParameterPacksVisitor(
42                  SmallVectorImpl<UnexpandedParameterPack> &Unexpanded)
43      : Unexpanded(Unexpanded), InLambda(false) { }
44
45    bool shouldWalkTypesOfTypeLocs() const { return false; }
46
47    //------------------------------------------------------------------------
48    // Recording occurrences of (unexpanded) parameter packs.
49    //------------------------------------------------------------------------
50
51    /// \brief Record occurrences of template type parameter packs.
52    bool VisitTemplateTypeParmTypeLoc(TemplateTypeParmTypeLoc TL) {
53      if (TL.getTypePtr()->isParameterPack())
54        Unexpanded.push_back(std::make_pair(TL.getTypePtr(), TL.getNameLoc()));
55      return true;
56    }
57
58    /// \brief Record occurrences of template type parameter packs
59    /// when we don't have proper source-location information for
60    /// them.
61    ///
62    /// Ideally, this routine would never be used.
63    bool VisitTemplateTypeParmType(TemplateTypeParmType *T) {
64      if (T->isParameterPack())
65        Unexpanded.push_back(std::make_pair(T, SourceLocation()));
66
67      return true;
68    }
69
70    /// \brief Record occurrences of function and non-type template
71    /// parameter packs in an expression.
72    bool VisitDeclRefExpr(DeclRefExpr *E) {
73      if (E->getDecl()->isParameterPack())
74        Unexpanded.push_back(std::make_pair(E->getDecl(), E->getLocation()));
75
76      return true;
77    }
78
79    /// \brief Record occurrences of template template parameter packs.
80    bool TraverseTemplateName(TemplateName Template) {
81      if (TemplateTemplateParmDecl *TTP
82            = dyn_cast_or_null<TemplateTemplateParmDecl>(
83                                                  Template.getAsTemplateDecl()))
84        if (TTP->isParameterPack())
85          Unexpanded.push_back(std::make_pair(TTP, SourceLocation()));
86
87      return inherited::TraverseTemplateName(Template);
88    }
89
90    /// \brief Suppress traversal into Objective-C container literal
91    /// elements that are pack expansions.
92    bool TraverseObjCDictionaryLiteral(ObjCDictionaryLiteral *E) {
93      if (!E->containsUnexpandedParameterPack())
94        return true;
95
96      for (unsigned I = 0, N = E->getNumElements(); I != N; ++I) {
97        ObjCDictionaryElement Element = E->getKeyValueElement(I);
98        if (Element.isPackExpansion())
99          continue;
100
101        TraverseStmt(Element.Key);
102        TraverseStmt(Element.Value);
103      }
104      return true;
105    }
106    //------------------------------------------------------------------------
107    // Pruning the search for unexpanded parameter packs.
108    //------------------------------------------------------------------------
109
110    /// \brief Suppress traversal into statements and expressions that
111    /// do not contain unexpanded parameter packs.
112    bool TraverseStmt(Stmt *S) {
113      Expr *E = dyn_cast_or_null<Expr>(S);
114      if ((E && E->containsUnexpandedParameterPack()) || InLambda)
115        return inherited::TraverseStmt(S);
116
117      return true;
118    }
119
120    /// \brief Suppress traversal into types that do not contain
121    /// unexpanded parameter packs.
122    bool TraverseType(QualType T) {
123      if ((!T.isNull() && T->containsUnexpandedParameterPack()) || InLambda)
124        return inherited::TraverseType(T);
125
126      return true;
127    }
128
129    /// \brief Suppress traversel into types with location information
130    /// that do not contain unexpanded parameter packs.
131    bool TraverseTypeLoc(TypeLoc TL) {
132      if ((!TL.getType().isNull() &&
133           TL.getType()->containsUnexpandedParameterPack()) ||
134          InLambda)
135        return inherited::TraverseTypeLoc(TL);
136
137      return true;
138    }
139
140    /// \brief Suppress traversal of non-parameter declarations, since
141    /// they cannot contain unexpanded parameter packs.
142    bool TraverseDecl(Decl *D) {
143      if ((D && isa<ParmVarDecl>(D)) || InLambda)
144        return inherited::TraverseDecl(D);
145
146      return true;
147    }
148
149    /// \brief Suppress traversal of template argument pack expansions.
150    bool TraverseTemplateArgument(const TemplateArgument &Arg) {
151      if (Arg.isPackExpansion())
152        return true;
153
154      return inherited::TraverseTemplateArgument(Arg);
155    }
156
157    /// \brief Suppress traversal of template argument pack expansions.
158    bool TraverseTemplateArgumentLoc(const TemplateArgumentLoc &ArgLoc) {
159      if (ArgLoc.getArgument().isPackExpansion())
160        return true;
161
162      return inherited::TraverseTemplateArgumentLoc(ArgLoc);
163    }
164
165    /// \brief Note whether we're traversing a lambda containing an unexpanded
166    /// parameter pack. In this case, the unexpanded pack can occur anywhere,
167    /// including all the places where we normally wouldn't look. Within a
168    /// lambda, we don't propagate the 'contains unexpanded parameter pack' bit
169    /// outside an expression.
170    bool TraverseLambdaExpr(LambdaExpr *Lambda) {
171      // The ContainsUnexpandedParameterPack bit on a lambda is always correct,
172      // even if it's contained within another lambda.
173      if (!Lambda->containsUnexpandedParameterPack())
174        return true;
175
176      bool WasInLambda = InLambda;
177      InLambda = true;
178
179      // If any capture names a function parameter pack, that pack is expanded
180      // when the lambda is expanded.
181      for (LambdaExpr::capture_iterator I = Lambda->capture_begin(),
182                                        E = Lambda->capture_end(); I != E; ++I)
183        if (VarDecl *VD = I->getCapturedVar())
184          if (VD->isParameterPack())
185            Unexpanded.push_back(std::make_pair(VD, I->getLocation()));
186
187      inherited::TraverseLambdaExpr(Lambda);
188
189      InLambda = WasInLambda;
190      return true;
191    }
192  };
193}
194
195/// \brief Diagnose all of the unexpanded parameter packs in the given
196/// vector.
197bool
198Sema::DiagnoseUnexpandedParameterPacks(SourceLocation Loc,
199                                       UnexpandedParameterPackContext UPPC,
200                                 ArrayRef<UnexpandedParameterPack> Unexpanded) {
201  if (Unexpanded.empty())
202    return false;
203
204  // If we are within a lambda expression, that lambda contains an unexpanded
205  // parameter pack, and we are done.
206  // FIXME: Store 'Unexpanded' on the lambda so we don't need to recompute it
207  // later.
208  for (unsigned N = FunctionScopes.size(); N; --N) {
209    if (sema::LambdaScopeInfo *LSI =
210          dyn_cast<sema::LambdaScopeInfo>(FunctionScopes[N-1])) {
211      LSI->ContainsUnexpandedParameterPack = true;
212      return false;
213    }
214  }
215
216  SmallVector<SourceLocation, 4> Locations;
217  SmallVector<IdentifierInfo *, 4> Names;
218  llvm::SmallPtrSet<IdentifierInfo *, 4> NamesKnown;
219
220  for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
221    IdentifierInfo *Name = 0;
222    if (const TemplateTypeParmType *TTP
223          = Unexpanded[I].first.dyn_cast<const TemplateTypeParmType *>())
224      Name = TTP->getIdentifier();
225    else
226      Name = Unexpanded[I].first.get<NamedDecl *>()->getIdentifier();
227
228    if (Name && NamesKnown.insert(Name))
229      Names.push_back(Name);
230
231    if (Unexpanded[I].second.isValid())
232      Locations.push_back(Unexpanded[I].second);
233  }
234
235  DiagnosticBuilder DB
236    = Names.size() == 0? Diag(Loc, diag::err_unexpanded_parameter_pack_0)
237                           << (int)UPPC
238    : Names.size() == 1? Diag(Loc, diag::err_unexpanded_parameter_pack_1)
239                           << (int)UPPC << Names[0]
240    : Names.size() == 2? Diag(Loc, diag::err_unexpanded_parameter_pack_2)
241                           << (int)UPPC << Names[0] << Names[1]
242    : Diag(Loc, diag::err_unexpanded_parameter_pack_3_or_more)
243        << (int)UPPC << Names[0] << Names[1];
244
245  for (unsigned I = 0, N = Locations.size(); I != N; ++I)
246    DB << SourceRange(Locations[I]);
247  return true;
248}
249
250bool Sema::DiagnoseUnexpandedParameterPack(SourceLocation Loc,
251                                           TypeSourceInfo *T,
252                                         UnexpandedParameterPackContext UPPC) {
253  // C++0x [temp.variadic]p5:
254  //   An appearance of a name of a parameter pack that is not expanded is
255  //   ill-formed.
256  if (!T->getType()->containsUnexpandedParameterPack())
257    return false;
258
259  SmallVector<UnexpandedParameterPack, 2> Unexpanded;
260  CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseTypeLoc(
261                                                              T->getTypeLoc());
262  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
263  return DiagnoseUnexpandedParameterPacks(Loc, UPPC, Unexpanded);
264}
265
266bool Sema::DiagnoseUnexpandedParameterPack(Expr *E,
267                                        UnexpandedParameterPackContext UPPC) {
268  // C++0x [temp.variadic]p5:
269  //   An appearance of a name of a parameter pack that is not expanded is
270  //   ill-formed.
271  if (!E->containsUnexpandedParameterPack())
272    return false;
273
274  SmallVector<UnexpandedParameterPack, 2> Unexpanded;
275  CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseStmt(E);
276  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
277  return DiagnoseUnexpandedParameterPacks(E->getLocStart(), UPPC, Unexpanded);
278}
279
280bool Sema::DiagnoseUnexpandedParameterPack(const CXXScopeSpec &SS,
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 (!SS.getScopeRep() ||
286      !SS.getScopeRep()->containsUnexpandedParameterPack())
287    return false;
288
289  SmallVector<UnexpandedParameterPack, 2> Unexpanded;
290  CollectUnexpandedParameterPacksVisitor(Unexpanded)
291    .TraverseNestedNameSpecifier(SS.getScopeRep());
292  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
293  return DiagnoseUnexpandedParameterPacks(SS.getRange().getBegin(),
294                                          UPPC, Unexpanded);
295}
296
297bool Sema::DiagnoseUnexpandedParameterPack(const DeclarationNameInfo &NameInfo,
298                                         UnexpandedParameterPackContext UPPC) {
299  // C++0x [temp.variadic]p5:
300  //   An appearance of a name of a parameter pack that is not expanded is
301  //   ill-formed.
302  switch (NameInfo.getName().getNameKind()) {
303  case DeclarationName::Identifier:
304  case DeclarationName::ObjCZeroArgSelector:
305  case DeclarationName::ObjCOneArgSelector:
306  case DeclarationName::ObjCMultiArgSelector:
307  case DeclarationName::CXXOperatorName:
308  case DeclarationName::CXXLiteralOperatorName:
309  case DeclarationName::CXXUsingDirective:
310    return false;
311
312  case DeclarationName::CXXConstructorName:
313  case DeclarationName::CXXDestructorName:
314  case DeclarationName::CXXConversionFunctionName:
315    // FIXME: We shouldn't need this null check!
316    if (TypeSourceInfo *TSInfo = NameInfo.getNamedTypeInfo())
317      return DiagnoseUnexpandedParameterPack(NameInfo.getLoc(), TSInfo, UPPC);
318
319    if (!NameInfo.getName().getCXXNameType()->containsUnexpandedParameterPack())
320      return false;
321
322    break;
323  }
324
325  SmallVector<UnexpandedParameterPack, 2> Unexpanded;
326  CollectUnexpandedParameterPacksVisitor(Unexpanded)
327    .TraverseType(NameInfo.getName().getCXXNameType());
328  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
329  return DiagnoseUnexpandedParameterPacks(NameInfo.getLoc(), UPPC, Unexpanded);
330}
331
332bool Sema::DiagnoseUnexpandedParameterPack(SourceLocation Loc,
333                                           TemplateName Template,
334                                       UnexpandedParameterPackContext UPPC) {
335
336  if (Template.isNull() || !Template.containsUnexpandedParameterPack())
337    return false;
338
339  SmallVector<UnexpandedParameterPack, 2> Unexpanded;
340  CollectUnexpandedParameterPacksVisitor(Unexpanded)
341    .TraverseTemplateName(Template);
342  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
343  return DiagnoseUnexpandedParameterPacks(Loc, UPPC, Unexpanded);
344}
345
346bool Sema::DiagnoseUnexpandedParameterPack(TemplateArgumentLoc Arg,
347                                         UnexpandedParameterPackContext UPPC) {
348  if (Arg.getArgument().isNull() ||
349      !Arg.getArgument().containsUnexpandedParameterPack())
350    return false;
351
352  SmallVector<UnexpandedParameterPack, 2> Unexpanded;
353  CollectUnexpandedParameterPacksVisitor(Unexpanded)
354    .TraverseTemplateArgumentLoc(Arg);
355  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
356  return DiagnoseUnexpandedParameterPacks(Arg.getLocation(), UPPC, Unexpanded);
357}
358
359void Sema::collectUnexpandedParameterPacks(TemplateArgument Arg,
360                   SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
361  CollectUnexpandedParameterPacksVisitor(Unexpanded)
362    .TraverseTemplateArgument(Arg);
363}
364
365void Sema::collectUnexpandedParameterPacks(TemplateArgumentLoc Arg,
366                   SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
367  CollectUnexpandedParameterPacksVisitor(Unexpanded)
368    .TraverseTemplateArgumentLoc(Arg);
369}
370
371void Sema::collectUnexpandedParameterPacks(QualType T,
372                   SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
373  CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseType(T);
374}
375
376void Sema::collectUnexpandedParameterPacks(TypeLoc TL,
377                   SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
378  CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseTypeLoc(TL);
379}
380
381void Sema::collectUnexpandedParameterPacks(CXXScopeSpec &SS,
382                                           SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
383  NestedNameSpecifier *Qualifier = SS.getScopeRep();
384  if (!Qualifier)
385    return;
386
387  NestedNameSpecifierLoc QualifierLoc(Qualifier, SS.location_data());
388  CollectUnexpandedParameterPacksVisitor(Unexpanded)
389    .TraverseNestedNameSpecifierLoc(QualifierLoc);
390}
391
392void Sema::collectUnexpandedParameterPacks(const DeclarationNameInfo &NameInfo,
393                         SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
394  CollectUnexpandedParameterPacksVisitor(Unexpanded)
395    .TraverseDeclarationNameInfo(NameInfo);
396}
397
398
399ParsedTemplateArgument
400Sema::ActOnPackExpansion(const ParsedTemplateArgument &Arg,
401                         SourceLocation EllipsisLoc) {
402  if (Arg.isInvalid())
403    return Arg;
404
405  switch (Arg.getKind()) {
406  case ParsedTemplateArgument::Type: {
407    TypeResult Result = ActOnPackExpansion(Arg.getAsType(), EllipsisLoc);
408    if (Result.isInvalid())
409      return ParsedTemplateArgument();
410
411    return ParsedTemplateArgument(Arg.getKind(), Result.get().getAsOpaquePtr(),
412                                  Arg.getLocation());
413  }
414
415  case ParsedTemplateArgument::NonType: {
416    ExprResult Result = ActOnPackExpansion(Arg.getAsExpr(), EllipsisLoc);
417    if (Result.isInvalid())
418      return ParsedTemplateArgument();
419
420    return ParsedTemplateArgument(Arg.getKind(), Result.get(),
421                                  Arg.getLocation());
422  }
423
424  case ParsedTemplateArgument::Template:
425    if (!Arg.getAsTemplate().get().containsUnexpandedParameterPack()) {
426      SourceRange R(Arg.getLocation());
427      if (Arg.getScopeSpec().isValid())
428        R.setBegin(Arg.getScopeSpec().getBeginLoc());
429      Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
430        << R;
431      return ParsedTemplateArgument();
432    }
433
434    return Arg.getTemplatePackExpansion(EllipsisLoc);
435  }
436  llvm_unreachable("Unhandled template argument kind?");
437}
438
439TypeResult Sema::ActOnPackExpansion(ParsedType Type,
440                                    SourceLocation EllipsisLoc) {
441  TypeSourceInfo *TSInfo;
442  GetTypeFromParser(Type, &TSInfo);
443  if (!TSInfo)
444    return true;
445
446  TypeSourceInfo *TSResult =
447      CheckPackExpansion(TSInfo, EllipsisLoc, Optional<unsigned>());
448  if (!TSResult)
449    return true;
450
451  return CreateParsedType(TSResult->getType(), TSResult);
452}
453
454TypeSourceInfo *
455Sema::CheckPackExpansion(TypeSourceInfo *Pattern, SourceLocation EllipsisLoc,
456                         Optional<unsigned> NumExpansions) {
457  // Create the pack expansion type and source-location information.
458  QualType Result = CheckPackExpansion(Pattern->getType(),
459                                       Pattern->getTypeLoc().getSourceRange(),
460                                       EllipsisLoc, NumExpansions);
461  if (Result.isNull())
462    return 0;
463
464  TypeSourceInfo *TSResult = Context.CreateTypeSourceInfo(Result);
465  PackExpansionTypeLoc TL =
466      TSResult->getTypeLoc().castAs<PackExpansionTypeLoc>();
467  TL.setEllipsisLoc(EllipsisLoc);
468
469  // Copy over the source-location information from the type.
470  memcpy(TL.getNextTypeLoc().getOpaqueData(),
471         Pattern->getTypeLoc().getOpaqueData(),
472         Pattern->getTypeLoc().getFullDataSize());
473  return TSResult;
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, Optional<unsigned>());
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 Optional<unsigned>();
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 Optional<unsigned>();
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_unknown_anytype:
732  case TST_image1d_t:
733  case TST_image1d_array_t:
734  case TST_image1d_buffer_t:
735  case TST_image2d_t:
736  case TST_image2d_array_t:
737  case TST_image3d_t:
738  case TST_sampler_t:
739  case TST_event_t:
740  case TST_error:
741    break;
742  }
743
744  for (unsigned I = 0, N = D.getNumTypeObjects(); I != N; ++I) {
745    const DeclaratorChunk &Chunk = D.getTypeObject(I);
746    switch (Chunk.Kind) {
747    case DeclaratorChunk::Pointer:
748    case DeclaratorChunk::Reference:
749    case DeclaratorChunk::Paren:
750      // These declarator chunks cannot contain any parameter packs.
751      break;
752
753    case DeclaratorChunk::Array:
754    case DeclaratorChunk::Function:
755    case DeclaratorChunk::BlockPointer:
756      // Syntactically, these kinds of declarator chunks all come after the
757      // declarator-id (conceptually), so the parser should not invoke this
758      // routine at this time.
759      llvm_unreachable("Could not have seen this kind of declarator chunk");
760
761    case DeclaratorChunk::MemberPointer:
762      if (Chunk.Mem.Scope().getScopeRep() &&
763          Chunk.Mem.Scope().getScopeRep()->containsUnexpandedParameterPack())
764        return true;
765      break;
766    }
767  }
768
769  return false;
770}
771
772namespace {
773
774// Callback to only accept typo corrections that refer to parameter packs.
775class ParameterPackValidatorCCC : public CorrectionCandidateCallback {
776 public:
777  virtual bool ValidateCandidate(const TypoCorrection &candidate) {
778    NamedDecl *ND = candidate.getCorrectionDecl();
779    return ND && ND->isParameterPack();
780  }
781};
782
783}
784
785/// \brief Called when an expression computing the size of a parameter pack
786/// is parsed.
787///
788/// \code
789/// template<typename ...Types> struct count {
790///   static const unsigned value = sizeof...(Types);
791/// };
792/// \endcode
793///
794//
795/// \param OpLoc The location of the "sizeof" keyword.
796/// \param Name The name of the parameter pack whose size will be determined.
797/// \param NameLoc The source location of the name of the parameter pack.
798/// \param RParenLoc The location of the closing parentheses.
799ExprResult Sema::ActOnSizeofParameterPackExpr(Scope *S,
800                                              SourceLocation OpLoc,
801                                              IdentifierInfo &Name,
802                                              SourceLocation NameLoc,
803                                              SourceLocation RParenLoc) {
804  // C++0x [expr.sizeof]p5:
805  //   The identifier in a sizeof... expression shall name a parameter pack.
806  LookupResult R(*this, &Name, NameLoc, LookupOrdinaryName);
807  LookupName(R, S);
808
809  NamedDecl *ParameterPack = 0;
810  ParameterPackValidatorCCC Validator;
811  switch (R.getResultKind()) {
812  case LookupResult::Found:
813    ParameterPack = R.getFoundDecl();
814    break;
815
816  case LookupResult::NotFound:
817  case LookupResult::NotFoundInCurrentInstantiation:
818    if (TypoCorrection Corrected = CorrectTypo(R.getLookupNameInfo(),
819                                               R.getLookupKind(), S, 0,
820                                               Validator)) {
821      std::string CorrectedQuotedStr(Corrected.getQuoted(getLangOpts()));
822      ParameterPack = Corrected.getCorrectionDecl();
823      Diag(NameLoc, diag::err_sizeof_pack_no_pack_name_suggest)
824        << &Name << CorrectedQuotedStr
825        << FixItHint::CreateReplacement(
826            NameLoc, Corrected.getAsString(getLangOpts()));
827      Diag(ParameterPack->getLocation(), diag::note_parameter_pack_here)
828        << CorrectedQuotedStr;
829    }
830
831  case LookupResult::FoundOverloaded:
832  case LookupResult::FoundUnresolvedValue:
833    break;
834
835  case LookupResult::Ambiguous:
836    DiagnoseAmbiguousLookup(R);
837    return ExprError();
838  }
839
840  if (!ParameterPack || !ParameterPack->isParameterPack()) {
841    Diag(NameLoc, diag::err_sizeof_pack_no_pack_name)
842      << &Name;
843    return ExprError();
844  }
845
846  MarkAnyDeclReferenced(OpLoc, ParameterPack, true);
847
848  return new (Context) SizeOfPackExpr(Context.getSizeType(), OpLoc,
849                                      ParameterPack, NameLoc, RParenLoc);
850}
851