SemaTemplateInstantiate.cpp revision 5b3f9130b95c0b73b74a8835d428b1e89397e066 
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 "Lookup.h"
16#include "clang/AST/ASTConsumer.h"
17#include "clang/AST/ASTContext.h"
18#include "clang/AST/Expr.h"
19#include "clang/AST/DeclTemplate.h"
20#include "clang/Parse/DeclSpec.h"
21#include "clang/Basic/LangOptions.h"
22#include "llvm/Support/Compiler.h"
23
24using namespace clang;
25
26//===----------------------------------------------------------------------===/
27// Template Instantiation Support
28//===----------------------------------------------------------------------===/
29
30/// \brief Retrieve the template argument list(s) that should be used to
31/// instantiate the definition of the given declaration.
32///
33/// \param D the declaration for which we are computing template instantiation
34/// arguments.
35///
36/// \param Innermost if non-NULL, the innermost template argument list.
37MultiLevelTemplateArgumentList
38Sema::getTemplateInstantiationArgs(NamedDecl *D,
39                                   const TemplateArgumentList *Innermost) {
40  // Accumulate the set of template argument lists in this structure.
41  MultiLevelTemplateArgumentList Result;
42
43  if (Innermost)
44    Result.addOuterTemplateArguments(Innermost);
45
46  DeclContext *Ctx = dyn_cast<DeclContext>(D);
47  if (!Ctx)
48    Ctx = D->getDeclContext();
49
50  while (!Ctx->isFileContext()) {
51    // Add template arguments from a class template instantiation.
52    if (ClassTemplateSpecializationDecl *Spec
53          = dyn_cast<ClassTemplateSpecializationDecl>(Ctx)) {
54      // We're done when we hit an explicit specialization.
55      if (Spec->getSpecializationKind() == TSK_ExplicitSpecialization)
56        break;
57
58      Result.addOuterTemplateArguments(&Spec->getTemplateInstantiationArgs());
59
60      // If this class template specialization was instantiated from a
61      // specialized member that is a class template, we're done.
62      assert(Spec->getSpecializedTemplate() && "No class template?");
63      if (Spec->getSpecializedTemplate()->isMemberSpecialization())
64        break;
65    }
66    // Add template arguments from a function template specialization.
67    else if (FunctionDecl *Function = dyn_cast<FunctionDecl>(Ctx)) {
68      if (Function->getTemplateSpecializationKind()
69            == TSK_ExplicitSpecialization)
70        break;
71
72      if (const TemplateArgumentList *TemplateArgs
73            = Function->getTemplateSpecializationArgs()) {
74        // Add the template arguments for this specialization.
75        Result.addOuterTemplateArguments(TemplateArgs);
76
77        // If this function was instantiated from a specialized member that is
78        // a function template, we're done.
79        assert(Function->getPrimaryTemplate() && "No function template?");
80        if (Function->getPrimaryTemplate()->isMemberSpecialization())
81          break;
82      }
83
84      // If this is a friend declaration and it declares an entity at
85      // namespace scope, take arguments from its lexical parent
86      // instead of its semantic parent.
87      if (Function->getFriendObjectKind() &&
88          Function->getDeclContext()->isFileContext()) {
89        Ctx = Function->getLexicalDeclContext();
90        continue;
91      }
92    }
93
94    Ctx = Ctx->getParent();
95  }
96
97  return Result;
98}
99
100bool Sema::ActiveTemplateInstantiation::isInstantiationRecord() const {
101  switch (Kind) {
102  case TemplateInstantiation:
103  case DefaultTemplateArgumentInstantiation:
104  case DefaultFunctionArgumentInstantiation:
105    return true;
106
107  case ExplicitTemplateArgumentSubstitution:
108  case DeducedTemplateArgumentSubstitution:
109  case PriorTemplateArgumentSubstitution:
110  case DefaultTemplateArgumentChecking:
111    return false;
112  }
113
114  return true;
115}
116
117Sema::InstantiatingTemplate::
118InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
119                      Decl *Entity,
120                      SourceRange InstantiationRange)
121  :  SemaRef(SemaRef) {
122
123  Invalid = CheckInstantiationDepth(PointOfInstantiation,
124                                    InstantiationRange);
125  if (!Invalid) {
126    ActiveTemplateInstantiation Inst;
127    Inst.Kind = ActiveTemplateInstantiation::TemplateInstantiation;
128    Inst.PointOfInstantiation = PointOfInstantiation;
129    Inst.Entity = reinterpret_cast<uintptr_t>(Entity);
130    Inst.TemplateArgs = 0;
131    Inst.NumTemplateArgs = 0;
132    Inst.InstantiationRange = InstantiationRange;
133    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
134  }
135}
136
137Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
138                                         SourceLocation PointOfInstantiation,
139                                         TemplateDecl *Template,
140                                         const TemplateArgument *TemplateArgs,
141                                         unsigned NumTemplateArgs,
142                                         SourceRange InstantiationRange)
143  : SemaRef(SemaRef) {
144
145  Invalid = CheckInstantiationDepth(PointOfInstantiation,
146                                    InstantiationRange);
147  if (!Invalid) {
148    ActiveTemplateInstantiation Inst;
149    Inst.Kind
150      = ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation;
151    Inst.PointOfInstantiation = PointOfInstantiation;
152    Inst.Entity = reinterpret_cast<uintptr_t>(Template);
153    Inst.TemplateArgs = TemplateArgs;
154    Inst.NumTemplateArgs = NumTemplateArgs;
155    Inst.InstantiationRange = InstantiationRange;
156    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
157  }
158}
159
160Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
161                                         SourceLocation PointOfInstantiation,
162                                      FunctionTemplateDecl *FunctionTemplate,
163                                        const TemplateArgument *TemplateArgs,
164                                                   unsigned NumTemplateArgs,
165                         ActiveTemplateInstantiation::InstantiationKind Kind,
166                                              SourceRange InstantiationRange)
167: SemaRef(SemaRef) {
168
169  Invalid = CheckInstantiationDepth(PointOfInstantiation,
170                                    InstantiationRange);
171  if (!Invalid) {
172    ActiveTemplateInstantiation Inst;
173    Inst.Kind = Kind;
174    Inst.PointOfInstantiation = PointOfInstantiation;
175    Inst.Entity = reinterpret_cast<uintptr_t>(FunctionTemplate);
176    Inst.TemplateArgs = TemplateArgs;
177    Inst.NumTemplateArgs = NumTemplateArgs;
178    Inst.InstantiationRange = InstantiationRange;
179    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
180
181    if (!Inst.isInstantiationRecord())
182      ++SemaRef.NonInstantiationEntries;
183  }
184}
185
186Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
187                                         SourceLocation PointOfInstantiation,
188                          ClassTemplatePartialSpecializationDecl *PartialSpec,
189                                         const TemplateArgument *TemplateArgs,
190                                         unsigned NumTemplateArgs,
191                                         SourceRange InstantiationRange)
192  : SemaRef(SemaRef) {
193
194  Invalid = false;
195
196  ActiveTemplateInstantiation Inst;
197  Inst.Kind = ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution;
198  Inst.PointOfInstantiation = PointOfInstantiation;
199  Inst.Entity = reinterpret_cast<uintptr_t>(PartialSpec);
200  Inst.TemplateArgs = TemplateArgs;
201  Inst.NumTemplateArgs = NumTemplateArgs;
202  Inst.InstantiationRange = InstantiationRange;
203  SemaRef.ActiveTemplateInstantiations.push_back(Inst);
204
205  assert(!Inst.isInstantiationRecord());
206  ++SemaRef.NonInstantiationEntries;
207}
208
209Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
210                                          SourceLocation PointOfInstantiation,
211                                          ParmVarDecl *Param,
212                                          const TemplateArgument *TemplateArgs,
213                                          unsigned NumTemplateArgs,
214                                          SourceRange InstantiationRange)
215  : SemaRef(SemaRef) {
216
217  Invalid = CheckInstantiationDepth(PointOfInstantiation, InstantiationRange);
218
219  if (!Invalid) {
220    ActiveTemplateInstantiation Inst;
221    Inst.Kind
222      = ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation;
223    Inst.PointOfInstantiation = PointOfInstantiation;
224    Inst.Entity = reinterpret_cast<uintptr_t>(Param);
225    Inst.TemplateArgs = TemplateArgs;
226    Inst.NumTemplateArgs = NumTemplateArgs;
227    Inst.InstantiationRange = InstantiationRange;
228    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
229  }
230}
231
232Sema::InstantiatingTemplate::
233InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
234                      TemplateDecl *Template,
235                      NonTypeTemplateParmDecl *Param,
236                      const TemplateArgument *TemplateArgs,
237                      unsigned NumTemplateArgs,
238                      SourceRange InstantiationRange) : SemaRef(SemaRef) {
239  Invalid = false;
240
241  ActiveTemplateInstantiation Inst;
242  Inst.Kind = ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution;
243  Inst.PointOfInstantiation = PointOfInstantiation;
244  Inst.Template = Template;
245  Inst.Entity = reinterpret_cast<uintptr_t>(Param);
246  Inst.TemplateArgs = TemplateArgs;
247  Inst.NumTemplateArgs = NumTemplateArgs;
248  Inst.InstantiationRange = InstantiationRange;
249  SemaRef.ActiveTemplateInstantiations.push_back(Inst);
250
251  assert(!Inst.isInstantiationRecord());
252  ++SemaRef.NonInstantiationEntries;
253}
254
255Sema::InstantiatingTemplate::
256InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
257                      TemplateDecl *Template,
258                      TemplateTemplateParmDecl *Param,
259                      const TemplateArgument *TemplateArgs,
260                      unsigned NumTemplateArgs,
261                      SourceRange InstantiationRange) : SemaRef(SemaRef) {
262  Invalid = false;
263  ActiveTemplateInstantiation Inst;
264  Inst.Kind = ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution;
265  Inst.PointOfInstantiation = PointOfInstantiation;
266  Inst.Template = Template;
267  Inst.Entity = reinterpret_cast<uintptr_t>(Param);
268  Inst.TemplateArgs = TemplateArgs;
269  Inst.NumTemplateArgs = NumTemplateArgs;
270  Inst.InstantiationRange = InstantiationRange;
271  SemaRef.ActiveTemplateInstantiations.push_back(Inst);
272
273  assert(!Inst.isInstantiationRecord());
274  ++SemaRef.NonInstantiationEntries;
275}
276
277Sema::InstantiatingTemplate::
278InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
279                      TemplateDecl *Template,
280                      NamedDecl *Param,
281                      const TemplateArgument *TemplateArgs,
282                      unsigned NumTemplateArgs,
283                      SourceRange InstantiationRange) : SemaRef(SemaRef) {
284  Invalid = false;
285
286  ActiveTemplateInstantiation Inst;
287  Inst.Kind = ActiveTemplateInstantiation::DefaultTemplateArgumentChecking;
288  Inst.PointOfInstantiation = PointOfInstantiation;
289  Inst.Template = Template;
290  Inst.Entity = reinterpret_cast<uintptr_t>(Param);
291  Inst.TemplateArgs = TemplateArgs;
292  Inst.NumTemplateArgs = NumTemplateArgs;
293  Inst.InstantiationRange = InstantiationRange;
294  SemaRef.ActiveTemplateInstantiations.push_back(Inst);
295
296  assert(!Inst.isInstantiationRecord());
297  ++SemaRef.NonInstantiationEntries;
298}
299
300void Sema::InstantiatingTemplate::Clear() {
301  if (!Invalid) {
302    if (!SemaRef.ActiveTemplateInstantiations.back().isInstantiationRecord()) {
303      assert(SemaRef.NonInstantiationEntries > 0);
304      --SemaRef.NonInstantiationEntries;
305    }
306
307    SemaRef.ActiveTemplateInstantiations.pop_back();
308    Invalid = true;
309  }
310}
311
312bool Sema::InstantiatingTemplate::CheckInstantiationDepth(
313                                        SourceLocation PointOfInstantiation,
314                                           SourceRange InstantiationRange) {
315  assert(SemaRef.NonInstantiationEntries <=
316                                   SemaRef.ActiveTemplateInstantiations.size());
317  if ((SemaRef.ActiveTemplateInstantiations.size() -
318          SemaRef.NonInstantiationEntries)
319        <= SemaRef.getLangOptions().InstantiationDepth)
320    return false;
321
322  SemaRef.Diag(PointOfInstantiation,
323               diag::err_template_recursion_depth_exceeded)
324    << SemaRef.getLangOptions().InstantiationDepth
325    << InstantiationRange;
326  SemaRef.Diag(PointOfInstantiation, diag::note_template_recursion_depth)
327    << SemaRef.getLangOptions().InstantiationDepth;
328  return true;
329}
330
331/// \brief Prints the current instantiation stack through a series of
332/// notes.
333void Sema::PrintInstantiationStack() {
334  // FIXME: In all of these cases, we need to show the template arguments
335  for (llvm::SmallVector<ActiveTemplateInstantiation, 16>::reverse_iterator
336         Active = ActiveTemplateInstantiations.rbegin(),
337         ActiveEnd = ActiveTemplateInstantiations.rend();
338       Active != ActiveEnd;
339       ++Active) {
340    switch (Active->Kind) {
341    case ActiveTemplateInstantiation::TemplateInstantiation: {
342      Decl *D = reinterpret_cast<Decl *>(Active->Entity);
343      if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(D)) {
344        unsigned DiagID = diag::note_template_member_class_here;
345        if (isa<ClassTemplateSpecializationDecl>(Record))
346          DiagID = diag::note_template_class_instantiation_here;
347        Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
348                     DiagID)
349          << Context.getTypeDeclType(Record)
350          << Active->InstantiationRange;
351      } else if (FunctionDecl *Function = dyn_cast<FunctionDecl>(D)) {
352        unsigned DiagID;
353        if (Function->getPrimaryTemplate())
354          DiagID = diag::note_function_template_spec_here;
355        else
356          DiagID = diag::note_template_member_function_here;
357        Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
358                     DiagID)
359          << Function
360          << Active->InstantiationRange;
361      } else {
362        Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
363                     diag::note_template_static_data_member_def_here)
364          << cast<VarDecl>(D)
365          << Active->InstantiationRange;
366      }
367      break;
368    }
369
370    case ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation: {
371      TemplateDecl *Template = cast<TemplateDecl>((Decl *)Active->Entity);
372      std::string TemplateArgsStr
373        = TemplateSpecializationType::PrintTemplateArgumentList(
374                                                         Active->TemplateArgs,
375                                                      Active->NumTemplateArgs,
376                                                      Context.PrintingPolicy);
377      Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
378                   diag::note_default_arg_instantiation_here)
379        << (Template->getNameAsString() + TemplateArgsStr)
380        << Active->InstantiationRange;
381      break;
382    }
383
384    case ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution: {
385      FunctionTemplateDecl *FnTmpl
386        = cast<FunctionTemplateDecl>((Decl *)Active->Entity);
387      Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
388                   diag::note_explicit_template_arg_substitution_here)
389        << FnTmpl << Active->InstantiationRange;
390      break;
391    }
392
393    case ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution:
394      if (ClassTemplatePartialSpecializationDecl *PartialSpec
395            = dyn_cast<ClassTemplatePartialSpecializationDecl>(
396                                                    (Decl *)Active->Entity)) {
397        Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
398                     diag::note_partial_spec_deduct_instantiation_here)
399          << Context.getTypeDeclType(PartialSpec)
400          << Active->InstantiationRange;
401      } else {
402        FunctionTemplateDecl *FnTmpl
403          = cast<FunctionTemplateDecl>((Decl *)Active->Entity);
404        Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
405                     diag::note_function_template_deduction_instantiation_here)
406          << FnTmpl << Active->InstantiationRange;
407      }
408      break;
409
410    case ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation: {
411      ParmVarDecl *Param = cast<ParmVarDecl>((Decl *)Active->Entity);
412      FunctionDecl *FD = cast<FunctionDecl>(Param->getDeclContext());
413
414      std::string TemplateArgsStr
415        = TemplateSpecializationType::PrintTemplateArgumentList(
416                                                         Active->TemplateArgs,
417                                                      Active->NumTemplateArgs,
418                                                      Context.PrintingPolicy);
419      Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
420                   diag::note_default_function_arg_instantiation_here)
421        << (FD->getNameAsString() + TemplateArgsStr)
422        << Active->InstantiationRange;
423      break;
424    }
425
426    case ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution: {
427      NamedDecl *Parm = cast<NamedDecl>((Decl *)Active->Entity);
428      std::string Name;
429      if (!Parm->getName().empty())
430        Name = std::string(" '") + Parm->getName().str() + "'";
431
432      Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
433                   diag::note_prior_template_arg_substitution)
434        << isa<TemplateTemplateParmDecl>(Parm)
435        << Name
436        << getTemplateArgumentBindingsText(
437                                    Active->Template->getTemplateParameters(),
438                                           Active->TemplateArgs,
439                                           Active->NumTemplateArgs)
440        << Active->InstantiationRange;
441      break;
442    }
443
444    case ActiveTemplateInstantiation::DefaultTemplateArgumentChecking: {
445      Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
446                   diag::note_template_default_arg_checking)
447        << getTemplateArgumentBindingsText(
448                                     Active->Template->getTemplateParameters(),
449                                           Active->TemplateArgs,
450                                           Active->NumTemplateArgs)
451        << Active->InstantiationRange;
452      break;
453    }
454    }
455  }
456}
457
458bool Sema::isSFINAEContext() const {
459  using llvm::SmallVector;
460  for (SmallVector<ActiveTemplateInstantiation, 16>::const_reverse_iterator
461         Active = ActiveTemplateInstantiations.rbegin(),
462         ActiveEnd = ActiveTemplateInstantiations.rend();
463       Active != ActiveEnd;
464       ++Active)
465  {
466    switch(Active->Kind) {
467    case ActiveTemplateInstantiation::TemplateInstantiation:
468    case ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation:
469      // This is a template instantiation, so there is no SFINAE.
470      return false;
471
472    case ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation:
473    case ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution:
474    case ActiveTemplateInstantiation::DefaultTemplateArgumentChecking:
475      // A default template argument instantiation and substitution into
476      // template parameters with arguments for prior parameters may or may
477      // not be a SFINAE context; look further up the stack.
478      break;
479
480    case ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution:
481    case ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution:
482      // We're either substitution explicitly-specified template arguments
483      // or deduced template arguments, so SFINAE applies.
484      return true;
485    }
486  }
487
488  return false;
489}
490
491//===----------------------------------------------------------------------===/
492// Template Instantiation for Types
493//===----------------------------------------------------------------------===/
494namespace {
495  class VISIBILITY_HIDDEN TemplateInstantiator
496    : public TreeTransform<TemplateInstantiator> {
497    const MultiLevelTemplateArgumentList &TemplateArgs;
498    SourceLocation Loc;
499    DeclarationName Entity;
500
501  public:
502    typedef TreeTransform<TemplateInstantiator> inherited;
503
504    TemplateInstantiator(Sema &SemaRef,
505                         const MultiLevelTemplateArgumentList &TemplateArgs,
506                         SourceLocation Loc,
507                         DeclarationName Entity)
508      : inherited(SemaRef), TemplateArgs(TemplateArgs), Loc(Loc),
509        Entity(Entity) { }
510
511    /// \brief Determine whether the given type \p T has already been
512    /// transformed.
513    ///
514    /// For the purposes of template instantiation, a type has already been
515    /// transformed if it is NULL or if it is not dependent.
516    bool AlreadyTransformed(QualType T) {
517      return T.isNull() || !T->isDependentType();
518    }
519
520    /// \brief Returns the location of the entity being instantiated, if known.
521    SourceLocation getBaseLocation() { return Loc; }
522
523    /// \brief Returns the name of the entity being instantiated, if any.
524    DeclarationName getBaseEntity() { return Entity; }
525
526    /// \brief Sets the "base" location and entity when that
527    /// information is known based on another transformation.
528    void setBase(SourceLocation Loc, DeclarationName Entity) {
529      this->Loc = Loc;
530      this->Entity = Entity;
531    }
532
533    /// \brief Transform the given declaration by instantiating a reference to
534    /// this declaration.
535    Decl *TransformDecl(Decl *D);
536
537    /// \brief Transform the definition of the given declaration by
538    /// instantiating it.
539    Decl *TransformDefinition(Decl *D);
540
541    /// \bried Transform the first qualifier within a scope by instantiating the
542    /// declaration.
543    NamedDecl *TransformFirstQualifierInScope(NamedDecl *D, SourceLocation Loc);
544
545    /// \brief Rebuild the exception declaration and register the declaration
546    /// as an instantiated local.
547    VarDecl *RebuildExceptionDecl(VarDecl *ExceptionDecl, QualType T,
548                                  DeclaratorInfo *Declarator,
549                                  IdentifierInfo *Name,
550                                  SourceLocation Loc, SourceRange TypeRange);
551
552    /// \brief Check for tag mismatches when instantiating an
553    /// elaborated type.
554    QualType RebuildElaboratedType(QualType T, ElaboratedType::TagKind Tag);
555
556    Sema::OwningExprResult TransformPredefinedExpr(PredefinedExpr *E,
557                                                   bool isAddressOfOperand);
558    Sema::OwningExprResult TransformDeclRefExpr(DeclRefExpr *E,
559                                                bool isAddressOfOperand);
560    Sema::OwningExprResult TransformUnresolvedLookupExpr(
561                                                UnresolvedLookupExpr *E,
562                                                bool isAddressOfOperand);
563
564    Sema::OwningExprResult TransformCXXDefaultArgExpr(CXXDefaultArgExpr *E,
565                                                      bool isAddressOfOperand);
566
567    /// \brief Transforms a template type parameter type by performing
568    /// substitution of the corresponding template type argument.
569    QualType TransformTemplateTypeParmType(TypeLocBuilder &TLB,
570                                           TemplateTypeParmTypeLoc TL);
571  };
572}
573
574Decl *TemplateInstantiator::TransformDecl(Decl *D) {
575  if (!D)
576    return 0;
577
578  if (TemplateTemplateParmDecl *TTP = dyn_cast<TemplateTemplateParmDecl>(D)) {
579    if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
580      TemplateName Template
581        = TemplateArgs(TTP->getDepth(), TTP->getPosition()).getAsTemplate();
582      assert(!Template.isNull() && Template.getAsTemplateDecl() &&
583             "Wrong kind of template template argument");
584      return Template.getAsTemplateDecl();
585    }
586
587    // If the corresponding template argument is NULL or non-existent, it's
588    // because we are performing instantiation from explicitly-specified
589    // template arguments in a function template, but there were some
590    // arguments left unspecified.
591    if (!TemplateArgs.hasTemplateArgument(TTP->getDepth(),
592                                          TTP->getPosition()))
593      return D;
594
595    // Fall through to find the instantiated declaration for this template
596    // template parameter.
597  }
598
599  return SemaRef.FindInstantiatedDecl(cast<NamedDecl>(D), TemplateArgs);
600}
601
602Decl *TemplateInstantiator::TransformDefinition(Decl *D) {
603  Decl *Inst = getSema().SubstDecl(D, getSema().CurContext, TemplateArgs);
604  if (!Inst)
605    return 0;
606
607  getSema().CurrentInstantiationScope->InstantiatedLocal(D, Inst);
608  return Inst;
609}
610
611NamedDecl *
612TemplateInstantiator::TransformFirstQualifierInScope(NamedDecl *D,
613                                                     SourceLocation Loc) {
614  // If the first part of the nested-name-specifier was a template type
615  // parameter, instantiate that type parameter down to a tag type.
616  if (TemplateTypeParmDecl *TTPD = dyn_cast_or_null<TemplateTypeParmDecl>(D)) {
617    const TemplateTypeParmType *TTP
618      = cast<TemplateTypeParmType>(getSema().Context.getTypeDeclType(TTPD));
619    if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
620      QualType T = TemplateArgs(TTP->getDepth(), TTP->getIndex()).getAsType();
621      if (T.isNull())
622        return cast_or_null<NamedDecl>(TransformDecl(D));
623
624      if (const TagType *Tag = T->getAs<TagType>())
625        return Tag->getDecl();
626
627      // The resulting type is not a tag; complain.
628      getSema().Diag(Loc, diag::err_nested_name_spec_non_tag) << T;
629      return 0;
630    }
631  }
632
633  return cast_or_null<NamedDecl>(TransformDecl(D));
634}
635
636VarDecl *
637TemplateInstantiator::RebuildExceptionDecl(VarDecl *ExceptionDecl,
638                                           QualType T,
639                                           DeclaratorInfo *Declarator,
640                                           IdentifierInfo *Name,
641                                           SourceLocation Loc,
642                                           SourceRange TypeRange) {
643  VarDecl *Var = inherited::RebuildExceptionDecl(ExceptionDecl, T, Declarator,
644                                                 Name, Loc, TypeRange);
645  if (Var && !Var->isInvalidDecl())
646    getSema().CurrentInstantiationScope->InstantiatedLocal(ExceptionDecl, Var);
647  return Var;
648}
649
650QualType
651TemplateInstantiator::RebuildElaboratedType(QualType T,
652                                            ElaboratedType::TagKind Tag) {
653  if (const TagType *TT = T->getAs<TagType>()) {
654    TagDecl* TD = TT->getDecl();
655
656    // FIXME: this location is very wrong;  we really need typelocs.
657    SourceLocation TagLocation = TD->getTagKeywordLoc();
658
659    // FIXME: type might be anonymous.
660    IdentifierInfo *Id = TD->getIdentifier();
661
662    // TODO: should we even warn on struct/class mismatches for this?  Seems
663    // like it's likely to produce a lot of spurious errors.
664    if (!SemaRef.isAcceptableTagRedeclaration(TD, Tag, TagLocation, *Id)) {
665      SemaRef.Diag(TagLocation, diag::err_use_with_wrong_tag)
666        << Id
667        << CodeModificationHint::CreateReplacement(SourceRange(TagLocation),
668                                                   TD->getKindName());
669      SemaRef.Diag(TD->getLocation(), diag::note_previous_use);
670    }
671  }
672
673  return TreeTransform<TemplateInstantiator>::RebuildElaboratedType(T, Tag);
674}
675
676Sema::OwningExprResult
677TemplateInstantiator::TransformPredefinedExpr(PredefinedExpr *E,
678                                              bool isAddressOfOperand) {
679  if (!E->isTypeDependent())
680    return SemaRef.Owned(E->Retain());
681
682  FunctionDecl *currentDecl = getSema().getCurFunctionDecl();
683  assert(currentDecl && "Must have current function declaration when "
684                        "instantiating.");
685
686  PredefinedExpr::IdentType IT = E->getIdentType();
687
688  unsigned Length =
689    PredefinedExpr::ComputeName(getSema().Context, IT, currentDecl).length();
690
691  llvm::APInt LengthI(32, Length + 1);
692  QualType ResTy = getSema().Context.CharTy.withConst();
693  ResTy = getSema().Context.getConstantArrayType(ResTy, LengthI,
694                                                 ArrayType::Normal, 0);
695  PredefinedExpr *PE =
696    new (getSema().Context) PredefinedExpr(E->getLocation(), ResTy, IT);
697  return getSema().Owned(PE);
698}
699
700Sema::OwningExprResult
701TemplateInstantiator::TransformUnresolvedLookupExpr(UnresolvedLookupExpr *Old,
702                                                    bool isAddressOfOperand) {
703  LookupResult R(SemaRef, Old->getName(), Old->getNameLoc(),
704                 Sema::LookupOrdinaryName);
705
706  for (UnresolvedLookupExpr::decls_iterator I = Old->decls_begin(),
707         E = Old->decls_end(); I != E; ++I) {
708    NamedDecl *InstD = SemaRef.FindInstantiatedDecl(*I, TemplateArgs);
709    if (!InstD)
710      return SemaRef.ExprError();
711
712    // The lookup values can never instantiate to a UsingDecl, because
713    // only UnresolvedUsingValueDecls do that, and those can never
714    // appear in UnresolvedLookupExprs (only UnresolvedMemberLookupExprs).
715    assert(!isa<UsingDecl>(InstD));
716
717    // Analogously.
718    assert(!isa<UnresolvedUsingValueDecl>(InstD->getUnderlyingDecl()));
719
720    R.addDecl(InstD);
721  }
722
723  R.resolveKind();
724
725  // This shouldn't be possible.
726  assert(!R.isAmbiguous());
727
728  CXXScopeSpec SS;
729  NestedNameSpecifier *Qualifier = 0;
730  if (Old->getQualifier()) {
731    Qualifier = TransformNestedNameSpecifier(Old->getQualifier(),
732                                             Old->getQualifierRange());
733    if (!Qualifier)
734      return SemaRef.ExprError();
735
736    SS.setScopeRep(Qualifier);
737    SS.setRange(Old->getQualifierRange());
738  }
739
740  return SemaRef.BuildDeclarationNameExpr(&SS, R, Old->requiresADL());
741}
742
743Sema::OwningExprResult
744TemplateInstantiator::TransformDeclRefExpr(DeclRefExpr *E,
745                                           bool isAddressOfOperand) {
746  // FIXME: Clean this up a bit
747  NamedDecl *D = E->getDecl();
748  if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D)) {
749    if (NTTP->getDepth() < TemplateArgs.getNumLevels()) {
750      // If the corresponding template argument is NULL or non-existent, it's
751      // because we are performing instantiation from explicitly-specified
752      // template arguments in a function template, but there were some
753      // arguments left unspecified.
754      if (!TemplateArgs.hasTemplateArgument(NTTP->getDepth(),
755                                            NTTP->getPosition()))
756        return SemaRef.Owned(E->Retain());
757
758      const TemplateArgument &Arg = TemplateArgs(NTTP->getDepth(),
759                                                 NTTP->getPosition());
760
761      // The template argument itself might be an expression, in which
762      // case we just return that expression.
763      if (Arg.getKind() == TemplateArgument::Expression)
764        return SemaRef.Owned(Arg.getAsExpr()->Retain());
765
766      if (Arg.getKind() == TemplateArgument::Declaration) {
767        ValueDecl *VD = cast<ValueDecl>(Arg.getAsDecl());
768
769        VD = cast_or_null<ValueDecl>(
770                              getSema().FindInstantiatedDecl(VD, TemplateArgs));
771        if (!VD)
772          return SemaRef.ExprError();
773
774        if (VD->getDeclContext()->isRecord()) {
775          // If the value is a class member, we might have a pointer-to-member.
776          // Determine whether the non-type template template parameter is of
777          // pointer-to-member type. If so, we need to build an appropriate
778          // expression for a pointer-to-member, since a "normal" DeclRefExpr
779          // would refer to the member itself.
780          if (NTTP->getType()->isMemberPointerType()) {
781            QualType ClassType
782              = SemaRef.Context.getTypeDeclType(
783                                        cast<RecordDecl>(VD->getDeclContext()));
784            NestedNameSpecifier *Qualifier
785              = NestedNameSpecifier::Create(SemaRef.Context, 0, false,
786                                            ClassType.getTypePtr());
787            CXXScopeSpec SS;
788            SS.setScopeRep(Qualifier);
789            OwningExprResult RefExpr
790              = SemaRef.BuildDeclRefExpr(VD,
791                                         VD->getType().getNonReferenceType(),
792                                         E->getLocation(),
793                                         /*FIXME:*/false, /*FIXME:*/false,
794                                         &SS);
795            if (RefExpr.isInvalid())
796              return SemaRef.ExprError();
797
798            return SemaRef.CreateBuiltinUnaryOp(E->getLocation(),
799                                                UnaryOperator::AddrOf,
800                                                move(RefExpr));
801          }
802        }
803
804        return SemaRef.BuildDeclRefExpr(VD, VD->getType().getNonReferenceType(),
805                                        E->getLocation(),
806                                        /*FIXME:*/false, /*FIXME:*/false);
807      }
808
809      assert(Arg.getKind() == TemplateArgument::Integral);
810      QualType T = Arg.getIntegralType();
811      if (T->isCharType() || T->isWideCharType())
812        return SemaRef.Owned(new (SemaRef.Context) CharacterLiteral(
813                                              Arg.getAsIntegral()->getZExtValue(),
814                                              T->isWideCharType(),
815                                              T,
816                                              E->getSourceRange().getBegin()));
817      if (T->isBooleanType())
818        return SemaRef.Owned(new (SemaRef.Context) CXXBoolLiteralExpr(
819                                            Arg.getAsIntegral()->getBoolValue(),
820                                            T,
821                                            E->getSourceRange().getBegin()));
822
823      assert(Arg.getAsIntegral()->getBitWidth() == SemaRef.Context.getIntWidth(T));
824      return SemaRef.Owned(new (SemaRef.Context) IntegerLiteral(
825                                                *Arg.getAsIntegral(),
826                                                T,
827                                                E->getSourceRange().getBegin()));
828    }
829
830    // We have a non-type template parameter that isn't fully substituted;
831    // FindInstantiatedDecl will find it in the local instantiation scope.
832  }
833
834  NamedDecl *InstD = SemaRef.FindInstantiatedDecl(D, TemplateArgs);
835  if (!InstD)
836    return SemaRef.ExprError();
837
838  assert(!isa<UsingDecl>(InstD) && "decl ref instantiated to UsingDecl");
839
840  CXXScopeSpec SS;
841  NestedNameSpecifier *Qualifier = 0;
842  if (E->getQualifier()) {
843    Qualifier = TransformNestedNameSpecifier(E->getQualifier(),
844                                             E->getQualifierRange());
845    if (!Qualifier)
846      return SemaRef.ExprError();
847
848    SS.setScopeRep(Qualifier);
849    SS.setRange(E->getQualifierRange());
850  }
851
852  return SemaRef.BuildDeclarationNameExpr(&SS, E->getLocation(), InstD);
853}
854
855Sema::OwningExprResult TemplateInstantiator::TransformCXXDefaultArgExpr(
856    CXXDefaultArgExpr *E, bool isAddressOfOperand) {
857  assert(!cast<FunctionDecl>(E->getParam()->getDeclContext())->
858             getDescribedFunctionTemplate() &&
859         "Default arg expressions are never formed in dependent cases.");
860  return SemaRef.Owned(E->Retain());
861}
862
863
864QualType
865TemplateInstantiator::TransformTemplateTypeParmType(TypeLocBuilder &TLB,
866                                                TemplateTypeParmTypeLoc TL) {
867  TemplateTypeParmType *T = TL.getTypePtr();
868  if (T->getDepth() < TemplateArgs.getNumLevels()) {
869    // Replace the template type parameter with its corresponding
870    // template argument.
871
872    // If the corresponding template argument is NULL or doesn't exist, it's
873    // because we are performing instantiation from explicitly-specified
874    // template arguments in a function template class, but there were some
875    // arguments left unspecified.
876    if (!TemplateArgs.hasTemplateArgument(T->getDepth(), T->getIndex())) {
877      TemplateTypeParmTypeLoc NewTL
878        = TLB.push<TemplateTypeParmTypeLoc>(TL.getType());
879      NewTL.setNameLoc(TL.getNameLoc());
880      return TL.getType();
881    }
882
883    assert(TemplateArgs(T->getDepth(), T->getIndex()).getKind()
884             == TemplateArgument::Type &&
885           "Template argument kind mismatch");
886
887    QualType Replacement
888      = TemplateArgs(T->getDepth(), T->getIndex()).getAsType();
889
890    // TODO: only do this uniquing once, at the start of instantiation.
891    QualType Result
892      = getSema().Context.getSubstTemplateTypeParmType(T, Replacement);
893    SubstTemplateTypeParmTypeLoc NewTL
894      = TLB.push<SubstTemplateTypeParmTypeLoc>(Result);
895    NewTL.setNameLoc(TL.getNameLoc());
896    return Result;
897  }
898
899  // The template type parameter comes from an inner template (e.g.,
900  // the template parameter list of a member template inside the
901  // template we are instantiating). Create a new template type
902  // parameter with the template "level" reduced by one.
903  QualType Result
904    = getSema().Context.getTemplateTypeParmType(T->getDepth()
905                                                 - TemplateArgs.getNumLevels(),
906                                                T->getIndex(),
907                                                T->isParameterPack(),
908                                                T->getName());
909  TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result);
910  NewTL.setNameLoc(TL.getNameLoc());
911  return Result;
912}
913
914/// \brief Perform substitution on the type T with a given set of template
915/// arguments.
916///
917/// This routine substitutes the given template arguments into the
918/// type T and produces the instantiated type.
919///
920/// \param T the type into which the template arguments will be
921/// substituted. If this type is not dependent, it will be returned
922/// immediately.
923///
924/// \param TemplateArgs the template arguments that will be
925/// substituted for the top-level template parameters within T.
926///
927/// \param Loc the location in the source code where this substitution
928/// is being performed. It will typically be the location of the
929/// declarator (if we're instantiating the type of some declaration)
930/// or the location of the type in the source code (if, e.g., we're
931/// instantiating the type of a cast expression).
932///
933/// \param Entity the name of the entity associated with a declaration
934/// being instantiated (if any). May be empty to indicate that there
935/// is no such entity (if, e.g., this is a type that occurs as part of
936/// a cast expression) or that the entity has no name (e.g., an
937/// unnamed function parameter).
938///
939/// \returns If the instantiation succeeds, the instantiated
940/// type. Otherwise, produces diagnostics and returns a NULL type.
941DeclaratorInfo *Sema::SubstType(DeclaratorInfo *T,
942                                const MultiLevelTemplateArgumentList &Args,
943                                SourceLocation Loc,
944                                DeclarationName Entity) {
945  assert(!ActiveTemplateInstantiations.empty() &&
946         "Cannot perform an instantiation without some context on the "
947         "instantiation stack");
948
949  if (!T->getType()->isDependentType())
950    return T;
951
952  TemplateInstantiator Instantiator(*this, Args, Loc, Entity);
953  return Instantiator.TransformType(T);
954}
955
956/// Deprecated form of the above.
957QualType Sema::SubstType(QualType T,
958                         const MultiLevelTemplateArgumentList &TemplateArgs,
959                         SourceLocation Loc, DeclarationName Entity) {
960  assert(!ActiveTemplateInstantiations.empty() &&
961         "Cannot perform an instantiation without some context on the "
962         "instantiation stack");
963
964  // If T is not a dependent type, there is nothing to do.
965  if (!T->isDependentType())
966    return T;
967
968  TemplateInstantiator Instantiator(*this, TemplateArgs, Loc, Entity);
969  return Instantiator.TransformType(T);
970}
971
972/// \brief Perform substitution on the base class specifiers of the
973/// given class template specialization.
974///
975/// Produces a diagnostic and returns true on error, returns false and
976/// attaches the instantiated base classes to the class template
977/// specialization if successful.
978bool
979Sema::SubstBaseSpecifiers(CXXRecordDecl *Instantiation,
980                          CXXRecordDecl *Pattern,
981                          const MultiLevelTemplateArgumentList &TemplateArgs) {
982  bool Invalid = false;
983  llvm::SmallVector<CXXBaseSpecifier*, 4> InstantiatedBases;
984  for (ClassTemplateSpecializationDecl::base_class_iterator
985         Base = Pattern->bases_begin(), BaseEnd = Pattern->bases_end();
986       Base != BaseEnd; ++Base) {
987    if (!Base->getType()->isDependentType()) {
988      InstantiatedBases.push_back(new (Context) CXXBaseSpecifier(*Base));
989      continue;
990    }
991
992    QualType BaseType = SubstType(Base->getType(),
993                                  TemplateArgs,
994                                  Base->getSourceRange().getBegin(),
995                                  DeclarationName());
996    if (BaseType.isNull()) {
997      Invalid = true;
998      continue;
999    }
1000
1001    if (CXXBaseSpecifier *InstantiatedBase
1002          = CheckBaseSpecifier(Instantiation,
1003                               Base->getSourceRange(),
1004                               Base->isVirtual(),
1005                               Base->getAccessSpecifierAsWritten(),
1006                               BaseType,
1007                               /*FIXME: Not totally accurate */
1008                               Base->getSourceRange().getBegin()))
1009      InstantiatedBases.push_back(InstantiatedBase);
1010    else
1011      Invalid = true;
1012  }
1013
1014  if (!Invalid &&
1015      AttachBaseSpecifiers(Instantiation, InstantiatedBases.data(),
1016                           InstantiatedBases.size()))
1017    Invalid = true;
1018
1019  return Invalid;
1020}
1021
1022/// \brief Instantiate the definition of a class from a given pattern.
1023///
1024/// \param PointOfInstantiation The point of instantiation within the
1025/// source code.
1026///
1027/// \param Instantiation is the declaration whose definition is being
1028/// instantiated. This will be either a class template specialization
1029/// or a member class of a class template specialization.
1030///
1031/// \param Pattern is the pattern from which the instantiation
1032/// occurs. This will be either the declaration of a class template or
1033/// the declaration of a member class of a class template.
1034///
1035/// \param TemplateArgs The template arguments to be substituted into
1036/// the pattern.
1037///
1038/// \param TSK the kind of implicit or explicit instantiation to perform.
1039///
1040/// \param Complain whether to complain if the class cannot be instantiated due
1041/// to the lack of a definition.
1042///
1043/// \returns true if an error occurred, false otherwise.
1044bool
1045Sema::InstantiateClass(SourceLocation PointOfInstantiation,
1046                       CXXRecordDecl *Instantiation, CXXRecordDecl *Pattern,
1047                       const MultiLevelTemplateArgumentList &TemplateArgs,
1048                       TemplateSpecializationKind TSK,
1049                       bool Complain) {
1050  bool Invalid = false;
1051
1052  CXXRecordDecl *PatternDef
1053    = cast_or_null<CXXRecordDecl>(Pattern->getDefinition(Context));
1054  if (!PatternDef) {
1055    if (!Complain) {
1056      // Say nothing
1057    } else if (Pattern == Instantiation->getInstantiatedFromMemberClass()) {
1058      Diag(PointOfInstantiation,
1059           diag::err_implicit_instantiate_member_undefined)
1060        << Context.getTypeDeclType(Instantiation);
1061      Diag(Pattern->getLocation(), diag::note_member_of_template_here);
1062    } else {
1063      Diag(PointOfInstantiation, diag::err_template_instantiate_undefined)
1064        << (TSK != TSK_ImplicitInstantiation)
1065        << Context.getTypeDeclType(Instantiation);
1066      Diag(Pattern->getLocation(), diag::note_template_decl_here);
1067    }
1068    return true;
1069  }
1070  Pattern = PatternDef;
1071
1072  // \brief Record the point of instantiation.
1073  if (MemberSpecializationInfo *MSInfo
1074        = Instantiation->getMemberSpecializationInfo()) {
1075    MSInfo->setTemplateSpecializationKind(TSK);
1076    MSInfo->setPointOfInstantiation(PointOfInstantiation);
1077  } else if (ClassTemplateSpecializationDecl *Spec
1078               = dyn_cast<ClassTemplateSpecializationDecl>(Instantiation)) {
1079    Spec->setTemplateSpecializationKind(TSK);
1080    Spec->setPointOfInstantiation(PointOfInstantiation);
1081  }
1082
1083  InstantiatingTemplate Inst(*this, PointOfInstantiation, Instantiation);
1084  if (Inst)
1085    return true;
1086
1087  // Enter the scope of this instantiation. We don't use
1088  // PushDeclContext because we don't have a scope.
1089  DeclContext *PreviousContext = CurContext;
1090  CurContext = Instantiation;
1091
1092  // Start the definition of this instantiation.
1093  Instantiation->startDefinition();
1094
1095  // Do substitution on the base class specifiers.
1096  if (SubstBaseSpecifiers(Instantiation, Pattern, TemplateArgs))
1097    Invalid = true;
1098
1099  llvm::SmallVector<DeclPtrTy, 4> Fields;
1100  for (RecordDecl::decl_iterator Member = Pattern->decls_begin(),
1101         MemberEnd = Pattern->decls_end();
1102       Member != MemberEnd; ++Member) {
1103    Decl *NewMember = SubstDecl(*Member, Instantiation, TemplateArgs);
1104    if (NewMember) {
1105      if (NewMember->isInvalidDecl()) {
1106        Invalid = true;
1107      } else if (FieldDecl *Field = dyn_cast<FieldDecl>(NewMember))
1108        Fields.push_back(DeclPtrTy::make(Field));
1109      else if (UsingDecl *UD = dyn_cast<UsingDecl>(NewMember))
1110        Instantiation->addDecl(UD);
1111    } else {
1112      // FIXME: Eventually, a NULL return will mean that one of the
1113      // instantiations was a semantic disaster, and we'll want to set Invalid =
1114      // true. For now, we expect to skip some members that we can't yet handle.
1115    }
1116  }
1117
1118  // Finish checking fields.
1119  ActOnFields(0, Instantiation->getLocation(), DeclPtrTy::make(Instantiation),
1120              Fields.data(), Fields.size(), SourceLocation(), SourceLocation(),
1121              0);
1122  if (Instantiation->isInvalidDecl())
1123    Invalid = true;
1124
1125  // Add any implicitly-declared members that we might need.
1126  if (!Invalid)
1127    AddImplicitlyDeclaredMembersToClass(Instantiation);
1128
1129  // Exit the scope of this instantiation.
1130  CurContext = PreviousContext;
1131
1132  if (!Invalid)
1133    Consumer.HandleTagDeclDefinition(Instantiation);
1134
1135  return Invalid;
1136}
1137
1138bool
1139Sema::InstantiateClassTemplateSpecialization(
1140                           SourceLocation PointOfInstantiation,
1141                           ClassTemplateSpecializationDecl *ClassTemplateSpec,
1142                           TemplateSpecializationKind TSK,
1143                           bool Complain) {
1144  // Perform the actual instantiation on the canonical declaration.
1145  ClassTemplateSpec = cast<ClassTemplateSpecializationDecl>(
1146                                         ClassTemplateSpec->getCanonicalDecl());
1147
1148  // Check whether we have already instantiated or specialized this class
1149  // template specialization.
1150  if (ClassTemplateSpec->getSpecializationKind() != TSK_Undeclared) {
1151    if (ClassTemplateSpec->getSpecializationKind() ==
1152          TSK_ExplicitInstantiationDeclaration &&
1153        TSK == TSK_ExplicitInstantiationDefinition) {
1154      // An explicit instantiation definition follows an explicit instantiation
1155      // declaration (C++0x [temp.explicit]p10); go ahead and perform the
1156      // explicit instantiation.
1157      ClassTemplateSpec->setSpecializationKind(TSK);
1158      return false;
1159    }
1160
1161    // We can only instantiate something that hasn't already been
1162    // instantiated or specialized. Fail without any diagnostics: our
1163    // caller will provide an error message.
1164    return true;
1165  }
1166
1167  if (ClassTemplateSpec->isInvalidDecl())
1168    return true;
1169
1170  ClassTemplateDecl *Template = ClassTemplateSpec->getSpecializedTemplate();
1171  CXXRecordDecl *Pattern = 0;
1172
1173  // C++ [temp.class.spec.match]p1:
1174  //   When a class template is used in a context that requires an
1175  //   instantiation of the class, it is necessary to determine
1176  //   whether the instantiation is to be generated using the primary
1177  //   template or one of the partial specializations. This is done by
1178  //   matching the template arguments of the class template
1179  //   specialization with the template argument lists of the partial
1180  //   specializations.
1181  typedef std::pair<ClassTemplatePartialSpecializationDecl *,
1182                    TemplateArgumentList *> MatchResult;
1183  llvm::SmallVector<MatchResult, 4> Matched;
1184  for (llvm::FoldingSet<ClassTemplatePartialSpecializationDecl>::iterator
1185         Partial = Template->getPartialSpecializations().begin(),
1186         PartialEnd = Template->getPartialSpecializations().end();
1187       Partial != PartialEnd;
1188       ++Partial) {
1189    TemplateDeductionInfo Info(Context);
1190    if (TemplateDeductionResult Result
1191          = DeduceTemplateArguments(&*Partial,
1192                                    ClassTemplateSpec->getTemplateArgs(),
1193                                    Info)) {
1194      // FIXME: Store the failed-deduction information for use in
1195      // diagnostics, later.
1196      (void)Result;
1197    } else {
1198      Matched.push_back(std::make_pair(&*Partial, Info.take()));
1199    }
1200  }
1201
1202  if (Matched.size() >= 1) {
1203    llvm::SmallVector<MatchResult, 4>::iterator Best = Matched.begin();
1204    if (Matched.size() == 1) {
1205      //   -- If exactly one matching specialization is found, the
1206      //      instantiation is generated from that specialization.
1207      // We don't need to do anything for this.
1208    } else {
1209      //   -- If more than one matching specialization is found, the
1210      //      partial order rules (14.5.4.2) are used to determine
1211      //      whether one of the specializations is more specialized
1212      //      than the others. If none of the specializations is more
1213      //      specialized than all of the other matching
1214      //      specializations, then the use of the class template is
1215      //      ambiguous and the program is ill-formed.
1216      for (llvm::SmallVector<MatchResult, 4>::iterator P = Best + 1,
1217                                                    PEnd = Matched.end();
1218           P != PEnd; ++P) {
1219        if (getMoreSpecializedPartialSpecialization(P->first, Best->first)
1220              == P->first)
1221          Best = P;
1222      }
1223
1224      // Determine if the best partial specialization is more specialized than
1225      // the others.
1226      bool Ambiguous = false;
1227      for (llvm::SmallVector<MatchResult, 4>::iterator P = Matched.begin(),
1228                                                    PEnd = Matched.end();
1229           P != PEnd; ++P) {
1230        if (P != Best &&
1231            getMoreSpecializedPartialSpecialization(P->first, Best->first)
1232              != Best->first) {
1233          Ambiguous = true;
1234          break;
1235        }
1236      }
1237
1238      if (Ambiguous) {
1239        // Partial ordering did not produce a clear winner. Complain.
1240        ClassTemplateSpec->setInvalidDecl();
1241        Diag(PointOfInstantiation, diag::err_partial_spec_ordering_ambiguous)
1242          << ClassTemplateSpec;
1243
1244        // Print the matching partial specializations.
1245        for (llvm::SmallVector<MatchResult, 4>::iterator P = Matched.begin(),
1246                                                      PEnd = Matched.end();
1247             P != PEnd; ++P)
1248          Diag(P->first->getLocation(), diag::note_partial_spec_match)
1249            << getTemplateArgumentBindingsText(P->first->getTemplateParameters(),
1250                                               *P->second);
1251
1252        return true;
1253      }
1254    }
1255
1256    // Instantiate using the best class template partial specialization.
1257    ClassTemplatePartialSpecializationDecl *OrigPartialSpec = Best->first;
1258    while (OrigPartialSpec->getInstantiatedFromMember()) {
1259      // If we've found an explicit specialization of this class template,
1260      // stop here and use that as the pattern.
1261      if (OrigPartialSpec->isMemberSpecialization())
1262        break;
1263
1264      OrigPartialSpec = OrigPartialSpec->getInstantiatedFromMember();
1265    }
1266
1267    Pattern = OrigPartialSpec;
1268    ClassTemplateSpec->setInstantiationOf(Best->first, Best->second);
1269  } else {
1270    //   -- If no matches are found, the instantiation is generated
1271    //      from the primary template.
1272    ClassTemplateDecl *OrigTemplate = Template;
1273    while (OrigTemplate->getInstantiatedFromMemberTemplate()) {
1274      // If we've found an explicit specialization of this class template,
1275      // stop here and use that as the pattern.
1276      if (OrigTemplate->isMemberSpecialization())
1277        break;
1278
1279      OrigTemplate = OrigTemplate->getInstantiatedFromMemberTemplate();
1280    }
1281
1282    Pattern = OrigTemplate->getTemplatedDecl();
1283  }
1284
1285  bool Result = InstantiateClass(PointOfInstantiation, ClassTemplateSpec,
1286                                 Pattern,
1287                                getTemplateInstantiationArgs(ClassTemplateSpec),
1288                                 TSK,
1289                                 Complain);
1290
1291  for (unsigned I = 0, N = Matched.size(); I != N; ++I) {
1292    // FIXME: Implement TemplateArgumentList::Destroy!
1293    //    if (Matched[I].first != Pattern)
1294    //      Matched[I].second->Destroy(Context);
1295  }
1296
1297  return Result;
1298}
1299
1300/// \brief Instantiates the definitions of all of the member
1301/// of the given class, which is an instantiation of a class template
1302/// or a member class of a template.
1303void
1304Sema::InstantiateClassMembers(SourceLocation PointOfInstantiation,
1305                              CXXRecordDecl *Instantiation,
1306                        const MultiLevelTemplateArgumentList &TemplateArgs,
1307                              TemplateSpecializationKind TSK) {
1308  for (DeclContext::decl_iterator D = Instantiation->decls_begin(),
1309                               DEnd = Instantiation->decls_end();
1310       D != DEnd; ++D) {
1311    bool SuppressNew = false;
1312    if (FunctionDecl *Function = dyn_cast<FunctionDecl>(*D)) {
1313      if (FunctionDecl *Pattern
1314            = Function->getInstantiatedFromMemberFunction()) {
1315        MemberSpecializationInfo *MSInfo
1316          = Function->getMemberSpecializationInfo();
1317        assert(MSInfo && "No member specialization information?");
1318        if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
1319                                                   Function,
1320                                        MSInfo->getTemplateSpecializationKind(),
1321                                              MSInfo->getPointOfInstantiation(),
1322                                                   SuppressNew) ||
1323            SuppressNew)
1324          continue;
1325
1326        if (Function->getBody())
1327          continue;
1328
1329        if (TSK == TSK_ExplicitInstantiationDefinition) {
1330          // C++0x [temp.explicit]p8:
1331          //   An explicit instantiation definition that names a class template
1332          //   specialization explicitly instantiates the class template
1333          //   specialization and is only an explicit instantiation definition
1334          //   of members whose definition is visible at the point of
1335          //   instantiation.
1336          if (!Pattern->getBody())
1337            continue;
1338
1339          Function->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1340
1341          InstantiateFunctionDefinition(PointOfInstantiation, Function);
1342        } else {
1343          Function->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1344        }
1345      }
1346    } else if (VarDecl *Var = dyn_cast<VarDecl>(*D)) {
1347      if (Var->isStaticDataMember()) {
1348        MemberSpecializationInfo *MSInfo = Var->getMemberSpecializationInfo();
1349        assert(MSInfo && "No member specialization information?");
1350        if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
1351                                                   Var,
1352                                        MSInfo->getTemplateSpecializationKind(),
1353                                              MSInfo->getPointOfInstantiation(),
1354                                                   SuppressNew) ||
1355            SuppressNew)
1356          continue;
1357
1358        if (TSK == TSK_ExplicitInstantiationDefinition) {
1359          // C++0x [temp.explicit]p8:
1360          //   An explicit instantiation definition that names a class template
1361          //   specialization explicitly instantiates the class template
1362          //   specialization and is only an explicit instantiation definition
1363          //   of members whose definition is visible at the point of
1364          //   instantiation.
1365          if (!Var->getInstantiatedFromStaticDataMember()
1366                                                     ->getOutOfLineDefinition())
1367            continue;
1368
1369          Var->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1370          InstantiateStaticDataMemberDefinition(PointOfInstantiation, Var);
1371        } else {
1372          Var->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1373        }
1374      }
1375    } else if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(*D)) {
1376      if (Record->isInjectedClassName())
1377        continue;
1378
1379      MemberSpecializationInfo *MSInfo = Record->getMemberSpecializationInfo();
1380      assert(MSInfo && "No member specialization information?");
1381      if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
1382                                                 Record,
1383                                        MSInfo->getTemplateSpecializationKind(),
1384                                              MSInfo->getPointOfInstantiation(),
1385                                                 SuppressNew) ||
1386          SuppressNew)
1387        continue;
1388
1389      CXXRecordDecl *Pattern = Record->getInstantiatedFromMemberClass();
1390      assert(Pattern && "Missing instantiated-from-template information");
1391
1392      if (!Record->getDefinition(Context)) {
1393        if (!Pattern->getDefinition(Context)) {
1394          // C++0x [temp.explicit]p8:
1395          //   An explicit instantiation definition that names a class template
1396          //   specialization explicitly instantiates the class template
1397          //   specialization and is only an explicit instantiation definition
1398          //   of members whose definition is visible at the point of
1399          //   instantiation.
1400          if (TSK == TSK_ExplicitInstantiationDeclaration) {
1401            MSInfo->setTemplateSpecializationKind(TSK);
1402            MSInfo->setPointOfInstantiation(PointOfInstantiation);
1403          }
1404
1405          continue;
1406        }
1407
1408        InstantiateClass(PointOfInstantiation, Record, Pattern,
1409                         TemplateArgs,
1410                         TSK);
1411      }
1412
1413      Pattern = cast_or_null<CXXRecordDecl>(Record->getDefinition(Context));
1414      if (Pattern)
1415        InstantiateClassMembers(PointOfInstantiation, Pattern, TemplateArgs,
1416                                TSK);
1417    }
1418  }
1419}
1420
1421/// \brief Instantiate the definitions of all of the members of the
1422/// given class template specialization, which was named as part of an
1423/// explicit instantiation.
1424void
1425Sema::InstantiateClassTemplateSpecializationMembers(
1426                                           SourceLocation PointOfInstantiation,
1427                            ClassTemplateSpecializationDecl *ClassTemplateSpec,
1428                                               TemplateSpecializationKind TSK) {
1429  // C++0x [temp.explicit]p7:
1430  //   An explicit instantiation that names a class template
1431  //   specialization is an explicit instantion of the same kind
1432  //   (declaration or definition) of each of its members (not
1433  //   including members inherited from base classes) that has not
1434  //   been previously explicitly specialized in the translation unit
1435  //   containing the explicit instantiation, except as described
1436  //   below.
1437  InstantiateClassMembers(PointOfInstantiation, ClassTemplateSpec,
1438                          getTemplateInstantiationArgs(ClassTemplateSpec),
1439                          TSK);
1440}
1441
1442Sema::OwningStmtResult
1443Sema::SubstStmt(Stmt *S, const MultiLevelTemplateArgumentList &TemplateArgs) {
1444  if (!S)
1445    return Owned(S);
1446
1447  TemplateInstantiator Instantiator(*this, TemplateArgs,
1448                                    SourceLocation(),
1449                                    DeclarationName());
1450  return Instantiator.TransformStmt(S);
1451}
1452
1453Sema::OwningExprResult
1454Sema::SubstExpr(Expr *E, const MultiLevelTemplateArgumentList &TemplateArgs) {
1455  if (!E)
1456    return Owned(E);
1457
1458  TemplateInstantiator Instantiator(*this, TemplateArgs,
1459                                    SourceLocation(),
1460                                    DeclarationName());
1461  return Instantiator.TransformExpr(E);
1462}
1463
1464/// \brief Do template substitution on a nested-name-specifier.
1465NestedNameSpecifier *
1466Sema::SubstNestedNameSpecifier(NestedNameSpecifier *NNS,
1467                               SourceRange Range,
1468                         const MultiLevelTemplateArgumentList &TemplateArgs) {
1469  TemplateInstantiator Instantiator(*this, TemplateArgs, Range.getBegin(),
1470                                    DeclarationName());
1471  return Instantiator.TransformNestedNameSpecifier(NNS, Range);
1472}
1473
1474TemplateName
1475Sema::SubstTemplateName(TemplateName Name, SourceLocation Loc,
1476                        const MultiLevelTemplateArgumentList &TemplateArgs) {
1477  TemplateInstantiator Instantiator(*this, TemplateArgs, Loc,
1478                                    DeclarationName());
1479  return Instantiator.TransformTemplateName(Name);
1480}
1481
1482bool Sema::Subst(const TemplateArgumentLoc &Input, TemplateArgumentLoc &Output,
1483                 const MultiLevelTemplateArgumentList &TemplateArgs) {
1484  TemplateInstantiator Instantiator(*this, TemplateArgs, SourceLocation(),
1485                                    DeclarationName());
1486
1487  return Instantiator.TransformTemplateArgument(Input, Output);
1488}
1489