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