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(SourceLocation Loc, Decl *D);
 544
 545     /// \brief Transform the definition of the given declaration by
 546     /// instantiating it.
 547     Decl *TransformDefinition(SourceLocation Loc, 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 function proto type by performing
 571     /// substitution in the function parameters, possibly adjusting
 572     /// their types and marking default arguments as uninstantiated.
 573     bool TransformFunctionTypeParams(FunctionProtoTypeLoc TL,
 574                                      llvm::SmallVectorImpl<QualType> &PTypes,
 575                                   llvm::SmallVectorImpl<ParmVarDecl*> &PVars);
 576
 577     ParmVarDecl *TransformFunctionTypeParam(ParmVarDecl *OldParm);
 578
 579     /// \brief Transforms a template type parameter type by performing
 580     /// substitution of the corresponding template type argument.
 581     QualType TransformTemplateTypeParmType(TypeLocBuilder &TLB,
 582                                            TemplateTypeParmTypeLoc TL,
 583                                            QualType ObjectType);
 584   };
 585 }
 586
 587 Decl *TemplateInstantiator::TransformDecl(SourceLocation Loc, Decl *D) {
 588   if (!D)
 589     return 0;
 590
 591   if (TemplateTemplateParmDecl *TTP = dyn_cast<TemplateTemplateParmDecl>(D)) {
 592     if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
 593       // If the corresponding template argument is NULL or non-existent, it's
 594       // because we are performing instantiation from explicitly-specified
 595       // template arguments in a function template, but there were some
 596       // arguments left unspecified.
 597       if (!TemplateArgs.hasTemplateArgument(TTP->getDepth(),
 598                                             TTP->getPosition()))
 599         return D;
 600
 601       TemplateName Template
 602         = TemplateArgs(TTP->getDepth(), TTP->getPosition()).getAsTemplate();
 603       assert(!Template.isNull() && Template.getAsTemplateDecl() &&
 604              "Wrong kind of template template argument");
 605       return Template.getAsTemplateDecl();
 606     }
 607
 608     // Fall through to find the instantiated declaration for this template
 609     // template parameter.
 610   }
 611
 612   return SemaRef.FindInstantiatedDecl(Loc, cast<NamedDecl>(D), TemplateArgs);
 613 }
 614
 615 Decl *TemplateInstantiator::TransformDefinition(SourceLocation Loc, Decl *D) {
 616   Decl *Inst = getSema().SubstDecl(D, getSema().CurContext, TemplateArgs);
 617   if (!Inst)
 618     return 0;
 619
 620   getSema().CurrentInstantiationScope->InstantiatedLocal(D, Inst);
 621   return Inst;
 622 }
 623
 624 NamedDecl *
 625 TemplateInstantiator::TransformFirstQualifierInScope(NamedDecl *D,
 626                                                      SourceLocation Loc) {
 627   // If the first part of the nested-name-specifier was a template type
 628   // parameter, instantiate that type parameter down to a tag type.
 629   if (TemplateTypeParmDecl *TTPD = dyn_cast_or_null<TemplateTypeParmDecl>(D)) {
 630     const TemplateTypeParmType *TTP
 631       = cast<TemplateTypeParmType>(getSema().Context.getTypeDeclType(TTPD));
 632     if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
 633       QualType T = TemplateArgs(TTP->getDepth(), TTP->getIndex()).getAsType();
 634       if (T.isNull())
 635         return cast_or_null<NamedDecl>(TransformDecl(Loc, D));
 636
 637       if (const TagType *Tag = T->getAs<TagType>())
 638         return Tag->getDecl();
 639
 640       // The resulting type is not a tag; complain.
 641       getSema().Diag(Loc, diag::err_nested_name_spec_non_tag) << T;
 642       return 0;
 643     }
 644   }
 645
 646   return cast_or_null<NamedDecl>(TransformDecl(Loc, D));
 647 }
 648
 649 VarDecl *
 650 TemplateInstantiator::RebuildExceptionDecl(VarDecl *ExceptionDecl,
 651                                            QualType T,
 652                                            TypeSourceInfo *Declarator,
 653                                            IdentifierInfo *Name,
 654                                            SourceLocation Loc,
 655                                            SourceRange TypeRange) {
 656   VarDecl *Var = inherited::RebuildExceptionDecl(ExceptionDecl, T, Declarator,
 657                                                  Name, Loc, TypeRange);
 658   if (Var && !Var->isInvalidDecl())
 659     getSema().CurrentInstantiationScope->InstantiatedLocal(ExceptionDecl, Var);
 660   return Var;
 661 }
 662
 663 QualType
 664 TemplateInstantiator::RebuildElaboratedType(QualType T,
 665                                             ElaboratedType::TagKind Tag) {
 666   if (const TagType *TT = T->getAs<TagType>()) {
 667     TagDecl* TD = TT->getDecl();
 668
 669     // FIXME: this location is very wrong;  we really need typelocs.
 670     SourceLocation TagLocation = TD->getTagKeywordLoc();
 671
 672     // FIXME: type might be anonymous.
 673     IdentifierInfo *Id = TD->getIdentifier();
 674
 675     // TODO: should we even warn on struct/class mismatches for this?  Seems
 676     // like it's likely to produce a lot of spurious errors.
 677     if (!SemaRef.isAcceptableTagRedeclaration(TD, Tag, TagLocation, *Id)) {
 678       SemaRef.Diag(TagLocation, diag::err_use_with_wrong_tag)
 679         << Id
 680         << CodeModificationHint::CreateReplacement(SourceRange(TagLocation),
 681                                                    TD->getKindName());
 682       SemaRef.Diag(TD->getLocation(), diag::note_previous_use);
 683     }
 684   }
 685
 686   return TreeTransform<TemplateInstantiator>::RebuildElaboratedType(T, Tag);
 687 }
 688
 689 Sema::OwningExprResult
 690 TemplateInstantiator::TransformPredefinedExpr(PredefinedExpr *E) {
 691   if (!E->isTypeDependent())
 692     return SemaRef.Owned(E->Retain());
 693
 694   FunctionDecl *currentDecl = getSema().getCurFunctionDecl();
 695   assert(currentDecl && "Must have current function declaration when "
 696                         "instantiating.");
 697
 698   PredefinedExpr::IdentType IT = E->getIdentType();
 699
 700   unsigned Length = PredefinedExpr::ComputeName(IT, currentDecl).length();
 701
 702   llvm::APInt LengthI(32, Length + 1);
 703   QualType ResTy = getSema().Context.CharTy.withConst();
 704   ResTy = getSema().Context.getConstantArrayType(ResTy, LengthI,
 705                                                  ArrayType::Normal, 0);
 706   PredefinedExpr *PE =
 707     new (getSema().Context) PredefinedExpr(E->getLocation(), ResTy, IT);
 708   return getSema().Owned(PE);
 709 }
 710
 711 Sema::OwningExprResult
 712 TemplateInstantiator::TransformTemplateParmRefExpr(DeclRefExpr *E,
 713                                                NonTypeTemplateParmDecl *NTTP) {
 714   // If the corresponding template argument is NULL or non-existent, it's
 715   // because we are performing instantiation from explicitly-specified
 716   // template arguments in a function template, but there were some
 717   // arguments left unspecified.
 718   if (!TemplateArgs.hasTemplateArgument(NTTP->getDepth(),
 719                                         NTTP->getPosition()))
 720     return SemaRef.Owned(E->Retain());
 721
 722   const TemplateArgument &Arg = TemplateArgs(NTTP->getDepth(),
 723                                              NTTP->getPosition());
 724
 725   // The template argument itself might be an expression, in which
 726   // case we just return that expression.
 727   if (Arg.getKind() == TemplateArgument::Expression)
 728     return SemaRef.Owned(Arg.getAsExpr()->Retain());
 729
 730   if (Arg.getKind() == TemplateArgument::Declaration) {
 731     ValueDecl *VD = cast<ValueDecl>(Arg.getAsDecl());
 732
 733     // Find the instantiation of the template argument.  This is
 734     // required for nested templates.
 735     VD = cast_or_null<ValueDecl>(
 736                             getSema().FindInstantiatedDecl(E->getLocation(),
 737                                                            VD, TemplateArgs));
 738     if (!VD)
 739       return SemaRef.ExprError();
 740
 741     // Derive the type we want the substituted decl to have.  This had
 742     // better be non-dependent, or these checks will have serious problems.
 743     QualType TargetType = SemaRef.SubstType(NTTP->getType(), TemplateArgs,
 744                                             E->getLocation(),
 745                                             DeclarationName());
 746     assert(!TargetType.isNull() && "type substitution failed for param type");
 747     assert(!TargetType->isDependentType() && "param type still dependent");
 748
 749     if (VD->getDeclContext()->isRecord() &&
 750         (isa<CXXMethodDecl>(VD) || isa<FieldDecl>(VD))) {
 751       // If the value is a class member, we might have a pointer-to-member.
 752       // Determine whether the non-type template template parameter is of
 753       // pointer-to-member type. If so, we need to build an appropriate
 754       // expression for a pointer-to-member, since a "normal" DeclRefExpr
 755       // would refer to the member itself.
 756       if (TargetType->isMemberPointerType()) {
 757         QualType ClassType
 758           = SemaRef.Context.getTypeDeclType(
 759                                         cast<RecordDecl>(VD->getDeclContext()));
 760         NestedNameSpecifier *Qualifier
 761           = NestedNameSpecifier::Create(SemaRef.Context, 0, false,
 762                                         ClassType.getTypePtr());
 763         CXXScopeSpec SS;
 764         SS.setScopeRep(Qualifier);
 765         OwningExprResult RefExpr
 766           = SemaRef.BuildDeclRefExpr(VD,
 767                                      VD->getType().getNonReferenceType(),
 768                                      E->getLocation(),
 769                                      &SS);
 770         if (RefExpr.isInvalid())
 771           return SemaRef.ExprError();
 772
 773         RefExpr = SemaRef.CreateBuiltinUnaryOp(E->getLocation(),
 774                                                UnaryOperator::AddrOf,
 775                                                move(RefExpr));
 776         assert(!RefExpr.isInvalid() &&
 777                SemaRef.Context.hasSameType(((Expr*) RefExpr.get())->getType(),
 778                                            TargetType));
 779         return move(RefExpr);
 780       }
 781     }
 782
 783     QualType T = VD->getType().getNonReferenceType();
 784
 785     if (TargetType->isPointerType()) {
 786       // C++03 [temp.arg.nontype]p5:
 787       //  - For a non-type template-parameter of type pointer to
 788       //    object, qualification conversions and the array-to-pointer
 789       //    conversion are applied.
 790       //  - For a non-type template-parameter of type pointer to
 791       //    function, only the function-to-pointer conversion is
 792       //    applied.
 793
 794       OwningExprResult RefExpr
 795         = SemaRef.BuildDeclRefExpr(VD, T, E->getLocation());
 796       if (RefExpr.isInvalid())
 797         return SemaRef.ExprError();
 798
 799       // Decay functions and arrays.
 800       Expr *RefE = (Expr *)RefExpr.get();
 801       SemaRef.DefaultFunctionArrayConversion(RefE);
 802       if (RefE != RefExpr.get()) {
 803         RefExpr.release();
 804         RefExpr = SemaRef.Owned(RefE);
 805       }
 806
 807       // Qualification conversions.
 808       RefExpr.release();
 809       SemaRef.ImpCastExprToType(RefE, TargetType.getUnqualifiedType(),
 810                                 CastExpr::CK_NoOp);
 811       return SemaRef.Owned(RefE);
 812     }
 813
 814     // If the non-type template parameter has reference type, qualify the
 815     // resulting declaration reference with the extra qualifiers on the
 816     // type that the reference refers to.
 817     if (const ReferenceType *TargetRef = TargetType->getAs<ReferenceType>())
 818       T = SemaRef.Context.getQualifiedType(T,
 819                                   TargetRef->getPointeeType().getQualifiers());
 820
 821     return SemaRef.BuildDeclRefExpr(VD, T, E->getLocation());
 822   }
 823
 824   assert(Arg.getKind() == TemplateArgument::Integral);
 825   QualType T = Arg.getIntegralType();
 826   if (T->isCharType() || T->isWideCharType())
 827     return SemaRef.Owned(new (SemaRef.Context) CharacterLiteral(
 828                                               Arg.getAsIntegral()->getZExtValue(),
 829                                               T->isWideCharType(),
 830                                               T,
 831                                               E->getSourceRange().getBegin()));
 832   if (T->isBooleanType())
 833     return SemaRef.Owned(new (SemaRef.Context) CXXBoolLiteralExpr(
 834                                             Arg.getAsIntegral()->getBoolValue(),
 835                                             T,
 836                                             E->getSourceRange().getBegin()));
 837
 838   assert(Arg.getAsIntegral()->getBitWidth() == SemaRef.Context.getIntWidth(T));
 839   return SemaRef.Owned(new (SemaRef.Context) IntegerLiteral(
 840                                                 *Arg.getAsIntegral(),
 841                                                 T,
 842                                                 E->getSourceRange().getBegin()));
 843 }
 844
 845
 846 Sema::OwningExprResult
 847 TemplateInstantiator::TransformDeclRefExpr(DeclRefExpr *E) {
 848   NamedDecl *D = E->getDecl();
 849   if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D)) {
 850     if (NTTP->getDepth() < TemplateArgs.getNumLevels())
 851       return TransformTemplateParmRefExpr(E, NTTP);
 852
 853     // We have a non-type template parameter that isn't fully substituted;
 854     // FindInstantiatedDecl will find it in the local instantiation scope.
 855   }
 856
 857   return TreeTransform<TemplateInstantiator>::TransformDeclRefExpr(E);
 858 }
 859
 860 Sema::OwningExprResult TemplateInstantiator::TransformCXXDefaultArgExpr(
 861     CXXDefaultArgExpr *E) {
 862   assert(!cast<FunctionDecl>(E->getParam()->getDeclContext())->
 863              getDescribedFunctionTemplate() &&
 864          "Default arg expressions are never formed in dependent cases.");
 865   return SemaRef.BuildCXXDefaultArgExpr(E->getUsedLocation(),
 866                            cast<FunctionDecl>(E->getParam()->getDeclContext()),
 867                                         E->getParam());
 868 }
 869
 870
 871 bool
 872 TemplateInstantiator::TransformFunctionTypeParams(FunctionProtoTypeLoc TL,
 873                                   llvm::SmallVectorImpl<QualType> &PTypes,
 874                                llvm::SmallVectorImpl<ParmVarDecl*> &PVars) {
 875   // Create a local instantiation scope for the parameters.
 876   Sema::LocalInstantiationScope
 877     Scope(SemaRef, SemaRef.CurrentInstantiationScope != 0);
 878
 879   if (TreeTransform<TemplateInstantiator>::
 880         TransformFunctionTypeParams(TL, PTypes, PVars))
 881     return true;
 882
 883   // Check instantiated parameters.
 884   if (SemaRef.CheckInstantiatedParams(PVars))
 885     return true;
 886
 887   return false;
 888 }
 889
 890 ParmVarDecl *
 891 TemplateInstantiator::TransformFunctionTypeParam(ParmVarDecl *OldParm) {
 892   TypeSourceInfo *OldDI = OldParm->getTypeSourceInfo();
 893   TypeSourceInfo *NewDI = getDerived().TransformType(OldDI);
 894   if (!NewDI)
 895     return 0;
 896
 897   // TODO: do we have to clone this decl if the types match and
 898   // there's no default argument?
 899
 900   ParmVarDecl *NewParm
 901     = ParmVarDecl::Create(SemaRef.Context,
 902                           OldParm->getDeclContext(),
 903                           OldParm->getLocation(),
 904                           OldParm->getIdentifier(),
 905                           NewDI->getType(),
 906                           NewDI,
 907                           OldParm->getStorageClass(),
 908                           /* DefArg */ NULL);
 909
 910   // Maybe adjust new parameter type.
 911   NewParm->setType(SemaRef.adjustParameterType(NewParm->getType()));
 912
 913   // Mark the (new) default argument as uninstantiated (if any).
 914   if (OldParm->hasUninstantiatedDefaultArg()) {
 915     Expr *Arg = OldParm->getUninstantiatedDefaultArg();
 916     NewParm->setUninstantiatedDefaultArg(Arg);
 917   } else if (Expr *Arg = OldParm->getDefaultArg())
 918     NewParm->setUninstantiatedDefaultArg(Arg);
 919
 920   NewParm->setHasInheritedDefaultArg(OldParm->hasInheritedDefaultArg());
 921
 922   SemaRef.CurrentInstantiationScope->InstantiatedLocal(OldParm, NewParm);
 923   return NewParm;
 924 }
 925
 926 QualType
 927 TemplateInstantiator::TransformTemplateTypeParmType(TypeLocBuilder &TLB,
 928                                                 TemplateTypeParmTypeLoc TL,
 929                                                     QualType ObjectType) {
 930   TemplateTypeParmType *T = TL.getTypePtr();
 931   if (T->getDepth() < TemplateArgs.getNumLevels()) {
 932     // Replace the template type parameter with its corresponding
 933     // template argument.
 934
 935     // If the corresponding template argument is NULL or doesn't exist, it's
 936     // because we are performing instantiation from explicitly-specified
 937     // template arguments in a function template class, but there were some
 938     // arguments left unspecified.
 939     if (!TemplateArgs.hasTemplateArgument(T->getDepth(), T->getIndex())) {
 940       TemplateTypeParmTypeLoc NewTL
 941         = TLB.push<TemplateTypeParmTypeLoc>(TL.getType());
 942       NewTL.setNameLoc(TL.getNameLoc());
 943       return TL.getType();
 944     }
 945
 946     assert(TemplateArgs(T->getDepth(), T->getIndex()).getKind()
 947              == TemplateArgument::Type &&
 948            "Template argument kind mismatch");
 949
 950     QualType Replacement
 951       = TemplateArgs(T->getDepth(), T->getIndex()).getAsType();
 952
 953     // TODO: only do this uniquing once, at the start of instantiation.
 954     QualType Result
 955       = getSema().Context.getSubstTemplateTypeParmType(T, Replacement);
 956     SubstTemplateTypeParmTypeLoc NewTL
 957       = TLB.push<SubstTemplateTypeParmTypeLoc>(Result);
 958     NewTL.setNameLoc(TL.getNameLoc());
 959     return Result;
 960   }
 961
 962   // The template type parameter comes from an inner template (e.g.,
 963   // the template parameter list of a member template inside the
 964   // template we are instantiating). Create a new template type
 965   // parameter with the template "level" reduced by one.
 966   QualType Result
 967     = getSema().Context.getTemplateTypeParmType(T->getDepth()
 968                                                  - TemplateArgs.getNumLevels(),
 969                                                 T->getIndex(),
 970                                                 T->isParameterPack(),
 971                                                 T->getName());
 972   TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result);
 973   NewTL.setNameLoc(TL.getNameLoc());
 974   return Result;
 975 }
 976
 977 /// \brief Perform substitution on the type T with a given set of template
 978 /// arguments.
 979 ///
 980 /// This routine substitutes the given template arguments into the
 981 /// type T and produces the instantiated type.
 982 ///
 983 /// \param T the type into which the template arguments will be
 984 /// substituted. If this type is not dependent, it will be returned
 985 /// immediately.
 986 ///
 987 /// \param TemplateArgs the template arguments that will be
 988 /// substituted for the top-level template parameters within T.
 989 ///
 990 /// \param Loc the location in the source code where this substitution
 991 /// is being performed. It will typically be the location of the
 992 /// declarator (if we're instantiating the type of some declaration)
 993 /// or the location of the type in the source code (if, e.g., we're
 994 /// instantiating the type of a cast expression).
 995 ///
 996 /// \param Entity the name of the entity associated with a declaration
 997 /// being instantiated (if any). May be empty to indicate that there
 998 /// is no such entity (if, e.g., this is a type that occurs as part of
 999 /// a cast expression) or that the entity has no name (e.g., an
1000 /// unnamed function parameter).
1001 ///
1002 /// \returns If the instantiation succeeds, the instantiated
1003 /// type. Otherwise, produces diagnostics and returns a NULL type.
1004 TypeSourceInfo *Sema::SubstType(TypeSourceInfo *T,
1005                                 const MultiLevelTemplateArgumentList &Args,
1006                                 SourceLocation Loc,
1007                                 DeclarationName Entity) {
1008   assert(!ActiveTemplateInstantiations.empty() &&
1009          "Cannot perform an instantiation without some context on the "
1010          "instantiation stack");
1011
1012   if (!T->getType()->isDependentType())
1013     return T;
1014
1015   TemplateInstantiator Instantiator(*this, Args, Loc, Entity);
1016   return Instantiator.TransformType(T);
1017 }
1018
1019 /// Deprecated form of the above.
1020 QualType Sema::SubstType(QualType T,
1021                          const MultiLevelTemplateArgumentList &TemplateArgs,
1022                          SourceLocation Loc, DeclarationName Entity) {
1023   assert(!ActiveTemplateInstantiations.empty() &&
1024          "Cannot perform an instantiation without some context on the "
1025          "instantiation stack");
1026
1027   // If T is not a dependent type, there is nothing to do.
1028   if (!T->isDependentType())
1029     return T;
1030
1031   TemplateInstantiator Instantiator(*this, TemplateArgs, Loc, Entity);
1032   return Instantiator.TransformType(T);
1033 }
1034
1035 /// \brief Perform substitution on the base class specifiers of the
1036 /// given class template specialization.
1037 ///
1038 /// Produces a diagnostic and returns true on error, returns false and
1039 /// attaches the instantiated base classes to the class template
1040 /// specialization if successful.
1041 bool
1042 Sema::SubstBaseSpecifiers(CXXRecordDecl *Instantiation,
1043                           CXXRecordDecl *Pattern,
1044                           const MultiLevelTemplateArgumentList &TemplateArgs) {
1045   bool Invalid = false;
1046   llvm::SmallVector<CXXBaseSpecifier*, 4> InstantiatedBases;
1047   for (ClassTemplateSpecializationDecl::base_class_iterator
1048          Base = Pattern->bases_begin(), BaseEnd = Pattern->bases_end();
1049        Base != BaseEnd; ++Base) {
1050     if (!Base->getType()->isDependentType()) {
1051       const CXXRecordDecl *BaseDecl =
1052         cast<CXXRecordDecl>(Base->getType()->getAs<RecordType>()->getDecl());
1053
1054       // Make sure to set the attributes from the base.
1055       SetClassDeclAttributesFromBase(Instantiation, BaseDecl,
1056                                      Base->isVirtual());
1057
1058       InstantiatedBases.push_back(new (Context) CXXBaseSpecifier(*Base));
1059       continue;
1060     }
1061
1062     QualType BaseType = SubstType(Base->getType(),
1063                                   TemplateArgs,
1064                                   Base->getSourceRange().getBegin(),
1065                                   DeclarationName());
1066     if (BaseType.isNull()) {
1067       Invalid = true;
1068       continue;
1069     }
1070
1071     if (CXXBaseSpecifier *InstantiatedBase
1072           = CheckBaseSpecifier(Instantiation,
1073                                Base->getSourceRange(),
1074                                Base->isVirtual(),
1075                                Base->getAccessSpecifierAsWritten(),
1076                                BaseType,
1077                                /*FIXME: Not totally accurate */
1078                                Base->getSourceRange().getBegin()))
1079       InstantiatedBases.push_back(InstantiatedBase);
1080     else
1081       Invalid = true;
1082   }
1083
1084   if (!Invalid &&
1085       AttachBaseSpecifiers(Instantiation, InstantiatedBases.data(),
1086                            InstantiatedBases.size()))
1087     Invalid = true;
1088
1089   return Invalid;
1090 }
1091
1092 /// \brief Instantiate the definition of a class from a given pattern.
1093 ///
1094 /// \param PointOfInstantiation The point of instantiation within the
1095 /// source code.
1096 ///
1097 /// \param Instantiation is the declaration whose definition is being
1098 /// instantiated. This will be either a class template specialization
1099 /// or a member class of a class template specialization.
1100 ///
1101 /// \param Pattern is the pattern from which the instantiation
1102 /// occurs. This will be either the declaration of a class template or
1103 /// the declaration of a member class of a class template.
1104 ///
1105 /// \param TemplateArgs The template arguments to be substituted into
1106 /// the pattern.
1107 ///
1108 /// \param TSK the kind of implicit or explicit instantiation to perform.
1109 ///
1110 /// \param Complain whether to complain if the class cannot be instantiated due
1111 /// to the lack of a definition.
1112 ///
1113 /// \returns true if an error occurred, false otherwise.
1114 bool
1115 Sema::InstantiateClass(SourceLocation PointOfInstantiation,
1116                        CXXRecordDecl *Instantiation, CXXRecordDecl *Pattern,
1117                        const MultiLevelTemplateArgumentList &TemplateArgs,
1118                        TemplateSpecializationKind TSK,
1119                        bool Complain) {
1120   bool Invalid = false;
1121
1122   CXXRecordDecl *PatternDef
1123     = cast_or_null<CXXRecordDecl>(Pattern->getDefinition());
1124   if (!PatternDef) {
1125     if (!Complain) {
1126       // Say nothing
1127     } else if (Pattern == Instantiation->getInstantiatedFromMemberClass()) {
1128       Diag(PointOfInstantiation,
1129            diag::err_implicit_instantiate_member_undefined)
1130         << Context.getTypeDeclType(Instantiation);
1131       Diag(Pattern->getLocation(), diag::note_member_of_template_here);
1132     } else {
1133       Diag(PointOfInstantiation, diag::err_template_instantiate_undefined)
1134         << (TSK != TSK_ImplicitInstantiation)
1135         << Context.getTypeDeclType(Instantiation);
1136       Diag(Pattern->getLocation(), diag::note_template_decl_here);
1137     }
1138     return true;
1139   }
1140   Pattern = PatternDef;
1141
1142   // \brief Record the point of instantiation.
1143   if (MemberSpecializationInfo *MSInfo
1144         = Instantiation->getMemberSpecializationInfo()) {
1145     MSInfo->setTemplateSpecializationKind(TSK);
1146     MSInfo->setPointOfInstantiation(PointOfInstantiation);
1147   } else if (ClassTemplateSpecializationDecl *Spec
1148                = dyn_cast<ClassTemplateSpecializationDecl>(Instantiation)) {
1149     Spec->setTemplateSpecializationKind(TSK);
1150     Spec->setPointOfInstantiation(PointOfInstantiation);
1151   }
1152
1153   InstantiatingTemplate Inst(*this, PointOfInstantiation, Instantiation);
1154   if (Inst)
1155     return true;
1156
1157   // Enter the scope of this instantiation. We don't use
1158   // PushDeclContext because we don't have a scope.
1159   DeclContext *PreviousContext = CurContext;
1160   CurContext = Instantiation;
1161
1162   // Start the definition of this instantiation.
1163   Instantiation->startDefinition();
1164
1165   // Do substitution on the base class specifiers.
1166   if (SubstBaseSpecifiers(Instantiation, Pattern, TemplateArgs))
1167     Invalid = true;
1168
1169   llvm::SmallVector<DeclPtrTy, 4> Fields;
1170   for (RecordDecl::decl_iterator Member = Pattern->decls_begin(),
1171          MemberEnd = Pattern->decls_end();
1172        Member != MemberEnd; ++Member) {
1173     Decl *NewMember = SubstDecl(*Member, Instantiation, TemplateArgs);
1174     if (NewMember) {
1175       if (FieldDecl *Field = dyn_cast<FieldDecl>(NewMember))
1176         Fields.push_back(DeclPtrTy::make(Field));
1177       else if (NewMember->isInvalidDecl())
1178         Invalid = true;
1179     } else {
1180       // FIXME: Eventually, a NULL return will mean that one of the
1181       // instantiations was a semantic disaster, and we'll want to set Invalid =
1182       // true. For now, we expect to skip some members that we can't yet handle.
1183     }
1184   }
1185
1186   // Finish checking fields.
1187   ActOnFields(0, Instantiation->getLocation(), DeclPtrTy::make(Instantiation),
1188               Fields.data(), Fields.size(), SourceLocation(), SourceLocation(),
1189               0);
1190   CheckCompletedCXXClass(Instantiation);
1191   if (Instantiation->isInvalidDecl())
1192     Invalid = true;
1193
1194   // Exit the scope of this instantiation.
1195   CurContext = PreviousContext;
1196
1197   // If this is a polymorphic C++ class without a key function, we'll
1198   // have to mark all of the virtual members to allow emission of a vtable
1199   // in this translation unit.
1200   if (Instantiation->isDynamicClass() &&
1201       !Context.getKeyFunction(Instantiation)) {
1202     // Local classes need to have their methods instantiated immediately in
1203     // order to have the correct instantiation scope.
1204     if (Instantiation->isLocalClass()) {
1205       MarkVirtualMembersReferenced(PointOfInstantiation,
1206                                    Instantiation);
1207     } else {
1208       ClassesWithUnmarkedVirtualMembers.push_back(std::make_pair(Instantiation,
1209                                                        PointOfInstantiation));
1210     }
1211   }
1212
1213   if (!Invalid)
1214     Consumer.HandleTagDeclDefinition(Instantiation);
1215
1216   return Invalid;
1217 }
1218
1219 bool
1220 Sema::InstantiateClassTemplateSpecialization(
1221                            SourceLocation PointOfInstantiation,
1222                            ClassTemplateSpecializationDecl *ClassTemplateSpec,
1223                            TemplateSpecializationKind TSK,
1224                            bool Complain) {
1225   // Perform the actual instantiation on the canonical declaration.
1226   ClassTemplateSpec = cast<ClassTemplateSpecializationDecl>(
1227                                          ClassTemplateSpec->getCanonicalDecl());
1228
1229   // Check whether we have already instantiated or specialized this class
1230   // template specialization.
1231   if (ClassTemplateSpec->getSpecializationKind() != TSK_Undeclared) {
1232     if (ClassTemplateSpec->getSpecializationKind() ==
1233           TSK_ExplicitInstantiationDeclaration &&
1234         TSK == TSK_ExplicitInstantiationDefinition) {
1235       // An explicit instantiation definition follows an explicit instantiation
1236       // declaration (C++0x [temp.explicit]p10); go ahead and perform the
1237       // explicit instantiation.
1238       ClassTemplateSpec->setSpecializationKind(TSK);
1239       return false;
1240     }
1241
1242     // We can only instantiate something that hasn't already been
1243     // instantiated or specialized. Fail without any diagnostics: our
1244     // caller will provide an error message.
1245     return true;
1246   }
1247
1248   if (ClassTemplateSpec->isInvalidDecl())
1249     return true;
1250
1251   ClassTemplateDecl *Template = ClassTemplateSpec->getSpecializedTemplate();
1252   CXXRecordDecl *Pattern = 0;
1253
1254   // C++ [temp.class.spec.match]p1:
1255   //   When a class template is used in a context that requires an
1256   //   instantiation of the class, it is necessary to determine
1257   //   whether the instantiation is to be generated using the primary
1258   //   template or one of the partial specializations. This is done by
1259   //   matching the template arguments of the class template
1260   //   specialization with the template argument lists of the partial
1261   //   specializations.
1262   typedef std::pair<ClassTemplatePartialSpecializationDecl *,
1263                     TemplateArgumentList *> MatchResult;
1264   llvm::SmallVector<MatchResult, 4> Matched;
1265   for (llvm::FoldingSet<ClassTemplatePartialSpecializationDecl>::iterator
1266          Partial = Template->getPartialSpecializations().begin(),
1267          PartialEnd = Template->getPartialSpecializations().end();
1268        Partial != PartialEnd;
1269        ++Partial) {
1270     TemplateDeductionInfo Info(Context, PointOfInstantiation);
1271     if (TemplateDeductionResult Result
1272           = DeduceTemplateArguments(&*Partial,
1273                                     ClassTemplateSpec->getTemplateArgs(),
1274                                     Info)) {
1275       // FIXME: Store the failed-deduction information for use in
1276       // diagnostics, later.
1277       (void)Result;
1278     } else {
1279       Matched.push_back(std::make_pair(&*Partial, Info.take()));
1280     }
1281   }
1282
1283   if (Matched.size() >= 1) {
1284     llvm::SmallVector<MatchResult, 4>::iterator Best = Matched.begin();
1285     if (Matched.size() == 1) {
1286       //   -- If exactly one matching specialization is found, the
1287       //      instantiation is generated from that specialization.
1288       // We don't need to do anything for this.
1289     } else {
1290       //   -- If more than one matching specialization is found, the
1291       //      partial order rules (14.5.4.2) are used to determine
1292       //      whether one of the specializations is more specialized
1293       //      than the others. If none of the specializations is more
1294       //      specialized than all of the other matching
1295       //      specializations, then the use of the class template is
1296       //      ambiguous and the program is ill-formed.
1297       for (llvm::SmallVector<MatchResult, 4>::iterator P = Best + 1,
1298                                                     PEnd = Matched.end();
1299            P != PEnd; ++P) {
1300         if (getMoreSpecializedPartialSpecialization(P->first, Best->first,
1301                                                     PointOfInstantiation)
1302               == P->first)
1303           Best = P;
1304       }
1305
1306       // Determine if the best partial specialization is more specialized than
1307       // the others.
1308       bool Ambiguous = false;
1309       for (llvm::SmallVector<MatchResult, 4>::iterator P = Matched.begin(),
1310                                                     PEnd = Matched.end();
1311            P != PEnd; ++P) {
1312         if (P != Best &&
1313             getMoreSpecializedPartialSpecialization(P->first, Best->first,
1314                                                     PointOfInstantiation)
1315               != Best->first) {
1316           Ambiguous = true;
1317           break;
1318         }
1319       }
1320
1321       if (Ambiguous) {
1322         // Partial ordering did not produce a clear winner. Complain.
1323         ClassTemplateSpec->setInvalidDecl();
1324         Diag(PointOfInstantiation, diag::err_partial_spec_ordering_ambiguous)
1325           << ClassTemplateSpec;
1326
1327         // Print the matching partial specializations.
1328         for (llvm::SmallVector<MatchResult, 4>::iterator P = Matched.begin(),
1329                                                       PEnd = Matched.end();
1330              P != PEnd; ++P)
1331           Diag(P->first->getLocation(), diag::note_partial_spec_match)
1332             << getTemplateArgumentBindingsText(P->first->getTemplateParameters(),
1333                                                *P->second);
1334
1335         return true;
1336       }
1337     }
1338
1339     // Instantiate using the best class template partial specialization.
1340     ClassTemplatePartialSpecializationDecl *OrigPartialSpec = Best->first;
1341     while (OrigPartialSpec->getInstantiatedFromMember()) {
1342       // If we've found an explicit specialization of this class template,
1343       // stop here and use that as the pattern.
1344       if (OrigPartialSpec->isMemberSpecialization())
1345         break;
1346
1347       OrigPartialSpec = OrigPartialSpec->getInstantiatedFromMember();
1348     }
1349
1350     Pattern = OrigPartialSpec;
1351     ClassTemplateSpec->setInstantiationOf(Best->first, Best->second);
1352   } else {
1353     //   -- If no matches are found, the instantiation is generated
1354     //      from the primary template.
1355     ClassTemplateDecl *OrigTemplate = Template;
1356     while (OrigTemplate->getInstantiatedFromMemberTemplate()) {
1357       // If we've found an explicit specialization of this class template,
1358       // stop here and use that as the pattern.
1359       if (OrigTemplate->isMemberSpecialization())
1360         break;
1361
1362       OrigTemplate = OrigTemplate->getInstantiatedFromMemberTemplate();
1363     }
1364
1365     Pattern = OrigTemplate->getTemplatedDecl();
1366   }
1367
1368   bool Result = InstantiateClass(PointOfInstantiation, ClassTemplateSpec,
1369                                  Pattern,
1370                                 getTemplateInstantiationArgs(ClassTemplateSpec),
1371                                  TSK,
1372                                  Complain);
1373
1374   for (unsigned I = 0, N = Matched.size(); I != N; ++I) {
1375     // FIXME: Implement TemplateArgumentList::Destroy!
1376     //    if (Matched[I].first != Pattern)
1377     //      Matched[I].second->Destroy(Context);
1378   }
1379
1380   return Result;
1381 }
1382
1383 /// \brief Instantiates the definitions of all of the member
1384 /// of the given class, which is an instantiation of a class template
1385 /// or a member class of a template.
1386 void
1387 Sema::InstantiateClassMembers(SourceLocation PointOfInstantiation,
1388                               CXXRecordDecl *Instantiation,
1389                         const MultiLevelTemplateArgumentList &TemplateArgs,
1390                               TemplateSpecializationKind TSK) {
1391   for (DeclContext::decl_iterator D = Instantiation->decls_begin(),
1392                                DEnd = Instantiation->decls_end();
1393        D != DEnd; ++D) {
1394     bool SuppressNew = false;
1395     if (FunctionDecl *Function = dyn_cast<FunctionDecl>(*D)) {
1396       if (FunctionDecl *Pattern
1397             = Function->getInstantiatedFromMemberFunction()) {
1398         MemberSpecializationInfo *MSInfo
1399           = Function->getMemberSpecializationInfo();
1400         assert(MSInfo && "No member specialization information?");
1401         if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
1402                                                    Function,
1403                                         MSInfo->getTemplateSpecializationKind(),
1404                                               MSInfo->getPointOfInstantiation(),
1405                                                    SuppressNew) ||
1406             SuppressNew)
1407           continue;
1408
1409         if (Function->getBody())
1410           continue;
1411
1412         if (TSK == TSK_ExplicitInstantiationDefinition) {
1413           // C++0x [temp.explicit]p8:
1414           //   An explicit instantiation definition that names a class template
1415           //   specialization explicitly instantiates the class template
1416           //   specialization and is only an explicit instantiation definition
1417           //   of members whose definition is visible at the point of
1418           //   instantiation.
1419           if (!Pattern->getBody())
1420             continue;
1421
1422           Function->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1423
1424           InstantiateFunctionDefinition(PointOfInstantiation, Function);
1425         } else {
1426           Function->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1427         }
1428       }
1429     } else if (VarDecl *Var = dyn_cast<VarDecl>(*D)) {
1430       if (Var->isStaticDataMember()) {
1431         MemberSpecializationInfo *MSInfo = Var->getMemberSpecializationInfo();
1432         assert(MSInfo && "No member specialization information?");
1433         if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
1434                                                    Var,
1435                                         MSInfo->getTemplateSpecializationKind(),
1436                                               MSInfo->getPointOfInstantiation(),
1437                                                    SuppressNew) ||
1438             SuppressNew)
1439           continue;
1440
1441         if (TSK == TSK_ExplicitInstantiationDefinition) {
1442           // C++0x [temp.explicit]p8:
1443           //   An explicit instantiation definition that names a class template
1444           //   specialization explicitly instantiates the class template
1445           //   specialization and is only an explicit instantiation definition
1446           //   of members whose definition is visible at the point of
1447           //   instantiation.
1448           if (!Var->getInstantiatedFromStaticDataMember()
1449                                                      ->getOutOfLineDefinition())
1450             continue;
1451
1452           Var->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1453           InstantiateStaticDataMemberDefinition(PointOfInstantiation, Var);
1454         } else {
1455           Var->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1456         }
1457       }
1458     } else if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(*D)) {
1459       if (Record->isInjectedClassName())
1460         continue;
1461
1462       MemberSpecializationInfo *MSInfo = Record->getMemberSpecializationInfo();
1463       assert(MSInfo && "No member specialization information?");
1464       if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
1465                                                  Record,
1466                                         MSInfo->getTemplateSpecializationKind(),
1467                                               MSInfo->getPointOfInstantiation(),
1468                                                  SuppressNew) ||
1469           SuppressNew)
1470         continue;
1471
1472       CXXRecordDecl *Pattern = Record->getInstantiatedFromMemberClass();
1473       assert(Pattern && "Missing instantiated-from-template information");
1474
1475       if (!Record->getDefinition()) {
1476         if (!Pattern->getDefinition()) {
1477           // C++0x [temp.explicit]p8:
1478           //   An explicit instantiation definition that names a class template
1479           //   specialization explicitly instantiates the class template
1480           //   specialization and is only an explicit instantiation definition
1481           //   of members whose definition is visible at the point of
1482           //   instantiation.
1483           if (TSK == TSK_ExplicitInstantiationDeclaration) {
1484             MSInfo->setTemplateSpecializationKind(TSK);
1485             MSInfo->setPointOfInstantiation(PointOfInstantiation);
1486           }
1487
1488           continue;
1489         }
1490
1491         InstantiateClass(PointOfInstantiation, Record, Pattern,
1492                          TemplateArgs,
1493                          TSK);
1494       }
1495
1496       Pattern = cast_or_null<CXXRecordDecl>(Record->getDefinition());
1497       if (Pattern)
1498         InstantiateClassMembers(PointOfInstantiation, Pattern, TemplateArgs,
1499                                 TSK);
1500     }
1501   }
1502 }
1503
1504 /// \brief Instantiate the definitions of all of the members of the
1505 /// given class template specialization, which was named as part of an
1506 /// explicit instantiation.
1507 void
1508 Sema::InstantiateClassTemplateSpecializationMembers(
1509                                            SourceLocation PointOfInstantiation,
1510                             ClassTemplateSpecializationDecl *ClassTemplateSpec,
1511                                                TemplateSpecializationKind TSK) {
1512   // C++0x [temp.explicit]p7:
1513   //   An explicit instantiation that names a class template
1514   //   specialization is an explicit instantion of the same kind
1515   //   (declaration or definition) of each of its members (not
1516   //   including members inherited from base classes) that has not
1517   //   been previously explicitly specialized in the translation unit
1518   //   containing the explicit instantiation, except as described
1519   //   below.
1520   InstantiateClassMembers(PointOfInstantiation, ClassTemplateSpec,
1521                           getTemplateInstantiationArgs(ClassTemplateSpec),
1522                           TSK);
1523 }
1524
1525 Sema::OwningStmtResult
1526 Sema::SubstStmt(Stmt *S, const MultiLevelTemplateArgumentList &TemplateArgs) {
1527   if (!S)
1528     return Owned(S);
1529
1530   TemplateInstantiator Instantiator(*this, TemplateArgs,
1531                                     SourceLocation(),
1532                                     DeclarationName());
1533   return Instantiator.TransformStmt(S);
1534 }
1535
1536 Sema::OwningExprResult
1537 Sema::SubstExpr(Expr *E, const MultiLevelTemplateArgumentList &TemplateArgs) {
1538   if (!E)
1539     return Owned(E);
1540
1541   TemplateInstantiator Instantiator(*this, TemplateArgs,
1542                                     SourceLocation(),
1543                                     DeclarationName());
1544   return Instantiator.TransformExpr(E);
1545 }
1546
1547 /// \brief Do template substitution on a nested-name-specifier.
1548 NestedNameSpecifier *
1549 Sema::SubstNestedNameSpecifier(NestedNameSpecifier *NNS,
1550                                SourceRange Range,
1551                          const MultiLevelTemplateArgumentList &TemplateArgs) {
1552   TemplateInstantiator Instantiator(*this, TemplateArgs, Range.getBegin(),
1553                                     DeclarationName());
1554   return Instantiator.TransformNestedNameSpecifier(NNS, Range);
1555 }
1556
1557 TemplateName
1558 Sema::SubstTemplateName(TemplateName Name, SourceLocation Loc,
1559                         const MultiLevelTemplateArgumentList &TemplateArgs) {
1560   TemplateInstantiator Instantiator(*this, TemplateArgs, Loc,
1561                                     DeclarationName());
1562   return Instantiator.TransformTemplateName(Name);
1563 }
1564
1565 bool Sema::Subst(const TemplateArgumentLoc &Input, TemplateArgumentLoc &Output,
1566                  const MultiLevelTemplateArgumentList &TemplateArgs) {
1567   TemplateInstantiator Instantiator(*this, TemplateArgs, SourceLocation(),
1568                                     DeclarationName());
1569
1570   return Instantiator.TransformTemplateArgument(Input, Output);
1571 }