Fix range length comparison in DraftStore::UpdateDraft when Unicode characters are removed from the document

[DaanDeMeyer]

Summary

See http://lists.llvm.org/pipermail/clangd-dev/2018-October/000171.html for context.

I kept the error (instead of downgrading to a log message) since the range lengths differing does indicate either a bug in the client or server range calculation or the buffers being out of sync (which both seems serious enough to me to be an error). If any existing clients aside from VSCode break they should only break when accidentally typing a Unicode character which should only be a minor nuisance for a little while until the bug is fixed in the respective client.

[sammccall]

Thanks for the fix! Just comment nits.

clangd/DraftStore.cpp

85 ↗

(On Diff #170486)

can we summarize this a bit?, e.g.
// EndIndex and StartIndex are in bytes, but rangeLength is in UTF-16 units
no need to explain exactly what the code is doing, just need to say why.

clangd/SourceCode.cpp

70 ↗

(On Diff #170486)

actually just moving this comment to the header would be great!

73 ↗

(On Diff #170486)

could you few simple assertions for this function (maybe ascii, BMP, astral) to unittests/clangd/SourceCodeTests.cpp?

clangd/SourceCode.h

26 ↗

(On Diff #170486)

I think it would be helpful to mention here (only in the comment!) that this is UTF-16 code units.

[DaanDeMeyer]

Update diff according to comments.

clang-tools-extra/trunk/clangd/DraftStore.cpp

if (!EndIndex)
       return EndIndex.takeError();
 
     if (*EndIndex < *StartIndex)
       return make_error<StringError>(
           formatv("Range's end position ({0}) is before start position ({1})",
                   End, Start),
           llvm::errc::invalid_argument);
 
-    if (Change.rangeLength &&
-        (ssize_t)(*EndIndex - *StartIndex) != *Change.rangeLength)
+    // Since the range length between two LSP positions is dependent on the
+    // contents of the buffer we compute the range length between the start and
+    // end position ourselves and compare it to the range length of the LSP
+    // message to verify the buffers of the client and server are in sync.
+
+    // EndIndex and StartIndex are in bytes, but Change.rangeLength is in UTF-16
+    // code units.
+    ssize_t ComputedRangeLength =
+        lspLength(Contents.substr(*StartIndex, *EndIndex - *StartIndex));
+
+    if (Change.rangeLength && ComputedRangeLength != *Change.rangeLength)
       return make_error<StringError>(
           formatv("Change's rangeLength ({0}) doesn't match the "
                   "computed range length ({1}).",
                   *Change.rangeLength, *EndIndex - *StartIndex),
           llvm::errc::invalid_argument);
 
     std::string NewContents;
     NewContents.reserve(*StartIndex + Change.text.length() +

clang-tools-extra/trunk/clangd/SourceCode.h

 #include "clang/Basic/SourceLocation.h"
 #include "clang/Tooling/Core/Replacement.h"
 
 namespace clang {
 class SourceManager;
 
 namespace clangd {
 
+// Counts the number of UTF-16 code units needed to represent a string (LSP
+// specifies string lengths in UTF-16 code units).
+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.
 ///
 /// The returned value is in the range [0, Code.size()].
 llvm::Expected<size_t>

clang-tools-extra/trunk/clangd/SourceCode.cpp

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());
 }
 
-// Counts the number of UTF-16 code units needed to represent a string.
 // Like most strings in clangd, the input is UTF-8 encoded.
-static size_t utf16Len(StringRef U8) {
+size_t lspLength(StringRef Code) {
   // 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(U8, [&](int U8Len, int U16Len) {
+  iterateCodepoints(Code, [&](int U8Len, int U16Len) {
     Count += U16Len;
     return false;
   });
   return Count;
 }
 
 Expected<size_t> positionToOffset(StringRef Code, Position P,
                                   bool AllowColumnsBeyondLineLength) {

 Position offsetToPosition(StringRef Code, size_t Offset) {
   Offset = std::min(Code.size(), Offset);
   StringRef Before = Code.substr(0, Offset);
   int Lines = Before.count('\n');
   size_t PrevNL = Before.rfind('\n');
   size_t StartOfLine = (PrevNL == StringRef::npos) ? 0 : (PrevNL + 1);
   Position Pos;
   Pos.line = Lines;
-  Pos.character = utf16Len(Before.substr(StartOfLine));
+  Pos.character = lspLength(Before.substr(StartOfLine));
   return Pos;
 }
 
 Position sourceLocToPosition(const SourceManager &SM, SourceLocation Loc) {
   // We use the SourceManager's line tables, but its column number is in bytes.
   FileID FID;
   unsigned Offset;
   std::tie(FID, Offset) = SM.getDecomposedSpellingLoc(Loc);
   Position P;
   P.line = static_cast<int>(SM.getLineNumber(FID, Offset)) - 1;
   bool Invalid = false;
   StringRef Code = SM.getBufferData(FID, &Invalid);
   if (!Invalid) {
     auto ColumnInBytes = SM.getColumnNumber(FID, Offset) - 1;
     auto LineSoFar = Code.substr(Offset - ColumnInBytes, ColumnInBytes);
-    P.character = utf16Len(LineSoFar);
+    P.character = lspLength(LineSoFar);
   }
   return P;
 }
 
 Range halfOpenToRange(const SourceManager &SM, CharSourceRange R) {
   // Clang is 1-based, LSP uses 0-based indexes.
   Position Begin = sourceLocToPosition(SM, R.getBegin());
   Position End = sourceLocToPosition(SM, R.getEnd());

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

 
 Range range(const std::pair<int, int> p1, const std::pair<int, int> p2) {
   Range range;
   range.start = position(p1.first, p1.second);
   range.end = position(p2.first, p2.second);
   return range;
 }
 
+TEST(SourceCodeTests, lspLength) {
+  EXPECT_EQ(lspLength(""), 0UL);
+  EXPECT_EQ(lspLength("ascii"), 5UL);
+  // BMP
+  EXPECT_EQ(lspLength("↓"), 1UL);
+  EXPECT_EQ(lspLength("¥"), 1UL);
+  // astral
+  EXPECT_EQ(lspLength("😂"), 2UL);
+}
+
 TEST(SourceCodeTests, PositionToOffset) {
   // line out of bounds
   EXPECT_THAT_EXPECTED(positionToOffset(File, position(-1, 2)), Failed());
   // first line
   EXPECT_THAT_EXPECTED(positionToOffset(File, position(0, -1)),
                        Failed()); // out of range
   EXPECT_THAT_EXPECTED(positionToOffset(File, position(0, 0)),
                        HasValue(0)); // first character