summaryrefslogtreecommitdiffstats
path: root/clang
diff options
context:
space:
mode:
Diffstat (limited to 'clang')
-rw-r--r--clang/include/clang/ASTMatchers/ASTMatchers.h20
-rw-r--r--clang/include/clang/ASTMatchers/ASTMatchersInternal.h54
-rw-r--r--clang/lib/ASTMatchers/ASTMatchFinder.cpp87
-rw-r--r--clang/unittests/ASTMatchers/ASTMatchersTest.cpp99
4 files changed, 245 insertions, 15 deletions
diff --git a/clang/include/clang/ASTMatchers/ASTMatchers.h b/clang/include/clang/ASTMatchers/ASTMatchers.h
index 54a0e02e13c..23743e529bd 100644
--- a/clang/include/clang/ASTMatchers/ASTMatchers.h
+++ b/clang/include/clang/ASTMatchers/ASTMatchers.h
@@ -1179,7 +1179,6 @@ hasDescendant(const internal::Matcher<DescendantT> &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 <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"))))
diff --git a/clang/include/clang/ASTMatchers/ASTMatchersInternal.h b/clang/include/clang/ASTMatchers/ASTMatchersInternal.h
index 36831e6f11d..2a49b63c839 100644
--- a/clang/include/clang/ASTMatchers/ASTMatchersInternal.h
+++ b/clang/include/clang/ASTMatchers/ASTMatchersInternal.h
@@ -388,13 +388,21 @@ const bool IsBaseType<T>::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 <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 +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<T> to a matcher of desired type \c To by
@@ -801,6 +824,29 @@ public:
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_ancestor_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.
///
diff --git a/clang/lib/ASTMatchers/ASTMatchFinder.cpp b/clang/lib/ASTMatchers/ASTMatchFinder.cpp
index 8f28c385b92..54b05b39390 100644
--- a/clang/lib/ASTMatchers/ASTMatchFinder.cpp
+++ b/clang/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<ParentMapASTVisitor> {
+public:
+ /// \brief Maps from a node to its parent.
+ typedef llvm::DenseMap<const void*, ast_type_traits::DynTypedNode> 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<ParentMapASTVisitor> VisitorBase;
+
+ ParentMapASTVisitor(ParentMap *Parents) : Parents(Parents) {}
+
+ bool shouldVisitTemplateInstantiations() const { return true; }
+ bool shouldVisitImplicitCode() const { return true; }
+
+ 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 +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<TranslationUnitDecl>() !=
+ 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<UntypedMatchInput, MemoizedMatchResult> MemoizationMap;
MemoizationMap ResultCache;
+
+ llvm::OwningPtr<ParentMapASTVisitor::ParentMap> Parents;
};
// Returns true if the given class is directly or indirectly derived
diff --git a/clang/unittests/ASTMatchers/ASTMatchersTest.cpp b/clang/unittests/ASTMatchers/ASTMatchersTest.cpp
index 86e949fef4f..7adc71837d7 100644
--- a/clang/unittests/ASTMatchers/ASTMatchersTest.cpp
+++ b/clang/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 <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 @@ private:
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,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<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")));
+}
+
+TEST(HasAncestor, MatchesInTemplateInstantiations) {
+ EXPECT_TRUE(matches(
+ "template <typename T> struct A { struct B { struct C { T t; }; }; }; "
+ "A<int>::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
OpenPOWER on IntegriCloud