3ab55fb3d3095b742bdf0959b509d4b7886718d0
[lldb.git] / clang / include / clang / AST / ParentMapContext.h
1 //===- ParentMapContext.h - Map of parents using DynTypedNode -------*- 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 // Similar to ParentMap.h, but generalizes to non-Stmt nodes, which can have
10 // multiple parents.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #ifndef LLVM_CLANG_AST_PARENTMAPCONTEXT_H
15 #define LLVM_CLANG_AST_PARENTMAPCONTEXT_H
16
17 #include "clang/AST/ASTContext.h"
18 #include "clang/AST/ASTTypeTraits.h"
19
20 namespace clang {
21 class DynTypedNodeList;
22
23 class ParentMapContext {
24 public:
25   ParentMapContext(ASTContext &Ctx);
26
27   ~ParentMapContext();
28
29   /// Returns the parents of the given node (within the traversal scope).
30   ///
31   /// Note that this will lazily compute the parents of all nodes
32   /// and store them for later retrieval. Thus, the first call is O(n)
33   /// in the number of AST nodes.
34   ///
35   /// Caveats and FIXMEs:
36   /// Calculating the parent map over all AST nodes will need to load the
37   /// full AST. This can be undesirable in the case where the full AST is
38   /// expensive to create (for example, when using precompiled header
39   /// preambles). Thus, there are good opportunities for optimization here.
40   /// One idea is to walk the given node downwards, looking for references
41   /// to declaration contexts - once a declaration context is found, compute
42   /// the parent map for the declaration context; if that can satisfy the
43   /// request, loading the whole AST can be avoided. Note that this is made
44   /// more complex by statements in templates having multiple parents - those
45   /// problems can be solved by building closure over the templated parts of
46   /// the AST, which also avoids touching large parts of the AST.
47   /// Additionally, we will want to add an interface to already give a hint
48   /// where to search for the parents, for example when looking at a statement
49   /// inside a certain function.
50   ///
51   /// 'NodeT' can be one of Decl, Stmt, Type, TypeLoc,
52   /// NestedNameSpecifier or NestedNameSpecifierLoc.
53   template <typename NodeT> DynTypedNodeList getParents(const NodeT &Node);
54
55   DynTypedNodeList getParents(const DynTypedNode &Node);
56
57   /// Clear parent maps.
58   void clear();
59
60   TraversalKind getTraversalKind() const { return Traversal; }
61   void setTraversalKind(TraversalKind TK) { Traversal = TK; }
62
63   const Expr *traverseIgnored(const Expr *E) const;
64   Expr *traverseIgnored(Expr *E) const;
65   DynTypedNode traverseIgnored(const DynTypedNode &N) const;
66
67 private:
68   ASTContext &ASTCtx;
69   class ParentMap;
70   TraversalKind Traversal = TK_AsIs;
71   std::unique_ptr<ParentMap> Parents;
72 };
73
74 class TraversalKindScope {
75   ParentMapContext &Ctx;
76   TraversalKind TK = TK_AsIs;
77
78 public:
79   TraversalKindScope(ASTContext &ASTCtx, llvm::Optional<TraversalKind> ScopeTK)
80       : Ctx(ASTCtx.getParentMapContext()) {
81     TK = Ctx.getTraversalKind();
82     if (ScopeTK)
83       Ctx.setTraversalKind(*ScopeTK);
84   }
85
86   ~TraversalKindScope() { Ctx.setTraversalKind(TK); }
87 };
88
89 /// Container for either a single DynTypedNode or for an ArrayRef to
90 /// DynTypedNode. For use with ParentMap.
91 class DynTypedNodeList {
92   using DynTypedNode = DynTypedNode;
93
94   llvm::AlignedCharArrayUnion<DynTypedNode, ArrayRef<DynTypedNode>> Storage;
95   bool IsSingleNode;
96
97 public:
98   DynTypedNodeList(const DynTypedNode &N) : IsSingleNode(true) {
99     new (Storage.buffer) DynTypedNode(N);
100   }
101
102   DynTypedNodeList(ArrayRef<DynTypedNode> A) : IsSingleNode(false) {
103     new (Storage.buffer) ArrayRef<DynTypedNode>(A);
104   }
105
106   const DynTypedNode *begin() const {
107     if (!IsSingleNode)
108       return reinterpret_cast<const ArrayRef<DynTypedNode> *>(Storage.buffer)
109           ->begin();
110     return reinterpret_cast<const DynTypedNode *>(Storage.buffer);
111   }
112
113   const DynTypedNode *end() const {
114     if (!IsSingleNode)
115       return reinterpret_cast<const ArrayRef<DynTypedNode> *>(Storage.buffer)
116           ->end();
117     return reinterpret_cast<const DynTypedNode *>(Storage.buffer) + 1;
118   }
119
120   size_t size() const { return end() - begin(); }
121   bool empty() const { return begin() == end(); }
122
123   const DynTypedNode &operator[](size_t N) const {
124     assert(N < size() && "Out of bounds!");
125     return *(begin() + N);
126   }
127 };
128
129 template <typename NodeT>
130 inline DynTypedNodeList ParentMapContext::getParents(const NodeT &Node) {
131   return getParents(DynTypedNode::create(Node));
132 }
133
134 template <typename NodeT>
135 inline DynTypedNodeList ASTContext::getParents(const NodeT &Node) {
136   return getParentMapContext().getParents(Node);
137 }
138
139 template <>
140 inline DynTypedNodeList ASTContext::getParents(const DynTypedNode &Node) {
141   return getParentMapContext().getParents(Node);
142 }
143
144 } // namespace clang
145
146 #endif