Reverted for now in r250889.
On Wed, Oct 21, 2015 at 12:07 PM, Daniel Jasper <djas...@google.com> wrote: > I think we'll need to come up with a different solution. The problem is that > DynTypedNode is 5 times larger than the bare pointer and we are storing many > more elements in the ParentMap. This means, this change is effectively > increasing the parent map by 10x and it was already large to begin with. > > Please revert and lets come up with a different solution. > > On Tue, Oct 20, 2015 at 5:08 PM, Benjamin Kramer via cfe-commits > <cfe-commits@lists.llvm.org> wrote: >> >> Author: d0k >> Date: Tue Oct 20 10:08:46 2015 >> New Revision: 250831 >> >> URL: http://llvm.org/viewvc/llvm-project?rev=250831&view=rev >> Log: >> [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 >> >> Modified: >> cfe/trunk/include/clang/AST/ASTContext.h >> cfe/trunk/include/clang/AST/ASTTypeTraits.h >> cfe/trunk/include/clang/ASTMatchers/ASTMatchers.h >> cfe/trunk/include/clang/ASTMatchers/ASTMatchersInternal.h >> cfe/trunk/lib/AST/ASTContext.cpp >> cfe/trunk/lib/ASTMatchers/ASTMatchFinder.cpp >> cfe/trunk/unittests/AST/ASTContextParentMapTest.cpp >> cfe/trunk/unittests/ASTMatchers/Dynamic/ParserTest.cpp >> cfe/trunk/unittests/ASTMatchers/Dynamic/RegistryTest.cpp >> >> Modified: cfe/trunk/include/clang/AST/ASTContext.h >> URL: >> http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/AST/ASTContext.h?rev=250831&r1=250830&r2=250831&view=diff >> >> ============================================================================== >> --- cfe/trunk/include/clang/AST/ASTContext.h (original) >> +++ cfe/trunk/include/clang/AST/ASTContext.h Tue Oct 20 10:08:46 2015 >> @@ -452,7 +452,7 @@ public: >> typedef llvm::SmallVector<ast_type_traits::DynTypedNode, 2> >> ParentVector; >> >> /// \brief Maps from a node to its parents. >> - typedef llvm::DenseMap<const void *, >> + typedef llvm::DenseMap<ast_type_traits::DynTypedNode, >> llvm::PointerUnion<ast_type_traits::DynTypedNode >> *, >> ParentVector *>> ParentMap; >> >> >> Modified: cfe/trunk/include/clang/AST/ASTTypeTraits.h >> URL: >> http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/AST/ASTTypeTraits.h?rev=250831&r1=250830&r2=250831&view=diff >> >> ============================================================================== >> --- cfe/trunk/include/clang/AST/ASTTypeTraits.h (original) >> +++ cfe/trunk/include/clang/AST/ASTTypeTraits.h Tue Oct 20 10:08:46 2015 >> @@ -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<TypeLoc>().isSame(NodeKind)) { >> + auto TLA = getUnchecked<TypeLoc>(); >> + auto TLB = Other.getUnchecked<TypeLoc>(); >> + return std::make_pair(TLA.getType().getAsOpaquePtr(), >> + TLA.getOpaqueData()) < >> + std::make_pair(TLB.getType().getAsOpaquePtr(), >> + TLB.getOpaqueData()); >> + } >> + >> + if (ASTNodeKind::getFromNodeKind<NestedNameSpecifierLoc>().isSame( >> + NodeKind)) { >> + auto NNSLA = getUnchecked<NestedNameSpecifierLoc>(); >> + auto NNSLB = Other.getUnchecked<NestedNameSpecifierLoc>(); >> + 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<QualType>().isSame(NodeKind)) >> return getUnchecked<QualType>() == Other.getUnchecked<QualType>(); >> >> + if (ASTNodeKind::getFromNodeKind<TypeLoc>().isSame(NodeKind)) >> + return getUnchecked<TypeLoc>() == Other.getUnchecked<TypeLoc>(); >> + >> + if >> (ASTNodeKind::getFromNodeKind<NestedNameSpecifierLoc>().isSame(NodeKind)) >> + return getUnchecked<NestedNameSpecifierLoc>() == >> + Other.getUnchecked<NestedNameSpecifierLoc>(); >> + >> 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<TypeLoc>().isSame(Val.NodeKind)) { >> + auto TL = Val.getUnchecked<TypeLoc>(); >> + return llvm::hash_combine(TL.getType().getAsOpaquePtr(), >> + TL.getOpaqueData()); >> + } >> + >> + if (ASTNodeKind::getFromNodeKind<NestedNameSpecifierLoc>().isSame( >> + Val.NodeKind)) { >> + auto NNSL = Val.getUnchecked<NestedNameSpecifierLoc>(); >> + 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 <typename T, typename EnablerT = void> struct BaseConverter; >> @@ -420,6 +488,10 @@ template <> >> struct DenseMapInfo<clang::ast_type_traits::ASTNodeKind> >> : clang::ast_type_traits::ASTNodeKind::DenseMapInfo {}; >> >> +template <> >> +struct DenseMapInfo<clang::ast_type_traits::DynTypedNode> >> + : clang::ast_type_traits::DynTypedNode::DenseMapInfo {}; >> + >> } // end namespace llvm >> >> #endif >> >> Modified: cfe/trunk/include/clang/ASTMatchers/ASTMatchers.h >> URL: >> http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/ASTMatchers/ASTMatchers.h?rev=250831&r1=250830&r2=250831&view=diff >> >> ============================================================================== >> --- cfe/trunk/include/clang/ASTMatchers/ASTMatchers.h (original) >> +++ cfe/trunk/include/clang/ASTMatchers/ASTMatchers.h Tue Oct 20 10:08:46 >> 2015 >> @@ -2068,8 +2068,10 @@ internal::Matcher<T> findAll(const inter >> /// >> /// Usable as: Any Matcher >> const internal::ArgumentAdaptingMatcherFunc< >> - internal::HasParentMatcher, internal::TypeList<Decl, Stmt>, >> - internal::TypeList<Decl, Stmt> > LLVM_ATTRIBUTE_UNUSED hasParent = >> {}; >> + internal::HasParentMatcher, >> + internal::TypeList<Decl, NestedNameSpecifierLoc, Stmt, TypeLoc>, >> + internal::TypeList<Decl, NestedNameSpecifierLoc, Stmt, TypeLoc>> >> + LLVM_ATTRIBUTE_UNUSED hasParent = {}; >> >> /// \brief Matches AST nodes that have an ancestor that matches the >> provided >> /// matcher. >> @@ -2083,8 +2085,10 @@ const internal::ArgumentAdaptingMatcherF >> /// >> /// Usable as: Any Matcher >> const internal::ArgumentAdaptingMatcherFunc< >> - internal::HasAncestorMatcher, internal::TypeList<Decl, Stmt>, >> - internal::TypeList<Decl, Stmt> > LLVM_ATTRIBUTE_UNUSED hasAncestor = >> {}; >> + internal::HasAncestorMatcher, >> + internal::TypeList<Decl, NestedNameSpecifierLoc, Stmt, TypeLoc>, >> + internal::TypeList<Decl, NestedNameSpecifierLoc, Stmt, TypeLoc>> >> + LLVM_ATTRIBUTE_UNUSED hasAncestor = {}; >> >> /// \brief Matches if the provided matcher does not match. >> /// >> >> Modified: cfe/trunk/include/clang/ASTMatchers/ASTMatchersInternal.h >> URL: >> http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/ASTMatchers/ASTMatchersInternal.h?rev=250831&r1=250830&r2=250831&view=diff >> >> ============================================================================== >> --- cfe/trunk/include/clang/ASTMatchers/ASTMatchersInternal.h (original) >> +++ cfe/trunk/include/clang/ASTMatchers/ASTMatchersInternal.h Tue Oct 20 >> 10:08:46 2015 >> @@ -848,8 +848,10 @@ public: >> BoundNodesTreeBuilder *Builder, >> AncestorMatchMode MatchMode) { >> static_assert(std::is_base_of<Decl, T>::value || >> - std::is_base_of<Stmt, T>::value, >> - "only Decl or Stmt allowed for recursive matching"); >> + std::is_base_of<NestedNameSpecifierLoc, T>::value >> || >> + std::is_base_of<Stmt, T>::value || >> + std::is_base_of<TypeLoc, T>::value, >> + "type not allowed for recursive matching"); >> return matchesAncestorOf(ast_type_traits::DynTypedNode::create(Node), >> Matcher, Builder, MatchMode); >> } >> >> Modified: cfe/trunk/lib/AST/ASTContext.cpp >> URL: >> http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/AST/ASTContext.cpp?rev=250831&r1=250830&r2=250831&view=diff >> >> ============================================================================== >> --- cfe/trunk/lib/AST/ASTContext.cpp (original) >> +++ cfe/trunk/lib/AST/ASTContext.cpp Tue Oct 20 10:08:46 2015 >> @@ -8678,6 +8678,23 @@ bool ASTContext::AtomicUsesUnsupportedLi >> >> namespace { >> >> +/// Template specializations to abstract away from pointers and TypeLocs. >> +/// @{ >> +template <typename T> >> +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<ParentMapASTVisitor> { >> >> public: >> @@ -8717,21 +8735,11 @@ namespace { >> } >> >> template <typename T> >> - 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<ast_type_traits::DynTypedNode, 16> ParentStack; >> >> @@ -8781,16 +8798,13 @@ namespace { >> >> ArrayRef<ast_type_traits::DynTypedNode> >> 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; >> } >> >> Modified: cfe/trunk/lib/ASTMatchers/ASTMatchFinder.cpp >> URL: >> http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/ASTMatchers/ASTMatchFinder.cpp?rev=250831&r1=250830&r2=250831&view=diff >> >> ============================================================================== >> --- cfe/trunk/lib/ASTMatchers/ASTMatchFinder.cpp (original) >> +++ cfe/trunk/lib/ASTMatchers/ASTMatchFinder.cpp Tue Oct 20 10:08:46 2015 >> @@ -621,9 +621,6 @@ private: >> if (Node.get<TranslationUnitDecl>() == >> 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::TraverseNestedName >> >> 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()) >> >> Modified: cfe/trunk/unittests/AST/ASTContextParentMapTest.cpp >> URL: >> http://llvm.org/viewvc/llvm-project/cfe/trunk/unittests/AST/ASTContextParentMapTest.cpp?rev=250831&r1=250830&r2=250831&view=diff >> >> ============================================================================== >> --- cfe/trunk/unittests/AST/ASTContextParentMapTest.cpp (original) >> +++ cfe/trunk/unittests/AST/ASTContextParentMapTest.cpp Tue Oct 20 >> 10:08:46 2015 >> @@ -38,6 +38,19 @@ TEST(GetParents, ReturnsParentForStmt) { >> ifStmt(hasParent(compoundStmt())))); >> } >> >> +TEST(GetParents, ReturnsParentForTypeLoc) { >> + MatchVerifier<TypeLoc> Verifier; >> + EXPECT_TRUE( >> + Verifier.match("namespace a { class b {}; } void f(a::b) {}", >> + >> typeLoc(hasParent(typeLoc(hasParent(functionDecl())))))); >> +} >> + >> +TEST(GetParents, ReturnsParentForNestedNameSpecifierLoc) { >> + MatchVerifier<NestedNameSpecifierLoc> Verifier; >> + EXPECT_TRUE(Verifier.match("namespace a { class b {}; } void f(a::b) >> {}", >> + >> nestedNameSpecifierLoc(hasParent(typeLoc())))); >> +} >> + >> TEST(GetParents, ReturnsParentInsideTemplateInstantiations) { >> MatchVerifier<Decl> DeclVerifier; >> EXPECT_TRUE(DeclVerifier.match( >> >> Modified: cfe/trunk/unittests/ASTMatchers/Dynamic/ParserTest.cpp >> URL: >> http://llvm.org/viewvc/llvm-project/cfe/trunk/unittests/ASTMatchers/Dynamic/ParserTest.cpp?rev=250831&r1=250830&r2=250831&view=diff >> >> ============================================================================== >> --- cfe/trunk/unittests/ASTMatchers/Dynamic/ParserTest.cpp (original) >> +++ cfe/trunk/unittests/ASTMatchers/Dynamic/ParserTest.cpp Tue Oct 20 >> 10:08:46 2015 >> @@ -318,7 +318,8 @@ TEST(ParserTest, CompletionNamedValues) >> Comps[1].MatcherDecl); >> >> EXPECT_EQ("arent(", Comps[2].TypedText); >> - EXPECT_EQ("Matcher<Decl> hasParent(Matcher<Decl|Stmt>)", >> + EXPECT_EQ("Matcher<Decl> " >> + >> "hasParent(Matcher<NestedNameSpecifierLoc|TypeLoc|Decl|...>)", >> Comps[2].MatcherDecl); >> } >> >> >> Modified: cfe/trunk/unittests/ASTMatchers/Dynamic/RegistryTest.cpp >> URL: >> http://llvm.org/viewvc/llvm-project/cfe/trunk/unittests/ASTMatchers/Dynamic/RegistryTest.cpp?rev=250831&r1=250830&r2=250831&view=diff >> >> ============================================================================== >> --- cfe/trunk/unittests/ASTMatchers/Dynamic/RegistryTest.cpp (original) >> +++ cfe/trunk/unittests/ASTMatchers/Dynamic/RegistryTest.cpp Tue Oct 20 >> 10:08:46 2015 >> @@ -447,8 +447,10 @@ TEST_F(RegistryTest, Errors) { >> TEST_F(RegistryTest, Completion) { >> CompVector Comps = getCompletions(); >> // Overloaded >> - EXPECT_TRUE(hasCompletion( >> - Comps, "hasParent(", "Matcher<Decl|Stmt> >> hasParent(Matcher<Decl|Stmt>)")); >> + EXPECT_TRUE(hasCompletion(Comps, "hasParent(", >> + >> "Matcher<NestedNameSpecifierLoc|TypeLoc|Decl|...> " >> + >> "hasParent(Matcher<NestedNameSpecifierLoc|TypeLoc|" >> + "Decl|...>)")); >> // Variadic. >> EXPECT_TRUE(hasCompletion(Comps, "whileStmt(", >> "Matcher<Stmt> >> whileStmt(Matcher<WhileStmt>...)")); >> @@ -463,8 +465,10 @@ TEST_F(RegistryTest, Completion) { >> >> EXPECT_TRUE(hasCompletion(WhileComps, "hasBody(", >> "Matcher<WhileStmt> >> hasBody(Matcher<Stmt>)")); >> - EXPECT_TRUE(hasCompletion(WhileComps, "hasParent(", >> - "Matcher<Stmt> >> hasParent(Matcher<Decl|Stmt>)")); >> + EXPECT_TRUE(hasCompletion(WhileComps, "hasParent(", "Matcher<Stmt> " >> + >> "hasParent(Matcher<" >> + >> "NestedNameSpecifierLoc|" >> + >> "TypeLoc|Decl|...>)")); >> EXPECT_TRUE( >> hasCompletion(WhileComps, "allOf(", "Matcher<T> >> allOf(Matcher<T>...)")); >> >> >> >> _______________________________________________ >> cfe-commits mailing list >> cfe-commits@lists.llvm.org >> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits > > _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
