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/AST/ASTConsumer.h"
16#include "clang/AST/ASTContext.h"
17#include "clang/AST/ASTLambda.h"
18#include "clang/AST/DeclTemplate.h"
19#include "clang/AST/Expr.h"
20#include "clang/Basic/LangOptions.h"
21#include "clang/Sema/DeclSpec.h"
22#include "clang/Sema/Initialization.h"
23#include "clang/Sema/Lookup.h"
24#include "clang/Sema/Template.h"
25#include "clang/Sema/TemplateDeduction.h"
26
27using namespace clang;
28using namespace sema;
29
30//===----------------------------------------------------------------------===/
31// Template Instantiation Support
32//===----------------------------------------------------------------------===/
33
34/// \brief Retrieve the template argument list(s) that should be used to
35/// instantiate the definition of the given declaration.
36///
37/// \param D the declaration for which we are computing template instantiation
38/// arguments.
39///
40/// \param Innermost if non-NULL, the innermost template argument list.
41///
42/// \param RelativeToPrimary true if we should get the template
43/// arguments relative to the primary template, even when we're
44/// dealing with a specialization. This is only relevant for function
45/// template specializations.
46///
47/// \param Pattern If non-NULL, indicates the pattern from which we will be
48/// instantiating the definition of the given declaration, \p D. This is
49/// used to determine the proper set of template instantiation arguments for
50/// friend function template specializations.
51MultiLevelTemplateArgumentList
52Sema::getTemplateInstantiationArgs(NamedDecl *D,
53                                   const TemplateArgumentList *Innermost,
54                                   bool RelativeToPrimary,
55                                   const FunctionDecl *Pattern) {
56  // Accumulate the set of template argument lists in this structure.
57  MultiLevelTemplateArgumentList Result;
58
59  if (Innermost)
60    Result.addOuterTemplateArguments(Innermost);
61
62  DeclContext *Ctx = dyn_cast<DeclContext>(D);
63  if (!Ctx) {
64    Ctx = D->getDeclContext();
65
66    // Add template arguments from a variable template instantiation.
67    if (VarTemplateSpecializationDecl *Spec =
68            dyn_cast<VarTemplateSpecializationDecl>(D)) {
69      // We're done when we hit an explicit specialization.
70      if (Spec->getSpecializationKind() == TSK_ExplicitSpecialization &&
71          !isa<VarTemplatePartialSpecializationDecl>(Spec))
72        return Result;
73
74      Result.addOuterTemplateArguments(&Spec->getTemplateInstantiationArgs());
75
76      // If this variable template specialization was instantiated from a
77      // specialized member that is a variable template, we're done.
78      assert(Spec->getSpecializedTemplate() && "No variable template?");
79      llvm::PointerUnion<VarTemplateDecl*,
80                         VarTemplatePartialSpecializationDecl*> Specialized
81                             = Spec->getSpecializedTemplateOrPartial();
82      if (VarTemplatePartialSpecializationDecl *Partial =
83              Specialized.dyn_cast<VarTemplatePartialSpecializationDecl *>()) {
84        if (Partial->isMemberSpecialization())
85          return Result;
86      } else {
87        VarTemplateDecl *Tmpl = Specialized.get<VarTemplateDecl *>();
88        if (Tmpl->isMemberSpecialization())
89          return Result;
90      }
91    }
92
93    // If we have a template template parameter with translation unit context,
94    // then we're performing substitution into a default template argument of
95    // this template template parameter before we've constructed the template
96    // that will own this template template parameter. In this case, we
97    // use empty template parameter lists for all of the outer templates
98    // to avoid performing any substitutions.
99    if (Ctx->isTranslationUnit()) {
100      if (TemplateTemplateParmDecl *TTP
101                                      = dyn_cast<TemplateTemplateParmDecl>(D)) {
102        for (unsigned I = 0, N = TTP->getDepth() + 1; I != N; ++I)
103          Result.addOuterTemplateArguments(None);
104        return Result;
105      }
106    }
107  }
108
109  while (!Ctx->isFileContext()) {
110    // Add template arguments from a class template instantiation.
111    if (ClassTemplateSpecializationDecl *Spec
112          = dyn_cast<ClassTemplateSpecializationDecl>(Ctx)) {
113      // We're done when we hit an explicit specialization.
114      if (Spec->getSpecializationKind() == TSK_ExplicitSpecialization &&
115          !isa<ClassTemplatePartialSpecializationDecl>(Spec))
116        break;
117
118      Result.addOuterTemplateArguments(&Spec->getTemplateInstantiationArgs());
119
120      // If this class template specialization was instantiated from a
121      // specialized member that is a class template, we're done.
122      assert(Spec->getSpecializedTemplate() && "No class template?");
123      if (Spec->getSpecializedTemplate()->isMemberSpecialization())
124        break;
125    }
126    // Add template arguments from a function template specialization.
127    else if (FunctionDecl *Function = dyn_cast<FunctionDecl>(Ctx)) {
128      if (!RelativeToPrimary &&
129          (Function->getTemplateSpecializationKind() ==
130                                                  TSK_ExplicitSpecialization &&
131           !Function->getClassScopeSpecializationPattern()))
132        break;
133
134      if (const TemplateArgumentList *TemplateArgs
135            = Function->getTemplateSpecializationArgs()) {
136        // Add the template arguments for this specialization.
137        Result.addOuterTemplateArguments(TemplateArgs);
138
139        // If this function was instantiated from a specialized member that is
140        // a function template, we're done.
141        assert(Function->getPrimaryTemplate() && "No function template?");
142        if (Function->getPrimaryTemplate()->isMemberSpecialization())
143          break;
144
145        // If this function is a generic lambda specialization, we are done.
146        if (isGenericLambdaCallOperatorSpecialization(Function))
147          break;
148
149      } else if (FunctionTemplateDecl *FunTmpl
150                                   = Function->getDescribedFunctionTemplate()) {
151        // Add the "injected" template arguments.
152        Result.addOuterTemplateArguments(FunTmpl->getInjectedTemplateArgs());
153      }
154
155      // If this is a friend declaration and it declares an entity at
156      // namespace scope, take arguments from its lexical parent
157      // instead of its semantic parent, unless of course the pattern we're
158      // instantiating actually comes from the file's context!
159      if (Function->getFriendObjectKind() &&
160          Function->getDeclContext()->isFileContext() &&
161          (!Pattern || !Pattern->getLexicalDeclContext()->isFileContext())) {
162        Ctx = Function->getLexicalDeclContext();
163        RelativeToPrimary = false;
164        continue;
165      }
166    } else if (CXXRecordDecl *Rec = dyn_cast<CXXRecordDecl>(Ctx)) {
167      if (ClassTemplateDecl *ClassTemplate = Rec->getDescribedClassTemplate()) {
168        QualType T = ClassTemplate->getInjectedClassNameSpecialization();
169        const TemplateSpecializationType *TST =
170            cast<TemplateSpecializationType>(Context.getCanonicalType(T));
171        Result.addOuterTemplateArguments(
172            llvm::makeArrayRef(TST->getArgs(), TST->getNumArgs()));
173        if (ClassTemplate->isMemberSpecialization())
174          break;
175      }
176    }
177
178    Ctx = Ctx->getParent();
179    RelativeToPrimary = false;
180  }
181
182  return Result;
183}
184
185bool Sema::ActiveTemplateInstantiation::isInstantiationRecord() const {
186  switch (Kind) {
187  case TemplateInstantiation:
188  case ExceptionSpecInstantiation:
189  case DefaultTemplateArgumentInstantiation:
190  case DefaultFunctionArgumentInstantiation:
191  case ExplicitTemplateArgumentSubstitution:
192  case DeducedTemplateArgumentSubstitution:
193  case PriorTemplateArgumentSubstitution:
194    return true;
195
196  case DefaultTemplateArgumentChecking:
197    return false;
198  }
199
200  llvm_unreachable("Invalid InstantiationKind!");
201}
202
203Sema::InstantiatingTemplate::InstantiatingTemplate(
204    Sema &SemaRef, ActiveTemplateInstantiation::InstantiationKind Kind,
205    SourceLocation PointOfInstantiation, SourceRange InstantiationRange,
206    Decl *Entity, NamedDecl *Template, ArrayRef<TemplateArgument> TemplateArgs,
207    sema::TemplateDeductionInfo *DeductionInfo)
208    : SemaRef(SemaRef), SavedInNonInstantiationSFINAEContext(
209                            SemaRef.InNonInstantiationSFINAEContext) {
210  // Don't allow further instantiation if a fatal error has occcured.  Any
211  // diagnostics we might have raised will not be visible.
212  if (SemaRef.Diags.hasFatalErrorOccurred()) {
213    Invalid = true;
214    return;
215  }
216  Invalid = CheckInstantiationDepth(PointOfInstantiation, InstantiationRange);
217  if (!Invalid) {
218    ActiveTemplateInstantiation Inst;
219    Inst.Kind = Kind;
220    Inst.PointOfInstantiation = PointOfInstantiation;
221    Inst.Entity = Entity;
222    Inst.Template = Template;
223    Inst.TemplateArgs = TemplateArgs.data();
224    Inst.NumTemplateArgs = TemplateArgs.size();
225    Inst.DeductionInfo = DeductionInfo;
226    Inst.InstantiationRange = InstantiationRange;
227    SemaRef.InNonInstantiationSFINAEContext = false;
228    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
229    if (!Inst.isInstantiationRecord())
230      ++SemaRef.NonInstantiationEntries;
231  }
232}
233
234Sema::InstantiatingTemplate::InstantiatingTemplate(
235    Sema &SemaRef, SourceLocation PointOfInstantiation, Decl *Entity,
236    SourceRange InstantiationRange)
237    : InstantiatingTemplate(SemaRef,
238                            ActiveTemplateInstantiation::TemplateInstantiation,
239                            PointOfInstantiation, InstantiationRange, Entity) {}
240
241Sema::InstantiatingTemplate::InstantiatingTemplate(
242    Sema &SemaRef, SourceLocation PointOfInstantiation, FunctionDecl *Entity,
243    ExceptionSpecification, SourceRange InstantiationRange)
244    : InstantiatingTemplate(
245          SemaRef, ActiveTemplateInstantiation::ExceptionSpecInstantiation,
246          PointOfInstantiation, InstantiationRange, Entity) {}
247
248Sema::InstantiatingTemplate::InstantiatingTemplate(
249    Sema &SemaRef, SourceLocation PointOfInstantiation, TemplateDecl *Template,
250    ArrayRef<TemplateArgument> TemplateArgs, SourceRange InstantiationRange)
251    : InstantiatingTemplate(
252          SemaRef,
253          ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation,
254          PointOfInstantiation, InstantiationRange, Template, nullptr,
255          TemplateArgs) {}
256
257Sema::InstantiatingTemplate::InstantiatingTemplate(
258    Sema &SemaRef, SourceLocation PointOfInstantiation,
259    FunctionTemplateDecl *FunctionTemplate,
260    ArrayRef<TemplateArgument> TemplateArgs,
261    ActiveTemplateInstantiation::InstantiationKind Kind,
262    sema::TemplateDeductionInfo &DeductionInfo, SourceRange InstantiationRange)
263    : InstantiatingTemplate(SemaRef, Kind, PointOfInstantiation,
264                            InstantiationRange, FunctionTemplate, nullptr,
265                            TemplateArgs, &DeductionInfo) {}
266
267Sema::InstantiatingTemplate::InstantiatingTemplate(
268    Sema &SemaRef, SourceLocation PointOfInstantiation,
269    ClassTemplatePartialSpecializationDecl *PartialSpec,
270    ArrayRef<TemplateArgument> TemplateArgs,
271    sema::TemplateDeductionInfo &DeductionInfo, SourceRange InstantiationRange)
272    : InstantiatingTemplate(
273          SemaRef,
274          ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution,
275          PointOfInstantiation, InstantiationRange, PartialSpec, nullptr,
276          TemplateArgs, &DeductionInfo) {}
277
278Sema::InstantiatingTemplate::InstantiatingTemplate(
279    Sema &SemaRef, SourceLocation PointOfInstantiation,
280    VarTemplatePartialSpecializationDecl *PartialSpec,
281    ArrayRef<TemplateArgument> TemplateArgs,
282    sema::TemplateDeductionInfo &DeductionInfo, SourceRange InstantiationRange)
283    : InstantiatingTemplate(
284          SemaRef,
285          ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution,
286          PointOfInstantiation, InstantiationRange, PartialSpec, nullptr,
287          TemplateArgs, &DeductionInfo) {}
288
289Sema::InstantiatingTemplate::InstantiatingTemplate(
290    Sema &SemaRef, SourceLocation PointOfInstantiation, ParmVarDecl *Param,
291    ArrayRef<TemplateArgument> TemplateArgs, SourceRange InstantiationRange)
292    : InstantiatingTemplate(
293          SemaRef,
294          ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation,
295          PointOfInstantiation, InstantiationRange, Param, nullptr,
296          TemplateArgs) {}
297
298Sema::InstantiatingTemplate::InstantiatingTemplate(
299    Sema &SemaRef, SourceLocation PointOfInstantiation, NamedDecl *Template,
300    NonTypeTemplateParmDecl *Param, ArrayRef<TemplateArgument> TemplateArgs,
301    SourceRange InstantiationRange)
302    : InstantiatingTemplate(
303          SemaRef,
304          ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution,
305          PointOfInstantiation, InstantiationRange, Param, Template,
306          TemplateArgs) {}
307
308Sema::InstantiatingTemplate::InstantiatingTemplate(
309    Sema &SemaRef, SourceLocation PointOfInstantiation, NamedDecl *Template,
310    TemplateTemplateParmDecl *Param, ArrayRef<TemplateArgument> TemplateArgs,
311    SourceRange InstantiationRange)
312    : InstantiatingTemplate(
313          SemaRef,
314          ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution,
315          PointOfInstantiation, InstantiationRange, Param, Template,
316          TemplateArgs) {}
317
318Sema::InstantiatingTemplate::InstantiatingTemplate(
319    Sema &SemaRef, SourceLocation PointOfInstantiation, TemplateDecl *Template,
320    NamedDecl *Param, ArrayRef<TemplateArgument> TemplateArgs,
321    SourceRange InstantiationRange)
322    : InstantiatingTemplate(
323          SemaRef, ActiveTemplateInstantiation::DefaultTemplateArgumentChecking,
324          PointOfInstantiation, InstantiationRange, Param, Template,
325          TemplateArgs) {}
326
327void Sema::InstantiatingTemplate::Clear() {
328  if (!Invalid) {
329    if (!SemaRef.ActiveTemplateInstantiations.back().isInstantiationRecord()) {
330      assert(SemaRef.NonInstantiationEntries > 0);
331      --SemaRef.NonInstantiationEntries;
332    }
333    SemaRef.InNonInstantiationSFINAEContext
334      = SavedInNonInstantiationSFINAEContext;
335
336    // Name lookup no longer looks in this template's defining module.
337    assert(SemaRef.ActiveTemplateInstantiations.size() >=
338           SemaRef.ActiveTemplateInstantiationLookupModules.size() &&
339           "forgot to remove a lookup module for a template instantiation");
340    if (SemaRef.ActiveTemplateInstantiations.size() ==
341        SemaRef.ActiveTemplateInstantiationLookupModules.size()) {
342      if (Module *M = SemaRef.ActiveTemplateInstantiationLookupModules.back())
343        SemaRef.LookupModulesCache.erase(M);
344      SemaRef.ActiveTemplateInstantiationLookupModules.pop_back();
345    }
346
347    SemaRef.ActiveTemplateInstantiations.pop_back();
348    Invalid = true;
349  }
350}
351
352bool Sema::InstantiatingTemplate::CheckInstantiationDepth(
353                                        SourceLocation PointOfInstantiation,
354                                           SourceRange InstantiationRange) {
355  assert(SemaRef.NonInstantiationEntries <=
356                                   SemaRef.ActiveTemplateInstantiations.size());
357  if ((SemaRef.ActiveTemplateInstantiations.size() -
358          SemaRef.NonInstantiationEntries)
359        <= SemaRef.getLangOpts().InstantiationDepth)
360    return false;
361
362  SemaRef.Diag(PointOfInstantiation,
363               diag::err_template_recursion_depth_exceeded)
364    << SemaRef.getLangOpts().InstantiationDepth
365    << InstantiationRange;
366  SemaRef.Diag(PointOfInstantiation, diag::note_template_recursion_depth)
367    << SemaRef.getLangOpts().InstantiationDepth;
368  return true;
369}
370
371/// \brief Prints the current instantiation stack through a series of
372/// notes.
373void Sema::PrintInstantiationStack() {
374  // Determine which template instantiations to skip, if any.
375  unsigned SkipStart = ActiveTemplateInstantiations.size(), SkipEnd = SkipStart;
376  unsigned Limit = Diags.getTemplateBacktraceLimit();
377  if (Limit && Limit < ActiveTemplateInstantiations.size()) {
378    SkipStart = Limit / 2 + Limit % 2;
379    SkipEnd = ActiveTemplateInstantiations.size() - Limit / 2;
380  }
381
382  // FIXME: In all of these cases, we need to show the template arguments
383  unsigned InstantiationIdx = 0;
384  for (SmallVectorImpl<ActiveTemplateInstantiation>::reverse_iterator
385         Active = ActiveTemplateInstantiations.rbegin(),
386         ActiveEnd = ActiveTemplateInstantiations.rend();
387       Active != ActiveEnd;
388       ++Active, ++InstantiationIdx) {
389    // Skip this instantiation?
390    if (InstantiationIdx >= SkipStart && InstantiationIdx < SkipEnd) {
391      if (InstantiationIdx == SkipStart) {
392        // Note that we're skipping instantiations.
393        Diags.Report(Active->PointOfInstantiation,
394                     diag::note_instantiation_contexts_suppressed)
395          << unsigned(ActiveTemplateInstantiations.size() - Limit);
396      }
397      continue;
398    }
399
400    switch (Active->Kind) {
401    case ActiveTemplateInstantiation::TemplateInstantiation: {
402      Decl *D = Active->Entity;
403      if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(D)) {
404        unsigned DiagID = diag::note_template_member_class_here;
405        if (isa<ClassTemplateSpecializationDecl>(Record))
406          DiagID = diag::note_template_class_instantiation_here;
407        Diags.Report(Active->PointOfInstantiation, DiagID)
408          << Context.getTypeDeclType(Record)
409          << Active->InstantiationRange;
410      } else if (FunctionDecl *Function = dyn_cast<FunctionDecl>(D)) {
411        unsigned DiagID;
412        if (Function->getPrimaryTemplate())
413          DiagID = diag::note_function_template_spec_here;
414        else
415          DiagID = diag::note_template_member_function_here;
416        Diags.Report(Active->PointOfInstantiation, DiagID)
417          << Function
418          << Active->InstantiationRange;
419      } else if (VarDecl *VD = dyn_cast<VarDecl>(D)) {
420        Diags.Report(Active->PointOfInstantiation,
421                     VD->isStaticDataMember()?
422                       diag::note_template_static_data_member_def_here
423                     : diag::note_template_variable_def_here)
424          << VD
425          << Active->InstantiationRange;
426      } else if (EnumDecl *ED = dyn_cast<EnumDecl>(D)) {
427        Diags.Report(Active->PointOfInstantiation,
428                     diag::note_template_enum_def_here)
429          << ED
430          << Active->InstantiationRange;
431      } else if (FieldDecl *FD = dyn_cast<FieldDecl>(D)) {
432        Diags.Report(Active->PointOfInstantiation,
433                     diag::note_template_nsdmi_here)
434            << FD << Active->InstantiationRange;
435      } else {
436        Diags.Report(Active->PointOfInstantiation,
437                     diag::note_template_type_alias_instantiation_here)
438          << cast<TypeAliasTemplateDecl>(D)
439          << Active->InstantiationRange;
440      }
441      break;
442    }
443
444    case ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation: {
445      TemplateDecl *Template = cast<TemplateDecl>(Active->Entity);
446      SmallVector<char, 128> TemplateArgsStr;
447      llvm::raw_svector_ostream OS(TemplateArgsStr);
448      Template->printName(OS);
449      TemplateSpecializationType::PrintTemplateArgumentList(OS,
450                                                         Active->TemplateArgs,
451                                                      Active->NumTemplateArgs,
452                                                      getPrintingPolicy());
453      Diags.Report(Active->PointOfInstantiation,
454                   diag::note_default_arg_instantiation_here)
455        << OS.str()
456        << Active->InstantiationRange;
457      break;
458    }
459
460    case ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution: {
461      FunctionTemplateDecl *FnTmpl = cast<FunctionTemplateDecl>(Active->Entity);
462      Diags.Report(Active->PointOfInstantiation,
463                   diag::note_explicit_template_arg_substitution_here)
464        << FnTmpl
465        << getTemplateArgumentBindingsText(FnTmpl->getTemplateParameters(),
466                                           Active->TemplateArgs,
467                                           Active->NumTemplateArgs)
468        << Active->InstantiationRange;
469      break;
470    }
471
472    case ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution:
473      if (ClassTemplatePartialSpecializationDecl *PartialSpec =
474            dyn_cast<ClassTemplatePartialSpecializationDecl>(Active->Entity)) {
475        Diags.Report(Active->PointOfInstantiation,
476                     diag::note_partial_spec_deduct_instantiation_here)
477          << Context.getTypeDeclType(PartialSpec)
478          << getTemplateArgumentBindingsText(
479                                         PartialSpec->getTemplateParameters(),
480                                             Active->TemplateArgs,
481                                             Active->NumTemplateArgs)
482          << Active->InstantiationRange;
483      } else {
484        FunctionTemplateDecl *FnTmpl
485          = cast<FunctionTemplateDecl>(Active->Entity);
486        Diags.Report(Active->PointOfInstantiation,
487                     diag::note_function_template_deduction_instantiation_here)
488          << FnTmpl
489          << getTemplateArgumentBindingsText(FnTmpl->getTemplateParameters(),
490                                             Active->TemplateArgs,
491                                             Active->NumTemplateArgs)
492          << Active->InstantiationRange;
493      }
494      break;
495
496    case ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation: {
497      ParmVarDecl *Param = cast<ParmVarDecl>(Active->Entity);
498      FunctionDecl *FD = cast<FunctionDecl>(Param->getDeclContext());
499
500      SmallVector<char, 128> TemplateArgsStr;
501      llvm::raw_svector_ostream OS(TemplateArgsStr);
502      FD->printName(OS);
503      TemplateSpecializationType::PrintTemplateArgumentList(OS,
504                                                         Active->TemplateArgs,
505                                                      Active->NumTemplateArgs,
506                                                      getPrintingPolicy());
507      Diags.Report(Active->PointOfInstantiation,
508                   diag::note_default_function_arg_instantiation_here)
509        << OS.str()
510        << Active->InstantiationRange;
511      break;
512    }
513
514    case ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution: {
515      NamedDecl *Parm = cast<NamedDecl>(Active->Entity);
516      std::string Name;
517      if (!Parm->getName().empty())
518        Name = std::string(" '") + Parm->getName().str() + "'";
519
520      TemplateParameterList *TemplateParams = nullptr;
521      if (TemplateDecl *Template = dyn_cast<TemplateDecl>(Active->Template))
522        TemplateParams = Template->getTemplateParameters();
523      else
524        TemplateParams =
525          cast<ClassTemplatePartialSpecializationDecl>(Active->Template)
526                                                      ->getTemplateParameters();
527      Diags.Report(Active->PointOfInstantiation,
528                   diag::note_prior_template_arg_substitution)
529        << isa<TemplateTemplateParmDecl>(Parm)
530        << Name
531        << getTemplateArgumentBindingsText(TemplateParams,
532                                           Active->TemplateArgs,
533                                           Active->NumTemplateArgs)
534        << Active->InstantiationRange;
535      break;
536    }
537
538    case ActiveTemplateInstantiation::DefaultTemplateArgumentChecking: {
539      TemplateParameterList *TemplateParams = nullptr;
540      if (TemplateDecl *Template = dyn_cast<TemplateDecl>(Active->Template))
541        TemplateParams = Template->getTemplateParameters();
542      else
543        TemplateParams =
544          cast<ClassTemplatePartialSpecializationDecl>(Active->Template)
545                                                      ->getTemplateParameters();
546
547      Diags.Report(Active->PointOfInstantiation,
548                   diag::note_template_default_arg_checking)
549        << getTemplateArgumentBindingsText(TemplateParams,
550                                           Active->TemplateArgs,
551                                           Active->NumTemplateArgs)
552        << Active->InstantiationRange;
553      break;
554    }
555
556    case ActiveTemplateInstantiation::ExceptionSpecInstantiation:
557      Diags.Report(Active->PointOfInstantiation,
558                   diag::note_template_exception_spec_instantiation_here)
559        << cast<FunctionDecl>(Active->Entity)
560        << Active->InstantiationRange;
561      break;
562    }
563  }
564}
565
566Optional<TemplateDeductionInfo *> Sema::isSFINAEContext() const {
567  if (InNonInstantiationSFINAEContext)
568    return Optional<TemplateDeductionInfo *>(nullptr);
569
570  for (SmallVectorImpl<ActiveTemplateInstantiation>::const_reverse_iterator
571         Active = ActiveTemplateInstantiations.rbegin(),
572         ActiveEnd = ActiveTemplateInstantiations.rend();
573       Active != ActiveEnd;
574       ++Active)
575  {
576    switch(Active->Kind) {
577    case ActiveTemplateInstantiation::TemplateInstantiation:
578      // An instantiation of an alias template may or may not be a SFINAE
579      // context, depending on what else is on the stack.
580      if (isa<TypeAliasTemplateDecl>(Active->Entity))
581        break;
582      // Fall through.
583    case ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation:
584    case ActiveTemplateInstantiation::ExceptionSpecInstantiation:
585      // This is a template instantiation, so there is no SFINAE.
586      return None;
587
588    case ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation:
589    case ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution:
590    case ActiveTemplateInstantiation::DefaultTemplateArgumentChecking:
591      // A default template argument instantiation and substitution into
592      // template parameters with arguments for prior parameters may or may
593      // not be a SFINAE context; look further up the stack.
594      break;
595
596    case ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution:
597    case ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution:
598      // We're either substitution explicitly-specified template arguments
599      // or deduced template arguments, so SFINAE applies.
600      assert(Active->DeductionInfo && "Missing deduction info pointer");
601      return Active->DeductionInfo;
602    }
603  }
604
605  return None;
606}
607
608/// \brief Retrieve the depth and index of a parameter pack.
609static std::pair<unsigned, unsigned>
610getDepthAndIndex(NamedDecl *ND) {
611  if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(ND))
612    return std::make_pair(TTP->getDepth(), TTP->getIndex());
613
614  if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(ND))
615    return std::make_pair(NTTP->getDepth(), NTTP->getIndex());
616
617  TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(ND);
618  return std::make_pair(TTP->getDepth(), TTP->getIndex());
619}
620
621//===----------------------------------------------------------------------===/
622// Template Instantiation for Types
623//===----------------------------------------------------------------------===/
624namespace {
625  class TemplateInstantiator : public TreeTransform<TemplateInstantiator> {
626    const MultiLevelTemplateArgumentList &TemplateArgs;
627    SourceLocation Loc;
628    DeclarationName Entity;
629
630  public:
631    typedef TreeTransform<TemplateInstantiator> inherited;
632
633    TemplateInstantiator(Sema &SemaRef,
634                         const MultiLevelTemplateArgumentList &TemplateArgs,
635                         SourceLocation Loc,
636                         DeclarationName Entity)
637      : inherited(SemaRef), TemplateArgs(TemplateArgs), Loc(Loc),
638        Entity(Entity) { }
639
640    /// \brief Determine whether the given type \p T has already been
641    /// transformed.
642    ///
643    /// For the purposes of template instantiation, a type has already been
644    /// transformed if it is NULL or if it is not dependent.
645    bool AlreadyTransformed(QualType T);
646
647    /// \brief Returns the location of the entity being instantiated, if known.
648    SourceLocation getBaseLocation() { return Loc; }
649
650    /// \brief Returns the name of the entity being instantiated, if any.
651    DeclarationName getBaseEntity() { return Entity; }
652
653    /// \brief Sets the "base" location and entity when that
654    /// information is known based on another transformation.
655    void setBase(SourceLocation Loc, DeclarationName Entity) {
656      this->Loc = Loc;
657      this->Entity = Entity;
658    }
659
660    bool TryExpandParameterPacks(SourceLocation EllipsisLoc,
661                                 SourceRange PatternRange,
662                                 ArrayRef<UnexpandedParameterPack> Unexpanded,
663                                 bool &ShouldExpand, bool &RetainExpansion,
664                                 Optional<unsigned> &NumExpansions) {
665      return getSema().CheckParameterPacksForExpansion(EllipsisLoc,
666                                                       PatternRange, Unexpanded,
667                                                       TemplateArgs,
668                                                       ShouldExpand,
669                                                       RetainExpansion,
670                                                       NumExpansions);
671    }
672
673    void ExpandingFunctionParameterPack(ParmVarDecl *Pack) {
674      SemaRef.CurrentInstantiationScope->MakeInstantiatedLocalArgPack(Pack);
675    }
676
677    TemplateArgument ForgetPartiallySubstitutedPack() {
678      TemplateArgument Result;
679      if (NamedDecl *PartialPack
680            = SemaRef.CurrentInstantiationScope->getPartiallySubstitutedPack()){
681        MultiLevelTemplateArgumentList &TemplateArgs
682          = const_cast<MultiLevelTemplateArgumentList &>(this->TemplateArgs);
683        unsigned Depth, Index;
684        std::tie(Depth, Index) = getDepthAndIndex(PartialPack);
685        if (TemplateArgs.hasTemplateArgument(Depth, Index)) {
686          Result = TemplateArgs(Depth, Index);
687          TemplateArgs.setArgument(Depth, Index, TemplateArgument());
688        }
689      }
690
691      return Result;
692    }
693
694    void RememberPartiallySubstitutedPack(TemplateArgument Arg) {
695      if (Arg.isNull())
696        return;
697
698      if (NamedDecl *PartialPack
699            = SemaRef.CurrentInstantiationScope->getPartiallySubstitutedPack()){
700        MultiLevelTemplateArgumentList &TemplateArgs
701        = const_cast<MultiLevelTemplateArgumentList &>(this->TemplateArgs);
702        unsigned Depth, Index;
703        std::tie(Depth, Index) = getDepthAndIndex(PartialPack);
704        TemplateArgs.setArgument(Depth, Index, Arg);
705      }
706    }
707
708    /// \brief Transform the given declaration by instantiating a reference to
709    /// this declaration.
710    Decl *TransformDecl(SourceLocation Loc, Decl *D);
711
712    void transformAttrs(Decl *Old, Decl *New) {
713      SemaRef.InstantiateAttrs(TemplateArgs, Old, New);
714    }
715
716    void transformedLocalDecl(Decl *Old, Decl *New) {
717      SemaRef.CurrentInstantiationScope->InstantiatedLocal(Old, New);
718    }
719
720    /// \brief Transform the definition of the given declaration by
721    /// instantiating it.
722    Decl *TransformDefinition(SourceLocation Loc, Decl *D);
723
724    /// \brief Transform the first qualifier within a scope by instantiating the
725    /// declaration.
726    NamedDecl *TransformFirstQualifierInScope(NamedDecl *D, SourceLocation Loc);
727
728    /// \brief Rebuild the exception declaration and register the declaration
729    /// as an instantiated local.
730    VarDecl *RebuildExceptionDecl(VarDecl *ExceptionDecl,
731                                  TypeSourceInfo *Declarator,
732                                  SourceLocation StartLoc,
733                                  SourceLocation NameLoc,
734                                  IdentifierInfo *Name);
735
736    /// \brief Rebuild the Objective-C exception declaration and register the
737    /// declaration as an instantiated local.
738    VarDecl *RebuildObjCExceptionDecl(VarDecl *ExceptionDecl,
739                                      TypeSourceInfo *TSInfo, QualType T);
740
741    /// \brief Check for tag mismatches when instantiating an
742    /// elaborated type.
743    QualType RebuildElaboratedType(SourceLocation KeywordLoc,
744                                   ElaboratedTypeKeyword Keyword,
745                                   NestedNameSpecifierLoc QualifierLoc,
746                                   QualType T);
747
748    TemplateName
749    TransformTemplateName(CXXScopeSpec &SS, TemplateName Name,
750                          SourceLocation NameLoc,
751                          QualType ObjectType = QualType(),
752                          NamedDecl *FirstQualifierInScope = nullptr);
753
754    const LoopHintAttr *TransformLoopHintAttr(const LoopHintAttr *LH);
755
756    ExprResult TransformPredefinedExpr(PredefinedExpr *E);
757    ExprResult TransformDeclRefExpr(DeclRefExpr *E);
758    ExprResult TransformCXXDefaultArgExpr(CXXDefaultArgExpr *E);
759
760    ExprResult TransformTemplateParmRefExpr(DeclRefExpr *E,
761                                            NonTypeTemplateParmDecl *D);
762    ExprResult TransformSubstNonTypeTemplateParmPackExpr(
763                                           SubstNonTypeTemplateParmPackExpr *E);
764
765    /// \brief Rebuild a DeclRefExpr for a ParmVarDecl reference.
766    ExprResult RebuildParmVarDeclRefExpr(ParmVarDecl *PD, SourceLocation Loc);
767
768    /// \brief Transform a reference to a function parameter pack.
769    ExprResult TransformFunctionParmPackRefExpr(DeclRefExpr *E,
770                                                ParmVarDecl *PD);
771
772    /// \brief Transform a FunctionParmPackExpr which was built when we couldn't
773    /// expand a function parameter pack reference which refers to an expanded
774    /// pack.
775    ExprResult TransformFunctionParmPackExpr(FunctionParmPackExpr *E);
776
777    QualType TransformFunctionProtoType(TypeLocBuilder &TLB,
778                                        FunctionProtoTypeLoc TL) {
779      // Call the base version; it will forward to our overridden version below.
780      return inherited::TransformFunctionProtoType(TLB, TL);
781    }
782
783    template<typename Fn>
784    QualType TransformFunctionProtoType(TypeLocBuilder &TLB,
785                                        FunctionProtoTypeLoc TL,
786                                        CXXRecordDecl *ThisContext,
787                                        unsigned ThisTypeQuals,
788                                        Fn TransformExceptionSpec);
789
790    ParmVarDecl *TransformFunctionTypeParam(ParmVarDecl *OldParm,
791                                            int indexAdjustment,
792                                            Optional<unsigned> NumExpansions,
793                                            bool ExpectParameterPack);
794
795    /// \brief Transforms a template type parameter type by performing
796    /// substitution of the corresponding template type argument.
797    QualType TransformTemplateTypeParmType(TypeLocBuilder &TLB,
798                                           TemplateTypeParmTypeLoc TL);
799
800    /// \brief Transforms an already-substituted template type parameter pack
801    /// into either itself (if we aren't substituting into its pack expansion)
802    /// or the appropriate substituted argument.
803    QualType TransformSubstTemplateTypeParmPackType(TypeLocBuilder &TLB,
804                                           SubstTemplateTypeParmPackTypeLoc TL);
805
806    ExprResult TransformCallExpr(CallExpr *CE) {
807      getSema().CallsUndergoingInstantiation.push_back(CE);
808      ExprResult Result =
809          TreeTransform<TemplateInstantiator>::TransformCallExpr(CE);
810      getSema().CallsUndergoingInstantiation.pop_back();
811      return Result;
812    }
813
814    ExprResult TransformLambdaExpr(LambdaExpr *E) {
815      LocalInstantiationScope Scope(SemaRef, /*CombineWithOuterScope=*/true);
816      return TreeTransform<TemplateInstantiator>::TransformLambdaExpr(E);
817    }
818
819    ExprResult TransformLambdaScope(LambdaExpr *E,
820        CXXMethodDecl *NewCallOperator,
821        ArrayRef<InitCaptureInfoTy> InitCaptureExprsAndTypes) {
822      CXXMethodDecl *const OldCallOperator = E->getCallOperator();
823      // In the generic lambda case, we set the NewTemplate to be considered
824      // an "instantiation" of the OldTemplate.
825      if (FunctionTemplateDecl *const NewCallOperatorTemplate =
826            NewCallOperator->getDescribedFunctionTemplate()) {
827
828        FunctionTemplateDecl *const OldCallOperatorTemplate =
829                              OldCallOperator->getDescribedFunctionTemplate();
830        NewCallOperatorTemplate->setInstantiatedFromMemberTemplate(
831                                                     OldCallOperatorTemplate);
832      } else
833        // For a non-generic lambda we set the NewCallOperator to
834        // be an instantiation of the OldCallOperator.
835        NewCallOperator->setInstantiationOfMemberFunction(OldCallOperator,
836                                                    TSK_ImplicitInstantiation);
837
838      return inherited::TransformLambdaScope(E, NewCallOperator,
839          InitCaptureExprsAndTypes);
840    }
841    TemplateParameterList *TransformTemplateParameterList(
842                              TemplateParameterList *OrigTPL)  {
843      if (!OrigTPL || !OrigTPL->size()) return OrigTPL;
844
845      DeclContext *Owner = OrigTPL->getParam(0)->getDeclContext();
846      TemplateDeclInstantiator  DeclInstantiator(getSema(),
847                        /* DeclContext *Owner */ Owner, TemplateArgs);
848      return DeclInstantiator.SubstTemplateParams(OrigTPL);
849    }
850  private:
851    ExprResult transformNonTypeTemplateParmRef(NonTypeTemplateParmDecl *parm,
852                                               SourceLocation loc,
853                                               TemplateArgument arg);
854  };
855}
856
857bool TemplateInstantiator::AlreadyTransformed(QualType T) {
858  if (T.isNull())
859    return true;
860
861  if (T->isInstantiationDependentType() || T->isVariablyModifiedType())
862    return false;
863
864  getSema().MarkDeclarationsReferencedInType(Loc, T);
865  return true;
866}
867
868static TemplateArgument
869getPackSubstitutedTemplateArgument(Sema &S, TemplateArgument Arg) {
870  assert(S.ArgumentPackSubstitutionIndex >= 0);
871  assert(S.ArgumentPackSubstitutionIndex < (int)Arg.pack_size());
872  Arg = Arg.pack_begin()[S.ArgumentPackSubstitutionIndex];
873  if (Arg.isPackExpansion())
874    Arg = Arg.getPackExpansionPattern();
875  return Arg;
876}
877
878Decl *TemplateInstantiator::TransformDecl(SourceLocation Loc, Decl *D) {
879  if (!D)
880    return nullptr;
881
882  if (TemplateTemplateParmDecl *TTP = dyn_cast<TemplateTemplateParmDecl>(D)) {
883    if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
884      // If the corresponding template argument is NULL or non-existent, it's
885      // because we are performing instantiation from explicitly-specified
886      // template arguments in a function template, but there were some
887      // arguments left unspecified.
888      if (!TemplateArgs.hasTemplateArgument(TTP->getDepth(),
889                                            TTP->getPosition()))
890        return D;
891
892      TemplateArgument Arg = TemplateArgs(TTP->getDepth(), TTP->getPosition());
893
894      if (TTP->isParameterPack()) {
895        assert(Arg.getKind() == TemplateArgument::Pack &&
896               "Missing argument pack");
897        Arg = getPackSubstitutedTemplateArgument(getSema(), Arg);
898      }
899
900      TemplateName Template = Arg.getAsTemplate();
901      assert(!Template.isNull() && Template.getAsTemplateDecl() &&
902             "Wrong kind of template template argument");
903      return Template.getAsTemplateDecl();
904    }
905
906    // Fall through to find the instantiated declaration for this template
907    // template parameter.
908  }
909
910  return SemaRef.FindInstantiatedDecl(Loc, cast<NamedDecl>(D), TemplateArgs);
911}
912
913Decl *TemplateInstantiator::TransformDefinition(SourceLocation Loc, Decl *D) {
914  Decl *Inst = getSema().SubstDecl(D, getSema().CurContext, TemplateArgs);
915  if (!Inst)
916    return nullptr;
917
918  getSema().CurrentInstantiationScope->InstantiatedLocal(D, Inst);
919  return Inst;
920}
921
922NamedDecl *
923TemplateInstantiator::TransformFirstQualifierInScope(NamedDecl *D,
924                                                     SourceLocation Loc) {
925  // If the first part of the nested-name-specifier was a template type
926  // parameter, instantiate that type parameter down to a tag type.
927  if (TemplateTypeParmDecl *TTPD = dyn_cast_or_null<TemplateTypeParmDecl>(D)) {
928    const TemplateTypeParmType *TTP
929      = cast<TemplateTypeParmType>(getSema().Context.getTypeDeclType(TTPD));
930
931    if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
932      // FIXME: This needs testing w/ member access expressions.
933      TemplateArgument Arg = TemplateArgs(TTP->getDepth(), TTP->getIndex());
934
935      if (TTP->isParameterPack()) {
936        assert(Arg.getKind() == TemplateArgument::Pack &&
937               "Missing argument pack");
938
939        if (getSema().ArgumentPackSubstitutionIndex == -1)
940          return nullptr;
941
942        Arg = getPackSubstitutedTemplateArgument(getSema(), Arg);
943      }
944
945      QualType T = Arg.getAsType();
946      if (T.isNull())
947        return cast_or_null<NamedDecl>(TransformDecl(Loc, D));
948
949      if (const TagType *Tag = T->getAs<TagType>())
950        return Tag->getDecl();
951
952      // The resulting type is not a tag; complain.
953      getSema().Diag(Loc, diag::err_nested_name_spec_non_tag) << T;
954      return nullptr;
955    }
956  }
957
958  return cast_or_null<NamedDecl>(TransformDecl(Loc, D));
959}
960
961VarDecl *
962TemplateInstantiator::RebuildExceptionDecl(VarDecl *ExceptionDecl,
963                                           TypeSourceInfo *Declarator,
964                                           SourceLocation StartLoc,
965                                           SourceLocation NameLoc,
966                                           IdentifierInfo *Name) {
967  VarDecl *Var = inherited::RebuildExceptionDecl(ExceptionDecl, Declarator,
968                                                 StartLoc, NameLoc, Name);
969  if (Var)
970    getSema().CurrentInstantiationScope->InstantiatedLocal(ExceptionDecl, Var);
971  return Var;
972}
973
974VarDecl *TemplateInstantiator::RebuildObjCExceptionDecl(VarDecl *ExceptionDecl,
975                                                        TypeSourceInfo *TSInfo,
976                                                        QualType T) {
977  VarDecl *Var = inherited::RebuildObjCExceptionDecl(ExceptionDecl, TSInfo, T);
978  if (Var)
979    getSema().CurrentInstantiationScope->InstantiatedLocal(ExceptionDecl, Var);
980  return Var;
981}
982
983QualType
984TemplateInstantiator::RebuildElaboratedType(SourceLocation KeywordLoc,
985                                            ElaboratedTypeKeyword Keyword,
986                                            NestedNameSpecifierLoc QualifierLoc,
987                                            QualType T) {
988  if (const TagType *TT = T->getAs<TagType>()) {
989    TagDecl* TD = TT->getDecl();
990
991    SourceLocation TagLocation = KeywordLoc;
992
993    IdentifierInfo *Id = TD->getIdentifier();
994
995    // TODO: should we even warn on struct/class mismatches for this?  Seems
996    // like it's likely to produce a lot of spurious errors.
997    if (Id && Keyword != ETK_None && Keyword != ETK_Typename) {
998      TagTypeKind Kind = TypeWithKeyword::getTagTypeKindForKeyword(Keyword);
999      if (!SemaRef.isAcceptableTagRedeclaration(TD, Kind, /*isDefinition*/false,
1000                                                TagLocation, *Id)) {
1001        SemaRef.Diag(TagLocation, diag::err_use_with_wrong_tag)
1002          << Id
1003          << FixItHint::CreateReplacement(SourceRange(TagLocation),
1004                                          TD->getKindName());
1005        SemaRef.Diag(TD->getLocation(), diag::note_previous_use);
1006      }
1007    }
1008  }
1009
1010  return TreeTransform<TemplateInstantiator>::RebuildElaboratedType(KeywordLoc,
1011                                                                    Keyword,
1012                                                                  QualifierLoc,
1013                                                                    T);
1014}
1015
1016TemplateName TemplateInstantiator::TransformTemplateName(CXXScopeSpec &SS,
1017                                                         TemplateName Name,
1018                                                         SourceLocation NameLoc,
1019                                                         QualType ObjectType,
1020                                             NamedDecl *FirstQualifierInScope) {
1021  if (TemplateTemplateParmDecl *TTP
1022       = dyn_cast_or_null<TemplateTemplateParmDecl>(Name.getAsTemplateDecl())) {
1023    if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
1024      // If the corresponding template argument is NULL or non-existent, it's
1025      // because we are performing instantiation from explicitly-specified
1026      // template arguments in a function template, but there were some
1027      // arguments left unspecified.
1028      if (!TemplateArgs.hasTemplateArgument(TTP->getDepth(),
1029                                            TTP->getPosition()))
1030        return Name;
1031
1032      TemplateArgument Arg = TemplateArgs(TTP->getDepth(), TTP->getPosition());
1033
1034      if (TTP->isParameterPack()) {
1035        assert(Arg.getKind() == TemplateArgument::Pack &&
1036               "Missing argument pack");
1037
1038        if (getSema().ArgumentPackSubstitutionIndex == -1) {
1039          // We have the template argument pack to substitute, but we're not
1040          // actually expanding the enclosing pack expansion yet. So, just
1041          // keep the entire argument pack.
1042          return getSema().Context.getSubstTemplateTemplateParmPack(TTP, Arg);
1043        }
1044
1045        Arg = getPackSubstitutedTemplateArgument(getSema(), Arg);
1046      }
1047
1048      TemplateName Template = Arg.getAsTemplate();
1049      assert(!Template.isNull() && "Null template template argument");
1050
1051      // We don't ever want to substitute for a qualified template name, since
1052      // the qualifier is handled separately. So, look through the qualified
1053      // template name to its underlying declaration.
1054      if (QualifiedTemplateName *QTN = Template.getAsQualifiedTemplateName())
1055        Template = TemplateName(QTN->getTemplateDecl());
1056
1057      Template = getSema().Context.getSubstTemplateTemplateParm(TTP, Template);
1058      return Template;
1059    }
1060  }
1061
1062  if (SubstTemplateTemplateParmPackStorage *SubstPack
1063      = Name.getAsSubstTemplateTemplateParmPack()) {
1064    if (getSema().ArgumentPackSubstitutionIndex == -1)
1065      return Name;
1066
1067    TemplateArgument Arg = SubstPack->getArgumentPack();
1068    Arg = getPackSubstitutedTemplateArgument(getSema(), Arg);
1069    return Arg.getAsTemplate();
1070  }
1071
1072  return inherited::TransformTemplateName(SS, Name, NameLoc, ObjectType,
1073                                          FirstQualifierInScope);
1074}
1075
1076ExprResult
1077TemplateInstantiator::TransformPredefinedExpr(PredefinedExpr *E) {
1078  if (!E->isTypeDependent())
1079    return E;
1080
1081  return getSema().BuildPredefinedExpr(E->getLocation(), E->getIdentType());
1082}
1083
1084ExprResult
1085TemplateInstantiator::TransformTemplateParmRefExpr(DeclRefExpr *E,
1086                                               NonTypeTemplateParmDecl *NTTP) {
1087  // If the corresponding template argument is NULL or non-existent, it's
1088  // because we are performing instantiation from explicitly-specified
1089  // template arguments in a function template, but there were some
1090  // arguments left unspecified.
1091  if (!TemplateArgs.hasTemplateArgument(NTTP->getDepth(),
1092                                        NTTP->getPosition()))
1093    return E;
1094
1095  TemplateArgument Arg = TemplateArgs(NTTP->getDepth(), NTTP->getPosition());
1096  if (NTTP->isParameterPack()) {
1097    assert(Arg.getKind() == TemplateArgument::Pack &&
1098           "Missing argument pack");
1099
1100    if (getSema().ArgumentPackSubstitutionIndex == -1) {
1101      // We have an argument pack, but we can't select a particular argument
1102      // out of it yet. Therefore, we'll build an expression to hold on to that
1103      // argument pack.
1104      QualType TargetType = SemaRef.SubstType(NTTP->getType(), TemplateArgs,
1105                                              E->getLocation(),
1106                                              NTTP->getDeclName());
1107      if (TargetType.isNull())
1108        return ExprError();
1109
1110      return new (SemaRef.Context) SubstNonTypeTemplateParmPackExpr(TargetType,
1111                                                                    NTTP,
1112                                                              E->getLocation(),
1113                                                                    Arg);
1114    }
1115
1116    Arg = getPackSubstitutedTemplateArgument(getSema(), Arg);
1117  }
1118
1119  return transformNonTypeTemplateParmRef(NTTP, E->getLocation(), Arg);
1120}
1121
1122const LoopHintAttr *
1123TemplateInstantiator::TransformLoopHintAttr(const LoopHintAttr *LH) {
1124  Expr *TransformedExpr = getDerived().TransformExpr(LH->getValue()).get();
1125
1126  if (TransformedExpr == LH->getValue())
1127    return LH;
1128
1129  // Generate error if there is a problem with the value.
1130  if (getSema().CheckLoopHintExpr(TransformedExpr, LH->getLocation()))
1131    return LH;
1132
1133  // Create new LoopHintValueAttr with integral expression in place of the
1134  // non-type template parameter.
1135  return LoopHintAttr::CreateImplicit(
1136      getSema().Context, LH->getSemanticSpelling(), LH->getOption(),
1137      LH->getState(), TransformedExpr, LH->getRange());
1138}
1139
1140ExprResult TemplateInstantiator::transformNonTypeTemplateParmRef(
1141                                                 NonTypeTemplateParmDecl *parm,
1142                                                 SourceLocation loc,
1143                                                 TemplateArgument arg) {
1144  ExprResult result;
1145  QualType type;
1146
1147  // The template argument itself might be an expression, in which
1148  // case we just return that expression.
1149  if (arg.getKind() == TemplateArgument::Expression) {
1150    Expr *argExpr = arg.getAsExpr();
1151    result = argExpr;
1152    type = argExpr->getType();
1153
1154  } else if (arg.getKind() == TemplateArgument::Declaration ||
1155             arg.getKind() == TemplateArgument::NullPtr) {
1156    ValueDecl *VD;
1157    if (arg.getKind() == TemplateArgument::Declaration) {
1158      VD = cast<ValueDecl>(arg.getAsDecl());
1159
1160      // Find the instantiation of the template argument.  This is
1161      // required for nested templates.
1162      VD = cast_or_null<ValueDecl>(
1163             getSema().FindInstantiatedDecl(loc, VD, TemplateArgs));
1164      if (!VD)
1165        return ExprError();
1166    } else {
1167      // Propagate NULL template argument.
1168      VD = nullptr;
1169    }
1170
1171    // Derive the type we want the substituted decl to have.  This had
1172    // better be non-dependent, or these checks will have serious problems.
1173    if (parm->isExpandedParameterPack()) {
1174      type = parm->getExpansionType(SemaRef.ArgumentPackSubstitutionIndex);
1175    } else if (parm->isParameterPack() &&
1176               isa<PackExpansionType>(parm->getType())) {
1177      type = SemaRef.SubstType(
1178                        cast<PackExpansionType>(parm->getType())->getPattern(),
1179                                     TemplateArgs, loc, parm->getDeclName());
1180    } else {
1181      type = SemaRef.SubstType(parm->getType(), TemplateArgs,
1182                               loc, parm->getDeclName());
1183    }
1184    assert(!type.isNull() && "type substitution failed for param type");
1185    assert(!type->isDependentType() && "param type still dependent");
1186    result = SemaRef.BuildExpressionFromDeclTemplateArgument(arg, type, loc);
1187
1188    if (!result.isInvalid()) type = result.get()->getType();
1189  } else {
1190    result = SemaRef.BuildExpressionFromIntegralTemplateArgument(arg, loc);
1191
1192    // Note that this type can be different from the type of 'result',
1193    // e.g. if it's an enum type.
1194    type = arg.getIntegralType();
1195  }
1196  if (result.isInvalid()) return ExprError();
1197
1198  Expr *resultExpr = result.get();
1199  return new (SemaRef.Context) SubstNonTypeTemplateParmExpr(
1200      type, resultExpr->getValueKind(), loc, parm, resultExpr);
1201}
1202
1203ExprResult
1204TemplateInstantiator::TransformSubstNonTypeTemplateParmPackExpr(
1205                                          SubstNonTypeTemplateParmPackExpr *E) {
1206  if (getSema().ArgumentPackSubstitutionIndex == -1) {
1207    // We aren't expanding the parameter pack, so just return ourselves.
1208    return E;
1209  }
1210
1211  TemplateArgument Arg = E->getArgumentPack();
1212  Arg = getPackSubstitutedTemplateArgument(getSema(), Arg);
1213  return transformNonTypeTemplateParmRef(E->getParameterPack(),
1214                                         E->getParameterPackLocation(),
1215                                         Arg);
1216}
1217
1218ExprResult
1219TemplateInstantiator::RebuildParmVarDeclRefExpr(ParmVarDecl *PD,
1220                                                SourceLocation Loc) {
1221  DeclarationNameInfo NameInfo(PD->getDeclName(), Loc);
1222  return getSema().BuildDeclarationNameExpr(CXXScopeSpec(), NameInfo, PD);
1223}
1224
1225ExprResult
1226TemplateInstantiator::TransformFunctionParmPackExpr(FunctionParmPackExpr *E) {
1227  if (getSema().ArgumentPackSubstitutionIndex != -1) {
1228    // We can expand this parameter pack now.
1229    ParmVarDecl *D = E->getExpansion(getSema().ArgumentPackSubstitutionIndex);
1230    ValueDecl *VD = cast_or_null<ValueDecl>(TransformDecl(E->getExprLoc(), D));
1231    if (!VD)
1232      return ExprError();
1233    return RebuildParmVarDeclRefExpr(cast<ParmVarDecl>(VD), E->getExprLoc());
1234  }
1235
1236  QualType T = TransformType(E->getType());
1237  if (T.isNull())
1238    return ExprError();
1239
1240  // Transform each of the parameter expansions into the corresponding
1241  // parameters in the instantiation of the function decl.
1242  SmallVector<Decl *, 8> Parms;
1243  Parms.reserve(E->getNumExpansions());
1244  for (FunctionParmPackExpr::iterator I = E->begin(), End = E->end();
1245       I != End; ++I) {
1246    ParmVarDecl *D =
1247        cast_or_null<ParmVarDecl>(TransformDecl(E->getExprLoc(), *I));
1248    if (!D)
1249      return ExprError();
1250    Parms.push_back(D);
1251  }
1252
1253  return FunctionParmPackExpr::Create(getSema().Context, T,
1254                                      E->getParameterPack(),
1255                                      E->getParameterPackLocation(), Parms);
1256}
1257
1258ExprResult
1259TemplateInstantiator::TransformFunctionParmPackRefExpr(DeclRefExpr *E,
1260                                                       ParmVarDecl *PD) {
1261  typedef LocalInstantiationScope::DeclArgumentPack DeclArgumentPack;
1262  llvm::PointerUnion<Decl *, DeclArgumentPack *> *Found
1263    = getSema().CurrentInstantiationScope->findInstantiationOf(PD);
1264  assert(Found && "no instantiation for parameter pack");
1265
1266  Decl *TransformedDecl;
1267  if (DeclArgumentPack *Pack = Found->dyn_cast<DeclArgumentPack *>()) {
1268    // If this is a reference to a function parameter pack which we can
1269    // substitute but can't yet expand, build a FunctionParmPackExpr for it.
1270    if (getSema().ArgumentPackSubstitutionIndex == -1) {
1271      QualType T = TransformType(E->getType());
1272      if (T.isNull())
1273        return ExprError();
1274      return FunctionParmPackExpr::Create(getSema().Context, T, PD,
1275                                          E->getExprLoc(), *Pack);
1276    }
1277
1278    TransformedDecl = (*Pack)[getSema().ArgumentPackSubstitutionIndex];
1279  } else {
1280    TransformedDecl = Found->get<Decl*>();
1281  }
1282
1283  // We have either an unexpanded pack or a specific expansion.
1284  return RebuildParmVarDeclRefExpr(cast<ParmVarDecl>(TransformedDecl),
1285                                   E->getExprLoc());
1286}
1287
1288ExprResult
1289TemplateInstantiator::TransformDeclRefExpr(DeclRefExpr *E) {
1290  NamedDecl *D = E->getDecl();
1291
1292  // Handle references to non-type template parameters and non-type template
1293  // parameter packs.
1294  if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D)) {
1295    if (NTTP->getDepth() < TemplateArgs.getNumLevels())
1296      return TransformTemplateParmRefExpr(E, NTTP);
1297
1298    // We have a non-type template parameter that isn't fully substituted;
1299    // FindInstantiatedDecl will find it in the local instantiation scope.
1300  }
1301
1302  // Handle references to function parameter packs.
1303  if (ParmVarDecl *PD = dyn_cast<ParmVarDecl>(D))
1304    if (PD->isParameterPack())
1305      return TransformFunctionParmPackRefExpr(E, PD);
1306
1307  return TreeTransform<TemplateInstantiator>::TransformDeclRefExpr(E);
1308}
1309
1310ExprResult TemplateInstantiator::TransformCXXDefaultArgExpr(
1311    CXXDefaultArgExpr *E) {
1312  assert(!cast<FunctionDecl>(E->getParam()->getDeclContext())->
1313             getDescribedFunctionTemplate() &&
1314         "Default arg expressions are never formed in dependent cases.");
1315  return SemaRef.BuildCXXDefaultArgExpr(E->getUsedLocation(),
1316                           cast<FunctionDecl>(E->getParam()->getDeclContext()),
1317                                        E->getParam());
1318}
1319
1320template<typename Fn>
1321QualType TemplateInstantiator::TransformFunctionProtoType(TypeLocBuilder &TLB,
1322                                 FunctionProtoTypeLoc TL,
1323                                 CXXRecordDecl *ThisContext,
1324                                 unsigned ThisTypeQuals,
1325                                 Fn TransformExceptionSpec) {
1326  // We need a local instantiation scope for this function prototype.
1327  LocalInstantiationScope Scope(SemaRef, /*CombineWithOuterScope=*/true);
1328  return inherited::TransformFunctionProtoType(
1329      TLB, TL, ThisContext, ThisTypeQuals, TransformExceptionSpec);
1330}
1331
1332ParmVarDecl *
1333TemplateInstantiator::TransformFunctionTypeParam(ParmVarDecl *OldParm,
1334                                                 int indexAdjustment,
1335                                               Optional<unsigned> NumExpansions,
1336                                                 bool ExpectParameterPack) {
1337  return SemaRef.SubstParmVarDecl(OldParm, TemplateArgs, indexAdjustment,
1338                                  NumExpansions, ExpectParameterPack);
1339}
1340
1341QualType
1342TemplateInstantiator::TransformTemplateTypeParmType(TypeLocBuilder &TLB,
1343                                                TemplateTypeParmTypeLoc TL) {
1344  const TemplateTypeParmType *T = TL.getTypePtr();
1345  if (T->getDepth() < TemplateArgs.getNumLevels()) {
1346    // Replace the template type parameter with its corresponding
1347    // template argument.
1348
1349    // If the corresponding template argument is NULL or doesn't exist, it's
1350    // because we are performing instantiation from explicitly-specified
1351    // template arguments in a function template class, but there were some
1352    // arguments left unspecified.
1353    if (!TemplateArgs.hasTemplateArgument(T->getDepth(), T->getIndex())) {
1354      TemplateTypeParmTypeLoc NewTL
1355        = TLB.push<TemplateTypeParmTypeLoc>(TL.getType());
1356      NewTL.setNameLoc(TL.getNameLoc());
1357      return TL.getType();
1358    }
1359
1360    TemplateArgument Arg = TemplateArgs(T->getDepth(), T->getIndex());
1361
1362    if (T->isParameterPack()) {
1363      assert(Arg.getKind() == TemplateArgument::Pack &&
1364             "Missing argument pack");
1365
1366      if (getSema().ArgumentPackSubstitutionIndex == -1) {
1367        // We have the template argument pack, but we're not expanding the
1368        // enclosing pack expansion yet. Just save the template argument
1369        // pack for later substitution.
1370        QualType Result
1371          = getSema().Context.getSubstTemplateTypeParmPackType(T, Arg);
1372        SubstTemplateTypeParmPackTypeLoc NewTL
1373          = TLB.push<SubstTemplateTypeParmPackTypeLoc>(Result);
1374        NewTL.setNameLoc(TL.getNameLoc());
1375        return Result;
1376      }
1377
1378      Arg = getPackSubstitutedTemplateArgument(getSema(), Arg);
1379    }
1380
1381    assert(Arg.getKind() == TemplateArgument::Type &&
1382           "Template argument kind mismatch");
1383
1384    QualType Replacement = Arg.getAsType();
1385
1386    // TODO: only do this uniquing once, at the start of instantiation.
1387    QualType Result
1388      = getSema().Context.getSubstTemplateTypeParmType(T, Replacement);
1389    SubstTemplateTypeParmTypeLoc NewTL
1390      = TLB.push<SubstTemplateTypeParmTypeLoc>(Result);
1391    NewTL.setNameLoc(TL.getNameLoc());
1392    return Result;
1393  }
1394
1395  // The template type parameter comes from an inner template (e.g.,
1396  // the template parameter list of a member template inside the
1397  // template we are instantiating). Create a new template type
1398  // parameter with the template "level" reduced by one.
1399  TemplateTypeParmDecl *NewTTPDecl = nullptr;
1400  if (TemplateTypeParmDecl *OldTTPDecl = T->getDecl())
1401    NewTTPDecl = cast_or_null<TemplateTypeParmDecl>(
1402                                  TransformDecl(TL.getNameLoc(), OldTTPDecl));
1403
1404  QualType Result
1405    = getSema().Context.getTemplateTypeParmType(T->getDepth()
1406                                                 - TemplateArgs.getNumLevels(),
1407                                                T->getIndex(),
1408                                                T->isParameterPack(),
1409                                                NewTTPDecl);
1410  TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result);
1411  NewTL.setNameLoc(TL.getNameLoc());
1412  return Result;
1413}
1414
1415QualType
1416TemplateInstantiator::TransformSubstTemplateTypeParmPackType(
1417                                                            TypeLocBuilder &TLB,
1418                                         SubstTemplateTypeParmPackTypeLoc TL) {
1419  if (getSema().ArgumentPackSubstitutionIndex == -1) {
1420    // We aren't expanding the parameter pack, so just return ourselves.
1421    SubstTemplateTypeParmPackTypeLoc NewTL
1422      = TLB.push<SubstTemplateTypeParmPackTypeLoc>(TL.getType());
1423    NewTL.setNameLoc(TL.getNameLoc());
1424    return TL.getType();
1425  }
1426
1427  TemplateArgument Arg = TL.getTypePtr()->getArgumentPack();
1428  Arg = getPackSubstitutedTemplateArgument(getSema(), Arg);
1429  QualType Result = Arg.getAsType();
1430
1431  Result = getSema().Context.getSubstTemplateTypeParmType(
1432                                      TL.getTypePtr()->getReplacedParameter(),
1433                                                          Result);
1434  SubstTemplateTypeParmTypeLoc NewTL
1435    = TLB.push<SubstTemplateTypeParmTypeLoc>(Result);
1436  NewTL.setNameLoc(TL.getNameLoc());
1437  return Result;
1438}
1439
1440/// \brief Perform substitution on the type T with a given set of template
1441/// arguments.
1442///
1443/// This routine substitutes the given template arguments into the
1444/// type T and produces the instantiated type.
1445///
1446/// \param T the type into which the template arguments will be
1447/// substituted. If this type is not dependent, it will be returned
1448/// immediately.
1449///
1450/// \param Args the template arguments that will be
1451/// substituted for the top-level template parameters within T.
1452///
1453/// \param Loc the location in the source code where this substitution
1454/// is being performed. It will typically be the location of the
1455/// declarator (if we're instantiating the type of some declaration)
1456/// or the location of the type in the source code (if, e.g., we're
1457/// instantiating the type of a cast expression).
1458///
1459/// \param Entity the name of the entity associated with a declaration
1460/// being instantiated (if any). May be empty to indicate that there
1461/// is no such entity (if, e.g., this is a type that occurs as part of
1462/// a cast expression) or that the entity has no name (e.g., an
1463/// unnamed function parameter).
1464///
1465/// \returns If the instantiation succeeds, the instantiated
1466/// type. Otherwise, produces diagnostics and returns a NULL type.
1467TypeSourceInfo *Sema::SubstType(TypeSourceInfo *T,
1468                                const MultiLevelTemplateArgumentList &Args,
1469                                SourceLocation Loc,
1470                                DeclarationName Entity) {
1471  assert(!ActiveTemplateInstantiations.empty() &&
1472         "Cannot perform an instantiation without some context on the "
1473         "instantiation stack");
1474
1475  if (!T->getType()->isInstantiationDependentType() &&
1476      !T->getType()->isVariablyModifiedType())
1477    return T;
1478
1479  TemplateInstantiator Instantiator(*this, Args, Loc, Entity);
1480  return Instantiator.TransformType(T);
1481}
1482
1483TypeSourceInfo *Sema::SubstType(TypeLoc TL,
1484                                const MultiLevelTemplateArgumentList &Args,
1485                                SourceLocation Loc,
1486                                DeclarationName Entity) {
1487  assert(!ActiveTemplateInstantiations.empty() &&
1488         "Cannot perform an instantiation without some context on the "
1489         "instantiation stack");
1490
1491  if (TL.getType().isNull())
1492    return nullptr;
1493
1494  if (!TL.getType()->isInstantiationDependentType() &&
1495      !TL.getType()->isVariablyModifiedType()) {
1496    // FIXME: Make a copy of the TypeLoc data here, so that we can
1497    // return a new TypeSourceInfo. Inefficient!
1498    TypeLocBuilder TLB;
1499    TLB.pushFullCopy(TL);
1500    return TLB.getTypeSourceInfo(Context, TL.getType());
1501  }
1502
1503  TemplateInstantiator Instantiator(*this, Args, Loc, Entity);
1504  TypeLocBuilder TLB;
1505  TLB.reserve(TL.getFullDataSize());
1506  QualType Result = Instantiator.TransformType(TLB, TL);
1507  if (Result.isNull())
1508    return nullptr;
1509
1510  return TLB.getTypeSourceInfo(Context, Result);
1511}
1512
1513/// Deprecated form of the above.
1514QualType Sema::SubstType(QualType T,
1515                         const MultiLevelTemplateArgumentList &TemplateArgs,
1516                         SourceLocation Loc, DeclarationName Entity) {
1517  assert(!ActiveTemplateInstantiations.empty() &&
1518         "Cannot perform an instantiation without some context on the "
1519         "instantiation stack");
1520
1521  // If T is not a dependent type or a variably-modified type, there
1522  // is nothing to do.
1523  if (!T->isInstantiationDependentType() && !T->isVariablyModifiedType())
1524    return T;
1525
1526  TemplateInstantiator Instantiator(*this, TemplateArgs, Loc, Entity);
1527  return Instantiator.TransformType(T);
1528}
1529
1530static bool NeedsInstantiationAsFunctionType(TypeSourceInfo *T) {
1531  if (T->getType()->isInstantiationDependentType() ||
1532      T->getType()->isVariablyModifiedType())
1533    return true;
1534
1535  TypeLoc TL = T->getTypeLoc().IgnoreParens();
1536  if (!TL.getAs<FunctionProtoTypeLoc>())
1537    return false;
1538
1539  FunctionProtoTypeLoc FP = TL.castAs<FunctionProtoTypeLoc>();
1540  for (unsigned I = 0, E = FP.getNumParams(); I != E; ++I) {
1541    ParmVarDecl *P = FP.getParam(I);
1542
1543    // This must be synthesized from a typedef.
1544    if (!P) continue;
1545
1546    // The parameter's type as written might be dependent even if the
1547    // decayed type was not dependent.
1548    if (TypeSourceInfo *TSInfo = P->getTypeSourceInfo())
1549      if (TSInfo->getType()->isInstantiationDependentType())
1550        return true;
1551
1552    // TODO: currently we always rebuild expressions.  When we
1553    // properly get lazier about this, we should use the same
1554    // logic to avoid rebuilding prototypes here.
1555    if (P->hasDefaultArg())
1556      return true;
1557  }
1558
1559  return false;
1560}
1561
1562/// A form of SubstType intended specifically for instantiating the
1563/// type of a FunctionDecl.  Its purpose is solely to force the
1564/// instantiation of default-argument expressions and to avoid
1565/// instantiating an exception-specification.
1566TypeSourceInfo *Sema::SubstFunctionDeclType(TypeSourceInfo *T,
1567                                const MultiLevelTemplateArgumentList &Args,
1568                                SourceLocation Loc,
1569                                DeclarationName Entity,
1570                                CXXRecordDecl *ThisContext,
1571                                unsigned ThisTypeQuals) {
1572  assert(!ActiveTemplateInstantiations.empty() &&
1573         "Cannot perform an instantiation without some context on the "
1574         "instantiation stack");
1575
1576  if (!NeedsInstantiationAsFunctionType(T))
1577    return T;
1578
1579  TemplateInstantiator Instantiator(*this, Args, Loc, Entity);
1580
1581  TypeLocBuilder TLB;
1582
1583  TypeLoc TL = T->getTypeLoc();
1584  TLB.reserve(TL.getFullDataSize());
1585
1586  QualType Result;
1587
1588  if (FunctionProtoTypeLoc Proto =
1589          TL.IgnoreParens().getAs<FunctionProtoTypeLoc>()) {
1590    // Instantiate the type, other than its exception specification. The
1591    // exception specification is instantiated in InitFunctionInstantiation
1592    // once we've built the FunctionDecl.
1593    // FIXME: Set the exception specification to EST_Uninstantiated here,
1594    // instead of rebuilding the function type again later.
1595    Result = Instantiator.TransformFunctionProtoType(
1596        TLB, Proto, ThisContext, ThisTypeQuals,
1597        [](FunctionProtoType::ExceptionSpecInfo &ESI,
1598           bool &Changed) { return false; });
1599  } else {
1600    Result = Instantiator.TransformType(TLB, TL);
1601  }
1602  if (Result.isNull())
1603    return nullptr;
1604
1605  return TLB.getTypeSourceInfo(Context, Result);
1606}
1607
1608void Sema::SubstExceptionSpec(FunctionDecl *New, const FunctionProtoType *Proto,
1609                              const MultiLevelTemplateArgumentList &Args) {
1610  FunctionProtoType::ExceptionSpecInfo ESI =
1611      Proto->getExtProtoInfo().ExceptionSpec;
1612  assert(ESI.Type != EST_Uninstantiated);
1613
1614  TemplateInstantiator Instantiator(*this, Args, New->getLocation(),
1615                                    New->getDeclName());
1616
1617  SmallVector<QualType, 4> ExceptionStorage;
1618  bool Changed = false;
1619  if (Instantiator.TransformExceptionSpec(
1620          New->getTypeSourceInfo()->getTypeLoc().getLocEnd(), ESI,
1621          ExceptionStorage, Changed))
1622    // On error, recover by dropping the exception specification.
1623    ESI.Type = EST_None;
1624
1625  UpdateExceptionSpec(New, ESI);
1626}
1627
1628ParmVarDecl *Sema::SubstParmVarDecl(ParmVarDecl *OldParm,
1629                            const MultiLevelTemplateArgumentList &TemplateArgs,
1630                                    int indexAdjustment,
1631                                    Optional<unsigned> NumExpansions,
1632                                    bool ExpectParameterPack) {
1633  TypeSourceInfo *OldDI = OldParm->getTypeSourceInfo();
1634  TypeSourceInfo *NewDI = nullptr;
1635
1636  TypeLoc OldTL = OldDI->getTypeLoc();
1637  if (PackExpansionTypeLoc ExpansionTL = OldTL.getAs<PackExpansionTypeLoc>()) {
1638
1639    // We have a function parameter pack. Substitute into the pattern of the
1640    // expansion.
1641    NewDI = SubstType(ExpansionTL.getPatternLoc(), TemplateArgs,
1642                      OldParm->getLocation(), OldParm->getDeclName());
1643    if (!NewDI)
1644      return nullptr;
1645
1646    if (NewDI->getType()->containsUnexpandedParameterPack()) {
1647      // We still have unexpanded parameter packs, which means that
1648      // our function parameter is still a function parameter pack.
1649      // Therefore, make its type a pack expansion type.
1650      NewDI = CheckPackExpansion(NewDI, ExpansionTL.getEllipsisLoc(),
1651                                 NumExpansions);
1652    } else if (ExpectParameterPack) {
1653      // We expected to get a parameter pack but didn't (because the type
1654      // itself is not a pack expansion type), so complain. This can occur when
1655      // the substitution goes through an alias template that "loses" the
1656      // pack expansion.
1657      Diag(OldParm->getLocation(),
1658           diag::err_function_parameter_pack_without_parameter_packs)
1659        << NewDI->getType();
1660      return nullptr;
1661    }
1662  } else {
1663    NewDI = SubstType(OldDI, TemplateArgs, OldParm->getLocation(),
1664                      OldParm->getDeclName());
1665  }
1666
1667  if (!NewDI)
1668    return nullptr;
1669
1670  if (NewDI->getType()->isVoidType()) {
1671    Diag(OldParm->getLocation(), diag::err_param_with_void_type);
1672    return nullptr;
1673  }
1674
1675  ParmVarDecl *NewParm = CheckParameter(Context.getTranslationUnitDecl(),
1676                                        OldParm->getInnerLocStart(),
1677                                        OldParm->getLocation(),
1678                                        OldParm->getIdentifier(),
1679                                        NewDI->getType(), NewDI,
1680                                        OldParm->getStorageClass());
1681  if (!NewParm)
1682    return nullptr;
1683
1684  // Mark the (new) default argument as uninstantiated (if any).
1685  if (OldParm->hasUninstantiatedDefaultArg()) {
1686    Expr *Arg = OldParm->getUninstantiatedDefaultArg();
1687    NewParm->setUninstantiatedDefaultArg(Arg);
1688  } else if (OldParm->hasUnparsedDefaultArg()) {
1689    NewParm->setUnparsedDefaultArg();
1690    UnparsedDefaultArgInstantiations[OldParm].push_back(NewParm);
1691  } else if (Expr *Arg = OldParm->getDefaultArg())
1692    // FIXME: if we non-lazily instantiated non-dependent default args for
1693    // non-dependent parameter types we could remove a bunch of duplicate
1694    // conversion warnings for such arguments.
1695    NewParm->setUninstantiatedDefaultArg(Arg);
1696
1697  NewParm->setHasInheritedDefaultArg(OldParm->hasInheritedDefaultArg());
1698
1699  if (OldParm->isParameterPack() && !NewParm->isParameterPack()) {
1700    // Add the new parameter to the instantiated parameter pack.
1701    CurrentInstantiationScope->InstantiatedLocalPackArg(OldParm, NewParm);
1702  } else {
1703    // Introduce an Old -> New mapping
1704    CurrentInstantiationScope->InstantiatedLocal(OldParm, NewParm);
1705  }
1706
1707  // FIXME: OldParm may come from a FunctionProtoType, in which case CurContext
1708  // can be anything, is this right ?
1709  NewParm->setDeclContext(CurContext);
1710
1711  NewParm->setScopeInfo(OldParm->getFunctionScopeDepth(),
1712                        OldParm->getFunctionScopeIndex() + indexAdjustment);
1713
1714  InstantiateAttrs(TemplateArgs, OldParm, NewParm);
1715
1716  return NewParm;
1717}
1718
1719/// \brief Substitute the given template arguments into the given set of
1720/// parameters, producing the set of parameter types that would be generated
1721/// from such a substitution.
1722bool Sema::SubstParmTypes(SourceLocation Loc,
1723                          ParmVarDecl **Params, unsigned NumParams,
1724                          const MultiLevelTemplateArgumentList &TemplateArgs,
1725                          SmallVectorImpl<QualType> &ParamTypes,
1726                          SmallVectorImpl<ParmVarDecl *> *OutParams) {
1727  assert(!ActiveTemplateInstantiations.empty() &&
1728         "Cannot perform an instantiation without some context on the "
1729         "instantiation stack");
1730
1731  TemplateInstantiator Instantiator(*this, TemplateArgs, Loc,
1732                                    DeclarationName());
1733  return Instantiator.TransformFunctionTypeParams(Loc, Params, NumParams,
1734                                                  nullptr, ParamTypes,
1735                                                  OutParams);
1736}
1737
1738/// \brief Perform substitution on the base class specifiers of the
1739/// given class template specialization.
1740///
1741/// Produces a diagnostic and returns true on error, returns false and
1742/// attaches the instantiated base classes to the class template
1743/// specialization if successful.
1744bool
1745Sema::SubstBaseSpecifiers(CXXRecordDecl *Instantiation,
1746                          CXXRecordDecl *Pattern,
1747                          const MultiLevelTemplateArgumentList &TemplateArgs) {
1748  bool Invalid = false;
1749  SmallVector<CXXBaseSpecifier*, 4> InstantiatedBases;
1750  for (const auto &Base : Pattern->bases()) {
1751    if (!Base.getType()->isDependentType()) {
1752      if (const CXXRecordDecl *RD = Base.getType()->getAsCXXRecordDecl()) {
1753        if (RD->isInvalidDecl())
1754          Instantiation->setInvalidDecl();
1755      }
1756      InstantiatedBases.push_back(new (Context) CXXBaseSpecifier(Base));
1757      continue;
1758    }
1759
1760    SourceLocation EllipsisLoc;
1761    TypeSourceInfo *BaseTypeLoc;
1762    if (Base.isPackExpansion()) {
1763      // This is a pack expansion. See whether we should expand it now, or
1764      // wait until later.
1765      SmallVector<UnexpandedParameterPack, 2> Unexpanded;
1766      collectUnexpandedParameterPacks(Base.getTypeSourceInfo()->getTypeLoc(),
1767                                      Unexpanded);
1768      bool ShouldExpand = false;
1769      bool RetainExpansion = false;
1770      Optional<unsigned> NumExpansions;
1771      if (CheckParameterPacksForExpansion(Base.getEllipsisLoc(),
1772                                          Base.getSourceRange(),
1773                                          Unexpanded,
1774                                          TemplateArgs, ShouldExpand,
1775                                          RetainExpansion,
1776                                          NumExpansions)) {
1777        Invalid = true;
1778        continue;
1779      }
1780
1781      // If we should expand this pack expansion now, do so.
1782      if (ShouldExpand) {
1783        for (unsigned I = 0; I != *NumExpansions; ++I) {
1784            Sema::ArgumentPackSubstitutionIndexRAII SubstIndex(*this, I);
1785
1786          TypeSourceInfo *BaseTypeLoc = SubstType(Base.getTypeSourceInfo(),
1787                                                  TemplateArgs,
1788                                              Base.getSourceRange().getBegin(),
1789                                                  DeclarationName());
1790          if (!BaseTypeLoc) {
1791            Invalid = true;
1792            continue;
1793          }
1794
1795          if (CXXBaseSpecifier *InstantiatedBase
1796                = CheckBaseSpecifier(Instantiation,
1797                                     Base.getSourceRange(),
1798                                     Base.isVirtual(),
1799                                     Base.getAccessSpecifierAsWritten(),
1800                                     BaseTypeLoc,
1801                                     SourceLocation()))
1802            InstantiatedBases.push_back(InstantiatedBase);
1803          else
1804            Invalid = true;
1805        }
1806
1807        continue;
1808      }
1809
1810      // The resulting base specifier will (still) be a pack expansion.
1811      EllipsisLoc = Base.getEllipsisLoc();
1812      Sema::ArgumentPackSubstitutionIndexRAII SubstIndex(*this, -1);
1813      BaseTypeLoc = SubstType(Base.getTypeSourceInfo(),
1814                              TemplateArgs,
1815                              Base.getSourceRange().getBegin(),
1816                              DeclarationName());
1817    } else {
1818      BaseTypeLoc = SubstType(Base.getTypeSourceInfo(),
1819                              TemplateArgs,
1820                              Base.getSourceRange().getBegin(),
1821                              DeclarationName());
1822    }
1823
1824    if (!BaseTypeLoc) {
1825      Invalid = true;
1826      continue;
1827    }
1828
1829    if (CXXBaseSpecifier *InstantiatedBase
1830          = CheckBaseSpecifier(Instantiation,
1831                               Base.getSourceRange(),
1832                               Base.isVirtual(),
1833                               Base.getAccessSpecifierAsWritten(),
1834                               BaseTypeLoc,
1835                               EllipsisLoc))
1836      InstantiatedBases.push_back(InstantiatedBase);
1837    else
1838      Invalid = true;
1839  }
1840
1841  if (!Invalid &&
1842      AttachBaseSpecifiers(Instantiation, InstantiatedBases.data(),
1843                           InstantiatedBases.size()))
1844    Invalid = true;
1845
1846  return Invalid;
1847}
1848
1849// Defined via #include from SemaTemplateInstantiateDecl.cpp
1850namespace clang {
1851  namespace sema {
1852    Attr *instantiateTemplateAttribute(const Attr *At, ASTContext &C, Sema &S,
1853                            const MultiLevelTemplateArgumentList &TemplateArgs);
1854  }
1855}
1856
1857/// Determine whether we would be unable to instantiate this template (because
1858/// it either has no definition, or is in the process of being instantiated).
1859static bool DiagnoseUninstantiableTemplate(Sema &S,
1860                                           SourceLocation PointOfInstantiation,
1861                                           TagDecl *Instantiation,
1862                                           bool InstantiatedFromMember,
1863                                           TagDecl *Pattern,
1864                                           TagDecl *PatternDef,
1865                                           TemplateSpecializationKind TSK,
1866                                           bool Complain = true) {
1867  if (PatternDef && !PatternDef->isBeingDefined())
1868    return false;
1869
1870  if (!Complain || (PatternDef && PatternDef->isInvalidDecl())) {
1871    // Say nothing
1872  } else if (PatternDef) {
1873    assert(PatternDef->isBeingDefined());
1874    S.Diag(PointOfInstantiation,
1875           diag::err_template_instantiate_within_definition)
1876      << (TSK != TSK_ImplicitInstantiation)
1877      << S.Context.getTypeDeclType(Instantiation);
1878    // Not much point in noting the template declaration here, since
1879    // we're lexically inside it.
1880    Instantiation->setInvalidDecl();
1881  } else if (InstantiatedFromMember) {
1882    S.Diag(PointOfInstantiation,
1883           diag::err_implicit_instantiate_member_undefined)
1884      << S.Context.getTypeDeclType(Instantiation);
1885    S.Diag(Pattern->getLocation(), diag::note_member_declared_at);
1886  } else {
1887    S.Diag(PointOfInstantiation, diag::err_template_instantiate_undefined)
1888      << (TSK != TSK_ImplicitInstantiation)
1889      << S.Context.getTypeDeclType(Instantiation);
1890    S.Diag(Pattern->getLocation(), diag::note_template_decl_here);
1891  }
1892
1893  // In general, Instantiation isn't marked invalid to get more than one
1894  // error for multiple undefined instantiations. But the code that does
1895  // explicit declaration -> explicit definition conversion can't handle
1896  // invalid declarations, so mark as invalid in that case.
1897  if (TSK == TSK_ExplicitInstantiationDeclaration)
1898    Instantiation->setInvalidDecl();
1899  return true;
1900}
1901
1902/// \brief Instantiate the definition of a class from a given pattern.
1903///
1904/// \param PointOfInstantiation The point of instantiation within the
1905/// source code.
1906///
1907/// \param Instantiation is the declaration whose definition is being
1908/// instantiated. This will be either a class template specialization
1909/// or a member class of a class template specialization.
1910///
1911/// \param Pattern is the pattern from which the instantiation
1912/// occurs. This will be either the declaration of a class template or
1913/// the declaration of a member class of a class template.
1914///
1915/// \param TemplateArgs The template arguments to be substituted into
1916/// the pattern.
1917///
1918/// \param TSK the kind of implicit or explicit instantiation to perform.
1919///
1920/// \param Complain whether to complain if the class cannot be instantiated due
1921/// to the lack of a definition.
1922///
1923/// \returns true if an error occurred, false otherwise.
1924bool
1925Sema::InstantiateClass(SourceLocation PointOfInstantiation,
1926                       CXXRecordDecl *Instantiation, CXXRecordDecl *Pattern,
1927                       const MultiLevelTemplateArgumentList &TemplateArgs,
1928                       TemplateSpecializationKind TSK,
1929                       bool Complain) {
1930  CXXRecordDecl *PatternDef
1931    = cast_or_null<CXXRecordDecl>(Pattern->getDefinition());
1932  if (DiagnoseUninstantiableTemplate(*this, PointOfInstantiation, Instantiation,
1933                                Instantiation->getInstantiatedFromMemberClass(),
1934                                     Pattern, PatternDef, TSK, Complain))
1935    return true;
1936  Pattern = PatternDef;
1937
1938  // \brief Record the point of instantiation.
1939  if (MemberSpecializationInfo *MSInfo
1940        = Instantiation->getMemberSpecializationInfo()) {
1941    MSInfo->setTemplateSpecializationKind(TSK);
1942    MSInfo->setPointOfInstantiation(PointOfInstantiation);
1943  } else if (ClassTemplateSpecializationDecl *Spec
1944        = dyn_cast<ClassTemplateSpecializationDecl>(Instantiation)) {
1945    Spec->setTemplateSpecializationKind(TSK);
1946    Spec->setPointOfInstantiation(PointOfInstantiation);
1947  }
1948
1949  InstantiatingTemplate Inst(*this, PointOfInstantiation, Instantiation);
1950  if (Inst.isInvalid())
1951    return true;
1952
1953  // Enter the scope of this instantiation. We don't use
1954  // PushDeclContext because we don't have a scope.
1955  ContextRAII SavedContext(*this, Instantiation);
1956  EnterExpressionEvaluationContext EvalContext(*this,
1957                                               Sema::PotentiallyEvaluated);
1958
1959  // If this is an instantiation of a local class, merge this local
1960  // instantiation scope with the enclosing scope. Otherwise, every
1961  // instantiation of a class has its own local instantiation scope.
1962  bool MergeWithParentScope = !Instantiation->isDefinedOutsideFunctionOrMethod();
1963  LocalInstantiationScope Scope(*this, MergeWithParentScope);
1964
1965  // Pull attributes from the pattern onto the instantiation.
1966  InstantiateAttrs(TemplateArgs, Pattern, Instantiation);
1967
1968  // Start the definition of this instantiation.
1969  Instantiation->startDefinition();
1970
1971  // The instantiation is visible here, even if it was first declared in an
1972  // unimported module.
1973  Instantiation->setHidden(false);
1974
1975  // FIXME: This loses the as-written tag kind for an explicit instantiation.
1976  Instantiation->setTagKind(Pattern->getTagKind());
1977
1978  // Do substitution on the base class specifiers.
1979  if (SubstBaseSpecifiers(Instantiation, Pattern, TemplateArgs))
1980    Instantiation->setInvalidDecl();
1981
1982  TemplateDeclInstantiator Instantiator(*this, Instantiation, TemplateArgs);
1983  SmallVector<Decl*, 4> Fields;
1984  // Delay instantiation of late parsed attributes.
1985  LateInstantiatedAttrVec LateAttrs;
1986  Instantiator.enableLateAttributeInstantiation(&LateAttrs);
1987
1988  for (auto *Member : Pattern->decls()) {
1989    // Don't instantiate members not belonging in this semantic context.
1990    // e.g. for:
1991    // @code
1992    //    template <int i> class A {
1993    //      class B *g;
1994    //    };
1995    // @endcode
1996    // 'class B' has the template as lexical context but semantically it is
1997    // introduced in namespace scope.
1998    if (Member->getDeclContext() != Pattern)
1999      continue;
2000
2001    if (Member->isInvalidDecl()) {
2002      Instantiation->setInvalidDecl();
2003      continue;
2004    }
2005
2006    Decl *NewMember = Instantiator.Visit(Member);
2007    if (NewMember) {
2008      if (FieldDecl *Field = dyn_cast<FieldDecl>(NewMember)) {
2009        Fields.push_back(Field);
2010      } else if (EnumDecl *Enum = dyn_cast<EnumDecl>(NewMember)) {
2011        // C++11 [temp.inst]p1: The implicit instantiation of a class template
2012        // specialization causes the implicit instantiation of the definitions
2013        // of unscoped member enumerations.
2014        // Record a point of instantiation for this implicit instantiation.
2015        if (TSK == TSK_ImplicitInstantiation && !Enum->isScoped() &&
2016            Enum->isCompleteDefinition()) {
2017          MemberSpecializationInfo *MSInfo =Enum->getMemberSpecializationInfo();
2018          assert(MSInfo && "no spec info for member enum specialization");
2019          MSInfo->setTemplateSpecializationKind(TSK_ImplicitInstantiation);
2020          MSInfo->setPointOfInstantiation(PointOfInstantiation);
2021        }
2022      } else if (StaticAssertDecl *SA = dyn_cast<StaticAssertDecl>(NewMember)) {
2023        if (SA->isFailed()) {
2024          // A static_assert failed. Bail out; instantiating this
2025          // class is probably not meaningful.
2026          Instantiation->setInvalidDecl();
2027          break;
2028        }
2029      }
2030
2031      if (NewMember->isInvalidDecl())
2032        Instantiation->setInvalidDecl();
2033    } else {
2034      // FIXME: Eventually, a NULL return will mean that one of the
2035      // instantiations was a semantic disaster, and we'll want to mark the
2036      // declaration invalid.
2037      // For now, we expect to skip some members that we can't yet handle.
2038    }
2039  }
2040
2041  // Finish checking fields.
2042  ActOnFields(nullptr, Instantiation->getLocation(), Instantiation, Fields,
2043              SourceLocation(), SourceLocation(), nullptr);
2044  CheckCompletedCXXClass(Instantiation);
2045
2046  // Default arguments are parsed, if not instantiated. We can go instantiate
2047  // default arg exprs for default constructors if necessary now.
2048  ActOnFinishCXXMemberDefaultArgs(Instantiation);
2049
2050  // Instantiate late parsed attributes, and attach them to their decls.
2051  // See Sema::InstantiateAttrs
2052  for (LateInstantiatedAttrVec::iterator I = LateAttrs.begin(),
2053       E = LateAttrs.end(); I != E; ++I) {
2054    assert(CurrentInstantiationScope == Instantiator.getStartingScope());
2055    CurrentInstantiationScope = I->Scope;
2056
2057    // Allow 'this' within late-parsed attributes.
2058    NamedDecl *ND = dyn_cast<NamedDecl>(I->NewDecl);
2059    CXXRecordDecl *ThisContext =
2060        dyn_cast_or_null<CXXRecordDecl>(ND->getDeclContext());
2061    CXXThisScopeRAII ThisScope(*this, ThisContext, /*TypeQuals*/0,
2062                               ND && ND->isCXXInstanceMember());
2063
2064    Attr *NewAttr =
2065      instantiateTemplateAttribute(I->TmplAttr, Context, *this, TemplateArgs);
2066    I->NewDecl->addAttr(NewAttr);
2067    LocalInstantiationScope::deleteScopes(I->Scope,
2068                                          Instantiator.getStartingScope());
2069  }
2070  Instantiator.disableLateAttributeInstantiation();
2071  LateAttrs.clear();
2072
2073  ActOnFinishDelayedMemberInitializers(Instantiation);
2074
2075  // FIXME: We should do something similar for explicit instantiations so they
2076  // end up in the right module.
2077  if (TSK == TSK_ImplicitInstantiation) {
2078    Instantiation->setLocation(Pattern->getLocation());
2079    Instantiation->setLocStart(Pattern->getInnerLocStart());
2080    Instantiation->setRBraceLoc(Pattern->getRBraceLoc());
2081  }
2082
2083  if (!Instantiation->isInvalidDecl()) {
2084    // Perform any dependent diagnostics from the pattern.
2085    PerformDependentDiagnostics(Pattern, TemplateArgs);
2086
2087    // Instantiate any out-of-line class template partial
2088    // specializations now.
2089    for (TemplateDeclInstantiator::delayed_partial_spec_iterator
2090              P = Instantiator.delayed_partial_spec_begin(),
2091           PEnd = Instantiator.delayed_partial_spec_end();
2092         P != PEnd; ++P) {
2093      if (!Instantiator.InstantiateClassTemplatePartialSpecialization(
2094              P->first, P->second)) {
2095        Instantiation->setInvalidDecl();
2096        break;
2097      }
2098    }
2099
2100    // Instantiate any out-of-line variable template partial
2101    // specializations now.
2102    for (TemplateDeclInstantiator::delayed_var_partial_spec_iterator
2103              P = Instantiator.delayed_var_partial_spec_begin(),
2104           PEnd = Instantiator.delayed_var_partial_spec_end();
2105         P != PEnd; ++P) {
2106      if (!Instantiator.InstantiateVarTemplatePartialSpecialization(
2107              P->first, P->second)) {
2108        Instantiation->setInvalidDecl();
2109        break;
2110      }
2111    }
2112  }
2113
2114  // Exit the scope of this instantiation.
2115  SavedContext.pop();
2116
2117  if (!Instantiation->isInvalidDecl()) {
2118    Consumer.HandleTagDeclDefinition(Instantiation);
2119
2120    // Always emit the vtable for an explicit instantiation definition
2121    // of a polymorphic class template specialization.
2122    if (TSK == TSK_ExplicitInstantiationDefinition)
2123      MarkVTableUsed(PointOfInstantiation, Instantiation, true);
2124  }
2125
2126  return Instantiation->isInvalidDecl();
2127}
2128
2129/// \brief Instantiate the definition of an enum from a given pattern.
2130///
2131/// \param PointOfInstantiation The point of instantiation within the
2132///        source code.
2133/// \param Instantiation is the declaration whose definition is being
2134///        instantiated. This will be a member enumeration of a class
2135///        temploid specialization, or a local enumeration within a
2136///        function temploid specialization.
2137/// \param Pattern The templated declaration from which the instantiation
2138///        occurs.
2139/// \param TemplateArgs The template arguments to be substituted into
2140///        the pattern.
2141/// \param TSK The kind of implicit or explicit instantiation to perform.
2142///
2143/// \return \c true if an error occurred, \c false otherwise.
2144bool Sema::InstantiateEnum(SourceLocation PointOfInstantiation,
2145                           EnumDecl *Instantiation, EnumDecl *Pattern,
2146                           const MultiLevelTemplateArgumentList &TemplateArgs,
2147                           TemplateSpecializationKind TSK) {
2148  EnumDecl *PatternDef = Pattern->getDefinition();
2149  if (DiagnoseUninstantiableTemplate(*this, PointOfInstantiation, Instantiation,
2150                                 Instantiation->getInstantiatedFromMemberEnum(),
2151                                     Pattern, PatternDef, TSK,/*Complain*/true))
2152    return true;
2153  Pattern = PatternDef;
2154
2155  // Record the point of instantiation.
2156  if (MemberSpecializationInfo *MSInfo
2157        = Instantiation->getMemberSpecializationInfo()) {
2158    MSInfo->setTemplateSpecializationKind(TSK);
2159    MSInfo->setPointOfInstantiation(PointOfInstantiation);
2160  }
2161
2162  InstantiatingTemplate Inst(*this, PointOfInstantiation, Instantiation);
2163  if (Inst.isInvalid())
2164    return true;
2165
2166  // The instantiation is visible here, even if it was first declared in an
2167  // unimported module.
2168  Instantiation->setHidden(false);
2169
2170  // Enter the scope of this instantiation. We don't use
2171  // PushDeclContext because we don't have a scope.
2172  ContextRAII SavedContext(*this, Instantiation);
2173  EnterExpressionEvaluationContext EvalContext(*this,
2174                                               Sema::PotentiallyEvaluated);
2175
2176  LocalInstantiationScope Scope(*this, /*MergeWithParentScope*/true);
2177
2178  // Pull attributes from the pattern onto the instantiation.
2179  InstantiateAttrs(TemplateArgs, Pattern, Instantiation);
2180
2181  TemplateDeclInstantiator Instantiator(*this, Instantiation, TemplateArgs);
2182  Instantiator.InstantiateEnumDefinition(Instantiation, Pattern);
2183
2184  // Exit the scope of this instantiation.
2185  SavedContext.pop();
2186
2187  return Instantiation->isInvalidDecl();
2188}
2189
2190
2191/// \brief Instantiate the definition of a field from the given pattern.
2192///
2193/// \param PointOfInstantiation The point of instantiation within the
2194///        source code.
2195/// \param Instantiation is the declaration whose definition is being
2196///        instantiated. This will be a class of a class temploid
2197///        specialization, or a local enumeration within a function temploid
2198///        specialization.
2199/// \param Pattern The templated declaration from which the instantiation
2200///        occurs.
2201/// \param TemplateArgs The template arguments to be substituted into
2202///        the pattern.
2203///
2204/// \return \c true if an error occurred, \c false otherwise.
2205bool Sema::InstantiateInClassInitializer(
2206    SourceLocation PointOfInstantiation, FieldDecl *Instantiation,
2207    FieldDecl *Pattern, const MultiLevelTemplateArgumentList &TemplateArgs) {
2208  // If there is no initializer, we don't need to do anything.
2209  if (!Pattern->hasInClassInitializer())
2210    return false;
2211
2212  assert(Instantiation->getInClassInitStyle() ==
2213             Pattern->getInClassInitStyle() &&
2214         "pattern and instantiation disagree about init style");
2215
2216  // Error out if we haven't parsed the initializer of the pattern yet because
2217  // we are waiting for the closing brace of the outer class.
2218  Expr *OldInit = Pattern->getInClassInitializer();
2219  if (!OldInit) {
2220    RecordDecl *PatternRD = Pattern->getParent();
2221    RecordDecl *OutermostClass = PatternRD->getOuterLexicalRecordContext();
2222    if (OutermostClass == PatternRD) {
2223      Diag(Pattern->getLocEnd(), diag::err_in_class_initializer_not_yet_parsed)
2224          << PatternRD << Pattern;
2225    } else {
2226      Diag(Pattern->getLocEnd(),
2227           diag::err_in_class_initializer_not_yet_parsed_outer_class)
2228          << PatternRD << OutermostClass << Pattern;
2229    }
2230    Instantiation->setInvalidDecl();
2231    return true;
2232  }
2233
2234  InstantiatingTemplate Inst(*this, PointOfInstantiation, Instantiation);
2235  if (Inst.isInvalid())
2236    return true;
2237
2238  // Enter the scope of this instantiation. We don't use PushDeclContext because
2239  // we don't have a scope.
2240  ContextRAII SavedContext(*this, Instantiation->getParent());
2241  EnterExpressionEvaluationContext EvalContext(*this,
2242                                               Sema::PotentiallyEvaluated);
2243
2244  LocalInstantiationScope Scope(*this);
2245
2246  // Instantiate the initializer.
2247  ActOnStartCXXInClassMemberInitializer();
2248  CXXThisScopeRAII ThisScope(*this, Instantiation->getParent(), /*TypeQuals=*/0);
2249
2250  ExprResult NewInit = SubstInitializer(OldInit, TemplateArgs,
2251                                        /*CXXDirectInit=*/false);
2252  Expr *Init = NewInit.get();
2253  assert((!Init || !isa<ParenListExpr>(Init)) && "call-style init in class");
2254  ActOnFinishCXXInClassMemberInitializer(
2255      Instantiation, Init ? Init->getLocStart() : SourceLocation(), Init);
2256
2257  // Exit the scope of this instantiation.
2258  SavedContext.pop();
2259
2260  // Return true if the in-class initializer is still missing.
2261  return !Instantiation->getInClassInitializer();
2262}
2263
2264namespace {
2265  /// \brief A partial specialization whose template arguments have matched
2266  /// a given template-id.
2267  struct PartialSpecMatchResult {
2268    ClassTemplatePartialSpecializationDecl *Partial;
2269    TemplateArgumentList *Args;
2270  };
2271}
2272
2273bool Sema::InstantiateClassTemplateSpecialization(
2274    SourceLocation PointOfInstantiation,
2275    ClassTemplateSpecializationDecl *ClassTemplateSpec,
2276    TemplateSpecializationKind TSK, bool Complain) {
2277  // Perform the actual instantiation on the canonical declaration.
2278  ClassTemplateSpec = cast<ClassTemplateSpecializationDecl>(
2279                                         ClassTemplateSpec->getCanonicalDecl());
2280
2281  // Check whether we have already instantiated or specialized this class
2282  // template specialization.
2283  if (ClassTemplateSpec->getSpecializationKind() != TSK_Undeclared) {
2284    if (ClassTemplateSpec->getSpecializationKind() ==
2285          TSK_ExplicitInstantiationDeclaration &&
2286        TSK == TSK_ExplicitInstantiationDefinition) {
2287      // An explicit instantiation definition follows an explicit instantiation
2288      // declaration (C++0x [temp.explicit]p10); go ahead and perform the
2289      // explicit instantiation.
2290      ClassTemplateSpec->setSpecializationKind(TSK);
2291
2292      // If this is an explicit instantiation definition, mark the
2293      // vtable as used.
2294      if (TSK == TSK_ExplicitInstantiationDefinition &&
2295          !ClassTemplateSpec->isInvalidDecl())
2296        MarkVTableUsed(PointOfInstantiation, ClassTemplateSpec, true);
2297
2298      return false;
2299    }
2300
2301    // We can only instantiate something that hasn't already been
2302    // instantiated or specialized. Fail without any diagnostics: our
2303    // caller will provide an error message.
2304    return true;
2305  }
2306
2307  if (ClassTemplateSpec->isInvalidDecl())
2308    return true;
2309
2310  ClassTemplateDecl *Template = ClassTemplateSpec->getSpecializedTemplate();
2311  CXXRecordDecl *Pattern = nullptr;
2312
2313  // C++ [temp.class.spec.match]p1:
2314  //   When a class template is used in a context that requires an
2315  //   instantiation of the class, it is necessary to determine
2316  //   whether the instantiation is to be generated using the primary
2317  //   template or one of the partial specializations. This is done by
2318  //   matching the template arguments of the class template
2319  //   specialization with the template argument lists of the partial
2320  //   specializations.
2321  typedef PartialSpecMatchResult MatchResult;
2322  SmallVector<MatchResult, 4> Matched;
2323  SmallVector<ClassTemplatePartialSpecializationDecl *, 4> PartialSpecs;
2324  Template->getPartialSpecializations(PartialSpecs);
2325  TemplateSpecCandidateSet FailedCandidates(PointOfInstantiation);
2326  for (unsigned I = 0, N = PartialSpecs.size(); I != N; ++I) {
2327    ClassTemplatePartialSpecializationDecl *Partial = PartialSpecs[I];
2328    TemplateDeductionInfo Info(FailedCandidates.getLocation());
2329    if (TemplateDeductionResult Result
2330          = DeduceTemplateArguments(Partial,
2331                                    ClassTemplateSpec->getTemplateArgs(),
2332                                    Info)) {
2333      // Store the failed-deduction information for use in diagnostics, later.
2334      // TODO: Actually use the failed-deduction info?
2335      FailedCandidates.addCandidate()
2336          .set(Partial, MakeDeductionFailureInfo(Context, Result, Info));
2337      (void)Result;
2338    } else {
2339      Matched.push_back(PartialSpecMatchResult());
2340      Matched.back().Partial = Partial;
2341      Matched.back().Args = Info.take();
2342    }
2343  }
2344
2345  // If we're dealing with a member template where the template parameters
2346  // have been instantiated, this provides the original template parameters
2347  // from which the member template's parameters were instantiated.
2348
2349  if (Matched.size() >= 1) {
2350    SmallVectorImpl<MatchResult>::iterator Best = Matched.begin();
2351    if (Matched.size() == 1) {
2352      //   -- If exactly one matching specialization is found, the
2353      //      instantiation is generated from that specialization.
2354      // We don't need to do anything for this.
2355    } else {
2356      //   -- If more than one matching specialization is found, the
2357      //      partial order rules (14.5.4.2) are used to determine
2358      //      whether one of the specializations is more specialized
2359      //      than the others. If none of the specializations is more
2360      //      specialized than all of the other matching
2361      //      specializations, then the use of the class template is
2362      //      ambiguous and the program is ill-formed.
2363      for (SmallVectorImpl<MatchResult>::iterator P = Best + 1,
2364                                               PEnd = Matched.end();
2365           P != PEnd; ++P) {
2366        if (getMoreSpecializedPartialSpecialization(P->Partial, Best->Partial,
2367                                                    PointOfInstantiation)
2368              == P->Partial)
2369          Best = P;
2370      }
2371
2372      // Determine if the best partial specialization is more specialized than
2373      // the others.
2374      bool Ambiguous = false;
2375      for (SmallVectorImpl<MatchResult>::iterator P = Matched.begin(),
2376                                               PEnd = Matched.end();
2377           P != PEnd; ++P) {
2378        if (P != Best &&
2379            getMoreSpecializedPartialSpecialization(P->Partial, Best->Partial,
2380                                                    PointOfInstantiation)
2381              != Best->Partial) {
2382          Ambiguous = true;
2383          break;
2384        }
2385      }
2386
2387      if (Ambiguous) {
2388        // Partial ordering did not produce a clear winner. Complain.
2389        ClassTemplateSpec->setInvalidDecl();
2390        Diag(PointOfInstantiation, diag::err_partial_spec_ordering_ambiguous)
2391          << ClassTemplateSpec;
2392
2393        // Print the matching partial specializations.
2394        for (SmallVectorImpl<MatchResult>::iterator P = Matched.begin(),
2395                                                 PEnd = Matched.end();
2396             P != PEnd; ++P)
2397          Diag(P->Partial->getLocation(), diag::note_partial_spec_match)
2398            << getTemplateArgumentBindingsText(
2399                                            P->Partial->getTemplateParameters(),
2400                                               *P->Args);
2401
2402        return true;
2403      }
2404    }
2405
2406    // Instantiate using the best class template partial specialization.
2407    ClassTemplatePartialSpecializationDecl *OrigPartialSpec = Best->Partial;
2408    while (OrigPartialSpec->getInstantiatedFromMember()) {
2409      // If we've found an explicit specialization of this class template,
2410      // stop here and use that as the pattern.
2411      if (OrigPartialSpec->isMemberSpecialization())
2412        break;
2413
2414      OrigPartialSpec = OrigPartialSpec->getInstantiatedFromMember();
2415    }
2416
2417    Pattern = OrigPartialSpec;
2418    ClassTemplateSpec->setInstantiationOf(Best->Partial, Best->Args);
2419  } else {
2420    //   -- If no matches are found, the instantiation is generated
2421    //      from the primary template.
2422    ClassTemplateDecl *OrigTemplate = Template;
2423    while (OrigTemplate->getInstantiatedFromMemberTemplate()) {
2424      // If we've found an explicit specialization of this class template,
2425      // stop here and use that as the pattern.
2426      if (OrigTemplate->isMemberSpecialization())
2427        break;
2428
2429      OrigTemplate = OrigTemplate->getInstantiatedFromMemberTemplate();
2430    }
2431
2432    Pattern = OrigTemplate->getTemplatedDecl();
2433  }
2434
2435  bool Result = InstantiateClass(PointOfInstantiation, ClassTemplateSpec,
2436                                 Pattern,
2437                                getTemplateInstantiationArgs(ClassTemplateSpec),
2438                                 TSK,
2439                                 Complain);
2440
2441  return Result;
2442}
2443
2444/// \brief Instantiates the definitions of all of the member
2445/// of the given class, which is an instantiation of a class template
2446/// or a member class of a template.
2447void
2448Sema::InstantiateClassMembers(SourceLocation PointOfInstantiation,
2449                              CXXRecordDecl *Instantiation,
2450                        const MultiLevelTemplateArgumentList &TemplateArgs,
2451                              TemplateSpecializationKind TSK) {
2452  // FIXME: We need to notify the ASTMutationListener that we did all of these
2453  // things, in case we have an explicit instantiation definition in a PCM, a
2454  // module, or preamble, and the declaration is in an imported AST.
2455  assert(
2456      (TSK == TSK_ExplicitInstantiationDefinition ||
2457       TSK == TSK_ExplicitInstantiationDeclaration ||
2458       (TSK == TSK_ImplicitInstantiation && Instantiation->isLocalClass())) &&
2459      "Unexpected template specialization kind!");
2460  for (auto *D : Instantiation->decls()) {
2461    bool SuppressNew = false;
2462    if (auto *Function = dyn_cast<FunctionDecl>(D)) {
2463      if (FunctionDecl *Pattern
2464            = Function->getInstantiatedFromMemberFunction()) {
2465        MemberSpecializationInfo *MSInfo
2466          = Function->getMemberSpecializationInfo();
2467        assert(MSInfo && "No member specialization information?");
2468        if (MSInfo->getTemplateSpecializationKind()
2469                                                 == TSK_ExplicitSpecialization)
2470          continue;
2471
2472        if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
2473                                                   Function,
2474                                        MSInfo->getTemplateSpecializationKind(),
2475                                              MSInfo->getPointOfInstantiation(),
2476                                                   SuppressNew) ||
2477            SuppressNew)
2478          continue;
2479
2480        // C++11 [temp.explicit]p8:
2481        //   An explicit instantiation definition that names a class template
2482        //   specialization explicitly instantiates the class template
2483        //   specialization and is only an explicit instantiation definition
2484        //   of members whose definition is visible at the point of
2485        //   instantiation.
2486        if (TSK == TSK_ExplicitInstantiationDefinition && !Pattern->isDefined())
2487          continue;
2488
2489        Function->setTemplateSpecializationKind(TSK, PointOfInstantiation);
2490
2491        if (Function->isDefined()) {
2492          // Let the ASTConsumer know that this function has been explicitly
2493          // instantiated now, and its linkage might have changed.
2494          Consumer.HandleTopLevelDecl(DeclGroupRef(Function));
2495        } else if (TSK == TSK_ExplicitInstantiationDefinition) {
2496          InstantiateFunctionDefinition(PointOfInstantiation, Function);
2497        } else if (TSK == TSK_ImplicitInstantiation) {
2498          PendingLocalImplicitInstantiations.push_back(
2499              std::make_pair(Function, PointOfInstantiation));
2500        }
2501      }
2502    } else if (auto *Var = dyn_cast<VarDecl>(D)) {
2503      if (isa<VarTemplateSpecializationDecl>(Var))
2504        continue;
2505
2506      if (Var->isStaticDataMember()) {
2507        MemberSpecializationInfo *MSInfo = Var->getMemberSpecializationInfo();
2508        assert(MSInfo && "No member specialization information?");
2509        if (MSInfo->getTemplateSpecializationKind()
2510                                                 == TSK_ExplicitSpecialization)
2511          continue;
2512
2513        if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
2514                                                   Var,
2515                                        MSInfo->getTemplateSpecializationKind(),
2516                                              MSInfo->getPointOfInstantiation(),
2517                                                   SuppressNew) ||
2518            SuppressNew)
2519          continue;
2520
2521        if (TSK == TSK_ExplicitInstantiationDefinition) {
2522          // C++0x [temp.explicit]p8:
2523          //   An explicit instantiation definition that names a class template
2524          //   specialization explicitly instantiates the class template
2525          //   specialization and is only an explicit instantiation definition
2526          //   of members whose definition is visible at the point of
2527          //   instantiation.
2528          if (!Var->getInstantiatedFromStaticDataMember()
2529                                                     ->getOutOfLineDefinition())
2530            continue;
2531
2532          Var->setTemplateSpecializationKind(TSK, PointOfInstantiation);
2533          InstantiateStaticDataMemberDefinition(PointOfInstantiation, Var);
2534        } else {
2535          Var->setTemplateSpecializationKind(TSK, PointOfInstantiation);
2536        }
2537      }
2538    } else if (auto *Record = dyn_cast<CXXRecordDecl>(D)) {
2539      // Always skip the injected-class-name, along with any
2540      // redeclarations of nested classes, since both would cause us
2541      // to try to instantiate the members of a class twice.
2542      // Skip closure types; they'll get instantiated when we instantiate
2543      // the corresponding lambda-expression.
2544      if (Record->isInjectedClassName() || Record->getPreviousDecl() ||
2545          Record->isLambda())
2546        continue;
2547
2548      MemberSpecializationInfo *MSInfo = Record->getMemberSpecializationInfo();
2549      assert(MSInfo && "No member specialization information?");
2550
2551      if (MSInfo->getTemplateSpecializationKind()
2552                                                == TSK_ExplicitSpecialization)
2553        continue;
2554
2555      if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
2556                                                 Record,
2557                                        MSInfo->getTemplateSpecializationKind(),
2558                                              MSInfo->getPointOfInstantiation(),
2559                                                 SuppressNew) ||
2560          SuppressNew)
2561        continue;
2562
2563      CXXRecordDecl *Pattern = Record->getInstantiatedFromMemberClass();
2564      assert(Pattern && "Missing instantiated-from-template information");
2565
2566      if (!Record->getDefinition()) {
2567        if (!Pattern->getDefinition()) {
2568          // C++0x [temp.explicit]p8:
2569          //   An explicit instantiation definition that names a class template
2570          //   specialization explicitly instantiates the class template
2571          //   specialization and is only an explicit instantiation definition
2572          //   of members whose definition is visible at the point of
2573          //   instantiation.
2574          if (TSK == TSK_ExplicitInstantiationDeclaration) {
2575            MSInfo->setTemplateSpecializationKind(TSK);
2576            MSInfo->setPointOfInstantiation(PointOfInstantiation);
2577          }
2578
2579          continue;
2580        }
2581
2582        InstantiateClass(PointOfInstantiation, Record, Pattern,
2583                         TemplateArgs,
2584                         TSK);
2585      } else {
2586        if (TSK == TSK_ExplicitInstantiationDefinition &&
2587            Record->getTemplateSpecializationKind() ==
2588                TSK_ExplicitInstantiationDeclaration) {
2589          Record->setTemplateSpecializationKind(TSK);
2590          MarkVTableUsed(PointOfInstantiation, Record, true);
2591        }
2592      }
2593
2594      Pattern = cast_or_null<CXXRecordDecl>(Record->getDefinition());
2595      if (Pattern)
2596        InstantiateClassMembers(PointOfInstantiation, Pattern, TemplateArgs,
2597                                TSK);
2598    } else if (auto *Enum = dyn_cast<EnumDecl>(D)) {
2599      MemberSpecializationInfo *MSInfo = Enum->getMemberSpecializationInfo();
2600      assert(MSInfo && "No member specialization information?");
2601
2602      if (MSInfo->getTemplateSpecializationKind()
2603            == TSK_ExplicitSpecialization)
2604        continue;
2605
2606      if (CheckSpecializationInstantiationRedecl(
2607            PointOfInstantiation, TSK, Enum,
2608            MSInfo->getTemplateSpecializationKind(),
2609            MSInfo->getPointOfInstantiation(), SuppressNew) ||
2610          SuppressNew)
2611        continue;
2612
2613      if (Enum->getDefinition())
2614        continue;
2615
2616      EnumDecl *Pattern = Enum->getInstantiatedFromMemberEnum();
2617      assert(Pattern && "Missing instantiated-from-template information");
2618
2619      if (TSK == TSK_ExplicitInstantiationDefinition) {
2620        if (!Pattern->getDefinition())
2621          continue;
2622
2623        InstantiateEnum(PointOfInstantiation, Enum, Pattern, TemplateArgs, TSK);
2624      } else {
2625        MSInfo->setTemplateSpecializationKind(TSK);
2626        MSInfo->setPointOfInstantiation(PointOfInstantiation);
2627      }
2628    } else if (auto *Field = dyn_cast<FieldDecl>(D)) {
2629      // No need to instantiate in-class initializers during explicit
2630      // instantiation.
2631      if (Field->hasInClassInitializer() && TSK == TSK_ImplicitInstantiation) {
2632        CXXRecordDecl *ClassPattern =
2633            Instantiation->getTemplateInstantiationPattern();
2634        DeclContext::lookup_result Lookup =
2635            ClassPattern->lookup(Field->getDeclName());
2636        assert(Lookup.size() == 1);
2637        FieldDecl *Pattern = cast<FieldDecl>(Lookup[0]);
2638        InstantiateInClassInitializer(PointOfInstantiation, Field, Pattern,
2639                                      TemplateArgs);
2640      }
2641    }
2642  }
2643}
2644
2645/// \brief Instantiate the definitions of all of the members of the
2646/// given class template specialization, which was named as part of an
2647/// explicit instantiation.
2648void
2649Sema::InstantiateClassTemplateSpecializationMembers(
2650                                           SourceLocation PointOfInstantiation,
2651                            ClassTemplateSpecializationDecl *ClassTemplateSpec,
2652                                               TemplateSpecializationKind TSK) {
2653  // C++0x [temp.explicit]p7:
2654  //   An explicit instantiation that names a class template
2655  //   specialization is an explicit instantion of the same kind
2656  //   (declaration or definition) of each of its members (not
2657  //   including members inherited from base classes) that has not
2658  //   been previously explicitly specialized in the translation unit
2659  //   containing the explicit instantiation, except as described
2660  //   below.
2661  InstantiateClassMembers(PointOfInstantiation, ClassTemplateSpec,
2662                          getTemplateInstantiationArgs(ClassTemplateSpec),
2663                          TSK);
2664}
2665
2666StmtResult
2667Sema::SubstStmt(Stmt *S, const MultiLevelTemplateArgumentList &TemplateArgs) {
2668  if (!S)
2669    return S;
2670
2671  TemplateInstantiator Instantiator(*this, TemplateArgs,
2672                                    SourceLocation(),
2673                                    DeclarationName());
2674  return Instantiator.TransformStmt(S);
2675}
2676
2677ExprResult
2678Sema::SubstExpr(Expr *E, const MultiLevelTemplateArgumentList &TemplateArgs) {
2679  if (!E)
2680    return E;
2681
2682  TemplateInstantiator Instantiator(*this, TemplateArgs,
2683                                    SourceLocation(),
2684                                    DeclarationName());
2685  return Instantiator.TransformExpr(E);
2686}
2687
2688ExprResult Sema::SubstInitializer(Expr *Init,
2689                          const MultiLevelTemplateArgumentList &TemplateArgs,
2690                          bool CXXDirectInit) {
2691  TemplateInstantiator Instantiator(*this, TemplateArgs,
2692                                    SourceLocation(),
2693                                    DeclarationName());
2694  return Instantiator.TransformInitializer(Init, CXXDirectInit);
2695}
2696
2697bool Sema::SubstExprs(Expr **Exprs, unsigned NumExprs, bool IsCall,
2698                      const MultiLevelTemplateArgumentList &TemplateArgs,
2699                      SmallVectorImpl<Expr *> &Outputs) {
2700  if (NumExprs == 0)
2701    return false;
2702
2703  TemplateInstantiator Instantiator(*this, TemplateArgs,
2704                                    SourceLocation(),
2705                                    DeclarationName());
2706  return Instantiator.TransformExprs(Exprs, NumExprs, IsCall, Outputs);
2707}
2708
2709NestedNameSpecifierLoc
2710Sema::SubstNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS,
2711                        const MultiLevelTemplateArgumentList &TemplateArgs) {
2712  if (!NNS)
2713    return NestedNameSpecifierLoc();
2714
2715  TemplateInstantiator Instantiator(*this, TemplateArgs, NNS.getBeginLoc(),
2716                                    DeclarationName());
2717  return Instantiator.TransformNestedNameSpecifierLoc(NNS);
2718}
2719
2720/// \brief Do template substitution on declaration name info.
2721DeclarationNameInfo
2722Sema::SubstDeclarationNameInfo(const DeclarationNameInfo &NameInfo,
2723                         const MultiLevelTemplateArgumentList &TemplateArgs) {
2724  TemplateInstantiator Instantiator(*this, TemplateArgs, NameInfo.getLoc(),
2725                                    NameInfo.getName());
2726  return Instantiator.TransformDeclarationNameInfo(NameInfo);
2727}
2728
2729TemplateName
2730Sema::SubstTemplateName(NestedNameSpecifierLoc QualifierLoc,
2731                        TemplateName Name, SourceLocation Loc,
2732                        const MultiLevelTemplateArgumentList &TemplateArgs) {
2733  TemplateInstantiator Instantiator(*this, TemplateArgs, Loc,
2734                                    DeclarationName());
2735  CXXScopeSpec SS;
2736  SS.Adopt(QualifierLoc);
2737  return Instantiator.TransformTemplateName(SS, Name, Loc);
2738}
2739
2740bool Sema::Subst(const TemplateArgumentLoc *Args, unsigned NumArgs,
2741                 TemplateArgumentListInfo &Result,
2742                 const MultiLevelTemplateArgumentList &TemplateArgs) {
2743  TemplateInstantiator Instantiator(*this, TemplateArgs, SourceLocation(),
2744                                    DeclarationName());
2745
2746  return Instantiator.TransformTemplateArguments(Args, NumArgs, Result);
2747}
2748
2749static const Decl *getCanonicalParmVarDecl(const Decl *D) {
2750  // When storing ParmVarDecls in the local instantiation scope, we always
2751  // want to use the ParmVarDecl from the canonical function declaration,
2752  // since the map is then valid for any redeclaration or definition of that
2753  // function.
2754  if (const ParmVarDecl *PV = dyn_cast<ParmVarDecl>(D)) {
2755    if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(PV->getDeclContext())) {
2756      unsigned i = PV->getFunctionScopeIndex();
2757      // This parameter might be from a freestanding function type within the
2758      // function and isn't necessarily referring to one of FD's parameters.
2759      if (FD->getParamDecl(i) == PV)
2760        return FD->getCanonicalDecl()->getParamDecl(i);
2761    }
2762  }
2763  return D;
2764}
2765
2766
2767llvm::PointerUnion<Decl *, LocalInstantiationScope::DeclArgumentPack *> *
2768LocalInstantiationScope::findInstantiationOf(const Decl *D) {
2769  D = getCanonicalParmVarDecl(D);
2770  for (LocalInstantiationScope *Current = this; Current;
2771       Current = Current->Outer) {
2772
2773    // Check if we found something within this scope.
2774    const Decl *CheckD = D;
2775    do {
2776      LocalDeclsMap::iterator Found = Current->LocalDecls.find(CheckD);
2777      if (Found != Current->LocalDecls.end())
2778        return &Found->second;
2779
2780      // If this is a tag declaration, it's possible that we need to look for
2781      // a previous declaration.
2782      if (const TagDecl *Tag = dyn_cast<TagDecl>(CheckD))
2783        CheckD = Tag->getPreviousDecl();
2784      else
2785        CheckD = nullptr;
2786    } while (CheckD);
2787
2788    // If we aren't combined with our outer scope, we're done.
2789    if (!Current->CombineWithOuterScope)
2790      break;
2791  }
2792
2793  // If we're performing a partial substitution during template argument
2794  // deduction, we may not have values for template parameters yet.
2795  if (isa<NonTypeTemplateParmDecl>(D) || isa<TemplateTypeParmDecl>(D) ||
2796      isa<TemplateTemplateParmDecl>(D))
2797    return nullptr;
2798
2799  // If we didn't find the decl, then we either have a sema bug, or we have a
2800  // forward reference to a label declaration.  Return null to indicate that
2801  // we have an uninstantiated label.
2802  assert(isa<LabelDecl>(D) && "declaration not instantiated in this scope");
2803  return nullptr;
2804}
2805
2806void LocalInstantiationScope::InstantiatedLocal(const Decl *D, Decl *Inst) {
2807  D = getCanonicalParmVarDecl(D);
2808  llvm::PointerUnion<Decl *, DeclArgumentPack *> &Stored = LocalDecls[D];
2809  if (Stored.isNull()) {
2810#ifndef NDEBUG
2811    // It should not be present in any surrounding scope either.
2812    LocalInstantiationScope *Current = this;
2813    while (Current->CombineWithOuterScope && Current->Outer) {
2814      Current = Current->Outer;
2815      assert(Current->LocalDecls.find(D) == Current->LocalDecls.end() &&
2816             "Instantiated local in inner and outer scopes");
2817    }
2818#endif
2819    Stored = Inst;
2820  } else if (DeclArgumentPack *Pack = Stored.dyn_cast<DeclArgumentPack *>()) {
2821    Pack->push_back(Inst);
2822  } else {
2823    assert(Stored.get<Decl *>() == Inst && "Already instantiated this local");
2824  }
2825}
2826
2827void LocalInstantiationScope::InstantiatedLocalPackArg(const Decl *D,
2828                                                       Decl *Inst) {
2829  D = getCanonicalParmVarDecl(D);
2830  DeclArgumentPack *Pack = LocalDecls[D].get<DeclArgumentPack *>();
2831  Pack->push_back(Inst);
2832}
2833
2834void LocalInstantiationScope::MakeInstantiatedLocalArgPack(const Decl *D) {
2835#ifndef NDEBUG
2836  // This should be the first time we've been told about this decl.
2837  for (LocalInstantiationScope *Current = this;
2838       Current && Current->CombineWithOuterScope; Current = Current->Outer)
2839    assert(Current->LocalDecls.find(D) == Current->LocalDecls.end() &&
2840           "Creating local pack after instantiation of local");
2841#endif
2842
2843  D = getCanonicalParmVarDecl(D);
2844  llvm::PointerUnion<Decl *, DeclArgumentPack *> &Stored = LocalDecls[D];
2845  DeclArgumentPack *Pack = new DeclArgumentPack;
2846  Stored = Pack;
2847  ArgumentPacks.push_back(Pack);
2848}
2849
2850void LocalInstantiationScope::SetPartiallySubstitutedPack(NamedDecl *Pack,
2851                                          const TemplateArgument *ExplicitArgs,
2852                                                    unsigned NumExplicitArgs) {
2853  assert((!PartiallySubstitutedPack || PartiallySubstitutedPack == Pack) &&
2854         "Already have a partially-substituted pack");
2855  assert((!PartiallySubstitutedPack
2856          || NumArgsInPartiallySubstitutedPack == NumExplicitArgs) &&
2857         "Wrong number of arguments in partially-substituted pack");
2858  PartiallySubstitutedPack = Pack;
2859  ArgsInPartiallySubstitutedPack = ExplicitArgs;
2860  NumArgsInPartiallySubstitutedPack = NumExplicitArgs;
2861}
2862
2863NamedDecl *LocalInstantiationScope::getPartiallySubstitutedPack(
2864                                         const TemplateArgument **ExplicitArgs,
2865                                              unsigned *NumExplicitArgs) const {
2866  if (ExplicitArgs)
2867    *ExplicitArgs = nullptr;
2868  if (NumExplicitArgs)
2869    *NumExplicitArgs = 0;
2870
2871  for (const LocalInstantiationScope *Current = this; Current;
2872       Current = Current->Outer) {
2873    if (Current->PartiallySubstitutedPack) {
2874      if (ExplicitArgs)
2875        *ExplicitArgs = Current->ArgsInPartiallySubstitutedPack;
2876      if (NumExplicitArgs)
2877        *NumExplicitArgs = Current->NumArgsInPartiallySubstitutedPack;
2878
2879      return Current->PartiallySubstitutedPack;
2880    }
2881
2882    if (!Current->CombineWithOuterScope)
2883      break;
2884  }
2885
2886  return nullptr;
2887}
2888