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