SemaTemplateInstantiateDecl.cpp revision 6e769988ffd4b543a8bf1e7aba5e83f770838363 
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 "Sema.h"
13#include "Lookup.h"
14#include "clang/AST/ASTConsumer.h"
15#include "clang/AST/ASTContext.h"
16#include "clang/AST/DeclTemplate.h"
17#include "clang/AST/DeclVisitor.h"
18#include "clang/AST/Expr.h"
19#include "clang/AST/ExprCXX.h"
20#include "clang/AST/TypeLoc.h"
21#include "clang/Basic/PrettyStackTrace.h"
22#include "clang/Lex/Preprocessor.h"
23
24using namespace clang;
25
26namespace {
27  class TemplateDeclInstantiator
28    : public DeclVisitor<TemplateDeclInstantiator, Decl *> {
29    Sema &SemaRef;
30    DeclContext *Owner;
31    const MultiLevelTemplateArgumentList &TemplateArgs;
32
33    void InstantiateAttrs(Decl *Tmpl, Decl *New);
34
35  public:
36    typedef Sema::OwningExprResult OwningExprResult;
37
38    TemplateDeclInstantiator(Sema &SemaRef, DeclContext *Owner,
39                             const MultiLevelTemplateArgumentList &TemplateArgs)
40      : SemaRef(SemaRef), Owner(Owner), TemplateArgs(TemplateArgs) { }
41
42    // FIXME: Once we get closer to completion, replace these manually-written
43    // declarations with automatically-generated ones from
44    // clang/AST/DeclNodes.def.
45    Decl *VisitTranslationUnitDecl(TranslationUnitDecl *D);
46    Decl *VisitNamespaceDecl(NamespaceDecl *D);
47    Decl *VisitNamespaceAliasDecl(NamespaceAliasDecl *D);
48    Decl *VisitTypedefDecl(TypedefDecl *D);
49    Decl *VisitVarDecl(VarDecl *D);
50    Decl *VisitFieldDecl(FieldDecl *D);
51    Decl *VisitStaticAssertDecl(StaticAssertDecl *D);
52    Decl *VisitEnumDecl(EnumDecl *D);
53    Decl *VisitEnumConstantDecl(EnumConstantDecl *D);
54    Decl *VisitFriendDecl(FriendDecl *D);
55    Decl *VisitFunctionDecl(FunctionDecl *D,
56                            TemplateParameterList *TemplateParams = 0);
57    Decl *VisitCXXRecordDecl(CXXRecordDecl *D);
58    Decl *VisitCXXMethodDecl(CXXMethodDecl *D,
59                             TemplateParameterList *TemplateParams = 0);
60    Decl *VisitCXXConstructorDecl(CXXConstructorDecl *D);
61    Decl *VisitCXXDestructorDecl(CXXDestructorDecl *D);
62    Decl *VisitCXXConversionDecl(CXXConversionDecl *D);
63    ParmVarDecl *VisitParmVarDecl(ParmVarDecl *D);
64    Decl *VisitClassTemplateDecl(ClassTemplateDecl *D);
65    Decl *VisitClassTemplatePartialSpecializationDecl(
66                                    ClassTemplatePartialSpecializationDecl *D);
67    Decl *VisitFunctionTemplateDecl(FunctionTemplateDecl *D);
68    Decl *VisitTemplateTypeParmDecl(TemplateTypeParmDecl *D);
69    Decl *VisitNonTypeTemplateParmDecl(NonTypeTemplateParmDecl *D);
70    Decl *VisitTemplateTemplateParmDecl(TemplateTemplateParmDecl *D);
71    Decl *VisitUsingDirectiveDecl(UsingDirectiveDecl *D);
72    Decl *VisitUsingDecl(UsingDecl *D);
73    Decl *VisitUsingShadowDecl(UsingShadowDecl *D);
74    Decl *VisitUnresolvedUsingValueDecl(UnresolvedUsingValueDecl *D);
75    Decl *VisitUnresolvedUsingTypenameDecl(UnresolvedUsingTypenameDecl *D);
76
77    // Base case. FIXME: Remove once we can instantiate everything.
78    Decl *VisitDecl(Decl *D) {
79      unsigned DiagID = SemaRef.getDiagnostics().getCustomDiagID(
80                                                            Diagnostic::Error,
81                                                   "cannot instantiate %0 yet");
82      SemaRef.Diag(D->getLocation(), DiagID)
83        << D->getDeclKindName();
84
85      return 0;
86    }
87
88    const LangOptions &getLangOptions() {
89      return SemaRef.getLangOptions();
90    }
91
92    // Helper functions for instantiating methods.
93    TypeSourceInfo *SubstFunctionType(FunctionDecl *D,
94                             llvm::SmallVectorImpl<ParmVarDecl *> &Params);
95    bool InitFunctionInstantiation(FunctionDecl *New, FunctionDecl *Tmpl);
96    bool InitMethodInstantiation(CXXMethodDecl *New, CXXMethodDecl *Tmpl);
97
98    TemplateParameterList *
99      SubstTemplateParams(TemplateParameterList *List);
100
101    bool InstantiateClassTemplatePartialSpecialization(
102                                              ClassTemplateDecl *ClassTemplate,
103                           ClassTemplatePartialSpecializationDecl *PartialSpec);
104  };
105}
106
107// FIXME: Is this too simple?
108void TemplateDeclInstantiator::InstantiateAttrs(Decl *Tmpl, Decl *New) {
109  for (const Attr *TmplAttr = Tmpl->getAttrs(); TmplAttr;
110       TmplAttr = TmplAttr->getNext()) {
111
112    // FIXME: Is cloning correct for all attributes?
113    Attr *NewAttr = TmplAttr->clone(SemaRef.Context);
114
115    New->addAttr(NewAttr);
116  }
117}
118
119Decl *
120TemplateDeclInstantiator::VisitTranslationUnitDecl(TranslationUnitDecl *D) {
121  assert(false && "Translation units cannot be instantiated");
122  return D;
123}
124
125Decl *
126TemplateDeclInstantiator::VisitNamespaceDecl(NamespaceDecl *D) {
127  assert(false && "Namespaces cannot be instantiated");
128  return D;
129}
130
131Decl *
132TemplateDeclInstantiator::VisitNamespaceAliasDecl(NamespaceAliasDecl *D) {
133  NamespaceAliasDecl *Inst
134    = NamespaceAliasDecl::Create(SemaRef.Context, Owner,
135                                 D->getNamespaceLoc(),
136                                 D->getAliasLoc(),
137                                 D->getNamespace()->getIdentifier(),
138                                 D->getQualifierRange(),
139                                 D->getQualifier(),
140                                 D->getTargetNameLoc(),
141                                 D->getNamespace());
142  Owner->addDecl(Inst);
143  return Inst;
144}
145
146Decl *TemplateDeclInstantiator::VisitTypedefDecl(TypedefDecl *D) {
147  bool Invalid = false;
148  TypeSourceInfo *DI = D->getTypeSourceInfo();
149  if (DI->getType()->isDependentType()) {
150    DI = SemaRef.SubstType(DI, TemplateArgs,
151                           D->getLocation(), D->getDeclName());
152    if (!DI) {
153      Invalid = true;
154      DI = SemaRef.Context.getTrivialTypeSourceInfo(SemaRef.Context.IntTy);
155    }
156  }
157
158  // Create the new typedef
159  TypedefDecl *Typedef
160    = TypedefDecl::Create(SemaRef.Context, Owner, D->getLocation(),
161                          D->getIdentifier(), DI);
162  if (Invalid)
163    Typedef->setInvalidDecl();
164
165  if (TypedefDecl *Prev = D->getPreviousDeclaration()) {
166    NamedDecl *InstPrev = SemaRef.FindInstantiatedDecl(D->getLocation(), Prev,
167                                                       TemplateArgs);
168    Typedef->setPreviousDeclaration(cast<TypedefDecl>(InstPrev));
169  }
170
171  Typedef->setAccess(D->getAccess());
172  Owner->addDecl(Typedef);
173
174  return Typedef;
175}
176
177/// \brief Instantiate the arguments provided as part of initialization.
178///
179/// \returns true if an error occurred, false otherwise.
180static bool InstantiateInitializationArguments(Sema &SemaRef,
181                                               Expr **Args, unsigned NumArgs,
182                           const MultiLevelTemplateArgumentList &TemplateArgs,
183                         llvm::SmallVectorImpl<SourceLocation> &FakeCommaLocs,
184                           ASTOwningVector<&ActionBase::DeleteExpr> &InitArgs) {
185  for (unsigned I = 0; I != NumArgs; ++I) {
186    // When we hit the first defaulted argument, break out of the loop:
187    // we don't pass those default arguments on.
188    if (Args[I]->isDefaultArgument())
189      break;
190
191    Sema::OwningExprResult Arg = SemaRef.SubstExpr(Args[I], TemplateArgs);
192    if (Arg.isInvalid())
193      return true;
194
195    Expr *ArgExpr = (Expr *)Arg.get();
196    InitArgs.push_back(Arg.release());
197
198    // FIXME: We're faking all of the comma locations. Do we need them?
199    FakeCommaLocs.push_back(
200                          SemaRef.PP.getLocForEndOfToken(ArgExpr->getLocEnd()));
201  }
202
203  return false;
204}
205
206/// \brief Instantiate an initializer, breaking it into separate
207/// initialization arguments.
208///
209/// \param S The semantic analysis object.
210///
211/// \param Init The initializer to instantiate.
212///
213/// \param TemplateArgs Template arguments to be substituted into the
214/// initializer.
215///
216/// \param NewArgs Will be filled in with the instantiation arguments.
217///
218/// \returns true if an error occurred, false otherwise
219static bool InstantiateInitializer(Sema &S, Expr *Init,
220                            const MultiLevelTemplateArgumentList &TemplateArgs,
221                                   SourceLocation &LParenLoc,
222                               llvm::SmallVector<SourceLocation, 4> &CommaLocs,
223                             ASTOwningVector<&ActionBase::DeleteExpr> &NewArgs,
224                                   SourceLocation &RParenLoc) {
225  NewArgs.clear();
226  LParenLoc = SourceLocation();
227  RParenLoc = SourceLocation();
228
229  if (!Init)
230    return false;
231
232  if (CXXExprWithTemporaries *ExprTemp = dyn_cast<CXXExprWithTemporaries>(Init))
233    Init = ExprTemp->getSubExpr();
234
235  while (CXXBindTemporaryExpr *Binder = dyn_cast<CXXBindTemporaryExpr>(Init))
236    Init = Binder->getSubExpr();
237
238  if (ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(Init))
239    Init = ICE->getSubExprAsWritten();
240
241  if (ParenListExpr *ParenList = dyn_cast<ParenListExpr>(Init)) {
242    LParenLoc = ParenList->getLParenLoc();
243    RParenLoc = ParenList->getRParenLoc();
244    return InstantiateInitializationArguments(S, ParenList->getExprs(),
245                                              ParenList->getNumExprs(),
246                                              TemplateArgs, CommaLocs,
247                                              NewArgs);
248  }
249
250  if (CXXConstructExpr *Construct = dyn_cast<CXXConstructExpr>(Init)) {
251    if (InstantiateInitializationArguments(S,
252                                           Construct->getArgs(),
253                                           Construct->getNumArgs(),
254                                           TemplateArgs,
255                                           CommaLocs, NewArgs))
256      return true;
257
258    // FIXME: Fake locations!
259    LParenLoc = S.PP.getLocForEndOfToken(Init->getLocStart());
260    RParenLoc = CommaLocs.empty()? LParenLoc : CommaLocs.back();
261    return false;
262  }
263
264  Sema::OwningExprResult Result = S.SubstExpr(Init, TemplateArgs);
265  if (Result.isInvalid())
266    return true;
267
268  NewArgs.push_back(Result.takeAs<Expr>());
269  return false;
270}
271
272Decl *TemplateDeclInstantiator::VisitVarDecl(VarDecl *D) {
273  // Do substitution on the type of the declaration
274  TypeSourceInfo *DI = SemaRef.SubstType(D->getTypeSourceInfo(),
275                                         TemplateArgs,
276                                         D->getTypeSpecStartLoc(),
277                                         D->getDeclName());
278  if (!DI)
279    return 0;
280
281  // Build the instantiated declaration
282  VarDecl *Var = VarDecl::Create(SemaRef.Context, Owner,
283                                 D->getLocation(), D->getIdentifier(),
284                                 DI->getType(), DI,
285                                 D->getStorageClass());
286  Var->setThreadSpecified(D->isThreadSpecified());
287  Var->setCXXDirectInitializer(D->hasCXXDirectInitializer());
288  Var->setDeclaredInCondition(D->isDeclaredInCondition());
289
290  // If we are instantiating a static data member defined
291  // out-of-line, the instantiation will have the same lexical
292  // context (which will be a namespace scope) as the template.
293  if (D->isOutOfLine())
294    Var->setLexicalDeclContext(D->getLexicalDeclContext());
295
296  Var->setAccess(D->getAccess());
297
298  // FIXME: In theory, we could have a previous declaration for variables that
299  // are not static data members.
300  bool Redeclaration = false;
301  // FIXME: having to fake up a LookupResult is dumb.
302  LookupResult Previous(SemaRef, Var->getDeclName(), Var->getLocation(),
303                        Sema::LookupOrdinaryName, Sema::ForRedeclaration);
304  if (D->isStaticDataMember())
305    SemaRef.LookupQualifiedName(Previous, Owner, false);
306  SemaRef.CheckVariableDeclaration(Var, Previous, Redeclaration);
307
308  if (D->isOutOfLine()) {
309    D->getLexicalDeclContext()->addDecl(Var);
310    Owner->makeDeclVisibleInContext(Var);
311  } else {
312    Owner->addDecl(Var);
313  }
314
315  // Link instantiations of static data members back to the template from
316  // which they were instantiated.
317  if (Var->isStaticDataMember())
318    SemaRef.Context.setInstantiatedFromStaticDataMember(Var, D,
319                                                     TSK_ImplicitInstantiation);
320
321  if (Var->getAnyInitializer()) {
322    // We already have an initializer in the class.
323  } else if (D->getInit()) {
324    if (Var->isStaticDataMember() && !D->isOutOfLine())
325      SemaRef.PushExpressionEvaluationContext(Sema::Unevaluated);
326    else
327      SemaRef.PushExpressionEvaluationContext(Sema::PotentiallyEvaluated);
328
329    // Instantiate the initializer.
330    SourceLocation LParenLoc, RParenLoc;
331    llvm::SmallVector<SourceLocation, 4> CommaLocs;
332    ASTOwningVector<&ActionBase::DeleteExpr> InitArgs(SemaRef);
333    if (!InstantiateInitializer(SemaRef, D->getInit(), TemplateArgs, LParenLoc,
334                                CommaLocs, InitArgs, RParenLoc)) {
335      // Attach the initializer to the declaration.
336      if (D->hasCXXDirectInitializer()) {
337        // Add the direct initializer to the declaration.
338        SemaRef.AddCXXDirectInitializerToDecl(Sema::DeclPtrTy::make(Var),
339                                              LParenLoc,
340                                              move_arg(InitArgs),
341                                              CommaLocs.data(),
342                                              RParenLoc);
343      } else if (InitArgs.size() == 1) {
344        Expr *Init = (Expr*)(InitArgs.take()[0]);
345        SemaRef.AddInitializerToDecl(Sema::DeclPtrTy::make(Var),
346                                     SemaRef.Owned(Init),
347                                     false);
348      } else {
349        assert(InitArgs.size() == 0);
350        SemaRef.ActOnUninitializedDecl(Sema::DeclPtrTy::make(Var), false);
351      }
352    } else {
353      // FIXME: Not too happy about invalidating the declaration
354      // because of a bogus initializer.
355      Var->setInvalidDecl();
356    }
357
358    SemaRef.PopExpressionEvaluationContext();
359  } else if (!Var->isStaticDataMember() || Var->isOutOfLine())
360    SemaRef.ActOnUninitializedDecl(Sema::DeclPtrTy::make(Var), false);
361
362  return Var;
363}
364
365Decl *TemplateDeclInstantiator::VisitFieldDecl(FieldDecl *D) {
366  bool Invalid = false;
367  TypeSourceInfo *DI = D->getTypeSourceInfo();
368  if (DI->getType()->isDependentType())  {
369    DI = SemaRef.SubstType(DI, TemplateArgs,
370                           D->getLocation(), D->getDeclName());
371    if (!DI) {
372      DI = D->getTypeSourceInfo();
373      Invalid = true;
374    } else if (DI->getType()->isFunctionType()) {
375      // C++ [temp.arg.type]p3:
376      //   If a declaration acquires a function type through a type
377      //   dependent on a template-parameter and this causes a
378      //   declaration that does not use the syntactic form of a
379      //   function declarator to have function type, the program is
380      //   ill-formed.
381      SemaRef.Diag(D->getLocation(), diag::err_field_instantiates_to_function)
382        << DI->getType();
383      Invalid = true;
384    }
385  }
386
387  Expr *BitWidth = D->getBitWidth();
388  if (Invalid)
389    BitWidth = 0;
390  else if (BitWidth) {
391    // The bit-width expression is not potentially evaluated.
392    EnterExpressionEvaluationContext Unevaluated(SemaRef, Action::Unevaluated);
393
394    OwningExprResult InstantiatedBitWidth
395      = SemaRef.SubstExpr(BitWidth, TemplateArgs);
396    if (InstantiatedBitWidth.isInvalid()) {
397      Invalid = true;
398      BitWidth = 0;
399    } else
400      BitWidth = InstantiatedBitWidth.takeAs<Expr>();
401  }
402
403  FieldDecl *Field = SemaRef.CheckFieldDecl(D->getDeclName(),
404                                            DI->getType(), DI,
405                                            cast<RecordDecl>(Owner),
406                                            D->getLocation(),
407                                            D->isMutable(),
408                                            BitWidth,
409                                            D->getTypeSpecStartLoc(),
410                                            D->getAccess(),
411                                            0);
412  if (!Field) {
413    cast<Decl>(Owner)->setInvalidDecl();
414    return 0;
415  }
416
417  InstantiateAttrs(D, Field);
418
419  if (Invalid)
420    Field->setInvalidDecl();
421
422  if (!Field->getDeclName()) {
423    // Keep track of where this decl came from.
424    SemaRef.Context.setInstantiatedFromUnnamedFieldDecl(Field, D);
425  }
426
427  Field->setImplicit(D->isImplicit());
428  Field->setAccess(D->getAccess());
429  Owner->addDecl(Field);
430
431  return Field;
432}
433
434Decl *TemplateDeclInstantiator::VisitFriendDecl(FriendDecl *D) {
435  FriendDecl::FriendUnion FU;
436
437  // Handle friend type expressions by simply substituting template
438  // parameters into the pattern type.
439  if (Type *Ty = D->getFriendType()) {
440    QualType T = SemaRef.SubstType(QualType(Ty,0), TemplateArgs,
441                                   D->getLocation(), DeclarationName());
442    if (T.isNull()) return 0;
443
444    assert(getLangOptions().CPlusPlus0x || T->isRecordType());
445    FU = T.getTypePtr();
446
447  // Handle everything else by appropriate substitution.
448  } else {
449    NamedDecl *ND = D->getFriendDecl();
450    assert(ND && "friend decl must be a decl or a type!");
451
452    // FIXME: We have a problem here, because the nested call to Visit(ND)
453    // will inject the thing that the friend references into the current
454    // owner, which is wrong.
455    Decl *NewND;
456
457    // Hack to make this work almost well pending a rewrite.
458    if (ND->getDeclContext()->isRecord()) {
459      if (!ND->getDeclContext()->isDependentContext()) {
460        NewND = SemaRef.FindInstantiatedDecl(D->getLocation(), ND,
461                                             TemplateArgs);
462      } else {
463        // FIXME: Hack to avoid crashing when incorrectly trying to instantiate
464        // templated friend declarations. This doesn't produce a correct AST;
465        // however this is sufficient for some AST analysis. The real solution
466        // must be put in place during the pending rewrite. See PR5848.
467        return 0;
468      }
469    } else if (D->wasSpecialization()) {
470      // Totally egregious hack to work around PR5866
471      return 0;
472    } else
473      NewND = Visit(ND);
474    if (!NewND) return 0;
475
476    FU = cast<NamedDecl>(NewND);
477  }
478
479  FriendDecl *FD =
480    FriendDecl::Create(SemaRef.Context, Owner, D->getLocation(), FU,
481                       D->getFriendLoc());
482  FD->setAccess(AS_public);
483  Owner->addDecl(FD);
484  return FD;
485}
486
487Decl *TemplateDeclInstantiator::VisitStaticAssertDecl(StaticAssertDecl *D) {
488  Expr *AssertExpr = D->getAssertExpr();
489
490  // The expression in a static assertion is not potentially evaluated.
491  EnterExpressionEvaluationContext Unevaluated(SemaRef, Action::Unevaluated);
492
493  OwningExprResult InstantiatedAssertExpr
494    = SemaRef.SubstExpr(AssertExpr, TemplateArgs);
495  if (InstantiatedAssertExpr.isInvalid())
496    return 0;
497
498  OwningExprResult Message(SemaRef, D->getMessage());
499  D->getMessage()->Retain();
500  Decl *StaticAssert
501    = SemaRef.ActOnStaticAssertDeclaration(D->getLocation(),
502                                           move(InstantiatedAssertExpr),
503                                           move(Message)).getAs<Decl>();
504  return StaticAssert;
505}
506
507Decl *TemplateDeclInstantiator::VisitEnumDecl(EnumDecl *D) {
508  EnumDecl *Enum = EnumDecl::Create(SemaRef.Context, Owner,
509                                    D->getLocation(), D->getIdentifier(),
510                                    D->getTagKeywordLoc(),
511                                    /*PrevDecl=*/0);
512  Enum->setInstantiationOfMemberEnum(D);
513  Enum->setAccess(D->getAccess());
514  Owner->addDecl(Enum);
515  Enum->startDefinition();
516
517  if (D->getDeclContext()->isFunctionOrMethod())
518    SemaRef.CurrentInstantiationScope->InstantiatedLocal(D, Enum);
519
520  llvm::SmallVector<Sema::DeclPtrTy, 4> Enumerators;
521
522  EnumConstantDecl *LastEnumConst = 0;
523  for (EnumDecl::enumerator_iterator EC = D->enumerator_begin(),
524         ECEnd = D->enumerator_end();
525       EC != ECEnd; ++EC) {
526    // The specified value for the enumerator.
527    OwningExprResult Value = SemaRef.Owned((Expr *)0);
528    if (Expr *UninstValue = EC->getInitExpr()) {
529      // The enumerator's value expression is not potentially evaluated.
530      EnterExpressionEvaluationContext Unevaluated(SemaRef,
531                                                   Action::Unevaluated);
532
533      Value = SemaRef.SubstExpr(UninstValue, TemplateArgs);
534    }
535
536    // Drop the initial value and continue.
537    bool isInvalid = false;
538    if (Value.isInvalid()) {
539      Value = SemaRef.Owned((Expr *)0);
540      isInvalid = true;
541    }
542
543    EnumConstantDecl *EnumConst
544      = SemaRef.CheckEnumConstant(Enum, LastEnumConst,
545                                  EC->getLocation(), EC->getIdentifier(),
546                                  move(Value));
547
548    if (isInvalid) {
549      if (EnumConst)
550        EnumConst->setInvalidDecl();
551      Enum->setInvalidDecl();
552    }
553
554    if (EnumConst) {
555      EnumConst->setAccess(Enum->getAccess());
556      Enum->addDecl(EnumConst);
557      Enumerators.push_back(Sema::DeclPtrTy::make(EnumConst));
558      LastEnumConst = EnumConst;
559
560      if (D->getDeclContext()->isFunctionOrMethod()) {
561        // If the enumeration is within a function or method, record the enum
562        // constant as a local.
563        SemaRef.CurrentInstantiationScope->InstantiatedLocal(*EC, EnumConst);
564      }
565    }
566  }
567
568  // FIXME: Fixup LBraceLoc and RBraceLoc
569  // FIXME: Empty Scope and AttributeList (required to handle attribute packed).
570  SemaRef.ActOnEnumBody(Enum->getLocation(), SourceLocation(), SourceLocation(),
571                        Sema::DeclPtrTy::make(Enum),
572                        &Enumerators[0], Enumerators.size(),
573                        0, 0);
574
575  return Enum;
576}
577
578Decl *TemplateDeclInstantiator::VisitEnumConstantDecl(EnumConstantDecl *D) {
579  assert(false && "EnumConstantDecls can only occur within EnumDecls.");
580  return 0;
581}
582
583namespace {
584  class SortDeclByLocation {
585    SourceManager &SourceMgr;
586
587  public:
588    explicit SortDeclByLocation(SourceManager &SourceMgr)
589      : SourceMgr(SourceMgr) { }
590
591    bool operator()(const Decl *X, const Decl *Y) const {
592      return SourceMgr.isBeforeInTranslationUnit(X->getLocation(),
593                                                 Y->getLocation());
594    }
595  };
596}
597
598Decl *TemplateDeclInstantiator::VisitClassTemplateDecl(ClassTemplateDecl *D) {
599  // Create a local instantiation scope for this class template, which
600  // will contain the instantiations of the template parameters.
601  Sema::LocalInstantiationScope Scope(SemaRef);
602  TemplateParameterList *TempParams = D->getTemplateParameters();
603  TemplateParameterList *InstParams = SubstTemplateParams(TempParams);
604  if (!InstParams)
605    return NULL;
606
607  CXXRecordDecl *Pattern = D->getTemplatedDecl();
608  CXXRecordDecl *RecordInst
609    = CXXRecordDecl::Create(SemaRef.Context, Pattern->getTagKind(), Owner,
610                            Pattern->getLocation(), Pattern->getIdentifier(),
611                            Pattern->getTagKeywordLoc(), /*PrevDecl=*/ NULL,
612                            /*DelayTypeCreation=*/true);
613
614  ClassTemplateDecl *Inst
615    = ClassTemplateDecl::Create(SemaRef.Context, Owner, D->getLocation(),
616                                D->getIdentifier(), InstParams, RecordInst, 0);
617  RecordInst->setDescribedClassTemplate(Inst);
618  if (D->getFriendObjectKind())
619    Inst->setObjectOfFriendDecl(true);
620  else
621    Inst->setAccess(D->getAccess());
622  Inst->setInstantiatedFromMemberTemplate(D);
623
624  // Trigger creation of the type for the instantiation.
625  SemaRef.Context.getInjectedClassNameType(RecordInst,
626                  Inst->getInjectedClassNameSpecialization(SemaRef.Context));
627
628  // Finish handling of friends.
629  if (Inst->getFriendObjectKind()) {
630    return Inst;
631  }
632
633  Inst->setAccess(D->getAccess());
634  Owner->addDecl(Inst);
635
636  // First, we sort the partial specializations by location, so
637  // that we instantiate them in the order they were declared.
638  llvm::SmallVector<ClassTemplatePartialSpecializationDecl *, 4> PartialSpecs;
639  for (llvm::FoldingSet<ClassTemplatePartialSpecializationDecl>::iterator
640         P = D->getPartialSpecializations().begin(),
641         PEnd = D->getPartialSpecializations().end();
642       P != PEnd; ++P)
643    PartialSpecs.push_back(&*P);
644  std::sort(PartialSpecs.begin(), PartialSpecs.end(),
645            SortDeclByLocation(SemaRef.SourceMgr));
646
647  // Instantiate all of the partial specializations of this member class
648  // template.
649  for (unsigned I = 0, N = PartialSpecs.size(); I != N; ++I)
650    InstantiateClassTemplatePartialSpecialization(Inst, PartialSpecs[I]);
651
652  return Inst;
653}
654
655Decl *
656TemplateDeclInstantiator::VisitClassTemplatePartialSpecializationDecl(
657                                   ClassTemplatePartialSpecializationDecl *D) {
658  ClassTemplateDecl *ClassTemplate = D->getSpecializedTemplate();
659
660  // Lookup the already-instantiated declaration in the instantiation
661  // of the class template and return that.
662  DeclContext::lookup_result Found
663    = Owner->lookup(ClassTemplate->getDeclName());
664  if (Found.first == Found.second)
665    return 0;
666
667  ClassTemplateDecl *InstClassTemplate
668    = dyn_cast<ClassTemplateDecl>(*Found.first);
669  if (!InstClassTemplate)
670    return 0;
671
672  Decl *DCanon = D->getCanonicalDecl();
673  for (llvm::FoldingSet<ClassTemplatePartialSpecializationDecl>::iterator
674            P = InstClassTemplate->getPartialSpecializations().begin(),
675         PEnd = InstClassTemplate->getPartialSpecializations().end();
676       P != PEnd; ++P) {
677    if (P->getInstantiatedFromMember()->getCanonicalDecl() == DCanon)
678      return &*P;
679  }
680
681  return 0;
682}
683
684Decl *
685TemplateDeclInstantiator::VisitFunctionTemplateDecl(FunctionTemplateDecl *D) {
686  // Create a local instantiation scope for this function template, which
687  // will contain the instantiations of the template parameters and then get
688  // merged with the local instantiation scope for the function template
689  // itself.
690  Sema::LocalInstantiationScope Scope(SemaRef);
691
692  TemplateParameterList *TempParams = D->getTemplateParameters();
693  TemplateParameterList *InstParams = SubstTemplateParams(TempParams);
694  if (!InstParams)
695    return NULL;
696
697  FunctionDecl *Instantiated = 0;
698  if (CXXMethodDecl *DMethod = dyn_cast<CXXMethodDecl>(D->getTemplatedDecl()))
699    Instantiated = cast_or_null<FunctionDecl>(VisitCXXMethodDecl(DMethod,
700                                                                 InstParams));
701  else
702    Instantiated = cast_or_null<FunctionDecl>(VisitFunctionDecl(
703                                                          D->getTemplatedDecl(),
704                                                                InstParams));
705
706  if (!Instantiated)
707    return 0;
708
709  Instantiated->setAccess(D->getAccess());
710
711  // Link the instantiated function template declaration to the function
712  // template from which it was instantiated.
713  FunctionTemplateDecl *InstTemplate
714    = Instantiated->getDescribedFunctionTemplate();
715  InstTemplate->setAccess(D->getAccess());
716  assert(InstTemplate &&
717         "VisitFunctionDecl/CXXMethodDecl didn't create a template!");
718
719  // Link the instantiation back to the pattern *unless* this is a
720  // non-definition friend declaration.
721  if (!InstTemplate->getInstantiatedFromMemberTemplate() &&
722      !(InstTemplate->getFriendObjectKind() &&
723        !D->getTemplatedDecl()->isThisDeclarationADefinition()))
724    InstTemplate->setInstantiatedFromMemberTemplate(D);
725
726  // Add non-friends into the owner.
727  if (!InstTemplate->getFriendObjectKind())
728    Owner->addDecl(InstTemplate);
729  return InstTemplate;
730}
731
732Decl *TemplateDeclInstantiator::VisitCXXRecordDecl(CXXRecordDecl *D) {
733  CXXRecordDecl *PrevDecl = 0;
734  if (D->isInjectedClassName())
735    PrevDecl = cast<CXXRecordDecl>(Owner);
736  else if (D->getPreviousDeclaration()) {
737    NamedDecl *Prev = SemaRef.FindInstantiatedDecl(D->getLocation(),
738                                                   D->getPreviousDeclaration(),
739                                                   TemplateArgs);
740    if (!Prev) return 0;
741    PrevDecl = cast<CXXRecordDecl>(Prev);
742  }
743
744  CXXRecordDecl *Record
745    = CXXRecordDecl::Create(SemaRef.Context, D->getTagKind(), Owner,
746                            D->getLocation(), D->getIdentifier(),
747                            D->getTagKeywordLoc(), PrevDecl);
748  Record->setImplicit(D->isImplicit());
749  // FIXME: Check against AS_none is an ugly hack to work around the issue that
750  // the tag decls introduced by friend class declarations don't have an access
751  // specifier. Remove once this area of the code gets sorted out.
752  if (D->getAccess() != AS_none)
753    Record->setAccess(D->getAccess());
754  if (!D->isInjectedClassName())
755    Record->setInstantiationOfMemberClass(D, TSK_ImplicitInstantiation);
756
757  // If the original function was part of a friend declaration,
758  // inherit its namespace state.
759  if (Decl::FriendObjectKind FOK = D->getFriendObjectKind())
760    Record->setObjectOfFriendDecl(FOK == Decl::FOK_Declared);
761
762  Record->setAnonymousStructOrUnion(D->isAnonymousStructOrUnion());
763
764  Owner->addDecl(Record);
765  return Record;
766}
767
768/// Normal class members are of more specific types and therefore
769/// don't make it here.  This function serves two purposes:
770///   1) instantiating function templates
771///   2) substituting friend declarations
772/// FIXME: preserve function definitions in case #2
773Decl *TemplateDeclInstantiator::VisitFunctionDecl(FunctionDecl *D,
774                                       TemplateParameterList *TemplateParams) {
775  // Check whether there is already a function template specialization for
776  // this declaration.
777  FunctionTemplateDecl *FunctionTemplate = D->getDescribedFunctionTemplate();
778  void *InsertPos = 0;
779  if (FunctionTemplate && !TemplateParams) {
780    llvm::FoldingSetNodeID ID;
781    FunctionTemplateSpecializationInfo::Profile(ID,
782                             TemplateArgs.getInnermost().getFlatArgumentList(),
783                                       TemplateArgs.getInnermost().flat_size(),
784                                                SemaRef.Context);
785
786    FunctionTemplateSpecializationInfo *Info
787      = FunctionTemplate->getSpecializations().FindNodeOrInsertPos(ID,
788                                                                   InsertPos);
789
790    // If we already have a function template specialization, return it.
791    if (Info)
792      return Info->Function;
793  }
794
795  bool MergeWithParentScope = (TemplateParams != 0) ||
796    !(isa<Decl>(Owner) &&
797      cast<Decl>(Owner)->isDefinedOutsideFunctionOrMethod());
798  Sema::LocalInstantiationScope Scope(SemaRef, MergeWithParentScope);
799
800  llvm::SmallVector<ParmVarDecl *, 4> Params;
801  TypeSourceInfo *TInfo = D->getTypeSourceInfo();
802  TInfo = SubstFunctionType(D, Params);
803  if (!TInfo)
804    return 0;
805  QualType T = TInfo->getType();
806
807  // If we're instantiating a local function declaration, put the result
808  // in the owner;  otherwise we need to find the instantiated context.
809  DeclContext *DC;
810  if (D->getDeclContext()->isFunctionOrMethod())
811    DC = Owner;
812  else
813    DC = SemaRef.FindInstantiatedContext(D->getLocation(), D->getDeclContext(),
814                                         TemplateArgs);
815
816  FunctionDecl *Function =
817      FunctionDecl::Create(SemaRef.Context, DC, D->getLocation(),
818                           D->getDeclName(), T, TInfo,
819                           D->getStorageClass(),
820                           D->isInlineSpecified(), D->hasWrittenPrototype());
821  Function->setLexicalDeclContext(Owner);
822
823  // Attach the parameters
824  for (unsigned P = 0; P < Params.size(); ++P)
825    Params[P]->setOwningFunction(Function);
826  Function->setParams(Params.data(), Params.size());
827
828  if (TemplateParams) {
829    // Our resulting instantiation is actually a function template, since we
830    // are substituting only the outer template parameters. For example, given
831    //
832    //   template<typename T>
833    //   struct X {
834    //     template<typename U> friend void f(T, U);
835    //   };
836    //
837    //   X<int> x;
838    //
839    // We are instantiating the friend function template "f" within X<int>,
840    // which means substituting int for T, but leaving "f" as a friend function
841    // template.
842    // Build the function template itself.
843    FunctionTemplate = FunctionTemplateDecl::Create(SemaRef.Context, Owner,
844                                                    Function->getLocation(),
845                                                    Function->getDeclName(),
846                                                    TemplateParams, Function);
847    Function->setDescribedFunctionTemplate(FunctionTemplate);
848    FunctionTemplate->setLexicalDeclContext(D->getLexicalDeclContext());
849  } else if (FunctionTemplate) {
850    // Record this function template specialization.
851    Function->setFunctionTemplateSpecialization(FunctionTemplate,
852                                                &TemplateArgs.getInnermost(),
853                                                InsertPos);
854  }
855
856  if (InitFunctionInstantiation(Function, D))
857    Function->setInvalidDecl();
858
859  bool Redeclaration = false;
860  bool OverloadableAttrRequired = false;
861
862  LookupResult Previous(SemaRef, Function->getDeclName(), SourceLocation(),
863                        Sema::LookupOrdinaryName, Sema::ForRedeclaration);
864
865  if (TemplateParams || !FunctionTemplate) {
866    // Look only into the namespace where the friend would be declared to
867    // find a previous declaration. This is the innermost enclosing namespace,
868    // as described in ActOnFriendFunctionDecl.
869    SemaRef.LookupQualifiedName(Previous, DC);
870
871    // In C++, the previous declaration we find might be a tag type
872    // (class or enum). In this case, the new declaration will hide the
873    // tag type. Note that this does does not apply if we're declaring a
874    // typedef (C++ [dcl.typedef]p4).
875    if (Previous.isSingleTagDecl())
876      Previous.clear();
877  }
878
879  SemaRef.CheckFunctionDeclaration(/*Scope*/ 0, Function, Previous,
880                                   false, Redeclaration,
881                                   /*FIXME:*/OverloadableAttrRequired);
882
883  // If the original function was part of a friend declaration,
884  // inherit its namespace state and add it to the owner.
885  NamedDecl *FromFriendD
886      = TemplateParams? cast<NamedDecl>(D->getDescribedFunctionTemplate()) : D;
887  if (FromFriendD->getFriendObjectKind()) {
888    NamedDecl *ToFriendD = 0;
889    NamedDecl *PrevDecl;
890    if (TemplateParams) {
891      ToFriendD = cast<NamedDecl>(FunctionTemplate);
892      PrevDecl = FunctionTemplate->getPreviousDeclaration();
893    } else {
894      ToFriendD = Function;
895      PrevDecl = Function->getPreviousDeclaration();
896    }
897    ToFriendD->setObjectOfFriendDecl(PrevDecl != NULL);
898    if (!Owner->isDependentContext() && !PrevDecl)
899      DC->makeDeclVisibleInContext(ToFriendD, /* Recoverable = */ false);
900
901    if (!TemplateParams)
902      Function->setInstantiationOfMemberFunction(D, TSK_ImplicitInstantiation);
903  }
904
905  return Function;
906}
907
908Decl *
909TemplateDeclInstantiator::VisitCXXMethodDecl(CXXMethodDecl *D,
910                                      TemplateParameterList *TemplateParams) {
911  FunctionTemplateDecl *FunctionTemplate = D->getDescribedFunctionTemplate();
912  void *InsertPos = 0;
913  if (FunctionTemplate && !TemplateParams) {
914    // We are creating a function template specialization from a function
915    // template. Check whether there is already a function template
916    // specialization for this particular set of template arguments.
917    llvm::FoldingSetNodeID ID;
918    FunctionTemplateSpecializationInfo::Profile(ID,
919                            TemplateArgs.getInnermost().getFlatArgumentList(),
920                                      TemplateArgs.getInnermost().flat_size(),
921                                                SemaRef.Context);
922
923    FunctionTemplateSpecializationInfo *Info
924      = FunctionTemplate->getSpecializations().FindNodeOrInsertPos(ID,
925                                                                   InsertPos);
926
927    // If we already have a function template specialization, return it.
928    if (Info)
929      return Info->Function;
930  }
931
932  bool MergeWithParentScope = (TemplateParams != 0) ||
933    !(isa<Decl>(Owner) &&
934      cast<Decl>(Owner)->isDefinedOutsideFunctionOrMethod());
935  Sema::LocalInstantiationScope Scope(SemaRef, MergeWithParentScope);
936
937  llvm::SmallVector<ParmVarDecl *, 4> Params;
938  TypeSourceInfo *TInfo = D->getTypeSourceInfo();
939  TInfo = SubstFunctionType(D, Params);
940  if (!TInfo)
941    return 0;
942  QualType T = TInfo->getType();
943
944  // Build the instantiated method declaration.
945  CXXRecordDecl *Record = cast<CXXRecordDecl>(Owner);
946  CXXMethodDecl *Method = 0;
947
948  DeclarationName Name = D->getDeclName();
949  if (CXXConstructorDecl *Constructor = dyn_cast<CXXConstructorDecl>(D)) {
950    QualType ClassTy = SemaRef.Context.getTypeDeclType(Record);
951    Name = SemaRef.Context.DeclarationNames.getCXXConstructorName(
952                                    SemaRef.Context.getCanonicalType(ClassTy));
953    Method = CXXConstructorDecl::Create(SemaRef.Context, Record,
954                                        Constructor->getLocation(),
955                                        Name, T, TInfo,
956                                        Constructor->isExplicit(),
957                                        Constructor->isInlineSpecified(), false);
958  } else if (CXXDestructorDecl *Destructor = dyn_cast<CXXDestructorDecl>(D)) {
959    QualType ClassTy = SemaRef.Context.getTypeDeclType(Record);
960    Name = SemaRef.Context.DeclarationNames.getCXXDestructorName(
961                                   SemaRef.Context.getCanonicalType(ClassTy));
962    Method = CXXDestructorDecl::Create(SemaRef.Context, Record,
963                                       Destructor->getLocation(), Name,
964                                       T, Destructor->isInlineSpecified(), false);
965  } else if (CXXConversionDecl *Conversion = dyn_cast<CXXConversionDecl>(D)) {
966    CanQualType ConvTy
967      = SemaRef.Context.getCanonicalType(
968                                      T->getAs<FunctionType>()->getResultType());
969    Name = SemaRef.Context.DeclarationNames.getCXXConversionFunctionName(
970                                                                      ConvTy);
971    Method = CXXConversionDecl::Create(SemaRef.Context, Record,
972                                       Conversion->getLocation(), Name,
973                                       T, TInfo,
974                                       Conversion->isInlineSpecified(),
975                                       Conversion->isExplicit());
976  } else {
977    Method = CXXMethodDecl::Create(SemaRef.Context, Record, D->getLocation(),
978                                   D->getDeclName(), T, TInfo,
979                                   D->isStatic(), D->isInlineSpecified());
980  }
981
982  if (TemplateParams) {
983    // Our resulting instantiation is actually a function template, since we
984    // are substituting only the outer template parameters. For example, given
985    //
986    //   template<typename T>
987    //   struct X {
988    //     template<typename U> void f(T, U);
989    //   };
990    //
991    //   X<int> x;
992    //
993    // We are instantiating the member template "f" within X<int>, which means
994    // substituting int for T, but leaving "f" as a member function template.
995    // Build the function template itself.
996    FunctionTemplate = FunctionTemplateDecl::Create(SemaRef.Context, Record,
997                                                    Method->getLocation(),
998                                                    Method->getDeclName(),
999                                                    TemplateParams, Method);
1000    if (D->isOutOfLine())
1001      FunctionTemplate->setLexicalDeclContext(D->getLexicalDeclContext());
1002    Method->setDescribedFunctionTemplate(FunctionTemplate);
1003  } else if (FunctionTemplate) {
1004    // Record this function template specialization.
1005    Method->setFunctionTemplateSpecialization(FunctionTemplate,
1006                                              &TemplateArgs.getInnermost(),
1007                                              InsertPos);
1008  } else {
1009    // Record that this is an instantiation of a member function.
1010    Method->setInstantiationOfMemberFunction(D, TSK_ImplicitInstantiation);
1011  }
1012
1013  // If we are instantiating a member function defined
1014  // out-of-line, the instantiation will have the same lexical
1015  // context (which will be a namespace scope) as the template.
1016  if (D->isOutOfLine())
1017    Method->setLexicalDeclContext(D->getLexicalDeclContext());
1018
1019  // Attach the parameters
1020  for (unsigned P = 0; P < Params.size(); ++P)
1021    Params[P]->setOwningFunction(Method);
1022  Method->setParams(Params.data(), Params.size());
1023
1024  if (InitMethodInstantiation(Method, D))
1025    Method->setInvalidDecl();
1026
1027  LookupResult Previous(SemaRef, Name, SourceLocation(),
1028                        Sema::LookupOrdinaryName, Sema::ForRedeclaration);
1029
1030  if (!FunctionTemplate || TemplateParams) {
1031    SemaRef.LookupQualifiedName(Previous, Owner);
1032
1033    // In C++, the previous declaration we find might be a tag type
1034    // (class or enum). In this case, the new declaration will hide the
1035    // tag type. Note that this does does not apply if we're declaring a
1036    // typedef (C++ [dcl.typedef]p4).
1037    if (Previous.isSingleTagDecl())
1038      Previous.clear();
1039  }
1040
1041  bool Redeclaration = false;
1042  bool OverloadableAttrRequired = false;
1043  SemaRef.CheckFunctionDeclaration(0, Method, Previous, false, Redeclaration,
1044                                   /*FIXME:*/OverloadableAttrRequired);
1045
1046  if (D->isPure())
1047    SemaRef.CheckPureMethod(Method, SourceRange());
1048
1049  Method->setAccess(D->getAccess());
1050
1051  if (!FunctionTemplate && (!Method->isInvalidDecl() || Previous.empty()) &&
1052      !Method->getFriendObjectKind())
1053    Owner->addDecl(Method);
1054
1055  return Method;
1056}
1057
1058Decl *TemplateDeclInstantiator::VisitCXXConstructorDecl(CXXConstructorDecl *D) {
1059  return VisitCXXMethodDecl(D);
1060}
1061
1062Decl *TemplateDeclInstantiator::VisitCXXDestructorDecl(CXXDestructorDecl *D) {
1063  return VisitCXXMethodDecl(D);
1064}
1065
1066Decl *TemplateDeclInstantiator::VisitCXXConversionDecl(CXXConversionDecl *D) {
1067  return VisitCXXMethodDecl(D);
1068}
1069
1070ParmVarDecl *TemplateDeclInstantiator::VisitParmVarDecl(ParmVarDecl *D) {
1071  QualType T;
1072  TypeSourceInfo *DI = D->getTypeSourceInfo();
1073  if (DI) {
1074    DI = SemaRef.SubstType(DI, TemplateArgs, D->getLocation(),
1075                           D->getDeclName());
1076    if (DI) T = DI->getType();
1077  } else {
1078    T = SemaRef.SubstType(D->getType(), TemplateArgs, D->getLocation(),
1079                          D->getDeclName());
1080    DI = 0;
1081  }
1082
1083  if (T.isNull())
1084    return 0;
1085
1086  T = SemaRef.adjustParameterType(T);
1087
1088  // Allocate the parameter
1089  ParmVarDecl *Param
1090    = ParmVarDecl::Create(SemaRef.Context,
1091                          SemaRef.Context.getTranslationUnitDecl(),
1092                          D->getLocation(),
1093                          D->getIdentifier(), T, DI, D->getStorageClass(), 0);
1094
1095  // Mark the default argument as being uninstantiated.
1096  if (D->hasUninstantiatedDefaultArg())
1097    Param->setUninstantiatedDefaultArg(D->getUninstantiatedDefaultArg());
1098  else if (Expr *Arg = D->getDefaultArg())
1099    Param->setUninstantiatedDefaultArg(Arg);
1100
1101  // Note: we don't try to instantiate function parameters until after
1102  // we've instantiated the function's type. Therefore, we don't have
1103  // to check for 'void' parameter types here.
1104  SemaRef.CurrentInstantiationScope->InstantiatedLocal(D, Param);
1105  return Param;
1106}
1107
1108Decl *TemplateDeclInstantiator::VisitTemplateTypeParmDecl(
1109                                                    TemplateTypeParmDecl *D) {
1110  // TODO: don't always clone when decls are refcounted.
1111  const Type* T = D->getTypeForDecl();
1112  assert(T->isTemplateTypeParmType());
1113  const TemplateTypeParmType *TTPT = T->getAs<TemplateTypeParmType>();
1114
1115  TemplateTypeParmDecl *Inst =
1116    TemplateTypeParmDecl::Create(SemaRef.Context, Owner, D->getLocation(),
1117                                 TTPT->getDepth() - 1, TTPT->getIndex(),
1118                                 TTPT->getName(),
1119                                 D->wasDeclaredWithTypename(),
1120                                 D->isParameterPack());
1121
1122  if (D->hasDefaultArgument())
1123    Inst->setDefaultArgument(D->getDefaultArgumentInfo(), false);
1124
1125  // Introduce this template parameter's instantiation into the instantiation
1126  // scope.
1127  SemaRef.CurrentInstantiationScope->InstantiatedLocal(D, Inst);
1128
1129  return Inst;
1130}
1131
1132Decl *TemplateDeclInstantiator::VisitNonTypeTemplateParmDecl(
1133                                                 NonTypeTemplateParmDecl *D) {
1134  // Substitute into the type of the non-type template parameter.
1135  QualType T;
1136  TypeSourceInfo *DI = D->getTypeSourceInfo();
1137  if (DI) {
1138    DI = SemaRef.SubstType(DI, TemplateArgs, D->getLocation(),
1139                           D->getDeclName());
1140    if (DI) T = DI->getType();
1141  } else {
1142    T = SemaRef.SubstType(D->getType(), TemplateArgs, D->getLocation(),
1143                          D->getDeclName());
1144    DI = 0;
1145  }
1146  if (T.isNull())
1147    return 0;
1148
1149  // Check that this type is acceptable for a non-type template parameter.
1150  bool Invalid = false;
1151  T = SemaRef.CheckNonTypeTemplateParameterType(T, D->getLocation());
1152  if (T.isNull()) {
1153    T = SemaRef.Context.IntTy;
1154    Invalid = true;
1155  }
1156
1157  NonTypeTemplateParmDecl *Param
1158    = NonTypeTemplateParmDecl::Create(SemaRef.Context, Owner, D->getLocation(),
1159                                      D->getDepth() - 1, D->getPosition(),
1160                                      D->getIdentifier(), T, DI);
1161  if (Invalid)
1162    Param->setInvalidDecl();
1163
1164  Param->setDefaultArgument(D->getDefaultArgument());
1165
1166  // Introduce this template parameter's instantiation into the instantiation
1167  // scope.
1168  SemaRef.CurrentInstantiationScope->InstantiatedLocal(D, Param);
1169  return Param;
1170}
1171
1172Decl *
1173TemplateDeclInstantiator::VisitTemplateTemplateParmDecl(
1174                                                  TemplateTemplateParmDecl *D) {
1175  // Instantiate the template parameter list of the template template parameter.
1176  TemplateParameterList *TempParams = D->getTemplateParameters();
1177  TemplateParameterList *InstParams;
1178  {
1179    // Perform the actual substitution of template parameters within a new,
1180    // local instantiation scope.
1181    Sema::LocalInstantiationScope Scope(SemaRef);
1182    InstParams = SubstTemplateParams(TempParams);
1183    if (!InstParams)
1184      return NULL;
1185  }
1186
1187  // Build the template template parameter.
1188  TemplateTemplateParmDecl *Param
1189    = TemplateTemplateParmDecl::Create(SemaRef.Context, Owner, D->getLocation(),
1190                                       D->getDepth() - 1, D->getPosition(),
1191                                       D->getIdentifier(), InstParams);
1192  Param->setDefaultArgument(D->getDefaultArgument());
1193
1194  // Introduce this template parameter's instantiation into the instantiation
1195  // scope.
1196  SemaRef.CurrentInstantiationScope->InstantiatedLocal(D, Param);
1197
1198  return Param;
1199}
1200
1201Decl *TemplateDeclInstantiator::VisitUsingDirectiveDecl(UsingDirectiveDecl *D) {
1202  // Using directives are never dependent, so they require no explicit
1203
1204  UsingDirectiveDecl *Inst
1205    = UsingDirectiveDecl::Create(SemaRef.Context, Owner, D->getLocation(),
1206                                 D->getNamespaceKeyLocation(),
1207                                 D->getQualifierRange(), D->getQualifier(),
1208                                 D->getIdentLocation(),
1209                                 D->getNominatedNamespace(),
1210                                 D->getCommonAncestor());
1211  Owner->addDecl(Inst);
1212  return Inst;
1213}
1214
1215Decl *TemplateDeclInstantiator::VisitUsingDecl(UsingDecl *D) {
1216  // The nested name specifier is non-dependent, so no transformation
1217  // is required.
1218
1219  // We only need to do redeclaration lookups if we're in a class
1220  // scope (in fact, it's not really even possible in non-class
1221  // scopes).
1222  bool CheckRedeclaration = Owner->isRecord();
1223
1224  LookupResult Prev(SemaRef, D->getDeclName(), D->getLocation(),
1225                    Sema::LookupUsingDeclName, Sema::ForRedeclaration);
1226
1227  UsingDecl *NewUD = UsingDecl::Create(SemaRef.Context, Owner,
1228                                       D->getLocation(),
1229                                       D->getNestedNameRange(),
1230                                       D->getUsingLocation(),
1231                                       D->getTargetNestedNameDecl(),
1232                                       D->getDeclName(),
1233                                       D->isTypeName());
1234
1235  CXXScopeSpec SS;
1236  SS.setScopeRep(D->getTargetNestedNameDecl());
1237  SS.setRange(D->getNestedNameRange());
1238
1239  if (CheckRedeclaration) {
1240    Prev.setHideTags(false);
1241    SemaRef.LookupQualifiedName(Prev, Owner);
1242
1243    // Check for invalid redeclarations.
1244    if (SemaRef.CheckUsingDeclRedeclaration(D->getUsingLocation(),
1245                                            D->isTypeName(), SS,
1246                                            D->getLocation(), Prev))
1247      NewUD->setInvalidDecl();
1248
1249  }
1250
1251  if (!NewUD->isInvalidDecl() &&
1252      SemaRef.CheckUsingDeclQualifier(D->getUsingLocation(), SS,
1253                                      D->getLocation()))
1254    NewUD->setInvalidDecl();
1255
1256  SemaRef.Context.setInstantiatedFromUsingDecl(NewUD, D);
1257  NewUD->setAccess(D->getAccess());
1258  Owner->addDecl(NewUD);
1259
1260  // Don't process the shadow decls for an invalid decl.
1261  if (NewUD->isInvalidDecl())
1262    return NewUD;
1263
1264  bool isFunctionScope = Owner->isFunctionOrMethod();
1265
1266  // Process the shadow decls.
1267  for (UsingDecl::shadow_iterator I = D->shadow_begin(), E = D->shadow_end();
1268         I != E; ++I) {
1269    UsingShadowDecl *Shadow = *I;
1270    NamedDecl *InstTarget =
1271      cast<NamedDecl>(SemaRef.FindInstantiatedDecl(Shadow->getLocation(),
1272                                                   Shadow->getTargetDecl(),
1273                                                   TemplateArgs));
1274
1275    if (CheckRedeclaration &&
1276        SemaRef.CheckUsingShadowDecl(NewUD, InstTarget, Prev))
1277      continue;
1278
1279    UsingShadowDecl *InstShadow
1280      = SemaRef.BuildUsingShadowDecl(/*Scope*/ 0, NewUD, InstTarget);
1281    SemaRef.Context.setInstantiatedFromUsingShadowDecl(InstShadow, Shadow);
1282
1283    if (isFunctionScope)
1284      SemaRef.CurrentInstantiationScope->InstantiatedLocal(Shadow, InstShadow);
1285  }
1286
1287  return NewUD;
1288}
1289
1290Decl *TemplateDeclInstantiator::VisitUsingShadowDecl(UsingShadowDecl *D) {
1291  // Ignore these;  we handle them in bulk when processing the UsingDecl.
1292  return 0;
1293}
1294
1295Decl * TemplateDeclInstantiator
1296    ::VisitUnresolvedUsingTypenameDecl(UnresolvedUsingTypenameDecl *D) {
1297  NestedNameSpecifier *NNS =
1298    SemaRef.SubstNestedNameSpecifier(D->getTargetNestedNameSpecifier(),
1299                                     D->getTargetNestedNameRange(),
1300                                     TemplateArgs);
1301  if (!NNS)
1302    return 0;
1303
1304  CXXScopeSpec SS;
1305  SS.setRange(D->getTargetNestedNameRange());
1306  SS.setScopeRep(NNS);
1307
1308  NamedDecl *UD =
1309    SemaRef.BuildUsingDeclaration(/*Scope*/ 0, D->getAccess(),
1310                                  D->getUsingLoc(), SS, D->getLocation(),
1311                                  D->getDeclName(), 0,
1312                                  /*instantiation*/ true,
1313                                  /*typename*/ true, D->getTypenameLoc());
1314  if (UD)
1315    SemaRef.Context.setInstantiatedFromUsingDecl(cast<UsingDecl>(UD), D);
1316
1317  return UD;
1318}
1319
1320Decl * TemplateDeclInstantiator
1321    ::VisitUnresolvedUsingValueDecl(UnresolvedUsingValueDecl *D) {
1322  NestedNameSpecifier *NNS =
1323    SemaRef.SubstNestedNameSpecifier(D->getTargetNestedNameSpecifier(),
1324                                     D->getTargetNestedNameRange(),
1325                                     TemplateArgs);
1326  if (!NNS)
1327    return 0;
1328
1329  CXXScopeSpec SS;
1330  SS.setRange(D->getTargetNestedNameRange());
1331  SS.setScopeRep(NNS);
1332
1333  NamedDecl *UD =
1334    SemaRef.BuildUsingDeclaration(/*Scope*/ 0, D->getAccess(),
1335                                  D->getUsingLoc(), SS, D->getLocation(),
1336                                  D->getDeclName(), 0,
1337                                  /*instantiation*/ true,
1338                                  /*typename*/ false, SourceLocation());
1339  if (UD)
1340    SemaRef.Context.setInstantiatedFromUsingDecl(cast<UsingDecl>(UD), D);
1341
1342  return UD;
1343}
1344
1345Decl *Sema::SubstDecl(Decl *D, DeclContext *Owner,
1346                      const MultiLevelTemplateArgumentList &TemplateArgs) {
1347  TemplateDeclInstantiator Instantiator(*this, Owner, TemplateArgs);
1348  if (D->isInvalidDecl())
1349    return 0;
1350
1351  return Instantiator.Visit(D);
1352}
1353
1354/// \brief Instantiates a nested template parameter list in the current
1355/// instantiation context.
1356///
1357/// \param L The parameter list to instantiate
1358///
1359/// \returns NULL if there was an error
1360TemplateParameterList *
1361TemplateDeclInstantiator::SubstTemplateParams(TemplateParameterList *L) {
1362  // Get errors for all the parameters before bailing out.
1363  bool Invalid = false;
1364
1365  unsigned N = L->size();
1366  typedef llvm::SmallVector<NamedDecl *, 8> ParamVector;
1367  ParamVector Params;
1368  Params.reserve(N);
1369  for (TemplateParameterList::iterator PI = L->begin(), PE = L->end();
1370       PI != PE; ++PI) {
1371    NamedDecl *D = cast_or_null<NamedDecl>(Visit(*PI));
1372    Params.push_back(D);
1373    Invalid = Invalid || !D || D->isInvalidDecl();
1374  }
1375
1376  // Clean up if we had an error.
1377  if (Invalid) {
1378    for (ParamVector::iterator PI = Params.begin(), PE = Params.end();
1379         PI != PE; ++PI)
1380      if (*PI)
1381        (*PI)->Destroy(SemaRef.Context);
1382    return NULL;
1383  }
1384
1385  TemplateParameterList *InstL
1386    = TemplateParameterList::Create(SemaRef.Context, L->getTemplateLoc(),
1387                                    L->getLAngleLoc(), &Params.front(), N,
1388                                    L->getRAngleLoc());
1389  return InstL;
1390}
1391
1392/// \brief Instantiate the declaration of a class template partial
1393/// specialization.
1394///
1395/// \param ClassTemplate the (instantiated) class template that is partially
1396// specialized by the instantiation of \p PartialSpec.
1397///
1398/// \param PartialSpec the (uninstantiated) class template partial
1399/// specialization that we are instantiating.
1400///
1401/// \returns true if there was an error, false otherwise.
1402bool
1403TemplateDeclInstantiator::InstantiateClassTemplatePartialSpecialization(
1404                                            ClassTemplateDecl *ClassTemplate,
1405                          ClassTemplatePartialSpecializationDecl *PartialSpec) {
1406  // Create a local instantiation scope for this class template partial
1407  // specialization, which will contain the instantiations of the template
1408  // parameters.
1409  Sema::LocalInstantiationScope Scope(SemaRef);
1410
1411  // Substitute into the template parameters of the class template partial
1412  // specialization.
1413  TemplateParameterList *TempParams = PartialSpec->getTemplateParameters();
1414  TemplateParameterList *InstParams = SubstTemplateParams(TempParams);
1415  if (!InstParams)
1416    return true;
1417
1418  // Substitute into the template arguments of the class template partial
1419  // specialization.
1420  const TemplateArgumentLoc *PartialSpecTemplateArgs
1421    = PartialSpec->getTemplateArgsAsWritten();
1422  unsigned N = PartialSpec->getNumTemplateArgsAsWritten();
1423
1424  TemplateArgumentListInfo InstTemplateArgs; // no angle locations
1425  for (unsigned I = 0; I != N; ++I) {
1426    TemplateArgumentLoc Loc;
1427    if (SemaRef.Subst(PartialSpecTemplateArgs[I], Loc, TemplateArgs))
1428      return true;
1429    InstTemplateArgs.addArgument(Loc);
1430  }
1431
1432
1433  // Check that the template argument list is well-formed for this
1434  // class template.
1435  TemplateArgumentListBuilder Converted(ClassTemplate->getTemplateParameters(),
1436                                        InstTemplateArgs.size());
1437  if (SemaRef.CheckTemplateArgumentList(ClassTemplate,
1438                                        PartialSpec->getLocation(),
1439                                        InstTemplateArgs,
1440                                        false,
1441                                        Converted))
1442    return true;
1443
1444  // Figure out where to insert this class template partial specialization
1445  // in the member template's set of class template partial specializations.
1446  llvm::FoldingSetNodeID ID;
1447  ClassTemplatePartialSpecializationDecl::Profile(ID,
1448                                                  Converted.getFlatArguments(),
1449                                                  Converted.flatSize(),
1450                                                  SemaRef.Context);
1451  void *InsertPos = 0;
1452  ClassTemplateSpecializationDecl *PrevDecl
1453    = ClassTemplate->getPartialSpecializations().FindNodeOrInsertPos(ID,
1454                                                                     InsertPos);
1455
1456  // Build the canonical type that describes the converted template
1457  // arguments of the class template partial specialization.
1458  QualType CanonType
1459    = SemaRef.Context.getTemplateSpecializationType(TemplateName(ClassTemplate),
1460                                                  Converted.getFlatArguments(),
1461                                                    Converted.flatSize());
1462
1463  // Build the fully-sugared type for this class template
1464  // specialization as the user wrote in the specialization
1465  // itself. This means that we'll pretty-print the type retrieved
1466  // from the specialization's declaration the way that the user
1467  // actually wrote the specialization, rather than formatting the
1468  // name based on the "canonical" representation used to store the
1469  // template arguments in the specialization.
1470  TypeSourceInfo *WrittenTy
1471    = SemaRef.Context.getTemplateSpecializationTypeInfo(
1472                                                    TemplateName(ClassTemplate),
1473                                                    PartialSpec->getLocation(),
1474                                                    InstTemplateArgs,
1475                                                    CanonType);
1476
1477  if (PrevDecl) {
1478    // We've already seen a partial specialization with the same template
1479    // parameters and template arguments. This can happen, for example, when
1480    // substituting the outer template arguments ends up causing two
1481    // class template partial specializations of a member class template
1482    // to have identical forms, e.g.,
1483    //
1484    //   template<typename T, typename U>
1485    //   struct Outer {
1486    //     template<typename X, typename Y> struct Inner;
1487    //     template<typename Y> struct Inner<T, Y>;
1488    //     template<typename Y> struct Inner<U, Y>;
1489    //   };
1490    //
1491    //   Outer<int, int> outer; // error: the partial specializations of Inner
1492    //                          // have the same signature.
1493    SemaRef.Diag(PartialSpec->getLocation(), diag::err_partial_spec_redeclared)
1494      << WrittenTy;
1495    SemaRef.Diag(PrevDecl->getLocation(), diag::note_prev_partial_spec_here)
1496      << SemaRef.Context.getTypeDeclType(PrevDecl);
1497    return true;
1498  }
1499
1500
1501  // Create the class template partial specialization declaration.
1502  ClassTemplatePartialSpecializationDecl *InstPartialSpec
1503    = ClassTemplatePartialSpecializationDecl::Create(SemaRef.Context, Owner,
1504                                                     PartialSpec->getLocation(),
1505                                                     InstParams,
1506                                                     ClassTemplate,
1507                                                     Converted,
1508                                                     InstTemplateArgs,
1509                                                     CanonType,
1510                                                     0);
1511  InstPartialSpec->setInstantiatedFromMember(PartialSpec);
1512  InstPartialSpec->setTypeAsWritten(WrittenTy);
1513
1514  // Add this partial specialization to the set of class template partial
1515  // specializations.
1516  ClassTemplate->getPartialSpecializations().InsertNode(InstPartialSpec,
1517                                                        InsertPos);
1518  return false;
1519}
1520
1521bool
1522Sema::CheckInstantiatedParams(llvm::SmallVectorImpl<ParmVarDecl*> &Params) {
1523  bool Invalid = false;
1524  for (unsigned i = 0, i_end = Params.size(); i != i_end; ++i)
1525    if (ParmVarDecl *PInst = Params[i]) {
1526      if (PInst->isInvalidDecl())
1527        Invalid = true;
1528      else if (PInst->getType()->isVoidType()) {
1529        Diag(PInst->getLocation(), diag::err_param_with_void_type);
1530        PInst->setInvalidDecl();
1531        Invalid = true;
1532      }
1533      else if (RequireNonAbstractType(PInst->getLocation(),
1534                                      PInst->getType(),
1535                                      diag::err_abstract_type_in_decl,
1536                                      Sema::AbstractParamType)) {
1537        PInst->setInvalidDecl();
1538        Invalid = true;
1539      }
1540    }
1541  return Invalid;
1542}
1543
1544TypeSourceInfo*
1545TemplateDeclInstantiator::SubstFunctionType(FunctionDecl *D,
1546                              llvm::SmallVectorImpl<ParmVarDecl *> &Params) {
1547  TypeSourceInfo *OldTInfo = D->getTypeSourceInfo();
1548  assert(OldTInfo && "substituting function without type source info");
1549  assert(Params.empty() && "parameter vector is non-empty at start");
1550  TypeSourceInfo *NewTInfo = SemaRef.SubstType(OldTInfo, TemplateArgs,
1551                                               D->getTypeSpecStartLoc(),
1552                                               D->getDeclName());
1553  if (!NewTInfo)
1554    return 0;
1555
1556  // Get parameters from the new type info.
1557  TypeLoc NewTL = NewTInfo->getTypeLoc();
1558  FunctionProtoTypeLoc *NewProtoLoc = cast<FunctionProtoTypeLoc>(&NewTL);
1559  assert(NewProtoLoc && "Missing prototype?");
1560  for (unsigned i = 0, i_end = NewProtoLoc->getNumArgs(); i != i_end; ++i)
1561    Params.push_back(NewProtoLoc->getArg(i));
1562
1563  return NewTInfo;
1564}
1565
1566/// \brief Initializes the common fields of an instantiation function
1567/// declaration (New) from the corresponding fields of its template (Tmpl).
1568///
1569/// \returns true if there was an error
1570bool
1571TemplateDeclInstantiator::InitFunctionInstantiation(FunctionDecl *New,
1572                                                    FunctionDecl *Tmpl) {
1573  if (Tmpl->isDeleted())
1574    New->setDeleted();
1575
1576  // If we are performing substituting explicitly-specified template arguments
1577  // or deduced template arguments into a function template and we reach this
1578  // point, we are now past the point where SFINAE applies and have committed
1579  // to keeping the new function template specialization. We therefore
1580  // convert the active template instantiation for the function template
1581  // into a template instantiation for this specific function template
1582  // specialization, which is not a SFINAE context, so that we diagnose any
1583  // further errors in the declaration itself.
1584  typedef Sema::ActiveTemplateInstantiation ActiveInstType;
1585  ActiveInstType &ActiveInst = SemaRef.ActiveTemplateInstantiations.back();
1586  if (ActiveInst.Kind == ActiveInstType::ExplicitTemplateArgumentSubstitution ||
1587      ActiveInst.Kind == ActiveInstType::DeducedTemplateArgumentSubstitution) {
1588    if (FunctionTemplateDecl *FunTmpl
1589          = dyn_cast<FunctionTemplateDecl>((Decl *)ActiveInst.Entity)) {
1590      assert(FunTmpl->getTemplatedDecl() == Tmpl &&
1591             "Deduction from the wrong function template?");
1592      (void) FunTmpl;
1593      ActiveInst.Kind = ActiveInstType::TemplateInstantiation;
1594      ActiveInst.Entity = reinterpret_cast<uintptr_t>(New);
1595      --SemaRef.NonInstantiationEntries;
1596    }
1597  }
1598
1599  const FunctionProtoType *Proto = Tmpl->getType()->getAs<FunctionProtoType>();
1600  assert(Proto && "Function template without prototype?");
1601
1602  if (Proto->hasExceptionSpec() || Proto->hasAnyExceptionSpec() ||
1603      Proto->getNoReturnAttr()) {
1604    // The function has an exception specification or a "noreturn"
1605    // attribute. Substitute into each of the exception types.
1606    llvm::SmallVector<QualType, 4> Exceptions;
1607    for (unsigned I = 0, N = Proto->getNumExceptions(); I != N; ++I) {
1608      // FIXME: Poor location information!
1609      QualType T
1610        = SemaRef.SubstType(Proto->getExceptionType(I), TemplateArgs,
1611                            New->getLocation(), New->getDeclName());
1612      if (T.isNull() ||
1613          SemaRef.CheckSpecifiedExceptionType(T, New->getLocation()))
1614        continue;
1615
1616      Exceptions.push_back(T);
1617    }
1618
1619    // Rebuild the function type
1620
1621    const FunctionProtoType *NewProto
1622      = New->getType()->getAs<FunctionProtoType>();
1623    assert(NewProto && "Template instantiation without function prototype?");
1624    New->setType(SemaRef.Context.getFunctionType(NewProto->getResultType(),
1625                                                 NewProto->arg_type_begin(),
1626                                                 NewProto->getNumArgs(),
1627                                                 NewProto->isVariadic(),
1628                                                 NewProto->getTypeQuals(),
1629                                                 Proto->hasExceptionSpec(),
1630                                                 Proto->hasAnyExceptionSpec(),
1631                                                 Exceptions.size(),
1632                                                 Exceptions.data(),
1633                                                 Proto->getNoReturnAttr(),
1634                                                 Proto->getCallConv()));
1635  }
1636
1637  return false;
1638}
1639
1640/// \brief Initializes common fields of an instantiated method
1641/// declaration (New) from the corresponding fields of its template
1642/// (Tmpl).
1643///
1644/// \returns true if there was an error
1645bool
1646TemplateDeclInstantiator::InitMethodInstantiation(CXXMethodDecl *New,
1647                                                  CXXMethodDecl *Tmpl) {
1648  if (InitFunctionInstantiation(New, Tmpl))
1649    return true;
1650
1651  CXXRecordDecl *Record = cast<CXXRecordDecl>(Owner);
1652  New->setAccess(Tmpl->getAccess());
1653  if (Tmpl->isVirtualAsWritten())
1654    Record->setMethodAsVirtual(New);
1655
1656  // FIXME: attributes
1657  // FIXME: New needs a pointer to Tmpl
1658  return false;
1659}
1660
1661/// \brief Instantiate the definition of the given function from its
1662/// template.
1663///
1664/// \param PointOfInstantiation the point at which the instantiation was
1665/// required. Note that this is not precisely a "point of instantiation"
1666/// for the function, but it's close.
1667///
1668/// \param Function the already-instantiated declaration of a
1669/// function template specialization or member function of a class template
1670/// specialization.
1671///
1672/// \param Recursive if true, recursively instantiates any functions that
1673/// are required by this instantiation.
1674///
1675/// \param DefinitionRequired if true, then we are performing an explicit
1676/// instantiation where the body of the function is required. Complain if
1677/// there is no such body.
1678void Sema::InstantiateFunctionDefinition(SourceLocation PointOfInstantiation,
1679                                         FunctionDecl *Function,
1680                                         bool Recursive,
1681                                         bool DefinitionRequired) {
1682  if (Function->isInvalidDecl())
1683    return;
1684
1685  assert(!Function->getBody() && "Already instantiated!");
1686
1687  // Never instantiate an explicit specialization.
1688  if (Function->getTemplateSpecializationKind() == TSK_ExplicitSpecialization)
1689    return;
1690
1691  // Find the function body that we'll be substituting.
1692  const FunctionDecl *PatternDecl = Function->getTemplateInstantiationPattern();
1693  Stmt *Pattern = 0;
1694  if (PatternDecl)
1695    Pattern = PatternDecl->getBody(PatternDecl);
1696
1697  if (!Pattern) {
1698    if (DefinitionRequired) {
1699      if (Function->getPrimaryTemplate())
1700        Diag(PointOfInstantiation,
1701             diag::err_explicit_instantiation_undefined_func_template)
1702          << Function->getPrimaryTemplate();
1703      else
1704        Diag(PointOfInstantiation,
1705             diag::err_explicit_instantiation_undefined_member)
1706          << 1 << Function->getDeclName() << Function->getDeclContext();
1707
1708      if (PatternDecl)
1709        Diag(PatternDecl->getLocation(),
1710             diag::note_explicit_instantiation_here);
1711    }
1712
1713    return;
1714  }
1715
1716  // C++0x [temp.explicit]p9:
1717  //   Except for inline functions, other explicit instantiation declarations
1718  //   have the effect of suppressing the implicit instantiation of the entity
1719  //   to which they refer.
1720  if (Function->getTemplateSpecializationKind()
1721        == TSK_ExplicitInstantiationDeclaration &&
1722      !PatternDecl->isInlined())
1723    return;
1724
1725  InstantiatingTemplate Inst(*this, PointOfInstantiation, Function);
1726  if (Inst)
1727    return;
1728
1729  // If we're performing recursive template instantiation, create our own
1730  // queue of pending implicit instantiations that we will instantiate later,
1731  // while we're still within our own instantiation context.
1732  std::deque<PendingImplicitInstantiation> SavedPendingImplicitInstantiations;
1733  if (Recursive)
1734    PendingImplicitInstantiations.swap(SavedPendingImplicitInstantiations);
1735
1736  ActOnStartOfFunctionDef(0, DeclPtrTy::make(Function));
1737
1738  // Introduce a new scope where local variable instantiations will be
1739  // recorded, unless we're actually a member function within a local
1740  // class, in which case we need to merge our results with the parent
1741  // scope (of the enclosing function).
1742  bool MergeWithParentScope = false;
1743  if (CXXRecordDecl *Rec = dyn_cast<CXXRecordDecl>(Function->getDeclContext()))
1744    MergeWithParentScope = Rec->isLocalClass();
1745
1746  LocalInstantiationScope Scope(*this, MergeWithParentScope);
1747
1748  // Introduce the instantiated function parameters into the local
1749  // instantiation scope.
1750  for (unsigned I = 0, N = PatternDecl->getNumParams(); I != N; ++I)
1751    Scope.InstantiatedLocal(PatternDecl->getParamDecl(I),
1752                            Function->getParamDecl(I));
1753
1754  // Enter the scope of this instantiation. We don't use
1755  // PushDeclContext because we don't have a scope.
1756  DeclContext *PreviousContext = CurContext;
1757  CurContext = Function;
1758
1759  MultiLevelTemplateArgumentList TemplateArgs =
1760    getTemplateInstantiationArgs(Function);
1761
1762  // If this is a constructor, instantiate the member initializers.
1763  if (const CXXConstructorDecl *Ctor =
1764        dyn_cast<CXXConstructorDecl>(PatternDecl)) {
1765    InstantiateMemInitializers(cast<CXXConstructorDecl>(Function), Ctor,
1766                               TemplateArgs);
1767  }
1768
1769  // Instantiate the function body.
1770  OwningStmtResult Body = SubstStmt(Pattern, TemplateArgs);
1771
1772  if (Body.isInvalid())
1773    Function->setInvalidDecl();
1774
1775  ActOnFinishFunctionBody(DeclPtrTy::make(Function), move(Body),
1776                          /*IsInstantiation=*/true);
1777
1778  CurContext = PreviousContext;
1779
1780  DeclGroupRef DG(Function);
1781  Consumer.HandleTopLevelDecl(DG);
1782
1783  // This class may have local implicit instantiations that need to be
1784  // instantiation within this scope.
1785  PerformPendingImplicitInstantiations(/*LocalOnly=*/true);
1786  Scope.Exit();
1787
1788  if (Recursive) {
1789    // Instantiate any pending implicit instantiations found during the
1790    // instantiation of this template.
1791    PerformPendingImplicitInstantiations();
1792
1793    // Restore the set of pending implicit instantiations.
1794    PendingImplicitInstantiations.swap(SavedPendingImplicitInstantiations);
1795  }
1796}
1797
1798/// \brief Instantiate the definition of the given variable from its
1799/// template.
1800///
1801/// \param PointOfInstantiation the point at which the instantiation was
1802/// required. Note that this is not precisely a "point of instantiation"
1803/// for the function, but it's close.
1804///
1805/// \param Var the already-instantiated declaration of a static member
1806/// variable of a class template specialization.
1807///
1808/// \param Recursive if true, recursively instantiates any functions that
1809/// are required by this instantiation.
1810///
1811/// \param DefinitionRequired if true, then we are performing an explicit
1812/// instantiation where an out-of-line definition of the member variable
1813/// is required. Complain if there is no such definition.
1814void Sema::InstantiateStaticDataMemberDefinition(
1815                                          SourceLocation PointOfInstantiation,
1816                                                 VarDecl *Var,
1817                                                 bool Recursive,
1818                                                 bool DefinitionRequired) {
1819  if (Var->isInvalidDecl())
1820    return;
1821
1822  // Find the out-of-line definition of this static data member.
1823  VarDecl *Def = Var->getInstantiatedFromStaticDataMember();
1824  assert(Def && "This data member was not instantiated from a template?");
1825  assert(Def->isStaticDataMember() && "Not a static data member?");
1826  Def = Def->getOutOfLineDefinition();
1827
1828  if (!Def) {
1829    // We did not find an out-of-line definition of this static data member,
1830    // so we won't perform any instantiation. Rather, we rely on the user to
1831    // instantiate this definition (or provide a specialization for it) in
1832    // another translation unit.
1833    if (DefinitionRequired) {
1834      Def = Var->getInstantiatedFromStaticDataMember();
1835      Diag(PointOfInstantiation,
1836           diag::err_explicit_instantiation_undefined_member)
1837        << 2 << Var->getDeclName() << Var->getDeclContext();
1838      Diag(Def->getLocation(), diag::note_explicit_instantiation_here);
1839    }
1840
1841    return;
1842  }
1843
1844  // Never instantiate an explicit specialization.
1845  if (Var->getTemplateSpecializationKind() == TSK_ExplicitSpecialization)
1846    return;
1847
1848  // C++0x [temp.explicit]p9:
1849  //   Except for inline functions, other explicit instantiation declarations
1850  //   have the effect of suppressing the implicit instantiation of the entity
1851  //   to which they refer.
1852  if (Var->getTemplateSpecializationKind()
1853        == TSK_ExplicitInstantiationDeclaration)
1854    return;
1855
1856  InstantiatingTemplate Inst(*this, PointOfInstantiation, Var);
1857  if (Inst)
1858    return;
1859
1860  // If we're performing recursive template instantiation, create our own
1861  // queue of pending implicit instantiations that we will instantiate later,
1862  // while we're still within our own instantiation context.
1863  std::deque<PendingImplicitInstantiation> SavedPendingImplicitInstantiations;
1864  if (Recursive)
1865    PendingImplicitInstantiations.swap(SavedPendingImplicitInstantiations);
1866
1867  // Enter the scope of this instantiation. We don't use
1868  // PushDeclContext because we don't have a scope.
1869  DeclContext *PreviousContext = CurContext;
1870  CurContext = Var->getDeclContext();
1871
1872  VarDecl *OldVar = Var;
1873  Var = cast_or_null<VarDecl>(SubstDecl(Def, Var->getDeclContext(),
1874                                          getTemplateInstantiationArgs(Var)));
1875  CurContext = PreviousContext;
1876
1877  if (Var) {
1878    MemberSpecializationInfo *MSInfo = OldVar->getMemberSpecializationInfo();
1879    assert(MSInfo && "Missing member specialization information?");
1880    Var->setTemplateSpecializationKind(MSInfo->getTemplateSpecializationKind(),
1881                                       MSInfo->getPointOfInstantiation());
1882    DeclGroupRef DG(Var);
1883    Consumer.HandleTopLevelDecl(DG);
1884  }
1885
1886  if (Recursive) {
1887    // Instantiate any pending implicit instantiations found during the
1888    // instantiation of this template.
1889    PerformPendingImplicitInstantiations();
1890
1891    // Restore the set of pending implicit instantiations.
1892    PendingImplicitInstantiations.swap(SavedPendingImplicitInstantiations);
1893  }
1894}
1895
1896void
1897Sema::InstantiateMemInitializers(CXXConstructorDecl *New,
1898                                 const CXXConstructorDecl *Tmpl,
1899                           const MultiLevelTemplateArgumentList &TemplateArgs) {
1900
1901  llvm::SmallVector<MemInitTy*, 4> NewInits;
1902  bool AnyErrors = false;
1903
1904  // Instantiate all the initializers.
1905  for (CXXConstructorDecl::init_const_iterator Inits = Tmpl->init_begin(),
1906                                            InitsEnd = Tmpl->init_end();
1907       Inits != InitsEnd; ++Inits) {
1908    CXXBaseOrMemberInitializer *Init = *Inits;
1909
1910    SourceLocation LParenLoc, RParenLoc;
1911    ASTOwningVector<&ActionBase::DeleteExpr> NewArgs(*this);
1912    llvm::SmallVector<SourceLocation, 4> CommaLocs;
1913
1914    // Instantiate the initializer.
1915    if (InstantiateInitializer(*this, Init->getInit(), TemplateArgs,
1916                               LParenLoc, CommaLocs, NewArgs, RParenLoc)) {
1917      AnyErrors = true;
1918      continue;
1919    }
1920
1921    MemInitResult NewInit;
1922    if (Init->isBaseInitializer()) {
1923      TypeSourceInfo *BaseTInfo = SubstType(Init->getBaseClassInfo(),
1924                                            TemplateArgs,
1925                                            Init->getSourceLocation(),
1926                                            New->getDeclName());
1927      if (!BaseTInfo) {
1928        AnyErrors = true;
1929        New->setInvalidDecl();
1930        continue;
1931      }
1932
1933      NewInit = BuildBaseInitializer(BaseTInfo->getType(), BaseTInfo,
1934                                     (Expr **)NewArgs.data(),
1935                                     NewArgs.size(),
1936                                     Init->getLParenLoc(),
1937                                     Init->getRParenLoc(),
1938                                     New->getParent());
1939    } else if (Init->isMemberInitializer()) {
1940      FieldDecl *Member;
1941
1942      // Is this an anonymous union?
1943      if (FieldDecl *UnionInit = Init->getAnonUnionMember())
1944        Member = cast<FieldDecl>(FindInstantiatedDecl(Init->getMemberLocation(),
1945                                                      UnionInit, TemplateArgs));
1946      else
1947        Member = cast<FieldDecl>(FindInstantiatedDecl(Init->getMemberLocation(),
1948                                                      Init->getMember(),
1949                                                      TemplateArgs));
1950
1951      NewInit = BuildMemberInitializer(Member, (Expr **)NewArgs.data(),
1952                                       NewArgs.size(),
1953                                       Init->getSourceLocation(),
1954                                       Init->getLParenLoc(),
1955                                       Init->getRParenLoc());
1956    }
1957
1958    if (NewInit.isInvalid()) {
1959      AnyErrors = true;
1960      New->setInvalidDecl();
1961    } else {
1962      // FIXME: It would be nice if ASTOwningVector had a release function.
1963      NewArgs.take();
1964
1965      NewInits.push_back((MemInitTy *)NewInit.get());
1966    }
1967  }
1968
1969  // Assign all the initializers to the new constructor.
1970  ActOnMemInitializers(DeclPtrTy::make(New),
1971                       /*FIXME: ColonLoc */
1972                       SourceLocation(),
1973                       NewInits.data(), NewInits.size(),
1974                       AnyErrors);
1975}
1976
1977// TODO: this could be templated if the various decl types used the
1978// same method name.
1979static bool isInstantiationOf(ClassTemplateDecl *Pattern,
1980                              ClassTemplateDecl *Instance) {
1981  Pattern = Pattern->getCanonicalDecl();
1982
1983  do {
1984    Instance = Instance->getCanonicalDecl();
1985    if (Pattern == Instance) return true;
1986    Instance = Instance->getInstantiatedFromMemberTemplate();
1987  } while (Instance);
1988
1989  return false;
1990}
1991
1992static bool isInstantiationOf(FunctionTemplateDecl *Pattern,
1993                              FunctionTemplateDecl *Instance) {
1994  Pattern = Pattern->getCanonicalDecl();
1995
1996  do {
1997    Instance = Instance->getCanonicalDecl();
1998    if (Pattern == Instance) return true;
1999    Instance = Instance->getInstantiatedFromMemberTemplate();
2000  } while (Instance);
2001
2002  return false;
2003}
2004
2005static bool
2006isInstantiationOf(ClassTemplatePartialSpecializationDecl *Pattern,
2007                  ClassTemplatePartialSpecializationDecl *Instance) {
2008  Pattern
2009    = cast<ClassTemplatePartialSpecializationDecl>(Pattern->getCanonicalDecl());
2010  do {
2011    Instance = cast<ClassTemplatePartialSpecializationDecl>(
2012                                                Instance->getCanonicalDecl());
2013    if (Pattern == Instance)
2014      return true;
2015    Instance = Instance->getInstantiatedFromMember();
2016  } while (Instance);
2017
2018  return false;
2019}
2020
2021static bool isInstantiationOf(CXXRecordDecl *Pattern,
2022                              CXXRecordDecl *Instance) {
2023  Pattern = Pattern->getCanonicalDecl();
2024
2025  do {
2026    Instance = Instance->getCanonicalDecl();
2027    if (Pattern == Instance) return true;
2028    Instance = Instance->getInstantiatedFromMemberClass();
2029  } while (Instance);
2030
2031  return false;
2032}
2033
2034static bool isInstantiationOf(FunctionDecl *Pattern,
2035                              FunctionDecl *Instance) {
2036  Pattern = Pattern->getCanonicalDecl();
2037
2038  do {
2039    Instance = Instance->getCanonicalDecl();
2040    if (Pattern == Instance) return true;
2041    Instance = Instance->getInstantiatedFromMemberFunction();
2042  } while (Instance);
2043
2044  return false;
2045}
2046
2047static bool isInstantiationOf(EnumDecl *Pattern,
2048                              EnumDecl *Instance) {
2049  Pattern = Pattern->getCanonicalDecl();
2050
2051  do {
2052    Instance = Instance->getCanonicalDecl();
2053    if (Pattern == Instance) return true;
2054    Instance = Instance->getInstantiatedFromMemberEnum();
2055  } while (Instance);
2056
2057  return false;
2058}
2059
2060static bool isInstantiationOf(UsingShadowDecl *Pattern,
2061                              UsingShadowDecl *Instance,
2062                              ASTContext &C) {
2063  return C.getInstantiatedFromUsingShadowDecl(Instance) == Pattern;
2064}
2065
2066static bool isInstantiationOf(UsingDecl *Pattern,
2067                              UsingDecl *Instance,
2068                              ASTContext &C) {
2069  return C.getInstantiatedFromUsingDecl(Instance) == Pattern;
2070}
2071
2072static bool isInstantiationOf(UnresolvedUsingValueDecl *Pattern,
2073                              UsingDecl *Instance,
2074                              ASTContext &C) {
2075  return C.getInstantiatedFromUsingDecl(Instance) == Pattern;
2076}
2077
2078static bool isInstantiationOf(UnresolvedUsingTypenameDecl *Pattern,
2079                              UsingDecl *Instance,
2080                              ASTContext &C) {
2081  return C.getInstantiatedFromUsingDecl(Instance) == Pattern;
2082}
2083
2084static bool isInstantiationOfStaticDataMember(VarDecl *Pattern,
2085                                              VarDecl *Instance) {
2086  assert(Instance->isStaticDataMember());
2087
2088  Pattern = Pattern->getCanonicalDecl();
2089
2090  do {
2091    Instance = Instance->getCanonicalDecl();
2092    if (Pattern == Instance) return true;
2093    Instance = Instance->getInstantiatedFromStaticDataMember();
2094  } while (Instance);
2095
2096  return false;
2097}
2098
2099// Other is the prospective instantiation
2100// D is the prospective pattern
2101static bool isInstantiationOf(ASTContext &Ctx, NamedDecl *D, Decl *Other) {
2102  if (D->getKind() != Other->getKind()) {
2103    if (UnresolvedUsingTypenameDecl *UUD
2104          = dyn_cast<UnresolvedUsingTypenameDecl>(D)) {
2105      if (UsingDecl *UD = dyn_cast<UsingDecl>(Other)) {
2106        return isInstantiationOf(UUD, UD, Ctx);
2107      }
2108    }
2109
2110    if (UnresolvedUsingValueDecl *UUD
2111          = dyn_cast<UnresolvedUsingValueDecl>(D)) {
2112      if (UsingDecl *UD = dyn_cast<UsingDecl>(Other)) {
2113        return isInstantiationOf(UUD, UD, Ctx);
2114      }
2115    }
2116
2117    return false;
2118  }
2119
2120  if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(Other))
2121    return isInstantiationOf(cast<CXXRecordDecl>(D), Record);
2122
2123  if (FunctionDecl *Function = dyn_cast<FunctionDecl>(Other))
2124    return isInstantiationOf(cast<FunctionDecl>(D), Function);
2125
2126  if (EnumDecl *Enum = dyn_cast<EnumDecl>(Other))
2127    return isInstantiationOf(cast<EnumDecl>(D), Enum);
2128
2129  if (VarDecl *Var = dyn_cast<VarDecl>(Other))
2130    if (Var->isStaticDataMember())
2131      return isInstantiationOfStaticDataMember(cast<VarDecl>(D), Var);
2132
2133  if (ClassTemplateDecl *Temp = dyn_cast<ClassTemplateDecl>(Other))
2134    return isInstantiationOf(cast<ClassTemplateDecl>(D), Temp);
2135
2136  if (FunctionTemplateDecl *Temp = dyn_cast<FunctionTemplateDecl>(Other))
2137    return isInstantiationOf(cast<FunctionTemplateDecl>(D), Temp);
2138
2139  if (ClassTemplatePartialSpecializationDecl *PartialSpec
2140        = dyn_cast<ClassTemplatePartialSpecializationDecl>(Other))
2141    return isInstantiationOf(cast<ClassTemplatePartialSpecializationDecl>(D),
2142                             PartialSpec);
2143
2144  if (FieldDecl *Field = dyn_cast<FieldDecl>(Other)) {
2145    if (!Field->getDeclName()) {
2146      // This is an unnamed field.
2147      return Ctx.getInstantiatedFromUnnamedFieldDecl(Field) ==
2148        cast<FieldDecl>(D);
2149    }
2150  }
2151
2152  if (UsingDecl *Using = dyn_cast<UsingDecl>(Other))
2153    return isInstantiationOf(cast<UsingDecl>(D), Using, Ctx);
2154
2155  if (UsingShadowDecl *Shadow = dyn_cast<UsingShadowDecl>(Other))
2156    return isInstantiationOf(cast<UsingShadowDecl>(D), Shadow, Ctx);
2157
2158  return D->getDeclName() && isa<NamedDecl>(Other) &&
2159    D->getDeclName() == cast<NamedDecl>(Other)->getDeclName();
2160}
2161
2162template<typename ForwardIterator>
2163static NamedDecl *findInstantiationOf(ASTContext &Ctx,
2164                                      NamedDecl *D,
2165                                      ForwardIterator first,
2166                                      ForwardIterator last) {
2167  for (; first != last; ++first)
2168    if (isInstantiationOf(Ctx, D, *first))
2169      return cast<NamedDecl>(*first);
2170
2171  return 0;
2172}
2173
2174/// \brief Finds the instantiation of the given declaration context
2175/// within the current instantiation.
2176///
2177/// \returns NULL if there was an error
2178DeclContext *Sema::FindInstantiatedContext(SourceLocation Loc, DeclContext* DC,
2179                          const MultiLevelTemplateArgumentList &TemplateArgs) {
2180  if (NamedDecl *D = dyn_cast<NamedDecl>(DC)) {
2181    Decl* ID = FindInstantiatedDecl(Loc, D, TemplateArgs);
2182    return cast_or_null<DeclContext>(ID);
2183  } else return DC;
2184}
2185
2186/// \brief Find the instantiation of the given declaration within the
2187/// current instantiation.
2188///
2189/// This routine is intended to be used when \p D is a declaration
2190/// referenced from within a template, that needs to mapped into the
2191/// corresponding declaration within an instantiation. For example,
2192/// given:
2193///
2194/// \code
2195/// template<typename T>
2196/// struct X {
2197///   enum Kind {
2198///     KnownValue = sizeof(T)
2199///   };
2200///
2201///   bool getKind() const { return KnownValue; }
2202/// };
2203///
2204/// template struct X<int>;
2205/// \endcode
2206///
2207/// In the instantiation of X<int>::getKind(), we need to map the
2208/// EnumConstantDecl for KnownValue (which refers to
2209/// X<T>::<Kind>::KnownValue) to its instantiation
2210/// (X<int>::<Kind>::KnownValue). InstantiateCurrentDeclRef() performs
2211/// this mapping from within the instantiation of X<int>.
2212NamedDecl *Sema::FindInstantiatedDecl(SourceLocation Loc, NamedDecl *D,
2213                          const MultiLevelTemplateArgumentList &TemplateArgs) {
2214  DeclContext *ParentDC = D->getDeclContext();
2215  if (isa<ParmVarDecl>(D) || isa<NonTypeTemplateParmDecl>(D) ||
2216      isa<TemplateTypeParmDecl>(D) || isa<TemplateTemplateParmDecl>(D) ||
2217      ParentDC->isFunctionOrMethod()) {
2218    // D is a local of some kind. Look into the map of local
2219    // declarations to their instantiations.
2220    return cast<NamedDecl>(CurrentInstantiationScope->getInstantiationOf(D));
2221  }
2222
2223  if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(D)) {
2224    if (!Record->isDependentContext())
2225      return D;
2226
2227    // If the RecordDecl is actually the injected-class-name or a
2228    // "templated" declaration for a class template, class template
2229    // partial specialization, or a member class of a class template,
2230    // substitute into the injected-class-name of the class template
2231    // or partial specialization to find the new DeclContext.
2232    QualType T;
2233    ClassTemplateDecl *ClassTemplate = Record->getDescribedClassTemplate();
2234
2235    if (ClassTemplate) {
2236      T = ClassTemplate->getInjectedClassNameSpecialization(Context);
2237    } else if (ClassTemplatePartialSpecializationDecl *PartialSpec
2238                 = dyn_cast<ClassTemplatePartialSpecializationDecl>(Record)) {
2239      ClassTemplate = PartialSpec->getSpecializedTemplate();
2240
2241      // If we call SubstType with an InjectedClassNameType here we
2242      // can end up in an infinite loop.
2243      T = Context.getTypeDeclType(Record);
2244      assert(isa<InjectedClassNameType>(T) &&
2245             "type of partial specialization is not an InjectedClassNameType");
2246      T = cast<InjectedClassNameType>(T)->getUnderlyingType();
2247    }
2248
2249    if (!T.isNull()) {
2250      // Substitute into the injected-class-name to get the type
2251      // corresponding to the instantiation we want, which may also be
2252      // the current instantiation (if we're in a template
2253      // definition). This substitution should never fail, since we
2254      // know we can instantiate the injected-class-name or we
2255      // wouldn't have gotten to the injected-class-name!
2256
2257      // FIXME: Can we use the CurrentInstantiationScope to avoid this
2258      // extra instantiation in the common case?
2259      T = SubstType(T, TemplateArgs, SourceLocation(), DeclarationName());
2260      assert(!T.isNull() && "Instantiation of injected-class-name cannot fail.");
2261
2262      if (!T->isDependentType()) {
2263        assert(T->isRecordType() && "Instantiation must produce a record type");
2264        return T->getAs<RecordType>()->getDecl();
2265      }
2266
2267      // We are performing "partial" template instantiation to create
2268      // the member declarations for the members of a class template
2269      // specialization. Therefore, D is actually referring to something
2270      // in the current instantiation. Look through the current
2271      // context, which contains actual instantiations, to find the
2272      // instantiation of the "current instantiation" that D refers
2273      // to.
2274      bool SawNonDependentContext = false;
2275      for (DeclContext *DC = CurContext; !DC->isFileContext();
2276           DC = DC->getParent()) {
2277        if (ClassTemplateSpecializationDecl *Spec
2278                          = dyn_cast<ClassTemplateSpecializationDecl>(DC))
2279          if (isInstantiationOf(ClassTemplate,
2280                                Spec->getSpecializedTemplate()))
2281            return Spec;
2282
2283        if (!DC->isDependentContext())
2284          SawNonDependentContext = true;
2285      }
2286
2287      // We're performing "instantiation" of a member of the current
2288      // instantiation while we are type-checking the
2289      // definition. Compute the declaration context and return that.
2290      assert(!SawNonDependentContext &&
2291             "No dependent context while instantiating record");
2292      DeclContext *DC = computeDeclContext(T);
2293      assert(DC &&
2294             "Unable to find declaration for the current instantiation");
2295      return cast<CXXRecordDecl>(DC);
2296    }
2297
2298    // Fall through to deal with other dependent record types (e.g.,
2299    // anonymous unions in class templates).
2300  }
2301
2302  if (!ParentDC->isDependentContext())
2303    return D;
2304
2305  ParentDC = FindInstantiatedContext(Loc, ParentDC, TemplateArgs);
2306  if (!ParentDC)
2307    return 0;
2308
2309  if (ParentDC != D->getDeclContext()) {
2310    // We performed some kind of instantiation in the parent context,
2311    // so now we need to look into the instantiated parent context to
2312    // find the instantiation of the declaration D.
2313
2314    // If our context used to be dependent, we may need to instantiate
2315    // it before performing lookup into that context.
2316    if (CXXRecordDecl *Spec = dyn_cast<CXXRecordDecl>(ParentDC)) {
2317      if (!Spec->isDependentContext()) {
2318        QualType T = Context.getTypeDeclType(Spec);
2319        const RecordType *Tag = T->getAs<RecordType>();
2320        assert(Tag && "type of non-dependent record is not a RecordType");
2321        if (!Tag->isBeingDefined() &&
2322            RequireCompleteType(Loc, T, diag::err_incomplete_type))
2323          return 0;
2324      }
2325    }
2326
2327    NamedDecl *Result = 0;
2328    if (D->getDeclName()) {
2329      DeclContext::lookup_result Found = ParentDC->lookup(D->getDeclName());
2330      Result = findInstantiationOf(Context, D, Found.first, Found.second);
2331    } else {
2332      // Since we don't have a name for the entity we're looking for,
2333      // our only option is to walk through all of the declarations to
2334      // find that name. This will occur in a few cases:
2335      //
2336      //   - anonymous struct/union within a template
2337      //   - unnamed class/struct/union/enum within a template
2338      //
2339      // FIXME: Find a better way to find these instantiations!
2340      Result = findInstantiationOf(Context, D,
2341                                   ParentDC->decls_begin(),
2342                                   ParentDC->decls_end());
2343    }
2344
2345    // UsingShadowDecls can instantiate to nothing because of using hiding.
2346    assert((Result || isa<UsingShadowDecl>(D) || D->isInvalidDecl() ||
2347            cast<Decl>(ParentDC)->isInvalidDecl())
2348           && "Unable to find instantiation of declaration!");
2349
2350    D = Result;
2351  }
2352
2353  return D;
2354}
2355
2356/// \brief Performs template instantiation for all implicit template
2357/// instantiations we have seen until this point.
2358void Sema::PerformPendingImplicitInstantiations(bool LocalOnly) {
2359  while (!PendingLocalImplicitInstantiations.empty() ||
2360         (!LocalOnly && !PendingImplicitInstantiations.empty())) {
2361    PendingImplicitInstantiation Inst;
2362
2363    if (PendingLocalImplicitInstantiations.empty()) {
2364      Inst = PendingImplicitInstantiations.front();
2365      PendingImplicitInstantiations.pop_front();
2366    } else {
2367      Inst = PendingLocalImplicitInstantiations.front();
2368      PendingLocalImplicitInstantiations.pop_front();
2369    }
2370
2371    // Instantiate function definitions
2372    if (FunctionDecl *Function = dyn_cast<FunctionDecl>(Inst.first)) {
2373      PrettyStackTraceActionsDecl CrashInfo(DeclPtrTy::make(Function),
2374                                            Function->getLocation(), *this,
2375                                            Context.getSourceManager(),
2376                                           "instantiating function definition");
2377
2378      if (!Function->getBody())
2379        InstantiateFunctionDefinition(/*FIXME:*/Inst.second, Function, true);
2380      continue;
2381    }
2382
2383    // Instantiate static data member definitions.
2384    VarDecl *Var = cast<VarDecl>(Inst.first);
2385    assert(Var->isStaticDataMember() && "Not a static data member?");
2386
2387    // Don't try to instantiate declarations if the most recent redeclaration
2388    // is invalid.
2389    if (Var->getMostRecentDeclaration()->isInvalidDecl())
2390      continue;
2391
2392    // Check if the most recent declaration has changed the specialization kind
2393    // and removed the need for implicit instantiation.
2394    switch (Var->getMostRecentDeclaration()->getTemplateSpecializationKind()) {
2395    case TSK_Undeclared:
2396      assert(false && "Cannot instantitiate an undeclared specialization.");
2397    case TSK_ExplicitInstantiationDeclaration:
2398    case TSK_ExplicitInstantiationDefinition:
2399    case TSK_ExplicitSpecialization:
2400      continue;  // No longer need implicit instantiation.
2401    case TSK_ImplicitInstantiation:
2402      break;
2403    }
2404
2405    PrettyStackTraceActionsDecl CrashInfo(DeclPtrTy::make(Var),
2406                                          Var->getLocation(), *this,
2407                                          Context.getSourceManager(),
2408                                          "instantiating static data member "
2409                                          "definition");
2410
2411    InstantiateStaticDataMemberDefinition(/*FIXME:*/Inst.second, Var, true);
2412  }
2413}
2414