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