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