SemaTemplateInstantiate.cpp revision ed3a398adc9a7745c2acc3fa0ad4a906149ef2de 
1//===------- SemaTemplateInstantiate.cpp - C++ Template Instantiation ------===/
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//===----------------------------------------------------------------------===/
8//
9//  This file implements C++ template instantiation.
10//
11//===----------------------------------------------------------------------===/
12
13#include "Sema.h"
14#include "clang/AST/ASTContext.h"
15#include "clang/AST/Expr.h"
16#include "clang/AST/ExprCXX.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 for Types
26//===----------------------------------------------------------------------===/
27namespace {
28  class VISIBILITY_HIDDEN TemplateTypeInstantiator {
29    Sema &SemaRef;
30    const TemplateArgument *TemplateArgs;
31    unsigned NumTemplateArgs;
32    SourceLocation Loc;
33    DeclarationName Entity;
34
35  public:
36    TemplateTypeInstantiator(Sema &SemaRef,
37                             const TemplateArgument *TemplateArgs,
38                             unsigned NumTemplateArgs,
39                             SourceLocation Loc,
40                             DeclarationName Entity)
41      : SemaRef(SemaRef), TemplateArgs(TemplateArgs),
42        NumTemplateArgs(NumTemplateArgs), Loc(Loc), Entity(Entity) { }
43
44    QualType operator()(QualType T) const { return Instantiate(T); }
45
46    QualType Instantiate(QualType T) const;
47
48    // Declare instantiate functions for each type.
49#define TYPE(Class, Base)                                       \
50    QualType Instantiate##Class##Type(const Class##Type *T,     \
51                                      unsigned Quals) const;
52#define ABSTRACT_TYPE(Class, Base)
53#include "clang/AST/TypeNodes.def"
54  };
55}
56
57QualType
58TemplateTypeInstantiator::InstantiateExtQualType(const ExtQualType *T,
59                                                 unsigned Quals) const {
60  // FIXME: Implement this
61  assert(false && "Cannot instantiate ExtQualType yet");
62  return QualType();
63}
64
65QualType
66TemplateTypeInstantiator::InstantiateBuiltinType(const BuiltinType *T,
67                                                 unsigned Quals) const {
68  assert(false && "Builtin types are not dependent and cannot be instantiated");
69  return QualType(T, Quals);
70}
71
72QualType
73TemplateTypeInstantiator::
74InstantiateFixedWidthIntType(const FixedWidthIntType *T, unsigned Quals) const {
75  // FIXME: Implement this
76  assert(false && "Cannot instantiate FixedWidthIntType yet");
77  return QualType();
78}
79
80QualType
81TemplateTypeInstantiator::InstantiateComplexType(const ComplexType *T,
82                                                 unsigned Quals) const {
83  // FIXME: Implement this
84  assert(false && "Cannot instantiate ComplexType yet");
85  return QualType();
86}
87
88QualType
89TemplateTypeInstantiator::InstantiatePointerType(const PointerType *T,
90                                                 unsigned Quals) const {
91  QualType PointeeType = Instantiate(T->getPointeeType());
92  if (PointeeType.isNull())
93    return QualType();
94
95  return SemaRef.BuildPointerType(PointeeType, Quals, Loc, Entity);
96}
97
98QualType
99TemplateTypeInstantiator::InstantiateBlockPointerType(const BlockPointerType *T,
100                                                      unsigned Quals) const {
101  // FIXME: Implement this
102  assert(false && "Cannot instantiate BlockPointerType yet");
103  return QualType();
104}
105
106QualType
107TemplateTypeInstantiator::InstantiateReferenceType(const ReferenceType *T,
108                                                   unsigned Quals) const {
109  QualType ReferentType = Instantiate(T->getPointeeType());
110  if (ReferentType.isNull())
111    return QualType();
112
113  return SemaRef.BuildReferenceType(ReferentType, Quals, Loc, Entity);
114}
115
116QualType
117TemplateTypeInstantiator::
118InstantiateMemberPointerType(const MemberPointerType *T,
119                             unsigned Quals) const {
120  // FIXME: Implement this
121  assert(false && "Cannot instantiate MemberPointerType yet");
122  return QualType();
123}
124
125QualType
126TemplateTypeInstantiator::
127InstantiateConstantArrayType(const ConstantArrayType *T,
128                             unsigned Quals) const {
129  QualType ElementType = Instantiate(T->getElementType());
130  if (ElementType.isNull())
131    return ElementType;
132
133  // Build a temporary integer literal to specify the size for
134  // BuildArrayType. Since we have already checked the size as part of
135  // creating the dependent array type in the first place, we know
136  // there aren't any errors.
137  // FIXME: Is IntTy big enough? Maybe not, but LongLongTy causes
138  // problems that I have yet to investigate.
139  IntegerLiteral ArraySize(T->getSize(), SemaRef.Context.IntTy, Loc);
140  return SemaRef.BuildArrayType(ElementType, T->getSizeModifier(),
141                                &ArraySize, T->getIndexTypeQualifier(),
142                                Loc, Entity);
143}
144
145QualType
146TemplateTypeInstantiator::
147InstantiateIncompleteArrayType(const IncompleteArrayType *T,
148                               unsigned Quals) const {
149  QualType ElementType = Instantiate(T->getElementType());
150  if (ElementType.isNull())
151    return ElementType;
152
153  return SemaRef.BuildArrayType(ElementType, T->getSizeModifier(),
154                                0, T->getIndexTypeQualifier(),
155                                Loc, Entity);
156}
157
158QualType
159TemplateTypeInstantiator::
160InstantiateVariableArrayType(const VariableArrayType *T,
161                             unsigned Quals) const {
162  // FIXME: Implement this
163  assert(false && "Cannot instantiate VariableArrayType yet");
164  return QualType();
165}
166
167QualType
168TemplateTypeInstantiator::
169InstantiateDependentSizedArrayType(const DependentSizedArrayType *T,
170                                   unsigned Quals) const {
171  // FIXME: Implement this
172  assert(false && "Cannot instantiate DependentSizedArrayType yet");
173  return QualType();
174}
175
176QualType
177TemplateTypeInstantiator::InstantiateVectorType(const VectorType *T,
178                                             unsigned Quals) const {
179  // FIXME: Implement this
180  assert(false && "Cannot instantiate VectorType yet");
181  return QualType();
182}
183
184QualType
185TemplateTypeInstantiator::InstantiateExtVectorType(const ExtVectorType *T,
186                                                   unsigned Quals) const {
187  // FIXME: Implement this
188  assert(false && "Cannot instantiate ExtVectorType yet");
189  return QualType();
190}
191
192QualType
193TemplateTypeInstantiator::
194InstantiateFunctionProtoType(const FunctionProtoType *T,
195                             unsigned Quals) const {
196  QualType ResultType = Instantiate(T->getResultType());
197  if (ResultType.isNull())
198    return ResultType;
199
200  llvm::SmallVector<QualType, 16> ParamTypes;
201  for (FunctionProtoType::arg_type_iterator Param = T->arg_type_begin(),
202                                         ParamEnd = T->arg_type_end();
203       Param != ParamEnd; ++Param) {
204    QualType P = Instantiate(*Param);
205    if (P.isNull())
206      return P;
207
208    ParamTypes.push_back(P);
209  }
210
211  return SemaRef.BuildFunctionType(ResultType, &ParamTypes[0],
212                                   ParamTypes.size(),
213                                   T->isVariadic(), T->getTypeQuals(),
214                                   Loc, Entity);
215}
216
217QualType
218TemplateTypeInstantiator::
219InstantiateFunctionNoProtoType(const FunctionNoProtoType *T,
220                               unsigned Quals) const {
221  assert(false && "Functions without prototypes cannot be dependent.");
222  return QualType();
223}
224
225QualType
226TemplateTypeInstantiator::InstantiateTypedefType(const TypedefType *T,
227                                                 unsigned Quals) const {
228  // FIXME: Implement this
229  assert(false && "Cannot instantiate TypedefType yet");
230  return QualType();
231}
232
233QualType
234TemplateTypeInstantiator::InstantiateTypeOfExprType(const TypeOfExprType *T,
235                                                    unsigned Quals) const {
236  // FIXME: Implement this
237  assert(false && "Cannot instantiate TypeOfExprType yet");
238  return QualType();
239}
240
241QualType
242TemplateTypeInstantiator::InstantiateTypeOfType(const TypeOfType *T,
243                                                unsigned Quals) const {
244  // FIXME: Implement this
245  assert(false && "Cannot instantiate TypeOfType yet");
246  return QualType();
247}
248
249QualType
250TemplateTypeInstantiator::InstantiateRecordType(const RecordType *T,
251                                                unsigned Quals) const {
252  // FIXME: Implement this
253  assert(false && "Cannot instantiate RecordType yet");
254  return QualType();
255}
256
257QualType
258TemplateTypeInstantiator::InstantiateEnumType(const EnumType *T,
259                                              unsigned Quals) const {
260  // FIXME: Implement this
261  assert(false && "Cannot instantiate EnumType yet");
262  return QualType();
263}
264
265QualType
266TemplateTypeInstantiator::
267InstantiateTemplateTypeParmType(const TemplateTypeParmType *T,
268                                unsigned Quals) const {
269  if (T->getDepth() == 0) {
270    // Replace the template type parameter with its corresponding
271    // template argument.
272    assert(T->getIndex() < NumTemplateArgs && "Wrong # of template args");
273    assert(TemplateArgs[T->getIndex()].getKind() == TemplateArgument::Type &&
274           "Template argument kind mismatch");
275    QualType Result = TemplateArgs[T->getIndex()].getAsType();
276    if (Result.isNull() || !Quals)
277      return Result;
278
279    // C++ [dcl.ref]p1:
280    //   [...] Cv-qualified references are ill-formed except when
281    //   the cv-qualifiers are introduced through the use of a
282    //   typedef (7.1.3) or of a template type argument (14.3), in
283    //   which case the cv-qualifiers are ignored.
284    if (Quals && Result->isReferenceType())
285      Quals = 0;
286
287    return QualType(Result.getTypePtr(), Quals | Result.getCVRQualifiers());
288  }
289
290  // The template type parameter comes from an inner template (e.g.,
291  // the template parameter list of a member template inside the
292  // template we are instantiating). Create a new template type
293  // parameter with the template "level" reduced by one.
294  return SemaRef.Context.getTemplateTypeParmType(T->getDepth() - 1,
295                                                 T->getIndex(),
296                                                 T->getName())
297    .getQualifiedType(Quals);
298}
299
300QualType
301TemplateTypeInstantiator::
302InstantiateClassTemplateSpecializationType(
303                                  const ClassTemplateSpecializationType *T,
304                                  unsigned Quals) const {
305  // FIXME: Implement this
306  assert(false && "Cannot instantiate ClassTemplateSpecializationType yet");
307  return QualType();
308}
309
310QualType
311TemplateTypeInstantiator::
312InstantiateObjCInterfaceType(const ObjCInterfaceType *T,
313                             unsigned Quals) const {
314  assert(false && "Objective-C types cannot be dependent");
315  return QualType();
316}
317
318QualType
319TemplateTypeInstantiator::
320InstantiateObjCQualifiedInterfaceType(const ObjCQualifiedInterfaceType *T,
321                                      unsigned Quals) const {
322  assert(false && "Objective-C types cannot be dependent");
323  return QualType();
324}
325
326QualType
327TemplateTypeInstantiator::
328InstantiateObjCQualifiedIdType(const ObjCQualifiedIdType *T,
329                               unsigned Quals) const {
330  assert(false && "Objective-C types cannot be dependent");
331  return QualType();
332}
333
334QualType
335TemplateTypeInstantiator::
336InstantiateObjCQualifiedClassType(const ObjCQualifiedClassType *T,
337                                  unsigned Quals) const {
338  assert(false && "Objective-C types cannot be dependent");
339  return QualType();
340}
341
342/// \brief The actual implementation of Sema::InstantiateType().
343QualType TemplateTypeInstantiator::Instantiate(QualType T) const {
344  // If T is not a dependent type, there is nothing to do.
345  if (!T->isDependentType())
346    return T;
347
348  switch (T->getTypeClass()) {
349#define TYPE(Class, Base)                                               \
350  case Type::Class:                                                     \
351    return Instantiate##Class##Type(cast<Class##Type>(T.getTypePtr()),  \
352                                    T.getCVRQualifiers());
353#define ABSTRACT_TYPE(Class, Base)
354#include "clang/AST/TypeNodes.def"
355  }
356
357  assert(false && "Not all types have been decoded for instantiation");
358  return QualType();
359}
360
361/// \brief Instantiate the type T with a given set of template arguments.
362///
363/// This routine substitutes the given template arguments into the
364/// type T and produces the instantiated type.
365///
366/// \param T the type into which the template arguments will be
367/// substituted. If this type is not dependent, it will be returned
368/// immediately.
369///
370/// \param TemplateArgs the template arguments that will be
371/// substituted for the top-level template parameters within T.
372///
373/// \param NumTemplateArgs the number of template arguments provided
374/// by TemplateArgs.
375///
376/// \param Loc the location in the source code where this substitution
377/// is being performed. It will typically be the location of the
378/// declarator (if we're instantiating the type of some declaration)
379/// or the location of the type in the source code (if, e.g., we're
380/// instantiating the type of a cast expression).
381///
382/// \param Entity the name of the entity associated with a declaration
383/// being instantiated (if any). May be empty to indicate that there
384/// is no such entity (if, e.g., this is a type that occurs as part of
385/// a cast expression) or that the entity has no name (e.g., an
386/// unnamed function parameter).
387///
388/// \returns If the instantiation succeeds, the instantiated
389/// type. Otherwise, produces diagnostics and returns a NULL type.
390QualType Sema::InstantiateType(QualType T,
391                               const TemplateArgument *TemplateArgs,
392                               unsigned NumTemplateArgs,
393                               SourceLocation Loc, DeclarationName Entity) {
394  // If T is not a dependent type, there is nothing to do.
395  if (!T->isDependentType())
396    return T;
397
398  TemplateTypeInstantiator Instantiator(*this, TemplateArgs, NumTemplateArgs,
399                                        Loc, Entity);
400  return Instantiator(T);
401}
402
403/// \brief Instantiate the base class specifiers of the given class
404/// template specialization.
405///
406/// Produces a diagnostic and returns true on error, returns false and
407/// attaches the instantiated base classes to the class template
408/// specialization if successful.
409bool
410Sema::InstantiateBaseSpecifiers(
411                           ClassTemplateSpecializationDecl *ClassTemplateSpec,
412                           ClassTemplateDecl *ClassTemplate) {
413  bool Invalid = false;
414  llvm::SmallVector<CXXBaseSpecifier*, 8> InstantiatedBases;
415  for (ClassTemplateSpecializationDecl::base_class_iterator
416         Base = ClassTemplate->getTemplatedDecl()->bases_begin(),
417         BaseEnd = ClassTemplate->getTemplatedDecl()->bases_end();
418       Base != BaseEnd && !Invalid; ++Base) {
419    if (!Base->getType()->isDependentType()) {
420      // FIXME: Allocate via ASTContext
421      InstantiatedBases.push_back(new CXXBaseSpecifier(*Base));
422      continue;
423    }
424
425    QualType BaseType = InstantiateType(Base->getType(),
426                                        ClassTemplateSpec->getTemplateArgs(),
427                                        ClassTemplateSpec->getNumTemplateArgs(),
428                                        Base->getSourceRange().getBegin(),
429                                        DeclarationName());
430    if (BaseType.isNull()) {
431      Invalid = true;
432      continue;
433    }
434
435    if (CXXBaseSpecifier *InstantiatedBase
436          = CheckBaseSpecifier(ClassTemplateSpec,
437                               Base->getSourceRange(),
438                               Base->isVirtual(),
439                               Base->getAccessSpecifierAsWritten(),
440                               BaseType,
441                               /*FIXME: Not totally accurate */
442                               Base->getSourceRange().getBegin()))
443      InstantiatedBases.push_back(InstantiatedBase);
444    else
445      Invalid = true;
446  }
447
448  if (AttachBaseSpecifiers(ClassTemplateSpec, &InstantiatedBases[0],
449                           InstantiatedBases.size()))
450    Invalid = true;
451
452  return Invalid;
453}
454
455bool
456Sema::InstantiateClassTemplateSpecialization(
457                           ClassTemplateSpecializationDecl *ClassTemplateSpec,
458                           bool ExplicitInstantiation) {
459  // Perform the actual instantiation on the canonical declaration.
460  ClassTemplateSpec = cast<ClassTemplateSpecializationDecl>(
461                               Context.getCanonicalDecl(ClassTemplateSpec));
462
463  // We can only instantiate something that hasn't already been
464  // instantiated or specialized. Fail without any diagnostics: our
465  // caller will provide an error message.
466  if (ClassTemplateSpec->getSpecializationKind() != TSK_Undeclared)
467    return true;
468
469  // FIXME: Push this class template instantiation onto the
470  // instantiation stack, checking for recursion that exceeds a
471  // certain depth.
472
473  // FIXME: Perform class template partial specialization to select
474  // the best template.
475  ClassTemplateDecl *Template = ClassTemplateSpec->getSpecializedTemplate();
476
477  if (!Template->getTemplatedDecl()->getDefinition(Context)) {
478    Diag(ClassTemplateSpec->getLocation(),
479         diag::err_template_implicit_instantiate_undefined)
480      << Context.getTypeDeclType(ClassTemplateSpec);
481    Diag(Template->getTemplatedDecl()->getLocation(),
482         diag::note_template_decl_here);
483    return true;
484  }
485
486  // Note that this is an instantiation.
487  ClassTemplateSpec->setSpecializationKind(
488                        ExplicitInstantiation? TSK_ExplicitInstantiation
489                                             : TSK_ImplicitInstantiation);
490
491
492  bool Invalid = false;
493
494  // Enter the scope of this instantiation. We don't use
495  // PushDeclContext because we don't have a scope.
496  DeclContext *PreviousContext = CurContext;
497  CurContext = ClassTemplateSpec;
498
499  // Start the definition of this instantiation.
500  ClassTemplateSpec->startDefinition();
501
502  // FIXME: Create the injected-class-name for the
503  // instantiation. Should this be a typedef or something like it?
504
505  // Instantiate the base class specifiers.
506  if (InstantiateBaseSpecifiers(ClassTemplateSpec, Template))
507    Invalid = true;
508
509  // FIXME: Instantiate all of the members.
510
511  // Add any implicitly-declared members that we might need.
512  AddImplicitlyDeclaredMembersToClass(ClassTemplateSpec);
513
514  // Finish the definition of this instantiation.
515  // FIXME: ActOnFields does more checking, which we'll eventually need.
516  ClassTemplateSpec->completeDefinition(Context);
517
518  // Exit the scope of this instantiation.
519  CurContext = PreviousContext;
520
521  return Invalid;
522}
523