Coverage Report

Created: 2021-01-23 06:44

/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.8k
ParentMapContext::ParentMapContext(ASTContext &Ctx) : ASTCtx(Ctx) {}
23
24
19.8k
ParentMapContext::~ParentMapContext() = default;
25
26
70
void ParentMapContext::clear() { Parents.reset(); }
27
28
355k
const Expr *ParentMapContext::traverseIgnored(const Expr *E) const {
29
355k
  return traverseIgnored(const_cast<Expr *>(E));
30
355k
}
31
32
395k
Expr *ParentMapContext::traverseIgnored(Expr *E) const {
33
395k
  if (!E)
34
0
    return nullptr;
35
36
395k
  switch (Traversal) {
37
360k
  case TK_AsIs:
38
360k
    return E;
39
34.4k
  case TK_IgnoreUnlessSpelledInSource:
40
34.4k
    return E->IgnoreUnlessSpelledInSource();
41
0
  }
42
0
  llvm_unreachable("Invalid Traversal type!");
43
0
}
44
45
759k
DynTypedNode ParentMapContext::traverseIgnored(const DynTypedNode &N) const {
46
759k
  if (const auto *E = N.get<Expr>()) {
47
355k
    return DynTypedNode::create(*traverseIgnored(E));
48
355k
  }
49
403k
  return N;
50
403k
}
51
52
class ParentMapContext::ParentMap {
53
  /// Contains parents of a node.
54
  using ParentVector = llvm::SmallVector<DynTypedNode, 2>;
55
56
  /// Maps from a node to its parents. This is used for nodes that have
57
  /// pointer identity only, which are more common and we can save space by
58
  /// only storing a unique pointer to them.
59
  using ParentMapPointers =
60
      llvm::DenseMap<const void *,
61
                     llvm::PointerUnion<const Decl *, const Stmt *,
62
                                        DynTypedNode *, ParentVector *>>;
63
64
  /// Parent map for nodes without pointer identity. We store a full
65
  /// DynTypedNode for all keys.
66
  using ParentMapOtherNodes =
67
      llvm::DenseMap<DynTypedNode,
68
                     llvm::PointerUnion<const Decl *, const Stmt *,
69
                                        DynTypedNode *, ParentVector *>>;
70
71
  ParentMapPointers PointerParents;
72
  ParentMapOtherNodes OtherParents;
73
  class ASTVisitor;
74
75
  static DynTypedNode
76
17.2k
  getSingleDynTypedNodeFromParentMap(ParentMapPointers::mapped_type U) {
77
17.2k
    if (const auto *D = U.dyn_cast<const Decl *>())
78
7.64k
      return DynTypedNode::create(*D);
79
9.56k
    if (const auto *S = U.dyn_cast<const Stmt *>())
80
6.87k
      return DynTypedNode::create(*S);
81
2.68k
    return *U.get<DynTypedNode *>();
82
2.68k
  }
83
84
  template <typename NodeTy, typename MapTy>
85
  static DynTypedNodeList getDynNodeFromMap(const NodeTy &Node,
86
17.6k
                                                        const MapTy &Map) {
87
17.6k
    auto I = Map.find(Node);
88
17.6k
    if (I == Map.end()) {
89
938
      return llvm::ArrayRef<DynTypedNode>();
90
938
    }
91
16.7k
    if (const auto *V = I->second.template dyn_cast<ParentVector *>()) {
92
100
      return llvm::makeArrayRef(*V);
93
100
    }
94
16.6k
    return getSingleDynTypedNodeFromParentMap(I->second);
95
16.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
86
12.0k
                                                        const MapTy &Map) {
87
12.0k
    auto I = Map.find(Node);
88
12.0k
    if (I == Map.end()) {
89
887
      return llvm::ArrayRef<DynTypedNode>();
90
887
    }
91
11.1k
    if (const auto *V = I->second.template dyn_cast<ParentVector *>()) {
92
89
      return llvm::makeArrayRef(*V);
93
89
    }
94
11.0k
    return getSingleDynTypedNodeFromParentMap(I->second);
95
11.0k
  }
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
86
5.62k
                                                        const MapTy &Map) {
87
5.62k
    auto I = Map.find(Node);
88
5.62k
    if (I == Map.end()) {
89
51
      return llvm::ArrayRef<DynTypedNode>();
90
51
    }
91
5.57k
    if (const auto *V = I->second.template dyn_cast<ParentVector *>()) {
92
11
      return llvm::makeArrayRef(*V);
93
11
    }
94
5.56k
    return getSingleDynTypedNodeFromParentMap(I->second);
95
5.56k
  }
96
97
public:
98
  ParentMap(ASTContext &Ctx);
99
1.15k
  ~ParentMap() {
100
42.7k
    for (const auto &Entry : PointerParents) {
101
42.7k
      if (Entry.second.is<DynTypedNode *>()) {
102
1.22k
        delete Entry.second.get<DynTypedNode *>();
103
41.5k
      } else if (Entry.second.is<ParentVector *>()) {
104
256
        delete Entry.second.get<ParentVector *>();
105
256
      }
106
42.7k
    }
107
23.6k
    for (const auto &Entry : OtherParents) {
108
23.6k
      if (Entry.second.is<DynTypedNode *>()) {
109
9.19k
        delete Entry.second.get<DynTypedNode *>();
110
14.4k
      } else if (Entry.second.is<ParentVector *>()) {
111
310
        delete Entry.second.get<ParentVector *>();
112
310
      }
113
23.6k
    }
114
1.15k
  }
115
116
17.6k
  DynTypedNodeList getParents(TraversalKind TK, const DynTypedNode &Node) {
117
17.6k
    if (Node.getNodeKind().hasPointerIdentity()) {
118
12.0k
      auto ParentList =
119
12.0k
          getDynNodeFromMap(Node.getMemoizationData(), PointerParents);
120
12.0k
      if (ParentList.size() == 1 && 
TK == TK_IgnoreUnlessSpelledInSource11.1k
) {
121
3.41k
        const auto *E = ParentList[0].get<Expr>();
122
3.41k
        const auto *Child = Node.get<Expr>();
123
3.41k
        if (E && 
Child55
)
124
53
          return AscendIgnoreUnlessSpelledInSource(E, Child);
125
11.9k
      }
126
11.9k
      return ParentList;
127
11.9k
    }
128
5.62k
    return getDynNodeFromMap(Node, OtherParents);
129
5.62k
  }
130
131
  DynTypedNodeList AscendIgnoreUnlessSpelledInSource(const Expr *E,
132
53
                                                     const Expr *Child) {
133
134
86
    auto ShouldSkip = [](const Expr *E, const Expr *Child) {
135
86
      if (isa<ImplicitCastExpr>(E))
136
39
        return true;
137
138
47
      if (isa<FullExpr>(E))
139
1
        return true;
140
141
46
      if (isa<MaterializeTemporaryExpr>(E))
142
1
        return true;
143
144
45
      if (isa<CXXBindTemporaryExpr>(E))
145
0
        return true;
146
147
45
      if (isa<ParenExpr>(E))
148
2
        return true;
149
150
43
      if (isa<ExprWithCleanups>(E))
151
0
        return true;
152
153
43
      auto SR = Child->getSourceRange();
154
155
43
      if (const auto *C = dyn_cast<CXXFunctionalCastExpr>(E)) {
156
2
        if (C->getSourceRange() == SR)
157
2
          return true;
158
41
      }
159
160
41
      if (const auto *C = dyn_cast<CXXConstructExpr>(E)) {
161
25
        if (C->getSourceRange() == SR || 
C->isElidable()12
)
162
13
          return true;
163
28
      }
164
165
28
      if (const auto *C = dyn_cast<CXXMemberCallExpr>(E)) {
166
2
        if (C->getSourceRange() == SR)
167
2
          return true;
168
26
      }
169
170
26
      if (const auto *C = dyn_cast<MemberExpr>(E)) {
171
2
        if (C->getSourceRange() == SR)
172
2
          return true;
173
24
      }
174
24
      return false;
175
24
    };
176
177
86
    while (ShouldSkip(E, Child)) {
178
62
      auto It = PointerParents.find(E);
179
62
      if (It == PointerParents.end())
180
0
        break;
181
62
      const auto *S = It->second.dyn_cast<const Stmt *>();
182
62
      if (!S) {
183
13
        if (auto *Vec = It->second.dyn_cast<ParentVector *>())
184
4
          return llvm::makeArrayRef(*Vec);
185
9
        return getSingleDynTypedNodeFromParentMap(It->second);
186
9
      }
187
49
      const auto *P = dyn_cast<Expr>(S);
188
49
      if (!P)
189
16
        return DynTypedNode::create(*S);
190
33
      Child = E;
191
33
      E = P;
192
33
    }
193
24
    return DynTypedNode::create(*E);
194
53
  }
195
};
196
197
/// Template specializations to abstract away from pointers and TypeLocs.
198
/// @{
199
27.3k
template <typename T> static DynTypedNode createDynTypedNode(const T &Node) {
200
27.3k
  return DynTypedNode::create(*Node);
201
27.3k
}
202
23.2k
template <> DynTypedNode createDynTypedNode(const TypeLoc &Node) {
203
23.2k
  return DynTypedNode::create(Node);
204
23.2k
}
205
template <>
206
798
DynTypedNode createDynTypedNode(const NestedNameSpecifierLoc &Node) {
207
798
  return DynTypedNode::create(Node);
208
798
}
209
/// @}
210
211
/// A \c RecursiveASTVisitor that builds a map from nodes to their
212
/// parents as defined by the \c RecursiveASTVisitor.
213
///
214
/// Note that the relationship described here is purely in terms of AST
215
/// traversal - there are other relationships (for example declaration context)
216
/// in the AST that are better modeled by special matchers.
217
class ParentMapContext::ParentMap::ASTVisitor
218
    : public RecursiveASTVisitor<ASTVisitor> {
219
public:
220
1.15k
  ASTVisitor(ParentMap &Map) : Map(Map) {}
221
222
private:
223
  friend class RecursiveASTVisitor<ASTVisitor>;
224
225
  using VisitorBase = RecursiveASTVisitor<ASTVisitor>;
226
227
1.09k
  bool shouldVisitTemplateInstantiations() const { return true; }
228
229
32.3k
  bool shouldVisitImplicitCode() const { return true; }
230
231
  /// Record the parent of the node we're visiting.
232
  /// MapNode is the child, the parent is on top of ParentStack.
233
  /// Parents is the parent storage (either PointerParents or OtherParents).
234
  template <typename MapNodeTy, typename MapTy>
235
68.3k
  void addParent(MapNodeTy MapNode, MapTy *Parents) {
236
68.3k
    if (ParentStack.empty())
237
1.15k
      return;
238
239
    // FIXME: Currently we add the same parent multiple times, but only
240
    // when no memoization data is available for the type.
241
    // For example when we visit all subexpressions of template
242
    // instantiations; this is suboptimal, but benign: the only way to
243
    // visit those is with hasAncestor / hasParent, and those do not create
244
    // new matches.
245
    // The plan is to enable DynTypedNode to be storable in a map or hash
246
    // map. The main problem there is to implement hash functions /
247
    // comparison operators for all types that DynTypedNode supports that
248
    // do not have pointer identity.
249
67.2k
    auto &NodeOrVector = (*Parents)[MapNode];
250
67.2k
    if (NodeOrVector.isNull()) {
251
66.4k
      if (const auto *D = ParentStack.back().get<Decl>())
252
41.2k
        NodeOrVector = D;
253
25.1k
      else if (const auto *S = ParentStack.back().get<Stmt>())
254
14.5k
        NodeOrVector = S;
255
10.5k
      else
256
10.5k
        NodeOrVector = new DynTypedNode(ParentStack.back());
257
793
    } else {
258
793
      if (!NodeOrVector.template is<ParentVector *>()) {
259
566
        auto *Vector = new ParentVector(
260
566
            1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
261
566
        delete NodeOrVector.template dyn_cast<DynTypedNode *>();
262
566
        NodeOrVector = Vector;
263
566
      }
264
265
793
      auto *Vector = NodeOrVector.template get<ParentVector *>();
266
      // Skip duplicates for types that have memoization data.
267
      // We must check that the type has memoization data before calling
268
      // std::find() because DynTypedNode::operator== can't compare all
269
      // types.
270
793
      bool Found = ParentStack.back().getMemoizationData() &&
271
546
                   std::find(Vector->begin(), Vector->end(),
272
546
                             ParentStack.back()) != Vector->end();
273
793
      if (!Found)
274
567
        Vector->push_back(ParentStack.back());
275
793
    }
276
67.2k
  }
void clang::ParentMapContext::ParentMap::ASTVisitor::addParent<clang::Decl*, 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*, 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
235
27.3k
  void addParent(MapNodeTy MapNode, MapTy *Parents) {
236
27.3k
    if (ParentStack.empty())
237
1.15k
      return;
238
239
    // FIXME: Currently we add the same parent multiple times, but only
240
    // when no memoization data is available for the type.
241
    // For example when we visit all subexpressions of template
242
    // instantiations; this is suboptimal, but benign: the only way to
243
    // visit those is with hasAncestor / hasParent, and those do not create
244
    // new matches.
245
    // The plan is to enable DynTypedNode to be storable in a map or hash
246
    // map. The main problem there is to implement hash functions /
247
    // comparison operators for all types that DynTypedNode supports that
248
    // do not have pointer identity.
249
26.2k
    auto &NodeOrVector = (*Parents)[MapNode];
250
26.2k
    if (NodeOrVector.isNull()) {
251
26.0k
      if (const auto *D = ParentStack.back().get<Decl>())
252
22.9k
        NodeOrVector = D;
253
3.11k
      else if (const auto *S = ParentStack.back().get<Stmt>())
254
1.89k
        NodeOrVector = S;
255
1.21k
      else
256
1.21k
        NodeOrVector = new DynTypedNode(ParentStack.back());
257
189
    } else {
258
189
      if (!NodeOrVector.template is<ParentVector *>()) {
259
77
        auto *Vector = new ParentVector(
260
77
            1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
261
77
        delete NodeOrVector.template dyn_cast<DynTypedNode *>();
262
77
        NodeOrVector = Vector;
263
77
      }
264
265
189
      auto *Vector = NodeOrVector.template get<ParentVector *>();
266
      // Skip duplicates for types that have memoization data.
267
      // We must check that the type has memoization data before calling
268
      // std::find() because DynTypedNode::operator== can't compare all
269
      // types.
270
189
      bool Found = ParentStack.back().getMemoizationData() &&
271
53
                   std::find(Vector->begin(), Vector->end(),
272
53
                             ParentStack.back()) != Vector->end();
273
189
      if (!Found)
274
189
        Vector->push_back(ParentStack.back());
275
189
    }
276
26.2k
  }
void clang::ParentMapContext::ParentMap::ASTVisitor::addParent<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, 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
235
24.0k
  void addParent(MapNodeTy MapNode, MapTy *Parents) {
236
24.0k
    if (ParentStack.empty())
237
0
      return;
238
239
    // FIXME: Currently we add the same parent multiple times, but only
240
    // when no memoization data is available for the type.
241
    // For example when we visit all subexpressions of template
242
    // instantiations; this is suboptimal, but benign: the only way to
243
    // visit those is with hasAncestor / hasParent, and those do not create
244
    // new matches.
245
    // The plan is to enable DynTypedNode to be storable in a map or hash
246
    // map. The main problem there is to implement hash functions /
247
    // comparison operators for all types that DynTypedNode supports that
248
    // do not have pointer identity.
249
24.0k
    auto &NodeOrVector = (*Parents)[MapNode];
250
24.0k
    if (NodeOrVector.isNull()) {
251
23.6k
      if (const auto *D = ParentStack.back().get<Decl>())
252
13.8k
        NodeOrVector = D;
253
9.85k
      else if (const auto *S = ParentStack.back().get<Stmt>())
254
555
        NodeOrVector = S;
255
9.29k
      else
256
9.29k
        NodeOrVector = new DynTypedNode(ParentStack.back());
257
416
    } else {
258
416
      if (!NodeOrVector.template is<ParentVector *>()) {
259
310
        auto *Vector = new ParentVector(
260
310
            1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
261
310
        delete NodeOrVector.template dyn_cast<DynTypedNode *>();
262
310
        NodeOrVector = Vector;
263
310
      }
264
265
416
      auto *Vector = NodeOrVector.template get<ParentVector *>();
266
      // Skip duplicates for types that have memoization data.
267
      // We must check that the type has memoization data before calling
268
      // std::find() because DynTypedNode::operator== can't compare all
269
      // types.
270
416
      bool Found = ParentStack.back().getMemoizationData() &&
271
305
                   std::find(Vector->begin(), Vector->end(),
272
305
                             ParentStack.back()) != Vector->end();
273
416
      if (!Found)
274
279
        Vector->push_back(ParentStack.back());
275
416
    }
276
24.0k
  }
void clang::ParentMapContext::ParentMap::ASTVisitor::addParent<clang::Stmt*, 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*, 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
235
16.8k
  void addParent(MapNodeTy MapNode, MapTy *Parents) {
236
16.8k
    if (ParentStack.empty())
237
0
      return;
238
239
    // FIXME: Currently we add the same parent multiple times, but only
240
    // when no memoization data is available for the type.
241
    // For example when we visit all subexpressions of template
242
    // instantiations; this is suboptimal, but benign: the only way to
243
    // visit those is with hasAncestor / hasParent, and those do not create
244
    // new matches.
245
    // The plan is to enable DynTypedNode to be storable in a map or hash
246
    // map. The main problem there is to implement hash functions /
247
    // comparison operators for all types that DynTypedNode supports that
248
    // do not have pointer identity.
249
16.8k
    auto &NodeOrVector = (*Parents)[MapNode];
250
16.8k
    if (NodeOrVector.isNull()) {
251
16.6k
      if (const auto *D = ParentStack.back().get<Decl>())
252
4.51k
        NodeOrVector = D;
253
12.1k
      else if (const auto *S = ParentStack.back().get<Stmt>())
254
12.1k
        NodeOrVector = S;
255
54
      else
256
54
        NodeOrVector = new DynTypedNode(ParentStack.back());
257
188
    } else {
258
188
      if (!NodeOrVector.template is<ParentVector *>()) {
259
179
        auto *Vector = new ParentVector(
260
179
            1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
261
179
        delete NodeOrVector.template dyn_cast<DynTypedNode *>();
262
179
        NodeOrVector = Vector;
263
179
      }
264
265
188
      auto *Vector = NodeOrVector.template get<ParentVector *>();
266
      // Skip duplicates for types that have memoization data.
267
      // We must check that the type has memoization data before calling
268
      // std::find() because DynTypedNode::operator== can't compare all
269
      // types.
270
188
      bool Found = ParentStack.back().getMemoizationData() &&
271
188
                   std::find(Vector->begin(), Vector->end(),
272
188
                             ParentStack.back()) != Vector->end();
273
188
      if (!Found)
274
99
        Vector->push_back(ParentStack.back());
275
188
    }
276
16.8k
  }
277
278
  template <typename T, typename MapNodeTy, typename BaseTraverseFn,
279
            typename MapTy>
280
  bool TraverseNode(T Node, MapNodeTy MapNode, BaseTraverseFn BaseTraverse,
281
71.7k
                    MapTy *Parents) {
282
71.7k
    if (!Node)
283
20.2k
      return true;
284
51.4k
    addParent(MapNode, Parents);
285
51.4k
    ParentStack.push_back(createDynTypedNode(Node));
286
51.4k
    bool Result = BaseTraverse();
287
51.4k
    ParentStack.pop_back();
288
51.4k
    return Result;
289
51.4k
  }
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
281
27.3k
                    MapTy *Parents) {
282
27.3k
    if (!Node)
283
0
      return true;
284
27.3k
    addParent(MapNode, Parents);
285
27.3k
    ParentStack.push_back(createDynTypedNode(Node));
286
27.3k
    bool Result = BaseTraverse();
287
27.3k
    ParentStack.pop_back();
288
27.3k
    return Result;
289
27.3k
  }
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
281
21.0k
                    MapTy *Parents) {
282
21.0k
    if (!Node)
283
20.2k
      return true;
284
798
    addParent(MapNode, Parents);
285
798
    ParentStack.push_back(createDynTypedNode(Node));
286
798
    bool Result = BaseTraverse();
287
798
    ParentStack.pop_back();
288
798
    return Result;
289
798
  }
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
281
23.2k
                    MapTy *Parents) {
282
23.2k
    if (!Node)
283
0
      return true;
284
23.2k
    addParent(MapNode, Parents);
285
23.2k
    ParentStack.push_back(createDynTypedNode(Node));
286
23.2k
    bool Result = BaseTraverse();
287
23.2k
    ParentStack.pop_back();
288
23.2k
    return Result;
289
23.2k
  }
290
291
27.3k
  bool TraverseDecl(Decl *DeclNode) {
292
27.3k
    return TraverseNode(
293
27.3k
        DeclNode, DeclNode, [&] { return VisitorBase::TraverseDecl(DeclNode); },
294
27.3k
        &Map.PointerParents);
295
27.3k
  }
296
23.2k
  bool TraverseTypeLoc(TypeLoc TypeLocNode) {
297
23.2k
    return TraverseNode(
298
23.2k
        TypeLocNode, DynTypedNode::create(TypeLocNode),
299
23.2k
        [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); },
300
23.2k
        &Map.OtherParents);
301
23.2k
  }
302
21.0k
  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) {
303
21.0k
    return TraverseNode(
304
21.0k
        NNSLocNode, DynTypedNode::create(NNSLocNode),
305
798
        [&] { return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode); },
306
21.0k
        &Map.OtherParents);
307
21.0k
  }
308
309
  // Using generic TraverseNode for Stmt would prevent data-recursion.
310
16.8k
  bool dataTraverseStmtPre(Stmt *StmtNode) {
311
16.8k
    addParent(StmtNode, &Map.PointerParents);
312
16.8k
    ParentStack.push_back(DynTypedNode::create(*StmtNode));
313
16.8k
    return true;
314
16.8k
  }
315
16.8k
  bool dataTraverseStmtPost(Stmt *StmtNode) {
316
16.8k
    ParentStack.pop_back();
317
16.8k
    return true;
318
16.8k
  }
319
320
  ParentMap &Map;
321
  llvm::SmallVector<DynTypedNode, 16> ParentStack;
322
};
323
324
1.15k
ParentMapContext::ParentMap::ParentMap(ASTContext &Ctx) {
325
1.15k
  ASTVisitor(*this).TraverseAST(Ctx);
326
1.15k
}
327
328
17.6k
DynTypedNodeList ParentMapContext::getParents(const DynTypedNode &Node) {
329
17.6k
  if (!Parents)
330
    // We build the parent map for the traversal scope (usually whole TU), as
331
    // hasAncestor can escape any subtree.
332
1.15k
    Parents = std::make_unique<ParentMap>(ASTCtx);
333
17.6k
  return Parents->getParents(getTraversalKind(), Node);
334
17.6k
}