1 //===--- ASTTypeTraits.h ----------------------------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
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
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_CLANG_AST_ASTTYPETRAITS_H
16 #define LLVM_CLANG_AST_ASTTYPETRAITS_H
18 #include "clang/AST/ASTFwd.h"
19 #include "clang/AST/DeclCXX.h"
20 #include "clang/AST/LambdaCapture.h"
21 #include "clang/AST/NestedNameSpecifier.h"
22 #include "clang/AST/TemplateBase.h"
23 #include "clang/AST/TypeLoc.h"
24 #include "clang/Basic/LLVM.h"
25 #include "llvm/ADT/DenseMapInfo.h"
26 #include "llvm/Support/AlignOf.h"
34 struct PrintingPolicy;
36 /// Defines how we descend a level in the AST when we pass
37 /// through expressions.
39 /// Will traverse all child nodes.
42 /// Ignore AST nodes not written in the source
43 TK_IgnoreUnlessSpelledInSource
48 /// It can be constructed from any node kind and allows for runtime type
50 /// Use getFromNodeKind<T>() to construct them.
53 /// Empty identifier. It matches nothing.
54 constexpr ASTNodeKind() : KindId(NKI_None) {}
56 /// Construct an identifier for T.
57 template <class T> static constexpr ASTNodeKind getFromNodeKind() {
58 return ASTNodeKind(KindToKindId<T>::Id);
62 /// Construct an identifier for the dynamic type of the node
63 static ASTNodeKind getFromNode(const Decl &D);
64 static ASTNodeKind getFromNode(const Stmt &S);
65 static ASTNodeKind getFromNode(const Type &T);
66 static ASTNodeKind getFromNode(const TypeLoc &T);
67 static ASTNodeKind getFromNode(const LambdaCapture &L);
68 static ASTNodeKind getFromNode(const OMPClause &C);
69 static ASTNodeKind getFromNode(const Attr &A);
72 /// Returns \c true if \c this and \c Other represent the same kind.
73 constexpr bool isSame(ASTNodeKind Other) const {
74 return KindId != NKI_None && KindId == Other.KindId;
77 /// Returns \c true only for the default \c ASTNodeKind()
78 constexpr bool isNone() const { return KindId == NKI_None; }
80 /// Returns \c true if \c this is a base kind of (or same as) \c Other.
81 bool isBaseOf(ASTNodeKind Other) const;
83 /// Returns \c true if \c this is a base kind of (or same as) \c Other.
84 /// \param Distance If non-null, used to return the distance between \c this
85 /// and \c Other in the class hierarchy.
86 bool isBaseOf(ASTNodeKind Other, unsigned *Distance) const;
88 /// String representation of the kind.
89 StringRef asStringRef() const;
91 /// Strict weak ordering for ASTNodeKind.
92 constexpr bool operator<(const ASTNodeKind &Other) const {
93 return KindId < Other.KindId;
96 /// Return the most derived type between \p Kind1 and \p Kind2.
98 /// Return ASTNodeKind() if they are not related.
99 static ASTNodeKind getMostDerivedType(ASTNodeKind Kind1, ASTNodeKind Kind2);
101 /// Return the most derived common ancestor between Kind1 and Kind2.
103 /// Return ASTNodeKind() if they are not related.
104 static ASTNodeKind getMostDerivedCommonAncestor(ASTNodeKind Kind1,
107 ASTNodeKind getCladeKind() const;
109 /// Hooks for using ASTNodeKind as a key in a DenseMap.
110 struct DenseMapInfo {
111 // ASTNodeKind() is a good empty key because it is represented as a 0.
112 static inline ASTNodeKind getEmptyKey() { return ASTNodeKind(); }
113 // NKI_NumberOfKinds is not a valid value, so it is good for a
115 static inline ASTNodeKind getTombstoneKey() {
116 return ASTNodeKind(NKI_NumberOfKinds);
118 static unsigned getHashValue(const ASTNodeKind &Val) { return Val.KindId; }
119 static bool isEqual(const ASTNodeKind &LHS, const ASTNodeKind &RHS) {
120 return LHS.KindId == RHS.KindId;
124 /// Check if the given ASTNodeKind identifies a type that offers pointer
125 /// identity. This is useful for the fast path in DynTypedNode.
126 constexpr bool hasPointerIdentity() const {
127 return KindId > NKI_LastKindWithoutPointerIdentity;
133 /// Includes all possible base and derived kinds.
136 NKI_TemplateArgument,
137 NKI_TemplateArgumentLoc,
140 NKI_NestedNameSpecifierLoc,
142 #define TYPELOC(CLASS, PARENT) NKI_##CLASS##TypeLoc,
143 #include "clang/AST/TypeLocNodes.def"
145 NKI_LastKindWithoutPointerIdentity = NKI_TypeLoc,
146 NKI_CXXBaseSpecifier,
147 NKI_CXXCtorInitializer,
148 NKI_NestedNameSpecifier,
150 #define DECL(DERIVED, BASE) NKI_##DERIVED##Decl,
151 #include "clang/AST/DeclNodes.inc"
153 #define STMT(DERIVED, BASE) NKI_##DERIVED,
154 #include "clang/AST/StmtNodes.inc"
156 #define TYPE(DERIVED, BASE) NKI_##DERIVED##Type,
157 #include "clang/AST/TypeNodes.inc"
159 #define GEN_CLANG_CLAUSE_CLASS
160 #define CLAUSE_CLASS(Enum, Str, Class) NKI_##Class,
161 #include "llvm/Frontend/OpenMP/OMP.inc"
163 #define ATTR(A) NKI_##A##Attr,
164 #include "clang/Basic/AttrList.inc"
169 /// Use getFromNodeKind<T>() to construct the kind.
170 constexpr ASTNodeKind(NodeKindId KindId) : KindId(KindId) {}
172 /// Returns \c true if \c Base is a base kind of (or same as) \c
174 static bool isBaseOf(NodeKindId Base, NodeKindId Derived);
176 /// Returns \c true if \c Base is a base kind of (or same as) \c
178 /// \param Distance If non-null, used to return the distance between \c Base
179 /// and \c Derived in the class hierarchy.
180 static bool isBaseOf(NodeKindId Base, NodeKindId Derived, unsigned *Distance);
182 /// Helper meta-function to convert a kind T to its enum value.
184 /// This struct is specialized below for all known kinds.
185 template <class T> struct KindToKindId {
186 static const NodeKindId Id = NKI_None;
189 struct KindToKindId<const T> : KindToKindId<T> {};
193 /// The id of the parent kind, or None if it has no parent.
195 /// Name of the kind.
198 static const KindInfo AllKindInfo[NKI_NumberOfKinds];
203 #define KIND_TO_KIND_ID(Class) \
204 template <> struct ASTNodeKind::KindToKindId<Class> { \
205 static const NodeKindId Id = NKI_##Class; \
207 KIND_TO_KIND_ID(CXXCtorInitializer)
208 KIND_TO_KIND_ID(TemplateArgument)
209 KIND_TO_KIND_ID(TemplateArgumentLoc)
210 KIND_TO_KIND_ID(LambdaCapture)
211 KIND_TO_KIND_ID(TemplateName)
212 KIND_TO_KIND_ID(NestedNameSpecifier)
213 KIND_TO_KIND_ID(NestedNameSpecifierLoc)
214 KIND_TO_KIND_ID(QualType)
215 #define TYPELOC(CLASS, PARENT) KIND_TO_KIND_ID(CLASS##TypeLoc)
216 #include "clang/AST/TypeLocNodes.def"
217 KIND_TO_KIND_ID(TypeLoc)
218 KIND_TO_KIND_ID(Decl)
219 KIND_TO_KIND_ID(Stmt)
220 KIND_TO_KIND_ID(Type)
221 KIND_TO_KIND_ID(OMPClause)
222 KIND_TO_KIND_ID(Attr)
223 KIND_TO_KIND_ID(ObjCProtocolLoc)
224 KIND_TO_KIND_ID(CXXBaseSpecifier)
225 #define DECL(DERIVED, BASE) KIND_TO_KIND_ID(DERIVED##Decl)
226 #include "clang/AST/DeclNodes.inc"
227 #define STMT(DERIVED, BASE) KIND_TO_KIND_ID(DERIVED)
228 #include "clang/AST/StmtNodes.inc"
229 #define TYPE(DERIVED, BASE) KIND_TO_KIND_ID(DERIVED##Type)
230 #include "clang/AST/TypeNodes.inc"
231 #define GEN_CLANG_CLAUSE_CLASS
232 #define CLAUSE_CLASS(Enum, Str, Class) KIND_TO_KIND_ID(Class)
233 #include "llvm/Frontend/OpenMP/OMP.inc"
234 #define ATTR(A) KIND_TO_KIND_ID(A##Attr)
235 #include "clang/Basic/AttrList.inc"
236 #undef KIND_TO_KIND_ID
238 inline raw_ostream &operator<<(raw_ostream &OS, ASTNodeKind K) {
239 OS << K.asStringRef();
243 /// A dynamically typed AST node container.
245 /// Stores an AST node in a type safe way. This allows writing code that
246 /// works with different kinds of AST nodes, despite the fact that they don't
247 /// have a common base class.
249 /// Use \c create(Node) to create a \c DynTypedNode from an AST node,
250 /// and \c get<T>() to retrieve the node as type T if the types match.
252 /// See \c ASTNodeKind for which node base types are currently supported;
253 /// You can create DynTypedNodes for all nodes in the inheritance hierarchy of
254 /// the supported base types.
257 /// Creates a \c DynTypedNode from \c Node.
258 template <typename T>
259 static DynTypedNode create(const T &Node) {
260 return BaseConverter<T>::create(Node);
263 /// Retrieve the stored node as type \c T.
265 /// Returns NULL if the stored node does not have a type that is
266 /// convertible to \c T.
268 /// For types that have identity via their pointer in the AST
269 /// (like \c Stmt, \c Decl, \c Type and \c NestedNameSpecifier) the returned
270 /// pointer points to the referenced AST node.
271 /// For other types (like \c QualType) the value is stored directly
272 /// in the \c DynTypedNode, and the returned pointer points at
273 /// the storage inside DynTypedNode. For those nodes, do not
274 /// use the pointer outside the scope of the DynTypedNode.
275 template <typename T> const T *get() const {
276 return BaseConverter<T>::get(NodeKind, &Storage);
279 /// Retrieve the stored node as type \c T.
281 /// Similar to \c get(), but asserts that the type is what we are expecting.
282 template <typename T>
283 const T &getUnchecked() const {
284 return BaseConverter<T>::getUnchecked(NodeKind, &Storage);
287 ASTNodeKind getNodeKind() const { return NodeKind; }
289 /// Returns a pointer that identifies the stored AST node.
291 /// Note that this is not supported by all AST nodes. For AST nodes
292 /// that don't have a pointer-defined identity inside the AST, this
293 /// method returns NULL.
294 const void *getMemoizationData() const {
295 return NodeKind.hasPointerIdentity()
296 ? *reinterpret_cast<void *const *>(&Storage)
300 /// Prints the node to the given output stream.
301 void print(llvm::raw_ostream &OS, const PrintingPolicy &PP) const;
303 /// Dumps the node to the given output stream.
304 void dump(llvm::raw_ostream &OS, const ASTContext &Context) const;
306 /// For nodes which represent textual entities in the source code,
307 /// return their SourceRange. For all other nodes, return SourceRange().
308 SourceRange getSourceRange() const;
311 /// Imposes an order on \c DynTypedNode.
313 /// Supports comparison of nodes that support memoization.
314 /// FIXME: Implement comparison for other node types (currently
315 /// only Stmt, Decl, Type and NestedNameSpecifier return memoization data).
316 bool operator<(const DynTypedNode &Other) const {
317 if (!NodeKind.isSame(Other.NodeKind))
318 return NodeKind < Other.NodeKind;
320 if (ASTNodeKind::getFromNodeKind<QualType>().isSame(NodeKind))
321 return getUnchecked<QualType>().getAsOpaquePtr() <
322 Other.getUnchecked<QualType>().getAsOpaquePtr();
324 if (ASTNodeKind::getFromNodeKind<TypeLoc>().isBaseOf(NodeKind)) {
325 auto TLA = getUnchecked<TypeLoc>();
326 auto TLB = Other.getUnchecked<TypeLoc>();
327 return std::make_pair(TLA.getType().getAsOpaquePtr(),
328 TLA.getOpaqueData()) <
329 std::make_pair(TLB.getType().getAsOpaquePtr(),
330 TLB.getOpaqueData());
333 if (ASTNodeKind::getFromNodeKind<NestedNameSpecifierLoc>().isSame(
335 auto NNSLA = getUnchecked<NestedNameSpecifierLoc>();
336 auto NNSLB = Other.getUnchecked<NestedNameSpecifierLoc>();
337 return std::make_pair(NNSLA.getNestedNameSpecifier(),
338 NNSLA.getOpaqueData()) <
339 std::make_pair(NNSLB.getNestedNameSpecifier(),
340 NNSLB.getOpaqueData());
343 assert(getMemoizationData() && Other.getMemoizationData());
344 return getMemoizationData() < Other.getMemoizationData();
346 bool operator==(const DynTypedNode &Other) const {
347 // DynTypedNode::create() stores the exact kind of the node in NodeKind.
348 // If they contain the same node, their NodeKind must be the same.
349 if (!NodeKind.isSame(Other.NodeKind))
352 // FIXME: Implement for other types.
353 if (ASTNodeKind::getFromNodeKind<QualType>().isSame(NodeKind))
354 return getUnchecked<QualType>() == Other.getUnchecked<QualType>();
356 if (ASTNodeKind::getFromNodeKind<TypeLoc>().isBaseOf(NodeKind))
357 return getUnchecked<TypeLoc>() == Other.getUnchecked<TypeLoc>();
359 if (ASTNodeKind::getFromNodeKind<NestedNameSpecifierLoc>().isSame(NodeKind))
360 return getUnchecked<NestedNameSpecifierLoc>() ==
361 Other.getUnchecked<NestedNameSpecifierLoc>();
363 assert(getMemoizationData() && Other.getMemoizationData());
364 return getMemoizationData() == Other.getMemoizationData();
366 bool operator!=(const DynTypedNode &Other) const {
367 return !operator==(Other);
371 /// Hooks for using DynTypedNode as a key in a DenseMap.
372 struct DenseMapInfo {
373 static inline DynTypedNode getEmptyKey() {
375 Node.NodeKind = ASTNodeKind::DenseMapInfo::getEmptyKey();
378 static inline DynTypedNode getTombstoneKey() {
380 Node.NodeKind = ASTNodeKind::DenseMapInfo::getTombstoneKey();
383 static unsigned getHashValue(const DynTypedNode &Val) {
384 // FIXME: Add hashing support for the remaining types.
385 if (ASTNodeKind::getFromNodeKind<TypeLoc>().isBaseOf(Val.NodeKind)) {
386 auto TL = Val.getUnchecked<TypeLoc>();
387 return llvm::hash_combine(TL.getType().getAsOpaquePtr(),
391 if (ASTNodeKind::getFromNodeKind<NestedNameSpecifierLoc>().isSame(
393 auto NNSL = Val.getUnchecked<NestedNameSpecifierLoc>();
394 return llvm::hash_combine(NNSL.getNestedNameSpecifier(),
395 NNSL.getOpaqueData());
398 assert(Val.getMemoizationData());
399 return llvm::hash_value(Val.getMemoizationData());
401 static bool isEqual(const DynTypedNode &LHS, const DynTypedNode &RHS) {
402 auto Empty = ASTNodeKind::DenseMapInfo::getEmptyKey();
403 auto TombStone = ASTNodeKind::DenseMapInfo::getTombstoneKey();
404 return (ASTNodeKind::DenseMapInfo::isEqual(LHS.NodeKind, Empty) &&
405 ASTNodeKind::DenseMapInfo::isEqual(RHS.NodeKind, Empty)) ||
406 (ASTNodeKind::DenseMapInfo::isEqual(LHS.NodeKind, TombStone) &&
407 ASTNodeKind::DenseMapInfo::isEqual(RHS.NodeKind, TombStone)) ||
413 /// Takes care of converting from and to \c T.
414 template <typename T, typename EnablerT = void> struct BaseConverter;
416 /// Converter that uses dyn_cast<T> from a stored BaseT*.
417 template <typename T, typename BaseT> struct DynCastPtrConverter {
418 static const T *get(ASTNodeKind NodeKind, const void *Storage) {
419 if (ASTNodeKind::getFromNodeKind<T>().isBaseOf(NodeKind))
420 return &getUnchecked(NodeKind, Storage);
423 static const T &getUnchecked(ASTNodeKind NodeKind, const void *Storage) {
424 assert(ASTNodeKind::getFromNodeKind<T>().isBaseOf(NodeKind));
425 return *cast<T>(static_cast<const BaseT *>(
426 *reinterpret_cast<const void *const *>(Storage)));
428 static DynTypedNode create(const BaseT &Node) {
430 Result.NodeKind = ASTNodeKind::getFromNode(Node);
431 new (&Result.Storage) const void *(&Node);
436 /// Converter that stores T* (by pointer).
437 template <typename T> struct PtrConverter {
438 static const T *get(ASTNodeKind NodeKind, const void *Storage) {
439 if (ASTNodeKind::getFromNodeKind<T>().isSame(NodeKind))
440 return &getUnchecked(NodeKind, Storage);
443 static const T &getUnchecked(ASTNodeKind NodeKind, const void *Storage) {
444 assert(ASTNodeKind::getFromNodeKind<T>().isSame(NodeKind));
445 return *static_cast<const T *>(
446 *reinterpret_cast<const void *const *>(Storage));
448 static DynTypedNode create(const T &Node) {
450 Result.NodeKind = ASTNodeKind::getFromNodeKind<T>();
451 new (&Result.Storage) const void *(&Node);
456 /// Converter that stores T (by value).
457 template <typename T> struct ValueConverter {
458 static const T *get(ASTNodeKind NodeKind, const void *Storage) {
459 if (ASTNodeKind::getFromNodeKind<T>().isSame(NodeKind))
460 return reinterpret_cast<const T *>(Storage);
463 static const T &getUnchecked(ASTNodeKind NodeKind, const void *Storage) {
464 assert(ASTNodeKind::getFromNodeKind<T>().isSame(NodeKind));
465 return *reinterpret_cast<const T *>(Storage);
467 static DynTypedNode create(const T &Node) {
469 Result.NodeKind = ASTNodeKind::getFromNodeKind<T>();
470 new (&Result.Storage) T(Node);
475 /// Converter that stores nodes by value. It must be possible to dynamically
476 /// cast the stored node within a type hierarchy without breaking (especially
477 /// through slicing).
478 template <typename T, typename BaseT,
479 typename = std::enable_if_t<(sizeof(T) == sizeof(BaseT))>>
480 struct DynCastValueConverter {
481 static const T *get(ASTNodeKind NodeKind, const void *Storage) {
482 if (ASTNodeKind::getFromNodeKind<T>().isBaseOf(NodeKind))
483 return &getUnchecked(NodeKind, Storage);
486 static const T &getUnchecked(ASTNodeKind NodeKind, const void *Storage) {
487 assert(ASTNodeKind::getFromNodeKind<T>().isBaseOf(NodeKind));
488 return *static_cast<const T *>(reinterpret_cast<const BaseT *>(Storage));
490 static DynTypedNode create(const T &Node) {
492 Result.NodeKind = ASTNodeKind::getFromNode(Node);
493 new (&Result.Storage) T(Node);
498 ASTNodeKind NodeKind;
500 /// Stores the data of the node.
502 /// Note that we can store \c Decls, \c Stmts, \c Types,
503 /// \c NestedNameSpecifiers and \c CXXCtorInitializer by pointer as they are
504 /// guaranteed to be unique pointers pointing to dedicated storage in the AST.
505 /// \c QualTypes, \c NestedNameSpecifierLocs, \c TypeLocs,
506 /// \c TemplateArguments and \c TemplateArgumentLocs on the other hand do not
507 /// have storage or unique pointers and thus need to be stored by value.
508 llvm::AlignedCharArrayUnion<const void *, TemplateArgument,
509 TemplateArgumentLoc, NestedNameSpecifierLoc,
510 QualType, TypeLoc, ObjCProtocolLoc>
514 template <typename T>
515 struct DynTypedNode::BaseConverter<
516 T, std::enable_if_t<std::is_base_of<Decl, T>::value>>
517 : public DynCastPtrConverter<T, Decl> {};
519 template <typename T>
520 struct DynTypedNode::BaseConverter<
521 T, std::enable_if_t<std::is_base_of<Stmt, T>::value>>
522 : public DynCastPtrConverter<T, Stmt> {};
524 template <typename T>
525 struct DynTypedNode::BaseConverter<
526 T, std::enable_if_t<std::is_base_of<Type, T>::value>>
527 : public DynCastPtrConverter<T, Type> {};
529 template <typename T>
530 struct DynTypedNode::BaseConverter<
531 T, std::enable_if_t<std::is_base_of<OMPClause, T>::value>>
532 : public DynCastPtrConverter<T, OMPClause> {};
534 template <typename T>
535 struct DynTypedNode::BaseConverter<
536 T, std::enable_if_t<std::is_base_of<Attr, T>::value>>
537 : public DynCastPtrConverter<T, Attr> {};
540 struct DynTypedNode::BaseConverter<
541 NestedNameSpecifier, void> : public PtrConverter<NestedNameSpecifier> {};
544 struct DynTypedNode::BaseConverter<
545 CXXCtorInitializer, void> : public PtrConverter<CXXCtorInitializer> {};
548 struct DynTypedNode::BaseConverter<
549 TemplateArgument, void> : public ValueConverter<TemplateArgument> {};
552 struct DynTypedNode::BaseConverter<TemplateArgumentLoc, void>
553 : public ValueConverter<TemplateArgumentLoc> {};
556 struct DynTypedNode::BaseConverter<LambdaCapture, void>
557 : public ValueConverter<LambdaCapture> {};
560 struct DynTypedNode::BaseConverter<
561 TemplateName, void> : public ValueConverter<TemplateName> {};
564 struct DynTypedNode::BaseConverter<
565 NestedNameSpecifierLoc,
566 void> : public ValueConverter<NestedNameSpecifierLoc> {};
569 struct DynTypedNode::BaseConverter<QualType,
570 void> : public ValueConverter<QualType> {};
572 template <typename T>
573 struct DynTypedNode::BaseConverter<
574 T, std::enable_if_t<std::is_base_of<TypeLoc, T>::value>>
575 : public DynCastValueConverter<T, TypeLoc> {};
578 struct DynTypedNode::BaseConverter<CXXBaseSpecifier, void>
579 : public PtrConverter<CXXBaseSpecifier> {};
582 struct DynTypedNode::BaseConverter<ObjCProtocolLoc, void>
583 : public ValueConverter<ObjCProtocolLoc> {};
585 // The only operation we allow on unsupported types is \c get.
586 // This allows to conveniently use \c DynTypedNode when having an arbitrary
587 // AST node that is not supported, but prevents misuse - a user cannot create
588 // a DynTypedNode from arbitrary types.
589 template <typename T, typename EnablerT> struct DynTypedNode::BaseConverter {
590 static const T *get(ASTNodeKind NodeKind, const char Storage[]) {
595 } // end namespace clang
600 struct DenseMapInfo<clang::ASTNodeKind> : clang::ASTNodeKind::DenseMapInfo {};
603 struct DenseMapInfo<clang::DynTypedNode> : clang::DynTypedNode::DenseMapInfo {};
605 } // end namespace llvm