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