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