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