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