clang/lib/Sema/SemaTemplateInstantiate.cpp

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