1 //===--- ASTMatchFinder.cpp - Structural query framework ------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Implements an algorithm to efficiently search for matches on AST nodes.
11 // Uses memoization to support recursive matches like HasDescendant.
13 // The general idea is to visit all AST nodes with a RecursiveASTVisitor,
14 // calling the Matches(...) method of each matcher we are running on each
15 // AST node. The matcher can recurse via the ASTMatchFinder interface.
17 //===----------------------------------------------------------------------===//
19 #include "clang/ASTMatchers/ASTMatchFinder.h"
20 #include "clang/AST/ASTConsumer.h"
21 #include "clang/AST/ASTContext.h"
22 #include "clang/AST/RecursiveASTVisitor.h"
23 #include "llvm/ADT/DenseMap.h"
24 #include "llvm/ADT/StringMap.h"
25 #include "llvm/Support/Timer.h"
31 namespace ast_matchers {
35 typedef MatchFinder::MatchCallback MatchCallback;
37 // The maximum number of memoization entries to store.
38 // 10k has been experimentally found to give a good trade-off
39 // of performance vs. memory consumption by running matcher
40 // that match on every statement over a very large codebase.
42 // FIXME: Do some performance optimization in general and
43 // revisit this number; also, put up micro-benchmarks that we can
45 static const unsigned MaxMemoizationEntries = 10000;
47 // We use memoization to avoid running the same matcher on the same
48 // AST node twice. This struct is the key for looking up match
49 // result. It consists of an ID of the MatcherInterface (for
50 // identifying the matcher), a pointer to the AST node and the
51 // bound nodes before the matcher was executed.
53 // We currently only memoize on nodes whose pointers identify the
54 // nodes (\c Stmt and \c Decl, but not \c QualType or \c TypeLoc).
55 // For \c QualType and \c TypeLoc it is possible to implement
56 // generation of keys for each type.
57 // FIXME: Benchmark whether memoization of non-pointer typed nodes
58 // provides enough benefit for the additional amount of code.
60 DynTypedMatcher::MatcherIDType MatcherID;
61 ast_type_traits::DynTypedNode Node;
62 BoundNodesTreeBuilder BoundNodes;
64 bool operator<(const MatchKey &Other) const {
65 return std::tie(MatcherID, Node, BoundNodes) <
66 std::tie(Other.MatcherID, Other.Node, Other.BoundNodes);
70 // Used to store the result of a match and possibly bound nodes.
71 struct MemoizedMatchResult {
73 BoundNodesTreeBuilder Nodes;
76 // A RecursiveASTVisitor that traverses all children or all descendants of
78 class MatchChildASTVisitor
79 : public RecursiveASTVisitor<MatchChildASTVisitor> {
81 typedef RecursiveASTVisitor<MatchChildASTVisitor> VisitorBase;
83 // Creates an AST visitor that matches 'matcher' on all children or
84 // descendants of a traversed node. max_depth is the maximum depth
85 // to traverse: use 1 for matching the children and INT_MAX for
86 // matching the descendants.
87 MatchChildASTVisitor(const DynTypedMatcher *Matcher,
88 ASTMatchFinder *Finder,
89 BoundNodesTreeBuilder *Builder,
91 ASTMatchFinder::TraversalKind Traversal,
92 ASTMatchFinder::BindKind Bind)
102 // Returns true if a match is found in the subtree rooted at the
103 // given AST node. This is done via a set of mutually recursive
104 // functions. Here's how the recursion is done (the *wildcard can
105 // actually be Decl, Stmt, or Type):
107 // - Traverse(node) calls BaseTraverse(node) when it needs
108 // to visit the descendants of node.
109 // - BaseTraverse(node) then calls (via VisitorBase::Traverse*(node))
110 // Traverse*(c) for each child c of 'node'.
111 // - Traverse*(c) in turn calls Traverse(c), completing the
113 bool findMatch(const ast_type_traits::DynTypedNode &DynNode) {
115 if (const Decl *D = DynNode.get<Decl>())
117 else if (const Stmt *S = DynNode.get<Stmt>())
119 else if (const NestedNameSpecifier *NNS =
120 DynNode.get<NestedNameSpecifier>())
122 else if (const NestedNameSpecifierLoc *NNSLoc =
123 DynNode.get<NestedNameSpecifierLoc>())
125 else if (const QualType *Q = DynNode.get<QualType>())
127 else if (const TypeLoc *T = DynNode.get<TypeLoc>())
129 else if (const auto *C = DynNode.get<CXXCtorInitializer>())
131 // FIXME: Add other base types after adding tests.
133 // It's OK to always overwrite the bound nodes, as if there was
134 // no match in this recursive branch, the result set is empty
136 *Builder = ResultBindings;
141 // The following are overriding methods from the base visitor class.
142 // They are public only to allow CRTP to work. They are *not *part
143 // of the public API of this class.
144 bool TraverseDecl(Decl *DeclNode) {
145 ScopedIncrement ScopedDepth(&CurrentDepth);
146 return (DeclNode == nullptr) || traverse(*DeclNode);
148 bool TraverseStmt(Stmt *StmtNode) {
149 ScopedIncrement ScopedDepth(&CurrentDepth);
150 const Stmt *StmtToTraverse = StmtNode;
152 ASTMatchFinder::TK_IgnoreImplicitCastsAndParentheses) {
153 const Expr *ExprNode = dyn_cast_or_null<Expr>(StmtNode);
155 StmtToTraverse = ExprNode->IgnoreParenImpCasts();
158 return (StmtToTraverse == nullptr) || traverse(*StmtToTraverse);
160 // We assume that the QualType and the contained type are on the same
161 // hierarchy level. Thus, we try to match either of them.
162 bool TraverseType(QualType TypeNode) {
163 if (TypeNode.isNull())
165 ScopedIncrement ScopedDepth(&CurrentDepth);
167 if (!match(*TypeNode))
169 // The QualType is matched inside traverse.
170 return traverse(TypeNode);
172 // We assume that the TypeLoc, contained QualType and contained Type all are
173 // on the same hierarchy level. Thus, we try to match all of them.
174 bool TraverseTypeLoc(TypeLoc TypeLocNode) {
175 if (TypeLocNode.isNull())
177 ScopedIncrement ScopedDepth(&CurrentDepth);
179 if (!match(*TypeLocNode.getType()))
181 // Match the QualType.
182 if (!match(TypeLocNode.getType()))
184 // The TypeLoc is matched inside traverse.
185 return traverse(TypeLocNode);
187 bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
188 ScopedIncrement ScopedDepth(&CurrentDepth);
189 return (NNS == nullptr) || traverse(*NNS);
191 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS) {
194 ScopedIncrement ScopedDepth(&CurrentDepth);
195 if (!match(*NNS.getNestedNameSpecifier()))
197 return traverse(NNS);
199 bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit) {
202 ScopedIncrement ScopedDepth(&CurrentDepth);
203 return traverse(*CtorInit);
206 bool shouldVisitTemplateInstantiations() const { return true; }
207 bool shouldVisitImplicitCode() const { return true; }
210 // Used for updating the depth during traversal.
211 struct ScopedIncrement {
212 explicit ScopedIncrement(int *Depth) : Depth(Depth) { ++(*Depth); }
213 ~ScopedIncrement() { --(*Depth); }
219 // Resets the state of this object.
225 // Forwards the call to the corresponding Traverse*() method in the
226 // base visitor class.
227 bool baseTraverse(const Decl &DeclNode) {
228 return VisitorBase::TraverseDecl(const_cast<Decl*>(&DeclNode));
230 bool baseTraverse(const Stmt &StmtNode) {
231 return VisitorBase::TraverseStmt(const_cast<Stmt*>(&StmtNode));
233 bool baseTraverse(QualType TypeNode) {
234 return VisitorBase::TraverseType(TypeNode);
236 bool baseTraverse(TypeLoc TypeLocNode) {
237 return VisitorBase::TraverseTypeLoc(TypeLocNode);
239 bool baseTraverse(const NestedNameSpecifier &NNS) {
240 return VisitorBase::TraverseNestedNameSpecifier(
241 const_cast<NestedNameSpecifier*>(&NNS));
243 bool baseTraverse(NestedNameSpecifierLoc NNS) {
244 return VisitorBase::TraverseNestedNameSpecifierLoc(NNS);
246 bool baseTraverse(const CXXCtorInitializer &CtorInit) {
247 return VisitorBase::TraverseConstructorInitializer(
248 const_cast<CXXCtorInitializer *>(&CtorInit));
251 // Sets 'Matched' to true if 'Matcher' matches 'Node' and:
252 // 0 < CurrentDepth <= MaxDepth.
254 // Returns 'true' if traversal should continue after this function
255 // returns, i.e. if no match is found or 'Bind' is 'BK_All'.
256 template <typename T>
257 bool match(const T &Node) {
258 if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
261 if (Bind != ASTMatchFinder::BK_All) {
262 BoundNodesTreeBuilder RecursiveBuilder(*Builder);
263 if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node), Finder,
264 &RecursiveBuilder)) {
266 ResultBindings.addMatch(RecursiveBuilder);
267 return false; // Abort as soon as a match is found.
270 BoundNodesTreeBuilder RecursiveBuilder(*Builder);
271 if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node), Finder,
272 &RecursiveBuilder)) {
273 // After the first match the matcher succeeds.
275 ResultBindings.addMatch(RecursiveBuilder);
281 // Traverses the subtree rooted at 'Node'; returns true if the
282 // traversal should continue after this function returns.
283 template <typename T>
284 bool traverse(const T &Node) {
285 static_assert(IsBaseType<T>::value,
286 "traverse can only be instantiated with base type");
289 return baseTraverse(Node);
292 const DynTypedMatcher *const Matcher;
293 ASTMatchFinder *const Finder;
294 BoundNodesTreeBuilder *const Builder;
295 BoundNodesTreeBuilder ResultBindings;
298 const ASTMatchFinder::TraversalKind Traversal;
299 const ASTMatchFinder::BindKind Bind;
303 // Controls the outermost traversal of the AST and allows to match multiple
305 class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>,
306 public ASTMatchFinder {
308 MatchASTVisitor(const MatchFinder::MatchersByType *Matchers,
309 const MatchFinder::MatchFinderOptions &Options)
310 : Matchers(Matchers), Options(Options), ActiveASTContext(nullptr) {}
312 ~MatchASTVisitor() override {
313 if (Options.CheckProfiling) {
314 Options.CheckProfiling->Records = std::move(TimeByBucket);
318 void onStartOfTranslationUnit() {
319 const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
320 TimeBucketRegion Timer;
321 for (MatchCallback *MC : Matchers->AllCallbacks) {
322 if (EnableCheckProfiling)
323 Timer.setBucket(&TimeByBucket[MC->getID()]);
324 MC->onStartOfTranslationUnit();
328 void onEndOfTranslationUnit() {
329 const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
330 TimeBucketRegion Timer;
331 for (MatchCallback *MC : Matchers->AllCallbacks) {
332 if (EnableCheckProfiling)
333 Timer.setBucket(&TimeByBucket[MC->getID()]);
334 MC->onEndOfTranslationUnit();
338 void set_active_ast_context(ASTContext *NewActiveASTContext) {
339 ActiveASTContext = NewActiveASTContext;
342 // The following Visit*() and Traverse*() functions "override"
343 // methods in RecursiveASTVisitor.
345 bool VisitTypedefNameDecl(TypedefNameDecl *DeclNode) {
346 // When we see 'typedef A B', we add name 'B' to the set of names
347 // A's canonical type maps to. This is necessary for implementing
348 // isDerivedFrom(x) properly, where x can be the name of the base
349 // class or any of its aliases.
351 // In general, the is-alias-of (as defined by typedefs) relation
352 // is tree-shaped, as you can typedef a type more than once. For
368 // It is wrong to assume that the relation is a chain. A correct
369 // implementation of isDerivedFrom() needs to recognize that B and
370 // E are aliases, even though neither is a typedef of the other.
371 // Therefore, we cannot simply walk through one typedef chain to
372 // find out whether the type name matches.
373 const Type *TypeNode = DeclNode->getUnderlyingType().getTypePtr();
374 const Type *CanonicalType = // root of the typedef tree
375 ActiveASTContext->getCanonicalType(TypeNode);
376 TypeAliases[CanonicalType].insert(DeclNode);
380 bool TraverseDecl(Decl *DeclNode);
381 bool TraverseStmt(Stmt *StmtNode);
382 bool TraverseType(QualType TypeNode);
383 bool TraverseTypeLoc(TypeLoc TypeNode);
384 bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS);
385 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS);
386 bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit);
388 // Matches children or descendants of 'Node' with 'BaseMatcher'.
389 bool memoizedMatchesRecursively(const ast_type_traits::DynTypedNode &Node,
390 const DynTypedMatcher &Matcher,
391 BoundNodesTreeBuilder *Builder, int MaxDepth,
392 TraversalKind Traversal, BindKind Bind) {
393 // For AST-nodes that don't have an identity, we can't memoize.
394 if (!Node.getMemoizationData() || !Builder->isComparable())
395 return matchesRecursively(Node, Matcher, Builder, MaxDepth, Traversal,
399 Key.MatcherID = Matcher.getID();
401 // Note that we key on the bindings *before* the match.
402 Key.BoundNodes = *Builder;
404 MemoizationMap::iterator I = ResultCache.find(Key);
405 if (I != ResultCache.end()) {
406 *Builder = I->second.Nodes;
407 return I->second.ResultOfMatch;
410 MemoizedMatchResult Result;
411 Result.Nodes = *Builder;
412 Result.ResultOfMatch = matchesRecursively(Node, Matcher, &Result.Nodes,
413 MaxDepth, Traversal, Bind);
415 MemoizedMatchResult &CachedResult = ResultCache[Key];
416 CachedResult = std::move(Result);
418 *Builder = CachedResult.Nodes;
419 return CachedResult.ResultOfMatch;
422 // Matches children or descendants of 'Node' with 'BaseMatcher'.
423 bool matchesRecursively(const ast_type_traits::DynTypedNode &Node,
424 const DynTypedMatcher &Matcher,
425 BoundNodesTreeBuilder *Builder, int MaxDepth,
426 TraversalKind Traversal, BindKind Bind) {
427 MatchChildASTVisitor Visitor(
428 &Matcher, this, Builder, MaxDepth, Traversal, Bind);
429 return Visitor.findMatch(Node);
432 bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
433 const Matcher<NamedDecl> &Base,
434 BoundNodesTreeBuilder *Builder) override;
436 // Implements ASTMatchFinder::matchesChildOf.
437 bool matchesChildOf(const ast_type_traits::DynTypedNode &Node,
438 const DynTypedMatcher &Matcher,
439 BoundNodesTreeBuilder *Builder,
440 TraversalKind Traversal,
441 BindKind Bind) override {
442 if (ResultCache.size() > MaxMemoizationEntries)
444 return memoizedMatchesRecursively(Node, Matcher, Builder, 1, Traversal,
447 // Implements ASTMatchFinder::matchesDescendantOf.
448 bool matchesDescendantOf(const ast_type_traits::DynTypedNode &Node,
449 const DynTypedMatcher &Matcher,
450 BoundNodesTreeBuilder *Builder,
451 BindKind Bind) override {
452 if (ResultCache.size() > MaxMemoizationEntries)
454 return memoizedMatchesRecursively(Node, Matcher, Builder, INT_MAX,
457 // Implements ASTMatchFinder::matchesAncestorOf.
458 bool matchesAncestorOf(const ast_type_traits::DynTypedNode &Node,
459 const DynTypedMatcher &Matcher,
460 BoundNodesTreeBuilder *Builder,
461 AncestorMatchMode MatchMode) override {
462 // Reset the cache outside of the recursive call to make sure we
463 // don't invalidate any iterators.
464 if (ResultCache.size() > MaxMemoizationEntries)
466 return memoizedMatchesAncestorOfRecursively(Node, Matcher, Builder,
470 // Matches all registered matchers on the given node and calls the
471 // result callback for every node that matches.
472 void match(const ast_type_traits::DynTypedNode &Node) {
473 // FIXME: Improve this with a switch or a visitor pattern.
474 if (auto *N = Node.get<Decl>()) {
476 } else if (auto *N = Node.get<Stmt>()) {
478 } else if (auto *N = Node.get<Type>()) {
480 } else if (auto *N = Node.get<QualType>()) {
482 } else if (auto *N = Node.get<NestedNameSpecifier>()) {
484 } else if (auto *N = Node.get<NestedNameSpecifierLoc>()) {
486 } else if (auto *N = Node.get<TypeLoc>()) {
488 } else if (auto *N = Node.get<CXXCtorInitializer>()) {
493 template <typename T> void match(const T &Node) {
494 matchDispatch(&Node);
497 // Implements ASTMatchFinder::getASTContext.
498 ASTContext &getASTContext() const override { return *ActiveASTContext; }
500 bool shouldVisitTemplateInstantiations() const { return true; }
501 bool shouldVisitImplicitCode() const { return true; }
504 class TimeBucketRegion {
506 TimeBucketRegion() : Bucket(nullptr) {}
507 ~TimeBucketRegion() { setBucket(nullptr); }
509 /// \brief Start timing for \p NewBucket.
511 /// If there was a bucket already set, it will finish the timing for that
513 /// \p NewBucket will be timed until the next call to \c setBucket() or
514 /// until the \c TimeBucketRegion is destroyed.
515 /// If \p NewBucket is the same as the currently timed bucket, this call
517 void setBucket(llvm::TimeRecord *NewBucket) {
518 if (Bucket != NewBucket) {
519 auto Now = llvm::TimeRecord::getCurrentTime(true);
529 llvm::TimeRecord *Bucket;
532 /// \brief Runs all the \p Matchers on \p Node.
534 /// Used by \c matchDispatch() below.
535 template <typename T, typename MC>
536 void matchWithoutFilter(const T &Node, const MC &Matchers) {
537 const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
538 TimeBucketRegion Timer;
539 for (const auto &MP : Matchers) {
540 if (EnableCheckProfiling)
541 Timer.setBucket(&TimeByBucket[MP.second->getID()]);
542 BoundNodesTreeBuilder Builder;
543 if (MP.first.matches(Node, this, &Builder)) {
544 MatchVisitor Visitor(ActiveASTContext, MP.second);
545 Builder.visitMatches(&Visitor);
550 void matchWithFilter(const ast_type_traits::DynTypedNode &DynNode) {
551 auto Kind = DynNode.getNodeKind();
552 auto it = MatcherFiltersMap.find(Kind);
554 it != MatcherFiltersMap.end() ? it->second : getFilterForKind(Kind);
559 const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
560 TimeBucketRegion Timer;
561 auto &Matchers = this->Matchers->DeclOrStmt;
562 for (unsigned short I : Filter) {
563 auto &MP = Matchers[I];
564 if (EnableCheckProfiling)
565 Timer.setBucket(&TimeByBucket[MP.second->getID()]);
566 BoundNodesTreeBuilder Builder;
567 if (MP.first.matchesNoKindCheck(DynNode, this, &Builder)) {
568 MatchVisitor Visitor(ActiveASTContext, MP.second);
569 Builder.visitMatches(&Visitor);
574 const std::vector<unsigned short> &
575 getFilterForKind(ast_type_traits::ASTNodeKind Kind) {
576 auto &Filter = MatcherFiltersMap[Kind];
577 auto &Matchers = this->Matchers->DeclOrStmt;
578 assert((Matchers.size() < USHRT_MAX) && "Too many matchers.");
579 for (unsigned I = 0, E = Matchers.size(); I != E; ++I) {
580 if (Matchers[I].first.canMatchNodesOfKind(Kind)) {
588 /// \brief Overloads to pair the different node types to their matchers.
589 void matchDispatch(const Decl *Node) {
590 return matchWithFilter(ast_type_traits::DynTypedNode::create(*Node));
592 void matchDispatch(const Stmt *Node) {
593 return matchWithFilter(ast_type_traits::DynTypedNode::create(*Node));
596 void matchDispatch(const Type *Node) {
597 matchWithoutFilter(QualType(Node, 0), Matchers->Type);
599 void matchDispatch(const TypeLoc *Node) {
600 matchWithoutFilter(*Node, Matchers->TypeLoc);
602 void matchDispatch(const QualType *Node) {
603 matchWithoutFilter(*Node, Matchers->Type);
605 void matchDispatch(const NestedNameSpecifier *Node) {
606 matchWithoutFilter(*Node, Matchers->NestedNameSpecifier);
608 void matchDispatch(const NestedNameSpecifierLoc *Node) {
609 matchWithoutFilter(*Node, Matchers->NestedNameSpecifierLoc);
611 void matchDispatch(const CXXCtorInitializer *Node) {
612 matchWithoutFilter(*Node, Matchers->CtorInit);
614 void matchDispatch(const void *) { /* Do nothing. */ }
617 // Returns whether an ancestor of \p Node matches \p Matcher.
619 // The order of matching ((which can lead to different nodes being bound in
620 // case there are multiple matches) is breadth first search.
622 // To allow memoization in the very common case of having deeply nested
623 // expressions inside a template function, we first walk up the AST, memoizing
624 // the result of the match along the way, as long as there is only a single
627 // Once there are multiple parents, the breadth first search order does not
628 // allow simple memoization on the ancestors. Thus, we only memoize as long
629 // as there is a single parent.
630 bool memoizedMatchesAncestorOfRecursively(
631 const ast_type_traits::DynTypedNode &Node, const DynTypedMatcher &Matcher,
632 BoundNodesTreeBuilder *Builder, AncestorMatchMode MatchMode) {
633 if (Node.get<TranslationUnitDecl>() ==
634 ActiveASTContext->getTranslationUnitDecl())
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);
642 Key.MatcherID = Matcher.getID();
644 Key.BoundNodes = *Builder;
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;
654 MemoizedMatchResult Result;
655 Result.Nodes = *Builder;
656 Result.ResultOfMatch =
657 matchesAncestorOfRecursively(Node, Matcher, &Result.Nodes, MatchMode);
659 MemoizedMatchResult &CachedResult = ResultCache[Key];
660 CachedResult = std::move(Result);
662 *Builder = CachedResult.Nodes;
663 return CachedResult.ResultOfMatch;
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 assert(!Parents.empty() && "Found node that is not in the parent map.");
672 if (Parents.size() == 1) {
673 // Only one parent - do recursive memoization.
674 const ast_type_traits::DynTypedNode Parent = Parents[0];
675 BoundNodesTreeBuilder BuilderCopy = *Builder;
676 if (Matcher.matches(Parent, this, &BuilderCopy)) {
677 *Builder = std::move(BuilderCopy);
680 if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
681 return memoizedMatchesAncestorOfRecursively(Parent, Matcher, Builder,
683 // Once we get back from the recursive call, the result will be the
684 // same as the parent's result.
687 // Multiple parents - BFS over the rest of the nodes.
688 llvm::DenseSet<const void *> Visited;
689 std::deque<ast_type_traits::DynTypedNode> Queue(Parents.begin(),
691 while (!Queue.empty()) {
692 BoundNodesTreeBuilder BuilderCopy = *Builder;
693 if (Matcher.matches(Queue.front(), this, &BuilderCopy)) {
694 *Builder = std::move(BuilderCopy);
697 if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
698 for (const auto &Parent :
699 ActiveASTContext->getParents(Queue.front())) {
700 // Make sure we do not visit the same node twice.
701 // Otherwise, we'll visit the common ancestors as often as there
702 // are splits on the way down.
703 if (Visited.insert(Parent.getMemoizationData()).second)
704 Queue.push_back(Parent);
713 // Implements a BoundNodesTree::Visitor that calls a MatchCallback with
714 // the aggregated bound nodes for each match.
715 class MatchVisitor : public BoundNodesTreeBuilder::Visitor {
717 MatchVisitor(ASTContext* Context,
718 MatchFinder::MatchCallback* Callback)
720 Callback(Callback) {}
722 void visitMatch(const BoundNodes& BoundNodesView) override {
723 Callback->run(MatchFinder::MatchResult(BoundNodesView, Context));
728 MatchFinder::MatchCallback* Callback;
731 // Returns true if 'TypeNode' has an alias that matches the given matcher.
732 bool typeHasMatchingAlias(const Type *TypeNode,
733 const Matcher<NamedDecl> &Matcher,
734 BoundNodesTreeBuilder *Builder) {
735 const Type *const CanonicalType =
736 ActiveASTContext->getCanonicalType(TypeNode);
737 auto Aliases = TypeAliases.find(CanonicalType);
738 if (Aliases == TypeAliases.end())
740 for (const TypedefNameDecl *Alias : Aliases->second) {
741 BoundNodesTreeBuilder Result(*Builder);
742 if (Matcher.matches(*Alias, this, &Result)) {
743 *Builder = std::move(Result);
750 /// \brief Bucket to record map.
752 /// Used to get the appropriate bucket for each matcher.
753 llvm::StringMap<llvm::TimeRecord> TimeByBucket;
755 const MatchFinder::MatchersByType *Matchers;
757 /// \brief Filtered list of matcher indices for each matcher kind.
759 /// \c Decl and \c Stmt toplevel matchers usually apply to a specific node
760 /// kind (and derived kinds) so it is a waste to try every matcher on every
762 /// We precalculate a list of matchers that pass the toplevel restrict check.
763 /// This also allows us to skip the restrict check at matching time. See
764 /// use \c matchesNoKindCheck() above.
765 llvm::DenseMap<ast_type_traits::ASTNodeKind, std::vector<unsigned short>>
768 const MatchFinder::MatchFinderOptions &Options;
769 ASTContext *ActiveASTContext;
771 // Maps a canonical type to its TypedefDecls.
772 llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases;
774 // Maps (matcher, node) -> the match result for memoization.
775 typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap;
776 MemoizationMap ResultCache;
779 static CXXRecordDecl *
780 getAsCXXRecordDeclOrPrimaryTemplate(const Type *TypeNode) {
781 if (auto *RD = TypeNode->getAsCXXRecordDecl())
784 // Find the innermost TemplateSpecializationType that isn't an alias template.
785 auto *TemplateType = TypeNode->getAs<TemplateSpecializationType>();
786 while (TemplateType && TemplateType->isTypeAlias())
788 TemplateType->getAliasedType()->getAs<TemplateSpecializationType>();
790 // If this is the name of a (dependent) template specialization, use the
791 // definition of the template, even though it might be specialized later.
793 if (auto *ClassTemplate = dyn_cast_or_null<ClassTemplateDecl>(
794 TemplateType->getTemplateName().getAsTemplateDecl()))
795 return ClassTemplate->getTemplatedDecl();
800 // Returns true if the given class is directly or indirectly derived
801 // from a base type with the given name. A class is not considered to be
802 // derived from itself.
803 bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,
804 const Matcher<NamedDecl> &Base,
805 BoundNodesTreeBuilder *Builder) {
806 if (!Declaration->hasDefinition())
808 for (const auto &It : Declaration->bases()) {
809 const Type *TypeNode = It.getType().getTypePtr();
811 if (typeHasMatchingAlias(TypeNode, Base, Builder))
814 // FIXME: Going to the primary template here isn't really correct, but
815 // unfortunately we accept a Decl matcher for the base class not a Type
816 // matcher, so it's the best thing we can do with our current interface.
817 CXXRecordDecl *ClassDecl = getAsCXXRecordDeclOrPrimaryTemplate(TypeNode);
820 if (ClassDecl == Declaration) {
821 // This can happen for recursive template definitions; if the
822 // current declaration did not match, we can safely return false.
825 BoundNodesTreeBuilder Result(*Builder);
826 if (Base.matches(*ClassDecl, this, &Result)) {
827 *Builder = std::move(Result);
830 if (classIsDerivedFrom(ClassDecl, Base, Builder))
836 bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {
841 return RecursiveASTVisitor<MatchASTVisitor>::TraverseDecl(DeclNode);
844 bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode) {
849 return RecursiveASTVisitor<MatchASTVisitor>::TraverseStmt(StmtNode);
852 bool MatchASTVisitor::TraverseType(QualType TypeNode) {
854 return RecursiveASTVisitor<MatchASTVisitor>::TraverseType(TypeNode);
857 bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode) {
858 // The RecursiveASTVisitor only visits types if they're not within TypeLocs.
859 // We still want to find those types via matchers, so we match them here. Note
860 // that the TypeLocs are structurally a shadow-hierarchy to the expressed
861 // type, so we visit all involved parts of a compound type when matching on
864 match(TypeLocNode.getType());
865 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTypeLoc(TypeLocNode);
868 bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
870 return RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifier(NNS);
873 bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
874 NestedNameSpecifierLoc NNS) {
880 // We only match the nested name specifier here (as opposed to traversing it)
881 // because the traversal is already done in the parallel "Loc"-hierarchy.
882 if (NNS.hasQualifier())
883 match(*NNS.getNestedNameSpecifier());
885 RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifierLoc(NNS);
888 bool MatchASTVisitor::TraverseConstructorInitializer(
889 CXXCtorInitializer *CtorInit) {
895 return RecursiveASTVisitor<MatchASTVisitor>::TraverseConstructorInitializer(
899 class MatchASTConsumer : public ASTConsumer {
901 MatchASTConsumer(MatchFinder *Finder,
902 MatchFinder::ParsingDoneTestCallback *ParsingDone)
903 : Finder(Finder), ParsingDone(ParsingDone) {}
906 void HandleTranslationUnit(ASTContext &Context) override {
907 if (ParsingDone != nullptr) {
910 Finder->matchAST(Context);
914 MatchFinder::ParsingDoneTestCallback *ParsingDone;
918 } // end namespace internal
920 MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes,
922 : Nodes(Nodes), Context(Context),
923 SourceManager(&Context->getSourceManager()) {}
925 MatchFinder::MatchCallback::~MatchCallback() {}
926 MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {}
928 MatchFinder::MatchFinder(MatchFinderOptions Options)
929 : Options(std::move(Options)), ParsingDone(nullptr) {}
931 MatchFinder::~MatchFinder() {}
933 void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch,
934 MatchCallback *Action) {
935 Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
936 Matchers.AllCallbacks.insert(Action);
939 void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
940 MatchCallback *Action) {
941 Matchers.Type.emplace_back(NodeMatch, Action);
942 Matchers.AllCallbacks.insert(Action);
945 void MatchFinder::addMatcher(const StatementMatcher &NodeMatch,
946 MatchCallback *Action) {
947 Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
948 Matchers.AllCallbacks.insert(Action);
951 void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch,
952 MatchCallback *Action) {
953 Matchers.NestedNameSpecifier.emplace_back(NodeMatch, Action);
954 Matchers.AllCallbacks.insert(Action);
957 void MatchFinder::addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch,
958 MatchCallback *Action) {
959 Matchers.NestedNameSpecifierLoc.emplace_back(NodeMatch, Action);
960 Matchers.AllCallbacks.insert(Action);
963 void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch,
964 MatchCallback *Action) {
965 Matchers.TypeLoc.emplace_back(NodeMatch, Action);
966 Matchers.AllCallbacks.insert(Action);
969 void MatchFinder::addMatcher(const CXXCtorInitializerMatcher &NodeMatch,
970 MatchCallback *Action) {
971 Matchers.CtorInit.emplace_back(NodeMatch, Action);
972 Matchers.AllCallbacks.insert(Action);
975 bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch,
976 MatchCallback *Action) {
977 if (NodeMatch.canConvertTo<Decl>()) {
978 addMatcher(NodeMatch.convertTo<Decl>(), Action);
980 } else if (NodeMatch.canConvertTo<QualType>()) {
981 addMatcher(NodeMatch.convertTo<QualType>(), Action);
983 } else if (NodeMatch.canConvertTo<Stmt>()) {
984 addMatcher(NodeMatch.convertTo<Stmt>(), Action);
986 } else if (NodeMatch.canConvertTo<NestedNameSpecifier>()) {
987 addMatcher(NodeMatch.convertTo<NestedNameSpecifier>(), Action);
989 } else if (NodeMatch.canConvertTo<NestedNameSpecifierLoc>()) {
990 addMatcher(NodeMatch.convertTo<NestedNameSpecifierLoc>(), Action);
992 } else if (NodeMatch.canConvertTo<TypeLoc>()) {
993 addMatcher(NodeMatch.convertTo<TypeLoc>(), Action);
995 } else if (NodeMatch.canConvertTo<CXXCtorInitializer>()) {
996 addMatcher(NodeMatch.convertTo<CXXCtorInitializer>(), Action);
1002 std::unique_ptr<ASTConsumer> MatchFinder::newASTConsumer() {
1003 return llvm::make_unique<internal::MatchASTConsumer>(this, ParsingDone);
1006 void MatchFinder::match(const clang::ast_type_traits::DynTypedNode &Node,
1007 ASTContext &Context) {
1008 internal::MatchASTVisitor Visitor(&Matchers, Options);
1009 Visitor.set_active_ast_context(&Context);
1010 Visitor.match(Node);
1013 void MatchFinder::matchAST(ASTContext &Context) {
1014 internal::MatchASTVisitor Visitor(&Matchers, Options);
1015 Visitor.set_active_ast_context(&Context);
1016 Visitor.onStartOfTranslationUnit();
1017 Visitor.TraverseDecl(Context.getTranslationUnitDecl());
1018 Visitor.onEndOfTranslationUnit();
1021 void MatchFinder::registerTestCallbackAfterParsing(
1022 MatchFinder::ParsingDoneTestCallback *NewParsingDone) {
1023 ParsingDone = NewParsingDone;
1026 StringRef MatchFinder::MatchCallback::getID() const { return "<unknown>"; }
1028 } // end namespace ast_matchers
1029 } // end namespace clang