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