From 8f3d8be71a4878852ea5edc5723e8effea21572f Mon Sep 17 00:00:00 2001 From: Benjamin Kramer Date: Tue, 20 Oct 2015 15:08:46 +0000 Subject: [PATCH] [AST] Put TypeLocs and NestedNameSpecifierLocs into the ParentMap. Firstly this changes the type of parent map to be keyed on DynTypedNode to simplify the following changes. This comes with a DenseMapInfo for DynTypedNode, which is a bit incomplete still and will probably only work for parentmap right now. Then the RecursiveASTVisitor in ASTContext is updated and finally ASTMatchers hasParent and hasAncestor learn about the new functionality. Now ParentMap is only missing TemplateArgumentLocs and CXXCtorInitializers. Differential Revision: http://reviews.llvm.org/D13897 git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@250831 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/clang/AST/ASTContext.h | 2 +- include/clang/AST/ASTTypeTraits.h | 78 ++++++++++++++++++- include/clang/ASTMatchers/ASTMatchers.h | 12 ++- .../clang/ASTMatchers/ASTMatchersInternal.h | 6 +- lib/AST/ASTContext.cpp | 50 +++++++----- lib/ASTMatchers/ASTMatchFinder.cpp | 7 +- unittests/AST/ASTContextParentMapTest.cpp | 13 ++++ unittests/ASTMatchers/Dynamic/ParserTest.cpp | 3 +- .../ASTMatchers/Dynamic/RegistryTest.cpp | 12 ++- 9 files changed, 147 insertions(+), 36 deletions(-) diff --git a/include/clang/AST/ASTContext.h b/include/clang/AST/ASTContext.h index 5b8240925d..7c7b910077 100644 --- a/include/clang/AST/ASTContext.h +++ b/include/clang/AST/ASTContext.h @@ -452,7 +452,7 @@ public: typedef llvm::SmallVector ParentVector; /// \brief Maps from a node to its parents. - typedef llvm::DenseMap> ParentMap; diff --git a/include/clang/AST/ASTTypeTraits.h b/include/clang/AST/ASTTypeTraits.h index dc3c34f28d..f5274d5043 100644 --- a/include/clang/AST/ASTTypeTraits.h +++ b/include/clang/AST/ASTTypeTraits.h @@ -253,10 +253,30 @@ public: /// @{ /// \brief Imposes an order on \c DynTypedNode. /// - /// Supports comparison of nodes that support memoization. - /// FIXME: Implement comparsion for other node types (currently - /// only Stmt, Decl, Type and NestedNameSpecifier return memoization data). + /// FIXME: Implement comparsion for other node types. bool operator<(const DynTypedNode &Other) const { + if (!NodeKind.isSame(Other.NodeKind)) + return NodeKind < Other.NodeKind; + + if (ASTNodeKind::getFromNodeKind().isSame(NodeKind)) { + auto TLA = getUnchecked(); + auto TLB = Other.getUnchecked(); + return std::make_pair(TLA.getType().getAsOpaquePtr(), + TLA.getOpaqueData()) < + std::make_pair(TLB.getType().getAsOpaquePtr(), + TLB.getOpaqueData()); + } + + if (ASTNodeKind::getFromNodeKind().isSame( + NodeKind)) { + auto NNSLA = getUnchecked(); + auto NNSLB = Other.getUnchecked(); + return std::make_pair(NNSLA.getNestedNameSpecifier(), + NNSLA.getOpaqueData()) < + std::make_pair(NNSLB.getNestedNameSpecifier(), + NNSLB.getOpaqueData()); + } + assert(getMemoizationData() && Other.getMemoizationData()); return getMemoizationData() < Other.getMemoizationData(); } @@ -270,6 +290,13 @@ public: if (ASTNodeKind::getFromNodeKind().isSame(NodeKind)) return getUnchecked() == Other.getUnchecked(); + if (ASTNodeKind::getFromNodeKind().isSame(NodeKind)) + return getUnchecked() == Other.getUnchecked(); + + if (ASTNodeKind::getFromNodeKind().isSame(NodeKind)) + return getUnchecked() == + Other.getUnchecked(); + assert(getMemoizationData() && Other.getMemoizationData()); return getMemoizationData() == Other.getMemoizationData(); } @@ -278,6 +305,47 @@ public: } /// @} + /// \brief Hooks for using DynTypedNode as a key in a DenseMap. + struct DenseMapInfo { + static inline DynTypedNode getEmptyKey() { + DynTypedNode Node; + Node.NodeKind = ASTNodeKind::DenseMapInfo::getEmptyKey(); + return Node; + } + static inline DynTypedNode getTombstoneKey() { + DynTypedNode Node; + Node.NodeKind = ASTNodeKind::DenseMapInfo::getTombstoneKey(); + return Node; + } + static unsigned getHashValue(const DynTypedNode &Val) { + // FIXME: Add hashing support for the remaining types. + if (ASTNodeKind::getFromNodeKind().isSame(Val.NodeKind)) { + auto TL = Val.getUnchecked(); + return llvm::hash_combine(TL.getType().getAsOpaquePtr(), + TL.getOpaqueData()); + } + + if (ASTNodeKind::getFromNodeKind().isSame( + Val.NodeKind)) { + auto NNSL = Val.getUnchecked(); + return llvm::hash_combine(NNSL.getNestedNameSpecifier(), + NNSL.getOpaqueData()); + } + + assert(Val.getMemoizationData()); + return llvm::hash_value(Val.getMemoizationData()); + } + static bool isEqual(const DynTypedNode &LHS, const DynTypedNode &RHS) { + auto Empty = ASTNodeKind::DenseMapInfo::getEmptyKey(); + auto TombStone = ASTNodeKind::DenseMapInfo::getTombstoneKey(); + return (ASTNodeKind::DenseMapInfo::isEqual(LHS.NodeKind, Empty) && + ASTNodeKind::DenseMapInfo::isEqual(RHS.NodeKind, Empty)) || + (ASTNodeKind::DenseMapInfo::isEqual(LHS.NodeKind, TombStone) && + ASTNodeKind::DenseMapInfo::isEqual(RHS.NodeKind, TombStone)) || + LHS == RHS; + } + }; + private: /// \brief Takes care of converting from and to \c T. template struct BaseConverter; @@ -420,6 +488,10 @@ template <> struct DenseMapInfo : clang::ast_type_traits::ASTNodeKind::DenseMapInfo {}; +template <> +struct DenseMapInfo + : clang::ast_type_traits::DynTypedNode::DenseMapInfo {}; + } // end namespace llvm #endif diff --git a/include/clang/ASTMatchers/ASTMatchers.h b/include/clang/ASTMatchers/ASTMatchers.h index 484cc943ea..0a1800b9d4 100644 --- a/include/clang/ASTMatchers/ASTMatchers.h +++ b/include/clang/ASTMatchers/ASTMatchers.h @@ -2068,8 +2068,10 @@ internal::Matcher findAll(const internal::Matcher &Matcher) { /// /// Usable as: Any Matcher const internal::ArgumentAdaptingMatcherFunc< - internal::HasParentMatcher, internal::TypeList, - internal::TypeList > LLVM_ATTRIBUTE_UNUSED hasParent = {}; + internal::HasParentMatcher, + internal::TypeList, + internal::TypeList> + LLVM_ATTRIBUTE_UNUSED hasParent = {}; /// \brief Matches AST nodes that have an ancestor that matches the provided /// matcher. @@ -2083,8 +2085,10 @@ const internal::ArgumentAdaptingMatcherFunc< /// /// Usable as: Any Matcher const internal::ArgumentAdaptingMatcherFunc< - internal::HasAncestorMatcher, internal::TypeList, - internal::TypeList > LLVM_ATTRIBUTE_UNUSED hasAncestor = {}; + internal::HasAncestorMatcher, + internal::TypeList, + internal::TypeList> + LLVM_ATTRIBUTE_UNUSED hasAncestor = {}; /// \brief Matches if the provided matcher does not match. /// diff --git a/include/clang/ASTMatchers/ASTMatchersInternal.h b/include/clang/ASTMatchers/ASTMatchersInternal.h index 8e1abc6f77..55839c53b4 100644 --- a/include/clang/ASTMatchers/ASTMatchersInternal.h +++ b/include/clang/ASTMatchers/ASTMatchersInternal.h @@ -848,8 +848,10 @@ public: BoundNodesTreeBuilder *Builder, AncestorMatchMode MatchMode) { static_assert(std::is_base_of::value || - std::is_base_of::value, - "only Decl or Stmt allowed for recursive matching"); + std::is_base_of::value || + std::is_base_of::value || + std::is_base_of::value, + "type not allowed for recursive matching"); return matchesAncestorOf(ast_type_traits::DynTypedNode::create(Node), Matcher, Builder, MatchMode); } diff --git a/lib/AST/ASTContext.cpp b/lib/AST/ASTContext.cpp index 848158877a..c26d772139 100644 --- a/lib/AST/ASTContext.cpp +++ b/lib/AST/ASTContext.cpp @@ -8678,6 +8678,23 @@ bool ASTContext::AtomicUsesUnsupportedLibcall(const AtomicExpr *E) const { namespace { +/// Template specializations to abstract away from pointers and TypeLocs. +/// @{ +template +ast_type_traits::DynTypedNode createDynTypedNode(const T &Node) { + return ast_type_traits::DynTypedNode::create(*Node); +} +template <> +ast_type_traits::DynTypedNode createDynTypedNode(const TypeLoc &Node) { + return ast_type_traits::DynTypedNode::create(Node); +} +template <> +ast_type_traits::DynTypedNode +createDynTypedNode(const NestedNameSpecifierLoc &Node) { + return ast_type_traits::DynTypedNode::create(Node); +} +/// @} + /// \brief A \c RecursiveASTVisitor that builds a map from nodes to their /// parents as defined by the \c RecursiveASTVisitor. /// @@ -8685,7 +8702,8 @@ namespace { /// 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. +/// FIXME: Currently only builds up the map using \c Stmt, \c Decl, +/// \c NestedNameSpecifierLoc and \c TypeLoc nodes. class ParentMapASTVisitor : public RecursiveASTVisitor { public: @@ -8717,21 +8735,11 @@ namespace { } template - bool TraverseNode(T *Node, bool(VisitorBase:: *traverse) (T *)) { + bool TraverseNode(T Node, bool (VisitorBase::*traverse)(T)) { 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)[Node]; + auto &NodeOrVector = (*Parents)[createDynTypedNode(Node)]; if (NodeOrVector.isNull()) { NodeOrVector = new ast_type_traits::DynTypedNode(ParentStack.back()); } else { @@ -8757,7 +8765,7 @@ namespace { Vector->push_back(ParentStack.back()); } } - ParentStack.push_back(ast_type_traits::DynTypedNode::create(*Node)); + ParentStack.push_back(createDynTypedNode(Node)); bool Result = (this ->* traverse) (Node); ParentStack.pop_back(); return Result; @@ -8771,6 +8779,15 @@ namespace { return TraverseNode(StmtNode, &VisitorBase::TraverseStmt); } + bool TraverseTypeLoc(TypeLoc TypeLocNode) { + return TraverseNode(TypeLocNode, &VisitorBase::TraverseTypeLoc); + } + + bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) { + return TraverseNode(NNSLocNode, + &VisitorBase::TraverseNestedNameSpecifierLoc); + } + ASTContext::ParentMap *Parents; llvm::SmallVector ParentStack; @@ -8781,16 +8798,13 @@ namespace { ArrayRef ASTContext::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()); + ParentMap::const_iterator I = AllParents->find(Node); if (I == AllParents->end()) { return None; } diff --git a/lib/ASTMatchers/ASTMatchFinder.cpp b/lib/ASTMatchers/ASTMatchFinder.cpp index 8807b13c5e..571e7dac24 100644 --- a/lib/ASTMatchers/ASTMatchFinder.cpp +++ b/lib/ASTMatchers/ASTMatchFinder.cpp @@ -621,9 +621,6 @@ private: if (Node.get() == ActiveASTContext->getTranslationUnitDecl()) return false; - assert(Node.getMemoizationData() && - "Invariant broken: only nodes that support memoization may be " - "used in the parent map."); MatchKey Key; Key.MatcherID = Matcher.getID(); @@ -867,7 +864,11 @@ bool MatchASTVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *NNS) { bool MatchASTVisitor::TraverseNestedNameSpecifierLoc( NestedNameSpecifierLoc NNS) { + if (!NNS) + return true; + match(NNS); + // We only match the nested name specifier here (as opposed to traversing it) // because the traversal is already done in the parallel "Loc"-hierarchy. if (NNS.hasQualifier()) diff --git a/unittests/AST/ASTContextParentMapTest.cpp b/unittests/AST/ASTContextParentMapTest.cpp index 94e9735654..b1d7db4164 100644 --- a/unittests/AST/ASTContextParentMapTest.cpp +++ b/unittests/AST/ASTContextParentMapTest.cpp @@ -38,6 +38,19 @@ TEST(GetParents, ReturnsParentForStmt) { ifStmt(hasParent(compoundStmt())))); } +TEST(GetParents, ReturnsParentForTypeLoc) { + MatchVerifier Verifier; + EXPECT_TRUE( + Verifier.match("namespace a { class b {}; } void f(a::b) {}", + typeLoc(hasParent(typeLoc(hasParent(functionDecl())))))); +} + +TEST(GetParents, ReturnsParentForNestedNameSpecifierLoc) { + MatchVerifier Verifier; + EXPECT_TRUE(Verifier.match("namespace a { class b {}; } void f(a::b) {}", + nestedNameSpecifierLoc(hasParent(typeLoc())))); +} + TEST(GetParents, ReturnsParentInsideTemplateInstantiations) { MatchVerifier DeclVerifier; EXPECT_TRUE(DeclVerifier.match( diff --git a/unittests/ASTMatchers/Dynamic/ParserTest.cpp b/unittests/ASTMatchers/Dynamic/ParserTest.cpp index ef66a816aa..2c94a727de 100644 --- a/unittests/ASTMatchers/Dynamic/ParserTest.cpp +++ b/unittests/ASTMatchers/Dynamic/ParserTest.cpp @@ -318,7 +318,8 @@ TEST(ParserTest, CompletionNamedValues) { Comps[1].MatcherDecl); EXPECT_EQ("arent(", Comps[2].TypedText); - EXPECT_EQ("Matcher hasParent(Matcher)", + EXPECT_EQ("Matcher " + "hasParent(Matcher)", Comps[2].MatcherDecl); } diff --git a/unittests/ASTMatchers/Dynamic/RegistryTest.cpp b/unittests/ASTMatchers/Dynamic/RegistryTest.cpp index ca1dfefd53..9b562bcc9d 100644 --- a/unittests/ASTMatchers/Dynamic/RegistryTest.cpp +++ b/unittests/ASTMatchers/Dynamic/RegistryTest.cpp @@ -447,8 +447,10 @@ TEST_F(RegistryTest, Errors) { TEST_F(RegistryTest, Completion) { CompVector Comps = getCompletions(); // Overloaded - EXPECT_TRUE(hasCompletion( - Comps, "hasParent(", "Matcher hasParent(Matcher)")); + EXPECT_TRUE(hasCompletion(Comps, "hasParent(", + "Matcher " + "hasParent(Matcher)")); // Variadic. EXPECT_TRUE(hasCompletion(Comps, "whileStmt(", "Matcher whileStmt(Matcher...)")); @@ -463,8 +465,10 @@ TEST_F(RegistryTest, Completion) { EXPECT_TRUE(hasCompletion(WhileComps, "hasBody(", "Matcher hasBody(Matcher)")); - EXPECT_TRUE(hasCompletion(WhileComps, "hasParent(", - "Matcher hasParent(Matcher)")); + EXPECT_TRUE(hasCompletion(WhileComps, "hasParent(", "Matcher " + "hasParent(Matcher<" + "NestedNameSpecifierLoc|" + "TypeLoc|Decl|...>)")); EXPECT_TRUE( hasCompletion(WhileComps, "allOf(", "Matcher allOf(Matcher...)")); -- 2.40.0