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