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