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