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