Coverage Report

Created: 2020-02-25 14:32

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/ASTMatchers/ASTMatchFinder.cpp
Line
Count
Source (jump to first uncovered line)
1
//===--- ASTMatchFinder.cpp - Structural query framework ------------------===//
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
//  Implements an algorithm to efficiently search for matches on AST nodes.
10
//  Uses memoization to support recursive matches like HasDescendant.
11
//
12
//  The general idea is to visit all AST nodes with a RecursiveASTVisitor,
13
//  calling the Matches(...) method of each matcher we are running on each
14
//  AST node. The matcher can recurse via the ASTMatchFinder interface.
15
//
16
//===----------------------------------------------------------------------===//
17
18
#include "clang/ASTMatchers/ASTMatchFinder.h"
19
#include "clang/AST/ASTConsumer.h"
20
#include "clang/AST/ASTContext.h"
21
#include "clang/AST/RecursiveASTVisitor.h"
22
#include "llvm/ADT/DenseMap.h"
23
#include "llvm/ADT/StringMap.h"
24
#include "llvm/Support/Timer.h"
25
#include <deque>
26
#include <memory>
27
#include <set>
28
29
namespace clang {
30
namespace ast_matchers {
31
namespace internal {
32
namespace {
33
34
typedef MatchFinder::MatchCallback MatchCallback;
35
36
// The maximum number of memoization entries to store.
37
// 10k has been experimentally found to give a good trade-off
38
// of performance vs. memory consumption by running matcher
39
// that match on every statement over a very large codebase.
40
//
41
// FIXME: Do some performance optimization in general and
42
// revisit this number; also, put up micro-benchmarks that we can
43
// optimize this on.
44
static const unsigned MaxMemoizationEntries = 10000;
45
46
// We use memoization to avoid running the same matcher on the same
47
// AST node twice.  This struct is the key for looking up match
48
// result.  It consists of an ID of the MatcherInterface (for
49
// identifying the matcher), a pointer to the AST node and the
50
// bound nodes before the matcher was executed.
51
//
52
// We currently only memoize on nodes whose pointers identify the
53
// nodes (\c Stmt and \c Decl, but not \c QualType or \c TypeLoc).
54
// For \c QualType and \c TypeLoc it is possible to implement
55
// generation of keys for each type.
56
// FIXME: Benchmark whether memoization of non-pointer typed nodes
57
// provides enough benefit for the additional amount of code.
58
struct MatchKey {
59
  DynTypedMatcher::MatcherIDType MatcherID;
60
  DynTypedNode Node;
61
  BoundNodesTreeBuilder BoundNodes;
62
  TraversalKind Traversal = TK_AsIs;
63
64
62.8k
  bool operator<(const MatchKey &Other) const {
65
62.8k
    return std::tie(Traversal, MatcherID, Node, BoundNodes) <
66
62.8k
           std::tie(Other.Traversal, Other.MatcherID, Other.Node,
67
62.8k
                    Other.BoundNodes);
68
62.8k
  }
69
};
70
71
// Used to store the result of a match and possibly bound nodes.
72
struct MemoizedMatchResult {
73
  bool ResultOfMatch;
74
  BoundNodesTreeBuilder Nodes;
75
};
76
77
// A RecursiveASTVisitor that traverses all children or all descendants of
78
// a node.
79
class MatchChildASTVisitor
80
    : public RecursiveASTVisitor<MatchChildASTVisitor> {
81
public:
82
  typedef RecursiveASTVisitor<MatchChildASTVisitor> VisitorBase;
83
84
  // Creates an AST visitor that matches 'matcher' on all children or
85
  // descendants of a traversed node. max_depth is the maximum depth
86
  // to traverse: use 1 for matching the children and INT_MAX for
87
  // matching the descendants.
88
  MatchChildASTVisitor(const DynTypedMatcher *Matcher, ASTMatchFinder *Finder,
89
                       BoundNodesTreeBuilder *Builder, int MaxDepth,
90
                       TraversalKind Traversal, ASTMatchFinder::BindKind Bind)
91
      : Matcher(Matcher), Finder(Finder), Builder(Builder), CurrentDepth(0),
92
7.99k
        MaxDepth(MaxDepth), Traversal(Traversal), Bind(Bind), Matches(false) {}
93
94
  // Returns true if a match is found in the subtree rooted at the
95
  // given AST node. This is done via a set of mutually recursive
96
  // functions. Here's how the recursion is done (the  *wildcard can
97
  // actually be Decl, Stmt, or Type):
98
  //
99
  //   - Traverse(node) calls BaseTraverse(node) when it needs
100
  //     to visit the descendants of node.
101
  //   - BaseTraverse(node) then calls (via VisitorBase::Traverse*(node))
102
  //     Traverse*(c) for each child c of 'node'.
103
  //   - Traverse*(c) in turn calls Traverse(c), completing the
104
  //     recursion.
105
7.99k
  bool findMatch(const DynTypedNode &DynNode) {
106
7.99k
    reset();
107
7.99k
    if (const Decl *D = DynNode.get<Decl>())
108
2.90k
      traverse(*D);
109
5.08k
    else if (const Stmt *S = DynNode.get<Stmt>())
110
5.00k
      traverse(*S);
111
75
    else if (const NestedNameSpecifier *NNS =
112
5
             DynNode.get<NestedNameSpecifier>())
113
5
      traverse(*NNS);
114
70
    else if (const NestedNameSpecifierLoc *NNSLoc =
115
8
             DynNode.get<NestedNameSpecifierLoc>())
116
8
      traverse(*NNSLoc);
117
62
    else if (const QualType *Q = DynNode.get<QualType>())
118
44
      traverse(*Q);
119
18
    else if (const TypeLoc *T = DynNode.get<TypeLoc>())
120
18
      traverse(*T);
121
0
    else if (const auto *C = DynNode.get<CXXCtorInitializer>())
122
0
      traverse(*C);
123
7.99k
    // FIXME: Add other base types after adding tests.
124
7.99k
125
7.99k
    // It's OK to always overwrite the bound nodes, as if there was
126
7.99k
    // no match in this recursive branch, the result set is empty
127
7.99k
    // anyway.
128
7.99k
    *Builder = ResultBindings;
129
7.99k
130
7.99k
    return Matches;
131
7.99k
  }
132
133
  // The following are overriding methods from the base visitor class.
134
  // They are public only to allow CRTP to work. They are *not *part
135
  // of the public API of this class.
136
13.9k
  bool TraverseDecl(Decl *DeclNode) {
137
13.9k
    ScopedIncrement ScopedDepth(&CurrentDepth);
138
13.9k
    return (DeclNode == nullptr) || 
traverse(*DeclNode)13.9k
;
139
13.9k
  }
140
141
43.9k
  Stmt *getStmtToTraverse(Stmt *StmtNode) {
142
43.9k
    Stmt *StmtToTraverse = StmtNode;
143
43.9k
    if (auto *ExprNode = dyn_cast_or_null<Expr>(StmtNode)) {
144
32.5k
      auto *LambdaNode = dyn_cast_or_null<LambdaExpr>(StmtNode);
145
32.5k
      if (LambdaNode &&
146
32.5k
          Finder->getASTContext().getParentMapContext().getTraversalKind() ==
147
110
              TK_IgnoreUnlessSpelledInSource)
148
1
        StmtToTraverse = LambdaNode;
149
32.5k
      else
150
32.5k
        StmtToTraverse =
151
32.5k
            Finder->getASTContext().getParentMapContext().traverseIgnored(
152
32.5k
                ExprNode);
153
32.5k
    }
154
43.9k
    if (Traversal == TraversalKind::TK_IgnoreImplicitCastsAndParentheses) {
155
1
      if (Expr *ExprNode = dyn_cast_or_null<Expr>(StmtNode))
156
0
        StmtToTraverse = ExprNode->IgnoreParenImpCasts();
157
1
    }
158
43.9k
    return StmtToTraverse;
159
43.9k
  }
160
161
43.9k
  bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue = nullptr) {
162
43.9k
    // If we need to keep track of the depth, we can't perform data recursion.
163
43.9k
    if (CurrentDepth == 0 || 
(33.8k
CurrentDepth <= MaxDepth33.8k
&&
MaxDepth < INT_MAX32.9k
))
164
10.4k
      Queue = nullptr;
165
43.9k
166
43.9k
    ScopedIncrement ScopedDepth(&CurrentDepth);
167
43.9k
    Stmt *StmtToTraverse = getStmtToTraverse(StmtNode);
168
43.9k
    if (!StmtToTraverse)
169
3.43k
      return true;
170
40.5k
    if (!match(*StmtToTraverse))
171
1.08k
      return false;
172
39.4k
    return VisitorBase::TraverseStmt(StmtToTraverse, Queue);
173
39.4k
  }
174
  // We assume that the QualType and the contained type are on the same
175
  // hierarchy level. Thus, we try to match either of them.
176
3.01k
  bool TraverseType(QualType TypeNode) {
177
3.01k
    if (TypeNode.isNull())
178
634
      return true;
179
2.38k
    ScopedIncrement ScopedDepth(&CurrentDepth);
180
2.38k
    // Match the Type.
181
2.38k
    if (!match(*TypeNode))
182
16
      return false;
183
2.36k
    // The QualType is matched inside traverse.
184
2.36k
    return traverse(TypeNode);
185
2.36k
  }
186
  // We assume that the TypeLoc, contained QualType and contained Type all are
187
  // on the same hierarchy level. Thus, we try to match all of them.
188
14.7k
  bool TraverseTypeLoc(TypeLoc TypeLocNode) {
189
14.7k
    if (TypeLocNode.isNull())
190
0
      return true;
191
14.7k
    ScopedIncrement ScopedDepth(&CurrentDepth);
192
14.7k
    // Match the Type.
193
14.7k
    if (!match(*TypeLocNode.getType()))
194
18
      return false;
195
14.7k
    // Match the QualType.
196
14.7k
    if (!match(TypeLocNode.getType()))
197
9
      return false;
198
14.7k
    // The TypeLoc is matched inside traverse.
199
14.7k
    return traverse(TypeLocNode);
200
14.7k
  }
201
9
  bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
202
9
    ScopedIncrement ScopedDepth(&CurrentDepth);
203
9
    return (NNS == nullptr) || traverse(*NNS);
204
9
  }
205
23.7k
  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS) {
206
23.7k
    if (!NNS)
207
23.2k
      return true;
208
497
    ScopedIncrement ScopedDepth(&CurrentDepth);
209
497
    if (!match(*NNS.getNestedNameSpecifier()))
210
3
      return false;
211
494
    return traverse(NNS);
212
494
  }
213
113
  bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit) {
214
113
    if (!CtorInit)
215
0
      return true;
216
113
    ScopedIncrement ScopedDepth(&CurrentDepth);
217
113
    return traverse(*CtorInit);
218
113
  }
219
115
  bool TraverseLambdaExpr(LambdaExpr *Node) {
220
115
    if (Finder->getASTContext().getParentMapContext().getTraversalKind() !=
221
115
        TK_IgnoreUnlessSpelledInSource)
222
109
      return VisitorBase::TraverseLambdaExpr(Node);
223
6
    if (!Node)
224
0
      return true;
225
6
    ScopedIncrement ScopedDepth(&CurrentDepth);
226
6
227
11
    for (unsigned I = 0, N = Node->capture_size(); I != N; 
++I5
) {
228
7
      const auto *C = Node->capture_begin() + I;
229
7
      if (!C->isExplicit())
230
0
        continue;
231
7
      if (Node->isInitCapture(C) && 
!match(*C->getCapturedVar())3
)
232
1
        return false;
233
6
      if (!match(*Node->capture_init_begin()[I]))
234
1
        return false;
235
6
    }
236
6
237
6
    
if (const auto *4
TPL4
= Node->getTemplateParameterList()) {
238
2
      for (const auto *TP : *TPL) {
239
2
        if (!match(*TP))
240
1
          return false;
241
2
      }
242
2
    }
243
4
244
4
    
for (const auto *P : Node->getCallOperator()->parameters())3
{
245
4
      if (!match(*P))
246
1
        return false;
247
4
    }
248
3
249
3
    
if (2
!match(*Node->getBody())2
)
250
1
      return false;
251
1
252
1
    return true;
253
1
  }
254
255
334
  bool shouldVisitTemplateInstantiations() const { return true; }
256
19.0k
  bool shouldVisitImplicitCode() const { return true; }
257
258
private:
259
  // Used for updating the depth during traversal.
260
  struct ScopedIncrement {
261
75.7k
    explicit ScopedIncrement(int *Depth) : Depth(Depth) { ++(*Depth); }
262
75.7k
    ~ScopedIncrement() { --(*Depth); }
263
264
   private:
265
    int *Depth;
266
  };
267
268
  // Resets the state of this object.
269
7.99k
  void reset() {
270
7.99k
    Matches = false;
271
7.99k
    CurrentDepth = 0;
272
7.99k
  }
273
274
  // Forwards the call to the corresponding Traverse*() method in the
275
  // base visitor class.
276
15.8k
  bool baseTraverse(const Decl &DeclNode) {
277
15.8k
    return VisitorBase::TraverseDecl(const_cast<Decl*>(&DeclNode));
278
15.8k
  }
279
5.00k
  bool baseTraverse(const Stmt &StmtNode) {
280
5.00k
    return VisitorBase::TraverseStmt(const_cast<Stmt*>(&StmtNode));
281
5.00k
  }
282
2.41k
  bool baseTraverse(QualType TypeNode) {
283
2.41k
    return VisitorBase::TraverseType(TypeNode);
284
2.41k
  }
285
14.7k
  bool baseTraverse(TypeLoc TypeLocNode) {
286
14.7k
    return VisitorBase::TraverseTypeLoc(TypeLocNode);
287
14.7k
  }
288
12
  bool baseTraverse(const NestedNameSpecifier &NNS) {
289
12
    return VisitorBase::TraverseNestedNameSpecifier(
290
12
        const_cast<NestedNameSpecifier*>(&NNS));
291
12
  }
292
495
  bool baseTraverse(NestedNameSpecifierLoc NNS) {
293
495
    return VisitorBase::TraverseNestedNameSpecifierLoc(NNS);
294
495
  }
295
109
  bool baseTraverse(const CXXCtorInitializer &CtorInit) {
296
109
    return VisitorBase::TraverseConstructorInitializer(
297
109
        const_cast<CXXCtorInitializer *>(&CtorInit));
298
109
  }
299
300
  // Sets 'Matched' to true if 'Matcher' matches 'Node' and:
301
  //   0 < CurrentDepth <= MaxDepth.
302
  //
303
  // Returns 'true' if traversal should continue after this function
304
  // returns, i.e. if no match is found or 'Bind' is 'BK_All'.
305
  template <typename T>
306
112k
  bool match(const T &Node) {
307
112k
    if (CurrentDepth == 0 || 
CurrentDepth > MaxDepth104k
) {
308
21.3k
      return true;
309
21.3k
    }
310
91.4k
    if (Bind != ASTMatchFinder::BK_All) {
311
29.6k
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
312
29.6k
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
313
29.6k
                           &RecursiveBuilder)) {
314
2.22k
        Matches = true;
315
2.22k
        ResultBindings.addMatch(RecursiveBuilder);
316
2.22k
        return false; // Abort as soon as a match is found.
317
2.22k
      }
318
61.7k
    } else {
319
61.7k
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
320
61.7k
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
321
61.7k
                           &RecursiveBuilder)) {
322
666
        // After the first match the matcher succeeds.
323
666
        Matches = true;
324
666
        ResultBindings.addMatch(RecursiveBuilder);
325
666
      }
326
61.7k
    }
327
91.4k
    
return true89.1k
;
328
91.4k
  }
ASTMatchFinder.cpp:bool clang::ast_matchers::internal::(anonymous namespace)::MatchChildASTVisitor::match<clang::Decl>(clang::Decl const&)
Line
Count
Source
306
16.8k
  bool match(const T &Node) {
307
16.8k
    if (CurrentDepth == 0 || 
CurrentDepth > MaxDepth13.9k
) {
308
4.18k
      return true;
309
4.18k
    }
310
12.7k
    if (Bind != ASTMatchFinder::BK_All) {
311
5.26k
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
312
5.26k
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
313
5.26k
                           &RecursiveBuilder)) {
314
1.04k
        Matches = true;
315
1.04k
        ResultBindings.addMatch(RecursiveBuilder);
316
1.04k
        return false; // Abort as soon as a match is found.
317
1.04k
      }
318
7.44k
    } else {
319
7.44k
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
320
7.44k
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
321
7.44k
                           &RecursiveBuilder)) {
322
146
        // After the first match the matcher succeeds.
323
146
        Matches = true;
324
146
        ResultBindings.addMatch(RecursiveBuilder);
325
146
      }
326
7.44k
    }
327
12.7k
    
return true11.6k
;
328
12.7k
  }
ASTMatchFinder.cpp:bool clang::ast_matchers::internal::(anonymous namespace)::MatchChildASTVisitor::match<clang::Stmt>(clang::Stmt const&)
Line
Count
Source
306
45.5k
  bool match(const T &Node) {
307
45.5k
    if (CurrentDepth == 0 || 
CurrentDepth > MaxDepth40.5k
) {
308
5.97k
      return true;
309
5.97k
    }
310
39.5k
    if (Bind != ASTMatchFinder::BK_All) {
311
12.6k
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
312
12.6k
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
313
12.6k
                           &RecursiveBuilder)) {
314
1.08k
        Matches = true;
315
1.08k
        ResultBindings.addMatch(RecursiveBuilder);
316
1.08k
        return false; // Abort as soon as a match is found.
317
1.08k
      }
318
26.9k
    } else {
319
26.9k
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
320
26.9k
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
321
26.9k
                           &RecursiveBuilder)) {
322
496
        // After the first match the matcher succeeds.
323
496
        Matches = true;
324
496
        ResultBindings.addMatch(RecursiveBuilder);
325
496
      }
326
26.9k
    }
327
39.5k
    
return true38.4k
;
328
39.5k
  }
ASTMatchFinder.cpp:bool clang::ast_matchers::internal::(anonymous namespace)::MatchChildASTVisitor::match<clang::NestedNameSpecifier>(clang::NestedNameSpecifier const&)
Line
Count
Source
306
511
  bool match(const T &Node) {
307
511
    if (CurrentDepth == 0 || 
CurrentDepth > MaxDepth506
) {
308
34
      return true;
309
34
    }
310
477
    if (Bind != ASTMatchFinder::BK_All) {
311
94
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
312
94
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
313
94
                           &RecursiveBuilder)) {
314
5
        Matches = true;
315
5
        ResultBindings.addMatch(RecursiveBuilder);
316
5
        return false; // Abort as soon as a match is found.
317
5
      }
318
383
    } else {
319
383
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
320
383
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
321
383
                           &RecursiveBuilder)) {
322
8
        // After the first match the matcher succeeds.
323
8
        Matches = true;
324
8
        ResultBindings.addMatch(RecursiveBuilder);
325
8
      }
326
383
    }
327
477
    
return true472
;
328
477
  }
ASTMatchFinder.cpp:bool clang::ast_matchers::internal::(anonymous namespace)::MatchChildASTVisitor::match<clang::Type>(clang::Type const&)
Line
Count
Source
306
17.1k
  bool match(const T &Node) {
307
17.1k
    if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
308
3.86k
      return true;
309
3.86k
    }
310
13.3k
    if (Bind != ASTMatchFinder::BK_All) {
311
3.94k
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
312
3.94k
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
313
3.94k
                           &RecursiveBuilder)) {
314
34
        Matches = true;
315
34
        ResultBindings.addMatch(RecursiveBuilder);
316
34
        return false; // Abort as soon as a match is found.
317
34
      }
318
9.35k
    } else {
319
9.35k
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
320
9.35k
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
321
9.35k
                           &RecursiveBuilder)) {
322
4
        // After the first match the matcher succeeds.
323
4
        Matches = true;
324
4
        ResultBindings.addMatch(RecursiveBuilder);
325
4
      }
326
9.35k
    }
327
13.3k
    
return true13.2k
;
328
13.3k
  }
ASTMatchFinder.cpp:bool clang::ast_matchers::internal::(anonymous namespace)::MatchChildASTVisitor::match<clang::QualType>(clang::QualType const&)
Line
Count
Source
306
17.1k
  bool match(const T &Node) {
307
17.1k
    if (CurrentDepth == 0 || 
CurrentDepth > MaxDepth17.1k
) {
308
3.91k
      return true;
309
3.91k
    }
310
13.2k
    if (Bind != ASTMatchFinder::BK_All) {
311
3.91k
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
312
3.91k
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
313
3.91k
                           &RecursiveBuilder)) {
314
9
        Matches = true;
315
9
        ResultBindings.addMatch(RecursiveBuilder);
316
9
        return false; // Abort as soon as a match is found.
317
9
      }
318
9.35k
    } else {
319
9.35k
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
320
9.35k
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
321
9.35k
                           &RecursiveBuilder)) {
322
4
        // After the first match the matcher succeeds.
323
4
        Matches = true;
324
4
        ResultBindings.addMatch(RecursiveBuilder);
325
4
      }
326
9.35k
    }
327
13.2k
    
return true13.2k
;
328
13.2k
  }
ASTMatchFinder.cpp:bool clang::ast_matchers::internal::(anonymous namespace)::MatchChildASTVisitor::match<clang::VarDecl>(clang::VarDecl const&)
Line
Count
Source
306
3
  bool match(const T &Node) {
307
3
    if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
308
0
      return true;
309
0
    }
310
3
    if (Bind != ASTMatchFinder::BK_All) {
311
3
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
312
3
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
313
3
                           &RecursiveBuilder)) {
314
1
        Matches = true;
315
1
        ResultBindings.addMatch(RecursiveBuilder);
316
1
        return false; // Abort as soon as a match is found.
317
1
      }
318
0
    } else {
319
0
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
320
0
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
321
0
                           &RecursiveBuilder)) {
322
0
        // After the first match the matcher succeeds.
323
0
        Matches = true;
324
0
        ResultBindings.addMatch(RecursiveBuilder);
325
0
      }
326
0
    }
327
3
    
return true2
;
328
3
  }
ASTMatchFinder.cpp:bool clang::ast_matchers::internal::(anonymous namespace)::MatchChildASTVisitor::match<clang::Expr>(clang::Expr const&)
Line
Count
Source
306
6
  bool match(const T &Node) {
307
6
    if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
308
0
      return true;
309
0
    }
310
6
    if (Bind != ASTMatchFinder::BK_All) {
311
6
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
312
6
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
313
6
                           &RecursiveBuilder)) {
314
1
        Matches = true;
315
1
        ResultBindings.addMatch(RecursiveBuilder);
316
1
        return false; // Abort as soon as a match is found.
317
1
      }
318
0
    } else {
319
0
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
320
0
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
321
0
                           &RecursiveBuilder)) {
322
0
        // After the first match the matcher succeeds.
323
0
        Matches = true;
324
0
        ResultBindings.addMatch(RecursiveBuilder);
325
0
      }
326
0
    }
327
6
    
return true5
;
328
6
  }
ASTMatchFinder.cpp:bool clang::ast_matchers::internal::(anonymous namespace)::MatchChildASTVisitor::match<clang::NamedDecl>(clang::NamedDecl const&)
Line
Count
Source
306
2
  bool match(const T &Node) {
307
2
    if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
308
0
      return true;
309
0
    }
310
2
    if (Bind != ASTMatchFinder::BK_All) {
311
2
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
312
2
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
313
2
                           &RecursiveBuilder)) {
314
1
        Matches = true;
315
1
        ResultBindings.addMatch(RecursiveBuilder);
316
1
        return false; // Abort as soon as a match is found.
317
1
      }
318
0
    } else {
319
0
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
320
0
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
321
0
                           &RecursiveBuilder)) {
322
0
        // After the first match the matcher succeeds.
323
0
        Matches = true;
324
0
        ResultBindings.addMatch(RecursiveBuilder);
325
0
      }
326
0
    }
327
2
    
return true1
;
328
2
  }
ASTMatchFinder.cpp:bool clang::ast_matchers::internal::(anonymous namespace)::MatchChildASTVisitor::match<clang::ParmVarDecl>(clang::ParmVarDecl const&)
Line
Count
Source
306
4
  bool match(const T &Node) {
307
4
    if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
308
0
      return true;
309
0
    }
310
4
    if (Bind != ASTMatchFinder::BK_All) {
311
4
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
312
4
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
313
4
                           &RecursiveBuilder)) {
314
1
        Matches = true;
315
1
        ResultBindings.addMatch(RecursiveBuilder);
316
1
        return false; // Abort as soon as a match is found.
317
1
      }
318
0
    } else {
319
0
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
320
0
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
321
0
                           &RecursiveBuilder)) {
322
0
        // After the first match the matcher succeeds.
323
0
        Matches = true;
324
0
        ResultBindings.addMatch(RecursiveBuilder);
325
0
      }
326
0
    }
327
4
    
return true3
;
328
4
  }
ASTMatchFinder.cpp:bool clang::ast_matchers::internal::(anonymous namespace)::MatchChildASTVisitor::match<clang::CompoundStmt>(clang::CompoundStmt const&)
Line
Count
Source
306
2
  bool match(const T &Node) {
307
2
    if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
308
0
      return true;
309
0
    }
310
2
    if (Bind != ASTMatchFinder::BK_All) {
311
2
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
312
2
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
313
2
                           &RecursiveBuilder)) {
314
1
        Matches = true;
315
1
        ResultBindings.addMatch(RecursiveBuilder);
316
1
        return false; // Abort as soon as a match is found.
317
1
      }
318
0
    } else {
319
0
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
320
0
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
321
0
                           &RecursiveBuilder)) {
322
0
        // After the first match the matcher succeeds.
323
0
        Matches = true;
324
0
        ResultBindings.addMatch(RecursiveBuilder);
325
0
      }
326
0
    }
327
2
    
return true1
;
328
2
  }
ASTMatchFinder.cpp:bool clang::ast_matchers::internal::(anonymous namespace)::MatchChildASTVisitor::match<clang::NestedNameSpecifierLoc>(clang::NestedNameSpecifierLoc const&)
Line
Count
Source
306
502
  bool match(const T &Node) {
307
502
    if (CurrentDepth == 0 || 
CurrentDepth > MaxDepth494
) {
308
34
      return true;
309
34
    }
310
468
    if (Bind != ASTMatchFinder::BK_All) {
311
87
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
312
87
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
313
87
                           &RecursiveBuilder)) {
314
7
        Matches = true;
315
7
        ResultBindings.addMatch(RecursiveBuilder);
316
7
        return false; // Abort as soon as a match is found.
317
7
      }
318
381
    } else {
319
381
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
320
381
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
321
381
                           &RecursiveBuilder)) {
322
8
        // After the first match the matcher succeeds.
323
8
        Matches = true;
324
8
        ResultBindings.addMatch(RecursiveBuilder);
325
8
      }
326
381
    }
327
468
    
return true461
;
328
468
  }
ASTMatchFinder.cpp:bool clang::ast_matchers::internal::(anonymous namespace)::MatchChildASTVisitor::match<clang::TypeLoc>(clang::TypeLoc const&)
Line
Count
Source
306
14.7k
  bool match(const T &Node) {
307
14.7k
    if (CurrentDepth == 0 || 
CurrentDepth > MaxDepth14.7k
) {
308
3.30k
      return true;
309
3.30k
    }
310
11.4k
    if (Bind != ASTMatchFinder::BK_All) {
311
3.69k
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
312
3.69k
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
313
3.69k
                           &RecursiveBuilder)) {
314
21
        Matches = true;
315
21
        ResultBindings.addMatch(RecursiveBuilder);
316
21
        return false; // Abort as soon as a match is found.
317
21
      }
318
7.78k
    } else {
319
7.78k
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
320
7.78k
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
321
7.78k
                           &RecursiveBuilder)) {
322
0
        // After the first match the matcher succeeds.
323
0
        Matches = true;
324
0
        ResultBindings.addMatch(RecursiveBuilder);
325
0
      }
326
7.78k
    }
327
11.4k
    
return true11.4k
;
328
11.4k
  }
ASTMatchFinder.cpp:bool clang::ast_matchers::internal::(anonymous namespace)::MatchChildASTVisitor::match<clang::CXXCtorInitializer>(clang::CXXCtorInitializer const&)
Line
Count
Source
306
113
  bool match(const T &Node) {
307
113
    if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
308
4
      return true;
309
4
    }
310
109
    if (Bind != ASTMatchFinder::BK_All) {
311
7
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
312
7
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
313
7
                           &RecursiveBuilder)) {
314
4
        Matches = true;
315
4
        ResultBindings.addMatch(RecursiveBuilder);
316
4
        return false; // Abort as soon as a match is found.
317
4
      }
318
102
    } else {
319
102
      BoundNodesTreeBuilder RecursiveBuilder(*Builder);
320
102
      if (Matcher->matches(DynTypedNode::create(Node), Finder,
321
102
                           &RecursiveBuilder)) {
322
0
        // After the first match the matcher succeeds.
323
0
        Matches = true;
324
0
        ResultBindings.addMatch(RecursiveBuilder);
325
0
      }
326
102
    }
327
109
    
return true105
;
328
109
  }
329
330
  // Traverses the subtree rooted at 'Node'; returns true if the
331
  // traversal should continue after this function returns.
332
  template <typename T>
333
39.7k
  bool traverse(const T &Node) {
334
39.7k
    static_assert(IsBaseType<T>::value,
335
39.7k
                  "traverse can only be instantiated with base type");
336
39.7k
    if (!match(Node))
337
1.08k
      return false;
338
38.6k
    return baseTraverse(Node);
339
38.6k
  }
ASTMatchFinder.cpp:bool clang::ast_matchers::internal::(anonymous namespace)::MatchChildASTVisitor::traverse<clang::Decl>(clang::Decl const&)
Line
Count
Source
333
16.8k
  bool traverse(const T &Node) {
334
16.8k
    static_assert(IsBaseType<T>::value,
335
16.8k
                  "traverse can only be instantiated with base type");
336
16.8k
    if (!match(Node))
337
1.04k
      return false;
338
15.8k
    return baseTraverse(Node);
339
15.8k
  }
ASTMatchFinder.cpp:bool clang::ast_matchers::internal::(anonymous namespace)::MatchChildASTVisitor::traverse<clang::Stmt>(clang::Stmt const&)
Line
Count
Source
333
5.00k
  bool traverse(const T &Node) {
334
5.00k
    static_assert(IsBaseType<T>::value,
335
5.00k
                  "traverse can only be instantiated with base type");
336
5.00k
    if (!match(Node))
337
0
      return false;
338
5.00k
    return baseTraverse(Node);
339
5.00k
  }
ASTMatchFinder.cpp:bool clang::ast_matchers::internal::(anonymous namespace)::MatchChildASTVisitor::traverse<clang::NestedNameSpecifier>(clang::NestedNameSpecifier const&)
Line
Count
Source
333
14
  bool traverse(const T &Node) {
334
14
    static_assert(IsBaseType<T>::value,
335
14
                  "traverse can only be instantiated with base type");
336
14
    if (!match(Node))
337
2
      return false;
338
12
    return baseTraverse(Node);
339
12
  }
ASTMatchFinder.cpp:bool clang::ast_matchers::internal::(anonymous namespace)::MatchChildASTVisitor::traverse<clang::NestedNameSpecifierLoc>(clang::NestedNameSpecifierLoc const&)
Line
Count
Source
333
502
  bool traverse(const T &Node) {
334
502
    static_assert(IsBaseType<T>::value,
335
502
                  "traverse can only be instantiated with base type");
336
502
    if (!match(Node))
337
7
      return false;
338
495
    return baseTraverse(Node);
339
495
  }
ASTMatchFinder.cpp:bool clang::ast_matchers::internal::(anonymous namespace)::MatchChildASTVisitor::traverse<clang::QualType>(clang::QualType const&)
Line
Count
Source
333
2.41k
  bool traverse(const T &Node) {
334
2.41k
    static_assert(IsBaseType<T>::value,
335
2.41k
                  "traverse can only be instantiated with base type");
336
2.41k
    if (!match(Node))
337
0
      return false;
338
2.41k
    return baseTraverse(Node);
339
2.41k
  }
ASTMatchFinder.cpp:bool clang::ast_matchers::internal::(anonymous namespace)::MatchChildASTVisitor::traverse<clang::TypeLoc>(clang::TypeLoc const&)
Line
Count
Source
333
14.7k
  bool traverse(const T &Node) {
334
14.7k
    static_assert(IsBaseType<T>::value,
335
14.7k
                  "traverse can only be instantiated with base type");
336
14.7k
    if (!match(Node))
337
21
      return false;
338
14.7k
    return baseTraverse(Node);
339
14.7k
  }
ASTMatchFinder.cpp:bool clang::ast_matchers::internal::(anonymous namespace)::MatchChildASTVisitor::traverse<clang::CXXCtorInitializer>(clang::CXXCtorInitializer const&)
Line
Count
Source
333
113
  bool traverse(const T &Node) {
334
113
    static_assert(IsBaseType<T>::value,
335
113
                  "traverse can only be instantiated with base type");
336
113
    if (!match(Node))
337
4
      return false;
338
109
    return baseTraverse(Node);
339
109
  }
340
341
  const DynTypedMatcher *const Matcher;
342
  ASTMatchFinder *const Finder;
343
  BoundNodesTreeBuilder *const Builder;
344
  BoundNodesTreeBuilder ResultBindings;
345
  int CurrentDepth;
346
  const int MaxDepth;
347
  const TraversalKind Traversal;
348
  const ASTMatchFinder::BindKind Bind;
349
  bool Matches;
350
};
351
352
// Controls the outermost traversal of the AST and allows to match multiple
353
// matchers.
354
class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>,
355
                        public ASTMatchFinder {
356
public:
357
  MatchASTVisitor(const MatchFinder::MatchersByType *Matchers,
358
                  const MatchFinder::MatchFinderOptions &Options)
359
28.9k
      : Matchers(Matchers), Options(Options), ActiveASTContext(nullptr) {}
360
361
28.9k
  ~MatchASTVisitor() override {
362
28.9k
    if (Options.CheckProfiling) {
363
1
      Options.CheckProfiling->Records = std::move(TimeByBucket);
364
1
    }
365
28.9k
  }
366
367
8.46k
  void onStartOfTranslationUnit() {
368
8.46k
    const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
369
8.46k
    TimeBucketRegion Timer;
370
10.3k
    for (MatchCallback *MC : Matchers->AllCallbacks) {
371
10.3k
      if (EnableCheckProfiling)
372
1
        Timer.setBucket(&TimeByBucket[MC->getID()]);
373
10.3k
      MC->onStartOfTranslationUnit();
374
10.3k
    }
375
8.46k
  }
376
377
8.46k
  void onEndOfTranslationUnit() {
378
8.46k
    const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
379
8.46k
    TimeBucketRegion Timer;
380
10.3k
    for (MatchCallback *MC : Matchers->AllCallbacks) {
381
10.3k
      if (EnableCheckProfiling)
382
1
        Timer.setBucket(&TimeByBucket[MC->getID()]);
383
10.3k
      MC->onEndOfTranslationUnit();
384
10.3k
    }
385
8.46k
  }
386
387
28.9k
  void set_active_ast_context(ASTContext *NewActiveASTContext) {
388
28.9k
    ActiveASTContext = NewActiveASTContext;
389
28.9k
  }
390
391
  // The following Visit*() and Traverse*() functions "override"
392
  // methods in RecursiveASTVisitor.
393
394
39.9k
  bool VisitTypedefNameDecl(TypedefNameDecl *DeclNode) {
395
39.9k
    // When we see 'typedef A B', we add name 'B' to the set of names
396
39.9k
    // A's canonical type maps to.  This is necessary for implementing
397
39.9k
    // isDerivedFrom(x) properly, where x can be the name of the base
398
39.9k
    // class or any of its aliases.
399
39.9k
    //
400
39.9k
    // In general, the is-alias-of (as defined by typedefs) relation
401
39.9k
    // is tree-shaped, as you can typedef a type more than once.  For
402
39.9k
    // example,
403
39.9k
    //
404
39.9k
    //   typedef A B;
405
39.9k
    //   typedef A C;
406
39.9k
    //   typedef C D;
407
39.9k
    //   typedef C E;
408
39.9k
    //
409
39.9k
    // gives you
410
39.9k
    //
411
39.9k
    //   A
412
39.9k
    //   |- B
413
39.9k
    //   `- C
414
39.9k
    //      |- D
415
39.9k
    //      `- E
416
39.9k
    //
417
39.9k
    // It is wrong to assume that the relation is a chain.  A correct
418
39.9k
    // implementation of isDerivedFrom() needs to recognize that B and
419
39.9k
    // E are aliases, even though neither is a typedef of the other.
420
39.9k
    // Therefore, we cannot simply walk through one typedef chain to
421
39.9k
    // find out whether the type name matches.
422
39.9k
    const Type *TypeNode = DeclNode->getUnderlyingType().getTypePtr();
423
39.9k
    const Type *CanonicalType =  // root of the typedef tree
424
39.9k
        ActiveASTContext->getCanonicalType(TypeNode);
425
39.9k
    TypeAliases[CanonicalType].insert(DeclNode);
426
39.9k
    return true;
427
39.9k
  }
428
429
16
  bool VisitObjCCompatibleAliasDecl(ObjCCompatibleAliasDecl *CAD) {
430
16
    const ObjCInterfaceDecl *InterfaceDecl = CAD->getClassInterface();
431
16
    CompatibleAliases[InterfaceDecl].insert(CAD);
432
16
    return true;
433
16
  }
434
435
  bool TraverseDecl(Decl *DeclNode);
436
  bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue = nullptr);
437
  bool TraverseType(QualType TypeNode);
438
  bool TraverseTypeLoc(TypeLoc TypeNode);
439
  bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS);
440
  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS);
441
  bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit);
442
443
  // Matches children or descendants of 'Node' with 'BaseMatcher'.
444
  bool memoizedMatchesRecursively(const DynTypedNode &Node, ASTContext &Ctx,
445
                                  const DynTypedMatcher &Matcher,
446
                                  BoundNodesTreeBuilder *Builder, int MaxDepth,
447
8.44k
                                  TraversalKind Traversal, BindKind Bind) {
448
8.44k
    // For AST-nodes that don't have an identity, we can't memoize.
449
8.44k
    if (!Node.getMemoizationData() || 
!Builder->isComparable()8.37k
)
450
194
      return matchesRecursively(Node, Matcher, Builder, MaxDepth, Traversal,
451
194
                                Bind);
452
8.24k
453
8.24k
    MatchKey Key;
454
8.24k
    Key.MatcherID = Matcher.getID();
455
8.24k
    Key.Node = Node;
456
8.24k
    // Note that we key on the bindings *before* the match.
457
8.24k
    Key.BoundNodes = *Builder;
458
8.24k
    Key.Traversal = Ctx.getParentMapContext().getTraversalKind();
459
8.24k
460
8.24k
    MemoizationMap::iterator I = ResultCache.find(Key);
461
8.24k
    if (I != ResultCache.end()) {
462
448
      *Builder = I->second.Nodes;
463
448
      return I->second.ResultOfMatch;
464
448
    }
465
7.79k
466
7.79k
    MemoizedMatchResult Result;
467
7.79k
    Result.Nodes = *Builder;
468
7.79k
    Result.ResultOfMatch = matchesRecursively(Node, Matcher, &Result.Nodes,
469
7.79k
                                              MaxDepth, Traversal, Bind);
470
7.79k
471
7.79k
    MemoizedMatchResult &CachedResult = ResultCache[Key];
472
7.79k
    CachedResult = std::move(Result);
473
7.79k
474
7.79k
    *Builder = CachedResult.Nodes;
475
7.79k
    return CachedResult.ResultOfMatch;
476
7.79k
  }
477
478
  // Matches children or descendants of 'Node' with 'BaseMatcher'.
479
  bool matchesRecursively(const DynTypedNode &Node,
480
                          const DynTypedMatcher &Matcher,
481
                          BoundNodesTreeBuilder *Builder, int MaxDepth,
482
7.99k
                          TraversalKind Traversal, BindKind Bind) {
483
7.99k
    MatchChildASTVisitor Visitor(
484
7.99k
      &Matcher, this, Builder, MaxDepth, Traversal, Bind);
485
7.99k
    return Visitor.findMatch(Node);
486
7.99k
  }
487
488
  bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
489
                          const Matcher<NamedDecl> &Base,
490
                          BoundNodesTreeBuilder *Builder,
491
                          bool Directly) override;
492
493
  bool objcClassIsDerivedFrom(const ObjCInterfaceDecl *Declaration,
494
                              const Matcher<NamedDecl> &Base,
495
                              BoundNodesTreeBuilder *Builder,
496
                              bool Directly) override;
497
498
  // Implements ASTMatchFinder::matchesChildOf.
499
  bool matchesChildOf(const DynTypedNode &Node, ASTContext &Ctx,
500
                      const DynTypedMatcher &Matcher,
501
                      BoundNodesTreeBuilder *Builder, TraversalKind Traversal,
502
2.65k
                      BindKind Bind) override {
503
2.65k
    if (ResultCache.size() > MaxMemoizationEntries)
504
0
      ResultCache.clear();
505
2.65k
    return memoizedMatchesRecursively(Node, Ctx, Matcher, Builder, 1, Traversal,
506
2.65k
                                      Bind);
507
2.65k
  }
508
  // Implements ASTMatchFinder::matchesDescendantOf.
509
  bool matchesDescendantOf(const DynTypedNode &Node, ASTContext &Ctx,
510
                           const DynTypedMatcher &Matcher,
511
                           BoundNodesTreeBuilder *Builder,
512
5.78k
                           BindKind Bind) override {
513
5.78k
    if (ResultCache.size() > MaxMemoizationEntries)
514
0
      ResultCache.clear();
515
5.78k
    return memoizedMatchesRecursively(Node, Ctx, Matcher, Builder, INT_MAX,
516
5.78k
                                      TraversalKind::TK_AsIs, Bind);
517
5.78k
  }
518
  // Implements ASTMatchFinder::matchesAncestorOf.
519
  bool matchesAncestorOf(const DynTypedNode &Node, ASTContext &Ctx,
520
                         const DynTypedMatcher &Matcher,
521
                         BoundNodesTreeBuilder *Builder,
522
1.59k
                         AncestorMatchMode MatchMode) override {
523
1.59k
    // Reset the cache outside of the recursive call to make sure we
524
1.59k
    // don't invalidate any iterators.
525
1.59k
    if (ResultCache.size() > MaxMemoizationEntries)
526
0
      ResultCache.clear();
527
1.59k
    return memoizedMatchesAncestorOfRecursively(Node, Ctx, Matcher, Builder,
528
1.59k
                                                MatchMode);
529
1.59k
  }
530
531
  // Matches all registered matchers on the given node and calls the
532
  // result callback for every node that matches.
533
20.4k
  void match(const DynTypedNode &Node) {
534
20.4k
    // FIXME: Improve this with a switch or a visitor pattern.
535
20.4k
    if (auto *N = Node.get<Decl>()) {
536
2.04k
      match(*N);
537
18.4k
    } else if (auto *N = Node.get<Stmt>()) {
538
18.4k
      match(*N);
539
18.4k
    } else 
if (auto *0
N0
= Node.get<Type>()) {
540
0
      match(*N);
541
0
    } else if (auto *N = Node.get<QualType>()) {
542
0
      match(*N);
543
0
    } else if (auto *N = Node.get<NestedNameSpecifier>()) {
544
0
      match(*N);
545
0
    } else if (auto *N = Node.get<NestedNameSpecifierLoc>()) {
546
0
      match(*N);
547
0
    } else if (auto *N = Node.get<TypeLoc>()) {
548
0
      match(*N);
549
0
    } else if (auto *N = Node.get<CXXCtorInitializer>()) {
550
0
      match(*N);
551
0
    }
552
20.4k
  }
553
554
355k
  template <typename T> void match(const T &Node) {
555
355k
    matchDispatch(&Node);
556
355k
  }
ASTMatchFinder.cpp:void clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::match<clang::Decl>(clang::Decl const&)
Line
Count
Source
554
102k
  template <typename T> void match(const T &Node) {
555
102k
    matchDispatch(&Node);
556
102k
  }
ASTMatchFinder.cpp:void clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::match<clang::Stmt>(clang::Stmt const&)
Line
Count
Source
554
54.7k
  template <typename T> void match(const T &Node) {
555
54.7k
    matchDispatch(&Node);
556
54.7k
  }
Unexecuted instantiation: ASTMatchFinder.cpp:void clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::match<clang::Type>(clang::Type const&)
ASTMatchFinder.cpp:void clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::match<clang::QualType>(clang::QualType const&)
Line
Count
Source
554
103k
  template <typename T> void match(const T &Node) {
555
103k
    matchDispatch(&Node);
556
103k
  }
ASTMatchFinder.cpp:void clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::match<clang::NestedNameSpecifier>(clang::NestedNameSpecifier const&)
Line
Count
Source
554
639
  template <typename T> void match(const T &Node) {
555
639
    matchDispatch(&Node);
556
639
  }
ASTMatchFinder.cpp:void clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::match<clang::NestedNameSpecifierLoc>(clang::NestedNameSpecifierLoc const&)
Line
Count
Source
554
637
  template <typename T> void match(const T &Node) {
555
637
    matchDispatch(&Node);
556
637
  }
ASTMatchFinder.cpp:void clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::match<clang::TypeLoc>(clang::TypeLoc const&)
Line
Count
Source
554
92.0k
  template <typename T> void match(const T &Node) {
555
92.0k
    matchDispatch(&Node);
556
92.0k
  }
ASTMatchFinder.cpp:void clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::match<clang::CXXCtorInitializer>(clang::CXXCtorInitializer const&)
Line
Count
Source
554
498
  template <typename T> void match(const T &Node) {
555
498
    matchDispatch(&Node);
556
498
  }
557
558
  // Implements ASTMatchFinder::getASTContext.
559
807k
  ASTContext &getASTContext() const override { return *ActiveASTContext; }
560
561
4.50k
  bool shouldVisitTemplateInstantiations() const { return true; }
562
112k
  bool shouldVisitImplicitCode() const { return true; }
563
564
private:
565
  class TimeBucketRegion {
566
  public:
567
261k
    TimeBucketRegion() : Bucket(nullptr) {}
568
261k
    ~TimeBucketRegion() { setBucket(nullptr); }
569
570
    /// Start timing for \p NewBucket.
571
    ///
572
    /// If there was a bucket already set, it will finish the timing for that
573
    /// other bucket.
574
    /// \p NewBucket will be timed until the next call to \c setBucket() or
575
    /// until the \c TimeBucketRegion is destroyed.
576
    /// If \p NewBucket is the same as the currently timed bucket, this call
577
    /// does nothing.
578
261k
    void setBucket(llvm::TimeRecord *NewBucket) {
579
261k
      if (Bucket != NewBucket) {
580
18
        auto Now = llvm::TimeRecord::getCurrentTime(true);
581
18
        if (Bucket)
582
9
          *Bucket += Now;
583
18
        if (NewBucket)
584
9
          *NewBucket -= Now;
585
18
        Bucket = NewBucket;
586
18
      }
587
261k
    }
588
589
  private:
590
    llvm::TimeRecord *Bucket;
591
  };
592
593
  /// Runs all the \p Matchers on \p Node.
594
  ///
595
  /// Used by \c matchDispatch() below.
596
  template <typename T, typename MC>
597
197k
  void matchWithoutFilter(const T &Node, const MC &Matchers) {
598
197k
    const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
599
197k
    TimeBucketRegion Timer;
600
197k
    for (const auto &MP : Matchers) {
601
1.91k
      if (EnableCheckProfiling)
602
0
        Timer.setBucket(&TimeByBucket[MP.second->getID()]);
603
1.91k
      BoundNodesTreeBuilder Builder;
604
1.91k
      if (MP.first.matches(Node, this, &Builder)) {
605
383
        MatchVisitor Visitor(ActiveASTContext, MP.second);
606
383
        Builder.visitMatches(&Visitor);
607
383
      }
608
1.91k
    }
609
197k
  }
ASTMatchFinder.cpp:void clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::matchWithoutFilter<clang::QualType, std::__1::vector<std::__1::pair<clang::ast_matchers::internal::Matcher<clang::QualType>, clang::ast_matchers::MatchFinder::MatchCallback*>, std::__1::allocator<std::__1::pair<clang::ast_matchers::internal::Matcher<clang::QualType>, clang::ast_matchers::MatchFinder::MatchCallback*> > > >(clang::QualType const&, std::__1::vector<std::__1::pair<clang::ast_matchers::internal::Matcher<clang::QualType>, clang::ast_matchers::MatchFinder::MatchCallback*>, std::__1::allocator<std::__1::pair<clang::ast_matchers::internal::Matcher<clang::QualType>, clang::ast_matchers::MatchFinder::MatchCallback*> > > const&)
Line
Count
Source
597
103k
  void matchWithoutFilter(const T &Node, const MC &Matchers) {
598
103k
    const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
599
103k
    TimeBucketRegion Timer;
600
103k
    for (const auto &MP : Matchers) {
601
1.48k
      if (EnableCheckProfiling)
602
0
        Timer.setBucket(&TimeByBucket[MP.second->getID()]);
603
1.48k
      BoundNodesTreeBuilder Builder;
604
1.48k
      if (MP.first.matches(Node, this, &Builder)) {
605
168
        MatchVisitor Visitor(ActiveASTContext, MP.second);
606
168
        Builder.visitMatches(&Visitor);
607
168
      }
608
1.48k
    }
609
103k
  }
ASTMatchFinder.cpp:void clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::matchWithoutFilter<clang::NestedNameSpecifier, std::__1::vector<std::__1::pair<clang::ast_matchers::internal::Matcher<clang::NestedNameSpecifier>, clang::ast_matchers::MatchFinder::MatchCallback*>, std::__1::allocator<std::__1::pair<clang::ast_matchers::internal::Matcher<clang::NestedNameSpecifier>, clang::ast_matchers::MatchFinder::MatchCallback*> > > >(clang::NestedNameSpecifier const&, std::__1::vector<std::__1::pair<clang::ast_matchers::internal::Matcher<clang::NestedNameSpecifier>, clang::ast_matchers::MatchFinder::MatchCallback*>, std::__1::allocator<std::__1::pair<clang::ast_matchers::internal::Matcher<clang::NestedNameSpecifier>, clang::ast_matchers::MatchFinder::MatchCallback*> > > const&)
Line
Count
Source
597
639
  void matchWithoutFilter(const T &Node, const MC &Matchers) {
598
639
    const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
599
639
    TimeBucketRegion Timer;
600
639
    for (const auto &MP : Matchers) {
601
56
      if (EnableCheckProfiling)
602
0
        Timer.setBucket(&TimeByBucket[MP.second->getID()]);
603
56
      BoundNodesTreeBuilder Builder;
604
56
      if (MP.first.matches(Node, this, &Builder)) {
605
26
        MatchVisitor Visitor(ActiveASTContext, MP.second);
606
26
        Builder.visitMatches(&Visitor);
607
26
      }
608
56
    }
609
639
  }
ASTMatchFinder.cpp:void clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::matchWithoutFilter<clang::NestedNameSpecifierLoc, std::__1::vector<std::__1::pair<clang::ast_matchers::internal::Matcher<clang::NestedNameSpecifierLoc>, clang::ast_matchers::MatchFinder::MatchCallback*>, std::__1::allocator<std::__1::pair<clang::ast_matchers::internal::Matcher<clang::NestedNameSpecifierLoc>, clang::ast_matchers::MatchFinder::MatchCallback*> > > >(clang::NestedNameSpecifierLoc const&, std::__1::vector<std::__1::pair<clang::ast_matchers::internal::Matcher<clang::NestedNameSpecifierLoc>, clang::ast_matchers::MatchFinder::MatchCallback*>, std::__1::allocator<std::__1::pair<clang::ast_matchers::internal::Matcher<clang::NestedNameSpecifierLoc>, clang::ast_matchers::MatchFinder::MatchCallback*> > > const&)
Line
Count
Source
597
637
  void matchWithoutFilter(const T &Node, const MC &Matchers) {
598
637
    const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
599
637
    TimeBucketRegion Timer;
600
637
    for (const auto &MP : Matchers) {
601
40
      if (EnableCheckProfiling)
602
0
        Timer.setBucket(&TimeByBucket[MP.second->getID()]);
603
40
      BoundNodesTreeBuilder Builder;
604
40
      if (MP.first.matches(Node, this, &Builder)) {
605
16
        MatchVisitor Visitor(ActiveASTContext, MP.second);
606
16
        Builder.visitMatches(&Visitor);
607
16
      }
608
40
    }
609
637
  }
ASTMatchFinder.cpp:void clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::matchWithoutFilter<clang::TypeLoc, std::__1::vector<std::__1::pair<clang::ast_matchers::internal::Matcher<clang::TypeLoc>, clang::ast_matchers::MatchFinder::MatchCallback*>, std::__1::allocator<std::__1::pair<clang::ast_matchers::internal::Matcher<clang::TypeLoc>, clang::ast_matchers::MatchFinder::MatchCallback*> > > >(clang::TypeLoc const&, std::__1::vector<std::__1::pair<clang::ast_matchers::internal::Matcher<clang::TypeLoc>, clang::ast_matchers::MatchFinder::MatchCallback*>, std::__1::allocator<std::__1::pair<clang::ast_matchers::internal::Matcher<clang::TypeLoc>, clang::ast_matchers::MatchFinder::MatchCallback*> > > const&)
Line
Count
Source
597
92.0k
  void matchWithoutFilter(const T &Node, const MC &Matchers) {
598
92.0k
    const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
599
92.0k
    TimeBucketRegion Timer;
600
92.0k
    for (const auto &MP : Matchers) {
601
335
      if (EnableCheckProfiling)
602
0
        Timer.setBucket(&TimeByBucket[MP.second->getID()]);
603
335
      BoundNodesTreeBuilder Builder;
604
335
      if (MP.first.matches(Node, this, &Builder)) {
605
170
        MatchVisitor Visitor(ActiveASTContext, MP.second);
606
170
        Builder.visitMatches(&Visitor);
607
170
      }
608
335
    }
609
92.0k
  }
ASTMatchFinder.cpp:void clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::matchWithoutFilter<clang::CXXCtorInitializer, std::__1::vector<std::__1::pair<clang::ast_matchers::internal::Matcher<clang::CXXCtorInitializer>, clang::ast_matchers::MatchFinder::MatchCallback*>, std::__1::allocator<std::__1::pair<clang::ast_matchers::internal::Matcher<clang::CXXCtorInitializer>, clang::ast_matchers::MatchFinder::MatchCallback*> > > >(clang::CXXCtorInitializer const&, std::__1::vector<std::__1::pair<clang::ast_matchers::internal::Matcher<clang::CXXCtorInitializer>, clang::ast_matchers::MatchFinder::MatchCallback*>, std::__1::allocator<std::__1::pair<clang::ast_matchers::internal::Matcher<clang::CXXCtorInitializer>, clang::ast_matchers::MatchFinder::MatchCallback*> > > const&)
Line
Count
Source
597
498
  void matchWithoutFilter(const T &Node, const MC &Matchers) {
598
498
    const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
599
498
    TimeBucketRegion Timer;
600
498
    for (const auto &MP : Matchers) {
601
3
      if (EnableCheckProfiling)
602
0
        Timer.setBucket(&TimeByBucket[MP.second->getID()]);
603
3
      BoundNodesTreeBuilder Builder;
604
3
      if (MP.first.matches(Node, this, &Builder)) {
605
3
        MatchVisitor Visitor(ActiveASTContext, MP.second);
606
3
        Builder.visitMatches(&Visitor);
607
3
      }
608
3
    }
609
498
  }
610
611
157k
  void matchWithFilter(const DynTypedNode &DynNode) {
612
157k
    auto Kind = DynNode.getNodeKind();
613
157k
    auto it = MatcherFiltersMap.find(Kind);
614
157k
    const auto &Filter =
615
157k
        it != MatcherFiltersMap.end() ? 
it->second76.3k
:
getFilterForKind(Kind)81.3k
;
616
157k
617
157k
    if (Filter.empty())
618
110k
      return;
619
46.9k
620
46.9k
    const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
621
46.9k
    TimeBucketRegion Timer;
622
46.9k
    auto &Matchers = this->Matchers->DeclOrStmt;
623
50.6k
    for (unsigned short I : Filter) {
624
50.6k
      auto &MP = Matchers[I];
625
50.6k
      if (EnableCheckProfiling)
626
7
        Timer.setBucket(&TimeByBucket[MP.second->getID()]);
627
50.6k
      BoundNodesTreeBuilder Builder;
628
50.6k
      if (MP.first.matches(DynNode, this, &Builder)) {
629
12.3k
        MatchVisitor Visitor(ActiveASTContext, MP.second);
630
12.3k
        Builder.visitMatches(&Visitor);
631
12.3k
      }
632
50.6k
    }
633
46.9k
  }
634
635
81.3k
  const std::vector<unsigned short> &getFilterForKind(ASTNodeKind Kind) {
636
81.3k
    auto &Filter = MatcherFiltersMap[Kind];
637
81.3k
    auto &Matchers = this->Matchers->DeclOrStmt;
638
81.3k
    assert((Matchers.size() < USHRT_MAX) && "Too many matchers.");
639
174k
    for (unsigned I = 0, E = Matchers.size(); I != E; 
++I93.4k
) {
640
93.4k
      if (Matchers[I].first.canMatchNodesOfKind(Kind)) {
641
34.1k
        Filter.push_back(I);
642
34.1k
      }
643
93.4k
    }
644
81.3k
    return Filter;
645
81.3k
  }
646
647
  /// @{
648
  /// Overloads to pair the different node types to their matchers.
649
102k
  void matchDispatch(const Decl *Node) {
650
102k
    return matchWithFilter(DynTypedNode::create(*Node));
651
102k
  }
652
54.7k
  void matchDispatch(const Stmt *Node) {
653
54.7k
    return matchWithFilter(DynTypedNode::create(*Node));
654
54.7k
  }
655
656
0
  void matchDispatch(const Type *Node) {
657
0
    matchWithoutFilter(QualType(Node, 0), Matchers->Type);
658
0
  }
659
92.0k
  void matchDispatch(const TypeLoc *Node) {
660
92.0k
    matchWithoutFilter(*Node, Matchers->TypeLoc);
661
92.0k
  }
662
103k
  void matchDispatch(const QualType *Node) {
663
103k
    matchWithoutFilter(*Node, Matchers->Type);
664
103k
  }
665
639
  void matchDispatch(const NestedNameSpecifier *Node) {
666
639
    matchWithoutFilter(*Node, Matchers->NestedNameSpecifier);
667
639
  }
668
637
  void matchDispatch(const NestedNameSpecifierLoc *Node) {
669
637
    matchWithoutFilter(*Node, Matchers->NestedNameSpecifierLoc);
670
637
  }
671
498
  void matchDispatch(const CXXCtorInitializer *Node) {
672
498
    matchWithoutFilter(*Node, Matchers->CtorInit);
673
498
  }
674
0
  void matchDispatch(const void *) { /* Do nothing. */ }
675
  /// @}
676
677
  // Returns whether an ancestor of \p Node matches \p Matcher.
678
  //
679
  // The order of matching ((which can lead to different nodes being bound in
680
  // case there are multiple matches) is breadth first search.
681
  //
682
  // To allow memoization in the very common case of having deeply nested
683
  // expressions inside a template function, we first walk up the AST, memoizing
684
  // the result of the match along the way, as long as there is only a single
685
  // parent.
686
  //
687
  // Once there are multiple parents, the breadth first search order does not
688
  // allow simple memoization on the ancestors. Thus, we only memoize as long
689
  // as there is a single parent.
690
  bool memoizedMatchesAncestorOfRecursively(const DynTypedNode &Node,
691
                                            ASTContext &Ctx,
692
                                            const DynTypedMatcher &Matcher,
693
                                            BoundNodesTreeBuilder *Builder,
694
5.10k
                                            AncestorMatchMode MatchMode) {
695
5.10k
    // For AST-nodes that don't have an identity, we can't memoize.
696
5.10k
    if (!Builder->isComparable())
697
12
      return matchesAncestorOfRecursively(Node, Ctx, Matcher, Builder,
698
12
                                          MatchMode);
699
5.09k
700
5.09k
    MatchKey Key;
701
5.09k
    Key.MatcherID = Matcher.getID();
702
5.09k
    Key.Node = Node;
703
5.09k
    Key.BoundNodes = *Builder;
704
5.09k
    Key.Traversal = Ctx.getParentMapContext().getTraversalKind();
705
5.09k
706
5.09k
    // Note that we cannot use insert and reuse the iterator, as recursive
707
5.09k
    // calls to match might invalidate the result cache iterators.
708
5.09k
    MemoizationMap::iterator I = ResultCache.find(Key);
709
5.09k
    if (I != ResultCache.end()) {
710
157
      *Builder = I->second.Nodes;
711
157
      return I->second.ResultOfMatch;
712
157
    }
713
4.93k
714
4.93k
    MemoizedMatchResult Result;
715
4.93k
    Result.Nodes = *Builder;
716
4.93k
    Result.ResultOfMatch = matchesAncestorOfRecursively(
717
4.93k
        Node, Ctx, Matcher, &Result.Nodes, MatchMode);
718
4.93k
719
4.93k
    MemoizedMatchResult &CachedResult = ResultCache[Key];
720
4.93k
    CachedResult = std::move(Result);
721
4.93k
722
4.93k
    *Builder = CachedResult.Nodes;
723
4.93k
    return CachedResult.ResultOfMatch;
724
4.93k
  }
725
726
  bool matchesAncestorOfRecursively(const DynTypedNode &Node, ASTContext &Ctx,
727
                                    const DynTypedMatcher &Matcher,
728
                                    BoundNodesTreeBuilder *Builder,
729
4.94k
                                    AncestorMatchMode MatchMode) {
730
4.94k
    const auto &Parents = ActiveASTContext->getParents(Node);
731
4.94k
    if (Parents.empty()) {
732
598
      // Nodes may have no parents if:
733
598
      //  a) the node is the TranslationUnitDecl
734
598
      //  b) we have a limited traversal scope that excludes the parent edges
735
598
      //  c) there is a bug in the AST, and the node is not reachable
736
598
      // Usually the traversal scope is the whole AST, which precludes b.
737
598
      // Bugs are common enough that it's worthwhile asserting when we can.
738
598
#ifndef NDEBUG
739
598
      if (!Node.get<TranslationUnitDecl>() &&
740
598
          /* Traversal scope is full AST if any of the bounds are the TU */
741
598
          
llvm::any_of(ActiveASTContext->getTraversalScope(), [](Decl *D) 0
{
742
0
            return D->getKind() == Decl::TranslationUnit;
743
0
          })) {
744
0
        llvm::errs() << "Tried to match orphan node:\n";
745
0
        Node.dump(llvm::errs(), ActiveASTContext->getSourceManager());
746
0
        llvm_unreachable("Parent map should be complete!");
747
0
      }
748
598
#endif
749
598
      return false;
750
598
    }
751
4.34k
    if (Parents.size() == 1) {
752
4.33k
      // Only one parent - do recursive memoization.
753
4.33k
      const DynTypedNode Parent = Parents[0];
754
4.33k
      BoundNodesTreeBuilder BuilderCopy = *Builder;
755
4.33k
      if (Matcher.matches(Parent, this, &BuilderCopy)) {
756
525
        *Builder = std::move(BuilderCopy);
757
525
        return true;
758
525
      }
759
3.80k
      if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
760
3.50k
        return memoizedMatchesAncestorOfRecursively(Parent, Ctx, Matcher,
761
3.50k
                                                    Builder, MatchMode);
762
3.50k
        // Once we get back from the recursive call, the result will be the
763
3.50k
        // same as the parent's result.
764
3.50k
      }
765
15
    } else {
766
15
      // Multiple parents - BFS over the rest of the nodes.
767
15
      llvm::DenseSet<const void *> Visited;
768
15
      std::deque<DynTypedNode> Queue(Parents.begin(), Parents.end());
769
53
      while (!Queue.empty()) {
770
50
        BoundNodesTreeBuilder BuilderCopy = *Builder;
771
50
        if (Matcher.matches(Queue.front(), this, &BuilderCopy)) {
772
12
          *Builder = std::move(BuilderCopy);
773
12
          return true;
774
12
        }
775
38
        if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
776
34
          for (const auto &Parent :
777
34
               ActiveASTContext->getParents(Queue.front())) {
778
32
            // Make sure we do not visit the same node twice.
779
32
            // Otherwise, we'll visit the common ancestors as often as there
780
32
            // are splits on the way down.
781
32
            if (Visited.insert(Parent.getMemoizationData()).second)
782
29
              Queue.push_back(Parent);
783
32
          }
784
34
        }
785
38
        Queue.pop_front();
786
38
      }
787
15
    }
788
4.34k
    
return false306
;
789
4.34k
  }
790
791
  // Implements a BoundNodesTree::Visitor that calls a MatchCallback with
792
  // the aggregated bound nodes for each match.
793
  class MatchVisitor : public BoundNodesTreeBuilder::Visitor {
794
  public:
795
    MatchVisitor(ASTContext* Context,
796
                 MatchFinder::MatchCallback* Callback)
797
      : Context(Context),
798
12.7k
        Callback(Callback) {}
799
800
12.9k
    void visitMatch(const BoundNodes& BoundNodesView) override {
801
12.9k
      Callback->run(MatchFinder::MatchResult(BoundNodesView, Context));
802
12.9k
    }
803
804
  private:
805
    ASTContext* Context;
806
    MatchFinder::MatchCallback* Callback;
807
  };
808
809
  // Returns true if 'TypeNode' has an alias that matches the given matcher.
810
  bool typeHasMatchingAlias(const Type *TypeNode,
811
                            const Matcher<NamedDecl> &Matcher,
812
619
                            BoundNodesTreeBuilder *Builder) {
813
619
    const Type *const CanonicalType =
814
619
      ActiveASTContext->getCanonicalType(TypeNode);
815
619
    auto Aliases = TypeAliases.find(CanonicalType);
816
619
    if (Aliases == TypeAliases.end())
817
565
      return false;
818
76
    
for (const TypedefNameDecl *Alias : Aliases->second)54
{
819
76
      BoundNodesTreeBuilder Result(*Builder);
820
76
      if (Matcher.matches(*Alias, this, &Result)) {
821
24
        *Builder = std::move(Result);
822
24
        return true;
823
24
      }
824
76
    }
825
54
    
return false30
;
826
54
  }
827
828
  bool
829
  objcClassHasMatchingCompatibilityAlias(const ObjCInterfaceDecl *InterfaceDecl,
830
                                         const Matcher<NamedDecl> &Matcher,
831
58
                                         BoundNodesTreeBuilder *Builder) {
832
58
    auto Aliases = CompatibleAliases.find(InterfaceDecl);
833
58
    if (Aliases == CompatibleAliases.end())
834
34
      return false;
835
24
    for (const ObjCCompatibleAliasDecl *Alias : Aliases->second) {
836
24
      BoundNodesTreeBuilder Result(*Builder);
837
24
      if (Matcher.matches(*Alias, this, &Result)) {
838
12
        *Builder = std::move(Result);
839
12
        return true;
840
12
      }
841
24
    }
842
24
    
return false12
;
843
24
  }
844
845
  /// Bucket to record map.
846
  ///
847
  /// Used to get the appropriate bucket for each matcher.
848
  llvm::StringMap<llvm::TimeRecord> TimeByBucket;
849
850
  const MatchFinder::MatchersByType *Matchers;
851
852
  /// Filtered list of matcher indices for each matcher kind.
853
  ///
854
  /// \c Decl and \c Stmt toplevel matchers usually apply to a specific node
855
  /// kind (and derived kinds) so it is a waste to try every matcher on every
856
  /// node.
857
  /// We precalculate a list of matchers that pass the toplevel restrict check.
858
  llvm::DenseMap<ASTNodeKind, std::vector<unsigned short>> MatcherFiltersMap;
859
860
  const MatchFinder::MatchFinderOptions &Options;
861
  ASTContext *ActiveASTContext;
862
863
  // Maps a canonical type to its TypedefDecls.
864
  llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases;
865
866
  // Maps an Objective-C interface to its ObjCCompatibleAliasDecls.
867
  llvm::DenseMap<const ObjCInterfaceDecl *,
868
                 llvm::SmallPtrSet<const ObjCCompatibleAliasDecl *, 2>>
869
      CompatibleAliases;
870
871
  // Maps (matcher, node) -> the match result for memoization.
872
  typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap;
873
  MemoizationMap ResultCache;
874
};
875
876
static CXXRecordDecl *
877
561
getAsCXXRecordDeclOrPrimaryTemplate(const Type *TypeNode) {
878
561
  if (auto *RD = TypeNode->getAsCXXRecordDecl())
879
523
    return RD;
880
38
881
38
  // Find the innermost TemplateSpecializationType that isn't an alias template.
882
38
  auto *TemplateType = TypeNode->getAs<TemplateSpecializationType>();
883
40
  while (TemplateType && 
TemplateType->isTypeAlias()22
)
884
2
    TemplateType =
885
2
        TemplateType->getAliasedType()->getAs<TemplateSpecializationType>();
886
38
887
38
  // If this is the name of a (dependent) template specialization, use the
888
38
  // definition of the template, even though it might be specialized later.
889
38
  if (TemplateType)
890
20
    if (auto *ClassTemplate = dyn_cast_or_null<ClassTemplateDecl>(
891
16
          TemplateType->getTemplateName().getAsTemplateDecl()))
892
16
      return ClassTemplate->getTemplatedDecl();
893
22
894
22
  return nullptr;
895
22
}
896
897
// Returns true if the given C++ class is directly or indirectly derived
898
// from a base type with the given name.  A class is not considered to be
899
// derived from itself.
900
bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,
901
                                         const Matcher<NamedDecl> &Base,
902
                                         BoundNodesTreeBuilder *Builder,
903
1.32k
                                         bool Directly) {
904
1.32k
  if (!Declaration->hasDefinition())
905
479
    return false;
906
841
  for (const auto &It : Declaration->bases()) {
907
573
    const Type *TypeNode = It.getType().getTypePtr();
908
573
909
573
    if (typeHasMatchingAlias(TypeNode, Base, Builder))
910
12
      return true;
911
561
912
561
    // FIXME: Going to the primary template here isn't really correct, but
913
561
    // unfortunately we accept a Decl matcher for the base class not a Type
914
561
    // matcher, so it's the best thing we can do with our current interface.
915
561
    CXXRecordDecl *ClassDecl = getAsCXXRecordDeclOrPrimaryTemplate(TypeNode);
916
561
    if (!ClassDecl)
917
22
      continue;
918
539
    if (ClassDecl == Declaration) {
919
4
      // This can happen for recursive template definitions; if the
920
4
      // current declaration did not match, we can safely return false.
921
4
      return false;
922
4
    }
923
535
    BoundNodesTreeBuilder Result(*Builder);
924
535
    if (Base.matches(*ClassDecl, this, &Result)) {
925
260
      *Builder = std::move(Result);
926
260
      return true;
927
260
    }
928
275
    if (!Directly && 
classIsDerivedFrom(ClassDecl, Base, Builder, Directly)267
)
929
220
      return true;
930
275
  }
931
841
  
return false345
;
932
841
}
933
934
// Returns true if the given Objective-C class is directly or indirectly
935
// derived from a matching base class. A class is not considered to be derived
936
// from itself.
937
bool MatchASTVisitor::objcClassIsDerivedFrom(
938
    const ObjCInterfaceDecl *Declaration, const Matcher<NamedDecl> &Base,
939
140
    BoundNodesTreeBuilder *Builder, bool Directly) {
940
140
  // Check if any of the superclasses of the class match.
941
140
  for (const ObjCInterfaceDecl *ClassDecl = Declaration->getSuperClass();
942
144
       ClassDecl != nullptr; 
ClassDecl = ClassDecl->getSuperClass()4
) {
943
58
    // Check if there are any matching compatibility aliases.
944
58
    if (objcClassHasMatchingCompatibilityAlias(ClassDecl, Base, Builder))
945
12
      return true;
946
46
947
46
    // Check if there are any matching type aliases.
948
46
    const Type *TypeNode = ClassDecl->getTypeForDecl();
949
46
    if (typeHasMatchingAlias(TypeNode, Base, Builder))
950
12
      return true;
951
34
952
34
    if (Base.matches(*ClassDecl, this, Builder))
953
30
      return true;
954
4
955
4
    // Not `return false` as a temporary workaround for PR43879.
956
4
    if (Directly)
957
0
      break;
958
4
  }
959
140
960
140
  
return false86
;
961
140
}
962
963
100k
bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {
964
100k
  if (!DeclNode) {
965
27
    return true;
966
27
  }
967
100k
  match(*DeclNode);
968
100k
  return RecursiveASTVisitor<MatchASTVisitor>::TraverseDecl(DeclNode);
969
100k
}
970
971
48.6k
bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue) {
972
48.6k
  if (!StmtNode) {
973
12.2k
    return true;
974
12.2k
  }
975
36.3k
  match(*StmtNode);
976
36.3k
  return RecursiveASTVisitor<MatchASTVisitor>::TraverseStmt(StmtNode, Queue);
977
36.3k
}
978
979
11.7k
bool MatchASTVisitor::TraverseType(QualType TypeNode) {
980
11.7k
  match(TypeNode);
981
11.7k
  return RecursiveASTVisitor<MatchASTVisitor>::TraverseType(TypeNode);
982
11.7k
}
983
984
92.0k
bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode) {
985
92.0k
  // The RecursiveASTVisitor only visits types if they're not within TypeLocs.
986
92.0k
  // We still want to find those types via matchers, so we match them here. Note
987
92.0k
  // that the TypeLocs are structurally a shadow-hierarchy to the expressed
988
92.0k
  // type, so we visit all involved parts of a compound type when matching on
989
92.0k
  // each TypeLoc.
990
92.0k
  match(TypeLocNode);
991
92.0k
  match(TypeLocNode.getType());
992
92.0k
  return RecursiveASTVisitor<MatchASTVisitor>::TraverseTypeLoc(TypeLocNode);
993
92.0k
}
994
995
2
bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
996
2
  match(*NNS);
997
2
  return RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifier(NNS);
998
2
}
999
1000
bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
1001
49.5k
    NestedNameSpecifierLoc NNS) {
1002
49.5k
  if (!NNS)
1003
48.8k
    return true;
1004
637
1005
637
  match(NNS);
1006
637
1007
637
  // We only match the nested name specifier here (as opposed to traversing it)
1008
637
  // because the traversal is already done in the parallel "Loc"-hierarchy.
1009
637
  if (NNS.hasQualifier())
1010
637
    match(*NNS.getNestedNameSpecifier());
1011
637
  return
1012
637
      RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifierLoc(NNS);
1013
637
}
1014
1015
bool MatchASTVisitor::TraverseConstructorInitializer(
1016
498
    CXXCtorInitializer *CtorInit) {
1017
498
  if (!CtorInit)
1018
0
    return true;
1019
498
1020
498
  match(*CtorInit);
1021
498
1022
498
  return RecursiveASTVisitor<MatchASTVisitor>::TraverseConstructorInitializer(
1023
498
      CtorInit);
1024
498
}
1025
1026
class MatchASTConsumer : public ASTConsumer {
1027
public:
1028
  MatchASTConsumer(MatchFinder *Finder,
1029
                   MatchFinder::ParsingDoneTestCallback *ParsingDone)
1030
2.51k
      : Finder(Finder), ParsingDone(ParsingDone) {}
1031
1032
private:
1033
2.51k
  void HandleTranslationUnit(ASTContext &Context) override {
1034
2.51k
    if (ParsingDone != nullptr) {
1035
0
      ParsingDone->run();
1036
0
    }
1037
2.51k
    Finder->matchAST(Context);
1038
2.51k
  }
1039
1040
  MatchFinder *Finder;
1041
  MatchFinder::ParsingDoneTestCallback *ParsingDone;
1042
};
1043
1044
} // end namespace
1045
} // end namespace internal
1046
1047
MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes,
1048
                                      ASTContext *Context)
1049
  : Nodes(Nodes), Context(Context),
1050
13.0k
    SourceManager(&Context->getSourceManager()) {}
1051
1052
30.4k
MatchFinder::MatchCallback::~MatchCallback() {}
1053
0
MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {}
1054
1055
MatchFinder::MatchFinder(MatchFinderOptions Options)
1056
28.8k
    : Options(std::move(Options)), ParsingDone(nullptr) {}
1057
1058
28.8k
MatchFinder::~MatchFinder() {}
1059
1060
void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch,
1061
9.88k
                             MatchCallback *Action) {
1062
9.88k
  Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
1063
9.88k
  Matchers.AllCallbacks.insert(Action);
1064
9.88k
}
1065
1066
void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
1067
203
                             MatchCallback *Action) {
1068
203
  Matchers.Type.emplace_back(NodeMatch, Action);
1069
203
  Matchers.AllCallbacks.insert(Action);
1070
203
}
1071
1072
void MatchFinder::addMatcher(const StatementMatcher &NodeMatch,
1073
20.5k
                             MatchCallback *Action) {
1074
20.5k
  Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
1075
20.5k
  Matchers.AllCallbacks.insert(Action);
1076
20.5k
}
1077
1078
void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch,
1079
34
                             MatchCallback *Action) {
1080
34
  Matchers.NestedNameSpecifier.emplace_back(NodeMatch, Action);
1081
34
  Matchers.AllCallbacks.insert(Action);
1082
34
}
1083
1084
void MatchFinder::addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch,
1085
18
                             MatchCallback *Action) {
1086
18
  Matchers.NestedNameSpecifierLoc.emplace_back(NodeMatch, Action);
1087
18
  Matchers.AllCallbacks.insert(Action);
1088
18
}
1089
1090
void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch,
1091
45
                             MatchCallback *Action) {
1092
45
  Matchers.TypeLoc.emplace_back(NodeMatch, Action);
1093
45
  Matchers.AllCallbacks.insert(Action);
1094
45
}
1095
1096
void MatchFinder::addMatcher(const CXXCtorInitializerMatcher &NodeMatch,
1097
3
                             MatchCallback *Action) {
1098
3
  Matchers.CtorInit.emplace_back(NodeMatch, Action);
1099
3
  Matchers.AllCallbacks.insert(Action);
1100
3
}
1101
1102
bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch,
1103
1.92k
                                    MatchCallback *Action) {
1104
1.92k
  if (NodeMatch.canConvertTo<Decl>()) {
1105
972
    addMatcher(NodeMatch.convertTo<Decl>(), Action);
1106
972
    return true;
1107
972
  } else 
if (950
NodeMatch.canConvertTo<QualType>()950
) {
1108
100
    addMatcher(NodeMatch.convertTo<QualType>(), Action);
1109
100
    return true;
1110
850
  } else if (NodeMatch.canConvertTo<Stmt>()) {
1111
814
    addMatcher(NodeMatch.convertTo<Stmt>(), Action);
1112
814
    return true;
1113
814
  } else 
if (36
NodeMatch.canConvertTo<NestedNameSpecifier>()36
) {
1114
16
    addMatcher(NodeMatch.convertTo<NestedNameSpecifier>(), Action);
1115
16
    return true;
1116
20
  } else if (NodeMatch.canConvertTo<NestedNameSpecifierLoc>()) {
1117
7
    addMatcher(NodeMatch.convertTo<NestedNameSpecifierLoc>(), Action);
1118
7
    return true;
1119
13
  } else if (NodeMatch.canConvertTo<TypeLoc>()) {
1120
10
    addMatcher(NodeMatch.convertTo<TypeLoc>(), Action);
1121
10
    return true;
1122
10
  } else 
if (3
NodeMatch.canConvertTo<CXXCtorInitializer>()3
) {
1123
1
    addMatcher(NodeMatch.convertTo<CXXCtorInitializer>(), Action);
1124
1
    return true;
1125
1
  }
1126
2
  return false;
1127
2
}
1128
1129
2.51k
std::unique_ptr<ASTConsumer> MatchFinder::newASTConsumer() {
1130
2.51k
  return std::make_unique<internal::MatchASTConsumer>(this, ParsingDone);
1131
2.51k
}
1132
1133
20.4k
void MatchFinder::match(const clang::DynTypedNode &Node, ASTContext &Context) {
1134
20.4k
  internal::MatchASTVisitor Visitor(&Matchers, Options);
1135
20.4k
  Visitor.set_active_ast_context(&Context);
1136
20.4k
  Visitor.match(Node);
1137
20.4k
}
1138
1139
8.46k
void MatchFinder::matchAST(ASTContext &Context) {
1140
8.46k
  internal::MatchASTVisitor Visitor(&Matchers, Options);
1141
8.46k
  Visitor.set_active_ast_context(&Context);
1142
8.46k
  Visitor.onStartOfTranslationUnit();
1143
8.46k
  Visitor.TraverseAST(Context);
1144
8.46k
  Visitor.onEndOfTranslationUnit();
1145
8.46k
}
1146
1147
void MatchFinder::registerTestCallbackAfterParsing(
1148
0
    MatchFinder::ParsingDoneTestCallback *NewParsingDone) {
1149
0
  ParsingDone = NewParsingDone;
1150
0
}
1151
1152
0
StringRef MatchFinder::MatchCallback::getID() const { return "<unknown>"; }
1153
1154
} // end namespace ast_matchers
1155
} // end namespace clang