SemaTemplateInstantiate.cpp revision 3395938e6e35025b5e9c74181ea37b0c716cd97a 
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    const MultiLevelTemplateArgumentList &TemplateArgs;
351    SourceLocation Loc;
352    DeclarationName Entity;
353
354  public:
355    typedef TreeTransform<TemplateInstantiator> inherited;
356
357    TemplateInstantiator(Sema &SemaRef,
358                         const MultiLevelTemplateArgumentList &TemplateArgs,
359                         SourceLocation Loc,
360                         DeclarationName Entity)
361      : inherited(SemaRef), TemplateArgs(TemplateArgs), Loc(Loc),
362        Entity(Entity) { }
363
364    /// \brief Determine whether the given type \p T has already been
365    /// transformed.
366    ///
367    /// For the purposes of template instantiation, a type has already been
368    /// transformed if it is NULL or if it is not dependent.
369    bool AlreadyTransformed(QualType T) {
370      return T.isNull() || !T->isDependentType();
371    }
372
373    /// \brief Returns the location of the entity being instantiated, if known.
374    SourceLocation getBaseLocation() { return Loc; }
375
376    /// \brief Returns the name of the entity being instantiated, if any.
377    DeclarationName getBaseEntity() { return Entity; }
378
379    /// \brief Transform the given declaration by instantiating a reference to
380    /// this declaration.
381    Decl *TransformDecl(Decl *D);
382
383    /// \brief Transform the definition of the given declaration by
384    /// instantiating it.
385    Decl *TransformDefinition(Decl *D);
386
387    /// \brief Rebuild the exception declaration and register the declaration
388    /// as an instantiated local.
389    VarDecl *RebuildExceptionDecl(VarDecl *ExceptionDecl, QualType T,
390                                  DeclaratorInfo *Declarator,
391                                  IdentifierInfo *Name,
392                                  SourceLocation Loc, SourceRange TypeRange);
393
394    /// \brief Check for tag mismatches when instantiating an
395    /// elaborated type.
396    QualType RebuildElaboratedType(QualType T, ElaboratedType::TagKind Tag);
397
398    Sema::OwningExprResult TransformPredefinedExpr(PredefinedExpr *E);
399    Sema::OwningExprResult TransformDeclRefExpr(DeclRefExpr *E);
400
401    /// \brief Transforms a template type parameter type by performing
402    /// substitution of the corresponding template type argument.
403    QualType TransformTemplateTypeParmType(const TemplateTypeParmType *T);
404  };
405}
406
407Decl *TemplateInstantiator::TransformDecl(Decl *D) {
408  if (!D)
409    return 0;
410
411  if (TemplateTemplateParmDecl *TTP = dyn_cast<TemplateTemplateParmDecl>(D)) {
412    if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
413      assert(TemplateArgs(TTP->getDepth(), TTP->getPosition()).getAsDecl() &&
414             "Wrong kind of template template argument");
415      return cast<TemplateDecl>(TemplateArgs(TTP->getDepth(),
416                                             TTP->getPosition()).getAsDecl());
417    }
418
419    // If the corresponding template argument is NULL or non-existent, it's
420    // because we are performing instantiation from explicitly-specified
421    // template arguments in a function template, but there were some
422    // arguments left unspecified.
423    if (!TemplateArgs.hasTemplateArgument(TTP->getDepth(),
424                                          TTP->getPosition()))
425      return D;
426
427    // FIXME: Implement depth reduction of template template parameters
428    assert(false &&
429      "Reducing depth of template template parameters is not yet implemented");
430  }
431
432  return SemaRef.FindInstantiatedDecl(cast<NamedDecl>(D), TemplateArgs);
433}
434
435Decl *TemplateInstantiator::TransformDefinition(Decl *D) {
436  Decl *Inst = getSema().SubstDecl(D, getSema().CurContext, TemplateArgs);
437  if (!Inst)
438    return 0;
439
440  getSema().CurrentInstantiationScope->InstantiatedLocal(D, Inst);
441  return Inst;
442}
443
444VarDecl *
445TemplateInstantiator::RebuildExceptionDecl(VarDecl *ExceptionDecl,
446                                           QualType T,
447                                           DeclaratorInfo *Declarator,
448                                           IdentifierInfo *Name,
449                                           SourceLocation Loc,
450                                           SourceRange TypeRange) {
451  VarDecl *Var = inherited::RebuildExceptionDecl(ExceptionDecl, T, Declarator,
452                                                 Name, Loc, TypeRange);
453  if (Var && !Var->isInvalidDecl())
454    getSema().CurrentInstantiationScope->InstantiatedLocal(ExceptionDecl, Var);
455  return Var;
456}
457
458QualType
459TemplateInstantiator::RebuildElaboratedType(QualType T,
460                                            ElaboratedType::TagKind Tag) {
461  if (const TagType *TT = T->getAs<TagType>()) {
462    TagDecl* TD = TT->getDecl();
463
464    // FIXME: this location is very wrong;  we really need typelocs.
465    SourceLocation TagLocation = TD->getTagKeywordLoc();
466
467    // FIXME: type might be anonymous.
468    IdentifierInfo *Id = TD->getIdentifier();
469
470    // TODO: should we even warn on struct/class mismatches for this?  Seems
471    // like it's likely to produce a lot of spurious errors.
472    if (!SemaRef.isAcceptableTagRedeclaration(TD, Tag, TagLocation, *Id)) {
473      SemaRef.Diag(TagLocation, diag::err_use_with_wrong_tag)
474        << Id
475        << CodeModificationHint::CreateReplacement(SourceRange(TagLocation),
476                                                   TD->getKindName());
477      SemaRef.Diag(TD->getLocation(), diag::note_previous_use);
478    }
479  }
480
481  return TreeTransform<TemplateInstantiator>::RebuildElaboratedType(T, Tag);
482}
483
484Sema::OwningExprResult
485TemplateInstantiator::TransformPredefinedExpr(PredefinedExpr *E) {
486  if (!E->isTypeDependent())
487    return SemaRef.Owned(E->Retain());
488
489  FunctionDecl *currentDecl = getSema().getCurFunctionDecl();
490  assert(currentDecl && "Must have current function declaration when "
491                        "instantiating.");
492
493  PredefinedExpr::IdentType IT = E->getIdentType();
494
495  unsigned Length =
496    PredefinedExpr::ComputeName(getSema().Context, IT, currentDecl).length();
497
498  llvm::APInt LengthI(32, Length + 1);
499  QualType ResTy = getSema().Context.CharTy.withConst();
500  ResTy = getSema().Context.getConstantArrayType(ResTy, LengthI,
501                                                 ArrayType::Normal, 0);
502  PredefinedExpr *PE =
503    new (getSema().Context) PredefinedExpr(E->getLocation(), ResTy, IT);
504  return getSema().Owned(PE);
505}
506
507Sema::OwningExprResult
508TemplateInstantiator::TransformDeclRefExpr(DeclRefExpr *E) {
509  // FIXME: Clean this up a bit
510  NamedDecl *D = E->getDecl();
511  if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D)) {
512    if (NTTP->getDepth() >= TemplateArgs.getNumLevels()) {
513      assert(false && "Cannot reduce non-type template parameter depth yet");
514      return getSema().ExprError();
515    }
516
517    // If the corresponding template argument is NULL or non-existent, it's
518    // because we are performing instantiation from explicitly-specified
519    // template arguments in a function template, but there were some
520    // arguments left unspecified.
521    if (!TemplateArgs.hasTemplateArgument(NTTP->getDepth(),
522                                          NTTP->getPosition()))
523      return SemaRef.Owned(E->Retain());
524
525    const TemplateArgument &Arg = TemplateArgs(NTTP->getDepth(),
526                                               NTTP->getPosition());
527
528    // The template argument itself might be an expression, in which
529    // case we just return that expression.
530    if (Arg.getKind() == TemplateArgument::Expression)
531      return SemaRef.Owned(Arg.getAsExpr()->Retain());
532
533    if (Arg.getKind() == TemplateArgument::Declaration) {
534      ValueDecl *VD = cast<ValueDecl>(Arg.getAsDecl());
535
536      VD = cast_or_null<ValueDecl>(
537                              getSema().FindInstantiatedDecl(VD, TemplateArgs));
538      if (!VD)
539        return SemaRef.ExprError();
540
541      return SemaRef.BuildDeclRefExpr(VD, VD->getType(), E->getLocation(),
542                                      /*FIXME:*/false, /*FIXME:*/false);
543    }
544
545    assert(Arg.getKind() == TemplateArgument::Integral);
546    QualType T = Arg.getIntegralType();
547    if (T->isCharType() || T->isWideCharType())
548      return SemaRef.Owned(new (SemaRef.Context) CharacterLiteral(
549                                            Arg.getAsIntegral()->getZExtValue(),
550                                            T->isWideCharType(),
551                                            T,
552                                            E->getSourceRange().getBegin()));
553    if (T->isBooleanType())
554      return SemaRef.Owned(new (SemaRef.Context) CXXBoolLiteralExpr(
555                                          Arg.getAsIntegral()->getBoolValue(),
556                                          T,
557                                          E->getSourceRange().getBegin()));
558
559    assert(Arg.getAsIntegral()->getBitWidth() == SemaRef.Context.getIntWidth(T));
560    return SemaRef.Owned(new (SemaRef.Context) IntegerLiteral(
561                                              *Arg.getAsIntegral(),
562                                              T,
563                                              E->getSourceRange().getBegin()));
564  }
565
566  NamedDecl *InstD = SemaRef.FindInstantiatedDecl(D, TemplateArgs);
567  if (!InstD)
568    return SemaRef.ExprError();
569
570  // If we instantiated an UnresolvedUsingDecl and got back an UsingDecl,
571  // we need to get the underlying decl.
572  // FIXME: Is this correct? Maybe FindInstantiatedDecl should do this?
573  InstD = InstD->getUnderlyingDecl();
574
575  // FIXME: nested-name-specifier for QualifiedDeclRefExpr
576  return SemaRef.BuildDeclarationNameExpr(E->getLocation(), InstD,
577                                          /*FIXME:*/false,
578                                          /*FIXME:*/0,
579                                          /*FIXME:*/false);
580}
581
582QualType
583TemplateInstantiator::TransformTemplateTypeParmType(
584                                              const TemplateTypeParmType *T) {
585  if (T->getDepth() < TemplateArgs.getNumLevels()) {
586    // Replace the template type parameter with its corresponding
587    // template argument.
588
589    // If the corresponding template argument is NULL or doesn't exist, it's
590    // because we are performing instantiation from explicitly-specified
591    // template arguments in a function template class, but there were some
592    // arguments left unspecified.
593    if (!TemplateArgs.hasTemplateArgument(T->getDepth(), T->getIndex()))
594      return QualType(T, 0);
595
596    assert(TemplateArgs(T->getDepth(), T->getIndex()).getKind()
597             == TemplateArgument::Type &&
598           "Template argument kind mismatch");
599
600    return TemplateArgs(T->getDepth(), T->getIndex()).getAsType();
601  }
602
603  // The template type parameter comes from an inner template (e.g.,
604  // the template parameter list of a member template inside the
605  // template we are instantiating). Create a new template type
606  // parameter with the template "level" reduced by one.
607  return getSema().Context.getTemplateTypeParmType(
608                                  T->getDepth() - TemplateArgs.getNumLevels(),
609                                                   T->getIndex(),
610                                                   T->isParameterPack(),
611                                                   T->getName());
612}
613
614/// \brief Perform substitution on the type T with a given set of template
615/// arguments.
616///
617/// This routine substitutes the given template arguments into the
618/// type T and produces the instantiated type.
619///
620/// \param T the type into which the template arguments will be
621/// substituted. If this type is not dependent, it will be returned
622/// immediately.
623///
624/// \param TemplateArgs the template arguments that will be
625/// substituted for the top-level template parameters within T.
626///
627/// \param Loc the location in the source code where this substitution
628/// is being performed. It will typically be the location of the
629/// declarator (if we're instantiating the type of some declaration)
630/// or the location of the type in the source code (if, e.g., we're
631/// instantiating the type of a cast expression).
632///
633/// \param Entity the name of the entity associated with a declaration
634/// being instantiated (if any). May be empty to indicate that there
635/// is no such entity (if, e.g., this is a type that occurs as part of
636/// a cast expression) or that the entity has no name (e.g., an
637/// unnamed function parameter).
638///
639/// \returns If the instantiation succeeds, the instantiated
640/// type. Otherwise, produces diagnostics and returns a NULL type.
641QualType Sema::SubstType(QualType T,
642                         const MultiLevelTemplateArgumentList &TemplateArgs,
643                         SourceLocation Loc, DeclarationName Entity) {
644  assert(!ActiveTemplateInstantiations.empty() &&
645         "Cannot perform an instantiation without some context on the "
646         "instantiation stack");
647
648  // If T is not a dependent type, there is nothing to do.
649  if (!T->isDependentType())
650    return T;
651
652  TemplateInstantiator Instantiator(*this, TemplateArgs, Loc, Entity);
653  return Instantiator.TransformType(T);
654}
655
656/// \brief Perform substitution on the base class specifiers of the
657/// given class template specialization.
658///
659/// Produces a diagnostic and returns true on error, returns false and
660/// attaches the instantiated base classes to the class template
661/// specialization if successful.
662bool
663Sema::SubstBaseSpecifiers(CXXRecordDecl *Instantiation,
664                          CXXRecordDecl *Pattern,
665                          const MultiLevelTemplateArgumentList &TemplateArgs) {
666  bool Invalid = false;
667  llvm::SmallVector<CXXBaseSpecifier*, 4> InstantiatedBases;
668  for (ClassTemplateSpecializationDecl::base_class_iterator
669         Base = Pattern->bases_begin(), BaseEnd = Pattern->bases_end();
670       Base != BaseEnd; ++Base) {
671    if (!Base->getType()->isDependentType()) {
672      InstantiatedBases.push_back(new (Context) CXXBaseSpecifier(*Base));
673      continue;
674    }
675
676    QualType BaseType = SubstType(Base->getType(),
677                                  TemplateArgs,
678                                  Base->getSourceRange().getBegin(),
679                                  DeclarationName());
680    if (BaseType.isNull()) {
681      Invalid = true;
682      continue;
683    }
684
685    if (CXXBaseSpecifier *InstantiatedBase
686          = CheckBaseSpecifier(Instantiation,
687                               Base->getSourceRange(),
688                               Base->isVirtual(),
689                               Base->getAccessSpecifierAsWritten(),
690                               BaseType,
691                               /*FIXME: Not totally accurate */
692                               Base->getSourceRange().getBegin()))
693      InstantiatedBases.push_back(InstantiatedBase);
694    else
695      Invalid = true;
696  }
697
698  if (!Invalid &&
699      AttachBaseSpecifiers(Instantiation, InstantiatedBases.data(),
700                           InstantiatedBases.size()))
701    Invalid = true;
702
703  return Invalid;
704}
705
706/// \brief Instantiate the definition of a class from a given pattern.
707///
708/// \param PointOfInstantiation The point of instantiation within the
709/// source code.
710///
711/// \param Instantiation is the declaration whose definition is being
712/// instantiated. This will be either a class template specialization
713/// or a member class of a class template specialization.
714///
715/// \param Pattern is the pattern from which the instantiation
716/// occurs. This will be either the declaration of a class template or
717/// the declaration of a member class of a class template.
718///
719/// \param TemplateArgs The template arguments to be substituted into
720/// the pattern.
721///
722/// \param TSK the kind of implicit or explicit instantiation to perform.
723///
724/// \param Complain whether to complain if the class cannot be instantiated due
725/// to the lack of a definition.
726///
727/// \returns true if an error occurred, false otherwise.
728bool
729Sema::InstantiateClass(SourceLocation PointOfInstantiation,
730                       CXXRecordDecl *Instantiation, CXXRecordDecl *Pattern,
731                       const MultiLevelTemplateArgumentList &TemplateArgs,
732                       TemplateSpecializationKind TSK,
733                       bool Complain) {
734  bool Invalid = false;
735
736  CXXRecordDecl *PatternDef
737    = cast_or_null<CXXRecordDecl>(Pattern->getDefinition(Context));
738  if (!PatternDef) {
739    if (!Complain) {
740      // Say nothing
741    } else if (Pattern == Instantiation->getInstantiatedFromMemberClass()) {
742      Diag(PointOfInstantiation,
743           diag::err_implicit_instantiate_member_undefined)
744        << Context.getTypeDeclType(Instantiation);
745      Diag(Pattern->getLocation(), diag::note_member_of_template_here);
746    } else {
747      Diag(PointOfInstantiation, diag::err_template_instantiate_undefined)
748        << (TSK != TSK_ImplicitInstantiation)
749        << Context.getTypeDeclType(Instantiation);
750      Diag(Pattern->getLocation(), diag::note_template_decl_here);
751    }
752    return true;
753  }
754  Pattern = PatternDef;
755
756  InstantiatingTemplate Inst(*this, PointOfInstantiation, Instantiation);
757  if (Inst)
758    return true;
759
760  // Enter the scope of this instantiation. We don't use
761  // PushDeclContext because we don't have a scope.
762  DeclContext *PreviousContext = CurContext;
763  CurContext = Instantiation;
764
765  // Start the definition of this instantiation.
766  Instantiation->startDefinition();
767
768  // Do substitution on the base class specifiers.
769  if (SubstBaseSpecifiers(Instantiation, Pattern, TemplateArgs))
770    Invalid = true;
771
772  llvm::SmallVector<DeclPtrTy, 4> Fields;
773  for (RecordDecl::decl_iterator Member = Pattern->decls_begin(),
774         MemberEnd = Pattern->decls_end();
775       Member != MemberEnd; ++Member) {
776    Decl *NewMember = SubstDecl(*Member, Instantiation, TemplateArgs);
777    if (NewMember) {
778      if (NewMember->isInvalidDecl())
779        Invalid = true;
780      else if (FieldDecl *Field = dyn_cast<FieldDecl>(NewMember))
781        Fields.push_back(DeclPtrTy::make(Field));
782      else if (UsingDecl *UD = dyn_cast<UsingDecl>(NewMember))
783        Instantiation->addDecl(UD);
784    } else {
785      // FIXME: Eventually, a NULL return will mean that one of the
786      // instantiations was a semantic disaster, and we'll want to set Invalid =
787      // true. For now, we expect to skip some members that we can't yet handle.
788    }
789  }
790
791  // Finish checking fields.
792  ActOnFields(0, Instantiation->getLocation(), DeclPtrTy::make(Instantiation),
793              Fields.data(), Fields.size(), SourceLocation(), SourceLocation(),
794              0);
795
796  // Add any implicitly-declared members that we might need.
797  AddImplicitlyDeclaredMembersToClass(Instantiation);
798
799  // Exit the scope of this instantiation.
800  CurContext = PreviousContext;
801
802  if (!Invalid)
803    Consumer.HandleTagDeclDefinition(Instantiation);
804
805  // If this is an explicit instantiation, instantiate our members, too.
806  if (!Invalid && TSK != TSK_ImplicitInstantiation) {
807    Inst.Clear();
808    InstantiateClassMembers(PointOfInstantiation, Instantiation, TemplateArgs,
809                            TSK);
810  }
811
812  return Invalid;
813}
814
815bool
816Sema::InstantiateClassTemplateSpecialization(
817                           ClassTemplateSpecializationDecl *ClassTemplateSpec,
818                           TemplateSpecializationKind TSK,
819                           bool Complain) {
820  // Perform the actual instantiation on the canonical declaration.
821  ClassTemplateSpec = cast<ClassTemplateSpecializationDecl>(
822                                         ClassTemplateSpec->getCanonicalDecl());
823
824  // Check whether we have already instantiated or specialized this class
825  // template specialization.
826  if (ClassTemplateSpec->getSpecializationKind() != TSK_Undeclared) {
827    if (ClassTemplateSpec->getSpecializationKind() ==
828          TSK_ExplicitInstantiationDeclaration &&
829        TSK == TSK_ExplicitInstantiationDefinition) {
830      // An explicit instantiation definition follows an explicit instantiation
831      // declaration (C++0x [temp.explicit]p10); go ahead and perform the
832      // explicit instantiation.
833      ClassTemplateSpec->setSpecializationKind(TSK);
834      InstantiateClassTemplateSpecializationMembers(
835                        /*FIXME?*/ClassTemplateSpec->getPointOfInstantiation(),
836                                  ClassTemplateSpec,
837                                  TSK);
838      return false;
839    }
840
841    // We can only instantiate something that hasn't already been
842    // instantiated or specialized. Fail without any diagnostics: our
843    // caller will provide an error message.
844    return true;
845  }
846
847  if (ClassTemplateSpec->isInvalidDecl())
848    return true;
849
850  ClassTemplateDecl *Template = ClassTemplateSpec->getSpecializedTemplate();
851  CXXRecordDecl *Pattern = 0;
852
853  // C++ [temp.class.spec.match]p1:
854  //   When a class template is used in a context that requires an
855  //   instantiation of the class, it is necessary to determine
856  //   whether the instantiation is to be generated using the primary
857  //   template or one of the partial specializations. This is done by
858  //   matching the template arguments of the class template
859  //   specialization with the template argument lists of the partial
860  //   specializations.
861  typedef std::pair<ClassTemplatePartialSpecializationDecl *,
862                    TemplateArgumentList *> MatchResult;
863  llvm::SmallVector<MatchResult, 4> Matched;
864  for (llvm::FoldingSet<ClassTemplatePartialSpecializationDecl>::iterator
865         Partial = Template->getPartialSpecializations().begin(),
866         PartialEnd = Template->getPartialSpecializations().end();
867       Partial != PartialEnd;
868       ++Partial) {
869    TemplateDeductionInfo Info(Context);
870    if (TemplateDeductionResult Result
871          = DeduceTemplateArguments(&*Partial,
872                                    ClassTemplateSpec->getTemplateArgs(),
873                                    Info)) {
874      // FIXME: Store the failed-deduction information for use in
875      // diagnostics, later.
876      (void)Result;
877    } else {
878      Matched.push_back(std::make_pair(&*Partial, Info.take()));
879    }
880  }
881
882  if (Matched.size() == 1) {
883    //   -- If exactly one matching specialization is found, the
884    //      instantiation is generated from that specialization.
885    Pattern = Matched[0].first;
886    ClassTemplateSpec->setInstantiationOf(Matched[0].first, Matched[0].second);
887  } else if (Matched.size() > 1) {
888    //   -- If more than one matching specialization is found, the
889    //      partial order rules (14.5.4.2) are used to determine
890    //      whether one of the specializations is more specialized
891    //      than the others. If none of the specializations is more
892    //      specialized than all of the other matching
893    //      specializations, then the use of the class template is
894    //      ambiguous and the program is ill-formed.
895    llvm::SmallVector<MatchResult, 4>::iterator Best = Matched.begin();
896    for (llvm::SmallVector<MatchResult, 4>::iterator P = Best + 1,
897                                                  PEnd = Matched.end();
898         P != PEnd; ++P) {
899      if (getMoreSpecializedPartialSpecialization(P->first, Best->first)
900            == P->first)
901        Best = P;
902    }
903
904    // Determine if the best partial specialization is more specialized than
905    // the others.
906    bool Ambiguous = false;
907    for (llvm::SmallVector<MatchResult, 4>::iterator P = Matched.begin(),
908                                                  PEnd = Matched.end();
909         P != PEnd; ++P) {
910      if (P != Best &&
911          getMoreSpecializedPartialSpecialization(P->first, Best->first)
912            != Best->first) {
913        Ambiguous = true;
914        break;
915      }
916    }
917
918    if (Ambiguous) {
919      // Partial ordering did not produce a clear winner. Complain.
920      ClassTemplateSpec->setInvalidDecl();
921      Diag(ClassTemplateSpec->getPointOfInstantiation(),
922           diag::err_partial_spec_ordering_ambiguous)
923        << ClassTemplateSpec;
924
925      // Print the matching partial specializations.
926      for (llvm::SmallVector<MatchResult, 4>::iterator P = Matched.begin(),
927                                                    PEnd = Matched.end();
928           P != PEnd; ++P)
929        Diag(P->first->getLocation(), diag::note_partial_spec_match)
930          << getTemplateArgumentBindingsText(P->first->getTemplateParameters(),
931                                             *P->second);
932
933      return true;
934    }
935
936    // Instantiate using the best class template partial specialization.
937    Pattern = Best->first;
938    ClassTemplateSpec->setInstantiationOf(Best->first, Best->second);
939  } else {
940    //   -- If no matches are found, the instantiation is generated
941    //      from the primary template.
942    ClassTemplateDecl *OrigTemplate = Template;
943    while (OrigTemplate->getInstantiatedFromMemberTemplate())
944      OrigTemplate = OrigTemplate->getInstantiatedFromMemberTemplate();
945
946    Pattern = OrigTemplate->getTemplatedDecl();
947  }
948
949  // Note that this is an instantiation.
950  ClassTemplateSpec->setSpecializationKind(TSK);
951
952  bool Result = InstantiateClass(ClassTemplateSpec->getPointOfInstantiation(),
953                                 ClassTemplateSpec, Pattern,
954                              getTemplateInstantiationArgs(ClassTemplateSpec),
955                                 TSK,
956                                 Complain);
957
958  for (unsigned I = 0, N = Matched.size(); I != N; ++I) {
959    // FIXME: Implement TemplateArgumentList::Destroy!
960    //    if (Matched[I].first != Pattern)
961    //      Matched[I].second->Destroy(Context);
962  }
963
964  return Result;
965}
966
967/// \brief Instantiates the definitions of all of the member
968/// of the given class, which is an instantiation of a class template
969/// or a member class of a template.
970void
971Sema::InstantiateClassMembers(SourceLocation PointOfInstantiation,
972                              CXXRecordDecl *Instantiation,
973                        const MultiLevelTemplateArgumentList &TemplateArgs,
974                              TemplateSpecializationKind TSK) {
975  // FIXME: extern templates
976  for (DeclContext::decl_iterator D = Instantiation->decls_begin(),
977                               DEnd = Instantiation->decls_end();
978       D != DEnd; ++D) {
979    if (FunctionDecl *Function = dyn_cast<FunctionDecl>(*D)) {
980      if (!Function->getBody() && TSK != TSK_ExplicitInstantiationDeclaration)
981        InstantiateFunctionDefinition(PointOfInstantiation, Function);
982    } else if (VarDecl *Var = dyn_cast<VarDecl>(*D)) {
983      if (Var->isStaticDataMember() &&
984          TSK != TSK_ExplicitInstantiationDeclaration)
985        InstantiateStaticDataMemberDefinition(PointOfInstantiation, Var);
986    } else if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(*D)) {
987      if (!Record->isInjectedClassName() && !Record->getDefinition(Context)) {
988        assert(Record->getInstantiatedFromMemberClass() &&
989               "Missing instantiated-from-template information");
990        InstantiateClass(PointOfInstantiation, Record,
991                         Record->getInstantiatedFromMemberClass(),
992                         TemplateArgs,
993                         TSK);
994      }
995    }
996  }
997}
998
999/// \brief Instantiate the definitions of all of the members of the
1000/// given class template specialization, which was named as part of an
1001/// explicit instantiation.
1002void
1003Sema::InstantiateClassTemplateSpecializationMembers(
1004                                           SourceLocation PointOfInstantiation,
1005                            ClassTemplateSpecializationDecl *ClassTemplateSpec,
1006                                               TemplateSpecializationKind TSK) {
1007  // C++0x [temp.explicit]p7:
1008  //   An explicit instantiation that names a class template
1009  //   specialization is an explicit instantion of the same kind
1010  //   (declaration or definition) of each of its members (not
1011  //   including members inherited from base classes) that has not
1012  //   been previously explicitly specialized in the translation unit
1013  //   containing the explicit instantiation, except as described
1014  //   below.
1015  InstantiateClassMembers(PointOfInstantiation, ClassTemplateSpec,
1016                          getTemplateInstantiationArgs(ClassTemplateSpec),
1017                          TSK);
1018}
1019
1020Sema::OwningStmtResult
1021Sema::SubstStmt(Stmt *S, const MultiLevelTemplateArgumentList &TemplateArgs) {
1022  if (!S)
1023    return Owned(S);
1024
1025  TemplateInstantiator Instantiator(*this, TemplateArgs,
1026                                    SourceLocation(),
1027                                    DeclarationName());
1028  return Instantiator.TransformStmt(S);
1029}
1030
1031Sema::OwningExprResult
1032Sema::SubstExpr(Expr *E, const MultiLevelTemplateArgumentList &TemplateArgs) {
1033  if (!E)
1034    return Owned(E);
1035
1036  TemplateInstantiator Instantiator(*this, TemplateArgs,
1037                                    SourceLocation(),
1038                                    DeclarationName());
1039  return Instantiator.TransformExpr(E);
1040}
1041
1042/// \brief Do template substitution on a nested-name-specifier.
1043NestedNameSpecifier *
1044Sema::SubstNestedNameSpecifier(NestedNameSpecifier *NNS,
1045                               SourceRange Range,
1046                         const MultiLevelTemplateArgumentList &TemplateArgs) {
1047  TemplateInstantiator Instantiator(*this, TemplateArgs, Range.getBegin(),
1048                                    DeclarationName());
1049  return Instantiator.TransformNestedNameSpecifier(NNS, Range);
1050}
1051
1052TemplateName
1053Sema::SubstTemplateName(TemplateName Name, SourceLocation Loc,
1054                        const MultiLevelTemplateArgumentList &TemplateArgs) {
1055  TemplateInstantiator Instantiator(*this, TemplateArgs, Loc,
1056                                    DeclarationName());
1057  return Instantiator.TransformTemplateName(Name);
1058}
1059
1060TemplateArgument Sema::Subst(TemplateArgument Arg,
1061                         const MultiLevelTemplateArgumentList &TemplateArgs) {
1062  TemplateInstantiator Instantiator(*this, TemplateArgs, SourceLocation(),
1063                                    DeclarationName());
1064  return Instantiator.TransformTemplateArgument(Arg);
1065}
1066