[clangd] Heuristic to avoid desync if editors are confused about newline-at-eof

[sammccall]

Summary

As strange as it seems to our files-are-strings view of the world, some editors
that treat files as arrays of lines can get confused about whether the last line
has a newline or not.

The consequences of failing to handle a bad incremental update are catastrophic.
If an update would be valid except for a missing newline at end of file, pretend
one exists.

This fixes problems still present in neovim where deleting all text often leads
to a desync shortly afterwards: https://github.com/neovim/neovim/issues/17085

[sammccall]

Sorry to dump more patches on you, but I want your opinion on whether we should carry such a hack.

My initial inclination is no, but the class of bug is not very hard to understand, could plausibly come up in other clients, and the fix is fairly simple.
I'd like to get this bug fixed in neovim. However it's survived two attempts by me to debug it and an attempt by the maintainer to fix it!

[sammccall]

(also the desyncs are incredibly annoying, and happen pretty much any time you clear all text out of a file)

[kadircet]

i also would rather not have the workaround solely for an editor (we usually try to address these on editor/plugin side). i am also worried about the understanding of that inferred line afterwards (e.g. what if editor thinks that line doesn't have a trailing \n and send edits with that view of the world, or somehow attributes the \n to the next line instead)

moreover, this won't fix the issue for existing clangd's (and until the next release). so i'd rather get it fixed on the client side (and if we can't, i guess editors that can't have delta changes reliably just send full text as changes).

[sammccall]

In D135508#3846231, @kadircet wrote:

i also would rather not have the workaround solely for an editor (we usually try to address these on editor/plugin side).

Yeah, for sure. My main concern is that in practice it won't get fixed, but I'll open a new bug and see (the old one is closed because we thought it was fixed).

i am also worried about the understanding of that inferred line afterwards (e.g. what if editor thinks that line doesn't have a trailing \n and send edits with that view of the world, or somehow attributes the \n to the next line instead)

The former can't really happen: the only edits that can touch this phantom newline either a) replace it, or b) replace text after it.
In the a) case it's gone so we'd agree with the editor, in the b) case... I can't imagine how a line-array-based editor could x on line 3 and then later claim line 2 and 3 are the same line as "I never added the newline".

moreover, this won't fix the issue for existing clangd's (and until the next release).

This is very true, though it cuts both ways: if we fix nvim then nvim 0.5-0.8 remain broken. The release & update cadence there is pretty similar to clangd.

so i'd rather get it fixed on the client side (and if we can't, i guess editors that can't have delta changes reliably just send full text as changes).

Turning off delta is an interesting idea, I'll mention that on the bug.

[kadircet]

as discussed, this is a rather contained fix that are likely to help with other editors that might get confused with new-lines at EOF. so LGTM

clang-tools-extra/clangd/SourceCode.cpp

 llvm::Error reformatEdit(Edit &E, const format::FormatStyle &Style) {
   if (auto NewEdits = cleanupAndFormat(E.InitialCode, E.Replacements, Style))
     E.Replacements = std::move(*NewEdits);
   else
     return NewEdits.takeError();
   return llvm::Error::success();
 }
 
+// Workaround for editors that have buggy handling of newlines at end of file.
+//
+// The editor is supposed to expose document contents over LSP as an exact
+// string, with whitespace and newlines well-defined. But internally many
+// editors treat text as an array of lines, and there can be ambiguity over
+// whether the last line ends with a newline or not.
+//
+// This confusion can lead to incorrect edits being sent. Failing to apply them
+// is catastrophic: we're desynced, LSP has no mechanism to get back in sync.
+// We apply a heuristic to avoid this state.
+//
+// If our current view of an N-line file does *not* end in a newline, but the
+// editor refers to the start of the next line (an impossible location), then
+// we silently add a newline to make this valid.
+// We will still validate that the rangeLength is correct, *including* the
+// inferred newline.
+//
+// See https://github.com/neovim/neovim/issues/17085
+static void inferFinalNewline(llvm::Expected<size_t> &Err,
+                              std::string &Contents, const Position &Pos) {
+  if (Err)
+    return;
+  if (!Contents.empty() && Contents.back() == '\n')
+    return;
+  if (Pos.character != 0)
+    return;
+  if (Pos.line != llvm::count(Contents, '\n') + 1)
+    return;
+  log("Editor sent invalid change coordinates, inferring newline at EOF");
+  Contents.push_back('\n');
+  consumeError(Err.takeError());
+  Err = Contents.size();
+}
+
 llvm::Error applyChange(std::string &Contents,
                         const TextDocumentContentChangeEvent &Change) {
   if (!Change.range) {
     Contents = Change.text;
     return llvm::Error::success();
   }
 
   const Position &Start = Change.range->start;
   llvm::Expected<size_t> StartIndex = positionToOffset(Contents, Start, false);
+  inferFinalNewline(StartIndex, Contents, Start);
   if (!StartIndex)
     return StartIndex.takeError();
 
   const Position &End = Change.range->end;
   llvm::Expected<size_t> EndIndex = positionToOffset(Contents, End, false);
+  inferFinalNewline(EndIndex, Contents, End);
   if (!EndIndex)
     return EndIndex.takeError();
 
   if (*EndIndex < *StartIndex)
     return error(llvm::errc::invalid_argument,
                  "Range's end position ({0}) is before start position ({1})",
                  End, Start);
 

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

TEST(ApplyEditsTest, WrongRangeLength) {
   Change.range->end.character = 2;
   Change.rangeLength = 10;
 
   EXPECT_THAT_ERROR(applyChange(Code, Change),
                     FailedWithMessage("Change's rangeLength (10) doesn't match "
                                       "the computed range length (2)."));
 }
 
+// Test that we correct observed buggy edits from Neovim.
+TEST(ApplyEditsTets, BuggyNeovimEdits) {
+  TextDocumentContentChangeEvent Change;
+  Change.range.emplace();
+
+  // https://github.com/neovim/neovim/issues/17085
+  // Adding a blank line after a (missing) newline
+  std::string Code = "a";
+  Change.range->start.line = 1;
+  Change.range->start.character = 0;
+  Change.range->end.line = 1;
+  Change.range->start.character = 0;
+  Change.rangeLength = 0;
+  Change.text = "\n";
+  EXPECT_THAT_ERROR(applyChange(Code, Change), llvm::Succeeded());
+  EXPECT_EQ(Code, "a\n\n");
+
+  // https://github.com/neovim/neovim/issues/17085#issuecomment-1269162264
+  // Replacing the (missing) newline with \n\n in an empty file.
+  Code = "";
+  Change.range->start.line = 0;
+  Change.range->start.character = 0;
+  Change.range->end.line = 1;
+  Change.range->end.character = 0;
+  Change.rangeLength = 1;
+  Change.text = "\n\n";
+
+  EXPECT_THAT_ERROR(applyChange(Code, Change), llvm::Succeeded());
+  EXPECT_EQ(Code, "\n\n");
+
+  // We do not apply the heuristic fixes if the rangeLength doesn't match.
+  Code = "";
+  Change.rangeLength = 0;
+  EXPECT_THAT_ERROR(applyChange(Code, Change),
+                    FailedWithMessage("Change's rangeLength (0) doesn't match "
+                                      "the computed range length (1)."));
+}
+
 TEST(ApplyEditsTest, EndBeforeStart) {
   std::string Code = "int main() {}\n";
 
   TextDocumentContentChangeEvent Change;
   Change.range.emplace();
   Change.range->start.line = 0;
   Change.range->start.character = 5;
   Change.range->end.line = 0;