clang  13.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 Tuple, std::size_t... 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 
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 *...>
280  match(const DynTypedNodeList &NodeList,
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 *>
302  match(const DynTypedNodeList &NodeList,
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 *...>
318  return MatchParents<T, U...>::match(NodeList, ParentMap);
319 }
320 
321 /// Template specializations to abstract away from pointers and TypeLocs.
322 /// @{
323 template <typename T> static DynTypedNode createDynTypedNode(const T &Node) {
324  return DynTypedNode::create(*Node);
325 }
327  return DynTypedNode::create(Node);
328 }
329 template <>
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.
342  : public RecursiveASTVisitor<ASTVisitor> {
343 public:
344  ASTVisitor(ParentMap &Map) : Map(Map) {}
345 
346 private:
348 
350 
351  bool shouldVisitTemplateInstantiations() const { return true; }
352 
353  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>
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>
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 
415  bool TraverseDecl(Decl *DeclNode) {
416  return TraverseNode(
417  DeclNode, DeclNode, [&] { return VisitorBase::TraverseDecl(DeclNode); },
418  &Map.PointerParents);
419  }
420  bool TraverseTypeLoc(TypeLoc TypeLocNode) {
421  return TraverseNode(
422  TypeLocNode, DynTypedNode::create(TypeLocNode),
423  [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); },
424  &Map.OtherParents);
425  }
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.
434  bool dataTraverseStmtPre(Stmt *StmtNode) {
435  addParent(StmtNode, &Map.PointerParents);
436  ParentStack.push_back(DynTypedNode::create(*StmtNode));
437  return true;
438  }
439  bool dataTraverseStmtPost(Stmt *StmtNode) {
440  ParentStack.pop_back();
441  return true;
442  }
443 
444  ParentMap &Map;
446 };
447 
449  ASTVisitor(*this).TraverseAST(Ctx);
450 }
451 
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 }
clang::TraversalKind
TraversalKind
Defines how we descend a level in the AST when we pass through expressions.
Definition: ASTTypeTraits.h:39
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:323
llvm::SmallVector
Definition: LLVM.h:38
clang::ASTNodeKind::hasPointerIdentity
bool hasPointerIdentity() const
Check if the given ASTNodeKind identifies a type that offers pointer identity.
Definition: ASTTypeTraits.h:122
clang::DynTypedNode::create
static DynTypedNode create(const T &Node)
Creates a DynTypedNode from Node.
Definition: ASTTypeTraits.h:237
clang::ParentMapContext::ParentMap::ASTVisitor
A RecursiveASTVisitor that builds a map from nodes to their parents as defined by the RecursiveASTVis...
Definition: ParentMapContext.cpp:341
MatchParents::match
static std::tuple< bool, DynTypedNodeList, const T *, const U *... > match(const DynTypedNodeList &NodeList, ParentMapContext::ParentMap *ParentMap)
Definition: ParentMapContext.cpp:280
clang::DynTypedNode::getMemoizationData
const void * getMemoizationData() const
Returns a pointer that identifies the stored AST node.
Definition: ASTTypeTraits.h:272
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:265
clang::ParentMapContext::traverseIgnored
const Expr * traverseIgnored(const Expr *E) const
Definition: ParentMapContext.cpp:28
Decl.h
ParentMapContext.h
size_t
__SIZE_TYPE__ size_t
The unsigned integer type of the result of the sizeof operator.
Definition: opencl-c-base.h:70
U
TemplateBase.h
clang::ParentMapContext::ParentMapContext
ParentMapContext(ASTContext &Ctx)
Definition: ParentMapContext.cpp:22
V
#define V(N, I)
Definition: ASTContext.h:3032
Node
DynTypedNode Node
Definition: ASTMatchFinder.cpp:67
clang::ASTContext
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:188
clang::RecursiveASTVisitor
A class that does preorder or postorder depth-first traversal on the entire Clang AST and visits each...
Definition: RecursiveASTVisitor.h:164
clang::diff::DynTypedNode
DynTypedNode DynTypedNode
Definition: ASTDiffInternal.h:18
Expr.h
bool
#define bool
Definition: stdbool.h:15
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:2836
clang::NestedNameSpecifierLoc
A C++ nested-name-specifier augmented with source location information.
Definition: NestedNameSpecifier.h:243
tuple_pop_front
auto tuple_pop_front(const Tuple &tuple)
Definition: ParentMapContext.cpp:273
clang::ParentMap
Definition: ParentMap.h:20
tuple_pop_front_impl
auto tuple_pop_front_impl(const Tuple &tuple, std::index_sequence< Is... >)
Definition: ParentMapContext.cpp:269
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:302
clang::TK_AsIs
@ TK_AsIs
Will traverse all child nodes.
Definition: ASTTypeTraits.h:41
llvm::ArrayRef
Definition: LLVM.h:34
clang::Decl
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:89
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:44
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:316
clang
Definition: CalledOnceCheck.h:17
RecursiveASTVisitor.h
clang::Stmt
Stmt - This represents one statement.
Definition: Stmt.h:68
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:655
clang::ParentMapContext::ParentMap::ParentMap
ParentMap(ASTContext &Ctx)
Definition: ParentMapContext.cpp:448
clang::DynTypedNode::get
const T * get() const
Retrieve the stored node as type T.
Definition: ASTTypeTraits.h:253
clang::DynTypedNode
A dynamically typed AST node container.
Definition: ASTTypeTraits.h:233
clang::ParentMapContext::ParentMap::ASTVisitor::ASTVisitor
ASTVisitor(ParentMap &Map)
Definition: ParentMapContext.cpp:344
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
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:702
clang::RecursiveASTVisitor::TraverseAST
bool TraverseAST(ASTContext &AST)
Recursively visits an entire AST, starting from the top-level Decls in the AST traversal scope (by de...
Definition: RecursiveASTVisitor.h:198
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:634