SemaTemplateInstantiate.cpp revision 54dabfca850ca9e60e9ffb60003529f868d4d127 
1//===------- SemaTemplateInstantiate.cpp - C++ Template 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.
10//
11//===----------------------------------------------------------------------===/
12
13#include "Sema.h"
14#include "clang/AST/ASTContext.h"
15#include "clang/AST/Expr.h"
16#include "clang/AST/DeclTemplate.h"
17#include "clang/Parse/DeclSpec.h"
18#include "clang/Basic/LangOptions.h"
19#include "llvm/Support/Compiler.h"
20
21using namespace clang;
22
23//===----------------------------------------------------------------------===/
24// Template Instantiation Support
25//===----------------------------------------------------------------------===/
26
27/// \brief Retrieve the template argument list that should be used to
28/// instantiate the given declaration.
29const TemplateArgumentList &
30Sema::getTemplateInstantiationArgs(NamedDecl *D) {
31  if (ClassTemplateSpecializationDecl *Spec
32        = dyn_cast<ClassTemplateSpecializationDecl>(D))
33    return Spec->getTemplateArgs();
34
35  DeclContext *EnclosingTemplateCtx = D->getDeclContext();
36  while (!isa<ClassTemplateSpecializationDecl>(EnclosingTemplateCtx)) {
37    assert(!EnclosingTemplateCtx->isFileContext() &&
38           "Tried to get the instantiation arguments of a non-template");
39    EnclosingTemplateCtx = EnclosingTemplateCtx->getParent();
40  }
41
42  ClassTemplateSpecializationDecl *EnclosingTemplate
43    = cast<ClassTemplateSpecializationDecl>(EnclosingTemplateCtx);
44  return EnclosingTemplate->getTemplateArgs();
45}
46
47Sema::InstantiatingTemplate::
48InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
49                      CXXRecordDecl *Entity,
50                      SourceRange InstantiationRange)
51  :  SemaRef(SemaRef) {
52
53  Invalid = CheckInstantiationDepth(PointOfInstantiation,
54                                    InstantiationRange);
55  if (!Invalid) {
56    ActiveTemplateInstantiation Inst;
57    Inst.Kind = ActiveTemplateInstantiation::TemplateInstantiation;
58    Inst.PointOfInstantiation = PointOfInstantiation;
59    Inst.Entity = reinterpret_cast<uintptr_t>(Entity);
60    Inst.TemplateArgs = 0;
61    Inst.NumTemplateArgs = 0;
62    Inst.InstantiationRange = InstantiationRange;
63    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
64    Invalid = false;
65  }
66}
67
68Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
69                                         SourceLocation PointOfInstantiation,
70                                         TemplateDecl *Template,
71                                         const TemplateArgument *TemplateArgs,
72                                         unsigned NumTemplateArgs,
73                                         SourceRange InstantiationRange)
74  : SemaRef(SemaRef) {
75
76  Invalid = CheckInstantiationDepth(PointOfInstantiation,
77                                    InstantiationRange);
78  if (!Invalid) {
79    ActiveTemplateInstantiation Inst;
80    Inst.Kind
81      = ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation;
82    Inst.PointOfInstantiation = PointOfInstantiation;
83    Inst.Entity = reinterpret_cast<uintptr_t>(Template);
84    Inst.TemplateArgs = TemplateArgs;
85    Inst.NumTemplateArgs = NumTemplateArgs;
86    Inst.InstantiationRange = InstantiationRange;
87    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
88    Invalid = false;
89  }
90}
91
92Sema::InstantiatingTemplate::~InstantiatingTemplate() {
93  if (!Invalid)
94    SemaRef.ActiveTemplateInstantiations.pop_back();
95}
96
97bool Sema::InstantiatingTemplate::CheckInstantiationDepth(
98                                        SourceLocation PointOfInstantiation,
99                                           SourceRange InstantiationRange) {
100  if (SemaRef.ActiveTemplateInstantiations.size()
101       <= SemaRef.getLangOptions().InstantiationDepth)
102    return false;
103
104  SemaRef.Diag(PointOfInstantiation,
105               diag::err_template_recursion_depth_exceeded)
106    << SemaRef.getLangOptions().InstantiationDepth
107    << InstantiationRange;
108  SemaRef.Diag(PointOfInstantiation, diag::note_template_recursion_depth)
109    << SemaRef.getLangOptions().InstantiationDepth;
110  return true;
111}
112
113/// \brief Prints the current instantiation stack through a series of
114/// notes.
115void Sema::PrintInstantiationStack() {
116  for (llvm::SmallVector<ActiveTemplateInstantiation, 16>::reverse_iterator
117         Active = ActiveTemplateInstantiations.rbegin(),
118         ActiveEnd = ActiveTemplateInstantiations.rend();
119       Active != ActiveEnd;
120       ++Active) {
121    switch (Active->Kind) {
122    case ActiveTemplateInstantiation::TemplateInstantiation: {
123      unsigned DiagID = diag::note_template_member_class_here;
124      CXXRecordDecl *Record = (CXXRecordDecl *)Active->Entity;
125      if (isa<ClassTemplateSpecializationDecl>(Record))
126        DiagID = diag::note_template_class_instantiation_here;
127      Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
128                   DiagID)
129        << Context.getTypeDeclType(Record)
130        << Active->InstantiationRange;
131      break;
132    }
133
134    case ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation: {
135      TemplateDecl *Template = cast<TemplateDecl>((Decl *)Active->Entity);
136      std::string TemplateArgsStr
137        = TemplateSpecializationType::PrintTemplateArgumentList(
138                                                      Active->TemplateArgs,
139                                                      Active->NumTemplateArgs);
140      Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
141                   diag::note_default_arg_instantiation_here)
142        << (Template->getNameAsString() + TemplateArgsStr)
143        << Active->InstantiationRange;
144      break;
145    }
146    }
147  }
148}
149
150//===----------------------------------------------------------------------===/
151// Template Instantiation for Types
152//===----------------------------------------------------------------------===/
153namespace {
154  class VISIBILITY_HIDDEN TemplateTypeInstantiator {
155    Sema &SemaRef;
156    const TemplateArgumentList &TemplateArgs;
157    SourceLocation Loc;
158    DeclarationName Entity;
159
160  public:
161    TemplateTypeInstantiator(Sema &SemaRef,
162                             const TemplateArgumentList &TemplateArgs,
163                             SourceLocation Loc,
164                             DeclarationName Entity)
165      : SemaRef(SemaRef), TemplateArgs(TemplateArgs),
166        Loc(Loc), Entity(Entity) { }
167
168    QualType operator()(QualType T) const { return Instantiate(T); }
169
170    QualType Instantiate(QualType T) const;
171
172    // Declare instantiate functions for each type.
173#define TYPE(Class, Base)                                       \
174    QualType Instantiate##Class##Type(const Class##Type *T,     \
175                                      unsigned Quals) const;
176#define ABSTRACT_TYPE(Class, Base)
177#include "clang/AST/TypeNodes.def"
178  };
179}
180
181QualType
182TemplateTypeInstantiator::InstantiateExtQualType(const ExtQualType *T,
183                                                 unsigned Quals) const {
184  // FIXME: Implement this
185  assert(false && "Cannot instantiate ExtQualType yet");
186  return QualType();
187}
188
189QualType
190TemplateTypeInstantiator::InstantiateBuiltinType(const BuiltinType *T,
191                                                 unsigned Quals) const {
192  assert(false && "Builtin types are not dependent and cannot be instantiated");
193  return QualType(T, Quals);
194}
195
196QualType
197TemplateTypeInstantiator::
198InstantiateFixedWidthIntType(const FixedWidthIntType *T, unsigned Quals) const {
199  // FIXME: Implement this
200  assert(false && "Cannot instantiate FixedWidthIntType yet");
201  return QualType();
202}
203
204QualType
205TemplateTypeInstantiator::InstantiateComplexType(const ComplexType *T,
206                                                 unsigned Quals) const {
207  // FIXME: Implement this
208  assert(false && "Cannot instantiate ComplexType yet");
209  return QualType();
210}
211
212QualType
213TemplateTypeInstantiator::InstantiatePointerType(const PointerType *T,
214                                                 unsigned Quals) const {
215  QualType PointeeType = Instantiate(T->getPointeeType());
216  if (PointeeType.isNull())
217    return QualType();
218
219  return SemaRef.BuildPointerType(PointeeType, Quals, Loc, Entity);
220}
221
222QualType
223TemplateTypeInstantiator::InstantiateBlockPointerType(const BlockPointerType *T,
224                                                      unsigned Quals) const {
225  // FIXME: Implement this
226  assert(false && "Cannot instantiate BlockPointerType yet");
227  return QualType();
228}
229
230QualType
231TemplateTypeInstantiator::InstantiateLValueReferenceType(
232    const LValueReferenceType *T, unsigned Quals) const {
233  QualType ReferentType = Instantiate(T->getPointeeType());
234  if (ReferentType.isNull())
235    return QualType();
236
237  return SemaRef.BuildReferenceType(ReferentType, true, Quals, Loc, Entity);
238}
239
240QualType
241TemplateTypeInstantiator::InstantiateRValueReferenceType(
242    const RValueReferenceType *T, unsigned Quals) const {
243  QualType ReferentType = Instantiate(T->getPointeeType());
244  if (ReferentType.isNull())
245    return QualType();
246
247  return SemaRef.BuildReferenceType(ReferentType, false, Quals, Loc, Entity);
248}
249
250QualType
251TemplateTypeInstantiator::
252InstantiateMemberPointerType(const MemberPointerType *T,
253                             unsigned Quals) const {
254  // FIXME: Implement this
255  assert(false && "Cannot instantiate MemberPointerType yet");
256  return QualType();
257}
258
259QualType
260TemplateTypeInstantiator::
261InstantiateConstantArrayType(const ConstantArrayType *T,
262                             unsigned Quals) const {
263  QualType ElementType = Instantiate(T->getElementType());
264  if (ElementType.isNull())
265    return ElementType;
266
267  // Build a temporary integer literal to specify the size for
268  // BuildArrayType. Since we have already checked the size as part of
269  // creating the dependent array type in the first place, we know
270  // there aren't any errors. However, we do need to determine what
271  // C++ type to give the size expression.
272  llvm::APInt Size = T->getSize();
273  QualType Types[] = {
274    SemaRef.Context.UnsignedCharTy, SemaRef.Context.UnsignedShortTy,
275    SemaRef.Context.UnsignedIntTy, SemaRef.Context.UnsignedLongTy,
276    SemaRef.Context.UnsignedLongLongTy, SemaRef.Context.UnsignedInt128Ty
277  };
278  const unsigned NumTypes = sizeof(Types) / sizeof(QualType);
279  QualType SizeType;
280  for (unsigned I = 0; I != NumTypes; ++I)
281    if (Size.getBitWidth() == SemaRef.Context.getIntWidth(Types[I])) {
282      SizeType = Types[I];
283      break;
284    }
285
286  if (SizeType.isNull())
287    SizeType = SemaRef.Context.getFixedWidthIntType(Size.getBitWidth(), false);
288
289  IntegerLiteral ArraySize(Size, SizeType, Loc);
290  return SemaRef.BuildArrayType(ElementType, T->getSizeModifier(),
291                                &ArraySize, T->getIndexTypeQualifier(),
292                                Loc, Entity);
293}
294
295QualType
296TemplateTypeInstantiator::
297InstantiateIncompleteArrayType(const IncompleteArrayType *T,
298                               unsigned Quals) const {
299  QualType ElementType = Instantiate(T->getElementType());
300  if (ElementType.isNull())
301    return ElementType;
302
303  return SemaRef.BuildArrayType(ElementType, T->getSizeModifier(),
304                                0, T->getIndexTypeQualifier(),
305                                Loc, Entity);
306}
307
308QualType
309TemplateTypeInstantiator::
310InstantiateVariableArrayType(const VariableArrayType *T,
311                             unsigned Quals) const {
312  // FIXME: Implement this
313  assert(false && "Cannot instantiate VariableArrayType yet");
314  return QualType();
315}
316
317QualType
318TemplateTypeInstantiator::
319InstantiateDependentSizedArrayType(const DependentSizedArrayType *T,
320                                   unsigned Quals) const {
321  Expr *ArraySize = T->getSizeExpr();
322  assert(ArraySize->isValueDependent() &&
323         "dependent sized array types must have value dependent size expr");
324
325  // Instantiate the element type if needed
326  QualType ElementType = T->getElementType();
327  if (ElementType->isDependentType()) {
328    ElementType = Instantiate(ElementType);
329    if (ElementType.isNull())
330      return QualType();
331  }
332
333  // Instantiate the size expression
334  Sema::OwningExprResult InstantiatedArraySize =
335    SemaRef.InstantiateExpr(ArraySize, TemplateArgs);
336  if (InstantiatedArraySize.isInvalid())
337    return QualType();
338
339  return SemaRef.BuildArrayType(ElementType, T->getSizeModifier(),
340                                InstantiatedArraySize.takeAs<Expr>(),
341                                T->getIndexTypeQualifier(), Loc, Entity);
342}
343
344QualType
345TemplateTypeInstantiator::InstantiateVectorType(const VectorType *T,
346                                             unsigned Quals) const {
347  // FIXME: Implement this
348  assert(false && "Cannot instantiate VectorType yet");
349  return QualType();
350}
351
352QualType
353TemplateTypeInstantiator::InstantiateExtVectorType(const ExtVectorType *T,
354                                                   unsigned Quals) const {
355  // FIXME: Implement this
356  assert(false && "Cannot instantiate ExtVectorType yet");
357  return QualType();
358}
359
360QualType
361TemplateTypeInstantiator::
362InstantiateFunctionProtoType(const FunctionProtoType *T,
363                             unsigned Quals) const {
364  QualType ResultType = Instantiate(T->getResultType());
365  if (ResultType.isNull())
366    return ResultType;
367
368  llvm::SmallVector<QualType, 16> ParamTypes;
369  for (FunctionProtoType::arg_type_iterator Param = T->arg_type_begin(),
370                                         ParamEnd = T->arg_type_end();
371       Param != ParamEnd; ++Param) {
372    QualType P = Instantiate(*Param);
373    if (P.isNull())
374      return P;
375
376    ParamTypes.push_back(P);
377  }
378
379  return SemaRef.BuildFunctionType(ResultType, &ParamTypes[0],
380                                   ParamTypes.size(),
381                                   T->isVariadic(), T->getTypeQuals(),
382                                   Loc, Entity);
383}
384
385QualType
386TemplateTypeInstantiator::
387InstantiateFunctionNoProtoType(const FunctionNoProtoType *T,
388                               unsigned Quals) const {
389  assert(false && "Functions without prototypes cannot be dependent.");
390  return QualType();
391}
392
393QualType
394TemplateTypeInstantiator::InstantiateTypedefType(const TypedefType *T,
395                                                 unsigned Quals) const {
396  // FIXME: Implement this
397  assert(false && "Cannot instantiate TypedefType yet");
398  return QualType();
399}
400
401QualType
402TemplateTypeInstantiator::InstantiateTypeOfExprType(const TypeOfExprType *T,
403                                                    unsigned Quals) const {
404  // FIXME: Implement this
405  assert(false && "Cannot instantiate TypeOfExprType yet");
406  return QualType();
407}
408
409QualType
410TemplateTypeInstantiator::InstantiateTypeOfType(const TypeOfType *T,
411                                                unsigned Quals) const {
412  // FIXME: Implement this
413  assert(false && "Cannot instantiate TypeOfType yet");
414  return QualType();
415}
416
417QualType
418TemplateTypeInstantiator::InstantiateRecordType(const RecordType *T,
419                                                unsigned Quals) const {
420  // FIXME: Implement this
421  assert(false && "Cannot instantiate RecordType yet");
422  return QualType();
423}
424
425QualType
426TemplateTypeInstantiator::InstantiateEnumType(const EnumType *T,
427                                              unsigned Quals) const {
428  // FIXME: Implement this
429  assert(false && "Cannot instantiate EnumType yet");
430  return QualType();
431}
432
433QualType
434TemplateTypeInstantiator::
435InstantiateTemplateTypeParmType(const TemplateTypeParmType *T,
436                                unsigned Quals) const {
437  if (T->getDepth() == 0) {
438    // Replace the template type parameter with its corresponding
439    // template argument.
440    assert(TemplateArgs[T->getIndex()].getKind() == TemplateArgument::Type &&
441           "Template argument kind mismatch");
442    QualType Result = TemplateArgs[T->getIndex()].getAsType();
443    if (Result.isNull() || !Quals)
444      return Result;
445
446    // C++ [dcl.ref]p1:
447    //   [...] Cv-qualified references are ill-formed except when
448    //   the cv-qualifiers are introduced through the use of a
449    //   typedef (7.1.3) or of a template type argument (14.3), in
450    //   which case the cv-qualifiers are ignored.
451    if (Quals && Result->isReferenceType())
452      Quals = 0;
453
454    return QualType(Result.getTypePtr(), Quals | Result.getCVRQualifiers());
455  }
456
457  // The template type parameter comes from an inner template (e.g.,
458  // the template parameter list of a member template inside the
459  // template we are instantiating). Create a new template type
460  // parameter with the template "level" reduced by one.
461  return SemaRef.Context.getTemplateTypeParmType(T->getDepth() - 1,
462                                                 T->getIndex(),
463                                                 T->getName())
464    .getQualifiedType(Quals);
465}
466
467QualType
468TemplateTypeInstantiator::
469InstantiateTemplateSpecializationType(
470                                  const TemplateSpecializationType *T,
471                                  unsigned Quals) const {
472  llvm::SmallVector<TemplateArgument, 16> InstantiatedTemplateArgs;
473  InstantiatedTemplateArgs.reserve(T->getNumArgs());
474  for (TemplateSpecializationType::iterator Arg = T->begin(), ArgEnd = T->end();
475       Arg != ArgEnd; ++Arg) {
476    switch (Arg->getKind()) {
477    case TemplateArgument::Type: {
478      QualType T = SemaRef.InstantiateType(Arg->getAsType(),
479                                           TemplateArgs,
480                                           Arg->getLocation(),
481                                           DeclarationName());
482      if (T.isNull())
483        return QualType();
484
485      InstantiatedTemplateArgs.push_back(
486                                TemplateArgument(Arg->getLocation(), T));
487      break;
488    }
489
490    case TemplateArgument::Declaration:
491    case TemplateArgument::Integral:
492      InstantiatedTemplateArgs.push_back(*Arg);
493      break;
494
495    case TemplateArgument::Expression:
496      Sema::OwningExprResult E
497        = SemaRef.InstantiateExpr(Arg->getAsExpr(), TemplateArgs);
498      if (E.isInvalid())
499        return QualType();
500      InstantiatedTemplateArgs.push_back(E.takeAs<Expr>());
501      break;
502    }
503  }
504
505  // FIXME: We're missing the locations of the template name, '<', and
506  // '>'.
507
508  TemplateName Name = SemaRef.InstantiateTemplateName(T->getTemplateName(),
509                                                      Loc,
510                                                      TemplateArgs);
511
512  return SemaRef.CheckTemplateIdType(Name, Loc, SourceLocation(),
513                                     &InstantiatedTemplateArgs[0],
514                                     InstantiatedTemplateArgs.size(),
515                                     SourceLocation());
516}
517
518QualType
519TemplateTypeInstantiator::
520InstantiateQualifiedNameType(const QualifiedNameType *T,
521                             unsigned Quals) const {
522  // When we instantiated a qualified name type, there's no point in
523  // keeping the qualification around in the instantiated result. So,
524  // just instantiate the named type.
525  return (*this)(T->getNamedType());
526}
527
528QualType
529TemplateTypeInstantiator::
530InstantiateTypenameType(const TypenameType *T, unsigned Quals) const {
531  if (const TemplateSpecializationType *TemplateId = T->getTemplateId()) {
532    // When the typename type refers to a template-id, the template-id
533    // is dependent and has enough information to instantiate the
534    // result of the typename type. Since we don't care about keeping
535    // the spelling of the typename type in template instantiations,
536    // we just instantiate the template-id.
537    return InstantiateTemplateSpecializationType(TemplateId, Quals);
538  }
539
540  NestedNameSpecifier *NNS
541    = SemaRef.InstantiateNestedNameSpecifier(T->getQualifier(),
542                                             SourceRange(Loc),
543                                             TemplateArgs);
544  if (!NNS)
545    return QualType();
546
547  return SemaRef.CheckTypenameType(NNS, *T->getIdentifier(), SourceRange(Loc));
548}
549
550QualType
551TemplateTypeInstantiator::
552InstantiateObjCInterfaceType(const ObjCInterfaceType *T,
553                             unsigned Quals) const {
554  assert(false && "Objective-C types cannot be dependent");
555  return QualType();
556}
557
558QualType
559TemplateTypeInstantiator::
560InstantiateObjCQualifiedInterfaceType(const ObjCQualifiedInterfaceType *T,
561                                      unsigned Quals) const {
562  assert(false && "Objective-C types cannot be dependent");
563  return QualType();
564}
565
566QualType
567TemplateTypeInstantiator::
568InstantiateObjCQualifiedIdType(const ObjCQualifiedIdType *T,
569                               unsigned Quals) const {
570  assert(false && "Objective-C types cannot be dependent");
571  return QualType();
572}
573
574/// \brief The actual implementation of Sema::InstantiateType().
575QualType TemplateTypeInstantiator::Instantiate(QualType T) const {
576  // If T is not a dependent type, there is nothing to do.
577  if (!T->isDependentType())
578    return T;
579
580  switch (T->getTypeClass()) {
581#define TYPE(Class, Base)                                               \
582  case Type::Class:                                                     \
583    return Instantiate##Class##Type(cast<Class##Type>(T.getTypePtr()),  \
584                                    T.getCVRQualifiers());
585#define ABSTRACT_TYPE(Class, Base)
586#include "clang/AST/TypeNodes.def"
587  }
588
589  assert(false && "Not all types have been decoded for instantiation");
590  return QualType();
591}
592
593/// \brief Instantiate the type T with a given set of template arguments.
594///
595/// This routine substitutes the given template arguments into the
596/// type T and produces the instantiated type.
597///
598/// \param T the type into which the template arguments will be
599/// substituted. If this type is not dependent, it will be returned
600/// immediately.
601///
602/// \param TemplateArgs the template arguments that will be
603/// substituted for the top-level template parameters within T.
604///
605/// \param Loc the location in the source code where this substitution
606/// is being performed. It will typically be the location of the
607/// declarator (if we're instantiating the type of some declaration)
608/// or the location of the type in the source code (if, e.g., we're
609/// instantiating the type of a cast expression).
610///
611/// \param Entity the name of the entity associated with a declaration
612/// being instantiated (if any). May be empty to indicate that there
613/// is no such entity (if, e.g., this is a type that occurs as part of
614/// a cast expression) or that the entity has no name (e.g., an
615/// unnamed function parameter).
616///
617/// \returns If the instantiation succeeds, the instantiated
618/// type. Otherwise, produces diagnostics and returns a NULL type.
619QualType Sema::InstantiateType(QualType T,
620                               const TemplateArgumentList &TemplateArgs,
621                               SourceLocation Loc, DeclarationName Entity) {
622  assert(!ActiveTemplateInstantiations.empty() &&
623         "Cannot perform an instantiation without some context on the "
624         "instantiation stack");
625
626  // If T is not a dependent type, there is nothing to do.
627  if (!T->isDependentType())
628    return T;
629
630  TemplateTypeInstantiator Instantiator(*this, TemplateArgs, Loc, Entity);
631  return Instantiator(T);
632}
633
634/// \brief Instantiate the base class specifiers of the given class
635/// template specialization.
636///
637/// Produces a diagnostic and returns true on error, returns false and
638/// attaches the instantiated base classes to the class template
639/// specialization if successful.
640bool
641Sema::InstantiateBaseSpecifiers(CXXRecordDecl *Instantiation,
642                                CXXRecordDecl *Pattern,
643                                const TemplateArgumentList &TemplateArgs) {
644  bool Invalid = false;
645  llvm::SmallVector<CXXBaseSpecifier*, 8> InstantiatedBases;
646  for (ClassTemplateSpecializationDecl::base_class_iterator
647         Base = Pattern->bases_begin(), BaseEnd = Pattern->bases_end();
648       Base != BaseEnd; ++Base) {
649    if (!Base->getType()->isDependentType()) {
650      // FIXME: Allocate via ASTContext
651      InstantiatedBases.push_back(new CXXBaseSpecifier(*Base));
652      continue;
653    }
654
655    QualType BaseType = InstantiateType(Base->getType(),
656                                        TemplateArgs,
657                                        Base->getSourceRange().getBegin(),
658                                        DeclarationName());
659    if (BaseType.isNull()) {
660      Invalid = true;
661      continue;
662    }
663
664    if (CXXBaseSpecifier *InstantiatedBase
665          = CheckBaseSpecifier(Instantiation,
666                               Base->getSourceRange(),
667                               Base->isVirtual(),
668                               Base->getAccessSpecifierAsWritten(),
669                               BaseType,
670                               /*FIXME: Not totally accurate */
671                               Base->getSourceRange().getBegin()))
672      InstantiatedBases.push_back(InstantiatedBase);
673    else
674      Invalid = true;
675  }
676
677  if (!Invalid &&
678      AttachBaseSpecifiers(Instantiation, &InstantiatedBases[0],
679                           InstantiatedBases.size()))
680    Invalid = true;
681
682  return Invalid;
683}
684
685/// \brief Instantiate the definition of a class from a given pattern.
686///
687/// \param PointOfInstantiation The point of instantiation within the
688/// source code.
689///
690/// \param Instantiation is the declaration whose definition is being
691/// instantiated. This will be either a class template specialization
692/// or a member class of a class template specialization.
693///
694/// \param Pattern is the pattern from which the instantiation
695/// occurs. This will be either the declaration of a class template or
696/// the declaration of a member class of a class template.
697///
698/// \param TemplateArgs The template arguments to be substituted into
699/// the pattern.
700///
701/// \returns true if an error occurred, false otherwise.
702bool
703Sema::InstantiateClass(SourceLocation PointOfInstantiation,
704                       CXXRecordDecl *Instantiation, CXXRecordDecl *Pattern,
705                       const TemplateArgumentList &TemplateArgs,
706                       bool ExplicitInstantiation) {
707  bool Invalid = false;
708
709  CXXRecordDecl *PatternDef
710    = cast_or_null<CXXRecordDecl>(Pattern->getDefinition(Context));
711  if (!PatternDef) {
712    if (Pattern == Instantiation->getInstantiatedFromMemberClass()) {
713      Diag(PointOfInstantiation,
714           diag::err_implicit_instantiate_member_undefined)
715        << Context.getTypeDeclType(Instantiation);
716      Diag(Pattern->getLocation(), diag::note_member_of_template_here);
717    } else {
718      Diag(PointOfInstantiation, diag::err_template_instantiate_undefined)
719        << ExplicitInstantiation
720        << Context.getTypeDeclType(Instantiation);
721      Diag(Pattern->getLocation(), diag::note_template_decl_here);
722    }
723    return true;
724  }
725  Pattern = PatternDef;
726
727  InstantiatingTemplate Inst(*this, PointOfInstantiation, Instantiation);
728  if (Inst)
729    return true;
730
731  // Enter the scope of this instantiation. We don't use
732  // PushDeclContext because we don't have a scope.
733  DeclContext *PreviousContext = CurContext;
734  CurContext = Instantiation;
735
736  // Start the definition of this instantiation.
737  Instantiation->startDefinition();
738
739  // Instantiate the base class specifiers.
740  if (InstantiateBaseSpecifiers(Instantiation, Pattern, TemplateArgs))
741    Invalid = true;
742
743  llvm::SmallVector<DeclPtrTy, 32> Fields;
744  for (RecordDecl::decl_iterator Member = Pattern->decls_begin(Context),
745         MemberEnd = Pattern->decls_end(Context);
746       Member != MemberEnd; ++Member) {
747    Decl *NewMember = InstantiateDecl(*Member, Instantiation, TemplateArgs);
748    if (NewMember) {
749      if (NewMember->isInvalidDecl())
750        Invalid = true;
751      else if (FieldDecl *Field = dyn_cast<FieldDecl>(NewMember))
752        Fields.push_back(DeclPtrTy::make(Field));
753    } else {
754      // FIXME: Eventually, a NULL return will mean that one of the
755      // instantiations was a semantic disaster, and we'll want to set
756      // Invalid = true. For now, we expect to skip some members that
757      // we can't yet handle.
758    }
759  }
760
761  // Finish checking fields.
762  ActOnFields(0, Instantiation->getLocation(), DeclPtrTy::make(Instantiation),
763              &Fields[0], Fields.size(), SourceLocation(), SourceLocation(),
764              0);
765
766  // Add any implicitly-declared members that we might need.
767  AddImplicitlyDeclaredMembersToClass(Instantiation);
768
769  // Exit the scope of this instantiation.
770  CurContext = PreviousContext;
771
772  // If this is an explicit instantiation, instantiate our members, too.
773  if (!Invalid && ExplicitInstantiation)
774    InstantiateClassMembers(PointOfInstantiation, Instantiation, TemplateArgs);
775
776  return Invalid;
777}
778
779bool
780Sema::InstantiateClassTemplateSpecialization(
781                           ClassTemplateSpecializationDecl *ClassTemplateSpec,
782                           bool ExplicitInstantiation) {
783  // Perform the actual instantiation on the canonical declaration.
784  ClassTemplateSpec = cast<ClassTemplateSpecializationDecl>(
785                               Context.getCanonicalDecl(ClassTemplateSpec));
786
787  // We can only instantiate something that hasn't already been
788  // instantiated or specialized. Fail without any diagnostics: our
789  // caller will provide an error message.
790  if (ClassTemplateSpec->getSpecializationKind() != TSK_Undeclared)
791    return true;
792
793  // FIXME: Push this class template instantiation onto the
794  // instantiation stack, checking for recursion that exceeds a
795  // certain depth.
796
797  // FIXME: Perform class template partial specialization to select
798  // the best template.
799  ClassTemplateDecl *Template = ClassTemplateSpec->getSpecializedTemplate();
800
801  CXXRecordDecl *Pattern = Template->getTemplatedDecl();
802
803  // Note that this is an instantiation.
804  ClassTemplateSpec->setSpecializationKind(
805                        ExplicitInstantiation? TSK_ExplicitInstantiation
806                                             : TSK_ImplicitInstantiation);
807
808  return InstantiateClass(ClassTemplateSpec->getLocation(),
809                          ClassTemplateSpec, Pattern,
810                          ClassTemplateSpec->getTemplateArgs(),
811                          ExplicitInstantiation);
812}
813
814/// \brief Instantiate the definitions of all of the member of the
815/// given class, which is an instantiation of a class template or a
816/// member class of a template.
817void
818Sema::InstantiateClassMembers(SourceLocation PointOfInstantiation,
819                              CXXRecordDecl *Instantiation,
820                              const TemplateArgumentList &TemplateArgs) {
821  for (DeclContext::decl_iterator D = Instantiation->decls_begin(Context),
822                               DEnd = Instantiation->decls_end(Context);
823       D != DEnd; ++D) {
824    if (FunctionDecl *Function = dyn_cast<FunctionDecl>(*D)) {
825      if (!Function->getBody(Context))
826        InstantiateFunctionDefinition(Function);
827    } else if (VarDecl *Var = dyn_cast<VarDecl>(*D)) {
828      const VarDecl *Def = 0;
829      if (!Var->getDefinition(Def))
830        InstantiateVariableDefinition(Var);
831    } else if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(*D)) {
832      if (!Record->isInjectedClassName() && !Record->getDefinition(Context)) {
833        assert(Record->getInstantiatedFromMemberClass() &&
834               "Missing instantiated-from-template information");
835        InstantiateClass(Record->getLocation(), Record,
836                         Record->getInstantiatedFromMemberClass(),
837                         TemplateArgs, true);
838      }
839    }
840  }
841}
842
843/// \brief Instantiate the definitions of all of the members of the
844/// given class template specialization, which was named as part of an
845/// explicit instantiation.
846void Sema::InstantiateClassTemplateSpecializationMembers(
847                                           SourceLocation PointOfInstantiation,
848                          ClassTemplateSpecializationDecl *ClassTemplateSpec) {
849  // C++0x [temp.explicit]p7:
850  //   An explicit instantiation that names a class template
851  //   specialization is an explicit instantion of the same kind
852  //   (declaration or definition) of each of its members (not
853  //   including members inherited from base classes) that has not
854  //   been previously explicitly specialized in the translation unit
855  //   containing the explicit instantiation, except as described
856  //   below.
857  InstantiateClassMembers(PointOfInstantiation, ClassTemplateSpec,
858                          ClassTemplateSpec->getTemplateArgs());
859}
860
861/// \brief Instantiate a nested-name-specifier.
862NestedNameSpecifier *
863Sema::InstantiateNestedNameSpecifier(NestedNameSpecifier *NNS,
864                                     SourceRange Range,
865                                     const TemplateArgumentList &TemplateArgs) {
866  // Instantiate the prefix of this nested name specifier.
867  NestedNameSpecifier *Prefix = NNS->getPrefix();
868  if (Prefix) {
869    Prefix = InstantiateNestedNameSpecifier(Prefix, Range, TemplateArgs);
870    if (!Prefix)
871      return 0;
872  }
873
874  switch (NNS->getKind()) {
875  case NestedNameSpecifier::Identifier: {
876    assert(Prefix &&
877           "Can't have an identifier nested-name-specifier with no prefix");
878    CXXScopeSpec SS;
879    // FIXME: The source location information is all wrong.
880    SS.setRange(Range);
881    SS.setScopeRep(Prefix);
882    return static_cast<NestedNameSpecifier *>(
883                                 ActOnCXXNestedNameSpecifier(0, SS,
884                                                             Range.getEnd(),
885                                                             Range.getEnd(),
886                                                    *NNS->getAsIdentifier()));
887    break;
888  }
889
890  case NestedNameSpecifier::Namespace:
891  case NestedNameSpecifier::Global:
892    return NNS;
893
894  case NestedNameSpecifier::TypeSpecWithTemplate:
895  case NestedNameSpecifier::TypeSpec: {
896    QualType T = QualType(NNS->getAsType(), 0);
897    if (!T->isDependentType())
898      return NNS;
899
900    T = InstantiateType(T, TemplateArgs, Range.getBegin(), DeclarationName());
901    if (T.isNull())
902      return 0;
903
904    if (T->isRecordType() ||
905        (getLangOptions().CPlusPlus0x && T->isEnumeralType())) {
906      assert(T.getCVRQualifiers() == 0 && "Can't get cv-qualifiers here");
907      return NestedNameSpecifier::Create(Context, Prefix,
908                 NNS->getKind() == NestedNameSpecifier::TypeSpecWithTemplate,
909                                         T.getTypePtr());
910    }
911
912    Diag(Range.getBegin(), diag::err_nested_name_spec_non_tag) << T;
913    return 0;
914  }
915  }
916
917  // Required to silence a GCC warning
918  return 0;
919}
920
921TemplateName
922Sema::InstantiateTemplateName(TemplateName Name, SourceLocation Loc,
923                              const TemplateArgumentList &TemplateArgs) {
924  if (TemplateTemplateParmDecl *TTP
925        = dyn_cast_or_null<TemplateTemplateParmDecl>(
926                                                 Name.getAsTemplateDecl())) {
927    assert(TTP->getDepth() == 0 &&
928           "Cannot reduce depth of a template template parameter");
929    assert(TemplateArgs[TTP->getPosition()].getAsDecl() &&
930           "Wrong kind of template template argument");
931    ClassTemplateDecl *ClassTemplate
932      = dyn_cast<ClassTemplateDecl>(
933                               TemplateArgs[TTP->getPosition()].getAsDecl());
934    assert(ClassTemplate && "Expected a class template");
935    if (QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName()) {
936      NestedNameSpecifier *NNS
937        = InstantiateNestedNameSpecifier(QTN->getQualifier(),
938                                         /*FIXME=*/SourceRange(Loc),
939                                         TemplateArgs);
940      if (NNS)
941        return Context.getQualifiedTemplateName(NNS,
942                                                QTN->hasTemplateKeyword(),
943                                                ClassTemplate);
944    }
945
946    return TemplateName(ClassTemplate);
947  } else if (DependentTemplateName *DTN = Name.getAsDependentTemplateName()) {
948    NestedNameSpecifier *NNS
949      = InstantiateNestedNameSpecifier(DTN->getQualifier(),
950                                       /*FIXME=*/SourceRange(Loc),
951                                       TemplateArgs);
952
953    if (!NNS) // FIXME: Not the best recovery strategy.
954      return Name;
955
956    if (NNS->isDependent())
957      return Context.getDependentTemplateName(NNS, DTN->getName());
958
959    // Somewhat redundant with ActOnDependentTemplateName.
960    CXXScopeSpec SS;
961    SS.setRange(SourceRange(Loc));
962    SS.setScopeRep(NNS);
963    TemplateTy Template;
964    TemplateNameKind TNK = isTemplateName(*DTN->getName(), 0, Template, &SS);
965    if (TNK == TNK_Non_template) {
966      Diag(Loc, diag::err_template_kw_refers_to_non_template)
967        << DTN->getName();
968      return Name;
969    } else if (TNK == TNK_Function_template) {
970      Diag(Loc, diag::err_template_kw_refers_to_non_template)
971        << DTN->getName();
972      return Name;
973    }
974
975    return Template.getAsVal<TemplateName>();
976  }
977
978
979
980  // FIXME: Even if we're referring to a Decl that isn't a template
981  // template parameter, we may need to instantiate the outer contexts
982  // of that Decl. However, this won't be needed until we implement
983  // member templates.
984  return Name;
985}
986