This does not yet implement the LimitNode approach discussed via email,
but I want to get some opinions in what that interface should look like
and how we'd want it to behave. If there's agreement that this is
generally desirable, I'll pull the ASTTypeTraits into AST/.
The impact of this is an O(n) in the number of nodes in the AST
reduction of complexity for certain kinds of matchers (as otherwise the
parent map gets recreated for every new MatchFinder).
Open questions:
- if we implement a second version with a LimitNode, do we want to cache
those results at all (it's hard, because of the
multiple-parents-problem).
- do we want to leave the RAV implementation in ASTContext (which is
already large), or pull it out into an ASTContextInternal header (or
similar)?
- this introduces ast_type_traits::DynTypedNode into a more prominent
location - if there's problems with that approach, now is the time to
point it out to me :)
http://llvm-reviews.chandlerc.com/D267
Files:
include/clang/AST/ASTContext.h
include/clang/ASTMatchers/ASTTypeTraits.h
lib/ASTMatchers/ASTMatchFinder.cpp
Index: include/clang/AST/ASTContext.h
===================================================================
--- include/clang/AST/ASTContext.h
+++ include/clang/AST/ASTContext.h
@@ -39,6 +39,10 @@
#include "llvm/Support/Allocator.h"
#include <vector>
+// FIXME: Move to a better location once we think all this is a good idea :)
+#include "clang/ASTMatchers/ASTTypeTraits.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+
namespace llvm {
struct fltSemantics;
}
@@ -398,6 +402,42 @@
OwningPtr<ExternalASTSource> ExternalSource;
ASTMutationListener *Listener;
+ /// \brief Contains parents of a node.
+ typedef llvm::SmallVector<ast_type_traits::DynTypedNode, 1> ParentVector;
+
+ /// \brief Maps from a node to its parents.
+ typedef llvm::DenseMap<const void *, ParentVector> ParentMap;
+
+ /// \brief Returns the parents of the given node.
+ ///
+ /// Note that this will lazily compute the parents of all nodes
+ /// and store them for later retrieval. Thus, the first call is O(n)
+ /// in the number of AST nodes.
+ ///
+ /// 'NodeT' can be one of Decl, Stmt, Type, TypeLoc,
+ /// NestedNameSpecifier or NestedNameSpecifierLoc.
+ template <typename NodeT, typename LimitNodeT>
+ ParentVector getParents(const NodeT &Node) {
+ return getParents(ast_type_traits::DynTypedNode::create(Node));
+ }
+
+ ParentVector getParents(const ast_type_traits::DynTypedNode &Node) {
+ assert(Node.getMemoizationData() &&
+ "Invariant broken: only nodes that support memoization may be "
+ "used in the parent map.");
+ if (!AllParents) {
+ // We always need to run over the whole translation unit, as
+ // \c hasAncestor can escape any subtree.
+ AllParents.reset(
+ ParentMapASTVisitor::buildMap(*getTranslationUnitDecl()));
+ }
+ ParentMap::const_iterator I = AllParents->find(Node.getMemoizationData());
+ if (I == AllParents->end()) {
+ return ParentVector();
+ }
+ return I->second;
+ }
+
const clang::PrintingPolicy &getPrintingPolicy() const {
return PrintingPolicy;
}
@@ -2129,8 +2169,81 @@
friend class DeclContext;
friend class DeclarationNameTable;
void ReleaseDeclContextMaps();
+
+ /// \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 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;
+ }
+ // Disables data recursion. We intercept Traverse* methods in the RAV, which
+ // are not triggered during data recursion.
+ bool shouldUseDataRecursionFor(clang::Stmt *S) const {
+ return false;
+ }
+
+ template <typename T>
+ bool TraverseNode(T *Node, bool(VisitorBase:: *traverse) (T *)) {
+ if (Node == NULL)
+ return true;
+ if (ParentStack.size() > 0)
+ // FIXME: Currently we add the same parent multiple times, for example
+ // when we visit all subexpressions of template instantiations; this is
+ // suboptimal, bug benign: the only way to visit those is with
+ // hasAncestor / hasParent, and those do not create new matches.
+ // The plan is to enable DynTypedNode to be storable in a map or hash
+ // map. The main problem there is to implement hash functions /
+ // comparison operators for all types that DynTypedNode supports that
+ // do not have pointer identity.
+ (*Parents)[Node].push_back(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>;
+ };
+
+ llvm::OwningPtr<ParentMap> AllParents;
};
-
+
/// \brief Utility function for constructing a nullary selector.
static inline Selector GetNullarySelector(StringRef name, ASTContext& Ctx) {
IdentifierInfo* II = &Ctx.Idents.get(name);
Index: include/clang/ASTMatchers/ASTTypeTraits.h
===================================================================
--- include/clang/ASTMatchers/ASTTypeTraits.h
+++ include/clang/ASTMatchers/ASTTypeTraits.h
@@ -17,6 +17,7 @@
#include "clang/AST/Decl.h"
#include "clang/AST/Stmt.h"
+#include "clang/AST/TypeLoc.h"
#include "llvm/Support/AlignOf.h"
namespace clang {
Index: lib/ASTMatchers/ASTMatchFinder.cpp
===================================================================
--- lib/ASTMatchers/ASTMatchFinder.cpp
+++ lib/ASTMatchers/ASTMatchFinder.cpp
@@ -29,76 +29,6 @@
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 Contains parents of a node.
- typedef llvm::SmallVector<ast_type_traits::DynTypedNode, 1> ParentVector;
-
- /// \brief Maps from a node to its parents.
- typedef llvm::DenseMap<const void *, ParentVector> 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; }
- // Disables data recursion. We intercept Traverse* methods in the RAV, which
- // are not triggered during data recursion.
- bool shouldUseDataRecursionFor(clang::Stmt *S) const { return false; }
-
- template <typename T>
- bool TraverseNode(T *Node, bool (VisitorBase::*traverse)(T*)) {
- if (Node == NULL)
- return true;
- if (ParentStack.size() > 0)
- // FIXME: Currently we add the same parent multiple times, for example
- // when we visit all subexpressions of template instantiations; this is
- // suboptimal, bug benign: the only way to visit those is with
- // hasAncestor / hasParent, and those do not create new matches.
- // The plan is to enable DynTypedNode to be storable in a map or hash
- // map. The main problem there is to implement hash functions /
- // comparison operators for all types that DynTypedNode supports that
- // do not have pointer identity.
- (*Parents)[Node].push_back(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
@@ -458,12 +388,6 @@
const DynTypedMatcher &Matcher,
BoundNodesTreeBuilder *Builder,
AncestorMatchMode MatchMode) {
- 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()));
- }
return matchesAncestorOfRecursively(Node, Matcher, Builder, MatchMode);
}
@@ -486,22 +410,21 @@
assert(Node.getMemoizationData() &&
"Invariant broken: only nodes that support memoization may be "
"used in the parent map.");
- ParentMapASTVisitor::ParentMap::const_iterator I =
- Parents->find(Node.getMemoizationData());
- if (I == Parents->end()) {
+ ASTContext::ParentVector Parents = ActiveASTContext->getParents(Node);
+ if (Parents.empty()) {
assert(false && "Found node that is not in the parent map.");
return false;
}
- for (ParentMapASTVisitor::ParentVector::const_iterator AncestorI =
- I->second.begin(), AncestorE = I->second.end();
+ for (ASTContext::ParentVector::const_iterator AncestorI = Parents.begin(),
+ AncestorE = Parents.end();
AncestorI != AncestorE; ++AncestorI) {
if (Matcher.matches(*AncestorI, this, Builder))
return true;
}
if (MatchMode == ASTMatchFinder::AMM_ParentOnly)
return false;
- for (ParentMapASTVisitor::ParentVector::const_iterator AncestorI =
- I->second.begin(), AncestorE = I->second.end();
+ for (ASTContext::ParentVector::const_iterator AncestorI = Parents.begin(),
+ AncestorE = Parents.end();
AncestorI != AncestorE; ++AncestorI) {
if (matchesAncestorOfRecursively(*AncestorI, Matcher, Builder, MatchMode))
return true;
@@ -572,8 +495,6 @@
// 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
_______________________________________________
cfe-commits mailing list
[email protected]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
