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