SemaTemplateInstantiate.cpp revision 454feb9da67504b475d032ca2a9fc34c5744748e 
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
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 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                                  TypeSourceInfo *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    Sema::OwningExprResult TransformDeclRefExpr(DeclRefExpr *E);
557
558    Sema::OwningExprResult TransformCXXDefaultArgExpr(CXXDefaultArgExpr *E);
559
560    /// \brief Transforms a template type parameter type by performing
561    /// substitution of the corresponding template type argument.
562    QualType TransformTemplateTypeParmType(TypeLocBuilder &TLB,
563                                           TemplateTypeParmTypeLoc TL);
564  };
565}
566
567Decl *TemplateInstantiator::TransformDecl(Decl *D) {
568  if (!D)
569    return 0;
570
571  if (TemplateTemplateParmDecl *TTP = dyn_cast<TemplateTemplateParmDecl>(D)) {
572    if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
573      TemplateName Template
574        = TemplateArgs(TTP->getDepth(), TTP->getPosition()).getAsTemplate();
575      assert(!Template.isNull() && Template.getAsTemplateDecl() &&
576             "Wrong kind of template template argument");
577      return Template.getAsTemplateDecl();
578    }
579
580    // If the corresponding template argument is NULL or non-existent, it's
581    // because we are performing instantiation from explicitly-specified
582    // template arguments in a function template, but there were some
583    // arguments left unspecified.
584    if (!TemplateArgs.hasTemplateArgument(TTP->getDepth(),
585                                          TTP->getPosition()))
586      return D;
587
588    // Fall through to find the instantiated declaration for this template
589    // template parameter.
590  }
591
592  return SemaRef.FindInstantiatedDecl(cast<NamedDecl>(D), TemplateArgs);
593}
594
595Decl *TemplateInstantiator::TransformDefinition(Decl *D) {
596  Decl *Inst = getSema().SubstDecl(D, getSema().CurContext, TemplateArgs);
597  if (!Inst)
598    return 0;
599
600  getSema().CurrentInstantiationScope->InstantiatedLocal(D, Inst);
601  return Inst;
602}
603
604NamedDecl *
605TemplateInstantiator::TransformFirstQualifierInScope(NamedDecl *D,
606                                                     SourceLocation Loc) {
607  // If the first part of the nested-name-specifier was a template type
608  // parameter, instantiate that type parameter down to a tag type.
609  if (TemplateTypeParmDecl *TTPD = dyn_cast_or_null<TemplateTypeParmDecl>(D)) {
610    const TemplateTypeParmType *TTP
611      = cast<TemplateTypeParmType>(getSema().Context.getTypeDeclType(TTPD));
612    if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
613      QualType T = TemplateArgs(TTP->getDepth(), TTP->getIndex()).getAsType();
614      if (T.isNull())
615        return cast_or_null<NamedDecl>(TransformDecl(D));
616
617      if (const TagType *Tag = T->getAs<TagType>())
618        return Tag->getDecl();
619
620      // The resulting type is not a tag; complain.
621      getSema().Diag(Loc, diag::err_nested_name_spec_non_tag) << T;
622      return 0;
623    }
624  }
625
626  return cast_or_null<NamedDecl>(TransformDecl(D));
627}
628
629VarDecl *
630TemplateInstantiator::RebuildExceptionDecl(VarDecl *ExceptionDecl,
631                                           QualType T,
632                                           TypeSourceInfo *Declarator,
633                                           IdentifierInfo *Name,
634                                           SourceLocation Loc,
635                                           SourceRange TypeRange) {
636  VarDecl *Var = inherited::RebuildExceptionDecl(ExceptionDecl, T, Declarator,
637                                                 Name, Loc, TypeRange);
638  if (Var && !Var->isInvalidDecl())
639    getSema().CurrentInstantiationScope->InstantiatedLocal(ExceptionDecl, Var);
640  return Var;
641}
642
643QualType
644TemplateInstantiator::RebuildElaboratedType(QualType T,
645                                            ElaboratedType::TagKind Tag) {
646  if (const TagType *TT = T->getAs<TagType>()) {
647    TagDecl* TD = TT->getDecl();
648
649    // FIXME: this location is very wrong;  we really need typelocs.
650    SourceLocation TagLocation = TD->getTagKeywordLoc();
651
652    // FIXME: type might be anonymous.
653    IdentifierInfo *Id = TD->getIdentifier();
654
655    // TODO: should we even warn on struct/class mismatches for this?  Seems
656    // like it's likely to produce a lot of spurious errors.
657    if (!SemaRef.isAcceptableTagRedeclaration(TD, Tag, TagLocation, *Id)) {
658      SemaRef.Diag(TagLocation, diag::err_use_with_wrong_tag)
659        << Id
660        << CodeModificationHint::CreateReplacement(SourceRange(TagLocation),
661                                                   TD->getKindName());
662      SemaRef.Diag(TD->getLocation(), diag::note_previous_use);
663    }
664  }
665
666  return TreeTransform<TemplateInstantiator>::RebuildElaboratedType(T, Tag);
667}
668
669Sema::OwningExprResult
670TemplateInstantiator::TransformPredefinedExpr(PredefinedExpr *E) {
671  if (!E->isTypeDependent())
672    return SemaRef.Owned(E->Retain());
673
674  FunctionDecl *currentDecl = getSema().getCurFunctionDecl();
675  assert(currentDecl && "Must have current function declaration when "
676                        "instantiating.");
677
678  PredefinedExpr::IdentType IT = E->getIdentType();
679
680  unsigned Length =
681    PredefinedExpr::ComputeName(getSema().Context, IT, currentDecl).length();
682
683  llvm::APInt LengthI(32, Length + 1);
684  QualType ResTy = getSema().Context.CharTy.withConst();
685  ResTy = getSema().Context.getConstantArrayType(ResTy, LengthI,
686                                                 ArrayType::Normal, 0);
687  PredefinedExpr *PE =
688    new (getSema().Context) PredefinedExpr(E->getLocation(), ResTy, IT);
689  return getSema().Owned(PE);
690}
691
692Sema::OwningExprResult
693TemplateInstantiator::TransformDeclRefExpr(DeclRefExpr *E) {
694  // FIXME: Clean this up a bit
695  NamedDecl *D = E->getDecl();
696  if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D)) {
697    if (NTTP->getDepth() < TemplateArgs.getNumLevels()) {
698      // If the corresponding template argument is NULL or non-existent, it's
699      // because we are performing instantiation from explicitly-specified
700      // template arguments in a function template, but there were some
701      // arguments left unspecified.
702      if (!TemplateArgs.hasTemplateArgument(NTTP->getDepth(),
703                                            NTTP->getPosition()))
704        return SemaRef.Owned(E->Retain());
705
706      const TemplateArgument &Arg = TemplateArgs(NTTP->getDepth(),
707                                                 NTTP->getPosition());
708
709      // The template argument itself might be an expression, in which
710      // case we just return that expression.
711      if (Arg.getKind() == TemplateArgument::Expression)
712        return SemaRef.Owned(Arg.getAsExpr()->Retain());
713
714      if (Arg.getKind() == TemplateArgument::Declaration) {
715        ValueDecl *VD = cast<ValueDecl>(Arg.getAsDecl());
716
717        VD = cast_or_null<ValueDecl>(
718                              getSema().FindInstantiatedDecl(VD, TemplateArgs));
719        if (!VD)
720          return SemaRef.ExprError();
721
722        if (VD->getDeclContext()->isRecord()) {
723          // If the value is a class member, we might have a pointer-to-member.
724          // Determine whether the non-type template template parameter is of
725          // pointer-to-member type. If so, we need to build an appropriate
726          // expression for a pointer-to-member, since a "normal" DeclRefExpr
727          // would refer to the member itself.
728          if (NTTP->getType()->isMemberPointerType()) {
729            QualType ClassType
730              = SemaRef.Context.getTypeDeclType(
731                                        cast<RecordDecl>(VD->getDeclContext()));
732            NestedNameSpecifier *Qualifier
733              = NestedNameSpecifier::Create(SemaRef.Context, 0, false,
734                                            ClassType.getTypePtr());
735            CXXScopeSpec SS;
736            SS.setScopeRep(Qualifier);
737            OwningExprResult RefExpr
738              = SemaRef.BuildDeclRefExpr(VD,
739                                         VD->getType().getNonReferenceType(),
740                                         E->getLocation(),
741                                         &SS);
742            if (RefExpr.isInvalid())
743              return SemaRef.ExprError();
744
745            return SemaRef.CreateBuiltinUnaryOp(E->getLocation(),
746                                                UnaryOperator::AddrOf,
747                                                move(RefExpr));
748          }
749        }
750
751        return SemaRef.BuildDeclRefExpr(VD, VD->getType().getNonReferenceType(),
752                                        E->getLocation());
753      }
754
755      assert(Arg.getKind() == TemplateArgument::Integral);
756      QualType T = Arg.getIntegralType();
757      if (T->isCharType() || T->isWideCharType())
758        return SemaRef.Owned(new (SemaRef.Context) CharacterLiteral(
759                                              Arg.getAsIntegral()->getZExtValue(),
760                                              T->isWideCharType(),
761                                              T,
762                                              E->getSourceRange().getBegin()));
763      if (T->isBooleanType())
764        return SemaRef.Owned(new (SemaRef.Context) CXXBoolLiteralExpr(
765                                            Arg.getAsIntegral()->getBoolValue(),
766                                            T,
767                                            E->getSourceRange().getBegin()));
768
769      assert(Arg.getAsIntegral()->getBitWidth() == SemaRef.Context.getIntWidth(T));
770      return SemaRef.Owned(new (SemaRef.Context) IntegerLiteral(
771                                                *Arg.getAsIntegral(),
772                                                T,
773                                                E->getSourceRange().getBegin()));
774    }
775
776    // We have a non-type template parameter that isn't fully substituted;
777    // FindInstantiatedDecl will find it in the local instantiation scope.
778  }
779
780  return TreeTransform<TemplateInstantiator>::TransformDeclRefExpr(E);
781}
782
783Sema::OwningExprResult TemplateInstantiator::TransformCXXDefaultArgExpr(
784    CXXDefaultArgExpr *E) {
785  assert(!cast<FunctionDecl>(E->getParam()->getDeclContext())->
786             getDescribedFunctionTemplate() &&
787         "Default arg expressions are never formed in dependent cases.");
788  return SemaRef.Owned(E->Retain());
789}
790
791
792QualType
793TemplateInstantiator::TransformTemplateTypeParmType(TypeLocBuilder &TLB,
794                                                TemplateTypeParmTypeLoc TL) {
795  TemplateTypeParmType *T = TL.getTypePtr();
796  if (T->getDepth() < TemplateArgs.getNumLevels()) {
797    // Replace the template type parameter with its corresponding
798    // template argument.
799
800    // If the corresponding template argument is NULL or doesn't exist, it's
801    // because we are performing instantiation from explicitly-specified
802    // template arguments in a function template class, but there were some
803    // arguments left unspecified.
804    if (!TemplateArgs.hasTemplateArgument(T->getDepth(), T->getIndex())) {
805      TemplateTypeParmTypeLoc NewTL
806        = TLB.push<TemplateTypeParmTypeLoc>(TL.getType());
807      NewTL.setNameLoc(TL.getNameLoc());
808      return TL.getType();
809    }
810
811    assert(TemplateArgs(T->getDepth(), T->getIndex()).getKind()
812             == TemplateArgument::Type &&
813           "Template argument kind mismatch");
814
815    QualType Replacement
816      = TemplateArgs(T->getDepth(), T->getIndex()).getAsType();
817
818    // TODO: only do this uniquing once, at the start of instantiation.
819    QualType Result
820      = getSema().Context.getSubstTemplateTypeParmType(T, Replacement);
821    SubstTemplateTypeParmTypeLoc NewTL
822      = TLB.push<SubstTemplateTypeParmTypeLoc>(Result);
823    NewTL.setNameLoc(TL.getNameLoc());
824    return Result;
825  }
826
827  // The template type parameter comes from an inner template (e.g.,
828  // the template parameter list of a member template inside the
829  // template we are instantiating). Create a new template type
830  // parameter with the template "level" reduced by one.
831  QualType Result
832    = getSema().Context.getTemplateTypeParmType(T->getDepth()
833                                                 - TemplateArgs.getNumLevels(),
834                                                T->getIndex(),
835                                                T->isParameterPack(),
836                                                T->getName());
837  TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result);
838  NewTL.setNameLoc(TL.getNameLoc());
839  return Result;
840}
841
842/// \brief Perform substitution on the type T with a given set of template
843/// arguments.
844///
845/// This routine substitutes the given template arguments into the
846/// type T and produces the instantiated type.
847///
848/// \param T the type into which the template arguments will be
849/// substituted. If this type is not dependent, it will be returned
850/// immediately.
851///
852/// \param TemplateArgs the template arguments that will be
853/// substituted for the top-level template parameters within T.
854///
855/// \param Loc the location in the source code where this substitution
856/// is being performed. It will typically be the location of the
857/// declarator (if we're instantiating the type of some declaration)
858/// or the location of the type in the source code (if, e.g., we're
859/// instantiating the type of a cast expression).
860///
861/// \param Entity the name of the entity associated with a declaration
862/// being instantiated (if any). May be empty to indicate that there
863/// is no such entity (if, e.g., this is a type that occurs as part of
864/// a cast expression) or that the entity has no name (e.g., an
865/// unnamed function parameter).
866///
867/// \returns If the instantiation succeeds, the instantiated
868/// type. Otherwise, produces diagnostics and returns a NULL type.
869TypeSourceInfo *Sema::SubstType(TypeSourceInfo *T,
870                                const MultiLevelTemplateArgumentList &Args,
871                                SourceLocation Loc,
872                                DeclarationName Entity) {
873  assert(!ActiveTemplateInstantiations.empty() &&
874         "Cannot perform an instantiation without some context on the "
875         "instantiation stack");
876
877  if (!T->getType()->isDependentType())
878    return T;
879
880  TemplateInstantiator Instantiator(*this, Args, Loc, Entity);
881  return Instantiator.TransformType(T);
882}
883
884/// Deprecated form of the above.
885QualType Sema::SubstType(QualType T,
886                         const MultiLevelTemplateArgumentList &TemplateArgs,
887                         SourceLocation Loc, DeclarationName Entity) {
888  assert(!ActiveTemplateInstantiations.empty() &&
889         "Cannot perform an instantiation without some context on the "
890         "instantiation stack");
891
892  // If T is not a dependent type, there is nothing to do.
893  if (!T->isDependentType())
894    return T;
895
896  TemplateInstantiator Instantiator(*this, TemplateArgs, Loc, Entity);
897  return Instantiator.TransformType(T);
898}
899
900/// \brief Perform substitution on the base class specifiers of the
901/// given class template specialization.
902///
903/// Produces a diagnostic and returns true on error, returns false and
904/// attaches the instantiated base classes to the class template
905/// specialization if successful.
906bool
907Sema::SubstBaseSpecifiers(CXXRecordDecl *Instantiation,
908                          CXXRecordDecl *Pattern,
909                          const MultiLevelTemplateArgumentList &TemplateArgs) {
910  bool Invalid = false;
911  llvm::SmallVector<CXXBaseSpecifier*, 4> InstantiatedBases;
912  for (ClassTemplateSpecializationDecl::base_class_iterator
913         Base = Pattern->bases_begin(), BaseEnd = Pattern->bases_end();
914       Base != BaseEnd; ++Base) {
915    if (!Base->getType()->isDependentType()) {
916      const CXXRecordDecl *BaseDecl =
917        cast<CXXRecordDecl>(Base->getType()->getAs<RecordType>()->getDecl());
918
919      // Make sure to set the attributes from the base.
920      SetClassDeclAttributesFromBase(Instantiation, BaseDecl,
921                                     Base->isVirtual());
922
923      InstantiatedBases.push_back(new (Context) CXXBaseSpecifier(*Base));
924      continue;
925    }
926
927    QualType BaseType = SubstType(Base->getType(),
928                                  TemplateArgs,
929                                  Base->getSourceRange().getBegin(),
930                                  DeclarationName());
931    if (BaseType.isNull()) {
932      Invalid = true;
933      continue;
934    }
935
936    if (CXXBaseSpecifier *InstantiatedBase
937          = CheckBaseSpecifier(Instantiation,
938                               Base->getSourceRange(),
939                               Base->isVirtual(),
940                               Base->getAccessSpecifierAsWritten(),
941                               BaseType,
942                               /*FIXME: Not totally accurate */
943                               Base->getSourceRange().getBegin()))
944      InstantiatedBases.push_back(InstantiatedBase);
945    else
946      Invalid = true;
947  }
948
949  if (!Invalid &&
950      AttachBaseSpecifiers(Instantiation, InstantiatedBases.data(),
951                           InstantiatedBases.size()))
952    Invalid = true;
953
954  return Invalid;
955}
956
957/// \brief Instantiate the definition of a class from a given pattern.
958///
959/// \param PointOfInstantiation The point of instantiation within the
960/// source code.
961///
962/// \param Instantiation is the declaration whose definition is being
963/// instantiated. This will be either a class template specialization
964/// or a member class of a class template specialization.
965///
966/// \param Pattern is the pattern from which the instantiation
967/// occurs. This will be either the declaration of a class template or
968/// the declaration of a member class of a class template.
969///
970/// \param TemplateArgs The template arguments to be substituted into
971/// the pattern.
972///
973/// \param TSK the kind of implicit or explicit instantiation to perform.
974///
975/// \param Complain whether to complain if the class cannot be instantiated due
976/// to the lack of a definition.
977///
978/// \returns true if an error occurred, false otherwise.
979bool
980Sema::InstantiateClass(SourceLocation PointOfInstantiation,
981                       CXXRecordDecl *Instantiation, CXXRecordDecl *Pattern,
982                       const MultiLevelTemplateArgumentList &TemplateArgs,
983                       TemplateSpecializationKind TSK,
984                       bool Complain) {
985  bool Invalid = false;
986
987  CXXRecordDecl *PatternDef
988    = cast_or_null<CXXRecordDecl>(Pattern->getDefinition(Context));
989  if (!PatternDef) {
990    if (!Complain) {
991      // Say nothing
992    } else if (Pattern == Instantiation->getInstantiatedFromMemberClass()) {
993      Diag(PointOfInstantiation,
994           diag::err_implicit_instantiate_member_undefined)
995        << Context.getTypeDeclType(Instantiation);
996      Diag(Pattern->getLocation(), diag::note_member_of_template_here);
997    } else {
998      Diag(PointOfInstantiation, diag::err_template_instantiate_undefined)
999        << (TSK != TSK_ImplicitInstantiation)
1000        << Context.getTypeDeclType(Instantiation);
1001      Diag(Pattern->getLocation(), diag::note_template_decl_here);
1002    }
1003    return true;
1004  }
1005  Pattern = PatternDef;
1006
1007  // \brief Record the point of instantiation.
1008  if (MemberSpecializationInfo *MSInfo
1009        = Instantiation->getMemberSpecializationInfo()) {
1010    MSInfo->setTemplateSpecializationKind(TSK);
1011    MSInfo->setPointOfInstantiation(PointOfInstantiation);
1012  } else if (ClassTemplateSpecializationDecl *Spec
1013               = dyn_cast<ClassTemplateSpecializationDecl>(Instantiation)) {
1014    Spec->setTemplateSpecializationKind(TSK);
1015    Spec->setPointOfInstantiation(PointOfInstantiation);
1016  }
1017
1018  InstantiatingTemplate Inst(*this, PointOfInstantiation, Instantiation);
1019  if (Inst)
1020    return true;
1021
1022  // Enter the scope of this instantiation. We don't use
1023  // PushDeclContext because we don't have a scope.
1024  DeclContext *PreviousContext = CurContext;
1025  CurContext = Instantiation;
1026
1027  // Start the definition of this instantiation.
1028  Instantiation->startDefinition();
1029
1030  // Do substitution on the base class specifiers.
1031  if (SubstBaseSpecifiers(Instantiation, Pattern, TemplateArgs))
1032    Invalid = true;
1033
1034  llvm::SmallVector<DeclPtrTy, 4> Fields;
1035  for (RecordDecl::decl_iterator Member = Pattern->decls_begin(),
1036         MemberEnd = Pattern->decls_end();
1037       Member != MemberEnd; ++Member) {
1038    Decl *NewMember = SubstDecl(*Member, Instantiation, TemplateArgs);
1039    if (NewMember) {
1040      if (FieldDecl *Field = dyn_cast<FieldDecl>(NewMember))
1041        Fields.push_back(DeclPtrTy::make(Field));
1042      else if (NewMember->isInvalidDecl())
1043        Invalid = true;
1044    } else {
1045      // FIXME: Eventually, a NULL return will mean that one of the
1046      // instantiations was a semantic disaster, and we'll want to set Invalid =
1047      // true. For now, we expect to skip some members that we can't yet handle.
1048    }
1049  }
1050
1051  // Finish checking fields.
1052  ActOnFields(0, Instantiation->getLocation(), DeclPtrTy::make(Instantiation),
1053              Fields.data(), Fields.size(), SourceLocation(), SourceLocation(),
1054              0);
1055  CheckCompletedCXXClass(Instantiation);
1056  if (Instantiation->isInvalidDecl())
1057    Invalid = true;
1058
1059  // Exit the scope of this instantiation.
1060  CurContext = PreviousContext;
1061
1062  if (!Invalid)
1063    Consumer.HandleTagDeclDefinition(Instantiation);
1064
1065  return Invalid;
1066}
1067
1068bool
1069Sema::InstantiateClassTemplateSpecialization(
1070                           SourceLocation PointOfInstantiation,
1071                           ClassTemplateSpecializationDecl *ClassTemplateSpec,
1072                           TemplateSpecializationKind TSK,
1073                           bool Complain) {
1074  // Perform the actual instantiation on the canonical declaration.
1075  ClassTemplateSpec = cast<ClassTemplateSpecializationDecl>(
1076                                         ClassTemplateSpec->getCanonicalDecl());
1077
1078  // Check whether we have already instantiated or specialized this class
1079  // template specialization.
1080  if (ClassTemplateSpec->getSpecializationKind() != TSK_Undeclared) {
1081    if (ClassTemplateSpec->getSpecializationKind() ==
1082          TSK_ExplicitInstantiationDeclaration &&
1083        TSK == TSK_ExplicitInstantiationDefinition) {
1084      // An explicit instantiation definition follows an explicit instantiation
1085      // declaration (C++0x [temp.explicit]p10); go ahead and perform the
1086      // explicit instantiation.
1087      ClassTemplateSpec->setSpecializationKind(TSK);
1088      return false;
1089    }
1090
1091    // We can only instantiate something that hasn't already been
1092    // instantiated or specialized. Fail without any diagnostics: our
1093    // caller will provide an error message.
1094    return true;
1095  }
1096
1097  if (ClassTemplateSpec->isInvalidDecl())
1098    return true;
1099
1100  ClassTemplateDecl *Template = ClassTemplateSpec->getSpecializedTemplate();
1101  CXXRecordDecl *Pattern = 0;
1102
1103  // C++ [temp.class.spec.match]p1:
1104  //   When a class template is used in a context that requires an
1105  //   instantiation of the class, it is necessary to determine
1106  //   whether the instantiation is to be generated using the primary
1107  //   template or one of the partial specializations. This is done by
1108  //   matching the template arguments of the class template
1109  //   specialization with the template argument lists of the partial
1110  //   specializations.
1111  typedef std::pair<ClassTemplatePartialSpecializationDecl *,
1112                    TemplateArgumentList *> MatchResult;
1113  llvm::SmallVector<MatchResult, 4> Matched;
1114  for (llvm::FoldingSet<ClassTemplatePartialSpecializationDecl>::iterator
1115         Partial = Template->getPartialSpecializations().begin(),
1116         PartialEnd = Template->getPartialSpecializations().end();
1117       Partial != PartialEnd;
1118       ++Partial) {
1119    TemplateDeductionInfo Info(Context);
1120    if (TemplateDeductionResult Result
1121          = DeduceTemplateArguments(&*Partial,
1122                                    ClassTemplateSpec->getTemplateArgs(),
1123                                    Info)) {
1124      // FIXME: Store the failed-deduction information for use in
1125      // diagnostics, later.
1126      (void)Result;
1127    } else {
1128      Matched.push_back(std::make_pair(&*Partial, Info.take()));
1129    }
1130  }
1131
1132  if (Matched.size() >= 1) {
1133    llvm::SmallVector<MatchResult, 4>::iterator Best = Matched.begin();
1134    if (Matched.size() == 1) {
1135      //   -- If exactly one matching specialization is found, the
1136      //      instantiation is generated from that specialization.
1137      // We don't need to do anything for this.
1138    } else {
1139      //   -- If more than one matching specialization is found, the
1140      //      partial order rules (14.5.4.2) are used to determine
1141      //      whether one of the specializations is more specialized
1142      //      than the others. If none of the specializations is more
1143      //      specialized than all of the other matching
1144      //      specializations, then the use of the class template is
1145      //      ambiguous and the program is ill-formed.
1146      for (llvm::SmallVector<MatchResult, 4>::iterator P = Best + 1,
1147                                                    PEnd = Matched.end();
1148           P != PEnd; ++P) {
1149        if (getMoreSpecializedPartialSpecialization(P->first, Best->first)
1150              == P->first)
1151          Best = P;
1152      }
1153
1154      // Determine if the best partial specialization is more specialized than
1155      // the others.
1156      bool Ambiguous = false;
1157      for (llvm::SmallVector<MatchResult, 4>::iterator P = Matched.begin(),
1158                                                    PEnd = Matched.end();
1159           P != PEnd; ++P) {
1160        if (P != Best &&
1161            getMoreSpecializedPartialSpecialization(P->first, Best->first)
1162              != Best->first) {
1163          Ambiguous = true;
1164          break;
1165        }
1166      }
1167
1168      if (Ambiguous) {
1169        // Partial ordering did not produce a clear winner. Complain.
1170        ClassTemplateSpec->setInvalidDecl();
1171        Diag(PointOfInstantiation, diag::err_partial_spec_ordering_ambiguous)
1172          << ClassTemplateSpec;
1173
1174        // Print the matching partial specializations.
1175        for (llvm::SmallVector<MatchResult, 4>::iterator P = Matched.begin(),
1176                                                      PEnd = Matched.end();
1177             P != PEnd; ++P)
1178          Diag(P->first->getLocation(), diag::note_partial_spec_match)
1179            << getTemplateArgumentBindingsText(P->first->getTemplateParameters(),
1180                                               *P->second);
1181
1182        return true;
1183      }
1184    }
1185
1186    // Instantiate using the best class template partial specialization.
1187    ClassTemplatePartialSpecializationDecl *OrigPartialSpec = Best->first;
1188    while (OrigPartialSpec->getInstantiatedFromMember()) {
1189      // If we've found an explicit specialization of this class template,
1190      // stop here and use that as the pattern.
1191      if (OrigPartialSpec->isMemberSpecialization())
1192        break;
1193
1194      OrigPartialSpec = OrigPartialSpec->getInstantiatedFromMember();
1195    }
1196
1197    Pattern = OrigPartialSpec;
1198    ClassTemplateSpec->setInstantiationOf(Best->first, Best->second);
1199  } else {
1200    //   -- If no matches are found, the instantiation is generated
1201    //      from the primary template.
1202    ClassTemplateDecl *OrigTemplate = Template;
1203    while (OrigTemplate->getInstantiatedFromMemberTemplate()) {
1204      // If we've found an explicit specialization of this class template,
1205      // stop here and use that as the pattern.
1206      if (OrigTemplate->isMemberSpecialization())
1207        break;
1208
1209      OrigTemplate = OrigTemplate->getInstantiatedFromMemberTemplate();
1210    }
1211
1212    Pattern = OrigTemplate->getTemplatedDecl();
1213  }
1214
1215  bool Result = InstantiateClass(PointOfInstantiation, ClassTemplateSpec,
1216                                 Pattern,
1217                                getTemplateInstantiationArgs(ClassTemplateSpec),
1218                                 TSK,
1219                                 Complain);
1220
1221  for (unsigned I = 0, N = Matched.size(); I != N; ++I) {
1222    // FIXME: Implement TemplateArgumentList::Destroy!
1223    //    if (Matched[I].first != Pattern)
1224    //      Matched[I].second->Destroy(Context);
1225  }
1226
1227  return Result;
1228}
1229
1230/// \brief Instantiates the definitions of all of the member
1231/// of the given class, which is an instantiation of a class template
1232/// or a member class of a template.
1233void
1234Sema::InstantiateClassMembers(SourceLocation PointOfInstantiation,
1235                              CXXRecordDecl *Instantiation,
1236                        const MultiLevelTemplateArgumentList &TemplateArgs,
1237                              TemplateSpecializationKind TSK) {
1238  for (DeclContext::decl_iterator D = Instantiation->decls_begin(),
1239                               DEnd = Instantiation->decls_end();
1240       D != DEnd; ++D) {
1241    bool SuppressNew = false;
1242    if (FunctionDecl *Function = dyn_cast<FunctionDecl>(*D)) {
1243      if (FunctionDecl *Pattern
1244            = Function->getInstantiatedFromMemberFunction()) {
1245        MemberSpecializationInfo *MSInfo
1246          = Function->getMemberSpecializationInfo();
1247        assert(MSInfo && "No member specialization information?");
1248        if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
1249                                                   Function,
1250                                        MSInfo->getTemplateSpecializationKind(),
1251                                              MSInfo->getPointOfInstantiation(),
1252                                                   SuppressNew) ||
1253            SuppressNew)
1254          continue;
1255
1256        if (Function->getBody())
1257          continue;
1258
1259        if (TSK == TSK_ExplicitInstantiationDefinition) {
1260          // C++0x [temp.explicit]p8:
1261          //   An explicit instantiation definition that names a class template
1262          //   specialization explicitly instantiates the class template
1263          //   specialization and is only an explicit instantiation definition
1264          //   of members whose definition is visible at the point of
1265          //   instantiation.
1266          if (!Pattern->getBody())
1267            continue;
1268
1269          Function->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1270
1271          InstantiateFunctionDefinition(PointOfInstantiation, Function);
1272        } else {
1273          Function->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1274        }
1275      }
1276    } else if (VarDecl *Var = dyn_cast<VarDecl>(*D)) {
1277      if (Var->isStaticDataMember()) {
1278        MemberSpecializationInfo *MSInfo = Var->getMemberSpecializationInfo();
1279        assert(MSInfo && "No member specialization information?");
1280        if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
1281                                                   Var,
1282                                        MSInfo->getTemplateSpecializationKind(),
1283                                              MSInfo->getPointOfInstantiation(),
1284                                                   SuppressNew) ||
1285            SuppressNew)
1286          continue;
1287
1288        if (TSK == TSK_ExplicitInstantiationDefinition) {
1289          // C++0x [temp.explicit]p8:
1290          //   An explicit instantiation definition that names a class template
1291          //   specialization explicitly instantiates the class template
1292          //   specialization and is only an explicit instantiation definition
1293          //   of members whose definition is visible at the point of
1294          //   instantiation.
1295          if (!Var->getInstantiatedFromStaticDataMember()
1296                                                     ->getOutOfLineDefinition())
1297            continue;
1298
1299          Var->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1300          InstantiateStaticDataMemberDefinition(PointOfInstantiation, Var);
1301        } else {
1302          Var->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1303        }
1304      }
1305    } else if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(*D)) {
1306      if (Record->isInjectedClassName())
1307        continue;
1308
1309      MemberSpecializationInfo *MSInfo = Record->getMemberSpecializationInfo();
1310      assert(MSInfo && "No member specialization information?");
1311      if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
1312                                                 Record,
1313                                        MSInfo->getTemplateSpecializationKind(),
1314                                              MSInfo->getPointOfInstantiation(),
1315                                                 SuppressNew) ||
1316          SuppressNew)
1317        continue;
1318
1319      CXXRecordDecl *Pattern = Record->getInstantiatedFromMemberClass();
1320      assert(Pattern && "Missing instantiated-from-template information");
1321
1322      if (!Record->getDefinition(Context)) {
1323        if (!Pattern->getDefinition(Context)) {
1324          // C++0x [temp.explicit]p8:
1325          //   An explicit instantiation definition that names a class template
1326          //   specialization explicitly instantiates the class template
1327          //   specialization and is only an explicit instantiation definition
1328          //   of members whose definition is visible at the point of
1329          //   instantiation.
1330          if (TSK == TSK_ExplicitInstantiationDeclaration) {
1331            MSInfo->setTemplateSpecializationKind(TSK);
1332            MSInfo->setPointOfInstantiation(PointOfInstantiation);
1333          }
1334
1335          continue;
1336        }
1337
1338        InstantiateClass(PointOfInstantiation, Record, Pattern,
1339                         TemplateArgs,
1340                         TSK);
1341      }
1342
1343      Pattern = cast_or_null<CXXRecordDecl>(Record->getDefinition(Context));
1344      if (Pattern)
1345        InstantiateClassMembers(PointOfInstantiation, Pattern, TemplateArgs,
1346                                TSK);
1347    }
1348  }
1349}
1350
1351/// \brief Instantiate the definitions of all of the members of the
1352/// given class template specialization, which was named as part of an
1353/// explicit instantiation.
1354void
1355Sema::InstantiateClassTemplateSpecializationMembers(
1356                                           SourceLocation PointOfInstantiation,
1357                            ClassTemplateSpecializationDecl *ClassTemplateSpec,
1358                                               TemplateSpecializationKind TSK) {
1359  // C++0x [temp.explicit]p7:
1360  //   An explicit instantiation that names a class template
1361  //   specialization is an explicit instantion of the same kind
1362  //   (declaration or definition) of each of its members (not
1363  //   including members inherited from base classes) that has not
1364  //   been previously explicitly specialized in the translation unit
1365  //   containing the explicit instantiation, except as described
1366  //   below.
1367  InstantiateClassMembers(PointOfInstantiation, ClassTemplateSpec,
1368                          getTemplateInstantiationArgs(ClassTemplateSpec),
1369                          TSK);
1370}
1371
1372Sema::OwningStmtResult
1373Sema::SubstStmt(Stmt *S, const MultiLevelTemplateArgumentList &TemplateArgs) {
1374  if (!S)
1375    return Owned(S);
1376
1377  TemplateInstantiator Instantiator(*this, TemplateArgs,
1378                                    SourceLocation(),
1379                                    DeclarationName());
1380  return Instantiator.TransformStmt(S);
1381}
1382
1383Sema::OwningExprResult
1384Sema::SubstExpr(Expr *E, const MultiLevelTemplateArgumentList &TemplateArgs) {
1385  if (!E)
1386    return Owned(E);
1387
1388  TemplateInstantiator Instantiator(*this, TemplateArgs,
1389                                    SourceLocation(),
1390                                    DeclarationName());
1391  return Instantiator.TransformExpr(E);
1392}
1393
1394/// \brief Do template substitution on a nested-name-specifier.
1395NestedNameSpecifier *
1396Sema::SubstNestedNameSpecifier(NestedNameSpecifier *NNS,
1397                               SourceRange Range,
1398                         const MultiLevelTemplateArgumentList &TemplateArgs) {
1399  TemplateInstantiator Instantiator(*this, TemplateArgs, Range.getBegin(),
1400                                    DeclarationName());
1401  return Instantiator.TransformNestedNameSpecifier(NNS, Range);
1402}
1403
1404TemplateName
1405Sema::SubstTemplateName(TemplateName Name, SourceLocation Loc,
1406                        const MultiLevelTemplateArgumentList &TemplateArgs) {
1407  TemplateInstantiator Instantiator(*this, TemplateArgs, Loc,
1408                                    DeclarationName());
1409  return Instantiator.TransformTemplateName(Name);
1410}
1411
1412bool Sema::Subst(const TemplateArgumentLoc &Input, TemplateArgumentLoc &Output,
1413                 const MultiLevelTemplateArgumentList &TemplateArgs) {
1414  TemplateInstantiator Instantiator(*this, TemplateArgs, SourceLocation(),
1415                                    DeclarationName());
1416
1417  return Instantiator.TransformTemplateArgument(Input, Output);
1418}
1419