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