diff options
| -rw-r--r-- | include/clang/AST/ASTContext.h | 129 | ||||
| -rw-r--r-- | include/clang/AST/ASTTypeTraits.h (renamed from include/clang/ASTMatchers/ASTTypeTraits.h) | 13 | ||||
| -rw-r--r-- | include/clang/ASTMatchers/ASTMatchersInternal.h | 6 | ||||
| -rw-r--r-- | lib/ASTMatchers/ASTMatchFinder.cpp | 91 | ||||
| -rw-r--r-- | unittests/AST/ASTContextParentMapTest.cpp | 71 | ||||
| -rw-r--r-- | unittests/AST/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | unittests/AST/MatchVerifier.h | 2 |
7 files changed, 217 insertions, 96 deletions
diff --git a/include/clang/AST/ASTContext.h b/include/clang/AST/ASTContext.h index 7c02699ee4..d12d0545c5 100644 --- a/include/clang/AST/ASTContext.h +++ b/include/clang/AST/ASTContext.h @@ -15,6 +15,7 @@ #ifndef LLVM_CLANG_AST_ASTCONTEXT_H #define LLVM_CLANG_AST_ASTCONTEXT_H +#include "clang/AST/ASTTypeTraits.h" #include "clang/AST/CanonicalType.h" #include "clang/AST/CommentCommandTraits.h" #include "clang/AST/Decl.h" @@ -22,6 +23,7 @@ #include "clang/AST/NestedNameSpecifier.h" #include "clang/AST/PrettyPrinter.h" #include "clang/AST/RawCommentList.h" +#include "clang/AST/RecursiveASTVisitor.h" #include "clang/AST/TemplateName.h" #include "clang/AST/Type.h" #include "clang/Basic/AddressSpaces.h" @@ -382,6 +384,58 @@ public: 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. + /// + /// Caveats and FIXMEs: + /// Calculating the parent map over all AST nodes will need to load the + /// full AST. This can be undesirable in the case where the full AST is + /// expensive to create (for example, when using precompiled header + /// preambles). Thus, there are good opportunities for optimization here. + /// One idea is to walk the given node downwards, looking for references + /// to declaration contexts - once a declaration context is found, compute + /// the parent map for the declaration context; if that can satisfy the + /// request, loading the whole AST can be avoided. Note that this is made + /// more complex by statements in templates having multiple parents - those + /// problems can be solved by building closure over the templated parts of + /// the AST, which also avoids touching large parts of the AST. + /// Additionally, we will want to add an interface to already give a hint + /// where to search for the parents, for example when looking at a statement + /// inside a certain function. + /// + /// 'NodeT' can be one of Decl, Stmt, Type, TypeLoc, + /// NestedNameSpecifier or NestedNameSpecifierLoc. + template <typename NodeT> + 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 + // 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; } @@ -2136,8 +2190,81 @@ private: 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); diff --git a/include/clang/ASTMatchers/ASTTypeTraits.h b/include/clang/AST/ASTTypeTraits.h index 1dc5441bbb..4688b12de7 100644 --- a/include/clang/ASTMatchers/ASTTypeTraits.h +++ b/include/clang/AST/ASTTypeTraits.h @@ -1,4 +1,4 @@ -//===--- ASTMatchersTypeTraits.h --------------------------------*- C++ -*-===// +//===--- ASTTypeTraits.h ----------------------------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -12,8 +12,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_AST_MATCHERS_AST_TYPE_TRAITS_H -#define LLVM_CLANG_AST_MATCHERS_AST_TYPE_TRAITS_H +#ifndef LLVM_CLANG_AST_AST_TYPE_TRAITS_H +#define LLVM_CLANG_AST_AST_TYPE_TRAITS_H #include "clang/AST/Decl.h" #include "clang/AST/Stmt.h" @@ -88,8 +88,9 @@ private: /// guaranteed to be unique pointers pointing to dedicated storage in the /// AST. \c QualTypes on the other hand do not have storage or unique /// pointers and thus need to be stored by value. - llvm::AlignedCharArrayUnion<Decl*, QualType, TypeLoc, NestedNameSpecifierLoc> - Storage; + llvm::AlignedCharArrayUnion<Decl *, Stmt *, NestedNameSpecifier, + NestedNameSpecifierLoc, QualType, Type, + TypeLoc> Storage; }; // FIXME: Pull out abstraction for the following. @@ -207,4 +208,4 @@ inline const void *DynTypedNode::getMemoizationData() const { } // end namespace ast_type_traits } // end namespace clang -#endif // LLVM_CLANG_AST_MATCHERS_AST_TYPE_TRAITS_H +#endif // LLVM_CLANG_AST_AST_TYPE_TRAITS_H diff --git a/include/clang/ASTMatchers/ASTMatchersInternal.h b/include/clang/ASTMatchers/ASTMatchersInternal.h index 1119a72a42..f309794034 100644 --- a/include/clang/ASTMatchers/ASTMatchersInternal.h +++ b/include/clang/ASTMatchers/ASTMatchersInternal.h @@ -35,13 +35,13 @@ #ifndef LLVM_CLANG_AST_MATCHERS_AST_MATCHERS_INTERNAL_H #define LLVM_CLANG_AST_MATCHERS_AST_MATCHERS_INTERNAL_H -#include "clang/AST/Decl.h" +#include "clang/AST/ASTTypeTraits.h" #include "clang/AST/DeclCXX.h" +#include "clang/AST/Decl.h" #include "clang/AST/ExprCXX.h" -#include "clang/AST/Stmt.h" #include "clang/AST/StmtCXX.h" +#include "clang/AST/Stmt.h" #include "clang/AST/Type.h" -#include "clang/ASTMatchers/ASTTypeTraits.h" #include "llvm/ADT/VariadicFunction.h" #include "llvm/Support/type_traits.h" #include <map> diff --git a/lib/ASTMatchers/ASTMatchFinder.cpp b/lib/ASTMatchers/ASTMatchFinder.cpp index 3a3c1fb6e1..1af2f09c3e 100644 --- a/lib/ASTMatchers/ASTMatchFinder.cpp +++ b/lib/ASTMatchers/ASTMatchFinder.cpp @@ -29,76 +29,6 @@ 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 Contains parents of a node. - typedef 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; - 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 @@ public: 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); } @@ -506,22 +430,21 @@ private: 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; @@ -574,8 +497,6 @@ private: // Maps (matcher, node) -> the match result for memoization. typedef llvm::DenseMap<UntypedMatchInput, MemoizedMatchResult> MemoizationMap; MemoizationMap ResultCache; - - OwningPtr<ParentMapASTVisitor::ParentMap> Parents; }; // Returns true if the given class is directly or indirectly derived diff --git a/unittests/AST/ASTContextParentMapTest.cpp b/unittests/AST/ASTContextParentMapTest.cpp new file mode 100644 index 0000000000..c1910a8231 --- /dev/null +++ b/unittests/AST/ASTContextParentMapTest.cpp @@ -0,0 +1,71 @@ +//===- unittest/AST/ASTContextParentMapTest.cpp - AST parent map test -----===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Tests for the getParents(...) methods of ASTContext. +// +//===----------------------------------------------------------------------===// + +#include "clang/AST/ASTContext.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/ASTMatchers/ASTMatchers.h" +#include "clang/Tooling/Tooling.h" +#include "gtest/gtest.h" +#include "MatchVerifier.h" + +namespace clang { +namespace ast_matchers { + +using clang::tooling::newFrontendActionFactory; +using clang::tooling::runToolOnCodeWithArgs; +using clang::tooling::FrontendActionFactory; + +TEST(GetParents, ReturnsParentForDecl) { + MatchVerifier<Decl> Verifier; + EXPECT_TRUE(Verifier.match("class C { void f(); };", + methodDecl(hasParent(recordDecl(hasName("C")))))); +} + +TEST(GetParents, ReturnsParentForStmt) { + MatchVerifier<Stmt> Verifier; + EXPECT_TRUE(Verifier.match("class C { void f() { if (true) {} } };", + ifStmt(hasParent(compoundStmt())))); +} + +TEST(GetParents, ReturnsParentInsideTemplateInstantiations) { + MatchVerifier<Decl> DeclVerifier; + EXPECT_TRUE(DeclVerifier.match( + "template<typename T> struct C { void f() {} };" + "void g() { C<int> c; c.f(); }", + methodDecl(hasName("f"), + hasParent(recordDecl(isTemplateInstantiation()))))); + EXPECT_TRUE(DeclVerifier.match( + "template<typename T> struct C { void f() {} };" + "void g() { C<int> c; c.f(); }", + methodDecl(hasName("f"), + hasParent(recordDecl(unless(isTemplateInstantiation())))))); + EXPECT_FALSE(DeclVerifier.match( + "template<typename T> struct C { void f() {} };" + "void g() { C<int> c; c.f(); }", + methodDecl(hasName("f"), + allOf(hasParent(recordDecl(unless(isTemplateInstantiation()))), + hasParent(recordDecl(isTemplateInstantiation())))))); +} + +TEST(GetParents, ReturnsMultipleParentsInTemplateInstantiations) { + MatchVerifier<Stmt> TemplateVerifier; + EXPECT_TRUE(TemplateVerifier.match( + "template<typename T> struct C { void f() {} };" + "void g() { C<int> c; c.f(); }", + compoundStmt( + allOf(hasAncestor(recordDecl(isTemplateInstantiation())), + hasAncestor(recordDecl(unless(isTemplateInstantiation()))))))); +} + +} // end namespace ast_matchers +} // end namespace clang diff --git a/unittests/AST/CMakeLists.txt b/unittests/AST/CMakeLists.txt index 1ea293ee83..ad29428220 100644 --- a/unittests/AST/CMakeLists.txt +++ b/unittests/AST/CMakeLists.txt @@ -1,4 +1,5 @@ add_clang_unittest(ASTTests + ASTContextParentMapTest.cpp CommentLexer.cpp CommentParser.cpp DeclPrinterTest.cpp diff --git a/unittests/AST/MatchVerifier.h b/unittests/AST/MatchVerifier.h index f0a5853704..7aa78860aa 100644 --- a/unittests/AST/MatchVerifier.h +++ b/unittests/AST/MatchVerifier.h @@ -44,7 +44,7 @@ public: protected: virtual void run(const MatchFinder::MatchResult &Result); virtual void verify(const MatchFinder::MatchResult &Result, - const NodeType &Node) = 0; + const NodeType &Node) {} void setFailure(const Twine &Result) { Verified = false; |