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 "Sema.h"
  14 #include "TreeTransform.h"
  15 #include "Lookup.h"
  16 #include "clang/AST/ASTConsumer.h"
  17 #include "clang/AST/ASTContext.h"
  18 #include "clang/AST/Expr.h"
  19 #include "clang/AST/DeclTemplate.h"
  20 #include "clang/Parse/DeclSpec.h"
  21 #include "clang/Basic/LangOptions.h"
  22
  23 using namespace clang;
  24
  25 //===----------------------------------------------------------------------===/
  26 // Template Instantiation Support
  27 //===----------------------------------------------------------------------===/
  28
  29 /// \brief Retrieve the template argument list(s) that should be used to
  30 /// instantiate the definition of the given declaration.
  31 ///
  32 /// \param D the declaration for which we are computing template instantiation
  33 /// arguments.
  34 ///
  35 /// \param Innermost if non-NULL, the innermost template argument list.
  36 ///
  37 /// \param RelativeToPrimary true if we should get the template
  38 /// arguments relative to the primary template, even when we're
  39 /// dealing with a specialization. This is only relevant for function
  40 /// template specializations.
  41 ///
  42 /// \param Pattern If non-NULL, indicates the pattern from which we will be
  43 /// instantiating the definition of the given declaration, \p D. This is
  44 /// used to determine the proper set of template instantiation arguments for
  45 /// friend function template specializations.
  46 MultiLevelTemplateArgumentList
  47 Sema::getTemplateInstantiationArgs(NamedDecl *D,
  48                                    const TemplateArgumentList *Innermost,
  49                                    bool RelativeToPrimary,
  50                                    const FunctionDecl *Pattern) {
  51   // Accumulate the set of template argument lists in this structure.
  52   MultiLevelTemplateArgumentList Result;
  53
  54   if (Innermost)
  55     Result.addOuterTemplateArguments(Innermost);
  56
  57   DeclContext *Ctx = dyn_cast<DeclContext>(D);
  58   if (!Ctx)
  59     Ctx = D->getDeclContext();
  60
  61   while (!Ctx->isFileContext()) {
  62     // Add template arguments from a class template instantiation.
  63     if (ClassTemplateSpecializationDecl *Spec
  64           = dyn_cast<ClassTemplateSpecializationDecl>(Ctx)) {
  65       // We're done when we hit an explicit specialization.
  66       if (Spec->getSpecializationKind() == TSK_ExplicitSpecialization &&
  67           !isa<ClassTemplatePartialSpecializationDecl>(Spec))
  68         break;
  69
  70       Result.addOuterTemplateArguments(&Spec->getTemplateInstantiationArgs());
  71
  72       // If this class template specialization was instantiated from a
  73       // specialized member that is a class template, we're done.
  74       assert(Spec->getSpecializedTemplate() && "No class template?");
  75       if (Spec->getSpecializedTemplate()->isMemberSpecialization())
  76         break;
  77     }
  78     // Add template arguments from a function template specialization.
  79     else if (FunctionDecl *Function = dyn_cast<FunctionDecl>(Ctx)) {
  80       if (!RelativeToPrimary &&
  81           Function->getTemplateSpecializationKind()
  82                                                   == TSK_ExplicitSpecialization)
  83         break;
  84
  85       if (const TemplateArgumentList *TemplateArgs
  86             = Function->getTemplateSpecializationArgs()) {
  87         // Add the template arguments for this specialization.
  88         Result.addOuterTemplateArguments(TemplateArgs);
  89
  90         // If this function was instantiated from a specialized member that is
  91         // a function template, we're done.
  92         assert(Function->getPrimaryTemplate() && "No function template?");
  93         if (Function->getPrimaryTemplate()->isMemberSpecialization())
  94           break;
  95       }
  96
  97       // If this is a friend declaration and it declares an entity at
  98       // namespace scope, take arguments from its lexical parent
  99       // instead of its semantic parent, unless of course the pattern we're
 100       // instantiating actually comes from the file's context!
 101       if (Function->getFriendObjectKind() &&
 102           Function->getDeclContext()->isFileContext() &&
 103           (!Pattern || !Pattern->getLexicalDeclContext()->isFileContext())) {
 104         Ctx = Function->getLexicalDeclContext();
 105         RelativeToPrimary = false;
 106         continue;
 107       }
 108     } else if (CXXRecordDecl *Rec = dyn_cast<CXXRecordDecl>(Ctx)) {
 109       if (ClassTemplateDecl *ClassTemplate = Rec->getDescribedClassTemplate()) {
 110         QualType T = ClassTemplate->getInjectedClassNameSpecialization();
 111         const TemplateSpecializationType *TST
 112           = cast<TemplateSpecializationType>(Context.getCanonicalType(T));
 113         Result.addOuterTemplateArguments(TST->getArgs(), TST->getNumArgs());
 114         if (ClassTemplate->isMemberSpecialization())
 115           break;
 116       }
 117     }
 118
 119     Ctx = Ctx->getParent();
 120     RelativeToPrimary = false;
 121   }
 122
 123   return Result;
 124 }
 125
 126 bool Sema::ActiveTemplateInstantiation::isInstantiationRecord() const {
 127   switch (Kind) {
 128   case TemplateInstantiation:
 129   case DefaultTemplateArgumentInstantiation:
 130   case DefaultFunctionArgumentInstantiation:
 131     return true;
 132
 133   case ExplicitTemplateArgumentSubstitution:
 134   case DeducedTemplateArgumentSubstitution:
 135   case PriorTemplateArgumentSubstitution:
 136   case DefaultTemplateArgumentChecking:
 137     return false;
 138   }
 139
 140   return true;
 141 }
 142
 143 Sema::InstantiatingTemplate::
 144 InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
 145                       Decl *Entity,
 146                       SourceRange InstantiationRange)
 147   :  SemaRef(SemaRef) {
 148
 149   Invalid = CheckInstantiationDepth(PointOfInstantiation,
 150                                     InstantiationRange);
 151   if (!Invalid) {
 152     ActiveTemplateInstantiation Inst;
 153     Inst.Kind = ActiveTemplateInstantiation::TemplateInstantiation;
 154     Inst.PointOfInstantiation = PointOfInstantiation;
 155     Inst.Entity = reinterpret_cast<uintptr_t>(Entity);
 156     Inst.TemplateArgs = 0;
 157     Inst.NumTemplateArgs = 0;
 158     Inst.InstantiationRange = InstantiationRange;
 159     SemaRef.ActiveTemplateInstantiations.push_back(Inst);
 160   }
 161 }
 162
 163 Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
 164                                          SourceLocation PointOfInstantiation,
 165                                          TemplateDecl *Template,
 166                                          const TemplateArgument *TemplateArgs,
 167                                          unsigned NumTemplateArgs,
 168                                          SourceRange InstantiationRange)
 169   : SemaRef(SemaRef) {
 170
 171   Invalid = CheckInstantiationDepth(PointOfInstantiation,
 172                                     InstantiationRange);
 173   if (!Invalid) {
 174     ActiveTemplateInstantiation Inst;
 175     Inst.Kind
 176       = ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation;
 177     Inst.PointOfInstantiation = PointOfInstantiation;
 178     Inst.Entity = reinterpret_cast<uintptr_t>(Template);
 179     Inst.TemplateArgs = TemplateArgs;
 180     Inst.NumTemplateArgs = NumTemplateArgs;
 181     Inst.InstantiationRange = InstantiationRange;
 182     SemaRef.ActiveTemplateInstantiations.push_back(Inst);
 183   }
 184 }
 185
 186 Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
 187                                          SourceLocation PointOfInstantiation,
 188                                       FunctionTemplateDecl *FunctionTemplate,
 189                                         const TemplateArgument *TemplateArgs,
 190                                                    unsigned NumTemplateArgs,
 191                          ActiveTemplateInstantiation::InstantiationKind Kind,
 192                                               SourceRange InstantiationRange)
 193 : SemaRef(SemaRef) {
 194
 195   Invalid = CheckInstantiationDepth(PointOfInstantiation,
 196                                     InstantiationRange);
 197   if (!Invalid) {
 198     ActiveTemplateInstantiation Inst;
 199     Inst.Kind = Kind;
 200     Inst.PointOfInstantiation = PointOfInstantiation;
 201     Inst.Entity = reinterpret_cast<uintptr_t>(FunctionTemplate);
 202     Inst.TemplateArgs = TemplateArgs;
 203     Inst.NumTemplateArgs = NumTemplateArgs;
 204     Inst.InstantiationRange = InstantiationRange;
 205     SemaRef.ActiveTemplateInstantiations.push_back(Inst);
 206
 207     if (!Inst.isInstantiationRecord())
 208       ++SemaRef.NonInstantiationEntries;
 209   }
 210 }
 211
 212 Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
 213                                          SourceLocation PointOfInstantiation,
 214                           ClassTemplatePartialSpecializationDecl *PartialSpec,
 215                                          const TemplateArgument *TemplateArgs,
 216                                          unsigned NumTemplateArgs,
 217                                          SourceRange InstantiationRange)
 218   : SemaRef(SemaRef) {
 219
 220   Invalid = false;
 221
 222   ActiveTemplateInstantiation Inst;
 223   Inst.Kind = ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution;
 224   Inst.PointOfInstantiation = PointOfInstantiation;
 225   Inst.Entity = reinterpret_cast<uintptr_t>(PartialSpec);
 226   Inst.TemplateArgs = TemplateArgs;
 227   Inst.NumTemplateArgs = NumTemplateArgs;
 228   Inst.InstantiationRange = InstantiationRange;
 229   SemaRef.ActiveTemplateInstantiations.push_back(Inst);
 230
 231   assert(!Inst.isInstantiationRecord());
 232   ++SemaRef.NonInstantiationEntries;
 233 }
 234
 235 Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
 236                                           SourceLocation PointOfInstantiation,
 237                                           ParmVarDecl *Param,
 238                                           const TemplateArgument *TemplateArgs,
 239                                           unsigned NumTemplateArgs,
 240                                           SourceRange InstantiationRange)
 241   : SemaRef(SemaRef) {
 242
 243   Invalid = CheckInstantiationDepth(PointOfInstantiation, InstantiationRange);
 244
 245   if (!Invalid) {
 246     ActiveTemplateInstantiation Inst;
 247     Inst.Kind
 248       = ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation;
 249     Inst.PointOfInstantiation = PointOfInstantiation;
 250     Inst.Entity = reinterpret_cast<uintptr_t>(Param);
 251     Inst.TemplateArgs = TemplateArgs;
 252     Inst.NumTemplateArgs = NumTemplateArgs;
 253     Inst.InstantiationRange = InstantiationRange;
 254     SemaRef.ActiveTemplateInstantiations.push_back(Inst);
 255   }
 256 }
 257
 258 Sema::InstantiatingTemplate::
 259 InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
 260                       TemplateDecl *Template,
 261                       NonTypeTemplateParmDecl *Param,
 262                       const TemplateArgument *TemplateArgs,
 263                       unsigned NumTemplateArgs,
 264                       SourceRange InstantiationRange) : SemaRef(SemaRef) {
 265   Invalid = false;
 266
 267   ActiveTemplateInstantiation Inst;
 268   Inst.Kind = ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution;
 269   Inst.PointOfInstantiation = PointOfInstantiation;
 270   Inst.Template = Template;
 271   Inst.Entity = reinterpret_cast<uintptr_t>(Param);
 272   Inst.TemplateArgs = TemplateArgs;
 273   Inst.NumTemplateArgs = NumTemplateArgs;
 274   Inst.InstantiationRange = InstantiationRange;
 275   SemaRef.ActiveTemplateInstantiations.push_back(Inst);
 276
 277   assert(!Inst.isInstantiationRecord());
 278   ++SemaRef.NonInstantiationEntries;
 279 }
 280
 281 Sema::InstantiatingTemplate::
 282 InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
 283                       TemplateDecl *Template,
 284                       TemplateTemplateParmDecl *Param,
 285                       const TemplateArgument *TemplateArgs,
 286                       unsigned NumTemplateArgs,
 287                       SourceRange InstantiationRange) : SemaRef(SemaRef) {
 288   Invalid = false;
 289   ActiveTemplateInstantiation Inst;
 290   Inst.Kind = ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution;
 291   Inst.PointOfInstantiation = PointOfInstantiation;
 292   Inst.Template = Template;
 293   Inst.Entity = reinterpret_cast<uintptr_t>(Param);
 294   Inst.TemplateArgs = TemplateArgs;
 295   Inst.NumTemplateArgs = NumTemplateArgs;
 296   Inst.InstantiationRange = InstantiationRange;
 297   SemaRef.ActiveTemplateInstantiations.push_back(Inst);
 298
 299   assert(!Inst.isInstantiationRecord());
 300   ++SemaRef.NonInstantiationEntries;
 301 }
 302
 303 Sema::InstantiatingTemplate::
 304 InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
 305                       TemplateDecl *Template,
 306                       NamedDecl *Param,
 307                       const TemplateArgument *TemplateArgs,
 308                       unsigned NumTemplateArgs,
 309                       SourceRange InstantiationRange) : SemaRef(SemaRef) {
 310   Invalid = false;
 311
 312   ActiveTemplateInstantiation Inst;
 313   Inst.Kind = ActiveTemplateInstantiation::DefaultTemplateArgumentChecking;
 314   Inst.PointOfInstantiation = PointOfInstantiation;
 315   Inst.Template = Template;
 316   Inst.Entity = reinterpret_cast<uintptr_t>(Param);
 317   Inst.TemplateArgs = TemplateArgs;
 318   Inst.NumTemplateArgs = NumTemplateArgs;
 319   Inst.InstantiationRange = InstantiationRange;
 320   SemaRef.ActiveTemplateInstantiations.push_back(Inst);
 321
 322   assert(!Inst.isInstantiationRecord());
 323   ++SemaRef.NonInstantiationEntries;
 324 }
 325
 326 void Sema::InstantiatingTemplate::Clear() {
 327   if (!Invalid) {
 328     if (!SemaRef.ActiveTemplateInstantiations.back().isInstantiationRecord()) {
 329       assert(SemaRef.NonInstantiationEntries > 0);
 330       --SemaRef.NonInstantiationEntries;
 331     }
 332
 333     SemaRef.ActiveTemplateInstantiations.pop_back();
 334     Invalid = true;
 335   }
 336 }
 337
 338 bool Sema::InstantiatingTemplate::CheckInstantiationDepth(
 339                                         SourceLocation PointOfInstantiation,
 340                                            SourceRange InstantiationRange) {
 341   assert(SemaRef.NonInstantiationEntries <=
 342                                    SemaRef.ActiveTemplateInstantiations.size());
 343   if ((SemaRef.ActiveTemplateInstantiations.size() -
 344           SemaRef.NonInstantiationEntries)
 345         <= SemaRef.getLangOptions().InstantiationDepth)
 346     return false;
 347
 348   SemaRef.Diag(PointOfInstantiation,
 349                diag::err_template_recursion_depth_exceeded)
 350     << SemaRef.getLangOptions().InstantiationDepth
 351     << InstantiationRange;
 352   SemaRef.Diag(PointOfInstantiation, diag::note_template_recursion_depth)
 353     << SemaRef.getLangOptions().InstantiationDepth;
 354   return true;
 355 }
 356
 357 /// \brief Prints the current instantiation stack through a series of
 358 /// notes.
 359 void Sema::PrintInstantiationStack() {
 360   // Determine which template instantiations to skip, if any.
 361   unsigned SkipStart = ActiveTemplateInstantiations.size(), SkipEnd = SkipStart;
 362   unsigned Limit = Diags.getTemplateBacktraceLimit();
 363   if (Limit && Limit < ActiveTemplateInstantiations.size()) {
 364     SkipStart = Limit / 2 + Limit % 2;
 365     SkipEnd = ActiveTemplateInstantiations.size() - Limit / 2;
 366   }
 367
 368   // FIXME: In all of these cases, we need to show the template arguments
 369   unsigned InstantiationIdx = 0;
 370   for (llvm::SmallVector<ActiveTemplateInstantiation, 16>::reverse_iterator
 371          Active = ActiveTemplateInstantiations.rbegin(),
 372          ActiveEnd = ActiveTemplateInstantiations.rend();
 373        Active != ActiveEnd;
 374        ++Active, ++InstantiationIdx) {
 375     // Skip this instantiation?
 376     if (InstantiationIdx >= SkipStart && InstantiationIdx < SkipEnd) {
 377       if (InstantiationIdx == SkipStart) {
 378         // Note that we're skipping instantiations.
 379         Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
 380                      diag::note_instantiation_contexts_suppressed)
 381           << unsigned(ActiveTemplateInstantiations.size() - Limit);
 382       }
 383       continue;
 384     }
 385
 386     switch (Active->Kind) {
 387     case ActiveTemplateInstantiation::TemplateInstantiation: {
 388       Decl *D = reinterpret_cast<Decl *>(Active->Entity);
 389       if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(D)) {
 390         unsigned DiagID = diag::note_template_member_class_here;
 391         if (isa<ClassTemplateSpecializationDecl>(Record))
 392           DiagID = diag::note_template_class_instantiation_here;
 393         Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
 394                      DiagID)
 395           << Context.getTypeDeclType(Record)
 396           << Active->InstantiationRange;
 397       } else if (FunctionDecl *Function = dyn_cast<FunctionDecl>(D)) {
 398         unsigned DiagID;
 399         if (Function->getPrimaryTemplate())
 400           DiagID = diag::note_function_template_spec_here;
 401         else
 402           DiagID = diag::note_template_member_function_here;
 403         Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
 404                      DiagID)
 405           << Function
 406           << Active->InstantiationRange;
 407       } else {
 408         Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
 409                      diag::note_template_static_data_member_def_here)
 410           << cast<VarDecl>(D)
 411           << Active->InstantiationRange;
 412       }
 413       break;
 414     }
 415
 416     case ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation: {
 417       TemplateDecl *Template = cast<TemplateDecl>((Decl *)Active->Entity);
 418       std::string TemplateArgsStr
 419         = TemplateSpecializationType::PrintTemplateArgumentList(
 420                                                          Active->TemplateArgs,
 421                                                       Active->NumTemplateArgs,
 422                                                       Context.PrintingPolicy);
 423       Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
 424                    diag::note_default_arg_instantiation_here)
 425         << (Template->getNameAsString() + TemplateArgsStr)
 426         << Active->InstantiationRange;
 427       break;
 428     }
 429
 430     case ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution: {
 431       FunctionTemplateDecl *FnTmpl
 432         = cast<FunctionTemplateDecl>((Decl *)Active->Entity);
 433       Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
 434                    diag::note_explicit_template_arg_substitution_here)
 435         << FnTmpl
 436         << getTemplateArgumentBindingsText(FnTmpl->getTemplateParameters(),
 437                                            Active->TemplateArgs,
 438                                            Active->NumTemplateArgs)
 439         << Active->InstantiationRange;
 440       break;
 441     }
 442
 443     case ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution:
 444       if (ClassTemplatePartialSpecializationDecl *PartialSpec
 445             = dyn_cast<ClassTemplatePartialSpecializationDecl>(
 446                                                     (Decl *)Active->Entity)) {
 447         Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
 448                      diag::note_partial_spec_deduct_instantiation_here)
 449           << Context.getTypeDeclType(PartialSpec)
 450           << getTemplateArgumentBindingsText(
 451                                          PartialSpec->getTemplateParameters(),
 452                                              Active->TemplateArgs,
 453                                              Active->NumTemplateArgs)
 454           << Active->InstantiationRange;
 455       } else {
 456         FunctionTemplateDecl *FnTmpl
 457           = cast<FunctionTemplateDecl>((Decl *)Active->Entity);
 458         Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
 459                      diag::note_function_template_deduction_instantiation_here)
 460           << FnTmpl
 461           << getTemplateArgumentBindingsText(FnTmpl->getTemplateParameters(),
 462                                              Active->TemplateArgs,
 463                                              Active->NumTemplateArgs)
 464           << Active->InstantiationRange;
 465       }
 466       break;
 467
 468     case ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation: {
 469       ParmVarDecl *Param = cast<ParmVarDecl>((Decl *)Active->Entity);
 470       FunctionDecl *FD = cast<FunctionDecl>(Param->getDeclContext());
 471
 472       std::string TemplateArgsStr
 473         = TemplateSpecializationType::PrintTemplateArgumentList(
 474                                                          Active->TemplateArgs,
 475                                                       Active->NumTemplateArgs,
 476                                                       Context.PrintingPolicy);
 477       Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
 478                    diag::note_default_function_arg_instantiation_here)
 479         << (FD->getNameAsString() + TemplateArgsStr)
 480         << Active->InstantiationRange;
 481       break;
 482     }
 483
 484     case ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution: {
 485       NamedDecl *Parm = cast<NamedDecl>((Decl *)Active->Entity);
 486       std::string Name;
 487       if (!Parm->getName().empty())
 488         Name = std::string(" '") + Parm->getName().str() + "'";
 489
 490       Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
 491                    diag::note_prior_template_arg_substitution)
 492         << isa<TemplateTemplateParmDecl>(Parm)
 493         << Name
 494         << getTemplateArgumentBindingsText(
 495                                     Active->Template->getTemplateParameters(),
 496                                            Active->TemplateArgs,
 497                                            Active->NumTemplateArgs)
 498         << Active->InstantiationRange;
 499       break;
 500     }
 501
 502     case ActiveTemplateInstantiation::DefaultTemplateArgumentChecking: {
 503       Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
 504                    diag::note_template_default_arg_checking)
 505         << getTemplateArgumentBindingsText(
 506                                      Active->Template->getTemplateParameters(),
 507                                            Active->TemplateArgs,
 508                                            Active->NumTemplateArgs)
 509         << Active->InstantiationRange;
 510       break;
 511     }
 512     }
 513   }
 514 }
 515
 516 bool Sema::isSFINAEContext() const {
 517   using llvm::SmallVector;
 518   for (SmallVector<ActiveTemplateInstantiation, 16>::const_reverse_iterator
 519          Active = ActiveTemplateInstantiations.rbegin(),
 520          ActiveEnd = ActiveTemplateInstantiations.rend();
 521        Active != ActiveEnd;
 522        ++Active)
 523   {
 524     switch(Active->Kind) {
 525     case ActiveTemplateInstantiation::TemplateInstantiation:
 526     case ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation:
 527       // This is a template instantiation, so there is no SFINAE.
 528       return false;
 529
 530     case ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation:
 531     case ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution:
 532     case ActiveTemplateInstantiation::DefaultTemplateArgumentChecking:
 533       // A default template argument instantiation and substitution into
 534       // template parameters with arguments for prior parameters may or may
 535       // not be a SFINAE context; look further up the stack.
 536       break;
 537
 538     case ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution:
 539     case ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution:
 540       // We're either substitution explicitly-specified template arguments
 541       // or deduced template arguments, so SFINAE applies.
 542       return true;
 543     }
 544   }
 545
 546   return false;
 547 }
 548
 549 //===----------------------------------------------------------------------===/
 550 // Template Instantiation for Types
 551 //===----------------------------------------------------------------------===/
 552 namespace {
 553   class TemplateInstantiator : public TreeTransform<TemplateInstantiator> {
 554     const MultiLevelTemplateArgumentList &TemplateArgs;
 555     SourceLocation Loc;
 556     DeclarationName Entity;
 557
 558   public:
 559     typedef TreeTransform<TemplateInstantiator> inherited;
 560
 561     TemplateInstantiator(Sema &SemaRef,
 562                          const MultiLevelTemplateArgumentList &TemplateArgs,
 563                          SourceLocation Loc,
 564                          DeclarationName Entity)
 565       : inherited(SemaRef), TemplateArgs(TemplateArgs), Loc(Loc),
 566         Entity(Entity) { }
 567
 568     /// \brief Determine whether the given type \p T has already been
 569     /// transformed.
 570     ///
 571     /// For the purposes of template instantiation, a type has already been
 572     /// transformed if it is NULL or if it is not dependent.
 573     bool AlreadyTransformed(QualType T);
 574
 575     /// \brief Returns the location of the entity being instantiated, if known.
 576     SourceLocation getBaseLocation() { return Loc; }
 577
 578     /// \brief Returns the name of the entity being instantiated, if any.
 579     DeclarationName getBaseEntity() { return Entity; }
 580
 581     /// \brief Sets the "base" location and entity when that
 582     /// information is known based on another transformation.
 583     void setBase(SourceLocation Loc, DeclarationName Entity) {
 584       this->Loc = Loc;
 585       this->Entity = Entity;
 586     }
 587
 588     /// \brief Transform the given declaration by instantiating a reference to
 589     /// this declaration.
 590     Decl *TransformDecl(SourceLocation Loc, Decl *D);
 591
 592     /// \brief Transform the definition of the given declaration by
 593     /// instantiating it.
 594     Decl *TransformDefinition(SourceLocation Loc, Decl *D);
 595
 596     /// \bried Transform the first qualifier within a scope by instantiating the
 597     /// declaration.
 598     NamedDecl *TransformFirstQualifierInScope(NamedDecl *D, SourceLocation Loc);
 599
 600     /// \brief Rebuild the exception declaration and register the declaration
 601     /// as an instantiated local.
 602     VarDecl *RebuildExceptionDecl(VarDecl *ExceptionDecl, QualType T,
 603                                   TypeSourceInfo *Declarator,
 604                                   IdentifierInfo *Name,
 605                                   SourceLocation Loc, SourceRange TypeRange);
 606
 607     /// \brief Rebuild the Objective-C exception declaration and register the
 608     /// declaration as an instantiated local.
 609     VarDecl *RebuildObjCExceptionDecl(VarDecl *ExceptionDecl,
 610                                       TypeSourceInfo *TSInfo, QualType T);
 611
 612     /// \brief Check for tag mismatches when instantiating an
 613     /// elaborated type.
 614     QualType RebuildElaboratedType(ElaboratedTypeKeyword Keyword,
 615                                    NestedNameSpecifier *NNS, QualType T);
 616
 617     Sema::OwningExprResult TransformPredefinedExpr(PredefinedExpr *E);
 618     Sema::OwningExprResult TransformDeclRefExpr(DeclRefExpr *E);
 619     Sema::OwningExprResult TransformCXXDefaultArgExpr(CXXDefaultArgExpr *E);
 620     Sema::OwningExprResult TransformTemplateParmRefExpr(DeclRefExpr *E,
 621                                                 NonTypeTemplateParmDecl *D);
 622
 623     QualType TransformFunctionProtoType(TypeLocBuilder &TLB,
 624                                         FunctionProtoTypeLoc TL,
 625                                         QualType ObjectType);
 626     ParmVarDecl *TransformFunctionTypeParam(ParmVarDecl *OldParm);
 627
 628     /// \brief Transforms a template type parameter type by performing
 629     /// substitution of the corresponding template type argument.
 630     QualType TransformTemplateTypeParmType(TypeLocBuilder &TLB,
 631                                            TemplateTypeParmTypeLoc TL,
 632                                            QualType ObjectType);
 633
 634     Sema::OwningExprResult TransformCallExpr(CallExpr *CE) {
 635       getSema().CallsUndergoingInstantiation.push_back(CE);
 636       OwningExprResult Result =
 637           TreeTransform<TemplateInstantiator>::TransformCallExpr(CE);
 638       getSema().CallsUndergoingInstantiation.pop_back();
 639       return move(Result);
 640     }
 641   };
 642 }
 643
 644 bool TemplateInstantiator::AlreadyTransformed(QualType T) {
 645   if (T.isNull())
 646     return true;
 647
 648   if (T->isDependentType() || T->isVariablyModifiedType())
 649     return false;
 650
 651   getSema().MarkDeclarationsReferencedInType(Loc, T);
 652   return true;
 653 }
 654
 655 Decl *TemplateInstantiator::TransformDecl(SourceLocation Loc, Decl *D) {
 656   if (!D)
 657     return 0;
 658
 659   if (TemplateTemplateParmDecl *TTP = dyn_cast<TemplateTemplateParmDecl>(D)) {
 660     if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
 661       // If the corresponding template argument is NULL or non-existent, it's
 662       // because we are performing instantiation from explicitly-specified
 663       // template arguments in a function template, but there were some
 664       // arguments left unspecified.
 665       if (!TemplateArgs.hasTemplateArgument(TTP->getDepth(),
 666                                             TTP->getPosition()))
 667         return D;
 668
 669       TemplateName Template
 670         = TemplateArgs(TTP->getDepth(), TTP->getPosition()).getAsTemplate();
 671       assert(!Template.isNull() && Template.getAsTemplateDecl() &&
 672              "Wrong kind of template template argument");
 673       return Template.getAsTemplateDecl();
 674     }
 675
 676     // Fall through to find the instantiated declaration for this template
 677     // template parameter.
 678   }
 679
 680   return SemaRef.FindInstantiatedDecl(Loc, cast<NamedDecl>(D), TemplateArgs);
 681 }
 682
 683 Decl *TemplateInstantiator::TransformDefinition(SourceLocation Loc, Decl *D) {
 684   Decl *Inst = getSema().SubstDecl(D, getSema().CurContext, TemplateArgs);
 685   if (!Inst)
 686     return 0;
 687
 688   getSema().CurrentInstantiationScope->InstantiatedLocal(D, Inst);
 689   return Inst;
 690 }
 691
 692 NamedDecl *
 693 TemplateInstantiator::TransformFirstQualifierInScope(NamedDecl *D,
 694                                                      SourceLocation Loc) {
 695   // If the first part of the nested-name-specifier was a template type
 696   // parameter, instantiate that type parameter down to a tag type.
 697   if (TemplateTypeParmDecl *TTPD = dyn_cast_or_null<TemplateTypeParmDecl>(D)) {
 698     const TemplateTypeParmType *TTP
 699       = cast<TemplateTypeParmType>(getSema().Context.getTypeDeclType(TTPD));
 700     if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
 701       QualType T = TemplateArgs(TTP->getDepth(), TTP->getIndex()).getAsType();
 702       if (T.isNull())
 703         return cast_or_null<NamedDecl>(TransformDecl(Loc, D));
 704
 705       if (const TagType *Tag = T->getAs<TagType>())
 706         return Tag->getDecl();
 707
 708       // The resulting type is not a tag; complain.
 709       getSema().Diag(Loc, diag::err_nested_name_spec_non_tag) << T;
 710       return 0;
 711     }
 712   }
 713
 714   return cast_or_null<NamedDecl>(TransformDecl(Loc, D));
 715 }
 716
 717 VarDecl *
 718 TemplateInstantiator::RebuildExceptionDecl(VarDecl *ExceptionDecl,
 719                                            QualType T,
 720                                            TypeSourceInfo *Declarator,
 721                                            IdentifierInfo *Name,
 722                                            SourceLocation Loc,
 723                                            SourceRange TypeRange) {
 724   VarDecl *Var = inherited::RebuildExceptionDecl(ExceptionDecl, T, Declarator,
 725                                                  Name, Loc, TypeRange);
 726   if (Var)
 727     getSema().CurrentInstantiationScope->InstantiatedLocal(ExceptionDecl, Var);
 728   return Var;
 729 }
 730
 731 VarDecl *TemplateInstantiator::RebuildObjCExceptionDecl(VarDecl *ExceptionDecl,
 732                                                         TypeSourceInfo *TSInfo,
 733                                                         QualType T) {
 734   VarDecl *Var = inherited::RebuildObjCExceptionDecl(ExceptionDecl, TSInfo, T);
 735   if (Var)
 736     getSema().CurrentInstantiationScope->InstantiatedLocal(ExceptionDecl, Var);
 737   return Var;
 738 }
 739
 740 QualType
 741 TemplateInstantiator::RebuildElaboratedType(ElaboratedTypeKeyword Keyword,
 742                                             NestedNameSpecifier *NNS,
 743                                             QualType T) {
 744   if (const TagType *TT = T->getAs<TagType>()) {
 745     TagDecl* TD = TT->getDecl();
 746
 747     // FIXME: this location is very wrong;  we really need typelocs.
 748     SourceLocation TagLocation = TD->getTagKeywordLoc();
 749
 750     // FIXME: type might be anonymous.
 751     IdentifierInfo *Id = TD->getIdentifier();
 752
 753     // TODO: should we even warn on struct/class mismatches for this?  Seems
 754     // like it's likely to produce a lot of spurious errors.
 755     if (Keyword != ETK_None && Keyword != ETK_Typename) {
 756       TagTypeKind Kind = TypeWithKeyword::getTagTypeKindForKeyword(Keyword);
 757       if (!SemaRef.isAcceptableTagRedeclaration(TD, Kind, TagLocation, *Id)) {
 758         SemaRef.Diag(TagLocation, diag::err_use_with_wrong_tag)
 759           << Id
 760           << FixItHint::CreateReplacement(SourceRange(TagLocation),
 761                                           TD->getKindName());
 762         SemaRef.Diag(TD->getLocation(), diag::note_previous_use);
 763       }
 764     }
 765   }
 766
 767   return TreeTransform<TemplateInstantiator>::RebuildElaboratedType(Keyword,
 768                                                                     NNS, T);
 769 }
 770
 771 Sema::OwningExprResult
 772 TemplateInstantiator::TransformPredefinedExpr(PredefinedExpr *E) {
 773   if (!E->isTypeDependent())
 774     return SemaRef.Owned(E->Retain());
 775
 776   FunctionDecl *currentDecl = getSema().getCurFunctionDecl();
 777   assert(currentDecl && "Must have current function declaration when "
 778                         "instantiating.");
 779
 780   PredefinedExpr::IdentType IT = E->getIdentType();
 781
 782   unsigned Length = PredefinedExpr::ComputeName(IT, currentDecl).length();
 783
 784   llvm::APInt LengthI(32, Length + 1);
 785   QualType ResTy = getSema().Context.CharTy.withConst();
 786   ResTy = getSema().Context.getConstantArrayType(ResTy, LengthI,
 787                                                  ArrayType::Normal, 0);
 788   PredefinedExpr *PE =
 789     new (getSema().Context) PredefinedExpr(E->getLocation(), ResTy, IT);
 790   return getSema().Owned(PE);
 791 }
 792
 793 Sema::OwningExprResult
 794 TemplateInstantiator::TransformTemplateParmRefExpr(DeclRefExpr *E,
 795                                                NonTypeTemplateParmDecl *NTTP) {
 796   // If the corresponding template argument is NULL or non-existent, it's
 797   // because we are performing instantiation from explicitly-specified
 798   // template arguments in a function template, but there were some
 799   // arguments left unspecified.
 800   if (!TemplateArgs.hasTemplateArgument(NTTP->getDepth(),
 801                                         NTTP->getPosition()))
 802     return SemaRef.Owned(E->Retain());
 803
 804   const TemplateArgument &Arg = TemplateArgs(NTTP->getDepth(),
 805                                              NTTP->getPosition());
 806
 807   // The template argument itself might be an expression, in which
 808   // case we just return that expression.
 809   if (Arg.getKind() == TemplateArgument::Expression)
 810     return SemaRef.Owned(Arg.getAsExpr()->Retain());
 811
 812   if (Arg.getKind() == TemplateArgument::Declaration) {
 813     ValueDecl *VD = cast<ValueDecl>(Arg.getAsDecl());
 814
 815     // Find the instantiation of the template argument.  This is
 816     // required for nested templates.
 817     VD = cast_or_null<ValueDecl>(
 818                             getSema().FindInstantiatedDecl(E->getLocation(),
 819                                                            VD, TemplateArgs));
 820     if (!VD)
 821       return SemaRef.ExprError();
 822
 823     // Derive the type we want the substituted decl to have.  This had
 824     // better be non-dependent, or these checks will have serious problems.
 825     QualType TargetType = SemaRef.SubstType(NTTP->getType(), TemplateArgs,
 826                                             E->getLocation(),
 827                                             DeclarationName());
 828     assert(!TargetType.isNull() && "type substitution failed for param type");
 829     assert(!TargetType->isDependentType() && "param type still dependent");
 830     return SemaRef.BuildExpressionFromDeclTemplateArgument(Arg,
 831                                                            TargetType,
 832                                                            E->getLocation());
 833   }
 834
 835   return SemaRef.BuildExpressionFromIntegralTemplateArgument(Arg,
 836                                                 E->getSourceRange().getBegin());
 837 }
 838
 839
 840 Sema::OwningExprResult
 841 TemplateInstantiator::TransformDeclRefExpr(DeclRefExpr *E) {
 842   NamedDecl *D = E->getDecl();
 843   if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D)) {
 844     if (NTTP->getDepth() < TemplateArgs.getNumLevels())
 845       return TransformTemplateParmRefExpr(E, NTTP);
 846
 847     // We have a non-type template parameter that isn't fully substituted;
 848     // FindInstantiatedDecl will find it in the local instantiation scope.
 849   }
 850
 851   return TreeTransform<TemplateInstantiator>::TransformDeclRefExpr(E);
 852 }
 853
 854 Sema::OwningExprResult TemplateInstantiator::TransformCXXDefaultArgExpr(
 855     CXXDefaultArgExpr *E) {
 856   assert(!cast<FunctionDecl>(E->getParam()->getDeclContext())->
 857              getDescribedFunctionTemplate() &&
 858          "Default arg expressions are never formed in dependent cases.");
 859   return SemaRef.BuildCXXDefaultArgExpr(E->getUsedLocation(),
 860                            cast<FunctionDecl>(E->getParam()->getDeclContext()),
 861                                         E->getParam());
 862 }
 863
 864 QualType TemplateInstantiator::TransformFunctionProtoType(TypeLocBuilder &TLB,
 865                                                         FunctionProtoTypeLoc TL,
 866                                                           QualType ObjectType) {
 867   // We need a local instantiation scope for this function prototype.
 868   Sema::LocalInstantiationScope Scope(SemaRef, /*CombineWithOuterScope=*/true);
 869   return inherited::TransformFunctionProtoType(TLB, TL, ObjectType);
 870 }
 871
 872 ParmVarDecl *
 873 TemplateInstantiator::TransformFunctionTypeParam(ParmVarDecl *OldParm) {
 874   return SemaRef.SubstParmVarDecl(OldParm, TemplateArgs);
 875 }
 876
 877 QualType
 878 TemplateInstantiator::TransformTemplateTypeParmType(TypeLocBuilder &TLB,
 879                                                 TemplateTypeParmTypeLoc TL,
 880                                                     QualType ObjectType) {
 881   TemplateTypeParmType *T = TL.getTypePtr();
 882   if (T->getDepth() < TemplateArgs.getNumLevels()) {
 883     // Replace the template type parameter with its corresponding
 884     // template argument.
 885
 886     // If the corresponding template argument is NULL or doesn't exist, it's
 887     // because we are performing instantiation from explicitly-specified
 888     // template arguments in a function template class, but there were some
 889     // arguments left unspecified.
 890     if (!TemplateArgs.hasTemplateArgument(T->getDepth(), T->getIndex())) {
 891       TemplateTypeParmTypeLoc NewTL
 892         = TLB.push<TemplateTypeParmTypeLoc>(TL.getType());
 893       NewTL.setNameLoc(TL.getNameLoc());
 894       return TL.getType();
 895     }
 896
 897     assert(TemplateArgs(T->getDepth(), T->getIndex()).getKind()
 898              == TemplateArgument::Type &&
 899            "Template argument kind mismatch");
 900
 901     QualType Replacement
 902       = TemplateArgs(T->getDepth(), T->getIndex()).getAsType();
 903
 904     // TODO: only do this uniquing once, at the start of instantiation.
 905     QualType Result
 906       = getSema().Context.getSubstTemplateTypeParmType(T, Replacement);
 907     SubstTemplateTypeParmTypeLoc NewTL
 908       = TLB.push<SubstTemplateTypeParmTypeLoc>(Result);
 909     NewTL.setNameLoc(TL.getNameLoc());
 910     return Result;
 911   }
 912
 913   // The template type parameter comes from an inner template (e.g.,
 914   // the template parameter list of a member template inside the
 915   // template we are instantiating). Create a new template type
 916   // parameter with the template "level" reduced by one.
 917   QualType Result
 918     = getSema().Context.getTemplateTypeParmType(T->getDepth()
 919                                                  - TemplateArgs.getNumLevels(),
 920                                                 T->getIndex(),
 921                                                 T->isParameterPack(),
 922                                                 T->getName());
 923   TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result);
 924   NewTL.setNameLoc(TL.getNameLoc());
 925   return Result;
 926 }
 927
 928 /// \brief Perform substitution on the type T with a given set of template
 929 /// arguments.
 930 ///
 931 /// This routine substitutes the given template arguments into the
 932 /// type T and produces the instantiated type.
 933 ///
 934 /// \param T the type into which the template arguments will be
 935 /// substituted. If this type is not dependent, it will be returned
 936 /// immediately.
 937 ///
 938 /// \param TemplateArgs the template arguments that will be
 939 /// substituted for the top-level template parameters within T.
 940 ///
 941 /// \param Loc the location in the source code where this substitution
 942 /// is being performed. It will typically be the location of the
 943 /// declarator (if we're instantiating the type of some declaration)
 944 /// or the location of the type in the source code (if, e.g., we're
 945 /// instantiating the type of a cast expression).
 946 ///
 947 /// \param Entity the name of the entity associated with a declaration
 948 /// being instantiated (if any). May be empty to indicate that there
 949 /// is no such entity (if, e.g., this is a type that occurs as part of
 950 /// a cast expression) or that the entity has no name (e.g., an
 951 /// unnamed function parameter).
 952 ///
 953 /// \returns If the instantiation succeeds, the instantiated
 954 /// type. Otherwise, produces diagnostics and returns a NULL type.
 955 TypeSourceInfo *Sema::SubstType(TypeSourceInfo *T,
 956                                 const MultiLevelTemplateArgumentList &Args,
 957                                 SourceLocation Loc,
 958                                 DeclarationName Entity) {
 959   assert(!ActiveTemplateInstantiations.empty() &&
 960          "Cannot perform an instantiation without some context on the "
 961          "instantiation stack");
 962
 963   if (!T->getType()->isDependentType() &&
 964       !T->getType()->isVariablyModifiedType())
 965     return T;
 966
 967   TemplateInstantiator Instantiator(*this, Args, Loc, Entity);
 968   return Instantiator.TransformType(T);
 969 }
 970
 971 /// Deprecated form of the above.
 972 QualType Sema::SubstType(QualType T,
 973                          const MultiLevelTemplateArgumentList &TemplateArgs,
 974                          SourceLocation Loc, DeclarationName Entity) {
 975   assert(!ActiveTemplateInstantiations.empty() &&
 976          "Cannot perform an instantiation without some context on the "
 977          "instantiation stack");
 978
 979   // If T is not a dependent type or a variably-modified type, there
 980   // is nothing to do.
 981   if (!T->isDependentType() && !T->isVariablyModifiedType())
 982     return T;
 983
 984   TemplateInstantiator Instantiator(*this, TemplateArgs, Loc, Entity);
 985   return Instantiator.TransformType(T);
 986 }
 987
 988 static bool NeedsInstantiationAsFunctionType(TypeSourceInfo *T) {
 989   if (T->getType()->isDependentType() || T->getType()->isVariablyModifiedType())
 990     return true;
 991
 992   TypeLoc TL = T->getTypeLoc();
 993   if (!isa<FunctionProtoTypeLoc>(TL))
 994     return false;
 995
 996   FunctionProtoTypeLoc FP = cast<FunctionProtoTypeLoc>(TL);
 997   for (unsigned I = 0, E = FP.getNumArgs(); I != E; ++I) {
 998     ParmVarDecl *P = FP.getArg(I);
 999
1000     // TODO: currently we always rebuild expressions.  When we
1001     // properly get lazier about this, we should use the same
1002     // logic to avoid rebuilding prototypes here.
1003     if (P->hasInit())
1004       return true;
1005   }
1006
1007   return false;
1008 }
1009
1010 /// A form of SubstType intended specifically for instantiating the
1011 /// type of a FunctionDecl.  Its purpose is solely to force the
1012 /// instantiation of default-argument expressions.
1013 TypeSourceInfo *Sema::SubstFunctionDeclType(TypeSourceInfo *T,
1014                                 const MultiLevelTemplateArgumentList &Args,
1015                                 SourceLocation Loc,
1016                                 DeclarationName Entity) {
1017   assert(!ActiveTemplateInstantiations.empty() &&
1018          "Cannot perform an instantiation without some context on the "
1019          "instantiation stack");
1020
1021   if (!NeedsInstantiationAsFunctionType(T))
1022     return T;
1023
1024   TemplateInstantiator Instantiator(*this, Args, Loc, Entity);
1025
1026   TypeLocBuilder TLB;
1027
1028   TypeLoc TL = T->getTypeLoc();
1029   TLB.reserve(TL.getFullDataSize());
1030
1031   QualType Result = Instantiator.TransformType(TLB, TL, QualType());
1032   if (Result.isNull())
1033     return 0;
1034
1035   return TLB.getTypeSourceInfo(Context, Result);
1036 }
1037
1038 ParmVarDecl *Sema::SubstParmVarDecl(ParmVarDecl *OldParm,
1039                           const MultiLevelTemplateArgumentList &TemplateArgs) {
1040   TypeSourceInfo *OldDI = OldParm->getTypeSourceInfo();
1041   TypeSourceInfo *NewDI = SubstType(OldDI, TemplateArgs, OldParm->getLocation(),
1042                                     OldParm->getDeclName());
1043   if (!NewDI)
1044     return 0;
1045
1046   if (NewDI->getType()->isVoidType()) {
1047     Diag(OldParm->getLocation(), diag::err_param_with_void_type);
1048     return 0;
1049   }
1050
1051   ParmVarDecl *NewParm = CheckParameter(Context.getTranslationUnitDecl(),
1052                                         NewDI, NewDI->getType(),
1053                                         OldParm->getIdentifier(),
1054                                         OldParm->getLocation(),
1055                                         OldParm->getStorageClass(),
1056                                         OldParm->getStorageClassAsWritten());
1057   if (!NewParm)
1058     return 0;
1059
1060   // Mark the (new) default argument as uninstantiated (if any).
1061   if (OldParm->hasUninstantiatedDefaultArg()) {
1062     Expr *Arg = OldParm->getUninstantiatedDefaultArg();
1063     NewParm->setUninstantiatedDefaultArg(Arg);
1064   } else if (Expr *Arg = OldParm->getDefaultArg())
1065     NewParm->setUninstantiatedDefaultArg(Arg);
1066
1067   NewParm->setHasInheritedDefaultArg(OldParm->hasInheritedDefaultArg());
1068
1069   CurrentInstantiationScope->InstantiatedLocal(OldParm, NewParm);
1070   return NewParm;
1071 }
1072
1073 /// \brief Perform substitution on the base class specifiers of the
1074 /// given class template specialization.
1075 ///
1076 /// Produces a diagnostic and returns true on error, returns false and
1077 /// attaches the instantiated base classes to the class template
1078 /// specialization if successful.
1079 bool
1080 Sema::SubstBaseSpecifiers(CXXRecordDecl *Instantiation,
1081                           CXXRecordDecl *Pattern,
1082                           const MultiLevelTemplateArgumentList &TemplateArgs) {
1083   bool Invalid = false;
1084   llvm::SmallVector<CXXBaseSpecifier*, 4> InstantiatedBases;
1085   for (ClassTemplateSpecializationDecl::base_class_iterator
1086          Base = Pattern->bases_begin(), BaseEnd = Pattern->bases_end();
1087        Base != BaseEnd; ++Base) {
1088     if (!Base->getType()->isDependentType()) {
1089       const CXXRecordDecl *BaseDecl =
1090         cast<CXXRecordDecl>(Base->getType()->getAs<RecordType>()->getDecl());
1091
1092       // Make sure to set the attributes from the base.
1093       SetClassDeclAttributesFromBase(Instantiation, BaseDecl,
1094                                      Base->isVirtual());
1095
1096       InstantiatedBases.push_back(new (Context) CXXBaseSpecifier(*Base));
1097       continue;
1098     }
1099
1100     QualType BaseType = SubstType(Base->getType(),
1101                                   TemplateArgs,
1102                                   Base->getSourceRange().getBegin(),
1103                                   DeclarationName());
1104     if (BaseType.isNull()) {
1105       Invalid = true;
1106       continue;
1107     }
1108
1109     if (CXXBaseSpecifier *InstantiatedBase
1110           = CheckBaseSpecifier(Instantiation,
1111                                Base->getSourceRange(),
1112                                Base->isVirtual(),
1113                                Base->getAccessSpecifierAsWritten(),
1114                                BaseType,
1115                                /*FIXME: Not totally accurate */
1116                                Base->getSourceRange().getBegin()))
1117       InstantiatedBases.push_back(InstantiatedBase);
1118     else
1119       Invalid = true;
1120   }
1121
1122   if (!Invalid &&
1123       AttachBaseSpecifiers(Instantiation, InstantiatedBases.data(),
1124                            InstantiatedBases.size()))
1125     Invalid = true;
1126
1127   return Invalid;
1128 }
1129
1130 /// \brief Instantiate the definition of a class from a given pattern.
1131 ///
1132 /// \param PointOfInstantiation The point of instantiation within the
1133 /// source code.
1134 ///
1135 /// \param Instantiation is the declaration whose definition is being
1136 /// instantiated. This will be either a class template specialization
1137 /// or a member class of a class template specialization.
1138 ///
1139 /// \param Pattern is the pattern from which the instantiation
1140 /// occurs. This will be either the declaration of a class template or
1141 /// the declaration of a member class of a class template.
1142 ///
1143 /// \param TemplateArgs The template arguments to be substituted into
1144 /// the pattern.
1145 ///
1146 /// \param TSK the kind of implicit or explicit instantiation to perform.
1147 ///
1148 /// \param Complain whether to complain if the class cannot be instantiated due
1149 /// to the lack of a definition.
1150 ///
1151 /// \returns true if an error occurred, false otherwise.
1152 bool
1153 Sema::InstantiateClass(SourceLocation PointOfInstantiation,
1154                        CXXRecordDecl *Instantiation, CXXRecordDecl *Pattern,
1155                        const MultiLevelTemplateArgumentList &TemplateArgs,
1156                        TemplateSpecializationKind TSK,
1157                        bool Complain) {
1158   bool Invalid = false;
1159
1160   CXXRecordDecl *PatternDef
1161     = cast_or_null<CXXRecordDecl>(Pattern->getDefinition());
1162   if (!PatternDef) {
1163     if (!Complain) {
1164       // Say nothing
1165     } else if (Pattern == Instantiation->getInstantiatedFromMemberClass()) {
1166       Diag(PointOfInstantiation,
1167            diag::err_implicit_instantiate_member_undefined)
1168         << Context.getTypeDeclType(Instantiation);
1169       Diag(Pattern->getLocation(), diag::note_member_of_template_here);
1170     } else {
1171       Diag(PointOfInstantiation, diag::err_template_instantiate_undefined)
1172         << (TSK != TSK_ImplicitInstantiation)
1173         << Context.getTypeDeclType(Instantiation);
1174       Diag(Pattern->getLocation(), diag::note_template_decl_here);
1175     }
1176     return true;
1177   }
1178   Pattern = PatternDef;
1179
1180   // \brief Record the point of instantiation.
1181   if (MemberSpecializationInfo *MSInfo
1182         = Instantiation->getMemberSpecializationInfo()) {
1183     MSInfo->setTemplateSpecializationKind(TSK);
1184     MSInfo->setPointOfInstantiation(PointOfInstantiation);
1185   } else if (ClassTemplateSpecializationDecl *Spec
1186                = dyn_cast<ClassTemplateSpecializationDecl>(Instantiation)) {
1187     Spec->setTemplateSpecializationKind(TSK);
1188     Spec->setPointOfInstantiation(PointOfInstantiation);
1189   }
1190
1191   InstantiatingTemplate Inst(*this, PointOfInstantiation, Instantiation);
1192   if (Inst)
1193     return true;
1194
1195   // Enter the scope of this instantiation. We don't use
1196   // PushDeclContext because we don't have a scope.
1197   ContextRAII SavedContext(*this, Instantiation);
1198   EnterExpressionEvaluationContext EvalContext(*this,
1199                                                Action::PotentiallyEvaluated);
1200
1201   // If this is an instantiation of a local class, merge this local
1202   // instantiation scope with the enclosing scope. Otherwise, every
1203   // instantiation of a class has its own local instantiation scope.
1204   bool MergeWithParentScope = !Instantiation->isDefinedOutsideFunctionOrMethod();
1205   Sema::LocalInstantiationScope Scope(*this, MergeWithParentScope);
1206
1207   // Start the definition of this instantiation.
1208   Instantiation->startDefinition();
1209
1210   Instantiation->setTagKind(Pattern->getTagKind());
1211
1212   // Do substitution on the base class specifiers.
1213   if (SubstBaseSpecifiers(Instantiation, Pattern, TemplateArgs))
1214     Invalid = true;
1215
1216   llvm::SmallVector<DeclPtrTy, 4> Fields;
1217   for (RecordDecl::decl_iterator Member = Pattern->decls_begin(),
1218          MemberEnd = Pattern->decls_end();
1219        Member != MemberEnd; ++Member) {
1220     Decl *NewMember = SubstDecl(*Member, Instantiation, TemplateArgs);
1221     if (NewMember) {
1222       if (FieldDecl *Field = dyn_cast<FieldDecl>(NewMember))
1223         Fields.push_back(DeclPtrTy::make(Field));
1224       else if (NewMember->isInvalidDecl())
1225         Invalid = true;
1226     } else {
1227       // FIXME: Eventually, a NULL return will mean that one of the
1228       // instantiations was a semantic disaster, and we'll want to set Invalid =
1229       // true. For now, we expect to skip some members that we can't yet handle.
1230     }
1231   }
1232
1233   // Finish checking fields.
1234   ActOnFields(0, Instantiation->getLocation(), DeclPtrTy::make(Instantiation),
1235               Fields.data(), Fields.size(), SourceLocation(), SourceLocation(),
1236               0);
1237   CheckCompletedCXXClass(Instantiation);
1238   if (Instantiation->isInvalidDecl())
1239     Invalid = true;
1240
1241   // Exit the scope of this instantiation.
1242   SavedContext.pop();
1243
1244   if (!Invalid) {
1245     Consumer.HandleTagDeclDefinition(Instantiation);
1246
1247     // Always emit the vtable for an explicit instantiation definition
1248     // of a polymorphic class template specialization.
1249     if (TSK == TSK_ExplicitInstantiationDefinition)
1250       MarkVTableUsed(PointOfInstantiation, Instantiation, true);
1251   }
1252
1253   return Invalid;
1254 }
1255
1256 bool
1257 Sema::InstantiateClassTemplateSpecialization(
1258                            SourceLocation PointOfInstantiation,
1259                            ClassTemplateSpecializationDecl *ClassTemplateSpec,
1260                            TemplateSpecializationKind TSK,
1261                            bool Complain) {
1262   // Perform the actual instantiation on the canonical declaration.
1263   ClassTemplateSpec = cast<ClassTemplateSpecializationDecl>(
1264                                          ClassTemplateSpec->getCanonicalDecl());
1265
1266   // Check whether we have already instantiated or specialized this class
1267   // template specialization.
1268   if (ClassTemplateSpec->getSpecializationKind() != TSK_Undeclared) {
1269     if (ClassTemplateSpec->getSpecializationKind() ==
1270           TSK_ExplicitInstantiationDeclaration &&
1271         TSK == TSK_ExplicitInstantiationDefinition) {
1272       // An explicit instantiation definition follows an explicit instantiation
1273       // declaration (C++0x [temp.explicit]p10); go ahead and perform the
1274       // explicit instantiation.
1275       ClassTemplateSpec->setSpecializationKind(TSK);
1276
1277       // If this is an explicit instantiation definition, mark the
1278       // vtable as used.
1279       if (TSK == TSK_ExplicitInstantiationDefinition)
1280         MarkVTableUsed(PointOfInstantiation, ClassTemplateSpec, true);
1281
1282       return false;
1283     }
1284
1285     // We can only instantiate something that hasn't already been
1286     // instantiated or specialized. Fail without any diagnostics: our
1287     // caller will provide an error message.
1288     return true;
1289   }
1290
1291   if (ClassTemplateSpec->isInvalidDecl())
1292     return true;
1293
1294   ClassTemplateDecl *Template = ClassTemplateSpec->getSpecializedTemplate();
1295   CXXRecordDecl *Pattern = 0;
1296
1297   // C++ [temp.class.spec.match]p1:
1298   //   When a class template is used in a context that requires an
1299   //   instantiation of the class, it is necessary to determine
1300   //   whether the instantiation is to be generated using the primary
1301   //   template or one of the partial specializations. This is done by
1302   //   matching the template arguments of the class template
1303   //   specialization with the template argument lists of the partial
1304   //   specializations.
1305   typedef std::pair<ClassTemplatePartialSpecializationDecl *,
1306                     TemplateArgumentList *> MatchResult;
1307   llvm::SmallVector<MatchResult, 4> Matched;
1308   llvm::SmallVector<ClassTemplatePartialSpecializationDecl *, 4> PartialSpecs;
1309   Template->getPartialSpecializations(PartialSpecs);
1310   for (unsigned I = 0, N = PartialSpecs.size(); I != N; ++I) {
1311     ClassTemplatePartialSpecializationDecl *Partial = PartialSpecs[I];
1312     TemplateDeductionInfo Info(Context, PointOfInstantiation);
1313     if (TemplateDeductionResult Result
1314           = DeduceTemplateArguments(Partial,
1315                                     ClassTemplateSpec->getTemplateArgs(),
1316                                     Info)) {
1317       // FIXME: Store the failed-deduction information for use in
1318       // diagnostics, later.
1319       (void)Result;
1320     } else {
1321       Matched.push_back(std::make_pair(Partial, Info.take()));
1322     }
1323   }
1324
1325   if (Matched.size() >= 1) {
1326     llvm::SmallVector<MatchResult, 4>::iterator Best = Matched.begin();
1327     if (Matched.size() == 1) {
1328       //   -- If exactly one matching specialization is found, the
1329       //      instantiation is generated from that specialization.
1330       // We don't need to do anything for this.
1331     } else {
1332       //   -- If more than one matching specialization is found, the
1333       //      partial order rules (14.5.4.2) are used to determine
1334       //      whether one of the specializations is more specialized
1335       //      than the others. If none of the specializations is more
1336       //      specialized than all of the other matching
1337       //      specializations, then the use of the class template is
1338       //      ambiguous and the program is ill-formed.
1339       for (llvm::SmallVector<MatchResult, 4>::iterator P = Best + 1,
1340                                                     PEnd = Matched.end();
1341            P != PEnd; ++P) {
1342         if (getMoreSpecializedPartialSpecialization(P->first, Best->first,
1343                                                     PointOfInstantiation)
1344               == P->first)
1345           Best = P;
1346       }
1347
1348       // Determine if the best partial specialization is more specialized than
1349       // the others.
1350       bool Ambiguous = false;
1351       for (llvm::SmallVector<MatchResult, 4>::iterator P = Matched.begin(),
1352                                                     PEnd = Matched.end();
1353            P != PEnd; ++P) {
1354         if (P != Best &&
1355             getMoreSpecializedPartialSpecialization(P->first, Best->first,
1356                                                     PointOfInstantiation)
1357               != Best->first) {
1358           Ambiguous = true;
1359           break;
1360         }
1361       }
1362
1363       if (Ambiguous) {
1364         // Partial ordering did not produce a clear winner. Complain.
1365         ClassTemplateSpec->setInvalidDecl();
1366         Diag(PointOfInstantiation, diag::err_partial_spec_ordering_ambiguous)
1367           << ClassTemplateSpec;
1368
1369         // Print the matching partial specializations.
1370         for (llvm::SmallVector<MatchResult, 4>::iterator P = Matched.begin(),
1371                                                       PEnd = Matched.end();
1372              P != PEnd; ++P)
1373           Diag(P->first->getLocation(), diag::note_partial_spec_match)
1374             << getTemplateArgumentBindingsText(P->first->getTemplateParameters(),
1375                                                *P->second);
1376
1377         return true;
1378       }
1379     }
1380
1381     // Instantiate using the best class template partial specialization.
1382     ClassTemplatePartialSpecializationDecl *OrigPartialSpec = Best->first;
1383     while (OrigPartialSpec->getInstantiatedFromMember()) {
1384       // If we've found an explicit specialization of this class template,
1385       // stop here and use that as the pattern.
1386       if (OrigPartialSpec->isMemberSpecialization())
1387         break;
1388
1389       OrigPartialSpec = OrigPartialSpec->getInstantiatedFromMember();
1390     }
1391
1392     Pattern = OrigPartialSpec;
1393     ClassTemplateSpec->setInstantiationOf(Best->first, Best->second);
1394   } else {
1395     //   -- If no matches are found, the instantiation is generated
1396     //      from the primary template.
1397     ClassTemplateDecl *OrigTemplate = Template;
1398     while (OrigTemplate->getInstantiatedFromMemberTemplate()) {
1399       // If we've found an explicit specialization of this class template,
1400       // stop here and use that as the pattern.
1401       if (OrigTemplate->isMemberSpecialization())
1402         break;
1403
1404       OrigTemplate = OrigTemplate->getInstantiatedFromMemberTemplate();
1405     }
1406
1407     Pattern = OrigTemplate->getTemplatedDecl();
1408   }
1409
1410   bool Result = InstantiateClass(PointOfInstantiation, ClassTemplateSpec,
1411                                  Pattern,
1412                                 getTemplateInstantiationArgs(ClassTemplateSpec),
1413                                  TSK,
1414                                  Complain);
1415
1416   for (unsigned I = 0, N = Matched.size(); I != N; ++I) {
1417     // FIXME: Implement TemplateArgumentList::Destroy!
1418     //    if (Matched[I].first != Pattern)
1419     //      Matched[I].second->Destroy(Context);
1420   }
1421
1422   return Result;
1423 }
1424
1425 /// \brief Instantiates the definitions of all of the member
1426 /// of the given class, which is an instantiation of a class template
1427 /// or a member class of a template.
1428 void
1429 Sema::InstantiateClassMembers(SourceLocation PointOfInstantiation,
1430                               CXXRecordDecl *Instantiation,
1431                         const MultiLevelTemplateArgumentList &TemplateArgs,
1432                               TemplateSpecializationKind TSK) {
1433   for (DeclContext::decl_iterator D = Instantiation->decls_begin(),
1434                                DEnd = Instantiation->decls_end();
1435        D != DEnd; ++D) {
1436     bool SuppressNew = false;
1437     if (FunctionDecl *Function = dyn_cast<FunctionDecl>(*D)) {
1438       if (FunctionDecl *Pattern
1439             = Function->getInstantiatedFromMemberFunction()) {
1440         MemberSpecializationInfo *MSInfo
1441           = Function->getMemberSpecializationInfo();
1442         assert(MSInfo && "No member specialization information?");
1443         if (MSInfo->getTemplateSpecializationKind()
1444                                                  == TSK_ExplicitSpecialization)
1445           continue;
1446
1447         if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
1448                                                    Function,
1449                                         MSInfo->getTemplateSpecializationKind(),
1450                                               MSInfo->getPointOfInstantiation(),
1451                                                    SuppressNew) ||
1452             SuppressNew)
1453           continue;
1454
1455         if (Function->hasBody())
1456           continue;
1457
1458         if (TSK == TSK_ExplicitInstantiationDefinition) {
1459           // C++0x [temp.explicit]p8:
1460           //   An explicit instantiation definition that names a class template
1461           //   specialization explicitly instantiates the class template
1462           //   specialization and is only an explicit instantiation definition
1463           //   of members whose definition is visible at the point of
1464           //   instantiation.
1465           if (!Pattern->hasBody())
1466             continue;
1467
1468           Function->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1469
1470           InstantiateFunctionDefinition(PointOfInstantiation, Function);
1471         } else {
1472           Function->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1473         }
1474       }
1475     } else if (VarDecl *Var = dyn_cast<VarDecl>(*D)) {
1476       if (Var->isStaticDataMember()) {
1477         MemberSpecializationInfo *MSInfo = Var->getMemberSpecializationInfo();
1478         assert(MSInfo && "No member specialization information?");
1479         if (MSInfo->getTemplateSpecializationKind()
1480                                                  == TSK_ExplicitSpecialization)
1481           continue;
1482
1483         if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
1484                                                    Var,
1485                                         MSInfo->getTemplateSpecializationKind(),
1486                                               MSInfo->getPointOfInstantiation(),
1487                                                    SuppressNew) ||
1488             SuppressNew)
1489           continue;
1490
1491         if (TSK == TSK_ExplicitInstantiationDefinition) {
1492           // C++0x [temp.explicit]p8:
1493           //   An explicit instantiation definition that names a class template
1494           //   specialization explicitly instantiates the class template
1495           //   specialization and is only an explicit instantiation definition
1496           //   of members whose definition is visible at the point of
1497           //   instantiation.
1498           if (!Var->getInstantiatedFromStaticDataMember()
1499                                                      ->getOutOfLineDefinition())
1500             continue;
1501
1502           Var->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1503           InstantiateStaticDataMemberDefinition(PointOfInstantiation, Var);
1504         } else {
1505           Var->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1506         }
1507       }
1508     } else if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(*D)) {
1509       // Always skip the injected-class-name, along with any
1510       // redeclarations of nested classes, since both would cause us
1511       // to try to instantiate the members of a class twice.
1512       if (Record->isInjectedClassName() || Record->getPreviousDeclaration())
1513         continue;
1514
1515       MemberSpecializationInfo *MSInfo = Record->getMemberSpecializationInfo();
1516       assert(MSInfo && "No member specialization information?");
1517
1518       if (MSInfo->getTemplateSpecializationKind()
1519                                                 == TSK_ExplicitSpecialization)
1520         continue;
1521
1522       if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
1523                                                  Record,
1524                                         MSInfo->getTemplateSpecializationKind(),
1525                                               MSInfo->getPointOfInstantiation(),
1526                                                  SuppressNew) ||
1527           SuppressNew)
1528         continue;
1529
1530       CXXRecordDecl *Pattern = Record->getInstantiatedFromMemberClass();
1531       assert(Pattern && "Missing instantiated-from-template information");
1532
1533       if (!Record->getDefinition()) {
1534         if (!Pattern->getDefinition()) {
1535           // C++0x [temp.explicit]p8:
1536           //   An explicit instantiation definition that names a class template
1537           //   specialization explicitly instantiates the class template
1538           //   specialization and is only an explicit instantiation definition
1539           //   of members whose definition is visible at the point of
1540           //   instantiation.
1541           if (TSK == TSK_ExplicitInstantiationDeclaration) {
1542             MSInfo->setTemplateSpecializationKind(TSK);
1543             MSInfo->setPointOfInstantiation(PointOfInstantiation);
1544           }
1545
1546           continue;
1547         }
1548
1549         InstantiateClass(PointOfInstantiation, Record, Pattern,
1550                          TemplateArgs,
1551                          TSK);
1552       }
1553
1554       Pattern = cast_or_null<CXXRecordDecl>(Record->getDefinition());
1555       if (Pattern)
1556         InstantiateClassMembers(PointOfInstantiation, Pattern, TemplateArgs,
1557                                 TSK);
1558     }
1559   }
1560 }
1561
1562 /// \brief Instantiate the definitions of all of the members of the
1563 /// given class template specialization, which was named as part of an
1564 /// explicit instantiation.
1565 void
1566 Sema::InstantiateClassTemplateSpecializationMembers(
1567                                            SourceLocation PointOfInstantiation,
1568                             ClassTemplateSpecializationDecl *ClassTemplateSpec,
1569                                                TemplateSpecializationKind TSK) {
1570   // C++0x [temp.explicit]p7:
1571   //   An explicit instantiation that names a class template
1572   //   specialization is an explicit instantion of the same kind
1573   //   (declaration or definition) of each of its members (not
1574   //   including members inherited from base classes) that has not
1575   //   been previously explicitly specialized in the translation unit
1576   //   containing the explicit instantiation, except as described
1577   //   below.
1578   InstantiateClassMembers(PointOfInstantiation, ClassTemplateSpec,
1579                           getTemplateInstantiationArgs(ClassTemplateSpec),
1580                           TSK);
1581 }
1582
1583 Sema::OwningStmtResult
1584 Sema::SubstStmt(Stmt *S, const MultiLevelTemplateArgumentList &TemplateArgs) {
1585   if (!S)
1586     return Owned(S);
1587
1588   TemplateInstantiator Instantiator(*this, TemplateArgs,
1589                                     SourceLocation(),
1590                                     DeclarationName());
1591   return Instantiator.TransformStmt(S);
1592 }
1593
1594 Sema::OwningExprResult
1595 Sema::SubstExpr(Expr *E, const MultiLevelTemplateArgumentList &TemplateArgs) {
1596   if (!E)
1597     return Owned(E);
1598
1599   TemplateInstantiator Instantiator(*this, TemplateArgs,
1600                                     SourceLocation(),
1601                                     DeclarationName());
1602   return Instantiator.TransformExpr(E);
1603 }
1604
1605 /// \brief Do template substitution on a nested-name-specifier.
1606 NestedNameSpecifier *
1607 Sema::SubstNestedNameSpecifier(NestedNameSpecifier *NNS,
1608                                SourceRange Range,
1609                          const MultiLevelTemplateArgumentList &TemplateArgs) {
1610   TemplateInstantiator Instantiator(*this, TemplateArgs, Range.getBegin(),
1611                                     DeclarationName());
1612   return Instantiator.TransformNestedNameSpecifier(NNS, Range);
1613 }
1614
1615 TemplateName
1616 Sema::SubstTemplateName(TemplateName Name, SourceLocation Loc,
1617                         const MultiLevelTemplateArgumentList &TemplateArgs) {
1618   TemplateInstantiator Instantiator(*this, TemplateArgs, Loc,
1619                                     DeclarationName());
1620   return Instantiator.TransformTemplateName(Name);
1621 }
1622
1623 bool Sema::Subst(const TemplateArgumentLoc &Input, TemplateArgumentLoc &Output,
1624                  const MultiLevelTemplateArgumentList &TemplateArgs) {
1625   TemplateInstantiator Instantiator(*this, TemplateArgs, SourceLocation(),
1626                                     DeclarationName());
1627
1628   return Instantiator.TransformTemplateArgument(Input, Output);
1629 }
1630
1631 Decl *Sema::LocalInstantiationScope::getInstantiationOf(const Decl *D) {
1632   for (LocalInstantiationScope *Current = this; Current;
1633        Current = Current->Outer) {
1634     // Check if we found something within this scope.
1635     llvm::DenseMap<const Decl *, Decl *>::iterator Found
1636       = Current->LocalDecls.find(D);
1637     if (Found != Current->LocalDecls.end())
1638       return Found->second;
1639
1640     // If we aren't combined with our outer scope, we're done.
1641     if (!Current->CombineWithOuterScope)
1642       break;
1643   }
1644
1645   assert(D->isInvalidDecl() &&
1646          "declaration was not instantiated in this scope!");
1647   return 0;
1648 }
1649
1650 void Sema::LocalInstantiationScope::InstantiatedLocal(const Decl *D,
1651                                                       Decl *Inst) {
1652   Decl *&Stored = LocalDecls[D];
1653   assert((!Stored || Stored == Inst)&& "Already instantiated this local");
1654   Stored = Inst;
1655 }