1//===------- SemaTemplateVariadic.cpp - C++ Variadic Templates ------------===/
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//===----------------------------------------------------------------------===/
8//
9//  This file implements semantic analysis for C++0x variadic templates.
10//===----------------------------------------------------------------------===/
11
12#include "clang/Sema/Sema.h"
13#include "TypeLocBuilder.h"
14#include "clang/AST/Expr.h"
15#include "clang/AST/RecursiveASTVisitor.h"
16#include "clang/AST/TypeLoc.h"
17#include "clang/Sema/Lookup.h"
18#include "clang/Sema/ParsedTemplate.h"
19#include "clang/Sema/ScopeInfo.h"
20#include "clang/Sema/SemaInternal.h"
21#include "clang/Sema/Template.h"
22
23using namespace clang;
24
25//----------------------------------------------------------------------------
26// Visitor that collects unexpanded parameter packs
27//----------------------------------------------------------------------------
28
29namespace {
30  /// \brief A class that collects unexpanded parameter packs.
31  class CollectUnexpandedParameterPacksVisitor :
32    public RecursiveASTVisitor<CollectUnexpandedParameterPacksVisitor>
33  {
34    typedef RecursiveASTVisitor<CollectUnexpandedParameterPacksVisitor>
35      inherited;
36
37    SmallVectorImpl<UnexpandedParameterPack> &Unexpanded;
38
39    bool InLambda;
40
41  public:
42    explicit CollectUnexpandedParameterPacksVisitor(
43                  SmallVectorImpl<UnexpandedParameterPack> &Unexpanded)
44      : Unexpanded(Unexpanded), InLambda(false) { }
45
46    bool shouldWalkTypesOfTypeLocs() const { return false; }
47
48    //------------------------------------------------------------------------
49    // Recording occurrences of (unexpanded) parameter packs.
50    //------------------------------------------------------------------------
51
52    /// \brief Record occurrences of template type parameter packs.
53    bool VisitTemplateTypeParmTypeLoc(TemplateTypeParmTypeLoc TL) {
54      if (TL.getTypePtr()->isParameterPack())
55        Unexpanded.push_back(std::make_pair(TL.getTypePtr(), TL.getNameLoc()));
56      return true;
57    }
58
59    /// \brief Record occurrences of template type parameter packs
60    /// when we don't have proper source-location information for
61    /// them.
62    ///
63    /// Ideally, this routine would never be used.
64    bool VisitTemplateTypeParmType(TemplateTypeParmType *T) {
65      if (T->isParameterPack())
66        Unexpanded.push_back(std::make_pair(T, SourceLocation()));
67
68      return true;
69    }
70
71    /// \brief Record occurrences of function and non-type template
72    /// parameter packs in an expression.
73    bool VisitDeclRefExpr(DeclRefExpr *E) {
74      if (E->getDecl()->isParameterPack())
75        Unexpanded.push_back(std::make_pair(E->getDecl(), E->getLocation()));
76
77      return true;
78    }
79
80    /// \brief Record occurrences of template template parameter packs.
81    bool TraverseTemplateName(TemplateName Template) {
82      if (TemplateTemplateParmDecl *TTP
83            = dyn_cast_or_null<TemplateTemplateParmDecl>(
84                                                  Template.getAsTemplateDecl()))
85        if (TTP->isParameterPack())
86          Unexpanded.push_back(std::make_pair(TTP, SourceLocation()));
87
88      return inherited::TraverseTemplateName(Template);
89    }
90
91    /// \brief Suppress traversal into Objective-C container literal
92    /// elements that are pack expansions.
93    bool TraverseObjCDictionaryLiteral(ObjCDictionaryLiteral *E) {
94      if (!E->containsUnexpandedParameterPack())
95        return true;
96
97      for (unsigned I = 0, N = E->getNumElements(); I != N; ++I) {
98        ObjCDictionaryElement Element = E->getKeyValueElement(I);
99        if (Element.isPackExpansion())
100          continue;
101
102        TraverseStmt(Element.Key);
103        TraverseStmt(Element.Value);
104      }
105      return true;
106    }
107    //------------------------------------------------------------------------
108    // Pruning the search for unexpanded parameter packs.
109    //------------------------------------------------------------------------
110
111    /// \brief Suppress traversal into statements and expressions that
112    /// do not contain unexpanded parameter packs.
113    bool TraverseStmt(Stmt *S) {
114      Expr *E = dyn_cast_or_null<Expr>(S);
115      if ((E && E->containsUnexpandedParameterPack()) || InLambda)
116        return inherited::TraverseStmt(S);
117
118      return true;
119    }
120
121    /// \brief Suppress traversal into types that do not contain
122    /// unexpanded parameter packs.
123    bool TraverseType(QualType T) {
124      if ((!T.isNull() && T->containsUnexpandedParameterPack()) || InLambda)
125        return inherited::TraverseType(T);
126
127      return true;
128    }
129
130    /// \brief Suppress traversel into types with location information
131    /// that do not contain unexpanded parameter packs.
132    bool TraverseTypeLoc(TypeLoc TL) {
133      if ((!TL.getType().isNull() &&
134           TL.getType()->containsUnexpandedParameterPack()) ||
135          InLambda)
136        return inherited::TraverseTypeLoc(TL);
137
138      return true;
139    }
140
141    /// \brief Suppress traversal of non-parameter declarations, since
142    /// they cannot contain unexpanded parameter packs.
143    bool TraverseDecl(Decl *D) {
144      if ((D && isa<ParmVarDecl>(D)) || InLambda)
145        return inherited::TraverseDecl(D);
146
147      return true;
148    }
149
150    /// \brief Suppress traversal of template argument pack expansions.
151    bool TraverseTemplateArgument(const TemplateArgument &Arg) {
152      if (Arg.isPackExpansion())
153        return true;
154
155      return inherited::TraverseTemplateArgument(Arg);
156    }
157
158    /// \brief Suppress traversal of template argument pack expansions.
159    bool TraverseTemplateArgumentLoc(const TemplateArgumentLoc &ArgLoc) {
160      if (ArgLoc.getArgument().isPackExpansion())
161        return true;
162
163      return inherited::TraverseTemplateArgumentLoc(ArgLoc);
164    }
165
166    /// \brief Note whether we're traversing a lambda containing an unexpanded
167    /// parameter pack. In this case, the unexpanded pack can occur anywhere,
168    /// including all the places where we normally wouldn't look. Within a
169    /// lambda, we don't propagate the 'contains unexpanded parameter pack' bit
170    /// outside an expression.
171    bool TraverseLambdaExpr(LambdaExpr *Lambda) {
172      // The ContainsUnexpandedParameterPack bit on a lambda is always correct,
173      // even if it's contained within another lambda.
174      if (!Lambda->containsUnexpandedParameterPack())
175        return true;
176
177      bool WasInLambda = InLambda;
178      InLambda = true;
179
180      // If any capture names a function parameter pack, that pack is expanded
181      // when the lambda is expanded.
182      for (LambdaExpr::capture_iterator I = Lambda->capture_begin(),
183                                        E = Lambda->capture_end();
184           I != E; ++I) {
185        if (I->capturesVariable()) {
186          VarDecl *VD = I->getCapturedVar();
187          if (VD->isParameterPack())
188            Unexpanded.push_back(std::make_pair(VD, I->getLocation()));
189        }
190      }
191
192      inherited::TraverseLambdaExpr(Lambda);
193
194      InLambda = WasInLambda;
195      return true;
196    }
197  };
198}
199
200/// \brief Determine whether it's possible for an unexpanded parameter pack to
201/// be valid in this location. This only happens when we're in a declaration
202/// that is nested within an expression that could be expanded, such as a
203/// lambda-expression within a function call.
204///
205/// This is conservatively correct, but may claim that some unexpanded packs are
206/// permitted when they are not.
207bool Sema::isUnexpandedParameterPackPermitted() {
208  for (auto *SI : FunctionScopes)
209    if (isa<sema::LambdaScopeInfo>(SI))
210      return true;
211  return false;
212}
213
214/// \brief Diagnose all of the unexpanded parameter packs in the given
215/// vector.
216bool
217Sema::DiagnoseUnexpandedParameterPacks(SourceLocation Loc,
218                                       UnexpandedParameterPackContext UPPC,
219                                 ArrayRef<UnexpandedParameterPack> Unexpanded) {
220  if (Unexpanded.empty())
221    return false;
222
223  // If we are within a lambda expression, that lambda contains an unexpanded
224  // parameter pack, and we are done.
225  // FIXME: Store 'Unexpanded' on the lambda so we don't need to recompute it
226  // later.
227  for (unsigned N = FunctionScopes.size(); N; --N) {
228    if (sema::LambdaScopeInfo *LSI =
229          dyn_cast<sema::LambdaScopeInfo>(FunctionScopes[N-1])) {
230      LSI->ContainsUnexpandedParameterPack = true;
231      return false;
232    }
233  }
234
235  SmallVector<SourceLocation, 4> Locations;
236  SmallVector<IdentifierInfo *, 4> Names;
237  llvm::SmallPtrSet<IdentifierInfo *, 4> NamesKnown;
238
239  for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
240    IdentifierInfo *Name = nullptr;
241    if (const TemplateTypeParmType *TTP
242          = Unexpanded[I].first.dyn_cast<const TemplateTypeParmType *>())
243      Name = TTP->getIdentifier();
244    else
245      Name = Unexpanded[I].first.get<NamedDecl *>()->getIdentifier();
246
247    if (Name && NamesKnown.insert(Name).second)
248      Names.push_back(Name);
249
250    if (Unexpanded[I].second.isValid())
251      Locations.push_back(Unexpanded[I].second);
252  }
253
254  DiagnosticBuilder DB = Diag(Loc, diag::err_unexpanded_parameter_pack)
255                         << (int)UPPC << (int)Names.size();
256  for (size_t I = 0, E = std::min(Names.size(), (size_t)2); I != E; ++I)
257    DB << Names[I];
258
259  for (unsigned I = 0, N = Locations.size(); I != N; ++I)
260    DB << SourceRange(Locations[I]);
261  return true;
262}
263
264bool Sema::DiagnoseUnexpandedParameterPack(SourceLocation Loc,
265                                           TypeSourceInfo *T,
266                                         UnexpandedParameterPackContext UPPC) {
267  // C++0x [temp.variadic]p5:
268  //   An appearance of a name of a parameter pack that is not expanded is
269  //   ill-formed.
270  if (!T->getType()->containsUnexpandedParameterPack())
271    return false;
272
273  SmallVector<UnexpandedParameterPack, 2> Unexpanded;
274  CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseTypeLoc(
275                                                              T->getTypeLoc());
276  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
277  return DiagnoseUnexpandedParameterPacks(Loc, UPPC, Unexpanded);
278}
279
280bool Sema::DiagnoseUnexpandedParameterPack(Expr *E,
281                                        UnexpandedParameterPackContext UPPC) {
282  // C++0x [temp.variadic]p5:
283  //   An appearance of a name of a parameter pack that is not expanded is
284  //   ill-formed.
285  if (!E->containsUnexpandedParameterPack())
286    return false;
287
288  SmallVector<UnexpandedParameterPack, 2> Unexpanded;
289  CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseStmt(E);
290  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
291  return DiagnoseUnexpandedParameterPacks(E->getLocStart(), UPPC, Unexpanded);
292}
293
294bool Sema::DiagnoseUnexpandedParameterPack(const CXXScopeSpec &SS,
295                                        UnexpandedParameterPackContext UPPC) {
296  // C++0x [temp.variadic]p5:
297  //   An appearance of a name of a parameter pack that is not expanded is
298  //   ill-formed.
299  if (!SS.getScopeRep() ||
300      !SS.getScopeRep()->containsUnexpandedParameterPack())
301    return false;
302
303  SmallVector<UnexpandedParameterPack, 2> Unexpanded;
304  CollectUnexpandedParameterPacksVisitor(Unexpanded)
305    .TraverseNestedNameSpecifier(SS.getScopeRep());
306  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
307  return DiagnoseUnexpandedParameterPacks(SS.getRange().getBegin(),
308                                          UPPC, Unexpanded);
309}
310
311bool Sema::DiagnoseUnexpandedParameterPack(const DeclarationNameInfo &NameInfo,
312                                         UnexpandedParameterPackContext UPPC) {
313  // C++0x [temp.variadic]p5:
314  //   An appearance of a name of a parameter pack that is not expanded is
315  //   ill-formed.
316  switch (NameInfo.getName().getNameKind()) {
317  case DeclarationName::Identifier:
318  case DeclarationName::ObjCZeroArgSelector:
319  case DeclarationName::ObjCOneArgSelector:
320  case DeclarationName::ObjCMultiArgSelector:
321  case DeclarationName::CXXOperatorName:
322  case DeclarationName::CXXLiteralOperatorName:
323  case DeclarationName::CXXUsingDirective:
324    return false;
325
326  case DeclarationName::CXXConstructorName:
327  case DeclarationName::CXXDestructorName:
328  case DeclarationName::CXXConversionFunctionName:
329    // FIXME: We shouldn't need this null check!
330    if (TypeSourceInfo *TSInfo = NameInfo.getNamedTypeInfo())
331      return DiagnoseUnexpandedParameterPack(NameInfo.getLoc(), TSInfo, UPPC);
332
333    if (!NameInfo.getName().getCXXNameType()->containsUnexpandedParameterPack())
334      return false;
335
336    break;
337  }
338
339  SmallVector<UnexpandedParameterPack, 2> Unexpanded;
340  CollectUnexpandedParameterPacksVisitor(Unexpanded)
341    .TraverseType(NameInfo.getName().getCXXNameType());
342  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
343  return DiagnoseUnexpandedParameterPacks(NameInfo.getLoc(), UPPC, Unexpanded);
344}
345
346bool Sema::DiagnoseUnexpandedParameterPack(SourceLocation Loc,
347                                           TemplateName Template,
348                                       UnexpandedParameterPackContext UPPC) {
349
350  if (Template.isNull() || !Template.containsUnexpandedParameterPack())
351    return false;
352
353  SmallVector<UnexpandedParameterPack, 2> Unexpanded;
354  CollectUnexpandedParameterPacksVisitor(Unexpanded)
355    .TraverseTemplateName(Template);
356  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
357  return DiagnoseUnexpandedParameterPacks(Loc, UPPC, Unexpanded);
358}
359
360bool Sema::DiagnoseUnexpandedParameterPack(TemplateArgumentLoc Arg,
361                                         UnexpandedParameterPackContext UPPC) {
362  if (Arg.getArgument().isNull() ||
363      !Arg.getArgument().containsUnexpandedParameterPack())
364    return false;
365
366  SmallVector<UnexpandedParameterPack, 2> Unexpanded;
367  CollectUnexpandedParameterPacksVisitor(Unexpanded)
368    .TraverseTemplateArgumentLoc(Arg);
369  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
370  return DiagnoseUnexpandedParameterPacks(Arg.getLocation(), UPPC, Unexpanded);
371}
372
373void Sema::collectUnexpandedParameterPacks(TemplateArgument Arg,
374                   SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
375  CollectUnexpandedParameterPacksVisitor(Unexpanded)
376    .TraverseTemplateArgument(Arg);
377}
378
379void Sema::collectUnexpandedParameterPacks(TemplateArgumentLoc Arg,
380                   SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
381  CollectUnexpandedParameterPacksVisitor(Unexpanded)
382    .TraverseTemplateArgumentLoc(Arg);
383}
384
385void Sema::collectUnexpandedParameterPacks(QualType T,
386                   SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
387  CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseType(T);
388}
389
390void Sema::collectUnexpandedParameterPacks(TypeLoc TL,
391                   SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
392  CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseTypeLoc(TL);
393}
394
395void Sema::collectUnexpandedParameterPacks(CXXScopeSpec &SS,
396                                           SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
397  NestedNameSpecifier *Qualifier = SS.getScopeRep();
398  if (!Qualifier)
399    return;
400
401  NestedNameSpecifierLoc QualifierLoc(Qualifier, SS.location_data());
402  CollectUnexpandedParameterPacksVisitor(Unexpanded)
403    .TraverseNestedNameSpecifierLoc(QualifierLoc);
404}
405
406void Sema::collectUnexpandedParameterPacks(const DeclarationNameInfo &NameInfo,
407                         SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
408  CollectUnexpandedParameterPacksVisitor(Unexpanded)
409    .TraverseDeclarationNameInfo(NameInfo);
410}
411
412
413ParsedTemplateArgument
414Sema::ActOnPackExpansion(const ParsedTemplateArgument &Arg,
415                         SourceLocation EllipsisLoc) {
416  if (Arg.isInvalid())
417    return Arg;
418
419  switch (Arg.getKind()) {
420  case ParsedTemplateArgument::Type: {
421    TypeResult Result = ActOnPackExpansion(Arg.getAsType(), EllipsisLoc);
422    if (Result.isInvalid())
423      return ParsedTemplateArgument();
424
425    return ParsedTemplateArgument(Arg.getKind(), Result.get().getAsOpaquePtr(),
426                                  Arg.getLocation());
427  }
428
429  case ParsedTemplateArgument::NonType: {
430    ExprResult Result = ActOnPackExpansion(Arg.getAsExpr(), EllipsisLoc);
431    if (Result.isInvalid())
432      return ParsedTemplateArgument();
433
434    return ParsedTemplateArgument(Arg.getKind(), Result.get(),
435                                  Arg.getLocation());
436  }
437
438  case ParsedTemplateArgument::Template:
439    if (!Arg.getAsTemplate().get().containsUnexpandedParameterPack()) {
440      SourceRange R(Arg.getLocation());
441      if (Arg.getScopeSpec().isValid())
442        R.setBegin(Arg.getScopeSpec().getBeginLoc());
443      Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
444        << R;
445      return ParsedTemplateArgument();
446    }
447
448    return Arg.getTemplatePackExpansion(EllipsisLoc);
449  }
450  llvm_unreachable("Unhandled template argument kind?");
451}
452
453TypeResult Sema::ActOnPackExpansion(ParsedType Type,
454                                    SourceLocation EllipsisLoc) {
455  TypeSourceInfo *TSInfo;
456  GetTypeFromParser(Type, &TSInfo);
457  if (!TSInfo)
458    return true;
459
460  TypeSourceInfo *TSResult = CheckPackExpansion(TSInfo, EllipsisLoc, None);
461  if (!TSResult)
462    return true;
463
464  return CreateParsedType(TSResult->getType(), TSResult);
465}
466
467TypeSourceInfo *
468Sema::CheckPackExpansion(TypeSourceInfo *Pattern, SourceLocation EllipsisLoc,
469                         Optional<unsigned> NumExpansions) {
470  // Create the pack expansion type and source-location information.
471  QualType Result = CheckPackExpansion(Pattern->getType(),
472                                       Pattern->getTypeLoc().getSourceRange(),
473                                       EllipsisLoc, NumExpansions);
474  if (Result.isNull())
475    return nullptr;
476
477  TypeLocBuilder TLB;
478  TLB.pushFullCopy(Pattern->getTypeLoc());
479  PackExpansionTypeLoc TL = TLB.push<PackExpansionTypeLoc>(Result);
480  TL.setEllipsisLoc(EllipsisLoc);
481
482  return TLB.getTypeSourceInfo(Context, Result);
483}
484
485QualType Sema::CheckPackExpansion(QualType Pattern, SourceRange PatternRange,
486                                  SourceLocation EllipsisLoc,
487                                  Optional<unsigned> NumExpansions) {
488  // C++0x [temp.variadic]p5:
489  //   The pattern of a pack expansion shall name one or more
490  //   parameter packs that are not expanded by a nested pack
491  //   expansion.
492  if (!Pattern->containsUnexpandedParameterPack()) {
493    Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
494      << PatternRange;
495    return QualType();
496  }
497
498  return Context.getPackExpansionType(Pattern, NumExpansions);
499}
500
501ExprResult Sema::ActOnPackExpansion(Expr *Pattern, SourceLocation EllipsisLoc) {
502  return CheckPackExpansion(Pattern, EllipsisLoc, None);
503}
504
505ExprResult Sema::CheckPackExpansion(Expr *Pattern, SourceLocation EllipsisLoc,
506                                    Optional<unsigned> NumExpansions) {
507  if (!Pattern)
508    return ExprError();
509
510  // C++0x [temp.variadic]p5:
511  //   The pattern of a pack expansion shall name one or more
512  //   parameter packs that are not expanded by a nested pack
513  //   expansion.
514  if (!Pattern->containsUnexpandedParameterPack()) {
515    Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
516    << Pattern->getSourceRange();
517    return ExprError();
518  }
519
520  // Create the pack expansion expression and source-location information.
521  return new (Context)
522    PackExpansionExpr(Context.DependentTy, Pattern, EllipsisLoc, NumExpansions);
523}
524
525/// \brief Retrieve the depth and index of a parameter pack.
526static std::pair<unsigned, unsigned>
527getDepthAndIndex(NamedDecl *ND) {
528  if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(ND))
529    return std::make_pair(TTP->getDepth(), TTP->getIndex());
530
531  if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(ND))
532    return std::make_pair(NTTP->getDepth(), NTTP->getIndex());
533
534  TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(ND);
535  return std::make_pair(TTP->getDepth(), TTP->getIndex());
536}
537
538bool Sema::CheckParameterPacksForExpansion(
539    SourceLocation EllipsisLoc, SourceRange PatternRange,
540    ArrayRef<UnexpandedParameterPack> Unexpanded,
541    const MultiLevelTemplateArgumentList &TemplateArgs, bool &ShouldExpand,
542    bool &RetainExpansion, Optional<unsigned> &NumExpansions) {
543  ShouldExpand = true;
544  RetainExpansion = false;
545  std::pair<IdentifierInfo *, SourceLocation> FirstPack;
546  bool HaveFirstPack = false;
547
548  for (ArrayRef<UnexpandedParameterPack>::iterator i = Unexpanded.begin(),
549                                                 end = Unexpanded.end();
550                                                  i != end; ++i) {
551    // Compute the depth and index for this parameter pack.
552    unsigned Depth = 0, Index = 0;
553    IdentifierInfo *Name;
554    bool IsFunctionParameterPack = false;
555
556    if (const TemplateTypeParmType *TTP
557        = i->first.dyn_cast<const TemplateTypeParmType *>()) {
558      Depth = TTP->getDepth();
559      Index = TTP->getIndex();
560      Name = TTP->getIdentifier();
561    } else {
562      NamedDecl *ND = i->first.get<NamedDecl *>();
563      if (isa<ParmVarDecl>(ND))
564        IsFunctionParameterPack = true;
565      else
566        std::tie(Depth, Index) = getDepthAndIndex(ND);
567
568      Name = ND->getIdentifier();
569    }
570
571    // Determine the size of this argument pack.
572    unsigned NewPackSize;
573    if (IsFunctionParameterPack) {
574      // Figure out whether we're instantiating to an argument pack or not.
575      typedef LocalInstantiationScope::DeclArgumentPack DeclArgumentPack;
576
577      llvm::PointerUnion<Decl *, DeclArgumentPack *> *Instantiation
578        = CurrentInstantiationScope->findInstantiationOf(
579                                        i->first.get<NamedDecl *>());
580      if (Instantiation->is<DeclArgumentPack *>()) {
581        // We could expand this function parameter pack.
582        NewPackSize = Instantiation->get<DeclArgumentPack *>()->size();
583      } else {
584        // We can't expand this function parameter pack, so we can't expand
585        // the pack expansion.
586        ShouldExpand = false;
587        continue;
588      }
589    } else {
590      // If we don't have a template argument at this depth/index, then we
591      // cannot expand the pack expansion. Make a note of this, but we still
592      // want to check any parameter packs we *do* have arguments for.
593      if (Depth >= TemplateArgs.getNumLevels() ||
594          !TemplateArgs.hasTemplateArgument(Depth, Index)) {
595        ShouldExpand = false;
596        continue;
597      }
598
599      // Determine the size of the argument pack.
600      NewPackSize = TemplateArgs(Depth, Index).pack_size();
601    }
602
603    // C++0x [temp.arg.explicit]p9:
604    //   Template argument deduction can extend the sequence of template
605    //   arguments corresponding to a template parameter pack, even when the
606    //   sequence contains explicitly specified template arguments.
607    if (!IsFunctionParameterPack && CurrentInstantiationScope) {
608      if (NamedDecl *PartialPack
609                    = CurrentInstantiationScope->getPartiallySubstitutedPack()){
610        unsigned PartialDepth, PartialIndex;
611        std::tie(PartialDepth, PartialIndex) = getDepthAndIndex(PartialPack);
612        if (PartialDepth == Depth && PartialIndex == Index)
613          RetainExpansion = true;
614      }
615    }
616
617    if (!NumExpansions) {
618      // The is the first pack we've seen for which we have an argument.
619      // Record it.
620      NumExpansions = NewPackSize;
621      FirstPack.first = Name;
622      FirstPack.second = i->second;
623      HaveFirstPack = true;
624      continue;
625    }
626
627    if (NewPackSize != *NumExpansions) {
628      // C++0x [temp.variadic]p5:
629      //   All of the parameter packs expanded by a pack expansion shall have
630      //   the same number of arguments specified.
631      if (HaveFirstPack)
632        Diag(EllipsisLoc, diag::err_pack_expansion_length_conflict)
633          << FirstPack.first << Name << *NumExpansions << NewPackSize
634          << SourceRange(FirstPack.second) << SourceRange(i->second);
635      else
636        Diag(EllipsisLoc, diag::err_pack_expansion_length_conflict_multilevel)
637          << Name << *NumExpansions << NewPackSize
638          << SourceRange(i->second);
639      return true;
640    }
641  }
642
643  return false;
644}
645
646Optional<unsigned> Sema::getNumArgumentsInExpansion(QualType T,
647                          const MultiLevelTemplateArgumentList &TemplateArgs) {
648  QualType Pattern = cast<PackExpansionType>(T)->getPattern();
649  SmallVector<UnexpandedParameterPack, 2> Unexpanded;
650  CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseType(Pattern);
651
652  Optional<unsigned> Result;
653  for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
654    // Compute the depth and index for this parameter pack.
655    unsigned Depth;
656    unsigned Index;
657
658    if (const TemplateTypeParmType *TTP
659          = Unexpanded[I].first.dyn_cast<const TemplateTypeParmType *>()) {
660      Depth = TTP->getDepth();
661      Index = TTP->getIndex();
662    } else {
663      NamedDecl *ND = Unexpanded[I].first.get<NamedDecl *>();
664      if (isa<ParmVarDecl>(ND)) {
665        // Function parameter pack.
666        typedef LocalInstantiationScope::DeclArgumentPack DeclArgumentPack;
667
668        llvm::PointerUnion<Decl *, DeclArgumentPack *> *Instantiation
669          = CurrentInstantiationScope->findInstantiationOf(
670                                        Unexpanded[I].first.get<NamedDecl *>());
671        if (Instantiation->is<Decl*>())
672          // The pattern refers to an unexpanded pack. We're not ready to expand
673          // this pack yet.
674          return None;
675
676        unsigned Size = Instantiation->get<DeclArgumentPack *>()->size();
677        assert((!Result || *Result == Size) && "inconsistent pack sizes");
678        Result = Size;
679        continue;
680      }
681
682      std::tie(Depth, Index) = getDepthAndIndex(ND);
683    }
684    if (Depth >= TemplateArgs.getNumLevels() ||
685        !TemplateArgs.hasTemplateArgument(Depth, Index))
686      // The pattern refers to an unknown template argument. We're not ready to
687      // expand this pack yet.
688      return None;
689
690    // Determine the size of the argument pack.
691    unsigned Size = TemplateArgs(Depth, Index).pack_size();
692    assert((!Result || *Result == Size) && "inconsistent pack sizes");
693    Result = Size;
694  }
695
696  return Result;
697}
698
699bool Sema::containsUnexpandedParameterPacks(Declarator &D) {
700  const DeclSpec &DS = D.getDeclSpec();
701  switch (DS.getTypeSpecType()) {
702  case TST_typename:
703  case TST_typeofType:
704  case TST_underlyingType:
705  case TST_atomic: {
706    QualType T = DS.getRepAsType().get();
707    if (!T.isNull() && T->containsUnexpandedParameterPack())
708      return true;
709    break;
710  }
711
712  case TST_typeofExpr:
713  case TST_decltype:
714    if (DS.getRepAsExpr() &&
715        DS.getRepAsExpr()->containsUnexpandedParameterPack())
716      return true;
717    break;
718
719  case TST_unspecified:
720  case TST_void:
721  case TST_char:
722  case TST_wchar:
723  case TST_char16:
724  case TST_char32:
725  case TST_int:
726  case TST_int128:
727  case TST_half:
728  case TST_float:
729  case TST_double:
730  case TST_float128:
731  case TST_bool:
732  case TST_decimal32:
733  case TST_decimal64:
734  case TST_decimal128:
735  case TST_enum:
736  case TST_union:
737  case TST_struct:
738  case TST_interface:
739  case TST_class:
740  case TST_auto:
741  case TST_auto_type:
742  case TST_decltype_auto:
743#define GENERIC_IMAGE_TYPE(ImgType, Id) case TST_##ImgType##_t:
744#include "clang/Basic/OpenCLImageTypes.def"
745  case TST_unknown_anytype:
746  case TST_error:
747    break;
748  }
749
750  for (unsigned I = 0, N = D.getNumTypeObjects(); I != N; ++I) {
751    const DeclaratorChunk &Chunk = D.getTypeObject(I);
752    switch (Chunk.Kind) {
753    case DeclaratorChunk::Pointer:
754    case DeclaratorChunk::Reference:
755    case DeclaratorChunk::Paren:
756    case DeclaratorChunk::Pipe:
757    case DeclaratorChunk::BlockPointer:
758      // These declarator chunks cannot contain any parameter packs.
759      break;
760
761    case DeclaratorChunk::Array:
762      if (Chunk.Arr.NumElts &&
763          Chunk.Arr.NumElts->containsUnexpandedParameterPack())
764        return true;
765      break;
766    case DeclaratorChunk::Function:
767      for (unsigned i = 0, e = Chunk.Fun.NumParams; i != e; ++i) {
768        ParmVarDecl *Param = cast<ParmVarDecl>(Chunk.Fun.Params[i].Param);
769        QualType ParamTy = Param->getType();
770        assert(!ParamTy.isNull() && "Couldn't parse type?");
771        if (ParamTy->containsUnexpandedParameterPack()) return true;
772      }
773
774      if (Chunk.Fun.getExceptionSpecType() == EST_Dynamic) {
775        for (unsigned i = 0; i != Chunk.Fun.NumExceptions; ++i) {
776          if (Chunk.Fun.Exceptions[i]
777                  .Ty.get()
778                  ->containsUnexpandedParameterPack())
779            return true;
780        }
781      } else if (Chunk.Fun.getExceptionSpecType() == EST_ComputedNoexcept &&
782                 Chunk.Fun.NoexceptExpr->containsUnexpandedParameterPack())
783        return true;
784
785      if (Chunk.Fun.hasTrailingReturnType()) {
786        QualType T = Chunk.Fun.getTrailingReturnType().get();
787	if (!T.isNull() && T->containsUnexpandedParameterPack())
788	  return true;
789      }
790      break;
791
792    case DeclaratorChunk::MemberPointer:
793      if (Chunk.Mem.Scope().getScopeRep() &&
794          Chunk.Mem.Scope().getScopeRep()->containsUnexpandedParameterPack())
795        return true;
796      break;
797    }
798  }
799
800  return false;
801}
802
803namespace {
804
805// Callback to only accept typo corrections that refer to parameter packs.
806class ParameterPackValidatorCCC : public CorrectionCandidateCallback {
807 public:
808  bool ValidateCandidate(const TypoCorrection &candidate) override {
809    NamedDecl *ND = candidate.getCorrectionDecl();
810    return ND && ND->isParameterPack();
811  }
812};
813
814}
815
816/// \brief Called when an expression computing the size of a parameter pack
817/// is parsed.
818///
819/// \code
820/// template<typename ...Types> struct count {
821///   static const unsigned value = sizeof...(Types);
822/// };
823/// \endcode
824///
825//
826/// \param OpLoc The location of the "sizeof" keyword.
827/// \param Name The name of the parameter pack whose size will be determined.
828/// \param NameLoc The source location of the name of the parameter pack.
829/// \param RParenLoc The location of the closing parentheses.
830ExprResult Sema::ActOnSizeofParameterPackExpr(Scope *S,
831                                              SourceLocation OpLoc,
832                                              IdentifierInfo &Name,
833                                              SourceLocation NameLoc,
834                                              SourceLocation RParenLoc) {
835  // C++0x [expr.sizeof]p5:
836  //   The identifier in a sizeof... expression shall name a parameter pack.
837  LookupResult R(*this, &Name, NameLoc, LookupOrdinaryName);
838  LookupName(R, S);
839
840  NamedDecl *ParameterPack = nullptr;
841  switch (R.getResultKind()) {
842  case LookupResult::Found:
843    ParameterPack = R.getFoundDecl();
844    break;
845
846  case LookupResult::NotFound:
847  case LookupResult::NotFoundInCurrentInstantiation:
848    if (TypoCorrection Corrected =
849            CorrectTypo(R.getLookupNameInfo(), R.getLookupKind(), S, nullptr,
850                        llvm::make_unique<ParameterPackValidatorCCC>(),
851                        CTK_ErrorRecovery)) {
852      diagnoseTypo(Corrected,
853                   PDiag(diag::err_sizeof_pack_no_pack_name_suggest) << &Name,
854                   PDiag(diag::note_parameter_pack_here));
855      ParameterPack = Corrected.getCorrectionDecl();
856    }
857
858  case LookupResult::FoundOverloaded:
859  case LookupResult::FoundUnresolvedValue:
860    break;
861
862  case LookupResult::Ambiguous:
863    DiagnoseAmbiguousLookup(R);
864    return ExprError();
865  }
866
867  if (!ParameterPack || !ParameterPack->isParameterPack()) {
868    Diag(NameLoc, diag::err_sizeof_pack_no_pack_name)
869      << &Name;
870    return ExprError();
871  }
872
873  MarkAnyDeclReferenced(OpLoc, ParameterPack, true);
874
875  return SizeOfPackExpr::Create(Context, OpLoc, ParameterPack, NameLoc,
876                                RParenLoc);
877}
878
879TemplateArgumentLoc
880Sema::getTemplateArgumentPackExpansionPattern(
881      TemplateArgumentLoc OrigLoc,
882      SourceLocation &Ellipsis, Optional<unsigned> &NumExpansions) const {
883  const TemplateArgument &Argument = OrigLoc.getArgument();
884  assert(Argument.isPackExpansion());
885  switch (Argument.getKind()) {
886  case TemplateArgument::Type: {
887    // FIXME: We shouldn't ever have to worry about missing
888    // type-source info!
889    TypeSourceInfo *ExpansionTSInfo = OrigLoc.getTypeSourceInfo();
890    if (!ExpansionTSInfo)
891      ExpansionTSInfo = Context.getTrivialTypeSourceInfo(Argument.getAsType(),
892                                                         Ellipsis);
893    PackExpansionTypeLoc Expansion =
894        ExpansionTSInfo->getTypeLoc().castAs<PackExpansionTypeLoc>();
895    Ellipsis = Expansion.getEllipsisLoc();
896
897    TypeLoc Pattern = Expansion.getPatternLoc();
898    NumExpansions = Expansion.getTypePtr()->getNumExpansions();
899
900    // We need to copy the TypeLoc because TemplateArgumentLocs store a
901    // TypeSourceInfo.
902    // FIXME: Find some way to avoid the copy?
903    TypeLocBuilder TLB;
904    TLB.pushFullCopy(Pattern);
905    TypeSourceInfo *PatternTSInfo =
906        TLB.getTypeSourceInfo(Context, Pattern.getType());
907    return TemplateArgumentLoc(TemplateArgument(Pattern.getType()),
908                               PatternTSInfo);
909  }
910
911  case TemplateArgument::Expression: {
912    PackExpansionExpr *Expansion
913      = cast<PackExpansionExpr>(Argument.getAsExpr());
914    Expr *Pattern = Expansion->getPattern();
915    Ellipsis = Expansion->getEllipsisLoc();
916    NumExpansions = Expansion->getNumExpansions();
917    return TemplateArgumentLoc(Pattern, Pattern);
918  }
919
920  case TemplateArgument::TemplateExpansion:
921    Ellipsis = OrigLoc.getTemplateEllipsisLoc();
922    NumExpansions = Argument.getNumTemplateExpansions();
923    return TemplateArgumentLoc(Argument.getPackExpansionPattern(),
924                               OrigLoc.getTemplateQualifierLoc(),
925                               OrigLoc.getTemplateNameLoc());
926
927  case TemplateArgument::Declaration:
928  case TemplateArgument::NullPtr:
929  case TemplateArgument::Template:
930  case TemplateArgument::Integral:
931  case TemplateArgument::Pack:
932  case TemplateArgument::Null:
933    return TemplateArgumentLoc();
934  }
935
936  llvm_unreachable("Invalid TemplateArgument Kind!");
937}
938
939static void CheckFoldOperand(Sema &S, Expr *E) {
940  if (!E)
941    return;
942
943  E = E->IgnoreImpCasts();
944  if (isa<BinaryOperator>(E) || isa<AbstractConditionalOperator>(E)) {
945    S.Diag(E->getExprLoc(), diag::err_fold_expression_bad_operand)
946        << E->getSourceRange()
947        << FixItHint::CreateInsertion(E->getLocStart(), "(")
948        << FixItHint::CreateInsertion(E->getLocEnd(), ")");
949  }
950}
951
952ExprResult Sema::ActOnCXXFoldExpr(SourceLocation LParenLoc, Expr *LHS,
953                                  tok::TokenKind Operator,
954                                  SourceLocation EllipsisLoc, Expr *RHS,
955                                  SourceLocation RParenLoc) {
956  // LHS and RHS must be cast-expressions. We allow an arbitrary expression
957  // in the parser and reduce down to just cast-expressions here.
958  CheckFoldOperand(*this, LHS);
959  CheckFoldOperand(*this, RHS);
960
961  // [expr.prim.fold]p3:
962  //   In a binary fold, op1 and op2 shall be the same fold-operator, and
963  //   either e1 shall contain an unexpanded parameter pack or e2 shall contain
964  //   an unexpanded parameter pack, but not both.
965  if (LHS && RHS &&
966      LHS->containsUnexpandedParameterPack() ==
967          RHS->containsUnexpandedParameterPack()) {
968    return Diag(EllipsisLoc,
969                LHS->containsUnexpandedParameterPack()
970                    ? diag::err_fold_expression_packs_both_sides
971                    : diag::err_pack_expansion_without_parameter_packs)
972        << LHS->getSourceRange() << RHS->getSourceRange();
973  }
974
975  // [expr.prim.fold]p2:
976  //   In a unary fold, the cast-expression shall contain an unexpanded
977  //   parameter pack.
978  if (!LHS || !RHS) {
979    Expr *Pack = LHS ? LHS : RHS;
980    assert(Pack && "fold expression with neither LHS nor RHS");
981    if (!Pack->containsUnexpandedParameterPack())
982      return Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
983             << Pack->getSourceRange();
984  }
985
986  BinaryOperatorKind Opc = ConvertTokenKindToBinaryOpcode(Operator);
987  return BuildCXXFoldExpr(LParenLoc, LHS, Opc, EllipsisLoc, RHS, RParenLoc);
988}
989
990ExprResult Sema::BuildCXXFoldExpr(SourceLocation LParenLoc, Expr *LHS,
991                                  BinaryOperatorKind Operator,
992                                  SourceLocation EllipsisLoc, Expr *RHS,
993                                  SourceLocation RParenLoc) {
994  return new (Context) CXXFoldExpr(Context.DependentTy, LParenLoc, LHS,
995                                   Operator, EllipsisLoc, RHS, RParenLoc);
996}
997
998ExprResult Sema::BuildEmptyCXXFoldExpr(SourceLocation EllipsisLoc,
999                                       BinaryOperatorKind Operator) {
1000  // [temp.variadic]p9:
1001  //   If N is zero for a unary fold-expression, the value of the expression is
1002  //       &&  ->  true
1003  //       ||  ->  false
1004  //       ,   ->  void()
1005  //   if the operator is not listed [above], the instantiation is ill-formed.
1006  //
1007  // Note that we need to use something like int() here, not merely 0, to
1008  // prevent the result from being a null pointer constant.
1009  QualType ScalarType;
1010  switch (Operator) {
1011  case BO_LOr:
1012    return ActOnCXXBoolLiteral(EllipsisLoc, tok::kw_false);
1013  case BO_LAnd:
1014    return ActOnCXXBoolLiteral(EllipsisLoc, tok::kw_true);
1015  case BO_Comma:
1016    ScalarType = Context.VoidTy;
1017    break;
1018
1019  default:
1020    return Diag(EllipsisLoc, diag::err_fold_expression_empty)
1021        << BinaryOperator::getOpcodeStr(Operator);
1022  }
1023
1024  return new (Context) CXXScalarValueInitExpr(
1025      ScalarType, Context.getTrivialTypeSourceInfo(ScalarType, EllipsisLoc),
1026      EllipsisLoc);
1027}
1028