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"
27 namespace ast_matchers {
31 typedef MatchFinder::MatchCallback MatchCallback;
33 // The maximum number of memoization entries to store.
34 // 10k has been experimentally found to give a good trade-off
35 // of performance vs. memory consumption by running matcher
36 // that match on every statement over a very large codebase.
38 // FIXME: Do some performance optimization in general and
39 // revisit this number; also, put up micro-benchmarks that we can
41 static const unsigned MaxMemoizationEntries = 10000;
43 // We use memoization to avoid running the same matcher on the same
44 // AST node twice. This struct is the key for looking up match
45 // result. It consists of an ID of the MatcherInterface (for
46 // identifying the matcher), a pointer to the AST node and the
47 // bound nodes before the matcher was executed.
49 // We currently only memoize on nodes whose pointers identify the
50 // nodes (\c Stmt and \c Decl, but not \c QualType or \c TypeLoc).
51 // For \c QualType and \c TypeLoc it is possible to implement
52 // generation of keys for each type.
53 // FIXME: Benchmark whether memoization of non-pointer typed nodes
54 // provides enough benefit for the additional amount of code.
57 ast_type_traits::DynTypedNode Node;
58 BoundNodesTreeBuilder BoundNodes;
60 bool operator<(const MatchKey &Other) const {
61 if (MatcherID != Other.MatcherID)
62 return MatcherID < Other.MatcherID;
63 if (Node != Other.Node)
64 return Node < Other.Node;
65 return BoundNodes < Other.BoundNodes;
69 // Used to store the result of a match and possibly bound nodes.
70 struct MemoizedMatchResult {
72 BoundNodesTreeBuilder Nodes;
75 // A RecursiveASTVisitor that traverses all children or all descendants of
77 class MatchChildASTVisitor
78 : public RecursiveASTVisitor<MatchChildASTVisitor> {
80 typedef RecursiveASTVisitor<MatchChildASTVisitor> VisitorBase;
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,
90 ASTMatchFinder::TraversalKind Traversal,
91 ASTMatchFinder::BindKind Bind)
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):
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
112 bool findMatch(const ast_type_traits::DynTypedNode &DynNode) {
114 if (const Decl *D = DynNode.get<Decl>())
116 else if (const Stmt *S = DynNode.get<Stmt>())
118 else if (const NestedNameSpecifier *NNS =
119 DynNode.get<NestedNameSpecifier>())
121 else if (const NestedNameSpecifierLoc *NNSLoc =
122 DynNode.get<NestedNameSpecifierLoc>())
124 else if (const QualType *Q = DynNode.get<QualType>())
126 else if (const TypeLoc *T = DynNode.get<TypeLoc>())
128 // FIXME: Add other base types after adding tests.
130 // It's OK to always overwrite the bound nodes, as if there was
131 // no match in this recursive branch, the result set is empty
133 *Builder = ResultBindings;
138 // The following are overriding methods from the base visitor class.
139 // They are public only to allow CRTP to work. They are *not *part
140 // of the public API of this class.
141 bool TraverseDecl(Decl *DeclNode) {
142 ScopedIncrement ScopedDepth(&CurrentDepth);
143 return (DeclNode == NULL) || traverse(*DeclNode);
145 bool TraverseStmt(Stmt *StmtNode) {
146 ScopedIncrement ScopedDepth(&CurrentDepth);
147 const Stmt *StmtToTraverse = StmtNode;
149 ASTMatchFinder::TK_IgnoreImplicitCastsAndParentheses) {
150 const Expr *ExprNode = dyn_cast_or_null<Expr>(StmtNode);
151 if (ExprNode != NULL) {
152 StmtToTraverse = ExprNode->IgnoreParenImpCasts();
155 return (StmtToTraverse == NULL) || traverse(*StmtToTraverse);
157 // We assume that the QualType and the contained type are on the same
158 // hierarchy level. Thus, we try to match either of them.
159 bool TraverseType(QualType TypeNode) {
160 if (TypeNode.isNull())
162 ScopedIncrement ScopedDepth(&CurrentDepth);
164 if (!match(*TypeNode))
166 // The QualType is matched inside traverse.
167 return traverse(TypeNode);
169 // We assume that the TypeLoc, contained QualType and contained Type all are
170 // on the same hierarchy level. Thus, we try to match all of them.
171 bool TraverseTypeLoc(TypeLoc TypeLocNode) {
172 if (TypeLocNode.isNull())
174 ScopedIncrement ScopedDepth(&CurrentDepth);
176 if (!match(*TypeLocNode.getType()))
178 // Match the QualType.
179 if (!match(TypeLocNode.getType()))
181 // The TypeLoc is matched inside traverse.
182 return traverse(TypeLocNode);
184 bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
185 ScopedIncrement ScopedDepth(&CurrentDepth);
186 return (NNS == NULL) || traverse(*NNS);
188 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS) {
191 ScopedIncrement ScopedDepth(&CurrentDepth);
192 if (!match(*NNS.getNestedNameSpecifier()))
194 return traverse(NNS);
197 bool shouldVisitTemplateInstantiations() const { return true; }
198 bool shouldVisitImplicitCode() const { return true; }
199 // Disables data recursion. We intercept Traverse* methods in the RAV, which
200 // are not triggered during data recursion.
201 bool shouldUseDataRecursionFor(clang::Stmt *S) const { return false; }
204 // Used for updating the depth during traversal.
205 struct ScopedIncrement {
206 explicit ScopedIncrement(int *Depth) : Depth(Depth) { ++(*Depth); }
207 ~ScopedIncrement() { --(*Depth); }
213 // Resets the state of this object.
219 // Forwards the call to the corresponding Traverse*() method in the
220 // base visitor class.
221 bool baseTraverse(const Decl &DeclNode) {
222 return VisitorBase::TraverseDecl(const_cast<Decl*>(&DeclNode));
224 bool baseTraverse(const Stmt &StmtNode) {
225 return VisitorBase::TraverseStmt(const_cast<Stmt*>(&StmtNode));
227 bool baseTraverse(QualType TypeNode) {
228 return VisitorBase::TraverseType(TypeNode);
230 bool baseTraverse(TypeLoc TypeLocNode) {
231 return VisitorBase::TraverseTypeLoc(TypeLocNode);
233 bool baseTraverse(const NestedNameSpecifier &NNS) {
234 return VisitorBase::TraverseNestedNameSpecifier(
235 const_cast<NestedNameSpecifier*>(&NNS));
237 bool baseTraverse(NestedNameSpecifierLoc NNS) {
238 return VisitorBase::TraverseNestedNameSpecifierLoc(NNS);
241 // Sets 'Matched' to true if 'Matcher' matches 'Node' and:
242 // 0 < CurrentDepth <= MaxDepth.
244 // Returns 'true' if traversal should continue after this function
245 // returns, i.e. if no match is found or 'Bind' is 'BK_All'.
246 template <typename T>
247 bool match(const T &Node) {
248 if (CurrentDepth == 0 || CurrentDepth > MaxDepth) {
251 if (Bind != ASTMatchFinder::BK_All) {
252 BoundNodesTreeBuilder RecursiveBuilder(*Builder);
253 if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node), Finder,
254 &RecursiveBuilder)) {
256 ResultBindings.addMatch(RecursiveBuilder);
257 return false; // Abort as soon as a match is found.
260 BoundNodesTreeBuilder RecursiveBuilder(*Builder);
261 if (Matcher->matches(ast_type_traits::DynTypedNode::create(Node), Finder,
262 &RecursiveBuilder)) {
263 // After the first match the matcher succeeds.
265 ResultBindings.addMatch(RecursiveBuilder);
271 // Traverses the subtree rooted at 'Node'; returns true if the
272 // traversal should continue after this function returns.
273 template <typename T>
274 bool traverse(const T &Node) {
275 TOOLING_COMPILE_ASSERT(IsBaseType<T>::value,
276 traverse_can_only_be_instantiated_with_base_type);
279 return baseTraverse(Node);
282 const DynTypedMatcher *const Matcher;
283 ASTMatchFinder *const Finder;
284 BoundNodesTreeBuilder *const Builder;
285 BoundNodesTreeBuilder ResultBindings;
288 const ASTMatchFinder::TraversalKind Traversal;
289 const ASTMatchFinder::BindKind Bind;
293 // Controls the outermost traversal of the AST and allows to match multiple
295 class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>,
296 public ASTMatchFinder {
299 std::vector<std::pair<internal::DynTypedMatcher, MatchCallback *> > *
300 MatcherCallbackPairs)
301 : MatcherCallbackPairs(MatcherCallbackPairs), ActiveASTContext(NULL) {}
303 void onStartOfTranslationUnit() {
304 for (std::vector<std::pair<internal::DynTypedMatcher,
305 MatchCallback *> >::const_iterator
306 I = MatcherCallbackPairs->begin(),
307 E = MatcherCallbackPairs->end();
309 I->second->onStartOfTranslationUnit();
313 void onEndOfTranslationUnit() {
314 for (std::vector<std::pair<internal::DynTypedMatcher,
315 MatchCallback *> >::const_iterator
316 I = MatcherCallbackPairs->begin(),
317 E = MatcherCallbackPairs->end();
319 I->second->onEndOfTranslationUnit();
323 void set_active_ast_context(ASTContext *NewActiveASTContext) {
324 ActiveASTContext = NewActiveASTContext;
327 // The following Visit*() and Traverse*() functions "override"
328 // methods in RecursiveASTVisitor.
330 bool VisitTypedefNameDecl(TypedefNameDecl *DeclNode) {
331 // When we see 'typedef A B', we add name 'B' to the set of names
332 // A's canonical type maps to. This is necessary for implementing
333 // isDerivedFrom(x) properly, where x can be the name of the base
334 // class or any of its aliases.
336 // In general, the is-alias-of (as defined by typedefs) relation
337 // is tree-shaped, as you can typedef a type more than once. For
353 // It is wrong to assume that the relation is a chain. A correct
354 // implementation of isDerivedFrom() needs to recognize that B and
355 // E are aliases, even though neither is a typedef of the other.
356 // Therefore, we cannot simply walk through one typedef chain to
357 // find out whether the type name matches.
358 const Type *TypeNode = DeclNode->getUnderlyingType().getTypePtr();
359 const Type *CanonicalType = // root of the typedef tree
360 ActiveASTContext->getCanonicalType(TypeNode);
361 TypeAliases[CanonicalType].insert(DeclNode);
365 bool TraverseDecl(Decl *DeclNode);
366 bool TraverseStmt(Stmt *StmtNode);
367 bool TraverseType(QualType TypeNode);
368 bool TraverseTypeLoc(TypeLoc TypeNode);
369 bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS);
370 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS);
372 // Matches children or descendants of 'Node' with 'BaseMatcher'.
373 bool memoizedMatchesRecursively(const ast_type_traits::DynTypedNode &Node,
374 const DynTypedMatcher &Matcher,
375 BoundNodesTreeBuilder *Builder, int MaxDepth,
376 TraversalKind Traversal, BindKind Bind) {
377 // For AST-nodes that don't have an identity, we can't memoize.
378 if (!Node.getMemoizationData())
379 return matchesRecursively(Node, Matcher, Builder, MaxDepth, Traversal,
383 Key.MatcherID = Matcher.getID();
385 // Note that we key on the bindings *before* the match.
386 Key.BoundNodes = *Builder;
388 MemoizationMap::iterator I = ResultCache.find(Key);
389 if (I != ResultCache.end()) {
390 *Builder = I->second.Nodes;
391 return I->second.ResultOfMatch;
394 MemoizedMatchResult Result;
395 Result.Nodes = *Builder;
396 Result.ResultOfMatch = matchesRecursively(Node, Matcher, &Result.Nodes,
397 MaxDepth, Traversal, Bind);
398 ResultCache[Key] = Result;
399 *Builder = Result.Nodes;
400 return Result.ResultOfMatch;
403 // Matches children or descendants of 'Node' with 'BaseMatcher'.
404 bool matchesRecursively(const ast_type_traits::DynTypedNode &Node,
405 const DynTypedMatcher &Matcher,
406 BoundNodesTreeBuilder *Builder, int MaxDepth,
407 TraversalKind Traversal, BindKind Bind) {
408 MatchChildASTVisitor Visitor(
409 &Matcher, this, Builder, MaxDepth, Traversal, Bind);
410 return Visitor.findMatch(Node);
413 virtual bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
414 const Matcher<NamedDecl> &Base,
415 BoundNodesTreeBuilder *Builder);
417 // Implements ASTMatchFinder::matchesChildOf.
418 virtual bool matchesChildOf(const ast_type_traits::DynTypedNode &Node,
419 const DynTypedMatcher &Matcher,
420 BoundNodesTreeBuilder *Builder,
421 TraversalKind Traversal,
423 if (ResultCache.size() > MaxMemoizationEntries)
425 return memoizedMatchesRecursively(Node, Matcher, Builder, 1, Traversal,
428 // Implements ASTMatchFinder::matchesDescendantOf.
429 virtual bool matchesDescendantOf(const ast_type_traits::DynTypedNode &Node,
430 const DynTypedMatcher &Matcher,
431 BoundNodesTreeBuilder *Builder,
433 if (ResultCache.size() > MaxMemoizationEntries)
435 return memoizedMatchesRecursively(Node, Matcher, Builder, INT_MAX,
438 // Implements ASTMatchFinder::matchesAncestorOf.
439 virtual bool matchesAncestorOf(const ast_type_traits::DynTypedNode &Node,
440 const DynTypedMatcher &Matcher,
441 BoundNodesTreeBuilder *Builder,
442 AncestorMatchMode MatchMode) {
443 // Reset the cache outside of the recursive call to make sure we
444 // don't invalidate any iterators.
445 if (ResultCache.size() > MaxMemoizationEntries)
447 return memoizedMatchesAncestorOfRecursively(Node, Matcher, Builder,
451 // Matches all registered matchers on the given node and calls the
452 // result callback for every node that matches.
453 void match(const ast_type_traits::DynTypedNode& Node) {
454 for (std::vector<std::pair<internal::DynTypedMatcher,
455 MatchCallback *> >::const_iterator
456 I = MatcherCallbackPairs->begin(),
457 E = MatcherCallbackPairs->end();
459 BoundNodesTreeBuilder Builder;
460 if (I->first.matches(Node, this, &Builder)) {
461 MatchVisitor Visitor(ActiveASTContext, I->second);
462 Builder.visitMatches(&Visitor);
467 template <typename T> void match(const T &Node) {
468 match(ast_type_traits::DynTypedNode::create(Node));
471 // Implements ASTMatchFinder::getASTContext.
472 virtual ASTContext &getASTContext() const { return *ActiveASTContext; }
474 bool shouldVisitTemplateInstantiations() const { return true; }
475 bool shouldVisitImplicitCode() const { return true; }
476 // Disables data recursion. We intercept Traverse* methods in the RAV, which
477 // are not triggered during data recursion.
478 bool shouldUseDataRecursionFor(clang::Stmt *S) const { return false; }
481 // Returns whether an ancestor of \p Node matches \p Matcher.
483 // The order of matching ((which can lead to different nodes being bound in
484 // case there are multiple matches) is breadth first search.
486 // To allow memoization in the very common case of having deeply nested
487 // expressions inside a template function, we first walk up the AST, memoizing
488 // the result of the match along the way, as long as there is only a single
491 // Once there are multiple parents, the breadth first search order does not
492 // allow simple memoization on the ancestors. Thus, we only memoize as long
493 // as there is a single parent.
494 bool memoizedMatchesAncestorOfRecursively(
495 const ast_type_traits::DynTypedNode &Node, const DynTypedMatcher &Matcher,
496 BoundNodesTreeBuilder *Builder, AncestorMatchMode MatchMode) {
497 if (Node.get<TranslationUnitDecl>() ==
498 ActiveASTContext->getTranslationUnitDecl())
500 assert(Node.getMemoizationData() &&
501 "Invariant broken: only nodes that support memoization may be "
502 "used in the parent map.");
503 ASTContext::ParentVector Parents = ActiveASTContext->getParents(Node);
504 if (Parents.empty()) {
505 assert(false && "Found node that is not in the parent map.");
509 Key.MatcherID = Matcher.getID();
511 Key.BoundNodes = *Builder;
513 // Note that we cannot use insert and reuse the iterator, as recursive
514 // calls to match might invalidate the result cache iterators.
515 MemoizationMap::iterator I = ResultCache.find(Key);
516 if (I != ResultCache.end()) {
517 *Builder = I->second.Nodes;
518 return I->second.ResultOfMatch;
520 MemoizedMatchResult Result;
521 Result.ResultOfMatch = false;
522 Result.Nodes = *Builder;
523 if (Parents.size() == 1) {
524 // Only one parent - do recursive memoization.
525 const ast_type_traits::DynTypedNode Parent = Parents[0];
526 if (Matcher.matches(Parent, this, &Result.Nodes)) {
527 Result.ResultOfMatch = true;
528 } else if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
529 // Reset the results to not include the bound nodes from the failed
531 Result.Nodes = *Builder;
532 Result.ResultOfMatch = memoizedMatchesAncestorOfRecursively(
533 Parent, Matcher, &Result.Nodes, MatchMode);
534 // Once we get back from the recursive call, the result will be the
535 // same as the parent's result.
538 // Multiple parents - BFS over the rest of the nodes.
539 llvm::DenseSet<const void *> Visited;
540 std::deque<ast_type_traits::DynTypedNode> Queue(Parents.begin(),
542 while (!Queue.empty()) {
543 Result.Nodes = *Builder;
544 if (Matcher.matches(Queue.front(), this, &Result.Nodes)) {
545 Result.ResultOfMatch = true;
548 if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
549 ASTContext::ParentVector Ancestors =
550 ActiveASTContext->getParents(Queue.front());
551 for (ASTContext::ParentVector::const_iterator I = Ancestors.begin(),
554 // Make sure we do not visit the same node twice.
555 // Otherwise, we'll visit the common ancestors as often as there
556 // are splits on the way down.
557 if (Visited.insert(I->getMemoizationData()).second)
564 ResultCache[Key] = Result;
566 *Builder = Result.Nodes;
567 return Result.ResultOfMatch;
570 // Implements a BoundNodesTree::Visitor that calls a MatchCallback with
571 // the aggregated bound nodes for each match.
572 class MatchVisitor : public BoundNodesTreeBuilder::Visitor {
574 MatchVisitor(ASTContext* Context,
575 MatchFinder::MatchCallback* Callback)
577 Callback(Callback) {}
579 virtual void visitMatch(const BoundNodes& BoundNodesView) {
580 Callback->run(MatchFinder::MatchResult(BoundNodesView, Context));
585 MatchFinder::MatchCallback* Callback;
588 // Returns true if 'TypeNode' has an alias that matches the given matcher.
589 bool typeHasMatchingAlias(const Type *TypeNode,
590 const Matcher<NamedDecl> Matcher,
591 BoundNodesTreeBuilder *Builder) {
592 const Type *const CanonicalType =
593 ActiveASTContext->getCanonicalType(TypeNode);
594 const std::set<const TypedefNameDecl *> &Aliases =
595 TypeAliases[CanonicalType];
596 for (std::set<const TypedefNameDecl*>::const_iterator
597 It = Aliases.begin(), End = Aliases.end();
599 BoundNodesTreeBuilder Result(*Builder);
600 if (Matcher.matches(**It, this, &Result)) {
608 std::vector<std::pair<internal::DynTypedMatcher, MatchCallback *> > *const
609 MatcherCallbackPairs;
610 ASTContext *ActiveASTContext;
612 // Maps a canonical type to its TypedefDecls.
613 llvm::DenseMap<const Type*, std::set<const TypedefNameDecl*> > TypeAliases;
615 // Maps (matcher, node) -> the match result for memoization.
616 typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap;
617 MemoizationMap ResultCache;
620 static CXXRecordDecl *getAsCXXRecordDecl(const Type *TypeNode) {
621 // Type::getAs<...>() drills through typedefs.
622 if (TypeNode->getAs<DependentNameType>() != NULL ||
623 TypeNode->getAs<DependentTemplateSpecializationType>() != NULL ||
624 TypeNode->getAs<TemplateTypeParmType>() != NULL)
625 // Dependent names and template TypeNode parameters will be matched when
626 // the template is instantiated.
628 TemplateSpecializationType const *TemplateType =
629 TypeNode->getAs<TemplateSpecializationType>();
630 if (TemplateType == NULL) {
631 return TypeNode->getAsCXXRecordDecl();
633 if (TemplateType->getTemplateName().isDependent())
634 // Dependent template specializations will be matched when the
635 // template is instantiated.
638 // For template specialization types which are specializing a template
639 // declaration which is an explicit or partial specialization of another
640 // template declaration, getAsCXXRecordDecl() returns the corresponding
641 // ClassTemplateSpecializationDecl.
643 // For template specialization types which are specializing a template
644 // declaration which is neither an explicit nor partial specialization of
645 // another template declaration, getAsCXXRecordDecl() returns NULL and
646 // we get the CXXRecordDecl of the templated declaration.
647 CXXRecordDecl *SpecializationDecl = TemplateType->getAsCXXRecordDecl();
648 if (SpecializationDecl != NULL) {
649 return SpecializationDecl;
651 NamedDecl *Templated =
652 TemplateType->getTemplateName().getAsTemplateDecl()->getTemplatedDecl();
653 if (CXXRecordDecl *TemplatedRecord = dyn_cast<CXXRecordDecl>(Templated)) {
654 return TemplatedRecord;
656 // Now it can still be that we have an alias template.
657 TypeAliasDecl *AliasDecl = dyn_cast<TypeAliasDecl>(Templated);
659 return getAsCXXRecordDecl(AliasDecl->getUnderlyingType().getTypePtr());
662 // Returns true if the given class is directly or indirectly derived
663 // from a base type with the given name. A class is not considered to be
664 // derived from itself.
665 bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,
666 const Matcher<NamedDecl> &Base,
667 BoundNodesTreeBuilder *Builder) {
668 if (!Declaration->hasDefinition())
670 typedef CXXRecordDecl::base_class_const_iterator BaseIterator;
671 for (BaseIterator It = Declaration->bases_begin(),
672 End = Declaration->bases_end();
674 const Type *TypeNode = It->getType().getTypePtr();
676 if (typeHasMatchingAlias(TypeNode, Base, Builder))
679 CXXRecordDecl *ClassDecl = getAsCXXRecordDecl(TypeNode);
680 if (ClassDecl == NULL)
682 if (ClassDecl == Declaration) {
683 // This can happen for recursive template definitions; if the
684 // current declaration did not match, we can safely return false.
687 BoundNodesTreeBuilder Result(*Builder);
688 if (Base.matches(*ClassDecl, this, &Result)) {
692 if (classIsDerivedFrom(ClassDecl, Base, Builder))
698 bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {
699 if (DeclNode == NULL) {
703 return RecursiveASTVisitor<MatchASTVisitor>::TraverseDecl(DeclNode);
706 bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode) {
707 if (StmtNode == NULL) {
711 return RecursiveASTVisitor<MatchASTVisitor>::TraverseStmt(StmtNode);
714 bool MatchASTVisitor::TraverseType(QualType TypeNode) {
716 return RecursiveASTVisitor<MatchASTVisitor>::TraverseType(TypeNode);
719 bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLocNode) {
720 // The RecursiveASTVisitor only visits types if they're not within TypeLocs.
721 // We still want to find those types via matchers, so we match them here. Note
722 // that the TypeLocs are structurally a shadow-hierarchy to the expressed
723 // type, so we visit all involved parts of a compound type when matching on
726 match(TypeLocNode.getType());
727 return RecursiveASTVisitor<MatchASTVisitor>::TraverseTypeLoc(TypeLocNode);
730 bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) {
732 return RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifier(NNS);
735 bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
736 NestedNameSpecifierLoc NNS) {
738 // We only match the nested name specifier here (as opposed to traversing it)
739 // because the traversal is already done in the parallel "Loc"-hierarchy.
740 match(*NNS.getNestedNameSpecifier());
742 RecursiveASTVisitor<MatchASTVisitor>::TraverseNestedNameSpecifierLoc(NNS);
745 class MatchASTConsumer : public ASTConsumer {
747 MatchASTConsumer(MatchFinder *Finder,
748 MatchFinder::ParsingDoneTestCallback *ParsingDone)
749 : Finder(Finder), ParsingDone(ParsingDone) {}
752 virtual void HandleTranslationUnit(ASTContext &Context) {
753 if (ParsingDone != NULL) {
756 Finder->matchAST(Context);
760 MatchFinder::ParsingDoneTestCallback *ParsingDone;
764 } // end namespace internal
766 MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes,
768 : Nodes(Nodes), Context(Context),
769 SourceManager(&Context->getSourceManager()) {}
771 MatchFinder::MatchCallback::~MatchCallback() {}
772 MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {}
774 MatchFinder::MatchFinder() : ParsingDone(NULL) {}
776 MatchFinder::~MatchFinder() {}
778 void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch,
779 MatchCallback *Action) {
780 MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
783 void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
784 MatchCallback *Action) {
785 MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
788 void MatchFinder::addMatcher(const StatementMatcher &NodeMatch,
789 MatchCallback *Action) {
790 MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
793 void MatchFinder::addMatcher(const NestedNameSpecifierMatcher &NodeMatch,
794 MatchCallback *Action) {
795 MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
798 void MatchFinder::addMatcher(const NestedNameSpecifierLocMatcher &NodeMatch,
799 MatchCallback *Action) {
800 MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
803 void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch,
804 MatchCallback *Action) {
805 MatcherCallbackPairs.push_back(std::make_pair(NodeMatch, Action));
808 bool MatchFinder::addDynamicMatcher(const internal::DynTypedMatcher &NodeMatch,
809 MatchCallback *Action) {
810 if (NodeMatch.canConvertTo<Decl>()) {
811 addMatcher(NodeMatch.convertTo<Decl>(), Action);
813 } else if (NodeMatch.canConvertTo<QualType>()) {
814 addMatcher(NodeMatch.convertTo<QualType>(), Action);
816 } else if (NodeMatch.canConvertTo<Stmt>()) {
817 addMatcher(NodeMatch.convertTo<Stmt>(), Action);
819 } else if (NodeMatch.canConvertTo<NestedNameSpecifier>()) {
820 addMatcher(NodeMatch.convertTo<NestedNameSpecifier>(), Action);
822 } else if (NodeMatch.canConvertTo<NestedNameSpecifierLoc>()) {
823 addMatcher(NodeMatch.convertTo<NestedNameSpecifierLoc>(), Action);
825 } else if (NodeMatch.canConvertTo<TypeLoc>()) {
826 addMatcher(NodeMatch.convertTo<TypeLoc>(), Action);
832 ASTConsumer *MatchFinder::newASTConsumer() {
833 return new internal::MatchASTConsumer(this, ParsingDone);
836 void MatchFinder::match(const clang::ast_type_traits::DynTypedNode &Node,
837 ASTContext &Context) {
838 internal::MatchASTVisitor Visitor(&MatcherCallbackPairs);
839 Visitor.set_active_ast_context(&Context);
843 void MatchFinder::matchAST(ASTContext &Context) {
844 internal::MatchASTVisitor Visitor(&MatcherCallbackPairs);
845 Visitor.set_active_ast_context(&Context);
846 Visitor.onStartOfTranslationUnit();
847 Visitor.TraverseDecl(Context.getTranslationUnitDecl());
848 Visitor.onEndOfTranslationUnit();
851 void MatchFinder::registerTestCallbackAfterParsing(
852 MatchFinder::ParsingDoneTestCallback *NewParsingDone) {
853 ParsingDone = NewParsingDone;
856 } // end namespace ast_matchers
857 } // end namespace clang