clang  16.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"
18 #include "clang/AST/TemplateBase.h"
19 
20 using namespace clang;
21 
23 
25 
26 void 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;
40  return E->IgnoreUnlessSpelledInSource();
41  }
42  llvm_unreachable("Invalid Traversal type!");
43 }
44 
46  if (const auto *E = N.get<Expr>()) {
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,
56 
57 template <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::makeArrayRef(*V);
103  }
104  return getSingleDynTypedNodeFromParentMap(I->second);
105  }
106 
107 public:
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::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 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 
291 template <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 
305 template <typename T, typename... U>
306 std::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 /// @{
314 template <typename T> static DynTypedNode createDynTypedNode(const T &Node) {
315  return DynTypedNode::create(*Node);
316 }
318  return DynTypedNode::create(Node);
319 }
320 template <>
322  return DynTypedNode::create(Node);
323 }
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.
336  : public RecursiveASTVisitor<ASTVisitor> {
337 public:
338  ASTVisitor(ParentMap &Map) : Map(Map) {}
339 
340 private:
342 
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 
459 DynTypedNodeList 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>(ASTCtx);
464  return Parents->getParents(getTraversalKind(), Node);
465 }
clang::TraversalKind
TraversalKind
Defines how we descend a level in the AST when we pass through expressions.
Definition: ASTTypeTraits.h:38
clang::ASTNodeKind::hasPointerIdentity
constexpr bool hasPointerIdentity() const
Check if the given ASTNodeKind identifies a type that offers pointer identity.
Definition: ASTTypeTraits.h:123
clang::DynTypedNodeList
Container for either a single DynTypedNode or for an ArrayRef to DynTypedNode.
Definition: ParentMapContext.h:92
createDynTypedNode
static DynTypedNode createDynTypedNode(const T &Node)
Template specializations to abstract away from pointers and TypeLocs.
Definition: ParentMapContext.cpp:314
llvm::SmallVector
Definition: LLVM.h:38
clang::DynTypedNode::create
static DynTypedNode create(const T &Node)
Creates a DynTypedNode from Node.
Definition: ASTTypeTraits.h:252
clang::ParentMapContext::ParentMap::ASTVisitor
A RecursiveASTVisitor that builds a map from nodes to their parents as defined by the RecursiveASTVis...
Definition: ParentMapContext.cpp:335
MatchParents::match
static std::tuple< bool, DynTypedNodeList, const T *, const U *... > match(const DynTypedNodeList &NodeList, ParentMapContext::ParentMap *ParentMap)
Definition: ParentMapContext.cpp:270
clang::DynTypedNode::getMemoizationData
const void * getMemoizationData() const
Returns a pointer that identifies the stored AST node.
Definition: ASTTypeTraits.h:287
clang::ParentMapContext::ParentMap::AscendIgnoreUnlessSpelledInSource
DynTypedNodeList AscendIgnoreUnlessSpelledInSource(const Expr *E, const Expr *Child)
Definition: ParentMapContext.cpp:202
clang::DynTypedNode::getNodeKind
ASTNodeKind getNodeKind() const
Definition: ASTTypeTraits.h:280
clang::ParentMapContext::traverseIgnored
const Expr * traverseIgnored(const Expr *E) const
Definition: ParentMapContext.cpp:28
Decl.h
ParentMapContext.h
U
TemplateBase.h
clang::ParentMapContext::ParentMapContext
ParentMapContext(ASTContext &Ctx)
Definition: ParentMapContext.cpp:22
V
#define V(N, I)
Definition: ASTContext.h:3237
Node
DynTypedNode Node
Definition: ASTMatchFinder.cpp:68
clang::ASTContext
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:209
clang::RecursiveASTVisitor
A class that does preorder or postorder depth-first traversal on the entire Clang AST and visits each...
Definition: RecursiveASTVisitor.h:152
clang::RecursiveASTVisitor< ASTVisitor >::TraverseAttr
bool TraverseAttr(Attr *At)
Recursively visit an attribute, by dispatching to Traverse*Attr() based on the argument's dynamic typ...
clang::diff::DynTypedNode
DynTypedNode DynTypedNode
Definition: ASTDiffInternal.h:18
Expr.h
bool
#define bool
Definition: stdbool.h:20
MapTy
llvm::DenseMap< Stmt *, Stmt * > MapTy
Definition: ParentMap.cpp:22
clang::Expr::IgnoreUnlessSpelledInSource
Expr * IgnoreUnlessSpelledInSource()
Skip past any invisble AST nodes which might surround this statement, such as ExprWithCleanups or Imp...
Definition: Expr.cpp:3088
clang::NestedNameSpecifierLoc
A C++ nested-name-specifier augmented with source location information.
Definition: NestedNameSpecifier.h:243
clang::RecursiveASTVisitor< ASTVisitor >::TraverseObjCProtocolLoc
bool TraverseObjCProtocolLoc(ObjCProtocolLoc ProtocolLoc)
Recursively visit an Objective-C protocol reference with location information.
clang::ParentMap
Definition: ParentMap.h:20
P
StringRef P
Definition: ASTMatchersInternal.cpp:563
MatchParents< T >::match
static std::tuple< bool, DynTypedNodeList, const T * > match(const DynTypedNodeList &NodeList, ParentMapContext::ParentMap *ParentMap)
Definition: ParentMapContext.cpp:293
clang::TK_AsIs
@ TK_AsIs
Will traverse all child nodes.
Definition: ASTTypeTraits.h:40
llvm::ArrayRef
Definition: LLVM.h:34
clang::Decl
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:83
clang::TypeLoc
Base wrapper for a particular "section" of type source info.
Definition: TypeLoc.h:58
clang::ParentMapContext::~ParentMapContext
~ParentMapContext()
clang::TK_IgnoreUnlessSpelledInSource
@ TK_IgnoreUnlessSpelledInSource
Ignore AST nodes not written in the source.
Definition: ASTTypeTraits.h:43
clang::ParentMapContext::clear
void clear()
Clear parent maps.
Definition: ParentMapContext.cpp:26
matchParents
std::tuple< bool, DynTypedNodeList, const T *, const U *... > matchParents(const DynTypedNodeList &NodeList, ParentMapContext::ParentMap *ParentMap)
Definition: ParentMapContext.cpp:307
clang
Definition: CalledOnceCheck.h:17
RecursiveASTVisitor.h
clang::Stmt
Stmt - This represents one statement.
Definition: Stmt.h:71
clang::Attr
Attr - This represents one attribute.
Definition: Attr.h:40
clang::RecursiveASTVisitor< ASTVisitor >::TraverseDecl
bool TraverseDecl(Decl *D)
Recursively visit a declaration, by dispatching to Traverse*Decl() based on the argument's dynamic ty...
Definition: RecursiveASTVisitor.h:736
clang::ParentMapContext::ParentMap::ParentMap
ParentMap(ASTContext &Ctx)
Definition: ParentMapContext.cpp:455
clang::DynTypedNode::get
const T * get() const
Retrieve the stored node as type T.
Definition: ASTTypeTraits.h:268
clang::DynTypedNode
A dynamically typed AST node container.
Definition: ASTTypeTraits.h:248
clang::ParentMapContext::ParentMap::ASTVisitor::ASTVisitor
ASTVisitor(ParentMap &Map)
Definition: ParentMapContext.cpp:338
clang::ParentMapContext::ParentMap::getParents
DynTypedNodeList getParents(TraversalKind TK, const DynTypedNode &Node)
Definition: ParentMapContext.cpp:126
clang::Expr
This represents one expression.
Definition: Expr.h:109
clang::ParentMapContext::ParentMap
Definition: ParentMapContext.cpp:59
clang::ParentMapContext::ParentMap::~ParentMap
~ParentMap()
Definition: ParentMapContext.cpp:109
clang::ObjCProtocolLoc
Definition: TypeLoc.h:2658
MatchParents
Definition: ParentMapContext.cpp:57
clang::RecursiveASTVisitor< ASTVisitor >::TraverseNestedNameSpecifierLoc
bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS)
Recursively visit a C++ nested-name-specifier with location information.
Definition: RecursiveASTVisitor.h:789
clang::RecursiveASTVisitor::TraverseAST
bool TraverseAST(ASTContext &AST)
Recursively visits an entire AST, starting from the TranslationUnitDecl.
Definition: RecursiveASTVisitor.h:185
clang::RecursiveASTVisitor< ASTVisitor >::TraverseTypeLoc
bool TraverseTypeLoc(TypeLoc TL)
Recursively visit a type with location, by dispatching to Traverse*TypeLoc() based on the argument ty...
Definition: RecursiveASTVisitor.h:715