Coverage Report

Created: 2020-02-15 09:57

/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
6.96k
ParentMapContext::ParentMapContext(ASTContext &Ctx) : ASTCtx(Ctx) {}
23
24
6.95k
ParentMapContext::~ParentMapContext() = default;
25
26
3
void ParentMapContext::clear() { Parents.reset(); }
27
28
206k
const Expr *ParentMapContext::traverseIgnored(const Expr *E) const {
29
206k
  return traverseIgnored(const_cast<Expr *>(E));
30
206k
}
31
32
239k
Expr *ParentMapContext::traverseIgnored(Expr *E) const {
33
239k
  if (!E)
34
0
    return nullptr;
35
239k
36
239k
  switch (Traversal) {
37
238k
  case TK_AsIs:
38
238k
    return E;
39
17
  case TK_IgnoreImplicitCastsAndParentheses:
40
17
    return E->IgnoreParenImpCasts();
41
456
  case TK_IgnoreUnlessSpelledInSource:
42
456
    return E->IgnoreUnlessSpelledInSource();
43
0
  }
44
0
  llvm_unreachable("Invalid Traversal type!");
45
0
}
46
47
372k
DynTypedNode ParentMapContext::traverseIgnored(const DynTypedNode &N) const {
48
372k
  if (const auto *E = N.get<Expr>()) {
49
206k
    return DynTypedNode::create(*traverseIgnored(E));
50
206k
  }
51
165k
  return N;
52
165k
}
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
12.0k
  getSingleDynTypedNodeFromParentMap(ParentMapPointers::mapped_type U) {
79
12.0k
    if (const auto *D = U.dyn_cast<const Decl *>())
80
5.81k
      return DynTypedNode::create(*D);
81
6.26k
    if (const auto *S = U.dyn_cast<const Stmt *>())
82
3.60k
      return DynTypedNode::create(*S);
83
2.66k
    return *U.get<DynTypedNode *>();
84
2.66k
  }
85
86
  template <typename NodeTy, typename MapTy>
87
  static DynTypedNodeList getDynNodeFromMap(const NodeTy &Node,
88
12.3k
                                                        const MapTy &Map) {
89
12.3k
    auto I = Map.find(Node);
90
12.3k
    if (I == Map.end()) {
91
651
      return llvm::ArrayRef<DynTypedNode>();
92
651
    }
93
11.7k
    if (const auto *V = I->second.template dyn_cast<ParentVector *>()) {
94
49
      return llvm::makeArrayRef(*V);
95
49
    }
96
11.6k
    return getSingleDynTypedNodeFromParentMap(I->second);
97
11.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
6.73k
                                                        const MapTy &Map) {
89
6.73k
    auto I = Map.find(Node);
90
6.73k
    if (I == Map.end()) {
91
601
      return llvm::ArrayRef<DynTypedNode>();
92
601
    }
93
6.13k
    if (const auto *V = I->second.template dyn_cast<ParentVector *>()) {
94
38
      return llvm::makeArrayRef(*V);
95
38
    }
96
6.10k
    return getSingleDynTypedNodeFromParentMap(I->second);
97
6.10k
  }
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
50
      return llvm::ArrayRef<DynTypedNode>();
92
50
    }
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
685
  ~ParentMap() {
102
26.6k
    for (const auto &Entry : PointerParents) {
103
26.6k
      if (Entry.second.is<DynTypedNode *>()) {
104
717
        delete Entry.second.get<DynTypedNode *>();
105
25.9k
      } else if (Entry.second.is<ParentVector *>()) {
106
154
        delete Entry.second.get<ParentVector *>();
107
154
      }
108
26.6k
    }
109
16.6k
    for (const auto &Entry : OtherParents) {
110
16.6k
      if (Entry.second.is<DynTypedNode *>()) {
111
6.82k
        delete Entry.second.get<DynTypedNode *>();
112
9.83k
      } else if (Entry.second.is<ParentVector *>()) {
113
260
        delete Entry.second.get<ParentVector *>();
114
260
      }
115
16.6k
    }
116
685
  }
117
118
12.3k
  DynTypedNodeList getParents(TraversalKind TK, const DynTypedNode &Node) {
119
12.3k
    if (Node.getNodeKind().hasPointerIdentity()) {
120
6.73k
      auto ParentList =
121
6.73k
          getDynNodeFromMap(Node.getMemoizationData(), PointerParents);
122
6.73k
      if (ParentList.size() == 1 && 
TK == TK_IgnoreUnlessSpelledInSource6.12k
) {
123
633
        const auto *E = ParentList[0].get<Expr>();
124
633
        const auto *Child = Node.get<Expr>();
125
633
        if (E && 
Child25
)
126
24
          return AscendIgnoreUnlessSpelledInSource(E, Child);
127
6.71k
      }
128
6.71k
      return ParentList;
129
6.71k
    }
130
5.62k
    return getDynNodeFromMap(Node, OtherParents);
131
5.62k
  }
132
133
  DynTypedNodeList AscendIgnoreUnlessSpelledInSource(const Expr *E,
134
24
                                                     const Expr *Child) {
135
24
136
62
    auto ShouldSkip = [](const Expr *E, const Expr *Child) {
137
62
      if (isa<ImplicitCastExpr>(E))
138
16
        return true;
139
46
140
46
      if (isa<FullExpr>(E))
141
8
        return true;
142
38
143
38
      if (isa<MaterializeTemporaryExpr>(E))
144
8
        return true;
145
30
146
30
      if (isa<CXXBindTemporaryExpr>(E))
147
0
        return true;
148
30
149
30
      if (isa<ParenExpr>(E))
150
1
        return true;
151
29
152
29
      if (isa<ExprWithCleanups>(E))
153
0
        return true;
154
29
155
29
      auto SR = Child->getSourceRange();
156
29
157
29
      if (const auto *C = dyn_cast<CXXConstructExpr>(E)) {
158
20
        if (C->getSourceRange() == SR || 
!isa<CXXTemporaryObjectExpr>(C)12
)
159
17
          return true;
160
12
      }
161
12
162
12
      if (const auto *C = dyn_cast<CXXMemberCallExpr>(E)) {
163
1
        if (C->getSourceRange() == SR)
164
1
          return true;
165
11
      }
166
11
167
11
      if (const auto *C = dyn_cast<MemberExpr>(E)) {
168
1
        if (C->getSourceRange() == SR)
169
1
          return true;
170
10
      }
171
10
      return false;
172
10
    };
173
24
174
62
    while (ShouldSkip(E, Child)) {
175
52
      auto It = PointerParents.find(E);
176
52
      if (It == PointerParents.end())
177
0
        break;
178
52
      const auto *S = It->second.dyn_cast<const Stmt *>();
179
52
      if (!S) {
180
5
        if (auto *Vec = It->second.dyn_cast<ParentVector *>())
181
1
          return llvm::makeArrayRef(*Vec);
182
4
        return getSingleDynTypedNodeFromParentMap(It->second);
183
4
      }
184
47
      const auto *P = dyn_cast<Expr>(S);
185
47
      if (!P)
186
9
        return DynTypedNode::create(*S);
187
38
      Child = E;
188
38
      E = P;
189
38
    }
190
24
    
return DynTypedNode::create(*E)10
;
191
24
  }
192
};
193
194
/// Template specializations to abstract away from pointers and TypeLocs.
195
/// @{
196
27.6k
template <typename T> static DynTypedNode createDynTypedNode(const T &Node) {
197
27.6k
  return DynTypedNode::create(*Node);
198
27.6k
}
ParentMapContext.cpp:clang::DynTypedNode createDynTypedNode<clang::Decl*>(clang::Decl* const&)
Line
Count
Source
196
19.2k
template <typename T> static DynTypedNode createDynTypedNode(const T &Node) {
197
19.2k
  return DynTypedNode::create(*Node);
198
19.2k
}
ParentMapContext.cpp:clang::DynTypedNode createDynTypedNode<clang::Stmt*>(clang::Stmt* const&)
Line
Count
Source
196
8.36k
template <typename T> static DynTypedNode createDynTypedNode(const T &Node) {
197
8.36k
  return DynTypedNode::create(*Node);
198
8.36k
}
199
16.2k
template <> DynTypedNode createDynTypedNode(const TypeLoc &Node) {
200
16.2k
  return DynTypedNode::create(Node);
201
16.2k
}
202
template <>
203
770
DynTypedNode createDynTypedNode(const NestedNameSpecifierLoc &Node) {
204
770
  return DynTypedNode::create(Node);
205
770
}
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
685
  ASTVisitor(ParentMap &Map) : Map(Map) {}
220
221
private:
222
  friend class RecursiveASTVisitor<ASTVisitor>;
223
224
  using VisitorBase = RecursiveASTVisitor<ASTVisitor>;
225
226
877
  bool shouldVisitTemplateInstantiations() const { return true; }
227
228
22.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
60.1k
                    MapTy *Parents) {
234
60.1k
    if (!Node)
235
15.5k
      return true;
236
44.6k
    if (ParentStack.size() > 0) {
237
43.9k
      // FIXME: Currently we add the same parent multiple times, but only
238
43.9k
      // when no memoization data is available for the type.
239
43.9k
      // For example when we visit all subexpressions of template
240
43.9k
      // instantiations; this is suboptimal, but benign: the only way to
241
43.9k
      // visit those is with hasAncestor / hasParent, and those do not create
242
43.9k
      // new matches.
243
43.9k
      // The plan is to enable DynTypedNode to be storable in a map or hash
244
43.9k
      // map. The main problem there is to implement hash functions /
245
43.9k
      // comparison operators for all types that DynTypedNode supports that
246
43.9k
      // do not have pointer identity.
247
43.9k
      auto &NodeOrVector = (*Parents)[MapNode];
248
43.9k
      if (NodeOrVector.isNull()) {
249
43.3k
        if (const auto *D = ParentStack.back().get<Decl>())
250
28.5k
          NodeOrVector = D;
251
14.7k
        else if (const auto *S = ParentStack.back().get<Stmt>())
252
7.10k
          NodeOrVector = S;
253
7.66k
        else
254
7.66k
          NodeOrVector = new DynTypedNode(ParentStack.back());
255
43.3k
      } else {
256
617
        if (!NodeOrVector.template is<ParentVector *>()) {
257
414
          auto *Vector = new ParentVector(
258
414
              1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
259
414
          delete NodeOrVector.template dyn_cast<DynTypedNode *>();
260
414
          NodeOrVector = Vector;
261
414
        }
262
617
263
617
        auto *Vector = NodeOrVector.template get<ParentVector *>();
264
617
        // Skip duplicates for types that have memoization data.
265
617
        // We must check that the type has memoization data before calling
266
617
        // std::find() because DynTypedNode::operator== can't compare all
267
617
        // types.
268
617
        bool Found = ParentStack.back().getMemoizationData() &&
269
617
                     std::find(Vector->begin(), Vector->end(),
270
406
                               ParentStack.back()) != Vector->end();
271
617
        if (!Found)
272
461
          Vector->push_back(ParentStack.back());
273
617
      }
274
43.9k
    }
275
44.6k
    ParentStack.push_back(createDynTypedNode(Node));
276
44.6k
    bool Result = BaseTraverse();
277
44.6k
    ParentStack.pop_back();
278
44.6k
    return Result;
279
44.6k
  }
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
19.2k
                    MapTy *Parents) {
234
19.2k
    if (!Node)
235
0
      return true;
236
19.2k
    if (ParentStack.size() > 0) {
237
18.5k
      // FIXME: Currently we add the same parent multiple times, but only
238
18.5k
      // when no memoization data is available for the type.
239
18.5k
      // For example when we visit all subexpressions of template
240
18.5k
      // instantiations; this is suboptimal, but benign: the only way to
241
18.5k
      // visit those is with hasAncestor / hasParent, and those do not create
242
18.5k
      // new matches.
243
18.5k
      // The plan is to enable DynTypedNode to be storable in a map or hash
244
18.5k
      // map. The main problem there is to implement hash functions /
245
18.5k
      // comparison operators for all types that DynTypedNode supports that
246
18.5k
      // do not have pointer identity.
247
18.5k
      auto &NodeOrVector = (*Parents)[MapNode];
248
18.5k
      if (NodeOrVector.isNull()) {
249
18.3k
        if (const auto *D = ParentStack.back().get<Decl>())
250
16.8k
          NodeOrVector = D;
251
1.53k
        else if (const auto *S = ParentStack.back().get<Stmt>())
252
821
          NodeOrVector = S;
253
710
        else
254
710
          NodeOrVector = new DynTypedNode(ParentStack.back());
255
18.3k
      } 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
186
263
186
        auto *Vector = NodeOrVector.template get<ParentVector *>();
264
186
        // Skip duplicates for types that have memoization data.
265
186
        // We must check that the type has memoization data before calling
266
186
        // std::find() because DynTypedNode::operator== can't compare all
267
186
        // types.
268
186
        bool Found = ParentStack.back().getMemoizationData() &&
269
186
                     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
18.5k
    }
275
19.2k
    ParentStack.push_back(createDynTypedNode(Node));
276
19.2k
    bool Result = BaseTraverse();
277
19.2k
    ParentStack.pop_back();
278
19.2k
    return Result;
279
19.2k
  }
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.1k
                    MapTy *Parents) {
234
11.1k
    if (!Node)
235
2.75k
      return true;
236
8.36k
    if (ParentStack.size() > 0) {
237
8.36k
      // FIXME: Currently we add the same parent multiple times, but only
238
8.36k
      // when no memoization data is available for the type.
239
8.36k
      // For example when we visit all subexpressions of template
240
8.36k
      // instantiations; this is suboptimal, but benign: the only way to
241
8.36k
      // visit those is with hasAncestor / hasParent, and those do not create
242
8.36k
      // new matches.
243
8.36k
      // The plan is to enable DynTypedNode to be storable in a map or hash
244
8.36k
      // map. The main problem there is to implement hash functions /
245
8.36k
      // comparison operators for all types that DynTypedNode supports that
246
8.36k
      // do not have pointer identity.
247
8.36k
      auto &NodeOrVector = (*Parents)[MapNode];
248
8.36k
      if (NodeOrVector.isNull()) {
249
8.28k
        if (const auto *D = ParentStack.back().get<Decl>())
250
2.48k
          NodeOrVector = D;
251
5.79k
        else if (const auto *S = ParentStack.back().get<Stmt>())
252
5.74k
          NodeOrVector = S;
253
53
        else
254
53
          NodeOrVector = new DynTypedNode(ParentStack.back());
255
8.28k
      } else {
256
81
        if (!NodeOrVector.template is<ParentVector *>()) {
257
78
          auto *Vector = new ParentVector(
258
78
              1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
259
78
          delete NodeOrVector.template dyn_cast<DynTypedNode *>();
260
78
          NodeOrVector = Vector;
261
78
        }
262
81
263
81
        auto *Vector = NodeOrVector.template get<ParentVector *>();
264
81
        // Skip duplicates for types that have memoization data.
265
81
        // We must check that the type has memoization data before calling
266
81
        // std::find() because DynTypedNode::operator== can't compare all
267
81
        // types.
268
81
        bool Found = ParentStack.back().getMemoizationData() &&
269
81
                     std::find(Vector->begin(), Vector->end(),
270
81
                               ParentStack.back()) != Vector->end();
271
81
        if (!Found)
272
59
          Vector->push_back(ParentStack.back());
273
81
      }
274
8.36k
    }
275
8.36k
    ParentStack.push_back(createDynTypedNode(Node));
276
8.36k
    bool Result = BaseTraverse();
277
8.36k
    ParentStack.pop_back();
278
8.36k
    return Result;
279
8.36k
  }
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
13.5k
                    MapTy *Parents) {
234
13.5k
    if (!Node)
235
12.7k
      return true;
236
770
    if (ParentStack.size() > 0) {
237
770
      // FIXME: Currently we add the same parent multiple times, but only
238
770
      // when no memoization data is available for the type.
239
770
      // For example when we visit all subexpressions of template
240
770
      // instantiations; this is suboptimal, but benign: the only way to
241
770
      // visit those is with hasAncestor / hasParent, and those do not create
242
770
      // new matches.
243
770
      // The plan is to enable DynTypedNode to be storable in a map or hash
244
770
      // map. The main problem there is to implement hash functions /
245
770
      // comparison operators for all types that DynTypedNode supports that
246
770
      // do not have pointer identity.
247
770
      auto &NodeOrVector = (*Parents)[MapNode];
248
770
      if (NodeOrVector.isNull()) {
249
765
        if (const auto *D = ParentStack.back().get<Decl>())
250
109
          NodeOrVector = D;
251
656
        else if (const auto *S = ParentStack.back().get<Stmt>())
252
115
          NodeOrVector = S;
253
541
        else
254
541
          NodeOrVector = new DynTypedNode(ParentStack.back());
255
765
      } 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
5
263
5
        auto *Vector = NodeOrVector.template get<ParentVector *>();
264
5
        // Skip duplicates for types that have memoization data.
265
5
        // We must check that the type has memoization data before calling
266
5
        // std::find() because DynTypedNode::operator== can't compare all
267
5
        // types.
268
5
        bool Found = ParentStack.back().getMemoizationData() &&
269
5
                     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
770
    }
275
770
    ParentStack.push_back(createDynTypedNode(Node));
276
770
    bool Result = BaseTraverse();
277
770
    ParentStack.pop_back();
278
770
    return Result;
279
770
  }
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
16.2k
                    MapTy *Parents) {
234
16.2k
    if (!Node)
235
0
      return true;
236
16.2k
    if (ParentStack.size() > 0) {
237
16.2k
      // FIXME: Currently we add the same parent multiple times, but only
238
16.2k
      // when no memoization data is available for the type.
239
16.2k
      // For example when we visit all subexpressions of template
240
16.2k
      // instantiations; this is suboptimal, but benign: the only way to
241
16.2k
      // visit those is with hasAncestor / hasParent, and those do not create
242
16.2k
      // new matches.
243
16.2k
      // The plan is to enable DynTypedNode to be storable in a map or hash
244
16.2k
      // map. The main problem there is to implement hash functions /
245
16.2k
      // comparison operators for all types that DynTypedNode supports that
246
16.2k
      // do not have pointer identity.
247
16.2k
      auto &NodeOrVector = (*Parents)[MapNode];
248
16.2k
      if (NodeOrVector.isNull()) {
249
15.8k
        if (const auto *D = ParentStack.back().get<Decl>())
250
9.11k
          NodeOrVector = D;
251
6.77k
        else if (const auto *S = ParentStack.back().get<Stmt>())
252
420
          NodeOrVector = S;
253
6.35k
        else
254
6.35k
          NodeOrVector = new DynTypedNode(ParentStack.back());
255
15.8k
      } else {
256
345
        if (!NodeOrVector.template is<ParentVector *>()) {
257
255
          auto *Vector = new ParentVector(
258
255
              1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
259
255
          delete NodeOrVector.template dyn_cast<DynTypedNode *>();
260
255
          NodeOrVector = Vector;
261
255
        }
262
345
263
345
        auto *Vector = NodeOrVector.template get<ParentVector *>();
264
345
        // Skip duplicates for types that have memoization data.
265
345
        // We must check that the type has memoization data before calling
266
345
        // std::find() because DynTypedNode::operator== can't compare all
267
345
        // types.
268
345
        bool Found = ParentStack.back().getMemoizationData() &&
269
345
                     std::find(Vector->begin(), Vector->end(),
270
268
                               ParentStack.back()) != Vector->end();
271
345
        if (!Found)
272
211
          Vector->push_back(ParentStack.back());
273
345
      }
274
16.2k
    }
275
16.2k
    ParentStack.push_back(createDynTypedNode(Node));
276
16.2k
    bool Result = BaseTraverse();
277
16.2k
    ParentStack.pop_back();
278
16.2k
    return Result;
279
16.2k
  }
280
281
19.2k
  bool TraverseDecl(Decl *DeclNode) {
282
19.2k
    return TraverseNode(
283
19.2k
        DeclNode, DeclNode, [&] { return VisitorBase::TraverseDecl(DeclNode); },
284
19.2k
        &Map.PointerParents);
285
19.2k
  }
286
287
11.1k
  bool TraverseStmt(Stmt *StmtNode) {
288
11.1k
    return TraverseNode(StmtNode, StmtNode,
289
11.1k
                        [&] 
{ return VisitorBase::TraverseStmt(StmtNode); }8.36k
,
290
11.1k
                        &Map.PointerParents);
291
11.1k
  }
292
293
16.2k
  bool TraverseTypeLoc(TypeLoc TypeLocNode) {
294
16.2k
    return TraverseNode(
295
16.2k
        TypeLocNode, DynTypedNode::create(TypeLocNode),
296
16.2k
        [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); },
297
16.2k
        &Map.OtherParents);
298
16.2k
  }
299
300
13.5k
  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) {
301
13.5k
    return TraverseNode(
302
13.5k
        NNSLocNode, DynTypedNode::create(NNSLocNode),
303
13.5k
        [&] 
{ return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode); }770
,
304
13.5k
        &Map.OtherParents);
305
13.5k
  }
306
307
  ParentMap &Map;
308
  llvm::SmallVector<DynTypedNode, 16> ParentStack;
309
};
310
311
685
ParentMapContext::ParentMap::ParentMap(ASTContext &Ctx) {
312
685
  ASTVisitor(*this).TraverseAST(Ctx);
313
685
}
314
315
12.3k
DynTypedNodeList ParentMapContext::getParents(const DynTypedNode &Node) {
316
12.3k
  if (!Parents)
317
685
    // We build the parent map for the traversal scope (usually whole TU), as
318
685
    // hasAncestor can escape any subtree.
319
685
    Parents = std::make_unique<ParentMap>(ASTCtx);
320
12.3k
  return Parents->getParents(getTraversalKind(), Node);
321
12.3k
}