SemaTemplateInstantiateDecl.cpp revision a735b206fdb5c15767a45289e1ffb3b568f70f2b 
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 "clang/AST/ASTConsumer.h"
14#include "clang/AST/ASTContext.h"
15#include "clang/AST/DeclTemplate.h"
16#include "clang/AST/DeclVisitor.h"
17#include "clang/AST/Expr.h"
18#include "clang/Basic/PrettyStackTrace.h"
19#include "clang/Lex/Preprocessor.h"
20#include "llvm/Support/Compiler.h"
21
22using namespace clang;
23
24namespace {
25  class VISIBILITY_HIDDEN TemplateDeclInstantiator
26    : public DeclVisitor<TemplateDeclInstantiator, Decl *> {
27    Sema &SemaRef;
28    DeclContext *Owner;
29    const MultiLevelTemplateArgumentList &TemplateArgs;
30
31  public:
32    typedef Sema::OwningExprResult OwningExprResult;
33
34    TemplateDeclInstantiator(Sema &SemaRef, DeclContext *Owner,
35                             const MultiLevelTemplateArgumentList &TemplateArgs)
36      : SemaRef(SemaRef), Owner(Owner), TemplateArgs(TemplateArgs) { }
37
38    // FIXME: Once we get closer to completion, replace these manually-written
39    // declarations with automatically-generated ones from
40    // clang/AST/DeclNodes.def.
41    Decl *VisitTranslationUnitDecl(TranslationUnitDecl *D);
42    Decl *VisitNamespaceDecl(NamespaceDecl *D);
43    Decl *VisitTypedefDecl(TypedefDecl *D);
44    Decl *VisitVarDecl(VarDecl *D);
45    Decl *VisitFieldDecl(FieldDecl *D);
46    Decl *VisitStaticAssertDecl(StaticAssertDecl *D);
47    Decl *VisitEnumDecl(EnumDecl *D);
48    Decl *VisitEnumConstantDecl(EnumConstantDecl *D);
49    Decl *VisitFriendDecl(FriendDecl *D);
50    Decl *VisitFunctionDecl(FunctionDecl *D,
51                            TemplateParameterList *TemplateParams = 0);
52    Decl *VisitCXXRecordDecl(CXXRecordDecl *D);
53    Decl *VisitCXXMethodDecl(CXXMethodDecl *D,
54                             TemplateParameterList *TemplateParams = 0);
55    Decl *VisitCXXConstructorDecl(CXXConstructorDecl *D);
56    Decl *VisitCXXDestructorDecl(CXXDestructorDecl *D);
57    Decl *VisitCXXConversionDecl(CXXConversionDecl *D);
58    ParmVarDecl *VisitParmVarDecl(ParmVarDecl *D);
59    Decl *VisitOriginalParmVarDecl(OriginalParmVarDecl *D);
60    Decl *VisitClassTemplateDecl(ClassTemplateDecl *D);
61    Decl *VisitClassTemplatePartialSpecializationDecl(
62                                    ClassTemplatePartialSpecializationDecl *D);
63    Decl *VisitFunctionTemplateDecl(FunctionTemplateDecl *D);
64    Decl *VisitTemplateTypeParmDecl(TemplateTypeParmDecl *D);
65    Decl *VisitUnresolvedUsingDecl(UnresolvedUsingDecl *D);
66
67    // Base case. FIXME: Remove once we can instantiate everything.
68    Decl *VisitDecl(Decl *) {
69      assert(false && "Template instantiation of unknown declaration kind!");
70      return 0;
71    }
72
73    const LangOptions &getLangOptions() {
74      return SemaRef.getLangOptions();
75    }
76
77    // Helper functions for instantiating methods.
78    QualType SubstFunctionType(FunctionDecl *D,
79                             llvm::SmallVectorImpl<ParmVarDecl *> &Params);
80    bool InitFunctionInstantiation(FunctionDecl *New, FunctionDecl *Tmpl);
81    bool InitMethodInstantiation(CXXMethodDecl *New, CXXMethodDecl *Tmpl);
82
83    TemplateParameterList *
84      SubstTemplateParams(TemplateParameterList *List);
85  };
86}
87
88Decl *
89TemplateDeclInstantiator::VisitTranslationUnitDecl(TranslationUnitDecl *D) {
90  assert(false && "Translation units cannot be instantiated");
91  return D;
92}
93
94Decl *
95TemplateDeclInstantiator::VisitNamespaceDecl(NamespaceDecl *D) {
96  assert(false && "Namespaces cannot be instantiated");
97  return D;
98}
99
100Decl *TemplateDeclInstantiator::VisitTypedefDecl(TypedefDecl *D) {
101  bool Invalid = false;
102  QualType T = D->getUnderlyingType();
103  if (T->isDependentType()) {
104    T = SemaRef.SubstType(T, TemplateArgs,
105                          D->getLocation(), D->getDeclName());
106    if (T.isNull()) {
107      Invalid = true;
108      T = SemaRef.Context.IntTy;
109    }
110  }
111
112  // Create the new typedef
113  TypedefDecl *Typedef
114    = TypedefDecl::Create(SemaRef.Context, Owner, D->getLocation(),
115                          D->getIdentifier(), T);
116  if (Invalid)
117    Typedef->setInvalidDecl();
118
119  Owner->addDecl(Typedef);
120
121  return Typedef;
122}
123
124Decl *TemplateDeclInstantiator::VisitVarDecl(VarDecl *D) {
125  // Do substitution on the type of the declaration
126  QualType T = SemaRef.SubstType(D->getType(), TemplateArgs,
127                                 D->getTypeSpecStartLoc(),
128                                 D->getDeclName());
129  if (T.isNull())
130    return 0;
131
132  // Build the instantiated declaration
133  VarDecl *Var = VarDecl::Create(SemaRef.Context, Owner,
134                                 D->getLocation(), D->getIdentifier(),
135                                 T, D->getDeclaratorInfo(),
136                                 D->getStorageClass());
137  Var->setThreadSpecified(D->isThreadSpecified());
138  Var->setCXXDirectInitializer(D->hasCXXDirectInitializer());
139  Var->setDeclaredInCondition(D->isDeclaredInCondition());
140
141  // If we are instantiating a static data member defined
142  // out-of-line, the instantiation will have the same lexical
143  // context (which will be a namespace scope) as the template.
144  if (D->isOutOfLine())
145    Var->setLexicalDeclContext(D->getLexicalDeclContext());
146
147  // FIXME: In theory, we could have a previous declaration for variables that
148  // are not static data members.
149  bool Redeclaration = false;
150  SemaRef.CheckVariableDeclaration(Var, 0, Redeclaration);
151
152  if (D->isOutOfLine()) {
153    D->getLexicalDeclContext()->addDecl(Var);
154    Owner->makeDeclVisibleInContext(Var);
155  } else {
156    Owner->addDecl(Var);
157  }
158
159  // Link instantiations of static data members back to the template from
160  // which they were instantiated.
161  if (Var->isStaticDataMember())
162    SemaRef.Context.setInstantiatedFromStaticDataMember(Var, D,
163                                                        TSK_ImplicitInstantiation);
164
165  if (D->getInit()) {
166    OwningExprResult Init
167      = SemaRef.SubstExpr(D->getInit(), TemplateArgs);
168    if (Init.isInvalid())
169      Var->setInvalidDecl();
170    else if (ParenListExpr *PLE = dyn_cast<ParenListExpr>((Expr *)Init.get())) {
171      // FIXME: We're faking all of the comma locations, which is suboptimal.
172      // Do we even need these comma locations?
173      llvm::SmallVector<SourceLocation, 4> FakeCommaLocs;
174      if (PLE->getNumExprs() > 0) {
175        FakeCommaLocs.reserve(PLE->getNumExprs() - 1);
176        for (unsigned I = 0, N = PLE->getNumExprs() - 1; I != N; ++I) {
177          Expr *E = PLE->getExpr(I)->Retain();
178          FakeCommaLocs.push_back(
179                                SemaRef.PP.getLocForEndOfToken(E->getLocEnd()));
180        }
181        PLE->getExpr(PLE->getNumExprs() - 1)->Retain();
182      }
183
184      // Add the direct initializer to the declaration.
185      SemaRef.AddCXXDirectInitializerToDecl(Sema::DeclPtrTy::make(Var),
186                                            PLE->getLParenLoc(),
187                                            Sema::MultiExprArg(SemaRef,
188                                                       (void**)PLE->getExprs(),
189                                                           PLE->getNumExprs()),
190                                            FakeCommaLocs.data(),
191                                            PLE->getRParenLoc());
192
193      // When Init is destroyed, it will destroy the instantiated ParenListExpr;
194      // we've explicitly retained all of its subexpressions already.
195    } else
196      SemaRef.AddInitializerToDecl(Sema::DeclPtrTy::make(Var), move(Init),
197                                   D->hasCXXDirectInitializer());
198  } else if (!Var->isStaticDataMember() || Var->isOutOfLine())
199    SemaRef.ActOnUninitializedDecl(Sema::DeclPtrTy::make(Var), false);
200
201  return Var;
202}
203
204Decl *TemplateDeclInstantiator::VisitFieldDecl(FieldDecl *D) {
205  bool Invalid = false;
206  QualType T = D->getType();
207  if (T->isDependentType())  {
208    T = SemaRef.SubstType(T, TemplateArgs,
209                          D->getLocation(), D->getDeclName());
210    if (!T.isNull() && T->isFunctionType()) {
211      // C++ [temp.arg.type]p3:
212      //   If a declaration acquires a function type through a type
213      //   dependent on a template-parameter and this causes a
214      //   declaration that does not use the syntactic form of a
215      //   function declarator to have function type, the program is
216      //   ill-formed.
217      SemaRef.Diag(D->getLocation(), diag::err_field_instantiates_to_function)
218        << T;
219      T = QualType();
220      Invalid = true;
221    }
222  }
223
224  Expr *BitWidth = D->getBitWidth();
225  if (Invalid)
226    BitWidth = 0;
227  else if (BitWidth) {
228    // The bit-width expression is not potentially evaluated.
229    EnterExpressionEvaluationContext Unevaluated(SemaRef, Action::Unevaluated);
230
231    OwningExprResult InstantiatedBitWidth
232      = SemaRef.SubstExpr(BitWidth, TemplateArgs);
233    if (InstantiatedBitWidth.isInvalid()) {
234      Invalid = true;
235      BitWidth = 0;
236    } else
237      BitWidth = InstantiatedBitWidth.takeAs<Expr>();
238  }
239
240  FieldDecl *Field = SemaRef.CheckFieldDecl(D->getDeclName(), T,
241                                            D->getDeclaratorInfo(),
242                                            cast<RecordDecl>(Owner),
243                                            D->getLocation(),
244                                            D->isMutable(),
245                                            BitWidth,
246                                            D->getTypeSpecStartLoc(),
247                                            D->getAccess(),
248                                            0);
249  if (!Field)
250    return 0;
251
252  if (Invalid)
253    Field->setInvalidDecl();
254
255  if (!Field->getDeclName()) {
256    // Keep track of where this decl came from.
257    SemaRef.Context.setInstantiatedFromUnnamedFieldDecl(Field, D);
258  }
259
260  Field->setImplicit(D->isImplicit());
261  Owner->addDecl(Field);
262
263  return Field;
264}
265
266Decl *TemplateDeclInstantiator::VisitFriendDecl(FriendDecl *D) {
267  FriendDecl::FriendUnion FU;
268
269  // Handle friend type expressions by simply substituting template
270  // parameters into the pattern type.
271  if (Type *Ty = D->getFriendType()) {
272    QualType T = SemaRef.SubstType(QualType(Ty,0), TemplateArgs,
273                                   D->getLocation(), DeclarationName());
274    if (T.isNull()) return 0;
275
276    assert(getLangOptions().CPlusPlus0x || T->isRecordType());
277    FU = T.getTypePtr();
278
279  // Handle everything else by appropriate substitution.
280  } else {
281    NamedDecl *ND = D->getFriendDecl();
282    assert(ND && "friend decl must be a decl or a type!");
283
284    // FIXME: We have a problem here, because the nested call to Visit(ND)
285    // will inject the thing that the friend references into the current
286    // owner, which is wrong.
287    Decl *NewND = Visit(ND);
288    if (!NewND) return 0;
289
290    FU = cast<NamedDecl>(NewND);
291  }
292
293  FriendDecl *FD =
294    FriendDecl::Create(SemaRef.Context, Owner, D->getLocation(), FU,
295                       D->getFriendLoc());
296  FD->setAccess(AS_public);
297  Owner->addDecl(FD);
298  return FD;
299}
300
301Decl *TemplateDeclInstantiator::VisitStaticAssertDecl(StaticAssertDecl *D) {
302  Expr *AssertExpr = D->getAssertExpr();
303
304  // The expression in a static assertion is not potentially evaluated.
305  EnterExpressionEvaluationContext Unevaluated(SemaRef, Action::Unevaluated);
306
307  OwningExprResult InstantiatedAssertExpr
308    = SemaRef.SubstExpr(AssertExpr, TemplateArgs);
309  if (InstantiatedAssertExpr.isInvalid())
310    return 0;
311
312  OwningExprResult Message(SemaRef, D->getMessage());
313  D->getMessage()->Retain();
314  Decl *StaticAssert
315    = SemaRef.ActOnStaticAssertDeclaration(D->getLocation(),
316                                           move(InstantiatedAssertExpr),
317                                           move(Message)).getAs<Decl>();
318  return StaticAssert;
319}
320
321Decl *TemplateDeclInstantiator::VisitEnumDecl(EnumDecl *D) {
322  EnumDecl *Enum = EnumDecl::Create(SemaRef.Context, Owner,
323                                    D->getLocation(), D->getIdentifier(),
324                                    D->getTagKeywordLoc(),
325                                    /*PrevDecl=*/0);
326  Enum->setInstantiationOfMemberEnum(D);
327  Enum->setAccess(D->getAccess());
328  Owner->addDecl(Enum);
329  Enum->startDefinition();
330
331  llvm::SmallVector<Sema::DeclPtrTy, 4> Enumerators;
332
333  EnumConstantDecl *LastEnumConst = 0;
334  for (EnumDecl::enumerator_iterator EC = D->enumerator_begin(),
335         ECEnd = D->enumerator_end();
336       EC != ECEnd; ++EC) {
337    // The specified value for the enumerator.
338    OwningExprResult Value = SemaRef.Owned((Expr *)0);
339    if (Expr *UninstValue = EC->getInitExpr()) {
340      // The enumerator's value expression is not potentially evaluated.
341      EnterExpressionEvaluationContext Unevaluated(SemaRef,
342                                                   Action::Unevaluated);
343
344      Value = SemaRef.SubstExpr(UninstValue, TemplateArgs);
345    }
346
347    // Drop the initial value and continue.
348    bool isInvalid = false;
349    if (Value.isInvalid()) {
350      Value = SemaRef.Owned((Expr *)0);
351      isInvalid = true;
352    }
353
354    EnumConstantDecl *EnumConst
355      = SemaRef.CheckEnumConstant(Enum, LastEnumConst,
356                                  EC->getLocation(), EC->getIdentifier(),
357                                  move(Value));
358
359    if (isInvalid) {
360      if (EnumConst)
361        EnumConst->setInvalidDecl();
362      Enum->setInvalidDecl();
363    }
364
365    if (EnumConst) {
366      Enum->addDecl(EnumConst);
367      Enumerators.push_back(Sema::DeclPtrTy::make(EnumConst));
368      LastEnumConst = EnumConst;
369    }
370  }
371
372  // FIXME: Fixup LBraceLoc and RBraceLoc
373  // FIXME: Empty Scope and AttributeList (required to handle attribute packed).
374  SemaRef.ActOnEnumBody(Enum->getLocation(), SourceLocation(), SourceLocation(),
375                        Sema::DeclPtrTy::make(Enum),
376                        &Enumerators[0], Enumerators.size(),
377                        0, 0);
378
379  return Enum;
380}
381
382Decl *TemplateDeclInstantiator::VisitEnumConstantDecl(EnumConstantDecl *D) {
383  assert(false && "EnumConstantDecls can only occur within EnumDecls.");
384  return 0;
385}
386
387Decl *TemplateDeclInstantiator::VisitClassTemplateDecl(ClassTemplateDecl *D) {
388  TemplateParameterList *TempParams = D->getTemplateParameters();
389  TemplateParameterList *InstParams = SubstTemplateParams(TempParams);
390  if (!InstParams)
391    return NULL;
392
393  CXXRecordDecl *Pattern = D->getTemplatedDecl();
394  CXXRecordDecl *RecordInst
395    = CXXRecordDecl::Create(SemaRef.Context, Pattern->getTagKind(), Owner,
396                            Pattern->getLocation(), Pattern->getIdentifier(),
397                            Pattern->getTagKeywordLoc(), /*PrevDecl=*/ NULL,
398                            /*DelayTypeCreation=*/true);
399
400  ClassTemplateDecl *Inst
401    = ClassTemplateDecl::Create(SemaRef.Context, Owner, D->getLocation(),
402                                D->getIdentifier(), InstParams, RecordInst, 0);
403  RecordInst->setDescribedClassTemplate(Inst);
404  Inst->setAccess(D->getAccess());
405  Inst->setInstantiatedFromMemberTemplate(D);
406
407  // Trigger creation of the type for the instantiation.
408  SemaRef.Context.getTypeDeclType(RecordInst);
409
410  Owner->addDecl(Inst);
411  return Inst;
412}
413
414Decl *
415TemplateDeclInstantiator::VisitClassTemplatePartialSpecializationDecl(
416                                   ClassTemplatePartialSpecializationDecl *D) {
417  assert(false &&"Partial specializations of member templates are unsupported");
418  return 0;
419}
420
421Decl *
422TemplateDeclInstantiator::VisitFunctionTemplateDecl(FunctionTemplateDecl *D) {
423  // FIXME: Dig out the out-of-line definition of this function template?
424
425  TemplateParameterList *TempParams = D->getTemplateParameters();
426  TemplateParameterList *InstParams = SubstTemplateParams(TempParams);
427  if (!InstParams)
428    return NULL;
429
430  FunctionDecl *Instantiated = 0;
431  if (CXXMethodDecl *DMethod = dyn_cast<CXXMethodDecl>(D->getTemplatedDecl()))
432    Instantiated = cast_or_null<FunctionDecl>(VisitCXXMethodDecl(DMethod,
433                                                                 InstParams));
434  else
435    Instantiated = cast_or_null<FunctionDecl>(VisitFunctionDecl(
436                                                          D->getTemplatedDecl(),
437                                                                InstParams));
438
439  if (!Instantiated)
440    return 0;
441
442  // Link the instantiated function template declaration to the function
443  // template from which it was instantiated.
444  FunctionTemplateDecl *InstTemplate
445    = Instantiated->getDescribedFunctionTemplate();
446  InstTemplate->setAccess(D->getAccess());
447  assert(InstTemplate &&
448         "VisitFunctionDecl/CXXMethodDecl didn't create a template!");
449  if (!InstTemplate->getInstantiatedFromMemberTemplate())
450    InstTemplate->setInstantiatedFromMemberTemplate(D);
451
452  // Add non-friends into the owner.
453  if (!InstTemplate->getFriendObjectKind())
454    Owner->addDecl(InstTemplate);
455  return InstTemplate;
456}
457
458Decl *TemplateDeclInstantiator::VisitCXXRecordDecl(CXXRecordDecl *D) {
459  CXXRecordDecl *PrevDecl = 0;
460  if (D->isInjectedClassName())
461    PrevDecl = cast<CXXRecordDecl>(Owner);
462
463  CXXRecordDecl *Record
464    = CXXRecordDecl::Create(SemaRef.Context, D->getTagKind(), Owner,
465                            D->getLocation(), D->getIdentifier(),
466                            D->getTagKeywordLoc(), PrevDecl);
467  Record->setImplicit(D->isImplicit());
468  // FIXME: Check against AS_none is an ugly hack to work around the issue that
469  // the tag decls introduced by friend class declarations don't have an access
470  // specifier. Remove once this area of the code gets sorted out.
471  if (D->getAccess() != AS_none)
472    Record->setAccess(D->getAccess());
473  if (!D->isInjectedClassName())
474    Record->setInstantiationOfMemberClass(D, TSK_ImplicitInstantiation);
475
476  // If the original function was part of a friend declaration,
477  // inherit its namespace state.
478  if (Decl::FriendObjectKind FOK = D->getFriendObjectKind())
479    Record->setObjectOfFriendDecl(FOK == Decl::FOK_Declared);
480
481  Record->setAnonymousStructOrUnion(D->isAnonymousStructOrUnion());
482
483  Owner->addDecl(Record);
484  return Record;
485}
486
487/// Normal class members are of more specific types and therefore
488/// don't make it here.  This function serves two purposes:
489///   1) instantiating function templates
490///   2) substituting friend declarations
491/// FIXME: preserve function definitions in case #2
492  Decl *TemplateDeclInstantiator::VisitFunctionDecl(FunctionDecl *D,
493                                       TemplateParameterList *TemplateParams) {
494  // Check whether there is already a function template specialization for
495  // this declaration.
496  FunctionTemplateDecl *FunctionTemplate = D->getDescribedFunctionTemplate();
497  void *InsertPos = 0;
498  if (FunctionTemplate && !TemplateParams) {
499    llvm::FoldingSetNodeID ID;
500    FunctionTemplateSpecializationInfo::Profile(ID,
501                             TemplateArgs.getInnermost().getFlatArgumentList(),
502                                       TemplateArgs.getInnermost().flat_size(),
503                                                SemaRef.Context);
504
505    FunctionTemplateSpecializationInfo *Info
506      = FunctionTemplate->getSpecializations().FindNodeOrInsertPos(ID,
507                                                                   InsertPos);
508
509    // If we already have a function template specialization, return it.
510    if (Info)
511      return Info->Function;
512  }
513
514  Sema::LocalInstantiationScope Scope(SemaRef);
515
516  llvm::SmallVector<ParmVarDecl *, 4> Params;
517  QualType T = SubstFunctionType(D, Params);
518  if (T.isNull())
519    return 0;
520
521  // Build the instantiated method declaration.
522  DeclContext *DC = SemaRef.FindInstantiatedContext(D->getDeclContext(),
523                                                    TemplateArgs);
524  FunctionDecl *Function =
525      FunctionDecl::Create(SemaRef.Context, DC, D->getLocation(),
526                           D->getDeclName(), T, D->getDeclaratorInfo(),
527                           D->getStorageClass(),
528                           D->isInline(), D->hasWrittenPrototype());
529  Function->setLexicalDeclContext(Owner);
530
531  // Attach the parameters
532  for (unsigned P = 0; P < Params.size(); ++P)
533    Params[P]->setOwningFunction(Function);
534  Function->setParams(SemaRef.Context, Params.data(), Params.size());
535
536  if (TemplateParams) {
537    // Our resulting instantiation is actually a function template, since we
538    // are substituting only the outer template parameters. For example, given
539    //
540    //   template<typename T>
541    //   struct X {
542    //     template<typename U> friend void f(T, U);
543    //   };
544    //
545    //   X<int> x;
546    //
547    // We are instantiating the friend function template "f" within X<int>,
548    // which means substituting int for T, but leaving "f" as a friend function
549    // template.
550    // Build the function template itself.
551    FunctionTemplate = FunctionTemplateDecl::Create(SemaRef.Context, Owner,
552                                                    Function->getLocation(),
553                                                    Function->getDeclName(),
554                                                    TemplateParams, Function);
555    Function->setDescribedFunctionTemplate(FunctionTemplate);
556    FunctionTemplate->setLexicalDeclContext(D->getLexicalDeclContext());
557  }
558
559  if (InitFunctionInstantiation(Function, D))
560    Function->setInvalidDecl();
561
562  bool Redeclaration = false;
563  bool OverloadableAttrRequired = false;
564
565  NamedDecl *PrevDecl = 0;
566  if (TemplateParams || !FunctionTemplate) {
567    // Look only into the namespace where the friend would be declared to
568    // find a previous declaration. This is the innermost enclosing namespace,
569    // as described in ActOnFriendFunctionDecl.
570    Sema::LookupResult R;
571    SemaRef.LookupQualifiedName(R, DC, Function->getDeclName(),
572                              Sema::LookupOrdinaryName, true);
573
574    PrevDecl = R.getAsSingleDecl(SemaRef.Context);
575
576    // In C++, the previous declaration we find might be a tag type
577    // (class or enum). In this case, the new declaration will hide the
578    // tag type. Note that this does does not apply if we're declaring a
579    // typedef (C++ [dcl.typedef]p4).
580    if (PrevDecl && PrevDecl->getIdentifierNamespace() == Decl::IDNS_Tag)
581      PrevDecl = 0;
582  }
583
584  SemaRef.CheckFunctionDeclaration(Function, PrevDecl, Redeclaration,
585                                   /*FIXME:*/OverloadableAttrRequired);
586
587  // If the original function was part of a friend declaration,
588  // inherit its namespace state and add it to the owner.
589  NamedDecl *FromFriendD
590      = TemplateParams? cast<NamedDecl>(D->getDescribedFunctionTemplate()) : D;
591  if (FromFriendD->getFriendObjectKind()) {
592    NamedDecl *ToFriendD = 0;
593    if (TemplateParams) {
594      ToFriendD = cast<NamedDecl>(FunctionTemplate);
595      PrevDecl = FunctionTemplate->getPreviousDeclaration();
596    } else {
597      ToFriendD = Function;
598      PrevDecl = Function->getPreviousDeclaration();
599    }
600    ToFriendD->setObjectOfFriendDecl(PrevDecl != NULL);
601    if (!Owner->isDependentContext() && !PrevDecl)
602      DC->makeDeclVisibleInContext(ToFriendD, /* Recoverable = */ false);
603
604    if (!TemplateParams)
605      Function->setInstantiationOfMemberFunction(D, TSK_ImplicitInstantiation);
606  }
607
608  if (FunctionTemplate && !TemplateParams) {
609    // Record this function template specialization.
610    Function->setFunctionTemplateSpecialization(SemaRef.Context,
611                                                FunctionTemplate,
612                                                &TemplateArgs.getInnermost(),
613                                                InsertPos);
614  }
615
616  return Function;
617}
618
619Decl *
620TemplateDeclInstantiator::VisitCXXMethodDecl(CXXMethodDecl *D,
621                                      TemplateParameterList *TemplateParams) {
622  FunctionTemplateDecl *FunctionTemplate = D->getDescribedFunctionTemplate();
623  void *InsertPos = 0;
624  if (FunctionTemplate && !TemplateParams) {
625    // We are creating a function template specialization from a function
626    // template. Check whether there is already a function template
627    // specialization for this particular set of template arguments.
628    llvm::FoldingSetNodeID ID;
629    FunctionTemplateSpecializationInfo::Profile(ID,
630                            TemplateArgs.getInnermost().getFlatArgumentList(),
631                                      TemplateArgs.getInnermost().flat_size(),
632                                                SemaRef.Context);
633
634    FunctionTemplateSpecializationInfo *Info
635      = FunctionTemplate->getSpecializations().FindNodeOrInsertPos(ID,
636                                                                   InsertPos);
637
638    // If we already have a function template specialization, return it.
639    if (Info)
640      return Info->Function;
641  }
642
643  Sema::LocalInstantiationScope Scope(SemaRef);
644
645  llvm::SmallVector<ParmVarDecl *, 4> Params;
646  QualType T = SubstFunctionType(D, Params);
647  if (T.isNull())
648    return 0;
649
650  // Build the instantiated method declaration.
651  CXXRecordDecl *Record = cast<CXXRecordDecl>(Owner);
652  CXXMethodDecl *Method = 0;
653
654  DeclarationName Name = D->getDeclName();
655  if (CXXConstructorDecl *Constructor = dyn_cast<CXXConstructorDecl>(D)) {
656    QualType ClassTy = SemaRef.Context.getTypeDeclType(Record);
657    Name = SemaRef.Context.DeclarationNames.getCXXConstructorName(
658                                    SemaRef.Context.getCanonicalType(ClassTy));
659    Method = CXXConstructorDecl::Create(SemaRef.Context, Record,
660                                        Constructor->getLocation(),
661                                        Name, T,
662                                        Constructor->getDeclaratorInfo(),
663                                        Constructor->isExplicit(),
664                                        Constructor->isInline(), false);
665  } else if (CXXDestructorDecl *Destructor = dyn_cast<CXXDestructorDecl>(D)) {
666    QualType ClassTy = SemaRef.Context.getTypeDeclType(Record);
667    Name = SemaRef.Context.DeclarationNames.getCXXDestructorName(
668                                   SemaRef.Context.getCanonicalType(ClassTy));
669    Method = CXXDestructorDecl::Create(SemaRef.Context, Record,
670                                       Destructor->getLocation(), Name,
671                                       T, Destructor->isInline(), false);
672  } else if (CXXConversionDecl *Conversion = dyn_cast<CXXConversionDecl>(D)) {
673    CanQualType ConvTy
674      = SemaRef.Context.getCanonicalType(
675                                      T->getAs<FunctionType>()->getResultType());
676    Name = SemaRef.Context.DeclarationNames.getCXXConversionFunctionName(
677                                                                      ConvTy);
678    Method = CXXConversionDecl::Create(SemaRef.Context, Record,
679                                       Conversion->getLocation(), Name,
680                                       T, Conversion->getDeclaratorInfo(),
681                                       Conversion->isInline(),
682                                       Conversion->isExplicit());
683  } else {
684    Method = CXXMethodDecl::Create(SemaRef.Context, Record, D->getLocation(),
685                                   D->getDeclName(), T, D->getDeclaratorInfo(),
686                                   D->isStatic(), D->isInline());
687  }
688
689  if (TemplateParams) {
690    // Our resulting instantiation is actually a function template, since we
691    // are substituting only the outer template parameters. For example, given
692    //
693    //   template<typename T>
694    //   struct X {
695    //     template<typename U> void f(T, U);
696    //   };
697    //
698    //   X<int> x;
699    //
700    // We are instantiating the member template "f" within X<int>, which means
701    // substituting int for T, but leaving "f" as a member function template.
702    // Build the function template itself.
703    FunctionTemplate = FunctionTemplateDecl::Create(SemaRef.Context, Record,
704                                                    Method->getLocation(),
705                                                    Method->getDeclName(),
706                                                    TemplateParams, Method);
707    if (D->isOutOfLine())
708      FunctionTemplate->setLexicalDeclContext(D->getLexicalDeclContext());
709    Method->setDescribedFunctionTemplate(FunctionTemplate);
710  } else if (!FunctionTemplate)
711    Method->setInstantiationOfMemberFunction(D, TSK_ImplicitInstantiation);
712
713  // If we are instantiating a member function defined
714  // out-of-line, the instantiation will have the same lexical
715  // context (which will be a namespace scope) as the template.
716  if (D->isOutOfLine())
717    Method->setLexicalDeclContext(D->getLexicalDeclContext());
718
719  // Attach the parameters
720  for (unsigned P = 0; P < Params.size(); ++P)
721    Params[P]->setOwningFunction(Method);
722  Method->setParams(SemaRef.Context, Params.data(), Params.size());
723
724  if (InitMethodInstantiation(Method, D))
725    Method->setInvalidDecl();
726
727  NamedDecl *PrevDecl = 0;
728
729  if (!FunctionTemplate || TemplateParams) {
730    Sema::LookupResult R;
731    SemaRef.LookupQualifiedName(R, Owner, Name, Sema::LookupOrdinaryName, true);
732    PrevDecl = R.getAsSingleDecl(SemaRef.Context);
733
734    // In C++, the previous declaration we find might be a tag type
735    // (class or enum). In this case, the new declaration will hide the
736    // tag type. Note that this does does not apply if we're declaring a
737    // typedef (C++ [dcl.typedef]p4).
738    if (PrevDecl && PrevDecl->getIdentifierNamespace() == Decl::IDNS_Tag)
739      PrevDecl = 0;
740  }
741
742  if (FunctionTemplate && !TemplateParams)
743    // Record this function template specialization.
744    Method->setFunctionTemplateSpecialization(SemaRef.Context,
745                                              FunctionTemplate,
746                                              &TemplateArgs.getInnermost(),
747                                              InsertPos);
748
749  bool Redeclaration = false;
750  bool OverloadableAttrRequired = false;
751  SemaRef.CheckFunctionDeclaration(Method, PrevDecl, Redeclaration,
752                                   /*FIXME:*/OverloadableAttrRequired);
753
754  if (!FunctionTemplate && (!Method->isInvalidDecl() || !PrevDecl) &&
755      !Method->getFriendObjectKind())
756    Owner->addDecl(Method);
757
758  return Method;
759}
760
761Decl *TemplateDeclInstantiator::VisitCXXConstructorDecl(CXXConstructorDecl *D) {
762  return VisitCXXMethodDecl(D);
763}
764
765Decl *TemplateDeclInstantiator::VisitCXXDestructorDecl(CXXDestructorDecl *D) {
766  return VisitCXXMethodDecl(D);
767}
768
769Decl *TemplateDeclInstantiator::VisitCXXConversionDecl(CXXConversionDecl *D) {
770  return VisitCXXMethodDecl(D);
771}
772
773ParmVarDecl *TemplateDeclInstantiator::VisitParmVarDecl(ParmVarDecl *D) {
774  QualType OrigT = SemaRef.SubstType(D->getOriginalType(), TemplateArgs,
775                                           D->getLocation(), D->getDeclName());
776  if (OrigT.isNull())
777    return 0;
778
779  QualType T = SemaRef.adjustParameterType(OrigT);
780
781  // Allocate the parameter
782  ParmVarDecl *Param = 0;
783  if (T == OrigT)
784    Param = ParmVarDecl::Create(SemaRef.Context, Owner, D->getLocation(),
785                                D->getIdentifier(), T, D->getDeclaratorInfo(),
786                                D->getStorageClass(), 0);
787  else
788    Param = OriginalParmVarDecl::Create(SemaRef.Context, Owner,
789                                        D->getLocation(), D->getIdentifier(),
790                                        T, D->getDeclaratorInfo(), OrigT,
791                                        D->getStorageClass(), 0);
792
793  // Mark the default argument as being uninstantiated.
794  if (D->hasUninstantiatedDefaultArg())
795    Param->setUninstantiatedDefaultArg(D->getUninstantiatedDefaultArg());
796  else if (Expr *Arg = D->getDefaultArg())
797    Param->setUninstantiatedDefaultArg(Arg);
798
799  // Note: we don't try to instantiate function parameters until after
800  // we've instantiated the function's type. Therefore, we don't have
801  // to check for 'void' parameter types here.
802  SemaRef.CurrentInstantiationScope->InstantiatedLocal(D, Param);
803  return Param;
804}
805
806Decl *
807TemplateDeclInstantiator::VisitOriginalParmVarDecl(OriginalParmVarDecl *D) {
808  // Since parameter types can decay either before or after
809  // instantiation, we simply treat OriginalParmVarDecls as
810  // ParmVarDecls the same way, and create one or the other depending
811  // on what happens after template instantiation.
812  return VisitParmVarDecl(D);
813}
814
815Decl *TemplateDeclInstantiator::VisitTemplateTypeParmDecl(
816                                                    TemplateTypeParmDecl *D) {
817  // TODO: don't always clone when decls are refcounted.
818  const Type* T = D->getTypeForDecl();
819  assert(T->isTemplateTypeParmType());
820  const TemplateTypeParmType *TTPT = T->getAs<TemplateTypeParmType>();
821
822  TemplateTypeParmDecl *Inst =
823    TemplateTypeParmDecl::Create(SemaRef.Context, Owner, D->getLocation(),
824                                 TTPT->getDepth(), TTPT->getIndex(),
825                                 TTPT->getName(),
826                                 D->wasDeclaredWithTypename(),
827                                 D->isParameterPack());
828
829  if (D->hasDefaultArgument()) {
830    QualType DefaultPattern = D->getDefaultArgument();
831    QualType DefaultInst
832      = SemaRef.SubstType(DefaultPattern, TemplateArgs,
833                          D->getDefaultArgumentLoc(),
834                          D->getDeclName());
835
836    Inst->setDefaultArgument(DefaultInst,
837                             D->getDefaultArgumentLoc(),
838                             D->defaultArgumentWasInherited() /* preserve? */);
839  }
840
841  return Inst;
842}
843
844Decl *
845TemplateDeclInstantiator::VisitUnresolvedUsingDecl(UnresolvedUsingDecl *D) {
846  NestedNameSpecifier *NNS =
847    SemaRef.SubstNestedNameSpecifier(D->getTargetNestedNameSpecifier(),
848                                     D->getTargetNestedNameRange(),
849                                     TemplateArgs);
850  if (!NNS)
851    return 0;
852
853  CXXScopeSpec SS;
854  SS.setRange(D->getTargetNestedNameRange());
855  SS.setScopeRep(NNS);
856
857  NamedDecl *UD =
858    SemaRef.BuildUsingDeclaration(D->getLocation(), SS,
859                                  D->getTargetNameLocation(),
860                                  D->getTargetName(), 0, D->isTypeName());
861  if (UD)
862    SemaRef.Context.setInstantiatedFromUnresolvedUsingDecl(cast<UsingDecl>(UD),
863                                                           D);
864  return UD;
865}
866
867Decl *Sema::SubstDecl(Decl *D, DeclContext *Owner,
868                      const MultiLevelTemplateArgumentList &TemplateArgs) {
869  TemplateDeclInstantiator Instantiator(*this, Owner, TemplateArgs);
870  return Instantiator.Visit(D);
871}
872
873/// \brief Instantiates a nested template parameter list in the current
874/// instantiation context.
875///
876/// \param L The parameter list to instantiate
877///
878/// \returns NULL if there was an error
879TemplateParameterList *
880TemplateDeclInstantiator::SubstTemplateParams(TemplateParameterList *L) {
881  // Get errors for all the parameters before bailing out.
882  bool Invalid = false;
883
884  unsigned N = L->size();
885  typedef llvm::SmallVector<NamedDecl *, 8> ParamVector;
886  ParamVector Params;
887  Params.reserve(N);
888  for (TemplateParameterList::iterator PI = L->begin(), PE = L->end();
889       PI != PE; ++PI) {
890    NamedDecl *D = cast_or_null<NamedDecl>(Visit(*PI));
891    Params.push_back(D);
892    Invalid = Invalid || !D;
893  }
894
895  // Clean up if we had an error.
896  if (Invalid) {
897    for (ParamVector::iterator PI = Params.begin(), PE = Params.end();
898         PI != PE; ++PI)
899      if (*PI)
900        (*PI)->Destroy(SemaRef.Context);
901    return NULL;
902  }
903
904  TemplateParameterList *InstL
905    = TemplateParameterList::Create(SemaRef.Context, L->getTemplateLoc(),
906                                    L->getLAngleLoc(), &Params.front(), N,
907                                    L->getRAngleLoc());
908  return InstL;
909}
910
911/// \brief Does substitution on the type of the given function, including
912/// all of the function parameters.
913///
914/// \param D The function whose type will be the basis of the substitution
915///
916/// \param Params the instantiated parameter declarations
917
918/// \returns the instantiated function's type if successful, a NULL
919/// type if there was an error.
920QualType
921TemplateDeclInstantiator::SubstFunctionType(FunctionDecl *D,
922                              llvm::SmallVectorImpl<ParmVarDecl *> &Params) {
923  bool InvalidDecl = false;
924
925  // Substitute all of the function's formal parameter types.
926  TemplateDeclInstantiator ParamInstantiator(SemaRef, 0, TemplateArgs);
927  llvm::SmallVector<QualType, 4> ParamTys;
928  for (FunctionDecl::param_iterator P = D->param_begin(),
929                                 PEnd = D->param_end();
930       P != PEnd; ++P) {
931    if (ParmVarDecl *PInst = ParamInstantiator.VisitParmVarDecl(*P)) {
932      if (PInst->getType()->isVoidType()) {
933        SemaRef.Diag(PInst->getLocation(), diag::err_param_with_void_type);
934        PInst->setInvalidDecl();
935      } else if (SemaRef.RequireNonAbstractType(PInst->getLocation(),
936                                                PInst->getType(),
937                                                diag::err_abstract_type_in_decl,
938                                                Sema::AbstractParamType))
939        PInst->setInvalidDecl();
940
941      Params.push_back(PInst);
942      ParamTys.push_back(PInst->getType());
943
944      if (PInst->isInvalidDecl())
945        InvalidDecl = true;
946    } else
947      InvalidDecl = true;
948  }
949
950  // FIXME: Deallocate dead declarations.
951  if (InvalidDecl)
952    return QualType();
953
954  const FunctionProtoType *Proto = D->getType()->getAs<FunctionProtoType>();
955  assert(Proto && "Missing prototype?");
956  QualType ResultType
957    = SemaRef.SubstType(Proto->getResultType(), TemplateArgs,
958                        D->getLocation(), D->getDeclName());
959  if (ResultType.isNull())
960    return QualType();
961
962  return SemaRef.BuildFunctionType(ResultType, ParamTys.data(), ParamTys.size(),
963                                   Proto->isVariadic(), Proto->getTypeQuals(),
964                                   D->getLocation(), D->getDeclName());
965}
966
967/// \brief Initializes the common fields of an instantiation function
968/// declaration (New) from the corresponding fields of its template (Tmpl).
969///
970/// \returns true if there was an error
971bool
972TemplateDeclInstantiator::InitFunctionInstantiation(FunctionDecl *New,
973                                                    FunctionDecl *Tmpl) {
974  if (Tmpl->isDeleted())
975    New->setDeleted();
976
977  // If we are performing substituting explicitly-specified template arguments
978  // or deduced template arguments into a function template and we reach this
979  // point, we are now past the point where SFINAE applies and have committed
980  // to keeping the new function template specialization. We therefore
981  // convert the active template instantiation for the function template
982  // into a template instantiation for this specific function template
983  // specialization, which is not a SFINAE context, so that we diagnose any
984  // further errors in the declaration itself.
985  typedef Sema::ActiveTemplateInstantiation ActiveInstType;
986  ActiveInstType &ActiveInst = SemaRef.ActiveTemplateInstantiations.back();
987  if (ActiveInst.Kind == ActiveInstType::ExplicitTemplateArgumentSubstitution ||
988      ActiveInst.Kind == ActiveInstType::DeducedTemplateArgumentSubstitution) {
989    if (FunctionTemplateDecl *FunTmpl
990          = dyn_cast<FunctionTemplateDecl>((Decl *)ActiveInst.Entity)) {
991      assert(FunTmpl->getTemplatedDecl() == Tmpl &&
992             "Deduction from the wrong function template?");
993      (void) FunTmpl;
994      ActiveInst.Kind = ActiveInstType::TemplateInstantiation;
995      ActiveInst.Entity = reinterpret_cast<uintptr_t>(New);
996    }
997  }
998
999  return false;
1000}
1001
1002/// \brief Initializes common fields of an instantiated method
1003/// declaration (New) from the corresponding fields of its template
1004/// (Tmpl).
1005///
1006/// \returns true if there was an error
1007bool
1008TemplateDeclInstantiator::InitMethodInstantiation(CXXMethodDecl *New,
1009                                                  CXXMethodDecl *Tmpl) {
1010  if (InitFunctionInstantiation(New, Tmpl))
1011    return true;
1012
1013  CXXRecordDecl *Record = cast<CXXRecordDecl>(Owner);
1014  New->setAccess(Tmpl->getAccess());
1015  if (Tmpl->isVirtualAsWritten()) {
1016    New->setVirtualAsWritten(true);
1017    Record->setAggregate(false);
1018    Record->setPOD(false);
1019    Record->setEmpty(false);
1020    Record->setPolymorphic(true);
1021  }
1022  if (Tmpl->isPure()) {
1023    New->setPure();
1024    Record->setAbstract(true);
1025  }
1026
1027  // FIXME: attributes
1028  // FIXME: New needs a pointer to Tmpl
1029  return false;
1030}
1031
1032/// \brief Instantiate the definition of the given function from its
1033/// template.
1034///
1035/// \param PointOfInstantiation the point at which the instantiation was
1036/// required. Note that this is not precisely a "point of instantiation"
1037/// for the function, but it's close.
1038///
1039/// \param Function the already-instantiated declaration of a
1040/// function template specialization or member function of a class template
1041/// specialization.
1042///
1043/// \param Recursive if true, recursively instantiates any functions that
1044/// are required by this instantiation.
1045void Sema::InstantiateFunctionDefinition(SourceLocation PointOfInstantiation,
1046                                         FunctionDecl *Function,
1047                                         bool Recursive) {
1048  if (Function->isInvalidDecl())
1049    return;
1050
1051  assert(!Function->getBody() && "Already instantiated!");
1052
1053  // Never instantiate an explicit specialization.
1054  if (Function->getTemplateSpecializationKind() == TSK_ExplicitSpecialization)
1055    return;
1056
1057  // Find the function body that we'll be substituting.
1058  const FunctionDecl *PatternDecl = 0;
1059  if (FunctionTemplateDecl *Primary = Function->getPrimaryTemplate()) {
1060    while (Primary->getInstantiatedFromMemberTemplate())
1061      Primary = Primary->getInstantiatedFromMemberTemplate();
1062
1063    PatternDecl = Primary->getTemplatedDecl();
1064  } else
1065    PatternDecl = Function->getInstantiatedFromMemberFunction();
1066  Stmt *Pattern = 0;
1067  if (PatternDecl)
1068    Pattern = PatternDecl->getBody(PatternDecl);
1069
1070  if (!Pattern)
1071    return;
1072
1073  // C++0x [temp.explicit]p9:
1074  //   Except for inline functions, other explicit instantiation declarations
1075  //   have the effect of suppressing the implicit instantiation of the entity
1076  //   to which they refer.
1077  if (Function->getTemplateSpecializationKind()
1078        == TSK_ExplicitInstantiationDeclaration &&
1079      PatternDecl->isOutOfLine() && !PatternDecl->isInline())
1080    return;
1081
1082  InstantiatingTemplate Inst(*this, PointOfInstantiation, Function);
1083  if (Inst)
1084    return;
1085
1086  // If we're performing recursive template instantiation, create our own
1087  // queue of pending implicit instantiations that we will instantiate later,
1088  // while we're still within our own instantiation context.
1089  std::deque<PendingImplicitInstantiation> SavedPendingImplicitInstantiations;
1090  if (Recursive)
1091    PendingImplicitInstantiations.swap(SavedPendingImplicitInstantiations);
1092
1093  ActOnStartOfFunctionDef(0, DeclPtrTy::make(Function));
1094
1095  // Introduce a new scope where local variable instantiations will be
1096  // recorded.
1097  LocalInstantiationScope Scope(*this);
1098
1099  // Introduce the instantiated function parameters into the local
1100  // instantiation scope.
1101  for (unsigned I = 0, N = PatternDecl->getNumParams(); I != N; ++I)
1102    Scope.InstantiatedLocal(PatternDecl->getParamDecl(I),
1103                            Function->getParamDecl(I));
1104
1105  // Enter the scope of this instantiation. We don't use
1106  // PushDeclContext because we don't have a scope.
1107  DeclContext *PreviousContext = CurContext;
1108  CurContext = Function;
1109
1110  MultiLevelTemplateArgumentList TemplateArgs =
1111    getTemplateInstantiationArgs(Function);
1112
1113  // If this is a constructor, instantiate the member initializers.
1114  if (const CXXConstructorDecl *Ctor =
1115        dyn_cast<CXXConstructorDecl>(PatternDecl)) {
1116    InstantiateMemInitializers(cast<CXXConstructorDecl>(Function), Ctor,
1117                               TemplateArgs);
1118  }
1119
1120  // Instantiate the function body.
1121  OwningStmtResult Body = SubstStmt(Pattern, TemplateArgs);
1122
1123  if (Body.isInvalid())
1124    Function->setInvalidDecl();
1125
1126  ActOnFinishFunctionBody(DeclPtrTy::make(Function), move(Body),
1127                          /*IsInstantiation=*/true);
1128
1129  CurContext = PreviousContext;
1130
1131  DeclGroupRef DG(Function);
1132  Consumer.HandleTopLevelDecl(DG);
1133
1134  if (Recursive) {
1135    // Instantiate any pending implicit instantiations found during the
1136    // instantiation of this template.
1137    PerformPendingImplicitInstantiations();
1138
1139    // Restore the set of pending implicit instantiations.
1140    PendingImplicitInstantiations.swap(SavedPendingImplicitInstantiations);
1141  }
1142}
1143
1144/// \brief Instantiate the definition of the given variable from its
1145/// template.
1146///
1147/// \param PointOfInstantiation the point at which the instantiation was
1148/// required. Note that this is not precisely a "point of instantiation"
1149/// for the function, but it's close.
1150///
1151/// \param Var the already-instantiated declaration of a static member
1152/// variable of a class template specialization.
1153///
1154/// \param Recursive if true, recursively instantiates any functions that
1155/// are required by this instantiation.
1156void Sema::InstantiateStaticDataMemberDefinition(
1157                                          SourceLocation PointOfInstantiation,
1158                                                 VarDecl *Var,
1159                                                 bool Recursive) {
1160  if (Var->isInvalidDecl())
1161    return;
1162
1163  // Find the out-of-line definition of this static data member.
1164  VarDecl *Def = Var->getInstantiatedFromStaticDataMember();
1165  bool FoundOutOfLineDef = false;
1166  assert(Def && "This data member was not instantiated from a template?");
1167  assert(Def->isStaticDataMember() && "Not a static data member?");
1168  for (VarDecl::redecl_iterator RD = Def->redecls_begin(),
1169                             RDEnd = Def->redecls_end();
1170       RD != RDEnd; ++RD) {
1171    if (RD->getLexicalDeclContext()->isFileContext()) {
1172      Def = *RD;
1173      FoundOutOfLineDef = true;
1174    }
1175  }
1176
1177  if (!FoundOutOfLineDef) {
1178    // We did not find an out-of-line definition of this static data member,
1179    // so we won't perform any instantiation. Rather, we rely on the user to
1180    // instantiate this definition (or provide a specialization for it) in
1181    // another translation unit.
1182    return;
1183  }
1184
1185  // Never instantiate an explicit specialization.
1186  if (Def->getTemplateSpecializationKind() == TSK_ExplicitSpecialization)
1187    return;
1188
1189  // C++0x [temp.explicit]p9:
1190  //   Except for inline functions, other explicit instantiation declarations
1191  //   have the effect of suppressing the implicit instantiation of the entity
1192  //   to which they refer.
1193  if (Def->getTemplateSpecializationKind()
1194        == TSK_ExplicitInstantiationDeclaration)
1195    return;
1196
1197  InstantiatingTemplate Inst(*this, PointOfInstantiation, Var);
1198  if (Inst)
1199    return;
1200
1201  // If we're performing recursive template instantiation, create our own
1202  // queue of pending implicit instantiations that we will instantiate later,
1203  // while we're still within our own instantiation context.
1204  std::deque<PendingImplicitInstantiation> SavedPendingImplicitInstantiations;
1205  if (Recursive)
1206    PendingImplicitInstantiations.swap(SavedPendingImplicitInstantiations);
1207
1208  // Enter the scope of this instantiation. We don't use
1209  // PushDeclContext because we don't have a scope.
1210  DeclContext *PreviousContext = CurContext;
1211  CurContext = Var->getDeclContext();
1212
1213  Var = cast_or_null<VarDecl>(SubstDecl(Def, Var->getDeclContext(),
1214                                          getTemplateInstantiationArgs(Var)));
1215
1216  CurContext = PreviousContext;
1217
1218  if (Var) {
1219    DeclGroupRef DG(Var);
1220    Consumer.HandleTopLevelDecl(DG);
1221  }
1222
1223  if (Recursive) {
1224    // Instantiate any pending implicit instantiations found during the
1225    // instantiation of this template.
1226    PerformPendingImplicitInstantiations();
1227
1228    // Restore the set of pending implicit instantiations.
1229    PendingImplicitInstantiations.swap(SavedPendingImplicitInstantiations);
1230  }
1231}
1232
1233void
1234Sema::InstantiateMemInitializers(CXXConstructorDecl *New,
1235                                 const CXXConstructorDecl *Tmpl,
1236                           const MultiLevelTemplateArgumentList &TemplateArgs) {
1237
1238  llvm::SmallVector<MemInitTy*, 4> NewInits;
1239
1240  // Instantiate all the initializers.
1241  for (CXXConstructorDecl::init_const_iterator Inits = Tmpl->init_begin(),
1242                                            InitsEnd = Tmpl->init_end();
1243       Inits != InitsEnd; ++Inits) {
1244    CXXBaseOrMemberInitializer *Init = *Inits;
1245
1246    ASTOwningVector<&ActionBase::DeleteExpr> NewArgs(*this);
1247
1248    // Instantiate all the arguments.
1249    for (ExprIterator Args = Init->arg_begin(), ArgsEnd = Init->arg_end();
1250         Args != ArgsEnd; ++Args) {
1251      OwningExprResult NewArg = SubstExpr(*Args, TemplateArgs);
1252
1253      if (NewArg.isInvalid())
1254        New->setInvalidDecl();
1255      else
1256        NewArgs.push_back(NewArg.takeAs<Expr>());
1257    }
1258
1259    MemInitResult NewInit;
1260
1261    if (Init->isBaseInitializer()) {
1262      QualType BaseType(Init->getBaseClass(), 0);
1263      BaseType = SubstType(BaseType, TemplateArgs, Init->getSourceLocation(),
1264                           New->getDeclName());
1265
1266      NewInit = BuildBaseInitializer(BaseType,
1267                                     (Expr **)NewArgs.data(),
1268                                     NewArgs.size(),
1269                                     Init->getSourceLocation(),
1270                                     Init->getRParenLoc(),
1271                                     New->getParent());
1272    } else if (Init->isMemberInitializer()) {
1273      FieldDecl *Member;
1274
1275      // Is this an anonymous union?
1276      if (FieldDecl *UnionInit = Init->getAnonUnionMember())
1277        Member = cast<FieldDecl>(FindInstantiatedDecl(UnionInit, TemplateArgs));
1278      else
1279        Member = cast<FieldDecl>(FindInstantiatedDecl(Init->getMember(),
1280                                                      TemplateArgs));
1281
1282      NewInit = BuildMemberInitializer(Member, (Expr **)NewArgs.data(),
1283                                       NewArgs.size(),
1284                                       Init->getSourceLocation(),
1285                                       Init->getRParenLoc());
1286    }
1287
1288    if (NewInit.isInvalid())
1289      New->setInvalidDecl();
1290    else {
1291      // FIXME: It would be nice if ASTOwningVector had a release function.
1292      NewArgs.take();
1293
1294      NewInits.push_back((MemInitTy *)NewInit.get());
1295    }
1296  }
1297
1298  // Assign all the initializers to the new constructor.
1299  ActOnMemInitializers(DeclPtrTy::make(New),
1300                       /*FIXME: ColonLoc */
1301                       SourceLocation(),
1302                       NewInits.data(), NewInits.size());
1303}
1304
1305// TODO: this could be templated if the various decl types used the
1306// same method name.
1307static bool isInstantiationOf(ClassTemplateDecl *Pattern,
1308                              ClassTemplateDecl *Instance) {
1309  Pattern = Pattern->getCanonicalDecl();
1310
1311  do {
1312    Instance = Instance->getCanonicalDecl();
1313    if (Pattern == Instance) return true;
1314    Instance = Instance->getInstantiatedFromMemberTemplate();
1315  } while (Instance);
1316
1317  return false;
1318}
1319
1320static bool isInstantiationOf(FunctionTemplateDecl *Pattern,
1321                              FunctionTemplateDecl *Instance) {
1322  Pattern = Pattern->getCanonicalDecl();
1323
1324  do {
1325    Instance = Instance->getCanonicalDecl();
1326    if (Pattern == Instance) return true;
1327    Instance = Instance->getInstantiatedFromMemberTemplate();
1328  } while (Instance);
1329
1330  return false;
1331}
1332
1333static bool isInstantiationOf(CXXRecordDecl *Pattern,
1334                              CXXRecordDecl *Instance) {
1335  Pattern = Pattern->getCanonicalDecl();
1336
1337  do {
1338    Instance = Instance->getCanonicalDecl();
1339    if (Pattern == Instance) return true;
1340    Instance = Instance->getInstantiatedFromMemberClass();
1341  } while (Instance);
1342
1343  return false;
1344}
1345
1346static bool isInstantiationOf(FunctionDecl *Pattern,
1347                              FunctionDecl *Instance) {
1348  Pattern = Pattern->getCanonicalDecl();
1349
1350  do {
1351    Instance = Instance->getCanonicalDecl();
1352    if (Pattern == Instance) return true;
1353    Instance = Instance->getInstantiatedFromMemberFunction();
1354  } while (Instance);
1355
1356  return false;
1357}
1358
1359static bool isInstantiationOf(EnumDecl *Pattern,
1360                              EnumDecl *Instance) {
1361  Pattern = Pattern->getCanonicalDecl();
1362
1363  do {
1364    Instance = Instance->getCanonicalDecl();
1365    if (Pattern == Instance) return true;
1366    Instance = Instance->getInstantiatedFromMemberEnum();
1367  } while (Instance);
1368
1369  return false;
1370}
1371
1372static bool isInstantiationOf(UnresolvedUsingDecl *Pattern,
1373                              UsingDecl *Instance,
1374                              ASTContext &C) {
1375  return C.getInstantiatedFromUnresolvedUsingDecl(Instance) == Pattern;
1376}
1377
1378static bool isInstantiationOfStaticDataMember(VarDecl *Pattern,
1379                                              VarDecl *Instance) {
1380  assert(Instance->isStaticDataMember());
1381
1382  Pattern = Pattern->getCanonicalDecl();
1383
1384  do {
1385    Instance = Instance->getCanonicalDecl();
1386    if (Pattern == Instance) return true;
1387    Instance = Instance->getInstantiatedFromStaticDataMember();
1388  } while (Instance);
1389
1390  return false;
1391}
1392
1393static bool isInstantiationOf(ASTContext &Ctx, NamedDecl *D, Decl *Other) {
1394  if (D->getKind() != Other->getKind()) {
1395    if (UnresolvedUsingDecl *UUD = dyn_cast<UnresolvedUsingDecl>(D)) {
1396      if (UsingDecl *UD = dyn_cast<UsingDecl>(Other)) {
1397        return isInstantiationOf(UUD, UD, Ctx);
1398      }
1399    }
1400
1401    return false;
1402  }
1403
1404  if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(Other))
1405    return isInstantiationOf(cast<CXXRecordDecl>(D), Record);
1406
1407  if (FunctionDecl *Function = dyn_cast<FunctionDecl>(Other))
1408    return isInstantiationOf(cast<FunctionDecl>(D), Function);
1409
1410  if (EnumDecl *Enum = dyn_cast<EnumDecl>(Other))
1411    return isInstantiationOf(cast<EnumDecl>(D), Enum);
1412
1413  if (VarDecl *Var = dyn_cast<VarDecl>(Other))
1414    if (Var->isStaticDataMember())
1415      return isInstantiationOfStaticDataMember(cast<VarDecl>(D), Var);
1416
1417  if (ClassTemplateDecl *Temp = dyn_cast<ClassTemplateDecl>(Other))
1418    return isInstantiationOf(cast<ClassTemplateDecl>(D), Temp);
1419
1420  if (FunctionTemplateDecl *Temp = dyn_cast<FunctionTemplateDecl>(Other))
1421    return isInstantiationOf(cast<FunctionTemplateDecl>(D), Temp);
1422
1423  if (FieldDecl *Field = dyn_cast<FieldDecl>(Other)) {
1424    if (!Field->getDeclName()) {
1425      // This is an unnamed field.
1426      return Ctx.getInstantiatedFromUnnamedFieldDecl(Field) ==
1427        cast<FieldDecl>(D);
1428    }
1429  }
1430
1431  return D->getDeclName() && isa<NamedDecl>(Other) &&
1432    D->getDeclName() == cast<NamedDecl>(Other)->getDeclName();
1433}
1434
1435template<typename ForwardIterator>
1436static NamedDecl *findInstantiationOf(ASTContext &Ctx,
1437                                      NamedDecl *D,
1438                                      ForwardIterator first,
1439                                      ForwardIterator last) {
1440  for (; first != last; ++first)
1441    if (isInstantiationOf(Ctx, D, *first))
1442      return cast<NamedDecl>(*first);
1443
1444  return 0;
1445}
1446
1447/// \brief Finds the instantiation of the given declaration context
1448/// within the current instantiation.
1449///
1450/// \returns NULL if there was an error
1451DeclContext *Sema::FindInstantiatedContext(DeclContext* DC,
1452                          const MultiLevelTemplateArgumentList &TemplateArgs) {
1453  if (NamedDecl *D = dyn_cast<NamedDecl>(DC)) {
1454    Decl* ID = FindInstantiatedDecl(D, TemplateArgs);
1455    return cast_or_null<DeclContext>(ID);
1456  } else return DC;
1457}
1458
1459/// \brief Find the instantiation of the given declaration within the
1460/// current instantiation.
1461///
1462/// This routine is intended to be used when \p D is a declaration
1463/// referenced from within a template, that needs to mapped into the
1464/// corresponding declaration within an instantiation. For example,
1465/// given:
1466///
1467/// \code
1468/// template<typename T>
1469/// struct X {
1470///   enum Kind {
1471///     KnownValue = sizeof(T)
1472///   };
1473///
1474///   bool getKind() const { return KnownValue; }
1475/// };
1476///
1477/// template struct X<int>;
1478/// \endcode
1479///
1480/// In the instantiation of X<int>::getKind(), we need to map the
1481/// EnumConstantDecl for KnownValue (which refers to
1482/// X<T>::<Kind>::KnownValue) to its instantiation
1483/// (X<int>::<Kind>::KnownValue). InstantiateCurrentDeclRef() performs
1484/// this mapping from within the instantiation of X<int>.
1485NamedDecl *Sema::FindInstantiatedDecl(NamedDecl *D,
1486                          const MultiLevelTemplateArgumentList &TemplateArgs) {
1487  if (OverloadedFunctionDecl *Ovl = dyn_cast<OverloadedFunctionDecl>(D)) {
1488    // Transform all of the elements of the overloaded function set.
1489    OverloadedFunctionDecl *Result
1490      = OverloadedFunctionDecl::Create(Context, CurContext, Ovl->getDeclName());
1491
1492    for (OverloadedFunctionDecl::function_iterator F = Ovl->function_begin(),
1493                                                FEnd = Ovl->function_end();
1494         F != FEnd; ++F) {
1495      Result->addOverload(
1496        AnyFunctionDecl::getFromNamedDecl(FindInstantiatedDecl(*F,
1497                                                               TemplateArgs)));
1498    }
1499
1500    return Result;
1501  }
1502
1503  DeclContext *ParentDC = D->getDeclContext();
1504  if (isa<ParmVarDecl>(D) || ParentDC->isFunctionOrMethod()) {
1505    // D is a local of some kind. Look into the map of local
1506    // declarations to their instantiations.
1507    return cast<NamedDecl>(CurrentInstantiationScope->getInstantiationOf(D));
1508  }
1509
1510  if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(D)) {
1511    if (!Record->isDependentContext())
1512      return D;
1513
1514    // If the RecordDecl is actually the injected-class-name or a "templated"
1515    // declaration for a class template or class template partial
1516    // specialization, substitute into the injected-class-name of the
1517    // class template or partial specialization to find the new DeclContext.
1518    QualType T;
1519    ClassTemplateDecl *ClassTemplate = Record->getDescribedClassTemplate();
1520
1521    if (ClassTemplate) {
1522      T = ClassTemplate->getInjectedClassNameType(Context);
1523    } else if (ClassTemplatePartialSpecializationDecl *PartialSpec
1524                 = dyn_cast<ClassTemplatePartialSpecializationDecl>(Record)) {
1525      T = Context.getTypeDeclType(Record);
1526      ClassTemplate = PartialSpec->getSpecializedTemplate();
1527    }
1528
1529    if (!T.isNull()) {
1530      // Substitute into the injected-class-name to get the type corresponding
1531      // to the instantiation we want. This substitution should never fail,
1532      // since we know we can instantiate the injected-class-name or we wouldn't
1533      // have gotten to the injected-class-name!
1534      // FIXME: Can we use the CurrentInstantiationScope to avoid this extra
1535      // instantiation in the common case?
1536      T = SubstType(T, TemplateArgs, SourceLocation(), DeclarationName());
1537      assert(!T.isNull() && "Instantiation of injected-class-name cannot fail.");
1538
1539      if (!T->isDependentType()) {
1540        assert(T->isRecordType() && "Instantiation must produce a record type");
1541        return T->getAs<RecordType>()->getDecl();
1542      }
1543
1544      // We are performing "partial" template instantiation to create the
1545      // member declarations for the members of a class template
1546      // specialization. Therefore, D is actually referring to something in
1547      // the current instantiation. Look through the current context,
1548      // which contains actual instantiations, to find the instantiation of
1549      // the "current instantiation" that D refers to.
1550      for (DeclContext *DC = CurContext; !DC->isFileContext();
1551           DC = DC->getParent()) {
1552        if (ClassTemplateSpecializationDecl *Spec
1553              = dyn_cast<ClassTemplateSpecializationDecl>(DC))
1554          if (isInstantiationOf(ClassTemplate,
1555                                Spec->getSpecializedTemplate()))
1556            return Spec;
1557      }
1558
1559      assert(false &&
1560             "Unable to find declaration for the current instantiation");
1561      return Record;
1562    }
1563
1564    // Fall through to deal with other dependent record types (e.g.,
1565    // anonymous unions in class templates).
1566  }
1567
1568  if (!ParentDC->isDependentContext())
1569    return D;
1570
1571  ParentDC = FindInstantiatedContext(ParentDC, TemplateArgs);
1572  if (!ParentDC)
1573    return 0;
1574
1575  if (ParentDC != D->getDeclContext()) {
1576    // We performed some kind of instantiation in the parent context,
1577    // so now we need to look into the instantiated parent context to
1578    // find the instantiation of the declaration D.
1579    NamedDecl *Result = 0;
1580    if (D->getDeclName()) {
1581      DeclContext::lookup_result Found = ParentDC->lookup(D->getDeclName());
1582      Result = findInstantiationOf(Context, D, Found.first, Found.second);
1583    } else {
1584      // Since we don't have a name for the entity we're looking for,
1585      // our only option is to walk through all of the declarations to
1586      // find that name. This will occur in a few cases:
1587      //
1588      //   - anonymous struct/union within a template
1589      //   - unnamed class/struct/union/enum within a template
1590      //
1591      // FIXME: Find a better way to find these instantiations!
1592      Result = findInstantiationOf(Context, D,
1593                                   ParentDC->decls_begin(),
1594                                   ParentDC->decls_end());
1595    }
1596
1597    assert(Result && "Unable to find instantiation of declaration!");
1598    D = Result;
1599  }
1600
1601  return D;
1602}
1603
1604/// \brief Performs template instantiation for all implicit template
1605/// instantiations we have seen until this point.
1606void Sema::PerformPendingImplicitInstantiations() {
1607  while (!PendingImplicitInstantiations.empty()) {
1608    PendingImplicitInstantiation Inst = PendingImplicitInstantiations.front();
1609    PendingImplicitInstantiations.pop_front();
1610
1611    // Instantiate function definitions
1612    if (FunctionDecl *Function = dyn_cast<FunctionDecl>(Inst.first)) {
1613      PrettyStackTraceActionsDecl CrashInfo(DeclPtrTy::make(Function),
1614                                            Function->getLocation(), *this,
1615                                            Context.getSourceManager(),
1616                                           "instantiating function definition");
1617
1618      if (!Function->getBody())
1619        InstantiateFunctionDefinition(/*FIXME:*/Inst.second, Function, true);
1620      continue;
1621    }
1622
1623    // Instantiate static data member definitions.
1624    VarDecl *Var = cast<VarDecl>(Inst.first);
1625    assert(Var->isStaticDataMember() && "Not a static data member?");
1626
1627    PrettyStackTraceActionsDecl CrashInfo(DeclPtrTy::make(Var),
1628                                          Var->getLocation(), *this,
1629                                          Context.getSourceManager(),
1630                                          "instantiating static data member "
1631                                          "definition");
1632
1633    InstantiateStaticDataMemberDefinition(/*FIXME:*/Inst.second, Var, true);
1634  }
1635}
1636