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