[clangd] Implement "textDocument/documentLink" protocol support

[MForster]

Summary

This adds an implementation for the "textDocument/documentLink" LSP request.

It returns links for all #include directives to the resolved target files.

Fixes https://github.com/clangd/clangd/issues/217.

[MForster]

clang-tools-extra/clangd/test/document-link.test

22

Originally I tried to add a header file to the setup with a second didOpen request, but I didn't get this to work. Would I need to set this up like background-index.test, or is there a simpler way?

Anyway, I think the regular expression is probably good enough for the purpose of this test.

[sammccall]

Thanks, looks nice!
It occurred to me we could compute (but not resolve) the ranges cheaply to speed up the UI. We don't need to do this now.
Only real thing to do is add a gunit test.

clang-tools-extra/clangd/ClangdLSPServer.cpp

1207

Eagerly resolving everything means that this request is going to block on the preamble/AST being built. This isn't terrible (clients should be sending their initial requests in parallel) but does mean a delay before the links show up. (And in updating if we insert an include and want to ctrl-click it, because we just invalidated the preamble).

There are a few ways we could improve this:
a) find the links using a quick pass (simple string matching or raw-lexer based), then resolve results from the MainFileIncludes structure (blocking on the AST at that point)
b) use a quick pass to serve results in the first place, e.g. a PreprocessorOnlyAction with SingleFileParseMode (doesn't descend into headers).
c) a combination of these.

I don't particularly think we need to do these at this point, but may be worth a comment.

clang-tools-extra/clangd/Protocol.h

1263

I don't think this TODO is needed - there's nothing to do unless we decide we want to emit other types of links.
(Which seems fairly unlikely: my understanding is that e.g. hyperlinks in comments should be resolved by editors generically rather than by language servers)

clang-tools-extra/clangd/XRefs.cpp

181

nit push_back(DocumentLink{...})

clang-tools-extra/clangd/test/document-link.test

2

Generally we smoke-test features in a lit test such as this one, and then do fine-grained testing as gunit tests (e.g. unittests/XRefTests.cpp). It's good to test end-to-end, but it's too hard to maintain lit tests for all cases as features get extended.

For this feature there's not much difference between the two, but you could drop one of the includes here and cover one more case in the unit tests:

#include "foo.h"
int end_of_preamble = 0;
#include "not_part_of_preamble.h"

(The non-preamble includes get into the data structures you're querying via a different path).

The unit tests are generally easier to set up:

• you can use Annotations to write code with marked regions, and get the coordinates + unmarked code
• you can use TestTU to add extra files "foo.h" to the VFS, and produce a ParsedAST
• then just assert that the results match testPath("foo.h") + annotations.points()[0] etc.

TEST(LocateSymbol, WithIndex) in XRefsTests.cpp is a reasonable example.

22

Originally I tried to add a header file to the setup with a second didOpen request, but I didn't get this to work

Clangd's model is that the *current* file is always via LSP (didOpen), and all other files are read from disk. The setup would be slightly simpler than background-index.test because you don't need a compile command for the other file, but still a bit awkward.

I think the regex is OK, but would prefer to change to stdint.h/stddef.h (not the C++ versions). This is because they're builtin headers in clang, so even if we don't find a standard library they'll still exist. (clangd tests do formally depend on the builtins but not a stdlib, I believe).

[sammccall]

Ping - how do you want to proceed here? I think the only thing that is really missing here is a unit test, I can add it if you don't have cycles.
I'll be gone after this week :-)

[MForster]

Adress review comments.

[MForster]

I think I addressed all review comments. PTAL.

[sammccall]

Thanks! I'll land this for you.

[MForster]

In D70872#1781703, @sammccall wrote:

Thanks! I'll land this for you.

Thanks!

[gribozavr2]

Sorry, I reverted this change in 079ef783dd5530b5f87beefe624b9179547ded7e. The tests depend on builtin headers, which is not intentionally supported in clangd tests; these tests are broken in some build environments.

[sammccall]

In D70872#1785797, @gribozavr2 wrote:

which is intentionally not supported in clangd tests

Not intentionally as far as I'm aware :-)
Do you have a link or details for some failing environment? I'm OOO but I'd like to follow up and sort this out (ideally by making the builtins available)

clang-tools-extra/clangd/ClangdLSPServer.h

void onTypeHierarchy(const TypeHierarchyParams &,
                        Callback<llvm::Optional<TypeHierarchyItem>>);
   void onResolveTypeHierarchy(const ResolveTypeHierarchyItemParams &,
                               Callback<llvm::Optional<TypeHierarchyItem>>);
   void onChangeConfiguration(const DidChangeConfigurationParams &);
   void onSymbolInfo(const TextDocumentPositionParams &,
                     Callback<std::vector<SymbolDetails>>);
   void onSelectionRange(const SelectionRangeParams &,
                         Callback<std::vector<SelectionRange>>);
+  void onDocumentLink(const DocumentLinkParams &,
+                      Callback<std::vector<DocumentLink>>);
 
   std::vector<Fix> getFixes(StringRef File, const clangd::Diagnostic &D);
 
   /// Checks if completion request should be ignored. We need this due to the
   /// limitation of the LSP. Per LSP, a client sends requests for all "trigger
   /// character" we specify, but for '>' and ':' we need to check they actually
   /// produce '->' and '::', respectively.
   bool shouldRunCompletion(const CompletionParams &Params) const;

clang-tools-extra/clangd/ClangdLSPServer.cpp

llvm::json::Object Result{
              }},
             {"signatureHelpProvider",
              llvm::json::Object{
                  {"triggerCharacters", {"(", ","}},
              }},
             {"declarationProvider", true},
             {"definitionProvider", true},
             {"documentHighlightProvider", true},
+            {"documentLinkProvider",
+             llvm::json::Object{
+                 {"resolveProvider", false},
+             }},
             {"hoverProvider", true},
             {"renameProvider", std::move(RenameProvider)},
             {"selectionRangeProvider", true},
             {"documentSymbolProvider", true},
             {"workspaceSymbolProvider", true},
             {"referencesProvider", true},
             {"executeCommandProvider",
              llvm::json::Object{
Server->semanticRanges(
           return Reply(Ranges.takeError());
         }
         std::vector<SelectionRange> Result;
         Result.emplace_back(render(std::move(*Ranges)));
         return Reply(std::move(Result));
       });
 }
 
+void ClangdLSPServer::onDocumentLink(
+    const DocumentLinkParams &Params,
+    Callback<std::vector<DocumentLink>> Reply) {
+
+  // TODO(forster): This currently resolves all targets eagerly. This is slow,
+  // because it blocks on the preamble/AST being built. We could respond to the
+  // request faster by using string matching or the lexer to find the includes
+  // and resolving the targets lazily.
+  Server->documentLinks(
+      Params.textDocument.uri.file(),
+      [Reply = std::move(Reply)](
+          llvm::Expected<std::vector<DocumentLink>> Links) mutable {
+        if (!Links) {
+          return Reply(Links.takeError());
+        }
+        return Reply(std::move(Links));
+      });
+}
+
 ClangdLSPServer::ClangdLSPServer(
     class Transport &Transp, const FileSystemProvider &FSProvider,
     const clangd::CodeCompleteOptions &CCOpts,
     llvm::Optional<Path> CompileCommandsDir, bool UseDirBasedCDB,
     llvm::Optional<OffsetEncoding> ForcedOffsetEncoding,
     const ClangdServer::Options &Opts)
     : BackgroundContext(Context::current().clone()), Transp(Transp),
       MsgHandler(new MessageHandler(*this)), FSProvider(FSProvider),
ClangdLSPServer::ClangdLSPServer(
   MsgHandler->bind("textDocument/didClose", &ClangdLSPServer::onDocumentDidClose);
   MsgHandler->bind("textDocument/didChange", &ClangdLSPServer::onDocumentDidChange);
   MsgHandler->bind("workspace/didChangeWatchedFiles", &ClangdLSPServer::onFileEvent);
   MsgHandler->bind("workspace/didChangeConfiguration", &ClangdLSPServer::onChangeConfiguration);
   MsgHandler->bind("textDocument/symbolInfo", &ClangdLSPServer::onSymbolInfo);
   MsgHandler->bind("textDocument/typeHierarchy", &ClangdLSPServer::onTypeHierarchy);
   MsgHandler->bind("typeHierarchy/resolve", &ClangdLSPServer::onResolveTypeHierarchy);
   MsgHandler->bind("textDocument/selectionRange", &ClangdLSPServer::onSelectionRange);
+  MsgHandler->bind("textDocument/documentLink", &ClangdLSPServer::onDocumentLink);
   // clang-format on
 }
 
 ClangdLSPServer::~ClangdLSPServer() { IsBeingDestroyed = true;
   // Explicitly destroy ClangdServer first, blocking on threads it owns.
   // This ensures they don't access any other members.
   Server.reset();
 }

clang-tools-extra/clangd/ClangdServer.h

public:
   /// Clangd extension - not part of official LSP.
   void symbolInfo(PathRef File, Position Pos,
                   Callback<std::vector<SymbolDetails>> CB);
 
   /// Get semantic ranges around a specified position in a file.
   void semanticRanges(PathRef File, Position Pos,
                       Callback<std::vector<Range>> CB);
 
+  /// Get all document links in a file.
+  void documentLinks(PathRef File, Callback<std::vector<DocumentLink>> CB);
+ 
   /// Returns estimated memory usage for each of the currently open files.
   /// The order of results is unspecified.
   /// Overall memory usage of clangd may be significantly more than reported
   /// here, as this metric does not account (at least) for:
   ///   - memory occupied by static and dynamic index,
   ///   - memory required for in-flight requests,
   /// FIXME: those metrics might be useful too, we should add them.
   std::vector<std::pair<Path, std::size_t>> getUsedBytesPerFile() const;

clang-tools-extra/clangd/ClangdServer.cpp

auto Action =
       [Pos, CB = std::move(CB)](llvm::Expected<InputsAndAST> InpAST) mutable {
         if (!InpAST)
           return CB(InpAST.takeError());
         CB(clangd::getSemanticRanges(InpAST->AST, Pos));
       };
   WorkScheduler.runWithAST("SemanticRanges", File, std::move(Action));
 }
 
+void ClangdServer::documentLinks(PathRef File,
+                                 Callback<std::vector<DocumentLink>> CB) {
+  auto Action =
+      [CB = std::move(CB)](llvm::Expected<InputsAndAST> InpAST) mutable {
+        if (!InpAST)
+          return CB(InpAST.takeError());
+        CB(clangd::getDocumentLinks(InpAST->AST));
+      };
+  WorkScheduler.runWithAST("DocumentLinks", File, std::move(Action));
+}
+
 std::vector<std::pair<Path, std::size_t>>
 ClangdServer::getUsedBytesPerFile() const {
   return WorkScheduler.getUsedBytesPerFile();
 }
 
 LLVM_NODISCARD bool
 ClangdServer::blockUntilIdleForTest(llvm::Optional<double> TimeoutSeconds) {
   return WorkScheduler.blockUntilIdle(timeoutSeconds(TimeoutSeconds)) &&
          (!BackgroundIdx ||
           BackgroundIdx->blockUntilIdleForTest(TimeoutSeconds));
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/Protocol.h

struct SelectionRange {
   /**
    * The parent selection range containing this range. Therefore `parent.range`
    * must contain `this.range`.
    */
   std::unique_ptr<SelectionRange> parent;
 };
 llvm::json::Value toJSON(const SelectionRange &);
 
+/// Parameters for the document link request.
+struct DocumentLinkParams {
+  /// The document to provide document links for.
+  TextDocumentIdentifier textDocument;
+};
+bool fromJSON(const llvm::json::Value &, DocumentLinkParams &);
+
+/// A range in a text document that links to an internal or external resource,
+/// like another text document or a web site.
+struct DocumentLink {
+  /// The range this link applies to.
+  Range range;
+
+  /// The uri this link points to. If missing a resolve request is sent later.
+  URIForFile target;
+
+  // TODO(forster): The following optional fields defined by the language
+  // server protocol are unsupported:
+  //
+  // data?: any - A data entry field that is preserved on a document link
+  //              between a DocumentLinkRequest and a
+  //              DocumentLinkResolveRequest.
+
+  friend bool operator==(const DocumentLink &LHS, const DocumentLink &RHS) {
+    return LHS.range == RHS.range && LHS.target == RHS.target;
+  }
+
+  friend bool operator!=(const DocumentLink &LHS, const DocumentLink &RHS) {
+    return !(LHS == RHS);
+  }
+};
+llvm::json::Value toJSON(const DocumentLink &DocumentLink);
+
 } // namespace clangd
 } // namespace clang
 
 namespace llvm {
 template <> struct format_provider<clang::clangd::Position> {
   static void format(const clang::clangd::Position &Pos, raw_ostream &OS,
                      StringRef Style) {
     assert(Style.empty() && "style modifiers for this type are not supported");
     OS << Pos;
   }
 };
 } // namespace llvm
 
 #endif

clang-tools-extra/clangd/Protocol.cpp

 
 llvm::json::Value toJSON(const SelectionRange &Out) {
   if (Out.parent) {
     return llvm::json::Object{{"range", Out.range},
                               {"parent", toJSON(*Out.parent)}};
   }
   return llvm::json::Object{{"range", Out.range}};
 }
+
+bool fromJSON(const llvm::json::Value &Params, DocumentLinkParams &R) {
+  llvm::json::ObjectMapper O(Params);
+  return O && O.map("textDocument", R.textDocument);
+}
+
+llvm::json::Value toJSON(const DocumentLink &DocumentLink) {
+  return llvm::json::Object{
+      {"range", DocumentLink.range},
+      {"target", DocumentLink.target},
+  };
+}
+
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/XRefs.h

struct LocatedSymbol {
   llvm::Optional<Location> Definition;
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const LocatedSymbol &);
 /// Get definition of symbol at a specified \p Pos.
 /// Multiple locations may be returned, corresponding to distinct symbols.
 std::vector<LocatedSymbol> locateSymbolAt(ParsedAST &AST, Position Pos,
                                           const SymbolIndex *Index = nullptr);
 
+/// Get all document links
+std::vector<DocumentLink> getDocumentLinks(ParsedAST &AST);
+
 /// 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;
 };

clang-tools-extra/clangd/XRefs.cpp

if (auto Range =
     L.range = *Range;
     return L;
   }
   return None;
 }
 
 } // namespace
 
+std::vector<DocumentLink> getDocumentLinks(ParsedAST &AST) {
+  const auto &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 links");
+    return {};
+  }
+
+  std::vector<DocumentLink> Result;
+  for (auto &Inc : AST.getIncludeStructure().MainFileIncludes) {
+    if (!Inc.Resolved.empty()) {
+      Result.push_back(DocumentLink(
+          {Inc.R, URIForFile::canonicalize(Inc.Resolved, *MainFilePath)}));
+    }
+  }
+
+  return Result;
+}
+
 std::vector<LocatedSymbol> locateSymbolAt(ParsedAST &AST, Position Pos,
                                           const SymbolIndex *Index) {
   const auto &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");
     return {};

clang-tools-extra/clangd/test/document-link.test

+# RUN: clangd -lit-test < %s | FileCheck -strict-whitespace %s
+{"jsonrpc":"2.0","id":0,"method":"initialize","params":{"processId":123,"rootPath":"clangd","capabilities":{},"trace":"off"}}
+---
+{"jsonrpc":"2.0","method":"textDocument/didOpen","params":{"textDocument":{"uri":"test:///main.cpp","languageId":"cpp","version":1,"text":"#include <stdint.h>\n#include <stddef.h>"}}}
+---
+{"jsonrpc":"2.0","id":2,"method":"textDocument/documentLink","params":{"textDocument":{"uri":"test:///main.cpp"}}}
+#      CHECK:  "id": 2,
+# CHECK-NEXT:  "jsonrpc": "2.0",
+# CHECK-NEXT:  "result": [
+# CHECK-NEXT:    {
+# CHECK-NEXT:      "range": {
+# CHECK-NEXT:        "end": {
+# CHECK-NEXT:          "character": 19,
+# CHECK-NEXT:          "line": 0
+# CHECK-NEXT:        },
+# CHECK-NEXT:        "start": {
+# CHECK-NEXT:          "character": 9,
+# CHECK-NEXT:          "line": 0
+# CHECK-NEXT:        }
+# CHECK-NEXT:      },
+# CHECK-NEXT:      "target": "file://{{.*}}/stdint.h"
+# CHECK-NEXT:    },
+# CHECK-NEXT:    {
+# CHECK-NEXT:      "range": {
+# CHECK-NEXT:        "end": {
+# CHECK-NEXT:          "character": 19,
+# CHECK-NEXT:          "line": 1
+# CHECK-NEXT:        },
+# CHECK-NEXT:        "start": {
+# CHECK-NEXT:          "character": 9,
+# CHECK-NEXT:          "line": 1
+# CHECK-NEXT:        }
+# CHECK-NEXT:      },
+# CHECK-NEXT:      "target": "file://{{.*}}/stddef.h"
+# CHECK-NEXT:    }
+# CHECK-NEXT:  ]
+# CHECK-NEXT:}
+
+---
+{"jsonrpc":"2.0","id":3,"method":"shutdown"}
+---
+{"jsonrpc":"2.0","method":"exit"}

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

 # CHECK-NEXT:          ">",
 # CHECK-NEXT:          ":"
 # CHECK-NEXT:        ]
 # CHECK-NEXT:      },
 # CHECK-NEXT:      "declarationProvider": true,
 # CHECK-NEXT:      "definitionProvider": true,
 # CHECK-NEXT:      "documentFormattingProvider": true,
 # CHECK-NEXT:      "documentHighlightProvider": true,
+# CHECK-NEXT:      "documentLinkProvider": {
+# CHECK-NEXT:        "resolveProvider": false
+# CHECK-NEXT:      }
 # CHECK-NEXT:      "documentOnTypeFormattingProvider": {
 # CHECK-NEXT:        "firstTriggerCharacter": "\n",
 # CHECK-NEXT:        "moreTriggerCharacter": []
 # CHECK-NEXT:      },
 # CHECK-NEXT:      "documentRangeFormattingProvider": true,
 # CHECK-NEXT:      "documentSymbolProvider": true,
 # CHECK-NEXT:      "executeCommandProvider": {
 # CHECK-NEXT:        "commands": [

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

for (const Decl *D : NonLocalDeclRefs) {
       if (const auto *ND = llvm::dyn_cast<NamedDecl>(D))
         Names.push_back(ND->getQualifiedNameAsString());
     }
     EXPECT_THAT(Names, UnorderedElementsAreArray(C.ExpectedDecls))
         << File.code();
   }
 }
 
+TEST(DocumentLinks, All) {
+  Annotations MainCpp(R"cpp(
+      #include $foo[["foo.h"]]
+      int end_of_preamble = 0;
+      #include $bar[["bar.h"]]
+    )cpp");
+
+  TestTU TU;
+  TU.Code = MainCpp.code();
+  TU.AdditionalFiles = {{"foo.h", ""}, {"bar.h", ""}};
+  auto AST = TU.build();
+
+  EXPECT_THAT(
+      clangd::getDocumentLinks(AST),
+      ElementsAre(
+          DocumentLink({MainCpp.range("foo"),
+                        URIForFile::canonicalize(testPath("foo.h"), "")}),
+          DocumentLink({MainCpp.range("bar"),
+                        URIForFile::canonicalize(testPath("bar.h"), "")})));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang