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