/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/AST/ParentMapContext.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- ParentMapContext.cpp - 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.cpp, but generalizes to non-Stmt nodes, which can have |
10 | | // multiple parents. |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #include "clang/AST/ParentMapContext.h" |
15 | | #include "clang/AST/RecursiveASTVisitor.h" |
16 | | #include "clang/AST/Decl.h" |
17 | | #include "clang/AST/Expr.h" |
18 | | #include "clang/AST/TemplateBase.h" |
19 | | |
20 | | using namespace clang; |
21 | | |
22 | 19.8k | ParentMapContext::ParentMapContext(ASTContext &Ctx) : ASTCtx(Ctx) {} |
23 | | |
24 | 19.8k | ParentMapContext::~ParentMapContext() = default; |
25 | | |
26 | 70 | void ParentMapContext::clear() { Parents.reset(); } |
27 | | |
28 | 355k | const Expr *ParentMapContext::traverseIgnored(const Expr *E) const { |
29 | 355k | return traverseIgnored(const_cast<Expr *>(E)); |
30 | 355k | } |
31 | | |
32 | 395k | Expr *ParentMapContext::traverseIgnored(Expr *E) const { |
33 | 395k | if (!E) |
34 | 0 | return nullptr; |
35 | | |
36 | 395k | switch (Traversal) { |
37 | 360k | case TK_AsIs: |
38 | 360k | return E; |
39 | 34.4k | case TK_IgnoreUnlessSpelledInSource: |
40 | 34.4k | return E->IgnoreUnlessSpelledInSource(); |
41 | 0 | } |
42 | 0 | llvm_unreachable("Invalid Traversal type!"); |
43 | 0 | } |
44 | | |
45 | 759k | DynTypedNode ParentMapContext::traverseIgnored(const DynTypedNode &N) const { |
46 | 759k | if (const auto *E = N.get<Expr>()) { |
47 | 355k | return DynTypedNode::create(*traverseIgnored(E)); |
48 | 355k | } |
49 | 403k | return N; |
50 | 403k | } |
51 | | |
52 | | class ParentMapContext::ParentMap { |
53 | | /// Contains parents of a node. |
54 | | using ParentVector = llvm::SmallVector<DynTypedNode, 2>; |
55 | | |
56 | | /// Maps from a node to its parents. This is used for nodes that have |
57 | | /// pointer identity only, which are more common and we can save space by |
58 | | /// only storing a unique pointer to them. |
59 | | using ParentMapPointers = |
60 | | llvm::DenseMap<const void *, |
61 | | llvm::PointerUnion<const Decl *, const Stmt *, |
62 | | DynTypedNode *, ParentVector *>>; |
63 | | |
64 | | /// Parent map for nodes without pointer identity. We store a full |
65 | | /// DynTypedNode for all keys. |
66 | | using ParentMapOtherNodes = |
67 | | llvm::DenseMap<DynTypedNode, |
68 | | llvm::PointerUnion<const Decl *, const Stmt *, |
69 | | DynTypedNode *, ParentVector *>>; |
70 | | |
71 | | ParentMapPointers PointerParents; |
72 | | ParentMapOtherNodes OtherParents; |
73 | | class ASTVisitor; |
74 | | |
75 | | static DynTypedNode |
76 | 17.2k | getSingleDynTypedNodeFromParentMap(ParentMapPointers::mapped_type U) { |
77 | 17.2k | if (const auto *D = U.dyn_cast<const Decl *>()) |
78 | 7.64k | return DynTypedNode::create(*D); |
79 | 9.56k | if (const auto *S = U.dyn_cast<const Stmt *>()) |
80 | 6.87k | return DynTypedNode::create(*S); |
81 | 2.68k | return *U.get<DynTypedNode *>(); |
82 | 2.68k | } |
83 | | |
84 | | template <typename NodeTy, typename MapTy> |
85 | | static DynTypedNodeList getDynNodeFromMap(const NodeTy &Node, |
86 | 17.6k | const MapTy &Map) { |
87 | 17.6k | auto I = Map.find(Node); |
88 | 17.6k | if (I == Map.end()) { |
89 | 938 | return llvm::ArrayRef<DynTypedNode>(); |
90 | 938 | } |
91 | 16.7k | if (const auto *V = I->second.template dyn_cast<ParentVector *>()) { |
92 | 100 | return llvm::makeArrayRef(*V); |
93 | 100 | } |
94 | 16.6k | return getSingleDynTypedNodeFromParentMap(I->second); |
95 | 16.6k | } clang::DynTypedNodeList clang::ParentMapContext::ParentMap::getDynNodeFromMap<void const*, llvm::DenseMap<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<void const*>, llvm::detail::DenseMapPair<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > > >(void const* const&, llvm::DenseMap<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<void const*>, llvm::detail::DenseMapPair<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > > const&) Line | Count | Source | 86 | 12.0k | const MapTy &Map) { | 87 | 12.0k | auto I = Map.find(Node); | 88 | 12.0k | if (I == Map.end()) { | 89 | 887 | return llvm::ArrayRef<DynTypedNode>(); | 90 | 887 | } | 91 | 11.1k | if (const auto *V = I->second.template dyn_cast<ParentVector *>()) { | 92 | 89 | return llvm::makeArrayRef(*V); | 93 | 89 | } | 94 | 11.0k | return getSingleDynTypedNodeFromParentMap(I->second); | 95 | 11.0k | } |
clang::DynTypedNodeList clang::ParentMapContext::ParentMap::getDynNodeFromMap<clang::DynTypedNode, llvm::DenseMap<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<clang::DynTypedNode>, llvm::detail::DenseMapPair<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > > >(clang::DynTypedNode const&, llvm::DenseMap<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<clang::DynTypedNode>, llvm::detail::DenseMapPair<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > > const&) Line | Count | Source | 86 | 5.62k | const MapTy &Map) { | 87 | 5.62k | auto I = Map.find(Node); | 88 | 5.62k | if (I == Map.end()) { | 89 | 51 | return llvm::ArrayRef<DynTypedNode>(); | 90 | 51 | } | 91 | 5.57k | if (const auto *V = I->second.template dyn_cast<ParentVector *>()) { | 92 | 11 | return llvm::makeArrayRef(*V); | 93 | 11 | } | 94 | 5.56k | return getSingleDynTypedNodeFromParentMap(I->second); | 95 | 5.56k | } |
|
96 | | |
97 | | public: |
98 | | ParentMap(ASTContext &Ctx); |
99 | 1.15k | ~ParentMap() { |
100 | 42.7k | for (const auto &Entry : PointerParents) { |
101 | 42.7k | if (Entry.second.is<DynTypedNode *>()) { |
102 | 1.22k | delete Entry.second.get<DynTypedNode *>(); |
103 | 41.5k | } else if (Entry.second.is<ParentVector *>()) { |
104 | 256 | delete Entry.second.get<ParentVector *>(); |
105 | 256 | } |
106 | 42.7k | } |
107 | 23.6k | for (const auto &Entry : OtherParents) { |
108 | 23.6k | if (Entry.second.is<DynTypedNode *>()) { |
109 | 9.19k | delete Entry.second.get<DynTypedNode *>(); |
110 | 14.4k | } else if (Entry.second.is<ParentVector *>()) { |
111 | 310 | delete Entry.second.get<ParentVector *>(); |
112 | 310 | } |
113 | 23.6k | } |
114 | 1.15k | } |
115 | | |
116 | 17.6k | DynTypedNodeList getParents(TraversalKind TK, const DynTypedNode &Node) { |
117 | 17.6k | if (Node.getNodeKind().hasPointerIdentity()) { |
118 | 12.0k | auto ParentList = |
119 | 12.0k | getDynNodeFromMap(Node.getMemoizationData(), PointerParents); |
120 | 12.0k | if (ParentList.size() == 1 && TK == TK_IgnoreUnlessSpelledInSource11.1k ) { |
121 | 3.41k | const auto *E = ParentList[0].get<Expr>(); |
122 | 3.41k | const auto *Child = Node.get<Expr>(); |
123 | 3.41k | if (E && Child55 ) |
124 | 53 | return AscendIgnoreUnlessSpelledInSource(E, Child); |
125 | 11.9k | } |
126 | 11.9k | return ParentList; |
127 | 11.9k | } |
128 | 5.62k | return getDynNodeFromMap(Node, OtherParents); |
129 | 5.62k | } |
130 | | |
131 | | DynTypedNodeList AscendIgnoreUnlessSpelledInSource(const Expr *E, |
132 | 53 | const Expr *Child) { |
133 | | |
134 | 86 | auto ShouldSkip = [](const Expr *E, const Expr *Child) { |
135 | 86 | if (isa<ImplicitCastExpr>(E)) |
136 | 39 | return true; |
137 | | |
138 | 47 | if (isa<FullExpr>(E)) |
139 | 1 | return true; |
140 | | |
141 | 46 | if (isa<MaterializeTemporaryExpr>(E)) |
142 | 1 | return true; |
143 | | |
144 | 45 | if (isa<CXXBindTemporaryExpr>(E)) |
145 | 0 | return true; |
146 | | |
147 | 45 | if (isa<ParenExpr>(E)) |
148 | 2 | return true; |
149 | | |
150 | 43 | if (isa<ExprWithCleanups>(E)) |
151 | 0 | return true; |
152 | | |
153 | 43 | auto SR = Child->getSourceRange(); |
154 | | |
155 | 43 | if (const auto *C = dyn_cast<CXXFunctionalCastExpr>(E)) { |
156 | 2 | if (C->getSourceRange() == SR) |
157 | 2 | return true; |
158 | 41 | } |
159 | | |
160 | 41 | if (const auto *C = dyn_cast<CXXConstructExpr>(E)) { |
161 | 25 | if (C->getSourceRange() == SR || C->isElidable()12 ) |
162 | 13 | return true; |
163 | 28 | } |
164 | | |
165 | 28 | if (const auto *C = dyn_cast<CXXMemberCallExpr>(E)) { |
166 | 2 | if (C->getSourceRange() == SR) |
167 | 2 | return true; |
168 | 26 | } |
169 | | |
170 | 26 | if (const auto *C = dyn_cast<MemberExpr>(E)) { |
171 | 2 | if (C->getSourceRange() == SR) |
172 | 2 | return true; |
173 | 24 | } |
174 | 24 | return false; |
175 | 24 | }; |
176 | | |
177 | 86 | while (ShouldSkip(E, Child)) { |
178 | 62 | auto It = PointerParents.find(E); |
179 | 62 | if (It == PointerParents.end()) |
180 | 0 | break; |
181 | 62 | const auto *S = It->second.dyn_cast<const Stmt *>(); |
182 | 62 | if (!S) { |
183 | 13 | if (auto *Vec = It->second.dyn_cast<ParentVector *>()) |
184 | 4 | return llvm::makeArrayRef(*Vec); |
185 | 9 | return getSingleDynTypedNodeFromParentMap(It->second); |
186 | 9 | } |
187 | 49 | const auto *P = dyn_cast<Expr>(S); |
188 | 49 | if (!P) |
189 | 16 | return DynTypedNode::create(*S); |
190 | 33 | Child = E; |
191 | 33 | E = P; |
192 | 33 | } |
193 | 24 | return DynTypedNode::create(*E); |
194 | 53 | } |
195 | | }; |
196 | | |
197 | | /// Template specializations to abstract away from pointers and TypeLocs. |
198 | | /// @{ |
199 | 27.3k | template <typename T> static DynTypedNode createDynTypedNode(const T &Node) { |
200 | 27.3k | return DynTypedNode::create(*Node); |
201 | 27.3k | } |
202 | 23.2k | template <> DynTypedNode createDynTypedNode(const TypeLoc &Node) { |
203 | 23.2k | return DynTypedNode::create(Node); |
204 | 23.2k | } |
205 | | template <> |
206 | 798 | DynTypedNode createDynTypedNode(const NestedNameSpecifierLoc &Node) { |
207 | 798 | return DynTypedNode::create(Node); |
208 | 798 | } |
209 | | /// @} |
210 | | |
211 | | /// A \c RecursiveASTVisitor that builds a map from nodes to their |
212 | | /// parents as defined by the \c RecursiveASTVisitor. |
213 | | /// |
214 | | /// Note that the relationship described here is purely in terms of AST |
215 | | /// traversal - there are other relationships (for example declaration context) |
216 | | /// in the AST that are better modeled by special matchers. |
217 | | class ParentMapContext::ParentMap::ASTVisitor |
218 | | : public RecursiveASTVisitor<ASTVisitor> { |
219 | | public: |
220 | 1.15k | ASTVisitor(ParentMap &Map) : Map(Map) {} |
221 | | |
222 | | private: |
223 | | friend class RecursiveASTVisitor<ASTVisitor>; |
224 | | |
225 | | using VisitorBase = RecursiveASTVisitor<ASTVisitor>; |
226 | | |
227 | 1.09k | bool shouldVisitTemplateInstantiations() const { return true; } |
228 | | |
229 | 32.3k | bool shouldVisitImplicitCode() const { return true; } |
230 | | |
231 | | /// Record the parent of the node we're visiting. |
232 | | /// MapNode is the child, the parent is on top of ParentStack. |
233 | | /// Parents is the parent storage (either PointerParents or OtherParents). |
234 | | template <typename MapNodeTy, typename MapTy> |
235 | 68.3k | void addParent(MapNodeTy MapNode, MapTy *Parents) { |
236 | 68.3k | if (ParentStack.empty()) |
237 | 1.15k | return; |
238 | | |
239 | | // FIXME: Currently we add the same parent multiple times, but only |
240 | | // when no memoization data is available for the type. |
241 | | // For example when we visit all subexpressions of template |
242 | | // instantiations; this is suboptimal, but benign: the only way to |
243 | | // visit those is with hasAncestor / hasParent, and those do not create |
244 | | // new matches. |
245 | | // The plan is to enable DynTypedNode to be storable in a map or hash |
246 | | // map. The main problem there is to implement hash functions / |
247 | | // comparison operators for all types that DynTypedNode supports that |
248 | | // do not have pointer identity. |
249 | 67.2k | auto &NodeOrVector = (*Parents)[MapNode]; |
250 | 67.2k | if (NodeOrVector.isNull()) { |
251 | 66.4k | if (const auto *D = ParentStack.back().get<Decl>()) |
252 | 41.2k | NodeOrVector = D; |
253 | 25.1k | else if (const auto *S = ParentStack.back().get<Stmt>()) |
254 | 14.5k | NodeOrVector = S; |
255 | 10.5k | else |
256 | 10.5k | NodeOrVector = new DynTypedNode(ParentStack.back()); |
257 | 793 | } else { |
258 | 793 | if (!NodeOrVector.template is<ParentVector *>()) { |
259 | 566 | auto *Vector = new ParentVector( |
260 | 566 | 1, getSingleDynTypedNodeFromParentMap(NodeOrVector)); |
261 | 566 | delete NodeOrVector.template dyn_cast<DynTypedNode *>(); |
262 | 566 | NodeOrVector = Vector; |
263 | 566 | } |
264 | | |
265 | 793 | auto *Vector = NodeOrVector.template get<ParentVector *>(); |
266 | | // Skip duplicates for types that have memoization data. |
267 | | // We must check that the type has memoization data before calling |
268 | | // std::find() because DynTypedNode::operator== can't compare all |
269 | | // types. |
270 | 793 | bool Found = ParentStack.back().getMemoizationData() && |
271 | 546 | std::find(Vector->begin(), Vector->end(), |
272 | 546 | ParentStack.back()) != Vector->end(); |
273 | 793 | if (!Found) |
274 | 567 | Vector->push_back(ParentStack.back()); |
275 | 793 | } |
276 | 67.2k | } void clang::ParentMapContext::ParentMap::ASTVisitor::addParent<clang::Decl*, llvm::DenseMap<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<void const*>, llvm::detail::DenseMapPair<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > > >(clang::Decl*, llvm::DenseMap<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<void const*>, llvm::detail::DenseMapPair<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > >*) Line | Count | Source | 235 | 27.3k | void addParent(MapNodeTy MapNode, MapTy *Parents) { | 236 | 27.3k | if (ParentStack.empty()) | 237 | 1.15k | return; | 238 | | | 239 | | // FIXME: Currently we add the same parent multiple times, but only | 240 | | // when no memoization data is available for the type. | 241 | | // For example when we visit all subexpressions of template | 242 | | // instantiations; this is suboptimal, but benign: the only way to | 243 | | // visit those is with hasAncestor / hasParent, and those do not create | 244 | | // new matches. | 245 | | // The plan is to enable DynTypedNode to be storable in a map or hash | 246 | | // map. The main problem there is to implement hash functions / | 247 | | // comparison operators for all types that DynTypedNode supports that | 248 | | // do not have pointer identity. | 249 | 26.2k | auto &NodeOrVector = (*Parents)[MapNode]; | 250 | 26.2k | if (NodeOrVector.isNull()) { | 251 | 26.0k | if (const auto *D = ParentStack.back().get<Decl>()) | 252 | 22.9k | NodeOrVector = D; | 253 | 3.11k | else if (const auto *S = ParentStack.back().get<Stmt>()) | 254 | 1.89k | NodeOrVector = S; | 255 | 1.21k | else | 256 | 1.21k | NodeOrVector = new DynTypedNode(ParentStack.back()); | 257 | 189 | } else { | 258 | 189 | if (!NodeOrVector.template is<ParentVector *>()) { | 259 | 77 | auto *Vector = new ParentVector( | 260 | 77 | 1, getSingleDynTypedNodeFromParentMap(NodeOrVector)); | 261 | 77 | delete NodeOrVector.template dyn_cast<DynTypedNode *>(); | 262 | 77 | NodeOrVector = Vector; | 263 | 77 | } | 264 | | | 265 | 189 | auto *Vector = NodeOrVector.template get<ParentVector *>(); | 266 | | // Skip duplicates for types that have memoization data. | 267 | | // We must check that the type has memoization data before calling | 268 | | // std::find() because DynTypedNode::operator== can't compare all | 269 | | // types. | 270 | 189 | bool Found = ParentStack.back().getMemoizationData() && | 271 | 53 | std::find(Vector->begin(), Vector->end(), | 272 | 53 | ParentStack.back()) != Vector->end(); | 273 | 189 | if (!Found) | 274 | 189 | Vector->push_back(ParentStack.back()); | 275 | 189 | } | 276 | 26.2k | } |
void clang::ParentMapContext::ParentMap::ASTVisitor::addParent<clang::DynTypedNode, llvm::DenseMap<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<clang::DynTypedNode>, llvm::detail::DenseMapPair<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > > >(clang::DynTypedNode, llvm::DenseMap<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<clang::DynTypedNode>, llvm::detail::DenseMapPair<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > >*) Line | Count | Source | 235 | 24.0k | void addParent(MapNodeTy MapNode, MapTy *Parents) { | 236 | 24.0k | if (ParentStack.empty()) | 237 | 0 | return; | 238 | | | 239 | | // FIXME: Currently we add the same parent multiple times, but only | 240 | | // when no memoization data is available for the type. | 241 | | // For example when we visit all subexpressions of template | 242 | | // instantiations; this is suboptimal, but benign: the only way to | 243 | | // visit those is with hasAncestor / hasParent, and those do not create | 244 | | // new matches. | 245 | | // The plan is to enable DynTypedNode to be storable in a map or hash | 246 | | // map. The main problem there is to implement hash functions / | 247 | | // comparison operators for all types that DynTypedNode supports that | 248 | | // do not have pointer identity. | 249 | 24.0k | auto &NodeOrVector = (*Parents)[MapNode]; | 250 | 24.0k | if (NodeOrVector.isNull()) { | 251 | 23.6k | if (const auto *D = ParentStack.back().get<Decl>()) | 252 | 13.8k | NodeOrVector = D; | 253 | 9.85k | else if (const auto *S = ParentStack.back().get<Stmt>()) | 254 | 555 | NodeOrVector = S; | 255 | 9.29k | else | 256 | 9.29k | NodeOrVector = new DynTypedNode(ParentStack.back()); | 257 | 416 | } else { | 258 | 416 | if (!NodeOrVector.template is<ParentVector *>()) { | 259 | 310 | auto *Vector = new ParentVector( | 260 | 310 | 1, getSingleDynTypedNodeFromParentMap(NodeOrVector)); | 261 | 310 | delete NodeOrVector.template dyn_cast<DynTypedNode *>(); | 262 | 310 | NodeOrVector = Vector; | 263 | 310 | } | 264 | | | 265 | 416 | auto *Vector = NodeOrVector.template get<ParentVector *>(); | 266 | | // Skip duplicates for types that have memoization data. | 267 | | // We must check that the type has memoization data before calling | 268 | | // std::find() because DynTypedNode::operator== can't compare all | 269 | | // types. | 270 | 416 | bool Found = ParentStack.back().getMemoizationData() && | 271 | 305 | std::find(Vector->begin(), Vector->end(), | 272 | 305 | ParentStack.back()) != Vector->end(); | 273 | 416 | if (!Found) | 274 | 279 | Vector->push_back(ParentStack.back()); | 275 | 416 | } | 276 | 24.0k | } |
void clang::ParentMapContext::ParentMap::ASTVisitor::addParent<clang::Stmt*, llvm::DenseMap<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<void const*>, llvm::detail::DenseMapPair<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > > >(clang::Stmt*, llvm::DenseMap<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<void const*>, llvm::detail::DenseMapPair<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > >*) Line | Count | Source | 235 | 16.8k | void addParent(MapNodeTy MapNode, MapTy *Parents) { | 236 | 16.8k | if (ParentStack.empty()) | 237 | 0 | return; | 238 | | | 239 | | // FIXME: Currently we add the same parent multiple times, but only | 240 | | // when no memoization data is available for the type. | 241 | | // For example when we visit all subexpressions of template | 242 | | // instantiations; this is suboptimal, but benign: the only way to | 243 | | // visit those is with hasAncestor / hasParent, and those do not create | 244 | | // new matches. | 245 | | // The plan is to enable DynTypedNode to be storable in a map or hash | 246 | | // map. The main problem there is to implement hash functions / | 247 | | // comparison operators for all types that DynTypedNode supports that | 248 | | // do not have pointer identity. | 249 | 16.8k | auto &NodeOrVector = (*Parents)[MapNode]; | 250 | 16.8k | if (NodeOrVector.isNull()) { | 251 | 16.6k | if (const auto *D = ParentStack.back().get<Decl>()) | 252 | 4.51k | NodeOrVector = D; | 253 | 12.1k | else if (const auto *S = ParentStack.back().get<Stmt>()) | 254 | 12.1k | NodeOrVector = S; | 255 | 54 | else | 256 | 54 | NodeOrVector = new DynTypedNode(ParentStack.back()); | 257 | 188 | } else { | 258 | 188 | if (!NodeOrVector.template is<ParentVector *>()) { | 259 | 179 | auto *Vector = new ParentVector( | 260 | 179 | 1, getSingleDynTypedNodeFromParentMap(NodeOrVector)); | 261 | 179 | delete NodeOrVector.template dyn_cast<DynTypedNode *>(); | 262 | 179 | NodeOrVector = Vector; | 263 | 179 | } | 264 | | | 265 | 188 | auto *Vector = NodeOrVector.template get<ParentVector *>(); | 266 | | // Skip duplicates for types that have memoization data. | 267 | | // We must check that the type has memoization data before calling | 268 | | // std::find() because DynTypedNode::operator== can't compare all | 269 | | // types. | 270 | 188 | bool Found = ParentStack.back().getMemoizationData() && | 271 | 188 | std::find(Vector->begin(), Vector->end(), | 272 | 188 | ParentStack.back()) != Vector->end(); | 273 | 188 | if (!Found) | 274 | 99 | Vector->push_back(ParentStack.back()); | 275 | 188 | } | 276 | 16.8k | } |
|
277 | | |
278 | | template <typename T, typename MapNodeTy, typename BaseTraverseFn, |
279 | | typename MapTy> |
280 | | bool TraverseNode(T Node, MapNodeTy MapNode, BaseTraverseFn BaseTraverse, |
281 | 71.7k | MapTy *Parents) { |
282 | 71.7k | if (!Node) |
283 | 20.2k | return true; |
284 | 51.4k | addParent(MapNode, Parents); |
285 | 51.4k | ParentStack.push_back(createDynTypedNode(Node)); |
286 | 51.4k | bool Result = BaseTraverse(); |
287 | 51.4k | ParentStack.pop_back(); |
288 | 51.4k | return Result; |
289 | 51.4k | } bool clang::ParentMapContext::ParentMap::ASTVisitor::TraverseNode<clang::Decl*, clang::Decl*, clang::ParentMapContext::ParentMap::ASTVisitor::TraverseDecl(clang::Decl*)::'lambda'(), llvm::DenseMap<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<void const*>, llvm::detail::DenseMapPair<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > > >(clang::Decl*, clang::Decl*, clang::ParentMapContext::ParentMap::ASTVisitor::TraverseDecl(clang::Decl*)::'lambda'(), llvm::DenseMap<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<void const*>, llvm::detail::DenseMapPair<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > >*) Line | Count | Source | 281 | 27.3k | MapTy *Parents) { | 282 | 27.3k | if (!Node) | 283 | 0 | return true; | 284 | 27.3k | addParent(MapNode, Parents); | 285 | 27.3k | ParentStack.push_back(createDynTypedNode(Node)); | 286 | 27.3k | bool Result = BaseTraverse(); | 287 | 27.3k | ParentStack.pop_back(); | 288 | 27.3k | return Result; | 289 | 27.3k | } |
bool clang::ParentMapContext::ParentMap::ASTVisitor::TraverseNode<clang::NestedNameSpecifierLoc, clang::DynTypedNode, clang::ParentMapContext::ParentMap::ASTVisitor::TraverseNestedNameSpecifierLoc(clang::NestedNameSpecifierLoc)::'lambda'(), llvm::DenseMap<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<clang::DynTypedNode>, llvm::detail::DenseMapPair<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > > >(clang::NestedNameSpecifierLoc, clang::DynTypedNode, clang::ParentMapContext::ParentMap::ASTVisitor::TraverseNestedNameSpecifierLoc(clang::NestedNameSpecifierLoc)::'lambda'(), llvm::DenseMap<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<clang::DynTypedNode>, llvm::detail::DenseMapPair<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > >*) Line | Count | Source | 281 | 21.0k | MapTy *Parents) { | 282 | 21.0k | if (!Node) | 283 | 20.2k | return true; | 284 | 798 | addParent(MapNode, Parents); | 285 | 798 | ParentStack.push_back(createDynTypedNode(Node)); | 286 | 798 | bool Result = BaseTraverse(); | 287 | 798 | ParentStack.pop_back(); | 288 | 798 | return Result; | 289 | 798 | } |
bool clang::ParentMapContext::ParentMap::ASTVisitor::TraverseNode<clang::TypeLoc, clang::DynTypedNode, clang::ParentMapContext::ParentMap::ASTVisitor::TraverseTypeLoc(clang::TypeLoc)::'lambda'(), llvm::DenseMap<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<clang::DynTypedNode>, llvm::detail::DenseMapPair<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > > >(clang::TypeLoc, clang::DynTypedNode, clang::ParentMapContext::ParentMap::ASTVisitor::TraverseTypeLoc(clang::TypeLoc)::'lambda'(), llvm::DenseMap<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<clang::DynTypedNode>, llvm::detail::DenseMapPair<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > >*) Line | Count | Source | 281 | 23.2k | MapTy *Parents) { | 282 | 23.2k | if (!Node) | 283 | 0 | return true; | 284 | 23.2k | addParent(MapNode, Parents); | 285 | 23.2k | ParentStack.push_back(createDynTypedNode(Node)); | 286 | 23.2k | bool Result = BaseTraverse(); | 287 | 23.2k | ParentStack.pop_back(); | 288 | 23.2k | return Result; | 289 | 23.2k | } |
|
290 | | |
291 | 27.3k | bool TraverseDecl(Decl *DeclNode) { |
292 | 27.3k | return TraverseNode( |
293 | 27.3k | DeclNode, DeclNode, [&] { return VisitorBase::TraverseDecl(DeclNode); }, |
294 | 27.3k | &Map.PointerParents); |
295 | 27.3k | } |
296 | 23.2k | bool TraverseTypeLoc(TypeLoc TypeLocNode) { |
297 | 23.2k | return TraverseNode( |
298 | 23.2k | TypeLocNode, DynTypedNode::create(TypeLocNode), |
299 | 23.2k | [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); }, |
300 | 23.2k | &Map.OtherParents); |
301 | 23.2k | } |
302 | 21.0k | bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) { |
303 | 21.0k | return TraverseNode( |
304 | 21.0k | NNSLocNode, DynTypedNode::create(NNSLocNode), |
305 | 798 | [&] { return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode); }, |
306 | 21.0k | &Map.OtherParents); |
307 | 21.0k | } |
308 | | |
309 | | // Using generic TraverseNode for Stmt would prevent data-recursion. |
310 | 16.8k | bool dataTraverseStmtPre(Stmt *StmtNode) { |
311 | 16.8k | addParent(StmtNode, &Map.PointerParents); |
312 | 16.8k | ParentStack.push_back(DynTypedNode::create(*StmtNode)); |
313 | 16.8k | return true; |
314 | 16.8k | } |
315 | 16.8k | bool dataTraverseStmtPost(Stmt *StmtNode) { |
316 | 16.8k | ParentStack.pop_back(); |
317 | 16.8k | return true; |
318 | 16.8k | } |
319 | | |
320 | | ParentMap ⤅ |
321 | | llvm::SmallVector<DynTypedNode, 16> ParentStack; |
322 | | }; |
323 | | |
324 | 1.15k | ParentMapContext::ParentMap::ParentMap(ASTContext &Ctx) { |
325 | 1.15k | ASTVisitor(*this).TraverseAST(Ctx); |
326 | 1.15k | } |
327 | | |
328 | 17.6k | DynTypedNodeList ParentMapContext::getParents(const DynTypedNode &Node) { |
329 | 17.6k | if (!Parents) |
330 | | // We build the parent map for the traversal scope (usually whole TU), as |
331 | | // hasAncestor can escape any subtree. |
332 | 1.15k | Parents = std::make_unique<ParentMap>(ASTCtx); |
333 | 17.6k | return Parents->getParents(getTraversalKind(), Node); |
334 | 17.6k | } |