[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
llvm-svn: 346847
diff --git a/clang/lib/AST/ASTContext.cpp b/clang/lib/AST/ASTContext.cpp
index 33c5b50..1ac46f8 100644
--- a/clang/lib/AST/ASTContext.cpp
+++ b/clang/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<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 @@
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 @@
}
/// @}
- /// 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 {
+ bool shouldVisitImplicitCode() const { 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;
- }
-
- bool shouldVisitImplicitCode() const {
- 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;
}
+
+ 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 TraverseDecl(Decl *DeclNode) {
- return TraverseNode(DeclNode, DeclNode,
- [&] { return VisitorBase::TraverseDecl(DeclNode); },
- Parents);
- }
-
- bool TraverseStmt(Stmt *StmtNode) {
- return TraverseNode(StmtNode, StmtNode,
- [&] { return VisitorBase::TraverseStmt(StmtNode); },
- Parents);
- }
-
- bool TraverseTypeLoc(TypeLoc TypeLocNode) {
- return TraverseNode(
- TypeLocNode, ast_type_traits::DynTypedNode::create(TypeLocNode),
- [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); },
- OtherParents);
- }
-
- bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) {
- return TraverseNode(
- NNSLocNode, ast_type_traits::DynTypedNode::create(NNSLocNode),
- [&] {
- return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode);
- },
- OtherParents);
- }
-
- ASTContext::ParentMapPointers *Parents;
- ASTContext::ParentMapOtherNodes *OtherParents;
- llvm::SmallVector<ast_type_traits::DynTypedNode, 16> ParentStack;
- };
-
-} // namespace
-
-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>();
+ ParentStack.push_back(createDynTypedNode(Node));
+ bool Result = BaseTraverse();
+ ParentStack.pop_back();
+ return Result;
}
- if (const auto *V =
- I->second.template dyn_cast<ASTContext::ParentVector *>()) {
- return llvm::makeArrayRef(*V);
+
+ bool TraverseDecl(Decl *DeclNode) {
+ return TraverseNode(
+ DeclNode, DeclNode, [&] { return VisitorBase::TraverseDecl(DeclNode); },
+ &Map.PointerParents);
}
- return getSingleDynTypedNodeFromParentMap(I->second);
+
+ bool TraverseStmt(Stmt *StmtNode) {
+ return TraverseNode(
+ StmtNode, StmtNode, [&] { return VisitorBase::TraverseStmt(StmtNode); },
+ &Map.PointerParents);
+ }
+
+ bool TraverseTypeLoc(TypeLoc TypeLocNode) {
+ return TraverseNode(
+ TypeLocNode, ast_type_traits::DynTypedNode::create(TypeLocNode),
+ [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); },
+ &Map.OtherParents);
+ }
+
+ bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) {
+ return TraverseNode(
+ NNSLocNode, ast_type_traits::DynTypedNode::create(NNSLocNode),
+ [&] { return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode); },
+ &Map.OtherParents);
+ }
+
+ ParentMap ⤅
+ llvm::SmallVector<ast_type_traits::DynTypedNode, 16> ParentStack;
+};
+
+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