Coverage Report

Created: 2020-09-19 12:23

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