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