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
21using namespace clang;
22
23ParentMapContext::ParentMapContext(ASTContext &Ctx) : ASTCtx(Ctx) {}
24
25ParentMapContext::~ParentMapContext() = default;
26
27void ParentMapContext::clear() { Parents.reset(); }
28
29const Expr *ParentMapContext::traverseIgnored(const Expr *E) const {
30 return traverseIgnored(E: const_cast<Expr *>(E));
31}
32
33Expr *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
46DynTypedNode 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
53template <typename T, typename... U>
54static std::tuple<bool, DynTypedNodeList, const T *, const U *...>
55matchParents(const DynTypedNodeList &NodeList,
56 ParentMapContext::ParentMap *ParentMap);
57
58template <typename, typename...> struct MatchParents;
59
60class 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
131public:
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
292template <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
315template <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
329template <typename T, typename... U>
330std::tuple<bool, DynTypedNodeList, const T *, const U *...>
331matchParents(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/// @{
338template <typename T> static DynTypedNode createDynTypedNode(const T &Node) {
339 return DynTypedNode::create(*Node);
340}
341template <> DynTypedNode createDynTypedNode(const TypeLoc &Node) {
342 return DynTypedNode::create(Node);
343}
344template <>
345DynTypedNode createDynTypedNode(const NestedNameSpecifierLoc &Node) {
346 return DynTypedNode::create(Node);
347}
348template <> 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.
359class ParentMapContext::ParentMap::ASTVisitor
360 : public RecursiveASTVisitor<ASTVisitor> {
361public:
362 ASTVisitor(ParentMap &Map) : Map(Map) {}
363
364private:
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 &Map;
476 llvm::SmallVector<DynTypedNode, 16> ParentStack;
477};
478
479ParentMapContext::ParentMap::ParentMap(ASTContext &Ctx) {
480 ASTVisitor(*this).TraverseAST(AST&: Ctx);
481}
482
483DynTypedNodeList 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

Provided by KDAB

Privacy Policy
Update your C++ knowledge – Modern C++11/14/17 Training
Find out more

source code of clang/lib/AST/ParentMapContext.cpp