clang 19.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.
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(Value);
78 }
79 llvm::ArrayRef<DynTypedNode> view() const { return Items; }
80 private:
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(*D);
108 if (const auto *S = U.dyn_cast<const Stmt *>())
109 return DynTypedNode::create(*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()) {
119 }
120 if (const auto *V = I->second.template dyn_cast<ParentVector *>()) {
121 return V->view();
122 }
123 return getSingleDynTypedNodeFromParentMap(I->second);
124 }
125
126public:
127 ParentMap(ASTContext &Ctx);
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
147 auto ParentList =
148 getDynNodeFromMap(Node.getMemoizationData(), 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>(S);
168 if (!RWBO) {
169 RewrittenBinOpParentsList = getDynNodeFromMap(S, PointerParents);
170 continue;
171 }
172 if (RWBO->getLHS()->IgnoreUnlessSpelledInSource() != ChildExpr &&
173 RWBO->getRHS()->IgnoreUnlessSpelledInSource() != ChildExpr)
174 break;
175 return DynTypedNode::create(*RWBO);
176 }
177 }
178
179 const auto *ParentExpr = ParentList[0].get<Expr>();
180 if (ParentExpr && ChildExpr)
181 return AscendIgnoreUnlessSpelledInSource(ParentExpr, ChildExpr);
182
183 {
184 auto AncestorNodes =
185 matchParents<DeclStmt, CXXForRangeStmt>(ParentList, this);
186 if (std::get<bool>(AncestorNodes) &&
187 std::get<const CXXForRangeStmt *>(AncestorNodes)
188 ->getLoopVarStmt() ==
189 std::get<const DeclStmt *>(AncestorNodes))
190 return std::get<DynTypedNodeList>(AncestorNodes);
191 }
192 {
193 auto AncestorNodes = matchParents<VarDecl, DeclStmt, CXXForRangeStmt>(
194 ParentList, this);
195 if (std::get<bool>(AncestorNodes) &&
196 std::get<const CXXForRangeStmt *>(AncestorNodes)
197 ->getRangeStmt() ==
198 std::get<const DeclStmt *>(AncestorNodes))
199 return std::get<DynTypedNodeList>(AncestorNodes);
200 }
201 {
202 auto AncestorNodes =
203 matchParents<CXXMethodDecl, CXXRecordDecl, LambdaExpr>(ParentList,
204 this);
205 if (std::get<bool>(AncestorNodes))
206 return std::get<DynTypedNodeList>(AncestorNodes);
207 }
208 {
209 auto AncestorNodes =
210 matchParents<FunctionTemplateDecl, CXXRecordDecl, LambdaExpr>(
211 ParentList, this);
212 if (std::get<bool>(AncestorNodes))
213 return std::get<DynTypedNodeList>(AncestorNodes);
214 }
215 }
216 return ParentList;
217 }
218 return getDynNodeFromMap(Node, OtherParents);
219 }
220
222 const Expr *Child) {
223
224 auto ShouldSkip = [](const Expr *E, const Expr *Child) {
225 if (isa<ImplicitCastExpr>(E))
226 return true;
227
228 if (isa<FullExpr>(E))
229 return true;
230
231 if (isa<MaterializeTemporaryExpr>(E))
232 return true;
233
234 if (isa<CXXBindTemporaryExpr>(E))
235 return true;
236
237 if (isa<ParenExpr>(E))
238 return true;
239
240 if (isa<ExprWithCleanups>(E))
241 return true;
242
243 auto SR = Child->getSourceRange();
244
245 if (const auto *C = dyn_cast<CXXFunctionalCastExpr>(E)) {
246 if (C->getSourceRange() == SR)
247 return true;
248 }
249
250 if (const auto *C = dyn_cast<CXXConstructExpr>(E)) {
251 if (C->getSourceRange() == SR || C->isElidable())
252 return true;
253 }
254
255 if (const auto *C = dyn_cast<CXXMemberCallExpr>(E)) {
256 if (C->getSourceRange() == SR)
257 return true;
258 }
259
260 if (const auto *C = dyn_cast<MemberExpr>(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(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(It->second);
276 }
277 const auto *P = dyn_cast<Expr>(S);
278 if (!P)
279 return DynTypedNode::create(*S);
280 Child = E;
281 E = P;
282 }
283 return DynTypedNode::create(*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,
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(false, 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,
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(false, NodeList, nullptr);
321 }
322};
323
324template <typename T, typename... U>
325std::tuple<bool, DynTypedNodeList, const T *, const U *...>
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}
338}
339template <>
342}
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.
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(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(createDynTypedNode(Node));
425 bool Result = BaseTraverse();
426 ParentStack.pop_back();
427 return Result;
428 }
429
430 bool TraverseDecl(Decl *DeclNode) {
431 return TraverseNode(
432 DeclNode, DeclNode, [&] { return VisitorBase::TraverseDecl(DeclNode); },
433 &Map.PointerParents);
434 }
435 bool TraverseTypeLoc(TypeLoc TypeLocNode) {
436 return TraverseNode(
437 TypeLocNode, DynTypedNode::create(TypeLocNode),
438 [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); },
439 &Map.OtherParents);
440 }
441 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) {
442 return TraverseNode(
443 NNSLocNode, DynTypedNode::create(NNSLocNode),
444 [&] { return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode); },
445 &Map.OtherParents);
446 }
447 bool TraverseAttr(Attr *AttrNode) {
448 return TraverseNode(
449 AttrNode, AttrNode, [&] { return VisitorBase::TraverseAttr(AttrNode); },
450 &Map.PointerParents);
451 }
452 bool TraverseObjCProtocolLoc(ObjCProtocolLoc ProtocolLocNode) {
453 return TraverseNode(
454 ProtocolLocNode, DynTypedNode::create(ProtocolLocNode),
455 [&] { return VisitorBase::TraverseObjCProtocolLoc(ProtocolLocNode); },
456 &Map.OtherParents);
457 }
458
459 // Using generic TraverseNode for Stmt would prevent data-recursion.
460 bool dataTraverseStmtPre(Stmt *StmtNode) {
461 addParent(StmtNode, &Map.PointerParents);
462 ParentStack.push_back(DynTypedNode::create(*StmtNode));
463 return true;
464 }
465 bool dataTraverseStmtPost(Stmt *StmtNode) {
466 ParentStack.pop_back();
467 return true;
468 }
469
470 ParentMap &Map;
472};
473
475 ASTVisitor(*this).TraverseAST(Ctx);
476}
477
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>(ASTCtx);
483 return Parents->getParents(getTraversalKind(), Node);
484}
#define V(N, I)
Definition: ASTContext.h:3294
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
static bool contains(const std::set< tok::TokenKind > &Terminators, const Token &Tok)
Definition: SourceCode.cpp:201
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:185
constexpr bool hasPointerIdentity() const
Check if the given ASTNodeKind identifies a type that offers pointer identity.
Attr - This represents one attribute.
Definition: Attr.h:42
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:86
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:3112
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
The JSON file list parser is used to communicate input to InstallAPI.
@ Vector
'vector' clause, allowed on 'loop', Combined, and 'routine' directives.
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.
const FunctionProtoType * T
#define bool
Definition: stdbool.h:24
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)