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::makeArrayRef(*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::makeArrayRef(*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 Tuple, std::size_t... Is>
269 auto tuple_pop_front_impl(const Tuple &tuple, std::index_sequence<Is...>) {
270   return std::make_tuple(std::get<1 + Is>(tuple)...);
271 }
272 
273 template <typename Tuple> auto tuple_pop_front(const Tuple &tuple) {
274   return tuple_pop_front_impl(
275       tuple, std::make_index_sequence<std::tuple_size<Tuple>::value - 1>());
276 }
277 
278 template <typename T, typename... U> struct MatchParents {
279   static std::tuple<bool, DynTypedNodeList, const T *, const U *...>
280   match(const DynTypedNodeList &NodeList,
281         ParentMapContext::ParentMap *ParentMap) {
282     if (const auto *TypedNode = NodeList[0].get<T>()) {
283       auto NextParentList =
284           ParentMap->getDynNodeFromMap(TypedNode, ParentMap->PointerParents);
285       if (NextParentList.size() == 1) {
286         auto TailTuple = MatchParents<U...>::match(NextParentList, ParentMap);
287         if (std::get<bool>(TailTuple)) {
288           return std::tuple_cat(
289               std::make_tuple(true, std::get<DynTypedNodeList>(TailTuple),
290                               TypedNode),
291               tuple_pop_front(tuple_pop_front(TailTuple)));
292         }
293       }
294     }
295     return std::tuple_cat(std::make_tuple(false, NodeList),
296                           std::tuple<const T *, const U *...>());
297   }
298 };
299 
300 template <typename T> struct MatchParents<T> {
301   static std::tuple<bool, DynTypedNodeList, const T *>
302   match(const DynTypedNodeList &NodeList,
303         ParentMapContext::ParentMap *ParentMap) {
304     if (const auto *TypedNode = NodeList[0].get<T>()) {
305       auto NextParentList =
306           ParentMap->getDynNodeFromMap(TypedNode, ParentMap->PointerParents);
307       if (NextParentList.size() == 1)
308         return std::make_tuple(true, NodeList, TypedNode);
309     }
310     return std::make_tuple(false, NodeList, nullptr);
311   }
312 };
313 
314 template <typename T, typename... U>
315 std::tuple<bool, DynTypedNodeList, const T *, const U *...>
316 matchParents(const DynTypedNodeList &NodeList,
317              ParentMapContext::ParentMap *ParentMap) {
318   return MatchParents<T, U...>::match(NodeList, ParentMap);
319 }
320 
321 /// Template specializations to abstract away from pointers and TypeLocs.
322 /// @{
323 template <typename T> static DynTypedNode createDynTypedNode(const T &Node) {
324   return DynTypedNode::create(*Node);
325 }
326 template <> DynTypedNode createDynTypedNode(const TypeLoc &Node) {
327   return DynTypedNode::create(Node);
328 }
329 template <>
330 DynTypedNode createDynTypedNode(const NestedNameSpecifierLoc &Node) {
331   return DynTypedNode::create(Node);
332 }
333 /// @}
334 
335 /// A \c RecursiveASTVisitor that builds a map from nodes to their
336 /// parents as defined by the \c RecursiveASTVisitor.
337 ///
338 /// Note that the relationship described here is purely in terms of AST
339 /// traversal - there are other relationships (for example declaration context)
340 /// in the AST that are better modeled by special matchers.
341 class ParentMapContext::ParentMap::ASTVisitor
342     : public RecursiveASTVisitor<ASTVisitor> {
343 public:
344   ASTVisitor(ParentMap &Map) : Map(Map) {}
345 
346 private:
347   friend class RecursiveASTVisitor<ASTVisitor>;
348 
349   using VisitorBase = RecursiveASTVisitor<ASTVisitor>;
350 
351   bool shouldVisitTemplateInstantiations() const { return true; }
352 
353   bool shouldVisitImplicitCode() const { return true; }
354 
355   /// Record the parent of the node we're visiting.
356   /// MapNode is the child, the parent is on top of ParentStack.
357   /// Parents is the parent storage (either PointerParents or OtherParents).
358   template <typename MapNodeTy, typename MapTy>
359   void addParent(MapNodeTy MapNode, MapTy *Parents) {
360     if (ParentStack.empty())
361       return;
362 
363     // FIXME: Currently we add the same parent multiple times, but only
364     // when no memoization data is available for the type.
365     // For example when we visit all subexpressions of template
366     // instantiations; this is suboptimal, but benign: the only way to
367     // visit those is with hasAncestor / hasParent, and those do not create
368     // new matches.
369     // The plan is to enable DynTypedNode to be storable in a map or hash
370     // map. The main problem there is to implement hash functions /
371     // comparison operators for all types that DynTypedNode supports that
372     // do not have pointer identity.
373     auto &NodeOrVector = (*Parents)[MapNode];
374     if (NodeOrVector.isNull()) {
375       if (const auto *D = ParentStack.back().get<Decl>())
376         NodeOrVector = D;
377       else if (const auto *S = ParentStack.back().get<Stmt>())
378         NodeOrVector = S;
379       else
380         NodeOrVector = new DynTypedNode(ParentStack.back());
381     } else {
382       if (!NodeOrVector.template is<ParentVector *>()) {
383         auto *Vector = new ParentVector(
384             1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
385         delete NodeOrVector.template dyn_cast<DynTypedNode *>();
386         NodeOrVector = Vector;
387       }
388 
389       auto *Vector = NodeOrVector.template get<ParentVector *>();
390       // Skip duplicates for types that have memoization data.
391       // We must check that the type has memoization data before calling
392       // std::find() because DynTypedNode::operator== can't compare all
393       // types.
394       bool Found = ParentStack.back().getMemoizationData() &&
395                    std::find(Vector->begin(), Vector->end(),
396                              ParentStack.back()) != Vector->end();
397       if (!Found)
398         Vector->push_back(ParentStack.back());
399     }
400   }
401 
402   template <typename T, typename MapNodeTy, typename BaseTraverseFn,
403             typename MapTy>
404   bool TraverseNode(T Node, MapNodeTy MapNode, BaseTraverseFn BaseTraverse,
405                     MapTy *Parents) {
406     if (!Node)
407       return true;
408     addParent(MapNode, Parents);
409     ParentStack.push_back(createDynTypedNode(Node));
410     bool Result = BaseTraverse();
411     ParentStack.pop_back();
412     return Result;
413   }
414 
415   bool TraverseDecl(Decl *DeclNode) {
416     return TraverseNode(
417         DeclNode, DeclNode, [&] { return VisitorBase::TraverseDecl(DeclNode); },
418         &Map.PointerParents);
419   }
420   bool TraverseTypeLoc(TypeLoc TypeLocNode) {
421     return TraverseNode(
422         TypeLocNode, DynTypedNode::create(TypeLocNode),
423         [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); },
424         &Map.OtherParents);
425   }
426   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) {
427     return TraverseNode(
428         NNSLocNode, DynTypedNode::create(NNSLocNode),
429         [&] { return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode); },
430         &Map.OtherParents);
431   }
432 
433   // Using generic TraverseNode for Stmt would prevent data-recursion.
434   bool dataTraverseStmtPre(Stmt *StmtNode) {
435     addParent(StmtNode, &Map.PointerParents);
436     ParentStack.push_back(DynTypedNode::create(*StmtNode));
437     return true;
438   }
439   bool dataTraverseStmtPost(Stmt *StmtNode) {
440     ParentStack.pop_back();
441     return true;
442   }
443 
444   ParentMap &Map;
445   llvm::SmallVector<DynTypedNode, 16> ParentStack;
446 };
447 
448 ParentMapContext::ParentMap::ParentMap(ASTContext &Ctx) {
449   ASTVisitor(*this).TraverseAST(Ctx);
450 }
451 
452 DynTypedNodeList ParentMapContext::getParents(const DynTypedNode &Node) {
453   if (!Parents)
454     // We build the parent map for the traversal scope (usually whole TU), as
455     // hasAncestor can escape any subtree.
456     Parents = std::make_unique<ParentMap>(ASTCtx);
457   return Parents->getParents(getTraversalKind(), Node);
458 }
459