SemaTemplateVariadic.cpp revision 10738d36b150aa65206890c1c845cdba076e4200 
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/ParsedTemplate.h"
14#include "clang/Sema/SemaInternal.h"
15#include "clang/Sema/Template.h"
16#include "clang/AST/Expr.h"
17#include "clang/AST/RecursiveASTVisitor.h"
18#include "clang/AST/TypeLoc.h"
19
20using namespace clang;
21
22//----------------------------------------------------------------------------
23// Visitor that collects unexpanded parameter packs
24//----------------------------------------------------------------------------
25
26namespace {
27  /// \brief A class that collects unexpanded parameter packs.
28  class CollectUnexpandedParameterPacksVisitor :
29    public RecursiveASTVisitor<CollectUnexpandedParameterPacksVisitor>
30  {
31    typedef RecursiveASTVisitor<CollectUnexpandedParameterPacksVisitor>
32      inherited;
33
34    llvm::SmallVectorImpl<UnexpandedParameterPack> &Unexpanded;
35
36  public:
37    explicit CollectUnexpandedParameterPacksVisitor(
38                  llvm::SmallVectorImpl<UnexpandedParameterPack> &Unexpanded)
39      : Unexpanded(Unexpanded) { }
40
41    bool shouldWalkTypesOfTypeLocs() const { return false; }
42
43    //------------------------------------------------------------------------
44    // Recording occurrences of (unexpanded) parameter packs.
45    //------------------------------------------------------------------------
46
47    /// \brief Record occurrences of template type parameter packs.
48    bool VisitTemplateTypeParmTypeLoc(TemplateTypeParmTypeLoc TL) {
49      if (TL.getTypePtr()->isParameterPack())
50        Unexpanded.push_back(std::make_pair(TL.getTypePtr(), TL.getNameLoc()));
51      return true;
52    }
53
54    /// \brief Record occurrences of template type parameter packs
55    /// when we don't have proper source-location information for
56    /// them.
57    ///
58    /// Ideally, this routine would never be used.
59    bool VisitTemplateTypeParmType(TemplateTypeParmType *T) {
60      if (T->isParameterPack())
61        Unexpanded.push_back(std::make_pair(T, SourceLocation()));
62
63      return true;
64    }
65
66    /// \brief Record occurrences of (FIXME: function and) non-type template
67    /// parameter packs in an expression.
68    bool VisitDeclRefExpr(DeclRefExpr *E) {
69      if (NonTypeTemplateParmDecl *NTTP
70                            = dyn_cast<NonTypeTemplateParmDecl>(E->getDecl())) {
71        if (NTTP->isParameterPack())
72          Unexpanded.push_back(std::make_pair(NTTP, E->getLocation()));
73      }
74
75      // FIXME: Function parameter packs.
76
77      return true;
78    }
79
80    // FIXME: Record occurrences of template template parameter packs.
81
82    // FIXME: Once we have pack expansions in the AST, block their
83    // traversal.
84
85    //------------------------------------------------------------------------
86    // Pruning the search for unexpanded parameter packs.
87    //------------------------------------------------------------------------
88
89    /// \brief Suppress traversal into statements and expressions that
90    /// do not contain unexpanded parameter packs.
91    bool TraverseStmt(Stmt *S) {
92      if (Expr *E = dyn_cast_or_null<Expr>(S))
93        if (E->containsUnexpandedParameterPack())
94          return inherited::TraverseStmt(E);
95
96      return true;
97    }
98
99    /// \brief Suppress traversal into types that do not contain
100    /// unexpanded parameter packs.
101    bool TraverseType(QualType T) {
102      if (!T.isNull() && T->containsUnexpandedParameterPack())
103        return inherited::TraverseType(T);
104
105      return true;
106    }
107
108    /// \brief Suppress traversel into types with location information
109    /// that do not contain unexpanded parameter packs.
110    bool TraverseTypeLoc(TypeLoc TL) {
111      if (!TL.getType().isNull() &&
112          TL.getType()->containsUnexpandedParameterPack())
113        return inherited::TraverseTypeLoc(TL);
114
115      return true;
116    }
117
118    /// \brief Suppress traversal of non-parameter declarations, since
119    /// they cannot contain unexpanded parameter packs.
120    bool TraverseDecl(Decl *D) {
121      if (D && isa<ParmVarDecl>(D))
122        return inherited::TraverseDecl(D);
123
124      return true;
125    }
126  };
127}
128
129/// \brief Diagnose all of the unexpanded parameter packs in the given
130/// vector.
131static void
132DiagnoseUnexpandedParameterPacks(Sema &S, SourceLocation Loc,
133                                 Sema::UnexpandedParameterPackContext UPPC,
134             const llvm::SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
135  llvm::SmallVector<SourceLocation, 4> Locations;
136  llvm::SmallVector<IdentifierInfo *, 4> Names;
137  llvm::SmallPtrSet<IdentifierInfo *, 4> NamesKnown;
138
139  for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
140    IdentifierInfo *Name = 0;
141    if (const TemplateTypeParmType *TTP
142          = Unexpanded[I].first.dyn_cast<const TemplateTypeParmType *>())
143      Name = TTP->getName();
144    else
145      Name = Unexpanded[I].first.get<NamedDecl *>()->getIdentifier();
146
147    if (Name && NamesKnown.insert(Name))
148      Names.push_back(Name);
149
150    if (Unexpanded[I].second.isValid())
151      Locations.push_back(Unexpanded[I].second);
152  }
153
154  DiagnosticBuilder DB
155    = Names.size() == 0? S.Diag(Loc, diag::err_unexpanded_parameter_pack_0)
156                           << (int)UPPC
157    : Names.size() == 1? S.Diag(Loc, diag::err_unexpanded_parameter_pack_1)
158                           << (int)UPPC << Names[0]
159    : Names.size() == 2? S.Diag(Loc, diag::err_unexpanded_parameter_pack_2)
160                           << (int)UPPC << Names[0] << Names[1]
161    : S.Diag(Loc, diag::err_unexpanded_parameter_pack_3_or_more)
162        << (int)UPPC << Names[0] << Names[1];
163
164  for (unsigned I = 0, N = Locations.size(); I != N; ++I)
165    DB << SourceRange(Locations[I]);
166}
167
168bool Sema::DiagnoseUnexpandedParameterPack(SourceLocation Loc,
169                                           TypeSourceInfo *T,
170                                         UnexpandedParameterPackContext UPPC) {
171  // C++0x [temp.variadic]p5:
172  //   An appearance of a name of a parameter pack that is not expanded is
173  //   ill-formed.
174  if (!T->getType()->containsUnexpandedParameterPack())
175    return false;
176
177  llvm::SmallVector<UnexpandedParameterPack, 2> Unexpanded;
178  CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseTypeLoc(
179                                                              T->getTypeLoc());
180  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
181  DiagnoseUnexpandedParameterPacks(*this, Loc, UPPC, Unexpanded);
182  return true;
183}
184
185bool Sema::DiagnoseUnexpandedParameterPack(Expr *E,
186                                        UnexpandedParameterPackContext UPPC) {
187  // C++0x [temp.variadic]p5:
188  //   An appearance of a name of a parameter pack that is not expanded is
189  //   ill-formed.
190  if (!E->containsUnexpandedParameterPack())
191    return false;
192
193  llvm::SmallVector<UnexpandedParameterPack, 2> Unexpanded;
194  CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseStmt(E);
195  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
196  DiagnoseUnexpandedParameterPacks(*this, E->getLocStart(), UPPC, Unexpanded);
197  return true;
198}
199
200bool Sema::DiagnoseUnexpandedParameterPack(const CXXScopeSpec &SS,
201                                        UnexpandedParameterPackContext UPPC) {
202  // C++0x [temp.variadic]p5:
203  //   An appearance of a name of a parameter pack that is not expanded is
204  //   ill-formed.
205  if (!SS.getScopeRep() ||
206      !SS.getScopeRep()->containsUnexpandedParameterPack())
207    return false;
208
209  llvm::SmallVector<UnexpandedParameterPack, 2> Unexpanded;
210  CollectUnexpandedParameterPacksVisitor(Unexpanded)
211    .TraverseNestedNameSpecifier(SS.getScopeRep());
212  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
213  DiagnoseUnexpandedParameterPacks(*this, SS.getRange().getBegin(),
214                                   UPPC, Unexpanded);
215  return true;
216}
217
218bool Sema::DiagnoseUnexpandedParameterPack(const DeclarationNameInfo &NameInfo,
219                                         UnexpandedParameterPackContext UPPC) {
220  // C++0x [temp.variadic]p5:
221  //   An appearance of a name of a parameter pack that is not expanded is
222  //   ill-formed.
223  switch (NameInfo.getName().getNameKind()) {
224  case DeclarationName::Identifier:
225  case DeclarationName::ObjCZeroArgSelector:
226  case DeclarationName::ObjCOneArgSelector:
227  case DeclarationName::ObjCMultiArgSelector:
228  case DeclarationName::CXXOperatorName:
229  case DeclarationName::CXXLiteralOperatorName:
230  case DeclarationName::CXXUsingDirective:
231    return false;
232
233  case DeclarationName::CXXConstructorName:
234  case DeclarationName::CXXDestructorName:
235  case DeclarationName::CXXConversionFunctionName:
236    // FIXME: We shouldn't need this null check!
237    if (TypeSourceInfo *TSInfo = NameInfo.getNamedTypeInfo())
238      return DiagnoseUnexpandedParameterPack(NameInfo.getLoc(), TSInfo, UPPC);
239
240    if (!NameInfo.getName().getCXXNameType()->containsUnexpandedParameterPack())
241      return false;
242
243    break;
244  }
245
246  llvm::SmallVector<UnexpandedParameterPack, 2> Unexpanded;
247  CollectUnexpandedParameterPacksVisitor(Unexpanded)
248    .TraverseType(NameInfo.getName().getCXXNameType());
249  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
250  DiagnoseUnexpandedParameterPacks(*this, NameInfo.getLoc(), UPPC, Unexpanded);
251  return true;
252}
253
254bool Sema::DiagnoseUnexpandedParameterPack(SourceLocation Loc,
255                                           TemplateName Template,
256                                       UnexpandedParameterPackContext UPPC) {
257
258  if (Template.isNull() || !Template.containsUnexpandedParameterPack())
259    return false;
260
261  llvm::SmallVector<UnexpandedParameterPack, 2> Unexpanded;
262  CollectUnexpandedParameterPacksVisitor(Unexpanded)
263    .TraverseTemplateName(Template);
264  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
265  DiagnoseUnexpandedParameterPacks(*this, Loc, UPPC, Unexpanded);
266  return true;
267}
268
269void Sema::collectUnexpandedParameterPacks(TemplateArgument Arg,
270                   llvm::SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
271  CollectUnexpandedParameterPacksVisitor(Unexpanded)
272    .TraverseTemplateArgument(Arg);
273}
274
275void Sema::collectUnexpandedParameterPacks(TemplateArgumentLoc Arg,
276                   llvm::SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
277  CollectUnexpandedParameterPacksVisitor(Unexpanded)
278    .TraverseTemplateArgumentLoc(Arg);
279}
280
281void Sema::collectUnexpandedParameterPacks(QualType T,
282                   llvm::SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
283  CollectUnexpandedParameterPacksVisitor(Unexpanded).TraverseType(T);
284}
285
286ParsedTemplateArgument
287Sema::ActOnPackExpansion(const ParsedTemplateArgument &Arg,
288                         SourceLocation EllipsisLoc) {
289  if (Arg.isInvalid())
290    return Arg;
291
292  switch (Arg.getKind()) {
293  case ParsedTemplateArgument::Type: {
294    TypeResult Result = ActOnPackExpansion(Arg.getAsType(), EllipsisLoc);
295    if (Result.isInvalid())
296      return ParsedTemplateArgument();
297
298    return ParsedTemplateArgument(Arg.getKind(), Result.get().getAsOpaquePtr(),
299                                  Arg.getLocation());
300  }
301
302  case ParsedTemplateArgument::NonType:
303    Diag(EllipsisLoc, diag::err_pack_expansion_unsupported)
304      << 0;
305    return ParsedTemplateArgument();
306
307  case ParsedTemplateArgument::Template:
308    Diag(EllipsisLoc, diag::err_pack_expansion_unsupported)
309      << 1;
310    return ParsedTemplateArgument();
311  }
312  llvm_unreachable("Unhandled template argument kind?");
313  return ParsedTemplateArgument();
314}
315
316TypeResult Sema::ActOnPackExpansion(ParsedType Type,
317                                    SourceLocation EllipsisLoc) {
318  TypeSourceInfo *TSInfo;
319  GetTypeFromParser(Type, &TSInfo);
320  if (!TSInfo)
321    return true;
322
323  TypeSourceInfo *TSResult = CheckPackExpansion(TSInfo, EllipsisLoc);
324  if (!TSResult)
325    return true;
326
327  return CreateParsedType(TSResult->getType(), TSResult);
328}
329
330TypeSourceInfo *Sema::CheckPackExpansion(TypeSourceInfo *Pattern,
331                                         SourceLocation EllipsisLoc) {
332  // C++0x [temp.variadic]p5:
333  //   The pattern of a pack expansion shall name one or more
334  //   parameter packs that are not expanded by a nested pack
335  //   expansion.
336  if (!Pattern->getType()->containsUnexpandedParameterPack()) {
337    Diag(EllipsisLoc, diag::err_pack_expansion_without_parameter_packs)
338      << Pattern->getTypeLoc().getSourceRange();
339    return 0;
340  }
341
342  // Create the pack expansion type and source-location information.
343  QualType Result = Context.getPackExpansionType(Pattern->getType());
344  TypeSourceInfo *TSResult = Context.CreateTypeSourceInfo(Result);
345  PackExpansionTypeLoc TL = cast<PackExpansionTypeLoc>(TSResult->getTypeLoc());
346  TL.setEllipsisLoc(EllipsisLoc);
347
348  // Copy over the source-location information from the type.
349  memcpy(TL.getNextTypeLoc().getOpaqueData(),
350         Pattern->getTypeLoc().getOpaqueData(),
351         Pattern->getTypeLoc().getFullDataSize());
352  return TSResult;
353}
354
355
356bool Sema::CheckParameterPacksForExpansion(SourceLocation EllipsisLoc,
357                                           SourceRange PatternRange,
358                                     const UnexpandedParameterPack *Unexpanded,
359                                           unsigned NumUnexpanded,
360                             const MultiLevelTemplateArgumentList &TemplateArgs,
361                                           bool &ShouldExpand,
362                                           unsigned &NumExpansions) {
363  ShouldExpand = true;
364  std::pair<IdentifierInfo *, SourceLocation> FirstPack;
365  bool HaveFirstPack = false;
366
367  for (unsigned I = 0; I != NumUnexpanded; ++I) {
368    // Compute the depth and index for this parameter pack.
369    unsigned Depth;
370    unsigned Index;
371    IdentifierInfo *Name;
372
373    if (const TemplateTypeParmType *TTP
374        = Unexpanded[I].first.dyn_cast<const TemplateTypeParmType *>()) {
375      Depth = TTP->getDepth();
376      Index = TTP->getIndex();
377      Name = TTP->getName();
378    } else {
379      NamedDecl *ND = Unexpanded[I].first.get<NamedDecl *>();
380      if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(ND)) {
381        Depth = TTP->getDepth();
382        Index = TTP->getIndex();
383      } else if (NonTypeTemplateParmDecl *NTTP
384                 = dyn_cast<NonTypeTemplateParmDecl>(ND)) {
385        Depth = NTTP->getDepth();
386        Index = NTTP->getIndex();
387      } else {
388        TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(ND);
389        Depth = TTP->getDepth();
390        Index = TTP->getIndex();
391      }
392      // FIXME: Variadic templates function parameter packs?
393      Name = ND->getIdentifier();
394    }
395
396    // If we don't have a template argument at this depth/index, then we
397    // cannot expand the pack expansion. Make a note of this, but we still
398    // want to check that any parameter packs we *do* have arguments for.
399    if (!TemplateArgs.hasTemplateArgument(Depth, Index)) {
400      ShouldExpand = false;
401      continue;
402    }
403
404    // Determine the size of the argument pack.
405    unsigned NewPackSize = TemplateArgs(Depth, Index).pack_size();
406    if (!HaveFirstPack) {
407      // The is the first pack we've seen for which we have an argument.
408      // Record it.
409      NumExpansions = NewPackSize;
410      FirstPack.first = Name;
411      FirstPack.second = Unexpanded[I].second;
412      HaveFirstPack = true;
413      continue;
414    }
415
416    if (NewPackSize != NumExpansions) {
417      // C++0x [temp.variadic]p5:
418      //   All of the parameter packs expanded by a pack expansion shall have
419      //   the same number of arguments specified.
420      Diag(EllipsisLoc, diag::err_pack_expansion_length_conflict)
421        << FirstPack.first << Name << NumExpansions << NewPackSize
422        << SourceRange(FirstPack.second) << SourceRange(Unexpanded[I].second);
423      return true;
424    }
425  }
426
427  return false;
428}
429
430bool Sema::containsUnexpandedParameterPacks(Declarator &D) {
431  const DeclSpec &DS = D.getDeclSpec();
432  switch (DS.getTypeSpecType()) {
433  case TST_typename:
434  case TST_typeofType: {
435    QualType T = DS.getRepAsType().get();
436    if (!T.isNull() && T->containsUnexpandedParameterPack())
437      return true;
438    break;
439  }
440
441  case TST_typeofExpr:
442  case TST_decltype:
443    if (DS.getRepAsExpr() &&
444        DS.getRepAsExpr()->containsUnexpandedParameterPack())
445      return true;
446    break;
447
448  case TST_unspecified:
449  case TST_void:
450  case TST_char:
451  case TST_wchar:
452  case TST_char16:
453  case TST_char32:
454  case TST_int:
455  case TST_float:
456  case TST_double:
457  case TST_bool:
458  case TST_decimal32:
459  case TST_decimal64:
460  case TST_decimal128:
461  case TST_enum:
462  case TST_union:
463  case TST_struct:
464  case TST_class:
465  case TST_auto:
466  case TST_error:
467    break;
468  }
469
470  for (unsigned I = 0, N = D.getNumTypeObjects(); I != N; ++I) {
471    const DeclaratorChunk &Chunk = D.getTypeObject(I);
472    switch (Chunk.Kind) {
473    case DeclaratorChunk::Pointer:
474    case DeclaratorChunk::Reference:
475    case DeclaratorChunk::Paren:
476      // These declarator chunks cannot contain any parameter packs.
477      break;
478
479    case DeclaratorChunk::Array:
480    case DeclaratorChunk::Function:
481    case DeclaratorChunk::BlockPointer:
482      // Syntactically, these kinds of declarator chunks all come after the
483      // declarator-id (conceptually), so the parser should not invoke this
484      // routine at this time.
485      llvm_unreachable("Could not have seen this kind of declarator chunk");
486      break;
487
488    case DeclaratorChunk::MemberPointer:
489      if (Chunk.Mem.Scope().getScopeRep() &&
490          Chunk.Mem.Scope().getScopeRep()->containsUnexpandedParameterPack())
491        return true;
492      break;
493    }
494  }
495
496  return false;
497}
498