SemaTemplateInstantiate.cpp revision 7b1cf305c97382676c61ee89cc6d22fc5c26a8ae 
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 "clang/Sema/SemaInternal.h"
14#include "TreeTransform.h"
15#include "clang/Sema/DeclSpec.h"
16#include "clang/Sema/Lookup.h"
17#include "clang/Sema/Template.h"
18#include "clang/Sema/TemplateDeduction.h"
19#include "clang/AST/ASTConsumer.h"
20#include "clang/AST/ASTContext.h"
21#include "clang/AST/Expr.h"
22#include "clang/AST/DeclTemplate.h"
23#include "clang/Basic/LangOptions.h"
24
25using namespace clang;
26using namespace sema;
27
28//===----------------------------------------------------------------------===/
29// Template Instantiation Support
30//===----------------------------------------------------------------------===/
31
32/// \brief Retrieve the template argument list(s) that should be used to
33/// instantiate the definition of the given declaration.
34///
35/// \param D the declaration for which we are computing template instantiation
36/// arguments.
37///
38/// \param Innermost if non-NULL, the innermost template argument list.
39///
40/// \param RelativeToPrimary true if we should get the template
41/// arguments relative to the primary template, even when we're
42/// dealing with a specialization. This is only relevant for function
43/// template specializations.
44///
45/// \param Pattern If non-NULL, indicates the pattern from which we will be
46/// instantiating the definition of the given declaration, \p D. This is
47/// used to determine the proper set of template instantiation arguments for
48/// friend function template specializations.
49MultiLevelTemplateArgumentList
50Sema::getTemplateInstantiationArgs(NamedDecl *D,
51                                   const TemplateArgumentList *Innermost,
52                                   bool RelativeToPrimary,
53                                   const FunctionDecl *Pattern) {
54  // Accumulate the set of template argument lists in this structure.
55  MultiLevelTemplateArgumentList Result;
56
57  if (Innermost)
58    Result.addOuterTemplateArguments(Innermost);
59
60  DeclContext *Ctx = dyn_cast<DeclContext>(D);
61  if (!Ctx)
62    Ctx = D->getDeclContext();
63
64  while (!Ctx->isFileContext()) {
65    // Add template arguments from a class template instantiation.
66    if (ClassTemplateSpecializationDecl *Spec
67          = dyn_cast<ClassTemplateSpecializationDecl>(Ctx)) {
68      // We're done when we hit an explicit specialization.
69      if (Spec->getSpecializationKind() == TSK_ExplicitSpecialization &&
70          !isa<ClassTemplatePartialSpecializationDecl>(Spec))
71        break;
72
73      Result.addOuterTemplateArguments(&Spec->getTemplateInstantiationArgs());
74
75      // If this class template specialization was instantiated from a
76      // specialized member that is a class template, we're done.
77      assert(Spec->getSpecializedTemplate() && "No class template?");
78      if (Spec->getSpecializedTemplate()->isMemberSpecialization())
79        break;
80    }
81    // Add template arguments from a function template specialization.
82    else if (FunctionDecl *Function = dyn_cast<FunctionDecl>(Ctx)) {
83      if (!RelativeToPrimary &&
84          Function->getTemplateSpecializationKind()
85                                                  == TSK_ExplicitSpecialization)
86        break;
87
88      if (const TemplateArgumentList *TemplateArgs
89            = Function->getTemplateSpecializationArgs()) {
90        // Add the template arguments for this specialization.
91        Result.addOuterTemplateArguments(TemplateArgs);
92
93        // If this function was instantiated from a specialized member that is
94        // a function template, we're done.
95        assert(Function->getPrimaryTemplate() && "No function template?");
96        if (Function->getPrimaryTemplate()->isMemberSpecialization())
97          break;
98      }
99
100      // If this is a friend declaration and it declares an entity at
101      // namespace scope, take arguments from its lexical parent
102      // instead of its semantic parent, unless of course the pattern we're
103      // instantiating actually comes from the file's context!
104      if (Function->getFriendObjectKind() &&
105          Function->getDeclContext()->isFileContext() &&
106          (!Pattern || !Pattern->getLexicalDeclContext()->isFileContext())) {
107        Ctx = Function->getLexicalDeclContext();
108        RelativeToPrimary = false;
109        continue;
110      }
111    } else if (CXXRecordDecl *Rec = dyn_cast<CXXRecordDecl>(Ctx)) {
112      if (ClassTemplateDecl *ClassTemplate = Rec->getDescribedClassTemplate()) {
113        QualType T = ClassTemplate->getInjectedClassNameSpecialization();
114        const TemplateSpecializationType *TST
115          = cast<TemplateSpecializationType>(Context.getCanonicalType(T));
116        Result.addOuterTemplateArguments(TST->getArgs(), TST->getNumArgs());
117        if (ClassTemplate->isMemberSpecialization())
118          break;
119      }
120    }
121
122    Ctx = Ctx->getParent();
123    RelativeToPrimary = false;
124  }
125
126  return Result;
127}
128
129bool Sema::ActiveTemplateInstantiation::isInstantiationRecord() const {
130  switch (Kind) {
131  case TemplateInstantiation:
132  case DefaultTemplateArgumentInstantiation:
133  case DefaultFunctionArgumentInstantiation:
134    return true;
135
136  case ExplicitTemplateArgumentSubstitution:
137  case DeducedTemplateArgumentSubstitution:
138  case PriorTemplateArgumentSubstitution:
139  case DefaultTemplateArgumentChecking:
140    return false;
141  }
142
143  return true;
144}
145
146Sema::InstantiatingTemplate::
147InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
148                      Decl *Entity,
149                      SourceRange InstantiationRange)
150  :  SemaRef(SemaRef) {
151  Invalid = CheckInstantiationDepth(PointOfInstantiation,
152                                    InstantiationRange);
153  if (!Invalid) {
154    ActiveTemplateInstantiation Inst;
155    Inst.Kind = ActiveTemplateInstantiation::TemplateInstantiation;
156    Inst.PointOfInstantiation = PointOfInstantiation;
157    Inst.Entity = reinterpret_cast<uintptr_t>(Entity);
158    Inst.TemplateArgs = 0;
159    Inst.NumTemplateArgs = 0;
160    Inst.InstantiationRange = InstantiationRange;
161    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
162  }
163}
164
165Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
166                                         SourceLocation PointOfInstantiation,
167                                         TemplateDecl *Template,
168                                         const TemplateArgument *TemplateArgs,
169                                         unsigned NumTemplateArgs,
170                                         SourceRange InstantiationRange)
171  : SemaRef(SemaRef) {
172
173  Invalid = CheckInstantiationDepth(PointOfInstantiation,
174                                    InstantiationRange);
175  if (!Invalid) {
176    ActiveTemplateInstantiation Inst;
177    Inst.Kind
178      = ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation;
179    Inst.PointOfInstantiation = PointOfInstantiation;
180    Inst.Entity = reinterpret_cast<uintptr_t>(Template);
181    Inst.TemplateArgs = TemplateArgs;
182    Inst.NumTemplateArgs = NumTemplateArgs;
183    Inst.InstantiationRange = InstantiationRange;
184    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
185  }
186}
187
188Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
189                                         SourceLocation PointOfInstantiation,
190                                      FunctionTemplateDecl *FunctionTemplate,
191                                        const TemplateArgument *TemplateArgs,
192                                                   unsigned NumTemplateArgs,
193                         ActiveTemplateInstantiation::InstantiationKind Kind,
194                                   sema::TemplateDeductionInfo &DeductionInfo,
195                                              SourceRange InstantiationRange)
196  : SemaRef(SemaRef) {
197
198  Invalid = CheckInstantiationDepth(PointOfInstantiation,
199                                    InstantiationRange);
200  if (!Invalid) {
201    ActiveTemplateInstantiation Inst;
202    Inst.Kind = Kind;
203    Inst.PointOfInstantiation = PointOfInstantiation;
204    Inst.Entity = reinterpret_cast<uintptr_t>(FunctionTemplate);
205    Inst.TemplateArgs = TemplateArgs;
206    Inst.NumTemplateArgs = NumTemplateArgs;
207    Inst.DeductionInfo = &DeductionInfo;
208    Inst.InstantiationRange = InstantiationRange;
209    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
210
211    if (!Inst.isInstantiationRecord())
212      ++SemaRef.NonInstantiationEntries;
213  }
214}
215
216Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
217                                         SourceLocation PointOfInstantiation,
218                          ClassTemplatePartialSpecializationDecl *PartialSpec,
219                                         const TemplateArgument *TemplateArgs,
220                                         unsigned NumTemplateArgs,
221                                    sema::TemplateDeductionInfo &DeductionInfo,
222                                         SourceRange InstantiationRange)
223  : SemaRef(SemaRef) {
224
225  Invalid = false;
226
227  ActiveTemplateInstantiation Inst;
228  Inst.Kind = ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution;
229  Inst.PointOfInstantiation = PointOfInstantiation;
230  Inst.Entity = reinterpret_cast<uintptr_t>(PartialSpec);
231  Inst.TemplateArgs = TemplateArgs;
232  Inst.NumTemplateArgs = NumTemplateArgs;
233  Inst.DeductionInfo = &DeductionInfo;
234  Inst.InstantiationRange = InstantiationRange;
235  SemaRef.ActiveTemplateInstantiations.push_back(Inst);
236
237  assert(!Inst.isInstantiationRecord());
238  ++SemaRef.NonInstantiationEntries;
239}
240
241Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
242                                          SourceLocation PointOfInstantiation,
243                                          ParmVarDecl *Param,
244                                          const TemplateArgument *TemplateArgs,
245                                          unsigned NumTemplateArgs,
246                                          SourceRange InstantiationRange)
247  : SemaRef(SemaRef) {
248
249  Invalid = CheckInstantiationDepth(PointOfInstantiation, InstantiationRange);
250
251  if (!Invalid) {
252    ActiveTemplateInstantiation Inst;
253    Inst.Kind
254      = ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation;
255    Inst.PointOfInstantiation = PointOfInstantiation;
256    Inst.Entity = reinterpret_cast<uintptr_t>(Param);
257    Inst.TemplateArgs = TemplateArgs;
258    Inst.NumTemplateArgs = NumTemplateArgs;
259    Inst.InstantiationRange = InstantiationRange;
260    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
261  }
262}
263
264Sema::InstantiatingTemplate::
265InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
266                      NamedDecl *Template,
267                      NonTypeTemplateParmDecl *Param,
268                      const TemplateArgument *TemplateArgs,
269                      unsigned NumTemplateArgs,
270                      SourceRange InstantiationRange) : SemaRef(SemaRef) {
271  Invalid = false;
272
273  ActiveTemplateInstantiation Inst;
274  Inst.Kind = ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution;
275  Inst.PointOfInstantiation = PointOfInstantiation;
276  Inst.Template = Template;
277  Inst.Entity = reinterpret_cast<uintptr_t>(Param);
278  Inst.TemplateArgs = TemplateArgs;
279  Inst.NumTemplateArgs = NumTemplateArgs;
280  Inst.InstantiationRange = InstantiationRange;
281  SemaRef.ActiveTemplateInstantiations.push_back(Inst);
282
283  assert(!Inst.isInstantiationRecord());
284  ++SemaRef.NonInstantiationEntries;
285}
286
287Sema::InstantiatingTemplate::
288InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
289                      NamedDecl *Template,
290                      TemplateTemplateParmDecl *Param,
291                      const TemplateArgument *TemplateArgs,
292                      unsigned NumTemplateArgs,
293                      SourceRange InstantiationRange) : SemaRef(SemaRef) {
294  Invalid = false;
295  ActiveTemplateInstantiation Inst;
296  Inst.Kind = ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution;
297  Inst.PointOfInstantiation = PointOfInstantiation;
298  Inst.Template = Template;
299  Inst.Entity = reinterpret_cast<uintptr_t>(Param);
300  Inst.TemplateArgs = TemplateArgs;
301  Inst.NumTemplateArgs = NumTemplateArgs;
302  Inst.InstantiationRange = InstantiationRange;
303  SemaRef.ActiveTemplateInstantiations.push_back(Inst);
304
305  assert(!Inst.isInstantiationRecord());
306  ++SemaRef.NonInstantiationEntries;
307}
308
309Sema::InstantiatingTemplate::
310InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
311                      TemplateDecl *Template,
312                      NamedDecl *Param,
313                      const TemplateArgument *TemplateArgs,
314                      unsigned NumTemplateArgs,
315                      SourceRange InstantiationRange) : SemaRef(SemaRef) {
316  Invalid = false;
317
318  ActiveTemplateInstantiation Inst;
319  Inst.Kind = ActiveTemplateInstantiation::DefaultTemplateArgumentChecking;
320  Inst.PointOfInstantiation = PointOfInstantiation;
321  Inst.Template = Template;
322  Inst.Entity = reinterpret_cast<uintptr_t>(Param);
323  Inst.TemplateArgs = TemplateArgs;
324  Inst.NumTemplateArgs = NumTemplateArgs;
325  Inst.InstantiationRange = InstantiationRange;
326  SemaRef.ActiveTemplateInstantiations.push_back(Inst);
327
328  assert(!Inst.isInstantiationRecord());
329  ++SemaRef.NonInstantiationEntries;
330}
331
332void Sema::InstantiatingTemplate::Clear() {
333  if (!Invalid) {
334    if (!SemaRef.ActiveTemplateInstantiations.back().isInstantiationRecord()) {
335      assert(SemaRef.NonInstantiationEntries > 0);
336      --SemaRef.NonInstantiationEntries;
337    }
338
339    SemaRef.ActiveTemplateInstantiations.pop_back();
340    Invalid = true;
341  }
342}
343
344bool Sema::InstantiatingTemplate::CheckInstantiationDepth(
345                                        SourceLocation PointOfInstantiation,
346                                           SourceRange InstantiationRange) {
347  assert(SemaRef.NonInstantiationEntries <=
348                                   SemaRef.ActiveTemplateInstantiations.size());
349  if ((SemaRef.ActiveTemplateInstantiations.size() -
350          SemaRef.NonInstantiationEntries)
351        <= SemaRef.getLangOptions().InstantiationDepth)
352    return false;
353
354  SemaRef.Diag(PointOfInstantiation,
355               diag::err_template_recursion_depth_exceeded)
356    << SemaRef.getLangOptions().InstantiationDepth
357    << InstantiationRange;
358  SemaRef.Diag(PointOfInstantiation, diag::note_template_recursion_depth)
359    << SemaRef.getLangOptions().InstantiationDepth;
360  return true;
361}
362
363/// \brief Prints the current instantiation stack through a series of
364/// notes.
365void Sema::PrintInstantiationStack() {
366  // Determine which template instantiations to skip, if any.
367  unsigned SkipStart = ActiveTemplateInstantiations.size(), SkipEnd = SkipStart;
368  unsigned Limit = Diags.getTemplateBacktraceLimit();
369  if (Limit && Limit < ActiveTemplateInstantiations.size()) {
370    SkipStart = Limit / 2 + Limit % 2;
371    SkipEnd = ActiveTemplateInstantiations.size() - Limit / 2;
372  }
373
374  // FIXME: In all of these cases, we need to show the template arguments
375  unsigned InstantiationIdx = 0;
376  for (llvm::SmallVector<ActiveTemplateInstantiation, 16>::reverse_iterator
377         Active = ActiveTemplateInstantiations.rbegin(),
378         ActiveEnd = ActiveTemplateInstantiations.rend();
379       Active != ActiveEnd;
380       ++Active, ++InstantiationIdx) {
381    // Skip this instantiation?
382    if (InstantiationIdx >= SkipStart && InstantiationIdx < SkipEnd) {
383      if (InstantiationIdx == SkipStart) {
384        // Note that we're skipping instantiations.
385        Diags.Report(Active->PointOfInstantiation,
386                     diag::note_instantiation_contexts_suppressed)
387          << unsigned(ActiveTemplateInstantiations.size() - Limit);
388      }
389      continue;
390    }
391
392    switch (Active->Kind) {
393    case ActiveTemplateInstantiation::TemplateInstantiation: {
394      Decl *D = reinterpret_cast<Decl *>(Active->Entity);
395      if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(D)) {
396        unsigned DiagID = diag::note_template_member_class_here;
397        if (isa<ClassTemplateSpecializationDecl>(Record))
398          DiagID = diag::note_template_class_instantiation_here;
399        Diags.Report(Active->PointOfInstantiation, DiagID)
400          << Context.getTypeDeclType(Record)
401          << Active->InstantiationRange;
402      } else if (FunctionDecl *Function = dyn_cast<FunctionDecl>(D)) {
403        unsigned DiagID;
404        if (Function->getPrimaryTemplate())
405          DiagID = diag::note_function_template_spec_here;
406        else
407          DiagID = diag::note_template_member_function_here;
408        Diags.Report(Active->PointOfInstantiation, DiagID)
409          << Function
410          << Active->InstantiationRange;
411      } else {
412        Diags.Report(Active->PointOfInstantiation,
413                     diag::note_template_static_data_member_def_here)
414          << cast<VarDecl>(D)
415          << Active->InstantiationRange;
416      }
417      break;
418    }
419
420    case ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation: {
421      TemplateDecl *Template = cast<TemplateDecl>((Decl *)Active->Entity);
422      std::string TemplateArgsStr
423        = TemplateSpecializationType::PrintTemplateArgumentList(
424                                                         Active->TemplateArgs,
425                                                      Active->NumTemplateArgs,
426                                                      Context.PrintingPolicy);
427      Diags.Report(Active->PointOfInstantiation,
428                   diag::note_default_arg_instantiation_here)
429        << (Template->getNameAsString() + TemplateArgsStr)
430        << Active->InstantiationRange;
431      break;
432    }
433
434    case ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution: {
435      FunctionTemplateDecl *FnTmpl
436        = cast<FunctionTemplateDecl>((Decl *)Active->Entity);
437      Diags.Report(Active->PointOfInstantiation,
438                   diag::note_explicit_template_arg_substitution_here)
439        << FnTmpl
440        << getTemplateArgumentBindingsText(FnTmpl->getTemplateParameters(),
441                                           Active->TemplateArgs,
442                                           Active->NumTemplateArgs)
443        << Active->InstantiationRange;
444      break;
445    }
446
447    case ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution:
448      if (ClassTemplatePartialSpecializationDecl *PartialSpec
449            = dyn_cast<ClassTemplatePartialSpecializationDecl>(
450                                                    (Decl *)Active->Entity)) {
451        Diags.Report(Active->PointOfInstantiation,
452                     diag::note_partial_spec_deduct_instantiation_here)
453          << Context.getTypeDeclType(PartialSpec)
454          << getTemplateArgumentBindingsText(
455                                         PartialSpec->getTemplateParameters(),
456                                             Active->TemplateArgs,
457                                             Active->NumTemplateArgs)
458          << Active->InstantiationRange;
459      } else {
460        FunctionTemplateDecl *FnTmpl
461          = cast<FunctionTemplateDecl>((Decl *)Active->Entity);
462        Diags.Report(Active->PointOfInstantiation,
463                     diag::note_function_template_deduction_instantiation_here)
464          << FnTmpl
465          << getTemplateArgumentBindingsText(FnTmpl->getTemplateParameters(),
466                                             Active->TemplateArgs,
467                                             Active->NumTemplateArgs)
468          << Active->InstantiationRange;
469      }
470      break;
471
472    case ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation: {
473      ParmVarDecl *Param = cast<ParmVarDecl>((Decl *)Active->Entity);
474      FunctionDecl *FD = cast<FunctionDecl>(Param->getDeclContext());
475
476      std::string TemplateArgsStr
477        = TemplateSpecializationType::PrintTemplateArgumentList(
478                                                         Active->TemplateArgs,
479                                                      Active->NumTemplateArgs,
480                                                      Context.PrintingPolicy);
481      Diags.Report(Active->PointOfInstantiation,
482                   diag::note_default_function_arg_instantiation_here)
483        << (FD->getNameAsString() + TemplateArgsStr)
484        << Active->InstantiationRange;
485      break;
486    }
487
488    case ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution: {
489      NamedDecl *Parm = cast<NamedDecl>((Decl *)Active->Entity);
490      std::string Name;
491      if (!Parm->getName().empty())
492        Name = std::string(" '") + Parm->getName().str() + "'";
493
494      TemplateParameterList *TemplateParams = 0;
495      if (TemplateDecl *Template = dyn_cast<TemplateDecl>(Active->Template))
496        TemplateParams = Template->getTemplateParameters();
497      else
498        TemplateParams =
499          cast<ClassTemplatePartialSpecializationDecl>(Active->Template)
500                                                      ->getTemplateParameters();
501      Diags.Report(Active->PointOfInstantiation,
502                   diag::note_prior_template_arg_substitution)
503        << isa<TemplateTemplateParmDecl>(Parm)
504        << Name
505        << getTemplateArgumentBindingsText(TemplateParams,
506                                           Active->TemplateArgs,
507                                           Active->NumTemplateArgs)
508        << Active->InstantiationRange;
509      break;
510    }
511
512    case ActiveTemplateInstantiation::DefaultTemplateArgumentChecking: {
513      TemplateParameterList *TemplateParams = 0;
514      if (TemplateDecl *Template = dyn_cast<TemplateDecl>(Active->Template))
515        TemplateParams = Template->getTemplateParameters();
516      else
517        TemplateParams =
518          cast<ClassTemplatePartialSpecializationDecl>(Active->Template)
519                                                      ->getTemplateParameters();
520
521      Diags.Report(Active->PointOfInstantiation,
522                   diag::note_template_default_arg_checking)
523        << getTemplateArgumentBindingsText(TemplateParams,
524                                           Active->TemplateArgs,
525                                           Active->NumTemplateArgs)
526        << Active->InstantiationRange;
527      break;
528    }
529    }
530  }
531}
532
533TemplateDeductionInfo *Sema::isSFINAEContext() const {
534  using llvm::SmallVector;
535  for (SmallVector<ActiveTemplateInstantiation, 16>::const_reverse_iterator
536         Active = ActiveTemplateInstantiations.rbegin(),
537         ActiveEnd = ActiveTemplateInstantiations.rend();
538       Active != ActiveEnd;
539       ++Active)
540  {
541    switch(Active->Kind) {
542    case ActiveTemplateInstantiation::TemplateInstantiation:
543    case ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation:
544      // This is a template instantiation, so there is no SFINAE.
545      return 0;
546
547    case ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation:
548    case ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution:
549    case ActiveTemplateInstantiation::DefaultTemplateArgumentChecking:
550      // A default template argument instantiation and substitution into
551      // template parameters with arguments for prior parameters may or may
552      // not be a SFINAE context; look further up the stack.
553      break;
554
555    case ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution:
556    case ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution:
557      // We're either substitution explicitly-specified template arguments
558      // or deduced template arguments, so SFINAE applies.
559      assert(Active->DeductionInfo && "Missing deduction info pointer");
560      return Active->DeductionInfo;
561    }
562  }
563
564  return 0;
565}
566
567//===----------------------------------------------------------------------===/
568// Template Instantiation for Types
569//===----------------------------------------------------------------------===/
570namespace {
571  class TemplateInstantiator : public TreeTransform<TemplateInstantiator> {
572    const MultiLevelTemplateArgumentList &TemplateArgs;
573    SourceLocation Loc;
574    DeclarationName Entity;
575
576  public:
577    typedef TreeTransform<TemplateInstantiator> inherited;
578
579    TemplateInstantiator(Sema &SemaRef,
580                         const MultiLevelTemplateArgumentList &TemplateArgs,
581                         SourceLocation Loc,
582                         DeclarationName Entity)
583      : inherited(SemaRef), TemplateArgs(TemplateArgs), Loc(Loc),
584        Entity(Entity) { }
585
586    /// \brief Determine whether the given type \p T has already been
587    /// transformed.
588    ///
589    /// For the purposes of template instantiation, a type has already been
590    /// transformed if it is NULL or if it is not dependent.
591    bool AlreadyTransformed(QualType T);
592
593    /// \brief Returns the location of the entity being instantiated, if known.
594    SourceLocation getBaseLocation() { return Loc; }
595
596    /// \brief Returns the name of the entity being instantiated, if any.
597    DeclarationName getBaseEntity() { return Entity; }
598
599    /// \brief Sets the "base" location and entity when that
600    /// information is known based on another transformation.
601    void setBase(SourceLocation Loc, DeclarationName Entity) {
602      this->Loc = Loc;
603      this->Entity = Entity;
604    }
605
606    bool TryExpandParameterPacks(SourceLocation EllipsisLoc,
607                                 SourceRange PatternRange,
608                                 const UnexpandedParameterPack *Unexpanded,
609                                 unsigned NumUnexpanded,
610                                 bool &ShouldExpand,
611                                 unsigned &NumExpansions) {
612      return getSema().CheckParameterPacksForExpansion(EllipsisLoc,
613                                                       PatternRange, Unexpanded,
614                                                       NumUnexpanded,
615                                                       TemplateArgs,
616                                                       ShouldExpand,
617                                                       NumExpansions);
618    }
619
620    /// \brief Transform the given declaration by instantiating a reference to
621    /// this declaration.
622    Decl *TransformDecl(SourceLocation Loc, Decl *D);
623
624    /// \brief Transform the definition of the given declaration by
625    /// instantiating it.
626    Decl *TransformDefinition(SourceLocation Loc, Decl *D);
627
628    /// \bried Transform the first qualifier within a scope by instantiating the
629    /// declaration.
630    NamedDecl *TransformFirstQualifierInScope(NamedDecl *D, SourceLocation Loc);
631
632    /// \brief Rebuild the exception declaration and register the declaration
633    /// as an instantiated local.
634    VarDecl *RebuildExceptionDecl(VarDecl *ExceptionDecl,
635                                  TypeSourceInfo *Declarator,
636                                  IdentifierInfo *Name,
637                                  SourceLocation Loc);
638
639    /// \brief Rebuild the Objective-C exception declaration and register the
640    /// declaration as an instantiated local.
641    VarDecl *RebuildObjCExceptionDecl(VarDecl *ExceptionDecl,
642                                      TypeSourceInfo *TSInfo, QualType T);
643
644    /// \brief Check for tag mismatches when instantiating an
645    /// elaborated type.
646    QualType RebuildElaboratedType(SourceLocation KeywordLoc,
647                                   ElaboratedTypeKeyword Keyword,
648                                   NestedNameSpecifier *NNS, QualType T);
649
650    ExprResult TransformPredefinedExpr(PredefinedExpr *E);
651    ExprResult TransformDeclRefExpr(DeclRefExpr *E);
652    ExprResult TransformCXXDefaultArgExpr(CXXDefaultArgExpr *E);
653    ExprResult TransformTemplateParmRefExpr(DeclRefExpr *E,
654                                            NonTypeTemplateParmDecl *D);
655
656    QualType TransformFunctionProtoType(TypeLocBuilder &TLB,
657                                        FunctionProtoTypeLoc TL);
658    ParmVarDecl *TransformFunctionTypeParam(ParmVarDecl *OldParm);
659
660    /// \brief Transforms a template type parameter type by performing
661    /// substitution of the corresponding template type argument.
662    QualType TransformTemplateTypeParmType(TypeLocBuilder &TLB,
663                                           TemplateTypeParmTypeLoc TL);
664
665    ExprResult TransformCallExpr(CallExpr *CE) {
666      getSema().CallsUndergoingInstantiation.push_back(CE);
667      ExprResult Result =
668          TreeTransform<TemplateInstantiator>::TransformCallExpr(CE);
669      getSema().CallsUndergoingInstantiation.pop_back();
670      return move(Result);
671    }
672  };
673}
674
675bool TemplateInstantiator::AlreadyTransformed(QualType T) {
676  if (T.isNull())
677    return true;
678
679  if (T->isDependentType() || T->isVariablyModifiedType())
680    return false;
681
682  getSema().MarkDeclarationsReferencedInType(Loc, T);
683  return true;
684}
685
686Decl *TemplateInstantiator::TransformDecl(SourceLocation Loc, Decl *D) {
687  if (!D)
688    return 0;
689
690  if (TemplateTemplateParmDecl *TTP = dyn_cast<TemplateTemplateParmDecl>(D)) {
691    if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
692      // If the corresponding template argument is NULL or non-existent, it's
693      // because we are performing instantiation from explicitly-specified
694      // template arguments in a function template, but there were some
695      // arguments left unspecified.
696      if (!TemplateArgs.hasTemplateArgument(TTP->getDepth(),
697                                            TTP->getPosition()))
698        return D;
699
700      TemplateArgument Arg = TemplateArgs(TTP->getDepth(), TTP->getPosition());
701
702      if (TTP->isParameterPack()) {
703        assert(Arg.getKind() == TemplateArgument::Pack &&
704               "Missing argument pack");
705
706        if (getSema().ArgumentPackSubstitutionIndex == -1) {
707          // FIXME: Variadic templates fun case.
708          getSema().Diag(Loc,  diag::err_pack_expansion_mismatch_unsupported);
709          return 0;
710        }
711
712        Arg = Arg.pack_begin()[getSema().ArgumentPackSubstitutionIndex];
713      }
714
715      TemplateName Template = Arg.getAsTemplate();
716      assert(!Template.isNull() && Template.getAsTemplateDecl() &&
717             "Wrong kind of template template argument");
718      return Template.getAsTemplateDecl();
719    }
720
721    // Fall through to find the instantiated declaration for this template
722    // template parameter.
723  }
724
725  return SemaRef.FindInstantiatedDecl(Loc, cast<NamedDecl>(D), TemplateArgs);
726}
727
728Decl *TemplateInstantiator::TransformDefinition(SourceLocation Loc, Decl *D) {
729  Decl *Inst = getSema().SubstDecl(D, getSema().CurContext, TemplateArgs);
730  if (!Inst)
731    return 0;
732
733  getSema().CurrentInstantiationScope->InstantiatedLocal(D, Inst);
734  return Inst;
735}
736
737NamedDecl *
738TemplateInstantiator::TransformFirstQualifierInScope(NamedDecl *D,
739                                                     SourceLocation Loc) {
740  // If the first part of the nested-name-specifier was a template type
741  // parameter, instantiate that type parameter down to a tag type.
742  if (TemplateTypeParmDecl *TTPD = dyn_cast_or_null<TemplateTypeParmDecl>(D)) {
743    const TemplateTypeParmType *TTP
744      = cast<TemplateTypeParmType>(getSema().Context.getTypeDeclType(TTPD));
745
746    if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
747      // FIXME: This needs testing w/ member access expressions.
748      TemplateArgument Arg = TemplateArgs(TTP->getDepth(), TTP->getIndex());
749
750      if (TTP->isParameterPack()) {
751        assert(Arg.getKind() == TemplateArgument::Pack &&
752               "Missing argument pack");
753
754        if (getSema().ArgumentPackSubstitutionIndex == -1) {
755          // FIXME: Variadic templates fun case.
756          getSema().Diag(Loc, diag::err_pack_expansion_mismatch_unsupported);
757          return 0;
758        }
759
760        Arg = Arg.pack_begin()[getSema().ArgumentPackSubstitutionIndex];
761      }
762
763      QualType T = Arg.getAsType();
764      if (T.isNull())
765        return cast_or_null<NamedDecl>(TransformDecl(Loc, D));
766
767      if (const TagType *Tag = T->getAs<TagType>())
768        return Tag->getDecl();
769
770      // The resulting type is not a tag; complain.
771      getSema().Diag(Loc, diag::err_nested_name_spec_non_tag) << T;
772      return 0;
773    }
774  }
775
776  return cast_or_null<NamedDecl>(TransformDecl(Loc, D));
777}
778
779VarDecl *
780TemplateInstantiator::RebuildExceptionDecl(VarDecl *ExceptionDecl,
781                                           TypeSourceInfo *Declarator,
782                                           IdentifierInfo *Name,
783                                           SourceLocation Loc) {
784  VarDecl *Var = inherited::RebuildExceptionDecl(ExceptionDecl, Declarator,
785                                                 Name, Loc);
786  if (Var)
787    getSema().CurrentInstantiationScope->InstantiatedLocal(ExceptionDecl, Var);
788  return Var;
789}
790
791VarDecl *TemplateInstantiator::RebuildObjCExceptionDecl(VarDecl *ExceptionDecl,
792                                                        TypeSourceInfo *TSInfo,
793                                                        QualType T) {
794  VarDecl *Var = inherited::RebuildObjCExceptionDecl(ExceptionDecl, TSInfo, T);
795  if (Var)
796    getSema().CurrentInstantiationScope->InstantiatedLocal(ExceptionDecl, Var);
797  return Var;
798}
799
800QualType
801TemplateInstantiator::RebuildElaboratedType(SourceLocation KeywordLoc,
802                                            ElaboratedTypeKeyword Keyword,
803                                            NestedNameSpecifier *NNS,
804                                            QualType T) {
805  if (const TagType *TT = T->getAs<TagType>()) {
806    TagDecl* TD = TT->getDecl();
807
808    SourceLocation TagLocation = KeywordLoc;
809
810    // FIXME: type might be anonymous.
811    IdentifierInfo *Id = TD->getIdentifier();
812
813    // TODO: should we even warn on struct/class mismatches for this?  Seems
814    // like it's likely to produce a lot of spurious errors.
815    if (Keyword != ETK_None && Keyword != ETK_Typename) {
816      TagTypeKind Kind = TypeWithKeyword::getTagTypeKindForKeyword(Keyword);
817      if (!SemaRef.isAcceptableTagRedeclaration(TD, Kind, TagLocation, *Id)) {
818        SemaRef.Diag(TagLocation, diag::err_use_with_wrong_tag)
819          << Id
820          << FixItHint::CreateReplacement(SourceRange(TagLocation),
821                                          TD->getKindName());
822        SemaRef.Diag(TD->getLocation(), diag::note_previous_use);
823      }
824    }
825  }
826
827  return TreeTransform<TemplateInstantiator>::RebuildElaboratedType(KeywordLoc,
828                                                                    Keyword,
829                                                                    NNS, T);
830}
831
832ExprResult
833TemplateInstantiator::TransformPredefinedExpr(PredefinedExpr *E) {
834  if (!E->isTypeDependent())
835    return SemaRef.Owned(E);
836
837  FunctionDecl *currentDecl = getSema().getCurFunctionDecl();
838  assert(currentDecl && "Must have current function declaration when "
839                        "instantiating.");
840
841  PredefinedExpr::IdentType IT = E->getIdentType();
842
843  unsigned Length = PredefinedExpr::ComputeName(IT, currentDecl).length();
844
845  llvm::APInt LengthI(32, Length + 1);
846  QualType ResTy = getSema().Context.CharTy.withConst();
847  ResTy = getSema().Context.getConstantArrayType(ResTy, LengthI,
848                                                 ArrayType::Normal, 0);
849  PredefinedExpr *PE =
850    new (getSema().Context) PredefinedExpr(E->getLocation(), ResTy, IT);
851  return getSema().Owned(PE);
852}
853
854ExprResult
855TemplateInstantiator::TransformTemplateParmRefExpr(DeclRefExpr *E,
856                                               NonTypeTemplateParmDecl *NTTP) {
857  // If the corresponding template argument is NULL or non-existent, it's
858  // because we are performing instantiation from explicitly-specified
859  // template arguments in a function template, but there were some
860  // arguments left unspecified.
861  if (!TemplateArgs.hasTemplateArgument(NTTP->getDepth(),
862                                        NTTP->getPosition()))
863    return SemaRef.Owned(E);
864
865  TemplateArgument Arg = TemplateArgs(NTTP->getDepth(), NTTP->getPosition());
866  if (NTTP->isParameterPack()) {
867    assert(Arg.getKind() == TemplateArgument::Pack &&
868           "Missing argument pack");
869
870    if (getSema().ArgumentPackSubstitutionIndex == -1) {
871      // FIXME: Variadic templates fun case.
872      getSema().Diag(Loc, diag::err_pack_expansion_mismatch_unsupported);
873      return ExprError();
874    }
875
876    Arg = Arg.pack_begin()[getSema().ArgumentPackSubstitutionIndex];
877  }
878
879  // The template argument itself might be an expression, in which
880  // case we just return that expression.
881  if (Arg.getKind() == TemplateArgument::Expression)
882    return SemaRef.Owned(Arg.getAsExpr());
883
884  if (Arg.getKind() == TemplateArgument::Declaration) {
885    ValueDecl *VD = cast<ValueDecl>(Arg.getAsDecl());
886
887    // Find the instantiation of the template argument.  This is
888    // required for nested templates.
889    VD = cast_or_null<ValueDecl>(
890                            getSema().FindInstantiatedDecl(E->getLocation(),
891                                                           VD, TemplateArgs));
892    if (!VD)
893      return ExprError();
894
895    // Derive the type we want the substituted decl to have.  This had
896    // better be non-dependent, or these checks will have serious problems.
897    QualType TargetType = SemaRef.SubstType(NTTP->getType(), TemplateArgs,
898                                            E->getLocation(),
899                                            DeclarationName());
900    assert(!TargetType.isNull() && "type substitution failed for param type");
901    assert(!TargetType->isDependentType() && "param type still dependent");
902    return SemaRef.BuildExpressionFromDeclTemplateArgument(Arg,
903                                                           TargetType,
904                                                           E->getLocation());
905  }
906
907  return SemaRef.BuildExpressionFromIntegralTemplateArgument(Arg,
908                                                E->getSourceRange().getBegin());
909}
910
911
912ExprResult
913TemplateInstantiator::TransformDeclRefExpr(DeclRefExpr *E) {
914  NamedDecl *D = E->getDecl();
915  if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D)) {
916    if (NTTP->getDepth() < TemplateArgs.getNumLevels())
917      return TransformTemplateParmRefExpr(E, NTTP);
918
919    // We have a non-type template parameter that isn't fully substituted;
920    // FindInstantiatedDecl will find it in the local instantiation scope.
921  }
922
923  return TreeTransform<TemplateInstantiator>::TransformDeclRefExpr(E);
924}
925
926ExprResult TemplateInstantiator::TransformCXXDefaultArgExpr(
927    CXXDefaultArgExpr *E) {
928  assert(!cast<FunctionDecl>(E->getParam()->getDeclContext())->
929             getDescribedFunctionTemplate() &&
930         "Default arg expressions are never formed in dependent cases.");
931  return SemaRef.BuildCXXDefaultArgExpr(E->getUsedLocation(),
932                           cast<FunctionDecl>(E->getParam()->getDeclContext()),
933                                        E->getParam());
934}
935
936QualType TemplateInstantiator::TransformFunctionProtoType(TypeLocBuilder &TLB,
937                                                      FunctionProtoTypeLoc TL) {
938  // We need a local instantiation scope for this function prototype.
939  LocalInstantiationScope Scope(SemaRef, /*CombineWithOuterScope=*/true);
940  return inherited::TransformFunctionProtoType(TLB, TL);
941}
942
943ParmVarDecl *
944TemplateInstantiator::TransformFunctionTypeParam(ParmVarDecl *OldParm) {
945  return SemaRef.SubstParmVarDecl(OldParm, TemplateArgs);
946}
947
948QualType
949TemplateInstantiator::TransformTemplateTypeParmType(TypeLocBuilder &TLB,
950                                                TemplateTypeParmTypeLoc TL) {
951  TemplateTypeParmType *T = TL.getTypePtr();
952  if (T->getDepth() < TemplateArgs.getNumLevels()) {
953    // Replace the template type parameter with its corresponding
954    // template argument.
955
956    // If the corresponding template argument is NULL or doesn't exist, it's
957    // because we are performing instantiation from explicitly-specified
958    // template arguments in a function template class, but there were some
959    // arguments left unspecified.
960    if (!TemplateArgs.hasTemplateArgument(T->getDepth(), T->getIndex())) {
961      TemplateTypeParmTypeLoc NewTL
962        = TLB.push<TemplateTypeParmTypeLoc>(TL.getType());
963      NewTL.setNameLoc(TL.getNameLoc());
964      return TL.getType();
965    }
966
967    TemplateArgument Arg = TemplateArgs(T->getDepth(), T->getIndex());
968
969    if (T->isParameterPack()) {
970      assert(Arg.getKind() == TemplateArgument::Pack &&
971             "Missing argument pack");
972
973      if (getSema().ArgumentPackSubstitutionIndex == -1) {
974        // FIXME: Variadic templates fun case.
975        getSema().Diag(TL.getSourceRange().getBegin(),
976                       diag::err_pack_expansion_mismatch_unsupported);
977        return QualType();
978      }
979
980      Arg = Arg.pack_begin()[getSema().ArgumentPackSubstitutionIndex];
981    }
982
983    assert(Arg.getKind() == TemplateArgument::Type &&
984           "Template argument kind mismatch");
985
986    QualType Replacement = Arg.getAsType();
987
988    // TODO: only do this uniquing once, at the start of instantiation.
989    QualType Result
990      = getSema().Context.getSubstTemplateTypeParmType(T, Replacement);
991    SubstTemplateTypeParmTypeLoc NewTL
992      = TLB.push<SubstTemplateTypeParmTypeLoc>(Result);
993    NewTL.setNameLoc(TL.getNameLoc());
994    return Result;
995  }
996
997  // The template type parameter comes from an inner template (e.g.,
998  // the template parameter list of a member template inside the
999  // template we are instantiating). Create a new template type
1000  // parameter with the template "level" reduced by one.
1001  QualType Result
1002    = getSema().Context.getTemplateTypeParmType(T->getDepth()
1003                                                 - TemplateArgs.getNumLevels(),
1004                                                T->getIndex(),
1005                                                T->isParameterPack(),
1006                                                T->getName());
1007  TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result);
1008  NewTL.setNameLoc(TL.getNameLoc());
1009  return Result;
1010}
1011
1012/// \brief Perform substitution on the type T with a given set of template
1013/// arguments.
1014///
1015/// This routine substitutes the given template arguments into the
1016/// type T and produces the instantiated type.
1017///
1018/// \param T the type into which the template arguments will be
1019/// substituted. If this type is not dependent, it will be returned
1020/// immediately.
1021///
1022/// \param TemplateArgs the template arguments that will be
1023/// substituted for the top-level template parameters within T.
1024///
1025/// \param Loc the location in the source code where this substitution
1026/// is being performed. It will typically be the location of the
1027/// declarator (if we're instantiating the type of some declaration)
1028/// or the location of the type in the source code (if, e.g., we're
1029/// instantiating the type of a cast expression).
1030///
1031/// \param Entity the name of the entity associated with a declaration
1032/// being instantiated (if any). May be empty to indicate that there
1033/// is no such entity (if, e.g., this is a type that occurs as part of
1034/// a cast expression) or that the entity has no name (e.g., an
1035/// unnamed function parameter).
1036///
1037/// \returns If the instantiation succeeds, the instantiated
1038/// type. Otherwise, produces diagnostics and returns a NULL type.
1039TypeSourceInfo *Sema::SubstType(TypeSourceInfo *T,
1040                                const MultiLevelTemplateArgumentList &Args,
1041                                SourceLocation Loc,
1042                                DeclarationName Entity) {
1043  assert(!ActiveTemplateInstantiations.empty() &&
1044         "Cannot perform an instantiation without some context on the "
1045         "instantiation stack");
1046
1047  if (!T->getType()->isDependentType() &&
1048      !T->getType()->isVariablyModifiedType())
1049    return T;
1050
1051  TemplateInstantiator Instantiator(*this, Args, Loc, Entity);
1052  return Instantiator.TransformType(T);
1053}
1054
1055/// Deprecated form of the above.
1056QualType Sema::SubstType(QualType T,
1057                         const MultiLevelTemplateArgumentList &TemplateArgs,
1058                         SourceLocation Loc, DeclarationName Entity) {
1059  assert(!ActiveTemplateInstantiations.empty() &&
1060         "Cannot perform an instantiation without some context on the "
1061         "instantiation stack");
1062
1063  // If T is not a dependent type or a variably-modified type, there
1064  // is nothing to do.
1065  if (!T->isDependentType() && !T->isVariablyModifiedType())
1066    return T;
1067
1068  TemplateInstantiator Instantiator(*this, TemplateArgs, Loc, Entity);
1069  return Instantiator.TransformType(T);
1070}
1071
1072static bool NeedsInstantiationAsFunctionType(TypeSourceInfo *T) {
1073  if (T->getType()->isDependentType() || T->getType()->isVariablyModifiedType())
1074    return true;
1075
1076  TypeLoc TL = T->getTypeLoc().IgnoreParens();
1077  if (!isa<FunctionProtoTypeLoc>(TL))
1078    return false;
1079
1080  FunctionProtoTypeLoc FP = cast<FunctionProtoTypeLoc>(TL);
1081  for (unsigned I = 0, E = FP.getNumArgs(); I != E; ++I) {
1082    ParmVarDecl *P = FP.getArg(I);
1083
1084    // TODO: currently we always rebuild expressions.  When we
1085    // properly get lazier about this, we should use the same
1086    // logic to avoid rebuilding prototypes here.
1087    if (P->hasDefaultArg())
1088      return true;
1089  }
1090
1091  return false;
1092}
1093
1094/// A form of SubstType intended specifically for instantiating the
1095/// type of a FunctionDecl.  Its purpose is solely to force the
1096/// instantiation of default-argument expressions.
1097TypeSourceInfo *Sema::SubstFunctionDeclType(TypeSourceInfo *T,
1098                                const MultiLevelTemplateArgumentList &Args,
1099                                SourceLocation Loc,
1100                                DeclarationName Entity) {
1101  assert(!ActiveTemplateInstantiations.empty() &&
1102         "Cannot perform an instantiation without some context on the "
1103         "instantiation stack");
1104
1105  if (!NeedsInstantiationAsFunctionType(T))
1106    return T;
1107
1108  TemplateInstantiator Instantiator(*this, Args, Loc, Entity);
1109
1110  TypeLocBuilder TLB;
1111
1112  TypeLoc TL = T->getTypeLoc();
1113  TLB.reserve(TL.getFullDataSize());
1114
1115  QualType Result = Instantiator.TransformType(TLB, TL);
1116  if (Result.isNull())
1117    return 0;
1118
1119  return TLB.getTypeSourceInfo(Context, Result);
1120}
1121
1122ParmVarDecl *Sema::SubstParmVarDecl(ParmVarDecl *OldParm,
1123                          const MultiLevelTemplateArgumentList &TemplateArgs) {
1124  TypeSourceInfo *OldDI = OldParm->getTypeSourceInfo();
1125  TypeSourceInfo *NewDI = SubstType(OldDI, TemplateArgs, OldParm->getLocation(),
1126                                    OldParm->getDeclName());
1127  if (!NewDI)
1128    return 0;
1129
1130  if (NewDI->getType()->isVoidType()) {
1131    Diag(OldParm->getLocation(), diag::err_param_with_void_type);
1132    return 0;
1133  }
1134
1135  ParmVarDecl *NewParm = CheckParameter(Context.getTranslationUnitDecl(),
1136                                        NewDI, NewDI->getType(),
1137                                        OldParm->getIdentifier(),
1138                                        OldParm->getLocation(),
1139                                        OldParm->getStorageClass(),
1140                                        OldParm->getStorageClassAsWritten());
1141  if (!NewParm)
1142    return 0;
1143
1144  // Mark the (new) default argument as uninstantiated (if any).
1145  if (OldParm->hasUninstantiatedDefaultArg()) {
1146    Expr *Arg = OldParm->getUninstantiatedDefaultArg();
1147    NewParm->setUninstantiatedDefaultArg(Arg);
1148  } else if (OldParm->hasUnparsedDefaultArg()) {
1149    NewParm->setUnparsedDefaultArg();
1150    UnparsedDefaultArgInstantiations[OldParm].push_back(NewParm);
1151  } else if (Expr *Arg = OldParm->getDefaultArg())
1152    NewParm->setUninstantiatedDefaultArg(Arg);
1153
1154  NewParm->setHasInheritedDefaultArg(OldParm->hasInheritedDefaultArg());
1155
1156  CurrentInstantiationScope->InstantiatedLocal(OldParm, NewParm);
1157  // FIXME: OldParm may come from a FunctionProtoType, in which case CurContext
1158  // can be anything, is this right ?
1159  NewParm->setDeclContext(CurContext);
1160
1161  return NewParm;
1162}
1163
1164/// \brief Perform substitution on the base class specifiers of the
1165/// given class template specialization.
1166///
1167/// Produces a diagnostic and returns true on error, returns false and
1168/// attaches the instantiated base classes to the class template
1169/// specialization if successful.
1170bool
1171Sema::SubstBaseSpecifiers(CXXRecordDecl *Instantiation,
1172                          CXXRecordDecl *Pattern,
1173                          const MultiLevelTemplateArgumentList &TemplateArgs) {
1174  bool Invalid = false;
1175  llvm::SmallVector<CXXBaseSpecifier*, 4> InstantiatedBases;
1176  for (ClassTemplateSpecializationDecl::base_class_iterator
1177         Base = Pattern->bases_begin(), BaseEnd = Pattern->bases_end();
1178       Base != BaseEnd; ++Base) {
1179    if (!Base->getType()->isDependentType()) {
1180      InstantiatedBases.push_back(new (Context) CXXBaseSpecifier(*Base));
1181      continue;
1182    }
1183
1184    SourceLocation EllipsisLoc;
1185    if (Base->isPackExpansion()) {
1186      // This is a pack expansion. See whether we should expand it now, or
1187      // wait until later.
1188      llvm::SmallVector<UnexpandedParameterPack, 2> Unexpanded;
1189      collectUnexpandedParameterPacks(Base->getTypeSourceInfo()->getTypeLoc(),
1190                                      Unexpanded);
1191      bool ShouldExpand = false;
1192      unsigned NumExpansions = 0;
1193      if (CheckParameterPacksForExpansion(Base->getEllipsisLoc(),
1194                                          Base->getSourceRange(),
1195                                          Unexpanded.data(), Unexpanded.size(),
1196                                          TemplateArgs, ShouldExpand,
1197                                          NumExpansions)) {
1198        Invalid = true;
1199        continue;
1200      }
1201
1202      // If we should expand this pack expansion now, do so.
1203      if (ShouldExpand) {
1204        for (unsigned I = 0; I != NumExpansions; ++I) {
1205            Sema::ArgumentPackSubstitutionIndexRAII SubstIndex(*this, I);
1206
1207          TypeSourceInfo *BaseTypeLoc = SubstType(Base->getTypeSourceInfo(),
1208                                                  TemplateArgs,
1209                                              Base->getSourceRange().getBegin(),
1210                                                  DeclarationName());
1211          if (!BaseTypeLoc) {
1212            Invalid = true;
1213            continue;
1214          }
1215
1216          if (CXXBaseSpecifier *InstantiatedBase
1217                = CheckBaseSpecifier(Instantiation,
1218                                     Base->getSourceRange(),
1219                                     Base->isVirtual(),
1220                                     Base->getAccessSpecifierAsWritten(),
1221                                     BaseTypeLoc,
1222                                     SourceLocation()))
1223            InstantiatedBases.push_back(InstantiatedBase);
1224          else
1225            Invalid = true;
1226        }
1227
1228        continue;
1229      }
1230
1231      // The resulting base specifier will (still) be a pack expansion.
1232      EllipsisLoc = Base->getEllipsisLoc();
1233    }
1234
1235    Sema::ArgumentPackSubstitutionIndexRAII SubstIndex(*this, -1);
1236    TypeSourceInfo *BaseTypeLoc = SubstType(Base->getTypeSourceInfo(),
1237                                            TemplateArgs,
1238                                            Base->getSourceRange().getBegin(),
1239                                            DeclarationName());
1240    if (!BaseTypeLoc) {
1241      Invalid = true;
1242      continue;
1243    }
1244
1245    if (CXXBaseSpecifier *InstantiatedBase
1246          = CheckBaseSpecifier(Instantiation,
1247                               Base->getSourceRange(),
1248                               Base->isVirtual(),
1249                               Base->getAccessSpecifierAsWritten(),
1250                               BaseTypeLoc,
1251                               EllipsisLoc))
1252      InstantiatedBases.push_back(InstantiatedBase);
1253    else
1254      Invalid = true;
1255  }
1256
1257  if (!Invalid &&
1258      AttachBaseSpecifiers(Instantiation, InstantiatedBases.data(),
1259                           InstantiatedBases.size()))
1260    Invalid = true;
1261
1262  return Invalid;
1263}
1264
1265/// \brief Instantiate the definition of a class from a given pattern.
1266///
1267/// \param PointOfInstantiation The point of instantiation within the
1268/// source code.
1269///
1270/// \param Instantiation is the declaration whose definition is being
1271/// instantiated. This will be either a class template specialization
1272/// or a member class of a class template specialization.
1273///
1274/// \param Pattern is the pattern from which the instantiation
1275/// occurs. This will be either the declaration of a class template or
1276/// the declaration of a member class of a class template.
1277///
1278/// \param TemplateArgs The template arguments to be substituted into
1279/// the pattern.
1280///
1281/// \param TSK the kind of implicit or explicit instantiation to perform.
1282///
1283/// \param Complain whether to complain if the class cannot be instantiated due
1284/// to the lack of a definition.
1285///
1286/// \returns true if an error occurred, false otherwise.
1287bool
1288Sema::InstantiateClass(SourceLocation PointOfInstantiation,
1289                       CXXRecordDecl *Instantiation, CXXRecordDecl *Pattern,
1290                       const MultiLevelTemplateArgumentList &TemplateArgs,
1291                       TemplateSpecializationKind TSK,
1292                       bool Complain) {
1293  bool Invalid = false;
1294
1295  CXXRecordDecl *PatternDef
1296    = cast_or_null<CXXRecordDecl>(Pattern->getDefinition());
1297  if (!PatternDef) {
1298    if (!Complain) {
1299      // Say nothing
1300    } else if (Pattern == Instantiation->getInstantiatedFromMemberClass()) {
1301      Diag(PointOfInstantiation,
1302           diag::err_implicit_instantiate_member_undefined)
1303        << Context.getTypeDeclType(Instantiation);
1304      Diag(Pattern->getLocation(), diag::note_member_of_template_here);
1305    } else {
1306      Diag(PointOfInstantiation, diag::err_template_instantiate_undefined)
1307        << (TSK != TSK_ImplicitInstantiation)
1308        << Context.getTypeDeclType(Instantiation);
1309      Diag(Pattern->getLocation(), diag::note_template_decl_here);
1310    }
1311    return true;
1312  }
1313  Pattern = PatternDef;
1314
1315  // \brief Record the point of instantiation.
1316  if (MemberSpecializationInfo *MSInfo
1317        = Instantiation->getMemberSpecializationInfo()) {
1318    MSInfo->setTemplateSpecializationKind(TSK);
1319    MSInfo->setPointOfInstantiation(PointOfInstantiation);
1320  } else if (ClassTemplateSpecializationDecl *Spec
1321               = dyn_cast<ClassTemplateSpecializationDecl>(Instantiation)) {
1322    Spec->setTemplateSpecializationKind(TSK);
1323    Spec->setPointOfInstantiation(PointOfInstantiation);
1324  }
1325
1326  InstantiatingTemplate Inst(*this, PointOfInstantiation, Instantiation);
1327  if (Inst)
1328    return true;
1329
1330  // Enter the scope of this instantiation. We don't use
1331  // PushDeclContext because we don't have a scope.
1332  ContextRAII SavedContext(*this, Instantiation);
1333  EnterExpressionEvaluationContext EvalContext(*this,
1334                                               Sema::PotentiallyEvaluated);
1335
1336  // If this is an instantiation of a local class, merge this local
1337  // instantiation scope with the enclosing scope. Otherwise, every
1338  // instantiation of a class has its own local instantiation scope.
1339  bool MergeWithParentScope = !Instantiation->isDefinedOutsideFunctionOrMethod();
1340  LocalInstantiationScope Scope(*this, MergeWithParentScope);
1341
1342  // Pull attributes from the pattern onto the instantiation.
1343  InstantiateAttrs(TemplateArgs, Pattern, Instantiation);
1344
1345  // Start the definition of this instantiation.
1346  Instantiation->startDefinition();
1347
1348  Instantiation->setTagKind(Pattern->getTagKind());
1349
1350  // Do substitution on the base class specifiers.
1351  if (SubstBaseSpecifiers(Instantiation, Pattern, TemplateArgs))
1352    Invalid = true;
1353
1354  TemplateDeclInstantiator Instantiator(*this, Instantiation, TemplateArgs);
1355  llvm::SmallVector<Decl*, 4> Fields;
1356  for (RecordDecl::decl_iterator Member = Pattern->decls_begin(),
1357         MemberEnd = Pattern->decls_end();
1358       Member != MemberEnd; ++Member) {
1359    // Don't instantiate members not belonging in this semantic context.
1360    // e.g. for:
1361    // @code
1362    //    template <int i> class A {
1363    //      class B *g;
1364    //    };
1365    // @endcode
1366    // 'class B' has the template as lexical context but semantically it is
1367    // introduced in namespace scope.
1368    if ((*Member)->getDeclContext() != Pattern)
1369      continue;
1370
1371    if ((*Member)->isInvalidDecl()) {
1372      Invalid = true;
1373      continue;
1374    }
1375
1376    Decl *NewMember = Instantiator.Visit(*Member);
1377    if (NewMember) {
1378      if (FieldDecl *Field = dyn_cast<FieldDecl>(NewMember))
1379        Fields.push_back(Field);
1380      else if (NewMember->isInvalidDecl())
1381        Invalid = true;
1382    } else {
1383      // FIXME: Eventually, a NULL return will mean that one of the
1384      // instantiations was a semantic disaster, and we'll want to set Invalid =
1385      // true. For now, we expect to skip some members that we can't yet handle.
1386    }
1387  }
1388
1389  // Finish checking fields.
1390  ActOnFields(0, Instantiation->getLocation(), Instantiation,
1391              Fields.data(), Fields.size(), SourceLocation(), SourceLocation(),
1392              0);
1393  CheckCompletedCXXClass(Instantiation);
1394  if (Instantiation->isInvalidDecl())
1395    Invalid = true;
1396  else {
1397    // Instantiate any out-of-line class template partial
1398    // specializations now.
1399    for (TemplateDeclInstantiator::delayed_partial_spec_iterator
1400              P = Instantiator.delayed_partial_spec_begin(),
1401           PEnd = Instantiator.delayed_partial_spec_end();
1402         P != PEnd; ++P) {
1403      if (!Instantiator.InstantiateClassTemplatePartialSpecialization(
1404                                                                P->first,
1405                                                                P->second)) {
1406        Invalid = true;
1407        break;
1408      }
1409    }
1410  }
1411
1412  // Exit the scope of this instantiation.
1413  SavedContext.pop();
1414
1415  if (!Invalid) {
1416    Consumer.HandleTagDeclDefinition(Instantiation);
1417
1418    // Always emit the vtable for an explicit instantiation definition
1419    // of a polymorphic class template specialization.
1420    if (TSK == TSK_ExplicitInstantiationDefinition)
1421      MarkVTableUsed(PointOfInstantiation, Instantiation, true);
1422  }
1423
1424  return Invalid;
1425}
1426
1427namespace {
1428  /// \brief A partial specialization whose template arguments have matched
1429  /// a given template-id.
1430  struct PartialSpecMatchResult {
1431    ClassTemplatePartialSpecializationDecl *Partial;
1432    TemplateArgumentList *Args;
1433  };
1434}
1435
1436bool
1437Sema::InstantiateClassTemplateSpecialization(
1438                           SourceLocation PointOfInstantiation,
1439                           ClassTemplateSpecializationDecl *ClassTemplateSpec,
1440                           TemplateSpecializationKind TSK,
1441                           bool Complain) {
1442  // Perform the actual instantiation on the canonical declaration.
1443  ClassTemplateSpec = cast<ClassTemplateSpecializationDecl>(
1444                                         ClassTemplateSpec->getCanonicalDecl());
1445
1446  // Check whether we have already instantiated or specialized this class
1447  // template specialization.
1448  if (ClassTemplateSpec->getSpecializationKind() != TSK_Undeclared) {
1449    if (ClassTemplateSpec->getSpecializationKind() ==
1450          TSK_ExplicitInstantiationDeclaration &&
1451        TSK == TSK_ExplicitInstantiationDefinition) {
1452      // An explicit instantiation definition follows an explicit instantiation
1453      // declaration (C++0x [temp.explicit]p10); go ahead and perform the
1454      // explicit instantiation.
1455      ClassTemplateSpec->setSpecializationKind(TSK);
1456
1457      // If this is an explicit instantiation definition, mark the
1458      // vtable as used.
1459      if (TSK == TSK_ExplicitInstantiationDefinition)
1460        MarkVTableUsed(PointOfInstantiation, ClassTemplateSpec, true);
1461
1462      return false;
1463    }
1464
1465    // We can only instantiate something that hasn't already been
1466    // instantiated or specialized. Fail without any diagnostics: our
1467    // caller will provide an error message.
1468    return true;
1469  }
1470
1471  if (ClassTemplateSpec->isInvalidDecl())
1472    return true;
1473
1474  ClassTemplateDecl *Template = ClassTemplateSpec->getSpecializedTemplate();
1475  CXXRecordDecl *Pattern = 0;
1476
1477  // C++ [temp.class.spec.match]p1:
1478  //   When a class template is used in a context that requires an
1479  //   instantiation of the class, it is necessary to determine
1480  //   whether the instantiation is to be generated using the primary
1481  //   template or one of the partial specializations. This is done by
1482  //   matching the template arguments of the class template
1483  //   specialization with the template argument lists of the partial
1484  //   specializations.
1485  typedef PartialSpecMatchResult MatchResult;
1486  llvm::SmallVector<MatchResult, 4> Matched;
1487  llvm::SmallVector<ClassTemplatePartialSpecializationDecl *, 4> PartialSpecs;
1488  Template->getPartialSpecializations(PartialSpecs);
1489  for (unsigned I = 0, N = PartialSpecs.size(); I != N; ++I) {
1490    ClassTemplatePartialSpecializationDecl *Partial = PartialSpecs[I];
1491    TemplateDeductionInfo Info(Context, PointOfInstantiation);
1492    if (TemplateDeductionResult Result
1493          = DeduceTemplateArguments(Partial,
1494                                    ClassTemplateSpec->getTemplateArgs(),
1495                                    Info)) {
1496      // FIXME: Store the failed-deduction information for use in
1497      // diagnostics, later.
1498      (void)Result;
1499    } else {
1500      Matched.push_back(PartialSpecMatchResult());
1501      Matched.back().Partial = Partial;
1502      Matched.back().Args = Info.take();
1503    }
1504  }
1505
1506  if (Matched.size() >= 1) {
1507    llvm::SmallVector<MatchResult, 4>::iterator Best = Matched.begin();
1508    if (Matched.size() == 1) {
1509      //   -- If exactly one matching specialization is found, the
1510      //      instantiation is generated from that specialization.
1511      // We don't need to do anything for this.
1512    } else {
1513      //   -- If more than one matching specialization is found, the
1514      //      partial order rules (14.5.4.2) are used to determine
1515      //      whether one of the specializations is more specialized
1516      //      than the others. If none of the specializations is more
1517      //      specialized than all of the other matching
1518      //      specializations, then the use of the class template is
1519      //      ambiguous and the program is ill-formed.
1520      for (llvm::SmallVector<MatchResult, 4>::iterator P = Best + 1,
1521                                                    PEnd = Matched.end();
1522           P != PEnd; ++P) {
1523        if (getMoreSpecializedPartialSpecialization(P->Partial, Best->Partial,
1524                                                    PointOfInstantiation)
1525              == P->Partial)
1526          Best = P;
1527      }
1528
1529      // Determine if the best partial specialization is more specialized than
1530      // the others.
1531      bool Ambiguous = false;
1532      for (llvm::SmallVector<MatchResult, 4>::iterator P = Matched.begin(),
1533                                                    PEnd = Matched.end();
1534           P != PEnd; ++P) {
1535        if (P != Best &&
1536            getMoreSpecializedPartialSpecialization(P->Partial, Best->Partial,
1537                                                    PointOfInstantiation)
1538              != Best->Partial) {
1539          Ambiguous = true;
1540          break;
1541        }
1542      }
1543
1544      if (Ambiguous) {
1545        // Partial ordering did not produce a clear winner. Complain.
1546        ClassTemplateSpec->setInvalidDecl();
1547        Diag(PointOfInstantiation, diag::err_partial_spec_ordering_ambiguous)
1548          << ClassTemplateSpec;
1549
1550        // Print the matching partial specializations.
1551        for (llvm::SmallVector<MatchResult, 4>::iterator P = Matched.begin(),
1552                                                      PEnd = Matched.end();
1553             P != PEnd; ++P)
1554          Diag(P->Partial->getLocation(), diag::note_partial_spec_match)
1555            << getTemplateArgumentBindingsText(
1556                                            P->Partial->getTemplateParameters(),
1557                                               *P->Args);
1558
1559        return true;
1560      }
1561    }
1562
1563    // Instantiate using the best class template partial specialization.
1564    ClassTemplatePartialSpecializationDecl *OrigPartialSpec = Best->Partial;
1565    while (OrigPartialSpec->getInstantiatedFromMember()) {
1566      // If we've found an explicit specialization of this class template,
1567      // stop here and use that as the pattern.
1568      if (OrigPartialSpec->isMemberSpecialization())
1569        break;
1570
1571      OrigPartialSpec = OrigPartialSpec->getInstantiatedFromMember();
1572    }
1573
1574    Pattern = OrigPartialSpec;
1575    ClassTemplateSpec->setInstantiationOf(Best->Partial, Best->Args);
1576  } else {
1577    //   -- If no matches are found, the instantiation is generated
1578    //      from the primary template.
1579    ClassTemplateDecl *OrigTemplate = Template;
1580    while (OrigTemplate->getInstantiatedFromMemberTemplate()) {
1581      // If we've found an explicit specialization of this class template,
1582      // stop here and use that as the pattern.
1583      if (OrigTemplate->isMemberSpecialization())
1584        break;
1585
1586      OrigTemplate = OrigTemplate->getInstantiatedFromMemberTemplate();
1587    }
1588
1589    Pattern = OrigTemplate->getTemplatedDecl();
1590  }
1591
1592  bool Result = InstantiateClass(PointOfInstantiation, ClassTemplateSpec,
1593                                 Pattern,
1594                                getTemplateInstantiationArgs(ClassTemplateSpec),
1595                                 TSK,
1596                                 Complain);
1597
1598  return Result;
1599}
1600
1601/// \brief Instantiates the definitions of all of the member
1602/// of the given class, which is an instantiation of a class template
1603/// or a member class of a template.
1604void
1605Sema::InstantiateClassMembers(SourceLocation PointOfInstantiation,
1606                              CXXRecordDecl *Instantiation,
1607                        const MultiLevelTemplateArgumentList &TemplateArgs,
1608                              TemplateSpecializationKind TSK) {
1609  for (DeclContext::decl_iterator D = Instantiation->decls_begin(),
1610                               DEnd = Instantiation->decls_end();
1611       D != DEnd; ++D) {
1612    bool SuppressNew = false;
1613    if (FunctionDecl *Function = dyn_cast<FunctionDecl>(*D)) {
1614      if (FunctionDecl *Pattern
1615            = Function->getInstantiatedFromMemberFunction()) {
1616        MemberSpecializationInfo *MSInfo
1617          = Function->getMemberSpecializationInfo();
1618        assert(MSInfo && "No member specialization information?");
1619        if (MSInfo->getTemplateSpecializationKind()
1620                                                 == TSK_ExplicitSpecialization)
1621          continue;
1622
1623        if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
1624                                                   Function,
1625                                        MSInfo->getTemplateSpecializationKind(),
1626                                              MSInfo->getPointOfInstantiation(),
1627                                                   SuppressNew) ||
1628            SuppressNew)
1629          continue;
1630
1631        if (Function->hasBody())
1632          continue;
1633
1634        if (TSK == TSK_ExplicitInstantiationDefinition) {
1635          // C++0x [temp.explicit]p8:
1636          //   An explicit instantiation definition that names a class template
1637          //   specialization explicitly instantiates the class template
1638          //   specialization and is only an explicit instantiation definition
1639          //   of members whose definition is visible at the point of
1640          //   instantiation.
1641          if (!Pattern->hasBody())
1642            continue;
1643
1644          Function->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1645
1646          InstantiateFunctionDefinition(PointOfInstantiation, Function);
1647        } else {
1648          Function->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1649        }
1650      }
1651    } else if (VarDecl *Var = dyn_cast<VarDecl>(*D)) {
1652      if (Var->isStaticDataMember()) {
1653        MemberSpecializationInfo *MSInfo = Var->getMemberSpecializationInfo();
1654        assert(MSInfo && "No member specialization information?");
1655        if (MSInfo->getTemplateSpecializationKind()
1656                                                 == TSK_ExplicitSpecialization)
1657          continue;
1658
1659        if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
1660                                                   Var,
1661                                        MSInfo->getTemplateSpecializationKind(),
1662                                              MSInfo->getPointOfInstantiation(),
1663                                                   SuppressNew) ||
1664            SuppressNew)
1665          continue;
1666
1667        if (TSK == TSK_ExplicitInstantiationDefinition) {
1668          // C++0x [temp.explicit]p8:
1669          //   An explicit instantiation definition that names a class template
1670          //   specialization explicitly instantiates the class template
1671          //   specialization and is only an explicit instantiation definition
1672          //   of members whose definition is visible at the point of
1673          //   instantiation.
1674          if (!Var->getInstantiatedFromStaticDataMember()
1675                                                     ->getOutOfLineDefinition())
1676            continue;
1677
1678          Var->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1679          InstantiateStaticDataMemberDefinition(PointOfInstantiation, Var);
1680        } else {
1681          Var->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1682        }
1683      }
1684    } else if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(*D)) {
1685      // Always skip the injected-class-name, along with any
1686      // redeclarations of nested classes, since both would cause us
1687      // to try to instantiate the members of a class twice.
1688      if (Record->isInjectedClassName() || Record->getPreviousDeclaration())
1689        continue;
1690
1691      MemberSpecializationInfo *MSInfo = Record->getMemberSpecializationInfo();
1692      assert(MSInfo && "No member specialization information?");
1693
1694      if (MSInfo->getTemplateSpecializationKind()
1695                                                == TSK_ExplicitSpecialization)
1696        continue;
1697
1698      if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
1699                                                 Record,
1700                                        MSInfo->getTemplateSpecializationKind(),
1701                                              MSInfo->getPointOfInstantiation(),
1702                                                 SuppressNew) ||
1703          SuppressNew)
1704        continue;
1705
1706      CXXRecordDecl *Pattern = Record->getInstantiatedFromMemberClass();
1707      assert(Pattern && "Missing instantiated-from-template information");
1708
1709      if (!Record->getDefinition()) {
1710        if (!Pattern->getDefinition()) {
1711          // C++0x [temp.explicit]p8:
1712          //   An explicit instantiation definition that names a class template
1713          //   specialization explicitly instantiates the class template
1714          //   specialization and is only an explicit instantiation definition
1715          //   of members whose definition is visible at the point of
1716          //   instantiation.
1717          if (TSK == TSK_ExplicitInstantiationDeclaration) {
1718            MSInfo->setTemplateSpecializationKind(TSK);
1719            MSInfo->setPointOfInstantiation(PointOfInstantiation);
1720          }
1721
1722          continue;
1723        }
1724
1725        InstantiateClass(PointOfInstantiation, Record, Pattern,
1726                         TemplateArgs,
1727                         TSK);
1728      } else {
1729        if (TSK == TSK_ExplicitInstantiationDefinition &&
1730            Record->getTemplateSpecializationKind() ==
1731                TSK_ExplicitInstantiationDeclaration) {
1732          Record->setTemplateSpecializationKind(TSK);
1733          MarkVTableUsed(PointOfInstantiation, Record, true);
1734        }
1735      }
1736
1737      Pattern = cast_or_null<CXXRecordDecl>(Record->getDefinition());
1738      if (Pattern)
1739        InstantiateClassMembers(PointOfInstantiation, Pattern, TemplateArgs,
1740                                TSK);
1741    }
1742  }
1743}
1744
1745/// \brief Instantiate the definitions of all of the members of the
1746/// given class template specialization, which was named as part of an
1747/// explicit instantiation.
1748void
1749Sema::InstantiateClassTemplateSpecializationMembers(
1750                                           SourceLocation PointOfInstantiation,
1751                            ClassTemplateSpecializationDecl *ClassTemplateSpec,
1752                                               TemplateSpecializationKind TSK) {
1753  // C++0x [temp.explicit]p7:
1754  //   An explicit instantiation that names a class template
1755  //   specialization is an explicit instantion of the same kind
1756  //   (declaration or definition) of each of its members (not
1757  //   including members inherited from base classes) that has not
1758  //   been previously explicitly specialized in the translation unit
1759  //   containing the explicit instantiation, except as described
1760  //   below.
1761  InstantiateClassMembers(PointOfInstantiation, ClassTemplateSpec,
1762                          getTemplateInstantiationArgs(ClassTemplateSpec),
1763                          TSK);
1764}
1765
1766StmtResult
1767Sema::SubstStmt(Stmt *S, const MultiLevelTemplateArgumentList &TemplateArgs) {
1768  if (!S)
1769    return Owned(S);
1770
1771  TemplateInstantiator Instantiator(*this, TemplateArgs,
1772                                    SourceLocation(),
1773                                    DeclarationName());
1774  return Instantiator.TransformStmt(S);
1775}
1776
1777ExprResult
1778Sema::SubstExpr(Expr *E, const MultiLevelTemplateArgumentList &TemplateArgs) {
1779  if (!E)
1780    return Owned(E);
1781
1782  TemplateInstantiator Instantiator(*this, TemplateArgs,
1783                                    SourceLocation(),
1784                                    DeclarationName());
1785  return Instantiator.TransformExpr(E);
1786}
1787
1788/// \brief Do template substitution on a nested-name-specifier.
1789NestedNameSpecifier *
1790Sema::SubstNestedNameSpecifier(NestedNameSpecifier *NNS,
1791                               SourceRange Range,
1792                         const MultiLevelTemplateArgumentList &TemplateArgs) {
1793  TemplateInstantiator Instantiator(*this, TemplateArgs, Range.getBegin(),
1794                                    DeclarationName());
1795  return Instantiator.TransformNestedNameSpecifier(NNS, Range);
1796}
1797
1798/// \brief Do template substitution on declaration name info.
1799DeclarationNameInfo
1800Sema::SubstDeclarationNameInfo(const DeclarationNameInfo &NameInfo,
1801                         const MultiLevelTemplateArgumentList &TemplateArgs) {
1802  TemplateInstantiator Instantiator(*this, TemplateArgs, NameInfo.getLoc(),
1803                                    NameInfo.getName());
1804  return Instantiator.TransformDeclarationNameInfo(NameInfo);
1805}
1806
1807TemplateName
1808Sema::SubstTemplateName(TemplateName Name, SourceLocation Loc,
1809                        const MultiLevelTemplateArgumentList &TemplateArgs) {
1810  TemplateInstantiator Instantiator(*this, TemplateArgs, Loc,
1811                                    DeclarationName());
1812  return Instantiator.TransformTemplateName(Name);
1813}
1814
1815bool Sema::Subst(const TemplateArgumentLoc *Args, unsigned NumArgs,
1816                 TemplateArgumentListInfo &Result,
1817                 const MultiLevelTemplateArgumentList &TemplateArgs) {
1818  TemplateInstantiator Instantiator(*this, TemplateArgs, SourceLocation(),
1819                                    DeclarationName());
1820
1821  return Instantiator.TransformTemplateArguments(Args, NumArgs, Result);
1822}
1823
1824Decl *LocalInstantiationScope::getInstantiationOf(const Decl *D) {
1825  for (LocalInstantiationScope *Current = this; Current;
1826       Current = Current->Outer) {
1827    // Check if we found something within this scope.
1828    const Decl *CheckD = D;
1829    do {
1830      llvm::DenseMap<const Decl *, Decl *>::iterator Found
1831        = Current->LocalDecls.find(CheckD);
1832      if (Found != Current->LocalDecls.end())
1833        return Found->second;
1834
1835      // If this is a tag declaration, it's possible that we need to look for
1836      // a previous declaration.
1837      if (const TagDecl *Tag = dyn_cast<TagDecl>(CheckD))
1838        CheckD = Tag->getPreviousDeclaration();
1839      else
1840        CheckD = 0;
1841    } while (CheckD);
1842
1843    // If we aren't combined with our outer scope, we're done.
1844    if (!Current->CombineWithOuterScope)
1845      break;
1846  }
1847
1848  assert(D->isInvalidDecl() &&
1849         "declaration was not instantiated in this scope!");
1850  return 0;
1851}
1852
1853void LocalInstantiationScope::InstantiatedLocal(const Decl *D, Decl *Inst) {
1854  Decl *&Stored = LocalDecls[D];
1855  assert((!Stored || Stored == Inst)&& "Already instantiated this local");
1856  Stored = Inst;
1857}
1858