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