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