[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/ClangdLSPServer.h

private:
   void onCodeAction(const CodeActionParams &, Callback<llvm::json::Value>);
   void onCompletion(const CompletionParams &, Callback<CompletionList>);
   void onSignatureHelp(const TextDocumentPositionParams &,
                        Callback<SignatureHelp>);
   void onGoToDeclaration(const TextDocumentPositionParams &,
                          Callback<std::vector<Location>>);
   void onGoToDefinition(const TextDocumentPositionParams &,
                         Callback<std::vector<Location>>);
+  void onImplementation(const ImplementationParams &,
+                        Callback<std::vector<Location>>);
   void onReference(const ReferenceParams &, Callback<std::vector<Location>>);
   void onSwitchSourceHeader(const TextDocumentIdentifier &,
                             Callback<llvm::Optional<URIForFile>>);
   void onDocumentHighlight(const TextDocumentPositionParams &,
                            Callback<std::vector<DocumentHighlight>>);
   void onFileEvent(const DidChangeWatchedFilesParams &);
   void onCommand(const ExecuteCommandParams &, Callback<llvm::json::Value>);
   void onWorkspaceSymbol(const WorkspaceSymbolParams &,

clang-tools-extra/clangd/ClangdLSPServer.cpp

llvm::json::Object Result{
              llvm::json::Object{
                  {"resolveProvider", false},
              }},
             {"hoverProvider", true},
             {"renameProvider", std::move(RenameProvider)},
             {"selectionRangeProvider", true},
             {"documentSymbolProvider", true},
             {"workspaceSymbolProvider", true},
+            {"implementationProvider", true},
             {"referencesProvider", true},
             {"executeCommandProvider",
              llvm::json::Object{
                  {"commands",
                   {ExecuteCommandParams::CLANGD_APPLY_FIX_COMMAND,
                    ExecuteCommandParams::CLANGD_APPLY_TWEAK}},
              }},
             {"typeHierarchyProvider", true},
Server->findReferences(Params.textDocument.uri.file(), Params.position,
                          [Reply = std::move(Reply)](
                              llvm::Expected<ReferencesResult> Refs) mutable {
                            if (!Refs)
                              return Reply(Refs.takeError());
                            return Reply(std::move(Refs->References));
                          });
 }
 
+void ClangdLSPServer::onImplementation(const ImplementationParams &Params,
+                                       Callback<std::vector<Location>> Reply) {
+  Server->findImplementations(
+      Params.textDocument.uri.file(), Params.position,
+      [Reply =
+           std::move(Reply)](llvm::Expected<ReferencesResult> Impls) mutable {
+        if (!Impls)
+          return Reply(Impls.takeError());
+        return Reply(std::move(Impls->References));
+      });
+}
+
 void ClangdLSPServer::onSymbolInfo(const TextDocumentPositionParams &Params,
                                    Callback<std::vector<SymbolDetails>> Reply) {
   Server->symbolInfo(Params.textDocument.uri.file(), Params.position,
                      std::move(Reply));
 }
 
 void ClangdLSPServer::onSelectionRange(
     const SelectionRangeParams &Params,
ClangdLSPServer::ClangdLSPServer(class Transport &Transp,
   MsgHandler->bind("textDocument/onTypeFormatting", &ClangdLSPServer::onDocumentOnTypeFormatting);
   MsgHandler->bind("textDocument/formatting", &ClangdLSPServer::onDocumentFormatting);
   MsgHandler->bind("textDocument/codeAction", &ClangdLSPServer::onCodeAction);
   MsgHandler->bind("textDocument/completion", &ClangdLSPServer::onCompletion);
   MsgHandler->bind("textDocument/signatureHelp", &ClangdLSPServer::onSignatureHelp);
   MsgHandler->bind("textDocument/definition", &ClangdLSPServer::onGoToDefinition);
   MsgHandler->bind("textDocument/declaration", &ClangdLSPServer::onGoToDeclaration);
   MsgHandler->bind("textDocument/references", &ClangdLSPServer::onReference);
+  MsgHandler->bind("textDocument/implementation", &ClangdLSPServer::onImplementation);
   MsgHandler->bind("textDocument/switchSourceHeader", &ClangdLSPServer::onSwitchSourceHeader);
   MsgHandler->bind("textDocument/prepareRename", &ClangdLSPServer::onPrepareRename);
   MsgHandler->bind("textDocument/rename", &ClangdLSPServer::onRename);
   MsgHandler->bind("textDocument/hover", &ClangdLSPServer::onHover);
   MsgHandler->bind("textDocument/documentSymbol", &ClangdLSPServer::onDocumentSymbol);
   MsgHandler->bind("workspace/executeCommand", &ClangdLSPServer::onCommand);
   MsgHandler->bind("textDocument/documentHighlight", &ClangdLSPServer::onDocumentHighlight);
   MsgHandler->bind("workspace/symbol", &ClangdLSPServer::onWorkspaceSymbol);

clang-tools-extra/clangd/ClangdServer.h

public:
 
   /// Retrieve the symbols within the specified file.
   void documentSymbols(StringRef File,
                        Callback<std::vector<DocumentSymbol>> CB);
 
   /// Retrieve ranges that can be used to fold code within the specified file.
   void foldingRanges(StringRef File, Callback<std::vector<FoldingRange>> CB);
 
+  /// Retrieve implementations for virtual method.
+  void findImplementations(PathRef File, Position Pos,
+                           Callback<ReferencesResult> CB);
+
   /// Retrieve locations for symbol references.
   void findReferences(PathRef File, Position Pos, uint32_t Limit,
                       Callback<ReferencesResult> CB);
 
   /// Run formatting for \p Rng inside \p File with content \p Code.
   void formatRange(PathRef File, StringRef Code, Range Rng,
                    Callback<tooling::Replacements> CB);
 

clang-tools-extra/clangd/ClangdServer.cpp

auto Action =
         if (!InpAST)
           return CB(InpAST.takeError());
         CB(clangd::getFoldingRanges(InpAST->AST));
       };
   WorkScheduler.runWithAST("foldingRanges", File, std::move(Action),
                            TUScheduler::InvalidateOnUpdate);
 }
 
+void ClangdServer::findImplementations(PathRef File, Position Pos,
+                                       Callback<ReferencesResult> CB) {
+  auto Action = [Pos, CB = std::move(CB),
+                 this](llvm::Expected<InputsAndAST> InpAST) mutable {
+    if (!InpAST)
+      return CB(InpAST.takeError());
+    CB(clangd::findImplementations(InpAST->AST, Pos, Index));
+  };
+
+  WorkScheduler.runWithAST("Implementations", File, std::move(Action));
+}
+
 void ClangdServer::findReferences(PathRef File, Position Pos, uint32_t Limit,
                                   Callback<ReferencesResult> CB) {
   auto Action = [Pos, Limit, CB = std::move(CB),
                  this](llvm::Expected<InputsAndAST> InpAST) mutable {
     if (!InpAST)
       return CB(InpAST.takeError());
     CB(clangd::findReferences(InpAST->AST, Pos, Limit, Index));
   };

clang-tools-extra/clangd/Protocol.h

 bool fromJSON(const llvm::json::Value &, ResolveTypeHierarchyItemParams &,
               llvm::json::Path);
 
 struct ReferenceParams : public TextDocumentPositionParams {
   // For now, no options like context.includeDeclaration are supported.
 };
 bool fromJSON(const llvm::json::Value &, ReferenceParams &, llvm::json::Path);
 
+struct ImplementationParams : public TextDocumentPositionParams {};
+bool fromJSON(const llvm::json::Value &, ImplementationParams &,
+              llvm::json::Path);
+
 /// Clangd extension: indicates the current state of the file in clangd,
 /// sent from server via the `textDocument/clangd.fileStatus` notification.
 struct FileStatus {
   /// The text document's URI.
   URIForFile uri;
   /// The human-readable string presents the current state of the file, can be
   /// shown in the UI (e.g. status bar).
   std::string state;

clang-tools-extra/clangd/Protocol.cpp

 }
 
 bool fromJSON(const llvm::json::Value &Params, ReferenceParams &R,
               llvm::json::Path P) {
   TextDocumentPositionParams &Base = R;
   return fromJSON(Params, Base, P);
 }
 
+bool fromJSON(const llvm::json::Value &Params, ImplementationParams &R,
+              llvm::json::Path P) {
+  TextDocumentPositionParams &Base = R;
+  return fromJSON(Params, Base, P);
+}
+
 static const char *toString(OffsetEncoding OE) {
   switch (OE) {
   case OffsetEncoding::UTF8:
     return "utf-8";
   case OffsetEncoding::UTF16:
     return "utf-16";
   case OffsetEncoding::UTF32:
     return "utf-32";

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.
+ReferencesResult 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;
 }
 
+ReferencesResult findImplementations(ParsedAST &AST, Position Pos,
+                                     const SymbolIndex *Index) {
+  ReferencesResult Results;
+  // We rely on index to find the implementations in subclasses.
+  if (!Index)
+    return Results;
+  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 Results;
+  }
+  auto CurLoc = sourceLocationInMainFile(SM, Pos);
+
+  DeclRelationSet Relations =
+      DeclRelation::TemplatePattern | DeclRelation::Alias;
+  RelationsRequest Req;
+  Req.Predicate = RelationKind::OverriddenBy;
+  for (const NamedDecl *ND : getDeclAtPosition(AST, *CurLoc, Relations))
+    if (llvm::isa<CXXMethodDecl>(ND))
+      Req.Subjects.insert(getSymbolID(ND));
+
+  if (Req.Subjects.empty())
+    return Results;
+  Index->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {
+    if (auto Loc = symbolToLocation(Object, *MainFilePath))
+      Results.References.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);
   if (!MainFilePath) {
     elog("Failed to get a path for the main file, so no references");

clang-tools-extra/clangd/test/initialize-params.test

 # CHECK-NEXT:      "documentSymbolProvider": true,
 # CHECK-NEXT:      "executeCommandProvider": {
 # CHECK-NEXT:        "commands": [
 # CHECK-NEXT:          "clangd.applyFix",
 # CHECK-NEXT:          "clangd.applyTweak"
 # CHECK-NEXT:        ]
 # CHECK-NEXT:      },
 # CHECK-NEXT:      "hoverProvider": true,
-# CHECK-NEXT:      "memoryUsageProvider": true
+# CHECK-NEXT:      "implementationProvider": true,
+# CHECK-NEXT:      "memoryUsageProvider": true,
 # CHECK-NEXT:      "referencesProvider": true,
 # CHECK-NEXT:      "renameProvider": true,
 # CHECK-NEXT:      "selectionRangeProvider": true,
 # CHECK-NEXT:      "semanticTokensProvider": {
 # CHECK-NEXT:        "full": {
 # CHECK-NEXT:          "delta": true
 # CHECK-NEXT:        },
 # CHECK-NEXT:        "legend": {

clang-tools-extra/clangd/unittests/XRefsTests.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();
+    };
+    struct Child1 : Base {
+      void $1[[Fo$3^o]]() override;
+      virtual void B$2^ar();
+    };
+    struct Child2 : Child1 {
+      void $3[[Foo]]() override;
+      void $2[[Bar]]() override;
+    };
+    void FromReference() {
+      Base* B;
+      B->Fo$1^o();
+      &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"}) {
+    std::vector<Matcher<Location>> ExpectedLocations;
+    for (const auto &R : Code.ranges(Label))
+      ExpectedLocations.push_back(RangeIs(R));
+    for (const auto &Point : Code.points(Label)) {
+      EXPECT_THAT(findImplementations(AST, Point, TU.index().get()).References,
+                  UnorderedElementsAreArray(ExpectedLocations))
+          << Code.code() << " at " << Point;
+    }
+  }
+}
+
 TEST(FindReferences, WithinAST) {
   const char *Tests[] = {
       R"cpp(// Local variable
         int main() {
           int [[foo]];
           [[^foo]] = 2;
           int test1 = [[foo]];
         }