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