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

   1 //===--- SemaTemplateInstantiateDecl.cpp - C++ Template Decl 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 for declarations.
  10 //
  11 //===----------------------------------------------------------------------===/
  12 #include "clang/Sema/SemaInternal.h"
  13 #include "clang/Sema/Lookup.h"
  14 #include "clang/Sema/PrettyDeclStackTrace.h"
  15 #include "clang/Sema/Template.h"
  16 #include "clang/AST/ASTConsumer.h"
  17 #include "clang/AST/ASTContext.h"
  18 #include "clang/AST/DeclTemplate.h"
  19 #include "clang/AST/DeclVisitor.h"
  20 #include "clang/AST/DependentDiagnostic.h"
  21 #include "clang/AST/Expr.h"
  22 #include "clang/AST/ExprCXX.h"
  23 #include "clang/AST/TypeLoc.h"
  24 #include "clang/Lex/Preprocessor.h"
  25
  26 using namespace clang;
  27
  28 bool TemplateDeclInstantiator::SubstQualifier(const DeclaratorDecl *OldDecl,
  29                                               DeclaratorDecl *NewDecl) {
  30   if (!OldDecl->getQualifierLoc())
  31     return false;
  32
  33   NestedNameSpecifierLoc NewQualifierLoc
  34     = SemaRef.SubstNestedNameSpecifierLoc(OldDecl->getQualifierLoc(),
  35                                           TemplateArgs);
  36
  37   if (!NewQualifierLoc)
  38     return true;
  39
  40   NewDecl->setQualifierInfo(NewQualifierLoc);
  41   return false;
  42 }
  43
  44 bool TemplateDeclInstantiator::SubstQualifier(const TagDecl *OldDecl,
  45                                               TagDecl *NewDecl) {
  46   if (!OldDecl->getQualifierLoc())
  47     return false;
  48
  49   NestedNameSpecifierLoc NewQualifierLoc
  50   = SemaRef.SubstNestedNameSpecifierLoc(OldDecl->getQualifierLoc(),
  51                                         TemplateArgs);
  52
  53   if (!NewQualifierLoc)
  54     return true;
  55
  56   NewDecl->setQualifierInfo(NewQualifierLoc);
  57   return false;
  58 }
  59
  60 // FIXME: Is this still too simple?
  61 void Sema::InstantiateAttrs(const MultiLevelTemplateArgumentList &TemplateArgs,
  62                             const Decl *Tmpl, Decl *New) {
  63   for (AttrVec::const_iterator i = Tmpl->attr_begin(), e = Tmpl->attr_end();
  64        i != e; ++i) {
  65     const Attr *TmplAttr = *i;
  66     // FIXME: This should be generalized to more than just the AlignedAttr.
  67     if (const AlignedAttr *Aligned = dyn_cast<AlignedAttr>(TmplAttr)) {
  68       if (Aligned->isAlignmentDependent()) {
  69         // The alignment expression is not potentially evaluated.
  70         EnterExpressionEvaluationContext Unevaluated(*this,
  71                                                      Sema::Unevaluated);
  72
  73         if (Aligned->isAlignmentExpr()) {
  74           ExprResult Result = SubstExpr(Aligned->getAlignmentExpr(),
  75                                         TemplateArgs);
  76           if (!Result.isInvalid())
  77             AddAlignedAttr(Aligned->getLocation(), New, Result.takeAs<Expr>());
  78         }
  79         else {
  80           TypeSourceInfo *Result = SubstType(Aligned->getAlignmentType(),
  81                                              TemplateArgs,
  82                                              Aligned->getLocation(),
  83                                              DeclarationName());
  84           if (Result)
  85             AddAlignedAttr(Aligned->getLocation(), New, Result);
  86         }
  87         continue;
  88       }
  89     }
  90
  91     // FIXME: Is cloning correct for all attributes?
  92     Attr *NewAttr = TmplAttr->clone(Context);
  93     New->addAttr(NewAttr);
  94   }
  95 }
  96
  97 Decl *
  98 TemplateDeclInstantiator::VisitTranslationUnitDecl(TranslationUnitDecl *D) {
  99   assert(false && "Translation units cannot be instantiated");
 100   return D;
 101 }
 102
 103 Decl *
 104 TemplateDeclInstantiator::VisitLabelDecl(LabelDecl *D) {
 105   LabelDecl *Inst = LabelDecl::Create(SemaRef.Context, Owner, D->getLocation(),
 106                                       D->getIdentifier());
 107   Owner->addDecl(Inst);
 108   return Inst;
 109 }
 110
 111 Decl *
 112 TemplateDeclInstantiator::VisitNamespaceDecl(NamespaceDecl *D) {
 113   assert(false && "Namespaces cannot be instantiated");
 114   return D;
 115 }
 116
 117 Decl *
 118 TemplateDeclInstantiator::VisitNamespaceAliasDecl(NamespaceAliasDecl *D) {
 119   NamespaceAliasDecl *Inst
 120     = NamespaceAliasDecl::Create(SemaRef.Context, Owner,
 121                                  D->getNamespaceLoc(),
 122                                  D->getAliasLoc(),
 123                                  D->getIdentifier(),
 124                                  D->getQualifierLoc(),
 125                                  D->getTargetNameLoc(),
 126                                  D->getNamespace());
 127   Owner->addDecl(Inst);
 128   return Inst;
 129 }
 130
 131 Decl *TemplateDeclInstantiator::InstantiateTypedefNameDecl(TypedefNameDecl *D,
 132                                                            bool IsTypeAlias) {
 133   bool Invalid = false;
 134   TypeSourceInfo *DI = D->getTypeSourceInfo();
 135   if (DI->getType()->isInstantiationDependentType() ||
 136       DI->getType()->isVariablyModifiedType()) {
 137     DI = SemaRef.SubstType(DI, TemplateArgs,
 138                            D->getLocation(), D->getDeclName());
 139     if (!DI) {
 140       Invalid = true;
 141       DI = SemaRef.Context.getTrivialTypeSourceInfo(SemaRef.Context.IntTy);
 142     }
 143   } else {
 144     SemaRef.MarkDeclarationsReferencedInType(D->getLocation(), DI->getType());
 145   }
 146
 147   // Create the new typedef
 148   TypedefNameDecl *Typedef;
 149   if (IsTypeAlias)
 150     Typedef = TypeAliasDecl::Create(SemaRef.Context, Owner, D->getLocStart(),
 151                                     D->getLocation(), D->getIdentifier(), DI);
 152   else
 153     Typedef = TypedefDecl::Create(SemaRef.Context, Owner, D->getLocStart(),
 154                                   D->getLocation(), D->getIdentifier(), DI);
 155   if (Invalid)
 156     Typedef->setInvalidDecl();
 157
 158   // If the old typedef was the name for linkage purposes of an anonymous
 159   // tag decl, re-establish that relationship for the new typedef.
 160   if (const TagType *oldTagType = D->getUnderlyingType()->getAs<TagType>()) {
 161     TagDecl *oldTag = oldTagType->getDecl();
 162     if (oldTag->getTypedefNameForAnonDecl() == D) {
 163       TagDecl *newTag = DI->getType()->castAs<TagType>()->getDecl();
 164       assert(!newTag->getIdentifier() && !newTag->getTypedefNameForAnonDecl());
 165       newTag->setTypedefNameForAnonDecl(Typedef);
 166     }
 167   }
 168
 169   if (TypedefNameDecl *Prev = D->getPreviousDeclaration()) {
 170     NamedDecl *InstPrev = SemaRef.FindInstantiatedDecl(D->getLocation(), Prev,
 171                                                        TemplateArgs);
 172     if (!InstPrev)
 173       return 0;
 174
 175     Typedef->setPreviousDeclaration(cast<TypedefNameDecl>(InstPrev));
 176   }
 177
 178   SemaRef.InstantiateAttrs(TemplateArgs, D, Typedef);
 179
 180   Typedef->setAccess(D->getAccess());
 181
 182   return Typedef;
 183 }
 184
 185 Decl *TemplateDeclInstantiator::VisitTypedefDecl(TypedefDecl *D) {
 186   Decl *Typedef = InstantiateTypedefNameDecl(D, /*IsTypeAlias=*/false);
 187   Owner->addDecl(Typedef);
 188   return Typedef;
 189 }
 190
 191 Decl *TemplateDeclInstantiator::VisitTypeAliasDecl(TypeAliasDecl *D) {
 192   Decl *Typedef = InstantiateTypedefNameDecl(D, /*IsTypeAlias=*/true);
 193   Owner->addDecl(Typedef);
 194   return Typedef;
 195 }
 196
 197 Decl *
 198 TemplateDeclInstantiator::VisitTypeAliasTemplateDecl(TypeAliasTemplateDecl *D) {
 199   // Create a local instantiation scope for this type alias template, which
 200   // will contain the instantiations of the template parameters.
 201   LocalInstantiationScope Scope(SemaRef);
 202
 203   TemplateParameterList *TempParams = D->getTemplateParameters();
 204   TemplateParameterList *InstParams = SubstTemplateParams(TempParams);
 205   if (!InstParams)
 206     return 0;
 207
 208   TypeAliasDecl *Pattern = D->getTemplatedDecl();
 209
 210   TypeAliasTemplateDecl *PrevAliasTemplate = 0;
 211   if (Pattern->getPreviousDeclaration()) {
 212     DeclContext::lookup_result Found = Owner->lookup(Pattern->getDeclName());
 213     if (Found.first != Found.second) {
 214       PrevAliasTemplate = dyn_cast<TypeAliasTemplateDecl>(*Found.first);
 215     }
 216   }
 217
 218   TypeAliasDecl *AliasInst = cast_or_null<TypeAliasDecl>(
 219     InstantiateTypedefNameDecl(Pattern, /*IsTypeAlias=*/true));
 220   if (!AliasInst)
 221     return 0;
 222
 223   TypeAliasTemplateDecl *Inst
 224     = TypeAliasTemplateDecl::Create(SemaRef.Context, Owner, D->getLocation(),
 225                                     D->getDeclName(), InstParams, AliasInst);
 226   if (PrevAliasTemplate)
 227     Inst->setPreviousDeclaration(PrevAliasTemplate);
 228
 229   Inst->setAccess(D->getAccess());
 230
 231   if (!PrevAliasTemplate)
 232     Inst->setInstantiatedFromMemberTemplate(D);
 233
 234   Owner->addDecl(Inst);
 235
 236   return Inst;
 237 }
 238
 239 /// \brief Instantiate an initializer, breaking it into separate
 240 /// initialization arguments.
 241 ///
 242 /// \param S The semantic analysis object.
 243 ///
 244 /// \param Init The initializer to instantiate.
 245 ///
 246 /// \param TemplateArgs Template arguments to be substituted into the
 247 /// initializer.
 248 ///
 249 /// \param NewArgs Will be filled in with the instantiation arguments.
 250 ///
 251 /// \returns true if an error occurred, false otherwise
 252 static bool InstantiateInitializer(Sema &S, Expr *Init,
 253                             const MultiLevelTemplateArgumentList &TemplateArgs,
 254                                    SourceLocation &LParenLoc,
 255                                    ASTOwningVector<Expr*> &NewArgs,
 256                                    SourceLocation &RParenLoc) {
 257   NewArgs.clear();
 258   LParenLoc = SourceLocation();
 259   RParenLoc = SourceLocation();
 260
 261   if (!Init)
 262     return false;
 263
 264   if (ExprWithCleanups *ExprTemp = dyn_cast<ExprWithCleanups>(Init))
 265     Init = ExprTemp->getSubExpr();
 266
 267   while (CXXBindTemporaryExpr *Binder = dyn_cast<CXXBindTemporaryExpr>(Init))
 268     Init = Binder->getSubExpr();
 269
 270   if (ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(Init))
 271     Init = ICE->getSubExprAsWritten();
 272
 273   if (ParenListExpr *ParenList = dyn_cast<ParenListExpr>(Init)) {
 274     LParenLoc = ParenList->getLParenLoc();
 275     RParenLoc = ParenList->getRParenLoc();
 276     return S.SubstExprs(ParenList->getExprs(), ParenList->getNumExprs(),
 277                         true, TemplateArgs, NewArgs);
 278   }
 279
 280   if (CXXConstructExpr *Construct = dyn_cast<CXXConstructExpr>(Init)) {
 281     if (!isa<CXXTemporaryObjectExpr>(Construct)) {
 282       if (S.SubstExprs(Construct->getArgs(), Construct->getNumArgs(), true,
 283                        TemplateArgs, NewArgs))
 284         return true;
 285
 286       // FIXME: Fake locations!
 287       LParenLoc = S.PP.getLocForEndOfToken(Init->getLocStart());
 288       RParenLoc = LParenLoc;
 289       return false;
 290     }
 291   }
 292
 293   ExprResult Result = S.SubstExpr(Init, TemplateArgs);
 294   if (Result.isInvalid())
 295     return true;
 296
 297   NewArgs.push_back(Result.takeAs<Expr>());
 298   return false;
 299 }
 300
 301 Decl *TemplateDeclInstantiator::VisitVarDecl(VarDecl *D) {
 302   // If this is the variable for an anonymous struct or union,
 303   // instantiate the anonymous struct/union type first.
 304   if (const RecordType *RecordTy = D->getType()->getAs<RecordType>())
 305     if (RecordTy->getDecl()->isAnonymousStructOrUnion())
 306       if (!VisitCXXRecordDecl(cast<CXXRecordDecl>(RecordTy->getDecl())))
 307         return 0;
 308
 309   // Do substitution on the type of the declaration
 310   TypeSourceInfo *DI = SemaRef.SubstType(D->getTypeSourceInfo(),
 311                                          TemplateArgs,
 312                                          D->getTypeSpecStartLoc(),
 313                                          D->getDeclName());
 314   if (!DI)
 315     return 0;
 316
 317   if (DI->getType()->isFunctionType()) {
 318     SemaRef.Diag(D->getLocation(), diag::err_variable_instantiates_to_function)
 319       << D->isStaticDataMember() << DI->getType();
 320     return 0;
 321   }
 322
 323   // Build the instantiated declaration
 324   VarDecl *Var = VarDecl::Create(SemaRef.Context, Owner,
 325                                  D->getInnerLocStart(),
 326                                  D->getLocation(), D->getIdentifier(),
 327                                  DI->getType(), DI,
 328                                  D->getStorageClass(),
 329                                  D->getStorageClassAsWritten());
 330   Var->setThreadSpecified(D->isThreadSpecified());
 331   Var->setCXXDirectInitializer(D->hasCXXDirectInitializer());
 332   Var->setCXXForRangeDecl(D->isCXXForRangeDecl());
 333
 334   // Substitute the nested name specifier, if any.
 335   if (SubstQualifier(D, Var))
 336     return 0;
 337
 338   // If we are instantiating a static data member defined
 339   // out-of-line, the instantiation will have the same lexical
 340   // context (which will be a namespace scope) as the template.
 341   if (D->isOutOfLine())
 342     Var->setLexicalDeclContext(D->getLexicalDeclContext());
 343
 344   Var->setAccess(D->getAccess());
 345
 346   if (!D->isStaticDataMember()) {
 347     Var->setUsed(D->isUsed(false));
 348     Var->setReferenced(D->isReferenced());
 349   }
 350
 351   // FIXME: In theory, we could have a previous declaration for variables that
 352   // are not static data members.
 353   bool Redeclaration = false;
 354   // FIXME: having to fake up a LookupResult is dumb.
 355   LookupResult Previous(SemaRef, Var->getDeclName(), Var->getLocation(),
 356                         Sema::LookupOrdinaryName, Sema::ForRedeclaration);
 357   if (D->isStaticDataMember())
 358     SemaRef.LookupQualifiedName(Previous, Owner, false);
 359   SemaRef.CheckVariableDeclaration(Var, Previous, Redeclaration);
 360
 361   if (D->isOutOfLine()) {
 362     if (!D->isStaticDataMember())
 363       D->getLexicalDeclContext()->addDecl(Var);
 364     Owner->makeDeclVisibleInContext(Var);
 365   } else {
 366     Owner->addDecl(Var);
 367     if (Owner->isFunctionOrMethod())
 368       SemaRef.CurrentInstantiationScope->InstantiatedLocal(D, Var);
 369   }
 370   SemaRef.InstantiateAttrs(TemplateArgs, D, Var);
 371
 372   // Link instantiations of static data members back to the template from
 373   // which they were instantiated.
 374   if (Var->isStaticDataMember())
 375     SemaRef.Context.setInstantiatedFromStaticDataMember(Var, D,
 376                                                      TSK_ImplicitInstantiation);
 377
 378   if (Var->getAnyInitializer()) {
 379     // We already have an initializer in the class.
 380   } else if (D->getInit()) {
 381     if (Var->isStaticDataMember() && !D->isOutOfLine())
 382       SemaRef.PushExpressionEvaluationContext(Sema::Unevaluated);
 383     else
 384       SemaRef.PushExpressionEvaluationContext(Sema::PotentiallyEvaluated);
 385
 386     // Instantiate the initializer.
 387     SourceLocation LParenLoc, RParenLoc;
 388     ASTOwningVector<Expr*> InitArgs(SemaRef);
 389     if (!InstantiateInitializer(SemaRef, D->getInit(), TemplateArgs, LParenLoc,
 390                                 InitArgs, RParenLoc)) {
 391       bool TypeMayContainAuto = true;
 392       // Attach the initializer to the declaration, if we have one.
 393       if (InitArgs.size() == 0)
 394         SemaRef.ActOnUninitializedDecl(Var, TypeMayContainAuto);
 395       else if (D->hasCXXDirectInitializer()) {
 396         // Add the direct initializer to the declaration.
 397         SemaRef.AddCXXDirectInitializerToDecl(Var,
 398                                               LParenLoc,
 399                                               move_arg(InitArgs),
 400                                               RParenLoc,
 401                                               TypeMayContainAuto);
 402       } else {
 403         assert(InitArgs.size() == 1);
 404         Expr *Init = InitArgs.take()[0];
 405         SemaRef.AddInitializerToDecl(Var, Init, false, TypeMayContainAuto);
 406       }
 407     } else {
 408       // FIXME: Not too happy about invalidating the declaration
 409       // because of a bogus initializer.
 410       Var->setInvalidDecl();
 411     }
 412
 413     SemaRef.PopExpressionEvaluationContext();
 414   } else if ((!Var->isStaticDataMember() || Var->isOutOfLine()) &&
 415              !Var->isCXXForRangeDecl())
 416     SemaRef.ActOnUninitializedDecl(Var, false);
 417
 418   // Diagnose unused local variables with dependent types, where the diagnostic
 419   // will have been deferred.
 420   if (!Var->isInvalidDecl() && Owner->isFunctionOrMethod() && !Var->isUsed() &&
 421       D->getType()->isDependentType())
 422     SemaRef.DiagnoseUnusedDecl(Var);
 423
 424   return Var;
 425 }
 426
 427 Decl *TemplateDeclInstantiator::VisitAccessSpecDecl(AccessSpecDecl *D) {
 428   AccessSpecDecl* AD
 429     = AccessSpecDecl::Create(SemaRef.Context, D->getAccess(), Owner,
 430                              D->getAccessSpecifierLoc(), D->getColonLoc());
 431   Owner->addHiddenDecl(AD);
 432   return AD;
 433 }
 434
 435 Decl *TemplateDeclInstantiator::VisitFieldDecl(FieldDecl *D) {
 436   bool Invalid = false;
 437   TypeSourceInfo *DI = D->getTypeSourceInfo();
 438   if (DI->getType()->isInstantiationDependentType() ||
 439       DI->getType()->isVariablyModifiedType())  {
 440     DI = SemaRef.SubstType(DI, TemplateArgs,
 441                            D->getLocation(), D->getDeclName());
 442     if (!DI) {
 443       DI = D->getTypeSourceInfo();
 444       Invalid = true;
 445     } else if (DI->getType()->isFunctionType()) {
 446       // C++ [temp.arg.type]p3:
 447       //   If a declaration acquires a function type through a type
 448       //   dependent on a template-parameter and this causes a
 449       //   declaration that does not use the syntactic form of a
 450       //   function declarator to have function type, the program is
 451       //   ill-formed.
 452       SemaRef.Diag(D->getLocation(), diag::err_field_instantiates_to_function)
 453         << DI->getType();
 454       Invalid = true;
 455     }
 456   } else {
 457     SemaRef.MarkDeclarationsReferencedInType(D->getLocation(), DI->getType());
 458   }
 459
 460   Expr *BitWidth = D->getBitWidth();
 461   if (Invalid)
 462     BitWidth = 0;
 463   else if (BitWidth) {
 464     // The bit-width expression is not potentially evaluated.
 465     EnterExpressionEvaluationContext Unevaluated(SemaRef, Sema::Unevaluated);
 466
 467     ExprResult InstantiatedBitWidth
 468       = SemaRef.SubstExpr(BitWidth, TemplateArgs);
 469     if (InstantiatedBitWidth.isInvalid()) {
 470       Invalid = true;
 471       BitWidth = 0;
 472     } else
 473       BitWidth = InstantiatedBitWidth.takeAs<Expr>();
 474   }
 475
 476   FieldDecl *Field = SemaRef.CheckFieldDecl(D->getDeclName(),
 477                                             DI->getType(), DI,
 478                                             cast<RecordDecl>(Owner),
 479                                             D->getLocation(),
 480                                             D->isMutable(),
 481                                             BitWidth,
 482                                             D->hasInClassInitializer(),
 483                                             D->getTypeSpecStartLoc(),
 484                                             D->getAccess(),
 485                                             0);
 486   if (!Field) {
 487     cast<Decl>(Owner)->setInvalidDecl();
 488     return 0;
 489   }
 490
 491   SemaRef.InstantiateAttrs(TemplateArgs, D, Field);
 492
 493   if (Invalid)
 494     Field->setInvalidDecl();
 495
 496   if (!Field->getDeclName()) {
 497     // Keep track of where this decl came from.
 498     SemaRef.Context.setInstantiatedFromUnnamedFieldDecl(Field, D);
 499   }
 500   if (CXXRecordDecl *Parent= dyn_cast<CXXRecordDecl>(Field->getDeclContext())) {
 501     if (Parent->isAnonymousStructOrUnion() &&
 502         Parent->getRedeclContext()->isFunctionOrMethod())
 503       SemaRef.CurrentInstantiationScope->InstantiatedLocal(D, Field);
 504   }
 505
 506   Field->setImplicit(D->isImplicit());
 507   Field->setAccess(D->getAccess());
 508   Owner->addDecl(Field);
 509
 510   return Field;
 511 }
 512
 513 Decl *TemplateDeclInstantiator::VisitIndirectFieldDecl(IndirectFieldDecl *D) {
 514   NamedDecl **NamedChain =
 515     new (SemaRef.Context)NamedDecl*[D->getChainingSize()];
 516
 517   int i = 0;
 518   for (IndirectFieldDecl::chain_iterator PI =
 519        D->chain_begin(), PE = D->chain_end();
 520        PI != PE; ++PI) {
 521     NamedDecl *Next = SemaRef.FindInstantiatedDecl(D->getLocation(), *PI,
 522                                               TemplateArgs);
 523     if (!Next)
 524       return 0;
 525
 526     NamedChain[i++] = Next;
 527   }
 528
 529   QualType T = cast<FieldDecl>(NamedChain[i-1])->getType();
 530   IndirectFieldDecl* IndirectField
 531     = IndirectFieldDecl::Create(SemaRef.Context, Owner, D->getLocation(),
 532                                 D->getIdentifier(), T,
 533                                 NamedChain, D->getChainingSize());
 534
 535
 536   IndirectField->setImplicit(D->isImplicit());
 537   IndirectField->setAccess(D->getAccess());
 538   Owner->addDecl(IndirectField);
 539   return IndirectField;
 540 }
 541
 542 Decl *TemplateDeclInstantiator::VisitFriendDecl(FriendDecl *D) {
 543   // Handle friend type expressions by simply substituting template
 544   // parameters into the pattern type and checking the result.
 545   if (TypeSourceInfo *Ty = D->getFriendType()) {
 546     TypeSourceInfo *InstTy;
 547     // If this is an unsupported friend, don't bother substituting template
 548     // arguments into it. The actual type referred to won't be used by any
 549     // parts of Clang, and may not be valid for instantiating. Just use the
 550     // same info for the instantiated friend.
 551     if (D->isUnsupportedFriend()) {
 552       InstTy = Ty;
 553     } else {
 554       InstTy = SemaRef.SubstType(Ty, TemplateArgs,
 555                                  D->getLocation(), DeclarationName());
 556     }
 557     if (!InstTy)
 558       return 0;
 559
 560     FriendDecl *FD = SemaRef.CheckFriendTypeDecl(D->getFriendLoc(), InstTy);
 561     if (!FD)
 562       return 0;
 563
 564     FD->setAccess(AS_public);
 565     FD->setUnsupportedFriend(D->isUnsupportedFriend());
 566     Owner->addDecl(FD);
 567     return FD;
 568   }
 569
 570   NamedDecl *ND = D->getFriendDecl();
 571   assert(ND && "friend decl must be a decl or a type!");
 572
 573   // All of the Visit implementations for the various potential friend
 574   // declarations have to be carefully written to work for friend
 575   // objects, with the most important detail being that the target
 576   // decl should almost certainly not be placed in Owner.
 577   Decl *NewND = Visit(ND);
 578   if (!NewND) return 0;
 579
 580   FriendDecl *FD =
 581     FriendDecl::Create(SemaRef.Context, Owner, D->getLocation(),
 582                        cast<NamedDecl>(NewND), D->getFriendLoc());
 583   FD->setAccess(AS_public);
 584   FD->setUnsupportedFriend(D->isUnsupportedFriend());
 585   Owner->addDecl(FD);
 586   return FD;
 587 }
 588
 589 Decl *TemplateDeclInstantiator::VisitStaticAssertDecl(StaticAssertDecl *D) {
 590   Expr *AssertExpr = D->getAssertExpr();
 591
 592   // The expression in a static assertion is not potentially evaluated.
 593   EnterExpressionEvaluationContext Unevaluated(SemaRef, Sema::Unevaluated);
 594
 595   ExprResult InstantiatedAssertExpr
 596     = SemaRef.SubstExpr(AssertExpr, TemplateArgs);
 597   if (InstantiatedAssertExpr.isInvalid())
 598     return 0;
 599
 600   ExprResult Message(D->getMessage());
 601   D->getMessage();
 602   return SemaRef.ActOnStaticAssertDeclaration(D->getLocation(),
 603                                               InstantiatedAssertExpr.get(),
 604                                               Message.get(),
 605                                               D->getRParenLoc());
 606 }
 607
 608 Decl *TemplateDeclInstantiator::VisitEnumDecl(EnumDecl *D) {
 609   EnumDecl *Enum = EnumDecl::Create(SemaRef.Context, Owner, D->getLocStart(),
 610                                     D->getLocation(), D->getIdentifier(),
 611                                     /*PrevDecl=*/0, D->isScoped(),
 612                                     D->isScopedUsingClassTag(), D->isFixed());
 613   if (D->isFixed()) {
 614     if (TypeSourceInfo* TI = D->getIntegerTypeSourceInfo()) {
 615       // If we have type source information for the underlying type, it means it
 616       // has been explicitly set by the user. Perform substitution on it before
 617       // moving on.
 618       SourceLocation UnderlyingLoc = TI->getTypeLoc().getBeginLoc();
 619       Enum->setIntegerTypeSourceInfo(SemaRef.SubstType(TI,
 620                                                        TemplateArgs,
 621                                                        UnderlyingLoc,
 622                                                        DeclarationName()));
 623
 624       if (!Enum->getIntegerTypeSourceInfo())
 625         Enum->setIntegerType(SemaRef.Context.IntTy);
 626     }
 627     else {
 628       assert(!D->getIntegerType()->isDependentType()
 629              && "Dependent type without type source info");
 630       Enum->setIntegerType(D->getIntegerType());
 631     }
 632   }
 633
 634   SemaRef.InstantiateAttrs(TemplateArgs, D, Enum);
 635
 636   Enum->setInstantiationOfMemberEnum(D);
 637   Enum->setAccess(D->getAccess());
 638   if (SubstQualifier(D, Enum)) return 0;
 639   Owner->addDecl(Enum);
 640   Enum->startDefinition();
 641
 642   if (D->getDeclContext()->isFunctionOrMethod())
 643     SemaRef.CurrentInstantiationScope->InstantiatedLocal(D, Enum);
 644
 645   llvm::SmallVector<Decl*, 4> Enumerators;
 646
 647   EnumConstantDecl *LastEnumConst = 0;
 648   for (EnumDecl::enumerator_iterator EC = D->enumerator_begin(),
 649          ECEnd = D->enumerator_end();
 650        EC != ECEnd; ++EC) {
 651     // The specified value for the enumerator.
 652     ExprResult Value = SemaRef.Owned((Expr *)0);
 653     if (Expr *UninstValue = EC->getInitExpr()) {
 654       // The enumerator's value expression is not potentially evaluated.
 655       EnterExpressionEvaluationContext Unevaluated(SemaRef,
 656                                                    Sema::Unevaluated);
 657
 658       Value = SemaRef.SubstExpr(UninstValue, TemplateArgs);
 659     }
 660
 661     // Drop the initial value and continue.
 662     bool isInvalid = false;
 663     if (Value.isInvalid()) {
 664       Value = SemaRef.Owned((Expr *)0);
 665       isInvalid = true;
 666     }
 667
 668     EnumConstantDecl *EnumConst
 669       = SemaRef.CheckEnumConstant(Enum, LastEnumConst,
 670                                   EC->getLocation(), EC->getIdentifier(),
 671                                   Value.get());
 672
 673     if (isInvalid) {
 674       if (EnumConst)
 675         EnumConst->setInvalidDecl();
 676       Enum->setInvalidDecl();
 677     }
 678
 679     if (EnumConst) {
 680       SemaRef.InstantiateAttrs(TemplateArgs, *EC, EnumConst);
 681
 682       EnumConst->setAccess(Enum->getAccess());
 683       Enum->addDecl(EnumConst);
 684       Enumerators.push_back(EnumConst);
 685       LastEnumConst = EnumConst;
 686
 687       if (D->getDeclContext()->isFunctionOrMethod()) {
 688         // If the enumeration is within a function or method, record the enum
 689         // constant as a local.
 690         SemaRef.CurrentInstantiationScope->InstantiatedLocal(*EC, EnumConst);
 691       }
 692     }
 693   }
 694
 695   // FIXME: Fixup LBraceLoc and RBraceLoc
 696   // FIXME: Empty Scope and AttributeList (required to handle attribute packed).
 697   SemaRef.ActOnEnumBody(Enum->getLocation(), SourceLocation(), SourceLocation(),
 698                         Enum,
 699                         Enumerators.data(), Enumerators.size(),
 700                         0, 0);
 701
 702   return Enum;
 703 }
 704
 705 Decl *TemplateDeclInstantiator::VisitEnumConstantDecl(EnumConstantDecl *D) {
 706   assert(false && "EnumConstantDecls can only occur within EnumDecls.");
 707   return 0;
 708 }
 709
 710 Decl *TemplateDeclInstantiator::VisitClassTemplateDecl(ClassTemplateDecl *D) {
 711   bool isFriend = (D->getFriendObjectKind() != Decl::FOK_None);
 712
 713   // Create a local instantiation scope for this class template, which
 714   // will contain the instantiations of the template parameters.
 715   LocalInstantiationScope Scope(SemaRef);
 716   TemplateParameterList *TempParams = D->getTemplateParameters();
 717   TemplateParameterList *InstParams = SubstTemplateParams(TempParams);
 718   if (!InstParams)
 719     return NULL;
 720
 721   CXXRecordDecl *Pattern = D->getTemplatedDecl();
 722
 723   // Instantiate the qualifier.  We have to do this first in case
 724   // we're a friend declaration, because if we are then we need to put
 725   // the new declaration in the appropriate context.
 726   NestedNameSpecifierLoc QualifierLoc = Pattern->getQualifierLoc();
 727   if (QualifierLoc) {
 728     QualifierLoc = SemaRef.SubstNestedNameSpecifierLoc(QualifierLoc,
 729                                                        TemplateArgs);
 730     if (!QualifierLoc)
 731       return 0;
 732   }
 733
 734   CXXRecordDecl *PrevDecl = 0;
 735   ClassTemplateDecl *PrevClassTemplate = 0;
 736
 737   if (!isFriend && Pattern->getPreviousDeclaration()) {
 738     DeclContext::lookup_result Found = Owner->lookup(Pattern->getDeclName());
 739     if (Found.first != Found.second) {
 740       PrevClassTemplate = dyn_cast<ClassTemplateDecl>(*Found.first);
 741       if (PrevClassTemplate)
 742         PrevDecl = PrevClassTemplate->getTemplatedDecl();
 743     }
 744   }
 745
 746   // If this isn't a friend, then it's a member template, in which
 747   // case we just want to build the instantiation in the
 748   // specialization.  If it is a friend, we want to build it in
 749   // the appropriate context.
 750   DeclContext *DC = Owner;
 751   if (isFriend) {
 752     if (QualifierLoc) {
 753       CXXScopeSpec SS;
 754       SS.Adopt(QualifierLoc);
 755       DC = SemaRef.computeDeclContext(SS);
 756       if (!DC) return 0;
 757     } else {
 758       DC = SemaRef.FindInstantiatedContext(Pattern->getLocation(),
 759                                            Pattern->getDeclContext(),
 760                                            TemplateArgs);
 761     }
 762
 763     // Look for a previous declaration of the template in the owning
 764     // context.
 765     LookupResult R(SemaRef, Pattern->getDeclName(), Pattern->getLocation(),
 766                    Sema::LookupOrdinaryName, Sema::ForRedeclaration);
 767     SemaRef.LookupQualifiedName(R, DC);
 768
 769     if (R.isSingleResult()) {
 770       PrevClassTemplate = R.getAsSingle<ClassTemplateDecl>();
 771       if (PrevClassTemplate)
 772         PrevDecl = PrevClassTemplate->getTemplatedDecl();
 773     }
 774
 775     if (!PrevClassTemplate && QualifierLoc) {
 776       SemaRef.Diag(Pattern->getLocation(), diag::err_not_tag_in_scope)
 777         << D->getTemplatedDecl()->getTagKind() << Pattern->getDeclName() << DC
 778         << QualifierLoc.getSourceRange();
 779       return 0;
 780     }
 781
 782     bool AdoptedPreviousTemplateParams = false;
 783     if (PrevClassTemplate) {
 784       bool Complain = true;
 785
 786       // HACK: libstdc++ 4.2.1 contains an ill-formed friend class
 787       // template for struct std::tr1::__detail::_Map_base, where the
 788       // template parameters of the friend declaration don't match the
 789       // template parameters of the original declaration. In this one
 790       // case, we don't complain about the ill-formed friend
 791       // declaration.
 792       if (isFriend && Pattern->getIdentifier() &&
 793           Pattern->getIdentifier()->isStr("_Map_base") &&
 794           DC->isNamespace() &&
 795           cast<NamespaceDecl>(DC)->getIdentifier() &&
 796           cast<NamespaceDecl>(DC)->getIdentifier()->isStr("__detail")) {
 797         DeclContext *DCParent = DC->getParent();
 798         if (DCParent->isNamespace() &&
 799             cast<NamespaceDecl>(DCParent)->getIdentifier() &&
 800             cast<NamespaceDecl>(DCParent)->getIdentifier()->isStr("tr1")) {
 801           DeclContext *DCParent2 = DCParent->getParent();
 802           if (DCParent2->isNamespace() &&
 803               cast<NamespaceDecl>(DCParent2)->getIdentifier() &&
 804               cast<NamespaceDecl>(DCParent2)->getIdentifier()->isStr("std") &&
 805               DCParent2->getParent()->isTranslationUnit())
 806             Complain = false;
 807         }
 808       }
 809
 810       TemplateParameterList *PrevParams
 811         = PrevClassTemplate->getTemplateParameters();
 812
 813       // Make sure the parameter lists match.
 814       if (!SemaRef.TemplateParameterListsAreEqual(InstParams, PrevParams,
 815                                                   Complain,
 816                                                   Sema::TPL_TemplateMatch)) {
 817         if (Complain)
 818           return 0;
 819
 820         AdoptedPreviousTemplateParams = true;
 821         InstParams = PrevParams;
 822       }
 823
 824       // Do some additional validation, then merge default arguments
 825       // from the existing declarations.
 826       if (!AdoptedPreviousTemplateParams &&
 827           SemaRef.CheckTemplateParameterList(InstParams, PrevParams,
 828                                              Sema::TPC_ClassTemplate))
 829         return 0;
 830     }
 831   }
 832
 833   CXXRecordDecl *RecordInst
 834     = CXXRecordDecl::Create(SemaRef.Context, Pattern->getTagKind(), DC,
 835                             Pattern->getLocStart(), Pattern->getLocation(),
 836                             Pattern->getIdentifier(), PrevDecl,
 837                             /*DelayTypeCreation=*/true);
 838
 839   if (QualifierLoc)
 840     RecordInst->setQualifierInfo(QualifierLoc);
 841
 842   ClassTemplateDecl *Inst
 843     = ClassTemplateDecl::Create(SemaRef.Context, DC, D->getLocation(),
 844                                 D->getIdentifier(), InstParams, RecordInst,
 845                                 PrevClassTemplate);
 846   RecordInst->setDescribedClassTemplate(Inst);
 847
 848   if (isFriend) {
 849     if (PrevClassTemplate)
 850       Inst->setAccess(PrevClassTemplate->getAccess());
 851     else
 852       Inst->setAccess(D->getAccess());
 853
 854     Inst->setObjectOfFriendDecl(PrevClassTemplate != 0);
 855     // TODO: do we want to track the instantiation progeny of this
 856     // friend target decl?
 857   } else {
 858     Inst->setAccess(D->getAccess());
 859     if (!PrevClassTemplate)
 860       Inst->setInstantiatedFromMemberTemplate(D);
 861   }
 862
 863   // Trigger creation of the type for the instantiation.
 864   SemaRef.Context.getInjectedClassNameType(RecordInst,
 865                                     Inst->getInjectedClassNameSpecialization());
 866
 867   // Finish handling of friends.
 868   if (isFriend) {
 869     DC->makeDeclVisibleInContext(Inst, /*Recoverable*/ false);
 870     return Inst;
 871   }
 872
 873   Owner->addDecl(Inst);
 874
 875   if (!PrevClassTemplate) {
 876     // Queue up any out-of-line partial specializations of this member
 877     // class template; the client will force their instantiation once
 878     // the enclosing class has been instantiated.
 879     llvm::SmallVector<ClassTemplatePartialSpecializationDecl *, 4> PartialSpecs;
 880     D->getPartialSpecializations(PartialSpecs);
 881     for (unsigned I = 0, N = PartialSpecs.size(); I != N; ++I)
 882       if (PartialSpecs[I]->isOutOfLine())
 883         OutOfLinePartialSpecs.push_back(std::make_pair(Inst, PartialSpecs[I]));
 884   }
 885
 886   return Inst;
 887 }
 888
 889 Decl *
 890 TemplateDeclInstantiator::VisitClassTemplatePartialSpecializationDecl(
 891                                    ClassTemplatePartialSpecializationDecl *D) {
 892   ClassTemplateDecl *ClassTemplate = D->getSpecializedTemplate();
 893
 894   // Lookup the already-instantiated declaration in the instantiation
 895   // of the class template and return that.
 896   DeclContext::lookup_result Found
 897     = Owner->lookup(ClassTemplate->getDeclName());
 898   if (Found.first == Found.second)
 899     return 0;
 900
 901   ClassTemplateDecl *InstClassTemplate
 902     = dyn_cast<ClassTemplateDecl>(*Found.first);
 903   if (!InstClassTemplate)
 904     return 0;
 905
 906   if (ClassTemplatePartialSpecializationDecl *Result
 907         = InstClassTemplate->findPartialSpecInstantiatedFromMember(D))
 908     return Result;
 909
 910   return InstantiateClassTemplatePartialSpecialization(InstClassTemplate, D);
 911 }
 912
 913 Decl *
 914 TemplateDeclInstantiator::VisitFunctionTemplateDecl(FunctionTemplateDecl *D) {
 915   // Create a local instantiation scope for this function template, which
 916   // will contain the instantiations of the template parameters and then get
 917   // merged with the local instantiation scope for the function template
 918   // itself.
 919   LocalInstantiationScope Scope(SemaRef);
 920
 921   TemplateParameterList *TempParams = D->getTemplateParameters();
 922   TemplateParameterList *InstParams = SubstTemplateParams(TempParams);
 923   if (!InstParams)
 924     return NULL;
 925
 926   FunctionDecl *Instantiated = 0;
 927   if (CXXMethodDecl *DMethod = dyn_cast<CXXMethodDecl>(D->getTemplatedDecl()))
 928     Instantiated = cast_or_null<FunctionDecl>(VisitCXXMethodDecl(DMethod,
 929                                                                  InstParams));
 930   else
 931     Instantiated = cast_or_null<FunctionDecl>(VisitFunctionDecl(
 932                                                           D->getTemplatedDecl(),
 933                                                                 InstParams));
 934
 935   if (!Instantiated)
 936     return 0;
 937
 938   Instantiated->setAccess(D->getAccess());
 939
 940   // Link the instantiated function template declaration to the function
 941   // template from which it was instantiated.
 942   FunctionTemplateDecl *InstTemplate
 943     = Instantiated->getDescribedFunctionTemplate();
 944   InstTemplate->setAccess(D->getAccess());
 945   assert(InstTemplate &&
 946          "VisitFunctionDecl/CXXMethodDecl didn't create a template!");
 947
 948   bool isFriend = (InstTemplate->getFriendObjectKind() != Decl::FOK_None);
 949
 950   // Link the instantiation back to the pattern *unless* this is a
 951   // non-definition friend declaration.
 952   if (!InstTemplate->getInstantiatedFromMemberTemplate() &&
 953       !(isFriend && !D->getTemplatedDecl()->isThisDeclarationADefinition()))
 954     InstTemplate->setInstantiatedFromMemberTemplate(D);
 955
 956   // Make declarations visible in the appropriate context.
 957   if (!isFriend)
 958     Owner->addDecl(InstTemplate);
 959
 960   return InstTemplate;
 961 }
 962
 963 Decl *TemplateDeclInstantiator::VisitCXXRecordDecl(CXXRecordDecl *D) {
 964   CXXRecordDecl *PrevDecl = 0;
 965   if (D->isInjectedClassName())
 966     PrevDecl = cast<CXXRecordDecl>(Owner);
 967   else if (D->getPreviousDeclaration()) {
 968     NamedDecl *Prev = SemaRef.FindInstantiatedDecl(D->getLocation(),
 969                                                    D->getPreviousDeclaration(),
 970                                                    TemplateArgs);
 971     if (!Prev) return 0;
 972     PrevDecl = cast<CXXRecordDecl>(Prev);
 973   }
 974
 975   CXXRecordDecl *Record
 976     = CXXRecordDecl::Create(SemaRef.Context, D->getTagKind(), Owner,
 977                             D->getLocStart(), D->getLocation(),
 978                             D->getIdentifier(), PrevDecl);
 979
 980   // Substitute the nested name specifier, if any.
 981   if (SubstQualifier(D, Record))
 982     return 0;
 983
 984   Record->setImplicit(D->isImplicit());
 985   // FIXME: Check against AS_none is an ugly hack to work around the issue that
 986   // the tag decls introduced by friend class declarations don't have an access
 987   // specifier. Remove once this area of the code gets sorted out.
 988   if (D->getAccess() != AS_none)
 989     Record->setAccess(D->getAccess());
 990   if (!D->isInjectedClassName())
 991     Record->setInstantiationOfMemberClass(D, TSK_ImplicitInstantiation);
 992
 993   // If the original function was part of a friend declaration,
 994   // inherit its namespace state.
 995   if (Decl::FriendObjectKind FOK = D->getFriendObjectKind())
 996     Record->setObjectOfFriendDecl(FOK == Decl::FOK_Declared);
 997
 998   // Make sure that anonymous structs and unions are recorded.
 999   if (D->isAnonymousStructOrUnion()) {
1000     Record->setAnonymousStructOrUnion(true);
1001     if (Record->getDeclContext()->getRedeclContext()->isFunctionOrMethod())
1002       SemaRef.CurrentInstantiationScope->InstantiatedLocal(D, Record);
1003   }
1004
1005   Owner->addDecl(Record);
1006   return Record;
1007 }
1008
1009 /// Normal class members are of more specific types and therefore
1010 /// don't make it here.  This function serves two purposes:
1011 ///   1) instantiating function templates
1012 ///   2) substituting friend declarations
1013 /// FIXME: preserve function definitions in case #2
1014 Decl *TemplateDeclInstantiator::VisitFunctionDecl(FunctionDecl *D,
1015                                        TemplateParameterList *TemplateParams) {
1016   // Check whether there is already a function template specialization for
1017   // this declaration.
1018   FunctionTemplateDecl *FunctionTemplate = D->getDescribedFunctionTemplate();
1019   void *InsertPos = 0;
1020   if (FunctionTemplate && !TemplateParams) {
1021     std::pair<const TemplateArgument *, unsigned> Innermost
1022       = TemplateArgs.getInnermost();
1023
1024     FunctionDecl *SpecFunc
1025       = FunctionTemplate->findSpecialization(Innermost.first, Innermost.second,
1026                                              InsertPos);
1027
1028     // If we already have a function template specialization, return it.
1029     if (SpecFunc)
1030       return SpecFunc;
1031   }
1032
1033   bool isFriend;
1034   if (FunctionTemplate)
1035     isFriend = (FunctionTemplate->getFriendObjectKind() != Decl::FOK_None);
1036   else
1037     isFriend = (D->getFriendObjectKind() != Decl::FOK_None);
1038
1039   bool MergeWithParentScope = (TemplateParams != 0) ||
1040     Owner->isFunctionOrMethod() ||
1041     !(isa<Decl>(Owner) &&
1042       cast<Decl>(Owner)->isDefinedOutsideFunctionOrMethod());
1043   LocalInstantiationScope Scope(SemaRef, MergeWithParentScope);
1044
1045   llvm::SmallVector<ParmVarDecl *, 4> Params;
1046   TypeSourceInfo *TInfo = D->getTypeSourceInfo();
1047   TInfo = SubstFunctionType(D, Params);
1048   if (!TInfo)
1049     return 0;
1050   QualType T = TInfo->getType();
1051
1052   NestedNameSpecifierLoc QualifierLoc = D->getQualifierLoc();
1053   if (QualifierLoc) {
1054     QualifierLoc = SemaRef.SubstNestedNameSpecifierLoc(QualifierLoc,
1055                                                        TemplateArgs);
1056     if (!QualifierLoc)
1057       return 0;
1058   }
1059
1060   // If we're instantiating a local function declaration, put the result
1061   // in the owner;  otherwise we need to find the instantiated context.
1062   DeclContext *DC;
1063   if (D->getDeclContext()->isFunctionOrMethod())
1064     DC = Owner;
1065   else if (isFriend && QualifierLoc) {
1066     CXXScopeSpec SS;
1067     SS.Adopt(QualifierLoc);
1068     DC = SemaRef.computeDeclContext(SS);
1069     if (!DC) return 0;
1070   } else {
1071     DC = SemaRef.FindInstantiatedContext(D->getLocation(), D->getDeclContext(),
1072                                          TemplateArgs);
1073   }
1074
1075   FunctionDecl *Function =
1076       FunctionDecl::Create(SemaRef.Context, DC, D->getInnerLocStart(),
1077                            D->getLocation(), D->getDeclName(), T, TInfo,
1078                            D->getStorageClass(), D->getStorageClassAsWritten(),
1079                            D->isInlineSpecified(), D->hasWrittenPrototype());
1080
1081   if (QualifierLoc)
1082     Function->setQualifierInfo(QualifierLoc);
1083
1084   DeclContext *LexicalDC = Owner;
1085   if (!isFriend && D->isOutOfLine()) {
1086     assert(D->getDeclContext()->isFileContext());
1087     LexicalDC = D->getDeclContext();
1088   }
1089
1090   Function->setLexicalDeclContext(LexicalDC);
1091
1092   // Attach the parameters
1093   if (isa<FunctionProtoType>(Function->getType().IgnoreParens())) {
1094     // Adopt the already-instantiated parameters into our own context.
1095     for (unsigned P = 0; P < Params.size(); ++P)
1096       if (Params[P])
1097         Params[P]->setOwningFunction(Function);
1098   } else {
1099     // Since we were instantiated via a typedef of a function type, create
1100     // new parameters.
1101     const FunctionProtoType *Proto
1102       = Function->getType()->getAs<FunctionProtoType>();
1103     assert(Proto && "No function prototype in template instantiation?");
1104     for (FunctionProtoType::arg_type_iterator AI = Proto->arg_type_begin(),
1105          AE = Proto->arg_type_end(); AI != AE; ++AI) {
1106       ParmVarDecl *Param
1107         = SemaRef.BuildParmVarDeclForTypedef(Function, Function->getLocation(),
1108                                              *AI);
1109       Param->setScopeInfo(0, Params.size());
1110       Params.push_back(Param);
1111     }
1112   }
1113   Function->setParams(Params.data(), Params.size());
1114
1115   SourceLocation InstantiateAtPOI;
1116   if (TemplateParams) {
1117     // Our resulting instantiation is actually a function template, since we
1118     // are substituting only the outer template parameters. For example, given
1119     //
1120     //   template<typename T>
1121     //   struct X {
1122     //     template<typename U> friend void f(T, U);
1123     //   };
1124     //
1125     //   X<int> x;
1126     //
1127     // We are instantiating the friend function template "f" within X<int>,
1128     // which means substituting int for T, but leaving "f" as a friend function
1129     // template.
1130     // Build the function template itself.
1131     FunctionTemplate = FunctionTemplateDecl::Create(SemaRef.Context, DC,
1132                                                     Function->getLocation(),
1133                                                     Function->getDeclName(),
1134                                                     TemplateParams, Function);
1135     Function->setDescribedFunctionTemplate(FunctionTemplate);
1136
1137     FunctionTemplate->setLexicalDeclContext(LexicalDC);
1138
1139     if (isFriend && D->isThisDeclarationADefinition()) {
1140       // TODO: should we remember this connection regardless of whether
1141       // the friend declaration provided a body?
1142       FunctionTemplate->setInstantiatedFromMemberTemplate(
1143                                            D->getDescribedFunctionTemplate());
1144     }
1145   } else if (FunctionTemplate) {
1146     // Record this function template specialization.
1147     std::pair<const TemplateArgument *, unsigned> Innermost
1148       = TemplateArgs.getInnermost();
1149     Function->setFunctionTemplateSpecialization(FunctionTemplate,
1150                             TemplateArgumentList::CreateCopy(SemaRef.Context,
1151                                                              Innermost.first,
1152                                                              Innermost.second),
1153                                                 InsertPos);
1154   } else if (isFriend && D->isThisDeclarationADefinition()) {
1155     // TODO: should we remember this connection regardless of whether
1156     // the friend declaration provided a body?
1157     Function->setInstantiationOfMemberFunction(D, TSK_ImplicitInstantiation);
1158   }
1159
1160   if (InitFunctionInstantiation(Function, D))
1161     Function->setInvalidDecl();
1162
1163   bool Redeclaration = false;
1164   bool isExplicitSpecialization = false;
1165
1166   LookupResult Previous(SemaRef, Function->getDeclName(), SourceLocation(),
1167                         Sema::LookupOrdinaryName, Sema::ForRedeclaration);
1168
1169   if (DependentFunctionTemplateSpecializationInfo *Info
1170         = D->getDependentSpecializationInfo()) {
1171     assert(isFriend && "non-friend has dependent specialization info?");
1172
1173     // This needs to be set now for future sanity.
1174     Function->setObjectOfFriendDecl(/*HasPrevious*/ true);
1175
1176     // Instantiate the explicit template arguments.
1177     TemplateArgumentListInfo ExplicitArgs(Info->getLAngleLoc(),
1178                                           Info->getRAngleLoc());
1179     if (SemaRef.Subst(Info->getTemplateArgs(), Info->getNumTemplateArgs(),
1180                       ExplicitArgs, TemplateArgs))
1181       return 0;
1182
1183     // Map the candidate templates to their instantiations.
1184     for (unsigned I = 0, E = Info->getNumTemplates(); I != E; ++I) {
1185       Decl *Temp = SemaRef.FindInstantiatedDecl(D->getLocation(),
1186                                                 Info->getTemplate(I),
1187                                                 TemplateArgs);
1188       if (!Temp) return 0;
1189
1190       Previous.addDecl(cast<FunctionTemplateDecl>(Temp));
1191     }
1192
1193     if (SemaRef.CheckFunctionTemplateSpecialization(Function,
1194                                                     &ExplicitArgs,
1195                                                     Previous))
1196       Function->setInvalidDecl();
1197
1198     isExplicitSpecialization = true;
1199
1200   } else if (TemplateParams || !FunctionTemplate) {
1201     // Look only into the namespace where the friend would be declared to
1202     // find a previous declaration. This is the innermost enclosing namespace,
1203     // as described in ActOnFriendFunctionDecl.
1204     SemaRef.LookupQualifiedName(Previous, DC);
1205
1206     // In C++, the previous declaration we find might be a tag type
1207     // (class or enum). In this case, the new declaration will hide the
1208     // tag type. Note that this does does not apply if we're declaring a
1209     // typedef (C++ [dcl.typedef]p4).
1210     if (Previous.isSingleTagDecl())
1211       Previous.clear();
1212   }
1213
1214   SemaRef.CheckFunctionDeclaration(/*Scope*/ 0, Function, Previous,
1215                                    isExplicitSpecialization, Redeclaration);
1216
1217   NamedDecl *PrincipalDecl = (TemplateParams
1218                               ? cast<NamedDecl>(FunctionTemplate)
1219                               : Function);
1220
1221   // If the original function was part of a friend declaration,
1222   // inherit its namespace state and add it to the owner.
1223   if (isFriend) {
1224     NamedDecl *PrevDecl;
1225     if (TemplateParams)
1226       PrevDecl = FunctionTemplate->getPreviousDeclaration();
1227     else
1228       PrevDecl = Function->getPreviousDeclaration();
1229
1230     PrincipalDecl->setObjectOfFriendDecl(PrevDecl != 0);
1231     DC->makeDeclVisibleInContext(PrincipalDecl, /*Recoverable=*/ false);
1232
1233     bool queuedInstantiation = false;
1234
1235     if (!SemaRef.getLangOptions().CPlusPlus0x &&
1236         D->isThisDeclarationADefinition()) {
1237       // Check for a function body.
1238       const FunctionDecl *Definition = 0;
1239       if (Function->isDefined(Definition) &&
1240           Definition->getTemplateSpecializationKind() == TSK_Undeclared) {
1241         SemaRef.Diag(Function->getLocation(), diag::err_redefinition)
1242           << Function->getDeclName();
1243         SemaRef.Diag(Definition->getLocation(), diag::note_previous_definition);
1244         Function->setInvalidDecl();
1245       }
1246       // Check for redefinitions due to other instantiations of this or
1247       // a similar friend function.
1248       else for (FunctionDecl::redecl_iterator R = Function->redecls_begin(),
1249                                            REnd = Function->redecls_end();
1250                 R != REnd; ++R) {
1251         if (*R == Function)
1252           continue;
1253         switch (R->getFriendObjectKind()) {
1254         case Decl::FOK_None:
1255           if (!queuedInstantiation && R->isUsed(false)) {
1256             if (MemberSpecializationInfo *MSInfo
1257                 = Function->getMemberSpecializationInfo()) {
1258               if (MSInfo->getPointOfInstantiation().isInvalid()) {
1259                 SourceLocation Loc = R->getLocation(); // FIXME
1260                 MSInfo->setPointOfInstantiation(Loc);
1261                 SemaRef.PendingLocalImplicitInstantiations.push_back(
1262                                                  std::make_pair(Function, Loc));
1263                 queuedInstantiation = true;
1264               }
1265             }
1266           }
1267           break;
1268         default:
1269           if (const FunctionDecl *RPattern
1270               = R->getTemplateInstantiationPattern())
1271             if (RPattern->isDefined(RPattern)) {
1272               SemaRef.Diag(Function->getLocation(), diag::err_redefinition)
1273                 << Function->getDeclName();
1274               SemaRef.Diag(R->getLocation(), diag::note_previous_definition);
1275               Function->setInvalidDecl();
1276               break;
1277             }
1278         }
1279       }
1280     }
1281   }
1282
1283   if (Function->isOverloadedOperator() && !DC->isRecord() &&
1284       PrincipalDecl->isInIdentifierNamespace(Decl::IDNS_Ordinary))
1285     PrincipalDecl->setNonMemberOperator();
1286
1287   assert(!D->isDefaulted() && "only methods should be defaulted");
1288   return Function;
1289 }
1290
1291 Decl *
1292 TemplateDeclInstantiator::VisitCXXMethodDecl(CXXMethodDecl *D,
1293                                       TemplateParameterList *TemplateParams) {
1294   FunctionTemplateDecl *FunctionTemplate = D->getDescribedFunctionTemplate();
1295   void *InsertPos = 0;
1296   if (FunctionTemplate && !TemplateParams) {
1297     // We are creating a function template specialization from a function
1298     // template. Check whether there is already a function template
1299     // specialization for this particular set of template arguments.
1300     std::pair<const TemplateArgument *, unsigned> Innermost
1301       = TemplateArgs.getInnermost();
1302
1303     FunctionDecl *SpecFunc
1304       = FunctionTemplate->findSpecialization(Innermost.first, Innermost.second,
1305                                              InsertPos);
1306
1307     // If we already have a function template specialization, return it.
1308     if (SpecFunc)
1309       return SpecFunc;
1310   }
1311
1312   bool isFriend;
1313   if (FunctionTemplate)
1314     isFriend = (FunctionTemplate->getFriendObjectKind() != Decl::FOK_None);
1315   else
1316     isFriend = (D->getFriendObjectKind() != Decl::FOK_None);
1317
1318   bool MergeWithParentScope = (TemplateParams != 0) ||
1319     !(isa<Decl>(Owner) &&
1320       cast<Decl>(Owner)->isDefinedOutsideFunctionOrMethod());
1321   LocalInstantiationScope Scope(SemaRef, MergeWithParentScope);
1322
1323   // Instantiate enclosing template arguments for friends.
1324   llvm::SmallVector<TemplateParameterList *, 4> TempParamLists;
1325   unsigned NumTempParamLists = 0;
1326   if (isFriend && (NumTempParamLists = D->getNumTemplateParameterLists())) {
1327     TempParamLists.set_size(NumTempParamLists);
1328     for (unsigned I = 0; I != NumTempParamLists; ++I) {
1329       TemplateParameterList *TempParams = D->getTemplateParameterList(I);
1330       TemplateParameterList *InstParams = SubstTemplateParams(TempParams);
1331       if (!InstParams)
1332         return NULL;
1333       TempParamLists[I] = InstParams;
1334     }
1335   }
1336
1337   llvm::SmallVector<ParmVarDecl *, 4> Params;
1338   TypeSourceInfo *TInfo = D->getTypeSourceInfo();
1339   TInfo = SubstFunctionType(D, Params);
1340   if (!TInfo)
1341     return 0;
1342   QualType T = TInfo->getType();
1343
1344   // \brief If the type of this function, after ignoring parentheses,
1345   // is not *directly* a function type, then we're instantiating a function
1346   // that was declared via a typedef, e.g.,
1347   //
1348   //   typedef int functype(int, int);
1349   //   functype func;
1350   //
1351   // In this case, we'll just go instantiate the ParmVarDecls that we
1352   // synthesized in the method declaration.
1353   if (!isa<FunctionProtoType>(T.IgnoreParens())) {
1354     assert(!Params.size() && "Instantiating type could not yield parameters");
1355     llvm::SmallVector<QualType, 4> ParamTypes;
1356     if (SemaRef.SubstParmTypes(D->getLocation(), D->param_begin(),
1357                                D->getNumParams(), TemplateArgs, ParamTypes,
1358                                &Params))
1359       return 0;
1360   }
1361
1362   NestedNameSpecifierLoc QualifierLoc = D->getQualifierLoc();
1363   if (QualifierLoc) {
1364     QualifierLoc = SemaRef.SubstNestedNameSpecifierLoc(QualifierLoc,
1365                                                  TemplateArgs);
1366     if (!QualifierLoc)
1367       return 0;
1368   }
1369
1370   DeclContext *DC = Owner;
1371   if (isFriend) {
1372     if (QualifierLoc) {
1373       CXXScopeSpec SS;
1374       SS.Adopt(QualifierLoc);
1375       DC = SemaRef.computeDeclContext(SS);
1376
1377       if (DC && SemaRef.RequireCompleteDeclContext(SS, DC))
1378         return 0;
1379     } else {
1380       DC = SemaRef.FindInstantiatedContext(D->getLocation(),
1381                                            D->getDeclContext(),
1382                                            TemplateArgs);
1383     }
1384     if (!DC) return 0;
1385   }
1386
1387   // Build the instantiated method declaration.
1388   CXXRecordDecl *Record = cast<CXXRecordDecl>(DC);
1389   CXXMethodDecl *Method = 0;
1390
1391   SourceLocation StartLoc = D->getInnerLocStart();
1392   DeclarationNameInfo NameInfo
1393     = SemaRef.SubstDeclarationNameInfo(D->getNameInfo(), TemplateArgs);
1394   if (CXXConstructorDecl *Constructor = dyn_cast<CXXConstructorDecl>(D)) {
1395     Method = CXXConstructorDecl::Create(SemaRef.Context, Record,
1396                                         StartLoc, NameInfo, T, TInfo,
1397                                         Constructor->isExplicit(),
1398                                         Constructor->isInlineSpecified(),
1399                                         false);
1400   } else if (CXXDestructorDecl *Destructor = dyn_cast<CXXDestructorDecl>(D)) {
1401     Method = CXXDestructorDecl::Create(SemaRef.Context, Record,
1402                                        StartLoc, NameInfo, T, TInfo,
1403                                        Destructor->isInlineSpecified(),
1404                                        false);
1405   } else if (CXXConversionDecl *Conversion = dyn_cast<CXXConversionDecl>(D)) {
1406     Method = CXXConversionDecl::Create(SemaRef.Context, Record,
1407                                        StartLoc, NameInfo, T, TInfo,
1408                                        Conversion->isInlineSpecified(),
1409                                        Conversion->isExplicit(),
1410                                        Conversion->getLocEnd());
1411   } else {
1412     Method = CXXMethodDecl::Create(SemaRef.Context, Record,
1413                                    StartLoc, NameInfo, T, TInfo,
1414                                    D->isStatic(),
1415                                    D->getStorageClassAsWritten(),
1416                                    D->isInlineSpecified(),
1417                                    D->getLocEnd());
1418   }
1419
1420   if (QualifierLoc)
1421     Method->setQualifierInfo(QualifierLoc);
1422
1423   if (TemplateParams) {
1424     // Our resulting instantiation is actually a function template, since we
1425     // are substituting only the outer template parameters. For example, given
1426     //
1427     //   template<typename T>
1428     //   struct X {
1429     //     template<typename U> void f(T, U);
1430     //   };
1431     //
1432     //   X<int> x;
1433     //
1434     // We are instantiating the member template "f" within X<int>, which means
1435     // substituting int for T, but leaving "f" as a member function template.
1436     // Build the function template itself.
1437     FunctionTemplate = FunctionTemplateDecl::Create(SemaRef.Context, Record,
1438                                                     Method->getLocation(),
1439                                                     Method->getDeclName(),
1440                                                     TemplateParams, Method);
1441     if (isFriend) {
1442       FunctionTemplate->setLexicalDeclContext(Owner);
1443       FunctionTemplate->setObjectOfFriendDecl(true);
1444     } else if (D->isOutOfLine())
1445       FunctionTemplate->setLexicalDeclContext(D->getLexicalDeclContext());
1446     Method->setDescribedFunctionTemplate(FunctionTemplate);
1447   } else if (FunctionTemplate) {
1448     // Record this function template specialization.
1449     std::pair<const TemplateArgument *, unsigned> Innermost
1450       = TemplateArgs.getInnermost();
1451     Method->setFunctionTemplateSpecialization(FunctionTemplate,
1452                          TemplateArgumentList::CreateCopy(SemaRef.Context,
1453                                                           Innermost.first,
1454                                                           Innermost.second),
1455                                               InsertPos);
1456   } else if (!isFriend) {
1457     // Record that this is an instantiation of a member function.
1458     Method->setInstantiationOfMemberFunction(D, TSK_ImplicitInstantiation);
1459   }
1460
1461   // If we are instantiating a member function defined
1462   // out-of-line, the instantiation will have the same lexical
1463   // context (which will be a namespace scope) as the template.
1464   if (isFriend) {
1465     if (NumTempParamLists)
1466       Method->setTemplateParameterListsInfo(SemaRef.Context,
1467                                             NumTempParamLists,
1468                                             TempParamLists.data());
1469
1470     Method->setLexicalDeclContext(Owner);
1471     Method->setObjectOfFriendDecl(true);
1472   } else if (D->isOutOfLine())
1473     Method->setLexicalDeclContext(D->getLexicalDeclContext());
1474
1475   // Attach the parameters
1476   for (unsigned P = 0; P < Params.size(); ++P)
1477     Params[P]->setOwningFunction(Method);
1478   Method->setParams(Params.data(), Params.size());
1479
1480   if (InitMethodInstantiation(Method, D))
1481     Method->setInvalidDecl();
1482
1483   LookupResult Previous(SemaRef, NameInfo, Sema::LookupOrdinaryName,
1484                         Sema::ForRedeclaration);
1485
1486   if (!FunctionTemplate || TemplateParams || isFriend) {
1487     SemaRef.LookupQualifiedName(Previous, Record);
1488
1489     // In C++, the previous declaration we find might be a tag type
1490     // (class or enum). In this case, the new declaration will hide the
1491     // tag type. Note that this does does not apply if we're declaring a
1492     // typedef (C++ [dcl.typedef]p4).
1493     if (Previous.isSingleTagDecl())
1494       Previous.clear();
1495   }
1496
1497   bool Redeclaration = false;
1498   SemaRef.CheckFunctionDeclaration(0, Method, Previous, false, Redeclaration);
1499
1500   if (D->isPure())
1501     SemaRef.CheckPureMethod(Method, SourceRange());
1502
1503   Method->setAccess(D->getAccess());
1504
1505   SemaRef.CheckOverrideControl(Method);
1506
1507   if (FunctionTemplate) {
1508     // If there's a function template, let our caller handle it.
1509   } else if (Method->isInvalidDecl() && !Previous.empty()) {
1510     // Don't hide a (potentially) valid declaration with an invalid one.
1511   } else {
1512     NamedDecl *DeclToAdd = (TemplateParams
1513                             ? cast<NamedDecl>(FunctionTemplate)
1514                             : Method);
1515     if (isFriend)
1516       Record->makeDeclVisibleInContext(DeclToAdd);
1517     else
1518       Owner->addDecl(DeclToAdd);
1519   }
1520
1521   if (D->isExplicitlyDefaulted()) {
1522     SemaRef.SetDeclDefaulted(Method, Method->getLocation());
1523   } else {
1524     assert(!D->isDefaulted() &&
1525            "should not implicitly default uninstantiated function");
1526   }
1527
1528   return Method;
1529 }
1530
1531 Decl *TemplateDeclInstantiator::VisitCXXConstructorDecl(CXXConstructorDecl *D) {
1532   return VisitCXXMethodDecl(D);
1533 }
1534
1535 Decl *TemplateDeclInstantiator::VisitCXXDestructorDecl(CXXDestructorDecl *D) {
1536   return VisitCXXMethodDecl(D);
1537 }
1538
1539 Decl *TemplateDeclInstantiator::VisitCXXConversionDecl(CXXConversionDecl *D) {
1540   return VisitCXXMethodDecl(D);
1541 }
1542
1543 ParmVarDecl *TemplateDeclInstantiator::VisitParmVarDecl(ParmVarDecl *D) {
1544   return SemaRef.SubstParmVarDecl(D, TemplateArgs, /*indexAdjustment*/ 0,
1545                                   llvm::Optional<unsigned>());
1546 }
1547
1548 Decl *TemplateDeclInstantiator::VisitTemplateTypeParmDecl(
1549                                                     TemplateTypeParmDecl *D) {
1550   // TODO: don't always clone when decls are refcounted.
1551   assert(D->getTypeForDecl()->isTemplateTypeParmType());
1552
1553   TemplateTypeParmDecl *Inst =
1554     TemplateTypeParmDecl::Create(SemaRef.Context, Owner,
1555                                  D->getLocStart(), D->getLocation(),
1556                                  D->getDepth() - TemplateArgs.getNumLevels(),
1557                                  D->getIndex(), D->getIdentifier(),
1558                                  D->wasDeclaredWithTypename(),
1559                                  D->isParameterPack());
1560   Inst->setAccess(AS_public);
1561
1562   if (D->hasDefaultArgument())
1563     Inst->setDefaultArgument(D->getDefaultArgumentInfo(), false);
1564
1565   // Introduce this template parameter's instantiation into the instantiation
1566   // scope.
1567   SemaRef.CurrentInstantiationScope->InstantiatedLocal(D, Inst);
1568
1569   return Inst;
1570 }
1571
1572 Decl *TemplateDeclInstantiator::VisitNonTypeTemplateParmDecl(
1573                                                  NonTypeTemplateParmDecl *D) {
1574   // Substitute into the type of the non-type template parameter.
1575   TypeLoc TL = D->getTypeSourceInfo()->getTypeLoc();
1576   llvm::SmallVector<TypeSourceInfo *, 4> ExpandedParameterPackTypesAsWritten;
1577   llvm::SmallVector<QualType, 4> ExpandedParameterPackTypes;
1578   bool IsExpandedParameterPack = false;
1579   TypeSourceInfo *DI;
1580   QualType T;
1581   bool Invalid = false;
1582
1583   if (D->isExpandedParameterPack()) {
1584     // The non-type template parameter pack is an already-expanded pack
1585     // expansion of types. Substitute into each of the expanded types.
1586     ExpandedParameterPackTypes.reserve(D->getNumExpansionTypes());
1587     ExpandedParameterPackTypesAsWritten.reserve(D->getNumExpansionTypes());
1588     for (unsigned I = 0, N = D->getNumExpansionTypes(); I != N; ++I) {
1589       TypeSourceInfo *NewDI =SemaRef.SubstType(D->getExpansionTypeSourceInfo(I),
1590                                                TemplateArgs,
1591                                                D->getLocation(),
1592                                                D->getDeclName());
1593       if (!NewDI)
1594         return 0;
1595
1596       ExpandedParameterPackTypesAsWritten.push_back(NewDI);
1597       QualType NewT =SemaRef.CheckNonTypeTemplateParameterType(NewDI->getType(),
1598                                                               D->getLocation());
1599       if (NewT.isNull())
1600         return 0;
1601       ExpandedParameterPackTypes.push_back(NewT);
1602     }
1603
1604     IsExpandedParameterPack = true;
1605     DI = D->getTypeSourceInfo();
1606     T = DI->getType();
1607   } else if (isa<PackExpansionTypeLoc>(TL)) {
1608     // The non-type template parameter pack's type is a pack expansion of types.
1609     // Determine whether we need to expand this parameter pack into separate
1610     // types.
1611     PackExpansionTypeLoc Expansion = cast<PackExpansionTypeLoc>(TL);
1612     TypeLoc Pattern = Expansion.getPatternLoc();
1613     llvm::SmallVector<UnexpandedParameterPack, 2> Unexpanded;
1614     SemaRef.collectUnexpandedParameterPacks(Pattern, Unexpanded);
1615
1616     // Determine whether the set of unexpanded parameter packs can and should
1617     // be expanded.
1618     bool Expand = true;
1619     bool RetainExpansion = false;
1620     llvm::Optional<unsigned> OrigNumExpansions
1621       = Expansion.getTypePtr()->getNumExpansions();
1622     llvm::Optional<unsigned> NumExpansions = OrigNumExpansions;
1623     if (SemaRef.CheckParameterPacksForExpansion(Expansion.getEllipsisLoc(),
1624                                                 Pattern.getSourceRange(),
1625                                                 Unexpanded.data(),
1626                                                 Unexpanded.size(),
1627                                                 TemplateArgs,
1628                                                 Expand, RetainExpansion,
1629                                                 NumExpansions))
1630       return 0;
1631
1632     if (Expand) {
1633       for (unsigned I = 0; I != *NumExpansions; ++I) {
1634         Sema::ArgumentPackSubstitutionIndexRAII SubstIndex(SemaRef, I);
1635         TypeSourceInfo *NewDI = SemaRef.SubstType(Pattern, TemplateArgs,
1636                                                   D->getLocation(),
1637                                                   D->getDeclName());
1638         if (!NewDI)
1639           return 0;
1640
1641         ExpandedParameterPackTypesAsWritten.push_back(NewDI);
1642         QualType NewT = SemaRef.CheckNonTypeTemplateParameterType(
1643                                                               NewDI->getType(),
1644                                                               D->getLocation());
1645         if (NewT.isNull())
1646           return 0;
1647         ExpandedParameterPackTypes.push_back(NewT);
1648       }
1649
1650       // Note that we have an expanded parameter pack. The "type" of this
1651       // expanded parameter pack is the original expansion type, but callers
1652       // will end up using the expanded parameter pack types for type-checking.
1653       IsExpandedParameterPack = true;
1654       DI = D->getTypeSourceInfo();
1655       T = DI->getType();
1656     } else {
1657       // We cannot fully expand the pack expansion now, so substitute into the
1658       // pattern and create a new pack expansion type.
1659       Sema::ArgumentPackSubstitutionIndexRAII SubstIndex(SemaRef, -1);
1660       TypeSourceInfo *NewPattern = SemaRef.SubstType(Pattern, TemplateArgs,
1661                                                      D->getLocation(),
1662                                                      D->getDeclName());
1663       if (!NewPattern)
1664         return 0;
1665
1666       DI = SemaRef.CheckPackExpansion(NewPattern, Expansion.getEllipsisLoc(),
1667                                       NumExpansions);
1668       if (!DI)
1669         return 0;
1670
1671       T = DI->getType();
1672     }
1673   } else {
1674     // Simple case: substitution into a parameter that is not a parameter pack.
1675     DI = SemaRef.SubstType(D->getTypeSourceInfo(), TemplateArgs,
1676                            D->getLocation(), D->getDeclName());
1677     if (!DI)
1678       return 0;
1679
1680     // Check that this type is acceptable for a non-type template parameter.
1681     T = SemaRef.CheckNonTypeTemplateParameterType(DI->getType(),
1682                                                   D->getLocation());
1683     if (T.isNull()) {
1684       T = SemaRef.Context.IntTy;
1685       Invalid = true;
1686     }
1687   }
1688
1689   NonTypeTemplateParmDecl *Param;
1690   if (IsExpandedParameterPack)
1691     Param = NonTypeTemplateParmDecl::Create(SemaRef.Context, Owner,
1692                                             D->getInnerLocStart(),
1693                                             D->getLocation(),
1694                                     D->getDepth() - TemplateArgs.getNumLevels(),
1695                                             D->getPosition(),
1696                                             D->getIdentifier(), T,
1697                                             DI,
1698                                             ExpandedParameterPackTypes.data(),
1699                                             ExpandedParameterPackTypes.size(),
1700                                     ExpandedParameterPackTypesAsWritten.data());
1701   else
1702     Param = NonTypeTemplateParmDecl::Create(SemaRef.Context, Owner,
1703                                             D->getInnerLocStart(),
1704                                             D->getLocation(),
1705                                     D->getDepth() - TemplateArgs.getNumLevels(),
1706                                             D->getPosition(),
1707                                             D->getIdentifier(), T,
1708                                             D->isParameterPack(), DI);
1709
1710   Param->setAccess(AS_public);
1711   if (Invalid)
1712     Param->setInvalidDecl();
1713
1714   Param->setDefaultArgument(D->getDefaultArgument(), false);
1715
1716   // Introduce this template parameter's instantiation into the instantiation
1717   // scope.
1718   SemaRef.CurrentInstantiationScope->InstantiatedLocal(D, Param);
1719   return Param;
1720 }
1721
1722 Decl *
1723 TemplateDeclInstantiator::VisitTemplateTemplateParmDecl(
1724                                                   TemplateTemplateParmDecl *D) {
1725   // Instantiate the template parameter list of the template template parameter.
1726   TemplateParameterList *TempParams = D->getTemplateParameters();
1727   TemplateParameterList *InstParams;
1728   {
1729     // Perform the actual substitution of template parameters within a new,
1730     // local instantiation scope.
1731     LocalInstantiationScope Scope(SemaRef);
1732     InstParams = SubstTemplateParams(TempParams);
1733     if (!InstParams)
1734       return NULL;
1735   }
1736
1737   // Build the template template parameter.
1738   TemplateTemplateParmDecl *Param
1739     = TemplateTemplateParmDecl::Create(SemaRef.Context, Owner, D->getLocation(),
1740                                    D->getDepth() - TemplateArgs.getNumLevels(),
1741                                        D->getPosition(), D->isParameterPack(),
1742                                        D->getIdentifier(), InstParams);
1743   Param->setDefaultArgument(D->getDefaultArgument(), false);
1744   Param->setAccess(AS_public);
1745
1746   // Introduce this template parameter's instantiation into the instantiation
1747   // scope.
1748   SemaRef.CurrentInstantiationScope->InstantiatedLocal(D, Param);
1749
1750   return Param;
1751 }
1752
1753 Decl *TemplateDeclInstantiator::VisitUsingDirectiveDecl(UsingDirectiveDecl *D) {
1754   // Using directives are never dependent (and never contain any types or
1755   // expressions), so they require no explicit instantiation work.
1756
1757   UsingDirectiveDecl *Inst
1758     = UsingDirectiveDecl::Create(SemaRef.Context, Owner, D->getLocation(),
1759                                  D->getNamespaceKeyLocation(),
1760                                  D->getQualifierLoc(),
1761                                  D->getIdentLocation(),
1762                                  D->getNominatedNamespace(),
1763                                  D->getCommonAncestor());
1764   Owner->addDecl(Inst);
1765   return Inst;
1766 }
1767
1768 Decl *TemplateDeclInstantiator::VisitUsingDecl(UsingDecl *D) {
1769
1770   // The nested name specifier may be dependent, for example
1771   //     template <typename T> struct t {
1772   //       struct s1 { T f1(); };
1773   //       struct s2 : s1 { using s1::f1; };
1774   //     };
1775   //     template struct t<int>;
1776   // Here, in using s1::f1, s1 refers to t<T>::s1;
1777   // we need to substitute for t<int>::s1.
1778   NestedNameSpecifierLoc QualifierLoc
1779     = SemaRef.SubstNestedNameSpecifierLoc(D->getQualifierLoc(),
1780                                           TemplateArgs);
1781   if (!QualifierLoc)
1782     return 0;
1783
1784   // The name info is non-dependent, so no transformation
1785   // is required.
1786   DeclarationNameInfo NameInfo = D->getNameInfo();
1787
1788   // We only need to do redeclaration lookups if we're in a class
1789   // scope (in fact, it's not really even possible in non-class
1790   // scopes).
1791   bool CheckRedeclaration = Owner->isRecord();
1792
1793   LookupResult Prev(SemaRef, NameInfo, Sema::LookupUsingDeclName,
1794                     Sema::ForRedeclaration);
1795
1796   UsingDecl *NewUD = UsingDecl::Create(SemaRef.Context, Owner,
1797                                        D->getUsingLocation(),
1798                                        QualifierLoc,
1799                                        NameInfo,
1800                                        D->isTypeName());
1801
1802   CXXScopeSpec SS;
1803   SS.Adopt(QualifierLoc);
1804   if (CheckRedeclaration) {
1805     Prev.setHideTags(false);
1806     SemaRef.LookupQualifiedName(Prev, Owner);
1807
1808     // Check for invalid redeclarations.
1809     if (SemaRef.CheckUsingDeclRedeclaration(D->getUsingLocation(),
1810                                             D->isTypeName(), SS,
1811                                             D->getLocation(), Prev))
1812       NewUD->setInvalidDecl();
1813
1814   }
1815
1816   if (!NewUD->isInvalidDecl() &&
1817       SemaRef.CheckUsingDeclQualifier(D->getUsingLocation(), SS,
1818                                       D->getLocation()))
1819     NewUD->setInvalidDecl();
1820
1821   SemaRef.Context.setInstantiatedFromUsingDecl(NewUD, D);
1822   NewUD->setAccess(D->getAccess());
1823   Owner->addDecl(NewUD);
1824
1825   // Don't process the shadow decls for an invalid decl.
1826   if (NewUD->isInvalidDecl())
1827     return NewUD;
1828
1829   bool isFunctionScope = Owner->isFunctionOrMethod();
1830
1831   // Process the shadow decls.
1832   for (UsingDecl::shadow_iterator I = D->shadow_begin(), E = D->shadow_end();
1833          I != E; ++I) {
1834     UsingShadowDecl *Shadow = *I;
1835     NamedDecl *InstTarget =
1836       cast_or_null<NamedDecl>(SemaRef.FindInstantiatedDecl(
1837                                                           Shadow->getLocation(),
1838                                                         Shadow->getTargetDecl(),
1839                                                            TemplateArgs));
1840     if (!InstTarget)
1841       return 0;
1842
1843     if (CheckRedeclaration &&
1844         SemaRef.CheckUsingShadowDecl(NewUD, InstTarget, Prev))
1845       continue;
1846
1847     UsingShadowDecl *InstShadow
1848       = SemaRef.BuildUsingShadowDecl(/*Scope*/ 0, NewUD, InstTarget);
1849     SemaRef.Context.setInstantiatedFromUsingShadowDecl(InstShadow, Shadow);
1850
1851     if (isFunctionScope)
1852       SemaRef.CurrentInstantiationScope->InstantiatedLocal(Shadow, InstShadow);
1853   }
1854
1855   return NewUD;
1856 }
1857
1858 Decl *TemplateDeclInstantiator::VisitUsingShadowDecl(UsingShadowDecl *D) {
1859   // Ignore these;  we handle them in bulk when processing the UsingDecl.
1860   return 0;
1861 }
1862
1863 Decl * TemplateDeclInstantiator
1864     ::VisitUnresolvedUsingTypenameDecl(UnresolvedUsingTypenameDecl *D) {
1865   NestedNameSpecifierLoc QualifierLoc
1866     = SemaRef.SubstNestedNameSpecifierLoc(D->getQualifierLoc(),
1867                                           TemplateArgs);
1868   if (!QualifierLoc)
1869     return 0;
1870
1871   CXXScopeSpec SS;
1872   SS.Adopt(QualifierLoc);
1873
1874   // Since NameInfo refers to a typename, it cannot be a C++ special name.
1875   // Hence, no tranformation is required for it.
1876   DeclarationNameInfo NameInfo(D->getDeclName(), D->getLocation());
1877   NamedDecl *UD =
1878     SemaRef.BuildUsingDeclaration(/*Scope*/ 0, D->getAccess(),
1879                                   D->getUsingLoc(), SS, NameInfo, 0,
1880                                   /*instantiation*/ true,
1881                                   /*typename*/ true, D->getTypenameLoc());
1882   if (UD)
1883     SemaRef.Context.setInstantiatedFromUsingDecl(cast<UsingDecl>(UD), D);
1884
1885   return UD;
1886 }
1887
1888 Decl * TemplateDeclInstantiator
1889     ::VisitUnresolvedUsingValueDecl(UnresolvedUsingValueDecl *D) {
1890   NestedNameSpecifierLoc QualifierLoc
1891       = SemaRef.SubstNestedNameSpecifierLoc(D->getQualifierLoc(), TemplateArgs);
1892   if (!QualifierLoc)
1893     return 0;
1894
1895   CXXScopeSpec SS;
1896   SS.Adopt(QualifierLoc);
1897
1898   DeclarationNameInfo NameInfo
1899     = SemaRef.SubstDeclarationNameInfo(D->getNameInfo(), TemplateArgs);
1900
1901   NamedDecl *UD =
1902     SemaRef.BuildUsingDeclaration(/*Scope*/ 0, D->getAccess(),
1903                                   D->getUsingLoc(), SS, NameInfo, 0,
1904                                   /*instantiation*/ true,
1905                                   /*typename*/ false, SourceLocation());
1906   if (UD)
1907     SemaRef.Context.setInstantiatedFromUsingDecl(cast<UsingDecl>(UD), D);
1908
1909   return UD;
1910 }
1911
1912 Decl *Sema::SubstDecl(Decl *D, DeclContext *Owner,
1913                       const MultiLevelTemplateArgumentList &TemplateArgs) {
1914   TemplateDeclInstantiator Instantiator(*this, Owner, TemplateArgs);
1915   if (D->isInvalidDecl())
1916     return 0;
1917
1918   return Instantiator.Visit(D);
1919 }
1920
1921 /// \brief Instantiates a nested template parameter list in the current
1922 /// instantiation context.
1923 ///
1924 /// \param L The parameter list to instantiate
1925 ///
1926 /// \returns NULL if there was an error
1927 TemplateParameterList *
1928 TemplateDeclInstantiator::SubstTemplateParams(TemplateParameterList *L) {
1929   // Get errors for all the parameters before bailing out.
1930   bool Invalid = false;
1931
1932   unsigned N = L->size();
1933   typedef llvm::SmallVector<NamedDecl *, 8> ParamVector;
1934   ParamVector Params;
1935   Params.reserve(N);
1936   for (TemplateParameterList::iterator PI = L->begin(), PE = L->end();
1937        PI != PE; ++PI) {
1938     NamedDecl *D = cast_or_null<NamedDecl>(Visit(*PI));
1939     Params.push_back(D);
1940     Invalid = Invalid || !D || D->isInvalidDecl();
1941   }
1942
1943   // Clean up if we had an error.
1944   if (Invalid)
1945     return NULL;
1946
1947   TemplateParameterList *InstL
1948     = TemplateParameterList::Create(SemaRef.Context, L->getTemplateLoc(),
1949                                     L->getLAngleLoc(), &Params.front(), N,
1950                                     L->getRAngleLoc());
1951   return InstL;
1952 }
1953
1954 /// \brief Instantiate the declaration of a class template partial
1955 /// specialization.
1956 ///
1957 /// \param ClassTemplate the (instantiated) class template that is partially
1958 // specialized by the instantiation of \p PartialSpec.
1959 ///
1960 /// \param PartialSpec the (uninstantiated) class template partial
1961 /// specialization that we are instantiating.
1962 ///
1963 /// \returns The instantiated partial specialization, if successful; otherwise,
1964 /// NULL to indicate an error.
1965 ClassTemplatePartialSpecializationDecl *
1966 TemplateDeclInstantiator::InstantiateClassTemplatePartialSpecialization(
1967                                             ClassTemplateDecl *ClassTemplate,
1968                           ClassTemplatePartialSpecializationDecl *PartialSpec) {
1969   // Create a local instantiation scope for this class template partial
1970   // specialization, which will contain the instantiations of the template
1971   // parameters.
1972   LocalInstantiationScope Scope(SemaRef);
1973
1974   // Substitute into the template parameters of the class template partial
1975   // specialization.
1976   TemplateParameterList *TempParams = PartialSpec->getTemplateParameters();
1977   TemplateParameterList *InstParams = SubstTemplateParams(TempParams);
1978   if (!InstParams)
1979     return 0;
1980
1981   // Substitute into the template arguments of the class template partial
1982   // specialization.
1983   TemplateArgumentListInfo InstTemplateArgs; // no angle locations
1984   if (SemaRef.Subst(PartialSpec->getTemplateArgsAsWritten(),
1985                     PartialSpec->getNumTemplateArgsAsWritten(),
1986                     InstTemplateArgs, TemplateArgs))
1987     return 0;
1988
1989   // Check that the template argument list is well-formed for this
1990   // class template.
1991   llvm::SmallVector<TemplateArgument, 4> Converted;
1992   if (SemaRef.CheckTemplateArgumentList(ClassTemplate,
1993                                         PartialSpec->getLocation(),
1994                                         InstTemplateArgs,
1995                                         false,
1996                                         Converted))
1997     return 0;
1998
1999   // Figure out where to insert this class template partial specialization
2000   // in the member template's set of class template partial specializations.
2001   void *InsertPos = 0;
2002   ClassTemplateSpecializationDecl *PrevDecl
2003     = ClassTemplate->findPartialSpecialization(Converted.data(),
2004                                                Converted.size(), InsertPos);
2005
2006   // Build the canonical type that describes the converted template
2007   // arguments of the class template partial specialization.
2008   QualType CanonType
2009     = SemaRef.Context.getTemplateSpecializationType(TemplateName(ClassTemplate),
2010                                                     Converted.data(),
2011                                                     Converted.size());
2012
2013   // Build the fully-sugared type for this class template
2014   // specialization as the user wrote in the specialization
2015   // itself. This means that we'll pretty-print the type retrieved
2016   // from the specialization's declaration the way that the user
2017   // actually wrote the specialization, rather than formatting the
2018   // name based on the "canonical" representation used to store the
2019   // template arguments in the specialization.
2020   TypeSourceInfo *WrittenTy
2021     = SemaRef.Context.getTemplateSpecializationTypeInfo(
2022                                                     TemplateName(ClassTemplate),
2023                                                     PartialSpec->getLocation(),
2024                                                     InstTemplateArgs,
2025                                                     CanonType);
2026
2027   if (PrevDecl) {
2028     // We've already seen a partial specialization with the same template
2029     // parameters and template arguments. This can happen, for example, when
2030     // substituting the outer template arguments ends up causing two
2031     // class template partial specializations of a member class template
2032     // to have identical forms, e.g.,
2033     //
2034     //   template<typename T, typename U>
2035     //   struct Outer {
2036     //     template<typename X, typename Y> struct Inner;
2037     //     template<typename Y> struct Inner<T, Y>;
2038     //     template<typename Y> struct Inner<U, Y>;
2039     //   };
2040     //
2041     //   Outer<int, int> outer; // error: the partial specializations of Inner
2042     //                          // have the same signature.
2043     SemaRef.Diag(PartialSpec->getLocation(), diag::err_partial_spec_redeclared)
2044       << WrittenTy->getType();
2045     SemaRef.Diag(PrevDecl->getLocation(), diag::note_prev_partial_spec_here)
2046       << SemaRef.Context.getTypeDeclType(PrevDecl);
2047     return 0;
2048   }
2049
2050
2051   // Create the class template partial specialization declaration.
2052   ClassTemplatePartialSpecializationDecl *InstPartialSpec
2053     = ClassTemplatePartialSpecializationDecl::Create(SemaRef.Context,
2054                                                      PartialSpec->getTagKind(),
2055                                                      Owner,
2056                                                      PartialSpec->getLocStart(),
2057                                                      PartialSpec->getLocation(),
2058                                                      InstParams,
2059                                                      ClassTemplate,
2060                                                      Converted.data(),
2061                                                      Converted.size(),
2062                                                      InstTemplateArgs,
2063                                                      CanonType,
2064                                                      0,
2065                              ClassTemplate->getNextPartialSpecSequenceNumber());
2066   // Substitute the nested name specifier, if any.
2067   if (SubstQualifier(PartialSpec, InstPartialSpec))
2068     return 0;
2069
2070   InstPartialSpec->setInstantiatedFromMember(PartialSpec);
2071   InstPartialSpec->setTypeAsWritten(WrittenTy);
2072
2073   // Add this partial specialization to the set of class template partial
2074   // specializations.
2075   ClassTemplate->AddPartialSpecialization(InstPartialSpec, InsertPos);
2076   return InstPartialSpec;
2077 }
2078
2079 TypeSourceInfo*
2080 TemplateDeclInstantiator::SubstFunctionType(FunctionDecl *D,
2081                               llvm::SmallVectorImpl<ParmVarDecl *> &Params) {
2082   TypeSourceInfo *OldTInfo = D->getTypeSourceInfo();
2083   assert(OldTInfo && "substituting function without type source info");
2084   assert(Params.empty() && "parameter vector is non-empty at start");
2085   TypeSourceInfo *NewTInfo
2086     = SemaRef.SubstFunctionDeclType(OldTInfo, TemplateArgs,
2087                                     D->getTypeSpecStartLoc(),
2088                                     D->getDeclName());
2089   if (!NewTInfo)
2090     return 0;
2091
2092   if (NewTInfo != OldTInfo) {
2093     // Get parameters from the new type info.
2094     TypeLoc OldTL = OldTInfo->getTypeLoc().IgnoreParens();
2095     if (FunctionProtoTypeLoc *OldProtoLoc
2096                                   = dyn_cast<FunctionProtoTypeLoc>(&OldTL)) {
2097       TypeLoc NewTL = NewTInfo->getTypeLoc().IgnoreParens();
2098       FunctionProtoTypeLoc *NewProtoLoc = cast<FunctionProtoTypeLoc>(&NewTL);
2099       assert(NewProtoLoc && "Missing prototype?");
2100       unsigned NewIdx = 0, NumNewParams = NewProtoLoc->getNumArgs();
2101       for (unsigned OldIdx = 0, NumOldParams = OldProtoLoc->getNumArgs();
2102            OldIdx != NumOldParams; ++OldIdx) {
2103         ParmVarDecl *OldParam = OldProtoLoc->getArg(OldIdx);
2104         if (!OldParam->isParameterPack() ||
2105             (NewIdx < NumNewParams &&
2106              NewProtoLoc->getArg(NewIdx)->isParameterPack())) {
2107           // Simple case: normal parameter, or a parameter pack that's
2108           // instantiated to a (still-dependent) parameter pack.
2109           ParmVarDecl *NewParam = NewProtoLoc->getArg(NewIdx++);
2110           Params.push_back(NewParam);
2111           SemaRef.CurrentInstantiationScope->InstantiatedLocal(OldParam,
2112                                                                NewParam);
2113           continue;
2114         }
2115
2116         // Parameter pack: make the instantiation an argument pack.
2117         SemaRef.CurrentInstantiationScope->MakeInstantiatedLocalArgPack(
2118                                                                       OldParam);
2119         unsigned NumArgumentsInExpansion
2120           = SemaRef.getNumArgumentsInExpansion(OldParam->getType(),
2121                                                TemplateArgs);
2122         while (NumArgumentsInExpansion--) {
2123           ParmVarDecl *NewParam = NewProtoLoc->getArg(NewIdx++);
2124           Params.push_back(NewParam);
2125           SemaRef.CurrentInstantiationScope->InstantiatedLocalPackArg(OldParam,
2126                                                                       NewParam);
2127         }
2128       }
2129     }
2130   } else {
2131     // The function type itself was not dependent and therefore no
2132     // substitution occurred. However, we still need to instantiate
2133     // the function parameters themselves.
2134     TypeLoc OldTL = OldTInfo->getTypeLoc().IgnoreParens();
2135     if (FunctionProtoTypeLoc *OldProtoLoc
2136                                     = dyn_cast<FunctionProtoTypeLoc>(&OldTL)) {
2137       for (unsigned i = 0, i_end = OldProtoLoc->getNumArgs(); i != i_end; ++i) {
2138         ParmVarDecl *Parm = VisitParmVarDecl(OldProtoLoc->getArg(i));
2139         if (!Parm)
2140           return 0;
2141         Params.push_back(Parm);
2142       }
2143     }
2144   }
2145   return NewTInfo;
2146 }
2147
2148 /// \brief Initializes the common fields of an instantiation function
2149 /// declaration (New) from the corresponding fields of its template (Tmpl).
2150 ///
2151 /// \returns true if there was an error
2152 bool
2153 TemplateDeclInstantiator::InitFunctionInstantiation(FunctionDecl *New,
2154                                                     FunctionDecl *Tmpl) {
2155   if (Tmpl->isDeletedAsWritten())
2156     New->setDeletedAsWritten();
2157
2158   // If we are performing substituting explicitly-specified template arguments
2159   // or deduced template arguments into a function template and we reach this
2160   // point, we are now past the point where SFINAE applies and have committed
2161   // to keeping the new function template specialization. We therefore
2162   // convert the active template instantiation for the function template
2163   // into a template instantiation for this specific function template
2164   // specialization, which is not a SFINAE context, so that we diagnose any
2165   // further errors in the declaration itself.
2166   typedef Sema::ActiveTemplateInstantiation ActiveInstType;
2167   ActiveInstType &ActiveInst = SemaRef.ActiveTemplateInstantiations.back();
2168   if (ActiveInst.Kind == ActiveInstType::ExplicitTemplateArgumentSubstitution ||
2169       ActiveInst.Kind == ActiveInstType::DeducedTemplateArgumentSubstitution) {
2170     if (FunctionTemplateDecl *FunTmpl
2171           = dyn_cast<FunctionTemplateDecl>((Decl *)ActiveInst.Entity)) {
2172       assert(FunTmpl->getTemplatedDecl() == Tmpl &&
2173              "Deduction from the wrong function template?");
2174       (void) FunTmpl;
2175       ActiveInst.Kind = ActiveInstType::TemplateInstantiation;
2176       ActiveInst.Entity = reinterpret_cast<uintptr_t>(New);
2177       --SemaRef.NonInstantiationEntries;
2178     }
2179   }
2180
2181   const FunctionProtoType *Proto = Tmpl->getType()->getAs<FunctionProtoType>();
2182   assert(Proto && "Function template without prototype?");
2183
2184   if (Proto->hasExceptionSpec() || Proto->getNoReturnAttr()) {
2185     // The function has an exception specification or a "noreturn"
2186     // attribute. Substitute into each of the exception types.
2187     llvm::SmallVector<QualType, 4> Exceptions;
2188     for (unsigned I = 0, N = Proto->getNumExceptions(); I != N; ++I) {
2189       // FIXME: Poor location information!
2190       if (const PackExpansionType *PackExpansion
2191             = Proto->getExceptionType(I)->getAs<PackExpansionType>()) {
2192         // We have a pack expansion. Instantiate it.
2193         llvm::SmallVector<UnexpandedParameterPack, 2> Unexpanded;
2194         SemaRef.collectUnexpandedParameterPacks(PackExpansion->getPattern(),
2195                                                 Unexpanded);
2196         assert(!Unexpanded.empty() &&
2197                "Pack expansion without parameter packs?");
2198
2199         bool Expand = false;
2200         bool RetainExpansion = false;
2201         llvm::Optional<unsigned> NumExpansions
2202                                           = PackExpansion->getNumExpansions();
2203         if (SemaRef.CheckParameterPacksForExpansion(New->getLocation(),
2204                                                     SourceRange(),
2205                                                     Unexpanded.data(),
2206                                                     Unexpanded.size(),
2207                                                     TemplateArgs,
2208                                                     Expand,
2209                                                     RetainExpansion,
2210                                                     NumExpansions))
2211           break;
2212
2213         if (!Expand) {
2214           // We can't expand this pack expansion into separate arguments yet;
2215           // just substitute into the pattern and create a new pack expansion
2216           // type.
2217           Sema::ArgumentPackSubstitutionIndexRAII SubstIndex(SemaRef, -1);
2218           QualType T = SemaRef.SubstType(PackExpansion->getPattern(),
2219                                          TemplateArgs,
2220                                        New->getLocation(), New->getDeclName());
2221           if (T.isNull())
2222             break;
2223
2224           T = SemaRef.Context.getPackExpansionType(T, NumExpansions);
2225           Exceptions.push_back(T);
2226           continue;
2227         }
2228
2229         // Substitute into the pack expansion pattern for each template
2230         bool Invalid = false;
2231         for (unsigned ArgIdx = 0; ArgIdx != *NumExpansions; ++ArgIdx) {
2232           Sema::ArgumentPackSubstitutionIndexRAII SubstIndex(SemaRef, ArgIdx);
2233
2234           QualType T = SemaRef.SubstType(PackExpansion->getPattern(),
2235                                          TemplateArgs,
2236                                        New->getLocation(), New->getDeclName());
2237           if (T.isNull()) {
2238             Invalid = true;
2239             break;
2240           }
2241
2242           Exceptions.push_back(T);
2243         }
2244
2245         if (Invalid)
2246           break;
2247
2248         continue;
2249       }
2250
2251       QualType T
2252         = SemaRef.SubstType(Proto->getExceptionType(I), TemplateArgs,
2253                             New->getLocation(), New->getDeclName());
2254       if (T.isNull() ||
2255           SemaRef.CheckSpecifiedExceptionType(T, New->getLocation()))
2256         continue;
2257
2258       Exceptions.push_back(T);
2259     }
2260     Expr *NoexceptExpr = 0;
2261     if (Expr *OldNoexceptExpr = Proto->getNoexceptExpr()) {
2262       EnterExpressionEvaluationContext Unevaluated(SemaRef, Sema::Unevaluated);
2263       ExprResult E = SemaRef.SubstExpr(OldNoexceptExpr, TemplateArgs);
2264       if (E.isUsable())
2265         NoexceptExpr = E.take();
2266     }
2267
2268     // Rebuild the function type
2269
2270     FunctionProtoType::ExtProtoInfo EPI = Proto->getExtProtoInfo();
2271     EPI.ExceptionSpecType = Proto->getExceptionSpecType();
2272     EPI.NumExceptions = Exceptions.size();
2273     EPI.Exceptions = Exceptions.data();
2274     EPI.NoexceptExpr = NoexceptExpr;
2275     EPI.ExtInfo = Proto->getExtInfo();
2276
2277     const FunctionProtoType *NewProto
2278       = New->getType()->getAs<FunctionProtoType>();
2279     assert(NewProto && "Template instantiation without function prototype?");
2280     New->setType(SemaRef.Context.getFunctionType(NewProto->getResultType(),
2281                                                  NewProto->arg_type_begin(),
2282                                                  NewProto->getNumArgs(),
2283                                                  EPI));
2284   }
2285
2286   const FunctionDecl* Definition = Tmpl;
2287
2288   // Get the definition. Leaves the variable unchanged if undefined.
2289   Tmpl->isDefined(Definition);
2290
2291   SemaRef.InstantiateAttrs(TemplateArgs, Definition, New);
2292
2293   return false;
2294 }
2295
2296 /// \brief Initializes common fields of an instantiated method
2297 /// declaration (New) from the corresponding fields of its template
2298 /// (Tmpl).
2299 ///
2300 /// \returns true if there was an error
2301 bool
2302 TemplateDeclInstantiator::InitMethodInstantiation(CXXMethodDecl *New,
2303                                                   CXXMethodDecl *Tmpl) {
2304   if (InitFunctionInstantiation(New, Tmpl))
2305     return true;
2306
2307   New->setAccess(Tmpl->getAccess());
2308   if (Tmpl->isVirtualAsWritten())
2309     New->setVirtualAsWritten(true);
2310
2311   // FIXME: attributes
2312   // FIXME: New needs a pointer to Tmpl
2313   return false;
2314 }
2315
2316 /// \brief Instantiate the definition of the given function from its
2317 /// template.
2318 ///
2319 /// \param PointOfInstantiation the point at which the instantiation was
2320 /// required. Note that this is not precisely a "point of instantiation"
2321 /// for the function, but it's close.
2322 ///
2323 /// \param Function the already-instantiated declaration of a
2324 /// function template specialization or member function of a class template
2325 /// specialization.
2326 ///
2327 /// \param Recursive if true, recursively instantiates any functions that
2328 /// are required by this instantiation.
2329 ///
2330 /// \param DefinitionRequired if true, then we are performing an explicit
2331 /// instantiation where the body of the function is required. Complain if
2332 /// there is no such body.
2333 void Sema::InstantiateFunctionDefinition(SourceLocation PointOfInstantiation,
2334                                          FunctionDecl *Function,
2335                                          bool Recursive,
2336                                          bool DefinitionRequired) {
2337   if (Function->isInvalidDecl() || Function->isDefined())
2338     return;
2339
2340   // Never instantiate an explicit specialization.
2341   if (Function->getTemplateSpecializationKind() == TSK_ExplicitSpecialization)
2342     return;
2343
2344   // Find the function body that we'll be substituting.
2345   const FunctionDecl *PatternDecl = Function->getTemplateInstantiationPattern();
2346   assert(PatternDecl && "instantiating a non-template");
2347
2348   Stmt *Pattern = PatternDecl->getBody(PatternDecl);
2349   assert(PatternDecl && "template definition is not a template");
2350   if (!Pattern) {
2351     // Try to find a defaulted definition
2352     PatternDecl->isDefined(PatternDecl);
2353   }
2354   assert(PatternDecl && "template definition is not a template");
2355
2356   // Postpone late parsed template instantiations.
2357   if (PatternDecl->isLateTemplateParsed() &&
2358       !LateTemplateParser) {
2359     PendingInstantiations.push_back(
2360       std::make_pair(Function, PointOfInstantiation));
2361     return;
2362   }
2363
2364   // Call the LateTemplateParser callback if there a need to late parse
2365   // a templated function definition.
2366   if (!Pattern && PatternDecl->isLateTemplateParsed() &&
2367       LateTemplateParser) {
2368     LateTemplateParser(OpaqueParser, PatternDecl);
2369     Pattern = PatternDecl->getBody(PatternDecl);
2370   }
2371
2372   if (!Pattern && !PatternDecl->isDefaulted()) {
2373     if (DefinitionRequired) {
2374       if (Function->getPrimaryTemplate())
2375         Diag(PointOfInstantiation,
2376              diag::err_explicit_instantiation_undefined_func_template)
2377           << Function->getPrimaryTemplate();
2378       else
2379         Diag(PointOfInstantiation,
2380              diag::err_explicit_instantiation_undefined_member)
2381           << 1 << Function->getDeclName() << Function->getDeclContext();
2382
2383       if (PatternDecl)
2384         Diag(PatternDecl->getLocation(),
2385              diag::note_explicit_instantiation_here);
2386       Function->setInvalidDecl();
2387     } else if (Function->getTemplateSpecializationKind()
2388                  == TSK_ExplicitInstantiationDefinition) {
2389       PendingInstantiations.push_back(
2390         std::make_pair(Function, PointOfInstantiation));
2391     }
2392
2393     return;
2394   }
2395
2396   // C++0x [temp.explicit]p9:
2397   //   Except for inline functions, other explicit instantiation declarations
2398   //   have the effect of suppressing the implicit instantiation of the entity
2399   //   to which they refer.
2400   if (Function->getTemplateSpecializationKind()
2401         == TSK_ExplicitInstantiationDeclaration &&
2402       !PatternDecl->isInlined())
2403     return;
2404
2405   InstantiatingTemplate Inst(*this, PointOfInstantiation, Function);
2406   if (Inst)
2407     return;
2408
2409   // If we're performing recursive template instantiation, create our own
2410   // queue of pending implicit instantiations that we will instantiate later,
2411   // while we're still within our own instantiation context.
2412   llvm::SmallVector<VTableUse, 16> SavedVTableUses;
2413   std::deque<PendingImplicitInstantiation> SavedPendingInstantiations;
2414   if (Recursive) {
2415     VTableUses.swap(SavedVTableUses);
2416     PendingInstantiations.swap(SavedPendingInstantiations);
2417   }
2418
2419   EnterExpressionEvaluationContext EvalContext(*this,
2420                                                Sema::PotentiallyEvaluated);
2421   ActOnStartOfFunctionDef(0, Function);
2422
2423   // Introduce a new scope where local variable instantiations will be
2424   // recorded, unless we're actually a member function within a local
2425   // class, in which case we need to merge our results with the parent
2426   // scope (of the enclosing function).
2427   bool MergeWithParentScope = false;
2428   if (CXXRecordDecl *Rec = dyn_cast<CXXRecordDecl>(Function->getDeclContext()))
2429     MergeWithParentScope = Rec->isLocalClass();
2430
2431   LocalInstantiationScope Scope(*this, MergeWithParentScope);
2432
2433   // Introduce the instantiated function parameters into the local
2434   // instantiation scope, and set the parameter names to those used
2435   // in the template.
2436   unsigned FParamIdx = 0;
2437   for (unsigned I = 0, N = PatternDecl->getNumParams(); I != N; ++I) {
2438     const ParmVarDecl *PatternParam = PatternDecl->getParamDecl(I);
2439     if (!PatternParam->isParameterPack()) {
2440       // Simple case: not a parameter pack.
2441       assert(FParamIdx < Function->getNumParams());
2442       ParmVarDecl *FunctionParam = Function->getParamDecl(I);
2443       FunctionParam->setDeclName(PatternParam->getDeclName());
2444       Scope.InstantiatedLocal(PatternParam, FunctionParam);
2445       ++FParamIdx;
2446       continue;
2447     }
2448
2449     // Expand the parameter pack.
2450     Scope.MakeInstantiatedLocalArgPack(PatternParam);
2451     for (unsigned NumFParams = Function->getNumParams();
2452          FParamIdx < NumFParams;
2453          ++FParamIdx) {
2454       ParmVarDecl *FunctionParam = Function->getParamDecl(FParamIdx);
2455       FunctionParam->setDeclName(PatternParam->getDeclName());
2456       Scope.InstantiatedLocalPackArg(PatternParam, FunctionParam);
2457     }
2458   }
2459
2460   // Enter the scope of this instantiation. We don't use
2461   // PushDeclContext because we don't have a scope.
2462   Sema::ContextRAII savedContext(*this, Function);
2463
2464   MultiLevelTemplateArgumentList TemplateArgs =
2465     getTemplateInstantiationArgs(Function, 0, false, PatternDecl);
2466
2467   if (PatternDecl->isDefaulted()) {
2468     ActOnFinishFunctionBody(Function, 0, /*IsInstantiation=*/true);
2469
2470     SetDeclDefaulted(Function, PatternDecl->getLocation());
2471   } else {
2472     // If this is a constructor, instantiate the member initializers.
2473     if (const CXXConstructorDecl *Ctor =
2474           dyn_cast<CXXConstructorDecl>(PatternDecl)) {
2475       InstantiateMemInitializers(cast<CXXConstructorDecl>(Function), Ctor,
2476                                  TemplateArgs);
2477     }
2478
2479     // Instantiate the function body.
2480     StmtResult Body = SubstStmt(Pattern, TemplateArgs);
2481
2482     if (Body.isInvalid())
2483       Function->setInvalidDecl();
2484
2485     ActOnFinishFunctionBody(Function, Body.get(),
2486                             /*IsInstantiation=*/true);
2487   }
2488
2489   PerformDependentDiagnostics(PatternDecl, TemplateArgs);
2490
2491   savedContext.pop();
2492
2493   DeclGroupRef DG(Function);
2494   Consumer.HandleTopLevelDecl(DG);
2495
2496   // This class may have local implicit instantiations that need to be
2497   // instantiation within this scope.
2498   PerformPendingInstantiations(/*LocalOnly=*/true);
2499   Scope.Exit();
2500
2501   if (Recursive) {
2502     // Define any pending vtables.
2503     DefineUsedVTables();
2504
2505     // Instantiate any pending implicit instantiations found during the
2506     // instantiation of this template.
2507     PerformPendingInstantiations();
2508
2509     // Restore the set of pending vtables.
2510     assert(VTableUses.empty() &&
2511            "VTableUses should be empty before it is discarded.");
2512     VTableUses.swap(SavedVTableUses);
2513
2514     // Restore the set of pending implicit instantiations.
2515     assert(PendingInstantiations.empty() &&
2516            "PendingInstantiations should be empty before it is discarded.");
2517     PendingInstantiations.swap(SavedPendingInstantiations);
2518   }
2519 }
2520
2521 /// \brief Instantiate the definition of the given variable from its
2522 /// template.
2523 ///
2524 /// \param PointOfInstantiation the point at which the instantiation was
2525 /// required. Note that this is not precisely a "point of instantiation"
2526 /// for the function, but it's close.
2527 ///
2528 /// \param Var the already-instantiated declaration of a static member
2529 /// variable of a class template specialization.
2530 ///
2531 /// \param Recursive if true, recursively instantiates any functions that
2532 /// are required by this instantiation.
2533 ///
2534 /// \param DefinitionRequired if true, then we are performing an explicit
2535 /// instantiation where an out-of-line definition of the member variable
2536 /// is required. Complain if there is no such definition.
2537 void Sema::InstantiateStaticDataMemberDefinition(
2538                                           SourceLocation PointOfInstantiation,
2539                                                  VarDecl *Var,
2540                                                  bool Recursive,
2541                                                  bool DefinitionRequired) {
2542   if (Var->isInvalidDecl())
2543     return;
2544
2545   // Find the out-of-line definition of this static data member.
2546   VarDecl *Def = Var->getInstantiatedFromStaticDataMember();
2547   assert(Def && "This data member was not instantiated from a template?");
2548   assert(Def->isStaticDataMember() && "Not a static data member?");
2549   Def = Def->getOutOfLineDefinition();
2550
2551   if (!Def) {
2552     // We did not find an out-of-line definition of this static data member,
2553     // so we won't perform any instantiation. Rather, we rely on the user to
2554     // instantiate this definition (or provide a specialization for it) in
2555     // another translation unit.
2556     if (DefinitionRequired) {
2557       Def = Var->getInstantiatedFromStaticDataMember();
2558       Diag(PointOfInstantiation,
2559            diag::err_explicit_instantiation_undefined_member)
2560         << 2 << Var->getDeclName() << Var->getDeclContext();
2561       Diag(Def->getLocation(), diag::note_explicit_instantiation_here);
2562     } else if (Var->getTemplateSpecializationKind()
2563                  == TSK_ExplicitInstantiationDefinition) {
2564       PendingInstantiations.push_back(
2565         std::make_pair(Var, PointOfInstantiation));
2566     }
2567
2568     return;
2569   }
2570
2571   // Never instantiate an explicit specialization.
2572   if (Var->getTemplateSpecializationKind() == TSK_ExplicitSpecialization)
2573     return;
2574
2575   // C++0x [temp.explicit]p9:
2576   //   Except for inline functions, other explicit instantiation declarations
2577   //   have the effect of suppressing the implicit instantiation of the entity
2578   //   to which they refer.
2579   if (Var->getTemplateSpecializationKind()
2580         == TSK_ExplicitInstantiationDeclaration)
2581     return;
2582
2583   // If we already have a definition, we're done.
2584   if (Var->getDefinition())
2585     return;
2586
2587   InstantiatingTemplate Inst(*this, PointOfInstantiation, Var);
2588   if (Inst)
2589     return;
2590
2591   // If we're performing recursive template instantiation, create our own
2592   // queue of pending implicit instantiations that we will instantiate later,
2593   // while we're still within our own instantiation context.
2594   llvm::SmallVector<VTableUse, 16> SavedVTableUses;
2595   std::deque<PendingImplicitInstantiation> SavedPendingInstantiations;
2596   if (Recursive) {
2597     VTableUses.swap(SavedVTableUses);
2598     PendingInstantiations.swap(SavedPendingInstantiations);
2599   }
2600
2601   // Enter the scope of this instantiation. We don't use
2602   // PushDeclContext because we don't have a scope.
2603   ContextRAII previousContext(*this, Var->getDeclContext());
2604
2605   VarDecl *OldVar = Var;
2606   Var = cast_or_null<VarDecl>(SubstDecl(Def, Var->getDeclContext(),
2607                                         getTemplateInstantiationArgs(Var)));
2608
2609   previousContext.pop();
2610
2611   if (Var) {
2612     MemberSpecializationInfo *MSInfo = OldVar->getMemberSpecializationInfo();
2613     assert(MSInfo && "Missing member specialization information?");
2614     Var->setTemplateSpecializationKind(MSInfo->getTemplateSpecializationKind(),
2615                                        MSInfo->getPointOfInstantiation());
2616     DeclGroupRef DG(Var);
2617     Consumer.HandleTopLevelDecl(DG);
2618   }
2619
2620   if (Recursive) {
2621     // Define any newly required vtables.
2622     DefineUsedVTables();
2623
2624     // Instantiate any pending implicit instantiations found during the
2625     // instantiation of this template.
2626     PerformPendingInstantiations();
2627
2628     // Restore the set of pending vtables.
2629     assert(VTableUses.empty() &&
2630            "VTableUses should be empty before it is discarded, "
2631            "while instantiating static data member.");
2632     VTableUses.swap(SavedVTableUses);
2633
2634     // Restore the set of pending implicit instantiations.
2635     assert(PendingInstantiations.empty() &&
2636            "PendingInstantiations should be empty before it is discarded, "
2637            "while instantiating static data member.");
2638     PendingInstantiations.swap(SavedPendingInstantiations);
2639   }
2640 }
2641
2642 void
2643 Sema::InstantiateMemInitializers(CXXConstructorDecl *New,
2644                                  const CXXConstructorDecl *Tmpl,
2645                            const MultiLevelTemplateArgumentList &TemplateArgs) {
2646
2647   llvm::SmallVector<MemInitTy*, 4> NewInits;
2648   bool AnyErrors = false;
2649
2650   // Instantiate all the initializers.
2651   for (CXXConstructorDecl::init_const_iterator Inits = Tmpl->init_begin(),
2652                                             InitsEnd = Tmpl->init_end();
2653        Inits != InitsEnd; ++Inits) {
2654     CXXCtorInitializer *Init = *Inits;
2655
2656     // Only instantiate written initializers, let Sema re-construct implicit
2657     // ones.
2658     if (!Init->isWritten())
2659       continue;
2660
2661     SourceLocation LParenLoc, RParenLoc;
2662     ASTOwningVector<Expr*> NewArgs(*this);
2663
2664     SourceLocation EllipsisLoc;
2665
2666     if (Init->isPackExpansion()) {
2667       // This is a pack expansion. We should expand it now.
2668       TypeLoc BaseTL = Init->getBaseClassInfo()->getTypeLoc();
2669       llvm::SmallVector<UnexpandedParameterPack, 2> Unexpanded;
2670       collectUnexpandedParameterPacks(BaseTL, Unexpanded);
2671       bool ShouldExpand = false;
2672       bool RetainExpansion = false;
2673       llvm::Optional<unsigned> NumExpansions;
2674       if (CheckParameterPacksForExpansion(Init->getEllipsisLoc(),
2675                                           BaseTL.getSourceRange(),
2676                                           Unexpanded.data(),
2677                                           Unexpanded.size(),
2678                                           TemplateArgs, ShouldExpand,
2679                                           RetainExpansion,
2680                                           NumExpansions)) {
2681         AnyErrors = true;
2682         New->setInvalidDecl();
2683         continue;
2684       }
2685       assert(ShouldExpand && "Partial instantiation of base initializer?");
2686
2687       // Loop over all of the arguments in the argument pack(s),
2688       for (unsigned I = 0; I != *NumExpansions; ++I) {
2689         Sema::ArgumentPackSubstitutionIndexRAII SubstIndex(*this, I);
2690
2691         // Instantiate the initializer.
2692         if (InstantiateInitializer(*this, Init->getInit(), TemplateArgs,
2693                                    LParenLoc, NewArgs, RParenLoc)) {
2694           AnyErrors = true;
2695           break;
2696         }
2697
2698         // Instantiate the base type.
2699         TypeSourceInfo *BaseTInfo = SubstType(Init->getBaseClassInfo(),
2700                                               TemplateArgs,
2701                                               Init->getSourceLocation(),
2702                                               New->getDeclName());
2703         if (!BaseTInfo) {
2704           AnyErrors = true;
2705           break;
2706         }
2707
2708         // Build the initializer.
2709         MemInitResult NewInit = BuildBaseInitializer(BaseTInfo->getType(),
2710                                                      BaseTInfo,
2711                                                      (Expr **)NewArgs.data(),
2712                                                      NewArgs.size(),
2713                                                      Init->getLParenLoc(),
2714                                                      Init->getRParenLoc(),
2715                                                      New->getParent(),
2716                                                      SourceLocation());
2717         if (NewInit.isInvalid()) {
2718           AnyErrors = true;
2719           break;
2720         }
2721
2722         NewInits.push_back(NewInit.get());
2723         NewArgs.clear();
2724       }
2725
2726       continue;
2727     }
2728
2729     // Instantiate the initializer.
2730     if (InstantiateInitializer(*this, Init->getInit(), TemplateArgs,
2731                                LParenLoc, NewArgs, RParenLoc)) {
2732       AnyErrors = true;
2733       continue;
2734     }
2735
2736     MemInitResult NewInit;
2737     if (Init->isBaseInitializer()) {
2738       TypeSourceInfo *BaseTInfo = SubstType(Init->getBaseClassInfo(),
2739                                             TemplateArgs,
2740                                             Init->getSourceLocation(),
2741                                             New->getDeclName());
2742       if (!BaseTInfo) {
2743         AnyErrors = true;
2744         New->setInvalidDecl();
2745         continue;
2746       }
2747
2748       NewInit = BuildBaseInitializer(BaseTInfo->getType(), BaseTInfo,
2749                                      (Expr **)NewArgs.data(),
2750                                      NewArgs.size(),
2751                                      Init->getLParenLoc(),
2752                                      Init->getRParenLoc(),
2753                                      New->getParent(),
2754                                      EllipsisLoc);
2755     } else if (Init->isMemberInitializer()) {
2756       FieldDecl *Member = cast_or_null<FieldDecl>(FindInstantiatedDecl(
2757                                                      Init->getMemberLocation(),
2758                                                      Init->getMember(),
2759                                                      TemplateArgs));
2760       if (!Member) {
2761         AnyErrors = true;
2762         New->setInvalidDecl();
2763         continue;
2764       }
2765
2766       NewInit = BuildMemberInitializer(Member, (Expr **)NewArgs.data(),
2767                                        NewArgs.size(),
2768                                        Init->getSourceLocation(),
2769                                        Init->getLParenLoc(),
2770                                        Init->getRParenLoc());
2771     } else if (Init->isIndirectMemberInitializer()) {
2772       IndirectFieldDecl *IndirectMember =
2773          cast_or_null<IndirectFieldDecl>(FindInstantiatedDecl(
2774                                  Init->getMemberLocation(),
2775                                  Init->getIndirectMember(), TemplateArgs));
2776
2777       if (!IndirectMember) {
2778         AnyErrors = true;
2779         New->setInvalidDecl();
2780         continue;
2781       }
2782
2783       NewInit = BuildMemberInitializer(IndirectMember, (Expr **)NewArgs.data(),
2784                                        NewArgs.size(),
2785                                        Init->getSourceLocation(),
2786                                        Init->getLParenLoc(),
2787                                        Init->getRParenLoc());
2788     }
2789
2790     if (NewInit.isInvalid()) {
2791       AnyErrors = true;
2792       New->setInvalidDecl();
2793     } else {
2794       // FIXME: It would be nice if ASTOwningVector had a release function.
2795       NewArgs.take();
2796
2797       NewInits.push_back((MemInitTy *)NewInit.get());
2798     }
2799   }
2800
2801   // Assign all the initializers to the new constructor.
2802   ActOnMemInitializers(New,
2803                        /*FIXME: ColonLoc */
2804                        SourceLocation(),
2805                        NewInits.data(), NewInits.size(),
2806                        AnyErrors);
2807 }
2808
2809 // TODO: this could be templated if the various decl types used the
2810 // same method name.
2811 static bool isInstantiationOf(ClassTemplateDecl *Pattern,
2812                               ClassTemplateDecl *Instance) {
2813   Pattern = Pattern->getCanonicalDecl();
2814
2815   do {
2816     Instance = Instance->getCanonicalDecl();
2817     if (Pattern == Instance) return true;
2818     Instance = Instance->getInstantiatedFromMemberTemplate();
2819   } while (Instance);
2820
2821   return false;
2822 }
2823
2824 static bool isInstantiationOf(FunctionTemplateDecl *Pattern,
2825                               FunctionTemplateDecl *Instance) {
2826   Pattern = Pattern->getCanonicalDecl();
2827
2828   do {
2829     Instance = Instance->getCanonicalDecl();
2830     if (Pattern == Instance) return true;
2831     Instance = Instance->getInstantiatedFromMemberTemplate();
2832   } while (Instance);
2833
2834   return false;
2835 }
2836
2837 static bool
2838 isInstantiationOf(ClassTemplatePartialSpecializationDecl *Pattern,
2839                   ClassTemplatePartialSpecializationDecl *Instance) {
2840   Pattern
2841     = cast<ClassTemplatePartialSpecializationDecl>(Pattern->getCanonicalDecl());
2842   do {
2843     Instance = cast<ClassTemplatePartialSpecializationDecl>(
2844                                                 Instance->getCanonicalDecl());
2845     if (Pattern == Instance)
2846       return true;
2847     Instance = Instance->getInstantiatedFromMember();
2848   } while (Instance);
2849
2850   return false;
2851 }
2852
2853 static bool isInstantiationOf(CXXRecordDecl *Pattern,
2854                               CXXRecordDecl *Instance) {
2855   Pattern = Pattern->getCanonicalDecl();
2856
2857   do {
2858     Instance = Instance->getCanonicalDecl();
2859     if (Pattern == Instance) return true;
2860     Instance = Instance->getInstantiatedFromMemberClass();
2861   } while (Instance);
2862
2863   return false;
2864 }
2865
2866 static bool isInstantiationOf(FunctionDecl *Pattern,
2867                               FunctionDecl *Instance) {
2868   Pattern = Pattern->getCanonicalDecl();
2869
2870   do {
2871     Instance = Instance->getCanonicalDecl();
2872     if (Pattern == Instance) return true;
2873     Instance = Instance->getInstantiatedFromMemberFunction();
2874   } while (Instance);
2875
2876   return false;
2877 }
2878
2879 static bool isInstantiationOf(EnumDecl *Pattern,
2880                               EnumDecl *Instance) {
2881   Pattern = Pattern->getCanonicalDecl();
2882
2883   do {
2884     Instance = Instance->getCanonicalDecl();
2885     if (Pattern == Instance) return true;
2886     Instance = Instance->getInstantiatedFromMemberEnum();
2887   } while (Instance);
2888
2889   return false;
2890 }
2891
2892 static bool isInstantiationOf(UsingShadowDecl *Pattern,
2893                               UsingShadowDecl *Instance,
2894                               ASTContext &C) {
2895   return C.getInstantiatedFromUsingShadowDecl(Instance) == Pattern;
2896 }
2897
2898 static bool isInstantiationOf(UsingDecl *Pattern,
2899                               UsingDecl *Instance,
2900                               ASTContext &C) {
2901   return C.getInstantiatedFromUsingDecl(Instance) == Pattern;
2902 }
2903
2904 static bool isInstantiationOf(UnresolvedUsingValueDecl *Pattern,
2905                               UsingDecl *Instance,
2906                               ASTContext &C) {
2907   return C.getInstantiatedFromUsingDecl(Instance) == Pattern;
2908 }
2909
2910 static bool isInstantiationOf(UnresolvedUsingTypenameDecl *Pattern,
2911                               UsingDecl *Instance,
2912                               ASTContext &C) {
2913   return C.getInstantiatedFromUsingDecl(Instance) == Pattern;
2914 }
2915
2916 static bool isInstantiationOfStaticDataMember(VarDecl *Pattern,
2917                                               VarDecl *Instance) {
2918   assert(Instance->isStaticDataMember());
2919
2920   Pattern = Pattern->getCanonicalDecl();
2921
2922   do {
2923     Instance = Instance->getCanonicalDecl();
2924     if (Pattern == Instance) return true;
2925     Instance = Instance->getInstantiatedFromStaticDataMember();
2926   } while (Instance);
2927
2928   return false;
2929 }
2930
2931 // Other is the prospective instantiation
2932 // D is the prospective pattern
2933 static bool isInstantiationOf(ASTContext &Ctx, NamedDecl *D, Decl *Other) {
2934   if (D->getKind() != Other->getKind()) {
2935     if (UnresolvedUsingTypenameDecl *UUD
2936           = dyn_cast<UnresolvedUsingTypenameDecl>(D)) {
2937       if (UsingDecl *UD = dyn_cast<UsingDecl>(Other)) {
2938         return isInstantiationOf(UUD, UD, Ctx);
2939       }
2940     }
2941
2942     if (UnresolvedUsingValueDecl *UUD
2943           = dyn_cast<UnresolvedUsingValueDecl>(D)) {
2944       if (UsingDecl *UD = dyn_cast<UsingDecl>(Other)) {
2945         return isInstantiationOf(UUD, UD, Ctx);
2946       }
2947     }
2948
2949     return false;
2950   }
2951
2952   if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(Other))
2953     return isInstantiationOf(cast<CXXRecordDecl>(D), Record);
2954
2955   if (FunctionDecl *Function = dyn_cast<FunctionDecl>(Other))
2956     return isInstantiationOf(cast<FunctionDecl>(D), Function);
2957
2958   if (EnumDecl *Enum = dyn_cast<EnumDecl>(Other))
2959     return isInstantiationOf(cast<EnumDecl>(D), Enum);
2960
2961   if (VarDecl *Var = dyn_cast<VarDecl>(Other))
2962     if (Var->isStaticDataMember())
2963       return isInstantiationOfStaticDataMember(cast<VarDecl>(D), Var);
2964
2965   if (ClassTemplateDecl *Temp = dyn_cast<ClassTemplateDecl>(Other))
2966     return isInstantiationOf(cast<ClassTemplateDecl>(D), Temp);
2967
2968   if (FunctionTemplateDecl *Temp = dyn_cast<FunctionTemplateDecl>(Other))
2969     return isInstantiationOf(cast<FunctionTemplateDecl>(D), Temp);
2970
2971   if (ClassTemplatePartialSpecializationDecl *PartialSpec
2972         = dyn_cast<ClassTemplatePartialSpecializationDecl>(Other))
2973     return isInstantiationOf(cast<ClassTemplatePartialSpecializationDecl>(D),
2974                              PartialSpec);
2975
2976   if (FieldDecl *Field = dyn_cast<FieldDecl>(Other)) {
2977     if (!Field->getDeclName()) {
2978       // This is an unnamed field.
2979       return Ctx.getInstantiatedFromUnnamedFieldDecl(Field) ==
2980         cast<FieldDecl>(D);
2981     }
2982   }
2983
2984   if (UsingDecl *Using = dyn_cast<UsingDecl>(Other))
2985     return isInstantiationOf(cast<UsingDecl>(D), Using, Ctx);
2986
2987   if (UsingShadowDecl *Shadow = dyn_cast<UsingShadowDecl>(Other))
2988     return isInstantiationOf(cast<UsingShadowDecl>(D), Shadow, Ctx);
2989
2990   return D->getDeclName() && isa<NamedDecl>(Other) &&
2991     D->getDeclName() == cast<NamedDecl>(Other)->getDeclName();
2992 }
2993
2994 template<typename ForwardIterator>
2995 static NamedDecl *findInstantiationOf(ASTContext &Ctx,
2996                                       NamedDecl *D,
2997                                       ForwardIterator first,
2998                                       ForwardIterator last) {
2999   for (; first != last; ++first)
3000     if (isInstantiationOf(Ctx, D, *first))
3001       return cast<NamedDecl>(*first);
3002
3003   return 0;
3004 }
3005
3006 /// \brief Finds the instantiation of the given declaration context
3007 /// within the current instantiation.
3008 ///
3009 /// \returns NULL if there was an error
3010 DeclContext *Sema::FindInstantiatedContext(SourceLocation Loc, DeclContext* DC,
3011                           const MultiLevelTemplateArgumentList &TemplateArgs) {
3012   if (NamedDecl *D = dyn_cast<NamedDecl>(DC)) {
3013     Decl* ID = FindInstantiatedDecl(Loc, D, TemplateArgs);
3014     return cast_or_null<DeclContext>(ID);
3015   } else return DC;
3016 }
3017
3018 /// \brief Find the instantiation of the given declaration within the
3019 /// current instantiation.
3020 ///
3021 /// This routine is intended to be used when \p D is a declaration
3022 /// referenced from within a template, that needs to mapped into the
3023 /// corresponding declaration within an instantiation. For example,
3024 /// given:
3025 ///
3026 /// \code
3027 /// template<typename T>
3028 /// struct X {
3029 ///   enum Kind {
3030 ///     KnownValue = sizeof(T)
3031 ///   };
3032 ///
3033 ///   bool getKind() const { return KnownValue; }
3034 /// };
3035 ///
3036 /// template struct X<int>;
3037 /// \endcode
3038 ///
3039 /// In the instantiation of X<int>::getKind(), we need to map the
3040 /// EnumConstantDecl for KnownValue (which refers to
3041 /// X<T>::<Kind>::KnownValue) to its instantiation
3042 /// (X<int>::<Kind>::KnownValue). InstantiateCurrentDeclRef() performs
3043 /// this mapping from within the instantiation of X<int>.
3044 NamedDecl *Sema::FindInstantiatedDecl(SourceLocation Loc, NamedDecl *D,
3045                           const MultiLevelTemplateArgumentList &TemplateArgs) {
3046   DeclContext *ParentDC = D->getDeclContext();
3047   if (isa<ParmVarDecl>(D) || isa<NonTypeTemplateParmDecl>(D) ||
3048       isa<TemplateTypeParmDecl>(D) || isa<TemplateTemplateParmDecl>(D) ||
3049       (ParentDC->isFunctionOrMethod() && ParentDC->isDependentContext())) {
3050     // D is a local of some kind. Look into the map of local
3051     // declarations to their instantiations.
3052     typedef LocalInstantiationScope::DeclArgumentPack DeclArgumentPack;
3053     llvm::PointerUnion<Decl *, DeclArgumentPack *> *Found
3054       = CurrentInstantiationScope->findInstantiationOf(D);
3055
3056     if (Found) {
3057       if (Decl *FD = Found->dyn_cast<Decl *>())
3058         return cast<NamedDecl>(FD);
3059
3060       unsigned PackIdx = ArgumentPackSubstitutionIndex;
3061       return cast<NamedDecl>((*Found->get<DeclArgumentPack *>())[PackIdx]);
3062     }
3063
3064     // If we didn't find the decl, then we must have a label decl that hasn't
3065     // been found yet.  Lazily instantiate it and return it now.
3066     assert(isa<LabelDecl>(D));
3067
3068     Decl *Inst = SubstDecl(D, CurContext, TemplateArgs);
3069     assert(Inst && "Failed to instantiate label??");
3070
3071     CurrentInstantiationScope->InstantiatedLocal(D, Inst);
3072     return cast<LabelDecl>(Inst);
3073   }
3074
3075   if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(D)) {
3076     if (!Record->isDependentContext())
3077       return D;
3078
3079     // If the RecordDecl is actually the injected-class-name or a
3080     // "templated" declaration for a class template, class template
3081     // partial specialization, or a member class of a class template,
3082     // substitute into the injected-class-name of the class template
3083     // or partial specialization to find the new DeclContext.
3084     QualType T;
3085     ClassTemplateDecl *ClassTemplate = Record->getDescribedClassTemplate();
3086
3087     if (ClassTemplate) {
3088       T = ClassTemplate->getInjectedClassNameSpecialization();
3089     } else if (ClassTemplatePartialSpecializationDecl *PartialSpec
3090                  = dyn_cast<ClassTemplatePartialSpecializationDecl>(Record)) {
3091       ClassTemplate = PartialSpec->getSpecializedTemplate();
3092
3093       // If we call SubstType with an InjectedClassNameType here we
3094       // can end up in an infinite loop.
3095       T = Context.getTypeDeclType(Record);
3096       assert(isa<InjectedClassNameType>(T) &&
3097              "type of partial specialization is not an InjectedClassNameType");
3098       T = cast<InjectedClassNameType>(T)->getInjectedSpecializationType();
3099     }
3100
3101     if (!T.isNull()) {
3102       // Substitute into the injected-class-name to get the type
3103       // corresponding to the instantiation we want, which may also be
3104       // the current instantiation (if we're in a template
3105       // definition). This substitution should never fail, since we
3106       // know we can instantiate the injected-class-name or we
3107       // wouldn't have gotten to the injected-class-name!
3108
3109       // FIXME: Can we use the CurrentInstantiationScope to avoid this
3110       // extra instantiation in the common case?
3111       T = SubstType(T, TemplateArgs, Loc, DeclarationName());
3112       assert(!T.isNull() && "Instantiation of injected-class-name cannot fail.");
3113
3114       if (!T->isDependentType()) {
3115         assert(T->isRecordType() && "Instantiation must produce a record type");
3116         return T->getAs<RecordType>()->getDecl();
3117       }
3118
3119       // We are performing "partial" template instantiation to create
3120       // the member declarations for the members of a class template
3121       // specialization. Therefore, D is actually referring to something
3122       // in the current instantiation. Look through the current
3123       // context, which contains actual instantiations, to find the
3124       // instantiation of the "current instantiation" that D refers
3125       // to.
3126       bool SawNonDependentContext = false;
3127       for (DeclContext *DC = CurContext; !DC->isFileContext();
3128            DC = DC->getParent()) {
3129         if (ClassTemplateSpecializationDecl *Spec
3130                           = dyn_cast<ClassTemplateSpecializationDecl>(DC))
3131           if (isInstantiationOf(ClassTemplate,
3132                                 Spec->getSpecializedTemplate()))
3133             return Spec;
3134
3135         if (!DC->isDependentContext())
3136           SawNonDependentContext = true;
3137       }
3138
3139       // We're performing "instantiation" of a member of the current
3140       // instantiation while we are type-checking the
3141       // definition. Compute the declaration context and return that.
3142       assert(!SawNonDependentContext &&
3143              "No dependent context while instantiating record");
3144       DeclContext *DC = computeDeclContext(T);
3145       assert(DC &&
3146              "Unable to find declaration for the current instantiation");
3147       return cast<CXXRecordDecl>(DC);
3148     }
3149
3150     // Fall through to deal with other dependent record types (e.g.,
3151     // anonymous unions in class templates).
3152   }
3153
3154   if (!ParentDC->isDependentContext())
3155     return D;
3156
3157   ParentDC = FindInstantiatedContext(Loc, ParentDC, TemplateArgs);
3158   if (!ParentDC)
3159     return 0;
3160
3161   if (ParentDC != D->getDeclContext()) {
3162     // We performed some kind of instantiation in the parent context,
3163     // so now we need to look into the instantiated parent context to
3164     // find the instantiation of the declaration D.
3165
3166     // If our context used to be dependent, we may need to instantiate
3167     // it before performing lookup into that context.
3168     bool IsBeingInstantiated = false;
3169     if (CXXRecordDecl *Spec = dyn_cast<CXXRecordDecl>(ParentDC)) {
3170       if (!Spec->isDependentContext()) {
3171         QualType T = Context.getTypeDeclType(Spec);
3172         const RecordType *Tag = T->getAs<RecordType>();
3173         assert(Tag && "type of non-dependent record is not a RecordType");
3174         if (Tag->isBeingDefined())
3175           IsBeingInstantiated = true;
3176         if (!Tag->isBeingDefined() &&
3177             RequireCompleteType(Loc, T, diag::err_incomplete_type))
3178           return 0;
3179
3180         ParentDC = Tag->getDecl();
3181       }
3182     }
3183
3184     NamedDecl *Result = 0;
3185     if (D->getDeclName()) {
3186       DeclContext::lookup_result Found = ParentDC->lookup(D->getDeclName());
3187       Result = findInstantiationOf(Context, D, Found.first, Found.second);
3188     } else {
3189       // Since we don't have a name for the entity we're looking for,
3190       // our only option is to walk through all of the declarations to
3191       // find that name. This will occur in a few cases:
3192       //
3193       //   - anonymous struct/union within a template
3194       //   - unnamed class/struct/union/enum within a template
3195       //
3196       // FIXME: Find a better way to find these instantiations!
3197       Result = findInstantiationOf(Context, D,
3198                                    ParentDC->decls_begin(),
3199                                    ParentDC->decls_end());
3200     }
3201
3202     if (!Result) {
3203       if (isa<UsingShadowDecl>(D)) {
3204         // UsingShadowDecls can instantiate to nothing because of using hiding.
3205       } else if (Diags.hasErrorOccurred()) {
3206         // We've already complained about something, so most likely this
3207         // declaration failed to instantiate. There's no point in complaining
3208         // further, since this is normal in invalid code.
3209       } else if (IsBeingInstantiated) {
3210         // The class in which this member exists is currently being
3211         // instantiated, and we haven't gotten around to instantiating this
3212         // member yet. This can happen when the code uses forward declarations
3213         // of member classes, and introduces ordering dependencies via
3214         // template instantiation.
3215         Diag(Loc, diag::err_member_not_yet_instantiated)
3216           << D->getDeclName()
3217           << Context.getTypeDeclType(cast<CXXRecordDecl>(ParentDC));
3218         Diag(D->getLocation(), diag::note_non_instantiated_member_here);
3219       } else {
3220         // We should have found something, but didn't.
3221         llvm_unreachable("Unable to find instantiation of declaration!");
3222       }
3223     }
3224
3225     D = Result;
3226   }
3227
3228   return D;
3229 }
3230
3231 /// \brief Performs template instantiation for all implicit template
3232 /// instantiations we have seen until this point.
3233 void Sema::PerformPendingInstantiations(bool LocalOnly) {
3234   while (!PendingLocalImplicitInstantiations.empty() ||
3235          (!LocalOnly && !PendingInstantiations.empty())) {
3236     PendingImplicitInstantiation Inst;
3237
3238     if (PendingLocalImplicitInstantiations.empty()) {
3239       Inst = PendingInstantiations.front();
3240       PendingInstantiations.pop_front();
3241     } else {
3242       Inst = PendingLocalImplicitInstantiations.front();
3243       PendingLocalImplicitInstantiations.pop_front();
3244     }
3245
3246     // Instantiate function definitions
3247     if (FunctionDecl *Function = dyn_cast<FunctionDecl>(Inst.first)) {
3248       PrettyDeclStackTraceEntry CrashInfo(*this, Function, SourceLocation(),
3249                                           "instantiating function definition");
3250       bool DefinitionRequired = Function->getTemplateSpecializationKind() ==
3251                                 TSK_ExplicitInstantiationDefinition;
3252       InstantiateFunctionDefinition(/*FIXME:*/Inst.second, Function, true,
3253                                     DefinitionRequired);
3254       continue;
3255     }
3256
3257     // Instantiate static data member definitions.
3258     VarDecl *Var = cast<VarDecl>(Inst.first);
3259     assert(Var->isStaticDataMember() && "Not a static data member?");
3260
3261     // Don't try to instantiate declarations if the most recent redeclaration
3262     // is invalid.
3263     if (Var->getMostRecentDeclaration()->isInvalidDecl())
3264       continue;
3265
3266     // Check if the most recent declaration has changed the specialization kind
3267     // and removed the need for implicit instantiation.
3268     switch (Var->getMostRecentDeclaration()->getTemplateSpecializationKind()) {
3269     case TSK_Undeclared:
3270       assert(false && "Cannot instantitiate an undeclared specialization.");
3271     case TSK_ExplicitInstantiationDeclaration:
3272     case TSK_ExplicitSpecialization:
3273       continue;  // No longer need to instantiate this type.
3274     case TSK_ExplicitInstantiationDefinition:
3275       // We only need an instantiation if the pending instantiation *is* the
3276       // explicit instantiation.
3277       if (Var != Var->getMostRecentDeclaration()) continue;
3278     case TSK_ImplicitInstantiation:
3279       break;
3280     }
3281
3282     PrettyDeclStackTraceEntry CrashInfo(*this, Var, Var->getLocation(),
3283                                         "instantiating static data member "
3284                                         "definition");
3285
3286     bool DefinitionRequired = Var->getTemplateSpecializationKind() ==
3287                               TSK_ExplicitInstantiationDefinition;
3288     InstantiateStaticDataMemberDefinition(/*FIXME:*/Inst.second, Var, true,
3289                                           DefinitionRequired);
3290   }
3291 }
3292
3293 void Sema::PerformDependentDiagnostics(const DeclContext *Pattern,
3294                        const MultiLevelTemplateArgumentList &TemplateArgs) {
3295   for (DeclContext::ddiag_iterator I = Pattern->ddiag_begin(),
3296          E = Pattern->ddiag_end(); I != E; ++I) {
3297     DependentDiagnostic *DD = *I;
3298
3299     switch (DD->getKind()) {
3300     case DependentDiagnostic::Access:
3301       HandleDependentAccessCheck(*DD, TemplateArgs);
3302       break;
3303     }
3304   }
3305 }