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 // FIXME: Add other base types after adding tests.
131 // It's OK to always overwrite the bound nodes, as if there was
132 // no match in this recursive branch, the result set is empty
134 *Builder = ResultBindings;
139 // The following are overriding methods from the base visitor class.
140 // They are public only to allow CRTP to work. They are *not *part
141 // of the public API of this class.
142 bool TraverseDecl(Decl *DeclNode) {
143 ScopedIncrement ScopedDepth(&CurrentDepth);
144 return (DeclNode == nullptr) || traverse(*DeclNode);
146 bool TraverseStmt(Stmt *StmtNode) {
147 ScopedIncrement ScopedDepth(&CurrentDepth);
148 const Stmt *StmtToTraverse = StmtNode;
150 ASTMatchFinder::TK_IgnoreImplicitCastsAndParentheses) {
151 const Expr *ExprNode = dyn_cast_or_null<Expr>(StmtNode);
153 StmtToTraverse = ExprNode->IgnoreParenImpCasts();
156 return (StmtToTraverse == nullptr) || traverse(*StmtToTraverse);
158 // We assume that the QualType and the contained type are on the same
159 // hierarchy level. Thus, we try to match either of them.
160 bool TraverseType(QualType TypeNode) {
161 if (TypeNode.isNull())
163 ScopedIncrement ScopedDepth(&CurrentDepth);
165 if (!match(*TypeNode))
167 // The QualType is matched inside traverse.
168 return traverse(TypeNode);
170 // We assume that the TypeLoc, contained QualType and contained Type all are
171 // on the same hierarchy level. Thus, we try to match all of them.
172 bool TraverseTypeLoc(TypeLoc TypeLocNode) {
173 if (TypeLocNode.isNull())
175 ScopedIncrement ScopedDepth(&CurrentDepth);
177 if (!match(*TypeLocNode.getType()))
179 // Match the QualType.
180 if (!match(TypeLocNode.getType()))
182 // The TypeLoc is matched inside traverse.
183 return traverse(TypeLocNode);
185 bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
186 ScopedIncrement ScopedDepth(&CurrentDepth);
187 return (NNS == nullptr) || traverse(*NNS);
189 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS) {
192 ScopedIncrement ScopedDepth(&CurrentDepth);
193 if (!match(*NNS.getNestedNameSpecifier()))
195 return traverse(NNS);
198 bool shouldVisitTemplateInstantiations() const { return true; }
199 bool shouldVisitImplicitCode() const { return true; }
202 // Used for updating the depth during traversal.
203 struct ScopedIncrement {
204 explicit ScopedIncrement(int *Depth) : Depth(Depth) { ++(*Depth); }
205 ~ScopedIncrement() { --(*Depth); }
211 // Resets the state of this object.
217 // Forwards the call to the corresponding Traverse*() method in the
218 // base visitor class.
219 bool baseTraverse(const Decl &DeclNode) {
220 return VisitorBase::TraverseDecl(const_cast<Decl*>(&DeclNode));
222 bool baseTraverse(const Stmt &StmtNode) {
223 return VisitorBase::TraverseStmt(const_cast<Stmt*>(&StmtNode));
225 bool baseTraverse(QualType TypeNode) {
226 return VisitorBase::TraverseType(TypeNode);
228 bool baseTraverse(TypeLoc TypeLocNode) {
229 return VisitorBase::TraverseTypeLoc(TypeLocNode);
231 bool baseTraverse(const NestedNameSpecifier &NNS) {
232 return VisitorBase::TraverseNestedNameSpecifier(
233 const_cast<NestedNameSpecifier*>(&NNS));
235 bool baseTraverse(NestedNameSpecifierLoc NNS) {
236 return VisitorBase::TraverseNestedNameSpecifierLoc(NNS);
239 // Sets 'Matched' to true if 'Matcher' matches 'Node' and:
240 // 0 < CurrentDepth <= MaxDepth.
242 // Returns 'true' if traversal should continue after this function
243 // returns, i.e. if no match is found or 'Bind' is 'BK_All'.
244 template <typename T>
245 bool match(const T &Node) {
246 if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
249 if (Bind != ASTMatchFinder::BK_All) {
250 BoundNodesTreeBuilder RecursiveBuilder(*Builder);
251 if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node), Finder,
252 &RecursiveBuilder)) {
254 ResultBindings.addMatch(RecursiveBuilder);
255 return false; // Abort as soon as a match is found.
258 BoundNodesTreeBuilder RecursiveBuilder(*Builder);
259 if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node), Finder,
260 &RecursiveBuilder)) {
261 // After the first match the matcher succeeds.
263 ResultBindings.addMatch(RecursiveBuilder);
269 // Traverses the subtree rooted at 'Node'; returns true if the
270 // traversal should continue after this function returns.
271 template <typename T>
272 bool traverse(const T &Node) {
273 static_assert(IsBaseType<T>::value,
274 "traverse can only be instantiated with base type");
277 return baseTraverse(Node);
280 const DynTypedMatcher *const Matcher;
281 ASTMatchFinder *const Finder;
282 BoundNodesTreeBuilder *const Builder;
283 BoundNodesTreeBuilder ResultBindings;
286 const ASTMatchFinder::TraversalKind Traversal;
287 const ASTMatchFinder::BindKind Bind;
291 // Controls the outermost traversal of the AST and allows to match multiple
293 class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>,
294 public ASTMatchFinder {
296 MatchASTVisitor(const MatchFinder::MatchersByType *Matchers,
297 const MatchFinder::MatchFinderOptions &Options)
298 : Matchers(Matchers), Options(Options), ActiveASTContext(nullptr) {}
300 ~MatchASTVisitor() override {
301 if (Options.CheckProfiling) {
302 Options.CheckProfiling->Records = std::move(TimeByBucket);
306 void onStartOfTranslationUnit() {
307 const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
308 TimeBucketRegion Timer;
309 for (MatchCallback *MC : Matchers->AllCallbacks) {
310 if (EnableCheckProfiling)
311 Timer.setBucket(&TimeByBucket[MC->getID()]);
312 MC->onStartOfTranslationUnit();
316 void onEndOfTranslationUnit() {
317 const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
318 TimeBucketRegion Timer;
319 for (MatchCallback *MC : Matchers->AllCallbacks) {
320 if (EnableCheckProfiling)
321 Timer.setBucket(&TimeByBucket[MC->getID()]);
322 MC->onEndOfTranslationUnit();
326 void set_active_ast_context(ASTContext *NewActiveASTContext) {
327 ActiveASTContext = NewActiveASTContext;
330 // The following Visit*() and Traverse*() functions "override"
331 // methods in RecursiveASTVisitor.
333 bool VisitTypedefNameDecl(TypedefNameDecl *DeclNode) {
334 // When we see 'typedef A B', we add name 'B' to the set of names
335 // A's canonical type maps to. This is necessary for implementing
336 // isDerivedFrom(x) properly, where x can be the name of the base
337 // class or any of its aliases.
339 // In general, the is-alias-of (as defined by typedefs) relation
340 // is tree-shaped, as you can typedef a type more than once. For
356 // It is wrong to assume that the relation is a chain. A correct
357 // implementation of isDerivedFrom() needs to recognize that B and
358 // E are aliases, even though neither is a typedef of the other.
359 // Therefore, we cannot simply walk through one typedef chain to
360 // find out whether the type name matches.
361 const Type *TypeNode = DeclNode->getUnderlyingType().getTypePtr();
362 const Type *CanonicalType = // root of the typedef tree
363 ActiveASTContext->getCanonicalType(TypeNode);
364 TypeAliases[CanonicalType].insert(DeclNode);
368 bool TraverseDecl(Decl *DeclNode);
369 bool TraverseStmt(Stmt *StmtNode);
370 bool TraverseType(QualType TypeNode);
371 bool TraverseTypeLoc(TypeLoc TypeNode);
372 bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS);
373 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS);
375 // Matches children or descendants of 'Node' with 'BaseMatcher'.
376 bool memoizedMatchesRecursively(const ast_type_traits::DynTypedNode &Node,
377 const DynTypedMatcher &Matcher,
378 BoundNodesTreeBuilder *Builder, int MaxDepth,
379 TraversalKind Traversal, BindKind Bind) {
380 // For AST-nodes that don't have an identity, we can't memoize.
381 if (!Node.getMemoizationData() || !Builder->isComparable())
382 return matchesRecursively(Node, Matcher, Builder, MaxDepth, Traversal,
386 Key.MatcherID = Matcher.getID();
388 // Note that we key on the bindings *before* the match.
389 Key.BoundNodes = *Builder;
391 MemoizationMap::iterator I = ResultCache.find(Key);
392 if (I != ResultCache.end()) {
393 *Builder = I->second.Nodes;
394 return I->second.ResultOfMatch;
397 MemoizedMatchResult Result;
398 Result.Nodes = *Builder;
399 Result.ResultOfMatch = matchesRecursively(Node, Matcher, &Result.Nodes,
400 MaxDepth, Traversal, Bind);
402 MemoizedMatchResult &CachedResult = ResultCache[Key];
403 CachedResult = std::move(Result);
405 *Builder = CachedResult.Nodes;
406 return CachedResult.ResultOfMatch;
409 // Matches children or descendants of 'Node' with 'BaseMatcher'.
410 bool matchesRecursively(const ast_type_traits::DynTypedNode &Node,
411 const DynTypedMatcher &Matcher,
412 BoundNodesTreeBuilder *Builder, int MaxDepth,
413 TraversalKind Traversal, BindKind Bind) {
414 MatchChildASTVisitor Visitor(
415 &Matcher, this, Builder, MaxDepth, Traversal, Bind);
416 return Visitor.findMatch(Node);
419 bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
420 const Matcher<NamedDecl> &Base,
421 BoundNodesTreeBuilder *Builder) override;
423 // Implements ASTMatchFinder::matchesChildOf.
424 bool matchesChildOf(const ast_type_traits::DynTypedNode &Node,
425 const DynTypedMatcher &Matcher,
426 BoundNodesTreeBuilder *Builder,
427 TraversalKind Traversal,
428 BindKind Bind) override {
429 if (ResultCache.size() > MaxMemoizationEntries)
431 return memoizedMatchesRecursively(Node, Matcher, Builder, 1, Traversal,
434 // Implements ASTMatchFinder::matchesDescendantOf.
435 bool matchesDescendantOf(const ast_type_traits::DynTypedNode &Node,
436 const DynTypedMatcher &Matcher,
437 BoundNodesTreeBuilder *Builder,
438 BindKind Bind) override {
439 if (ResultCache.size() > MaxMemoizationEntries)
441 return memoizedMatchesRecursively(Node, Matcher, Builder, INT_MAX,
444 // Implements ASTMatchFinder::matchesAncestorOf.
445 bool matchesAncestorOf(const ast_type_traits::DynTypedNode &Node,
446 const DynTypedMatcher &Matcher,
447 BoundNodesTreeBuilder *Builder,
448 AncestorMatchMode MatchMode) override {
449 // Reset the cache outside of the recursive call to make sure we
450 // don't invalidate any iterators.
451 if (ResultCache.size() > MaxMemoizationEntries)
453 return memoizedMatchesAncestorOfRecursively(Node, Matcher, Builder,
457 // Matches all registered matchers on the given node and calls the
458 // result callback for every node that matches.
459 void match(const ast_type_traits::DynTypedNode &Node) {
460 // FIXME: Improve this with a switch or a visitor pattern.
461 if (auto *N = Node.get<Decl>()) {
463 } else if (auto *N = Node.get<Stmt>()) {
465 } else if (auto *N = Node.get<Type>()) {
467 } else if (auto *N = Node.get<QualType>()) {
469 } else if (auto *N = Node.get<NestedNameSpecifier>()) {
471 } else if (auto *N = Node.get<NestedNameSpecifierLoc>()) {
473 } else if (auto *N = Node.get<TypeLoc>()) {
478 template <typename T> void match(const T &Node) {
479 matchDispatch(&Node);
482 // Implements ASTMatchFinder::getASTContext.
483 ASTContext &getASTContext() const override { return *ActiveASTContext; }
485 bool shouldVisitTemplateInstantiations() const { return true; }
486 bool shouldVisitImplicitCode() const { return true; }
489 class TimeBucketRegion {
491 TimeBucketRegion() : Bucket(nullptr) {}
492 ~TimeBucketRegion() { setBucket(nullptr); }
494 /// \brief Start timing for \p NewBucket.
496 /// If there was a bucket already set, it will finish the timing for that
498 /// \p NewBucket will be timed until the next call to \c setBucket() or
499 /// until the \c TimeBucketRegion is destroyed.
500 /// If \p NewBucket is the same as the currently timed bucket, this call
502 void setBucket(llvm::TimeRecord *NewBucket) {
503 if (Bucket != NewBucket) {
504 auto Now = llvm::TimeRecord::getCurrentTime(true);
514 llvm::TimeRecord *Bucket;
517 /// \brief Runs all the \p Matchers on \p Node.
519 /// Used by \c matchDispatch() below.
520 template <typename T, typename MC>
521 void matchWithoutFilter(const T &Node, const MC &Matchers) {
522 const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
523 TimeBucketRegion Timer;
524 for (const auto &MP : Matchers) {
525 if (EnableCheckProfiling)
526 Timer.setBucket(&TimeByBucket[MP.second->getID()]);
527 BoundNodesTreeBuilder Builder;
528 if (MP.first.matches(Node, this, &Builder)) {
529 MatchVisitor Visitor(ActiveASTContext, MP.second);
530 Builder.visitMatches(&Visitor);
535 void matchWithFilter(const ast_type_traits::DynTypedNode &DynNode) {
536 auto Kind = DynNode.getNodeKind();
537 auto it = MatcherFiltersMap.find(Kind);
539 it != MatcherFiltersMap.end() ? it->second : getFilterForKind(Kind);
544 const bool EnableCheckProfiling = Options.CheckProfiling.hasValue();
545 TimeBucketRegion Timer;
546 auto &Matchers = this->Matchers->DeclOrStmt;
547 for (unsigned short I : Filter) {
548 auto &MP = Matchers[I];
549 if (EnableCheckProfiling)
550 Timer.setBucket(&TimeByBucket[MP.second->getID()]);
551 BoundNodesTreeBuilder Builder;
552 if (MP.first.matchesNoKindCheck(DynNode, this, &Builder)) {
553 MatchVisitor Visitor(ActiveASTContext, MP.second);
554 Builder.visitMatches(&Visitor);
559 const std::vector<unsigned short> &
560 getFilterForKind(ast_type_traits::ASTNodeKind Kind) {
561 auto &Filter = MatcherFiltersMap[Kind];
562 auto &Matchers = this->Matchers->DeclOrStmt;
563 assert((Matchers.size() < USHRT_MAX) && "Too many matchers.");
564 for (unsigned I = 0, E = Matchers.size(); I != E; ++I) {
565 if (Matchers[I].first.canMatchNodesOfKind(Kind)) {
573 /// \brief Overloads to pair the different node types to their matchers.
574 void matchDispatch(const Decl *Node) {
575 return matchWithFilter(ast_type_traits::DynTypedNode::create(*Node));
577 void matchDispatch(const Stmt *Node) {
578 return matchWithFilter(ast_type_traits::DynTypedNode::create(*Node));
581 void matchDispatch(const Type *Node) {
582 matchWithoutFilter(QualType(Node, 0), Matchers->Type);
584 void matchDispatch(const TypeLoc *Node) {
585 matchWithoutFilter(*Node, Matchers->TypeLoc);
587 void matchDispatch(const QualType *Node) {
588 matchWithoutFilter(*Node, Matchers->Type);
590 void matchDispatch(const NestedNameSpecifier *Node) {
591 matchWithoutFilter(*Node, Matchers->NestedNameSpecifier);
593 void matchDispatch(const NestedNameSpecifierLoc *Node) {
594 matchWithoutFilter(*Node, Matchers->NestedNameSpecifierLoc);
596 void matchDispatch(const void *) { /* Do nothing. */ }
599 // Returns whether an ancestor of \p Node matches \p Matcher.
601 // The order of matching ((which can lead to different nodes being bound in
602 // case there are multiple matches) is breadth first search.
604 // To allow memoization in the very common case of having deeply nested
605 // expressions inside a template function, we first walk up the AST, memoizing
606 // the result of the match along the way, as long as there is only a single
609 // Once there are multiple parents, the breadth first search order does not
610 // allow simple memoization on the ancestors. Thus, we only memoize as long
611 // as there is a single parent.
612 bool memoizedMatchesAncestorOfRecursively(
613 const ast_type_traits::DynTypedNode &Node, const DynTypedMatcher &Matcher,
614 BoundNodesTreeBuilder *Builder, AncestorMatchMode MatchMode) {
615 if (Node.get<TranslationUnitDecl>() ==
616 ActiveASTContext->getTranslationUnitDecl())
620 Key.MatcherID = Matcher.getID();
622 Key.BoundNodes = *Builder;
624 // Note that we cannot use insert and reuse the iterator, as recursive
625 // calls to match might invalidate the result cache iterators.
626 MemoizationMap::iterator I = ResultCache.find(Key);
627 if (I != ResultCache.end()) {
628 *Builder = I->second.Nodes;
629 return I->second.ResultOfMatch;
632 MemoizedMatchResult Result;
633 Result.ResultOfMatch = false;
634 Result.Nodes = *Builder;
636 const auto &Parents = ActiveASTContext->getParents(Node);
637 assert(!Parents.empty() && "Found node that is not in the parent map.");
638 if (Parents.size() == 1) {
639 // Only one parent - do recursive memoization.
640 const ast_type_traits::DynTypedNode Parent = Parents[0];
641 if (Matcher.matches(Parent, this, &Result.Nodes)) {
642 Result.ResultOfMatch = true;
643 } else if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
644 // Reset the results to not include the bound nodes from the failed
646 Result.Nodes = *Builder;
647 Result.ResultOfMatch = memoizedMatchesAncestorOfRecursively(
648 Parent, Matcher, &Result.Nodes, MatchMode);
649 // Once we get back from the recursive call, the result will be the
650 // same as the parent's result.
653 // Multiple parents - BFS over the rest of the nodes.
654 llvm::DenseSet<const void *> Visited;
655 std::deque<ast_type_traits::DynTypedNode> Queue(Parents.begin(),
657 while (!Queue.empty()) {
658 Result.Nodes = *Builder;
659 if (Matcher.matches(Queue.front(), this, &Result.Nodes)) {
660 Result.ResultOfMatch = true;
663 if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
664 for (const auto &Parent :
665 ActiveASTContext->getParents(Queue.front())) {
666 // Make sure we do not visit the same node twice.
667 // Otherwise, we'll visit the common ancestors as often as there
668 // are splits on the way down.
669 if (Visited.insert(Parent.getMemoizationData()).second)
670 Queue.push_back(Parent);
677 MemoizedMatchResult &CachedResult = ResultCache[Key];
678 CachedResult = std::move(Result);
680 *Builder = CachedResult.Nodes;
681 return CachedResult.ResultOfMatch;
684 // Implements a BoundNodesTree::Visitor that calls a MatchCallback with
685 // the aggregated bound nodes for each match.
686 class MatchVisitor : public BoundNodesTreeBuilder::Visitor {
688 MatchVisitor(ASTContext* Context,
689 MatchFinder::MatchCallback* Callback)
691 Callback(Callback) {}
693 void visitMatch(const BoundNodes& BoundNodesView) override {
694 Callback->run(MatchFinder::MatchResult(BoundNodesView, Context));
699 MatchFinder::MatchCallback* Callback;
702 // Returns true if 'TypeNode' has an alias that matches the given matcher.
703 bool typeHasMatchingAlias(const Type *TypeNode,
704 const Matcher<NamedDecl> Matcher,
705 BoundNodesTreeBuilder *Builder) {
706 const Type *const CanonicalType =
707 ActiveASTContext->getCanonicalType(TypeNode);
708 for (const TypedefNameDecl *Alias : TypeAliases.lookup(CanonicalType)) {
709 BoundNodesTreeBuilder Result(*Builder);
710 if (Matcher.matches(*Alias, this, &Result)) {
711 *Builder = std::move(Result);
718 /// \brief Bucket to record map.
720 /// Used to get the appropriate bucket for each matcher.
721 llvm::StringMap<llvm::TimeRecord> TimeByBucket;
723 const MatchFinder::MatchersByType *Matchers;
725 /// \brief Filtered list of matcher indices for each matcher kind.
727 /// \c Decl and \c Stmt toplevel matchers usually apply to a specific node
728 /// kind (and derived kinds) so it is a waste to try every matcher on every
730 /// We precalculate a list of matchers that pass the toplevel restrict check.
731 /// This also allows us to skip the restrict check at matching time. See
732 /// use \c matchesNoKindCheck() above.
733 llvm::DenseMap<ast_type_traits::ASTNodeKind, std::vector<unsigned short>>
736 const MatchFinder::MatchFinderOptions &Options;
737 ASTContext *ActiveASTContext;
739 // Maps a canonical type to its TypedefDecls.
740 llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases;
742 // Maps (matcher, node) -> the match result for memoization.
743 typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap;
744 MemoizationMap ResultCache;
747 static CXXRecordDecl *getAsCXXRecordDecl(const Type *TypeNode) {
748 // Type::getAs<...>() drills through typedefs.
749 if (TypeNode->getAs<DependentNameType>() != nullptr ||
750 TypeNode->getAs<DependentTemplateSpecializationType>() != nullptr ||
751 TypeNode->getAs<TemplateTypeParmType>() != nullptr)
752 // Dependent names and template TypeNode parameters will be matched when
753 // the template is instantiated.
755 TemplateSpecializationType const *TemplateType =
756 TypeNode->getAs<TemplateSpecializationType>();
758 return TypeNode->getAsCXXRecordDecl();
760 if (TemplateType->getTemplateName().isDependent())
761 // Dependent template specializations will be matched when the
762 // template is instantiated.
765 // For template specialization types which are specializing a template
766 // declaration which is an explicit or partial specialization of another
767 // template declaration, getAsCXXRecordDecl() returns the corresponding
768 // ClassTemplateSpecializationDecl.
770 // For template specialization types which are specializing a template
771 // declaration which is neither an explicit nor partial specialization of
772 // another template declaration, getAsCXXRecordDecl() returns NULL and
773 // we get the CXXRecordDecl of the templated declaration.
774 CXXRecordDecl *SpecializationDecl = TemplateType->getAsCXXRecordDecl();
775 if (SpecializationDecl) {
776 return SpecializationDecl;
778 NamedDecl *Templated =
779 TemplateType->getTemplateName().getAsTemplateDecl()->getTemplatedDecl();
780 if (CXXRecordDecl *TemplatedRecord = dyn_cast<CXXRecordDecl>(Templated)) {
781 return TemplatedRecord;
783 // Now it can still be that we have an alias template.
784 TypeAliasDecl *AliasDecl = dyn_cast<TypeAliasDecl>(Templated);
786 return getAsCXXRecordDecl(AliasDecl->getUnderlyingType().getTypePtr());
789 // Returns true if the given class is directly or indirectly derived
790 // from a base type with the given name. A class is not considered to be
791 // derived from itself.
792 bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,
793 const Matcher<NamedDecl> &Base,
794 BoundNodesTreeBuilder *Builder) {
795 if (!Declaration->hasDefinition())
797 for (const auto &It : Declaration->bases()) {
798 const Type *TypeNode = It.getType().getTypePtr();
800 if (typeHasMatchingAlias(TypeNode, Base, Builder))
803 CXXRecordDecl *ClassDecl = getAsCXXRecordDecl(TypeNode);
806 if (ClassDecl == Declaration) {
807 // This can happen for recursive template definitions; if the
808 // current declaration did not match, we can safely return false.
811 BoundNodesTreeBuilder Result(*Builder);
812 if (Base.matches(*ClassDecl, this, &Result)) {
813 *Builder = std::move(Result);
816 if (classIsDerivedFrom(ClassDecl, Base, Builder))
822 bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {
827 return RecursiveASTVisitor<MatchASTVisitor>::TraverseDecl(DeclNode);
830 bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode) {
835 return RecursiveASTVisitor<MatchASTVisitor>::TraverseStmt(StmtNode);
838 bool MatchASTVisitor::TraverseType(QualType TypeNode) {
840 return RecursiveASTVisitor<MatchASTVisitor>::TraverseType(TypeNode);
843 bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode) {
844 // The RecursiveASTVisitor only visits types if they're not within TypeLocs.
845 // We still want to find those types via matchers, so we match them here. Note
846 // that the TypeLocs are structurally a shadow-hierarchy to the expressed
847 // type, so we visit all involved parts of a compound type when matching on
850 match(TypeLocNode.getType());
851 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTypeLoc(TypeLocNode);
854 bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
856 return RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifier(NNS);
859 bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
860 NestedNameSpecifierLoc NNS) {
866 // We only match the nested name specifier here (as opposed to traversing it)
867 // because the traversal is already done in the parallel "Loc"-hierarchy.
868 if (NNS.hasQualifier())
869 match(*NNS.getNestedNameSpecifier());
871 RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifierLoc(NNS);
874 class MatchASTConsumer : public ASTConsumer {
876 MatchASTConsumer(MatchFinder *Finder,
877 MatchFinder::ParsingDoneTestCallback *ParsingDone)
878 : Finder(Finder), ParsingDone(ParsingDone) {}
881 void HandleTranslationUnit(ASTContext &Context) override {
882 if (ParsingDone != nullptr) {
885 Finder->matchAST(Context);
889 MatchFinder::ParsingDoneTestCallback *ParsingDone;
893 } // end namespace internal
895 MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes,
897 : Nodes(Nodes), Context(Context),
898 SourceManager(&Context->getSourceManager()) {}
900 MatchFinder::MatchCallback::~MatchCallback() {}
901 MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {}
903 MatchFinder::MatchFinder(MatchFinderOptions Options)
904 : Options(std::move(Options)), ParsingDone(nullptr) {}
906 MatchFinder::~MatchFinder() {}
908 void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch,
909 MatchCallback *Action) {
910 Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
911 Matchers.AllCallbacks.insert(Action);
914 void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
915 MatchCallback *Action) {
916 Matchers.Type.emplace_back(NodeMatch, Action);
917 Matchers.AllCallbacks.insert(Action);
920 void MatchFinder::addMatcher(const StatementMatcher &NodeMatch,
921 MatchCallback *Action) {
922 Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
923 Matchers.AllCallbacks.insert(Action);
926 void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch,
927 MatchCallback *Action) {
928 Matchers.NestedNameSpecifier.emplace_back(NodeMatch, Action);
929 Matchers.AllCallbacks.insert(Action);
932 void MatchFinder::addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch,
933 MatchCallback *Action) {
934 Matchers.NestedNameSpecifierLoc.emplace_back(NodeMatch, Action);
935 Matchers.AllCallbacks.insert(Action);
938 void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch,
939 MatchCallback *Action) {
940 Matchers.TypeLoc.emplace_back(NodeMatch, Action);
941 Matchers.AllCallbacks.insert(Action);
944 bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch,
945 MatchCallback *Action) {
946 if (NodeMatch.canConvertTo<Decl>()) {
947 addMatcher(NodeMatch.convertTo<Decl>(), Action);
949 } else if (NodeMatch.canConvertTo<QualType>()) {
950 addMatcher(NodeMatch.convertTo<QualType>(), Action);
952 } else if (NodeMatch.canConvertTo<Stmt>()) {
953 addMatcher(NodeMatch.convertTo<Stmt>(), Action);
955 } else if (NodeMatch.canConvertTo<NestedNameSpecifier>()) {
956 addMatcher(NodeMatch.convertTo<NestedNameSpecifier>(), Action);
958 } else if (NodeMatch.canConvertTo<NestedNameSpecifierLoc>()) {
959 addMatcher(NodeMatch.convertTo<NestedNameSpecifierLoc>(), Action);
961 } else if (NodeMatch.canConvertTo<TypeLoc>()) {
962 addMatcher(NodeMatch.convertTo<TypeLoc>(), Action);
968 std::unique_ptr<ASTConsumer> MatchFinder::newASTConsumer() {
969 return llvm::make_unique<internal::MatchASTConsumer>(this, ParsingDone);
972 void MatchFinder::match(const clang::ast_type_traits::DynTypedNode &Node,
973 ASTContext &Context) {
974 internal::MatchASTVisitor Visitor(&Matchers, Options);
975 Visitor.set_active_ast_context(&Context);
979 void MatchFinder::matchAST(ASTContext &Context) {
980 internal::MatchASTVisitor Visitor(&Matchers, Options);
981 Visitor.set_active_ast_context(&Context);
982 Visitor.onStartOfTranslationUnit();
983 Visitor.TraverseDecl(Context.getTranslationUnitDecl());
984 Visitor.onEndOfTranslationUnit();
987 void MatchFinder::registerTestCallbackAfterParsing(
988 MatchFinder::ParsingDoneTestCallback *NewParsingDone) {
989 ParsingDone = NewParsingDone;
992 StringRef MatchFinder::MatchCallback::getID() const { return "<unknown>"; }
994 } // end namespace ast_matchers
995 } // end namespace clang