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