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 "clang/Basic/Module.h"
24#include "llvm/ADT/DenseMap.h"
25#include "llvm/ADT/SmallPtrSet.h"
26#include "llvm/ADT/StringMap.h"
27#include "llvm/Support/PrettyStackTrace.h"
28#include "llvm/Support/Timer.h"
29#include <deque>
30#include <memory>
31#include <set>
32
33namespace clang {
34namespace ast_matchers {
35namespace internal {
36namespace {
37
38typedef MatchFinder::MatchCallback MatchCallback;
39
40// The maximum number of memoization entries to store.
41// 10k has been experimentally found to give a good trade-off
42// of performance vs. memory consumption by running matcher
43// that match on every statement over a very large codebase.
44//
45// FIXME: Do some performance optimization in general and
46// revisit this number; also, put up micro-benchmarks that we can
47// optimize this on.
48static const unsigned MaxMemoizationEntries = 10000;
49
50enum class MatchType {
51 Ancestors,
52
53 Descendants,
54 Child,
55};
56
57// We use memoization to avoid running the same matcher on the same
58// AST node twice. This struct is the key for looking up match
59// result. It consists of an ID of the MatcherInterface (for
60// identifying the matcher), a pointer to the AST node and the
61// bound nodes before the matcher was executed.
62//
63// We currently only memoize on nodes whose pointers identify the
64// nodes (\c Stmt and \c Decl, but not \c QualType or \c TypeLoc).
65// For \c QualType and \c TypeLoc it is possible to implement
66// generation of keys for each type.
67// FIXME: Benchmark whether memoization of non-pointer typed nodes
68// provides enough benefit for the additional amount of code.
69struct MatchKey {
70 DynTypedMatcher::MatcherIDType MatcherID;
71 DynTypedNode Node;
72 BoundNodesTreeBuilder BoundNodes;
73 TraversalKind Traversal = TK_AsIs;
74 MatchType Type;
75
76 bool operator<(const MatchKey &Other) const {
77 return std::tie(args: Traversal, args: Type, args: MatcherID, args: Node, args: BoundNodes) <
78 std::tie(args: Other.Traversal, args: Other.Type, args: Other.MatcherID, args: Other.Node,
79 args: Other.BoundNodes);
80 }
81};
82
83// Used to store the result of a match and possibly bound nodes.
84struct MemoizedMatchResult {
85 bool ResultOfMatch;
86 BoundNodesTreeBuilder Nodes;
87};
88
89// A RecursiveASTVisitor that traverses all children or all descendants of
90// a node.
91class MatchChildASTVisitor
92 : public RecursiveASTVisitor<MatchChildASTVisitor> {
93public:
94 typedef RecursiveASTVisitor<MatchChildASTVisitor> VisitorBase;
95
96 // Creates an AST visitor that matches 'matcher' on all children or
97 // descendants of a traversed node. max_depth is the maximum depth
98 // to traverse: use 1 for matching the children and INT_MAX for
99 // matching the descendants.
100 MatchChildASTVisitor(const DynTypedMatcher *Matcher, ASTMatchFinder *Finder,
101 BoundNodesTreeBuilder *Builder, int MaxDepth,
102 bool IgnoreImplicitChildren,
103 ASTMatchFinder::BindKind Bind)
104 : Matcher(Matcher), Finder(Finder), Builder(Builder), CurrentDepth(0),
105 MaxDepth(MaxDepth), IgnoreImplicitChildren(IgnoreImplicitChildren),
106 Bind(Bind), Matches(false) {}
107
108 // Returns true if a match is found in the subtree rooted at the
109 // given AST node. This is done via a set of mutually recursive
110 // functions. Here's how the recursion is done (the *wildcard can
111 // actually be Decl, Stmt, or Type):
112 //
113 // - Traverse(node) calls BaseTraverse(node) when it needs
114 // to visit the descendants of node.
115 // - BaseTraverse(node) then calls (via VisitorBase::Traverse*(node))
116 // Traverse*(c) for each child c of 'node'.
117 // - Traverse*(c) in turn calls Traverse(c), completing the
118 // recursion.
119 bool findMatch(const DynTypedNode &DynNode) {
120 reset();
121 if (const Decl *D = DynNode.get<Decl>())
122 traverse(Node: *D);
123 else if (const Stmt *S = DynNode.get<Stmt>())
124 traverse(Node: *S);
125 else if (const NestedNameSpecifier *NNS =
126 DynNode.get<NestedNameSpecifier>())
127 traverse(Node: *NNS);
128 else if (const NestedNameSpecifierLoc *NNSLoc =
129 DynNode.get<NestedNameSpecifierLoc>())
130 traverse(Node: *NNSLoc);
131 else if (const QualType *Q = DynNode.get<QualType>())
132 traverse(Node: *Q, /*TraverseQualifier=*/args: true);
133 else if (const TypeLoc *T = DynNode.get<TypeLoc>())
134 traverse(Node: *T, /*TraverseQualifier=*/args: true);
135 else if (const auto *C = DynNode.get<CXXCtorInitializer>())
136 traverse(Node: *C);
137 else if (const TemplateArgumentLoc *TALoc =
138 DynNode.get<TemplateArgumentLoc>())
139 traverse(Node: *TALoc);
140 else if (const Attr *A = DynNode.get<Attr>())
141 traverse(Node: *A);
142 // FIXME: Add other base types after adding tests.
143
144 // It's OK to always overwrite the bound nodes, as if there was
145 // no match in this recursive branch, the result set is empty
146 // anyway.
147 *Builder = ResultBindings;
148
149 return Matches;
150 }
151
152 // The following are overriding methods from the base visitor class.
153 // They are public only to allow CRTP to work. They are *not *part
154 // of the public API of this class.
155 bool TraverseDecl(Decl *DeclNode) {
156
157 if (DeclNode && DeclNode->isImplicit() &&
158 Finder->isTraversalIgnoringImplicitNodes())
159 return baseTraverse(DeclNode: *DeclNode);
160
161 ScopedIncrement ScopedDepth(&CurrentDepth);
162 return (DeclNode == nullptr) || traverse(Node: *DeclNode);
163 }
164
165 Stmt *getStmtToTraverse(Stmt *StmtNode) {
166 Stmt *StmtToTraverse = StmtNode;
167 if (auto *ExprNode = dyn_cast_or_null<Expr>(Val: StmtNode)) {
168 auto *LambdaNode = dyn_cast_or_null<LambdaExpr>(Val: StmtNode);
169 if (LambdaNode && Finder->isTraversalIgnoringImplicitNodes())
170 StmtToTraverse = LambdaNode;
171 else
172 StmtToTraverse =
173 Finder->getASTContext().getParentMapContext().traverseIgnored(
174 E: ExprNode);
175 }
176 return StmtToTraverse;
177 }
178
179 bool TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue = nullptr) {
180 // If we need to keep track of the depth, we can't perform data recursion.
181 if (CurrentDepth == 0 || (CurrentDepth <= MaxDepth && MaxDepth < INT_MAX))
182 Queue = nullptr;
183
184 ScopedIncrement ScopedDepth(&CurrentDepth);
185 Stmt *StmtToTraverse = getStmtToTraverse(StmtNode);
186 if (!StmtToTraverse)
187 return true;
188
189 if (IgnoreImplicitChildren && isa<CXXDefaultArgExpr>(Val: StmtNode))
190 return true;
191
192 if (!match(Node: *StmtToTraverse))
193 return false;
194 return VisitorBase::TraverseStmt(S: StmtToTraverse, Queue);
195 }
196 // We assume that the QualType and the contained type are on the same
197 // hierarchy level. Thus, we try to match either of them.
198 bool TraverseType(QualType TypeNode, bool TraverseQualifier = true) {
199 if (TypeNode.isNull())
200 return true;
201 ScopedIncrement ScopedDepth(&CurrentDepth);
202 // Match the Type.
203 if (!match(Node: *TypeNode))
204 return false;
205 // The QualType is matched inside traverse.
206 return traverse(Node: TypeNode, args&: TraverseQualifier);
207 }
208 // We assume that the TypeLoc, contained QualType and contained Type all are
209 // on the same hierarchy level. Thus, we try to match all of them.
210 bool TraverseTypeLoc(TypeLoc TypeLocNode, bool TraverseQualifier = true) {
211 if (TypeLocNode.isNull())
212 return true;
213 ScopedIncrement ScopedDepth(&CurrentDepth);
214 // Match the Type.
215 if (!match(Node: *TypeLocNode.getType()))
216 return false;
217 // Match the QualType.
218 if (!match(Node: TypeLocNode.getType()))
219 return false;
220 // The TypeLoc is matched inside traverse.
221 return traverse(Node: TypeLocNode, args&: TraverseQualifier);
222 }
223 bool TraverseNestedNameSpecifier(NestedNameSpecifier NNS) {
224 ScopedIncrement ScopedDepth(&CurrentDepth);
225 return !NNS || traverse(Node: NNS);
226 }
227 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS) {
228 if (!NNS)
229 return true;
230 ScopedIncrement ScopedDepth(&CurrentDepth);
231 if (!match(Node: NNS.getNestedNameSpecifier()))
232 return false;
233 return traverse(Node: NNS);
234 }
235 bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit) {
236 if (!CtorInit)
237 return true;
238 ScopedIncrement ScopedDepth(&CurrentDepth);
239 return traverse(Node: *CtorInit);
240 }
241 bool TraverseTemplateArgumentLoc(TemplateArgumentLoc TAL) {
242 ScopedIncrement ScopedDepth(&CurrentDepth);
243 return traverse(Node: TAL);
244 }
245 bool TraverseCXXForRangeStmt(CXXForRangeStmt *Node) {
246 if (!Finder->isTraversalIgnoringImplicitNodes())
247 return VisitorBase::TraverseCXXForRangeStmt(S: Node);
248 if (!Node)
249 return true;
250 ScopedIncrement ScopedDepth(&CurrentDepth);
251 if (auto *Init = Node->getInit())
252 if (!traverse(Node: *Init))
253 return false;
254 if (!match(Node: *Node->getLoopVariable()))
255 return false;
256 if (match(Node: *Node->getRangeInit()))
257 if (!VisitorBase::TraverseStmt(S: Node->getRangeInit()))
258 return false;
259 if (!match(Node: *Node->getBody()))
260 return false;
261 return VisitorBase::TraverseStmt(S: Node->getBody());
262 }
263 bool TraverseCXXRewrittenBinaryOperator(CXXRewrittenBinaryOperator *Node) {
264 if (!Finder->isTraversalIgnoringImplicitNodes())
265 return VisitorBase::TraverseCXXRewrittenBinaryOperator(S: Node);
266 if (!Node)
267 return true;
268 ScopedIncrement ScopedDepth(&CurrentDepth);
269
270 return match(Node: *Node->getLHS()) && match(Node: *Node->getRHS());
271 }
272 bool TraverseAttr(Attr *A) {
273 if (A == nullptr ||
274 (A->isImplicit() &&
275 Finder->getASTContext().getParentMapContext().getTraversalKind() ==
276 TK_IgnoreUnlessSpelledInSource))
277 return true;
278 ScopedIncrement ScopedDepth(&CurrentDepth);
279 return traverse(Node: *A);
280 }
281 bool TraverseLambdaExpr(LambdaExpr *Node) {
282 if (!Finder->isTraversalIgnoringImplicitNodes())
283 return VisitorBase::TraverseLambdaExpr(S: Node);
284 if (!Node)
285 return true;
286 ScopedIncrement ScopedDepth(&CurrentDepth);
287
288 for (unsigned I = 0, N = Node->capture_size(); I != N; ++I) {
289 const LambdaCapture *C = Node->capture_begin() + I;
290 if (!C->isExplicit())
291 continue;
292 if (Node->isInitCapture(Capture: C) && !match(Node: *C->getCapturedVar()))
293 return false;
294 const Expr *CIE = Node->capture_init_begin()[I];
295 if (CIE != nullptr && !match(Node: *CIE))
296 return false;
297 }
298
299 if (const auto *TPL = Node->getTemplateParameterList()) {
300 for (const auto *TP : *TPL) {
301 if (!match(Node: *TP))
302 return false;
303 }
304 }
305
306 for (const auto *P : Node->getCallOperator()->parameters()) {
307 if (!match(Node: *P))
308 return false;
309 }
310
311 if (!match(Node: *Node->getBody()))
312 return false;
313
314 return VisitorBase::TraverseStmt(S: Node->getBody());
315 }
316
317 bool shouldVisitTemplateInstantiations() const { return true; }
318 bool shouldVisitImplicitCode() const { return !IgnoreImplicitChildren; }
319
320private:
321 // Used for updating the depth during traversal.
322 struct ScopedIncrement {
323 explicit ScopedIncrement(int *Depth) : Depth(Depth) { ++(*Depth); }
324 ~ScopedIncrement() { --(*Depth); }
325
326 private:
327 int *Depth;
328 };
329
330 // Resets the state of this object.
331 void reset() {
332 Matches = false;
333 CurrentDepth = 0;
334 }
335
336 // Forwards the call to the corresponding Traverse*() method in the
337 // base visitor class.
338 bool baseTraverse(const Decl &DeclNode) {
339 return VisitorBase::TraverseDecl(D: const_cast<Decl*>(&DeclNode));
340 }
341 bool baseTraverse(const Stmt &StmtNode) {
342 return VisitorBase::TraverseStmt(S: const_cast<Stmt*>(&StmtNode));
343 }
344 bool baseTraverse(QualType TypeNode, bool TraverseQualifier) {
345 return VisitorBase::TraverseType(T: TypeNode, TraverseQualifier);
346 }
347 bool baseTraverse(TypeLoc TypeLocNode, bool TraverseQualifier) {
348 return VisitorBase::TraverseTypeLoc(TL: TypeLocNode, TraverseQualifier);
349 }
350 bool baseTraverse(NestedNameSpecifier NNS) {
351 return VisitorBase::TraverseNestedNameSpecifier(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, class... Args>
400 bool traverse(const T &Node, Args &&...args) {
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, std::forward<Args>(args)...);
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, bool TraverseQualifier = true);
505 bool TraverseTypeLoc(TypeLoc TypeNode, bool TraverseQualifier = true);
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, /*TraverseQualifier=*/true);
581
582 if (Expr *NE = T->getNoexceptExpr())
583 TraverseStmt(StmtNode: NE, Queue);
584
585 if (LE->hasExplicitResultType())
586 TraverseTypeLoc(TypeNode: Proto.getReturnLoc(), /*TraverseQualifier=*/true);
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 auto matches = [&](const TypedefNameDecl *Alias) {
1293 BoundNodesTreeBuilder Result(*Builder);
1294 if (Matcher.matches(Node: *Alias, Finder: this, Builder: &Result)) {
1295 *Builder = std::move(Result);
1296 return true;
1297 }
1298 return false;
1299 };
1300
1301 if (const auto *T = TypeNode->getAs<TypedefType>()) {
1302 const auto *TD = T->getDecl()->getCanonicalDecl();
1303
1304 // Prioritize exact matches.
1305 SmallVector<const TypedefNameDecl *, 8> NonExactMatches;
1306 for (const TypedefNameDecl *Alias : Aliases->second) {
1307 if (!declaresSameEntity(D1: TD, D2: Alias)) {
1308 NonExactMatches.push_back(Elt: Alias);
1309 continue;
1310 }
1311 if (matches(Alias))
1312 return true;
1313 }
1314
1315 for (const TypedefNameDecl *Alias : NonExactMatches) {
1316 BoundNodesTreeBuilder Result(*Builder);
1317 if (Matcher.matches(Node: *Alias, Finder: this, Builder: &Result)) {
1318 *Builder = std::move(Result);
1319 return true;
1320 }
1321 }
1322 return false;
1323 }
1324
1325 for (const TypedefNameDecl *Alias : Aliases->second)
1326 if (matches(Alias))
1327 return true;
1328 return false;
1329 }
1330
1331 bool
1332 objcClassHasMatchingCompatibilityAlias(const ObjCInterfaceDecl *InterfaceDecl,
1333 const Matcher<NamedDecl> &Matcher,
1334 BoundNodesTreeBuilder *Builder) {
1335 auto Aliases = CompatibleAliases.find(Val: InterfaceDecl);
1336 if (Aliases == CompatibleAliases.end())
1337 return false;
1338 for (const ObjCCompatibleAliasDecl *Alias : Aliases->second) {
1339 BoundNodesTreeBuilder Result(*Builder);
1340 if (Matcher.matches(Node: *Alias, Finder: this, Builder: &Result)) {
1341 *Builder = std::move(Result);
1342 return true;
1343 }
1344 }
1345 return false;
1346 }
1347
1348 template <typename T> static SourceLocation getNodeLocation(const T &Node) {
1349 return Node.getBeginLoc();
1350 }
1351
1352 static SourceLocation getNodeLocation(const CXXCtorInitializer &Node) {
1353 return Node.getSourceLocation();
1354 }
1355
1356 static SourceLocation getNodeLocation(const TemplateArgumentLoc &Node) {
1357 return Node.getLocation();
1358 }
1359
1360 static SourceLocation getNodeLocation(const Attr &Node) {
1361 return Node.getLocation();
1362 }
1363
1364 bool isInSystemHeader(SourceLocation Loc) {
1365 const SourceManager &SM = getASTContext().getSourceManager();
1366 return SM.isInSystemHeader(Loc);
1367 }
1368
1369 template <typename T> bool shouldSkipNode(T &Node) {
1370 if (Options.IgnoreSystemHeaders && isInSystemHeader(Loc: getNodeLocation(Node)))
1371 return true;
1372 return false;
1373 }
1374
1375 template <typename T> bool shouldSkipNode(T *Node) {
1376 return (Node == nullptr) || shouldSkipNode(*Node);
1377 }
1378
1379 bool shouldSkipNode(QualType &) { return false; }
1380
1381 bool shouldSkipNode(NestedNameSpecifier &) { return false; }
1382
1383 /// Bucket to record map.
1384 ///
1385 /// Used to get the appropriate bucket for each matcher.
1386 llvm::StringMap<llvm::TimeRecord> TimeByBucket;
1387
1388 const MatchFinder::MatchersByType *Matchers;
1389
1390 /// Filtered list of matcher indices for each matcher kind.
1391 ///
1392 /// \c Decl and \c Stmt toplevel matchers usually apply to a specific node
1393 /// kind (and derived kinds) so it is a waste to try every matcher on every
1394 /// node.
1395 /// We precalculate a list of matchers that pass the toplevel restrict check.
1396 llvm::DenseMap<ASTNodeKind, std::vector<unsigned short>> MatcherFiltersMap;
1397
1398 const MatchFinder::MatchFinderOptions &Options;
1399 ASTContext *ActiveASTContext;
1400
1401 // Maps a canonical type to its TypedefDecls.
1402 llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases;
1403
1404 // Maps an Objective-C interface to its ObjCCompatibleAliasDecls.
1405 llvm::DenseMap<const ObjCInterfaceDecl *,
1406 llvm::SmallPtrSet<const ObjCCompatibleAliasDecl *, 2>>
1407 CompatibleAliases;
1408
1409 // Maps (matcher, node) -> the match result for memoization.
1410 typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap;
1411 MemoizationMap ResultCache;
1412};
1413
1414static CXXRecordDecl *
1415getAsCXXRecordDeclOrPrimaryTemplate(const Type *TypeNode) {
1416 if (auto *RD = TypeNode->getAsCXXRecordDecl())
1417 return RD;
1418
1419 // Find the innermost TemplateSpecializationType that isn't an alias template.
1420 auto *TemplateType = TypeNode->getAs<TemplateSpecializationType>();
1421 while (TemplateType && TemplateType->isTypeAlias())
1422 TemplateType =
1423 TemplateType->getAliasedType()->getAs<TemplateSpecializationType>();
1424
1425 // If this is the name of a (dependent) template specialization, use the
1426 // definition of the template, even though it might be specialized later.
1427 if (TemplateType)
1428 if (auto *ClassTemplate = dyn_cast_or_null<ClassTemplateDecl>(
1429 Val: TemplateType->getTemplateName().getAsTemplateDecl()))
1430 return ClassTemplate->getTemplatedDecl();
1431
1432 return nullptr;
1433}
1434
1435// Returns true if the given C++ class is directly or indirectly derived
1436// from a base type with the given name. A class is not considered to be
1437// derived from itself.
1438bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,
1439 const Matcher<NamedDecl> &Base,
1440 BoundNodesTreeBuilder *Builder,
1441 bool Directly) {
1442 llvm::SmallPtrSet<const CXXRecordDecl *, 8> Visited;
1443 return classIsDerivedFromImpl(Declaration, Base, Builder, Directly, Visited);
1444}
1445
1446bool MatchASTVisitor::classIsDerivedFromImpl(
1447 const CXXRecordDecl *Declaration, const Matcher<NamedDecl> &Base,
1448 BoundNodesTreeBuilder *Builder, bool Directly,
1449 llvm::SmallPtrSetImpl<const CXXRecordDecl *> &Visited) {
1450 if (!Declaration->hasDefinition())
1451 return false;
1452 if (!Visited.insert(Ptr: Declaration).second)
1453 return false;
1454 for (const auto &It : Declaration->bases()) {
1455 const Type *TypeNode = It.getType().getTypePtr();
1456
1457 if (typeHasMatchingAlias(TypeNode, Matcher: Base, Builder))
1458 return true;
1459
1460 // FIXME: Going to the primary template here isn't really correct, but
1461 // unfortunately we accept a Decl matcher for the base class not a Type
1462 // matcher, so it's the best thing we can do with our current interface.
1463 CXXRecordDecl *ClassDecl = getAsCXXRecordDeclOrPrimaryTemplate(TypeNode);
1464 if (!ClassDecl)
1465 continue;
1466 if (ClassDecl == Declaration) {
1467 // This can happen for recursive template definitions.
1468 continue;
1469 }
1470 BoundNodesTreeBuilder Result(*Builder);
1471 if (Base.matches(Node: *ClassDecl, Finder: this, Builder: &Result)) {
1472 *Builder = std::move(Result);
1473 return true;
1474 }
1475 if (!Directly &&
1476 classIsDerivedFromImpl(Declaration: ClassDecl, Base, Builder, Directly, Visited))
1477 return true;
1478 }
1479 return false;
1480}
1481
1482// Returns true if the given Objective-C class is directly or indirectly
1483// derived from a matching base class. A class is not considered to be derived
1484// from itself.
1485bool MatchASTVisitor::objcClassIsDerivedFrom(
1486 const ObjCInterfaceDecl *Declaration, const Matcher<NamedDecl> &Base,
1487 BoundNodesTreeBuilder *Builder, bool Directly) {
1488 // Check if any of the superclasses of the class match.
1489 for (const ObjCInterfaceDecl *ClassDecl = Declaration->getSuperClass();
1490 ClassDecl != nullptr; ClassDecl = ClassDecl->getSuperClass()) {
1491 // Check if there are any matching compatibility aliases.
1492 if (objcClassHasMatchingCompatibilityAlias(InterfaceDecl: ClassDecl, Matcher: Base, Builder))
1493 return true;
1494
1495 // Check if there are any matching type aliases.
1496 const Type *TypeNode = ClassDecl->getTypeForDecl();
1497 if (typeHasMatchingAlias(TypeNode, Matcher: Base, Builder))
1498 return true;
1499
1500 if (Base.matches(Node: *ClassDecl, Finder: this, Builder))
1501 return true;
1502
1503 // Not `return false` as a temporary workaround for PR43879.
1504 if (Directly)
1505 break;
1506 }
1507
1508 return false;
1509}
1510
1511bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {
1512 if (shouldSkipNode(Node: DeclNode))
1513 return true;
1514
1515 if (Options.SkipDeclsInModules && DeclNode->isInAnotherModuleUnit())
1516 return true;
1517
1518 bool ScopedTraversal =
1519 TraversingASTNodeNotSpelledInSource || DeclNode->isImplicit();
1520 bool ScopedChildren = TraversingASTChildrenNotSpelledInSource;
1521
1522 if (const auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(Val: DeclNode)) {
1523 auto SK = CTSD->getSpecializationKind();
1524 if (SK == TSK_ExplicitInstantiationDeclaration ||
1525 SK == TSK_ExplicitInstantiationDefinition)
1526 ScopedChildren = true;
1527 } else if (const auto *FD = dyn_cast<FunctionDecl>(Val: DeclNode)) {
1528 if (FD->isDefaulted())
1529 ScopedChildren = true;
1530 if (FD->isTemplateInstantiation())
1531 ScopedTraversal = true;
1532 } else if (isa<BindingDecl>(Val: DeclNode)) {
1533 ScopedChildren = true;
1534 }
1535
1536 ASTNodeNotSpelledInSourceScope RAII1(this, ScopedTraversal);
1537 ASTChildrenNotSpelledInSourceScope RAII2(this, ScopedChildren);
1538
1539 match(Node: *DeclNode);
1540 return RecursiveASTVisitor<MatchASTVisitor>::TraverseDecl(D: DeclNode);
1541}
1542
1543bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue) {
1544 if (shouldSkipNode(Node: StmtNode))
1545 return true;
1546
1547 bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
1548 TraversingASTChildrenNotSpelledInSource;
1549
1550 ASTNodeNotSpelledInSourceScope RAII(this, ScopedTraversal);
1551 match(Node: *StmtNode);
1552 return RecursiveASTVisitor<MatchASTVisitor>::TraverseStmt(S: StmtNode, Queue);
1553}
1554
1555bool MatchASTVisitor::TraverseType(QualType TypeNode, bool TraverseQualifier) {
1556 if (shouldSkipNode(TypeNode))
1557 return true;
1558
1559 match(Node: TypeNode);
1560 return RecursiveASTVisitor<MatchASTVisitor>::TraverseType(T: TypeNode,
1561 TraverseQualifier);
1562}
1563
1564bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode,
1565 bool TraverseQualifier) {
1566 if (shouldSkipNode(Node&: TypeLocNode))
1567 return true;
1568 // The RecursiveASTVisitor only visits types if they're not within TypeLocs.
1569 // We still want to find those types via matchers, so we match them here. Note
1570 // that the TypeLocs are structurally a shadow-hierarchy to the expressed
1571 // type, so we visit all involved parts of a compound type when matching on
1572 // each TypeLoc.
1573 match(Node: TypeLocNode);
1574 match(Node: TypeLocNode.getType());
1575 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTypeLoc(
1576 TL: TypeLocNode, TraverseQualifier);
1577}
1578
1579bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier NNS) {
1580 if (shouldSkipNode(NNS))
1581 return true;
1582
1583 match(Node: NNS);
1584 return RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifier(NNS);
1585}
1586
1587bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
1588 NestedNameSpecifierLoc NNS) {
1589 if (!NNS)
1590 return true;
1591
1592 if (shouldSkipNode(Node&: NNS))
1593 return true;
1594
1595 match(Node: NNS);
1596
1597 // We only match the nested name specifier here (as opposed to traversing it)
1598 // because the traversal is already done in the parallel "Loc"-hierarchy.
1599 if (NNS.hasQualifier())
1600 match(Node: NNS.getNestedNameSpecifier());
1601 return
1602 RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifierLoc(NNS);
1603}
1604
1605bool MatchASTVisitor::TraverseConstructorInitializer(
1606 CXXCtorInitializer *CtorInit) {
1607 if (shouldSkipNode(Node: CtorInit))
1608 return true;
1609
1610 bool ScopedTraversal = TraversingASTNodeNotSpelledInSource ||
1611 TraversingASTChildrenNotSpelledInSource;
1612
1613 if (!CtorInit->isWritten())
1614 ScopedTraversal = true;
1615
1616 ASTNodeNotSpelledInSourceScope RAII1(this, ScopedTraversal);
1617
1618 match(Node: *CtorInit);
1619
1620 return RecursiveASTVisitor<MatchASTVisitor>::TraverseConstructorInitializer(
1621 Init: CtorInit);
1622}
1623
1624bool MatchASTVisitor::TraverseTemplateArgumentLoc(TemplateArgumentLoc Loc) {
1625 if (shouldSkipNode(Node&: Loc))
1626 return true;
1627
1628 match(Node: Loc);
1629 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateArgumentLoc(ArgLoc: Loc);
1630}
1631
1632bool MatchASTVisitor::TraverseAttr(Attr *AttrNode) {
1633 if (shouldSkipNode(Node: AttrNode))
1634 return true;
1635
1636 match(Node: *AttrNode);
1637 return RecursiveASTVisitor<MatchASTVisitor>::TraverseAttr(A: AttrNode);
1638}
1639
1640class MatchASTConsumer : public ASTConsumer {
1641public:
1642 MatchASTConsumer(MatchFinder *Finder,
1643 MatchFinder::ParsingDoneTestCallback *ParsingDone)
1644 : Finder(Finder), ParsingDone(ParsingDone) {}
1645
1646private:
1647 void HandleTranslationUnit(ASTContext &Context) override {
1648 if (ParsingDone != nullptr) {
1649 ParsingDone->run();
1650 }
1651 Finder->matchAST(Context);
1652 }
1653
1654 MatchFinder *Finder;
1655 MatchFinder::ParsingDoneTestCallback *ParsingDone;
1656};
1657
1658} // end namespace
1659} // end namespace internal
1660
1661template <typename T>
1662static internal::Matcher<T>
1663adjustTraversalKind(const internal::Matcher<T> &NodeMatch,
1664 MatchFinder::MatchCallback *Action) {
1665 if (Action)
1666 if (std::optional<TraversalKind> TK = Action->getCheckTraversalKind())
1667 return traverse(*TK, NodeMatch);
1668 return NodeMatch;
1669}
1670
1671MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes,
1672 ASTContext *Context)
1673 : Nodes(Nodes), Context(Context),
1674 SourceManager(&Context->getSourceManager()) {}
1675
1676MatchFinder::MatchCallback::~MatchCallback() {}
1677MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {}
1678
1679MatchFinder::MatchFinder(MatchFinderOptions Options)
1680 : Options(std::move(Options)), ParsingDone(nullptr) {}
1681
1682MatchFinder::~MatchFinder() {}
1683
1684void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch,
1685 MatchCallback *Action) {
1686 Matchers.DeclOrStmt.emplace_back(args: adjustTraversalKind(NodeMatch, Action),
1687 args&: Action);
1688 Matchers.AllCallbacks.insert(Ptr: Action);
1689}
1690
1691void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
1692 MatchCallback *Action) {
1693 Matchers.Type.emplace_back(args: adjustTraversalKind(NodeMatch, Action), args&: Action);
1694 Matchers.AllCallbacks.insert(Ptr: Action);
1695}
1696
1697void MatchFinder::addMatcher(const StatementMatcher &NodeMatch,
1698 MatchCallback *Action) {
1699 Matchers.DeclOrStmt.emplace_back(args: adjustTraversalKind(NodeMatch, Action),
1700 args&: Action);
1701 Matchers.AllCallbacks.insert(Ptr: Action);
1702}
1703
1704void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch,
1705 MatchCallback *Action) {
1706 Matchers.NestedNameSpecifier.emplace_back(
1707 args: adjustTraversalKind(NodeMatch, Action), args&: Action);
1708 Matchers.AllCallbacks.insert(Ptr: Action);
1709}
1710
1711void MatchFinder::addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch,
1712 MatchCallback *Action) {
1713 Matchers.NestedNameSpecifierLoc.emplace_back(
1714 args: adjustTraversalKind(NodeMatch, Action), args&: Action);
1715 Matchers.AllCallbacks.insert(Ptr: Action);
1716}
1717
1718void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch,
1719 MatchCallback *Action) {
1720 Matchers.TypeLoc.emplace_back(args: adjustTraversalKind(NodeMatch, Action), args&: Action);
1721 Matchers.AllCallbacks.insert(Ptr: Action);
1722}
1723
1724void MatchFinder::addMatcher(const CXXCtorInitializerMatcher &NodeMatch,
1725 MatchCallback *Action) {
1726 Matchers.CtorInit.emplace_back(args: adjustTraversalKind(NodeMatch, Action),
1727 args&: Action);
1728 Matchers.AllCallbacks.insert(Ptr: Action);
1729}
1730
1731void MatchFinder::addMatcher(const TemplateArgumentLocMatcher &NodeMatch,
1732 MatchCallback *Action) {
1733 Matchers.TemplateArgumentLoc.emplace_back(
1734 args: adjustTraversalKind(NodeMatch, Action), args&: Action);
1735 Matchers.AllCallbacks.insert(Ptr: Action);
1736}
1737
1738void MatchFinder::addMatcher(const AttrMatcher &AttrMatch,
1739 MatchCallback *Action) {
1740 Matchers.Attr.emplace_back(args: adjustTraversalKind(NodeMatch: AttrMatch, Action), args&: Action);
1741 Matchers.AllCallbacks.insert(Ptr: Action);
1742}
1743
1744bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch,
1745 MatchCallback *Action) {
1746 if (NodeMatch.canConvertTo<Decl>()) {
1747 addMatcher(NodeMatch: NodeMatch.convertTo<Decl>(), Action);
1748 return true;
1749 } else if (NodeMatch.canConvertTo<QualType>()) {
1750 addMatcher(NodeMatch: NodeMatch.convertTo<QualType>(), Action);
1751 return true;
1752 } else if (NodeMatch.canConvertTo<Stmt>()) {
1753 addMatcher(NodeMatch: NodeMatch.convertTo<Stmt>(), Action);
1754 return true;
1755 } else if (NodeMatch.canConvertTo<NestedNameSpecifier>()) {
1756 addMatcher(NodeMatch: NodeMatch.convertTo<NestedNameSpecifier>(), Action);
1757 return true;
1758 } else if (NodeMatch.canConvertTo<NestedNameSpecifierLoc>()) {
1759 addMatcher(NodeMatch: NodeMatch.convertTo<NestedNameSpecifierLoc>(), Action);
1760 return true;
1761 } else if (NodeMatch.canConvertTo<TypeLoc>()) {
1762 addMatcher(NodeMatch: NodeMatch.convertTo<TypeLoc>(), Action);
1763 return true;
1764 } else if (NodeMatch.canConvertTo<CXXCtorInitializer>()) {
1765 addMatcher(NodeMatch: NodeMatch.convertTo<CXXCtorInitializer>(), Action);
1766 return true;
1767 } else if (NodeMatch.canConvertTo<TemplateArgumentLoc>()) {
1768 addMatcher(NodeMatch: NodeMatch.convertTo<TemplateArgumentLoc>(), Action);
1769 return true;
1770 } else if (NodeMatch.canConvertTo<Attr>()) {
1771 addMatcher(AttrMatch: NodeMatch.convertTo<Attr>(), Action);
1772 return true;
1773 }
1774 return false;
1775}
1776
1777std::unique_ptr<ASTConsumer> MatchFinder::newASTConsumer() {
1778 return std::make_unique<internal::MatchASTConsumer>(args: this, args&: ParsingDone);
1779}
1780
1781void MatchFinder::match(const clang::DynTypedNode &Node, ASTContext &Context) {
1782 internal::MatchASTVisitor Visitor(&Matchers, Options);
1783 Visitor.set_active_ast_context(&Context);
1784 Visitor.match(Node);
1785}
1786
1787void MatchFinder::matchAST(ASTContext &Context) {
1788 internal::MatchASTVisitor Visitor(&Matchers, Options);
1789 internal::MatchASTVisitor::TraceReporter StackTrace(Visitor);
1790 Visitor.set_active_ast_context(&Context);
1791 Visitor.onStartOfTranslationUnit();
1792 Visitor.TraverseAST(AST&: Context);
1793 Visitor.onEndOfTranslationUnit();
1794}
1795
1796void MatchFinder::registerTestCallbackAfterParsing(
1797 MatchFinder::ParsingDoneTestCallback *NewParsingDone) {
1798 ParsingDone = NewParsingDone;
1799}
1800
1801StringRef MatchFinder::MatchCallback::getID() const { return "<unknown>"; }
1802
1803std::optional<TraversalKind>
1804MatchFinder::MatchCallback::getCheckTraversalKind() const {
1805 return std::nullopt;
1806}
1807
1808} // end namespace ast_matchers
1809} // end namespace clang
1810