[clangd] Support utf-8 offsets (rather than utf-16) as a protocol extension

[sammccall]

Summary

Still some pieces to go here: unit tests for new SourceCode functionality and
a command-line flag to force utf-8 mode. But wanted to get early feedback.

[hokein]

The code looks good. For this protocol extension, we need supports from other LSP clients, I think we may want to propose this extension to the LSP specification, so that all LSP servers/clients respect it.

clangd/Protocol.h

377

nit: also mention this is in preferred order.

[sammccall]

In D58275#1399195, @hokein wrote:

The code looks good. For this protocol extension, we need supports from other LSP clients, I think we may want to propose this extension to the LSP specification, so that all LSP servers/clients respect it.

My reading of https://github.com/Microsoft/language-server-protocol/issues/376 is that they may only accept a proposal that comes with patches to Microsoft's implementations.
I'm not likely to work on that soon (it doesn't directly get us closer to interop goals) so my preferred path is implement and document the extension, get some support from other language clients/servers, and then push again for standardization.

[sammccall]

Add tests, command-line flag, and misc cleanups.
No flag for clangd-indexer yet. It's surprisingly hard with the executor API :-(

[hokein]

I think we need to update the comment in the SymbolLocation::Column.

clangd/tool/ClangdMain.cpp

9 ↗

(On Diff #187002)

the #include introduced by global code completion seems not get shortened.

clangd/ClangdLSPServer.h

 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_CLANGDLSPSERVER_H
 
 #include "ClangdServer.h"
 #include "DraftStore.h"
 #include "FindSymbols.h"
 #include "GlobalCompilationDatabase.h"
 #include "Path.h"
 #include "Protocol.h"
+#include "SourceCode.h"
 #include "Transport.h"
 #include "clang/Tooling/Core/Replacement.h"
 #include "llvm/ADT/Optional.h"
 #include <memory>
 
 namespace clang {
 namespace clangd {
 
private:
   llvm::Optional<Path> CompileCommandsDir; // FIXME: merge with capability?
   std::unique_ptr<GlobalCompilationDatabase> BaseCDB;
   // CDB is BaseCDB plus any comands overridden via LSP extensions.
   llvm::Optional<OverlayCDB> CDB;
   // The ClangdServer is created by the "initialize" LSP method.
   // It is destroyed before run() returns, to ensure worker threads exit.
   ClangdServer::Options ClangdServerOpts;
   llvm::Optional<ClangdServer> Server;
+  llvm::Optional<OffsetEncoding> NegotiatedOffsetEncoding;
 };
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_CLANGDLSPSERVER_H

clangd/ClangdLSPServer.cpp

 //===--- ClangdLSPServer.cpp - LSP server ------------------------*- C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "ClangdLSPServer.h"
 #include "Diagnostics.h"
 #include "Protocol.h"
 #include "SourceCode.h"
 #include "Trace.h"
 #include "URI.h"
 #include "clang/Tooling/Core/Replacement.h"
+#include "llvm/ADT/Optional.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/ScopedPrinter.h"
 
 namespace clang {

 //  - cancellation handling
 //  - basic call tracing
 // MessageHandler ensures that initialize() is called before any other handler.
 class ClangdLSPServer::MessageHandler : public Transport::MessageHandler {
 public:
   MessageHandler(ClangdLSPServer &Server) : Server(Server) {}
 
   bool onNotify(llvm::StringRef Method, llvm::json::Value Params) override {
+    WithContext HandlerContext(handlerContext());
     log("<-- {0}", Method);
     if (Method == "exit")
       return false;
     if (!Server.Server)
       elog("Notification {0} before initialization", Method);
     else if (Method == "$/cancelRequest")
       onCancel(std::move(Params));
     else if (auto Handler = Notifications.lookup(Method))
       Handler(std::move(Params));
     else
       log("unhandled notification {0}", Method);
     return true;
   }
 
   bool onCall(llvm::StringRef Method, llvm::json::Value Params,
               llvm::json::Value ID) override {
+    WithContext HandlerContext(handlerContext());
     // Calls can be canceled by the client. Add cancellation context.
     WithContext WithCancel(cancelableRequestContext(ID));
     trace::Span Tracer(Method);
     SPAN_ATTACH(Tracer, "Params", Params);
     ReplyOnce Reply(ID, Method, &Server, Tracer.Args);
     log("<-- {0}({1})", Method, ID);
     if (!Server.Server && Method != "initialize") {
       elog("Call {0} before initialization.", Method);
       Reply(llvm::make_error<LSPError>("server not initialized",
                                        ErrorCode::ServerNotInitialized));
     } else if (auto Handler = Calls.lookup(Method))
       Handler(std::move(Params), std::move(Reply));
     else
       Reply(llvm::make_error<LSPError>("method not found",
                                        ErrorCode::MethodNotFound));
     return true;
   }
 
   bool onReply(llvm::json::Value ID,
                llvm::Expected<llvm::json::Value> Result) override {
+    WithContext HandlerContext(handlerContext());
     // We ignore replies, just log them.
     if (Result)
       log("<-- reply({0})", ID);
     else
       log("<-- reply({0}) error: {1}", ID, llvm::toString(Result.takeError()));
     return true;
   }
 
if (!ID) {
       return;
     }
     auto StrID = llvm::to_string(*ID);
     std::lock_guard<std::mutex> Lock(RequestCancelersMutex);
     auto It = RequestCancelers.find(StrID);
     if (It != RequestCancelers.end())
       It->second.first(); // Invoke the canceler.
   }
+
+  Context handlerContext() const {
+    return Context::current().derive(
+        kCurrentOffsetEncoding,
+        Server.NegotiatedOffsetEncoding.getValueOr(OffsetEncoding::UTF16));
+  }
+
   // We run cancelable requests in a context that does two things:
   //  - allows cancellation using RequestCancelers[ID]
   //  - cleans up the entry in RequestCancelers when it's no longer needed
   // If a client reuses an ID, the last wins and the first cannot be canceled.
   Context cancelableRequestContext(const llvm::json::Value &ID) {
     auto Task = cancelableTask();
     auto StrID = llvm::to_string(ID);  // JSON-serialize ID for map key.
     auto Cookie = NextRequestCookie++; // No lock, only called on main thread.

 void ClangdLSPServer::notify(llvm::StringRef Method, llvm::json::Value Params) {
   log("--> {0}", Method);
   std::lock_guard<std::mutex> Lock(TranspWriter);
   Transp.notify(Method, std::move(Params));
 }
 
 void ClangdLSPServer::onInitialize(const InitializeParams &Params,
                                    Callback<llvm::json::Value> Reply) {
+  // Determine character encoding first as it affects constructed ClangdServer.
+  if (Params.capabilities.offsetEncoding && !NegotiatedOffsetEncoding) {
+    NegotiatedOffsetEncoding = OffsetEncoding::UTF16; // fallback
+    for (OffsetEncoding Supported : *Params.capabilities.offsetEncoding)
+      if (Supported != OffsetEncoding::UnsupportedEncoding) {
+        NegotiatedOffsetEncoding = Supported;
+        break;
+      }
+  }
+  llvm::Optional<WithContextValue> WithOffsetEncoding;
+  if (NegotiatedOffsetEncoding)
+    WithOffsetEncoding.emplace(kCurrentOffsetEncoding,
+                               *NegotiatedOffsetEncoding);
+
   if (Params.rootUri && *Params.rootUri)
     ClangdServerOpts.WorkspaceRoot = Params.rootUri->file();
   else if (Params.rootPath && !Params.rootPath->empty())
     ClangdServerOpts.WorkspaceRoot = *Params.rootPath;
   if (Server)
     return Reply(llvm::make_error<LSPError>("server already initialized",
                                             ErrorCode::InvalidRequest));
   if (const auto &Dir = Params.initializationOptions.compilationDatabasePath)
void ClangdLSPServer::onInitialize(const InitializeParams &Params,
   if (Params.capabilities.WorkspaceSymbolKinds)
     SupportedSymbolKinds |= *Params.capabilities.WorkspaceSymbolKinds;
   if (Params.capabilities.CompletionItemKinds)
     SupportedCompletionItemKinds |= *Params.capabilities.CompletionItemKinds;
   SupportsCodeAction = Params.capabilities.CodeActionStructure;
   SupportsHierarchicalDocumentSymbol =
       Params.capabilities.HierarchicalDocumentSymbol;
   SupportFileStatus = Params.initializationOptions.FileStatus;
-  Reply(llvm::json::Object{
+  llvm::json::Object Result{
       {{"capabilities",
         llvm::json::Object{
             {"textDocumentSync", (int)TextDocumentSyncKind::Incremental},
             {"documentFormattingProvider", true},
             {"documentRangeFormattingProvider", true},
             {"documentOnTypeFormattingProvider",
              llvm::json::Object{
                  {"firstTriggerCharacter", "}"},
llvm::json::Object Result{
             {"workspaceSymbolProvider", true},
             {"referencesProvider", true},
             {"executeCommandProvider",
              llvm::json::Object{
                  {"commands",
                   {ExecuteCommandParams::CLANGD_APPLY_FIX_COMMAND,
                    ExecuteCommandParams::CLANGD_APPLY_TWEAK}},
              }},
-        }}}});
+        }}}};
+  if (NegotiatedOffsetEncoding)
+    Result["offsetEncoding"] = *NegotiatedOffsetEncoding;
+  Reply(std::move(Result));
 }
 
 void ClangdLSPServer::onShutdown(const ShutdownParams &Params,
                                  Callback<std::nullptr_t> Reply) {
   // Do essentially nothing, just say we're ready to exit.
   ShutdownRequestReceived = true;
   Reply(nullptr);
 }

clangd/Protocol.h

 bool fromJSON(const llvm::json::Value &, SymbolKind &);
 constexpr auto SymbolKindMin = static_cast<size_t>(SymbolKind::File);
 constexpr auto SymbolKindMax = static_cast<size_t>(SymbolKind::TypeParameter);
 using SymbolKindBitset = std::bitset<SymbolKindMax + 1>;
 bool fromJSON(const llvm::json::Value &, SymbolKindBitset &);
 SymbolKind adjustKindToCapability(SymbolKind Kind,
                                   SymbolKindBitset &supportedSymbolKinds);
 
+// Determines the encoding used to measure offsets and lengths of source in LSP.
+enum class OffsetEncoding {
+  UnsupportedEncoding,
+  // Length counts code units of UTF-16 encoded text. (Standard LSP behavior).
+  UTF16,
+  // Length counts bytes of UTF-8 encoded text. (Clangd extension).
+  UTF8,
+};
+llvm::json::Value toJSON(const OffsetEncoding &);
+bool fromJSON(const llvm::json::Value &, OffsetEncoding &);
+
 // This struct doesn't mirror LSP!
 // The protocol defines deeply nested structures for client capabilities.
 // Instead of mapping them all, this just parses out the bits we care about.
 struct ClientCapabilities {
   /// The supported set of SymbolKinds for workspace/symbol.
   /// workspace.symbol.symbolKind.valueSet
   llvm::Optional<SymbolKindBitset> WorkspaceSymbolKinds;
 
struct ClientCapabilities {
 
   /// The supported set of CompletionItemKinds for textDocument/completion.
   /// textDocument.completion.completionItemKind.valueSet
   llvm::Optional<CompletionItemKindBitset> CompletionItemKinds;
 
   /// Client supports CodeAction return value for textDocument/codeAction.
   /// textDocument.codeAction.codeActionLiteralSupport.
   bool CodeActionStructure = false;
+
+  /// Supported encodings for LSP character offsets. (clangd extension).
+  llvm::Optional<std::vector<OffsetEncoding>> offsetEncoding;
 };
 bool fromJSON(const llvm::json::Value &, ClientCapabilities &);
 
 /// Clangd extension that's used in the 'compilationDatabaseChanges' in
 /// workspace/didChangeConfiguration to record updates to the in-memory
 /// compilation database.
 struct ClangdCompileCommand {
   std::string workingDirectory;

clangd/Protocol.cpp

 //===--- Protocol.cpp - Language Server Protocol Implementation -----------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains the serialization code for the LSP structs.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Protocol.h"
 #include "Logger.h"
+#include "SourceCode.h"
 #include "URI.h"
 #include "index/Index.h"
 #include "clang/Basic/LLVM.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/StringSwitch.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/JSON.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/raw_ostream.h"
 
 namespace clang {
 namespace clangd {
if (auto *Symbol = Workspace->getObject("symbol")) {
         if (auto *ValueSet = SymbolKind->get("valueSet")) {
           R.WorkspaceSymbolKinds.emplace();
           if (!fromJSON(*ValueSet, *R.WorkspaceSymbolKinds))
             return false;
         }
       }
     }
   }
+  if (auto *OffsetEncoding = O->get("offsetEncoding")) {
+    R.offsetEncoding.emplace();
+    if (!fromJSON(*OffsetEncoding, *R.offsetEncoding))
+      return false;
+  }
   return true;
 }
 
 bool fromJSON(const llvm::json::Value &Params, InitializeParams &R) {
   llvm::json::ObjectMapper O(Params);
   if (!O)
     return false;
   // We deliberately don't fail if we can't parse individual fields.
bool fromJSON(const llvm::json::Value &Params, InitializationOptions &Opts) {
   return true;
 }
 
 bool fromJSON(const llvm::json::Value &Params, ReferenceParams &R) {
   TextDocumentPositionParams &Base = R;
   return fromJSON(Params, Base);
 }
 
+llvm::json::Value toJSON(const OffsetEncoding &OE) {
+  switch (OE) {
+    case OffsetEncoding::UTF8:
+      return "utf-8";
+    case OffsetEncoding::UTF16:
+      return "utf-16";
+    case OffsetEncoding::UnsupportedEncoding:
+      return "unknown";
+  }
+}
+bool fromJSON(const llvm::json::Value &V, OffsetEncoding &OE) {
+  auto Str = V.getAsString();
+  if (!Str)
+    return false;
+  OE = llvm::StringSwitch<OffsetEncoding>(*Str)
+           .Case("utf-8", OffsetEncoding::UTF8)
+           .Case("utf-16", OffsetEncoding::UTF16)
+           .Default(OffsetEncoding::UnsupportedEncoding);
+  return true;
+}
+
 } // namespace clangd
 } // namespace clang

clangd/SourceCode.h

 //===--- SourceCode.h - Manipulating source code as strings -----*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // Various code that examines C++ source code without using heavy AST machinery
 // (and often not even the lexer). To be used sparingly!
 //
 //===----------------------------------------------------------------------===//
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_SOURCECODE_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_SOURCECODE_H
+#include "Context.h"
 #include "Protocol.h"
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Format/Format.h"
 #include "clang/Tooling/Core/Replacement.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/SHA1.h"
 
 namespace clang {
 class SourceManager;
 
 namespace clangd {
 
 // We tend to generate digests for source codes in a lot of different places.
 // This represents the type for those digests to prevent us hard coding details
 // of hashing function at every place that needs to store this information.
 using FileDigest = decltype(llvm::SHA1::hash({}));
 FileDigest digest(StringRef Content);
 Optional<FileDigest> digestFile(const SourceManager &SM, FileID FID);
 
+// This context variable controls the behavior of functions in this file
+// that convert between LSP offsets and native clang byte offsets.
+// If not set, defaults to UTF-16 for backwards-compatibility.
+extern Key<OffsetEncoding> kCurrentOffsetEncoding;
+
 // Counts the number of UTF-16 code units needed to represent a string (LSP
 // specifies string lengths in UTF-16 code units).
+// Use of UTF-16 may be overridden by kCurrentOffsetEncoding.
 size_t lspLength(StringRef Code);
 
 /// Turn a [line, column] pair into an offset in Code.
 ///
 /// If P.character exceeds the line length, returns the offset at end-of-line.
 /// (If !AllowColumnsBeyondLineLength, then returns an error instead).
 /// If the line number is out of range, returns an error.
 ///

clangd/SourceCode.cpp

 //===--- SourceCode.h - Manipulating source code as strings -----*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 #include "SourceCode.h"
 
+#include "Context.h"
 #include "Logger.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Lex/Lexer.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/Path.h"
 
 namespace clang {
 namespace clangd {
 
+Key<OffsetEncoding> kCurrentOffsetEncoding;
+
 // Here be dragons. LSP positions use columns measured in *UTF-16 code units*!
 // Clangd uses UTF-8 and byte-offsets internally, so conversion is nontrivial.
 
 // Iterates over unicode codepoints in the (UTF-8) string. For each,
 // invokes CB(UTF-8 length, UTF-16 length), and breaks if it returns true.
 // Returns true if CB returned true, false if we hit the end of string.
 template <typename Callback>
 static bool iterateCodepoints(llvm::StringRef U8, const Callback &CB) {
Valid = U16Units == 0 || iterateCodepoints(U8, [&](int U8Len, int U16Len) {
             return U16Units <= 0;
           });
   if (U16Units < 0) // Offset was into the middle of a surrogate pair.
     Valid = false;
   // Don't return an out-of-range index if we overran.
   return std::min(Result, U8.size());
 }
 
+static bool useUTF8ForLSP() {
+  if (auto *Enc = Context::current().get(kCurrentOffsetEncoding))
+    if (*Enc == OffsetEncoding::UTF8)
+      return true;
+  return false;
+}
+
 // Like most strings in clangd, the input is UTF-8 encoded.
 size_t lspLength(llvm::StringRef Code) {
+  if (useUTF8ForLSP())
+    return Code.size();
   // A codepoint takes two UTF-16 code unit if it's astral (outside BMP).
   // Astral codepoints are encoded as 4 bytes in UTF-8, starting with 11110xxx.
   size_t Count = 0;
   iterateCodepoints(Code, [&](int U8Len, int U16Len) {
     Count += U16Len;
     return false;
   });
   return Count;
llvm::Expected<size_t> positionToOffset(llvm::StringRef Code, Position P,
   for (int I = 0; I != P.line; ++I) {
     size_t NextNL = Code.find('\n', StartOfLine);
     if (NextNL == llvm::StringRef::npos)
       return llvm::make_error<llvm::StringError>(
           llvm::formatv("Line value is out of range ({0})", P.line),
           llvm::errc::invalid_argument);
     StartOfLine = NextNL + 1;
   }
+  StringRef Line =
+      Code.substr(StartOfLine).take_until([](char C) { return C == '\n'; });
 
-  size_t NextNL = Code.find('\n', StartOfLine);
-  if (NextNL == llvm::StringRef::npos)
-    NextNL = Code.size();
-
+  // If the encoding is UTF-8, we do bounds-checking only.
+  if (useUTF8ForLSP()) {
+    if (P.character > int(Line.size())) {
+      if (AllowColumnsBeyondLineLength)
+        return StartOfLine + Line.size();
+      else
+        return llvm::make_error<llvm::StringError>(
+            llvm::formatv("UTF-8 offset {0} overruns line {1}", P.character,
+                          P.line),
+            llvm::errc::invalid_argument);
+    }
+    return StartOfLine + P.character;
+  }
+  // Otherwise P.character is in UTF-16 code units, so we have to transcode.
   bool Valid;
-  size_t ByteOffsetInLine = measureUTF16(
-      Code.substr(StartOfLine, NextNL - StartOfLine), P.character, Valid);
+  size_t ByteOffsetInLine = measureUTF16(Line, P.character, Valid);
   if (!Valid && !AllowColumnsBeyondLineLength)
     return llvm::make_error<llvm::StringError>(
         llvm::formatv("UTF-16 offset {0} is invalid for line {1}", P.character,
                       P.line),
         llvm::errc::invalid_argument);
   return StartOfLine + ByteOffsetInLine;
 }
 

test/clangd/utf8.test

+# RUN: clangd -lit-test < %s | FileCheck -strict-whitespace %s
+# This test verifies that we can negotiate UTF-8 offsets via protocol extension.
+{"jsonrpc":"2.0","id":0,"method":"initialize","params":{"processId":123,"rootPath":"clangd","capabilities":{"offsetEncoding":["utf-8","utf-16"]},"trace":"off"}}
+# CHECK: "offsetEncoding": "utf-8"
+---
+{"jsonrpc":"2.0","method":"textDocument/didOpen","params":{"textDocument":{"uri":"test:///main.cpp","languageId":"cpp","version":1,"text":"/*ö*/int x;\nint y=x;"}}}
+---
+{"jsonrpc":"2.0","id":1,"method":"textDocument/definition","params":{"textDocument":{"uri":"test:///main.cpp"},"position":{"line":1,"character":6}}}
+# /*ö*/int x;
+# 01234567890
+# x is character (and utf-16) range [9,10) but byte range [10,11).
+#      CHECK:  "id": 1,
+# CHECK-NEXT:  "jsonrpc": "2.0",
+# CHECK-NEXT:  "result": [
+# CHECK-NEXT:    {
+# CHECK-NEXT:      "range": {
+# CHECK-NEXT:        "end": {
+# CHECK-NEXT:          "character": 11,
+# CHECK-NEXT:          "line": 0
+# CHECK-NEXT:        },
+# CHECK-NEXT:        "start": {
+# CHECK-NEXT:          "character": 10,
+# CHECK-NEXT:          "line": 0
+# CHECK-NEXT:        }
+# CHECK-NEXT:      },
+# CHECK-NEXT:      "uri": "file://{{.*}}/main.cpp"
+# CHECK-NEXT:    }
+# CHECK-NEXT:  ]
+---
+{"jsonrpc":"2.0","id":10000,"method":"shutdown"}
+---
+{"jsonrpc":"2.0","method":"exit"}