Coverage Report

Created: 2020-09-22 08:39

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/AST/ParentMapContext.cpp
Line
Count
Source (jump to first uncovered line)
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
19.1k
ParentMapContext::ParentMapContext(ASTContext &Ctx) : ASTCtx(Ctx) {}
23
24
19.1k
ParentMapContext::~ParentMapContext() = default;
25
26
70
void ParentMapContext::clear() { Parents.reset(); }
27
28
220k
const Expr *ParentMapContext::traverseIgnored(const Expr *E) const {
29
220k
  return traverseIgnored(const_cast<Expr *>(E));
30
220k
}
31
32
254k
Expr *ParentMapContext::traverseIgnored(Expr *E) const {
33
254k
  if (!E)
34
0
    return nullptr;
35
36
254k
  switch (Traversal) {
37
254k
  case TK_AsIs:
38
254k
    return E;
39
17
  case TK_IgnoreImplicitCastsAndParentheses:
40
17
    return E->IgnoreParenImpCasts();
41
486
  case TK_IgnoreUnlessSpelledInSource:
42
486
    return E->IgnoreUnlessSpelledInSource();
43
0
  }
44
0
  llvm_unreachable("Invalid Traversal type!");
45
0
}
46
47
571k
DynTypedNode ParentMapContext::traverseIgnored(const DynTypedNode &N) const {
48
571k
  if (const auto *E = N.get<Expr>()) {
49
220k
    return DynTypedNode::create(*traverseIgnored(E));
50
220k
  }
51
351k
  return N;
52
351k
}
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
13.1k
  getSingleDynTypedNodeFromParentMap(ParentMapPointers::mapped_type U) {
79
13.1k
    if (const auto *D = U.dyn_cast<const Decl *>())
80
6.45k
      return DynTypedNode::create(*D);
81
6.70k
    if (const auto *S = U.dyn_cast<const Stmt *>())
82
4.02k
      return DynTypedNode::create(*S);
83
2.67k
    return *U.get<DynTypedNode *>();
84
2.67k
  }
85
86
  template <typename NodeTy, typename MapTy>
87
  static DynTypedNodeList getDynNodeFromMap(const NodeTy &Node,
88
13.5k
                                                        const MapTy &Map) {
89
13.5k
    auto I = Map.find(Node);
90
13.5k
    if (I == Map.end()) {
91
814
      return llvm::ArrayRef<DynTypedNode>();
92
814
    }
93
12.7k
    if (const auto *V = I->second.template dyn_cast<ParentVector *>()) {
94
100
      return llvm::makeArrayRef(*V);
95
100
    }
96
12.6k
    return getSingleDynTypedNodeFromParentMap(I->second);
97
12.6k
  }
clang::DynTypedNodeList clang::ParentMapContext::ParentMap::getDynNodeFromMap<void const*, llvm::DenseMap<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<void const*>, llvm::detail::DenseMapPair<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > > >(void const* const&, llvm::DenseMap<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<void const*>, llvm::detail::DenseMapPair<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > > const&)
Line
Count
Source
88
7.96k
                                                        const MapTy &Map) {
89
7.96k
    auto I = Map.find(Node);
90
7.96k
    if (I == Map.end()) {
91
763
      return llvm::ArrayRef<DynTypedNode>();
92
763
    }
93
7.20k
    if (const auto *V = I->second.template dyn_cast<ParentVector *>()) {
94
89
      return llvm::makeArrayRef(*V);
95
89
    }
96
7.11k
    return getSingleDynTypedNodeFromParentMap(I->second);
97
7.11k
  }
clang::DynTypedNodeList clang::ParentMapContext::ParentMap::getDynNodeFromMap<clang::DynTypedNode, llvm::DenseMap<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<clang::DynTypedNode>, llvm::detail::DenseMapPair<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > > >(clang::DynTypedNode const&, llvm::DenseMap<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<clang::DynTypedNode>, llvm::detail::DenseMapPair<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > > const&)
Line
Count
Source
88
5.62k
                                                        const MapTy &Map) {
89
5.62k
    auto I = Map.find(Node);
90
5.62k
    if (I == Map.end()) {
91
51
      return llvm::ArrayRef<DynTypedNode>();
92
51
    }
93
5.57k
    if (const auto *V = I->second.template dyn_cast<ParentVector *>()) {
94
11
      return llvm::makeArrayRef(*V);
95
11
    }
96
5.56k
    return getSingleDynTypedNodeFromParentMap(I->second);
97
5.56k
  }
98
99
public:
100
  ParentMap(ASTContext &Ctx);
101
936
  ~ParentMap() {
102
29.7k
    for (const auto &Entry : PointerParents) {
103
29.7k
      if (Entry.second.is<DynTypedNode *>()) {
104
859
        delete Entry.second.get<DynTypedNode *>();
105
28.9k
      } else if (Entry.second.is<ParentVector *>()) {
106
199
        delete Entry.second.get<ParentVector *>();
107
199
      }
108
29.7k
    }
109
18.9k
    for (const auto &Entry : OtherParents) {
110
18.9k
      if (Entry.second.is<DynTypedNode *>()) {
111
7.57k
        delete Entry.second.get<DynTypedNode *>();
112
11.3k
      } else if (Entry.second.is<ParentVector *>()) {
113
278
        delete Entry.second.get<ParentVector *>();
114
278
      }
115
18.9k
    }
116
936
  }
117
118
13.5k
  DynTypedNodeList getParents(TraversalKind TK, const DynTypedNode &Node) {
119
13.5k
    if (Node.getNodeKind().hasPointerIdentity()) {
120
7.96k
      auto ParentList =
121
7.96k
          getDynNodeFromMap(Node.getMemoizationData(), PointerParents);
122
7.96k
      if (ParentList.size() == 1 && 
TK == TK_IgnoreUnlessSpelledInSource7.16k
) {
123
676
        const auto *E = ParentList[0].get<Expr>();
124
676
        const auto *Child = Node.get<Expr>();
125
676
        if (E && 
Child48
)
126
46
          return AscendIgnoreUnlessSpelledInSource(E, Child);
127
7.91k
      }
128
7.91k
      return ParentList;
129
7.91k
    }
130
5.62k
    return getDynNodeFromMap(Node, OtherParents);
131
5.62k
  }
132
133
  DynTypedNodeList AscendIgnoreUnlessSpelledInSource(const Expr *E,
134
46
                                                     const Expr *Child) {
135
136
78
    auto ShouldSkip = [](const Expr *E, const Expr *Child) {
137
78
      if (isa<ImplicitCastExpr>(E))
138
34
        return true;
139
140
44
      if (isa<FullExpr>(E))
141
0
        return true;
142
143
44
      if (isa<MaterializeTemporaryExpr>(E))
144
0
        return true;
145
146
44
      if (isa<CXXBindTemporaryExpr>(E))
147
0
        return true;
148
149
44
      if (isa<ParenExpr>(E))
150
2
        return true;
151
152
42
      if (isa<ExprWithCleanups>(E))
153
0
        return true;
154
155
42
      auto SR = Child->getSourceRange();
156
157
42
      if (const auto *C = dyn_cast<CXXConstructExpr>(E)) {
158
24
        if (C->getSourceRange() == SR || 
!isa<CXXTemporaryObjectExpr>(C)12
)
159
18
          return true;
160
24
      }
161
162
24
      if (const auto *C = dyn_cast<CXXMemberCallExpr>(E)) {
163
2
        if (C->getSourceRange() == SR)
164
2
          return true;
165
22
      }
166
167
22
      if (const auto *C = dyn_cast<MemberExpr>(E)) {
168
2
        if (C->getSourceRange() == SR)
169
2
          return true;
170
20
      }
171
20
      return false;
172
20
    };
173
174
78
    while (ShouldSkip(E, Child)) {
175
58
      auto It = PointerParents.find(E);
176
58
      if (It == PointerParents.end())
177
0
        break;
178
58
      const auto *S = It->second.dyn_cast<const Stmt *>();
179
58
      if (!S) {
180
12
        if (auto *Vec = It->second.dyn_cast<ParentVector *>())
181
4
          return llvm::makeArrayRef(*Vec);
182
8
        return getSingleDynTypedNodeFromParentMap(It->second);
183
8
      }
184
46
      const auto *P = dyn_cast<Expr>(S);
185
46
      if (!P)
186
14
        return DynTypedNode::create(*S);
187
32
      Child = E;
188
32
      E = P;
189
32
    }
190
20
    return DynTypedNode::create(*E);
191
46
  }
192
};
193
194
/// Template specializations to abstract away from pointers and TypeLocs.
195
/// @{
196
31.0k
template <typename T> static DynTypedNode createDynTypedNode(const T &Node) {
197
31.0k
  return DynTypedNode::create(*Node);
198
31.0k
}
ParentMapContext.cpp:clang::DynTypedNode createDynTypedNode<clang::Decl*>(clang::Decl* const&)
Line
Count
Source
196
22.0k
template <typename T> static DynTypedNode createDynTypedNode(const T &Node) {
197
22.0k
  return DynTypedNode::create(*Node);
198
22.0k
}
ParentMapContext.cpp:clang::DynTypedNode createDynTypedNode<clang::Stmt*>(clang::Stmt* const&)
Line
Count
Source
196
8.95k
template <typename T> static DynTypedNode createDynTypedNode(const T &Node) {
197
8.95k
  return DynTypedNode::create(*Node);
198
8.95k
}
199
18.5k
template <> DynTypedNode createDynTypedNode(const TypeLoc &Node) {
200
18.5k
  return DynTypedNode::create(Node);
201
18.5k
}
202
template <>
203
768
DynTypedNode createDynTypedNode(const NestedNameSpecifierLoc &Node) {
204
768
  return DynTypedNode::create(Node);
205
768
}
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
936
  ASTVisitor(ParentMap &Map) : Map(Map) {}
220
221
private:
222
  friend class RecursiveASTVisitor<ASTVisitor>;
223
224
  using VisitorBase = RecursiveASTVisitor<ASTVisitor>;
225
226
990
  bool shouldVisitTemplateInstantiations() const { return true; }
227
228
25.3k
  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
67.7k
                    MapTy *Parents) {
234
67.7k
    if (!Node)
235
17.4k
      return true;
236
50.3k
    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
49.4k
      auto &NodeOrVector = (*Parents)[MapNode];
248
49.4k
      if (NodeOrVector.isNull()) {
249
48.7k
        if (const auto *D = ParentStack.back().get<Decl>())
250
32.7k
          NodeOrVector = D;
251
15.9k
        else if (const auto *S = ParentStack.back().get<Stmt>())
252
7.42k
          NodeOrVector = S;
253
8.56k
        else
254
8.56k
          NodeOrVector = new DynTypedNode(ParentStack.back());
255
680
      } else {
256
680
        if (!NodeOrVector.template is<ParentVector *>()) {
257
477
          auto *Vector = new ParentVector(
258
477
              1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
259
477
          delete NodeOrVector.template dyn_cast<DynTypedNode *>();
260
477
          NodeOrVector = Vector;
261
477
        }
262
263
680
        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
680
        bool Found = ParentStack.back().getMemoizationData() &&
269
460
                     std::find(Vector->begin(), Vector->end(),
270
460
                               ParentStack.back()) != Vector->end();
271
680
        if (!Found)
272
497
          Vector->push_back(ParentStack.back());
273
680
      }
274
49.4k
    }
275
50.3k
    ParentStack.push_back(createDynTypedNode(Node));
276
50.3k
    bool Result = BaseTraverse();
277
50.3k
    ParentStack.pop_back();
278
50.3k
    return Result;
279
50.3k
  }
bool clang::ParentMapContext::ParentMap::ASTVisitor::TraverseNode<clang::Decl*, clang::Decl*, clang::ParentMapContext::ParentMap::ASTVisitor::TraverseDecl(clang::Decl*)::'lambda'(), llvm::DenseMap<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<void const*>, llvm::detail::DenseMapPair<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > > >(clang::Decl*, clang::Decl*, clang::ParentMapContext::ParentMap::ASTVisitor::TraverseDecl(clang::Decl*)::'lambda'(), llvm::DenseMap<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<void const*>, llvm::detail::DenseMapPair<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > >*)
Line
Count
Source
233
22.0k
                    MapTy *Parents) {
234
22.0k
    if (!Node)
235
0
      return true;
236
22.0k
    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
21.1k
      auto &NodeOrVector = (*Parents)[MapNode];
248
21.1k
      if (NodeOrVector.isNull()) {
249
20.9k
        if (const auto *D = ParentStack.back().get<Decl>())
250
19.1k
          NodeOrVector = D;
251
1.75k
        else if (const auto *S = ParentStack.back().get<Stmt>())
252
900
          NodeOrVector = S;
253
852
        else
254
852
          NodeOrVector = new DynTypedNode(ParentStack.back());
255
186
      } else {
256
186
        if (!NodeOrVector.template is<ParentVector *>()) {
257
76
          auto *Vector = new ParentVector(
258
76
              1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
259
76
          delete NodeOrVector.template dyn_cast<DynTypedNode *>();
260
76
          NodeOrVector = Vector;
261
76
        }
262
263
186
        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
186
        bool Found = ParentStack.back().getMemoizationData() &&
269
53
                     std::find(Vector->begin(), Vector->end(),
270
53
                               ParentStack.back()) != Vector->end();
271
186
        if (!Found)
272
186
          Vector->push_back(ParentStack.back());
273
186
      }
274
21.1k
    }
275
22.0k
    ParentStack.push_back(createDynTypedNode(Node));
276
22.0k
    bool Result = BaseTraverse();
277
22.0k
    ParentStack.pop_back();
278
22.0k
    return Result;
279
22.0k
  }
bool clang::ParentMapContext::ParentMap::ASTVisitor::TraverseNode<clang::Stmt*, clang::Stmt*, clang::ParentMapContext::ParentMap::ASTVisitor::TraverseStmt(clang::Stmt*)::'lambda'(), llvm::DenseMap<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<void const*>, llvm::detail::DenseMapPair<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > > >(clang::Stmt*, clang::Stmt*, clang::ParentMapContext::ParentMap::ASTVisitor::TraverseStmt(clang::Stmt*)::'lambda'(), llvm::DenseMap<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<void const*>, llvm::detail::DenseMapPair<void const*, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > >*)
Line
Count
Source
233
11.8k
                    MapTy *Parents) {
234
11.8k
    if (!Node)
235
2.91k
      return true;
236
8.95k
    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
8.95k
      auto &NodeOrVector = (*Parents)[MapNode];
248
8.95k
      if (NodeOrVector.isNull()) {
249
8.83k
        if (const auto *D = ParentStack.back().get<Decl>())
250
2.78k
          NodeOrVector = D;
251
6.04k
        else if (const auto *S = ParentStack.back().get<Stmt>())
252
5.99k
          NodeOrVector = S;
253
53
        else
254
53
          NodeOrVector = new DynTypedNode(ParentStack.back());
255
126
      } else {
256
126
        if (!NodeOrVector.template is<ParentVector *>()) {
257
123
          auto *Vector = new ParentVector(
258
123
              1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
259
123
          delete NodeOrVector.template dyn_cast<DynTypedNode *>();
260
123
          NodeOrVector = Vector;
261
123
        }
262
263
126
        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
126
        bool Found = ParentStack.back().getMemoizationData() &&
269
126
                     std::find(Vector->begin(), Vector->end(),
270
126
                               ParentStack.back()) != Vector->end();
271
126
        if (!Found)
272
77
          Vector->push_back(ParentStack.back());
273
126
      }
274
8.95k
    }
275
8.95k
    ParentStack.push_back(createDynTypedNode(Node));
276
8.95k
    bool Result = BaseTraverse();
277
8.95k
    ParentStack.pop_back();
278
8.95k
    return Result;
279
8.95k
  }
bool clang::ParentMapContext::ParentMap::ASTVisitor::TraverseNode<clang::NestedNameSpecifierLoc, clang::DynTypedNode, clang::ParentMapContext::ParentMap::ASTVisitor::TraverseNestedNameSpecifierLoc(clang::NestedNameSpecifierLoc)::'lambda'(), llvm::DenseMap<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<clang::DynTypedNode>, llvm::detail::DenseMapPair<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > > >(clang::NestedNameSpecifierLoc, clang::DynTypedNode, clang::ParentMapContext::ParentMap::ASTVisitor::TraverseNestedNameSpecifierLoc(clang::NestedNameSpecifierLoc)::'lambda'(), llvm::DenseMap<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<clang::DynTypedNode>, llvm::detail::DenseMapPair<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > >*)
Line
Count
Source
233
15.2k
                    MapTy *Parents) {
234
15.2k
    if (!Node)
235
14.5k
      return true;
236
768
    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
768
      auto &NodeOrVector = (*Parents)[MapNode];
248
768
      if (NodeOrVector.isNull()) {
249
763
        if (const auto *D = ParentStack.back().get<Decl>())
250
109
          NodeOrVector = D;
251
654
        else if (const auto *S = ParentStack.back().get<Stmt>())
252
115
          NodeOrVector = S;
253
539
        else
254
539
          NodeOrVector = new DynTypedNode(ParentStack.back());
255
5
      } else {
256
5
        if (!NodeOrVector.template is<ParentVector *>()) {
257
5
          auto *Vector = new ParentVector(
258
5
              1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
259
5
          delete NodeOrVector.template dyn_cast<DynTypedNode *>();
260
5
          NodeOrVector = Vector;
261
5
        }
262
263
5
        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
5
        bool Found = ParentStack.back().getMemoizationData() &&
269
4
                     std::find(Vector->begin(), Vector->end(),
270
4
                               ParentStack.back()) != Vector->end();
271
5
        if (!Found)
272
5
          Vector->push_back(ParentStack.back());
273
5
      }
274
768
    }
275
768
    ParentStack.push_back(createDynTypedNode(Node));
276
768
    bool Result = BaseTraverse();
277
768
    ParentStack.pop_back();
278
768
    return Result;
279
768
  }
bool clang::ParentMapContext::ParentMap::ASTVisitor::TraverseNode<clang::TypeLoc, clang::DynTypedNode, clang::ParentMapContext::ParentMap::ASTVisitor::TraverseTypeLoc(clang::TypeLoc)::'lambda'(), llvm::DenseMap<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<clang::DynTypedNode>, llvm::detail::DenseMapPair<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > > >(clang::TypeLoc, clang::DynTypedNode, clang::ParentMapContext::ParentMap::ASTVisitor::TraverseTypeLoc(clang::TypeLoc)::'lambda'(), llvm::DenseMap<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*>, llvm::DenseMapInfo<clang::DynTypedNode>, llvm::detail::DenseMapPair<clang::DynTypedNode, llvm::PointerUnion<clang::Decl const*, clang::Stmt const*, clang::DynTypedNode*, llvm::SmallVector<clang::DynTypedNode, 2u>*> > >*)
Line
Count
Source
233
18.5k
                    MapTy *Parents) {
234
18.5k
    if (!Node)
235
0
      return true;
236
18.5k
    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
18.5k
      auto &NodeOrVector = (*Parents)[MapNode];
248
18.5k
      if (NodeOrVector.isNull()) {
249
18.2k
        if (const auto *D = ParentStack.back().get<Decl>())
250
10.6k
          NodeOrVector = D;
251
7.54k
        else if (const auto *S = ParentStack.back().get<Stmt>())
252
420
          NodeOrVector = S;
253
7.12k
        else
254
7.12k
          NodeOrVector = new DynTypedNode(ParentStack.back());
255
363
      } else {
256
363
        if (!NodeOrVector.template is<ParentVector *>()) {
257
273
          auto *Vector = new ParentVector(
258
273
              1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
259
273
          delete NodeOrVector.template dyn_cast<DynTypedNode *>();
260
273
          NodeOrVector = Vector;
261
273
        }
262
263
363
        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
363
        bool Found = ParentStack.back().getMemoizationData() &&
269
277
                     std::find(Vector->begin(), Vector->end(),
270
277
                               ParentStack.back()) != Vector->end();
271
363
        if (!Found)
272
229
          Vector->push_back(ParentStack.back());
273
363
      }
274
18.5k
    }
275
18.5k
    ParentStack.push_back(createDynTypedNode(Node));
276
18.5k
    bool Result = BaseTraverse();
277
18.5k
    ParentStack.pop_back();
278
18.5k
    return Result;
279
18.5k
  }
280
281
22.0k
  bool TraverseDecl(Decl *DeclNode) {
282
22.0k
    return TraverseNode(
283
22.0k
        DeclNode, DeclNode, [&] { return VisitorBase::TraverseDecl(DeclNode); },
284
22.0k
        &Map.PointerParents);
285
22.0k
  }
286
287
11.8k
  bool TraverseStmt(Stmt *StmtNode) {
288
11.8k
    return TraverseNode(StmtNode, StmtNode,
289
8.95k
                        [&] { return VisitorBase::TraverseStmt(StmtNode); },
290
11.8k
                        &Map.PointerParents);
291
11.8k
  }
292
293
18.5k
  bool TraverseTypeLoc(TypeLoc TypeLocNode) {
294
18.5k
    return TraverseNode(
295
18.5k
        TypeLocNode, DynTypedNode::create(TypeLocNode),
296
18.5k
        [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); },
297
18.5k
        &Map.OtherParents);
298
18.5k
  }
299
300
15.2k
  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) {
301
15.2k
    return TraverseNode(
302
15.2k
        NNSLocNode, DynTypedNode::create(NNSLocNode),
303
768
        [&] { return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode); },
304
15.2k
        &Map.OtherParents);
305
15.2k
  }
306
307
  ParentMap &Map;
308
  llvm::SmallVector<DynTypedNode, 16> ParentStack;
309
};
310
311
936
ParentMapContext::ParentMap::ParentMap(ASTContext &Ctx) {
312
936
  ASTVisitor(*this).TraverseAST(Ctx);
313
936
}
314
315
13.5k
DynTypedNodeList ParentMapContext::getParents(const DynTypedNode &Node) {
316
13.5k
  if (!Parents)
317
    // We build the parent map for the traversal scope (usually whole TU), as
318
    // hasAncestor can escape any subtree.
319
936
    Parents = std::make_unique<ParentMap>(ASTCtx);
320
13.5k
  return Parents->getParents(getTraversalKind(), Node);
321
13.5k
}