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