1//===-- TemplateBase.h - Core classes for C++ templates ---------*- C++ -*-===//
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//
10//  This file provides definitions which are common for all kinds of
11//  template representation.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_CLANG_AST_TEMPLATEBASE_H
16#define LLVM_CLANG_AST_TEMPLATEBASE_H
17
18#include "clang/AST/TemplateName.h"
19#include "clang/AST/Type.h"
20#include "llvm/ADT/APSInt.h"
21#include "llvm/ADT/SmallVector.h"
22#include "llvm/Support/Compiler.h"
23#include "llvm/Support/ErrorHandling.h"
24
25namespace llvm {
26  class FoldingSetNodeID;
27}
28
29namespace clang {
30
31class DiagnosticBuilder;
32class Expr;
33struct PrintingPolicy;
34class TypeSourceInfo;
35class ValueDecl;
36
37/// \brief Represents a template argument.
38class TemplateArgument {
39public:
40  /// \brief The kind of template argument we're storing.
41  enum ArgKind {
42    /// \brief Represents an empty template argument, e.g., one that has not
43    /// been deduced.
44    Null = 0,
45    /// The template argument is a type.
46    Type,
47    /// The template argument is a declaration that was provided for a pointer,
48    /// reference, or pointer to member non-type template parameter.
49    Declaration,
50    /// The template argument is a null pointer or null pointer to member that
51    /// was provided for a non-type template parameter.
52    NullPtr,
53    /// The template argument is an integral value stored in an llvm::APSInt
54    /// that was provided for an integral non-type template parameter.
55    Integral,
56    /// The template argument is a template name that was provided for a
57    /// template template parameter.
58    Template,
59    /// The template argument is a pack expansion of a template name that was
60    /// provided for a template template parameter.
61    TemplateExpansion,
62    /// The template argument is an expression, and we've not resolved it to one
63    /// of the other forms yet, either because it's dependent or because we're
64    /// representing a non-canonical template argument (for instance, in a
65    /// TemplateSpecializationType). Also used to represent a non-dependent
66    /// __uuidof expression (a Microsoft extension).
67    Expression,
68    /// The template argument is actually a parameter pack. Arguments are stored
69    /// in the Args struct.
70    Pack
71  };
72
73private:
74  /// \brief The kind of template argument we're storing.
75
76  struct DA {
77    unsigned Kind;
78    bool ForRefParam;
79    ValueDecl *D;
80  };
81  struct I {
82    unsigned Kind;
83    // We store a decomposed APSInt with the data allocated by ASTContext if
84    // BitWidth > 64. The memory may be shared between multiple
85    // TemplateArgument instances.
86    unsigned BitWidth : 31;
87    unsigned IsUnsigned : 1;
88    union {
89      uint64_t VAL;          ///< Used to store the <= 64 bits integer value.
90      const uint64_t *pVal;  ///< Used to store the >64 bits integer value.
91    };
92    void *Type;
93  };
94  struct A {
95    unsigned Kind;
96    unsigned NumArgs;
97    const TemplateArgument *Args;
98  };
99  struct TA {
100    unsigned Kind;
101    unsigned NumExpansions;
102    void *Name;
103  };
104  struct TV {
105    unsigned Kind;
106    uintptr_t V;
107  };
108  union {
109    struct DA DeclArg;
110    struct I Integer;
111    struct A Args;
112    struct TA TemplateArg;
113    struct TV TypeOrValue;
114  };
115
116  TemplateArgument(TemplateName, bool) LLVM_DELETED_FUNCTION;
117
118public:
119  /// \brief Construct an empty, invalid template argument.
120  TemplateArgument() {
121    TypeOrValue.Kind = Null;
122    TypeOrValue.V = 0;
123  }
124
125  /// \brief Construct a template type argument.
126  TemplateArgument(QualType T, bool isNullPtr = false) {
127    TypeOrValue.Kind = isNullPtr ? NullPtr : Type;
128    TypeOrValue.V = reinterpret_cast<uintptr_t>(T.getAsOpaquePtr());
129  }
130
131  /// \brief Construct a template argument that refers to a
132  /// declaration, which is either an external declaration or a
133  /// template declaration.
134  TemplateArgument(ValueDecl *D, bool ForRefParam) {
135    assert(D && "Expected decl");
136    DeclArg.Kind = Declaration;
137    DeclArg.D = D;
138    DeclArg.ForRefParam = ForRefParam;
139  }
140
141  /// \brief Construct an integral constant template argument. The memory to
142  /// store the value is allocated with Ctx.
143  TemplateArgument(ASTContext &Ctx, const llvm::APSInt &Value, QualType Type);
144
145  /// \brief Construct an integral constant template argument with the same
146  /// value as Other but a different type.
147  TemplateArgument(const TemplateArgument &Other, QualType Type) {
148    Integer = Other.Integer;
149    Integer.Type = Type.getAsOpaquePtr();
150  }
151
152  /// \brief Construct a template argument that is a template.
153  ///
154  /// This form of template argument is generally used for template template
155  /// parameters. However, the template name could be a dependent template
156  /// name that ends up being instantiated to a function template whose address
157  /// is taken.
158  ///
159  /// \param Name The template name.
160  TemplateArgument(TemplateName Name) {
161    TemplateArg.Kind = Template;
162    TemplateArg.Name = Name.getAsVoidPointer();
163    TemplateArg.NumExpansions = 0;
164  }
165
166  /// \brief Construct a template argument that is a template pack expansion.
167  ///
168  /// This form of template argument is generally used for template template
169  /// parameters. However, the template name could be a dependent template
170  /// name that ends up being instantiated to a function template whose address
171  /// is taken.
172  ///
173  /// \param Name The template name.
174  ///
175  /// \param NumExpansions The number of expansions that will be generated by
176  /// instantiating
177  TemplateArgument(TemplateName Name, Optional<unsigned> NumExpansions) {
178    TemplateArg.Kind = TemplateExpansion;
179    TemplateArg.Name = Name.getAsVoidPointer();
180    if (NumExpansions)
181      TemplateArg.NumExpansions = *NumExpansions + 1;
182    else
183      TemplateArg.NumExpansions = 0;
184  }
185
186  /// \brief Construct a template argument that is an expression.
187  ///
188  /// This form of template argument only occurs in template argument
189  /// lists used for dependent types and for expression; it will not
190  /// occur in a non-dependent, canonical template argument list.
191  TemplateArgument(Expr *E) {
192    TypeOrValue.Kind = Expression;
193    TypeOrValue.V = reinterpret_cast<uintptr_t>(E);
194  }
195
196  /// \brief Construct a template argument that is a template argument pack.
197  ///
198  /// We assume that storage for the template arguments provided
199  /// outlives the TemplateArgument itself.
200  TemplateArgument(const TemplateArgument *Args, unsigned NumArgs) {
201    this->Args.Kind = Pack;
202    this->Args.Args = Args;
203    this->Args.NumArgs = NumArgs;
204  }
205
206  static TemplateArgument getEmptyPack() {
207    return TemplateArgument((TemplateArgument*)nullptr, 0);
208  }
209
210  /// \brief Create a new template argument pack by copying the given set of
211  /// template arguments.
212  static TemplateArgument CreatePackCopy(ASTContext &Context,
213                                         const TemplateArgument *Args,
214                                         unsigned NumArgs);
215
216  /// \brief Return the kind of stored template argument.
217  ArgKind getKind() const { return (ArgKind)TypeOrValue.Kind; }
218
219  /// \brief Determine whether this template argument has no value.
220  bool isNull() const { return getKind() == Null; }
221
222  /// \brief Whether this template argument is dependent on a template
223  /// parameter such that its result can change from one instantiation to
224  /// another.
225  bool isDependent() const;
226
227  /// \brief Whether this template argument is dependent on a template
228  /// parameter.
229  bool isInstantiationDependent() const;
230
231  /// \brief Whether this template argument contains an unexpanded
232  /// parameter pack.
233  bool containsUnexpandedParameterPack() const;
234
235  /// \brief Determine whether this template argument is a pack expansion.
236  bool isPackExpansion() const;
237
238  /// \brief Retrieve the type for a type template argument.
239  QualType getAsType() const {
240    assert(getKind() == Type && "Unexpected kind");
241    return QualType::getFromOpaquePtr(reinterpret_cast<void*>(TypeOrValue.V));
242  }
243
244  /// \brief Retrieve the declaration for a declaration non-type
245  /// template argument.
246  ValueDecl *getAsDecl() const {
247    assert(getKind() == Declaration && "Unexpected kind");
248    return DeclArg.D;
249  }
250
251  /// \brief Retrieve whether a declaration is binding to a
252  /// reference parameter in a declaration non-type template argument.
253  bool isDeclForReferenceParam() const {
254    assert(getKind() == Declaration && "Unexpected kind");
255    return DeclArg.ForRefParam;
256  }
257
258  /// \brief Retrieve the type for null non-type template argument.
259  QualType getNullPtrType() const {
260    assert(getKind() == NullPtr && "Unexpected kind");
261    return QualType::getFromOpaquePtr(reinterpret_cast<void*>(TypeOrValue.V));
262  }
263
264  /// \brief Retrieve the template name for a template name argument.
265  TemplateName getAsTemplate() const {
266    assert(getKind() == Template && "Unexpected kind");
267    return TemplateName::getFromVoidPointer(TemplateArg.Name);
268  }
269
270  /// \brief Retrieve the template argument as a template name; if the argument
271  /// is a pack expansion, return the pattern as a template name.
272  TemplateName getAsTemplateOrTemplatePattern() const {
273    assert((getKind() == Template || getKind() == TemplateExpansion) &&
274           "Unexpected kind");
275
276    return TemplateName::getFromVoidPointer(TemplateArg.Name);
277  }
278
279  /// \brief Retrieve the number of expansions that a template template argument
280  /// expansion will produce, if known.
281  Optional<unsigned> getNumTemplateExpansions() const;
282
283  /// \brief Retrieve the template argument as an integral value.
284  // FIXME: Provide a way to read the integral data without copying the value.
285  llvm::APSInt getAsIntegral() const {
286    assert(getKind() == Integral && "Unexpected kind");
287    using namespace llvm;
288    if (Integer.BitWidth <= 64)
289      return APSInt(APInt(Integer.BitWidth, Integer.VAL), Integer.IsUnsigned);
290
291    unsigned NumWords = APInt::getNumWords(Integer.BitWidth);
292    return APSInt(APInt(Integer.BitWidth, makeArrayRef(Integer.pVal, NumWords)),
293                  Integer.IsUnsigned);
294  }
295
296  /// \brief Retrieve the type of the integral value.
297  QualType getIntegralType() const {
298    assert(getKind() == Integral && "Unexpected kind");
299    return QualType::getFromOpaquePtr(Integer.Type);
300  }
301
302  void setIntegralType(QualType T) {
303    assert(getKind() == Integral && "Unexpected kind");
304    Integer.Type = T.getAsOpaquePtr();
305  }
306
307  /// \brief Retrieve the template argument as an expression.
308  Expr *getAsExpr() const {
309    assert(getKind() == Expression && "Unexpected kind");
310    return reinterpret_cast<Expr *>(TypeOrValue.V);
311  }
312
313  /// \brief Iterator that traverses the elements of a template argument pack.
314  typedef const TemplateArgument * pack_iterator;
315
316  /// \brief Iterator referencing the first argument of a template argument
317  /// pack.
318  pack_iterator pack_begin() const {
319    assert(getKind() == Pack);
320    return Args.Args;
321  }
322
323  /// \brief Iterator referencing one past the last argument of a template
324  /// argument pack.
325  pack_iterator pack_end() const {
326    assert(getKind() == Pack);
327    return Args.Args + Args.NumArgs;
328  }
329
330  /// \brief The number of template arguments in the given template argument
331  /// pack.
332  unsigned pack_size() const {
333    assert(getKind() == Pack);
334    return Args.NumArgs;
335  }
336
337  /// \brief Return the array of arguments in this template argument pack.
338  ArrayRef<TemplateArgument> getPackAsArray() const {
339    assert(getKind() == Pack);
340    return ArrayRef<TemplateArgument>(Args.Args, Args.NumArgs);
341  }
342
343  /// \brief Determines whether two template arguments are superficially the
344  /// same.
345  bool structurallyEquals(const TemplateArgument &Other) const;
346
347  /// \brief When the template argument is a pack expansion, returns
348  /// the pattern of the pack expansion.
349  TemplateArgument getPackExpansionPattern() const;
350
351  /// \brief Print this template argument to the given output stream.
352  void print(const PrintingPolicy &Policy, raw_ostream &Out) const;
353
354  /// \brief Used to insert TemplateArguments into FoldingSets.
355  void Profile(llvm::FoldingSetNodeID &ID, const ASTContext &Context) const;
356};
357
358/// Location information for a TemplateArgument.
359struct TemplateArgumentLocInfo {
360private:
361
362  struct T {
363    // FIXME: We'd like to just use the qualifier in the TemplateName,
364    // but template arguments get canonicalized too quickly.
365    NestedNameSpecifier *Qualifier;
366    void *QualifierLocData;
367    unsigned TemplateNameLoc;
368    unsigned EllipsisLoc;
369  };
370
371  union {
372    struct T Template;
373    Expr *Expression;
374    TypeSourceInfo *Declarator;
375  };
376
377public:
378  TemplateArgumentLocInfo();
379
380  TemplateArgumentLocInfo(TypeSourceInfo *TInfo) : Declarator(TInfo) {}
381
382  TemplateArgumentLocInfo(Expr *E) : Expression(E) {}
383
384  TemplateArgumentLocInfo(NestedNameSpecifierLoc QualifierLoc,
385                          SourceLocation TemplateNameLoc,
386                          SourceLocation EllipsisLoc)
387  {
388    Template.Qualifier = QualifierLoc.getNestedNameSpecifier();
389    Template.QualifierLocData = QualifierLoc.getOpaqueData();
390    Template.TemplateNameLoc = TemplateNameLoc.getRawEncoding();
391    Template.EllipsisLoc = EllipsisLoc.getRawEncoding();
392  }
393
394  TypeSourceInfo *getAsTypeSourceInfo() const {
395    return Declarator;
396  }
397
398  Expr *getAsExpr() const {
399    return Expression;
400  }
401
402  NestedNameSpecifierLoc getTemplateQualifierLoc() const {
403    return NestedNameSpecifierLoc(Template.Qualifier,
404                                  Template.QualifierLocData);
405  }
406
407  SourceLocation getTemplateNameLoc() const {
408    return SourceLocation::getFromRawEncoding(Template.TemplateNameLoc);
409  }
410
411  SourceLocation getTemplateEllipsisLoc() const {
412    return SourceLocation::getFromRawEncoding(Template.EllipsisLoc);
413  }
414};
415
416/// Location wrapper for a TemplateArgument.  TemplateArgument is to
417/// TemplateArgumentLoc as Type is to TypeLoc.
418class TemplateArgumentLoc {
419  TemplateArgument Argument;
420  TemplateArgumentLocInfo LocInfo;
421
422public:
423  TemplateArgumentLoc() {}
424
425  TemplateArgumentLoc(const TemplateArgument &Argument,
426                      TemplateArgumentLocInfo Opaque)
427    : Argument(Argument), LocInfo(Opaque) {
428  }
429
430  TemplateArgumentLoc(const TemplateArgument &Argument, TypeSourceInfo *TInfo)
431    : Argument(Argument), LocInfo(TInfo) {
432    assert(Argument.getKind() == TemplateArgument::Type);
433  }
434
435  TemplateArgumentLoc(const TemplateArgument &Argument, Expr *E)
436    : Argument(Argument), LocInfo(E) {
437    assert(Argument.getKind() == TemplateArgument::Expression);
438  }
439
440  TemplateArgumentLoc(const TemplateArgument &Argument,
441                      NestedNameSpecifierLoc QualifierLoc,
442                      SourceLocation TemplateNameLoc,
443                      SourceLocation EllipsisLoc = SourceLocation())
444    : Argument(Argument), LocInfo(QualifierLoc, TemplateNameLoc, EllipsisLoc) {
445    assert(Argument.getKind() == TemplateArgument::Template ||
446           Argument.getKind() == TemplateArgument::TemplateExpansion);
447  }
448
449  /// \brief - Fetches the primary location of the argument.
450  SourceLocation getLocation() const {
451    if (Argument.getKind() == TemplateArgument::Template ||
452        Argument.getKind() == TemplateArgument::TemplateExpansion)
453      return getTemplateNameLoc();
454
455    return getSourceRange().getBegin();
456  }
457
458  /// \brief - Fetches the full source range of the argument.
459  SourceRange getSourceRange() const LLVM_READONLY;
460
461  const TemplateArgument &getArgument() const {
462    return Argument;
463  }
464
465  TemplateArgumentLocInfo getLocInfo() const {
466    return LocInfo;
467  }
468
469  TypeSourceInfo *getTypeSourceInfo() const {
470    assert(Argument.getKind() == TemplateArgument::Type);
471    return LocInfo.getAsTypeSourceInfo();
472  }
473
474  Expr *getSourceExpression() const {
475    assert(Argument.getKind() == TemplateArgument::Expression);
476    return LocInfo.getAsExpr();
477  }
478
479  Expr *getSourceDeclExpression() const {
480    assert(Argument.getKind() == TemplateArgument::Declaration);
481    return LocInfo.getAsExpr();
482  }
483
484  Expr *getSourceNullPtrExpression() const {
485    assert(Argument.getKind() == TemplateArgument::NullPtr);
486    return LocInfo.getAsExpr();
487  }
488
489  Expr *getSourceIntegralExpression() const {
490    assert(Argument.getKind() == TemplateArgument::Integral);
491    return LocInfo.getAsExpr();
492  }
493
494  NestedNameSpecifierLoc getTemplateQualifierLoc() const {
495    assert(Argument.getKind() == TemplateArgument::Template ||
496           Argument.getKind() == TemplateArgument::TemplateExpansion);
497    return LocInfo.getTemplateQualifierLoc();
498  }
499
500  SourceLocation getTemplateNameLoc() const {
501    assert(Argument.getKind() == TemplateArgument::Template ||
502           Argument.getKind() == TemplateArgument::TemplateExpansion);
503    return LocInfo.getTemplateNameLoc();
504  }
505
506  SourceLocation getTemplateEllipsisLoc() const {
507    assert(Argument.getKind() == TemplateArgument::TemplateExpansion);
508    return LocInfo.getTemplateEllipsisLoc();
509  }
510};
511
512/// A convenient class for passing around template argument
513/// information.  Designed to be passed by reference.
514class TemplateArgumentListInfo {
515  SmallVector<TemplateArgumentLoc, 8> Arguments;
516  SourceLocation LAngleLoc;
517  SourceLocation RAngleLoc;
518
519  // This can leak if used in an AST node, use ASTTemplateArgumentListInfo
520  // instead.
521  void* operator new(size_t bytes, ASTContext& C);
522
523public:
524  TemplateArgumentListInfo() {}
525
526  TemplateArgumentListInfo(SourceLocation LAngleLoc,
527                           SourceLocation RAngleLoc)
528    : LAngleLoc(LAngleLoc), RAngleLoc(RAngleLoc) {}
529
530  SourceLocation getLAngleLoc() const { return LAngleLoc; }
531  SourceLocation getRAngleLoc() const { return RAngleLoc; }
532
533  void setLAngleLoc(SourceLocation Loc) { LAngleLoc = Loc; }
534  void setRAngleLoc(SourceLocation Loc) { RAngleLoc = Loc; }
535
536  unsigned size() const { return Arguments.size(); }
537
538  const TemplateArgumentLoc *getArgumentArray() const {
539    return Arguments.data();
540  }
541
542  const TemplateArgumentLoc &operator[](unsigned I) const {
543    return Arguments[I];
544  }
545
546  TemplateArgumentLoc &operator[](unsigned I) {
547    return Arguments[I];
548  }
549
550  void addArgument(const TemplateArgumentLoc &Loc) {
551    Arguments.push_back(Loc);
552  }
553};
554
555/// \brief Represents an explicit template argument list in C++, e.g.,
556/// the "<int>" in "sort<int>".
557/// This is safe to be used inside an AST node, in contrast with
558/// TemplateArgumentListInfo.
559struct ASTTemplateArgumentListInfo {
560  /// \brief The source location of the left angle bracket ('<').
561  SourceLocation LAngleLoc;
562
563  /// \brief The source location of the right angle bracket ('>').
564  SourceLocation RAngleLoc;
565
566  union {
567    /// \brief The number of template arguments in TemplateArgs.
568    /// The actual template arguments (if any) are stored after the
569    /// ExplicitTemplateArgumentList structure.
570    unsigned NumTemplateArgs;
571
572    /// Force ASTTemplateArgumentListInfo to the right alignment
573    /// for the following array of TemplateArgumentLocs.
574    llvm::AlignedCharArray<
575        llvm::AlignOf<TemplateArgumentLoc>::Alignment, 1> Aligner;
576  };
577
578  /// \brief Retrieve the template arguments
579  TemplateArgumentLoc *getTemplateArgs() {
580    return reinterpret_cast<TemplateArgumentLoc *> (this + 1);
581  }
582
583  /// \brief Retrieve the template arguments
584  const TemplateArgumentLoc *getTemplateArgs() const {
585    return reinterpret_cast<const TemplateArgumentLoc *> (this + 1);
586  }
587
588  const TemplateArgumentLoc &operator[](unsigned I) const {
589    return getTemplateArgs()[I];
590  }
591
592  static const ASTTemplateArgumentListInfo *Create(ASTContext &C,
593                                          const TemplateArgumentListInfo &List);
594
595  void initializeFrom(const TemplateArgumentListInfo &List);
596  void initializeFrom(const TemplateArgumentListInfo &List,
597                      bool &Dependent, bool &InstantiationDependent,
598                      bool &ContainsUnexpandedParameterPack);
599  void copyInto(TemplateArgumentListInfo &List) const;
600  static std::size_t sizeFor(unsigned NumTemplateArgs);
601};
602
603/// \brief Extends ASTTemplateArgumentListInfo with the source location
604/// information for the template keyword; this is used as part of the
605/// representation of qualified identifiers, such as S<T>::template apply<T>.
606struct ASTTemplateKWAndArgsInfo : public ASTTemplateArgumentListInfo {
607  typedef ASTTemplateArgumentListInfo Base;
608
609  // NOTE: the source location of the (optional) template keyword is
610  // stored after all template arguments.
611
612  /// \brief Get the source location of the template keyword.
613  SourceLocation getTemplateKeywordLoc() const {
614    return *reinterpret_cast<const SourceLocation*>
615      (getTemplateArgs() + NumTemplateArgs);
616  }
617
618  /// \brief Sets the source location of the template keyword.
619  void setTemplateKeywordLoc(SourceLocation TemplateKWLoc) {
620    *reinterpret_cast<SourceLocation*>
621      (getTemplateArgs() + NumTemplateArgs) = TemplateKWLoc;
622  }
623
624  static const ASTTemplateKWAndArgsInfo*
625  Create(ASTContext &C, SourceLocation TemplateKWLoc,
626         const TemplateArgumentListInfo &List);
627
628  void initializeFrom(SourceLocation TemplateKWLoc,
629                      const TemplateArgumentListInfo &List);
630  void initializeFrom(SourceLocation TemplateKWLoc,
631                      const TemplateArgumentListInfo &List,
632                      bool &Dependent, bool &InstantiationDependent,
633                      bool &ContainsUnexpandedParameterPack);
634  void initializeFrom(SourceLocation TemplateKWLoc);
635
636  static std::size_t sizeFor(unsigned NumTemplateArgs);
637};
638
639const DiagnosticBuilder &operator<<(const DiagnosticBuilder &DB,
640                                    const TemplateArgument &Arg);
641
642inline TemplateSpecializationType::iterator
643    TemplateSpecializationType::end() const {
644  return getArgs() + getNumArgs();
645}
646
647inline DependentTemplateSpecializationType::iterator
648    DependentTemplateSpecializationType::end() const {
649  return getArgs() + getNumArgs();
650}
651
652inline const TemplateArgument &
653    TemplateSpecializationType::getArg(unsigned Idx) const {
654  assert(Idx < getNumArgs() && "Template argument out of range");
655  return getArgs()[Idx];
656}
657
658inline const TemplateArgument &
659    DependentTemplateSpecializationType::getArg(unsigned Idx) const {
660  assert(Idx < getNumArgs() && "Template argument out of range");
661  return getArgs()[Idx];
662}
663
664} // end namespace clang
665
666#endif
667