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