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 template <typename T, typename... U>
53 std::tuple<bool, DynTypedNodeList, const T *, const U *...>
54 matchParents(const DynTypedNodeList &NodeList,
55              ParentMapContext::ParentMap *ParentMap);
56 
57 template <typename, typename...> struct MatchParents;
58 
59 class ParentMapContext::ParentMap {
60 
61   template <typename, typename...> friend struct ::MatchParents;
62 
63   /// Contains parents of a node.
64   using ParentVector = llvm::SmallVector<DynTypedNode, 2>;
65 
66   /// Maps from a node to its parents. This is used for nodes that have
67   /// pointer identity only, which are more common and we can save space by
68   /// only storing a unique pointer to them.
69   using ParentMapPointers =
70       llvm::DenseMap<const void *,
71                      llvm::PointerUnion<const Decl *, const Stmt *,
72                                         DynTypedNode *, ParentVector *>>;
73 
74   /// Parent map for nodes without pointer identity. We store a full
75   /// DynTypedNode for all keys.
76   using ParentMapOtherNodes =
77       llvm::DenseMap<DynTypedNode,
78                      llvm::PointerUnion<const Decl *, const Stmt *,
79                                         DynTypedNode *, ParentVector *>>;
80 
81   ParentMapPointers PointerParents;
82   ParentMapOtherNodes OtherParents;
83   class ASTVisitor;
84 
85   static DynTypedNode
86   getSingleDynTypedNodeFromParentMap(ParentMapPointers::mapped_type U) {
87     if (const auto *D = U.dyn_cast<const Decl *>())
88       return DynTypedNode::create(*D);
89     if (const auto *S = U.dyn_cast<const Stmt *>())
90       return DynTypedNode::create(*S);
91     return *U.get<DynTypedNode *>();
92   }
93 
94   template <typename NodeTy, typename MapTy>
95   static DynTypedNodeList getDynNodeFromMap(const NodeTy &Node,
96                                                         const MapTy &Map) {
97     auto I = Map.find(Node);
98     if (I == Map.end()) {
99       return llvm::ArrayRef<DynTypedNode>();
100     }
101     if (const auto *V = I->second.template dyn_cast<ParentVector *>()) {
102       return llvm::ArrayRef(*V);
103     }
104     return getSingleDynTypedNodeFromParentMap(I->second);
105   }
106 
107 public:
108   ParentMap(ASTContext &Ctx);
109   ~ParentMap() {
110     for (const auto &Entry : PointerParents) {
111       if (Entry.second.is<DynTypedNode *>()) {
112         delete Entry.second.get<DynTypedNode *>();
113       } else if (Entry.second.is<ParentVector *>()) {
114         delete Entry.second.get<ParentVector *>();
115       }
116     }
117     for (const auto &Entry : OtherParents) {
118       if (Entry.second.is<DynTypedNode *>()) {
119         delete Entry.second.get<DynTypedNode *>();
120       } else if (Entry.second.is<ParentVector *>()) {
121         delete Entry.second.get<ParentVector *>();
122       }
123     }
124   }
125 
126   DynTypedNodeList getParents(TraversalKind TK, const DynTypedNode &Node) {
127     if (Node.getNodeKind().hasPointerIdentity()) {
128       auto ParentList =
129           getDynNodeFromMap(Node.getMemoizationData(), PointerParents);
130       if (ParentList.size() > 0 && TK == TK_IgnoreUnlessSpelledInSource) {
131 
132         const auto *ChildExpr = Node.get<Expr>();
133 
134         {
135           // Don't match explicit node types because different stdlib
136           // implementations implement this in different ways and have
137           // different intermediate nodes.
138           // Look up 4 levels for a cxxRewrittenBinaryOperator as that is
139           // enough for the major stdlib implementations.
140           auto RewrittenBinOpParentsList = ParentList;
141           int I = 0;
142           while (ChildExpr && RewrittenBinOpParentsList.size() == 1 &&
143                  I++ < 4) {
144             const auto *S = RewrittenBinOpParentsList[0].get<Stmt>();
145             if (!S)
146               break;
147 
148             const auto *RWBO = dyn_cast<CXXRewrittenBinaryOperator>(S);
149             if (!RWBO) {
150               RewrittenBinOpParentsList = getDynNodeFromMap(S, PointerParents);
151               continue;
152             }
153             if (RWBO->getLHS()->IgnoreUnlessSpelledInSource() != ChildExpr &&
154                 RWBO->getRHS()->IgnoreUnlessSpelledInSource() != ChildExpr)
155               break;
156             return DynTypedNode::create(*RWBO);
157           }
158         }
159 
160         const auto *ParentExpr = ParentList[0].get<Expr>();
161         if (ParentExpr && ChildExpr)
162           return AscendIgnoreUnlessSpelledInSource(ParentExpr, ChildExpr);
163 
164         {
165           auto AncestorNodes =
166               matchParents<DeclStmt, CXXForRangeStmt>(ParentList, this);
167           if (std::get<bool>(AncestorNodes) &&
168               std::get<const CXXForRangeStmt *>(AncestorNodes)
169                       ->getLoopVarStmt() ==
170                   std::get<const DeclStmt *>(AncestorNodes))
171             return std::get<DynTypedNodeList>(AncestorNodes);
172         }
173         {
174           auto AncestorNodes = matchParents<VarDecl, DeclStmt, CXXForRangeStmt>(
175               ParentList, this);
176           if (std::get<bool>(AncestorNodes) &&
177               std::get<const CXXForRangeStmt *>(AncestorNodes)
178                       ->getRangeStmt() ==
179                   std::get<const DeclStmt *>(AncestorNodes))
180             return std::get<DynTypedNodeList>(AncestorNodes);
181         }
182         {
183           auto AncestorNodes =
184               matchParents<CXXMethodDecl, CXXRecordDecl, LambdaExpr>(ParentList,
185                                                                      this);
186           if (std::get<bool>(AncestorNodes))
187             return std::get<DynTypedNodeList>(AncestorNodes);
188         }
189         {
190           auto AncestorNodes =
191               matchParents<FunctionTemplateDecl, CXXRecordDecl, LambdaExpr>(
192                   ParentList, this);
193           if (std::get<bool>(AncestorNodes))
194             return std::get<DynTypedNodeList>(AncestorNodes);
195         }
196       }
197       return ParentList;
198     }
199     return getDynNodeFromMap(Node, OtherParents);
200   }
201 
202   DynTypedNodeList AscendIgnoreUnlessSpelledInSource(const Expr *E,
203                                                      const Expr *Child) {
204 
205     auto ShouldSkip = [](const Expr *E, const Expr *Child) {
206       if (isa<ImplicitCastExpr>(E))
207         return true;
208 
209       if (isa<FullExpr>(E))
210         return true;
211 
212       if (isa<MaterializeTemporaryExpr>(E))
213         return true;
214 
215       if (isa<CXXBindTemporaryExpr>(E))
216         return true;
217 
218       if (isa<ParenExpr>(E))
219         return true;
220 
221       if (isa<ExprWithCleanups>(E))
222         return true;
223 
224       auto SR = Child->getSourceRange();
225 
226       if (const auto *C = dyn_cast<CXXFunctionalCastExpr>(E)) {
227         if (C->getSourceRange() == SR)
228           return true;
229       }
230 
231       if (const auto *C = dyn_cast<CXXConstructExpr>(E)) {
232         if (C->getSourceRange() == SR || C->isElidable())
233           return true;
234       }
235 
236       if (const auto *C = dyn_cast<CXXMemberCallExpr>(E)) {
237         if (C->getSourceRange() == SR)
238           return true;
239       }
240 
241       if (const auto *C = dyn_cast<MemberExpr>(E)) {
242         if (C->getSourceRange() == SR)
243           return true;
244       }
245       return false;
246     };
247 
248     while (ShouldSkip(E, Child)) {
249       auto It = PointerParents.find(E);
250       if (It == PointerParents.end())
251         break;
252       const auto *S = It->second.dyn_cast<const Stmt *>();
253       if (!S) {
254         if (auto *Vec = It->second.dyn_cast<ParentVector *>())
255           return llvm::ArrayRef(*Vec);
256         return getSingleDynTypedNodeFromParentMap(It->second);
257       }
258       const auto *P = dyn_cast<Expr>(S);
259       if (!P)
260         return DynTypedNode::create(*S);
261       Child = E;
262       E = P;
263     }
264     return DynTypedNode::create(*E);
265   }
266 };
267 
268 template <typename T, typename... U> struct MatchParents {
269   static std::tuple<bool, DynTypedNodeList, const T *, const U *...>
270   match(const DynTypedNodeList &NodeList,
271         ParentMapContext::ParentMap *ParentMap) {
272     if (const auto *TypedNode = NodeList[0].get<T>()) {
273       auto NextParentList =
274           ParentMap->getDynNodeFromMap(TypedNode, ParentMap->PointerParents);
275       if (NextParentList.size() == 1) {
276         auto TailTuple = MatchParents<U...>::match(NextParentList, ParentMap);
277         if (std::get<bool>(TailTuple)) {
278           return std::apply(
279               [TypedNode](bool, DynTypedNodeList NodeList, auto... TupleTail) {
280                 return std::make_tuple(true, NodeList, TypedNode, TupleTail...);
281               },
282               TailTuple);
283         }
284       }
285     }
286     return std::tuple_cat(std::make_tuple(false, NodeList),
287                           std::tuple<const T *, const U *...>());
288   }
289 };
290 
291 template <typename T> struct MatchParents<T> {
292   static std::tuple<bool, DynTypedNodeList, const T *>
293   match(const DynTypedNodeList &NodeList,
294         ParentMapContext::ParentMap *ParentMap) {
295     if (const auto *TypedNode = NodeList[0].get<T>()) {
296       auto NextParentList =
297           ParentMap->getDynNodeFromMap(TypedNode, ParentMap->PointerParents);
298       if (NextParentList.size() == 1)
299         return std::make_tuple(true, NodeList, TypedNode);
300     }
301     return std::make_tuple(false, NodeList, nullptr);
302   }
303 };
304 
305 template <typename T, typename... U>
306 std::tuple<bool, DynTypedNodeList, const T *, const U *...>
307 matchParents(const DynTypedNodeList &NodeList,
308              ParentMapContext::ParentMap *ParentMap) {
309   return MatchParents<T, U...>::match(NodeList, ParentMap);
310 }
311 
312 /// Template specializations to abstract away from pointers and TypeLocs.
313 /// @{
314 template <typename T> static DynTypedNode createDynTypedNode(const T &Node) {
315   return DynTypedNode::create(*Node);
316 }
317 template <> DynTypedNode createDynTypedNode(const TypeLoc &Node) {
318   return DynTypedNode::create(Node);
319 }
320 template <>
321 DynTypedNode createDynTypedNode(const NestedNameSpecifierLoc &Node) {
322   return DynTypedNode::create(Node);
323 }
324 template <> DynTypedNode createDynTypedNode(const ObjCProtocolLoc &Node) {
325   return DynTypedNode::create(Node);
326 }
327 /// @}
328 
329 /// A \c RecursiveASTVisitor that builds a map from nodes to their
330 /// parents as defined by the \c RecursiveASTVisitor.
331 ///
332 /// Note that the relationship described here is purely in terms of AST
333 /// traversal - there are other relationships (for example declaration context)
334 /// in the AST that are better modeled by special matchers.
335 class ParentMapContext::ParentMap::ASTVisitor
336     : public RecursiveASTVisitor<ASTVisitor> {
337 public:
338   ASTVisitor(ParentMap &Map) : Map(Map) {}
339 
340 private:
341   friend class RecursiveASTVisitor<ASTVisitor>;
342 
343   using VisitorBase = RecursiveASTVisitor<ASTVisitor>;
344 
345   bool shouldVisitTemplateInstantiations() const { return true; }
346 
347   bool shouldVisitImplicitCode() const { return true; }
348 
349   /// Record the parent of the node we're visiting.
350   /// MapNode is the child, the parent is on top of ParentStack.
351   /// Parents is the parent storage (either PointerParents or OtherParents).
352   template <typename MapNodeTy, typename MapTy>
353   void addParent(MapNodeTy MapNode, MapTy *Parents) {
354     if (ParentStack.empty())
355       return;
356 
357     // FIXME: Currently we add the same parent multiple times, but only
358     // when no memoization data is available for the type.
359     // For example when we visit all subexpressions of template
360     // instantiations; this is suboptimal, but benign: the only way to
361     // visit those is with hasAncestor / hasParent, and those do not create
362     // new matches.
363     // The plan is to enable DynTypedNode to be storable in a map or hash
364     // map. The main problem there is to implement hash functions /
365     // comparison operators for all types that DynTypedNode supports that
366     // do not have pointer identity.
367     auto &NodeOrVector = (*Parents)[MapNode];
368     if (NodeOrVector.isNull()) {
369       if (const auto *D = ParentStack.back().get<Decl>())
370         NodeOrVector = D;
371       else if (const auto *S = ParentStack.back().get<Stmt>())
372         NodeOrVector = S;
373       else
374         NodeOrVector = new DynTypedNode(ParentStack.back());
375     } else {
376       if (!NodeOrVector.template is<ParentVector *>()) {
377         auto *Vector = new ParentVector(
378             1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
379         delete NodeOrVector.template dyn_cast<DynTypedNode *>();
380         NodeOrVector = Vector;
381       }
382 
383       auto *Vector = NodeOrVector.template get<ParentVector *>();
384       // Skip duplicates for types that have memoization data.
385       // We must check that the type has memoization data before calling
386       // llvm::is_contained() because DynTypedNode::operator== can't compare all
387       // types.
388       bool Found = ParentStack.back().getMemoizationData() &&
389                    llvm::is_contained(*Vector, ParentStack.back());
390       if (!Found)
391         Vector->push_back(ParentStack.back());
392     }
393   }
394 
395   template <typename T> static bool isNull(T Node) { return !Node; }
396   static bool isNull(ObjCProtocolLoc Node) { return false; }
397 
398   template <typename T, typename MapNodeTy, typename BaseTraverseFn,
399             typename MapTy>
400   bool TraverseNode(T Node, MapNodeTy MapNode, BaseTraverseFn BaseTraverse,
401                     MapTy *Parents) {
402     if (isNull(Node))
403       return true;
404     addParent(MapNode, Parents);
405     ParentStack.push_back(createDynTypedNode(Node));
406     bool Result = BaseTraverse();
407     ParentStack.pop_back();
408     return Result;
409   }
410 
411   bool TraverseDecl(Decl *DeclNode) {
412     return TraverseNode(
413         DeclNode, DeclNode, [&] { return VisitorBase::TraverseDecl(DeclNode); },
414         &Map.PointerParents);
415   }
416   bool TraverseTypeLoc(TypeLoc TypeLocNode) {
417     return TraverseNode(
418         TypeLocNode, DynTypedNode::create(TypeLocNode),
419         [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); },
420         &Map.OtherParents);
421   }
422   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) {
423     return TraverseNode(
424         NNSLocNode, DynTypedNode::create(NNSLocNode),
425         [&] { return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode); },
426         &Map.OtherParents);
427   }
428   bool TraverseAttr(Attr *AttrNode) {
429     return TraverseNode(
430         AttrNode, AttrNode, [&] { return VisitorBase::TraverseAttr(AttrNode); },
431         &Map.PointerParents);
432   }
433   bool TraverseObjCProtocolLoc(ObjCProtocolLoc ProtocolLocNode) {
434     return TraverseNode(
435         ProtocolLocNode, DynTypedNode::create(ProtocolLocNode),
436         [&] { return VisitorBase::TraverseObjCProtocolLoc(ProtocolLocNode); },
437         &Map.OtherParents);
438   }
439 
440   // Using generic TraverseNode for Stmt would prevent data-recursion.
441   bool dataTraverseStmtPre(Stmt *StmtNode) {
442     addParent(StmtNode, &Map.PointerParents);
443     ParentStack.push_back(DynTypedNode::create(*StmtNode));
444     return true;
445   }
446   bool dataTraverseStmtPost(Stmt *StmtNode) {
447     ParentStack.pop_back();
448     return true;
449   }
450 
451   ParentMap &Map;
452   llvm::SmallVector<DynTypedNode, 16> ParentStack;
453 };
454 
455 ParentMapContext::ParentMap::ParentMap(ASTContext &Ctx) {
456   ASTVisitor(*this).TraverseAST(Ctx);
457 }
458 
459 DynTypedNodeList ParentMapContext::getParents(const DynTypedNode &Node) {
460   if (!Parents)
461     // We build the parent map for the traversal scope (usually whole TU), as
462     // hasAncestor can escape any subtree.
463     Parents = std::make_unique<ParentMap>(ASTCtx);
464   return Parents->getParents(getTraversalKind(), Node);
465 }
466