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

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