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