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