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 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
107public:
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
268template <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
291template <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
305template <typename T, typename... U>
306std::tuple<bool, DynTypedNodeList, const T *, const U *...>
307matchParents(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/// @{
314template <typename T> static DynTypedNode createDynTypedNode(const T &Node) {
315 return DynTypedNode::create(*Node);
316}
317template <> DynTypedNode createDynTypedNode(const TypeLoc &Node) {
318 return DynTypedNode::create(Node);
319}
320template <>
321DynTypedNode createDynTypedNode(const NestedNameSpecifierLoc &Node) {
322 return DynTypedNode::create(Node);
323}
324template <> 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.
335class ParentMapContext::ParentMap::ASTVisitor
336 : public RecursiveASTVisitor<ASTVisitor> {
337public:
338 ASTVisitor(ParentMap &Map) : Map(Map) {}
339
340private:
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 &Map;
452 llvm::SmallVector<DynTypedNode, 16> ParentStack;
453};
454
455ParentMapContext::ParentMap::ParentMap(ASTContext &Ctx) {
456 ASTVisitor(*this).TraverseAST(AST&: Ctx);
457}
458
459DynTypedNodeList 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

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