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