clang 18.0.0git
ParentMapContext.cpp
Go to the documentation of this file.
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
16#include "clang/AST/Decl.h"
17#include "clang/AST/Expr.h"
19
20using namespace clang;
21
23
25
26void ParentMapContext::clear() { Parents.reset(); }
27
29 return traverseIgnored(const_cast<Expr *>(E));
30}
31
33 if (!E)
34 return nullptr;
35
36 switch (Traversal) {
37 case TK_AsIs:
38 return E;
41 }
42 llvm_unreachable("Invalid Traversal type!");
43}
44
46 if (const auto *E = N.get<Expr>()) {
48 }
49 return N;
50}
51
52template <typename T, typename... U>
53std::tuple<bool, DynTypedNodeList, const T *, const U *...>
54matchParents(const DynTypedNodeList &NodeList,
56
57template <typename, typename...> struct MatchParents;
58
60
61 template <typename, typename...> friend struct ::MatchParents;
62
63 /// Contains parents of a node.
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 *,
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 *,
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(*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>
95 static DynTypedNodeList getDynNodeFromMap(const NodeTy &Node,
96 const MapTy &Map) {
97 auto I = Map.find(Node);
98 if (I == Map.end()) {
100 }
101 if (const auto *V = I->second.template dyn_cast<ParentVector *>()) {
102 return llvm::ArrayRef(*V);
103 }
104 return getSingleDynTypedNodeFromParentMap(I->second);
105 }
106
107public:
108 ParentMap(ASTContext &Ctx);
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
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
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::ArrayRef(*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
268template <typename T, typename... U> struct MatchParents {
269 static std::tuple<bool, DynTypedNodeList, const T *, const U *...>
270 match(const DynTypedNodeList &NodeList,
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(false, 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,
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(false, NodeList, nullptr);
302 }
303};
304
305template <typename T, typename... U>
306std::tuple<bool, DynTypedNodeList, const T *, const U *...>
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}
319}
320template <>
323}
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.
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(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(createDynTypedNode(Node));
406 bool Result = BaseTraverse();
407 ParentStack.pop_back();
408 return Result;
409 }
410
411 bool TraverseDecl(Decl *DeclNode) {
412 return TraverseNode(
413 DeclNode, DeclNode, [&] { return VisitorBase::TraverseDecl(DeclNode); },
414 &Map.PointerParents);
415 }
416 bool TraverseTypeLoc(TypeLoc TypeLocNode) {
417 return TraverseNode(
418 TypeLocNode, DynTypedNode::create(TypeLocNode),
419 [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); },
420 &Map.OtherParents);
421 }
422 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) {
423 return TraverseNode(
424 NNSLocNode, DynTypedNode::create(NNSLocNode),
425 [&] { return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode); },
426 &Map.OtherParents);
427 }
428 bool TraverseAttr(Attr *AttrNode) {
429 return TraverseNode(
430 AttrNode, AttrNode, [&] { return VisitorBase::TraverseAttr(AttrNode); },
431 &Map.PointerParents);
432 }
433 bool TraverseObjCProtocolLoc(ObjCProtocolLoc ProtocolLocNode) {
434 return TraverseNode(
435 ProtocolLocNode, DynTypedNode::create(ProtocolLocNode),
436 [&] { return VisitorBase::TraverseObjCProtocolLoc(ProtocolLocNode); },
437 &Map.OtherParents);
438 }
439
440 // Using generic TraverseNode for Stmt would prevent data-recursion.
441 bool dataTraverseStmtPre(Stmt *StmtNode) {
442 addParent(StmtNode, &Map.PointerParents);
443 ParentStack.push_back(DynTypedNode::create(*StmtNode));
444 return true;
445 }
446 bool dataTraverseStmtPost(Stmt *StmtNode) {
447 ParentStack.pop_back();
448 return true;
449 }
450
451 ParentMap &Map;
453};
454
456 ASTVisitor(*this).TraverseAST(Ctx);
457}
458
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>(ASTCtx);
464 return Parents->getParents(getTraversalKind(), Node);
465}
#define V(N, I)
Definition: ASTContext.h:3241
DynTypedNode Node
StringRef P
std::tuple< bool, DynTypedNodeList, const T *, const U *... > matchParents(const DynTypedNodeList &NodeList, ParentMapContext::ParentMap *ParentMap)
static DynTypedNode createDynTypedNode(const T &Node)
Template specializations to abstract away from pointers and TypeLocs.
llvm::DenseMap< Stmt *, Stmt * > MapTy
Definition: ParentMap.cpp:22
A RecursiveASTVisitor that builds a map from nodes to their parents as defined by the RecursiveASTVis...
DynTypedNodeList getParents(TraversalKind TK, const DynTypedNode &Node)
DynTypedNodeList AscendIgnoreUnlessSpelledInSource(const Expr *E, const Expr *Child)
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:182
constexpr bool hasPointerIdentity() const
Check if the given ASTNodeKind identifies a type that offers pointer identity.
Attr - This represents one attribute.
Definition: Attr.h:41
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:85
Container for either a single DynTypedNode or for an ArrayRef to DynTypedNode.
A dynamically typed AST node container.
ASTNodeKind getNodeKind() const
const T * get() const
Retrieve the stored node as type T.
static DynTypedNode create(const T &Node)
Creates a DynTypedNode from Node.
const void * getMemoizationData() const
Returns a pointer that identifies the stored AST node.
This represents one expression.
Definition: Expr.h:110
Expr * IgnoreUnlessSpelledInSource()
Skip past any invisible AST nodes which might surround this statement, such as ExprWithCleanups or Im...
Definition: Expr.cpp:3084
A C++ nested-name-specifier augmented with source location information.
const Expr * traverseIgnored(const Expr *E) const
void clear()
Clear parent maps.
TraversalKind getTraversalKind() const
DynTypedNodeList getParents(const NodeT &Node)
Returns the parents of the given node (within the traversal scope).
ParentMapContext(ASTContext &Ctx)
A class that does preorder or postorder depth-first traversal on the entire Clang AST and visits each...
bool TraverseObjCProtocolLoc(ObjCProtocolLoc ProtocolLoc)
Recursively visit an Objective-C protocol reference with location information.
bool TraverseAST(ASTContext &AST)
Recursively visits an entire AST, starting from the TranslationUnitDecl.
bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS)
Recursively visit a C++ nested-name-specifier with location information.
bool TraverseDecl(Decl *D)
Recursively visit a declaration, by dispatching to Traverse*Decl() based on the argument's dynamic ty...
bool TraverseTypeLoc(TypeLoc TL)
Recursively visit a type with location, by dispatching to Traverse*TypeLoc() based on the argument ty...
bool TraverseAttr(Attr *At)
Recursively visit an attribute, by dispatching to Traverse*Attr() based on the argument's dynamic typ...
Stmt - This represents one statement.
Definition: Stmt.h:84
Base wrapper for a particular "section" of type source info.
Definition: TypeLoc.h:59
TraversalKind
Defines how we descend a level in the AST when we pass through expressions.
Definition: ASTTypeTraits.h:38
@ TK_AsIs
Will traverse all child nodes.
Definition: ASTTypeTraits.h:40
@ TK_IgnoreUnlessSpelledInSource
Ignore AST nodes not written in the source.
Definition: ASTTypeTraits.h:43
@ Result
The result type of a method or function.
#define bool
Definition: stdbool.h:20
static std::tuple< bool, DynTypedNodeList, const T * > match(const DynTypedNodeList &NodeList, ParentMapContext::ParentMap *ParentMap)
static std::tuple< bool, DynTypedNodeList, const T *, const U *... > match(const DynTypedNodeList &NodeList, ParentMapContext::ParentMap *ParentMap)