From 579b120038ca817e0ce423303ebc1b4e0c6cbbe1 Mon Sep 17 00:00:00 2001 From: Manuel Klimek Date: Fri, 7 Sep 2012 09:26:10 +0000 Subject: [PATCH] Implements hasAncestor. Implements the hasAncestor matcher. This builds on the previous patch that introduced DynTypedNode to build up a parent map for an additional degree of freedom in the AST traversal. The map is only built once we hit an hasAncestor matcher, in order to not slow down matching for cases where this is not needed. We could implement some speed-ups for special cases, like building up the parent map as we go and only building up the full map if we break out of the already visited part of the tree, but that is probably not going to be worth it, and would make the code significantly more complex. Major TODOs are: - implement hasParent - implement type traversal - implement memoization in hasAncestor git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@163382 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/clang/ASTMatchers/ASTMatchers.h | 20 +++- .../clang/ASTMatchers/ASTMatchersInternal.h | 54 +++++++++- lib/ASTMatchers/ASTMatchFinder.cpp | 87 ++++++++++++++++ unittests/ASTMatchers/ASTMatchersTest.cpp | 99 +++++++++++++++++-- 4 files changed, 245 insertions(+), 15 deletions(-) diff --git a/include/clang/ASTMatchers/ASTMatchers.h b/include/clang/ASTMatchers/ASTMatchers.h index 54a0e02e13..23743e529b 100644 --- a/include/clang/ASTMatchers/ASTMatchers.h +++ b/include/clang/ASTMatchers/ASTMatchers.h @@ -1179,7 +1179,6 @@ hasDescendant(const internal::Matcher &DescendantMatcher) { DescendantT>(DescendantMatcher); } - /// \brief Matches AST nodes that have child AST nodes that match the /// provided matcher. /// @@ -1237,6 +1236,25 @@ forEachDescendant( DescendantT>(DescendantMatcher); } +/// \brief Matches AST nodes that have an ancestor that matches the provided +/// matcher. +/// +/// Given +/// \code +/// void f() { if (true) { int x = 42; } } +/// void g() { for (;;) { int x = 43; } } +/// \endcode +/// \c expr(integerLiteral(hasAncsestor(ifStmt()))) matches \c 42, but not 43. +/// +/// Usable as: Any Matcher +template +internal::ArgumentAdaptingMatcher +hasAncestor(const internal::Matcher &AncestorMatcher) { + return internal::ArgumentAdaptingMatcher< + internal::HasAncestorMatcher, + AncestorT>(AncestorMatcher); +} + /// \brief Matches if the provided matcher does not match. /// /// Example matches Y (matcher = recordDecl(unless(hasName("X")))) diff --git a/include/clang/ASTMatchers/ASTMatchersInternal.h b/include/clang/ASTMatchers/ASTMatchersInternal.h index 36831e6f11..2a49b63c83 100644 --- a/include/clang/ASTMatchers/ASTMatchersInternal.h +++ b/include/clang/ASTMatchers/ASTMatchersInternal.h @@ -388,13 +388,21 @@ const bool IsBaseType::value; /// \brief Interface that allows matchers to traverse the AST. /// FIXME: Find a better name. /// -/// This provides two entry methods for each base node type in the AST: -/// - matchesChildOf: +/// This provides three entry methods for each base node type in the AST: +/// - \c matchesChildOf: /// Matches a matcher on every child node of the given node. Returns true /// if at least one child node could be matched. -/// - matchesDescendantOf: +/// - \c matchesDescendantOf: /// Matches a matcher on all descendant nodes of the given node. Returns true /// if at least one descendant matched. +/// - \c matchesAncestorOf: +/// Matches a matcher on all ancestors of the given node. Returns true if +/// at least one ancestor matched. +/// +/// FIXME: Currently we only allow Stmt and Decl nodes to start a traversal. +/// In the future, we wan to implement this for all nodes for which it makes +/// sense. In the case of matchesAncestorOf, we'll want to implement it for +/// all nodes, as all nodes have ancestors. class ASTMatchFinder { public: /// \brief Defines how we descend a level in the AST when we pass @@ -449,8 +457,19 @@ public: Matcher, Builder, Bind); } + // FIXME: Implement support for BindKind. + template + bool matchesAncestorOf(const T &Node, + const DynTypedMatcher &Matcher, + BoundNodesTreeBuilder *Builder) { + TOOLING_COMPILE_ASSERT((llvm::is_base_of::value || + llvm::is_base_of::value), + only_Decl_or_Stmt_allowed_for_recursive_matching); + return matchesAncestorOf(ast_type_traits::DynTypedNode::create(Node), + Matcher, Builder); + } + protected: - // FIXME: Implement for other base nodes. virtual bool matchesChildOf(const ast_type_traits::DynTypedNode &Node, const DynTypedMatcher &Matcher, BoundNodesTreeBuilder *Builder, @@ -461,6 +480,10 @@ protected: const DynTypedMatcher &Matcher, BoundNodesTreeBuilder *Builder, BindKind Bind) = 0; + + virtual bool matchesAncestorOf(const ast_type_traits::DynTypedNode &Node, + const DynTypedMatcher &Matcher, + BoundNodesTreeBuilder *Builder) = 0; }; /// \brief Converts a \c Matcher to a matcher of desired type \c To by @@ -801,6 +824,29 @@ public: const Matcher DescendantMatcher; }; +/// \brief Matches nodes of type \c T that have at least one ancestor node of +/// type \c AncestorT for which the given inner matcher matches. +/// +/// \c AncestorT must be an AST base type. +template +class HasAncestorMatcher : public MatcherInterface { + TOOLING_COMPILE_ASSERT(IsBaseType::value, + has_ancestor_only_accepts_base_type_matcher); +public: + explicit HasAncestorMatcher(const Matcher &AncestorMatcher) + : AncestorMatcher(AncestorMatcher) {} + + virtual bool matches(const T &Node, + ASTMatchFinder *Finder, + BoundNodesTreeBuilder *Builder) const { + return Finder->matchesAncestorOf( + Node, AncestorMatcher, Builder); + } + + private: + const Matcher AncestorMatcher; +}; + /// \brief Matches nodes of type T that have at least one descendant node of /// type DescendantT for which the given inner matcher matches. /// diff --git a/lib/ASTMatchers/ASTMatchFinder.cpp b/lib/ASTMatchers/ASTMatchFinder.cpp index 8f28c385b9..54b05b3939 100644 --- a/lib/ASTMatchers/ASTMatchFinder.cpp +++ b/lib/ASTMatchers/ASTMatchFinder.cpp @@ -29,6 +29,62 @@ namespace { typedef MatchFinder::MatchCallback MatchCallback; +/// \brief A \c RecursiveASTVisitor that builds a map from nodes to their +/// parents as defined by the \c RecursiveASTVisitor. +/// +/// Note that the relationship described here is purely in terms of AST +/// traversal - there are other relationships (for example declaration context) +/// in the AST that are better modeled by special matchers. +/// +/// FIXME: Currently only builds up the map using \c Stmt and \c Decl nodes. +class ParentMapASTVisitor : public RecursiveASTVisitor { +public: + /// \brief Maps from a node to its parent. + typedef llvm::DenseMap ParentMap; + + /// \brief Builds and returns the translation unit's parent map. + /// + /// The caller takes ownership of the returned \c ParentMap. + static ParentMap *buildMap(TranslationUnitDecl &TU) { + ParentMapASTVisitor Visitor(new ParentMap); + Visitor.TraverseDecl(&TU); + return Visitor.Parents; + } + +private: + typedef RecursiveASTVisitor VisitorBase; + + ParentMapASTVisitor(ParentMap *Parents) : Parents(Parents) {} + + bool shouldVisitTemplateInstantiations() const { return true; } + bool shouldVisitImplicitCode() const { return true; } + + template + bool TraverseNode(T *Node, bool (VisitorBase::*traverse)(T*)) { + if (Node == NULL) + return true; + if (ParentStack.size() > 0) + (*Parents)[Node] = ParentStack.back(); + ParentStack.push_back(ast_type_traits::DynTypedNode::create(*Node)); + bool Result = (this->*traverse)(Node); + ParentStack.pop_back(); + return Result; + } + + bool TraverseDecl(Decl *DeclNode) { + return TraverseNode(DeclNode, &VisitorBase::TraverseDecl); + } + + bool TraverseStmt(Stmt *StmtNode) { + return TraverseNode(StmtNode, &VisitorBase::TraverseStmt); + } + + ParentMap *Parents; + llvm::SmallVector ParentStack; + + friend class RecursiveASTVisitor; +}; + // We use memoization to avoid running the same matcher on the same // AST node twice. This pair is the key for looking up match // result. It consists of an ID of the MatcherInterface (for @@ -311,6 +367,35 @@ public: return memoizedMatchesRecursively(Node, Matcher, Builder, INT_MAX, TK_AsIs, Bind); } + // Implements ASTMatchFinder::matchesAncestorOf. + virtual bool matchesAncestorOf(const ast_type_traits::DynTypedNode &Node, + const DynTypedMatcher &Matcher, + BoundNodesTreeBuilder *Builder) { + if (!Parents) { + // We always need to run over the whole translation unit, as + // \c hasAncestor can escape any subtree. + Parents.reset(ParentMapASTVisitor::buildMap( + *ActiveASTContext->getTranslationUnitDecl())); + } + ast_type_traits::DynTypedNode Ancestor = Node; + while (Ancestor.get() != + ActiveASTContext->getTranslationUnitDecl()) { + assert(Ancestor.getMemoizationData() && + "Invariant broken: only nodes that support memoization may be " + "used in the parent map."); + ParentMapASTVisitor::ParentMap::const_iterator I = + Parents->find(Ancestor.getMemoizationData()); + if (I == Parents->end()) { + assert(false && + "Found node that is not in the parent map."); + return false; + } + Ancestor = I->second; + if (Matcher.matches(Ancestor, this, Builder)) + return true; + } + return false; + } bool shouldVisitTemplateInstantiations() const { return true; } bool shouldVisitImplicitCode() const { return true; } @@ -378,6 +463,8 @@ private: // Maps (matcher, node) -> the match result for memoization. typedef llvm::DenseMap MemoizationMap; MemoizationMap ResultCache; + + llvm::OwningPtr Parents; }; // Returns true if the given class is directly or indirectly derived diff --git a/unittests/ASTMatchers/ASTMatchersTest.cpp b/unittests/ASTMatchers/ASTMatchersTest.cpp index 86e949fef4..7adc71837d 100644 --- a/unittests/ASTMatchers/ASTMatchersTest.cpp +++ b/unittests/ASTMatchers/ASTMatchersTest.cpp @@ -597,31 +597,41 @@ TEST(TypeMatcher, MatchesClassType) { matches("class A { public: A *a; class B {}; };", TypeAHasClassB)); } -// Returns from Run whether 'bound_nodes' contain a Decl bound to 'Id', which -// can be dynamically casted to T. +// Implements a run method that returns whether BoundNodes contains a +// Decl bound to Id that can be dynamically cast to T. // Optionally checks that the check succeeded a specific number of times. template class VerifyIdIsBoundToDecl : public BoundNodesCallback { public: - // Create an object that checks that a node of type 'T' was bound to 'Id'. + // Create an object that checks that a node of type \c T was bound to \c Id. // Does not check for a certain number of matches. - explicit VerifyIdIsBoundToDecl(const std::string& Id) + explicit VerifyIdIsBoundToDecl(llvm::StringRef Id) : Id(Id), ExpectedCount(-1), Count(0) {} - // Create an object that checks that a node of type 'T' was bound to 'Id'. - // Checks that there were exactly 'ExpectedCount' matches. - explicit VerifyIdIsBoundToDecl(const std::string& Id, int ExpectedCount) + // Create an object that checks that a node of type \c T was bound to \c Id. + // Checks that there were exactly \c ExpectedCount matches. + VerifyIdIsBoundToDecl(llvm::StringRef Id, int ExpectedCount) : Id(Id), ExpectedCount(ExpectedCount), Count(0) {} + // Create an object that checks that a node of type \c T was bound to \c Id. + // Checks that there was exactly one match with the name \c ExpectedDeclName. + // Note that \c T must be a NamedDecl for this to work. + VerifyIdIsBoundToDecl(llvm::StringRef Id, llvm::StringRef ExpectedDeclName) + : Id(Id), ExpectedCount(1), Count(0), ExpectedDeclName(ExpectedDeclName) {} + ~VerifyIdIsBoundToDecl() { - if (ExpectedCount != -1) { + if (ExpectedCount != -1) EXPECT_EQ(ExpectedCount, Count); - } + if (!ExpectedDeclName.empty()) + EXPECT_EQ(ExpectedDeclName, DeclName); } virtual bool run(const BoundNodes *Nodes) { - if (Nodes->getDeclAs(Id) != NULL) { + if (const Decl *Node = Nodes->getDeclAs(Id)) { ++Count; + if (const NamedDecl *Named = llvm::dyn_cast(Node)) { + DeclName = Named->getNameAsString(); + } return true; } return false; @@ -631,6 +641,8 @@ private: const std::string Id; const int ExpectedCount; int Count; + const std::string ExpectedDeclName; + std::string DeclName; }; template class VerifyIdIsBoundToStmt : public BoundNodesCallback { @@ -2721,5 +2733,72 @@ TEST(IsExplicitTemplateSpecialization, functionDecl(isExplicitTemplateSpecialization()))); } +TEST(HasAncenstor, MatchesDeclarationAncestors) { + EXPECT_TRUE(matches( + "class A { class B { class C {}; }; };", + recordDecl(hasName("C"), hasAncestor(recordDecl(hasName("A")))))); +} + +TEST(HasAncenstor, FailsIfNoAncestorMatches) { + EXPECT_TRUE(notMatches( + "class A { class B { class C {}; }; };", + recordDecl(hasName("C"), hasAncestor(recordDecl(hasName("X")))))); +} + +TEST(HasAncestor, MatchesDeclarationsThatGetVisitedLater) { + EXPECT_TRUE(matches( + "class A { class B { void f() { C c; } class C {}; }; };", + varDecl(hasName("c"), hasType(recordDecl(hasName("C"), + hasAncestor(recordDecl(hasName("A")))))))); +} + +TEST(HasAncenstor, MatchesStatementAncestors) { + EXPECT_TRUE(matches( + "void f() { if (true) { while (false) { 42; } } }", + expr(integerLiteral(equals(42), hasAncestor(ifStmt()))))); +} + +TEST(HasAncestor, DrillsThroughDifferentHierarchies) { + EXPECT_TRUE(matches( + "void f() { if (true) { int x = 42; } }", + expr(integerLiteral( + equals(42), hasAncestor(functionDecl(hasName("f"))))))); +} + +TEST(HasAncestor, BindsRecursiveCombinations) { + EXPECT_TRUE(matchAndVerifyResultTrue( + "class C { class D { class E { class F { int y; }; }; }; };", + fieldDecl(hasAncestor(recordDecl(hasAncestor(recordDecl().bind("r"))))), + new VerifyIdIsBoundToDecl("r", 1))); +} + +TEST(HasAncestor, BindsCombinationsWithHasDescendant) { + EXPECT_TRUE(matchAndVerifyResultTrue( + "class C { class D { class E { class F { int y; }; }; }; };", + fieldDecl(hasAncestor( + decl( + hasDescendant(recordDecl(isDefinition(), + hasAncestor(recordDecl()))) + ).bind("d") + )), + new VerifyIdIsBoundToDecl("d", "E"))); +} + +TEST(HasAncestor, MatchesInTemplateInstantiations) { + EXPECT_TRUE(matches( + "template struct A { struct B { struct C { T t; }; }; }; " + "A::B::C a;", + fieldDecl(hasType(asString("int")), + hasAncestor(recordDecl(hasName("A")))))); +} + +TEST(HasAncestor, MatchesInImplicitCode) { + EXPECT_TRUE(matches( + "struct X {}; struct A { A() {} X x; };", + constructorDecl( + hasAnyConstructorInitializer(withInitializer(expr( + hasAncestor(recordDecl(hasName("A"))))))))); +} + } // end namespace ast_matchers } // end namespace clang -- 2.40.0