SemaTemplateInstantiate.cpp revision f608ead7de135a3d5495d605d18e3007c922751e 
1//===------- SemaTemplateInstantiate.cpp - C++ Template Instantiation ------===/
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 C++ template instantiation.
10//
11//===----------------------------------------------------------------------===/
12
13#include "Sema.h"
14#include "TreeTransform.h"
15#include "clang/AST/ASTConsumer.h"
16#include "clang/AST/ASTContext.h"
17#include "clang/AST/Expr.h"
18#include "clang/AST/DeclTemplate.h"
19#include "clang/Parse/DeclSpec.h"
20#include "clang/Basic/LangOptions.h"
21#include "llvm/Support/Compiler.h"
22
23using namespace clang;
24
25//===----------------------------------------------------------------------===/
26// Template Instantiation Support
27//===----------------------------------------------------------------------===/
28
29/// \brief Retrieve the template argument list(s) that should be used to
30/// instantiate the definition of the given declaration.
31MultiLevelTemplateArgumentList
32Sema::getTemplateInstantiationArgs(NamedDecl *D) {
33  // Accumulate the set of template argument lists in this structure.
34  MultiLevelTemplateArgumentList Result;
35
36  DeclContext *Ctx = dyn_cast<DeclContext>(D);
37  if (!Ctx)
38    Ctx = D->getDeclContext();
39
40  while (!Ctx->isFileContext()) {
41    // Add template arguments from a class template instantiation.
42    if (ClassTemplateSpecializationDecl *Spec
43          = dyn_cast<ClassTemplateSpecializationDecl>(Ctx)) {
44      // We're done when we hit an explicit specialization.
45      if (Spec->getSpecializationKind() == TSK_ExplicitSpecialization)
46        break;
47
48      Result.addOuterTemplateArguments(&Spec->getTemplateInstantiationArgs());
49    }
50
51    // Add template arguments from a function template specialization.
52    else if (FunctionDecl *Function = dyn_cast<FunctionDecl>(Ctx)) {
53      // FIXME: Check whether this is an explicit specialization.
54      if (const TemplateArgumentList *TemplateArgs
55            = Function->getTemplateSpecializationArgs())
56        Result.addOuterTemplateArguments(TemplateArgs);
57
58      // If this is a friend declaration and it declares an entity at
59      // namespace scope, take arguments from its lexical parent
60      // instead of its semantic parent.
61      if (Function->getFriendObjectKind() &&
62          Function->getDeclContext()->isFileContext()) {
63        Ctx = Function->getLexicalDeclContext();
64        continue;
65      }
66    }
67
68    Ctx = Ctx->getParent();
69  }
70
71  return Result;
72}
73
74Sema::InstantiatingTemplate::
75InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
76                      Decl *Entity,
77                      SourceRange InstantiationRange)
78  :  SemaRef(SemaRef) {
79
80  Invalid = CheckInstantiationDepth(PointOfInstantiation,
81                                    InstantiationRange);
82  if (!Invalid) {
83    ActiveTemplateInstantiation Inst;
84    Inst.Kind = ActiveTemplateInstantiation::TemplateInstantiation;
85    Inst.PointOfInstantiation = PointOfInstantiation;
86    Inst.Entity = reinterpret_cast<uintptr_t>(Entity);
87    Inst.TemplateArgs = 0;
88    Inst.NumTemplateArgs = 0;
89    Inst.InstantiationRange = InstantiationRange;
90    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
91    Invalid = false;
92  }
93}
94
95Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
96                                         SourceLocation PointOfInstantiation,
97                                         TemplateDecl *Template,
98                                         const TemplateArgument *TemplateArgs,
99                                         unsigned NumTemplateArgs,
100                                         SourceRange InstantiationRange)
101  : SemaRef(SemaRef) {
102
103  Invalid = CheckInstantiationDepth(PointOfInstantiation,
104                                    InstantiationRange);
105  if (!Invalid) {
106    ActiveTemplateInstantiation Inst;
107    Inst.Kind
108      = ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation;
109    Inst.PointOfInstantiation = PointOfInstantiation;
110    Inst.Entity = reinterpret_cast<uintptr_t>(Template);
111    Inst.TemplateArgs = TemplateArgs;
112    Inst.NumTemplateArgs = NumTemplateArgs;
113    Inst.InstantiationRange = InstantiationRange;
114    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
115    Invalid = false;
116  }
117}
118
119Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
120                                         SourceLocation PointOfInstantiation,
121                                      FunctionTemplateDecl *FunctionTemplate,
122                                        const TemplateArgument *TemplateArgs,
123                                                   unsigned NumTemplateArgs,
124                         ActiveTemplateInstantiation::InstantiationKind Kind,
125                                              SourceRange InstantiationRange)
126: SemaRef(SemaRef) {
127
128  Invalid = CheckInstantiationDepth(PointOfInstantiation,
129                                    InstantiationRange);
130  if (!Invalid) {
131    ActiveTemplateInstantiation Inst;
132    Inst.Kind = Kind;
133    Inst.PointOfInstantiation = PointOfInstantiation;
134    Inst.Entity = reinterpret_cast<uintptr_t>(FunctionTemplate);
135    Inst.TemplateArgs = TemplateArgs;
136    Inst.NumTemplateArgs = NumTemplateArgs;
137    Inst.InstantiationRange = InstantiationRange;
138    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
139    Invalid = false;
140  }
141}
142
143Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
144                                         SourceLocation PointOfInstantiation,
145                          ClassTemplatePartialSpecializationDecl *PartialSpec,
146                                         const TemplateArgument *TemplateArgs,
147                                         unsigned NumTemplateArgs,
148                                         SourceRange InstantiationRange)
149  : SemaRef(SemaRef) {
150
151  Invalid = CheckInstantiationDepth(PointOfInstantiation,
152                                    InstantiationRange);
153  if (!Invalid) {
154    ActiveTemplateInstantiation Inst;
155    Inst.Kind
156      = ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution;
157    Inst.PointOfInstantiation = PointOfInstantiation;
158    Inst.Entity = reinterpret_cast<uintptr_t>(PartialSpec);
159    Inst.TemplateArgs = TemplateArgs;
160    Inst.NumTemplateArgs = NumTemplateArgs;
161    Inst.InstantiationRange = InstantiationRange;
162    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
163    Invalid = false;
164  }
165}
166
167Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
168                                          SourceLocation PointOfInstantation,
169                                          ParmVarDecl *Param,
170                                          const TemplateArgument *TemplateArgs,
171                                          unsigned NumTemplateArgs,
172                                          SourceRange InstantiationRange)
173  : SemaRef(SemaRef) {
174
175  Invalid = CheckInstantiationDepth(PointOfInstantation, InstantiationRange);
176
177  if (!Invalid) {
178    ActiveTemplateInstantiation Inst;
179    Inst.Kind
180      = ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation;
181    Inst.PointOfInstantiation = PointOfInstantation;
182    Inst.Entity = reinterpret_cast<uintptr_t>(Param);
183    Inst.TemplateArgs = TemplateArgs;
184    Inst.NumTemplateArgs = NumTemplateArgs;
185    Inst.InstantiationRange = InstantiationRange;
186    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
187    Invalid = false;
188  }
189}
190
191void Sema::InstantiatingTemplate::Clear() {
192  if (!Invalid) {
193    SemaRef.ActiveTemplateInstantiations.pop_back();
194    Invalid = true;
195  }
196}
197
198bool Sema::InstantiatingTemplate::CheckInstantiationDepth(
199                                        SourceLocation PointOfInstantiation,
200                                           SourceRange InstantiationRange) {
201  if (SemaRef.ActiveTemplateInstantiations.size()
202       <= SemaRef.getLangOptions().InstantiationDepth)
203    return false;
204
205  SemaRef.Diag(PointOfInstantiation,
206               diag::err_template_recursion_depth_exceeded)
207    << SemaRef.getLangOptions().InstantiationDepth
208    << InstantiationRange;
209  SemaRef.Diag(PointOfInstantiation, diag::note_template_recursion_depth)
210    << SemaRef.getLangOptions().InstantiationDepth;
211  return true;
212}
213
214/// \brief Prints the current instantiation stack through a series of
215/// notes.
216void Sema::PrintInstantiationStack() {
217  // FIXME: In all of these cases, we need to show the template arguments
218  for (llvm::SmallVector<ActiveTemplateInstantiation, 16>::reverse_iterator
219         Active = ActiveTemplateInstantiations.rbegin(),
220         ActiveEnd = ActiveTemplateInstantiations.rend();
221       Active != ActiveEnd;
222       ++Active) {
223    switch (Active->Kind) {
224    case ActiveTemplateInstantiation::TemplateInstantiation: {
225      Decl *D = reinterpret_cast<Decl *>(Active->Entity);
226      if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(D)) {
227        unsigned DiagID = diag::note_template_member_class_here;
228        if (isa<ClassTemplateSpecializationDecl>(Record))
229          DiagID = diag::note_template_class_instantiation_here;
230        Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
231                     DiagID)
232          << Context.getTypeDeclType(Record)
233          << Active->InstantiationRange;
234      } else if (FunctionDecl *Function = dyn_cast<FunctionDecl>(D)) {
235        unsigned DiagID;
236        if (Function->getPrimaryTemplate())
237          DiagID = diag::note_function_template_spec_here;
238        else
239          DiagID = diag::note_template_member_function_here;
240        Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
241                     DiagID)
242          << Function
243          << Active->InstantiationRange;
244      } else {
245        Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
246                     diag::note_template_static_data_member_def_here)
247          << cast<VarDecl>(D)
248          << Active->InstantiationRange;
249      }
250      break;
251    }
252
253    case ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation: {
254      TemplateDecl *Template = cast<TemplateDecl>((Decl *)Active->Entity);
255      std::string TemplateArgsStr
256        = TemplateSpecializationType::PrintTemplateArgumentList(
257                                                         Active->TemplateArgs,
258                                                      Active->NumTemplateArgs,
259                                                      Context.PrintingPolicy);
260      Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
261                   diag::note_default_arg_instantiation_here)
262        << (Template->getNameAsString() + TemplateArgsStr)
263        << Active->InstantiationRange;
264      break;
265    }
266
267    case ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution: {
268      FunctionTemplateDecl *FnTmpl
269        = cast<FunctionTemplateDecl>((Decl *)Active->Entity);
270      Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
271                   diag::note_explicit_template_arg_substitution_here)
272        << FnTmpl << Active->InstantiationRange;
273      break;
274    }
275
276    case ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution:
277      if (ClassTemplatePartialSpecializationDecl *PartialSpec
278            = dyn_cast<ClassTemplatePartialSpecializationDecl>(
279                                                    (Decl *)Active->Entity)) {
280        Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
281                     diag::note_partial_spec_deduct_instantiation_here)
282          << Context.getTypeDeclType(PartialSpec)
283          << Active->InstantiationRange;
284      } else {
285        FunctionTemplateDecl *FnTmpl
286          = cast<FunctionTemplateDecl>((Decl *)Active->Entity);
287        Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
288                     diag::note_function_template_deduction_instantiation_here)
289          << FnTmpl << Active->InstantiationRange;
290      }
291      break;
292
293    case ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation: {
294      ParmVarDecl *Param = cast<ParmVarDecl>((Decl *)Active->Entity);
295      FunctionDecl *FD = cast<FunctionDecl>(Param->getDeclContext());
296
297      std::string TemplateArgsStr
298        = TemplateSpecializationType::PrintTemplateArgumentList(
299                                                         Active->TemplateArgs,
300                                                      Active->NumTemplateArgs,
301                                                      Context.PrintingPolicy);
302      Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
303                   diag::note_default_function_arg_instantiation_here)
304        << (FD->getNameAsString() + TemplateArgsStr)
305        << Active->InstantiationRange;
306      break;
307    }
308
309    }
310  }
311}
312
313bool Sema::isSFINAEContext() const {
314  using llvm::SmallVector;
315  for (SmallVector<ActiveTemplateInstantiation, 16>::const_reverse_iterator
316         Active = ActiveTemplateInstantiations.rbegin(),
317         ActiveEnd = ActiveTemplateInstantiations.rend();
318       Active != ActiveEnd;
319       ++Active) {
320
321    switch(Active->Kind) {
322    case ActiveTemplateInstantiation::TemplateInstantiation:
323    case ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation:
324
325      // This is a template instantiation, so there is no SFINAE.
326      return false;
327
328    case ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation:
329      // A default template argument instantiation may or may not be a
330      // SFINAE context; look further up the stack.
331      break;
332
333    case ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution:
334    case ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution:
335      // We're either substitution explicitly-specified template arguments
336      // or deduced template arguments, so SFINAE applies.
337      return true;
338    }
339  }
340
341  return false;
342}
343
344//===----------------------------------------------------------------------===/
345// Template Instantiation for Types
346//===----------------------------------------------------------------------===/
347namespace {
348  class VISIBILITY_HIDDEN TemplateInstantiator
349    : public TreeTransform<TemplateInstantiator>
350  {
351    const MultiLevelTemplateArgumentList &TemplateArgs;
352    SourceLocation Loc;
353    DeclarationName Entity;
354
355  public:
356    typedef TreeTransform<TemplateInstantiator> inherited;
357
358    TemplateInstantiator(Sema &SemaRef,
359                         const MultiLevelTemplateArgumentList &TemplateArgs,
360                         SourceLocation Loc,
361                         DeclarationName Entity)
362      : inherited(SemaRef), TemplateArgs(TemplateArgs), Loc(Loc),
363        Entity(Entity) { }
364
365    /// \brief Determine whether the given type \p T has already been
366    /// transformed.
367    ///
368    /// For the purposes of template instantiation, a type has already been
369    /// transformed if it is NULL or if it is not dependent.
370    bool AlreadyTransformed(QualType T) {
371      return T.isNull() || !T->isDependentType();
372    }
373
374    /// \brief Returns the location of the entity being instantiated, if known.
375    SourceLocation getBaseLocation() { return Loc; }
376
377    /// \brief Returns the name of the entity being instantiated, if any.
378    DeclarationName getBaseEntity() { return Entity; }
379
380    /// \brief Transform the given declaration by instantiating a reference to
381    /// this declaration.
382    Decl *TransformDecl(Decl *D);
383
384    /// \brief Transform the definition of the given declaration by
385    /// instantiating it.
386    Decl *TransformDefinition(Decl *D);
387
388    /// \brief Rebuild the exception declaration and register the declaration
389    /// as an instantiated local.
390    VarDecl *RebuildExceptionDecl(VarDecl *ExceptionDecl, QualType T,
391                                  DeclaratorInfo *Declarator,
392                                  IdentifierInfo *Name,
393                                  SourceLocation Loc, SourceRange TypeRange);
394
395    Sema::OwningExprResult TransformDeclRefExpr(DeclRefExpr *E);
396
397    /// \brief Transforms a template type parameter type by performing
398    /// substitution of the corresponding template type argument.
399    QualType TransformTemplateTypeParmType(const TemplateTypeParmType *T);
400  };
401}
402
403Decl *TemplateInstantiator::TransformDecl(Decl *D) {
404  if (!D)
405    return 0;
406
407  if (TemplateTemplateParmDecl *TTP = dyn_cast<TemplateTemplateParmDecl>(D)) {
408    if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
409      assert(TemplateArgs(TTP->getDepth(), TTP->getPosition()).getAsDecl() &&
410             "Wrong kind of template template argument");
411      return cast<TemplateDecl>(TemplateArgs(TTP->getDepth(),
412                                             TTP->getPosition()).getAsDecl());
413    }
414
415    // If the corresponding template argument is NULL or non-existent, it's
416    // because we are performing instantiation from explicitly-specified
417    // template arguments in a function template, but there were some
418    // arguments left unspecified.
419    if (!TemplateArgs.hasTemplateArgument(TTP->getDepth(),
420                                          TTP->getPosition()))
421      return D;
422
423    // FIXME: Implement depth reduction of template template parameters
424    assert(false &&
425      "Reducing depth of template template parameters is not yet implemented");
426  }
427
428  return SemaRef.FindInstantiatedDecl(cast<NamedDecl>(D));
429}
430
431Decl *TemplateInstantiator::TransformDefinition(Decl *D) {
432  Decl *Inst = getSema().SubstDecl(D, getSema().CurContext, TemplateArgs);
433  if (!Inst)
434    return 0;
435
436  getSema().CurrentInstantiationScope->InstantiatedLocal(D, Inst);
437  return Inst;
438}
439
440VarDecl *
441TemplateInstantiator::RebuildExceptionDecl(VarDecl *ExceptionDecl,
442                                           QualType T,
443                                           DeclaratorInfo *Declarator,
444                                           IdentifierInfo *Name,
445                                           SourceLocation Loc,
446                                           SourceRange TypeRange) {
447  VarDecl *Var = inherited::RebuildExceptionDecl(ExceptionDecl, T, Declarator,
448                                                 Name, Loc, TypeRange);
449  if (Var && !Var->isInvalidDecl())
450    getSema().CurrentInstantiationScope->InstantiatedLocal(ExceptionDecl, Var);
451  return Var;
452}
453
454Sema::OwningExprResult
455TemplateInstantiator::TransformDeclRefExpr(DeclRefExpr *E) {
456  // FIXME: Clean this up a bit
457  NamedDecl *D = E->getDecl();
458  if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D)) {
459    if (NTTP->getDepth() >= TemplateArgs.getNumLevels()) {
460      assert(false && "Cannot reduce non-type template parameter depth yet");
461      return getSema().ExprError();
462    }
463
464    // If the corresponding template argument is NULL or non-existent, it's
465    // because we are performing instantiation from explicitly-specified
466    // template arguments in a function template, but there were some
467    // arguments left unspecified.
468    if (!TemplateArgs.hasTemplateArgument(NTTP->getDepth(),
469                                          NTTP->getPosition()))
470      return SemaRef.Owned(E->Retain());
471
472    const TemplateArgument &Arg = TemplateArgs(NTTP->getDepth(),
473                                               NTTP->getPosition());
474
475    // The template argument itself might be an expression, in which
476    // case we just return that expression.
477    if (Arg.getKind() == TemplateArgument::Expression)
478      return SemaRef.Owned(Arg.getAsExpr()->Retain());
479
480    if (Arg.getKind() == TemplateArgument::Declaration) {
481      ValueDecl *VD = cast<ValueDecl>(Arg.getAsDecl());
482
483      VD = cast_or_null<ValueDecl>(getSema().FindInstantiatedDecl(VD));
484      if (!VD)
485        return SemaRef.ExprError();
486
487      return SemaRef.BuildDeclRefExpr(VD, VD->getType(), E->getLocation(),
488                                      /*FIXME:*/false, /*FIXME:*/false);
489    }
490
491    assert(Arg.getKind() == TemplateArgument::Integral);
492    QualType T = Arg.getIntegralType();
493    if (T->isCharType() || T->isWideCharType())
494      return SemaRef.Owned(new (SemaRef.Context) CharacterLiteral(
495                                            Arg.getAsIntegral()->getZExtValue(),
496                                            T->isWideCharType(),
497                                            T,
498                                            E->getSourceRange().getBegin()));
499    if (T->isBooleanType())
500      return SemaRef.Owned(new (SemaRef.Context) CXXBoolLiteralExpr(
501                                          Arg.getAsIntegral()->getBoolValue(),
502                                          T,
503                                          E->getSourceRange().getBegin()));
504
505    assert(Arg.getAsIntegral()->getBitWidth() == SemaRef.Context.getIntWidth(T));
506    return SemaRef.Owned(new (SemaRef.Context) IntegerLiteral(
507                                              *Arg.getAsIntegral(),
508                                              T,
509                                              E->getSourceRange().getBegin()));
510  }
511
512  NamedDecl *InstD = SemaRef.FindInstantiatedDecl(D);
513  if (!InstD)
514    return SemaRef.ExprError();
515
516  // If we instantiated an UnresolvedUsingDecl and got back an UsingDecl,
517  // we need to get the underlying decl.
518  // FIXME: Is this correct? Maybe FindInstantiatedDecl should do this?
519  InstD = InstD->getUnderlyingDecl();
520
521  // FIXME: nested-name-specifier for QualifiedDeclRefExpr
522  return SemaRef.BuildDeclarationNameExpr(E->getLocation(), InstD,
523                                          /*FIXME:*/false,
524                                          /*FIXME:*/0,
525                                          /*FIXME:*/false);
526}
527
528QualType
529TemplateInstantiator::TransformTemplateTypeParmType(
530                                              const TemplateTypeParmType *T) {
531  if (T->getDepth() < TemplateArgs.getNumLevels()) {
532    // Replace the template type parameter with its corresponding
533    // template argument.
534
535    // If the corresponding template argument is NULL or doesn't exist, it's
536    // because we are performing instantiation from explicitly-specified
537    // template arguments in a function template class, but there were some
538    // arguments left unspecified.
539    if (!TemplateArgs.hasTemplateArgument(T->getDepth(), T->getIndex()))
540      return QualType(T, 0);
541
542    assert(TemplateArgs(T->getDepth(), T->getIndex()).getKind()
543             == TemplateArgument::Type &&
544           "Template argument kind mismatch");
545
546    return TemplateArgs(T->getDepth(), T->getIndex()).getAsType();
547  }
548
549  // The template type parameter comes from an inner template (e.g.,
550  // the template parameter list of a member template inside the
551  // template we are instantiating). Create a new template type
552  // parameter with the template "level" reduced by one.
553  return getSema().Context.getTemplateTypeParmType(
554                                  T->getDepth() - TemplateArgs.getNumLevels(),
555                                                   T->getIndex(),
556                                                   T->isParameterPack(),
557                                                   T->getName());
558}
559
560/// \brief Perform substitution on the type T with a given set of template
561/// arguments.
562///
563/// This routine substitutes the given template arguments into the
564/// type T and produces the instantiated type.
565///
566/// \param T the type into which the template arguments will be
567/// substituted. If this type is not dependent, it will be returned
568/// immediately.
569///
570/// \param TemplateArgs the template arguments that will be
571/// substituted for the top-level template parameters within T.
572///
573/// \param Loc the location in the source code where this substitution
574/// is being performed. It will typically be the location of the
575/// declarator (if we're instantiating the type of some declaration)
576/// or the location of the type in the source code (if, e.g., we're
577/// instantiating the type of a cast expression).
578///
579/// \param Entity the name of the entity associated with a declaration
580/// being instantiated (if any). May be empty to indicate that there
581/// is no such entity (if, e.g., this is a type that occurs as part of
582/// a cast expression) or that the entity has no name (e.g., an
583/// unnamed function parameter).
584///
585/// \returns If the instantiation succeeds, the instantiated
586/// type. Otherwise, produces diagnostics and returns a NULL type.
587QualType Sema::SubstType(QualType T,
588                         const MultiLevelTemplateArgumentList &TemplateArgs,
589                         SourceLocation Loc, DeclarationName Entity) {
590  assert(!ActiveTemplateInstantiations.empty() &&
591         "Cannot perform an instantiation without some context on the "
592         "instantiation stack");
593
594  // If T is not a dependent type, there is nothing to do.
595  if (!T->isDependentType())
596    return T;
597
598  TemplateInstantiator Instantiator(*this, TemplateArgs, Loc, Entity);
599  return Instantiator.TransformType(T);
600}
601
602/// \brief Perform substitution on the base class specifiers of the
603/// given class template specialization.
604///
605/// Produces a diagnostic and returns true on error, returns false and
606/// attaches the instantiated base classes to the class template
607/// specialization if successful.
608bool
609Sema::SubstBaseSpecifiers(CXXRecordDecl *Instantiation,
610                          CXXRecordDecl *Pattern,
611                          const MultiLevelTemplateArgumentList &TemplateArgs) {
612  bool Invalid = false;
613  llvm::SmallVector<CXXBaseSpecifier*, 4> InstantiatedBases;
614  for (ClassTemplateSpecializationDecl::base_class_iterator
615         Base = Pattern->bases_begin(), BaseEnd = Pattern->bases_end();
616       Base != BaseEnd; ++Base) {
617    if (!Base->getType()->isDependentType()) {
618      InstantiatedBases.push_back(new (Context) CXXBaseSpecifier(*Base));
619      continue;
620    }
621
622    QualType BaseType = SubstType(Base->getType(),
623                                  TemplateArgs,
624                                  Base->getSourceRange().getBegin(),
625                                  DeclarationName());
626    if (BaseType.isNull()) {
627      Invalid = true;
628      continue;
629    }
630
631    if (CXXBaseSpecifier *InstantiatedBase
632          = CheckBaseSpecifier(Instantiation,
633                               Base->getSourceRange(),
634                               Base->isVirtual(),
635                               Base->getAccessSpecifierAsWritten(),
636                               BaseType,
637                               /*FIXME: Not totally accurate */
638                               Base->getSourceRange().getBegin()))
639      InstantiatedBases.push_back(InstantiatedBase);
640    else
641      Invalid = true;
642  }
643
644  if (!Invalid &&
645      AttachBaseSpecifiers(Instantiation, InstantiatedBases.data(),
646                           InstantiatedBases.size()))
647    Invalid = true;
648
649  return Invalid;
650}
651
652/// \brief Instantiate the definition of a class from a given pattern.
653///
654/// \param PointOfInstantiation The point of instantiation within the
655/// source code.
656///
657/// \param Instantiation is the declaration whose definition is being
658/// instantiated. This will be either a class template specialization
659/// or a member class of a class template specialization.
660///
661/// \param Pattern is the pattern from which the instantiation
662/// occurs. This will be either the declaration of a class template or
663/// the declaration of a member class of a class template.
664///
665/// \param TemplateArgs The template arguments to be substituted into
666/// the pattern.
667///
668/// \param TSK the kind of implicit or explicit instantiation to perform.
669///
670/// \param Complain whether to complain if the class cannot be instantiated due
671/// to the lack of a definition.
672///
673/// \returns true if an error occurred, false otherwise.
674bool
675Sema::InstantiateClass(SourceLocation PointOfInstantiation,
676                       CXXRecordDecl *Instantiation, CXXRecordDecl *Pattern,
677                       const MultiLevelTemplateArgumentList &TemplateArgs,
678                       TemplateSpecializationKind TSK,
679                       bool Complain) {
680  bool Invalid = false;
681
682  CXXRecordDecl *PatternDef
683    = cast_or_null<CXXRecordDecl>(Pattern->getDefinition(Context));
684  if (!PatternDef) {
685    if (!Complain) {
686      // Say nothing
687    } else if (Pattern == Instantiation->getInstantiatedFromMemberClass()) {
688      Diag(PointOfInstantiation,
689           diag::err_implicit_instantiate_member_undefined)
690        << Context.getTypeDeclType(Instantiation);
691      Diag(Pattern->getLocation(), diag::note_member_of_template_here);
692    } else {
693      Diag(PointOfInstantiation, diag::err_template_instantiate_undefined)
694        << (TSK != TSK_ImplicitInstantiation)
695        << Context.getTypeDeclType(Instantiation);
696      Diag(Pattern->getLocation(), diag::note_template_decl_here);
697    }
698    return true;
699  }
700  Pattern = PatternDef;
701
702  InstantiatingTemplate Inst(*this, PointOfInstantiation, Instantiation);
703  if (Inst)
704    return true;
705
706  // Enter the scope of this instantiation. We don't use
707  // PushDeclContext because we don't have a scope.
708  DeclContext *PreviousContext = CurContext;
709  CurContext = Instantiation;
710
711  // Start the definition of this instantiation.
712  Instantiation->startDefinition();
713
714  // Do substitution on the base class specifiers.
715  if (SubstBaseSpecifiers(Instantiation, Pattern, TemplateArgs))
716    Invalid = true;
717
718  llvm::SmallVector<DeclPtrTy, 4> Fields;
719  for (RecordDecl::decl_iterator Member = Pattern->decls_begin(),
720         MemberEnd = Pattern->decls_end();
721       Member != MemberEnd; ++Member) {
722    Decl *NewMember = SubstDecl(*Member, Instantiation, TemplateArgs);
723    if (NewMember) {
724      if (NewMember->isInvalidDecl())
725        Invalid = true;
726      else if (FieldDecl *Field = dyn_cast<FieldDecl>(NewMember))
727        Fields.push_back(DeclPtrTy::make(Field));
728      else if (UsingDecl *UD = dyn_cast<UsingDecl>(NewMember))
729        Instantiation->addDecl(UD);
730    } else {
731      // FIXME: Eventually, a NULL return will mean that one of the
732      // instantiations was a semantic disaster, and we'll want to set Invalid =
733      // true. For now, we expect to skip some members that we can't yet handle.
734    }
735  }
736
737  // Finish checking fields.
738  ActOnFields(0, Instantiation->getLocation(), DeclPtrTy::make(Instantiation),
739              Fields.data(), Fields.size(), SourceLocation(), SourceLocation(),
740              0);
741
742  // Add any implicitly-declared members that we might need.
743  AddImplicitlyDeclaredMembersToClass(Instantiation);
744
745  // Exit the scope of this instantiation.
746  CurContext = PreviousContext;
747
748  if (!Invalid)
749    Consumer.HandleTagDeclDefinition(Instantiation);
750
751  // If this is an explicit instantiation, instantiate our members, too.
752  if (!Invalid && TSK != TSK_ImplicitInstantiation) {
753    Inst.Clear();
754    InstantiateClassMembers(PointOfInstantiation, Instantiation, TemplateArgs,
755                            TSK);
756  }
757
758  return Invalid;
759}
760
761bool
762Sema::InstantiateClassTemplateSpecialization(
763                           ClassTemplateSpecializationDecl *ClassTemplateSpec,
764                           TemplateSpecializationKind TSK,
765                           bool Complain) {
766  // Perform the actual instantiation on the canonical declaration.
767  ClassTemplateSpec = cast<ClassTemplateSpecializationDecl>(
768                                         ClassTemplateSpec->getCanonicalDecl());
769
770  // We can only instantiate something that hasn't already been
771  // instantiated or specialized. Fail without any diagnostics: our
772  // caller will provide an error message.
773  if (ClassTemplateSpec->getSpecializationKind() != TSK_Undeclared)
774    return true;
775
776  ClassTemplateDecl *Template = ClassTemplateSpec->getSpecializedTemplate();
777  CXXRecordDecl *Pattern = 0;
778
779  // C++ [temp.class.spec.match]p1:
780  //   When a class template is used in a context that requires an
781  //   instantiation of the class, it is necessary to determine
782  //   whether the instantiation is to be generated using the primary
783  //   template or one of the partial specializations. This is done by
784  //   matching the template arguments of the class template
785  //   specialization with the template argument lists of the partial
786  //   specializations.
787  typedef std::pair<ClassTemplatePartialSpecializationDecl *,
788                    TemplateArgumentList *> MatchResult;
789  llvm::SmallVector<MatchResult, 4> Matched;
790  for (llvm::FoldingSet<ClassTemplatePartialSpecializationDecl>::iterator
791         Partial = Template->getPartialSpecializations().begin(),
792         PartialEnd = Template->getPartialSpecializations().end();
793       Partial != PartialEnd;
794       ++Partial) {
795    TemplateDeductionInfo Info(Context);
796    if (TemplateDeductionResult Result
797          = DeduceTemplateArguments(&*Partial,
798                                    ClassTemplateSpec->getTemplateArgs(),
799                                    Info)) {
800      // FIXME: Store the failed-deduction information for use in
801      // diagnostics, later.
802      (void)Result;
803    } else {
804      Matched.push_back(std::make_pair(&*Partial, Info.take()));
805    }
806  }
807
808  if (Matched.size() == 1) {
809    //   -- If exactly one matching specialization is found, the
810    //      instantiation is generated from that specialization.
811    Pattern = Matched[0].first;
812    ClassTemplateSpec->setInstantiationOf(Matched[0].first, Matched[0].second);
813  } else if (Matched.size() > 1) {
814    //   -- If more than one matching specialization is found, the
815    //      partial order rules (14.5.4.2) are used to determine
816    //      whether one of the specializations is more specialized
817    //      than the others. If none of the specializations is more
818    //      specialized than all of the other matching
819    //      specializations, then the use of the class template is
820    //      ambiguous and the program is ill-formed.
821    // FIXME: Implement partial ordering of class template partial
822    // specializations.
823    Diag(ClassTemplateSpec->getLocation(),
824         diag::unsup_template_partial_spec_ordering);
825
826    // FIXME: Temporary hack to fall back to the primary template
827    ClassTemplateDecl *OrigTemplate = Template;
828    while (OrigTemplate->getInstantiatedFromMemberTemplate())
829      OrigTemplate = OrigTemplate->getInstantiatedFromMemberTemplate();
830
831    Pattern = OrigTemplate->getTemplatedDecl();
832  } else {
833    //   -- If no matches are found, the instantiation is generated
834    //      from the primary template.
835    ClassTemplateDecl *OrigTemplate = Template;
836    while (OrigTemplate->getInstantiatedFromMemberTemplate())
837      OrigTemplate = OrigTemplate->getInstantiatedFromMemberTemplate();
838
839    Pattern = OrigTemplate->getTemplatedDecl();
840  }
841
842  // Note that this is an instantiation.
843  ClassTemplateSpec->setSpecializationKind(TSK);
844
845  bool Result = InstantiateClass(ClassTemplateSpec->getLocation(),
846                                 ClassTemplateSpec, Pattern,
847                              getTemplateInstantiationArgs(ClassTemplateSpec),
848                                 TSK,
849                                 Complain);
850
851  for (unsigned I = 0, N = Matched.size(); I != N; ++I) {
852    // FIXME: Implement TemplateArgumentList::Destroy!
853    //    if (Matched[I].first != Pattern)
854    //      Matched[I].second->Destroy(Context);
855  }
856
857  return Result;
858}
859
860/// \brief Instantiates the definitions of all of the member
861/// of the given class, which is an instantiation of a class template
862/// or a member class of a template.
863void
864Sema::InstantiateClassMembers(SourceLocation PointOfInstantiation,
865                              CXXRecordDecl *Instantiation,
866                        const MultiLevelTemplateArgumentList &TemplateArgs,
867                              TemplateSpecializationKind TSK) {
868  // FIXME: extern templates
869  for (DeclContext::decl_iterator D = Instantiation->decls_begin(),
870                               DEnd = Instantiation->decls_end();
871       D != DEnd; ++D) {
872    if (FunctionDecl *Function = dyn_cast<FunctionDecl>(*D)) {
873      if (!Function->getBody())
874        InstantiateFunctionDefinition(PointOfInstantiation, Function);
875    } else if (VarDecl *Var = dyn_cast<VarDecl>(*D)) {
876      if (Var->isStaticDataMember())
877        InstantiateStaticDataMemberDefinition(PointOfInstantiation, Var);
878    } else if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(*D)) {
879      if (!Record->isInjectedClassName() && !Record->getDefinition(Context)) {
880        assert(Record->getInstantiatedFromMemberClass() &&
881               "Missing instantiated-from-template information");
882        InstantiateClass(PointOfInstantiation, Record,
883                         Record->getInstantiatedFromMemberClass(),
884                         TemplateArgs,
885                         TSK);
886      }
887    }
888  }
889}
890
891/// \brief Instantiate the definitions of all of the members of the
892/// given class template specialization, which was named as part of an
893/// explicit instantiation.
894void
895Sema::InstantiateClassTemplateSpecializationMembers(
896                                           SourceLocation PointOfInstantiation,
897                            ClassTemplateSpecializationDecl *ClassTemplateSpec,
898                                               TemplateSpecializationKind TSK) {
899  // C++0x [temp.explicit]p7:
900  //   An explicit instantiation that names a class template
901  //   specialization is an explicit instantion of the same kind
902  //   (declaration or definition) of each of its members (not
903  //   including members inherited from base classes) that has not
904  //   been previously explicitly specialized in the translation unit
905  //   containing the explicit instantiation, except as described
906  //   below.
907  InstantiateClassMembers(PointOfInstantiation, ClassTemplateSpec,
908                          getTemplateInstantiationArgs(ClassTemplateSpec),
909                          TSK);
910}
911
912Sema::OwningStmtResult
913Sema::SubstStmt(Stmt *S, const MultiLevelTemplateArgumentList &TemplateArgs) {
914  if (!S)
915    return Owned(S);
916
917  TemplateInstantiator Instantiator(*this, TemplateArgs,
918                                    SourceLocation(),
919                                    DeclarationName());
920  return Instantiator.TransformStmt(S);
921}
922
923Sema::OwningExprResult
924Sema::SubstExpr(Expr *E, const MultiLevelTemplateArgumentList &TemplateArgs) {
925  if (!E)
926    return Owned(E);
927
928  TemplateInstantiator Instantiator(*this, TemplateArgs,
929                                    SourceLocation(),
930                                    DeclarationName());
931  return Instantiator.TransformExpr(E);
932}
933
934/// \brief Do template substitution on a nested-name-specifier.
935NestedNameSpecifier *
936Sema::SubstNestedNameSpecifier(NestedNameSpecifier *NNS,
937                               SourceRange Range,
938                         const MultiLevelTemplateArgumentList &TemplateArgs) {
939  TemplateInstantiator Instantiator(*this, TemplateArgs, Range.getBegin(),
940                                    DeclarationName());
941  return Instantiator.TransformNestedNameSpecifier(NNS, Range);
942}
943
944TemplateName
945Sema::SubstTemplateName(TemplateName Name, SourceLocation Loc,
946                        const MultiLevelTemplateArgumentList &TemplateArgs) {
947  TemplateInstantiator Instantiator(*this, TemplateArgs, Loc,
948                                    DeclarationName());
949  return Instantiator.TransformTemplateName(Name);
950}
951
952TemplateArgument Sema::Subst(TemplateArgument Arg,
953                         const MultiLevelTemplateArgumentList &TemplateArgs) {
954  TemplateInstantiator Instantiator(*this, TemplateArgs, SourceLocation(),
955                                    DeclarationName());
956  return Instantiator.TransformTemplateArgument(Arg);
957}
958