Index: include/clang/AST/ASTContext.h =================================================================== --- include/clang/AST/ASTContext.h +++ include/clang/AST/ASTContext.h @@ -569,26 +569,6 @@ IntrusiveRefCntPtr ExternalSource; ASTMutationListener *Listener = nullptr; - /// Contains parents of a node. - using ParentVector = llvm::SmallVector; - - /// Maps from a node to its parents. This is used for nodes that have - /// pointer identity only, which are more common and we can save space by - /// only storing a unique pointer to them. - using ParentMapPointers = - llvm::DenseMap>; - - /// Parent map for nodes without pointer identity. We store a full - /// DynTypedNode for all keys. - using ParentMapOtherNodes = - llvm::DenseMap>; - /// Container for either a single DynTypedNode or for an ArrayRef to /// DynTypedNode. For use with ParentMap. class DynTypedNodeList { @@ -630,7 +610,17 @@ } }; - /// Returns the parents of the given node. + // A traversal scope limits the parts of the AST visible to certain analyses. + // RecursiveASTVisitor::TraverseAST will only visit reachable nodes, and + // getParents() will only observe reachable parent edges. + // + // The scope is defined by a set of "top-level" declarations. + // Initially, it is the entire TU: {getTranslationUnitDecl()}. + // Changing the scope clears the parent cache, which is expensive to rebuild. + std::vector getTraversalScope() const { return TraversalScope; } + void setTraversalScope(const std::vector &); + + /// Returns the parents of the given node (within the traversal scope). /// /// Note that this will lazily compute the parents of all nodes /// and store them for later retrieval. Thus, the first call is O(n) @@ -2924,13 +2914,13 @@ // but we include it here so that ASTContext can quickly deallocate them. llvm::PointerIntPair LastSDM; - std::unique_ptr PointerParents; - std::unique_ptr OtherParents; + std::vector TraversalScope; + class ParentMap; + std::unique_ptr Parents; std::unique_ptr VTContext; void ReleaseDeclContextMaps(); - void ReleaseParentMapEntries(); public: enum PragmaSectionFlag : unsigned { Index: include/clang/AST/RecursiveASTVisitor.h =================================================================== --- include/clang/AST/RecursiveASTVisitor.h +++ include/clang/AST/RecursiveASTVisitor.h @@ -176,6 +176,16 @@ /// Return whether this visitor should traverse post-order. bool shouldTraversePostOrder() const { return false; } + /// Recursively visits an entire AST, starting from the top-level Decls + /// in the AST traversal scope (by default, the TranslationUnitDecl). + /// \returns false if visitation was terminated early. + bool TraverseAST(ASTContext &AST) { + for (Decl *D : AST.getTraversalScope()) + if (!getDerived().TraverseDecl(D)) + return false; + return true; + } + /// Recursively visit a statement or expression, by /// dispatching to Traverse*() based on the argument's dynamic type. /// Index: lib/AST/ASTContext.cpp =================================================================== --- lib/AST/ASTContext.cpp +++ lib/AST/ASTContext.cpp @@ -796,11 +796,10 @@ CommentCommandTraits(BumpAlloc, LOpts.CommentOpts), CompCategories(this_()), LastSDM(nullptr, 0) { TUDecl = TranslationUnitDecl::Create(*this); + TraversalScope = {TUDecl}; } ASTContext::~ASTContext() { - ReleaseParentMapEntries(); - // Release the DenseMaps associated with DeclContext objects. // FIXME: Is this the ideal solution? ReleaseDeclContextMaps(); @@ -838,22 +837,80 @@ Value.second->~PerModuleInitializers(); } -void ASTContext::ReleaseParentMapEntries() { - if (!PointerParents) return; - for (const auto &Entry : *PointerParents) { - if (Entry.second.is()) { - delete Entry.second.get(); - } else if (Entry.second.is()) { - delete Entry.second.get(); - } - } - for (const auto &Entry : *OtherParents) { - if (Entry.second.is()) { - delete Entry.second.get(); - } else if (Entry.second.is()) { - delete Entry.second.get(); - } +class ASTContext::ParentMap { + /// Contains parents of a node. + using ParentVector = llvm::SmallVector; + + /// Maps from a node to its parents. This is used for nodes that have + /// pointer identity only, which are more common and we can save space by + /// only storing a unique pointer to them. + using ParentMapPointers = llvm::DenseMap< + const void *, + llvm::PointerUnion4>; + + /// Parent map for nodes without pointer identity. We store a full + /// DynTypedNode for all keys. + using ParentMapOtherNodes = llvm::DenseMap< + ast_type_traits::DynTypedNode, + llvm::PointerUnion4>; + + ParentMapPointers PointerParents; + ParentMapOtherNodes OtherParents; + class ASTVisitor; + + static ast_type_traits::DynTypedNode + getSingleDynTypedNodeFromParentMap(ParentMapPointers::mapped_type U) { + if (const auto *D = U.dyn_cast()) + return ast_type_traits::DynTypedNode::create(*D); + if (const auto *S = U.dyn_cast()) + return ast_type_traits::DynTypedNode::create(*S); + return *U.get(); + } + + template + static ASTContext::DynTypedNodeList getDynNodeFromMap(const NodeTy &Node, + const MapTy &Map) { + auto I = Map.find(Node); + if (I == Map.end()) { + return llvm::ArrayRef(); + } + if (const auto *V = I->second.template dyn_cast()) { + return llvm::makeArrayRef(*V); + } + return getSingleDynTypedNodeFromParentMap(I->second); + } + +public: + ParentMap(ASTContext &Ctx); + ~ParentMap() { + for (const auto &Entry : PointerParents) { + if (Entry.second.is()) { + delete Entry.second.get(); + } else if (Entry.second.is()) { + delete Entry.second.get(); + } + } + for (const auto &Entry : OtherParents) { + if (Entry.second.is()) { + delete Entry.second.get(); + } else if (Entry.second.is()) { + delete Entry.second.get(); + } + } + } + + DynTypedNodeList getParents(const ast_type_traits::DynTypedNode &Node) { + if (Node.getNodeKind().hasPointerIdentity()) + return getDynNodeFromMap(Node.getMemoizationData(), PointerParents); + return getDynNodeFromMap(Node, OtherParents); } +}; + +void ASTContext::setTraversalScope(const std::vector &TopLevelDecls) { + TraversalScope = TopLevelDecls; + Parents.reset(); } void ASTContext::AddDeallocation(void (*Callback)(void*), void *Data) { @@ -10104,21 +10161,10 @@ return (Size != Align || toBits(sizeChars) > MaxInlineWidthInBits); } -static ast_type_traits::DynTypedNode getSingleDynTypedNodeFromParentMap( - ASTContext::ParentMapPointers::mapped_type U) { - if (const auto *D = U.dyn_cast()) - return ast_type_traits::DynTypedNode::create(*D); - if (const auto *S = U.dyn_cast()) - return ast_type_traits::DynTypedNode::create(*S); - return *U.get(); -} - -namespace { - /// Template specializations to abstract away from pointers and TypeLocs. /// @{ template -ast_type_traits::DynTypedNode createDynTypedNode(const T &Node) { +static ast_type_traits::DynTypedNode createDynTypedNode(const T &Node) { return ast_type_traits::DynTypedNode::create(*Node); } template <> @@ -10132,160 +10178,121 @@ } /// @} - /// 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: - /// Builds and returns the translation unit's parent map. - /// - /// The caller takes ownership of the returned \c ParentMap. - static std::pair - buildMap(TranslationUnitDecl &TU) { - ParentMapASTVisitor Visitor(new ASTContext::ParentMapPointers, - new ASTContext::ParentMapOtherNodes); - Visitor.TraverseDecl(&TU); - return std::make_pair(Visitor.Parents, Visitor.OtherParents); - } - - private: - friend class RecursiveASTVisitor; - - using VisitorBase = RecursiveASTVisitor; - - ParentMapASTVisitor(ASTContext::ParentMapPointers *Parents, - ASTContext::ParentMapOtherNodes *OtherParents) - : Parents(Parents), OtherParents(OtherParents) {} - - bool shouldVisitTemplateInstantiations() const { - return true; - } - - bool shouldVisitImplicitCode() const { +/// 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 ASTContext::ParentMap::ASTVisitor + : public RecursiveASTVisitor { +public: + ASTVisitor(ParentMap &Map) : Map(Map) {} + +private: + friend class RecursiveASTVisitor; + + using VisitorBase = RecursiveASTVisitor; + + bool shouldVisitTemplateInstantiations() const { return true; } + + bool shouldVisitImplicitCode() const { return true; } + + template + bool TraverseNode(T Node, MapNodeTy MapNode, BaseTraverseFn BaseTraverse, + MapTy *Parents) { + if (!Node) return true; - } - - template - bool TraverseNode(T Node, MapNodeTy MapNode, - BaseTraverseFn BaseTraverse, MapTy *Parents) { - if (!Node) - return true; - if (ParentStack.size() > 0) { - // FIXME: Currently we add the same parent multiple times, but only - // when no memoization data is available for the type. - // For example when we visit all subexpressions of template - // instantiations; this is suboptimal, but 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. - auto &NodeOrVector = (*Parents)[MapNode]; - if (NodeOrVector.isNull()) { - if (const auto *D = ParentStack.back().get()) - NodeOrVector = D; - else if (const auto *S = ParentStack.back().get()) - NodeOrVector = S; - else - NodeOrVector = - new ast_type_traits::DynTypedNode(ParentStack.back()); - } else { - if (!NodeOrVector.template is()) { - auto *Vector = new ASTContext::ParentVector( - 1, getSingleDynTypedNodeFromParentMap(NodeOrVector)); - delete NodeOrVector - .template dyn_cast(); - NodeOrVector = Vector; - } - - auto *Vector = - NodeOrVector.template get(); - // Skip duplicates for types that have memoization data. - // We must check that the type has memoization data before calling - // std::find() because DynTypedNode::operator== can't compare all - // types. - bool Found = ParentStack.back().getMemoizationData() && - std::find(Vector->begin(), Vector->end(), - ParentStack.back()) != Vector->end(); - if (!Found) - Vector->push_back(ParentStack.back()); + if (ParentStack.size() > 0) { + // FIXME: Currently we add the same parent multiple times, but only + // when no memoization data is available for the type. + // For example when we visit all subexpressions of template + // instantiations; this is suboptimal, but 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. + auto &NodeOrVector = (*Parents)[MapNode]; + if (NodeOrVector.isNull()) { + if (const auto *D = ParentStack.back().get()) + NodeOrVector = D; + else if (const auto *S = ParentStack.back().get()) + NodeOrVector = S; + else + NodeOrVector = new ast_type_traits::DynTypedNode(ParentStack.back()); + } else { + if (!NodeOrVector.template is()) { + auto *Vector = new ParentVector( + 1, getSingleDynTypedNodeFromParentMap(NodeOrVector)); + delete NodeOrVector + .template dyn_cast(); + NodeOrVector = Vector; } - } - ParentStack.push_back(createDynTypedNode(Node)); - bool Result = BaseTraverse(); - ParentStack.pop_back(); - return Result; - } - bool TraverseDecl(Decl *DeclNode) { - return TraverseNode(DeclNode, DeclNode, - [&] { return VisitorBase::TraverseDecl(DeclNode); }, - Parents); + auto *Vector = NodeOrVector.template get(); + // Skip duplicates for types that have memoization data. + // We must check that the type has memoization data before calling + // std::find() because DynTypedNode::operator== can't compare all + // types. + bool Found = ParentStack.back().getMemoizationData() && + std::find(Vector->begin(), Vector->end(), + ParentStack.back()) != Vector->end(); + if (!Found) + Vector->push_back(ParentStack.back()); + } } + ParentStack.push_back(createDynTypedNode(Node)); + bool Result = BaseTraverse(); + ParentStack.pop_back(); + return Result; + } - bool TraverseStmt(Stmt *StmtNode) { - return TraverseNode(StmtNode, StmtNode, - [&] { return VisitorBase::TraverseStmt(StmtNode); }, - Parents); - } + bool TraverseDecl(Decl *DeclNode) { + return TraverseNode( + DeclNode, DeclNode, [&] { return VisitorBase::TraverseDecl(DeclNode); }, + &Map.PointerParents); + } - bool TraverseTypeLoc(TypeLoc TypeLocNode) { - return TraverseNode( - TypeLocNode, ast_type_traits::DynTypedNode::create(TypeLocNode), - [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); }, - OtherParents); - } + bool TraverseStmt(Stmt *StmtNode) { + return TraverseNode( + StmtNode, StmtNode, [&] { return VisitorBase::TraverseStmt(StmtNode); }, + &Map.PointerParents); + } - bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) { - return TraverseNode( - NNSLocNode, ast_type_traits::DynTypedNode::create(NNSLocNode), - [&] { - return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode); - }, - OtherParents); - } + bool TraverseTypeLoc(TypeLoc TypeLocNode) { + return TraverseNode( + TypeLocNode, ast_type_traits::DynTypedNode::create(TypeLocNode), + [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); }, + &Map.OtherParents); + } - ASTContext::ParentMapPointers *Parents; - ASTContext::ParentMapOtherNodes *OtherParents; - llvm::SmallVector ParentStack; - }; + bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) { + return TraverseNode( + NNSLocNode, ast_type_traits::DynTypedNode::create(NNSLocNode), + [&] { return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode); }, + &Map.OtherParents); + } -} // namespace + ParentMap ⤅ + llvm::SmallVector ParentStack; +}; -template -static ASTContext::DynTypedNodeList getDynNodeFromMap(const NodeTy &Node, - const MapTy &Map) { - auto I = Map.find(Node); - if (I == Map.end()) { - return llvm::ArrayRef(); - } - if (const auto *V = - I->second.template dyn_cast()) { - return llvm::makeArrayRef(*V); - } - return getSingleDynTypedNodeFromParentMap(I->second); +ASTContext::ParentMap::ParentMap(ASTContext &Ctx) { + ASTVisitor(*this).TraverseAST(Ctx); } ASTContext::DynTypedNodeList ASTContext::getParents(const ast_type_traits::DynTypedNode &Node) { - if (!PointerParents) { - // We always need to run over the whole translation unit, as + if (!Parents) + // We build the parent map for the traversal scope (usually whole TU), as // hasAncestor can escape any subtree. - auto Maps = ParentMapASTVisitor::buildMap(*getTranslationUnitDecl()); - PointerParents.reset(Maps.first); - OtherParents.reset(Maps.second); - } - if (Node.getNodeKind().hasPointerIdentity()) - return getDynNodeFromMap(Node.getMemoizationData(), *PointerParents); - return getDynNodeFromMap(Node, *OtherParents); + Parents = llvm::make_unique(*this); + return Parents->getParents(Node); } bool Index: lib/ASTMatchers/ASTMatchFinder.cpp =================================================================== --- lib/ASTMatchers/ASTMatchFinder.cpp +++ lib/ASTMatchers/ASTMatchFinder.cpp @@ -635,10 +635,6 @@ bool memoizedMatchesAncestorOfRecursively( const ast_type_traits::DynTypedNode &Node, const DynTypedMatcher &Matcher, BoundNodesTreeBuilder *Builder, AncestorMatchMode MatchMode) { - if (Node.get() == - ActiveASTContext->getTranslationUnitDecl()) - return false; - // For AST-nodes that don't have an identity, we can't memoize. if (!Builder->isComparable()) return matchesAncestorOfRecursively(Node, Matcher, Builder, MatchMode); @@ -673,7 +669,22 @@ BoundNodesTreeBuilder *Builder, AncestorMatchMode MatchMode) { const auto &Parents = ActiveASTContext->getParents(Node); - assert(!Parents.empty() && "Found node that is not in the parent map."); + if (Parents.empty()) { + // Nodes may have no parents if: + // a) the node is the TranslationUnitDecl + // b) we have a limited traversal scope that excludes the parent edges + // c) there is a bug in the AST, and the node is not reachable + // Usually the traversal scope is the whole AST, which precludes b. + // Bugs are common enough that it's worthwhile asserting when we can. + assert(Node.get() || + /* Traversal scope is limited if none of the bounds are the TU */ + llvm::none_of(ActiveASTContext->getTraversalScope(), + [](Decl *D) { + return D->getKind() == Decl::TranslationUnit; + }) && + "Found node that is not in the complete parent map!"); + return false; + } if (Parents.size() == 1) { // Only one parent - do recursive memoization. const ast_type_traits::DynTypedNode Parent = Parents[0]; @@ -1019,7 +1030,7 @@ internal::MatchASTVisitor Visitor(&Matchers, Options); Visitor.set_active_ast_context(&Context); Visitor.onStartOfTranslationUnit(); - Visitor.TraverseDecl(Context.getTranslationUnitDecl()); + Visitor.TraverseAST(Context); Visitor.onEndOfTranslationUnit(); } Index: unittests/AST/ASTContextParentMapTest.cpp =================================================================== --- unittests/AST/ASTContextParentMapTest.cpp +++ unittests/AST/ASTContextParentMapTest.cpp @@ -17,6 +17,9 @@ #include "clang/ASTMatchers/ASTMatchers.h" #include "clang/Tooling/Tooling.h" #include "gtest/gtest.h" +#include "gmock/gmock.h" + +using testing::ElementsAre; namespace clang { namespace ast_matchers { @@ -78,5 +81,30 @@ hasAncestor(cxxRecordDecl(unless(isTemplateInstantiation()))))))); } +TEST(GetParents, RespectsTraversalScope) { + auto AST = + tooling::buildASTFromCode("struct foo { int bar; };", "foo.cpp", + std::make_shared()); + auto &Ctx = AST->getASTContext(); + auto &TU = *Ctx.getTranslationUnitDecl(); + auto &Foo = *TU.lookup(&Ctx.Idents.get("foo")).front(); + auto &Bar = *cast(Foo).lookup(&Ctx.Idents.get("bar")).front(); + + using ast_type_traits::DynTypedNode; + // Initially, scope is the whole TU. + EXPECT_THAT(Ctx.getParents(Bar), ElementsAre(DynTypedNode::create(Foo))); + EXPECT_THAT(Ctx.getParents(Foo), ElementsAre(DynTypedNode::create(TU))); + + // Restrict the scope, now some parents are gone. + Ctx.setTraversalScope({&Foo}); + EXPECT_THAT(Ctx.getParents(Bar), ElementsAre(DynTypedNode::create(Foo))); + EXPECT_THAT(Ctx.getParents(Foo), ElementsAre()); + + // Reset the scope, we get back the original results. + Ctx.setTraversalScope({&TU}); + EXPECT_THAT(Ctx.getParents(Bar), ElementsAre(DynTypedNode::create(Foo))); + EXPECT_THAT(Ctx.getParents(Foo), ElementsAre(DynTypedNode::create(TU))); +} + } // end namespace ast_matchers } // end namespace clang Index: unittests/Tooling/CMakeLists.txt =================================================================== --- unittests/Tooling/CMakeLists.txt +++ unittests/Tooling/CMakeLists.txt @@ -40,6 +40,7 @@ RecursiveASTVisitorTests/NestedNameSpecifiers.cpp RecursiveASTVisitorTests/ParenExpr.cpp RecursiveASTVisitorTests/TemplateArgumentLocTraverser.cpp + RecursiveASTVisitorTests/TraversalScope.cpp RecursiveASTVisitorTestDeclVisitor.cpp RecursiveASTVisitorTestPostOrderVisitor.cpp RecursiveASTVisitorTestTypeLocVisitor.cpp Index: unittests/Tooling/RecursiveASTVisitorTests/TraversalScope.cpp =================================================================== --- unittests/Tooling/RecursiveASTVisitorTests/TraversalScope.cpp +++ unittests/Tooling/RecursiveASTVisitorTests/TraversalScope.cpp @@ -0,0 +1,51 @@ +//===- unittest/Tooling/RecursiveASTVisitorTests/TraversalScope.cpp -------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "TestVisitor.h" + +using namespace clang; + +namespace { + +class Visitor : public ExpectedLocationVisitor { +public: + Visitor(ASTContext *Context) { this->Context = Context; } + + bool VisitNamedDecl(NamedDecl *D) { + if (!D->isImplicit()) + Match(D->getName(), D->getLocation()); + return true; + } +}; + +TEST(RecursiveASTVisitor, RespectsTraversalScope) { + auto AST = tooling::buildASTFromCode( + R"cpp( +struct foo { + struct bar { + struct baz {}; + }; +}; + )cpp", + "foo.cpp", std::make_shared()); + auto &Ctx = AST->getASTContext(); + auto &TU = *Ctx.getTranslationUnitDecl(); + auto &Foo = *TU.lookup(&Ctx.Idents.get("foo")).front(); + auto &Bar = *cast(Foo).lookup(&Ctx.Idents.get("bar")).front(); + + Ctx.setTraversalScope({&Bar}); + + Visitor V(&Ctx); + V.DisallowMatch("foo", 2, 8); + V.ExpectMatch("bar", 3, 10); + V.ExpectMatch("baz", 4, 12); + V.TraverseAST(Ctx); +} + +} // end anonymous namespace