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