contrib/llvm/tools/clang/lib/Sema/SemaTemplateInstantiate.cpp

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