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