Index: cfe/trunk/include/clang/AST/ASTContext.h =================================================================== --- cfe/trunk/include/clang/AST/ASTContext.h +++ cfe/trunk/include/clang/AST/ASTContext.h @@ -452,7 +452,7 @@ typedef llvm::SmallVector ParentVector; /// \brief Maps from a node to its parents. - typedef llvm::DenseMap> ParentMap; Index: cfe/trunk/include/clang/AST/ASTTypeTraits.h =================================================================== --- cfe/trunk/include/clang/AST/ASTTypeTraits.h +++ cfe/trunk/include/clang/AST/ASTTypeTraits.h @@ -253,10 +253,30 @@ /// @{ /// \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 @@ 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 @@ } /// @} + /// \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 @@ 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 @@ -8678,6 +8678,23 @@ 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 @@ /// 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 @@ } 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 @@ 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 @@ 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 @@ 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; } 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,7 +318,8 @@ Comps[1].MatcherDecl); EXPECT_EQ("arent(", Comps[2].TypedText); - EXPECT_EQ("Matcher hasParent(Matcher)", + EXPECT_EQ("Matcher " + "hasParent(Matcher)", Comps[2].MatcherDecl); } Index: cfe/trunk/unittests/ASTMatchers/Dynamic/RegistryTest.cpp =================================================================== --- cfe/trunk/unittests/ASTMatchers/Dynamic/RegistryTest.cpp +++ cfe/trunk/unittests/ASTMatchers/Dynamic/RegistryTest.cpp @@ -447,8 +447,10 @@ 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 @@ 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...)"));