[clangd] Implement textDocument/implementation (Xref layer)

[usaxena95]

Summary

Xref layer changes for textdocument/implementation (https://microsoft.github.io/language-server-protocol/specification#textDocument_implementation)

This currently shows all functions (implementations) that overrides a virtual function.

[usaxena95]

Type fix.

[usaxena95]

Typo fix.

[usaxena95]

Refactor.

[usaxena95]

Minor fixes.

[usaxena95]

Addressed final comments. Ready to land.

[usaxena95]

Remove unintended change.

[hokein]

thanks, just reviewed at the xrefs code. I think we can narrow the scope of the patch by splitting it into two patches

• find-implementation in xrefs.cpp
• LSP & clangd server layer (needs a smoke lit test)

clang-tools-extra/clangd/XRefs.cpp

1147

I think we should restrict to virtual method only.

1153

symbolToLocation will prefer definition location over declaration location.

there are a few options:

1. just return declaration location
2. just return definition location
3. return both

in the find-implementaiton case, I think the declaration location is more? interesting than the definition location, I would slightly prefer 1), what do you think?

clang-tools-extra/clangd/XRefs.h

87

not sure ReferenceResult is the best fit -- we never set the HasMore field.

I'd use std::vector<LocatedSymbol>, this returns richer information, and the client (LSPServer can choose which location they want to return).

[usaxena95]

Addressed comments.

clang-tools-extra/clangd/XRefs.cpp

1153

You are right. I experienced this while playing with it in VSCode. Sorry to not explicitly mention this.
I too prefer declaration in such case.

[usaxena95]

Added test for no implementation for concrete methods.

[hokein]

The patch description is a bit stale now.

clang-tools-extra/clangd/XRefs.cpp

1130

The current way is probably ok -- the index may be stale (if the index is not finished yet by the time we call find-implementation), so we might loose some latest results for the current main file. I think we need some comments describing the behavior. Maybe in future, we'll reconsider it

1140

nit: we need to verify CurLoc is available.

1160

I think we can leave the Definition if !DefLoc.

[usaxena95]

Addressed comments.

clang-tools-extra/clangd/XRefs.h

 /// Returns highlights for all usages of a symbol at \p Pos.
 std::vector<DocumentHighlight> findDocumentHighlights(ParsedAST &AST,
                                                       Position Pos);
 
 struct ReferencesResult {
   std::vector<Location> References;
   bool HasMore = false;
 };
+
+/// Returns implementations of the virtual function at a specified \p Pos.
+std::vector<LocatedSymbol> findImplementations(ParsedAST &AST, Position Pos,
+                                               const SymbolIndex *Index);
+
 /// Returns references of the symbol at a specified \p Pos.
 /// \p Limit limits the number of results returned (0 means no limit).
 ReferencesResult findReferences(ParsedAST &AST, Position Pos, uint32_t Limit,
                                 const SymbolIndex *Index = nullptr);
 
 /// Get info about symbols at \p Pos.
 std::vector<SymbolDetails> getSymbolInfo(ParsedAST &AST, Position Pos);
 

clang-tools-extra/clangd/XRefs.cpp

std::vector<DocumentHighlight> findDocumentHighlights(ParsedAST &AST,
 
   unsigned Offset =
       AST.getSourceManager().getDecomposedSpellingLoc(*CurLoc).second;
   SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), Offset,
                             Offset, TryTree);
   return Result;
 }
 
+std::vector<LocatedSymbol> findImplementations(ParsedAST &AST, Position Pos,
+                                               const SymbolIndex *Index) {
+  // We rely on index to find the implementations in subclasses.
+  // FIXME: Index can be stale, so we may loose some latest results from the
+  // main file.
+  if (!Index)
+    return {};
+  const SourceManager &SM = AST.getSourceManager();
+  auto MainFilePath =
+      getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()), SM);
+  if (!MainFilePath) {
+    elog("Failed to get a path for the main file, so no implementations.");
+    return {};
+  }
+  auto CurLoc = sourceLocationInMainFile(SM, Pos);
+  if (!CurLoc) {
+    elog("Failed to convert position to source location: {0}",
+         CurLoc.takeError());
+    return {};
+  }
+  std::vector<LocatedSymbol> Results;
+  DeclRelationSet Relations =
+      DeclRelation::TemplatePattern | DeclRelation::Alias;
+  RelationsRequest Req;
+  Req.Predicate = RelationKind::OverriddenBy;
+  for (const NamedDecl *ND : getDeclAtPosition(AST, *CurLoc, Relations))
+    if (const CXXMethodDecl *CXXMD = llvm::dyn_cast<CXXMethodDecl>(ND))
+      if (CXXMD->isVirtual())
+        Req.Subjects.insert(getSymbolID(ND));
+
+  if (Req.Subjects.empty())
+    return Results;
+  Index->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {
+    if (auto DeclLoc =
+            indexToLSPLocation(Object.CanonicalDeclaration, *MainFilePath)) {
+      LocatedSymbol Loc;
+      Loc.Name = Object.Name.str();
+      Loc.PreferredDeclaration = *DeclLoc;
+      if (auto DefLoc = indexToLSPLocation(Object.Definition, *MainFilePath))
+        Loc.Definition = *DefLoc;
+      Results.push_back(Loc);
+    }
+  });
+  return Results;
+}
+
 ReferencesResult findReferences(ParsedAST &AST, Position Pos, uint32_t Limit,
                                 const SymbolIndex *Index) {
   if (!Limit)
     Limit = std::numeric_limits<uint32_t>::max();
   ReferencesResult Results;
   const SourceManager &SM = AST.getSourceManager();
   auto MainFilePath =
       getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()), SM);

clang-tools-extra/clangd/unittests/XRefsTests.cpp

 namespace {
 
 using ::testing::ElementsAre;
 using ::testing::Eq;
 using ::testing::IsEmpty;
 using ::testing::Matcher;
 using ::testing::UnorderedElementsAre;
 using ::testing::UnorderedElementsAreArray;
+using ::testing::UnorderedPointwise;
 
 MATCHER_P2(FileRange, File, Range, "") {
   return Location{URIForFile::canonicalize(File, testRoot()), Range} == arg;
 }
 MATCHER(DeclRange, "") {
   const LocatedSymbol &Sym = ::testing::get<0>(arg);
   const Range &Range = ::testing::get<1>(arg);
   return Sym.PreferredDeclaration.range == Range;
)cpp",
       };
       template <typename T>
       struct Derived : Base<T> {
         using Base<T>::w^aldo;
       };
     )cpp",
   };
 
-  for (const auto* Case : Tests) {
+  for (const auto *Case : Tests) {
     SCOPED_TRACE(Case);
     auto T = Annotations(Case);
     auto AST = TestTU::withCode(T.code()).build();
     EXPECT_THAT(locateSymbolAt(AST, T.point()),
-                ::testing::UnorderedPointwise(DeclRange(), T.ranges()));
+                UnorderedPointwise(DeclRange(), T.ranges()));
   }
 }
 
 TEST(LocateSymbol, RelPathsInCompileCommand) {
   // The source is in "/clangd-test/src".
   // We build in "/clangd-test/build".
 
   Annotations SourceAnnotations(R"cpp(
if (const auto *Tok = findNearbyIdentifier(*Word, AST.getTokens()))
                                        Tok->location(), Tok->endLocation()));
     if (T.ranges().empty())
       EXPECT_THAT(Nearby, Eq(llvm::None)) << Test;
     else
       EXPECT_EQ(Nearby, T.range()) << Test;
   }
 }
 
+TEST(FindImplementations, Inheritance) {
+  llvm::StringRef Test = R"cpp(
+    struct Base {
+      virtual void F$1^oo();
+      void C$4^oncrete();
+    };
+    struct Child1 : Base {
+      void $1[[Fo$3^o]]() override;
+      virtual void B$2^ar();
+      void Concrete();  // No implementations for concrete methods.
+    };
+    struct Child2 : Child1 {
+      void $3[[Foo]]() override;
+      void $2[[Bar]]() override;
+    };
+    void FromReference() {
+      Base* B;
+      B->Fo$1^o();
+      B->C$4^oncrete();
+      &Base::Fo$1^o;
+      Child1 * C1;
+      C1->B$2^ar();
+      C1->Fo$3^o();
+    }    
+  )cpp";
+
+  Annotations Code(Test);
+  auto TU = TestTU::withCode(Code.code());
+  auto AST = TU.build();
+  for (const std::string &Label : {"1", "2", "3", "4"}) {
+    for (const auto &Point : Code.points(Label)) {
+      EXPECT_THAT(findImplementations(AST, Point, TU.index().get()),
+                  UnorderedPointwise(DeclRange(), Code.ranges(Label)))
+          << Code.code() << " at " << Point << " for Label " << Label;
+    }
+  }
+}
+
+TEST(FindImplementations, CaptureDefintion) {
+  llvm::StringRef Test = R"cpp(
+    struct Base {
+      virtual void F^oo();
+    };
+    struct Child1 : Base {
+      void $Decl[[Foo]]() override;
+    };
+    struct Child2 : Base {
+      void $Child2[[Foo]]() override;
+    };
+    void Child1::$Def[[Foo]]() { /* Definition */ }
+  )cpp";
+  Annotations Code(Test);
+  auto TU = TestTU::withCode(Code.code());
+  auto AST = TU.build();
+  EXPECT_THAT(
+      findImplementations(AST, Code.point(), TU.index().get()),
+      UnorderedElementsAre(Sym("Foo", Code.range("Decl"), Code.range("Def")),
+                           Sym("Foo", Code.range("Child2"), llvm::None)))
+      << Test;
+}
+
 TEST(FindReferences, WithinAST) {
   const char *Tests[] = {
       R"cpp(// Local variable
         int main() {
           int [[foo]];
           [[^foo]] = 2;
           int test1 = [[foo]];
         }