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/Decl.h" |
16 | #include "clang/AST/Expr.h" |
17 | #include "clang/AST/RecursiveASTVisitor.h" |
18 | #include "clang/AST/TemplateBase.h" |
19 | #include "llvm/ADT/SmallPtrSet.h" |
20 | |
21 | using namespace clang; |
22 | |
23 | ParentMapContext::ParentMapContext(ASTContext &Ctx) : ASTCtx(Ctx) {} |
24 | |
25 | ParentMapContext::~ParentMapContext() = default; |
26 | |
27 | void ParentMapContext::clear() { Parents.reset(); } |
28 | |
29 | const Expr *ParentMapContext::traverseIgnored(const Expr *E) const { |
30 | return traverseIgnored(E: const_cast<Expr *>(E)); |
31 | } |
32 | |
33 | Expr *ParentMapContext::traverseIgnored(Expr *E) const { |
34 | if (!E) |
35 | return nullptr; |
36 | |
37 | switch (Traversal) { |
38 | case TK_AsIs: |
39 | return E; |
40 | case TK_IgnoreUnlessSpelledInSource: |
41 | return E->IgnoreUnlessSpelledInSource(); |
42 | } |
43 | llvm_unreachable("Invalid Traversal type!"); |
44 | } |
45 | |
46 | DynTypedNode ParentMapContext::traverseIgnored(const DynTypedNode &N) const { |
47 | if (const auto *E = N.get<Expr>()) { |
48 | return DynTypedNode::create(Node: *traverseIgnored(E)); |
49 | } |
50 | return N; |
51 | } |
52 | |
53 | template <typename T, typename... U> |
54 | static std::tuple<bool, DynTypedNodeList, const T *, const U *...> |
55 | matchParents(const DynTypedNodeList &NodeList, |
56 | ParentMapContext::ParentMap *ParentMap); |
57 | |
58 | template <typename, typename...> struct MatchParents; |
59 | |
60 | class ParentMapContext::ParentMap { |
61 | |
62 | template <typename, typename...> friend struct ::MatchParents; |
63 | |
64 | /// Contains parents of a node. |
65 | class ParentVector { |
66 | public: |
67 | ParentVector() = default; |
68 | explicit ParentVector(size_t N, const DynTypedNode &Value) { |
69 | Items.reserve(N); |
70 | for (; N > 0; --N) |
71 | push_back(Value); |
72 | } |
73 | bool contains(const DynTypedNode &Value) const { |
74 | const void *Identity = Value.getMemoizationData(); |
75 | assert(Identity); |
76 | return Dedup.contains(Ptr: Identity); |
77 | } |
78 | void push_back(const DynTypedNode &Value) { |
79 | const void *Identity = Value.getMemoizationData(); |
80 | if (!Identity || Dedup.insert(Ptr: Identity).second) { |
81 | Items.push_back(Elt: Value); |
82 | } |
83 | } |
84 | llvm::ArrayRef<DynTypedNode> view() const { return Items; } |
85 | private: |
86 | llvm::SmallVector<DynTypedNode, 1> Items; |
87 | llvm::SmallPtrSet<const void *, 2> Dedup; |
88 | }; |
89 | |
90 | /// Maps from a node to its parents. This is used for nodes that have |
91 | /// pointer identity only, which are more common and we can save space by |
92 | /// only storing a unique pointer to them. |
93 | using ParentMapPointers = |
94 | llvm::DenseMap<const void *, |
95 | llvm::PointerUnion<const Decl *, const Stmt *, |
96 | DynTypedNode *, ParentVector *>>; |
97 | |
98 | /// Parent map for nodes without pointer identity. We store a full |
99 | /// DynTypedNode for all keys. |
100 | using ParentMapOtherNodes = |
101 | llvm::DenseMap<DynTypedNode, |
102 | llvm::PointerUnion<const Decl *, const Stmt *, |
103 | DynTypedNode *, ParentVector *>>; |
104 | |
105 | ParentMapPointers PointerParents; |
106 | ParentMapOtherNodes OtherParents; |
107 | class ASTVisitor; |
108 | |
109 | static DynTypedNode |
110 | getSingleDynTypedNodeFromParentMap(ParentMapPointers::mapped_type U) { |
111 | if (const auto *D = dyn_cast<const Decl *>(Val&: U)) |
112 | return DynTypedNode::create(Node: *D); |
113 | if (const auto *S = dyn_cast<const Stmt *>(Val&: U)) |
114 | return DynTypedNode::create(Node: *S); |
115 | return *cast<DynTypedNode *>(Val&: U); |
116 | } |
117 | |
118 | template <typename NodeTy, typename MapTy> |
119 | static DynTypedNodeList getDynNodeFromMap(const NodeTy &Node, |
120 | const MapTy &Map) { |
121 | auto I = Map.find(Node); |
122 | if (I == Map.end()) { |
123 | return llvm::ArrayRef<DynTypedNode>(); |
124 | } |
125 | if (const auto *V = dyn_cast<ParentVector *>(I->second)) { |
126 | return V->view(); |
127 | } |
128 | return getSingleDynTypedNodeFromParentMap(U: I->second); |
129 | } |
130 | |
131 | public: |
132 | ParentMap(ASTContext &Ctx); |
133 | ~ParentMap() { |
134 | for (const auto &Entry : PointerParents) { |
135 | if (auto *DTN = dyn_cast<DynTypedNode *>(Val: Entry.second)) { |
136 | delete DTN; |
137 | } else if (auto *PV = dyn_cast<ParentVector *>(Val: Entry.second)) { |
138 | delete PV; |
139 | } |
140 | } |
141 | for (const auto &Entry : OtherParents) { |
142 | if (auto *DTN = dyn_cast<DynTypedNode *>(Entry.second)) { |
143 | delete DTN; |
144 | } else if (auto *PV = dyn_cast<ParentVector *>(Entry.second)) { |
145 | delete PV; |
146 | } |
147 | } |
148 | } |
149 | |
150 | DynTypedNodeList getParents(TraversalKind TK, const DynTypedNode &Node) { |
151 | if (Node.getNodeKind().hasPointerIdentity()) { |
152 | auto ParentList = |
153 | getDynNodeFromMap(Node: Node.getMemoizationData(), Map: PointerParents); |
154 | if (ParentList.size() > 0 && TK == TK_IgnoreUnlessSpelledInSource) { |
155 | |
156 | const auto *ChildExpr = Node.get<Expr>(); |
157 | |
158 | { |
159 | // Don't match explicit node types because different stdlib |
160 | // implementations implement this in different ways and have |
161 | // different intermediate nodes. |
162 | // Look up 4 levels for a cxxRewrittenBinaryOperator as that is |
163 | // enough for the major stdlib implementations. |
164 | auto RewrittenBinOpParentsList = ParentList; |
165 | int I = 0; |
166 | while (ChildExpr && RewrittenBinOpParentsList.size() == 1 && |
167 | I++ < 4) { |
168 | const auto *S = RewrittenBinOpParentsList[0].get<Stmt>(); |
169 | if (!S) |
170 | break; |
171 | |
172 | const auto *RWBO = dyn_cast<CXXRewrittenBinaryOperator>(Val: S); |
173 | if (!RWBO) { |
174 | RewrittenBinOpParentsList = getDynNodeFromMap(Node: S, Map: PointerParents); |
175 | continue; |
176 | } |
177 | if (RWBO->getLHS()->IgnoreUnlessSpelledInSource() != ChildExpr && |
178 | RWBO->getRHS()->IgnoreUnlessSpelledInSource() != ChildExpr) |
179 | break; |
180 | return DynTypedNode::create(Node: *RWBO); |
181 | } |
182 | } |
183 | |
184 | const auto *ParentExpr = ParentList[0].get<Expr>(); |
185 | if (ParentExpr && ChildExpr) |
186 | return AscendIgnoreUnlessSpelledInSource(E: ParentExpr, Child: ChildExpr); |
187 | |
188 | { |
189 | auto AncestorNodes = |
190 | matchParents<DeclStmt, CXXForRangeStmt>(NodeList: ParentList, ParentMap: this); |
191 | if (std::get<bool>(t&: AncestorNodes) && |
192 | std::get<const CXXForRangeStmt *>(t&: AncestorNodes) |
193 | ->getLoopVarStmt() == |
194 | std::get<const DeclStmt *>(t&: AncestorNodes)) |
195 | return std::get<DynTypedNodeList>(t&: AncestorNodes); |
196 | } |
197 | { |
198 | auto AncestorNodes = matchParents<VarDecl, DeclStmt, CXXForRangeStmt>( |
199 | NodeList: ParentList, ParentMap: this); |
200 | if (std::get<bool>(t&: AncestorNodes) && |
201 | std::get<const CXXForRangeStmt *>(t&: AncestorNodes) |
202 | ->getRangeStmt() == |
203 | std::get<const DeclStmt *>(t&: AncestorNodes)) |
204 | return std::get<DynTypedNodeList>(t&: AncestorNodes); |
205 | } |
206 | { |
207 | auto AncestorNodes = |
208 | matchParents<CXXMethodDecl, CXXRecordDecl, LambdaExpr>(NodeList: ParentList, |
209 | ParentMap: this); |
210 | if (std::get<bool>(t&: AncestorNodes)) |
211 | return std::get<DynTypedNodeList>(t&: AncestorNodes); |
212 | } |
213 | { |
214 | auto AncestorNodes = |
215 | matchParents<FunctionTemplateDecl, CXXRecordDecl, LambdaExpr>( |
216 | NodeList: ParentList, ParentMap: this); |
217 | if (std::get<bool>(t&: AncestorNodes)) |
218 | return std::get<DynTypedNodeList>(t&: AncestorNodes); |
219 | } |
220 | } |
221 | return ParentList; |
222 | } |
223 | return getDynNodeFromMap(Node, Map: OtherParents); |
224 | } |
225 | |
226 | DynTypedNodeList AscendIgnoreUnlessSpelledInSource(const Expr *E, |
227 | const Expr *Child) { |
228 | |
229 | auto ShouldSkip = [](const Expr *E, const Expr *Child) { |
230 | if (isa<ImplicitCastExpr>(Val: E)) |
231 | return true; |
232 | |
233 | if (isa<FullExpr>(Val: E)) |
234 | return true; |
235 | |
236 | if (isa<MaterializeTemporaryExpr>(Val: E)) |
237 | return true; |
238 | |
239 | if (isa<CXXBindTemporaryExpr>(Val: E)) |
240 | return true; |
241 | |
242 | if (isa<ParenExpr>(Val: E)) |
243 | return true; |
244 | |
245 | if (isa<ExprWithCleanups>(Val: E)) |
246 | return true; |
247 | |
248 | auto SR = Child->getSourceRange(); |
249 | |
250 | if (const auto *C = dyn_cast<CXXFunctionalCastExpr>(Val: E)) { |
251 | if (C->getSourceRange() == SR) |
252 | return true; |
253 | } |
254 | |
255 | if (const auto *C = dyn_cast<CXXConstructExpr>(Val: E)) { |
256 | if (C->getSourceRange() == SR || C->isElidable()) |
257 | return true; |
258 | } |
259 | |
260 | if (const auto *C = dyn_cast<CXXMemberCallExpr>(Val: E)) { |
261 | if (C->getSourceRange() == SR) |
262 | return true; |
263 | } |
264 | |
265 | if (const auto *C = dyn_cast<MemberExpr>(Val: E)) { |
266 | if (C->getSourceRange() == SR) |
267 | return true; |
268 | } |
269 | return false; |
270 | }; |
271 | |
272 | while (ShouldSkip(E, Child)) { |
273 | auto It = PointerParents.find(Val: E); |
274 | if (It == PointerParents.end()) |
275 | break; |
276 | const auto *S = dyn_cast<const Stmt *>(Val&: It->second); |
277 | if (!S) { |
278 | if (auto *Vec = dyn_cast<ParentVector *>(Val&: It->second)) |
279 | return Vec->view(); |
280 | return getSingleDynTypedNodeFromParentMap(U: It->second); |
281 | } |
282 | const auto *P = dyn_cast<Expr>(Val: S); |
283 | if (!P) |
284 | return DynTypedNode::create(Node: *S); |
285 | Child = E; |
286 | E = P; |
287 | } |
288 | return DynTypedNode::create(Node: *E); |
289 | } |
290 | }; |
291 | |
292 | template <typename T, typename... U> struct MatchParents { |
293 | static std::tuple<bool, DynTypedNodeList, const T *, const U *...> |
294 | match(const DynTypedNodeList &NodeList, |
295 | ParentMapContext::ParentMap *ParentMap) { |
296 | if (const auto *TypedNode = NodeList[0].get<T>()) { |
297 | auto NextParentList = |
298 | ParentMap->getDynNodeFromMap(TypedNode, ParentMap->PointerParents); |
299 | if (NextParentList.size() == 1) { |
300 | auto TailTuple = MatchParents<U...>::match(NextParentList, ParentMap); |
301 | if (std::get<bool>(TailTuple)) { |
302 | return std::apply( |
303 | [TypedNode](bool, DynTypedNodeList NodeList, auto... TupleTail) { |
304 | return std::make_tuple(true, NodeList, TypedNode, TupleTail...); |
305 | }, |
306 | TailTuple); |
307 | } |
308 | } |
309 | } |
310 | return std::tuple_cat(std::make_tuple(args: false, args: NodeList), |
311 | std::tuple<const T *, const U *...>()); |
312 | } |
313 | }; |
314 | |
315 | template <typename T> struct MatchParents<T> { |
316 | static std::tuple<bool, DynTypedNodeList, const T *> |
317 | match(const DynTypedNodeList &NodeList, |
318 | ParentMapContext::ParentMap *ParentMap) { |
319 | if (const auto *TypedNode = NodeList[0].get<T>()) { |
320 | auto NextParentList = |
321 | ParentMap->getDynNodeFromMap(TypedNode, ParentMap->PointerParents); |
322 | if (NextParentList.size() == 1) |
323 | return std::make_tuple(true, NodeList, TypedNode); |
324 | } |
325 | return std::make_tuple(args: false, args: NodeList, args: nullptr); |
326 | } |
327 | }; |
328 | |
329 | template <typename T, typename... U> |
330 | std::tuple<bool, DynTypedNodeList, const T *, const U *...> |
331 | matchParents(const DynTypedNodeList &NodeList, |
332 | ParentMapContext::ParentMap *ParentMap) { |
333 | return MatchParents<T, U...>::match(NodeList, ParentMap); |
334 | } |
335 | |
336 | /// Template specializations to abstract away from pointers and TypeLocs. |
337 | /// @{ |
338 | template <typename T> static DynTypedNode createDynTypedNode(const T &Node) { |
339 | return DynTypedNode::create(*Node); |
340 | } |
341 | template <> DynTypedNode createDynTypedNode(const TypeLoc &Node) { |
342 | return DynTypedNode::create(Node); |
343 | } |
344 | template <> |
345 | DynTypedNode createDynTypedNode(const NestedNameSpecifierLoc &Node) { |
346 | return DynTypedNode::create(Node); |
347 | } |
348 | template <> DynTypedNode createDynTypedNode(const ObjCProtocolLoc &Node) { |
349 | return DynTypedNode::create(Node); |
350 | } |
351 | /// @} |
352 | |
353 | /// A \c RecursiveASTVisitor that builds a map from nodes to their |
354 | /// parents as defined by the \c RecursiveASTVisitor. |
355 | /// |
356 | /// Note that the relationship described here is purely in terms of AST |
357 | /// traversal - there are other relationships (for example declaration context) |
358 | /// in the AST that are better modeled by special matchers. |
359 | class ParentMapContext::ParentMap::ASTVisitor |
360 | : public RecursiveASTVisitor<ASTVisitor> { |
361 | public: |
362 | ASTVisitor(ParentMap &Map) : Map(Map) {} |
363 | |
364 | private: |
365 | friend class RecursiveASTVisitor<ASTVisitor>; |
366 | |
367 | using VisitorBase = RecursiveASTVisitor<ASTVisitor>; |
368 | |
369 | bool shouldVisitTemplateInstantiations() const { return true; } |
370 | |
371 | bool shouldVisitImplicitCode() const { return true; } |
372 | |
373 | /// Record the parent of the node we're visiting. |
374 | /// MapNode is the child, the parent is on top of ParentStack. |
375 | /// Parents is the parent storage (either PointerParents or OtherParents). |
376 | template <typename MapNodeTy, typename MapTy> |
377 | void addParent(MapNodeTy MapNode, MapTy *Parents) { |
378 | if (ParentStack.empty()) |
379 | return; |
380 | |
381 | // FIXME: Currently we add the same parent multiple times, but only |
382 | // when no memoization data is available for the type. |
383 | // For example when we visit all subexpressions of template |
384 | // instantiations; this is suboptimal, but benign: the only way to |
385 | // visit those is with hasAncestor / hasParent, and those do not create |
386 | // new matches. |
387 | // The plan is to enable DynTypedNode to be storable in a map or hash |
388 | // map. The main problem there is to implement hash functions / |
389 | // comparison operators for all types that DynTypedNode supports that |
390 | // do not have pointer identity. |
391 | auto &NodeOrVector = (*Parents)[MapNode]; |
392 | if (NodeOrVector.isNull()) { |
393 | if (const auto *D = ParentStack.back().get<Decl>()) |
394 | NodeOrVector = D; |
395 | else if (const auto *S = ParentStack.back().get<Stmt>()) |
396 | NodeOrVector = S; |
397 | else |
398 | NodeOrVector = new DynTypedNode(ParentStack.back()); |
399 | } else { |
400 | if (!isa<ParentVector *>(NodeOrVector)) { |
401 | auto *Vector = new ParentVector( |
402 | 1, getSingleDynTypedNodeFromParentMap(U: NodeOrVector)); |
403 | delete dyn_cast<DynTypedNode *>(NodeOrVector); |
404 | NodeOrVector = Vector; |
405 | } |
406 | |
407 | auto *Vector = cast<ParentVector *>(NodeOrVector); |
408 | // Skip duplicates for types that have memoization data. |
409 | // We must check that the type has memoization data before calling |
410 | // llvm::is_contained() because DynTypedNode::operator== can't compare all |
411 | // types. |
412 | bool Found = ParentStack.back().getMemoizationData() && |
413 | llvm::is_contained(*Vector, ParentStack.back()); |
414 | if (!Found) |
415 | Vector->push_back(ParentStack.back()); |
416 | } |
417 | } |
418 | |
419 | template <typename T> static bool isNull(T Node) { return !Node; } |
420 | static bool isNull(ObjCProtocolLoc Node) { return false; } |
421 | |
422 | template <typename T, typename MapNodeTy, typename BaseTraverseFn, |
423 | typename MapTy> |
424 | bool TraverseNode(T Node, MapNodeTy MapNode, BaseTraverseFn BaseTraverse, |
425 | MapTy *Parents) { |
426 | if (isNull(Node)) |
427 | return true; |
428 | addParent(MapNode, Parents); |
429 | ParentStack.push_back(Elt: createDynTypedNode(Node)); |
430 | bool Result = BaseTraverse(); |
431 | ParentStack.pop_back(); |
432 | return Result; |
433 | } |
434 | |
435 | bool TraverseDecl(Decl *DeclNode) { |
436 | return TraverseNode( |
437 | Node: DeclNode, MapNode: DeclNode, BaseTraverse: [&] { return VisitorBase::TraverseDecl(D: DeclNode); }, |
438 | Parents: &Map.PointerParents); |
439 | } |
440 | bool TraverseTypeLoc(TypeLoc TypeLocNode) { |
441 | return TraverseNode( |
442 | Node: TypeLocNode, MapNode: DynTypedNode::create(Node: TypeLocNode), |
443 | BaseTraverse: [&] { return VisitorBase::TraverseTypeLoc(TL: TypeLocNode); }, |
444 | Parents: &Map.OtherParents); |
445 | } |
446 | bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) { |
447 | return TraverseNode( |
448 | Node: NNSLocNode, MapNode: DynTypedNode::create(Node: NNSLocNode), |
449 | BaseTraverse: [&] { return VisitorBase::TraverseNestedNameSpecifierLoc(NNS: NNSLocNode); }, |
450 | Parents: &Map.OtherParents); |
451 | } |
452 | bool TraverseAttr(Attr *AttrNode) { |
453 | return TraverseNode( |
454 | Node: AttrNode, MapNode: AttrNode, BaseTraverse: [&] { return VisitorBase::TraverseAttr(At: AttrNode); }, |
455 | Parents: &Map.PointerParents); |
456 | } |
457 | bool TraverseObjCProtocolLoc(ObjCProtocolLoc ProtocolLocNode) { |
458 | return TraverseNode( |
459 | Node: ProtocolLocNode, MapNode: DynTypedNode::create(Node: ProtocolLocNode), |
460 | BaseTraverse: [&] { return VisitorBase::TraverseObjCProtocolLoc(ProtocolLoc: ProtocolLocNode); }, |
461 | Parents: &Map.OtherParents); |
462 | } |
463 | |
464 | // Using generic TraverseNode for Stmt would prevent data-recursion. |
465 | bool dataTraverseStmtPre(Stmt *StmtNode) { |
466 | addParent(MapNode: StmtNode, Parents: &Map.PointerParents); |
467 | ParentStack.push_back(Elt: DynTypedNode::create(Node: *StmtNode)); |
468 | return true; |
469 | } |
470 | bool dataTraverseStmtPost(Stmt *StmtNode) { |
471 | ParentStack.pop_back(); |
472 | return true; |
473 | } |
474 | |
475 | ParentMap ⤅ |
476 | llvm::SmallVector<DynTypedNode, 16> ParentStack; |
477 | }; |
478 | |
479 | ParentMapContext::ParentMap::ParentMap(ASTContext &Ctx) { |
480 | ASTVisitor(*this).TraverseAST(AST&: Ctx); |
481 | } |
482 | |
483 | DynTypedNodeList ParentMapContext::getParents(const DynTypedNode &Node) { |
484 | if (!Parents) |
485 | // We build the parent map for the traversal scope (usually whole TU), as |
486 | // hasAncestor can escape any subtree. |
487 | Parents = std::make_unique<ParentMap>(args&: ASTCtx); |
488 | return Parents->getParents(TK: getTraversalKind(), Node); |
489 | } |
490 |
Definitions
- ParentMapContext
- ~ParentMapContext
- clear
- traverseIgnored
- traverseIgnored
- traverseIgnored
- ParentMap
- ParentVector
- ParentVector
- ParentVector
- contains
- push_back
- view
- getSingleDynTypedNodeFromParentMap
- getDynNodeFromMap
- ~ParentMap
- getParents
- AscendIgnoreUnlessSpelledInSource
- MatchParents
- match
- MatchParents
- match
- matchParents
- createDynTypedNode
- createDynTypedNode
- createDynTypedNode
- createDynTypedNode
- ASTVisitor
- ASTVisitor
- shouldVisitTemplateInstantiations
- shouldVisitImplicitCode
- addParent
- isNull
- isNull
- TraverseNode
- TraverseDecl
- TraverseTypeLoc
- TraverseNestedNameSpecifierLoc
- TraverseAttr
- TraverseObjCProtocolLoc
- dataTraverseStmtPre
- dataTraverseStmtPost
- ParentMap
Update your C++ knowledge – Modern C++11/14/17 Training
Find out more