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