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