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