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