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

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