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
20using namespace clang;
21
22ParentMapContext::ParentMapContext(ASTContext &Ctx) : ASTCtx(Ctx) {}
23
24ParentMapContext::~ParentMapContext() = default;
25
26void ParentMapContext::clear() { Parents.reset(); }
27
28const Expr *ParentMapContext::traverseIgnored(const Expr *E) const {
29  return traverseIgnored(const_cast<Expr *>(E));
30}
31
32Expr *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
47DynTypedNode 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
54class 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
99public:
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/// @{
196template <typename T> static DynTypedNode createDynTypedNode(const T &Node) {
197  return DynTypedNode::create(*Node);
198}
199template <> DynTypedNode createDynTypedNode(const TypeLoc &Node) {
200  return DynTypedNode::create(Node);
201}
202template <>
203DynTypedNode 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.
216class ParentMapContext::ParentMap::ASTVisitor
217    : public RecursiveASTVisitor<ASTVisitor> {
218public:
219  ASTVisitor(ParentMap &Map) : Map(Map) {}
220
221private:
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
311ParentMapContext::ParentMap::ParentMap(ASTContext &Ctx) {
312  ASTVisitor(*this).TraverseAST(Ctx);
313}
314
315DynTypedNodeList 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