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