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