Hi djasper, mdiamond,
A first shot at implementing the hasAncestor matcher. This builds
on the previous patch that introduced DynTypedNode to build up
a parent map for an dditional 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.
http://llvm-reviews.chandlerc.com/D36
Files:
include/clang/ASTMatchers/ASTMatchers.h
include/clang/ASTMatchers/ASTMatchersInternal.h
include/clang/ASTMatchers/ASTTypeTraits.h
lib/ASTMatchers/ASTMatchFinder.cpp
unittests/ASTMatchers/ASTMatchersTest.cpp
Index: include/clang/ASTMatchers/ASTMatchers.h
===================================================================
--- include/clang/ASTMatchers/ASTMatchers.h
+++ include/clang/ASTMatchers/ASTMatchers.h
@@ -1179,7 +1179,6 @@
DescendantT>(DescendantMatcher);
}
-
/// \brief Matches AST nodes that have child AST nodes that match the
/// provided matcher.
///
@@ -1237,6 +1236,25 @@
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 <typename AncestorT>
+internal::ArgumentAdaptingMatcher<internal::HasAncestorMatcher, AncestorT>
+hasAncestor(const internal::Matcher<AncestorT> &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"))))
Index: include/clang/ASTMatchers/ASTMatchersInternal.h
===================================================================
--- include/clang/ASTMatchers/ASTMatchersInternal.h
+++ include/clang/ASTMatchers/ASTMatchersInternal.h
@@ -395,6 +395,9 @@
/// - matchesDescendantOf:
/// Matches a matcher on all descendant nodes of the given node. Returns true
/// if at least one descendant matched.
+/// - matchesAncestorOf:
+/// Matches a matcher on all ancestors of the given node. Returns true if
+/// at least one ancestor matched.
class ASTMatchFinder {
public:
/// \brief Defines how we descend a level in the AST when we pass
@@ -449,8 +452,18 @@
Matcher, Builder, Bind);
}
+ template <typename T>
+ bool matchesAncestorOf(const T &Node,
+ const DynTypedMatcher &Matcher,
+ BoundNodesTreeBuilder *Builder) {
+ TOOLING_COMPILE_ASSERT((llvm::is_base_of<Decl, T>::value ||
+ llvm::is_base_of<Stmt, T>::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 +474,10 @@
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<T> to a matcher of desired type \c To by
@@ -801,6 +818,29 @@
const Matcher<DescendantT> 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 <typename T, typename AncestorT>
+class HasAncestorMatcher : public MatcherInterface<T> {
+ TOOLING_COMPILE_ASSERT(IsBaseType<AncestorT>::value,
+ has_descendant_only_accepts_base_type_matcher);
+public:
+ explicit HasAncestorMatcher(const Matcher<AncestorT> &AncestorMatcher)
+ : AncestorMatcher(AncestorMatcher) {}
+
+ virtual bool matches(const T &Node,
+ ASTMatchFinder *Finder,
+ BoundNodesTreeBuilder *Builder) const {
+ return Finder->matchesAncestorOf(
+ Node, AncestorMatcher, Builder);
+ }
+
+ private:
+ const Matcher<AncestorT> AncestorMatcher;
+};
+
/// \brief Matches nodes of type T that have at least one descendant node of
/// type DescendantT for which the given inner matcher matches.
///
Index: include/clang/ASTMatchers/ASTTypeTraits.h
===================================================================
--- include/clang/ASTMatchers/ASTTypeTraits.h
+++ include/clang/ASTMatchers/ASTTypeTraits.h
@@ -36,6 +36,8 @@
/// the supported base types.
class DynTypedNode {
public:
+ DynTypedNode() : Tag(NT_Null) {}
+
/// \brief Creates a \c DynTypedNode from \c Node.
template <typename T>
static DynTypedNode create(const T &Node) {
@@ -66,12 +68,17 @@
/// method returns NULL.
const void *getMemoizationData() const;
+ bool isNull() const {
+ return Tag == NT_Null;
+ }
+
private:
/// \brief Takes care of converting from and to \c T.
template <typename T, typename EnablerT = void> struct BaseConverter;
/// \brief Supported base node types.
enum NodeTypeTag {
+ NT_Null,
NT_Decl,
NT_Stmt,
NT_QualType
Index: lib/ASTMatchers/ASTMatchFinder.cpp
===================================================================
--- lib/ASTMatchers/ASTMatchFinder.cpp
+++ lib/ASTMatchers/ASTMatchFinder.cpp
@@ -29,6 +29,53 @@
typedef MatchFinder::MatchCallback MatchCallback;
+/// \brief A \c RecursiveASTVisitor that builds a map from nodes to their
+/// parents.
+///
+/// FIXME: Currently only builds up the map using Stmt and Decl nodes.
+class ParentMapASTVisitor : public RecursiveASTVisitor<ParentMapASTVisitor> {
+public:
+ /// \brief Maps from a node to its parent.
+ typedef llvm::DenseMap<const void*, ast_type_traits::DynTypedNode> ParentMap;
+
+ /// Builds and returns the translation unit's parent map.
+ static ParentMap *buildMap(TranslationUnitDecl &TU) {
+ ParentMapASTVisitor Visitor(new ParentMap);
+ Visitor.TraverseDecl(&TU);
+ return Visitor.Parents;
+ }
+
+private:
+ typedef RecursiveASTVisitor<ParentMapASTVisitor> VisitorBase;
+
+ ParentMapASTVisitor(ParentMap *Parents) : Parents(Parents) {}
+
+ template <typename T>
+ 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<ast_type_traits::DynTypedNode, 16> ParentStack;
+
+ friend class RecursiveASTVisitor<ParentMapASTVisitor>;
+};
+
// 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 +358,34 @@
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) {
+ assert(Node.getMemoizationData() &&
+ "Ancestor matching is only allowed for nodes that have pointer "
+ "identity in the AST.");
+ if (!Parents) {
+ // We always need to run over the whole translation unit, as
+ // hasAncestor can escape any subtree.
+ Parents.reset(ParentMapASTVisitor::buildMap(
+ *ActiveASTContext->getTranslationUnitDecl()));
+ }
+ ast_type_traits::DynTypedNode Ancestor = Node;
+ ast_type_traits::DynTypedNode PreviousAncestor;
+ do {
+ PreviousAncestor = Ancestor;
+ assert(PreviousAncestor.getMemoizationData() &&
+ "Invariant broken: only nodes that support memoization may be "
+ "used in the parent map.");
+ Ancestor = Parents->lookup(PreviousAncestor.getMemoizationData());
+ if (Matcher.matches(Ancestor, this, Builder))
+ return true;
+ } while (!Ancestor.isNull());
+ assert(PreviousAncestor.get<TranslationUnitDecl>() ==
+ ActiveASTContext->getTranslationUnitDecl());
+ return false;
+ }
bool shouldVisitTemplateInstantiations() const { return true; }
bool shouldVisitImplicitCode() const { return true; }
@@ -378,6 +453,8 @@
// Maps (matcher, node) -> the match result for memoization.
typedef llvm::DenseMap<UntypedMatchInput, MemoizedMatchResult> MemoizationMap;
MemoizationMap ResultCache;
+
+ llvm::OwningPtr<ParentMapASTVisitor::ParentMap> Parents;
};
// Returns true if the given class is directly or indirectly derived
Index: unittests/ASTMatchers/ASTMatchersTest.cpp
===================================================================
--- unittests/ASTMatchers/ASTMatchersTest.cpp
+++ unittests/ASTMatchers/ASTMatchersTest.cpp
@@ -597,31 +597,41 @@
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.
+// Returns from \c run whether \c BoundNodes contain a \c Decl bound to \c Id
+// that can be dynamically casted to \c T.
// Optionally checks that the check succeeded a specific number of times.
template <typename T>
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<T>(Id) != NULL) {
+ if (const Decl *Node = Nodes->getDeclAs<T>(Id)) {
++Count;
+ if (const NamedDecl *Named = llvm::dyn_cast<NamedDecl>(Node)) {
+ DeclName = Named->getNameAsString();
+ }
return true;
}
return false;
@@ -631,6 +641,8 @@
const std::string Id;
const int ExpectedCount;
int Count;
+ const std::string ExpectedDeclName;
+ std::string DeclName;
};
template <typename T>
class VerifyIdIsBoundToStmt : public BoundNodesCallback {
@@ -2721,5 +2733,53 @@
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<CXXRecordDecl>("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<CXXRecordDecl>("d", "E")));
+}
+
} // end namespace ast_matchers
} // end namespace clang
_______________________________________________
cfe-commits mailing list
[email protected]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
