SemaTemplateInstantiate.cpp revision 1ac02dcb60177c1c1b36526323be76a57efcc468 
1//===------- SemaTemplateInstantiate.cpp - C++ Template Instantiation ------===/
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//===----------------------------------------------------------------------===/
8//
9//  This file implements C++ template instantiation.
10//
11//===----------------------------------------------------------------------===/
12
13#include "Sema.h"
14#include "clang/AST/ASTContext.h"
15#include "clang/AST/Expr.h"
16#include "clang/AST/ExprCXX.h"
17#include "clang/AST/DeclTemplate.h"
18#include "clang/AST/StmtVisitor.h"
19#include "clang/Parse/DeclSpec.h"
20#include "clang/Lex/Preprocessor.h" // for the identifier table
21#include "clang/Basic/LangOptions.h"
22#include "llvm/Support/Compiler.h"
23
24using namespace clang;
25
26//===----------------------------------------------------------------------===/
27// Template Instantiation Support
28//===----------------------------------------------------------------------===/
29
30Sema::InstantiatingTemplate::
31InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
32                      ClassTemplateSpecializationDecl *Entity,
33                      SourceRange InstantiationRange)
34  :  SemaRef(SemaRef) {
35
36  Invalid = CheckInstantiationDepth(PointOfInstantiation,
37                                    InstantiationRange);
38  if (!Invalid) {
39    ActiveTemplateInstantiation Inst;
40    Inst.Kind = ActiveTemplateInstantiation::TemplateInstantiation;
41    Inst.PointOfInstantiation = PointOfInstantiation;
42    Inst.Entity = reinterpret_cast<uintptr_t>(Entity);
43    Inst.TemplateArgs = 0;
44    Inst.NumTemplateArgs = 0;
45    Inst.InstantiationRange = InstantiationRange;
46    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
47    Invalid = false;
48  }
49}
50
51Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
52                                         SourceLocation PointOfInstantiation,
53                                         TemplateDecl *Template,
54                                         const TemplateArgument *TemplateArgs,
55                                         unsigned NumTemplateArgs,
56                                         SourceRange InstantiationRange)
57  : SemaRef(SemaRef) {
58
59  Invalid = CheckInstantiationDepth(PointOfInstantiation,
60                                    InstantiationRange);
61  if (!Invalid) {
62    ActiveTemplateInstantiation Inst;
63    Inst.Kind
64      = ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation;
65    Inst.PointOfInstantiation = PointOfInstantiation;
66    Inst.Entity = reinterpret_cast<uintptr_t>(Template);
67    Inst.TemplateArgs = TemplateArgs;
68    Inst.NumTemplateArgs = NumTemplateArgs;
69    Inst.InstantiationRange = InstantiationRange;
70    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
71    Invalid = false;
72  }
73}
74
75Sema::InstantiatingTemplate::~InstantiatingTemplate() {
76  if (!Invalid)
77    SemaRef.ActiveTemplateInstantiations.pop_back();
78}
79
80bool Sema::InstantiatingTemplate::CheckInstantiationDepth(
81                                        SourceLocation PointOfInstantiation,
82                                           SourceRange InstantiationRange) {
83  if (SemaRef.ActiveTemplateInstantiations.size()
84       <= SemaRef.getLangOptions().InstantiationDepth)
85    return false;
86
87  SemaRef.Diag(PointOfInstantiation,
88               diag::err_template_recursion_depth_exceeded)
89    << SemaRef.getLangOptions().InstantiationDepth
90    << InstantiationRange;
91  SemaRef.Diag(PointOfInstantiation, diag::note_template_recursion_depth)
92    << SemaRef.getLangOptions().InstantiationDepth;
93  return true;
94}
95
96/// \brief Post-diagnostic hook for printing the instantiation stack.
97void Sema::PrintInstantiationStackHook(unsigned, void *Cookie) {
98  Sema &SemaRef = *static_cast<Sema*>(Cookie);
99  SemaRef.PrintInstantiationStack();
100  SemaRef.LastTemplateInstantiationErrorContext
101    = SemaRef.ActiveTemplateInstantiations.back();
102}
103
104/// \brief Prints the current instantiation stack through a series of
105/// notes.
106void Sema::PrintInstantiationStack() {
107  for (llvm::SmallVector<ActiveTemplateInstantiation, 16>::reverse_iterator
108         Active = ActiveTemplateInstantiations.rbegin(),
109         ActiveEnd = ActiveTemplateInstantiations.rend();
110       Active != ActiveEnd;
111       ++Active) {
112    switch (Active->Kind) {
113    case ActiveTemplateInstantiation::TemplateInstantiation: {
114      ClassTemplateSpecializationDecl *Spec
115        = cast<ClassTemplateSpecializationDecl>((Decl*)Active->Entity);
116      Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
117                   diag::note_template_class_instantiation_here)
118        << Context.getTypeDeclType(Spec)
119        << Active->InstantiationRange;
120      break;
121    }
122
123    case ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation: {
124      TemplateDecl *Template = cast<TemplateDecl>((Decl *)Active->Entity);
125      std::string TemplateArgsStr
126        = ClassTemplateSpecializationType::PrintTemplateArgumentList(
127                                                      Active->TemplateArgs,
128                                                      Active->NumTemplateArgs);
129      Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
130                   diag::note_default_arg_instantiation_here)
131        << (Template->getNameAsString() + TemplateArgsStr)
132        << Active->InstantiationRange;
133      break;
134    }
135    }
136  }
137}
138
139//===----------------------------------------------------------------------===/
140// Template Instantiation for Types
141//===----------------------------------------------------------------------===/
142namespace {
143  class VISIBILITY_HIDDEN TemplateTypeInstantiator {
144    Sema &SemaRef;
145    const TemplateArgument *TemplateArgs;
146    unsigned NumTemplateArgs;
147    SourceLocation Loc;
148    DeclarationName Entity;
149
150  public:
151    TemplateTypeInstantiator(Sema &SemaRef,
152                             const TemplateArgument *TemplateArgs,
153                             unsigned NumTemplateArgs,
154                             SourceLocation Loc,
155                             DeclarationName Entity)
156      : SemaRef(SemaRef), TemplateArgs(TemplateArgs),
157        NumTemplateArgs(NumTemplateArgs), Loc(Loc), Entity(Entity) { }
158
159    QualType operator()(QualType T) const { return Instantiate(T); }
160
161    QualType Instantiate(QualType T) const;
162
163    // Declare instantiate functions for each type.
164#define TYPE(Class, Base)                                       \
165    QualType Instantiate##Class##Type(const Class##Type *T,     \
166                                      unsigned Quals) const;
167#define ABSTRACT_TYPE(Class, Base)
168#include "clang/AST/TypeNodes.def"
169  };
170}
171
172QualType
173TemplateTypeInstantiator::InstantiateExtQualType(const ExtQualType *T,
174                                                 unsigned Quals) const {
175  // FIXME: Implement this
176  assert(false && "Cannot instantiate ExtQualType yet");
177  return QualType();
178}
179
180QualType
181TemplateTypeInstantiator::InstantiateBuiltinType(const BuiltinType *T,
182                                                 unsigned Quals) const {
183  assert(false && "Builtin types are not dependent and cannot be instantiated");
184  return QualType(T, Quals);
185}
186
187QualType
188TemplateTypeInstantiator::
189InstantiateFixedWidthIntType(const FixedWidthIntType *T, unsigned Quals) const {
190  // FIXME: Implement this
191  assert(false && "Cannot instantiate FixedWidthIntType yet");
192  return QualType();
193}
194
195QualType
196TemplateTypeInstantiator::InstantiateComplexType(const ComplexType *T,
197                                                 unsigned Quals) const {
198  // FIXME: Implement this
199  assert(false && "Cannot instantiate ComplexType yet");
200  return QualType();
201}
202
203QualType
204TemplateTypeInstantiator::InstantiatePointerType(const PointerType *T,
205                                                 unsigned Quals) const {
206  QualType PointeeType = Instantiate(T->getPointeeType());
207  if (PointeeType.isNull())
208    return QualType();
209
210  return SemaRef.BuildPointerType(PointeeType, Quals, Loc, Entity);
211}
212
213QualType
214TemplateTypeInstantiator::InstantiateBlockPointerType(const BlockPointerType *T,
215                                                      unsigned Quals) const {
216  // FIXME: Implement this
217  assert(false && "Cannot instantiate BlockPointerType yet");
218  return QualType();
219}
220
221QualType
222TemplateTypeInstantiator::InstantiateLValueReferenceType(
223    const LValueReferenceType *T, unsigned Quals) const {
224  QualType ReferentType = Instantiate(T->getPointeeType());
225  if (ReferentType.isNull())
226    return QualType();
227
228  return SemaRef.BuildReferenceType(ReferentType, true, Quals, Loc, Entity);
229}
230
231QualType
232TemplateTypeInstantiator::InstantiateRValueReferenceType(
233    const RValueReferenceType *T, unsigned Quals) const {
234  QualType ReferentType = Instantiate(T->getPointeeType());
235  if (ReferentType.isNull())
236    return QualType();
237
238  return SemaRef.BuildReferenceType(ReferentType, false, Quals, Loc, Entity);
239}
240
241QualType
242TemplateTypeInstantiator::
243InstantiateMemberPointerType(const MemberPointerType *T,
244                             unsigned Quals) const {
245  // FIXME: Implement this
246  assert(false && "Cannot instantiate MemberPointerType yet");
247  return QualType();
248}
249
250QualType
251TemplateTypeInstantiator::
252InstantiateConstantArrayType(const ConstantArrayType *T,
253                             unsigned Quals) const {
254  QualType ElementType = Instantiate(T->getElementType());
255  if (ElementType.isNull())
256    return ElementType;
257
258  // Build a temporary integer literal to specify the size for
259  // BuildArrayType. Since we have already checked the size as part of
260  // creating the dependent array type in the first place, we know
261  // there aren't any errors.
262  // FIXME: Is IntTy big enough? Maybe not, but LongLongTy causes
263  // problems that I have yet to investigate.
264  IntegerLiteral ArraySize(T->getSize(), SemaRef.Context.IntTy, Loc);
265  return SemaRef.BuildArrayType(ElementType, T->getSizeModifier(),
266                                &ArraySize, T->getIndexTypeQualifier(),
267                                Loc, Entity);
268}
269
270QualType
271TemplateTypeInstantiator::
272InstantiateIncompleteArrayType(const IncompleteArrayType *T,
273                               unsigned Quals) const {
274  QualType ElementType = Instantiate(T->getElementType());
275  if (ElementType.isNull())
276    return ElementType;
277
278  return SemaRef.BuildArrayType(ElementType, T->getSizeModifier(),
279                                0, T->getIndexTypeQualifier(),
280                                Loc, Entity);
281}
282
283QualType
284TemplateTypeInstantiator::
285InstantiateVariableArrayType(const VariableArrayType *T,
286                             unsigned Quals) const {
287  // FIXME: Implement this
288  assert(false && "Cannot instantiate VariableArrayType yet");
289  return QualType();
290}
291
292QualType
293TemplateTypeInstantiator::
294InstantiateDependentSizedArrayType(const DependentSizedArrayType *T,
295                                   unsigned Quals) const {
296  Expr *ArraySize = T->getSizeExpr();
297  assert(ArraySize->isValueDependent() &&
298         "dependent sized array types must have value dependent size expr");
299
300  // Instantiate the element type if needed
301  QualType ElementType = T->getElementType();
302  if (ElementType->isDependentType()) {
303    ElementType = Instantiate(ElementType);
304    if (ElementType.isNull())
305      return QualType();
306  }
307
308  // Instantiate the size expression
309  Sema::OwningExprResult InstantiatedArraySize =
310    SemaRef.InstantiateExpr(ArraySize, TemplateArgs, NumTemplateArgs);
311  if (InstantiatedArraySize.isInvalid())
312    return QualType();
313
314  return SemaRef.BuildArrayType(ElementType, T->getSizeModifier(),
315                                (Expr *)InstantiatedArraySize.release(),
316                                T->getIndexTypeQualifier(), Loc, Entity);
317}
318
319QualType
320TemplateTypeInstantiator::InstantiateVectorType(const VectorType *T,
321                                             unsigned Quals) const {
322  // FIXME: Implement this
323  assert(false && "Cannot instantiate VectorType yet");
324  return QualType();
325}
326
327QualType
328TemplateTypeInstantiator::InstantiateExtVectorType(const ExtVectorType *T,
329                                                   unsigned Quals) const {
330  // FIXME: Implement this
331  assert(false && "Cannot instantiate ExtVectorType yet");
332  return QualType();
333}
334
335QualType
336TemplateTypeInstantiator::
337InstantiateFunctionProtoType(const FunctionProtoType *T,
338                             unsigned Quals) const {
339  QualType ResultType = Instantiate(T->getResultType());
340  if (ResultType.isNull())
341    return ResultType;
342
343  llvm::SmallVector<QualType, 16> ParamTypes;
344  for (FunctionProtoType::arg_type_iterator Param = T->arg_type_begin(),
345                                         ParamEnd = T->arg_type_end();
346       Param != ParamEnd; ++Param) {
347    QualType P = Instantiate(*Param);
348    if (P.isNull())
349      return P;
350
351    ParamTypes.push_back(P);
352  }
353
354  return SemaRef.BuildFunctionType(ResultType, &ParamTypes[0],
355                                   ParamTypes.size(),
356                                   T->isVariadic(), T->getTypeQuals(),
357                                   Loc, Entity);
358}
359
360QualType
361TemplateTypeInstantiator::
362InstantiateFunctionNoProtoType(const FunctionNoProtoType *T,
363                               unsigned Quals) const {
364  assert(false && "Functions without prototypes cannot be dependent.");
365  return QualType();
366}
367
368QualType
369TemplateTypeInstantiator::InstantiateTypedefType(const TypedefType *T,
370                                                 unsigned Quals) const {
371  // FIXME: Implement this
372  assert(false && "Cannot instantiate TypedefType yet");
373  return QualType();
374}
375
376QualType
377TemplateTypeInstantiator::InstantiateTypeOfExprType(const TypeOfExprType *T,
378                                                    unsigned Quals) const {
379  // FIXME: Implement this
380  assert(false && "Cannot instantiate TypeOfExprType yet");
381  return QualType();
382}
383
384QualType
385TemplateTypeInstantiator::InstantiateTypeOfType(const TypeOfType *T,
386                                                unsigned Quals) const {
387  // FIXME: Implement this
388  assert(false && "Cannot instantiate TypeOfType yet");
389  return QualType();
390}
391
392QualType
393TemplateTypeInstantiator::InstantiateRecordType(const RecordType *T,
394                                                unsigned Quals) const {
395  // FIXME: Implement this
396  assert(false && "Cannot instantiate RecordType yet");
397  return QualType();
398}
399
400QualType
401TemplateTypeInstantiator::InstantiateEnumType(const EnumType *T,
402                                              unsigned Quals) const {
403  // FIXME: Implement this
404  assert(false && "Cannot instantiate EnumType yet");
405  return QualType();
406}
407
408QualType
409TemplateTypeInstantiator::
410InstantiateTemplateTypeParmType(const TemplateTypeParmType *T,
411                                unsigned Quals) const {
412  if (T->getDepth() == 0) {
413    // Replace the template type parameter with its corresponding
414    // template argument.
415    assert(T->getIndex() < NumTemplateArgs && "Wrong # of template args");
416    assert(TemplateArgs[T->getIndex()].getKind() == TemplateArgument::Type &&
417           "Template argument kind mismatch");
418    QualType Result = TemplateArgs[T->getIndex()].getAsType();
419    if (Result.isNull() || !Quals)
420      return Result;
421
422    // C++ [dcl.ref]p1:
423    //   [...] Cv-qualified references are ill-formed except when
424    //   the cv-qualifiers are introduced through the use of a
425    //   typedef (7.1.3) or of a template type argument (14.3), in
426    //   which case the cv-qualifiers are ignored.
427    if (Quals && Result->isReferenceType())
428      Quals = 0;
429
430    return QualType(Result.getTypePtr(), Quals | Result.getCVRQualifiers());
431  }
432
433  // The template type parameter comes from an inner template (e.g.,
434  // the template parameter list of a member template inside the
435  // template we are instantiating). Create a new template type
436  // parameter with the template "level" reduced by one.
437  return SemaRef.Context.getTemplateTypeParmType(T->getDepth() - 1,
438                                                 T->getIndex(),
439                                                 T->getName())
440    .getQualifiedType(Quals);
441}
442
443QualType
444TemplateTypeInstantiator::
445InstantiateClassTemplateSpecializationType(
446                                  const ClassTemplateSpecializationType *T,
447                                  unsigned Quals) const {
448  llvm::SmallVector<TemplateArgument, 16> InstantiatedTemplateArgs;
449  InstantiatedTemplateArgs.reserve(T->getNumArgs());
450  for (ClassTemplateSpecializationType::iterator Arg = T->begin(),
451                                              ArgEnd = T->end();
452       Arg != ArgEnd; ++Arg) {
453    switch (Arg->getKind()) {
454    case TemplateArgument::Type: {
455      QualType T = SemaRef.InstantiateType(Arg->getAsType(),
456                                           TemplateArgs, NumTemplateArgs,
457                                           Arg->getLocation(),
458                                           DeclarationName());
459      if (T.isNull())
460        return QualType();
461
462      InstantiatedTemplateArgs.push_back(
463                                TemplateArgument(Arg->getLocation(), T));
464      break;
465    }
466
467    case TemplateArgument::Declaration:
468    case TemplateArgument::Integral:
469      InstantiatedTemplateArgs.push_back(*Arg);
470      break;
471
472    case TemplateArgument::Expression:
473      Sema::OwningExprResult E
474        = SemaRef.InstantiateExpr(Arg->getAsExpr(), TemplateArgs,
475                                  NumTemplateArgs);
476      if (E.isInvalid())
477        return QualType();
478      InstantiatedTemplateArgs.push_back((Expr *)E.release());
479      break;
480    }
481  }
482
483  // FIXME: We're missing the locations of the template name, '<', and
484  // '>'.
485  return SemaRef.CheckClassTemplateId(cast<ClassTemplateDecl>(T->getTemplate()),
486                                      Loc,
487                                      SourceLocation(),
488                                      &InstantiatedTemplateArgs[0],
489                                      InstantiatedTemplateArgs.size(),
490                                      SourceLocation());
491}
492
493QualType
494TemplateTypeInstantiator::
495InstantiateObjCInterfaceType(const ObjCInterfaceType *T,
496                             unsigned Quals) const {
497  assert(false && "Objective-C types cannot be dependent");
498  return QualType();
499}
500
501QualType
502TemplateTypeInstantiator::
503InstantiateObjCQualifiedInterfaceType(const ObjCQualifiedInterfaceType *T,
504                                      unsigned Quals) const {
505  assert(false && "Objective-C types cannot be dependent");
506  return QualType();
507}
508
509QualType
510TemplateTypeInstantiator::
511InstantiateObjCQualifiedIdType(const ObjCQualifiedIdType *T,
512                               unsigned Quals) const {
513  assert(false && "Objective-C types cannot be dependent");
514  return QualType();
515}
516
517QualType
518TemplateTypeInstantiator::
519InstantiateObjCQualifiedClassType(const ObjCQualifiedClassType *T,
520                                  unsigned Quals) const {
521  assert(false && "Objective-C types cannot be dependent");
522  return QualType();
523}
524
525/// \brief The actual implementation of Sema::InstantiateType().
526QualType TemplateTypeInstantiator::Instantiate(QualType T) const {
527  // If T is not a dependent type, there is nothing to do.
528  if (!T->isDependentType())
529    return T;
530
531  switch (T->getTypeClass()) {
532#define TYPE(Class, Base)                                               \
533  case Type::Class:                                                     \
534    return Instantiate##Class##Type(cast<Class##Type>(T.getTypePtr()),  \
535                                    T.getCVRQualifiers());
536#define ABSTRACT_TYPE(Class, Base)
537#include "clang/AST/TypeNodes.def"
538  }
539
540  assert(false && "Not all types have been decoded for instantiation");
541  return QualType();
542}
543
544/// \brief Instantiate the type T with a given set of template arguments.
545///
546/// This routine substitutes the given template arguments into the
547/// type T and produces the instantiated type.
548///
549/// \param T the type into which the template arguments will be
550/// substituted. If this type is not dependent, it will be returned
551/// immediately.
552///
553/// \param TemplateArgs the template arguments that will be
554/// substituted for the top-level template parameters within T.
555///
556/// \param NumTemplateArgs the number of template arguments provided
557/// by TemplateArgs.
558///
559/// \param Loc the location in the source code where this substitution
560/// is being performed. It will typically be the location of the
561/// declarator (if we're instantiating the type of some declaration)
562/// or the location of the type in the source code (if, e.g., we're
563/// instantiating the type of a cast expression).
564///
565/// \param Entity the name of the entity associated with a declaration
566/// being instantiated (if any). May be empty to indicate that there
567/// is no such entity (if, e.g., this is a type that occurs as part of
568/// a cast expression) or that the entity has no name (e.g., an
569/// unnamed function parameter).
570///
571/// \returns If the instantiation succeeds, the instantiated
572/// type. Otherwise, produces diagnostics and returns a NULL type.
573QualType Sema::InstantiateType(QualType T,
574                               const TemplateArgument *TemplateArgs,
575                               unsigned NumTemplateArgs,
576                               SourceLocation Loc, DeclarationName Entity) {
577  assert(!ActiveTemplateInstantiations.empty() &&
578         "Cannot perform an instantiation without some context on the "
579         "instantiation stack");
580
581  // If T is not a dependent type, there is nothing to do.
582  if (!T->isDependentType())
583    return T;
584
585  TemplateTypeInstantiator Instantiator(*this, TemplateArgs, NumTemplateArgs,
586                                        Loc, Entity);
587  return Instantiator(T);
588}
589
590//===----------------------------------------------------------------------===/
591// Template Instantiation for Expressions
592//===----------------------------------------------------------------------===/
593namespace {
594  class VISIBILITY_HIDDEN TemplateExprInstantiator
595    : public StmtVisitor<TemplateExprInstantiator, Sema::OwningExprResult> {
596    Sema &SemaRef;
597    const TemplateArgument *TemplateArgs;
598    unsigned NumTemplateArgs;
599
600  public:
601    typedef Sema::OwningExprResult OwningExprResult;
602
603    TemplateExprInstantiator(Sema &SemaRef,
604                             const TemplateArgument *TemplateArgs,
605                             unsigned NumTemplateArgs)
606      : SemaRef(SemaRef), TemplateArgs(TemplateArgs),
607        NumTemplateArgs(NumTemplateArgs) { }
608
609    // FIXME: Once we get closer to completion, replace these
610    // manually-written declarations with automatically-generated ones
611    // from clang/AST/StmtNodes.def.
612    OwningExprResult VisitIntegerLiteral(IntegerLiteral *E);
613    OwningExprResult VisitDeclRefExpr(DeclRefExpr *E);
614    OwningExprResult VisitParenExpr(ParenExpr *E);
615    OwningExprResult VisitUnaryOperator(UnaryOperator *E);
616    OwningExprResult VisitBinaryOperator(BinaryOperator *E);
617    OwningExprResult VisitCXXOperatorCallExpr(CXXOperatorCallExpr *E);
618    OwningExprResult VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E);
619    OwningExprResult VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *E);
620
621    // Base case. I'm supposed to ignore this.
622    Sema::OwningExprResult VisitStmt(Stmt *S) {
623      S->dump();
624      assert(false && "Cannot instantiate this kind of expression");
625      return SemaRef.ExprError();
626    }
627  };
628}
629
630Sema::OwningExprResult
631TemplateExprInstantiator::VisitIntegerLiteral(IntegerLiteral *E) {
632  return SemaRef.Clone(E);
633}
634
635Sema::OwningExprResult
636TemplateExprInstantiator::VisitDeclRefExpr(DeclRefExpr *E) {
637  Decl *D = E->getDecl();
638  if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D)) {
639    assert(NTTP->getDepth() == 0 && "No nested templates yet");
640    const TemplateArgument &Arg = TemplateArgs[NTTP->getPosition()];
641    QualType T = Arg.getIntegralType();
642    if (T->isCharType() || T->isWideCharType())
643      return SemaRef.Owned(new (SemaRef.Context) CharacterLiteral(
644                                          Arg.getAsIntegral()->getZExtValue(),
645                                          T->isWideCharType(),
646                                          T,
647                                       E->getSourceRange().getBegin()));
648    else if (T->isBooleanType())
649      return SemaRef.Owned(new (SemaRef.Context) CXXBoolLiteralExpr(
650                                          Arg.getAsIntegral()->getBoolValue(),
651                                                 T,
652                                       E->getSourceRange().getBegin()));
653
654    return SemaRef.Owned(new (SemaRef.Context) IntegerLiteral(
655                                                 *Arg.getAsIntegral(),
656                                                 T,
657                                       E->getSourceRange().getBegin()));
658  } else
659    assert(false && "Can't handle arbitrary declaration references");
660
661  return SemaRef.ExprError();
662}
663
664Sema::OwningExprResult
665TemplateExprInstantiator::VisitParenExpr(ParenExpr *E) {
666  Sema::OwningExprResult SubExpr
667    = SemaRef.InstantiateExpr(E->getSubExpr(), TemplateArgs, NumTemplateArgs);
668  if (SubExpr.isInvalid())
669    return SemaRef.ExprError();
670
671  return SemaRef.Owned(new (SemaRef.Context) ParenExpr(
672                                               E->getLParen(), E->getRParen(),
673                                               (Expr *)SubExpr.release()));
674}
675
676Sema::OwningExprResult
677TemplateExprInstantiator::VisitUnaryOperator(UnaryOperator *E) {
678  Sema::OwningExprResult Arg = Visit(E->getSubExpr());
679  if (Arg.isInvalid())
680    return SemaRef.ExprError();
681
682  return SemaRef.CreateBuiltinUnaryOp(E->getOperatorLoc(),
683                                      E->getOpcode(),
684                                      move(Arg));
685}
686
687Sema::OwningExprResult
688TemplateExprInstantiator::VisitBinaryOperator(BinaryOperator *E) {
689  Sema::OwningExprResult LHS = Visit(E->getLHS());
690  if (LHS.isInvalid())
691    return SemaRef.ExprError();
692
693  Sema::OwningExprResult RHS = Visit(E->getRHS());
694  if (RHS.isInvalid())
695    return SemaRef.ExprError();
696
697  Sema::OwningExprResult Result
698    = SemaRef.CreateBuiltinBinOp(E->getOperatorLoc(),
699                                 E->getOpcode(),
700                                 (Expr *)LHS.get(),
701                                 (Expr *)RHS.get());
702  if (Result.isInvalid())
703    return SemaRef.ExprError();
704
705  LHS.release();
706  RHS.release();
707  return move(Result);
708}
709
710Sema::OwningExprResult
711TemplateExprInstantiator::VisitCXXOperatorCallExpr(CXXOperatorCallExpr *E) {
712  Sema::OwningExprResult First = Visit(E->getArg(0));
713  if (First.isInvalid())
714    return SemaRef.ExprError();
715
716  Expr *Args[2] = { (Expr *)First.get(), 0 };
717
718  Sema::OwningExprResult Second(SemaRef);
719  if (E->getNumArgs() == 2) {
720    Second = Visit(E->getArg(1));
721
722    if (Second.isInvalid())
723      return SemaRef.ExprError();
724
725    Args[1] = (Expr *)Second.get();
726  }
727
728  if (!E->isTypeDependent()) {
729    // Since our original expression was not type-dependent, we do not
730    // perform lookup again at instantiation time (C++ [temp.dep]p1).
731    // Instead, we just build the new overloaded operator call
732    // expression.
733    First.release();
734    Second.release();
735    return SemaRef.Owned(new (SemaRef.Context) CXXOperatorCallExpr(
736                                                       SemaRef.Context,
737                                                       E->getOperator(),
738                                                       E->getCallee(),
739                                                       Args, E->getNumArgs(),
740                                                       E->getType(),
741                                                       E->getOperatorLoc()));
742  }
743
744  bool isPostIncDec = E->getNumArgs() == 2 &&
745    (E->getOperator() == OO_PlusPlus || E->getOperator() == OO_MinusMinus);
746  if (E->getNumArgs() == 1 || isPostIncDec) {
747    if (!Args[0]->getType()->isOverloadableType()) {
748      // The argument is not of overloadable type, so try to create a
749      // built-in unary operation.
750      UnaryOperator::Opcode Opc
751        = UnaryOperator::getOverloadedOpcode(E->getOperator(), isPostIncDec);
752
753      return SemaRef.CreateBuiltinUnaryOp(E->getOperatorLoc(), Opc,
754                                          move(First));
755    }
756
757    // Fall through to perform overload resolution
758  } else {
759    assert(E->getNumArgs() == 2 && "Expected binary operation");
760
761    Sema::OwningExprResult Result(SemaRef);
762    if (!Args[0]->getType()->isOverloadableType() &&
763        !Args[1]->getType()->isOverloadableType()) {
764      // Neither of the arguments is an overloadable type, so try to
765      // create a built-in binary operation.
766      BinaryOperator::Opcode Opc =
767        BinaryOperator::getOverloadedOpcode(E->getOperator());
768      Result = SemaRef.CreateBuiltinBinOp(E->getOperatorLoc(), Opc,
769                                          Args[0], Args[1]);
770      if (Result.isInvalid())
771        return SemaRef.ExprError();
772
773      First.release();
774      Second.release();
775      return move(Result);
776    }
777
778    // Fall through to perform overload resolution.
779  }
780
781  // Compute the set of functions that were found at template
782  // definition time.
783  Sema::FunctionSet Functions;
784  DeclRefExpr *DRE = cast<DeclRefExpr>(E->getCallee());
785  OverloadedFunctionDecl *Overloads
786    = cast<OverloadedFunctionDecl>(DRE->getDecl());
787
788  // FIXME: Do we have to check
789  // IsAcceptableNonMemberOperatorCandidate for each of these?
790  for (OverloadedFunctionDecl::function_iterator
791         F = Overloads->function_begin(),
792         FEnd = Overloads->function_end();
793       F != FEnd; ++F)
794    Functions.insert(*F);
795
796  // Add any functions found via argument-dependent lookup.
797  DeclarationName OpName
798    = SemaRef.Context.DeclarationNames.getCXXOperatorName(E->getOperator());
799  SemaRef.ArgumentDependentLookup(OpName, Args, E->getNumArgs(), Functions);
800
801  // Create the overloaded operator invocation.
802  if (E->getNumArgs() == 1 || isPostIncDec) {
803    UnaryOperator::Opcode Opc
804      = UnaryOperator::getOverloadedOpcode(E->getOperator(), isPostIncDec);
805    return SemaRef.CreateOverloadedUnaryOp(E->getOperatorLoc(), Opc,
806                                           Functions, move(First));
807  }
808
809  // FIXME: This would be far less ugly if CreateOverloadedBinOp took
810  // in ExprArg arguments!
811  BinaryOperator::Opcode Opc =
812    BinaryOperator::getOverloadedOpcode(E->getOperator());
813  OwningExprResult Result
814    = SemaRef.CreateOverloadedBinOp(E->getOperatorLoc(), Opc,
815                                    Functions, Args[0], Args[1]);
816
817  if (Result.isInvalid())
818    return SemaRef.ExprError();
819
820  First.release();
821  Second.release();
822  return move(Result);
823}
824
825Sema::OwningExprResult
826TemplateExprInstantiator::VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E) {
827  bool isSizeOf = E->isSizeOf();
828
829  if (E->isArgumentType()) {
830    QualType T = E->getArgumentType();
831    if (T->isDependentType()) {
832      T = SemaRef.InstantiateType(T, TemplateArgs, NumTemplateArgs,
833                                  /*FIXME*/E->getOperatorLoc(),
834                                  &SemaRef.PP.getIdentifierTable().get("sizeof"));
835      if (T.isNull())
836        return SemaRef.ExprError();
837    }
838
839    return SemaRef.CreateSizeOfAlignOfExpr(T, E->getOperatorLoc(), isSizeOf,
840                                           E->getSourceRange());
841  }
842
843  Sema::OwningExprResult Arg = Visit(E->getArgumentExpr());
844  if (Arg.isInvalid())
845    return SemaRef.ExprError();
846
847  Sema::OwningExprResult Result
848    = SemaRef.CreateSizeOfAlignOfExpr((Expr *)Arg.get(), E->getOperatorLoc(),
849                                      isSizeOf, E->getSourceRange());
850  if (Result.isInvalid())
851    return SemaRef.ExprError();
852
853  Arg.release();
854  return move(Result);
855}
856
857Sema::OwningExprResult
858TemplateExprInstantiator::VisitCXXTemporaryObjectExpr(
859                                                  CXXTemporaryObjectExpr *E) {
860  QualType T = E->getType();
861  if (T->isDependentType()) {
862    T = SemaRef.InstantiateType(T, TemplateArgs, NumTemplateArgs,
863                                E->getTypeBeginLoc(), DeclarationName());
864    if (T.isNull())
865      return SemaRef.ExprError();
866  }
867
868  llvm::SmallVector<Expr *, 16> Args;
869  Args.reserve(E->getNumArgs());
870  bool Invalid = false;
871  for (CXXTemporaryObjectExpr::arg_iterator Arg = E->arg_begin(),
872                                         ArgEnd = E->arg_end();
873       Arg != ArgEnd; ++Arg) {
874    OwningExprResult InstantiatedArg = Visit(*Arg);
875    if (InstantiatedArg.isInvalid()) {
876      Invalid = true;
877      break;
878    }
879
880    Args.push_back((Expr *)InstantiatedArg.release());
881  }
882
883  if (!Invalid) {
884    SourceLocation CommaLoc;
885    // FIXME: HACK!
886    if (Args.size() > 1)
887      CommaLoc
888        = SemaRef.PP.getLocForEndOfToken(Args[0]->getSourceRange().getEnd());
889    Sema::OwningExprResult Result(
890      SemaRef.ActOnCXXTypeConstructExpr(SourceRange(E->getTypeBeginLoc()
891                                                    /*, FIXME*/),
892                                        T.getAsOpaquePtr(),
893                                        /*FIXME*/E->getTypeBeginLoc(),
894                                        Sema::MultiExprArg(SemaRef,
895                                                           (void**)&Args[0],
896                                                           Args.size()),
897                                        /*HACK*/&CommaLoc,
898                                        E->getSourceRange().getEnd()));
899    // At this point, Args no longer owns the arguments, no matter what.
900    return move(Result);
901  }
902
903  // Clean up the instantiated arguments.
904  // FIXME: Would rather do this with RAII.
905  for (unsigned Idx = 0; Idx < Args.size(); ++Idx)
906    SemaRef.DeleteExpr(Args[Idx]);
907
908  return SemaRef.ExprError();
909}
910
911Sema::OwningExprResult
912Sema::InstantiateExpr(Expr *E, const TemplateArgument *TemplateArgs,
913                      unsigned NumTemplateArgs) {
914  TemplateExprInstantiator Instantiator(*this, TemplateArgs, NumTemplateArgs);
915  return Instantiator.Visit(E);
916}
917
918/// \brief Instantiate the base class specifiers of the given class
919/// template specialization.
920///
921/// Produces a diagnostic and returns true on error, returns false and
922/// attaches the instantiated base classes to the class template
923/// specialization if successful.
924bool
925Sema::InstantiateBaseSpecifiers(
926                           ClassTemplateSpecializationDecl *ClassTemplateSpec,
927                           ClassTemplateDecl *ClassTemplate) {
928  bool Invalid = false;
929  llvm::SmallVector<CXXBaseSpecifier*, 8> InstantiatedBases;
930  for (ClassTemplateSpecializationDecl::base_class_iterator
931         Base = ClassTemplate->getTemplatedDecl()->bases_begin(),
932         BaseEnd = ClassTemplate->getTemplatedDecl()->bases_end();
933       Base != BaseEnd; ++Base) {
934    if (!Base->getType()->isDependentType()) {
935      // FIXME: Allocate via ASTContext
936      InstantiatedBases.push_back(new CXXBaseSpecifier(*Base));
937      continue;
938    }
939
940    QualType BaseType = InstantiateType(Base->getType(),
941                                        ClassTemplateSpec->getTemplateArgs(),
942                                        ClassTemplateSpec->getNumTemplateArgs(),
943                                        Base->getSourceRange().getBegin(),
944                                        DeclarationName());
945    if (BaseType.isNull()) {
946      Invalid = true;
947      continue;
948    }
949
950    if (CXXBaseSpecifier *InstantiatedBase
951          = CheckBaseSpecifier(ClassTemplateSpec,
952                               Base->getSourceRange(),
953                               Base->isVirtual(),
954                               Base->getAccessSpecifierAsWritten(),
955                               BaseType,
956                               /*FIXME: Not totally accurate */
957                               Base->getSourceRange().getBegin()))
958      InstantiatedBases.push_back(InstantiatedBase);
959    else
960      Invalid = true;
961  }
962
963  if (!Invalid &&
964      AttachBaseSpecifiers(ClassTemplateSpec, &InstantiatedBases[0],
965                           InstantiatedBases.size()))
966    Invalid = true;
967
968  return Invalid;
969}
970
971bool
972Sema::InstantiateClassTemplateSpecialization(
973                           ClassTemplateSpecializationDecl *ClassTemplateSpec,
974                           bool ExplicitInstantiation) {
975  // Perform the actual instantiation on the canonical declaration.
976  ClassTemplateSpec = cast<ClassTemplateSpecializationDecl>(
977                               Context.getCanonicalDecl(ClassTemplateSpec));
978
979  // We can only instantiate something that hasn't already been
980  // instantiated or specialized. Fail without any diagnostics: our
981  // caller will provide an error message.
982  if (ClassTemplateSpec->getSpecializationKind() != TSK_Undeclared)
983    return true;
984
985  // FIXME: Push this class template instantiation onto the
986  // instantiation stack, checking for recursion that exceeds a
987  // certain depth.
988
989  // FIXME: Perform class template partial specialization to select
990  // the best template.
991  ClassTemplateDecl *Template = ClassTemplateSpec->getSpecializedTemplate();
992
993  if (!Template->getTemplatedDecl()->getDefinition(Context)) {
994    Diag(ClassTemplateSpec->getLocation(),
995         diag::err_template_implicit_instantiate_undefined)
996      << Context.getTypeDeclType(ClassTemplateSpec);
997    Diag(Template->getTemplatedDecl()->getLocation(),
998         diag::note_template_decl_here);
999    return true;
1000  }
1001
1002  // Note that this is an instantiation.
1003  ClassTemplateSpec->setSpecializationKind(
1004                        ExplicitInstantiation? TSK_ExplicitInstantiation
1005                                             : TSK_ImplicitInstantiation);
1006
1007
1008  bool Invalid = false;
1009
1010  InstantiatingTemplate Inst(*this, ClassTemplateSpec->getLocation(),
1011                             ClassTemplateSpec);
1012  if (Inst)
1013    return true;
1014
1015  // Enter the scope of this instantiation. We don't use
1016  // PushDeclContext because we don't have a scope.
1017  DeclContext *PreviousContext = CurContext;
1018  CurContext = ClassTemplateSpec;
1019
1020  // Start the definition of this instantiation.
1021  ClassTemplateSpec->startDefinition();
1022
1023
1024  // Instantiate the base class specifiers.
1025  if (InstantiateBaseSpecifiers(ClassTemplateSpec, Template))
1026    Invalid = true;
1027
1028  // FIXME: Create the injected-class-name for the
1029  // instantiation. Should this be a typedef or something like it?
1030
1031  RecordDecl *Pattern = Template->getTemplatedDecl();
1032  llvm::SmallVector<DeclTy *, 32> Fields;
1033  for (RecordDecl::decl_iterator Member = Pattern->decls_begin(),
1034                              MemberEnd = Pattern->decls_end();
1035       Member != MemberEnd; ++Member) {
1036    if (TypedefDecl *Typedef = dyn_cast<TypedefDecl>(*Member)) {
1037      // FIXME: Simplified instantiation of typedefs needs to be made
1038      // "real".
1039      QualType T = Typedef->getUnderlyingType();
1040      if (T->isDependentType()) {
1041        T = InstantiateType(T, ClassTemplateSpec->getTemplateArgs(),
1042                            ClassTemplateSpec->getNumTemplateArgs(),
1043                            Typedef->getLocation(),
1044                            Typedef->getDeclName());
1045        if (T.isNull()) {
1046          Invalid = true;
1047          T = Context.IntTy;
1048        }
1049      }
1050
1051      // Create the new typedef
1052      TypedefDecl *New
1053        = TypedefDecl::Create(Context, ClassTemplateSpec,
1054                              Typedef->getLocation(),
1055                              Typedef->getIdentifier(),
1056                              T);
1057      ClassTemplateSpec->addDecl(New);
1058    }
1059    else if (FieldDecl *Field = dyn_cast<FieldDecl>(*Member)) {
1060      // FIXME: Simplified instantiation of fields needs to be made
1061      // "real".
1062      bool InvalidDecl = false;
1063      QualType T = Field->getType();
1064      if (T->isDependentType())  {
1065        T = InstantiateType(T, ClassTemplateSpec->getTemplateArgs(),
1066                            ClassTemplateSpec->getNumTemplateArgs(),
1067                            Field->getLocation(),
1068                            Field->getDeclName());
1069        if (!T.isNull() && T->isFunctionType()) {
1070          // C++ [temp.arg.type]p3:
1071          //   If a declaration acquires a function type through a type
1072          //   dependent on a template-parameter and this causes a
1073          //   declaration that does not use the syntactic form of a
1074          //   function declarator to have function type, the program is
1075          //   ill-formed.
1076          Diag(Field->getLocation(), diag::err_field_instantiates_to_function)
1077            << T;
1078          T = QualType();
1079          InvalidDecl = true;
1080        }
1081      }
1082
1083      Expr *BitWidth = Field->getBitWidth();
1084      if (InvalidDecl)
1085        BitWidth = 0;
1086      else if (BitWidth) {
1087        OwningExprResult InstantiatedBitWidth
1088          = InstantiateExpr(BitWidth,
1089                            ClassTemplateSpec->getTemplateArgs(),
1090                            ClassTemplateSpec->getNumTemplateArgs());
1091        if (InstantiatedBitWidth.isInvalid()) {
1092          Invalid = InvalidDecl = true;
1093          BitWidth = 0;
1094        } else
1095          BitWidth = (Expr *)InstantiatedBitWidth.release();
1096      }
1097
1098      FieldDecl *New = CheckFieldDecl(Field->getDeclName(), T,
1099                                      ClassTemplateSpec,
1100                                      Field->getLocation(),
1101                                      Field->isMutable(),
1102                                      BitWidth,
1103                                      Field->getAccess(),
1104                                      0);
1105      if (New) {
1106        ClassTemplateSpec->addDecl(New);
1107        Fields.push_back(New);
1108
1109        if (InvalidDecl)
1110          New->setInvalidDecl();
1111
1112        if (New->isInvalidDecl())
1113          Invalid = true;
1114      }
1115    } else if (StaticAssertDecl *SA = dyn_cast<StaticAssertDecl>(*Member)) {
1116      Expr *AssertExpr = SA->getAssertExpr();
1117
1118      OwningExprResult InstantiatedAssertExpr
1119        = InstantiateExpr(AssertExpr,
1120                          ClassTemplateSpec->getTemplateArgs(),
1121                          ClassTemplateSpec->getNumTemplateArgs());
1122      if (!InstantiatedAssertExpr.isInvalid()) {
1123        OwningExprResult Message = Clone(SA->getMessage());
1124
1125        Decl *New =
1126          (Decl *)ActOnStaticAssertDeclaration(SA->getLocation(),
1127                                               move(InstantiatedAssertExpr),
1128                                               move(Message));
1129        if (New->isInvalidDecl())
1130          Invalid = true;
1131
1132      } else
1133        Invalid = true;
1134    }
1135  }
1136
1137  // Finish checking fields.
1138  ActOnFields(0, ClassTemplateSpec->getLocation(), ClassTemplateSpec,
1139              &Fields[0], Fields.size(), SourceLocation(), SourceLocation(),
1140              0);
1141
1142  // Add any implicitly-declared members that we might need.
1143  AddImplicitlyDeclaredMembersToClass(ClassTemplateSpec);
1144
1145  // Exit the scope of this instantiation.
1146  CurContext = PreviousContext;
1147
1148  return Invalid;
1149}
1150