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