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

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