https://github.com/timon-ul updated https://github.com/llvm/llvm-project/pull/177564
>From 3c3921d92e7f71230abacb56382ea1b47c51cbf5 Mon Sep 17 00:00:00 2001 From: Timon Ulrich <[email protected]> Date: Fri, 23 Jan 2026 11:27:30 +0100 Subject: [PATCH 1/3] Implemented recursive search for findImplementations --- clang-tools-extra/clangd/XRefs.cpp | 41 +++++++++++-------- .../clangd/unittests/XRefsTests.cpp | 4 +- 2 files changed, 25 insertions(+), 20 deletions(-) diff --git a/clang-tools-extra/clangd/XRefs.cpp b/clang-tools-extra/clangd/XRefs.cpp index 8a24d19a7d129..dbc75c2868c47 100644 --- a/clang-tools-extra/clangd/XRefs.cpp +++ b/clang-tools-extra/clangd/XRefs.cpp @@ -306,25 +306,30 @@ std::vector<LocatedSymbol> findImplementors(llvm::DenseSet<SymbolID> IDs, RelationsRequest Req; Req.Predicate = Predicate; - Req.Subjects = std::move(IDs); + llvm::DenseSet<SymbolID> RecursiveSearch = std::move(IDs); std::vector<LocatedSymbol> Results; - Index->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) { - auto DeclLoc = - indexToLSPLocation(Object.CanonicalDeclaration, MainFilePath); - if (!DeclLoc) { - elog("Find overrides: {0}", DeclLoc.takeError()); - return; - } - Results.emplace_back(); - Results.back().Name = Object.Name.str(); - Results.back().PreferredDeclaration = *DeclLoc; - auto DefLoc = indexToLSPLocation(Object.Definition, MainFilePath); - if (!DefLoc) { - elog("Failed to convert location: {0}", DefLoc.takeError()); - return; - } - Results.back().Definition = *DefLoc; - }); + while (!RecursiveSearch.empty()) { + Req.Subjects = std::move(RecursiveSearch); + RecursiveSearch = {}; + Index->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) { + RecursiveSearch.insert(Object.ID); + auto DeclLoc = + indexToLSPLocation(Object.CanonicalDeclaration, MainFilePath); + if (!DeclLoc) { + elog("Find overrides: {0}", DeclLoc.takeError()); + return; + } + Results.emplace_back(); + Results.back().Name = Object.Name.str(); + Results.back().PreferredDeclaration = *DeclLoc; + auto DefLoc = indexToLSPLocation(Object.Definition, MainFilePath); + if (!DefLoc) { + elog("Failed to convert location: {0}", DefLoc.takeError()); + return; + } + Results.back().Definition = *DefLoc; + }); + } return Results; } diff --git a/clang-tools-extra/clangd/unittests/XRefsTests.cpp b/clang-tools-extra/clangd/unittests/XRefsTests.cpp index 4106c6cf7b2d0..0fd0f33500006 100644 --- a/clang-tools-extra/clangd/unittests/XRefsTests.cpp +++ b/clang-tools-extra/clangd/unittests/XRefsTests.cpp @@ -1878,8 +1878,8 @@ TEST(FindImplementations, Inheritance) { virtual void B$2^ar(); void Concrete(); // No implementations for concrete methods. }; - struct Child2 : Child1 { - void $3[[Foo]]() override; + struct $0[[Child2]] : Child1 { + void $1[[$3[[Foo]]]]() override; void $2[[Bar]]() override; }; void FromReference() { >From ddc206578859a1d265da369a294dd1231f258514 Mon Sep 17 00:00:00 2001 From: Timon Ulrich <[email protected]> Date: Mon, 26 Jan 2026 14:47:35 +0100 Subject: [PATCH 2/3] Fixed infinite recursion --- clang-tools-extra/clangd/XRefs.cpp | 3 ++ .../clangd/unittests/XRefsTests.cpp | 36 +++++++++++++++++++ 2 files changed, 39 insertions(+) diff --git a/clang-tools-extra/clangd/XRefs.cpp b/clang-tools-extra/clangd/XRefs.cpp index dbc75c2868c47..65b50bc2d5363 100644 --- a/clang-tools-extra/clangd/XRefs.cpp +++ b/clang-tools-extra/clangd/XRefs.cpp @@ -306,12 +306,15 @@ std::vector<LocatedSymbol> findImplementors(llvm::DenseSet<SymbolID> IDs, RelationsRequest Req; Req.Predicate = Predicate; + llvm::DenseSet<SymbolID> SeenIDs; llvm::DenseSet<SymbolID> RecursiveSearch = std::move(IDs); std::vector<LocatedSymbol> Results; while (!RecursiveSearch.empty()) { Req.Subjects = std::move(RecursiveSearch); RecursiveSearch = {}; Index->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) { + if (!SeenIDs.insert(Object.ID).second) + return; RecursiveSearch.insert(Object.ID); auto DeclLoc = indexToLSPLocation(Object.CanonicalDeclaration, MainFilePath); diff --git a/clang-tools-extra/clangd/unittests/XRefsTests.cpp b/clang-tools-extra/clangd/unittests/XRefsTests.cpp index 0fd0f33500006..3b11ecda88a75 100644 --- a/clang-tools-extra/clangd/unittests/XRefsTests.cpp +++ b/clang-tools-extra/clangd/unittests/XRefsTests.cpp @@ -1923,6 +1923,42 @@ TEST(FindImplementations, Inheritance) { } } +TEST(FindImplementations, InheritanceRecursion) { + // Make sure inheritance is followed, but does not diverge. + llvm::StringRef Test = R"cpp( + template <int> + struct [[Ev^en]]; + + template <int> + struct [[Odd]]; + + template <> + struct Even<0> { + static const bool value = true; + }; + + template <> + struct Odd<0> { + static const bool value = false; + }; + + template <int I> + struct Even : Odd<I - 1> {}; + + template <int I> + struct Odd : Even<I - 1> {}; + + constexpr bool Answer = Even<42>::value; + )cpp"; + + Annotations Code(Test); + auto TU = TestTU::withCode(Code.code()); + auto AST = TU.build(); + auto Index = TU.index(); + EXPECT_THAT(findImplementations(AST, Code.point(), Index.get()), + UnorderedPointwise(declRange(), Code.ranges())); +} + TEST(FindImplementations, InheritanceObjC) { llvm::StringRef Test = R"objc( @interface $base^Base >From b90606076ea3bc43e42e6f63b3cdedaeff88050f Mon Sep 17 00:00:00 2001 From: Timon Ulrich <[email protected]> Date: Tue, 27 Jan 2026 17:11:32 +0100 Subject: [PATCH 3/3] Added defRange matcher and renamed Queue --- clang-tools-extra/clangd/XRefs.cpp | 10 +++++----- clang-tools-extra/clangd/unittests/XRefsTests.cpp | 15 ++++++++++----- 2 files changed, 15 insertions(+), 10 deletions(-) diff --git a/clang-tools-extra/clangd/XRefs.cpp b/clang-tools-extra/clangd/XRefs.cpp index 65b50bc2d5363..d4398a593d48e 100644 --- a/clang-tools-extra/clangd/XRefs.cpp +++ b/clang-tools-extra/clangd/XRefs.cpp @@ -307,15 +307,15 @@ std::vector<LocatedSymbol> findImplementors(llvm::DenseSet<SymbolID> IDs, RelationsRequest Req; Req.Predicate = Predicate; llvm::DenseSet<SymbolID> SeenIDs; - llvm::DenseSet<SymbolID> RecursiveSearch = std::move(IDs); + llvm::DenseSet<SymbolID> Queue = std::move(IDs); std::vector<LocatedSymbol> Results; - while (!RecursiveSearch.empty()) { - Req.Subjects = std::move(RecursiveSearch); - RecursiveSearch = {}; + while (!Queue.empty()) { + Req.Subjects = std::move(Queue); + Queue = {}; Index->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) { if (!SeenIDs.insert(Object.ID).second) return; - RecursiveSearch.insert(Object.ID); + Queue.insert(Object.ID); auto DeclLoc = indexToLSPLocation(Object.CanonicalDeclaration, MainFilePath); if (!DeclLoc) { diff --git a/clang-tools-extra/clangd/unittests/XRefsTests.cpp b/clang-tools-extra/clangd/unittests/XRefsTests.cpp index 3b11ecda88a75..757833c58ee17 100644 --- a/clang-tools-extra/clangd/unittests/XRefsTests.cpp +++ b/clang-tools-extra/clangd/unittests/XRefsTests.cpp @@ -54,6 +54,11 @@ MATCHER(declRange, "") { const Range &Range = ::testing::get<1>(arg); return Sym.PreferredDeclaration.range == Range; } +MATCHER(defRange, "") { + const LocatedSymbol &Sym = ::testing::get<0>(arg); + const Range &Range = ::testing::get<1>(arg); + return Sym.Definition.value_or(Sym.PreferredDeclaration).range == Range; +} // Extracts ranges from an annotated example, and constructs a matcher for a // highlight set. Ranges should be named $read/$write as appropriate. @@ -1927,10 +1932,10 @@ TEST(FindImplementations, InheritanceRecursion) { // Make sure inheritance is followed, but does not diverge. llvm::StringRef Test = R"cpp( template <int> - struct [[Ev^en]]; + struct Ev^en; template <int> - struct [[Odd]]; + struct Odd; template <> struct Even<0> { @@ -1943,10 +1948,10 @@ TEST(FindImplementations, InheritanceRecursion) { }; template <int I> - struct Even : Odd<I - 1> {}; + struct [[Even]] : Odd<I - 1> {}; template <int I> - struct Odd : Even<I - 1> {}; + struct [[Odd]] : Even<I - 1> {}; constexpr bool Answer = Even<42>::value; )cpp"; @@ -1956,7 +1961,7 @@ TEST(FindImplementations, InheritanceRecursion) { auto AST = TU.build(); auto Index = TU.index(); EXPECT_THAT(findImplementations(AST, Code.point(), Index.get()), - UnorderedPointwise(declRange(), Code.ranges())); + UnorderedPointwise(defRange(), Code.ranges())); } TEST(FindImplementations, InheritanceObjC) { _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
