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