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