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