SemaTemplateInstantiate.cpp revision 30c42404202d2e2512e51efc6066bd614cfdb5a4 
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/Initialization.h"
17#include "clang/Sema/Lookup.h"
18#include "clang/Sema/Template.h"
19#include "clang/Sema/TemplateDeduction.h"
20#include "clang/AST/ASTConsumer.h"
21#include "clang/AST/ASTContext.h"
22#include "clang/AST/Expr.h"
23#include "clang/AST/DeclTemplate.h"
24#include "clang/Basic/LangOptions.h"
25
26using namespace clang;
27using namespace sema;
28
29//===----------------------------------------------------------------------===/
30// Template Instantiation Support
31//===----------------------------------------------------------------------===/
32
33/// \brief Retrieve the template argument list(s) that should be used to
34/// instantiate the definition of the given declaration.
35///
36/// \param D the declaration for which we are computing template instantiation
37/// arguments.
38///
39/// \param Innermost if non-NULL, the innermost template argument list.
40///
41/// \param RelativeToPrimary true if we should get the template
42/// arguments relative to the primary template, even when we're
43/// dealing with a specialization. This is only relevant for function
44/// template specializations.
45///
46/// \param Pattern If non-NULL, indicates the pattern from which we will be
47/// instantiating the definition of the given declaration, \p D. This is
48/// used to determine the proper set of template instantiation arguments for
49/// friend function template specializations.
50MultiLevelTemplateArgumentList
51Sema::getTemplateInstantiationArgs(NamedDecl *D,
52                                   const TemplateArgumentList *Innermost,
53                                   bool RelativeToPrimary,
54                                   const FunctionDecl *Pattern) {
55  // Accumulate the set of template argument lists in this structure.
56  MultiLevelTemplateArgumentList Result;
57
58  if (Innermost)
59    Result.addOuterTemplateArguments(Innermost);
60
61  DeclContext *Ctx = dyn_cast<DeclContext>(D);
62  if (!Ctx) {
63    Ctx = D->getDeclContext();
64
65    // If we have a template template parameter with translation unit context,
66    // then we're performing substitution into a default template argument of
67    // this template template parameter before we've constructed the template
68    // that will own this template template parameter. In this case, we
69    // use empty template parameter lists for all of the outer templates
70    // to avoid performing any substitutions.
71    if (Ctx->isTranslationUnit()) {
72      if (TemplateTemplateParmDecl *TTP
73                                      = dyn_cast<TemplateTemplateParmDecl>(D)) {
74        for (unsigned I = 0, N = TTP->getDepth() + 1; I != N; ++I)
75          Result.addOuterTemplateArguments(0, 0);
76        return Result;
77      }
78    }
79  }
80
81  while (!Ctx->isFileContext()) {
82    // Add template arguments from a class template instantiation.
83    if (ClassTemplateSpecializationDecl *Spec
84          = dyn_cast<ClassTemplateSpecializationDecl>(Ctx)) {
85      // We're done when we hit an explicit specialization.
86      if (Spec->getSpecializationKind() == TSK_ExplicitSpecialization &&
87          !isa<ClassTemplatePartialSpecializationDecl>(Spec))
88        break;
89
90      Result.addOuterTemplateArguments(&Spec->getTemplateInstantiationArgs());
91
92      // If this class template specialization was instantiated from a
93      // specialized member that is a class template, we're done.
94      assert(Spec->getSpecializedTemplate() && "No class template?");
95      if (Spec->getSpecializedTemplate()->isMemberSpecialization())
96        break;
97    }
98    // Add template arguments from a function template specialization.
99    else if (FunctionDecl *Function = dyn_cast<FunctionDecl>(Ctx)) {
100      if (!RelativeToPrimary &&
101          (Function->getTemplateSpecializationKind() ==
102                                                  TSK_ExplicitSpecialization &&
103           !Function->getClassScopeSpecializationPattern()))
104        break;
105
106      if (const TemplateArgumentList *TemplateArgs
107            = Function->getTemplateSpecializationArgs()) {
108        // Add the template arguments for this specialization.
109        Result.addOuterTemplateArguments(TemplateArgs);
110
111        // If this function was instantiated from a specialized member that is
112        // a function template, we're done.
113        assert(Function->getPrimaryTemplate() && "No function template?");
114        if (Function->getPrimaryTemplate()->isMemberSpecialization())
115          break;
116      } else if (FunctionTemplateDecl *FunTmpl
117                                   = Function->getDescribedFunctionTemplate()) {
118        // Add the "injected" template arguments.
119        std::pair<const TemplateArgument *, unsigned>
120          Injected = FunTmpl->getInjectedTemplateArgs();
121        Result.addOuterTemplateArguments(Injected.first, Injected.second);
122      }
123
124      // If this is a friend declaration and it declares an entity at
125      // namespace scope, take arguments from its lexical parent
126      // instead of its semantic parent, unless of course the pattern we're
127      // instantiating actually comes from the file's context!
128      if (Function->getFriendObjectKind() &&
129          Function->getDeclContext()->isFileContext() &&
130          (!Pattern || !Pattern->getLexicalDeclContext()->isFileContext())) {
131        Ctx = Function->getLexicalDeclContext();
132        RelativeToPrimary = false;
133        continue;
134      }
135    } else if (CXXRecordDecl *Rec = dyn_cast<CXXRecordDecl>(Ctx)) {
136      if (ClassTemplateDecl *ClassTemplate = Rec->getDescribedClassTemplate()) {
137        QualType T = ClassTemplate->getInjectedClassNameSpecialization();
138        const TemplateSpecializationType *TST
139          = cast<TemplateSpecializationType>(Context.getCanonicalType(T));
140        Result.addOuterTemplateArguments(TST->getArgs(), TST->getNumArgs());
141        if (ClassTemplate->isMemberSpecialization())
142          break;
143      }
144    }
145
146    Ctx = Ctx->getParent();
147    RelativeToPrimary = false;
148  }
149
150  return Result;
151}
152
153bool Sema::ActiveTemplateInstantiation::isInstantiationRecord() const {
154  switch (Kind) {
155  case TemplateInstantiation:
156  case DefaultTemplateArgumentInstantiation:
157  case DefaultFunctionArgumentInstantiation:
158    return true;
159
160  case ExplicitTemplateArgumentSubstitution:
161  case DeducedTemplateArgumentSubstitution:
162  case PriorTemplateArgumentSubstitution:
163  case DefaultTemplateArgumentChecking:
164    return false;
165  }
166
167  return true;
168}
169
170Sema::InstantiatingTemplate::
171InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
172                      Decl *Entity,
173                      SourceRange InstantiationRange)
174  : SemaRef(SemaRef),
175    SavedInNonInstantiationSFINAEContext(
176                                        SemaRef.InNonInstantiationSFINAEContext)
177{
178  Invalid = CheckInstantiationDepth(PointOfInstantiation,
179                                    InstantiationRange);
180  if (!Invalid) {
181    ActiveTemplateInstantiation Inst;
182    Inst.Kind = ActiveTemplateInstantiation::TemplateInstantiation;
183    Inst.PointOfInstantiation = PointOfInstantiation;
184    Inst.Entity = reinterpret_cast<uintptr_t>(Entity);
185    Inst.TemplateArgs = 0;
186    Inst.NumTemplateArgs = 0;
187    Inst.InstantiationRange = InstantiationRange;
188    SemaRef.InNonInstantiationSFINAEContext = false;
189    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
190  }
191}
192
193Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
194                                         SourceLocation PointOfInstantiation,
195                                         TemplateDecl *Template,
196                                         const TemplateArgument *TemplateArgs,
197                                         unsigned NumTemplateArgs,
198                                         SourceRange InstantiationRange)
199  : SemaRef(SemaRef),
200    SavedInNonInstantiationSFINAEContext(
201                                     SemaRef.InNonInstantiationSFINAEContext)
202{
203  Invalid = CheckInstantiationDepth(PointOfInstantiation,
204                                    InstantiationRange);
205  if (!Invalid) {
206    ActiveTemplateInstantiation Inst;
207    Inst.Kind
208      = ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation;
209    Inst.PointOfInstantiation = PointOfInstantiation;
210    Inst.Entity = reinterpret_cast<uintptr_t>(Template);
211    Inst.TemplateArgs = TemplateArgs;
212    Inst.NumTemplateArgs = NumTemplateArgs;
213    Inst.InstantiationRange = InstantiationRange;
214    SemaRef.InNonInstantiationSFINAEContext = false;
215    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
216  }
217}
218
219Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
220                                         SourceLocation PointOfInstantiation,
221                                      FunctionTemplateDecl *FunctionTemplate,
222                                        const TemplateArgument *TemplateArgs,
223                                                   unsigned NumTemplateArgs,
224                         ActiveTemplateInstantiation::InstantiationKind Kind,
225                                   sema::TemplateDeductionInfo &DeductionInfo,
226                                              SourceRange InstantiationRange)
227  : SemaRef(SemaRef),
228    SavedInNonInstantiationSFINAEContext(
229                                     SemaRef.InNonInstantiationSFINAEContext)
230{
231  Invalid = CheckInstantiationDepth(PointOfInstantiation,
232                                    InstantiationRange);
233  if (!Invalid) {
234    ActiveTemplateInstantiation Inst;
235    Inst.Kind = Kind;
236    Inst.PointOfInstantiation = PointOfInstantiation;
237    Inst.Entity = reinterpret_cast<uintptr_t>(FunctionTemplate);
238    Inst.TemplateArgs = TemplateArgs;
239    Inst.NumTemplateArgs = NumTemplateArgs;
240    Inst.DeductionInfo = &DeductionInfo;
241    Inst.InstantiationRange = InstantiationRange;
242    SemaRef.InNonInstantiationSFINAEContext = false;
243    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
244
245    if (!Inst.isInstantiationRecord())
246      ++SemaRef.NonInstantiationEntries;
247  }
248}
249
250Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
251                                         SourceLocation PointOfInstantiation,
252                          ClassTemplatePartialSpecializationDecl *PartialSpec,
253                                         const TemplateArgument *TemplateArgs,
254                                         unsigned NumTemplateArgs,
255                                    sema::TemplateDeductionInfo &DeductionInfo,
256                                         SourceRange InstantiationRange)
257  : SemaRef(SemaRef),
258    SavedInNonInstantiationSFINAEContext(
259                                     SemaRef.InNonInstantiationSFINAEContext)
260{
261  Invalid = false;
262
263  ActiveTemplateInstantiation Inst;
264  Inst.Kind = ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution;
265  Inst.PointOfInstantiation = PointOfInstantiation;
266  Inst.Entity = reinterpret_cast<uintptr_t>(PartialSpec);
267  Inst.TemplateArgs = TemplateArgs;
268  Inst.NumTemplateArgs = NumTemplateArgs;
269  Inst.DeductionInfo = &DeductionInfo;
270  Inst.InstantiationRange = InstantiationRange;
271  SemaRef.InNonInstantiationSFINAEContext = false;
272  SemaRef.ActiveTemplateInstantiations.push_back(Inst);
273
274  assert(!Inst.isInstantiationRecord());
275  ++SemaRef.NonInstantiationEntries;
276}
277
278Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
279                                          SourceLocation PointOfInstantiation,
280                                          ParmVarDecl *Param,
281                                          const TemplateArgument *TemplateArgs,
282                                          unsigned NumTemplateArgs,
283                                          SourceRange InstantiationRange)
284  : SemaRef(SemaRef),
285    SavedInNonInstantiationSFINAEContext(
286                                     SemaRef.InNonInstantiationSFINAEContext)
287{
288  Invalid = CheckInstantiationDepth(PointOfInstantiation, InstantiationRange);
289
290  if (!Invalid) {
291    ActiveTemplateInstantiation Inst;
292    Inst.Kind
293      = ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation;
294    Inst.PointOfInstantiation = PointOfInstantiation;
295    Inst.Entity = reinterpret_cast<uintptr_t>(Param);
296    Inst.TemplateArgs = TemplateArgs;
297    Inst.NumTemplateArgs = NumTemplateArgs;
298    Inst.InstantiationRange = InstantiationRange;
299    SemaRef.InNonInstantiationSFINAEContext = false;
300    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
301  }
302}
303
304Sema::InstantiatingTemplate::
305InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
306                      NamedDecl *Template,
307                      NonTypeTemplateParmDecl *Param,
308                      const TemplateArgument *TemplateArgs,
309                      unsigned NumTemplateArgs,
310                      SourceRange InstantiationRange)
311  : SemaRef(SemaRef),
312    SavedInNonInstantiationSFINAEContext(
313                                     SemaRef.InNonInstantiationSFINAEContext)
314{
315  Invalid = false;
316
317  ActiveTemplateInstantiation Inst;
318  Inst.Kind = ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution;
319  Inst.PointOfInstantiation = PointOfInstantiation;
320  Inst.Template = Template;
321  Inst.Entity = reinterpret_cast<uintptr_t>(Param);
322  Inst.TemplateArgs = TemplateArgs;
323  Inst.NumTemplateArgs = NumTemplateArgs;
324  Inst.InstantiationRange = InstantiationRange;
325  SemaRef.InNonInstantiationSFINAEContext = false;
326  SemaRef.ActiveTemplateInstantiations.push_back(Inst);
327
328  assert(!Inst.isInstantiationRecord());
329  ++SemaRef.NonInstantiationEntries;
330}
331
332Sema::InstantiatingTemplate::
333InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
334                      NamedDecl *Template,
335                      TemplateTemplateParmDecl *Param,
336                      const TemplateArgument *TemplateArgs,
337                      unsigned NumTemplateArgs,
338                      SourceRange InstantiationRange)
339  : SemaRef(SemaRef),
340    SavedInNonInstantiationSFINAEContext(
341                                     SemaRef.InNonInstantiationSFINAEContext)
342{
343  Invalid = false;
344  ActiveTemplateInstantiation Inst;
345  Inst.Kind = ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution;
346  Inst.PointOfInstantiation = PointOfInstantiation;
347  Inst.Template = Template;
348  Inst.Entity = reinterpret_cast<uintptr_t>(Param);
349  Inst.TemplateArgs = TemplateArgs;
350  Inst.NumTemplateArgs = NumTemplateArgs;
351  Inst.InstantiationRange = InstantiationRange;
352  SemaRef.InNonInstantiationSFINAEContext = false;
353  SemaRef.ActiveTemplateInstantiations.push_back(Inst);
354
355  assert(!Inst.isInstantiationRecord());
356  ++SemaRef.NonInstantiationEntries;
357}
358
359Sema::InstantiatingTemplate::
360InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
361                      TemplateDecl *Template,
362                      NamedDecl *Param,
363                      const TemplateArgument *TemplateArgs,
364                      unsigned NumTemplateArgs,
365                      SourceRange InstantiationRange)
366  : SemaRef(SemaRef),
367    SavedInNonInstantiationSFINAEContext(
368                                     SemaRef.InNonInstantiationSFINAEContext)
369{
370  Invalid = false;
371
372  ActiveTemplateInstantiation Inst;
373  Inst.Kind = ActiveTemplateInstantiation::DefaultTemplateArgumentChecking;
374  Inst.PointOfInstantiation = PointOfInstantiation;
375  Inst.Template = Template;
376  Inst.Entity = reinterpret_cast<uintptr_t>(Param);
377  Inst.TemplateArgs = TemplateArgs;
378  Inst.NumTemplateArgs = NumTemplateArgs;
379  Inst.InstantiationRange = InstantiationRange;
380  SemaRef.InNonInstantiationSFINAEContext = false;
381  SemaRef.ActiveTemplateInstantiations.push_back(Inst);
382
383  assert(!Inst.isInstantiationRecord());
384  ++SemaRef.NonInstantiationEntries;
385}
386
387void Sema::InstantiatingTemplate::Clear() {
388  if (!Invalid) {
389    if (!SemaRef.ActiveTemplateInstantiations.back().isInstantiationRecord()) {
390      assert(SemaRef.NonInstantiationEntries > 0);
391      --SemaRef.NonInstantiationEntries;
392    }
393    SemaRef.InNonInstantiationSFINAEContext
394      = SavedInNonInstantiationSFINAEContext;
395    SemaRef.ActiveTemplateInstantiations.pop_back();
396    Invalid = true;
397  }
398}
399
400bool Sema::InstantiatingTemplate::CheckInstantiationDepth(
401                                        SourceLocation PointOfInstantiation,
402                                           SourceRange InstantiationRange) {
403  assert(SemaRef.NonInstantiationEntries <=
404                                   SemaRef.ActiveTemplateInstantiations.size());
405  if ((SemaRef.ActiveTemplateInstantiations.size() -
406          SemaRef.NonInstantiationEntries)
407        <= SemaRef.getLangOptions().InstantiationDepth)
408    return false;
409
410  SemaRef.Diag(PointOfInstantiation,
411               diag::err_template_recursion_depth_exceeded)
412    << SemaRef.getLangOptions().InstantiationDepth
413    << InstantiationRange;
414  SemaRef.Diag(PointOfInstantiation, diag::note_template_recursion_depth)
415    << SemaRef.getLangOptions().InstantiationDepth;
416  return true;
417}
418
419/// \brief Prints the current instantiation stack through a series of
420/// notes.
421void Sema::PrintInstantiationStack() {
422  // Determine which template instantiations to skip, if any.
423  unsigned SkipStart = ActiveTemplateInstantiations.size(), SkipEnd = SkipStart;
424  unsigned Limit = Diags.getTemplateBacktraceLimit();
425  if (Limit && Limit < ActiveTemplateInstantiations.size()) {
426    SkipStart = Limit / 2 + Limit % 2;
427    SkipEnd = ActiveTemplateInstantiations.size() - Limit / 2;
428  }
429
430  // FIXME: In all of these cases, we need to show the template arguments
431  unsigned InstantiationIdx = 0;
432  for (SmallVector<ActiveTemplateInstantiation, 16>::reverse_iterator
433         Active = ActiveTemplateInstantiations.rbegin(),
434         ActiveEnd = ActiveTemplateInstantiations.rend();
435       Active != ActiveEnd;
436       ++Active, ++InstantiationIdx) {
437    // Skip this instantiation?
438    if (InstantiationIdx >= SkipStart && InstantiationIdx < SkipEnd) {
439      if (InstantiationIdx == SkipStart) {
440        // Note that we're skipping instantiations.
441        Diags.Report(Active->PointOfInstantiation,
442                     diag::note_instantiation_contexts_suppressed)
443          << unsigned(ActiveTemplateInstantiations.size() - Limit);
444      }
445      continue;
446    }
447
448    switch (Active->Kind) {
449    case ActiveTemplateInstantiation::TemplateInstantiation: {
450      Decl *D = reinterpret_cast<Decl *>(Active->Entity);
451      if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(D)) {
452        unsigned DiagID = diag::note_template_member_class_here;
453        if (isa<ClassTemplateSpecializationDecl>(Record))
454          DiagID = diag::note_template_class_instantiation_here;
455        Diags.Report(Active->PointOfInstantiation, DiagID)
456          << Context.getTypeDeclType(Record)
457          << Active->InstantiationRange;
458      } else if (FunctionDecl *Function = dyn_cast<FunctionDecl>(D)) {
459        unsigned DiagID;
460        if (Function->getPrimaryTemplate())
461          DiagID = diag::note_function_template_spec_here;
462        else
463          DiagID = diag::note_template_member_function_here;
464        Diags.Report(Active->PointOfInstantiation, DiagID)
465          << Function
466          << Active->InstantiationRange;
467      } else if (VarDecl *VD = dyn_cast<VarDecl>(D)) {
468        Diags.Report(Active->PointOfInstantiation,
469                     diag::note_template_static_data_member_def_here)
470          << VD
471          << Active->InstantiationRange;
472      } else {
473        Diags.Report(Active->PointOfInstantiation,
474                     diag::note_template_type_alias_instantiation_here)
475          << cast<TypeAliasTemplateDecl>(D)
476          << Active->InstantiationRange;
477      }
478      break;
479    }
480
481    case ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation: {
482      TemplateDecl *Template = cast<TemplateDecl>((Decl *)Active->Entity);
483      std::string TemplateArgsStr
484        = TemplateSpecializationType::PrintTemplateArgumentList(
485                                                         Active->TemplateArgs,
486                                                      Active->NumTemplateArgs,
487                                                      Context.getPrintingPolicy());
488      Diags.Report(Active->PointOfInstantiation,
489                   diag::note_default_arg_instantiation_here)
490        << (Template->getNameAsString() + TemplateArgsStr)
491        << Active->InstantiationRange;
492      break;
493    }
494
495    case ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution: {
496      FunctionTemplateDecl *FnTmpl
497        = cast<FunctionTemplateDecl>((Decl *)Active->Entity);
498      Diags.Report(Active->PointOfInstantiation,
499                   diag::note_explicit_template_arg_substitution_here)
500        << FnTmpl
501        << getTemplateArgumentBindingsText(FnTmpl->getTemplateParameters(),
502                                           Active->TemplateArgs,
503                                           Active->NumTemplateArgs)
504        << Active->InstantiationRange;
505      break;
506    }
507
508    case ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution:
509      if (ClassTemplatePartialSpecializationDecl *PartialSpec
510            = dyn_cast<ClassTemplatePartialSpecializationDecl>(
511                                                    (Decl *)Active->Entity)) {
512        Diags.Report(Active->PointOfInstantiation,
513                     diag::note_partial_spec_deduct_instantiation_here)
514          << Context.getTypeDeclType(PartialSpec)
515          << getTemplateArgumentBindingsText(
516                                         PartialSpec->getTemplateParameters(),
517                                             Active->TemplateArgs,
518                                             Active->NumTemplateArgs)
519          << Active->InstantiationRange;
520      } else {
521        FunctionTemplateDecl *FnTmpl
522          = cast<FunctionTemplateDecl>((Decl *)Active->Entity);
523        Diags.Report(Active->PointOfInstantiation,
524                     diag::note_function_template_deduction_instantiation_here)
525          << FnTmpl
526          << getTemplateArgumentBindingsText(FnTmpl->getTemplateParameters(),
527                                             Active->TemplateArgs,
528                                             Active->NumTemplateArgs)
529          << Active->InstantiationRange;
530      }
531      break;
532
533    case ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation: {
534      ParmVarDecl *Param = cast<ParmVarDecl>((Decl *)Active->Entity);
535      FunctionDecl *FD = cast<FunctionDecl>(Param->getDeclContext());
536
537      std::string TemplateArgsStr
538        = TemplateSpecializationType::PrintTemplateArgumentList(
539                                                         Active->TemplateArgs,
540                                                      Active->NumTemplateArgs,
541                                                      Context.getPrintingPolicy());
542      Diags.Report(Active->PointOfInstantiation,
543                   diag::note_default_function_arg_instantiation_here)
544        << (FD->getNameAsString() + TemplateArgsStr)
545        << Active->InstantiationRange;
546      break;
547    }
548
549    case ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution: {
550      NamedDecl *Parm = cast<NamedDecl>((Decl *)Active->Entity);
551      std::string Name;
552      if (!Parm->getName().empty())
553        Name = std::string(" '") + Parm->getName().str() + "'";
554
555      TemplateParameterList *TemplateParams = 0;
556      if (TemplateDecl *Template = dyn_cast<TemplateDecl>(Active->Template))
557        TemplateParams = Template->getTemplateParameters();
558      else
559        TemplateParams =
560          cast<ClassTemplatePartialSpecializationDecl>(Active->Template)
561                                                      ->getTemplateParameters();
562      Diags.Report(Active->PointOfInstantiation,
563                   diag::note_prior_template_arg_substitution)
564        << isa<TemplateTemplateParmDecl>(Parm)
565        << Name
566        << getTemplateArgumentBindingsText(TemplateParams,
567                                           Active->TemplateArgs,
568                                           Active->NumTemplateArgs)
569        << Active->InstantiationRange;
570      break;
571    }
572
573    case ActiveTemplateInstantiation::DefaultTemplateArgumentChecking: {
574      TemplateParameterList *TemplateParams = 0;
575      if (TemplateDecl *Template = dyn_cast<TemplateDecl>(Active->Template))
576        TemplateParams = Template->getTemplateParameters();
577      else
578        TemplateParams =
579          cast<ClassTemplatePartialSpecializationDecl>(Active->Template)
580                                                      ->getTemplateParameters();
581
582      Diags.Report(Active->PointOfInstantiation,
583                   diag::note_template_default_arg_checking)
584        << getTemplateArgumentBindingsText(TemplateParams,
585                                           Active->TemplateArgs,
586                                           Active->NumTemplateArgs)
587        << Active->InstantiationRange;
588      break;
589    }
590    }
591  }
592}
593
594llvm::Optional<TemplateDeductionInfo *> Sema::isSFINAEContext() const {
595  if (InNonInstantiationSFINAEContext)
596    return llvm::Optional<TemplateDeductionInfo *>(0);
597
598  for (SmallVector<ActiveTemplateInstantiation, 16>::const_reverse_iterator
599         Active = ActiveTemplateInstantiations.rbegin(),
600         ActiveEnd = ActiveTemplateInstantiations.rend();
601       Active != ActiveEnd;
602       ++Active)
603  {
604    switch(Active->Kind) {
605    case ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation:
606    case ActiveTemplateInstantiation::TemplateInstantiation:
607      // This is a template instantiation, so there is no SFINAE.
608      return llvm::Optional<TemplateDeductionInfo *>();
609
610    case ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation:
611    case ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution:
612    case ActiveTemplateInstantiation::DefaultTemplateArgumentChecking:
613      // A default template argument instantiation and substitution into
614      // template parameters with arguments for prior parameters may or may
615      // not be a SFINAE context; look further up the stack.
616      break;
617
618    case ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution:
619    case ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution:
620      // We're either substitution explicitly-specified template arguments
621      // or deduced template arguments, so SFINAE applies.
622      assert(Active->DeductionInfo && "Missing deduction info pointer");
623      return Active->DeductionInfo;
624    }
625  }
626
627  return llvm::Optional<TemplateDeductionInfo *>();
628}
629
630/// \brief Retrieve the depth and index of a parameter pack.
631static std::pair<unsigned, unsigned>
632getDepthAndIndex(NamedDecl *ND) {
633  if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(ND))
634    return std::make_pair(TTP->getDepth(), TTP->getIndex());
635
636  if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(ND))
637    return std::make_pair(NTTP->getDepth(), NTTP->getIndex());
638
639  TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(ND);
640  return std::make_pair(TTP->getDepth(), TTP->getIndex());
641}
642
643//===----------------------------------------------------------------------===/
644// Template Instantiation for Types
645//===----------------------------------------------------------------------===/
646namespace {
647  class TemplateInstantiator : public TreeTransform<TemplateInstantiator> {
648    const MultiLevelTemplateArgumentList &TemplateArgs;
649    SourceLocation Loc;
650    DeclarationName Entity;
651
652  public:
653    typedef TreeTransform<TemplateInstantiator> inherited;
654
655    TemplateInstantiator(Sema &SemaRef,
656                         const MultiLevelTemplateArgumentList &TemplateArgs,
657                         SourceLocation Loc,
658                         DeclarationName Entity)
659      : inherited(SemaRef), TemplateArgs(TemplateArgs), Loc(Loc),
660        Entity(Entity) { }
661
662    /// \brief Determine whether the given type \p T has already been
663    /// transformed.
664    ///
665    /// For the purposes of template instantiation, a type has already been
666    /// transformed if it is NULL or if it is not dependent.
667    bool AlreadyTransformed(QualType T);
668
669    /// \brief Returns the location of the entity being instantiated, if known.
670    SourceLocation getBaseLocation() { return Loc; }
671
672    /// \brief Returns the name of the entity being instantiated, if any.
673    DeclarationName getBaseEntity() { return Entity; }
674
675    /// \brief Sets the "base" location and entity when that
676    /// information is known based on another transformation.
677    void setBase(SourceLocation Loc, DeclarationName Entity) {
678      this->Loc = Loc;
679      this->Entity = Entity;
680    }
681
682    bool TryExpandParameterPacks(SourceLocation EllipsisLoc,
683                                 SourceRange PatternRange,
684                             llvm::ArrayRef<UnexpandedParameterPack> Unexpanded,
685                                 bool &ShouldExpand,
686                                 bool &RetainExpansion,
687                                 llvm::Optional<unsigned> &NumExpansions) {
688      return getSema().CheckParameterPacksForExpansion(EllipsisLoc,
689                                                       PatternRange, Unexpanded,
690                                                       TemplateArgs,
691                                                       ShouldExpand,
692                                                       RetainExpansion,
693                                                       NumExpansions);
694    }
695
696    void ExpandingFunctionParameterPack(ParmVarDecl *Pack) {
697      SemaRef.CurrentInstantiationScope->MakeInstantiatedLocalArgPack(Pack);
698    }
699
700    TemplateArgument ForgetPartiallySubstitutedPack() {
701      TemplateArgument Result;
702      if (NamedDecl *PartialPack
703            = SemaRef.CurrentInstantiationScope->getPartiallySubstitutedPack()){
704        MultiLevelTemplateArgumentList &TemplateArgs
705          = const_cast<MultiLevelTemplateArgumentList &>(this->TemplateArgs);
706        unsigned Depth, Index;
707        llvm::tie(Depth, Index) = getDepthAndIndex(PartialPack);
708        if (TemplateArgs.hasTemplateArgument(Depth, Index)) {
709          Result = TemplateArgs(Depth, Index);
710          TemplateArgs.setArgument(Depth, Index, TemplateArgument());
711        }
712      }
713
714      return Result;
715    }
716
717    void RememberPartiallySubstitutedPack(TemplateArgument Arg) {
718      if (Arg.isNull())
719        return;
720
721      if (NamedDecl *PartialPack
722            = SemaRef.CurrentInstantiationScope->getPartiallySubstitutedPack()){
723        MultiLevelTemplateArgumentList &TemplateArgs
724        = const_cast<MultiLevelTemplateArgumentList &>(this->TemplateArgs);
725        unsigned Depth, Index;
726        llvm::tie(Depth, Index) = getDepthAndIndex(PartialPack);
727        TemplateArgs.setArgument(Depth, Index, Arg);
728      }
729    }
730
731    /// \brief Transform the given declaration by instantiating a reference to
732    /// this declaration.
733    Decl *TransformDecl(SourceLocation Loc, Decl *D);
734
735    /// \brief Transform the definition of the given declaration by
736    /// instantiating it.
737    Decl *TransformDefinition(SourceLocation Loc, Decl *D);
738
739    /// \bried Transform the first qualifier within a scope by instantiating the
740    /// declaration.
741    NamedDecl *TransformFirstQualifierInScope(NamedDecl *D, SourceLocation Loc);
742
743    /// \brief Rebuild the exception declaration and register the declaration
744    /// as an instantiated local.
745    VarDecl *RebuildExceptionDecl(VarDecl *ExceptionDecl,
746                                  TypeSourceInfo *Declarator,
747                                  SourceLocation StartLoc,
748                                  SourceLocation NameLoc,
749                                  IdentifierInfo *Name);
750
751    /// \brief Rebuild the Objective-C exception declaration and register the
752    /// declaration as an instantiated local.
753    VarDecl *RebuildObjCExceptionDecl(VarDecl *ExceptionDecl,
754                                      TypeSourceInfo *TSInfo, QualType T);
755
756    /// \brief Check for tag mismatches when instantiating an
757    /// elaborated type.
758    QualType RebuildElaboratedType(SourceLocation KeywordLoc,
759                                   ElaboratedTypeKeyword Keyword,
760                                   NestedNameSpecifierLoc QualifierLoc,
761                                   QualType T);
762
763    TemplateName TransformTemplateName(CXXScopeSpec &SS,
764                                       TemplateName Name,
765                                       SourceLocation NameLoc,
766                                       QualType ObjectType = QualType(),
767                                       NamedDecl *FirstQualifierInScope = 0);
768
769    ExprResult TransformPredefinedExpr(PredefinedExpr *E);
770    ExprResult TransformDeclRefExpr(DeclRefExpr *E);
771    ExprResult TransformCXXDefaultArgExpr(CXXDefaultArgExpr *E);
772    ExprResult TransformTemplateParmRefExpr(DeclRefExpr *E,
773                                            NonTypeTemplateParmDecl *D);
774    ExprResult TransformSubstNonTypeTemplateParmPackExpr(
775                                           SubstNonTypeTemplateParmPackExpr *E);
776
777    QualType TransformFunctionProtoType(TypeLocBuilder &TLB,
778                                        FunctionProtoTypeLoc TL);
779    ParmVarDecl *TransformFunctionTypeParam(ParmVarDecl *OldParm,
780                                            int indexAdjustment,
781                                      llvm::Optional<unsigned> NumExpansions);
782
783    /// \brief Transforms a template type parameter type by performing
784    /// substitution of the corresponding template type argument.
785    QualType TransformTemplateTypeParmType(TypeLocBuilder &TLB,
786                                           TemplateTypeParmTypeLoc TL);
787
788    /// \brief Transforms an already-substituted template type parameter pack
789    /// into either itself (if we aren't substituting into its pack expansion)
790    /// or the appropriate substituted argument.
791    QualType TransformSubstTemplateTypeParmPackType(TypeLocBuilder &TLB,
792                                           SubstTemplateTypeParmPackTypeLoc TL);
793
794    ExprResult TransformCallExpr(CallExpr *CE) {
795      getSema().CallsUndergoingInstantiation.push_back(CE);
796      ExprResult Result =
797          TreeTransform<TemplateInstantiator>::TransformCallExpr(CE);
798      getSema().CallsUndergoingInstantiation.pop_back();
799      return move(Result);
800    }
801
802  private:
803    ExprResult transformNonTypeTemplateParmRef(NonTypeTemplateParmDecl *parm,
804                                               SourceLocation loc,
805                                               const TemplateArgument &arg);
806  };
807}
808
809bool TemplateInstantiator::AlreadyTransformed(QualType T) {
810  if (T.isNull())
811    return true;
812
813  if (T->isInstantiationDependentType() || T->isVariablyModifiedType())
814    return false;
815
816  getSema().MarkDeclarationsReferencedInType(Loc, T);
817  return true;
818}
819
820Decl *TemplateInstantiator::TransformDecl(SourceLocation Loc, Decl *D) {
821  if (!D)
822    return 0;
823
824  if (TemplateTemplateParmDecl *TTP = dyn_cast<TemplateTemplateParmDecl>(D)) {
825    if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
826      // If the corresponding template argument is NULL or non-existent, it's
827      // because we are performing instantiation from explicitly-specified
828      // template arguments in a function template, but there were some
829      // arguments left unspecified.
830      if (!TemplateArgs.hasTemplateArgument(TTP->getDepth(),
831                                            TTP->getPosition()))
832        return D;
833
834      TemplateArgument Arg = TemplateArgs(TTP->getDepth(), TTP->getPosition());
835
836      if (TTP->isParameterPack()) {
837        assert(Arg.getKind() == TemplateArgument::Pack &&
838               "Missing argument pack");
839
840        assert(getSema().ArgumentPackSubstitutionIndex >= 0);
841        assert(getSema().ArgumentPackSubstitutionIndex < (int)Arg.pack_size());
842        Arg = Arg.pack_begin()[getSema().ArgumentPackSubstitutionIndex];
843      }
844
845      TemplateName Template = Arg.getAsTemplate();
846      assert(!Template.isNull() && Template.getAsTemplateDecl() &&
847             "Wrong kind of template template argument");
848      return Template.getAsTemplateDecl();
849    }
850
851    // Fall through to find the instantiated declaration for this template
852    // template parameter.
853  }
854
855  return SemaRef.FindInstantiatedDecl(Loc, cast<NamedDecl>(D), TemplateArgs);
856}
857
858Decl *TemplateInstantiator::TransformDefinition(SourceLocation Loc, Decl *D) {
859  Decl *Inst = getSema().SubstDecl(D, getSema().CurContext, TemplateArgs);
860  if (!Inst)
861    return 0;
862
863  getSema().CurrentInstantiationScope->InstantiatedLocal(D, Inst);
864  return Inst;
865}
866
867NamedDecl *
868TemplateInstantiator::TransformFirstQualifierInScope(NamedDecl *D,
869                                                     SourceLocation Loc) {
870  // If the first part of the nested-name-specifier was a template type
871  // parameter, instantiate that type parameter down to a tag type.
872  if (TemplateTypeParmDecl *TTPD = dyn_cast_or_null<TemplateTypeParmDecl>(D)) {
873    const TemplateTypeParmType *TTP
874      = cast<TemplateTypeParmType>(getSema().Context.getTypeDeclType(TTPD));
875
876    if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
877      // FIXME: This needs testing w/ member access expressions.
878      TemplateArgument Arg = TemplateArgs(TTP->getDepth(), TTP->getIndex());
879
880      if (TTP->isParameterPack()) {
881        assert(Arg.getKind() == TemplateArgument::Pack &&
882               "Missing argument pack");
883
884        if (getSema().ArgumentPackSubstitutionIndex == -1)
885          return 0;
886
887        assert(getSema().ArgumentPackSubstitutionIndex < (int)Arg.pack_size());
888        Arg = Arg.pack_begin()[getSema().ArgumentPackSubstitutionIndex];
889      }
890
891      QualType T = Arg.getAsType();
892      if (T.isNull())
893        return cast_or_null<NamedDecl>(TransformDecl(Loc, D));
894
895      if (const TagType *Tag = T->getAs<TagType>())
896        return Tag->getDecl();
897
898      // The resulting type is not a tag; complain.
899      getSema().Diag(Loc, diag::err_nested_name_spec_non_tag) << T;
900      return 0;
901    }
902  }
903
904  return cast_or_null<NamedDecl>(TransformDecl(Loc, D));
905}
906
907VarDecl *
908TemplateInstantiator::RebuildExceptionDecl(VarDecl *ExceptionDecl,
909                                           TypeSourceInfo *Declarator,
910                                           SourceLocation StartLoc,
911                                           SourceLocation NameLoc,
912                                           IdentifierInfo *Name) {
913  VarDecl *Var = inherited::RebuildExceptionDecl(ExceptionDecl, Declarator,
914                                                 StartLoc, NameLoc, Name);
915  if (Var)
916    getSema().CurrentInstantiationScope->InstantiatedLocal(ExceptionDecl, Var);
917  return Var;
918}
919
920VarDecl *TemplateInstantiator::RebuildObjCExceptionDecl(VarDecl *ExceptionDecl,
921                                                        TypeSourceInfo *TSInfo,
922                                                        QualType T) {
923  VarDecl *Var = inherited::RebuildObjCExceptionDecl(ExceptionDecl, TSInfo, T);
924  if (Var)
925    getSema().CurrentInstantiationScope->InstantiatedLocal(ExceptionDecl, Var);
926  return Var;
927}
928
929QualType
930TemplateInstantiator::RebuildElaboratedType(SourceLocation KeywordLoc,
931                                            ElaboratedTypeKeyword Keyword,
932                                            NestedNameSpecifierLoc QualifierLoc,
933                                            QualType T) {
934  if (const TagType *TT = T->getAs<TagType>()) {
935    TagDecl* TD = TT->getDecl();
936
937    SourceLocation TagLocation = KeywordLoc;
938
939    // FIXME: type might be anonymous.
940    IdentifierInfo *Id = TD->getIdentifier();
941
942    // TODO: should we even warn on struct/class mismatches for this?  Seems
943    // like it's likely to produce a lot of spurious errors.
944    if (Keyword != ETK_None && Keyword != ETK_Typename) {
945      TagTypeKind Kind = TypeWithKeyword::getTagTypeKindForKeyword(Keyword);
946      if (!SemaRef.isAcceptableTagRedeclaration(TD, Kind, /*isDefinition*/false,
947                                                TagLocation, *Id)) {
948        SemaRef.Diag(TagLocation, diag::err_use_with_wrong_tag)
949          << Id
950          << FixItHint::CreateReplacement(SourceRange(TagLocation),
951                                          TD->getKindName());
952        SemaRef.Diag(TD->getLocation(), diag::note_previous_use);
953      }
954    }
955  }
956
957  return TreeTransform<TemplateInstantiator>::RebuildElaboratedType(KeywordLoc,
958                                                                    Keyword,
959                                                                  QualifierLoc,
960                                                                    T);
961}
962
963TemplateName TemplateInstantiator::TransformTemplateName(CXXScopeSpec &SS,
964                                                         TemplateName Name,
965                                                         SourceLocation NameLoc,
966                                                         QualType ObjectType,
967                                             NamedDecl *FirstQualifierInScope) {
968  if (TemplateTemplateParmDecl *TTP
969       = dyn_cast_or_null<TemplateTemplateParmDecl>(Name.getAsTemplateDecl())) {
970    if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
971      // If the corresponding template argument is NULL or non-existent, it's
972      // because we are performing instantiation from explicitly-specified
973      // template arguments in a function template, but there were some
974      // arguments left unspecified.
975      if (!TemplateArgs.hasTemplateArgument(TTP->getDepth(),
976                                            TTP->getPosition()))
977        return Name;
978
979      TemplateArgument Arg = TemplateArgs(TTP->getDepth(), TTP->getPosition());
980
981      if (TTP->isParameterPack()) {
982        assert(Arg.getKind() == TemplateArgument::Pack &&
983               "Missing argument pack");
984
985        if (getSema().ArgumentPackSubstitutionIndex == -1) {
986          // We have the template argument pack to substitute, but we're not
987          // actually expanding the enclosing pack expansion yet. So, just
988          // keep the entire argument pack.
989          return getSema().Context.getSubstTemplateTemplateParmPack(TTP, Arg);
990        }
991
992        assert(getSema().ArgumentPackSubstitutionIndex < (int)Arg.pack_size());
993        Arg = Arg.pack_begin()[getSema().ArgumentPackSubstitutionIndex];
994      }
995
996      TemplateName Template = Arg.getAsTemplate();
997      assert(!Template.isNull() && "Null template template argument");
998
999      // We don't ever want to substitute for a qualified template name, since
1000      // the qualifier is handled separately. So, look through the qualified
1001      // template name to its underlying declaration.
1002      if (QualifiedTemplateName *QTN = Template.getAsQualifiedTemplateName())
1003        Template = TemplateName(QTN->getTemplateDecl());
1004
1005      Template = getSema().Context.getSubstTemplateTemplateParm(TTP, Template);
1006      return Template;
1007    }
1008  }
1009
1010  if (SubstTemplateTemplateParmPackStorage *SubstPack
1011      = Name.getAsSubstTemplateTemplateParmPack()) {
1012    if (getSema().ArgumentPackSubstitutionIndex == -1)
1013      return Name;
1014
1015    const TemplateArgument &ArgPack = SubstPack->getArgumentPack();
1016    assert(getSema().ArgumentPackSubstitutionIndex < (int)ArgPack.pack_size() &&
1017           "Pack substitution index out-of-range");
1018    return ArgPack.pack_begin()[getSema().ArgumentPackSubstitutionIndex]
1019    .getAsTemplate();
1020  }
1021
1022  return inherited::TransformTemplateName(SS, Name, NameLoc, ObjectType,
1023                                          FirstQualifierInScope);
1024}
1025
1026ExprResult
1027TemplateInstantiator::TransformPredefinedExpr(PredefinedExpr *E) {
1028  if (!E->isTypeDependent())
1029    return SemaRef.Owned(E);
1030
1031  FunctionDecl *currentDecl = getSema().getCurFunctionDecl();
1032  assert(currentDecl && "Must have current function declaration when "
1033                        "instantiating.");
1034
1035  PredefinedExpr::IdentType IT = E->getIdentType();
1036
1037  unsigned Length = PredefinedExpr::ComputeName(IT, currentDecl).length();
1038
1039  llvm::APInt LengthI(32, Length + 1);
1040  QualType ResTy = getSema().Context.CharTy.withConst();
1041  ResTy = getSema().Context.getConstantArrayType(ResTy, LengthI,
1042                                                 ArrayType::Normal, 0);
1043  PredefinedExpr *PE =
1044    new (getSema().Context) PredefinedExpr(E->getLocation(), ResTy, IT);
1045  return getSema().Owned(PE);
1046}
1047
1048ExprResult
1049TemplateInstantiator::TransformTemplateParmRefExpr(DeclRefExpr *E,
1050                                               NonTypeTemplateParmDecl *NTTP) {
1051  // If the corresponding template argument is NULL or non-existent, it's
1052  // because we are performing instantiation from explicitly-specified
1053  // template arguments in a function template, but there were some
1054  // arguments left unspecified.
1055  if (!TemplateArgs.hasTemplateArgument(NTTP->getDepth(),
1056                                        NTTP->getPosition()))
1057    return SemaRef.Owned(E);
1058
1059  TemplateArgument Arg = TemplateArgs(NTTP->getDepth(), NTTP->getPosition());
1060  if (NTTP->isParameterPack()) {
1061    assert(Arg.getKind() == TemplateArgument::Pack &&
1062           "Missing argument pack");
1063
1064    if (getSema().ArgumentPackSubstitutionIndex == -1) {
1065      // We have an argument pack, but we can't select a particular argument
1066      // out of it yet. Therefore, we'll build an expression to hold on to that
1067      // argument pack.
1068      QualType TargetType = SemaRef.SubstType(NTTP->getType(), TemplateArgs,
1069                                              E->getLocation(),
1070                                              NTTP->getDeclName());
1071      if (TargetType.isNull())
1072        return ExprError();
1073
1074      return new (SemaRef.Context) SubstNonTypeTemplateParmPackExpr(TargetType,
1075                                                                    NTTP,
1076                                                              E->getLocation(),
1077                                                                    Arg);
1078    }
1079
1080    assert(getSema().ArgumentPackSubstitutionIndex < (int)Arg.pack_size());
1081    Arg = Arg.pack_begin()[getSema().ArgumentPackSubstitutionIndex];
1082  }
1083
1084  return transformNonTypeTemplateParmRef(NTTP, E->getLocation(), Arg);
1085}
1086
1087ExprResult TemplateInstantiator::transformNonTypeTemplateParmRef(
1088                                                 NonTypeTemplateParmDecl *parm,
1089                                                 SourceLocation loc,
1090                                                 const TemplateArgument &arg) {
1091  ExprResult result;
1092  QualType type;
1093
1094  // The template argument itself might be an expression, in which
1095  // case we just return that expression.
1096  if (arg.getKind() == TemplateArgument::Expression) {
1097    Expr *argExpr = arg.getAsExpr();
1098    result = SemaRef.Owned(argExpr);
1099    type = argExpr->getType();
1100
1101  } else if (arg.getKind() == TemplateArgument::Declaration) {
1102    ValueDecl *VD = cast<ValueDecl>(arg.getAsDecl());
1103
1104    // Find the instantiation of the template argument.  This is
1105    // required for nested templates.
1106    VD = cast_or_null<ValueDecl>(
1107                       getSema().FindInstantiatedDecl(loc, VD, TemplateArgs));
1108    if (!VD)
1109      return ExprError();
1110
1111    // Derive the type we want the substituted decl to have.  This had
1112    // better be non-dependent, or these checks will have serious problems.
1113    if (parm->isExpandedParameterPack()) {
1114      type = parm->getExpansionType(SemaRef.ArgumentPackSubstitutionIndex);
1115    } else if (parm->isParameterPack() &&
1116               isa<PackExpansionType>(parm->getType())) {
1117      type = SemaRef.SubstType(
1118                        cast<PackExpansionType>(parm->getType())->getPattern(),
1119                                     TemplateArgs, loc, parm->getDeclName());
1120    } else {
1121      type = SemaRef.SubstType(parm->getType(), TemplateArgs,
1122                               loc, parm->getDeclName());
1123    }
1124    assert(!type.isNull() && "type substitution failed for param type");
1125    assert(!type->isDependentType() && "param type still dependent");
1126    result = SemaRef.BuildExpressionFromDeclTemplateArgument(arg, type, loc);
1127
1128    if (!result.isInvalid()) type = result.get()->getType();
1129  } else {
1130    result = SemaRef.BuildExpressionFromIntegralTemplateArgument(arg, loc);
1131
1132    // Note that this type can be different from the type of 'result',
1133    // e.g. if it's an enum type.
1134    type = arg.getIntegralType();
1135  }
1136  if (result.isInvalid()) return ExprError();
1137
1138  Expr *resultExpr = result.take();
1139  return SemaRef.Owned(new (SemaRef.Context)
1140                SubstNonTypeTemplateParmExpr(type,
1141                                             resultExpr->getValueKind(),
1142                                             loc, parm, resultExpr));
1143}
1144
1145ExprResult
1146TemplateInstantiator::TransformSubstNonTypeTemplateParmPackExpr(
1147                                          SubstNonTypeTemplateParmPackExpr *E) {
1148  if (getSema().ArgumentPackSubstitutionIndex == -1) {
1149    // We aren't expanding the parameter pack, so just return ourselves.
1150    return getSema().Owned(E);
1151  }
1152
1153  const TemplateArgument &ArgPack = E->getArgumentPack();
1154  unsigned Index = (unsigned)getSema().ArgumentPackSubstitutionIndex;
1155  assert(Index < ArgPack.pack_size() && "Substitution index out-of-range");
1156
1157  const TemplateArgument &Arg = ArgPack.pack_begin()[Index];
1158  return transformNonTypeTemplateParmRef(E->getParameterPack(),
1159                                         E->getParameterPackLocation(),
1160                                         Arg);
1161}
1162
1163ExprResult
1164TemplateInstantiator::TransformDeclRefExpr(DeclRefExpr *E) {
1165  NamedDecl *D = E->getDecl();
1166  if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D)) {
1167    if (NTTP->getDepth() < TemplateArgs.getNumLevels())
1168      return TransformTemplateParmRefExpr(E, NTTP);
1169
1170    // We have a non-type template parameter that isn't fully substituted;
1171    // FindInstantiatedDecl will find it in the local instantiation scope.
1172  }
1173
1174  return TreeTransform<TemplateInstantiator>::TransformDeclRefExpr(E);
1175}
1176
1177ExprResult TemplateInstantiator::TransformCXXDefaultArgExpr(
1178    CXXDefaultArgExpr *E) {
1179  assert(!cast<FunctionDecl>(E->getParam()->getDeclContext())->
1180             getDescribedFunctionTemplate() &&
1181         "Default arg expressions are never formed in dependent cases.");
1182  return SemaRef.BuildCXXDefaultArgExpr(E->getUsedLocation(),
1183                           cast<FunctionDecl>(E->getParam()->getDeclContext()),
1184                                        E->getParam());
1185}
1186
1187QualType TemplateInstantiator::TransformFunctionProtoType(TypeLocBuilder &TLB,
1188                                                      FunctionProtoTypeLoc TL) {
1189  // We need a local instantiation scope for this function prototype.
1190  LocalInstantiationScope Scope(SemaRef, /*CombineWithOuterScope=*/true);
1191  return inherited::TransformFunctionProtoType(TLB, TL);
1192}
1193
1194ParmVarDecl *
1195TemplateInstantiator::TransformFunctionTypeParam(ParmVarDecl *OldParm,
1196                                                 int indexAdjustment,
1197                                       llvm::Optional<unsigned> NumExpansions) {
1198  return SemaRef.SubstParmVarDecl(OldParm, TemplateArgs, indexAdjustment,
1199                                  NumExpansions);
1200}
1201
1202QualType
1203TemplateInstantiator::TransformTemplateTypeParmType(TypeLocBuilder &TLB,
1204                                                TemplateTypeParmTypeLoc TL) {
1205  const TemplateTypeParmType *T = TL.getTypePtr();
1206  if (T->getDepth() < TemplateArgs.getNumLevels()) {
1207    // Replace the template type parameter with its corresponding
1208    // template argument.
1209
1210    // If the corresponding template argument is NULL or doesn't exist, it's
1211    // because we are performing instantiation from explicitly-specified
1212    // template arguments in a function template class, but there were some
1213    // arguments left unspecified.
1214    if (!TemplateArgs.hasTemplateArgument(T->getDepth(), T->getIndex())) {
1215      TemplateTypeParmTypeLoc NewTL
1216        = TLB.push<TemplateTypeParmTypeLoc>(TL.getType());
1217      NewTL.setNameLoc(TL.getNameLoc());
1218      return TL.getType();
1219    }
1220
1221    TemplateArgument Arg = TemplateArgs(T->getDepth(), T->getIndex());
1222
1223    if (T->isParameterPack()) {
1224      assert(Arg.getKind() == TemplateArgument::Pack &&
1225             "Missing argument pack");
1226
1227      if (getSema().ArgumentPackSubstitutionIndex == -1) {
1228        // We have the template argument pack, but we're not expanding the
1229        // enclosing pack expansion yet. Just save the template argument
1230        // pack for later substitution.
1231        QualType Result
1232          = getSema().Context.getSubstTemplateTypeParmPackType(T, Arg);
1233        SubstTemplateTypeParmPackTypeLoc NewTL
1234          = TLB.push<SubstTemplateTypeParmPackTypeLoc>(Result);
1235        NewTL.setNameLoc(TL.getNameLoc());
1236        return Result;
1237      }
1238
1239      assert(getSema().ArgumentPackSubstitutionIndex < (int)Arg.pack_size());
1240      Arg = Arg.pack_begin()[getSema().ArgumentPackSubstitutionIndex];
1241    }
1242
1243    assert(Arg.getKind() == TemplateArgument::Type &&
1244           "Template argument kind mismatch");
1245
1246    QualType Replacement = Arg.getAsType();
1247
1248    // TODO: only do this uniquing once, at the start of instantiation.
1249    QualType Result
1250      = getSema().Context.getSubstTemplateTypeParmType(T, Replacement);
1251    SubstTemplateTypeParmTypeLoc NewTL
1252      = TLB.push<SubstTemplateTypeParmTypeLoc>(Result);
1253    NewTL.setNameLoc(TL.getNameLoc());
1254    return Result;
1255  }
1256
1257  // The template type parameter comes from an inner template (e.g.,
1258  // the template parameter list of a member template inside the
1259  // template we are instantiating). Create a new template type
1260  // parameter with the template "level" reduced by one.
1261  TemplateTypeParmDecl *NewTTPDecl = 0;
1262  if (TemplateTypeParmDecl *OldTTPDecl = T->getDecl())
1263    NewTTPDecl = cast_or_null<TemplateTypeParmDecl>(
1264                                  TransformDecl(TL.getNameLoc(), OldTTPDecl));
1265
1266  QualType Result
1267    = getSema().Context.getTemplateTypeParmType(T->getDepth()
1268                                                 - TemplateArgs.getNumLevels(),
1269                                                T->getIndex(),
1270                                                T->isParameterPack(),
1271                                                NewTTPDecl);
1272  TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result);
1273  NewTL.setNameLoc(TL.getNameLoc());
1274  return Result;
1275}
1276
1277QualType
1278TemplateInstantiator::TransformSubstTemplateTypeParmPackType(
1279                                                            TypeLocBuilder &TLB,
1280                                         SubstTemplateTypeParmPackTypeLoc TL) {
1281  if (getSema().ArgumentPackSubstitutionIndex == -1) {
1282    // We aren't expanding the parameter pack, so just return ourselves.
1283    SubstTemplateTypeParmPackTypeLoc NewTL
1284      = TLB.push<SubstTemplateTypeParmPackTypeLoc>(TL.getType());
1285    NewTL.setNameLoc(TL.getNameLoc());
1286    return TL.getType();
1287  }
1288
1289  const TemplateArgument &ArgPack = TL.getTypePtr()->getArgumentPack();
1290  unsigned Index = (unsigned)getSema().ArgumentPackSubstitutionIndex;
1291  assert(Index < ArgPack.pack_size() && "Substitution index out-of-range");
1292
1293  QualType Result = ArgPack.pack_begin()[Index].getAsType();
1294  Result = getSema().Context.getSubstTemplateTypeParmType(
1295                                      TL.getTypePtr()->getReplacedParameter(),
1296                                                          Result);
1297  SubstTemplateTypeParmTypeLoc NewTL
1298    = TLB.push<SubstTemplateTypeParmTypeLoc>(Result);
1299  NewTL.setNameLoc(TL.getNameLoc());
1300  return Result;
1301}
1302
1303/// \brief Perform substitution on the type T with a given set of template
1304/// arguments.
1305///
1306/// This routine substitutes the given template arguments into the
1307/// type T and produces the instantiated type.
1308///
1309/// \param T the type into which the template arguments will be
1310/// substituted. If this type is not dependent, it will be returned
1311/// immediately.
1312///
1313/// \param TemplateArgs the template arguments that will be
1314/// substituted for the top-level template parameters within T.
1315///
1316/// \param Loc the location in the source code where this substitution
1317/// is being performed. It will typically be the location of the
1318/// declarator (if we're instantiating the type of some declaration)
1319/// or the location of the type in the source code (if, e.g., we're
1320/// instantiating the type of a cast expression).
1321///
1322/// \param Entity the name of the entity associated with a declaration
1323/// being instantiated (if any). May be empty to indicate that there
1324/// is no such entity (if, e.g., this is a type that occurs as part of
1325/// a cast expression) or that the entity has no name (e.g., an
1326/// unnamed function parameter).
1327///
1328/// \returns If the instantiation succeeds, the instantiated
1329/// type. Otherwise, produces diagnostics and returns a NULL type.
1330TypeSourceInfo *Sema::SubstType(TypeSourceInfo *T,
1331                                const MultiLevelTemplateArgumentList &Args,
1332                                SourceLocation Loc,
1333                                DeclarationName Entity) {
1334  assert(!ActiveTemplateInstantiations.empty() &&
1335         "Cannot perform an instantiation without some context on the "
1336         "instantiation stack");
1337
1338  if (!T->getType()->isInstantiationDependentType() &&
1339      !T->getType()->isVariablyModifiedType())
1340    return T;
1341
1342  TemplateInstantiator Instantiator(*this, Args, Loc, Entity);
1343  return Instantiator.TransformType(T);
1344}
1345
1346TypeSourceInfo *Sema::SubstType(TypeLoc TL,
1347                                const MultiLevelTemplateArgumentList &Args,
1348                                SourceLocation Loc,
1349                                DeclarationName Entity) {
1350  assert(!ActiveTemplateInstantiations.empty() &&
1351         "Cannot perform an instantiation without some context on the "
1352         "instantiation stack");
1353
1354  if (TL.getType().isNull())
1355    return 0;
1356
1357  if (!TL.getType()->isInstantiationDependentType() &&
1358      !TL.getType()->isVariablyModifiedType()) {
1359    // FIXME: Make a copy of the TypeLoc data here, so that we can
1360    // return a new TypeSourceInfo. Inefficient!
1361    TypeLocBuilder TLB;
1362    TLB.pushFullCopy(TL);
1363    return TLB.getTypeSourceInfo(Context, TL.getType());
1364  }
1365
1366  TemplateInstantiator Instantiator(*this, Args, Loc, Entity);
1367  TypeLocBuilder TLB;
1368  TLB.reserve(TL.getFullDataSize());
1369  QualType Result = Instantiator.TransformType(TLB, TL);
1370  if (Result.isNull())
1371    return 0;
1372
1373  return TLB.getTypeSourceInfo(Context, Result);
1374}
1375
1376/// Deprecated form of the above.
1377QualType Sema::SubstType(QualType T,
1378                         const MultiLevelTemplateArgumentList &TemplateArgs,
1379                         SourceLocation Loc, DeclarationName Entity) {
1380  assert(!ActiveTemplateInstantiations.empty() &&
1381         "Cannot perform an instantiation without some context on the "
1382         "instantiation stack");
1383
1384  // If T is not a dependent type or a variably-modified type, there
1385  // is nothing to do.
1386  if (!T->isInstantiationDependentType() && !T->isVariablyModifiedType())
1387    return T;
1388
1389  TemplateInstantiator Instantiator(*this, TemplateArgs, Loc, Entity);
1390  return Instantiator.TransformType(T);
1391}
1392
1393static bool NeedsInstantiationAsFunctionType(TypeSourceInfo *T) {
1394  if (T->getType()->isInstantiationDependentType() ||
1395      T->getType()->isVariablyModifiedType())
1396    return true;
1397
1398  TypeLoc TL = T->getTypeLoc().IgnoreParens();
1399  if (!isa<FunctionProtoTypeLoc>(TL))
1400    return false;
1401
1402  FunctionProtoTypeLoc FP = cast<FunctionProtoTypeLoc>(TL);
1403  for (unsigned I = 0, E = FP.getNumArgs(); I != E; ++I) {
1404    ParmVarDecl *P = FP.getArg(I);
1405
1406    // The parameter's type as written might be dependent even if the
1407    // decayed type was not dependent.
1408    if (TypeSourceInfo *TSInfo = P->getTypeSourceInfo())
1409      if (TSInfo->getType()->isInstantiationDependentType())
1410        return true;
1411
1412    // TODO: currently we always rebuild expressions.  When we
1413    // properly get lazier about this, we should use the same
1414    // logic to avoid rebuilding prototypes here.
1415    if (P->hasDefaultArg())
1416      return true;
1417  }
1418
1419  return false;
1420}
1421
1422/// A form of SubstType intended specifically for instantiating the
1423/// type of a FunctionDecl.  Its purpose is solely to force the
1424/// instantiation of default-argument expressions.
1425TypeSourceInfo *Sema::SubstFunctionDeclType(TypeSourceInfo *T,
1426                                const MultiLevelTemplateArgumentList &Args,
1427                                SourceLocation Loc,
1428                                DeclarationName Entity) {
1429  assert(!ActiveTemplateInstantiations.empty() &&
1430         "Cannot perform an instantiation without some context on the "
1431         "instantiation stack");
1432
1433  if (!NeedsInstantiationAsFunctionType(T))
1434    return T;
1435
1436  TemplateInstantiator Instantiator(*this, Args, Loc, Entity);
1437
1438  TypeLocBuilder TLB;
1439
1440  TypeLoc TL = T->getTypeLoc();
1441  TLB.reserve(TL.getFullDataSize());
1442
1443  QualType Result = Instantiator.TransformType(TLB, TL);
1444  if (Result.isNull())
1445    return 0;
1446
1447  return TLB.getTypeSourceInfo(Context, Result);
1448}
1449
1450ParmVarDecl *Sema::SubstParmVarDecl(ParmVarDecl *OldParm,
1451                            const MultiLevelTemplateArgumentList &TemplateArgs,
1452                                    int indexAdjustment,
1453                                    llvm::Optional<unsigned> NumExpansions) {
1454  TypeSourceInfo *OldDI = OldParm->getTypeSourceInfo();
1455  TypeSourceInfo *NewDI = 0;
1456
1457  TypeLoc OldTL = OldDI->getTypeLoc();
1458  if (isa<PackExpansionTypeLoc>(OldTL)) {
1459    PackExpansionTypeLoc ExpansionTL = cast<PackExpansionTypeLoc>(OldTL);
1460
1461    // We have a function parameter pack. Substitute into the pattern of the
1462    // expansion.
1463    NewDI = SubstType(ExpansionTL.getPatternLoc(), TemplateArgs,
1464                      OldParm->getLocation(), OldParm->getDeclName());
1465    if (!NewDI)
1466      return 0;
1467
1468    if (NewDI->getType()->containsUnexpandedParameterPack()) {
1469      // We still have unexpanded parameter packs, which means that
1470      // our function parameter is still a function parameter pack.
1471      // Therefore, make its type a pack expansion type.
1472      NewDI = CheckPackExpansion(NewDI, ExpansionTL.getEllipsisLoc(),
1473                                 NumExpansions);
1474    }
1475  } else {
1476    NewDI = SubstType(OldDI, TemplateArgs, OldParm->getLocation(),
1477                      OldParm->getDeclName());
1478  }
1479
1480  if (!NewDI)
1481    return 0;
1482
1483  if (NewDI->getType()->isVoidType()) {
1484    Diag(OldParm->getLocation(), diag::err_param_with_void_type);
1485    return 0;
1486  }
1487
1488  ParmVarDecl *NewParm = CheckParameter(Context.getTranslationUnitDecl(),
1489                                        OldParm->getInnerLocStart(),
1490                                        OldParm->getLocation(),
1491                                        OldParm->getIdentifier(),
1492                                        NewDI->getType(), NewDI,
1493                                        OldParm->getStorageClass(),
1494                                        OldParm->getStorageClassAsWritten());
1495  if (!NewParm)
1496    return 0;
1497
1498  // Mark the (new) default argument as uninstantiated (if any).
1499  if (OldParm->hasUninstantiatedDefaultArg()) {
1500    Expr *Arg = OldParm->getUninstantiatedDefaultArg();
1501    NewParm->setUninstantiatedDefaultArg(Arg);
1502  } else if (OldParm->hasUnparsedDefaultArg()) {
1503    NewParm->setUnparsedDefaultArg();
1504    UnparsedDefaultArgInstantiations[OldParm].push_back(NewParm);
1505  } else if (Expr *Arg = OldParm->getDefaultArg())
1506    NewParm->setUninstantiatedDefaultArg(Arg);
1507
1508  NewParm->setHasInheritedDefaultArg(OldParm->hasInheritedDefaultArg());
1509
1510  // FIXME: When OldParm is a parameter pack and NewParm is not a parameter
1511  // pack, we actually have a set of instantiated locations. Maintain this set!
1512  if (OldParm->isParameterPack() && !NewParm->isParameterPack()) {
1513    // Add the new parameter to
1514    CurrentInstantiationScope->InstantiatedLocalPackArg(OldParm, NewParm);
1515  } else {
1516    // Introduce an Old -> New mapping
1517    CurrentInstantiationScope->InstantiatedLocal(OldParm, NewParm);
1518  }
1519
1520  // FIXME: OldParm may come from a FunctionProtoType, in which case CurContext
1521  // can be anything, is this right ?
1522  NewParm->setDeclContext(CurContext);
1523
1524  NewParm->setScopeInfo(OldParm->getFunctionScopeDepth(),
1525                        OldParm->getFunctionScopeIndex() + indexAdjustment);
1526
1527  return NewParm;
1528}
1529
1530/// \brief Substitute the given template arguments into the given set of
1531/// parameters, producing the set of parameter types that would be generated
1532/// from such a substitution.
1533bool Sema::SubstParmTypes(SourceLocation Loc,
1534                          ParmVarDecl **Params, unsigned NumParams,
1535                          const MultiLevelTemplateArgumentList &TemplateArgs,
1536                          SmallVectorImpl<QualType> &ParamTypes,
1537                          SmallVectorImpl<ParmVarDecl *> *OutParams) {
1538  assert(!ActiveTemplateInstantiations.empty() &&
1539         "Cannot perform an instantiation without some context on the "
1540         "instantiation stack");
1541
1542  TemplateInstantiator Instantiator(*this, TemplateArgs, Loc,
1543                                    DeclarationName());
1544  return Instantiator.TransformFunctionTypeParams(Loc, Params, NumParams, 0,
1545                                                  ParamTypes, OutParams);
1546}
1547
1548/// \brief Perform substitution on the base class specifiers of the
1549/// given class template specialization.
1550///
1551/// Produces a diagnostic and returns true on error, returns false and
1552/// attaches the instantiated base classes to the class template
1553/// specialization if successful.
1554bool
1555Sema::SubstBaseSpecifiers(CXXRecordDecl *Instantiation,
1556                          CXXRecordDecl *Pattern,
1557                          const MultiLevelTemplateArgumentList &TemplateArgs) {
1558  bool Invalid = false;
1559  SmallVector<CXXBaseSpecifier*, 4> InstantiatedBases;
1560  for (ClassTemplateSpecializationDecl::base_class_iterator
1561         Base = Pattern->bases_begin(), BaseEnd = Pattern->bases_end();
1562       Base != BaseEnd; ++Base) {
1563    if (!Base->getType()->isDependentType()) {
1564      InstantiatedBases.push_back(new (Context) CXXBaseSpecifier(*Base));
1565      continue;
1566    }
1567
1568    SourceLocation EllipsisLoc;
1569    TypeSourceInfo *BaseTypeLoc;
1570    if (Base->isPackExpansion()) {
1571      // This is a pack expansion. See whether we should expand it now, or
1572      // wait until later.
1573      SmallVector<UnexpandedParameterPack, 2> Unexpanded;
1574      collectUnexpandedParameterPacks(Base->getTypeSourceInfo()->getTypeLoc(),
1575                                      Unexpanded);
1576      bool ShouldExpand = false;
1577      bool RetainExpansion = false;
1578      llvm::Optional<unsigned> NumExpansions;
1579      if (CheckParameterPacksForExpansion(Base->getEllipsisLoc(),
1580                                          Base->getSourceRange(),
1581                                          Unexpanded,
1582                                          TemplateArgs, ShouldExpand,
1583                                          RetainExpansion,
1584                                          NumExpansions)) {
1585        Invalid = true;
1586        continue;
1587      }
1588
1589      // If we should expand this pack expansion now, do so.
1590      if (ShouldExpand) {
1591        for (unsigned I = 0; I != *NumExpansions; ++I) {
1592            Sema::ArgumentPackSubstitutionIndexRAII SubstIndex(*this, I);
1593
1594          TypeSourceInfo *BaseTypeLoc = SubstType(Base->getTypeSourceInfo(),
1595                                                  TemplateArgs,
1596                                              Base->getSourceRange().getBegin(),
1597                                                  DeclarationName());
1598          if (!BaseTypeLoc) {
1599            Invalid = true;
1600            continue;
1601          }
1602
1603          if (CXXBaseSpecifier *InstantiatedBase
1604                = CheckBaseSpecifier(Instantiation,
1605                                     Base->getSourceRange(),
1606                                     Base->isVirtual(),
1607                                     Base->getAccessSpecifierAsWritten(),
1608                                     BaseTypeLoc,
1609                                     SourceLocation()))
1610            InstantiatedBases.push_back(InstantiatedBase);
1611          else
1612            Invalid = true;
1613        }
1614
1615        continue;
1616      }
1617
1618      // The resulting base specifier will (still) be a pack expansion.
1619      EllipsisLoc = Base->getEllipsisLoc();
1620      Sema::ArgumentPackSubstitutionIndexRAII SubstIndex(*this, -1);
1621      BaseTypeLoc = SubstType(Base->getTypeSourceInfo(),
1622                              TemplateArgs,
1623                              Base->getSourceRange().getBegin(),
1624                              DeclarationName());
1625    } else {
1626      BaseTypeLoc = SubstType(Base->getTypeSourceInfo(),
1627                              TemplateArgs,
1628                              Base->getSourceRange().getBegin(),
1629                              DeclarationName());
1630    }
1631
1632    if (!BaseTypeLoc) {
1633      Invalid = true;
1634      continue;
1635    }
1636
1637    if (CXXBaseSpecifier *InstantiatedBase
1638          = CheckBaseSpecifier(Instantiation,
1639                               Base->getSourceRange(),
1640                               Base->isVirtual(),
1641                               Base->getAccessSpecifierAsWritten(),
1642                               BaseTypeLoc,
1643                               EllipsisLoc))
1644      InstantiatedBases.push_back(InstantiatedBase);
1645    else
1646      Invalid = true;
1647  }
1648
1649  if (!Invalid &&
1650      AttachBaseSpecifiers(Instantiation, InstantiatedBases.data(),
1651                           InstantiatedBases.size()))
1652    Invalid = true;
1653
1654  return Invalid;
1655}
1656
1657/// \brief Instantiate the definition of a class from a given pattern.
1658///
1659/// \param PointOfInstantiation The point of instantiation within the
1660/// source code.
1661///
1662/// \param Instantiation is the declaration whose definition is being
1663/// instantiated. This will be either a class template specialization
1664/// or a member class of a class template specialization.
1665///
1666/// \param Pattern is the pattern from which the instantiation
1667/// occurs. This will be either the declaration of a class template or
1668/// the declaration of a member class of a class template.
1669///
1670/// \param TemplateArgs The template arguments to be substituted into
1671/// the pattern.
1672///
1673/// \param TSK the kind of implicit or explicit instantiation to perform.
1674///
1675/// \param Complain whether to complain if the class cannot be instantiated due
1676/// to the lack of a definition.
1677///
1678/// \returns true if an error occurred, false otherwise.
1679bool
1680Sema::InstantiateClass(SourceLocation PointOfInstantiation,
1681                       CXXRecordDecl *Instantiation, CXXRecordDecl *Pattern,
1682                       const MultiLevelTemplateArgumentList &TemplateArgs,
1683                       TemplateSpecializationKind TSK,
1684                       bool Complain) {
1685  bool Invalid = false;
1686
1687  CXXRecordDecl *PatternDef
1688    = cast_or_null<CXXRecordDecl>(Pattern->getDefinition());
1689  if (!PatternDef || PatternDef->isBeingDefined()) {
1690    if (!Complain || (PatternDef && PatternDef->isInvalidDecl())) {
1691      // Say nothing
1692    } else if (PatternDef) {
1693      assert(PatternDef->isBeingDefined());
1694      Diag(PointOfInstantiation,
1695           diag::err_template_instantiate_within_definition)
1696        << (TSK != TSK_ImplicitInstantiation)
1697        << Context.getTypeDeclType(Instantiation);
1698      // Not much point in noting the template declaration here, since
1699      // we're lexically inside it.
1700      Instantiation->setInvalidDecl();
1701    } else if (Pattern == Instantiation->getInstantiatedFromMemberClass()) {
1702      Diag(PointOfInstantiation,
1703           diag::err_implicit_instantiate_member_undefined)
1704        << Context.getTypeDeclType(Instantiation);
1705      Diag(Pattern->getLocation(), diag::note_member_of_template_here);
1706    } else {
1707      Diag(PointOfInstantiation, diag::err_template_instantiate_undefined)
1708        << (TSK != TSK_ImplicitInstantiation)
1709        << Context.getTypeDeclType(Instantiation);
1710      Diag(Pattern->getLocation(), diag::note_template_decl_here);
1711    }
1712    return true;
1713  }
1714  Pattern = PatternDef;
1715
1716  // \brief Record the point of instantiation.
1717  if (MemberSpecializationInfo *MSInfo
1718        = Instantiation->getMemberSpecializationInfo()) {
1719    MSInfo->setTemplateSpecializationKind(TSK);
1720    MSInfo->setPointOfInstantiation(PointOfInstantiation);
1721  } else if (ClassTemplateSpecializationDecl *Spec
1722               = dyn_cast<ClassTemplateSpecializationDecl>(Instantiation)) {
1723    Spec->setTemplateSpecializationKind(TSK);
1724    Spec->setPointOfInstantiation(PointOfInstantiation);
1725  }
1726
1727  InstantiatingTemplate Inst(*this, PointOfInstantiation, Instantiation);
1728  if (Inst)
1729    return true;
1730
1731  // Enter the scope of this instantiation. We don't use
1732  // PushDeclContext because we don't have a scope.
1733  ContextRAII SavedContext(*this, Instantiation);
1734  EnterExpressionEvaluationContext EvalContext(*this,
1735                                               Sema::PotentiallyEvaluated);
1736
1737  // If this is an instantiation of a local class, merge this local
1738  // instantiation scope with the enclosing scope. Otherwise, every
1739  // instantiation of a class has its own local instantiation scope.
1740  bool MergeWithParentScope = !Instantiation->isDefinedOutsideFunctionOrMethod();
1741  LocalInstantiationScope Scope(*this, MergeWithParentScope);
1742
1743  // Pull attributes from the pattern onto the instantiation.
1744  InstantiateAttrs(TemplateArgs, Pattern, Instantiation);
1745
1746  // Start the definition of this instantiation.
1747  Instantiation->startDefinition();
1748
1749  Instantiation->setTagKind(Pattern->getTagKind());
1750
1751  // Do substitution on the base class specifiers.
1752  if (SubstBaseSpecifiers(Instantiation, Pattern, TemplateArgs))
1753    Invalid = true;
1754
1755  TemplateDeclInstantiator Instantiator(*this, Instantiation, TemplateArgs);
1756  SmallVector<Decl*, 4> Fields;
1757  SmallVector<std::pair<FieldDecl*, FieldDecl*>, 4>
1758    FieldsWithMemberInitializers;
1759  for (RecordDecl::decl_iterator Member = Pattern->decls_begin(),
1760         MemberEnd = Pattern->decls_end();
1761       Member != MemberEnd; ++Member) {
1762    // Don't instantiate members not belonging in this semantic context.
1763    // e.g. for:
1764    // @code
1765    //    template <int i> class A {
1766    //      class B *g;
1767    //    };
1768    // @endcode
1769    // 'class B' has the template as lexical context but semantically it is
1770    // introduced in namespace scope.
1771    if ((*Member)->getDeclContext() != Pattern)
1772      continue;
1773
1774    if ((*Member)->isInvalidDecl()) {
1775      Invalid = true;
1776      continue;
1777    }
1778
1779    Decl *NewMember = Instantiator.Visit(*Member);
1780    if (NewMember) {
1781      if (FieldDecl *Field = dyn_cast<FieldDecl>(NewMember)) {
1782        Fields.push_back(Field);
1783        FieldDecl *OldField = cast<FieldDecl>(*Member);
1784        if (OldField->getInClassInitializer())
1785          FieldsWithMemberInitializers.push_back(std::make_pair(OldField,
1786                                                                Field));
1787      } else if (NewMember->isInvalidDecl())
1788        Invalid = true;
1789    } else {
1790      // FIXME: Eventually, a NULL return will mean that one of the
1791      // instantiations was a semantic disaster, and we'll want to set Invalid =
1792      // true. For now, we expect to skip some members that we can't yet handle.
1793    }
1794  }
1795
1796  // Finish checking fields.
1797  ActOnFields(0, Instantiation->getLocation(), Instantiation, Fields,
1798              SourceLocation(), SourceLocation(), 0);
1799  CheckCompletedCXXClass(Instantiation);
1800
1801  // Attach any in-class member initializers now the class is complete.
1802  for (unsigned I = 0, N = FieldsWithMemberInitializers.size(); I != N; ++I) {
1803    FieldDecl *OldField = FieldsWithMemberInitializers[I].first;
1804    FieldDecl *NewField = FieldsWithMemberInitializers[I].second;
1805    Expr *OldInit = OldField->getInClassInitializer();
1806
1807    SourceLocation LParenLoc, RParenLoc;
1808    ASTOwningVector<Expr*> NewArgs(*this);
1809    if (InstantiateInitializer(OldInit, TemplateArgs, LParenLoc, NewArgs,
1810                               RParenLoc))
1811      NewField->setInvalidDecl();
1812    else {
1813      assert(NewArgs.size() == 1 && "wrong number of in-class initializers");
1814      ActOnCXXInClassMemberInitializer(NewField, LParenLoc, NewArgs[0]);
1815    }
1816  }
1817
1818  if (!FieldsWithMemberInitializers.empty())
1819    ActOnFinishDelayedMemberInitializers(Instantiation);
1820
1821  if (Instantiation->isInvalidDecl())
1822    Invalid = true;
1823  else {
1824    // Instantiate any out-of-line class template partial
1825    // specializations now.
1826    for (TemplateDeclInstantiator::delayed_partial_spec_iterator
1827              P = Instantiator.delayed_partial_spec_begin(),
1828           PEnd = Instantiator.delayed_partial_spec_end();
1829         P != PEnd; ++P) {
1830      if (!Instantiator.InstantiateClassTemplatePartialSpecialization(
1831                                                                P->first,
1832                                                                P->second)) {
1833        Invalid = true;
1834        break;
1835      }
1836    }
1837  }
1838
1839  // Exit the scope of this instantiation.
1840  SavedContext.pop();
1841
1842  if (!Invalid) {
1843    Consumer.HandleTagDeclDefinition(Instantiation);
1844
1845    // Always emit the vtable for an explicit instantiation definition
1846    // of a polymorphic class template specialization.
1847    if (TSK == TSK_ExplicitInstantiationDefinition)
1848      MarkVTableUsed(PointOfInstantiation, Instantiation, true);
1849  }
1850
1851  return Invalid;
1852}
1853
1854namespace {
1855  /// \brief A partial specialization whose template arguments have matched
1856  /// a given template-id.
1857  struct PartialSpecMatchResult {
1858    ClassTemplatePartialSpecializationDecl *Partial;
1859    TemplateArgumentList *Args;
1860  };
1861}
1862
1863bool
1864Sema::InstantiateClassTemplateSpecialization(
1865                           SourceLocation PointOfInstantiation,
1866                           ClassTemplateSpecializationDecl *ClassTemplateSpec,
1867                           TemplateSpecializationKind TSK,
1868                           bool Complain) {
1869  // Perform the actual instantiation on the canonical declaration.
1870  ClassTemplateSpec = cast<ClassTemplateSpecializationDecl>(
1871                                         ClassTemplateSpec->getCanonicalDecl());
1872
1873  // Check whether we have already instantiated or specialized this class
1874  // template specialization.
1875  if (ClassTemplateSpec->getSpecializationKind() != TSK_Undeclared) {
1876    if (ClassTemplateSpec->getSpecializationKind() ==
1877          TSK_ExplicitInstantiationDeclaration &&
1878        TSK == TSK_ExplicitInstantiationDefinition) {
1879      // An explicit instantiation definition follows an explicit instantiation
1880      // declaration (C++0x [temp.explicit]p10); go ahead and perform the
1881      // explicit instantiation.
1882      ClassTemplateSpec->setSpecializationKind(TSK);
1883
1884      // If this is an explicit instantiation definition, mark the
1885      // vtable as used.
1886      if (TSK == TSK_ExplicitInstantiationDefinition)
1887        MarkVTableUsed(PointOfInstantiation, ClassTemplateSpec, true);
1888
1889      return false;
1890    }
1891
1892    // We can only instantiate something that hasn't already been
1893    // instantiated or specialized. Fail without any diagnostics: our
1894    // caller will provide an error message.
1895    return true;
1896  }
1897
1898  if (ClassTemplateSpec->isInvalidDecl())
1899    return true;
1900
1901  ClassTemplateDecl *Template = ClassTemplateSpec->getSpecializedTemplate();
1902  CXXRecordDecl *Pattern = 0;
1903
1904  // C++ [temp.class.spec.match]p1:
1905  //   When a class template is used in a context that requires an
1906  //   instantiation of the class, it is necessary to determine
1907  //   whether the instantiation is to be generated using the primary
1908  //   template or one of the partial specializations. This is done by
1909  //   matching the template arguments of the class template
1910  //   specialization with the template argument lists of the partial
1911  //   specializations.
1912  typedef PartialSpecMatchResult MatchResult;
1913  SmallVector<MatchResult, 4> Matched;
1914  SmallVector<ClassTemplatePartialSpecializationDecl *, 4> PartialSpecs;
1915  Template->getPartialSpecializations(PartialSpecs);
1916  for (unsigned I = 0, N = PartialSpecs.size(); I != N; ++I) {
1917    ClassTemplatePartialSpecializationDecl *Partial = PartialSpecs[I];
1918    TemplateDeductionInfo Info(Context, PointOfInstantiation);
1919    if (TemplateDeductionResult Result
1920          = DeduceTemplateArguments(Partial,
1921                                    ClassTemplateSpec->getTemplateArgs(),
1922                                    Info)) {
1923      // FIXME: Store the failed-deduction information for use in
1924      // diagnostics, later.
1925      (void)Result;
1926    } else {
1927      Matched.push_back(PartialSpecMatchResult());
1928      Matched.back().Partial = Partial;
1929      Matched.back().Args = Info.take();
1930    }
1931  }
1932
1933  // If we're dealing with a member template where the template parameters
1934  // have been instantiated, this provides the original template parameters
1935  // from which the member template's parameters were instantiated.
1936  SmallVector<const NamedDecl *, 4> InstantiatedTemplateParameters;
1937
1938  if (Matched.size() >= 1) {
1939    SmallVector<MatchResult, 4>::iterator Best = Matched.begin();
1940    if (Matched.size() == 1) {
1941      //   -- If exactly one matching specialization is found, the
1942      //      instantiation is generated from that specialization.
1943      // We don't need to do anything for this.
1944    } else {
1945      //   -- If more than one matching specialization is found, the
1946      //      partial order rules (14.5.4.2) are used to determine
1947      //      whether one of the specializations is more specialized
1948      //      than the others. If none of the specializations is more
1949      //      specialized than all of the other matching
1950      //      specializations, then the use of the class template is
1951      //      ambiguous and the program is ill-formed.
1952      for (SmallVector<MatchResult, 4>::iterator P = Best + 1,
1953                                                    PEnd = Matched.end();
1954           P != PEnd; ++P) {
1955        if (getMoreSpecializedPartialSpecialization(P->Partial, Best->Partial,
1956                                                    PointOfInstantiation)
1957              == P->Partial)
1958          Best = P;
1959      }
1960
1961      // Determine if the best partial specialization is more specialized than
1962      // the others.
1963      bool Ambiguous = false;
1964      for (SmallVector<MatchResult, 4>::iterator P = Matched.begin(),
1965                                                    PEnd = Matched.end();
1966           P != PEnd; ++P) {
1967        if (P != Best &&
1968            getMoreSpecializedPartialSpecialization(P->Partial, Best->Partial,
1969                                                    PointOfInstantiation)
1970              != Best->Partial) {
1971          Ambiguous = true;
1972          break;
1973        }
1974      }
1975
1976      if (Ambiguous) {
1977        // Partial ordering did not produce a clear winner. Complain.
1978        ClassTemplateSpec->setInvalidDecl();
1979        Diag(PointOfInstantiation, diag::err_partial_spec_ordering_ambiguous)
1980          << ClassTemplateSpec;
1981
1982        // Print the matching partial specializations.
1983        for (SmallVector<MatchResult, 4>::iterator P = Matched.begin(),
1984                                                      PEnd = Matched.end();
1985             P != PEnd; ++P)
1986          Diag(P->Partial->getLocation(), diag::note_partial_spec_match)
1987            << getTemplateArgumentBindingsText(
1988                                            P->Partial->getTemplateParameters(),
1989                                               *P->Args);
1990
1991        return true;
1992      }
1993    }
1994
1995    // Instantiate using the best class template partial specialization.
1996    ClassTemplatePartialSpecializationDecl *OrigPartialSpec = Best->Partial;
1997    while (OrigPartialSpec->getInstantiatedFromMember()) {
1998      // If we've found an explicit specialization of this class template,
1999      // stop here and use that as the pattern.
2000      if (OrigPartialSpec->isMemberSpecialization())
2001        break;
2002
2003      OrigPartialSpec = OrigPartialSpec->getInstantiatedFromMember();
2004    }
2005
2006    Pattern = OrigPartialSpec;
2007    ClassTemplateSpec->setInstantiationOf(Best->Partial, Best->Args);
2008  } else {
2009    //   -- If no matches are found, the instantiation is generated
2010    //      from the primary template.
2011    ClassTemplateDecl *OrigTemplate = Template;
2012    while (OrigTemplate->getInstantiatedFromMemberTemplate()) {
2013      // If we've found an explicit specialization of this class template,
2014      // stop here and use that as the pattern.
2015      if (OrigTemplate->isMemberSpecialization())
2016        break;
2017
2018      OrigTemplate = OrigTemplate->getInstantiatedFromMemberTemplate();
2019    }
2020
2021    Pattern = OrigTemplate->getTemplatedDecl();
2022  }
2023
2024  bool Result = InstantiateClass(PointOfInstantiation, ClassTemplateSpec,
2025                                 Pattern,
2026                                getTemplateInstantiationArgs(ClassTemplateSpec),
2027                                 TSK,
2028                                 Complain);
2029
2030  return Result;
2031}
2032
2033/// \brief Instantiates the definitions of all of the member
2034/// of the given class, which is an instantiation of a class template
2035/// or a member class of a template.
2036void
2037Sema::InstantiateClassMembers(SourceLocation PointOfInstantiation,
2038                              CXXRecordDecl *Instantiation,
2039                        const MultiLevelTemplateArgumentList &TemplateArgs,
2040                              TemplateSpecializationKind TSK) {
2041  for (DeclContext::decl_iterator D = Instantiation->decls_begin(),
2042                               DEnd = Instantiation->decls_end();
2043       D != DEnd; ++D) {
2044    bool SuppressNew = false;
2045    if (FunctionDecl *Function = dyn_cast<FunctionDecl>(*D)) {
2046      if (FunctionDecl *Pattern
2047            = Function->getInstantiatedFromMemberFunction()) {
2048        MemberSpecializationInfo *MSInfo
2049          = Function->getMemberSpecializationInfo();
2050        assert(MSInfo && "No member specialization information?");
2051        if (MSInfo->getTemplateSpecializationKind()
2052                                                 == TSK_ExplicitSpecialization)
2053          continue;
2054
2055        if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
2056                                                   Function,
2057                                        MSInfo->getTemplateSpecializationKind(),
2058                                              MSInfo->getPointOfInstantiation(),
2059                                                   SuppressNew) ||
2060            SuppressNew)
2061          continue;
2062
2063        if (Function->isDefined())
2064          continue;
2065
2066        if (TSK == TSK_ExplicitInstantiationDefinition) {
2067          // C++0x [temp.explicit]p8:
2068          //   An explicit instantiation definition that names a class template
2069          //   specialization explicitly instantiates the class template
2070          //   specialization and is only an explicit instantiation definition
2071          //   of members whose definition is visible at the point of
2072          //   instantiation.
2073          if (!Pattern->isDefined())
2074            continue;
2075
2076          Function->setTemplateSpecializationKind(TSK, PointOfInstantiation);
2077
2078          InstantiateFunctionDefinition(PointOfInstantiation, Function);
2079        } else {
2080          Function->setTemplateSpecializationKind(TSK, PointOfInstantiation);
2081        }
2082      }
2083    } else if (VarDecl *Var = dyn_cast<VarDecl>(*D)) {
2084      if (Var->isStaticDataMember()) {
2085        MemberSpecializationInfo *MSInfo = Var->getMemberSpecializationInfo();
2086        assert(MSInfo && "No member specialization information?");
2087        if (MSInfo->getTemplateSpecializationKind()
2088                                                 == TSK_ExplicitSpecialization)
2089          continue;
2090
2091        if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
2092                                                   Var,
2093                                        MSInfo->getTemplateSpecializationKind(),
2094                                              MSInfo->getPointOfInstantiation(),
2095                                                   SuppressNew) ||
2096            SuppressNew)
2097          continue;
2098
2099        if (TSK == TSK_ExplicitInstantiationDefinition) {
2100          // C++0x [temp.explicit]p8:
2101          //   An explicit instantiation definition that names a class template
2102          //   specialization explicitly instantiates the class template
2103          //   specialization and is only an explicit instantiation definition
2104          //   of members whose definition is visible at the point of
2105          //   instantiation.
2106          if (!Var->getInstantiatedFromStaticDataMember()
2107                                                     ->getOutOfLineDefinition())
2108            continue;
2109
2110          Var->setTemplateSpecializationKind(TSK, PointOfInstantiation);
2111          InstantiateStaticDataMemberDefinition(PointOfInstantiation, Var);
2112        } else {
2113          Var->setTemplateSpecializationKind(TSK, PointOfInstantiation);
2114        }
2115      }
2116    } else if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(*D)) {
2117      // Always skip the injected-class-name, along with any
2118      // redeclarations of nested classes, since both would cause us
2119      // to try to instantiate the members of a class twice.
2120      if (Record->isInjectedClassName() || Record->getPreviousDeclaration())
2121        continue;
2122
2123      MemberSpecializationInfo *MSInfo = Record->getMemberSpecializationInfo();
2124      assert(MSInfo && "No member specialization information?");
2125
2126      if (MSInfo->getTemplateSpecializationKind()
2127                                                == TSK_ExplicitSpecialization)
2128        continue;
2129
2130      if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
2131                                                 Record,
2132                                        MSInfo->getTemplateSpecializationKind(),
2133                                              MSInfo->getPointOfInstantiation(),
2134                                                 SuppressNew) ||
2135          SuppressNew)
2136        continue;
2137
2138      CXXRecordDecl *Pattern = Record->getInstantiatedFromMemberClass();
2139      assert(Pattern && "Missing instantiated-from-template information");
2140
2141      if (!Record->getDefinition()) {
2142        if (!Pattern->getDefinition()) {
2143          // C++0x [temp.explicit]p8:
2144          //   An explicit instantiation definition that names a class template
2145          //   specialization explicitly instantiates the class template
2146          //   specialization and is only an explicit instantiation definition
2147          //   of members whose definition is visible at the point of
2148          //   instantiation.
2149          if (TSK == TSK_ExplicitInstantiationDeclaration) {
2150            MSInfo->setTemplateSpecializationKind(TSK);
2151            MSInfo->setPointOfInstantiation(PointOfInstantiation);
2152          }
2153
2154          continue;
2155        }
2156
2157        InstantiateClass(PointOfInstantiation, Record, Pattern,
2158                         TemplateArgs,
2159                         TSK);
2160      } else {
2161        if (TSK == TSK_ExplicitInstantiationDefinition &&
2162            Record->getTemplateSpecializationKind() ==
2163                TSK_ExplicitInstantiationDeclaration) {
2164          Record->setTemplateSpecializationKind(TSK);
2165          MarkVTableUsed(PointOfInstantiation, Record, true);
2166        }
2167      }
2168
2169      Pattern = cast_or_null<CXXRecordDecl>(Record->getDefinition());
2170      if (Pattern)
2171        InstantiateClassMembers(PointOfInstantiation, Pattern, TemplateArgs,
2172                                TSK);
2173    }
2174  }
2175}
2176
2177/// \brief Instantiate the definitions of all of the members of the
2178/// given class template specialization, which was named as part of an
2179/// explicit instantiation.
2180void
2181Sema::InstantiateClassTemplateSpecializationMembers(
2182                                           SourceLocation PointOfInstantiation,
2183                            ClassTemplateSpecializationDecl *ClassTemplateSpec,
2184                                               TemplateSpecializationKind TSK) {
2185  // C++0x [temp.explicit]p7:
2186  //   An explicit instantiation that names a class template
2187  //   specialization is an explicit instantion of the same kind
2188  //   (declaration or definition) of each of its members (not
2189  //   including members inherited from base classes) that has not
2190  //   been previously explicitly specialized in the translation unit
2191  //   containing the explicit instantiation, except as described
2192  //   below.
2193  InstantiateClassMembers(PointOfInstantiation, ClassTemplateSpec,
2194                          getTemplateInstantiationArgs(ClassTemplateSpec),
2195                          TSK);
2196}
2197
2198StmtResult
2199Sema::SubstStmt(Stmt *S, const MultiLevelTemplateArgumentList &TemplateArgs) {
2200  if (!S)
2201    return Owned(S);
2202
2203  TemplateInstantiator Instantiator(*this, TemplateArgs,
2204                                    SourceLocation(),
2205                                    DeclarationName());
2206  return Instantiator.TransformStmt(S);
2207}
2208
2209ExprResult
2210Sema::SubstExpr(Expr *E, const MultiLevelTemplateArgumentList &TemplateArgs) {
2211  if (!E)
2212    return Owned(E);
2213
2214  TemplateInstantiator Instantiator(*this, TemplateArgs,
2215                                    SourceLocation(),
2216                                    DeclarationName());
2217  return Instantiator.TransformExpr(E);
2218}
2219
2220bool Sema::SubstExprs(Expr **Exprs, unsigned NumExprs, bool IsCall,
2221                      const MultiLevelTemplateArgumentList &TemplateArgs,
2222                      SmallVectorImpl<Expr *> &Outputs) {
2223  if (NumExprs == 0)
2224    return false;
2225
2226  TemplateInstantiator Instantiator(*this, TemplateArgs,
2227                                    SourceLocation(),
2228                                    DeclarationName());
2229  return Instantiator.TransformExprs(Exprs, NumExprs, IsCall, Outputs);
2230}
2231
2232NestedNameSpecifierLoc
2233Sema::SubstNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS,
2234                        const MultiLevelTemplateArgumentList &TemplateArgs) {
2235  if (!NNS)
2236    return NestedNameSpecifierLoc();
2237
2238  TemplateInstantiator Instantiator(*this, TemplateArgs, NNS.getBeginLoc(),
2239                                    DeclarationName());
2240  return Instantiator.TransformNestedNameSpecifierLoc(NNS);
2241}
2242
2243/// \brief Do template substitution on declaration name info.
2244DeclarationNameInfo
2245Sema::SubstDeclarationNameInfo(const DeclarationNameInfo &NameInfo,
2246                         const MultiLevelTemplateArgumentList &TemplateArgs) {
2247  TemplateInstantiator Instantiator(*this, TemplateArgs, NameInfo.getLoc(),
2248                                    NameInfo.getName());
2249  return Instantiator.TransformDeclarationNameInfo(NameInfo);
2250}
2251
2252TemplateName
2253Sema::SubstTemplateName(NestedNameSpecifierLoc QualifierLoc,
2254                        TemplateName Name, SourceLocation Loc,
2255                        const MultiLevelTemplateArgumentList &TemplateArgs) {
2256  TemplateInstantiator Instantiator(*this, TemplateArgs, Loc,
2257                                    DeclarationName());
2258  CXXScopeSpec SS;
2259  SS.Adopt(QualifierLoc);
2260  return Instantiator.TransformTemplateName(SS, Name, Loc);
2261}
2262
2263bool Sema::Subst(const TemplateArgumentLoc *Args, unsigned NumArgs,
2264                 TemplateArgumentListInfo &Result,
2265                 const MultiLevelTemplateArgumentList &TemplateArgs) {
2266  TemplateInstantiator Instantiator(*this, TemplateArgs, SourceLocation(),
2267                                    DeclarationName());
2268
2269  return Instantiator.TransformTemplateArguments(Args, NumArgs, Result);
2270}
2271
2272llvm::PointerUnion<Decl *, LocalInstantiationScope::DeclArgumentPack *> *
2273LocalInstantiationScope::findInstantiationOf(const Decl *D) {
2274  for (LocalInstantiationScope *Current = this; Current;
2275       Current = Current->Outer) {
2276
2277    // Check if we found something within this scope.
2278    const Decl *CheckD = D;
2279    do {
2280      LocalDeclsMap::iterator Found = Current->LocalDecls.find(CheckD);
2281      if (Found != Current->LocalDecls.end())
2282        return &Found->second;
2283
2284      // If this is a tag declaration, it's possible that we need to look for
2285      // a previous declaration.
2286      if (const TagDecl *Tag = dyn_cast<TagDecl>(CheckD))
2287        CheckD = Tag->getPreviousDeclaration();
2288      else
2289        CheckD = 0;
2290    } while (CheckD);
2291
2292    // If we aren't combined with our outer scope, we're done.
2293    if (!Current->CombineWithOuterScope)
2294      break;
2295  }
2296
2297  // If we didn't find the decl, then we either have a sema bug, or we have a
2298  // forward reference to a label declaration.  Return null to indicate that
2299  // we have an uninstantiated label.
2300  assert(isa<LabelDecl>(D) && "declaration not instantiated in this scope");
2301  return 0;
2302}
2303
2304void LocalInstantiationScope::InstantiatedLocal(const Decl *D, Decl *Inst) {
2305  llvm::PointerUnion<Decl *, DeclArgumentPack *> &Stored = LocalDecls[D];
2306  if (Stored.isNull())
2307    Stored = Inst;
2308  else if (Stored.is<Decl *>()) {
2309    assert(Stored.get<Decl *>() == Inst && "Already instantiated this local");
2310    Stored = Inst;
2311  } else
2312    LocalDecls[D].get<DeclArgumentPack *>()->push_back(Inst);
2313}
2314
2315void LocalInstantiationScope::InstantiatedLocalPackArg(const Decl *D,
2316                                                       Decl *Inst) {
2317  DeclArgumentPack *Pack = LocalDecls[D].get<DeclArgumentPack *>();
2318  Pack->push_back(Inst);
2319}
2320
2321void LocalInstantiationScope::MakeInstantiatedLocalArgPack(const Decl *D) {
2322  llvm::PointerUnion<Decl *, DeclArgumentPack *> &Stored = LocalDecls[D];
2323  assert(Stored.isNull() && "Already instantiated this local");
2324  DeclArgumentPack *Pack = new DeclArgumentPack;
2325  Stored = Pack;
2326  ArgumentPacks.push_back(Pack);
2327}
2328
2329void LocalInstantiationScope::SetPartiallySubstitutedPack(NamedDecl *Pack,
2330                                          const TemplateArgument *ExplicitArgs,
2331                                                    unsigned NumExplicitArgs) {
2332  assert((!PartiallySubstitutedPack || PartiallySubstitutedPack == Pack) &&
2333         "Already have a partially-substituted pack");
2334  assert((!PartiallySubstitutedPack
2335          || NumArgsInPartiallySubstitutedPack == NumExplicitArgs) &&
2336         "Wrong number of arguments in partially-substituted pack");
2337  PartiallySubstitutedPack = Pack;
2338  ArgsInPartiallySubstitutedPack = ExplicitArgs;
2339  NumArgsInPartiallySubstitutedPack = NumExplicitArgs;
2340}
2341
2342NamedDecl *LocalInstantiationScope::getPartiallySubstitutedPack(
2343                                         const TemplateArgument **ExplicitArgs,
2344                                              unsigned *NumExplicitArgs) const {
2345  if (ExplicitArgs)
2346    *ExplicitArgs = 0;
2347  if (NumExplicitArgs)
2348    *NumExplicitArgs = 0;
2349
2350  for (const LocalInstantiationScope *Current = this; Current;
2351       Current = Current->Outer) {
2352    if (Current->PartiallySubstitutedPack) {
2353      if (ExplicitArgs)
2354        *ExplicitArgs = Current->ArgsInPartiallySubstitutedPack;
2355      if (NumExplicitArgs)
2356        *NumExplicitArgs = Current->NumArgsInPartiallySubstitutedPack;
2357
2358      return Current->PartiallySubstitutedPack;
2359    }
2360
2361    if (!Current->CombineWithOuterScope)
2362      break;
2363  }
2364
2365  return 0;
2366}
2367