[clangd] Support incremental document syncing

[simark]

Summary

This patch adds support for incremental document syncing, as described
in the LSP spec. The protocol specifies ranges in terms of Position (a
line and a character), and our drafts are stored as plain strings. So I
see two things that may not be super efficient for very large files:

• Converting a Position to an offset (the positionToOffset function) requires searching for end of lines until we reach the desired line.
• When we update a range, we construct a new string, which implies copying the whole document.

However, for the typical size of a C++ document and the frequency of
update (at which a user types), it may not be an issue. This patch aims
at getting the basic feature in, and we can always improve it later if
we find it's too slow.

Signed-off-by: Simon Marchi <[e-mail]>

[ilya-biryukov]

clangd/ClangdLSPServer.cpp

103

A comment mentioning that 2 means incremental document sync from LSP would be useful here.

154–155

We should handle more than a single change here.

clangd/ClangdServer.h

159 ↗

(On Diff #137648)

I don't think we should do this on ClangdServer level. We will have to copy the whole file anyway before passing it to clang, so there are no performance wins here and it complicates the interface.
I suggest we update the document text from diffs on ClangdLSPServer level and continue passing the whole document to ClangdServer.
It would mean DraftMgr will need to move to ClangdLSPServer, but it's fine.

clangd/DraftStore.cpp

38

NIT: LLVM uses UpperCamelCase for parameters and local variables

46

We should return an error to the client in that case. Changing return type to llvm::Expected<DocVersion> and handling an error in the callers should do the trick.

55

We need to check that startIndex and endIndex are inside the bounds of the string.

clangd/DraftStore.h

35–42

Let's model the LSP more closely here:

// Protocol.h
struct TextDocumentContentChangeEvent {
  llvm::Optional<Range> range;
  llvm::Optional<int>  rangeLength;
  std::string text;
};

/// DraftManager
class DraftManager {
  /// For initial didOpen.
  DocVersion addDraft(PathRef File, std::string Contents);

  /// For didChange, handles both incremental and full updates. \p Changes cannot be empty.
  DocVersion updateDraft(PathRef File, ArrayRef<TextDocumentContentChangeEvent> Changes);
};

Keeping track of LSP versions here could also be useful to make sure we drop any updates in between (which would definitely lead to surprising results), but it's ok if we add a FIXME and do it later.

clangd/Protocol.h

306

Please add rangeLength from lsp spec too. On one hand, it seems redundant, but it can be used to add assertions that the text is the same.

[ilya-biryukov]

clangd/ClangdServer.cpp

557 ↗

(On Diff #137648)

When you'll try remove the DraftMgr, this piece of code will be hard to refactor because it relies on DocVersion.
This is a workaround for a possible race condition that should really be handled by TUScheduler rather than this code, but we haven't got around to fixing it yet. (It's on the list, though, would probably get in next week).

A proper workaround for now would be to add llvm::StringMap<uint64_t> InternalVersions field to ClangdServer, increment those versions on each call to addDocument and use them here in the same way we currently use DraftMgr's versions.

[simark]

clangd/ClangdLSPServer.cpp

103

I opted to add a TextDocumentSyncKind enum to Protocol.h and use that. Though instead of an enum, I did a class with static const fields:

struct TextDocumentSyncKind {
  /// Documents should not be synced at all.
  static const int None = 0;

  /// Documents are synced by always sending the full content of the document.
  static const int Full = 1;

  /// Documents are synced by sending the full content on open.  After that
  /// only incremental updates to the document are send.
  static const int Incremental = 2;
};

otherwise it would've required an (int) cast when using it to generate JSON:

{"textDocumentSync", TextDocumentSyncKind::Incremental},

154–155

Ok, I'll try that. I am not sure I interpret the spec correctly. If you have two changes, the second change applies to the state of the document after having applied the first change, is that right? If that's the case, I think we only need to iterate on the changes and call addDocument on them sequentially (which could be done in the DraftMgr, given the interface change to DraftStore you suggest lower).

clangd/ClangdServer.h

159 ↗

(On Diff #137648)

ClangdServer also needs DraftMgr for forceReparse and reparseOpenedFiles. I guess that too would move to ClangdLSPServer? I'm just not sure how to adapt the unit tests, since we don't have unittests using ClangdLSPServer (yet).

[simark]

clangd/ClangdServer.cpp

557 ↗

(On Diff #137648)

Hmm ok, it will probably make sense when I try to do it. The InternalVersions map maps URIs to the latest version seen?

Is the race condition because we could get diagnostics for a stale version of the document, so we don't want to emit them?

clangd/DraftStore.cpp

38

Woops. I should learn to use clang-tidy. It found other instances (the local variables) but it doesn't find the parameters not written in camel case. Do you have an idea why? I dumped the config and see these:

- key:             readability-identifier-naming.ClassCase
  value:           CamelCase
- key:             readability-identifier-naming.EnumCase
  value:           CamelCase
- key:             readability-identifier-naming.UnionCase
  value:           CamelCase
- key:             readability-identifier-naming.VariableCase
  value:           CamelCase

I assume there must be a ParamCase or something like that, but I can't find the exhaustive list of parameters for that check.

55

Right.

clangd/DraftStore.h

35–42

By DraftManager I suppose you mean DraftStore? I'm fine with that interface change.

clangd/Protocol.h

306

Ok.

[simark]

clangd/ClangdServer.h

159 ↗

(On Diff #137648)

Actually, forceReparse doesn't really need DraftMgr (it's only used for the assert), only reparseOpenedFiles needs it. So in the test, we can manually call forceReparse on all the files by hand... this just means that reparseOpenedFiles won't be tested anymore.

[simark]

I uploaded a new patch that moves the draft store to ClangdLSPServer, that implements what you suggested.

https://reviews.llvm.org/D44408

I will update the incremental sync patch once that patch is in.

[ilya-biryukov]

clangd/ClangdLSPServer.cpp

154–155

I am interpreting it in the same manner, i.e. we need to apply the edits in the sequence they were provided.
But I would double-check on a client that actually send multiple changes. Does VSCode do that?

clangd/ClangdServer.cpp

557 ↗

(On Diff #137648)

For the record:
The race only happens if you add a file(version 1), remove the same file(version 2), add the same file again(version 3).
The diagnostics callbacks for version 1 and version 3 are triggered concurrently and we right report (3) and later (1).
It breaks "eventual consistency", i.e. clangd should eventually provide diagnostics for the latest version of the file, and we provide stale diagnostics in that case.

clangd/DraftStore.cpp

38

There is indeed a readability-idenfitier.ParameterCase key.
Found in the code, it is probably missing from the docs. IdentifierNamingCheck.cpp.
We should probably update the relevant clang-tidy config. (not sure where it is, though, I don't use clang-tidy for clangd development. should really start doing that :-))

[ilya-biryukov]

clangd/ClangdLSPServer.cpp

103

I'd opt for a real enum. Having some extra type-safety and compiler warnings (i.e. non-covered enum value in switch) is much more valuable than a small inconvenience when converting the value back to json and back.

[simark]

clangd/ClangdLSPServer.cpp

103

Makes sense.

154–155

I don't know of any client that does that. AFAIK, vscode doesn't:

https://github.com/Microsoft/vscode-languageserver-node/blob/master/client/src/client.ts#L907-L908

It's the only place I could find where a DidChangeTextDocumentParams is created, and it comes from a single TextDocumentChangeEvent, so there will always be only one item in the array.

clangd/ClangdServer.cpp

557 ↗

(On Diff #137648)

Ok, thanks.

clangd/DraftStore.cpp

38

The .clang-tidy file in the root of the llvm repo contains it. But the one in the clang repo overrides the readability-identifier-naming section without defining ParameterCase. That's probably why it's not enabled.

'llvm-header-guard' is enabled in the /home/emaisin/src/llvm/tools/clang/tools/extra/clangd/.clang-tidy.
'llvm-include-order' is enabled in the /home/emaisin/src/llvm/tools/clang/tools/extra/clangd/.clang-tidy.
'llvm-namespace-comment' is enabled in the /home/emaisin/src/llvm/tools/clang/tools/extra/clangd/.clang-tidy.
'llvm-twine-local' is enabled in the /home/emaisin/src/llvm/tools/clang/tools/extra/clangd/.clang-tidy.
'misc-definitions-in-headers' is enabled in the /home/emaisin/src/llvm/tools/clang/tools/extra/clangd/.clang-tidy.
'misc-misplaced-const' is enabled in the /home/emaisin/src/llvm/tools/clang/tools/extra/clangd/.clang-tidy.
'misc-new-delete-overloads' is enabled in the /home/emaisin/src/llvm/tools/clang/tools/extra/clangd/.clang-tidy.
'misc-non-copyable-objects' is enabled in the /home/emaisin/src/llvm/tools/clang/tools/extra/clangd/.clang-tidy.
'misc-redundant-expression' is enabled in the /home/emaisin/src/llvm/tools/clang/tools/extra/clangd/.clang-tidy.
'misc-static-assert' is enabled in the /home/emaisin/src/llvm/tools/clang/tools/extra/clangd/.clang-tidy.
'misc-throw-by-value-catch-by-reference' is enabled in the /home/emaisin/src/llvm/tools/clang/tools/extra/clangd/.clang-tidy.
'misc-unconventional-assign-operator' is enabled in the /home/emaisin/src/llvm/tools/clang/tools/extra/clangd/.clang-tidy.
'misc-uniqueptr-reset-release' is enabled in the /home/emaisin/src/llvm/tools/clang/tools/extra/clangd/.clang-tidy.
'misc-unused-alias-decls' is enabled in the /home/emaisin/src/llvm/tools/clang/tools/extra/clangd/.clang-tidy.
'misc-unused-using-decls' is enabled in the /home/emaisin/src/llvm/tools/clang/tools/extra/clangd/.clang-tidy.
'readability-identifier-naming' is enabled in the /home/emaisin/src/llvm/tools/clang/tools/extra/clangd/.clang-tidy.

So we should probably update the .clang-tidy file in the clang repo?

[simark]

Address review comments, rebase on latest master

[ilya-biryukov]

clangd/ClangdLSPServer.cpp

154–155

But TextDocumentChangeEvent may contain multiple content changes, see codeConverter.ts.

Anyway, the spec seems to be clear enough here. Let's support multiple changes, it should be super-easy on our side (just call a function that does the update in a loop)

164

We should signal an error to the client by calling replyError

clangd/DraftStore.cpp

38

Yeah, it looks outdated, .clang_tidy in top-level llvm directory already has ParameterCase. Created D44628 to update the config in clang too.

61

positionToOffset always truncates to size of contents. It has to return Expected<int> too here.

64

NIT: maybe use change or edit instead of range?
range's start position .... is out of range is a bit confusing.

73

Having partially applied changes in the map seems weird. Maybe the code applying the diffs to a separate function that returns either new contents or an error and use it here?
I.e. we won't be able to end up in a state with partially applied changes:

Expected<string> applyChanges(StringRef Contents, ArrayRef<TextDocumentChange> Changes) {
}

// See other comment about Version.
Expected<string> updateDraft(StringRef File, /*int Version,*/ ArrayRef<TextDocumentChange> Changes) {
  // check File is in the map and version matches....
  //...
  string& Contents = ...;
  auto NewContents = applyChanges(Contents, Changes);
  if (!NewContents) 
    return NewContents.takeError();
  Contents = *NewContents;
  return std::move(*NewContents);
}

97

The math is correct, but I'm confused on how to properly read the formula here.
Maybe change to:
Contents.length() - (EndIndex - StartIndex) + Change.text.length()?

This clearly reads as:
LengthBefore - LengthRemoved + LengthAdded

103

This check seems unnecessary, we've already checked for range errors. Maybe remove it?

106

It is impossible to mix full content changes with incremental range changes, right?

I suggest handling the full content change as a separate case at the start of the function:

if (Changes.size() == 1 && !Changes[0].range) {
  Contents = std::move(Change.text);
  return Contents;
}

for (auto &Change : Changes) {
  if (!Change.range)
    return make_error("Full change in the middle of incremental changes");
}

clangd/DraftStore.h

36

Could we add versions from LSP's VersionedTextDocumentIdentifier here and make the relevant sanity checks?
Applying diffs to the wrong version will cause everything to fall apart, so we should detect this error and signal it to the client as soon as possible.

unittests/clangd/DraftStoreTests.cpp

27

no need for static, since function is already inside an anonymous namespace.
remove it?

38

NIT: remove empty line after comment?
NIT: make the comment doxygen-like (i.e. start with ///)?

42

NIT: use constexpr StringLiteral Path("/hello.cpp") instead?
It's a StringRef with size known at compile-time.

58

Use ASSERT_TRUE(!!Result), the code below won't work for failure results anyway.

[simark]

clangd/ClangdLSPServer.cpp

164

textDocument/didChange is a jsonrpc notification, not request, so we can't send back an error.

clangd/DraftStore.cpp

106

I'd say it is unlikely and there's probably no reason to do it, but the way the data structure is allows it.

[simark]

clangd/DraftStore.cpp

61

Indeed, it would be better.

73

It makes sense, but I think we can achieve the same result by just tweaking the current code. I don't think a separate function is really needed here.

97

I saw it as LengthOfTheSliceFromTheOriginalThatWeKeepBefore + LengthOfNewStuff + LengthOfTheSliceFromTheOriginalThatWeKeepAfter. But I don't mind changing it.

103

Note that this check is not equivalent to the previous

if (EndIndex > Contents.length())

for the case where EndIndex == Contents.length(). In our case, it's possible (and valid) for EndIndex to be equal to Contents.length(), when referring to the end of the document (past the last character). I thought that doing Contents.substr(Contents.length()) would be throw std::out_of_range or be undefined behavior, but now that I read it correctly:

@throw  std::out_of_range  If __pos > size().

So it looks like it would fine to have pos == Contents.length().

[ilya-biryukov]

clangd/ClangdLSPServer.cpp

164

Right, my mistake. Sorry for the confusion.

clangd/DraftStore.cpp

73

Sure, tweaking the function is also ok. Have to be careful to not accidentally update the old Contents before all changes are applied, but no problems other than that.

97

Ha, that also makes sense to me, thanks for the explanation. And even mirrors the code better.

103

Right, the substr will simply return an empty string. An extra check is not really necessary.

106

I would be very surprised to see a request that mixes both, even though the data structure allows it. It's up to you if you want to change the behaviour or not.
If we keep the code this way, maybe first handle the full content update? It would make the code somewhat easier to read and reduce nesting (see the relevant bit of LLVM style guide):

for (auto &Change : Changes) {
  if (!Change.range) {
    Contents = std::move(Change.Text);
    continue;
  }

  // Handle incremental change
}

[simark]

clangd/DraftStore.h

36

I agree that applying diffs to the wrong version will break basically everything, but even if we detect a version mismatch, I don't see what we could do, since we don't have a mean to report the error to the client. The only thing we could do is log it (which we already do.

[simark]

Address review comments, except LSP version check

[ilya-biryukov]

clangd/DraftStore.h

36

If we couldn't apply a diff, we should return errors from all future operations on this file until it gets closed and reopened. Otherwise clangd and the editor would see inconsistent contents for the file and results provided by clangd would be unreliable.
The errors from any actions on the invalid file would actually be visible to the users.

The simplest way to achieve that is to remove the file from DraftStore and ClangdServer on errors from updateDraft.
This will give "calling action on non-tracked file" errors for future operations and the actual root cause can be figured out from the logs.

[simark]

Remove draft if update fails

[simark]

Add lit test case

[ilya-biryukov]

unittests/clangd/DraftStoreTests.cpp

27

This comment is marked as done, but not addressed.

38

This comment is marked as done, but not addressed.

42

This comment is marked as done, but not addressed.

58

This comment is marked as done, but not addressed.

[simark]

unittests/clangd/DraftStoreTests.cpp

27

Hmm I addressed the comments at two different times, but I probably messed up my branches or something, so I lost the changes of my first pass. Sorry about that.

[simark]

Address review comments I failed to address previously

[ilya-biryukov]

Thanks for addressing the comments. I have just one comment left, about the LSP versions and sanity-checking.

clangd/DraftStore.h

36

We still ignore version numbers from the LSP.
Is this another change that didn't get in?

[simark]

clangd/DraftStore.h

36

The more I think about it, the less sure I am that this is the intended usage of the version. The spec doesn't even say what the initial version of a file should be, 0 or 1? Then, it just says that the version optionally contained in the VersionedTextDocumentIdentifier reflects the version of the document after having applied the edit. But I don't think we can predict and validate what that version should be. Most clients will probably just use a sequence number, but I guess they don't have to...

Also, I initially assumed that having N changes in the contentChanges array would mean that the version number would be bumped by N. But now that I re-read it, there's really nothing that says it should behave like this.

I think that we should just record the version number and treat it as opaque, so that we can use it later when sending text edits to the client, for example. The client can then verify that the edit is for the same version of the document that it has at the moment.

Therefore, I don't think it would really be useful in this patch.

[ilya-biryukov]

Thanks again. This generally looks LGTM, just a last drop of small nits. Will approve as soon as they land.

clangd/DraftStore.cpp

75

Could we add a format provide for Position to make this formatting code shorter?
We'll need to define the corresponding specialization in Protocol.h:

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;
    }
  };
}

This will allow to simplify this call site to:

llvm::formatv("Range's end position ({0}) is before start position ({1})", End, Start)

100

Doing return std::move(localvar) is a pessimization. Use return Contents; instead.
(for reference see this SO post, clang should give a warning for that case too)

clangd/DraftStore.h

26

Could we also mention in the comment that this class now handles applying incremental document changes?

36

The initial version is provided in didOpen (see TextDocumentItem).
I've also misread description of contentChanges in the same way. It's true that versions might grow by any any positive number, so we can't rely on them for the checks I propose here.
Thanks for looking into that and explaining the spec :-)

unittests/clangd/DraftStoreTests.cpp

37

NIT: another redundant static

63

NIT: another redundant static

67

NIT: another instance of constexpr StringLiteral

[simark]

clangd/DraftStore.cpp

75

Good idea, this is good for printing them in a consistent way too.

100

Thanks, good catch.

[simark]

Address review comments

[ilya-biryukov]

LGTM.

unittests/clangd/DraftStoreTests.cpp

2

NIT: s/Clangd unit tests/Draft store tests
Or remove the comment title altogether, the filename seems to provide the same information.

21

It seems this using namespace can be removed (at least there are lots of names qualified with llvm:: throughout the file)

clangd/ClangdLSPServer.cpp

else if (Params.rootPath && !Params.rootPath->empty())
     Server.setRootPath(*Params.rootPath);
 
   CCOpts.EnableSnippets =
       Params.capabilities.textDocument.completion.completionItem.snippetSupport;
 
   reply(json::obj{
       {{"capabilities",
         json::obj{
-            {"textDocumentSync", 1},
+            {"textDocumentSync", (int)TextDocumentSyncKind::Incremental},
             {"documentFormattingProvider", true},
             {"documentRangeFormattingProvider", true},
             {"documentOnTypeFormattingProvider",
              json::obj{
                  {"firstTriggerCharacter", "}"},
                  {"moreTriggerCharacter", {}},
              }},
             {"codeActionProvider", true},

 void ClangdLSPServer::onDocumentDidOpen(DidOpenTextDocumentParams &Params) {
   if (Params.metadata && !Params.metadata->extraFlags.empty())
     CDB.setExtraFlagsForFile(Params.textDocument.uri.file(),
                              std::move(Params.metadata->extraFlags));
 
   PathRef File = Params.textDocument.uri.file();
   std::string &Contents = Params.textDocument.text;
 
-  DraftMgr.updateDraft(File, Contents);
+  DraftMgr.addDraft(File, Contents);
   Server.addDocument(File, Contents, WantDiagnostics::Yes);
 }
 
 void ClangdLSPServer::onDocumentDidChange(DidChangeTextDocumentParams &Params) {
-  if (Params.contentChanges.size() != 1)
-    return replyError(ErrorCode::InvalidParams,
-                      "can only apply one change at a time");
   auto WantDiags = WantDiagnostics::Auto;
   if (Params.wantDiagnostics.hasValue())
     WantDiags = Params.wantDiagnostics.getValue() ? WantDiagnostics::Yes
                                                   : WantDiagnostics::No;
 
   PathRef File = Params.textDocument.uri.file();
-  std::string &Contents = Params.contentChanges[0].text;
+  llvm::Expected<std::string> Contents =
+      DraftMgr.updateDraft(File, Params.contentChanges);
+  if (!Contents) {
+    log(llvm::toString(Contents.takeError()));
+    return;
+  }
 
-  // We only support full syncing right now.
-  DraftMgr.updateDraft(File, Contents);
-  Server.addDocument(File, Contents, WantDiags);
+  Server.addDocument(File, *Contents, WantDiags);
 }
 
 void ClangdLSPServer::onFileEvent(DidChangeWatchedFilesParams &Params) {
   Server.onFileEvent(Params);
 }
 
 void ClangdLSPServer::onCommand(ExecuteCommandParams &Params) {
   auto ApplyEdit = [](WorkspaceEdit WE) {

clangd/DraftStore.h

 //===--- DraftStore.h - File contents container -----------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_DRAFTSTORE_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_DRAFTSTORE_H
 
 #include "Path.h"
+#include "Protocol.h"
 #include "clang/Basic/LLVM.h"
 #include "llvm/ADT/StringMap.h"
 #include <mutex>
 #include <string>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 
 /// A thread-safe container for files opened in a workspace, addressed by
 /// filenames. The contents are owned by the DraftStore.
 class DraftStore {
 public:
   /// \return Contents of the stored document.
   /// For untracked files, a llvm::None is returned.
   llvm::Optional<std::string> getDraft(PathRef File) const;
 
   /// \return List of names of the drafts in this store.
   std::vector<Path> getActiveFiles() const;
 
   /// Replace contents of the draft for \p File with \p Contents.
-  void updateDraft(PathRef File, StringRef Contents);
+  void addDraft(PathRef File, StringRef Contents);
+
+  /// Update the contents of the draft for \p File based on \p Changes.
+  /// \return The new version of the draft for \p File.
+  llvm::Expected<std::string>
+  updateDraft(PathRef File,
+              llvm::ArrayRef<TextDocumentContentChangeEvent> Changes);
 
   /// Remove the draft from the store.
   void removeDraft(PathRef File);
 
 private:
   mutable std::mutex Mutex;
   llvm::StringMap<std::string> Drafts;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif

clangd/DraftStore.cpp

 //===--- DraftStore.cpp - File contents container ---------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "DraftStore.h"
+#include "SourceCode.h"
+#include "llvm/Support/Errc.h"
 
 using namespace clang;
 using namespace clang::clangd;
 
 llvm::Optional<std::string> DraftStore::getDraft(PathRef File) const {
   std::lock_guard<std::mutex> Lock(Mutex);
 
   auto It = Drafts.find(File);
   if (It == Drafts.end())
     return llvm::None;
 
   return It->second;
 }
 
 std::vector<Path> DraftStore::getActiveFiles() const {
   std::lock_guard<std::mutex> Lock(Mutex);
   std::vector<Path> ResultVector;
 
   for (auto DraftIt = Drafts.begin(); DraftIt != Drafts.end(); DraftIt++)
     ResultVector.push_back(DraftIt->getKey());
 
   return ResultVector;
 }
 
-void DraftStore::updateDraft(PathRef File, StringRef Contents) {
+void DraftStore::addDraft(PathRef File, StringRef Contents) {
   std::lock_guard<std::mutex> Lock(Mutex);
 
   Drafts[File] = Contents;
 }
 
+llvm::Expected<std::string> DraftStore::updateDraft(
+    PathRef File, llvm::ArrayRef<TextDocumentContentChangeEvent> Changes) {
+  std::lock_guard<std::mutex> Lock(Mutex);
+
+  auto EntryIt = Drafts.find(File);
+  if (EntryIt == Drafts.end()) {
+    return llvm::make_error<llvm::StringError>(
+        "Trying to do incremental update on non-added document: " + File,
+        llvm::errc::invalid_argument);
+  }
+
+  std::string &Contents = EntryIt->second;
+
+  for (const TextDocumentContentChangeEvent &Change : Changes) {
+    std::string NewContents;
+
+    if (Change.range) {
+      const Position &Start = Change.range->start;
+      size_t StartIndex = positionToOffset(Contents, Start);
+      if (StartIndex > Contents.length()) {
+        return llvm::make_error<llvm::StringError>(
+            llvm::formatv("Range's start position (line={0}, character={1}) is "
+                          "out of range.",
+                          Start.line, Start.character),
+            llvm::errc::invalid_argument);
+      }
+
+      const Position &End = Change.range->end;
+      size_t EndIndex = positionToOffset(Contents, End);
+      if (EndIndex > Contents.length()) {
+        return llvm::make_error<llvm::StringError>(
+            llvm::formatv("Range's end position (line={0}, character={1}) is "
+                          "out of range.",
+                          End.line, End.character),
+            llvm::errc::invalid_argument);
+      }
+
+      if (EndIndex < StartIndex) {
+        return llvm::make_error<llvm::StringError>(
+            llvm::formatv("Range's end position (line={0}, character={1}) is "
+                          "before start position (line={2}, character={3}).",
+                          End.line, End.character, Start.line, Start.character),
+            llvm::errc::invalid_argument);
+      }
+
+      if (Change.rangeLength &&
+          (ssize_t)(EndIndex - StartIndex) != *Change.rangeLength) {
+        return llvm::make_error<llvm::StringError>(
+            llvm::formatv("Change's rangeLength ({0}) doesn't match the "
+                          "computed range length ({1}).",
+                          *Change.rangeLength, EndIndex - StartIndex),
+            llvm::errc::invalid_argument);
+      }
+
+      NewContents.reserve(StartIndex + Change.text.length() +
+                          (Contents.length() - EndIndex));
+
+      NewContents = Contents.substr(0, StartIndex);
+      NewContents += Change.text;
+
+      if (EndIndex < Contents.length())
+        NewContents += Contents.substr(EndIndex);
+    } else {
+      NewContents = Change.text;
+    }
+
+    Contents = std::move(NewContents);
+  }
+
+  return Contents;
+}
+
 void DraftStore::removeDraft(PathRef File) {
   std::lock_guard<std::mutex> Lock(Mutex);
 
   Drafts.erase(File);
 }

clangd/Protocol.h

 };
 bool fromJSON(const json::Expr &E, TraceLevel &Out);
 
 struct NoParams {};
 inline bool fromJSON(const json::Expr &, NoParams &) { return true; }
 using ShutdownParams = NoParams;
 using ExitParams = NoParams;
 
+/// Defines how the host (editor) should sync document changes to the language
+/// server.
+enum class TextDocumentSyncKind {
+  /// Documents should not be synced at all.
+  None = 0,
+
+  /// Documents are synced by always sending the full content of the document.
+  Full = 1,
+
+  /// Documents are synced by sending the full content on open.  After that
+  /// only incremental updates to the document are send.
+  Incremental = 2,
+};
+
 struct CompletionItemClientCapabilities {
   /// Client supports snippets as insert text.
   bool snippetSupport = false;
   /// Client supports commit characters on a completion item.
   bool commitCharacterSupport = false;
   // Client supports the follow content formats for the documentation property.
   // The order describes the preferred format of the client.
   // NOTE: not used by clangd at the moment.

 
 struct DidCloseTextDocumentParams {
   /// The document that was closed.
   TextDocumentIdentifier textDocument;
 };
 bool fromJSON(const json::Expr &, DidCloseTextDocumentParams &);
 
 struct TextDocumentContentChangeEvent {
-  /// The new text of the document.
+  /// The range of the document that changed.
+  llvm::Optional<Range> range;
+
+  /// The length of the range that got replaced.
+  llvm::Optional<int> rangeLength;
+
+  /// The new text of the range/document.
   std::string text;
 };
 bool fromJSON(const json::Expr &, TextDocumentContentChangeEvent &);
 
 struct DidChangeTextDocumentParams {
   /// The document that did change. The version number points
   /// to the version after all provided content changes have
   /// been applied.

clangd/Protocol.cpp

 
 bool fromJSON(const json::Expr &Params, DidChangeWatchedFilesParams &R) {
   json::ObjectMapper O(Params);
   return O && O.map("changes", R.changes);
 }
 
 bool fromJSON(const json::Expr &Params, TextDocumentContentChangeEvent &R) {
   json::ObjectMapper O(Params);
-  return O && O.map("text", R.text);
+  return O && O.map("range", R.range) && O.map("rangeLength", R.rangeLength) &&
+         O.map("text", R.text);
 }
 
 bool fromJSON(const json::Expr &Params, FormattingOptions &R) {
   json::ObjectMapper O(Params);
   return O && O.map("tabSize", R.tabSize) &&
          O.map("insertSpaces", R.insertSpaces);
 }
 

test/clangd/initialize-params-invalid.test

 # CHECK-NEXT:      "hoverProvider": true,
 # CHECK-NEXT:      "renameProvider": true,
 # CHECK-NEXT:      "signatureHelpProvider": {
 # CHECK-NEXT:        "triggerCharacters": [
 # CHECK-NEXT:          "(",
 # CHECK-NEXT:          ","
 # CHECK-NEXT:        ]
 # CHECK-NEXT:      },
-# CHECK-NEXT:      "textDocumentSync": 1
+# CHECK-NEXT:      "textDocumentSync": 2
 # CHECK-NEXT:    }
 # CHECK-NEXT:  }
 ---
 {"jsonrpc":"2.0","id":3,"method":"shutdown"}
 ---
 {"jsonrpc":"2.0","method":"exit"}

test/clangd/initialize-params.test

 # CHECK-NEXT:      "hoverProvider": true,
 # CHECK-NEXT:      "renameProvider": true,
 # CHECK-NEXT:      "signatureHelpProvider": {
 # CHECK-NEXT:        "triggerCharacters": [
 # CHECK-NEXT:          "(",
 # CHECK-NEXT:          ","
 # CHECK-NEXT:        ]
 # CHECK-NEXT:      },
-# CHECK-NEXT:      "textDocumentSync": 1
+# CHECK-NEXT:      "textDocumentSync": 2
 # CHECK-NEXT:    }
 # CHECK-NEXT:  }
 ---
 {"jsonrpc":"2.0","id":3,"method":"shutdown"}
 #      CHECK:  "id": 3,
 # CHECK-NEXT:  "jsonrpc": "2.0",
 # CHECK-NEXT:  "result": null
 ---
 {"jsonrpc":"2.0":"method":"exit"}

unittests/clangd/CMakeLists.txt

 
 add_extra_unittest(ClangdTests
   Annotations.cpp
   ClangdTests.cpp
   ClangdUnitTests.cpp
   CodeCompleteTests.cpp
   CodeCompletionStringsTests.cpp
   ContextTests.cpp
+  DraftStoreTests.cpp
   FileIndexTests.cpp
   FuzzyMatchTests.cpp
   HeadersTests.cpp
   IndexTests.cpp
   JSONExprTests.cpp
   SourceCodeTests.cpp
   SymbolCollectorTests.cpp
   SyncAPI.cpp

unittests/clangd/DraftStoreTests.cpp

+//===-- DraftStoreTests.cpp - Clangd unit tests -----------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Annotations.h"
+#include "DraftStore.h"
+#include "SourceCode.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+
+using namespace llvm;
+
+struct IncrementalTestStep {
+  StringRef Src;
+  StringRef Contents;
+};
+
+static int rangeLength(StringRef Code, const Range &Rng) {
+  size_t Start = positionToOffset(Code, Rng.start);
+  size_t End = positionToOffset(Code, Rng.end);
+
+  assert(Start <= Code.size());
+  assert(End <= Code.size());
+
+  return End - Start;
+}
+
+// Send the changes one by one to updateDraft, verify the intermediate results.
+
+static void stepByStep(llvm::ArrayRef<IncrementalTestStep> Steps) {
+  DraftStore DS;
+  Annotations InitialSrc(Steps.front().Src);
+  const char Path[] = "/hello.cpp";
+
+  // Set the initial content.
+  DS.addDraft(Path, InitialSrc.code());
+
+  for (size_t i = 1; i < Steps.size(); i++) {
+    Annotations SrcBefore(Steps[i - 1].Src);
+    Annotations SrcAfter(Steps[i].Src);
+    StringRef Contents = Steps[i - 1].Contents;
+    TextDocumentContentChangeEvent Event{
+        SrcBefore.range(),
+        rangeLength(SrcBefore.code(), SrcBefore.range()),
+        Contents.str(),
+    };
+
+    llvm::Expected<std::string> Result = DS.updateDraft(Path, {Event});
+    EXPECT_TRUE(!!Result);
+    EXPECT_EQ(*Result, SrcAfter.code());
+    EXPECT_EQ(*DS.getDraft(Path), SrcAfter.code());
+  }
+}
+
+// Send all the changes at once to updateDraft, check only the final result.
+
+static void allAtOnce(llvm::ArrayRef<IncrementalTestStep> Steps) {
+  DraftStore DS;
+  Annotations InitialSrc(Steps.front().Src);
+  Annotations FinalSrc(Steps.back().Src);
+  const char Path[] = "/hello.cpp";
+  std::vector<TextDocumentContentChangeEvent> Changes;
+
+  for (size_t i = 0; i < Steps.size() - 1; i++) {
+    Annotations Src(Steps[i].Src);
+    StringRef Contents = Steps[i].Contents;
+
+    Changes.push_back({
+        Src.range(),
+        rangeLength(Src.code(), Src.range()),
+        Contents.str(),
+    });
+  }
+
+  // Set the initial content.
+  DS.addDraft(Path, InitialSrc.code());
+
+  llvm::Expected<std::string> Result = DS.updateDraft(Path, Changes);
+
+  EXPECT_TRUE(!!Result) << llvm::toString(Result.takeError());
+  EXPECT_EQ(*Result, FinalSrc.code());
+  EXPECT_EQ(*DS.getDraft(Path), FinalSrc.code());
+}
+
+TEST(DraftStoreIncrementalUpdateTest, Simple) {
+  // clang-format off
+  IncrementalTestStep Steps[] =
+    {
+      // Replace a range
+      {
+R"cpp(static int
+hello[[World]]()
+{})cpp",
+        "Universe"
+      },
+      // Delete a range
+      {
+R"cpp(static int
+hello[[Universe]]()
+{})cpp",
+        ""
+      },
+      // Add a range
+      {
+R"cpp(static int
+hello[[]]()
+{})cpp",
+        "Monde"
+      },
+      {
+R"cpp(static int
+helloMonde()
+{})cpp",
+        ""
+      }
+    };
+  // clang-format on
+
+  stepByStep(Steps);
+  allAtOnce(Steps);
+}
+
+TEST(DraftStoreIncrementalUpdateTest, MultiLine) {
+  // clang-format off
+  IncrementalTestStep Steps[] =
+    {
+      // Replace a range
+      {
+R"cpp(static [[int
+helloWorld]]()
+{})cpp",
+R"cpp(char
+welcome)cpp"
+      },
+      // Delete a range
+      {
+R"cpp(static char[[
+welcome]]()
+{})cpp",
+        ""
+      },
+      // Add a range
+      {
+R"cpp(static char[[]]()
+{})cpp",
+        R"cpp(
+cookies)cpp"
+      },
+      // Replace the whole file
+      {
+R"cpp([[static char
+cookies()
+{}]])cpp",
+        R"cpp(#include <stdio.h>
+)cpp"
+      },
+      // Delete the whole file
+      {
+        R"cpp([[#include <stdio.h>
+]])cpp",
+        "",
+      },
+      // Add something to an empty file
+      {
+        "[[]]",
+        R"cpp(int main() {
+)cpp",
+      },
+      {
+        R"cpp(int main() {
+)cpp",
+        ""
+      }
+    };
+  // clang-format on
+
+  stepByStep(Steps);
+  allAtOnce(Steps);
+}
+
+TEST(DraftStoreIncrementalUpdateTest, WrongRangeLength) {
+  DraftStore DS;
+  Path File = "foo.cpp";
+
+  DS.addDraft(File, "int main() {}\n");
+
+  TextDocumentContentChangeEvent Change;
+  Change.range.emplace();
+  Change.range->start.line = 0;
+  Change.range->start.character = 0;
+  Change.range->end.line = 0;
+  Change.range->end.character = 2;
+  Change.rangeLength = 10;
+
+  llvm::Expected<std::string> Result = DS.updateDraft(File, {Change});
+
+  EXPECT_TRUE(!Result);
+  EXPECT_EQ(
+      llvm::toString(Result.takeError()),
+      "Change's rangeLength (10) doesn't match the computed range length (2).");
+}
+
+TEST(DraftStoreIncrementalUpdateTest, EndBeforeStart) {
+  DraftStore DS;
+  Path File = "foo.cpp";
+
+  DS.addDraft(File, "int main() {}\n");
+
+  TextDocumentContentChangeEvent Change;
+  Change.range.emplace();
+  Change.range->start.line = 0;
+  Change.range->start.character = 5;
+  Change.range->end.line = 0;
+  Change.range->end.character = 3;
+
+  llvm::Expected<std::string> Result = DS.updateDraft(File, {Change});
+
+  EXPECT_TRUE(!Result);
+  EXPECT_EQ(llvm::toString(Result.takeError()),
+            "Range's end position (line=0, character=3) is before start "
+            "position (line=0, character=5).");
+}
+
+} // namespace
+} // namespace clangd
+} // namespace clang