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