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