diff options
author | Sam McCall <sam.mccall@gmail.com> | 2018-11-14 10:33:30 +0000 |
---|---|---|
committer | Sam McCall <sam.mccall@gmail.com> | 2018-11-14 10:33:30 +0000 |
commit | 86ada78ef4993dbfec778ed962f19756184453bc (patch) | |
tree | be8f6f2ef2ee3c57334c31fbbcb55ca7099f0e74 /lib | |
parent | 40b6333e608f4f64a3314ee4fe4a35d40a2974d9 (diff) |
[AST] Allow limiting the scope of common AST traversals (getParents, RAV).
Summary:
The goal is to allow analyses such as clang-tidy checks to run on a
subset of the AST, e.g. "only on main-file decls" for interactive tools.
Today, these become "problematically global" by running RecursiveASTVisitors
rooted at the TUDecl, or by navigating up via ASTContext::getParent().
The scope is restricted using a set of top-level-decls that RecursiveASTVisitors
should be rooted at. This also applies to the visitor that populates the
parent map, and so the top-level-decls are considered to have no parents.
This patch makes the traversal scope a mutable property of ASTContext.
The more obvious way to do this is to pass the top-level decls to
relevant functions directly, but this has some problems:
- it's error-prone: accidentally mixing restricted and unrestricted
scopes is a performance trap. Interleaving multiple analyses is
common (many clang-tidy checks run matchers or RAVs from matcher callbacks)
- it doesn't map well to the actual use cases, where we really do want
*all* traversals to be restricted.
- it involves a lot of plumbing in parts of the code that don't care
about traversals.
This approach was tried out in D54259 and D54261, I wanted to like it
but it feels pretty awful in practice.
Caveats: to get scope-limiting behavior of RecursiveASTVisitors, callers
have to call the new TraverseAST(Ctx) function instead of TraverseDecl(TU).
I think this is an improvement to the API regardless.
Reviewers: klimek, ioeric
Subscribers: mgorny, cfe-commits
Differential Revision: https://reviews.llvm.org/D54309
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@346847 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib')
-rw-r--r-- | lib/AST/ASTContext.cpp | 329 | ||||
-rw-r--r-- | lib/ASTMatchers/ASTMatchFinder.cpp | 23 |
2 files changed, 185 insertions, 167 deletions
diff --git a/lib/AST/ASTContext.cpp b/lib/AST/ASTContext.cpp index 33c5b50f66..1ac46f897c 100644 --- a/lib/AST/ASTContext.cpp +++ b/lib/AST/ASTContext.cpp @@ -796,11 +796,10 @@ ASTContext::ASTContext(LangOptions &LOpts, SourceManager &SM, 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 @@ ASTContext::~ASTContext() { Value.second->~PerModuleInitializers(); } -void ASTContext::ReleaseParentMapEntries() { - if (!PointerParents) return; - for (const auto &Entry : *PointerParents) { - if (Entry.second.is<ast_type_traits::DynTypedNode *>()) { - delete Entry.second.get<ast_type_traits::DynTypedNode *>(); - } else if (Entry.second.is<ParentVector *>()) { - delete Entry.second.get<ParentVector *>(); +class ASTContext::ParentMap { + /// Contains parents of a node. + using ParentVector = llvm::SmallVector<ast_type_traits::DynTypedNode, 2>; + + /// 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<const Decl *, const Stmt *, + ast_type_traits::DynTypedNode *, ParentVector *>>; + + /// 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<const Decl *, const Stmt *, + ast_type_traits::DynTypedNode *, ParentVector *>>; + + ParentMapPointers PointerParents; + ParentMapOtherNodes OtherParents; + class ASTVisitor; + + static ast_type_traits::DynTypedNode + getSingleDynTypedNodeFromParentMap(ParentMapPointers::mapped_type U) { + if (const auto *D = U.dyn_cast<const Decl *>()) + return ast_type_traits::DynTypedNode::create(*D); + if (const auto *S = U.dyn_cast<const Stmt *>()) + return ast_type_traits::DynTypedNode::create(*S); + return *U.get<ast_type_traits::DynTypedNode *>(); + } + + template <typename NodeTy, typename MapTy> + static ASTContext::DynTypedNodeList getDynNodeFromMap(const NodeTy &Node, + const MapTy &Map) { + auto I = Map.find(Node); + if (I == Map.end()) { + return llvm::ArrayRef<ast_type_traits::DynTypedNode>(); + } + if (const auto *V = I->second.template dyn_cast<ParentVector *>()) { + return llvm::makeArrayRef(*V); + } + return getSingleDynTypedNodeFromParentMap(I->second); + } + +public: + ParentMap(ASTContext &Ctx); + ~ParentMap() { + for (const auto &Entry : PointerParents) { + if (Entry.second.is<ast_type_traits::DynTypedNode *>()) { + delete Entry.second.get<ast_type_traits::DynTypedNode *>(); + } else if (Entry.second.is<ParentVector *>()) { + delete Entry.second.get<ParentVector *>(); + } } - } - for (const auto &Entry : *OtherParents) { - if (Entry.second.is<ast_type_traits::DynTypedNode *>()) { - delete Entry.second.get<ast_type_traits::DynTypedNode *>(); - } else if (Entry.second.is<ParentVector *>()) { - delete Entry.second.get<ParentVector *>(); + for (const auto &Entry : OtherParents) { + if (Entry.second.is<ast_type_traits::DynTypedNode *>()) { + delete Entry.second.get<ast_type_traits::DynTypedNode *>(); + } else if (Entry.second.is<ParentVector *>()) { + delete Entry.second.get<ParentVector *>(); + } } } + + 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<Decl *> &TopLevelDecls) { + TraversalScope = TopLevelDecls; + Parents.reset(); } void ASTContext::AddDeallocation(void (*Callback)(void*), void *Data) { @@ -10104,21 +10161,10 @@ bool ASTContext::AtomicUsesUnsupportedLibcall(const AtomicExpr *E) const { return (Size != Align || toBits(sizeChars) > MaxInlineWidthInBits); } -static ast_type_traits::DynTypedNode getSingleDynTypedNodeFromParentMap( - ASTContext::ParentMapPointers::mapped_type U) { - if (const auto *D = U.dyn_cast<const Decl *>()) - return ast_type_traits::DynTypedNode::create(*D); - if (const auto *S = U.dyn_cast<const Stmt *>()) - return ast_type_traits::DynTypedNode::create(*S); - return *U.get<ast_type_traits::DynTypedNode *>(); -} - -namespace { - /// Template specializations to abstract away from pointers and TypeLocs. /// @{ template <typename T> -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 @@ createDynTypedNode(const NestedNameSpecifierLoc &Node) { } /// @} - /// 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: - /// Builds and returns the translation unit's parent map. - /// - /// The caller takes ownership of the returned \c ParentMap. - static std::pair<ASTContext::ParentMapPointers *, - ASTContext::ParentMapOtherNodes *> - buildMap(TranslationUnitDecl &TU) { - ParentMapASTVisitor Visitor(new ASTContext::ParentMapPointers, - new ASTContext::ParentMapOtherNodes); - Visitor.TraverseDecl(&TU); - return std::make_pair(Visitor.Parents, Visitor.OtherParents); - } +/// 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<ASTVisitor> { +public: + ASTVisitor(ParentMap &Map) : Map(Map) {} - private: - friend class RecursiveASTVisitor<ParentMapASTVisitor>; +private: + friend class RecursiveASTVisitor<ASTVisitor>; - using VisitorBase = RecursiveASTVisitor<ParentMapASTVisitor>; + using VisitorBase = RecursiveASTVisitor<ASTVisitor>; - ParentMapASTVisitor(ASTContext::ParentMapPointers *Parents, - ASTContext::ParentMapOtherNodes *OtherParents) - : Parents(Parents), OtherParents(OtherParents) {} + bool shouldVisitTemplateInstantiations() const { return true; } - bool shouldVisitTemplateInstantiations() const { - return true; - } + bool shouldVisitImplicitCode() const { return true; } - bool shouldVisitImplicitCode() const { + template <typename T, typename MapNodeTy, typename BaseTraverseFn, + typename MapTy> + bool TraverseNode(T Node, MapNodeTy MapNode, BaseTraverseFn BaseTraverse, + MapTy *Parents) { + if (!Node) return true; - } - - template <typename T, typename MapNodeTy, typename BaseTraverseFn, - typename MapTy> - 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<Decl>()) - NodeOrVector = D; - else if (const auto *S = ParentStack.back().get<Stmt>()) - NodeOrVector = S; - else - NodeOrVector = - new ast_type_traits::DynTypedNode(ParentStack.back()); - } else { - if (!NodeOrVector.template is<ASTContext::ParentVector *>()) { - auto *Vector = new ASTContext::ParentVector( - 1, getSingleDynTypedNodeFromParentMap(NodeOrVector)); - delete NodeOrVector - .template dyn_cast<ast_type_traits::DynTypedNode *>(); - NodeOrVector = Vector; - } - - auto *Vector = - NodeOrVector.template get<ASTContext::ParentVector *>(); - // 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<Decl>()) + NodeOrVector = D; + else if (const auto *S = ParentStack.back().get<Stmt>()) + NodeOrVector = S; + else + NodeOrVector = new ast_type_traits::DynTypedNode(ParentStack.back()); + } else { + if (!NodeOrVector.template is<ParentVector *>()) { + auto *Vector = new ParentVector( + 1, getSingleDynTypedNodeFromParentMap(NodeOrVector)); + delete NodeOrVector + .template dyn_cast<ast_type_traits::DynTypedNode *>(); + 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<ParentVector *>(); + // 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<ast_type_traits::DynTypedNode, 16> ParentStack; - }; + bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) { + return TraverseNode( + NNSLocNode, ast_type_traits::DynTypedNode::create(NNSLocNode), + [&] { return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode); }, + &Map.OtherParents); + } -} // namespace + ParentMap ⤅ + llvm::SmallVector<ast_type_traits::DynTypedNode, 16> ParentStack; +}; -template <typename NodeTy, typename MapTy> -static ASTContext::DynTypedNodeList getDynNodeFromMap(const NodeTy &Node, - const MapTy &Map) { - auto I = Map.find(Node); - if (I == Map.end()) { - return llvm::ArrayRef<ast_type_traits::DynTypedNode>(); - } - if (const auto *V = - I->second.template dyn_cast<ASTContext::ParentVector *>()) { - 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<ParentMap>(*this); + return Parents->getParents(Node); } bool diff --git a/lib/ASTMatchers/ASTMatchFinder.cpp b/lib/ASTMatchers/ASTMatchFinder.cpp index 63f8395b82..8d65714317 100644 --- a/lib/ASTMatchers/ASTMatchFinder.cpp +++ b/lib/ASTMatchers/ASTMatchFinder.cpp @@ -635,10 +635,6 @@ private: bool memoizedMatchesAncestorOfRecursively( const ast_type_traits::DynTypedNode &Node, const DynTypedMatcher &Matcher, BoundNodesTreeBuilder *Builder, AncestorMatchMode MatchMode) { - if (Node.get<TranslationUnitDecl>() == - 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 @@ private: 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<TranslationUnitDecl>() || + /* 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 @@ void MatchFinder::matchAST(ASTContext &Context) { internal::MatchASTVisitor Visitor(&Matchers, Options); Visitor.set_active_ast_context(&Context); Visitor.onStartOfTranslationUnit(); - Visitor.TraverseDecl(Context.getTranslationUnitDecl()); + Visitor.TraverseAST(Context); Visitor.onEndOfTranslationUnit(); } |