1 //===--- ASTTypeTraits.h ----------------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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
14 //===----------------------------------------------------------------------===//
16 #ifndef LLVM_CLANG_AST_ASTTYPETRAITS_H
17 #define LLVM_CLANG_AST_ASTTYPETRAITS_H
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"
37 struct PrintingPolicy;
39 namespace ast_type_traits {
41 /// \brief Kind identifier.
43 /// It can be constructed from any node kind and allows for runtime type
45 /// Use getFromNodeKind<T>() to construct them.
48 /// \brief Empty identifier. It matches nothing.
49 ASTNodeKind() : KindId(NKI_None) {}
51 /// \brief Construct an identifier for T.
53 static ASTNodeKind getFromNodeKind() {
54 return ASTNodeKind(KindToKindId<T>::Id);
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);
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;
69 /// \brief Returns \c true only for the default \c ASTNodeKind()
70 bool isNone() const { return KindId == NKI_None; }
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;
77 /// \brief String representation of the kind.
78 StringRef asStringRef() const;
80 /// \brief Strict weak ordering for ASTNodeKind.
81 bool operator<(const ASTNodeKind &Other) const {
82 return KindId < Other.KindId;
85 /// \brief Return the most derived type between \p Kind1 and \p Kind2.
87 /// Return ASTNodeKind() if they are not related.
88 static ASTNodeKind getMostDerivedType(ASTNodeKind Kind1, ASTNodeKind Kind2);
90 /// \brief Return the most derived common ancestor between Kind1 and Kind2.
92 /// Return ASTNodeKind() if they are not related.
93 static ASTNodeKind getMostDerivedCommonAncestor(ASTNodeKind Kind1,
96 /// \brief Hooks for using ASTNodeKind as a key in a DenseMap.
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
102 static inline ASTNodeKind getTombstoneKey() {
103 return ASTNodeKind(NKI_NumberOfKinds);
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;
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;
120 /// Includes all possible base and derived kinds.
123 NKI_TemplateArgument,
124 NKI_NestedNameSpecifierLoc,
127 NKI_LastKindWithoutPointerIdentity = NKI_TypeLoc,
128 NKI_CXXCtorInitializer,
129 NKI_NestedNameSpecifier,
131 #define DECL(DERIVED, BASE) NKI_##DERIVED##Decl,
132 #include "clang/AST/DeclNodes.inc"
134 #define STMT(DERIVED, BASE) NKI_##DERIVED,
135 #include "clang/AST/StmtNodes.inc"
137 #define TYPE(DERIVED, BASE) NKI_##DERIVED##Type,
138 #include "clang/AST/TypeNodes.def"
142 /// \brief Use getFromNodeKind<T>() to construct the kind.
143 ASTNodeKind(NodeKindId KindId) : KindId(KindId) {}
145 /// \brief Returns \c true if \c Base is a base kind of (or same as) \c
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);
151 /// \brief Helper meta-function to convert a kind T to its enum value.
153 /// This struct is specialized below for all known kinds.
154 template <class T> struct KindToKindId {
155 static const NodeKindId Id = NKI_None;
158 struct KindToKindId<const T> : KindToKindId<T> {};
160 /// \brief Per kind info.
162 /// \brief The id of the parent kind, or None if it has no parent.
164 /// \brief Name of the kind.
167 static const KindInfo AllKindInfo[NKI_NumberOfKinds];
172 #define KIND_TO_KIND_ID(Class) \
173 template <> struct ASTNodeKind::KindToKindId<Class> { \
174 static const NodeKindId Id = NKI_##Class; \
176 KIND_TO_KIND_ID(CXXCtorInitializer)
177 KIND_TO_KIND_ID(TemplateArgument)
178 KIND_TO_KIND_ID(NestedNameSpecifier)
179 KIND_TO_KIND_ID(NestedNameSpecifierLoc)
180 KIND_TO_KIND_ID(QualType)
181 KIND_TO_KIND_ID(TypeLoc)
182 KIND_TO_KIND_ID(Decl)
183 KIND_TO_KIND_ID(Stmt)
184 KIND_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
193 inline raw_ostream &operator<<(raw_ostream &OS, ASTNodeKind K) {
194 OS << K.asStringRef();
198 /// \brief A dynamically typed AST node container.
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.
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.
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.
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);
218 /// \brief Retrieve the stored node as type \c T.
220 /// Returns NULL if the stored node does not have a type that is
221 /// convertible to \c T.
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);
235 /// \brief Retrieve the stored node as type \c T.
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);
243 ASTNodeKind getNodeKind() const { return NodeKind; }
245 /// \brief Returns a pointer that identifies the stored AST node.
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)
256 /// \brief Prints the node to the given output stream.
257 void print(llvm::raw_ostream &OS, const PrintingPolicy &PP) const;
259 /// \brief Dumps the node to the given output stream.
260 void dump(llvm::raw_ostream &OS, SourceManager &SM) const;
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;
267 /// \brief Imposes an order on \c DynTypedNode.
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;
276 if (ASTNodeKind::getFromNodeKind<QualType>().isSame(NodeKind))
277 return getUnchecked<QualType>().getAsOpaquePtr() <
278 Other.getUnchecked<QualType>().getAsOpaquePtr();
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());
289 if (ASTNodeKind::getFromNodeKind<NestedNameSpecifierLoc>().isSame(
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());
299 assert(getMemoizationData() && Other.getMemoizationData());
300 return getMemoizationData() < Other.getMemoizationData();
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))
308 // FIXME: Implement for other types.
309 if (ASTNodeKind::getFromNodeKind<QualType>().isSame(NodeKind))
310 return getUnchecked<QualType>() == Other.getUnchecked<QualType>();
312 if (ASTNodeKind::getFromNodeKind<TypeLoc>().isSame(NodeKind))
313 return getUnchecked<TypeLoc>() == Other.getUnchecked<TypeLoc>();
315 if (ASTNodeKind::getFromNodeKind<NestedNameSpecifierLoc>().isSame(NodeKind))
316 return getUnchecked<NestedNameSpecifierLoc>() ==
317 Other.getUnchecked<NestedNameSpecifierLoc>();
319 assert(getMemoizationData() && Other.getMemoizationData());
320 return getMemoizationData() == Other.getMemoizationData();
322 bool operator!=(const DynTypedNode &Other) const {
323 return !operator==(Other);
327 /// \brief Hooks for using DynTypedNode as a key in a DenseMap.
328 struct DenseMapInfo {
329 static inline DynTypedNode getEmptyKey() {
331 Node.NodeKind = ASTNodeKind::DenseMapInfo::getEmptyKey();
334 static inline DynTypedNode getTombstoneKey() {
336 Node.NodeKind = ASTNodeKind::DenseMapInfo::getTombstoneKey();
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(),
347 if (ASTNodeKind::getFromNodeKind<NestedNameSpecifierLoc>().isSame(
349 auto NNSL = Val.getUnchecked<NestedNameSpecifierLoc>();
350 return llvm::hash_combine(NNSL.getNestedNameSpecifier(),
351 NNSL.getOpaqueData());
354 assert(Val.getMemoizationData());
355 return llvm::hash_value(Val.getMemoizationData());
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)) ||
369 /// \brief Takes care of converting from and to \c T.
370 template <typename T, typename EnablerT = void> struct BaseConverter;
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);
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)));
384 static DynTypedNode create(const BaseT &Node) {
386 Result.NodeKind = ASTNodeKind::getFromNode(Node);
387 new (Result.Storage.buffer) const void *(&Node);
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);
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));
404 static DynTypedNode create(const T &Node) {
406 Result.NodeKind = ASTNodeKind::getFromNodeKind<T>();
407 new (Result.Storage.buffer) const void *(&Node);
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);
419 static const T &getUnchecked(ASTNodeKind NodeKind, const char Storage[]) {
420 assert(ASTNodeKind::getFromNodeKind<T>().isSame(NodeKind));
421 return *reinterpret_cast<const T *>(Storage);
423 static DynTypedNode create(const T &Node) {
425 Result.NodeKind = ASTNodeKind::getFromNodeKind<T>();
426 new (Result.Storage.buffer) T(Node);
431 ASTNodeKind NodeKind;
433 /// \brief Stores the data of the node.
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,
446 template <typename T>
447 struct DynTypedNode::BaseConverter<
448 T, typename std::enable_if<std::is_base_of<Decl, T>::value>::type>
449 : public DynCastPtrConverter<T, Decl> {};
451 template <typename T>
452 struct DynTypedNode::BaseConverter<
453 T, typename std::enable_if<std::is_base_of<Stmt, T>::value>::type>
454 : public DynCastPtrConverter<T, Stmt> {};
456 template <typename T>
457 struct DynTypedNode::BaseConverter<
458 T, typename std::enable_if<std::is_base_of<Type, T>::value>::type>
459 : public DynCastPtrConverter<T, Type> {};
462 struct DynTypedNode::BaseConverter<
463 NestedNameSpecifier, void> : public PtrConverter<NestedNameSpecifier> {};
466 struct DynTypedNode::BaseConverter<
467 CXXCtorInitializer, void> : public PtrConverter<CXXCtorInitializer> {};
470 struct DynTypedNode::BaseConverter<
471 TemplateArgument, void> : public ValueConverter<TemplateArgument> {};
474 struct DynTypedNode::BaseConverter<
475 NestedNameSpecifierLoc,
476 void> : public ValueConverter<NestedNameSpecifierLoc> {};
479 struct DynTypedNode::BaseConverter<QualType,
480 void> : public ValueConverter<QualType> {};
483 struct DynTypedNode::BaseConverter<
484 TypeLoc, void> : public ValueConverter<TypeLoc> {};
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.
490 template <typename T, typename EnablerT> struct DynTypedNode::BaseConverter {
491 static const T *get(ASTNodeKind NodeKind, const char Storage[]) {
496 } // end namespace ast_type_traits
497 } // end namespace clang
502 struct DenseMapInfo<clang::ast_type_traits::ASTNodeKind>
503 : clang::ast_type_traits::ASTNodeKind::DenseMapInfo {};
506 struct DenseMapInfo<clang::ast_type_traits::DynTypedNode>
507 : clang::ast_type_traits::DynTypedNode::DenseMapInfo {};
509 } // end namespace llvm