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
getTraversalKind()60 TraversalKind getTraversalKind() const { return Traversal; }
setTraversalKind(TraversalKind TK)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 class ParentMap;
68
69 private:
70 ASTContext &ASTCtx;
71 TraversalKind Traversal = TK_AsIs;
72 std::unique_ptr<ParentMap> Parents;
73 };
74
75 class TraversalKindScope {
76 ParentMapContext &Ctx;
77 TraversalKind TK = TK_AsIs;
78
79 public:
TraversalKindScope(ASTContext & ASTCtx,llvm::Optional<TraversalKind> ScopeTK)80 TraversalKindScope(ASTContext &ASTCtx, llvm::Optional<TraversalKind> ScopeTK)
81 : Ctx(ASTCtx.getParentMapContext()) {
82 TK = Ctx.getTraversalKind();
83 if (ScopeTK)
84 Ctx.setTraversalKind(*ScopeTK);
85 }
86
~TraversalKindScope()87 ~TraversalKindScope() { Ctx.setTraversalKind(TK); }
88 };
89
90 /// Container for either a single DynTypedNode or for an ArrayRef to
91 /// DynTypedNode. For use with ParentMap.
92 class DynTypedNodeList {
93 llvm::AlignedCharArrayUnion<DynTypedNode, ArrayRef<DynTypedNode>> Storage;
94 bool IsSingleNode;
95
96 public:
DynTypedNodeList(const DynTypedNode & N)97 DynTypedNodeList(const DynTypedNode &N) : IsSingleNode(true) {
98 new (&Storage) DynTypedNode(N);
99 }
100
DynTypedNodeList(ArrayRef<DynTypedNode> A)101 DynTypedNodeList(ArrayRef<DynTypedNode> A) : IsSingleNode(false) {
102 new (&Storage) ArrayRef<DynTypedNode>(A);
103 }
104
begin()105 const DynTypedNode *begin() const {
106 if (!IsSingleNode)
107 return reinterpret_cast<const ArrayRef<DynTypedNode> *>(&Storage)
108 ->begin();
109 return reinterpret_cast<const DynTypedNode *>(&Storage);
110 }
111
end()112 const DynTypedNode *end() const {
113 if (!IsSingleNode)
114 return reinterpret_cast<const ArrayRef<DynTypedNode> *>(&Storage)->end();
115 return reinterpret_cast<const DynTypedNode *>(&Storage) + 1;
116 }
117
size()118 size_t size() const { return end() - begin(); }
empty()119 bool empty() const { return begin() == end(); }
120
121 const DynTypedNode &operator[](size_t N) const {
122 assert(N < size() && "Out of bounds!");
123 return *(begin() + N);
124 }
125 };
126
127 template <typename NodeT>
getParents(const NodeT & Node)128 inline DynTypedNodeList ParentMapContext::getParents(const NodeT &Node) {
129 return getParents(DynTypedNode::create(Node));
130 }
131
132 template <typename NodeT>
getParents(const NodeT & Node)133 inline DynTypedNodeList ASTContext::getParents(const NodeT &Node) {
134 return getParentMapContext().getParents(Node);
135 }
136
137 template <>
getParents(const DynTypedNode & Node)138 inline DynTypedNodeList ASTContext::getParents(const DynTypedNode &Node) {
139 return getParentMapContext().getParents(Node);
140 }
141
142 } // namespace clang
143
144 #endif
145