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