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 
22 ParentMapContext::ParentMapContext(ASTContext &Ctx) : ASTCtx(Ctx) {}
23 
24 ParentMapContext::~ParentMapContext() = default;
25 
26 void ParentMapContext::clear() { Parents.reset(); }
27 
28 const Expr *ParentMapContext::traverseIgnored(const Expr *E) const {
29   return traverseIgnored(const_cast<Expr *>(E));
30 }
31 
32 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_IgnoreImplicitCastsAndParentheses:
40     return E->IgnoreParenImpCasts();
41   case TK_IgnoreUnlessSpelledInSource:
42     return E->IgnoreUnlessSpelledInSource();
43   }
44   llvm_unreachable("Invalid Traversal type!");
45 }
46 
47 DynTypedNode ParentMapContext::traverseIgnored(const DynTypedNode &N) const {
48   if (const auto *E = N.get<Expr>()) {
49     return DynTypedNode::create(*traverseIgnored(E));
50   }
51   return N;
52 }
53 
54 class ParentMapContext::ParentMap {
55   /// Contains parents of a node.
56   using ParentVector = llvm::SmallVector<DynTypedNode, 2>;
57 
58   /// Maps from a node to its parents. This is used for nodes that have
59   /// pointer identity only, which are more common and we can save space by
60   /// only storing a unique pointer to them.
61   using ParentMapPointers =
62       llvm::DenseMap<const void *,
63                      llvm::PointerUnion<const Decl *, const Stmt *,
64                                         DynTypedNode *, ParentVector *>>;
65 
66   /// Parent map for nodes without pointer identity. We store a full
67   /// DynTypedNode for all keys.
68   using ParentMapOtherNodes =
69       llvm::DenseMap<DynTypedNode,
70                      llvm::PointerUnion<const Decl *, const Stmt *,
71                                         DynTypedNode *, ParentVector *>>;
72 
73   ParentMapPointers PointerParents;
74   ParentMapOtherNodes OtherParents;
75   class ASTVisitor;
76 
77   static DynTypedNode
78   getSingleDynTypedNodeFromParentMap(ParentMapPointers::mapped_type U) {
79     if (const auto *D = U.dyn_cast<const Decl *>())
80       return DynTypedNode::create(*D);
81     if (const auto *S = U.dyn_cast<const Stmt *>())
82       return DynTypedNode::create(*S);
83     return *U.get<DynTypedNode *>();
84   }
85 
86   template <typename NodeTy, typename MapTy>
87   static DynTypedNodeList getDynNodeFromMap(const NodeTy &Node,
88                                                         const MapTy &Map) {
89     auto I = Map.find(Node);
90     if (I == Map.end()) {
91       return llvm::ArrayRef<DynTypedNode>();
92     }
93     if (const auto *V = I->second.template dyn_cast<ParentVector *>()) {
94       return llvm::makeArrayRef(*V);
95     }
96     return getSingleDynTypedNodeFromParentMap(I->second);
97   }
98 
99 public:
100   ParentMap(ASTContext &Ctx);
101   ~ParentMap() {
102     for (const auto &Entry : PointerParents) {
103       if (Entry.second.is<DynTypedNode *>()) {
104         delete Entry.second.get<DynTypedNode *>();
105       } else if (Entry.second.is<ParentVector *>()) {
106         delete Entry.second.get<ParentVector *>();
107       }
108     }
109     for (const auto &Entry : OtherParents) {
110       if (Entry.second.is<DynTypedNode *>()) {
111         delete Entry.second.get<DynTypedNode *>();
112       } else if (Entry.second.is<ParentVector *>()) {
113         delete Entry.second.get<ParentVector *>();
114       }
115     }
116   }
117 
118   DynTypedNodeList getParents(TraversalKind TK, const DynTypedNode &Node) {
119     if (Node.getNodeKind().hasPointerIdentity()) {
120       auto ParentList =
121           getDynNodeFromMap(Node.getMemoizationData(), PointerParents);
122       if (ParentList.size() == 1 && TK == TK_IgnoreUnlessSpelledInSource) {
123         const auto *E = ParentList[0].get<Expr>();
124         const auto *Child = Node.get<Expr>();
125         if (E && Child)
126           return AscendIgnoreUnlessSpelledInSource(E, Child);
127       }
128       return ParentList;
129     }
130     return getDynNodeFromMap(Node, OtherParents);
131   }
132 
133   DynTypedNodeList AscendIgnoreUnlessSpelledInSource(const Expr *E,
134                                                      const Expr *Child) {
135 
136     auto ShouldSkip = [](const Expr *E, const Expr *Child) {
137       if (isa<ImplicitCastExpr>(E))
138         return true;
139 
140       if (isa<FullExpr>(E))
141         return true;
142 
143       if (isa<MaterializeTemporaryExpr>(E))
144         return true;
145 
146       if (isa<CXXBindTemporaryExpr>(E))
147         return true;
148 
149       if (isa<ParenExpr>(E))
150         return true;
151 
152       if (isa<ExprWithCleanups>(E))
153         return true;
154 
155       auto SR = Child->getSourceRange();
156 
157       if (const auto *C = dyn_cast<CXXConstructExpr>(E)) {
158         if (C->getSourceRange() == SR || !isa<CXXTemporaryObjectExpr>(C))
159           return true;
160       }
161 
162       if (const auto *C = dyn_cast<CXXMemberCallExpr>(E)) {
163         if (C->getSourceRange() == SR)
164           return true;
165       }
166 
167       if (const auto *C = dyn_cast<MemberExpr>(E)) {
168         if (C->getSourceRange() == SR)
169           return true;
170       }
171       return false;
172     };
173 
174     while (ShouldSkip(E, Child)) {
175       auto It = PointerParents.find(E);
176       if (It == PointerParents.end())
177         break;
178       const auto *S = It->second.dyn_cast<const Stmt *>();
179       if (!S) {
180         if (auto *Vec = It->second.dyn_cast<ParentVector *>())
181           return llvm::makeArrayRef(*Vec);
182         return getSingleDynTypedNodeFromParentMap(It->second);
183       }
184       const auto *P = dyn_cast<Expr>(S);
185       if (!P)
186         return DynTypedNode::create(*S);
187       Child = E;
188       E = P;
189     }
190     return DynTypedNode::create(*E);
191   }
192 };
193 
194 /// Template specializations to abstract away from pointers and TypeLocs.
195 /// @{
196 template <typename T> static DynTypedNode createDynTypedNode(const T &Node) {
197   return DynTypedNode::create(*Node);
198 }
199 template <> DynTypedNode createDynTypedNode(const TypeLoc &Node) {
200   return DynTypedNode::create(Node);
201 }
202 template <>
203 DynTypedNode createDynTypedNode(const NestedNameSpecifierLoc &Node) {
204   return DynTypedNode::create(Node);
205 }
206 /// @}
207 
208 /// A \c RecursiveASTVisitor that builds a map from nodes to their
209 /// parents as defined by the \c RecursiveASTVisitor.
210 ///
211 /// Note that the relationship described here is purely in terms of AST
212 /// traversal - there are other relationships (for example declaration context)
213 /// in the AST that are better modeled by special matchers.
214 class ParentMapContext::ParentMap::ASTVisitor
215     : public RecursiveASTVisitor<ASTVisitor> {
216 public:
217   ASTVisitor(ParentMap &Map) : Map(Map) {}
218 
219 private:
220   friend class RecursiveASTVisitor<ASTVisitor>;
221 
222   using VisitorBase = RecursiveASTVisitor<ASTVisitor>;
223 
224   bool shouldVisitTemplateInstantiations() const { return true; }
225 
226   bool shouldVisitImplicitCode() const { return true; }
227 
228   /// Record the parent of the node we're visiting.
229   /// MapNode is the child, the parent is on top of ParentStack.
230   /// Parents is the parent storage (either PointerParents or OtherParents).
231   template <typename MapNodeTy, typename MapTy>
232   void addParent(MapNodeTy MapNode, MapTy *Parents) {
233     if (ParentStack.empty())
234       return;
235 
236     // FIXME: Currently we add the same parent multiple times, but only
237     // when no memoization data is available for the type.
238     // For example when we visit all subexpressions of template
239     // instantiations; this is suboptimal, but benign: the only way to
240     // visit those is with hasAncestor / hasParent, and those do not create
241     // new matches.
242     // The plan is to enable DynTypedNode to be storable in a map or hash
243     // map. The main problem there is to implement hash functions /
244     // comparison operators for all types that DynTypedNode supports that
245     // do not have pointer identity.
246     auto &NodeOrVector = (*Parents)[MapNode];
247     if (NodeOrVector.isNull()) {
248       if (const auto *D = ParentStack.back().get<Decl>())
249         NodeOrVector = D;
250       else if (const auto *S = ParentStack.back().get<Stmt>())
251         NodeOrVector = S;
252       else
253         NodeOrVector = new DynTypedNode(ParentStack.back());
254     } else {
255       if (!NodeOrVector.template is<ParentVector *>()) {
256         auto *Vector = new ParentVector(
257             1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
258         delete NodeOrVector.template dyn_cast<DynTypedNode *>();
259         NodeOrVector = Vector;
260       }
261 
262       auto *Vector = NodeOrVector.template get<ParentVector *>();
263       // Skip duplicates for types that have memoization data.
264       // We must check that the type has memoization data before calling
265       // std::find() because DynTypedNode::operator== can't compare all
266       // types.
267       bool Found = ParentStack.back().getMemoizationData() &&
268                    std::find(Vector->begin(), Vector->end(),
269                              ParentStack.back()) != Vector->end();
270       if (!Found)
271         Vector->push_back(ParentStack.back());
272     }
273   }
274 
275   template <typename T, typename MapNodeTy, typename BaseTraverseFn,
276             typename MapTy>
277   bool TraverseNode(T Node, MapNodeTy MapNode, BaseTraverseFn BaseTraverse,
278                     MapTy *Parents) {
279     if (!Node)
280       return true;
281     addParent(MapNode, Parents);
282     ParentStack.push_back(createDynTypedNode(Node));
283     bool Result = BaseTraverse();
284     ParentStack.pop_back();
285     return Result;
286   }
287 
288   bool TraverseDecl(Decl *DeclNode) {
289     return TraverseNode(
290         DeclNode, DeclNode, [&] { return VisitorBase::TraverseDecl(DeclNode); },
291         &Map.PointerParents);
292   }
293   bool TraverseTypeLoc(TypeLoc TypeLocNode) {
294     return TraverseNode(
295         TypeLocNode, DynTypedNode::create(TypeLocNode),
296         [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); },
297         &Map.OtherParents);
298   }
299   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) {
300     return TraverseNode(
301         NNSLocNode, DynTypedNode::create(NNSLocNode),
302         [&] { return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode); },
303         &Map.OtherParents);
304   }
305 
306   // Using generic TraverseNode for Stmt would prevent data-recursion.
307   bool dataTraverseStmtPre(Stmt *StmtNode) {
308     addParent(StmtNode, &Map.PointerParents);
309     ParentStack.push_back(DynTypedNode::create(*StmtNode));
310     return true;
311   }
312   bool dataTraverseStmtPost(Stmt *StmtNode) {
313     ParentStack.pop_back();
314     return true;
315   }
316 
317   ParentMap &Map;
318   llvm::SmallVector<DynTypedNode, 16> ParentStack;
319 };
320 
321 ParentMapContext::ParentMap::ParentMap(ASTContext &Ctx) {
322   ASTVisitor(*this).TraverseAST(Ctx);
323 }
324 
325 DynTypedNodeList ParentMapContext::getParents(const DynTypedNode &Node) {
326   if (!Parents)
327     // We build the parent map for the traversal scope (usually whole TU), as
328     // hasAncestor can escape any subtree.
329     Parents = std::make_unique<ParentMap>(ASTCtx);
330   return Parents->getParents(getTraversalKind(), Node);
331 }
332