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
27namespace llvm {
28
29class raw_ostream;
30
31}
32
33namespace clang {
34
35struct PrintingPolicy;
36
37/// Defines how we descend a level in the AST when we pass
38/// through expressions.
39enum 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.
52class ASTNodeKind {
53public:
54 /// Empty identifier. It matches nothing.
55 ASTNodeKind() : KindId(NKI_None) {}
56
57 /// Construct an identifier for T.
58 template <class T>
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.
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()
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.
108 static inline ASTNodeKind getEmptyKey() { return ASTNodeKind(); }
109 // NKI_NumberOfKinds is not a valid value, so it is good for a
110 // tombstone key.
111 static inline ASTNodeKind getTombstoneKey() {
112 return ASTNodeKind(NKI_NumberOfKinds);
113 }
114 static unsigned getHashValue(const ASTNodeKind &Val) { return Val.KindId; }
115 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.
122 bool hasPointerIdentity() const {
123 return KindId > NKI_LastKindWithoutPointerIdentity;
124 }
125
126private:
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.
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 };
192KIND_TO_KIND_ID(CXXCtorInitializer)
193KIND_TO_KIND_ID(TemplateArgument)
194KIND_TO_KIND_ID(TemplateArgumentLoc)
195KIND_TO_KIND_ID(TemplateName)
196KIND_TO_KIND_ID(NestedNameSpecifier)
197KIND_TO_KIND_ID(NestedNameSpecifierLoc)
198KIND_TO_KIND_ID(QualType)
199KIND_TO_KIND_ID(TypeLoc)
200KIND_TO_KIND_ID(Decl)
201KIND_TO_KIND_ID(Stmt)
202KIND_TO_KIND_ID(Type)
203KIND_TO_KIND_ID(OMPClause)
204KIND_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
216inline 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.
233class DynTypedNode {
234public:
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
390private:
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
469template <typename T>
470struct DynTypedNode::BaseConverter<
471 T, std::enable_if_t<std::is_base_of<Decl, T>::value>>
472 : public DynCastPtrConverter<T, Decl> {};
473
474template <typename T>
475struct DynTypedNode::BaseConverter<
476 T, std::enable_if_t<std::is_base_of<Stmt, T>::value>>
477 : public DynCastPtrConverter<T, Stmt> {};
478
479template <typename T>
480struct DynTypedNode::BaseConverter<
481 T, std::enable_if_t<std::is_base_of<Type, T>::value>>
482 : public DynCastPtrConverter<T, Type> {};
483
484template <typename T>
485struct DynTypedNode::BaseConverter<
486 T, std::enable_if_t<std::is_base_of<OMPClause, T>::value>>
487 : public DynCastPtrConverter<T, OMPClause> {};
488
489template <>
490struct DynTypedNode::BaseConverter<
491 NestedNameSpecifier, void> : public PtrConverter<NestedNameSpecifier> {};
492
493template <>
494struct DynTypedNode::BaseConverter<
495 CXXCtorInitializer, void> : public PtrConverter<CXXCtorInitializer> {};
496
497template <>
498struct DynTypedNode::BaseConverter<
499 TemplateArgument, void> : public ValueConverter<TemplateArgument> {};
500
501template <>
502struct DynTypedNode::BaseConverter<TemplateArgumentLoc, void>
503 : public ValueConverter<TemplateArgumentLoc> {};
504
505template <>
506struct DynTypedNode::BaseConverter<
507 TemplateName, void> : public ValueConverter<TemplateName> {};
508
509template <>
510struct DynTypedNode::BaseConverter<
511 NestedNameSpecifierLoc,
512 void> : public ValueConverter<NestedNameSpecifierLoc> {};
513
514template <>
515struct DynTypedNode::BaseConverter<QualType,
516 void> : public ValueConverter<QualType> {};
517
518template <>
519struct DynTypedNode::BaseConverter<
520 TypeLoc, void> : public ValueConverter<TypeLoc> {};
521
522template <>
523struct 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.
530template <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
538namespace llvm {
539
540template <>
541struct DenseMapInfo<clang::ASTNodeKind> : clang::ASTNodeKind::DenseMapInfo {};
542
543template <>
544struct DenseMapInfo<clang::DynTypedNode> : clang::DynTypedNode::DenseMapInfo {};
545
546} // end namespace llvm
547
548#endif
549