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 ///
215 /// FIXME: Currently only builds up the map using \c Stmt and \c Decl nodes.
216 class ParentMapContext::ParentMap::ASTVisitor
217     : public RecursiveASTVisitor<ASTVisitor> {
218 public:
219   ASTVisitor(ParentMap &Map) : Map(Map) {}
220 
221 private:
222   friend class RecursiveASTVisitor<ASTVisitor>;
223 
224   using VisitorBase = RecursiveASTVisitor<ASTVisitor>;
225 
226   bool shouldVisitTemplateInstantiations() const { return true; }
227 
228   bool shouldVisitImplicitCode() const { return true; }
229 
230   template <typename T, typename MapNodeTy, typename BaseTraverseFn,
231             typename MapTy>
232   bool TraverseNode(T Node, MapNodeTy MapNode, BaseTraverseFn BaseTraverse,
233                     MapTy *Parents) {
234     if (!Node)
235       return true;
236     if (ParentStack.size() > 0) {
237       // FIXME: Currently we add the same parent multiple times, but only
238       // when no memoization data is available for the type.
239       // For example when we visit all subexpressions of template
240       // instantiations; this is suboptimal, but benign: the only way to
241       // visit those is with hasAncestor / hasParent, and those do not create
242       // new matches.
243       // The plan is to enable DynTypedNode to be storable in a map or hash
244       // map. The main problem there is to implement hash functions /
245       // comparison operators for all types that DynTypedNode supports that
246       // do not have pointer identity.
247       auto &NodeOrVector = (*Parents)[MapNode];
248       if (NodeOrVector.isNull()) {
249         if (const auto *D = ParentStack.back().get<Decl>())
250           NodeOrVector = D;
251         else if (const auto *S = ParentStack.back().get<Stmt>())
252           NodeOrVector = S;
253         else
254           NodeOrVector = new DynTypedNode(ParentStack.back());
255       } else {
256         if (!NodeOrVector.template is<ParentVector *>()) {
257           auto *Vector = new ParentVector(
258               1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
259           delete NodeOrVector.template dyn_cast<DynTypedNode *>();
260           NodeOrVector = Vector;
261         }
262 
263         auto *Vector = NodeOrVector.template get<ParentVector *>();
264         // Skip duplicates for types that have memoization data.
265         // We must check that the type has memoization data before calling
266         // std::find() because DynTypedNode::operator== can't compare all
267         // types.
268         bool Found = ParentStack.back().getMemoizationData() &&
269                      std::find(Vector->begin(), Vector->end(),
270                                ParentStack.back()) != Vector->end();
271         if (!Found)
272           Vector->push_back(ParentStack.back());
273       }
274     }
275     ParentStack.push_back(createDynTypedNode(Node));
276     bool Result = BaseTraverse();
277     ParentStack.pop_back();
278     return Result;
279   }
280 
281   bool TraverseDecl(Decl *DeclNode) {
282     return TraverseNode(
283         DeclNode, DeclNode, [&] { return VisitorBase::TraverseDecl(DeclNode); },
284         &Map.PointerParents);
285   }
286 
287   bool TraverseStmt(Stmt *StmtNode) {
288     return TraverseNode(StmtNode, StmtNode,
289                         [&] { return VisitorBase::TraverseStmt(StmtNode); },
290                         &Map.PointerParents);
291   }
292 
293   bool TraverseTypeLoc(TypeLoc TypeLocNode) {
294     return TraverseNode(
295         TypeLocNode, DynTypedNode::create(TypeLocNode),
296         [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); },
297         &Map.OtherParents);
298   }
299 
300   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) {
301     return TraverseNode(
302         NNSLocNode, DynTypedNode::create(NNSLocNode),
303         [&] { return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode); },
304         &Map.OtherParents);
305   }
306 
307   ParentMap &Map;
308   llvm::SmallVector<DynTypedNode, 16> ParentStack;
309 };
310 
311 ParentMapContext::ParentMap::ParentMap(ASTContext &Ctx) {
312   ASTVisitor(*this).TraverseAST(Ctx);
313 }
314 
315 DynTypedNodeList ParentMapContext::getParents(const DynTypedNode &Node) {
316   if (!Parents)
317     // We build the parent map for the traversal scope (usually whole TU), as
318     // hasAncestor can escape any subtree.
319     Parents = std::make_unique<ParentMap>(ASTCtx);
320   return Parents->getParents(getTraversalKind(), Node);
321 }
322