1//===--- ASTTypeTraits.h ----------------------------------------*- 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//  Provides a dynamic type identifier and a dynamically typed node container
11//  that can be used to store an AST base node at runtime in the same storage in
12//  a type safe way.
13//
14//===----------------------------------------------------------------------===//
15
16#ifndef LLVM_CLANG_AST_AST_TYPE_TRAITS_H
17#define LLVM_CLANG_AST_AST_TYPE_TRAITS_H
18
19#include "clang/AST/ASTFwd.h"
20#include "clang/AST/Decl.h"
21#include "clang/AST/NestedNameSpecifier.h"
22#include "clang/AST/Stmt.h"
23#include "clang/AST/TemplateBase.h"
24#include "clang/AST/TypeLoc.h"
25#include "clang/Basic/LLVM.h"
26#include "llvm/Support/AlignOf.h"
27
28namespace llvm {
29
30class raw_ostream;
31
32}
33
34namespace clang {
35
36struct PrintingPolicy;
37
38namespace ast_type_traits {
39
40/// \brief Kind identifier.
41///
42/// It can be constructed from any node kind and allows for runtime type
43/// hierarchy checks.
44/// Use getFromNodeKind<T>() to construct them.
45class ASTNodeKind {
46public:
47  /// \brief Empty identifier. It matches nothing.
48  ASTNodeKind() : KindId(NKI_None) {}
49
50  /// \brief Construct an identifier for T.
51  template <class T>
52  static ASTNodeKind getFromNodeKind() {
53    return ASTNodeKind(KindToKindId<T>::Id);
54  }
55
56  /// \brief Returns \c true if \c this and \c Other represent the same kind.
57  bool isSame(ASTNodeKind Other) const;
58
59  /// \brief Returns \c true if \c this is a base kind of (or same as) \c Other.
60  /// \param Distance If non-null, used to return the distance between \c this
61  /// and \c Other in the class hierarchy.
62  bool isBaseOf(ASTNodeKind Other, unsigned *Distance = nullptr) const;
63
64  /// \brief String representation of the kind.
65  StringRef asStringRef() const;
66
67  /// \brief Strict weak ordering for ASTNodeKind.
68  bool operator<(const ASTNodeKind &Other) const {
69    return KindId < Other.KindId;
70  }
71
72private:
73  /// \brief Kind ids.
74  ///
75  /// Includes all possible base and derived kinds.
76  enum NodeKindId {
77    NKI_None,
78    NKI_CXXCtorInitializer,
79    NKI_TemplateArgument,
80    NKI_NestedNameSpecifier,
81    NKI_NestedNameSpecifierLoc,
82    NKI_QualType,
83    NKI_TypeLoc,
84    NKI_Decl,
85#define DECL(DERIVED, BASE) NKI_##DERIVED##Decl,
86#include "clang/AST/DeclNodes.inc"
87    NKI_Stmt,
88#define STMT(DERIVED, BASE) NKI_##DERIVED,
89#include "clang/AST/StmtNodes.inc"
90    NKI_Type,
91#define TYPE(DERIVED, BASE) NKI_##DERIVED##Type,
92#include "clang/AST/TypeNodes.def"
93    NKI_NumberOfKinds
94  };
95
96  /// \brief Use getFromNodeKind<T>() to construct the kind.
97  ASTNodeKind(NodeKindId KindId) : KindId(KindId) {}
98
99  /// \brief Returns \c true if \c Base is a base kind of (or same as) \c
100  ///   Derived.
101  /// \param Distance If non-null, used to return the distance between \c Base
102  /// and \c Derived in the class hierarchy.
103  static bool isBaseOf(NodeKindId Base, NodeKindId Derived, unsigned *Distance);
104
105  /// \brief Helper meta-function to convert a kind T to its enum value.
106  ///
107  /// This struct is specialized below for all known kinds.
108  template <class T> struct KindToKindId {
109    static const NodeKindId Id = NKI_None;
110  };
111
112  /// \brief Per kind info.
113  struct KindInfo {
114    /// \brief The id of the parent kind, or None if it has no parent.
115    NodeKindId ParentId;
116    /// \brief Name of the kind.
117    const char *Name;
118  };
119  static const KindInfo AllKindInfo[NKI_NumberOfKinds];
120
121  NodeKindId KindId;
122};
123
124#define KIND_TO_KIND_ID(Class)                                                 \
125  template <> struct ASTNodeKind::KindToKindId<Class> {                        \
126    static const NodeKindId Id = NKI_##Class;                                  \
127  };
128KIND_TO_KIND_ID(CXXCtorInitializer)
129KIND_TO_KIND_ID(TemplateArgument)
130KIND_TO_KIND_ID(NestedNameSpecifier)
131KIND_TO_KIND_ID(NestedNameSpecifierLoc)
132KIND_TO_KIND_ID(QualType)
133KIND_TO_KIND_ID(TypeLoc)
134KIND_TO_KIND_ID(Decl)
135KIND_TO_KIND_ID(Stmt)
136KIND_TO_KIND_ID(Type)
137#define DECL(DERIVED, BASE) KIND_TO_KIND_ID(DERIVED##Decl)
138#include "clang/AST/DeclNodes.inc"
139#define STMT(DERIVED, BASE) KIND_TO_KIND_ID(DERIVED)
140#include "clang/AST/StmtNodes.inc"
141#define TYPE(DERIVED, BASE) KIND_TO_KIND_ID(DERIVED##Type)
142#include "clang/AST/TypeNodes.def"
143#undef KIND_TO_KIND_ID
144
145inline raw_ostream &operator<<(raw_ostream &OS, ASTNodeKind K) {
146  OS << K.asStringRef();
147  return OS;
148}
149
150/// \brief A dynamically typed AST node container.
151///
152/// Stores an AST node in a type safe way. This allows writing code that
153/// works with different kinds of AST nodes, despite the fact that they don't
154/// have a common base class.
155///
156/// Use \c create(Node) to create a \c DynTypedNode from an AST node,
157/// and \c get<T>() to retrieve the node as type T if the types match.
158///
159/// See \c ASTNodeKind for which node base types are currently supported;
160/// You can create DynTypedNodes for all nodes in the inheritance hierarchy of
161/// the supported base types.
162class DynTypedNode {
163public:
164  /// \brief Creates a \c DynTypedNode from \c Node.
165  template <typename T>
166  static DynTypedNode create(const T &Node) {
167    return BaseConverter<T>::create(Node);
168  }
169
170  /// \brief Retrieve the stored node as type \c T.
171  ///
172  /// Returns NULL if the stored node does not have a type that is
173  /// convertible to \c T.
174  ///
175  /// For types that have identity via their pointer in the AST
176  /// (like \c Stmt, \c Decl, \c Type and \c NestedNameSpecifier) the returned
177  /// pointer points to the referenced AST node.
178  /// For other types (like \c QualType) the value is stored directly
179  /// in the \c DynTypedNode, and the returned pointer points at
180  /// the storage inside DynTypedNode. For those nodes, do not
181  /// use the pointer outside the scope of the DynTypedNode.
182  template <typename T>
183  const T *get() const {
184    return BaseConverter<T>::get(NodeKind, Storage.buffer);
185  }
186
187  /// \brief Returns a pointer that identifies the stored AST node.
188  ///
189  /// Note that this is not supported by all AST nodes. For AST nodes
190  /// that don't have a pointer-defined identity inside the AST, this
191  /// method returns NULL.
192  const void *getMemoizationData() const;
193
194  /// \brief Prints the node to the given output stream.
195  void print(llvm::raw_ostream &OS, const PrintingPolicy &PP) const;
196
197  /// \brief Dumps the node to the given output stream.
198  void dump(llvm::raw_ostream &OS, SourceManager &SM) const;
199
200  /// \brief For nodes which represent textual entities in the source code,
201  /// return their SourceRange.  For all other nodes, return SourceRange().
202  SourceRange getSourceRange() const;
203
204  /// @{
205  /// \brief Imposes an order on \c DynTypedNode.
206  ///
207  /// Supports comparison of nodes that support memoization.
208  /// FIXME: Implement comparsion for other node types (currently
209  /// only Stmt, Decl, Type and NestedNameSpecifier return memoization data).
210  bool operator<(const DynTypedNode &Other) const {
211    assert(getMemoizationData() && Other.getMemoizationData());
212    return getMemoizationData() < Other.getMemoizationData();
213  }
214  bool operator==(const DynTypedNode &Other) const {
215    if (!NodeKind.isBaseOf(Other.NodeKind) &&
216        !Other.NodeKind.isBaseOf(NodeKind))
217      return false;
218
219    // FIXME: Implement for other types.
220    if (ASTNodeKind::getFromNodeKind<QualType>().isBaseOf(NodeKind)) {
221      return *get<QualType>() == *Other.get<QualType>();
222    }
223    assert(getMemoizationData() && Other.getMemoizationData());
224    return getMemoizationData() == Other.getMemoizationData();
225  }
226  bool operator!=(const DynTypedNode &Other) const {
227    return !operator==(Other);
228  }
229  /// @}
230
231private:
232  /// \brief Takes care of converting from and to \c T.
233  template <typename T, typename EnablerT = void> struct BaseConverter;
234
235  /// \brief Converter that uses dyn_cast<T> from a stored BaseT*.
236  template <typename T, typename BaseT> struct DynCastPtrConverter {
237    static const T *get(ASTNodeKind NodeKind, const char Storage[]) {
238      if (ASTNodeKind::getFromNodeKind<BaseT>().isBaseOf(NodeKind))
239        return dyn_cast<T>(*reinterpret_cast<BaseT *const *>(Storage));
240      return nullptr;
241    }
242    static DynTypedNode create(const BaseT &Node) {
243      DynTypedNode Result;
244      Result.NodeKind = ASTNodeKind::getFromNodeKind<T>();
245      new (Result.Storage.buffer) const BaseT * (&Node);
246      return Result;
247    }
248  };
249
250  /// \brief Converter that stores T* (by pointer).
251  template <typename T> struct PtrConverter {
252    static const T *get(ASTNodeKind NodeKind, const char Storage[]) {
253      if (ASTNodeKind::getFromNodeKind<T>().isSame(NodeKind))
254        return *reinterpret_cast<T *const *>(Storage);
255      return nullptr;
256    }
257    static DynTypedNode create(const T &Node) {
258      DynTypedNode Result;
259      Result.NodeKind = ASTNodeKind::getFromNodeKind<T>();
260      new (Result.Storage.buffer) const T * (&Node);
261      return Result;
262    }
263  };
264
265  /// \brief Converter that stores T (by value).
266  template <typename T> struct ValueConverter {
267    static const T *get(ASTNodeKind NodeKind, const char Storage[]) {
268      if (ASTNodeKind::getFromNodeKind<T>().isSame(NodeKind))
269        return reinterpret_cast<const T *>(Storage);
270      return nullptr;
271    }
272    static DynTypedNode create(const T &Node) {
273      DynTypedNode Result;
274      Result.NodeKind = ASTNodeKind::getFromNodeKind<T>();
275      new (Result.Storage.buffer) T(Node);
276      return Result;
277    }
278  };
279
280  ASTNodeKind NodeKind;
281
282  /// \brief Stores the data of the node.
283  ///
284  /// Note that we can store \c Decls, \c Stmts, \c Types,
285  /// \c NestedNameSpecifiers and \c CXXCtorInitializer by pointer as they are
286  /// guaranteed to be unique pointers pointing to dedicated storage in the AST.
287  /// \c QualTypes, \c NestedNameSpecifierLocs, \c TypeLocs and
288  /// \c TemplateArguments on the other hand do not have storage or unique
289  /// pointers and thus need to be stored by value.
290  typedef llvm::AlignedCharArrayUnion<
291      Decl *, Stmt *, Type *, NestedNameSpecifier *, CXXCtorInitializer *>
292      KindsByPointer;
293  llvm::AlignedCharArrayUnion<KindsByPointer, TemplateArgument,
294                              NestedNameSpecifierLoc, QualType, TypeLoc>
295      Storage;
296};
297
298template <typename T>
299struct DynTypedNode::BaseConverter<
300    T, typename std::enable_if<std::is_base_of<Decl, T>::value>::type>
301    : public DynCastPtrConverter<T, Decl> {};
302
303template <typename T>
304struct DynTypedNode::BaseConverter<
305    T, typename std::enable_if<std::is_base_of<Stmt, T>::value>::type>
306    : public DynCastPtrConverter<T, Stmt> {};
307
308template <typename T>
309struct DynTypedNode::BaseConverter<
310    T, typename std::enable_if<std::is_base_of<Type, T>::value>::type>
311    : public DynCastPtrConverter<T, Type> {};
312
313template <>
314struct DynTypedNode::BaseConverter<
315    NestedNameSpecifier, void> : public PtrConverter<NestedNameSpecifier> {};
316
317template <>
318struct DynTypedNode::BaseConverter<
319    CXXCtorInitializer, void> : public PtrConverter<CXXCtorInitializer> {};
320
321template <>
322struct DynTypedNode::BaseConverter<
323    TemplateArgument, void> : public ValueConverter<TemplateArgument> {};
324
325template <>
326struct DynTypedNode::BaseConverter<
327    NestedNameSpecifierLoc,
328    void> : public ValueConverter<NestedNameSpecifierLoc> {};
329
330template <>
331struct DynTypedNode::BaseConverter<QualType,
332                                   void> : public ValueConverter<QualType> {};
333
334template <>
335struct DynTypedNode::BaseConverter<
336    TypeLoc, void> : public ValueConverter<TypeLoc> {};
337
338// The only operation we allow on unsupported types is \c get.
339// This allows to conveniently use \c DynTypedNode when having an arbitrary
340// AST node that is not supported, but prevents misuse - a user cannot create
341// a DynTypedNode from arbitrary types.
342template <typename T, typename EnablerT> struct DynTypedNode::BaseConverter {
343  static const T *get(ASTNodeKind NodeKind, const char Storage[]) {
344    return NULL;
345  }
346};
347
348inline const void *DynTypedNode::getMemoizationData() const {
349  if (ASTNodeKind::getFromNodeKind<Decl>().isBaseOf(NodeKind)) {
350    return BaseConverter<Decl>::get(NodeKind, Storage.buffer);
351  } else if (ASTNodeKind::getFromNodeKind<Stmt>().isBaseOf(NodeKind)) {
352    return BaseConverter<Stmt>::get(NodeKind, Storage.buffer);
353  } else if (ASTNodeKind::getFromNodeKind<Type>().isBaseOf(NodeKind)) {
354    return BaseConverter<Type>::get(NodeKind, Storage.buffer);
355  } else if (ASTNodeKind::getFromNodeKind<NestedNameSpecifier>().isBaseOf(NodeKind)) {
356    return BaseConverter<NestedNameSpecifier>::get(NodeKind, Storage.buffer);
357  }
358  return nullptr;
359}
360
361} // end namespace ast_type_traits
362} // end namespace clang
363
364#endif // LLVM_CLANG_AST_AST_TYPE_TRAITS_H
365