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