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/DeclCXX.h"
22#include "clang/AST/RecursiveASTVisitor.h"
23#include "llvm/ADT/DenseMap.h"
24#include "llvm/ADT/SmallPtrSet.h"
25#include "llvm/ADT/StringMap.h"
26#include "llvm/Support/PrettyStackTrace.h"
27#include "llvm/Support/Timer.h"
28#include <deque>
29#include <memory>
30#include <set>
31
32namespace clang {
33namespace ast_matchers {
34namespace internal {
35namespace {
36
37typedef MatchFinder::MatchCallback MatchCallback;
38
39// The maximum number of memoization entries to store.
40// 10k has been experimentally found to give a good trade-off
41// of performance vs. memory consumption by running matcher
42// that match on every statement over a very large codebase.
43//
44// FIXME: Do some performance optimization in general and
45// revisit this number; also, put up micro-benchmarks that we can
46// optimize this on.
47static const unsigned MaxMemoizationEntries = 10000;
48
49enum class MatchType {
50 Ancestors,
51
52 Descendants,
53 Child,
54};
55
56// We use memoization to avoid running the same matcher on the same
57// AST node twice. This struct is the key for looking up match
58// result. It consists of an ID of the MatcherInterface (for
59// identifying the matcher), a pointer to the AST node and the
60// bound nodes before the matcher was executed.
61//
62// We currently only memoize on nodes whose pointers identify the
63// nodes (\c Stmt and \c Decl, but not \c QualType or \c TypeLoc).
64// For \c QualType and \c TypeLoc it is possible to implement
65// generation of keys for each type.
66// FIXME: Benchmark whether memoization of non-pointer typed nodes
67// provides enough benefit for the additional amount of code.
68struct MatchKey {
69 DynTypedMatcher::MatcherIDType MatcherID;
70 DynTypedNode Node;
71 BoundNodesTreeBuilder BoundNodes;
72 TraversalKind Traversal = TK_AsIs;
73 MatchType Type;
74
75 bool operator<(const MatchKey &Other) const {
76 return std::tie(args: Traversal, args: Type, args: MatcherID, args: Node, args: BoundNodes) <
77 std::tie(args: Other.Traversal, args: Other.Type, args: Other.MatcherID, args: Other.Node,
78 args: Other.BoundNodes);
79 }
80};
81
82// Used to store the result of a match and possibly bound nodes.
83struct MemoizedMatchResult {
84 bool ResultOfMatch;
85 BoundNodesTreeBuilder Nodes;
86};
87
88// A RecursiveASTVisitor that traverses all children or all descendants of
89// a node.
90class MatchChildASTVisitor
91 : public RecursiveASTVisitor<MatchChildASTVisitor> {
92public:
93 typedef RecursiveASTVisitor<MatchChildASTVisitor> VisitorBase;
94
95 // Creates an AST visitor that matches 'matcher' on all children or
96 // descendants of a traversed node. max_depth is the maximum depth
97 // to traverse: use 1 for matching the children and INT_MAX for
98 // matching the descendants.
99 MatchChildASTVisitor(const DynTypedMatcher *Matcher, ASTMatchFinder *Finder,
100 BoundNodesTreeBuilder *Builder, int MaxDepth,
101 bool IgnoreImplicitChildren,
102 ASTMatchFinder::BindKind Bind)
103 : Matcher(Matcher), Finder(Finder), Builder(Builder), CurrentDepth(0),
104 MaxDepth(MaxDepth), IgnoreImplicitChildren(IgnoreImplicitChildren),
105 Bind(Bind), Matches(false) {}
106
107 // Returns true if a match is found in the subtree rooted at the
108 // given AST node. This is done via a set of mutually recursive
109 // functions. Here's how the recursion is done (the *wildcard can
110 // actually be Decl, Stmt, or Type):
111 //
112 // - Traverse(node) calls BaseTraverse(node) when it needs
113 // to visit the descendants of node.
114 // - BaseTraverse(node) then calls (via VisitorBase::Traverse*(node))
115 // Traverse*(c) for each child c of 'node'.
116 // - Traverse*(c) in turn calls Traverse(c), completing the
117 // recursion.
118 bool findMatch(const DynTypedNode &DynNode) {
119 reset();
120 if (const Decl *D = DynNode.get<Decl>())
121 traverse(Node: *D);
122 else if (const Stmt *S = DynNode.get<Stmt>())
123 traverse(Node: *S);
124 else if (const NestedNameSpecifier *NNS =
125 DynNode.get<NestedNameSpecifier>())
126 traverse(Node: *NNS);
127 else if (const NestedNameSpecifierLoc *NNSLoc =
128 DynNode.get<NestedNameSpecifierLoc>())
129 traverse(Node: *NNSLoc);
130 else if (const QualType *Q = DynNode.get<QualType>())
131 traverse(Node: *Q);
132 else if (const TypeLoc *T = DynNode.get<TypeLoc>())
133 traverse(Node: *T);
134 else if (const auto *C = DynNode.get<CXXCtorInitializer>())
135 traverse(Node: *C);
136 else if (const TemplateArgumentLoc *TALoc =
137 DynNode.get<TemplateArgumentLoc>())
138 traverse(Node: *TALoc);
139 else if (const Attr *A = DynNode.get<Attr>())
140 traverse(Node: *A);
141 // FIXME: Add other base types after adding tests.
142
143 // It's OK to always overwrite the bound nodes, as if there was
144 // no match in this recursive branch, the result set is empty
145 // anyway.
146 *Builder = ResultBindings;
147
148 return Matches;
149 }
150
151 // The following are overriding methods from the base visitor class.
152 // They are public only to allow CRTP to work. They are *not *part
153 // of the public API of this class.
154 bool TraverseDecl(Decl *DeclNode) {
155
156 if (DeclNode && DeclNode->isImplicit() &&
157 Finder->isTraversalIgnoringImplicitNodes())
158 return baseTraverse(DeclNode: *DeclNode);
159
160 ScopedIncrement ScopedDepth(&CurrentDepth);
161 return (DeclNode == nullptr) || traverse(Node: *DeclNode);
162 }
163
164 Stmt *getStmtToTraverse(Stmt *StmtNode) {
165 Stmt *StmtToTraverse = StmtNode;
166 if (auto *ExprNode = dyn_cast_or_null<Expr>(Val: StmtNode)) {
167 auto *LambdaNode = dyn_cast_or_null<LambdaExpr>(Val: StmtNode);
168 if (LambdaNode && Finder->isTraversalIgnoringImplicitNodes())
169 StmtToTraverse = LambdaNode;
170 else
171 StmtToTraverse =
172 Finder->getASTContext().getParentMapContext().traverseIgnored(
173 E: ExprNode);
174 }
175 return StmtToTraverse;
176 }
177
178 bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue = nullptr) {
179 // If we need to keep track of the depth, we can't perform data recursion.
180 if (CurrentDepth == 0 || (CurrentDepth <= MaxDepth && MaxDepth < INT_MAX))
181 Queue = nullptr;
182
183 ScopedIncrement ScopedDepth(&CurrentDepth);
184 Stmt *StmtToTraverse = getStmtToTraverse(StmtNode);
185 if (!StmtToTraverse)
186 return true;
187
188 if (IgnoreImplicitChildren && isa<CXXDefaultArgExpr>(Val: StmtNode))
189 return true;
190
191 if (!match(Node: *StmtToTraverse))
192 return false;
193 return VisitorBase::TraverseStmt(S: StmtToTraverse, Queue);
194 }
195 // We assume that the QualType and the contained type are on the same
196 // hierarchy level. Thus, we try to match either of them.
197 bool TraverseType(QualType TypeNode) {
198 if (TypeNode.isNull())
199 return true;
200 ScopedIncrement ScopedDepth(&CurrentDepth);
201 // Match the Type.
202 if (!match(Node: *TypeNode))
203 return false;
204 // The QualType is matched inside traverse.
205 return traverse(Node: TypeNode);
206 }
207 // We assume that the TypeLoc, contained QualType and contained Type all are
208 // on the same hierarchy level. Thus, we try to match all of them.
209 bool TraverseTypeLoc(TypeLoc TypeLocNode) {
210 if (TypeLocNode.isNull())
211 return true;
212 ScopedIncrement ScopedDepth(&CurrentDepth);
213 // Match the Type.
214 if (!match(Node: *TypeLocNode.getType()))
215 return false;
216 // Match the QualType.
217 if (!match(Node: TypeLocNode.getType()))
218 return false;
219 // The TypeLoc is matched inside traverse.
220 return traverse(Node: TypeLocNode);
221 }
222 bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
223 ScopedIncrement ScopedDepth(&CurrentDepth);
224 return (NNS == nullptr) || traverse(Node: *NNS);
225 }
226 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS) {
227 if (!NNS)
228 return true;
229 ScopedIncrement ScopedDepth(&CurrentDepth);
230 if (!match(Node: *NNS.getNestedNameSpecifier()))
231 return false;
232 return traverse(Node: NNS);
233 }
234 bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit) {
235 if (!CtorInit)
236 return true;
237 ScopedIncrement ScopedDepth(&CurrentDepth);
238 return traverse(Node: *CtorInit);
239 }
240 bool TraverseTemplateArgumentLoc(TemplateArgumentLoc TAL) {
241 ScopedIncrement ScopedDepth(&CurrentDepth);
242 return traverse(Node: TAL);
243 }
244 bool TraverseCXXForRangeStmt(CXXForRangeStmt *Node) {
245 if (!Finder->isTraversalIgnoringImplicitNodes())
246 return VisitorBase::TraverseCXXForRangeStmt(S: Node);
247 if (!Node)
248 return true;
249 ScopedIncrement ScopedDepth(&CurrentDepth);
250 if (auto *Init = Node->getInit())
251 if (!traverse(Node: *Init))
252 return false;
253 if (!match(Node: *Node->getLoopVariable()))
254 return false;
255 if (match(Node: *Node->getRangeInit()))
256 if (!VisitorBase::TraverseStmt(S: Node->getRangeInit()))
257 return false;
258 if (!match(Node: *Node->getBody()))
259 return false;
260 return VisitorBase::TraverseStmt(S: Node->getBody());
261 }
262 bool TraverseCXXRewrittenBinaryOperator(CXXRewrittenBinaryOperator *Node) {
263 if (!Finder->isTraversalIgnoringImplicitNodes())
264 return VisitorBase::TraverseCXXRewrittenBinaryOperator(S: Node);
265 if (!Node)
266 return true;
267 ScopedIncrement ScopedDepth(&CurrentDepth);
268
269 return match(Node: *Node->getLHS()) && match(Node: *Node->getRHS());
270 }
271 bool TraverseAttr(Attr *A) {
272 if (A == nullptr ||
273 (A->isImplicit() &&
274 Finder->getASTContext().getParentMapContext().getTraversalKind() ==
275 TK_IgnoreUnlessSpelledInSource))
276 return true;
277 ScopedIncrement ScopedDepth(&CurrentDepth);
278 return traverse(Node: *A);
279 }
280 bool TraverseLambdaExpr(LambdaExpr *Node) {
281 if (!Finder->isTraversalIgnoringImplicitNodes())
282 return VisitorBase::TraverseLambdaExpr(S: Node);
283 if (!Node)
284 return true;
285 ScopedIncrement ScopedDepth(&CurrentDepth);
286
287 for (unsigned I = 0, N = Node->capture_size(); I != N; ++I) {
288 const LambdaCapture *C = Node->capture_begin() + I;
289 if (!C->isExplicit())
290 continue;
291 if (Node->isInitCapture(Capture: C) && !match(Node: *C->getCapturedVar()))
292 return false;
293 const Expr *CIE = Node->capture_init_begin()[I];
294 if (CIE != nullptr && !match(Node: *CIE))
295 return false;
296 }
297
298 if (const auto *TPL = Node->getTemplateParameterList()) {
299 for (const auto *TP : *TPL) {
300 if (!match(Node: *TP))
301 return false;
302 }
303 }
304
305 for (const auto *P : Node->getCallOperator()->parameters()) {
306 if (!match(Node: *P))
307 return false;
308 }
309
310 if (!match(Node: *Node->getBody()))
311 return false;
312
313 return VisitorBase::TraverseStmt(S: Node->getBody());
314 }
315
316 bool shouldVisitTemplateInstantiations() const { return true; }
317 bool shouldVisitImplicitCode() const { return !IgnoreImplicitChildren; }
318
319private:
320 // Used for updating the depth during traversal.
321 struct ScopedIncrement {
322 explicit ScopedIncrement(int *Depth) : Depth(Depth) { ++(*Depth); }
323 ~ScopedIncrement() { --(*Depth); }
324
325 private:
326 int *Depth;
327 };
328
329 // Resets the state of this object.
330 void reset() {
331 Matches = false;
332 CurrentDepth = 0;
333 }
334
335 // Forwards the call to the corresponding Traverse*() method in the
336 // base visitor class.
337 bool baseTraverse(const Decl &DeclNode) {
338 return VisitorBase::TraverseDecl(D: const_cast<Decl*>(&DeclNode));
339 }
340 bool baseTraverse(const Stmt &StmtNode) {
341 return VisitorBase::TraverseStmt(S: const_cast<Stmt*>(&StmtNode));
342 }
343 bool baseTraverse(QualType TypeNode) {
344 return VisitorBase::TraverseType(T: TypeNode);
345 }
346 bool baseTraverse(TypeLoc TypeLocNode) {
347 return VisitorBase::TraverseTypeLoc(TL: TypeLocNode);
348 }
349 bool baseTraverse(const NestedNameSpecifier &NNS) {
350 return VisitorBase::TraverseNestedNameSpecifier(
351 NNS: const_cast<NestedNameSpecifier*>(&NNS));
352 }
353 bool baseTraverse(NestedNameSpecifierLoc NNS) {
354 return VisitorBase::TraverseNestedNameSpecifierLoc(NNS);
355 }
356 bool baseTraverse(const CXXCtorInitializer &CtorInit) {
357 return VisitorBase::TraverseConstructorInitializer(
358 Init: const_cast<CXXCtorInitializer *>(&CtorInit));
359 }
360 bool baseTraverse(TemplateArgumentLoc TAL) {
361 return VisitorBase::TraverseTemplateArgumentLoc(ArgLoc: TAL);
362 }
363 bool baseTraverse(const Attr &AttrNode) {
364 return VisitorBase::TraverseAttr(A: const_cast<Attr *>(&AttrNode));
365 }
366
367 // Sets 'Matched' to true if 'Matcher' matches 'Node' and:
368 // 0 < CurrentDepth <= MaxDepth.
369 //
370 // Returns 'true' if traversal should continue after this function
371 // returns, i.e. if no match is found or 'Bind' is 'BK_All'.
372 template <typename T>
373 bool match(const T &Node) {
374 if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
375 return true;
376 }
377 if (Bind != ASTMatchFinder::BK_All) {
378 BoundNodesTreeBuilder RecursiveBuilder(*Builder);
379 if (Matcher->matches(DynNode: DynTypedNode::create(Node), Finder,
380 Builder: &RecursiveBuilder)) {
381 Matches = true;
382 ResultBindings.addMatch(Bindings: RecursiveBuilder);
383 return false; // Abort as soon as a match is found.
384 }
385 } else {
386 BoundNodesTreeBuilder RecursiveBuilder(*Builder);
387 if (Matcher->matches(DynNode: DynTypedNode::create(Node), Finder,
388 Builder: &RecursiveBuilder)) {
389 // After the first match the matcher succeeds.
390 Matches = true;
391 ResultBindings.addMatch(Bindings: RecursiveBuilder);
392 }
393 }
394 return true;
395 }
396
397 // Traverses the subtree rooted at 'Node'; returns true if the
398 // traversal should continue after this function returns.
399 template <typename T>
400 bool traverse(const T &Node) {
401 static_assert(IsBaseType<T>::value,
402 "traverse can only be instantiated with base type");
403 if (!match(Node))
404 return false;
405 return baseTraverse(Node);
406 }
407
408 const DynTypedMatcher *const Matcher;
409 ASTMatchFinder *const Finder;
410 BoundNodesTreeBuilder *const Builder;
411 BoundNodesTreeBuilder ResultBindings;
412 int CurrentDepth;
413 const int MaxDepth;
414 const bool IgnoreImplicitChildren;
415 const ASTMatchFinder::BindKind Bind;
416 bool Matches;
417};
418
419// Controls the outermost traversal of the AST and allows to match multiple
420// matchers.
421class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>,
422 public ASTMatchFinder {
423public:
424 MatchASTVisitor(const MatchFinder::MatchersByType *Matchers,
425 const MatchFinder::MatchFinderOptions &Options)
426 : Matchers(Matchers), Options(Options), ActiveASTContext(nullptr) {}
427
428 ~MatchASTVisitor() override {
429 if (Options.CheckProfiling) {
430 Options.CheckProfiling->Records = std::move(TimeByBucket);
431 }
432 }
433
434 void onStartOfTranslationUnit() {
435 const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
436 TimeBucketRegion Timer;
437 for (MatchCallback *MC : Matchers->AllCallbacks) {
438 if (EnableCheckProfiling)
439 Timer.setBucket(&TimeByBucket[MC->getID()]);
440 MC->onStartOfTranslationUnit();
441 }
442 }
443
444 void onEndOfTranslationUnit() {
445 const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
446 TimeBucketRegion Timer;
447 for (MatchCallback *MC : Matchers->AllCallbacks) {
448 if (EnableCheckProfiling)
449 Timer.setBucket(&TimeByBucket[MC->getID()]);
450 MC->onEndOfTranslationUnit();
451 }
452 }
453
454 void set_active_ast_context(ASTContext *NewActiveASTContext) {
455 ActiveASTContext = NewActiveASTContext;
456 }
457
458 // The following Visit*() and Traverse*() functions "override"
459 // methods in RecursiveASTVisitor.
460
461 bool VisitTypedefNameDecl(TypedefNameDecl *DeclNode) {
462 // When we see 'typedef A B', we add name 'B' to the set of names
463 // A's canonical type maps to. This is necessary for implementing
464 // isDerivedFrom(x) properly, where x can be the name of the base
465 // class or any of its aliases.
466 //
467 // In general, the is-alias-of (as defined by typedefs) relation
468 // is tree-shaped, as you can typedef a type more than once. For
469 // example,
470 //
471 // typedef A B;
472 // typedef A C;
473 // typedef C D;
474 // typedef C E;
475 //
476 // gives you
477 //
478 // A
479 // |- B
480 // `- C
481 // |- D
482 // `- E
483 //
484 // It is wrong to assume that the relation is a chain. A correct
485 // implementation of isDerivedFrom() needs to recognize that B and
486 // E are aliases, even though neither is a typedef of the other.
487 // Therefore, we cannot simply walk through one typedef chain to
488 // find out whether the type name matches.
489 const Type *TypeNode = DeclNode->getUnderlyingType().getTypePtr();
490 const Type *CanonicalType = // root of the typedef tree
491 ActiveASTContext->getCanonicalType(T: TypeNode);
492 TypeAliases[CanonicalType].insert(x: DeclNode);
493 return true;
494 }
495
496 bool VisitObjCCompatibleAliasDecl(ObjCCompatibleAliasDecl *CAD) {
497 const ObjCInterfaceDecl *InterfaceDecl = CAD->getClassInterface();
498 CompatibleAliases[InterfaceDecl].insert(Ptr: CAD);
499 return true;
500 }
501
502 bool TraverseDecl(Decl *DeclNode);
503 bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue = nullptr);
504 bool TraverseType(QualType TypeNode);
505 bool TraverseTypeLoc(TypeLoc TypeNode);
506 bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS);
507 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS);
508 bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit);
509 bool TraverseTemplateArgumentLoc(TemplateArgumentLoc TAL);
510 bool TraverseAttr(Attr *AttrNode);
511
512 bool dataTraverseNode(Stmt *S, DataRecursionQueue *Queue) {
513 if (auto *RF = dyn_cast<CXXForRangeStmt>(Val: S)) {
514 {
515 ASTNodeNotAsIsSourceScope RAII(this, true);
516 TraverseStmt(StmtNode: RF->getInit());
517 // Don't traverse under the loop variable
518 match(Node: *RF->getLoopVariable());
519 TraverseStmt(StmtNode: RF->getRangeInit());
520 }
521 {
522 ASTNodeNotSpelledInSourceScope RAII(this, true);
523 for (auto *SubStmt : RF->children()) {
524 if (SubStmt != RF->getBody())
525 TraverseStmt(StmtNode: SubStmt);
526 }
527 }
528 TraverseStmt(StmtNode: RF->getBody());
529 return true;
530 } else if (auto *RBO = dyn_cast<CXXRewrittenBinaryOperator>(Val: S)) {
531 {
532 ASTNodeNotAsIsSourceScope RAII(this, true);
533 TraverseStmt(StmtNode: const_cast<Expr *>(RBO->getLHS()));
534 TraverseStmt(StmtNode: const_cast<Expr *>(RBO->getRHS()));
535 }
536 {
537 ASTNodeNotSpelledInSourceScope RAII(this, true);
538 for (auto *SubStmt : RBO->children()) {
539 TraverseStmt(StmtNode: SubStmt);
540 }
541 }
542 return true;
543 } else if (auto *LE = dyn_cast<LambdaExpr>(Val: S)) {
544 for (auto I : llvm::zip(t: LE->captures(), u: LE->capture_inits())) {
545 auto C = std::get<0>(t&: I);
546 ASTNodeNotSpelledInSourceScope RAII(
547 this, TraversingASTNodeNotSpelledInSource || !C.isExplicit());
548 TraverseLambdaCapture(LE, C: &C, Init: std::get<1>(t&: I));
549 }
550
551 {
552 ASTNodeNotSpelledInSourceScope RAII(this, true);
553 TraverseDecl(DeclNode: LE->getLambdaClass());
554 }
555 {
556 ASTNodeNotAsIsSourceScope RAII(this, true);
557
558 // We need to poke around to find the bits that might be explicitly
559 // written.
560 TypeLoc TL = LE->getCallOperator()->getTypeSourceInfo()->getTypeLoc();
561 FunctionProtoTypeLoc Proto = TL.getAsAdjusted<FunctionProtoTypeLoc>();
562
563 if (auto *TPL = LE->getTemplateParameterList()) {
564 for (NamedDecl *D : *TPL) {
565 TraverseDecl(DeclNode: D);
566 }
567 if (Expr *RequiresClause = TPL->getRequiresClause()) {
568 TraverseStmt(StmtNode: RequiresClause);
569 }
570 }
571
572 if (LE->hasExplicitParameters()) {
573 // Visit parameters.
574 for (ParmVarDecl *Param : Proto.getParams())
575 TraverseDecl(DeclNode: Param);
576 }
577
578 const auto *T = Proto.getTypePtr();
579 for (const auto &E : T->exceptions())
580 TraverseType(TypeNode: E);
581
582 if (Expr *NE = T->getNoexceptExpr())
583 TraverseStmt(StmtNode: NE, Queue);
584
585 if (LE->hasExplicitResultType())
586 TraverseTypeLoc(TypeNode: Proto.getReturnLoc());
587 TraverseStmt(
588 StmtNode: const_cast<Expr *>(LE->getTrailingRequiresClause().ConstraintExpr));
589 }
590
591 TraverseStmt(StmtNode: LE->getBody());
592 return true;
593 }
594 return RecursiveASTVisitor<MatchASTVisitor>::dataTraverseNode(S, Queue);
595 }
596
597 // Matches children or descendants of 'Node' with 'BaseMatcher'.
598 bool memoizedMatchesRecursively(const DynTypedNode &Node, ASTContext &Ctx,
599 const DynTypedMatcher &Matcher,
600 BoundNodesTreeBuilder *Builder, int MaxDepth,
601 BindKind Bind) {
602 // For AST-nodes that don't have an identity, we can't memoize.
603 if (!Node.getMemoizationData() || !Builder->isComparable())
604 return matchesRecursively(Node, Matcher, Builder, MaxDepth, Bind);
605
606 MatchKey Key;
607 Key.MatcherID = Matcher.getID();
608 Key.Node = Node;
609 // Note that we key on the bindings *before* the match.
610 Key.BoundNodes = *Builder;
611 Key.Traversal = Ctx.getParentMapContext().getTraversalKind();
612 // Memoize result even doing a single-level match, it might be expensive.
613 Key.Type = MaxDepth == 1 ? MatchType::Child : MatchType::Descendants;
614 MemoizationMap::iterator I = ResultCache.find(x: Key);
615 if (I != ResultCache.end()) {
616 *Builder = I->second.Nodes;
617 return I->second.ResultOfMatch;
618 }
619
620 MemoizedMatchResult Result;
621 Result.Nodes = *Builder;
622 Result.ResultOfMatch =
623 matchesRecursively(Node, Matcher, Builder: &Result.Nodes, MaxDepth, Bind);
624
625 MemoizedMatchResult &CachedResult = ResultCache[Key];
626 CachedResult = std::move(Result);
627
628 *Builder = CachedResult.Nodes;
629 return CachedResult.ResultOfMatch;
630 }
631
632 // Matches children or descendants of 'Node' with 'BaseMatcher'.
633 bool matchesRecursively(const DynTypedNode &Node,
634 const DynTypedMatcher &Matcher,
635 BoundNodesTreeBuilder *Builder, int MaxDepth,
636 BindKind Bind) {
637 bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
638 TraversingASTChildrenNotSpelledInSource;
639
640 bool IgnoreImplicitChildren = false;
641
642 if (isTraversalIgnoringImplicitNodes()) {
643 IgnoreImplicitChildren = true;
644 }
645
646 ASTNodeNotSpelledInSourceScope RAII(this, ScopedTraversal);
647
648 MatchChildASTVisitor Visitor(&Matcher, this, Builder, MaxDepth,
649 IgnoreImplicitChildren, Bind);
650 return Visitor.findMatch(DynNode: Node);
651 }
652
653 bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
654 const Matcher<NamedDecl> &Base,
655 BoundNodesTreeBuilder *Builder,
656 bool Directly) override;
657
658private:
659 bool
660 classIsDerivedFromImpl(const CXXRecordDecl *Declaration,
661 const Matcher<NamedDecl> &Base,
662 BoundNodesTreeBuilder *Builder, bool Directly,
663 llvm::SmallPtrSetImpl<const CXXRecordDecl *> &Visited);
664
665public:
666 bool objcClassIsDerivedFrom(const ObjCInterfaceDecl *Declaration,
667 const Matcher<NamedDecl> &Base,
668 BoundNodesTreeBuilder *Builder,
669 bool Directly) override;
670
671public:
672 // Implements ASTMatchFinder::matchesChildOf.
673 bool matchesChildOf(const DynTypedNode &Node, ASTContext &Ctx,
674 const DynTypedMatcher &Matcher,
675 BoundNodesTreeBuilder *Builder, BindKind Bind) override {
676 if (ResultCache.size() > MaxMemoizationEntries)
677 ResultCache.clear();
678 return memoizedMatchesRecursively(Node, Ctx, Matcher, Builder, MaxDepth: 1, Bind);
679 }
680 // Implements ASTMatchFinder::matchesDescendantOf.
681 bool matchesDescendantOf(const DynTypedNode &Node, ASTContext &Ctx,
682 const DynTypedMatcher &Matcher,
683 BoundNodesTreeBuilder *Builder,
684 BindKind Bind) override {
685 if (ResultCache.size() > MaxMemoizationEntries)
686 ResultCache.clear();
687 return memoizedMatchesRecursively(Node, Ctx, Matcher, Builder, INT_MAX,
688 Bind);
689 }
690 // Implements ASTMatchFinder::matchesAncestorOf.
691 bool matchesAncestorOf(const DynTypedNode &Node, ASTContext &Ctx,
692 const DynTypedMatcher &Matcher,
693 BoundNodesTreeBuilder *Builder,
694 AncestorMatchMode MatchMode) override {
695 // Reset the cache outside of the recursive call to make sure we
696 // don't invalidate any iterators.
697 if (ResultCache.size() > MaxMemoizationEntries)
698 ResultCache.clear();
699 if (MatchMode == AncestorMatchMode::AMM_ParentOnly)
700 return matchesParentOf(Node, Matcher, Builder);
701 return matchesAnyAncestorOf(Node, Ctx, Matcher, Builder);
702 }
703
704 // Matches all registered matchers on the given node and calls the
705 // result callback for every node that matches.
706 void match(const DynTypedNode &Node) {
707 // FIXME: Improve this with a switch or a visitor pattern.
708 if (auto *N = Node.get<Decl>()) {
709 match(Node: *N);
710 } else if (auto *N = Node.get<Stmt>()) {
711 match(Node: *N);
712 } else if (auto *N = Node.get<Type>()) {
713 match(Node: *N);
714 } else if (auto *N = Node.get<QualType>()) {
715 match(Node: *N);
716 } else if (auto *N = Node.get<NestedNameSpecifier>()) {
717 match(Node: *N);
718 } else if (auto *N = Node.get<NestedNameSpecifierLoc>()) {
719 match(Node: *N);
720 } else if (auto *N = Node.get<TypeLoc>()) {
721 match(Node: *N);
722 } else if (auto *N = Node.get<CXXCtorInitializer>()) {
723 match(Node: *N);
724 } else if (auto *N = Node.get<TemplateArgumentLoc>()) {
725 match(Node: *N);
726 } else if (auto *N = Node.get<Attr>()) {
727 match(Node: *N);
728 }
729 }
730
731 template <typename T> void match(const T &Node) {
732 matchDispatch(&Node);
733 }
734
735 // Implements ASTMatchFinder::getASTContext.
736 ASTContext &getASTContext() const override { return *ActiveASTContext; }
737
738 bool shouldVisitTemplateInstantiations() const { return true; }
739 bool shouldVisitImplicitCode() const { return true; }
740
741 // We visit the lambda body explicitly, so instruct the RAV
742 // to not visit it on our behalf too.
743 bool shouldVisitLambdaBody() const { return false; }
744
745 bool IsMatchingInASTNodeNotSpelledInSource() const override {
746 return TraversingASTNodeNotSpelledInSource;
747 }
748 bool isMatchingChildrenNotSpelledInSource() const override {
749 return TraversingASTChildrenNotSpelledInSource;
750 }
751 void setMatchingChildrenNotSpelledInSource(bool Set) override {
752 TraversingASTChildrenNotSpelledInSource = Set;
753 }
754
755 bool IsMatchingInASTNodeNotAsIs() const override {
756 return TraversingASTNodeNotAsIs;
757 }
758
759 bool TraverseTemplateInstantiations(ClassTemplateDecl *D) {
760 ASTNodeNotSpelledInSourceScope RAII(this, true);
761 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
762 D);
763 }
764
765 bool TraverseTemplateInstantiations(VarTemplateDecl *D) {
766 ASTNodeNotSpelledInSourceScope RAII(this, true);
767 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
768 D);
769 }
770
771 bool TraverseTemplateInstantiations(FunctionTemplateDecl *D) {
772 ASTNodeNotSpelledInSourceScope RAII(this, true);
773 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
774 D);
775 }
776
777private:
778 bool TraversingASTNodeNotSpelledInSource = false;
779 bool TraversingASTNodeNotAsIs = false;
780 bool TraversingASTChildrenNotSpelledInSource = false;
781
782 class CurMatchData {
783// We don't have enough free low bits in 32bit builds to discriminate 8 pointer
784// types in PointerUnion. so split the union in 2 using a free bit from the
785// callback pointer.
786#define CMD_TYPES_0 \
787 const QualType *, const TypeLoc *, const NestedNameSpecifier *, \
788 const NestedNameSpecifierLoc *
789#define CMD_TYPES_1 \
790 const CXXCtorInitializer *, const TemplateArgumentLoc *, const Attr *, \
791 const DynTypedNode *
792
793#define IMPL(Index) \
794 template <typename NodeType> \
795 std::enable_if_t< \
796 llvm::is_one_of<const NodeType *, CMD_TYPES_##Index>::value> \
797 SetCallbackAndRawNode(const MatchCallback *CB, const NodeType &N) { \
798 assertEmpty(); \
799 Callback.setPointerAndInt(CB, Index); \
800 Node##Index = &N; \
801 } \
802 \
803 template <typename T> \
804 std::enable_if_t<llvm::is_one_of<const T *, CMD_TYPES_##Index>::value, \
805 const T *> \
806 getNode() const { \
807 assertHoldsState(); \
808 return Callback.getInt() == (Index) ? Node##Index.dyn_cast<const T *>() \
809 : nullptr; \
810 }
811
812 public:
813 CurMatchData() : Node0(nullptr) {}
814
815 IMPL(0)
816 IMPL(1)
817
818 const MatchCallback *getCallback() const { return Callback.getPointer(); }
819
820 void SetBoundNodes(const BoundNodes &BN) {
821 assertHoldsState();
822 BNodes = &BN;
823 }
824
825 void clearBoundNodes() {
826 assertHoldsState();
827 BNodes = nullptr;
828 }
829
830 const BoundNodes *getBoundNodes() const {
831 assertHoldsState();
832 return BNodes;
833 }
834
835 void reset() {
836 assertHoldsState();
837 Callback.setPointerAndInt(PtrVal: nullptr, IntVal: 0);
838 Node0 = nullptr;
839 }
840
841 private:
842 void assertHoldsState() const {
843 assert(Callback.getPointer() != nullptr && !Node0.isNull());
844 }
845
846 void assertEmpty() const {
847 assert(Callback.getPointer() == nullptr && Node0.isNull() &&
848 BNodes == nullptr);
849 }
850
851 llvm::PointerIntPair<const MatchCallback *, 1> Callback;
852 union {
853 llvm::PointerUnion<CMD_TYPES_0> Node0;
854 llvm::PointerUnion<CMD_TYPES_1> Node1;
855 };
856 const BoundNodes *BNodes = nullptr;
857
858#undef CMD_TYPES_0
859#undef CMD_TYPES_1
860#undef IMPL
861 } CurMatchState;
862
863 struct CurMatchRAII {
864 template <typename NodeType>
865 CurMatchRAII(MatchASTVisitor &MV, const MatchCallback *CB,
866 const NodeType &NT)
867 : MV(MV) {
868 MV.CurMatchState.SetCallbackAndRawNode(CB, NT);
869 }
870
871 ~CurMatchRAII() { MV.CurMatchState.reset(); }
872
873 private:
874 MatchASTVisitor &MV;
875 };
876
877public:
878 class TraceReporter : llvm::PrettyStackTraceEntry {
879 static void dumpNode(const ASTContext &Ctx, const DynTypedNode &Node,
880 raw_ostream &OS) {
881 if (const auto *D = Node.get<Decl>()) {
882 OS << D->getDeclKindName() << "Decl ";
883 if (const auto *ND = dyn_cast<NamedDecl>(Val: D)) {
884 ND->printQualifiedName(OS);
885 OS << " : ";
886 } else
887 OS << ": ";
888 D->getSourceRange().print(OS, SM: Ctx.getSourceManager());
889 } else if (const auto *S = Node.get<Stmt>()) {
890 OS << S->getStmtClassName() << " : ";
891 S->getSourceRange().print(OS, SM: Ctx.getSourceManager());
892 } else if (const auto *T = Node.get<Type>()) {
893 OS << T->getTypeClassName() << "Type : ";
894 QualType(T, 0).print(OS, Policy: Ctx.getPrintingPolicy());
895 } else if (const auto *QT = Node.get<QualType>()) {
896 OS << "QualType : ";
897 QT->print(OS, Policy: Ctx.getPrintingPolicy());
898 } else {
899 OS << Node.getNodeKind().asStringRef() << " : ";
900 Node.getSourceRange().print(OS, SM: Ctx.getSourceManager());
901 }
902 }
903
904 static void dumpNodeFromState(const ASTContext &Ctx,
905 const CurMatchData &State, raw_ostream &OS) {
906 if (const DynTypedNode *MatchNode = State.getNode<DynTypedNode>()) {
907 dumpNode(Ctx, Node: *MatchNode, OS);
908 } else if (const auto *QT = State.getNode<QualType>()) {
909 dumpNode(Ctx, Node: DynTypedNode::create(Node: *QT), OS);
910 } else if (const auto *TL = State.getNode<TypeLoc>()) {
911 dumpNode(Ctx, Node: DynTypedNode::create(Node: *TL), OS);
912 } else if (const auto *NNS = State.getNode<NestedNameSpecifier>()) {
913 dumpNode(Ctx, Node: DynTypedNode::create(Node: *NNS), OS);
914 } else if (const auto *NNSL = State.getNode<NestedNameSpecifierLoc>()) {
915 dumpNode(Ctx, Node: DynTypedNode::create(Node: *NNSL), OS);
916 } else if (const auto *CtorInit = State.getNode<CXXCtorInitializer>()) {
917 dumpNode(Ctx, Node: DynTypedNode::create(Node: *CtorInit), OS);
918 } else if (const auto *TAL = State.getNode<TemplateArgumentLoc>()) {
919 dumpNode(Ctx, Node: DynTypedNode::create(Node: *TAL), OS);
920 } else if (const auto *At = State.getNode<Attr>()) {
921 dumpNode(Ctx, Node: DynTypedNode::create(Node: *At), OS);
922 }
923 }
924
925 public:
926 TraceReporter(const MatchASTVisitor &MV) : MV(MV) {}
927 void print(raw_ostream &OS) const override {
928 const CurMatchData &State = MV.CurMatchState;
929 const MatchCallback *CB = State.getCallback();
930 if (!CB) {
931 OS << "ASTMatcher: Not currently matching\n";
932 return;
933 }
934
935 assert(MV.ActiveASTContext &&
936 "ActiveASTContext should be set if there is a matched callback");
937
938 ASTContext &Ctx = MV.getASTContext();
939
940 if (const BoundNodes *Nodes = State.getBoundNodes()) {
941 OS << "ASTMatcher: Processing '" << CB->getID() << "' against:\n\t";
942 dumpNodeFromState(Ctx, State, OS);
943 const BoundNodes::IDToNodeMap &Map = Nodes->getMap();
944 if (Map.empty()) {
945 OS << "\nNo bound nodes\n";
946 return;
947 }
948 OS << "\n--- Bound Nodes Begin ---\n";
949 for (const auto &Item : Map) {
950 OS << " " << Item.first << " - { ";
951 dumpNode(Ctx, Node: Item.second, OS);
952 OS << " }\n";
953 }
954 OS << "--- Bound Nodes End ---\n";
955 } else {
956 OS << "ASTMatcher: Matching '" << CB->getID() << "' against:\n\t";
957 dumpNodeFromState(Ctx, State, OS);
958 OS << '\n';
959 }
960 }
961
962 private:
963 const MatchASTVisitor &MV;
964 };
965
966private:
967 struct ASTNodeNotSpelledInSourceScope {
968 ASTNodeNotSpelledInSourceScope(MatchASTVisitor *V, bool B)
969 : MV(V), MB(V->TraversingASTNodeNotSpelledInSource) {
970 V->TraversingASTNodeNotSpelledInSource = B;
971 }
972 ~ASTNodeNotSpelledInSourceScope() {
973 MV->TraversingASTNodeNotSpelledInSource = MB;
974 }
975
976 private:
977 MatchASTVisitor *MV;
978 bool MB;
979 };
980
981 struct ASTNodeNotAsIsSourceScope {
982 ASTNodeNotAsIsSourceScope(MatchASTVisitor *V, bool B)
983 : MV(V), MB(V->TraversingASTNodeNotAsIs) {
984 V->TraversingASTNodeNotAsIs = B;
985 }
986 ~ASTNodeNotAsIsSourceScope() { MV->TraversingASTNodeNotAsIs = MB; }
987
988 private:
989 MatchASTVisitor *MV;
990 bool MB;
991 };
992
993 class TimeBucketRegion {
994 public:
995 TimeBucketRegion() = default;
996 ~TimeBucketRegion() { setBucket(nullptr); }
997
998 /// Start timing for \p NewBucket.
999 ///
1000 /// If there was a bucket already set, it will finish the timing for that
1001 /// other bucket.
1002 /// \p NewBucket will be timed until the next call to \c setBucket() or
1003 /// until the \c TimeBucketRegion is destroyed.
1004 /// If \p NewBucket is the same as the currently timed bucket, this call
1005 /// does nothing.
1006 void setBucket(llvm::TimeRecord *NewBucket) {
1007 if (Bucket != NewBucket) {
1008 auto Now = llvm::TimeRecord::getCurrentTime(Start: true);
1009 if (Bucket)
1010 *Bucket += Now;
1011 if (NewBucket)
1012 *NewBucket -= Now;
1013 Bucket = NewBucket;
1014 }
1015 }
1016
1017 private:
1018 llvm::TimeRecord *Bucket = nullptr;
1019 };
1020
1021 /// Runs all the \p Matchers on \p Node.
1022 ///
1023 /// Used by \c matchDispatch() below.
1024 template <typename T, typename MC>
1025 void matchWithoutFilter(const T &Node, const MC &Matchers) {
1026 const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
1027 TimeBucketRegion Timer;
1028 for (const auto &MP : Matchers) {
1029 if (EnableCheckProfiling)
1030 Timer.setBucket(&TimeByBucket[MP.second->getID()]);
1031 BoundNodesTreeBuilder Builder;
1032 CurMatchRAII RAII(*this, MP.second, Node);
1033 if (MP.first.matches(Node, this, &Builder)) {
1034 MatchVisitor Visitor(*this, ActiveASTContext, MP.second);
1035 Builder.visitMatches(ResultVisitor: &Visitor);
1036 }
1037 }
1038 }
1039
1040 void matchWithFilter(const DynTypedNode &DynNode) {
1041 auto Kind = DynNode.getNodeKind();
1042 auto it = MatcherFiltersMap.find(Val: Kind);
1043 const auto &Filter =
1044 it != MatcherFiltersMap.end() ? it->second : getFilterForKind(Kind);
1045
1046 if (Filter.empty())
1047 return;
1048
1049 const bool EnableCheckProfiling = Options.CheckProfiling.has_value();
1050 TimeBucketRegion Timer;
1051 auto &Matchers = this->Matchers->DeclOrStmt;
1052 for (unsigned short I : Filter) {
1053 auto &MP = Matchers[I];
1054 if (EnableCheckProfiling)
1055 Timer.setBucket(&TimeByBucket[MP.second->getID()]);
1056 BoundNodesTreeBuilder Builder;
1057
1058 {
1059 TraversalKindScope RAII(getASTContext(), MP.first.getTraversalKind());
1060 if (getASTContext().getParentMapContext().traverseIgnored(N: DynNode) !=
1061 DynNode)
1062 continue;
1063 }
1064
1065 CurMatchRAII RAII(*this, MP.second, DynNode);
1066 if (MP.first.matches(DynNode, Finder: this, Builder: &Builder)) {
1067 MatchVisitor Visitor(*this, ActiveASTContext, MP.second);
1068 Builder.visitMatches(ResultVisitor: &Visitor);
1069 }
1070 }
1071 }
1072
1073 const std::vector<unsigned short> &getFilterForKind(ASTNodeKind Kind) {
1074 auto &Filter = MatcherFiltersMap[Kind];
1075 auto &Matchers = this->Matchers->DeclOrStmt;
1076 assert((Matchers.size() < USHRT_MAX) && "Too many matchers.");
1077 for (unsigned I = 0, E = Matchers.size(); I != E; ++I) {
1078 if (Matchers[I].first.canMatchNodesOfKind(Kind)) {
1079 Filter.push_back(x: I);
1080 }
1081 }
1082 return Filter;
1083 }
1084
1085 /// @{
1086 /// Overloads to pair the different node types to their matchers.
1087 void matchDispatch(const Decl *Node) {
1088 return matchWithFilter(DynNode: DynTypedNode::create(Node: *Node));
1089 }
1090 void matchDispatch(const Stmt *Node) {
1091 return matchWithFilter(DynNode: DynTypedNode::create(Node: *Node));
1092 }
1093
1094 void matchDispatch(const Type *Node) {
1095 matchWithoutFilter(Node: QualType(Node, 0), Matchers: Matchers->Type);
1096 }
1097 void matchDispatch(const TypeLoc *Node) {
1098 matchWithoutFilter(Node: *Node, Matchers: Matchers->TypeLoc);
1099 }
1100 void matchDispatch(const QualType *Node) {
1101 matchWithoutFilter(Node: *Node, Matchers: Matchers->Type);
1102 }
1103 void matchDispatch(const NestedNameSpecifier *Node) {
1104 matchWithoutFilter(Node: *Node, Matchers: Matchers->NestedNameSpecifier);
1105 }
1106 void matchDispatch(const NestedNameSpecifierLoc *Node) {
1107 matchWithoutFilter(Node: *Node, Matchers: Matchers->NestedNameSpecifierLoc);
1108 }
1109 void matchDispatch(const CXXCtorInitializer *Node) {
1110 matchWithoutFilter(Node: *Node, Matchers: Matchers->CtorInit);
1111 }
1112 void matchDispatch(const TemplateArgumentLoc *Node) {
1113 matchWithoutFilter(Node: *Node, Matchers: Matchers->TemplateArgumentLoc);
1114 }
1115 void matchDispatch(const Attr *Node) {
1116 matchWithoutFilter(Node: *Node, Matchers: Matchers->Attr);
1117 }
1118 void matchDispatch(const void *) { /* Do nothing. */ }
1119 /// @}
1120
1121 // Returns whether a direct parent of \p Node matches \p Matcher.
1122 // Unlike matchesAnyAncestorOf there's no memoization: it doesn't save much.
1123 bool matchesParentOf(const DynTypedNode &Node, const DynTypedMatcher &Matcher,
1124 BoundNodesTreeBuilder *Builder) {
1125 for (const auto &Parent : ActiveASTContext->getParents(Node)) {
1126 BoundNodesTreeBuilder BuilderCopy = *Builder;
1127 if (Matcher.matches(DynNode: Parent, Finder: this, Builder: &BuilderCopy)) {
1128 *Builder = std::move(BuilderCopy);
1129 return true;
1130 }
1131 }
1132 return false;
1133 }
1134
1135 // Returns whether an ancestor of \p Node matches \p Matcher.
1136 //
1137 // The order of matching (which can lead to different nodes being bound in
1138 // case there are multiple matches) is breadth first search.
1139 //
1140 // To allow memoization in the very common case of having deeply nested
1141 // expressions inside a template function, we first walk up the AST, memoizing
1142 // the result of the match along the way, as long as there is only a single
1143 // parent.
1144 //
1145 // Once there are multiple parents, the breadth first search order does not
1146 // allow simple memoization on the ancestors. Thus, we only memoize as long
1147 // as there is a single parent.
1148 //
1149 // We avoid a recursive implementation to prevent excessive stack use on
1150 // very deep ASTs (similarly to RecursiveASTVisitor's data recursion).
1151 bool matchesAnyAncestorOf(DynTypedNode Node, ASTContext &Ctx,
1152 const DynTypedMatcher &Matcher,
1153 BoundNodesTreeBuilder *Builder) {
1154
1155 // Memoization keys that can be updated with the result.
1156 // These are the memoizable nodes in the chain of unique parents, which
1157 // terminates when a node has multiple parents, or matches, or is the root.
1158 std::vector<MatchKey> Keys;
1159 // When returning, update the memoization cache.
1160 auto Finish = [&](bool Matched) {
1161 for (const auto &Key : Keys) {
1162 MemoizedMatchResult &CachedResult = ResultCache[Key];
1163 CachedResult.ResultOfMatch = Matched;
1164 CachedResult.Nodes = *Builder;
1165 }
1166 return Matched;
1167 };
1168
1169 // Loop while there's a single parent and we want to attempt memoization.
1170 DynTypedNodeList Parents{ArrayRef<DynTypedNode>()}; // after loop: size != 1
1171 for (;;) {
1172 // A cache key only makes sense if memoization is possible.
1173 if (Builder->isComparable()) {
1174 Keys.emplace_back();
1175 Keys.back().MatcherID = Matcher.getID();
1176 Keys.back().Node = Node;
1177 Keys.back().BoundNodes = *Builder;
1178 Keys.back().Traversal = Ctx.getParentMapContext().getTraversalKind();
1179 Keys.back().Type = MatchType::Ancestors;
1180
1181 // Check the cache.
1182 MemoizationMap::iterator I = ResultCache.find(x: Keys.back());
1183 if (I != ResultCache.end()) {
1184 Keys.pop_back(); // Don't populate the cache for the matching node!
1185 *Builder = I->second.Nodes;
1186 return Finish(I->second.ResultOfMatch);
1187 }
1188 }
1189
1190 Parents = ActiveASTContext->getParents(Node);
1191 // Either no parents or multiple parents: leave chain+memoize mode and
1192 // enter bfs+forgetful mode.
1193 if (Parents.size() != 1)
1194 break;
1195
1196 // Check the next parent.
1197 Node = *Parents.begin();
1198 BoundNodesTreeBuilder BuilderCopy = *Builder;
1199 if (Matcher.matches(DynNode: Node, Finder: this, Builder: &BuilderCopy)) {
1200 *Builder = std::move(BuilderCopy);
1201 return Finish(true);
1202 }
1203 }
1204 // We reached the end of the chain.
1205
1206 if (Parents.empty()) {
1207 // Nodes may have no parents if:
1208 // a) the node is the TranslationUnitDecl
1209 // b) we have a limited traversal scope that excludes the parent edges
1210 // c) there is a bug in the AST, and the node is not reachable
1211 // Usually the traversal scope is the whole AST, which precludes b.
1212 // Bugs are common enough that it's worthwhile asserting when we can.
1213#ifndef NDEBUG
1214 if (!Node.get<TranslationUnitDecl>() &&
1215 /* Traversal scope is full AST if any of the bounds are the TU */
1216 llvm::any_of(ActiveASTContext->getTraversalScope(), [](Decl *D) {
1217 return D->getKind() == Decl::TranslationUnit;
1218 })) {
1219 llvm::errs() << "Tried to match orphan node:\n";
1220 Node.dump(llvm::errs(), *ActiveASTContext);
1221 llvm_unreachable("Parent map should be complete!");
1222 }
1223#endif
1224 } else {
1225 assert(Parents.size() > 1);
1226 // BFS starting from the parents not yet considered.
1227 // Memoization of newly visited nodes is not possible (but we still update
1228 // results for the elements in the chain we found above).
1229 std::deque<DynTypedNode> Queue(Parents.begin(), Parents.end());
1230 llvm::DenseSet<const void *> Visited;
1231 while (!Queue.empty()) {
1232 BoundNodesTreeBuilder BuilderCopy = *Builder;
1233 if (Matcher.matches(DynNode: Queue.front(), Finder: this, Builder: &BuilderCopy)) {
1234 *Builder = std::move(BuilderCopy);
1235 return Finish(true);
1236 }
1237 for (const auto &Parent : ActiveASTContext->getParents(Node: Queue.front())) {
1238 // Make sure we do not visit the same node twice.
1239 // Otherwise, we'll visit the common ancestors as often as there
1240 // are splits on the way down.
1241 if (Visited.insert(V: Parent.getMemoizationData()).second)
1242 Queue.push_back(x: Parent);
1243 }
1244 Queue.pop_front();
1245 }
1246 }
1247 return Finish(false);
1248 }
1249
1250 // Implements a BoundNodesTree::Visitor that calls a MatchCallback with
1251 // the aggregated bound nodes for each match.
1252 class MatchVisitor : public BoundNodesTreeBuilder::Visitor {
1253 struct CurBoundScope {
1254 CurBoundScope(MatchASTVisitor::CurMatchData &State, const BoundNodes &BN)
1255 : State(State) {
1256 State.SetBoundNodes(BN);
1257 }
1258
1259 ~CurBoundScope() { State.clearBoundNodes(); }
1260
1261 private:
1262 MatchASTVisitor::CurMatchData &State;
1263 };
1264
1265 public:
1266 MatchVisitor(MatchASTVisitor &MV, ASTContext *Context,
1267 MatchFinder::MatchCallback *Callback)
1268 : State(MV.CurMatchState), Context(Context), Callback(Callback) {}
1269
1270 void visitMatch(const BoundNodes& BoundNodesView) override {
1271 TraversalKindScope RAII(*Context, Callback->getCheckTraversalKind());
1272 CurBoundScope RAII2(State, BoundNodesView);
1273 Callback->run(Result: MatchFinder::MatchResult(BoundNodesView, Context));
1274 }
1275
1276 private:
1277 MatchASTVisitor::CurMatchData &State;
1278 ASTContext* Context;
1279 MatchFinder::MatchCallback* Callback;
1280 };
1281
1282 // Returns true if 'TypeNode' has an alias that matches the given matcher.
1283 bool typeHasMatchingAlias(const Type *TypeNode,
1284 const Matcher<NamedDecl> &Matcher,
1285 BoundNodesTreeBuilder *Builder) {
1286 const Type *const CanonicalType =
1287 ActiveASTContext->getCanonicalType(T: TypeNode);
1288 auto Aliases = TypeAliases.find(Val: CanonicalType);
1289 if (Aliases == TypeAliases.end())
1290 return false;
1291
1292 if (const auto *ElaboratedTypeNode =
1293 llvm::dyn_cast<ElaboratedType>(Val: TypeNode)) {
1294 if (ElaboratedTypeNode->isSugared() && Aliases->second.size() > 1) {
1295 const auto &DesugaredTypeName =
1296 ElaboratedTypeNode->desugar().getAsString();
1297
1298 for (const TypedefNameDecl *Alias : Aliases->second) {
1299 if (Alias->getName() != DesugaredTypeName) {
1300 continue;
1301 }
1302
1303 BoundNodesTreeBuilder Result(*Builder);
1304 if (Matcher.matches(Node: *Alias, Finder: this, Builder: &Result)) {
1305 *Builder = std::move(Result);
1306 return true;
1307 }
1308 }
1309 }
1310 }
1311
1312 for (const TypedefNameDecl *Alias : Aliases->second) {
1313 BoundNodesTreeBuilder Result(*Builder);
1314 if (Matcher.matches(Node: *Alias, Finder: this, Builder: &Result)) {
1315 *Builder = std::move(Result);
1316 return true;
1317 }
1318 }
1319 return false;
1320 }
1321
1322 bool
1323 objcClassHasMatchingCompatibilityAlias(const ObjCInterfaceDecl *InterfaceDecl,
1324 const Matcher<NamedDecl> &Matcher,
1325 BoundNodesTreeBuilder *Builder) {
1326 auto Aliases = CompatibleAliases.find(Val: InterfaceDecl);
1327 if (Aliases == CompatibleAliases.end())
1328 return false;
1329 for (const ObjCCompatibleAliasDecl *Alias : Aliases->second) {
1330 BoundNodesTreeBuilder Result(*Builder);
1331 if (Matcher.matches(Node: *Alias, Finder: this, Builder: &Result)) {
1332 *Builder = std::move(Result);
1333 return true;
1334 }
1335 }
1336 return false;
1337 }
1338
1339 /// Bucket to record map.
1340 ///
1341 /// Used to get the appropriate bucket for each matcher.
1342 llvm::StringMap<llvm::TimeRecord> TimeByBucket;
1343
1344 const MatchFinder::MatchersByType *Matchers;
1345
1346 /// Filtered list of matcher indices for each matcher kind.
1347 ///
1348 /// \c Decl and \c Stmt toplevel matchers usually apply to a specific node
1349 /// kind (and derived kinds) so it is a waste to try every matcher on every
1350 /// node.
1351 /// We precalculate a list of matchers that pass the toplevel restrict check.
1352 llvm::DenseMap<ASTNodeKind, std::vector<unsigned short>> MatcherFiltersMap;
1353
1354 const MatchFinder::MatchFinderOptions &Options;
1355 ASTContext *ActiveASTContext;
1356
1357 // Maps a canonical type to its TypedefDecls.
1358 llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases;
1359
1360 // Maps an Objective-C interface to its ObjCCompatibleAliasDecls.
1361 llvm::DenseMap<const ObjCInterfaceDecl *,
1362 llvm::SmallPtrSet<const ObjCCompatibleAliasDecl *, 2>>
1363 CompatibleAliases;
1364
1365 // Maps (matcher, node) -> the match result for memoization.
1366 typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap;
1367 MemoizationMap ResultCache;
1368};
1369
1370static CXXRecordDecl *
1371getAsCXXRecordDeclOrPrimaryTemplate(const Type *TypeNode) {
1372 if (auto *RD = TypeNode->getAsCXXRecordDecl())
1373 return RD;
1374
1375 // Find the innermost TemplateSpecializationType that isn't an alias template.
1376 auto *TemplateType = TypeNode->getAs<TemplateSpecializationType>();
1377 while (TemplateType && TemplateType->isTypeAlias())
1378 TemplateType =
1379 TemplateType->getAliasedType()->getAs<TemplateSpecializationType>();
1380
1381 // If this is the name of a (dependent) template specialization, use the
1382 // definition of the template, even though it might be specialized later.
1383 if (TemplateType)
1384 if (auto *ClassTemplate = dyn_cast_or_null<ClassTemplateDecl>(
1385 Val: TemplateType->getTemplateName().getAsTemplateDecl()))
1386 return ClassTemplate->getTemplatedDecl();
1387
1388 return nullptr;
1389}
1390
1391// Returns true if the given C++ class is directly or indirectly derived
1392// from a base type with the given name. A class is not considered to be
1393// derived from itself.
1394bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,
1395 const Matcher<NamedDecl> &Base,
1396 BoundNodesTreeBuilder *Builder,
1397 bool Directly) {
1398 llvm::SmallPtrSet<const CXXRecordDecl *, 8> Visited;
1399 return classIsDerivedFromImpl(Declaration, Base, Builder, Directly, Visited);
1400}
1401
1402bool MatchASTVisitor::classIsDerivedFromImpl(
1403 const CXXRecordDecl *Declaration, const Matcher<NamedDecl> &Base,
1404 BoundNodesTreeBuilder *Builder, bool Directly,
1405 llvm::SmallPtrSetImpl<const CXXRecordDecl *> &Visited) {
1406 if (!Declaration->hasDefinition())
1407 return false;
1408 if (!Visited.insert(Ptr: Declaration).second)
1409 return false;
1410 for (const auto &It : Declaration->bases()) {
1411 const Type *TypeNode = It.getType().getTypePtr();
1412
1413 if (typeHasMatchingAlias(TypeNode, Matcher: Base, Builder))
1414 return true;
1415
1416 // FIXME: Going to the primary template here isn't really correct, but
1417 // unfortunately we accept a Decl matcher for the base class not a Type
1418 // matcher, so it's the best thing we can do with our current interface.
1419 CXXRecordDecl *ClassDecl = getAsCXXRecordDeclOrPrimaryTemplate(TypeNode);
1420 if (!ClassDecl)
1421 continue;
1422 if (ClassDecl == Declaration) {
1423 // This can happen for recursive template definitions.
1424 continue;
1425 }
1426 BoundNodesTreeBuilder Result(*Builder);
1427 if (Base.matches(Node: *ClassDecl, Finder: this, Builder: &Result)) {
1428 *Builder = std::move(Result);
1429 return true;
1430 }
1431 if (!Directly &&
1432 classIsDerivedFromImpl(Declaration: ClassDecl, Base, Builder, Directly, Visited))
1433 return true;
1434 }
1435 return false;
1436}
1437
1438// Returns true if the given Objective-C class is directly or indirectly
1439// derived from a matching base class. A class is not considered to be derived
1440// from itself.
1441bool MatchASTVisitor::objcClassIsDerivedFrom(
1442 const ObjCInterfaceDecl *Declaration, const Matcher<NamedDecl> &Base,
1443 BoundNodesTreeBuilder *Builder, bool Directly) {
1444 // Check if any of the superclasses of the class match.
1445 for (const ObjCInterfaceDecl *ClassDecl = Declaration->getSuperClass();
1446 ClassDecl != nullptr; ClassDecl = ClassDecl->getSuperClass()) {
1447 // Check if there are any matching compatibility aliases.
1448 if (objcClassHasMatchingCompatibilityAlias(InterfaceDecl: ClassDecl, Matcher: Base, Builder))
1449 return true;
1450
1451 // Check if there are any matching type aliases.
1452 const Type *TypeNode = ClassDecl->getTypeForDecl();
1453 if (typeHasMatchingAlias(TypeNode, Matcher: Base, Builder))
1454 return true;
1455
1456 if (Base.matches(Node: *ClassDecl, Finder: this, Builder))
1457 return true;
1458
1459 // Not `return false` as a temporary workaround for PR43879.
1460 if (Directly)
1461 break;
1462 }
1463
1464 return false;
1465}
1466
1467bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {
1468 if (!DeclNode) {
1469 return true;
1470 }
1471
1472 bool ScopedTraversal =
1473 TraversingASTNodeNotSpelledInSource || DeclNode->isImplicit();
1474 bool ScopedChildren = TraversingASTChildrenNotSpelledInSource;
1475
1476 if (const auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(Val: DeclNode)) {
1477 auto SK = CTSD->getSpecializationKind();
1478 if (SK == TSK_ExplicitInstantiationDeclaration ||
1479 SK == TSK_ExplicitInstantiationDefinition)
1480 ScopedChildren = true;
1481 } else if (const auto *FD = dyn_cast<FunctionDecl>(Val: DeclNode)) {
1482 if (FD->isDefaulted())
1483 ScopedChildren = true;
1484 if (FD->isTemplateInstantiation())
1485 ScopedTraversal = true;
1486 } else if (isa<BindingDecl>(Val: DeclNode)) {
1487 ScopedChildren = true;
1488 }
1489
1490 ASTNodeNotSpelledInSourceScope RAII1(this, ScopedTraversal);
1491 ASTChildrenNotSpelledInSourceScope RAII2(this, ScopedChildren);
1492
1493 match(Node: *DeclNode);
1494 return RecursiveASTVisitor<MatchASTVisitor>::TraverseDecl(D: DeclNode);
1495}
1496
1497bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue) {
1498 if (!StmtNode) {
1499 return true;
1500 }
1501 bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
1502 TraversingASTChildrenNotSpelledInSource;
1503
1504 ASTNodeNotSpelledInSourceScope RAII(this, ScopedTraversal);
1505 match(Node: *StmtNode);
1506 return RecursiveASTVisitor<MatchASTVisitor>::TraverseStmt(S: StmtNode, Queue);
1507}
1508
1509bool MatchASTVisitor::TraverseType(QualType TypeNode) {
1510 match(Node: TypeNode);
1511 return RecursiveASTVisitor<MatchASTVisitor>::TraverseType(T: TypeNode);
1512}
1513
1514bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode) {
1515 // The RecursiveASTVisitor only visits types if they're not within TypeLocs.
1516 // We still want to find those types via matchers, so we match them here. Note
1517 // that the TypeLocs are structurally a shadow-hierarchy to the expressed
1518 // type, so we visit all involved parts of a compound type when matching on
1519 // each TypeLoc.
1520 match(Node: TypeLocNode);
1521 match(Node: TypeLocNode.getType());
1522 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTypeLoc(TL: TypeLocNode);
1523}
1524
1525bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
1526 match(Node: *NNS);
1527 return RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifier(NNS);
1528}
1529
1530bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
1531 NestedNameSpecifierLoc NNS) {
1532 if (!NNS)
1533 return true;
1534
1535 match(Node: NNS);
1536
1537 // We only match the nested name specifier here (as opposed to traversing it)
1538 // because the traversal is already done in the parallel "Loc"-hierarchy.
1539 if (NNS.hasQualifier())
1540 match(Node: *NNS.getNestedNameSpecifier());
1541 return
1542 RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifierLoc(NNS);
1543}
1544
1545bool MatchASTVisitor::TraverseConstructorInitializer(
1546 CXXCtorInitializer *CtorInit) {
1547 if (!CtorInit)
1548 return true;
1549
1550 bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
1551 TraversingASTChildrenNotSpelledInSource;
1552
1553 if (!CtorInit->isWritten())
1554 ScopedTraversal = true;
1555
1556 ASTNodeNotSpelledInSourceScope RAII1(this, ScopedTraversal);
1557
1558 match(Node: *CtorInit);
1559
1560 return RecursiveASTVisitor<MatchASTVisitor>::TraverseConstructorInitializer(
1561 Init: CtorInit);
1562}
1563
1564bool MatchASTVisitor::TraverseTemplateArgumentLoc(TemplateArgumentLoc Loc) {
1565 match(Node: Loc);
1566 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateArgumentLoc(ArgLoc: Loc);
1567}
1568
1569bool MatchASTVisitor::TraverseAttr(Attr *AttrNode) {
1570 match(Node: *AttrNode);
1571 return RecursiveASTVisitor<MatchASTVisitor>::TraverseAttr(A: AttrNode);
1572}
1573
1574class MatchASTConsumer : public ASTConsumer {
1575public:
1576 MatchASTConsumer(MatchFinder *Finder,
1577 MatchFinder::ParsingDoneTestCallback *ParsingDone)
1578 : Finder(Finder), ParsingDone(ParsingDone) {}
1579
1580private:
1581 void HandleTranslationUnit(ASTContext &Context) override {
1582 if (ParsingDone != nullptr) {
1583 ParsingDone->run();
1584 }
1585 Finder->matchAST(Context);
1586 }
1587
1588 MatchFinder *Finder;
1589 MatchFinder::ParsingDoneTestCallback *ParsingDone;
1590};
1591
1592} // end namespace
1593} // end namespace internal
1594
1595MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes,
1596 ASTContext *Context)
1597 : Nodes(Nodes), Context(Context),
1598 SourceManager(&Context->getSourceManager()) {}
1599
1600MatchFinder::MatchCallback::~MatchCallback() {}
1601MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {}
1602
1603MatchFinder::MatchFinder(MatchFinderOptions Options)
1604 : Options(std::move(Options)), ParsingDone(nullptr) {}
1605
1606MatchFinder::~MatchFinder() {}
1607
1608void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch,
1609 MatchCallback *Action) {
1610 std::optional<TraversalKind> TK;
1611 if (Action)
1612 TK = Action->getCheckTraversalKind();
1613 if (TK)
1614 Matchers.DeclOrStmt.emplace_back(args: traverse(TK: *TK, InnerMatcher: NodeMatch), args&: Action);
1615 else
1616 Matchers.DeclOrStmt.emplace_back(args: NodeMatch, args&: Action);
1617 Matchers.AllCallbacks.insert(Ptr: Action);
1618}
1619
1620void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
1621 MatchCallback *Action) {
1622 Matchers.Type.emplace_back(args: NodeMatch, args&: Action);
1623 Matchers.AllCallbacks.insert(Ptr: Action);
1624}
1625
1626void MatchFinder::addMatcher(const StatementMatcher &NodeMatch,
1627 MatchCallback *Action) {
1628 std::optional<TraversalKind> TK;
1629 if (Action)
1630 TK = Action->getCheckTraversalKind();
1631 if (TK)
1632 Matchers.DeclOrStmt.emplace_back(args: traverse(TK: *TK, InnerMatcher: NodeMatch), args&: Action);
1633 else
1634 Matchers.DeclOrStmt.emplace_back(args: NodeMatch, args&: Action);
1635 Matchers.AllCallbacks.insert(Ptr: Action);
1636}
1637
1638void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch,
1639 MatchCallback *Action) {
1640 Matchers.NestedNameSpecifier.emplace_back(args: NodeMatch, args&: Action);
1641 Matchers.AllCallbacks.insert(Ptr: Action);
1642}
1643
1644void MatchFinder::addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch,
1645 MatchCallback *Action) {
1646 Matchers.NestedNameSpecifierLoc.emplace_back(args: NodeMatch, args&: Action);
1647 Matchers.AllCallbacks.insert(Ptr: Action);
1648}
1649
1650void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch,
1651 MatchCallback *Action) {
1652 Matchers.TypeLoc.emplace_back(args: NodeMatch, args&: Action);
1653 Matchers.AllCallbacks.insert(Ptr: Action);
1654}
1655
1656void MatchFinder::addMatcher(const CXXCtorInitializerMatcher &NodeMatch,
1657 MatchCallback *Action) {
1658 Matchers.CtorInit.emplace_back(args: NodeMatch, args&: Action);
1659 Matchers.AllCallbacks.insert(Ptr: Action);
1660}
1661
1662void MatchFinder::addMatcher(const TemplateArgumentLocMatcher &NodeMatch,
1663 MatchCallback *Action) {
1664 Matchers.TemplateArgumentLoc.emplace_back(args: NodeMatch, args&: Action);
1665 Matchers.AllCallbacks.insert(Ptr: Action);
1666}
1667
1668void MatchFinder::addMatcher(const AttrMatcher &AttrMatch,
1669 MatchCallback *Action) {
1670 Matchers.Attr.emplace_back(args: AttrMatch, args&: Action);
1671 Matchers.AllCallbacks.insert(Ptr: Action);
1672}
1673
1674bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch,
1675 MatchCallback *Action) {
1676 if (NodeMatch.canConvertTo<Decl>()) {
1677 addMatcher(NodeMatch: NodeMatch.convertTo<Decl>(), Action);
1678 return true;
1679 } else if (NodeMatch.canConvertTo<QualType>()) {
1680 addMatcher(NodeMatch: NodeMatch.convertTo<QualType>(), Action);
1681 return true;
1682 } else if (NodeMatch.canConvertTo<Stmt>()) {
1683 addMatcher(NodeMatch: NodeMatch.convertTo<Stmt>(), Action);
1684 return true;
1685 } else if (NodeMatch.canConvertTo<NestedNameSpecifier>()) {
1686 addMatcher(NodeMatch: NodeMatch.convertTo<NestedNameSpecifier>(), Action);
1687 return true;
1688 } else if (NodeMatch.canConvertTo<NestedNameSpecifierLoc>()) {
1689 addMatcher(NodeMatch: NodeMatch.convertTo<NestedNameSpecifierLoc>(), Action);
1690 return true;
1691 } else if (NodeMatch.canConvertTo<TypeLoc>()) {
1692 addMatcher(NodeMatch: NodeMatch.convertTo<TypeLoc>(), Action);
1693 return true;
1694 } else if (NodeMatch.canConvertTo<CXXCtorInitializer>()) {
1695 addMatcher(NodeMatch: NodeMatch.convertTo<CXXCtorInitializer>(), Action);
1696 return true;
1697 } else if (NodeMatch.canConvertTo<TemplateArgumentLoc>()) {
1698 addMatcher(NodeMatch: NodeMatch.convertTo<TemplateArgumentLoc>(), Action);
1699 return true;
1700 } else if (NodeMatch.canConvertTo<Attr>()) {
1701 addMatcher(AttrMatch: NodeMatch.convertTo<Attr>(), Action);
1702 return true;
1703 }
1704 return false;
1705}
1706
1707std::unique_ptr<ASTConsumer> MatchFinder::newASTConsumer() {
1708 return std::make_unique<internal::MatchASTConsumer>(args: this, args&: ParsingDone);
1709}
1710
1711void MatchFinder::match(const clang::DynTypedNode &Node, ASTContext &Context) {
1712 internal::MatchASTVisitor Visitor(&Matchers, Options);
1713 Visitor.set_active_ast_context(&Context);
1714 Visitor.match(Node);
1715}
1716
1717void MatchFinder::matchAST(ASTContext &Context) {
1718 internal::MatchASTVisitor Visitor(&Matchers, Options);
1719 internal::MatchASTVisitor::TraceReporter StackTrace(Visitor);
1720 Visitor.set_active_ast_context(&Context);
1721 Visitor.onStartOfTranslationUnit();
1722 Visitor.TraverseAST(AST&: Context);
1723 Visitor.onEndOfTranslationUnit();
1724}
1725
1726void MatchFinder::registerTestCallbackAfterParsing(
1727 MatchFinder::ParsingDoneTestCallback *NewParsingDone) {
1728 ParsingDone = NewParsingDone;
1729}
1730
1731StringRef MatchFinder::MatchCallback::getID() const { return "<unknown>"; }
1732
1733std::optional<TraversalKind>
1734MatchFinder::MatchCallback::getCheckTraversalKind() const {
1735 return std::nullopt;
1736}
1737
1738} // end namespace ast_matchers
1739} // end namespace clang
1740