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<CXXFunctionalCastExpr>(E)) {
158         if (C->getSourceRange() == SR)
159           return true;
160       }
161 
162       if (const auto *C = dyn_cast<CXXConstructExpr>(E)) {
163         if (C->getSourceRange() == SR || C->isElidable())
164           return true;
165       }
166 
167       if (const auto *C = dyn_cast<CXXMemberCallExpr>(E)) {
168         if (C->getSourceRange() == SR)
169           return true;
170       }
171 
172       if (const auto *C = dyn_cast<MemberExpr>(E)) {
173         if (C->getSourceRange() == SR)
174           return true;
175       }
176       return false;
177     };
178 
179     while (ShouldSkip(E, Child)) {
180       auto It = PointerParents.find(E);
181       if (It == PointerParents.end())
182         break;
183       const auto *S = It->second.dyn_cast<const Stmt *>();
184       if (!S) {
185         if (auto *Vec = It->second.dyn_cast<ParentVector *>())
186           return llvm::makeArrayRef(*Vec);
187         return getSingleDynTypedNodeFromParentMap(It->second);
188       }
189       const auto *P = dyn_cast<Expr>(S);
190       if (!P)
191         return DynTypedNode::create(*S);
192       Child = E;
193       E = P;
194     }
195     return DynTypedNode::create(*E);
196   }
197 };
198 
199 /// Template specializations to abstract away from pointers and TypeLocs.
200 /// @{
201 template <typename T> static DynTypedNode createDynTypedNode(const T &Node) {
202   return DynTypedNode::create(*Node);
203 }
204 template <> DynTypedNode createDynTypedNode(const TypeLoc &Node) {
205   return DynTypedNode::create(Node);
206 }
207 template <>
208 DynTypedNode createDynTypedNode(const NestedNameSpecifierLoc &Node) {
209   return DynTypedNode::create(Node);
210 }
211 /// @}
212 
213 /// A \c RecursiveASTVisitor that builds a map from nodes to their
214 /// parents as defined by the \c RecursiveASTVisitor.
215 ///
216 /// Note that the relationship described here is purely in terms of AST
217 /// traversal - there are other relationships (for example declaration context)
218 /// in the AST that are better modeled by special matchers.
219 class ParentMapContext::ParentMap::ASTVisitor
220     : public RecursiveASTVisitor<ASTVisitor> {
221 public:
222   ASTVisitor(ParentMap &Map) : Map(Map) {}
223 
224 private:
225   friend class RecursiveASTVisitor<ASTVisitor>;
226 
227   using VisitorBase = RecursiveASTVisitor<ASTVisitor>;
228 
229   bool shouldVisitTemplateInstantiations() const { return true; }
230 
231   bool shouldVisitImplicitCode() const { return true; }
232 
233   /// Record the parent of the node we're visiting.
234   /// MapNode is the child, the parent is on top of ParentStack.
235   /// Parents is the parent storage (either PointerParents or OtherParents).
236   template <typename MapNodeTy, typename MapTy>
237   void addParent(MapNodeTy MapNode, MapTy *Parents) {
238     if (ParentStack.empty())
239       return;
240 
241     // FIXME: Currently we add the same parent multiple times, but only
242     // when no memoization data is available for the type.
243     // For example when we visit all subexpressions of template
244     // instantiations; this is suboptimal, but benign: the only way to
245     // visit those is with hasAncestor / hasParent, and those do not create
246     // new matches.
247     // The plan is to enable DynTypedNode to be storable in a map or hash
248     // map. The main problem there is to implement hash functions /
249     // comparison operators for all types that DynTypedNode supports that
250     // do not have pointer identity.
251     auto &NodeOrVector = (*Parents)[MapNode];
252     if (NodeOrVector.isNull()) {
253       if (const auto *D = ParentStack.back().get<Decl>())
254         NodeOrVector = D;
255       else if (const auto *S = ParentStack.back().get<Stmt>())
256         NodeOrVector = S;
257       else
258         NodeOrVector = new DynTypedNode(ParentStack.back());
259     } else {
260       if (!NodeOrVector.template is<ParentVector *>()) {
261         auto *Vector = new ParentVector(
262             1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
263         delete NodeOrVector.template dyn_cast<DynTypedNode *>();
264         NodeOrVector = Vector;
265       }
266 
267       auto *Vector = NodeOrVector.template get<ParentVector *>();
268       // Skip duplicates for types that have memoization data.
269       // We must check that the type has memoization data before calling
270       // std::find() because DynTypedNode::operator== can't compare all
271       // types.
272       bool Found = ParentStack.back().getMemoizationData() &&
273                    std::find(Vector->begin(), Vector->end(),
274                              ParentStack.back()) != Vector->end();
275       if (!Found)
276         Vector->push_back(ParentStack.back());
277     }
278   }
279 
280   template <typename T, typename MapNodeTy, typename BaseTraverseFn,
281             typename MapTy>
282   bool TraverseNode(T Node, MapNodeTy MapNode, BaseTraverseFn BaseTraverse,
283                     MapTy *Parents) {
284     if (!Node)
285       return true;
286     addParent(MapNode, Parents);
287     ParentStack.push_back(createDynTypedNode(Node));
288     bool Result = BaseTraverse();
289     ParentStack.pop_back();
290     return Result;
291   }
292 
293   bool TraverseDecl(Decl *DeclNode) {
294     return TraverseNode(
295         DeclNode, DeclNode, [&] { return VisitorBase::TraverseDecl(DeclNode); },
296         &Map.PointerParents);
297   }
298   bool TraverseTypeLoc(TypeLoc TypeLocNode) {
299     return TraverseNode(
300         TypeLocNode, DynTypedNode::create(TypeLocNode),
301         [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); },
302         &Map.OtherParents);
303   }
304   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) {
305     return TraverseNode(
306         NNSLocNode, DynTypedNode::create(NNSLocNode),
307         [&] { return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode); },
308         &Map.OtherParents);
309   }
310 
311   // Using generic TraverseNode for Stmt would prevent data-recursion.
312   bool dataTraverseStmtPre(Stmt *StmtNode) {
313     addParent(StmtNode, &Map.PointerParents);
314     ParentStack.push_back(DynTypedNode::create(*StmtNode));
315     return true;
316   }
317   bool dataTraverseStmtPost(Stmt *StmtNode) {
318     ParentStack.pop_back();
319     return true;
320   }
321 
322   ParentMap &Map;
323   llvm::SmallVector<DynTypedNode, 16> ParentStack;
324 };
325 
326 ParentMapContext::ParentMap::ParentMap(ASTContext &Ctx) {
327   ASTVisitor(*this).TraverseAST(Ctx);
328 }
329 
330 DynTypedNodeList ParentMapContext::getParents(const DynTypedNode &Node) {
331   if (!Parents)
332     // We build the parent map for the traversal scope (usually whole TU), as
333     // hasAncestor can escape any subtree.
334     Parents = std::make_unique<ParentMap>(ASTCtx);
335   return Parents->getParents(getTraversalKind(), Node);
336 }
337