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
ParentMapContext(ASTContext & Ctx)22 ParentMapContext::ParentMapContext(ASTContext &Ctx) : ASTCtx(Ctx) {}
23
24 ParentMapContext::~ParentMapContext() = default;
25
clear()26 void ParentMapContext::clear() { Parents.reset(); }
27
traverseIgnored(const Expr * E) const28 const Expr *ParentMapContext::traverseIgnored(const Expr *E) const {
29 return traverseIgnored(const_cast<Expr *>(E));
30 }
31
traverseIgnored(Expr * E) const32 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
traverseIgnored(const DynTypedNode & N) const45 DynTypedNode ParentMapContext::traverseIgnored(const DynTypedNode &N) const {
46 if (const auto *E = N.get<Expr>()) {
47 return DynTypedNode::create(*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
getSingleDynTypedNodeFromParentMap(ParentMapPointers::mapped_type U)86 getSingleDynTypedNodeFromParentMap(ParentMapPointers::mapped_type U) {
87 if (const auto *D = U.dyn_cast<const Decl *>())
88 return DynTypedNode::create(*D);
89 if (const auto *S = U.dyn_cast<const Stmt *>())
90 return DynTypedNode::create(*S);
91 return *U.get<DynTypedNode *>();
92 }
93
94 template <typename NodeTy, typename MapTy>
getDynNodeFromMap(const NodeTy & Node,const MapTy & Map)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::makeArrayRef(*V);
103 }
104 return getSingleDynTypedNodeFromParentMap(I->second);
105 }
106
107 public:
108 ParentMap(ASTContext &Ctx);
~ParentMap()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
getParents(TraversalKind TK,const DynTypedNode & Node)126 DynTypedNodeList getParents(TraversalKind TK, const DynTypedNode &Node) {
127 if (Node.getNodeKind().hasPointerIdentity()) {
128 auto ParentList =
129 getDynNodeFromMap(Node.getMemoizationData(), 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>(S);
149 if (!RWBO) {
150 RewrittenBinOpParentsList = getDynNodeFromMap(S, PointerParents);
151 continue;
152 }
153 if (RWBO->getLHS()->IgnoreUnlessSpelledInSource() != ChildExpr &&
154 RWBO->getRHS()->IgnoreUnlessSpelledInSource() != ChildExpr)
155 break;
156 return DynTypedNode::create(*RWBO);
157 }
158 }
159
160 const auto *ParentExpr = ParentList[0].get<Expr>();
161 if (ParentExpr && ChildExpr)
162 return AscendIgnoreUnlessSpelledInSource(ParentExpr, ChildExpr);
163
164 {
165 auto AncestorNodes =
166 matchParents<DeclStmt, CXXForRangeStmt>(ParentList, this);
167 if (std::get<bool>(AncestorNodes) &&
168 std::get<const CXXForRangeStmt *>(AncestorNodes)
169 ->getLoopVarStmt() ==
170 std::get<const DeclStmt *>(AncestorNodes))
171 return std::get<DynTypedNodeList>(AncestorNodes);
172 }
173 {
174 auto AncestorNodes = matchParents<VarDecl, DeclStmt, CXXForRangeStmt>(
175 ParentList, this);
176 if (std::get<bool>(AncestorNodes) &&
177 std::get<const CXXForRangeStmt *>(AncestorNodes)
178 ->getRangeStmt() ==
179 std::get<const DeclStmt *>(AncestorNodes))
180 return std::get<DynTypedNodeList>(AncestorNodes);
181 }
182 {
183 auto AncestorNodes =
184 matchParents<CXXMethodDecl, CXXRecordDecl, LambdaExpr>(ParentList,
185 this);
186 if (std::get<bool>(AncestorNodes))
187 return std::get<DynTypedNodeList>(AncestorNodes);
188 }
189 {
190 auto AncestorNodes =
191 matchParents<FunctionTemplateDecl, CXXRecordDecl, LambdaExpr>(
192 ParentList, this);
193 if (std::get<bool>(AncestorNodes))
194 return std::get<DynTypedNodeList>(AncestorNodes);
195 }
196 }
197 return ParentList;
198 }
199 return getDynNodeFromMap(Node, OtherParents);
200 }
201
AscendIgnoreUnlessSpelledInSource(const Expr * E,const Expr * Child)202 DynTypedNodeList AscendIgnoreUnlessSpelledInSource(const Expr *E,
203 const Expr *Child) {
204
205 auto ShouldSkip = [](const Expr *E, const Expr *Child) {
206 if (isa<ImplicitCastExpr>(E))
207 return true;
208
209 if (isa<FullExpr>(E))
210 return true;
211
212 if (isa<MaterializeTemporaryExpr>(E))
213 return true;
214
215 if (isa<CXXBindTemporaryExpr>(E))
216 return true;
217
218 if (isa<ParenExpr>(E))
219 return true;
220
221 if (isa<ExprWithCleanups>(E))
222 return true;
223
224 auto SR = Child->getSourceRange();
225
226 if (const auto *C = dyn_cast<CXXFunctionalCastExpr>(E)) {
227 if (C->getSourceRange() == SR)
228 return true;
229 }
230
231 if (const auto *C = dyn_cast<CXXConstructExpr>(E)) {
232 if (C->getSourceRange() == SR || C->isElidable())
233 return true;
234 }
235
236 if (const auto *C = dyn_cast<CXXMemberCallExpr>(E)) {
237 if (C->getSourceRange() == SR)
238 return true;
239 }
240
241 if (const auto *C = dyn_cast<MemberExpr>(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(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::makeArrayRef(*Vec);
256 return getSingleDynTypedNodeFromParentMap(It->second);
257 }
258 const auto *P = dyn_cast<Expr>(S);
259 if (!P)
260 return DynTypedNode::create(*S);
261 Child = E;
262 E = P;
263 }
264 return DynTypedNode::create(*E);
265 }
266 };
267
268 template <typename Tuple, std::size_t... Is>
tuple_pop_front_impl(const Tuple & tuple,std::index_sequence<Is...>)269 auto tuple_pop_front_impl(const Tuple &tuple, std::index_sequence<Is...>) {
270 return std::make_tuple(std::get<1 + Is>(tuple)...);
271 }
272
tuple_pop_front(const Tuple & tuple)273 template <typename Tuple> auto tuple_pop_front(const Tuple &tuple) {
274 return tuple_pop_front_impl(
275 tuple, std::make_index_sequence<std::tuple_size<Tuple>::value - 1>());
276 }
277
278 template <typename T, typename... U> struct MatchParents {
279 static std::tuple<bool, DynTypedNodeList, const T *, const U *...>
matchMatchParents280 match(const DynTypedNodeList &NodeList,
281 ParentMapContext::ParentMap *ParentMap) {
282 if (const auto *TypedNode = NodeList[0].get<T>()) {
283 auto NextParentList =
284 ParentMap->getDynNodeFromMap(TypedNode, ParentMap->PointerParents);
285 if (NextParentList.size() == 1) {
286 auto TailTuple = MatchParents<U...>::match(NextParentList, ParentMap);
287 if (std::get<bool>(TailTuple)) {
288 return std::tuple_cat(
289 std::make_tuple(true, std::get<DynTypedNodeList>(TailTuple),
290 TypedNode),
291 tuple_pop_front(tuple_pop_front(TailTuple)));
292 }
293 }
294 }
295 return std::tuple_cat(std::make_tuple(false, NodeList),
296 std::tuple<const T *, const U *...>());
297 }
298 };
299
300 template <typename T> struct MatchParents<T> {
301 static std::tuple<bool, DynTypedNodeList, const T *>
matchMatchParents302 match(const DynTypedNodeList &NodeList,
303 ParentMapContext::ParentMap *ParentMap) {
304 if (const auto *TypedNode = NodeList[0].get<T>()) {
305 auto NextParentList =
306 ParentMap->getDynNodeFromMap(TypedNode, ParentMap->PointerParents);
307 if (NextParentList.size() == 1)
308 return std::make_tuple(true, NodeList, TypedNode);
309 }
310 return std::make_tuple(false, NodeList, nullptr);
311 }
312 };
313
314 template <typename T, typename... U>
315 std::tuple<bool, DynTypedNodeList, const T *, const U *...>
matchParents(const DynTypedNodeList & NodeList,ParentMapContext::ParentMap * ParentMap)316 matchParents(const DynTypedNodeList &NodeList,
317 ParentMapContext::ParentMap *ParentMap) {
318 return MatchParents<T, U...>::match(NodeList, ParentMap);
319 }
320
321 /// Template specializations to abstract away from pointers and TypeLocs.
322 /// @{
createDynTypedNode(const T & Node)323 template <typename T> static DynTypedNode createDynTypedNode(const T &Node) {
324 return DynTypedNode::create(*Node);
325 }
createDynTypedNode(const TypeLoc & Node)326 template <> DynTypedNode createDynTypedNode(const TypeLoc &Node) {
327 return DynTypedNode::create(Node);
328 }
329 template <>
createDynTypedNode(const NestedNameSpecifierLoc & Node)330 DynTypedNode createDynTypedNode(const NestedNameSpecifierLoc &Node) {
331 return DynTypedNode::create(Node);
332 }
333 /// @}
334
335 /// A \c RecursiveASTVisitor that builds a map from nodes to their
336 /// parents as defined by the \c RecursiveASTVisitor.
337 ///
338 /// Note that the relationship described here is purely in terms of AST
339 /// traversal - there are other relationships (for example declaration context)
340 /// in the AST that are better modeled by special matchers.
341 class ParentMapContext::ParentMap::ASTVisitor
342 : public RecursiveASTVisitor<ASTVisitor> {
343 public:
ASTVisitor(ParentMap & Map)344 ASTVisitor(ParentMap &Map) : Map(Map) {}
345
346 private:
347 friend class RecursiveASTVisitor<ASTVisitor>;
348
349 using VisitorBase = RecursiveASTVisitor<ASTVisitor>;
350
shouldVisitTemplateInstantiations() const351 bool shouldVisitTemplateInstantiations() const { return true; }
352
shouldVisitImplicitCode() const353 bool shouldVisitImplicitCode() const { return true; }
354
355 /// Record the parent of the node we're visiting.
356 /// MapNode is the child, the parent is on top of ParentStack.
357 /// Parents is the parent storage (either PointerParents or OtherParents).
358 template <typename MapNodeTy, typename MapTy>
addParent(MapNodeTy MapNode,MapTy * Parents)359 void addParent(MapNodeTy MapNode, MapTy *Parents) {
360 if (ParentStack.empty())
361 return;
362
363 // FIXME: Currently we add the same parent multiple times, but only
364 // when no memoization data is available for the type.
365 // For example when we visit all subexpressions of template
366 // instantiations; this is suboptimal, but benign: the only way to
367 // visit those is with hasAncestor / hasParent, and those do not create
368 // new matches.
369 // The plan is to enable DynTypedNode to be storable in a map or hash
370 // map. The main problem there is to implement hash functions /
371 // comparison operators for all types that DynTypedNode supports that
372 // do not have pointer identity.
373 auto &NodeOrVector = (*Parents)[MapNode];
374 if (NodeOrVector.isNull()) {
375 if (const auto *D = ParentStack.back().get<Decl>())
376 NodeOrVector = D;
377 else if (const auto *S = ParentStack.back().get<Stmt>())
378 NodeOrVector = S;
379 else
380 NodeOrVector = new DynTypedNode(ParentStack.back());
381 } else {
382 if (!NodeOrVector.template is<ParentVector *>()) {
383 auto *Vector = new ParentVector(
384 1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
385 delete NodeOrVector.template dyn_cast<DynTypedNode *>();
386 NodeOrVector = Vector;
387 }
388
389 auto *Vector = NodeOrVector.template get<ParentVector *>();
390 // Skip duplicates for types that have memoization data.
391 // We must check that the type has memoization data before calling
392 // std::find() because DynTypedNode::operator== can't compare all
393 // types.
394 bool Found = ParentStack.back().getMemoizationData() &&
395 std::find(Vector->begin(), Vector->end(),
396 ParentStack.back()) != Vector->end();
397 if (!Found)
398 Vector->push_back(ParentStack.back());
399 }
400 }
401
402 template <typename T, typename MapNodeTy, typename BaseTraverseFn,
403 typename MapTy>
TraverseNode(T Node,MapNodeTy MapNode,BaseTraverseFn BaseTraverse,MapTy * Parents)404 bool TraverseNode(T Node, MapNodeTy MapNode, BaseTraverseFn BaseTraverse,
405 MapTy *Parents) {
406 if (!Node)
407 return true;
408 addParent(MapNode, Parents);
409 ParentStack.push_back(createDynTypedNode(Node));
410 bool Result = BaseTraverse();
411 ParentStack.pop_back();
412 return Result;
413 }
414
TraverseDecl(Decl * DeclNode)415 bool TraverseDecl(Decl *DeclNode) {
416 return TraverseNode(
417 DeclNode, DeclNode, [&] { return VisitorBase::TraverseDecl(DeclNode); },
418 &Map.PointerParents);
419 }
TraverseTypeLoc(TypeLoc TypeLocNode)420 bool TraverseTypeLoc(TypeLoc TypeLocNode) {
421 return TraverseNode(
422 TypeLocNode, DynTypedNode::create(TypeLocNode),
423 [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); },
424 &Map.OtherParents);
425 }
TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode)426 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) {
427 return TraverseNode(
428 NNSLocNode, DynTypedNode::create(NNSLocNode),
429 [&] { return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode); },
430 &Map.OtherParents);
431 }
432
433 // Using generic TraverseNode for Stmt would prevent data-recursion.
dataTraverseStmtPre(Stmt * StmtNode)434 bool dataTraverseStmtPre(Stmt *StmtNode) {
435 addParent(StmtNode, &Map.PointerParents);
436 ParentStack.push_back(DynTypedNode::create(*StmtNode));
437 return true;
438 }
dataTraverseStmtPost(Stmt * StmtNode)439 bool dataTraverseStmtPost(Stmt *StmtNode) {
440 ParentStack.pop_back();
441 return true;
442 }
443
444 ParentMap ⤅
445 llvm::SmallVector<DynTypedNode, 16> ParentStack;
446 };
447
ParentMap(ASTContext & Ctx)448 ParentMapContext::ParentMap::ParentMap(ASTContext &Ctx) {
449 ASTVisitor(*this).TraverseAST(Ctx);
450 }
451
getParents(const DynTypedNode & Node)452 DynTypedNodeList ParentMapContext::getParents(const DynTypedNode &Node) {
453 if (!Parents)
454 // We build the parent map for the traversal scope (usually whole TU), as
455 // hasAncestor can escape any subtree.
456 Parents = std::make_unique<ParentMap>(ASTCtx);
457 return Parents->getParents(getTraversalKind(), Node);
458 }
459