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