Index: cfe/trunk/include/clang/AST/ASTContext.h =================================================================== --- cfe/trunk/include/clang/AST/ASTContext.h +++ cfe/trunk/include/clang/AST/ASTContext.h @@ -451,11 +451,21 @@ /// \brief Contains parents of a node. typedef llvm::SmallVector ParentVector; - /// \brief Maps from a node to its parents. + /// \brief 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. typedef llvm::DenseMap> ParentMap; + ParentVector *>> ParentMapPointers; + + /// Parent map for nodes without pointer identity. We store a full + /// DynTypedNode for all keys. + typedef llvm::DenseMap< + ast_type_traits::DynTypedNode, + llvm::PointerUnion4> + ParentMapOtherNodes; /// Container for either a single DynTypedNode or for an ArrayRef to /// DynTypedNode. For use with ParentMap. @@ -2513,7 +2523,8 @@ void ReleaseDeclContextMaps(); void ReleaseParentMapEntries(); - std::unique_ptr AllParents; + std::unique_ptr PointerParents; + std::unique_ptr OtherParents; std::unique_ptr VTContext; Index: cfe/trunk/include/clang/AST/ASTTypeTraits.h =================================================================== --- cfe/trunk/include/clang/AST/ASTTypeTraits.h +++ cfe/trunk/include/clang/AST/ASTTypeTraits.h @@ -268,6 +268,28 @@ /// FIXME: Implement comparsion for other node types (currently /// only Stmt, Decl, Type and NestedNameSpecifier return memoization data). 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(); } @@ -281,6 +303,13 @@ 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(); } @@ -289,6 +318,47 @@ } /// @} + /// \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; @@ -426,6 +496,10 @@ struct DenseMapInfo : clang::ast_type_traits::ASTNodeKind::DenseMapInfo {}; +template <> +struct DenseMapInfo + : clang::ast_type_traits::DynTypedNode::DenseMapInfo {}; + } // end namespace llvm #endif Index: cfe/trunk/include/clang/ASTMatchers/ASTMatchers.h =================================================================== --- cfe/trunk/include/clang/ASTMatchers/ASTMatchers.h +++ cfe/trunk/include/clang/ASTMatchers/ASTMatchers.h @@ -2068,8 +2068,10 @@ /// /// 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 @@ /// /// 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. /// Index: cfe/trunk/include/clang/ASTMatchers/ASTMatchersInternal.h =================================================================== --- cfe/trunk/include/clang/ASTMatchers/ASTMatchersInternal.h +++ cfe/trunk/include/clang/ASTMatchers/ASTMatchersInternal.h @@ -848,8 +848,10 @@ 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); } Index: cfe/trunk/lib/AST/ASTContext.cpp =================================================================== --- cfe/trunk/lib/AST/ASTContext.cpp +++ cfe/trunk/lib/AST/ASTContext.cpp @@ -793,8 +793,15 @@ } void ASTContext::ReleaseParentMapEntries() { - if (!AllParents) return; - for (const auto &Entry : *AllParents) { + 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()) { @@ -8670,8 +8677,8 @@ namespace { -ast_type_traits::DynTypedNode -getSingleDynTypedNodeFromParentMap(ASTContext::ParentMap::mapped_type U) { +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()) @@ -8679,6 +8686,23 @@ return *U.get(); } +/// 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. /// @@ -8693,17 +8717,21 @@ /// \brief Builds and returns the translation unit's parent map. /// /// The caller takes ownership of the returned \c ParentMap. - static ASTContext::ParentMap *buildMap(TranslationUnitDecl &TU) { - ParentMapASTVisitor Visitor(new ASTContext::ParentMap); + static std::pair + buildMap(TranslationUnitDecl &TU) { + ParentMapASTVisitor Visitor(new ASTContext::ParentMapPointers, + new ASTContext::ParentMapOtherNodes); Visitor.TraverseDecl(&TU); - return Visitor.Parents; + return std::make_pair(Visitor.Parents, Visitor.OtherParents); } private: typedef RecursiveASTVisitor VisitorBase; - ParentMapASTVisitor(ASTContext::ParentMap *Parents) : Parents(Parents) { - } + ParentMapASTVisitor(ASTContext::ParentMapPointers *Parents, + ASTContext::ParentMapOtherNodes *OtherParents) + : Parents(Parents), OtherParents(OtherParents) {} bool shouldVisitTemplateInstantiations() const { return true; @@ -8717,8 +8745,9 @@ return false; } - template - bool TraverseNode(T *Node, bool(VisitorBase:: *traverse) (T *)) { + template + bool TraverseNode(T Node, MapNodeTy MapNode, + bool (VisitorBase::*traverse)(T), MapTy *Parents) { if (!Node) return true; if (ParentStack.size() > 0) { @@ -8732,7 +8761,7 @@ // 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)[MapNode]; if (NodeOrVector.isNull()) { if (const auto *D = ParentStack.back().get()) NodeOrVector = D; @@ -8765,21 +8794,36 @@ 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; } bool TraverseDecl(Decl *DeclNode) { - return TraverseNode(DeclNode, &VisitorBase::TraverseDecl); + return TraverseNode(DeclNode, DeclNode, &VisitorBase::TraverseDecl, + Parents); } bool TraverseStmt(Stmt *StmtNode) { - return TraverseNode(StmtNode, &VisitorBase::TraverseStmt); + return TraverseNode(StmtNode, StmtNode, &VisitorBase::TraverseStmt, + Parents); + } + + bool TraverseTypeLoc(TypeLoc TypeLocNode) { + return TraverseNode(TypeLocNode, + ast_type_traits::DynTypedNode::create(TypeLocNode), + &VisitorBase::TraverseTypeLoc, OtherParents); } - ASTContext::ParentMap *Parents; + bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) { + return TraverseNode( + NNSLocNode, ast_type_traits::DynTypedNode::create(NNSLocNode), + &VisitorBase::TraverseNestedNameSpecifierLoc, OtherParents); + } + + ASTContext::ParentMapPointers *Parents; + ASTContext::ParentMapOtherNodes *OtherParents; llvm::SmallVector ParentStack; friend class RecursiveASTVisitor; @@ -8787,27 +8831,33 @@ } // end namespace -ASTContext::DynTypedNodeList -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()); - if (I == AllParents->end()) { +template +static ASTContext::DynTypedNodeList getDynNodeFromMap(const NodeTy &Node, + const MapTy &Map) { + auto I = Map.find(Node); + if (I == Map.end()) { return llvm::ArrayRef(); } - if (auto *V = I->second.dyn_cast()) { + if (auto *V = I->second.template dyn_cast()) { return llvm::makeArrayRef(*V); } return getSingleDynTypedNodeFromParentMap(I->second); } +ASTContext::DynTypedNodeList +ASTContext::getParents(const ast_type_traits::DynTypedNode &Node) { + if (!PointerParents) { + // We always need to run over the whole translation unit, 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); +} + bool ASTContext::ObjCMethodsAreEqual(const ObjCMethodDecl *MethodDecl, const ObjCMethodDecl *MethodImpl) { Index: cfe/trunk/lib/ASTMatchers/ASTMatchFinder.cpp =================================================================== --- cfe/trunk/lib/ASTMatchers/ASTMatchFinder.cpp +++ cfe/trunk/lib/ASTMatchers/ASTMatchFinder.cpp @@ -621,9 +621,6 @@ 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::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()) Index: cfe/trunk/unittests/AST/ASTContextParentMapTest.cpp =================================================================== --- cfe/trunk/unittests/AST/ASTContextParentMapTest.cpp +++ cfe/trunk/unittests/AST/ASTContextParentMapTest.cpp @@ -38,6 +38,19 @@ 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( Index: cfe/trunk/unittests/ASTMatchers/Dynamic/ParserTest.cpp =================================================================== --- cfe/trunk/unittests/ASTMatchers/Dynamic/ParserTest.cpp +++ cfe/trunk/unittests/ASTMatchers/Dynamic/ParserTest.cpp @@ -318,8 +318,10 @@ Comps[1].MatcherDecl); EXPECT_EQ("arent(", Comps[2].TypedText); - EXPECT_EQ("Matcher hasParent(Matcher)", - Comps[2].MatcherDecl); + EXPECT_EQ( + "Matcher " + "hasParent(Matcher)", + Comps[2].MatcherDecl); } } // end anonymous namespace Index: cfe/trunk/unittests/ASTMatchers/Dynamic/RegistryTest.cpp =================================================================== --- cfe/trunk/unittests/ASTMatchers/Dynamic/RegistryTest.cpp +++ cfe/trunk/unittests/ASTMatchers/Dynamic/RegistryTest.cpp @@ -448,7 +448,9 @@ CompVector Comps = getCompletions(); // Overloaded EXPECT_TRUE(hasCompletion( - Comps, "hasParent(", "Matcher hasParent(Matcher)")); + Comps, "hasParent(", + "Matcher " + "hasParent(Matcher)")); // Variadic. EXPECT_TRUE(hasCompletion(Comps, "whileStmt(", "Matcher whileStmt(Matcher...)")); @@ -464,7 +466,9 @@ EXPECT_TRUE(hasCompletion(WhileComps, "hasBody(", "Matcher hasBody(Matcher)")); EXPECT_TRUE(hasCompletion(WhileComps, "hasParent(", - "Matcher hasParent(Matcher)")); + "Matcher " + "hasParent(Matcher)")); EXPECT_TRUE( hasCompletion(WhileComps, "allOf(", "Matcher allOf(Matcher...)"));