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