Make positionToOffset return llvm::Expected<size_t>

[simark]

Summary

To implement incremental document syncing, we want to verify that the
ranges provided by the front-end are valid. Currently, positionToOffset
deals with invalid Positions by returning 0 or Code.size(), which are
two valid offsets.

Instead, return an llvm:Expected<size_t> with an error if the position
is invalid. According to the LSP, if the character value exceeds the
number of characters of the given line, it should default back to the
end of the line, so this is what I did. However, I considered a line
number larger than the number of lines in the file to be an error.

[ilya-biryukov]

clangd/ClangdServer.cpp

196

NIT: maybe remove empty lines? they don't seem to add much to readability, since when prev line is indented.
up to you.

clangd/SourceCode.cpp

20

This lambda carries its weight. Maybe inline it?

23

NIT: don't add empty lines here too?

30

I find the previous code more readable, the more values are "outputs" of the loop, the trickier it gets to read.
I suggest keeping NextNL inside a loop:

size_t StartOfLine = 0;
for (int I = 0; I != P.line; ++I) {
  size_t NextNL = Code.find('\n', StartOfLine);
  if (NextNL == StringRef::npos)
     return Err(...);
  StartOfLine = NextNL + 1;
}
size_t LastColumn = Code.fine('\n', StartOfLine);
if (LastColumn == StringRef::npos)
  LastColumn = Code.size();
return std::min(LastColumn, StartOfLine = P.character);

40

NIT: remove braces around single-statement if

clangd/SourceCode.h

25–38

Reverting to line length for larger column numbers seems to be the wrong thing to do for content changes, even though LSP does not distinguish this case.
The fundamental difference is that position provided as inputs to features are caret or selection positions and it makes sense for them to span non-existing columns if the editors allows to put the caret there. Text changes, on the other hand, should be generated from proper offsets inside a string and it does not make sense for their columns to be out of range.
I suggest to add a param with default argument to the function to control this behavior (bool AllowColumnsBeyondLineLength = true).

unittests/clangd/Annotations.cpp

91

NIT: remove empty lines

unittests/clangd/SourceCodeTests.cpp

41

NIT: opening must be on the previous line

41

Use matchers from include/llvm/Testing/Support/Error.h instead of the helper functions:

using llvm::Failed;
using llvm::HasValue;
using testing::Eq;

// ....

EXPECT_THAT_EXPECTED(positionToOffset(File, position(-1, 2)), HasValue(Eq(2)));
EXPECT_THAT_EXPECTED(positionToOffset(File, position(100, 200)), Failed);

[simark]

Address review comments

[simark]

clangd/SourceCode.h

25–38

Ok, when AllowColumnsBeyondLineLength is false and the character value exceeds the line length, I now return an error.

unittests/clangd/SourceCodeTests.cpp

41

Oops, forgot to run clang-format this time.

[ilya-biryukov]

LGTM. See the empty line NITS, though.

clangd/ClangdServer.cpp

199

NIT: unnecessary empty line

215

NIT: unnecessary empty line

clangd/SourceCode.cpp

29

NIT: unnecessary empty line

47

NIT: unnecessary empty line

unittests/clangd/Annotations.cpp

91

NIT: unnecessary empty line

94

NIT: unnecessary empty line

[ilya-biryukov]

clangd/SourceCode.h

42

We should be consistent for all functions inside this fail. They may all fail for the same reasons, and it doesn't make sense for them to have a different interfaces.
Could you add a FIXME that we should update other functions to report errors?

[simark]

Remove spaces, add fixmes

[simark]

clangd/ClangdServer.cpp

199

In general I like spacing out the different logical blocks of code a little bit, especially after a "return", but I don't mind removing them.

[ilya-biryukov]

clangd/ClangdServer.cpp

199

We don't really have a style rule for that, but most of clangd code does not have that many empty lines.
I personally think it's fine to have reasonable style differences in new functions, but I prefer to stick to the original author's style when refactoring code. Hence my suggestions to remove the empty lines here.

clangd/ClangdServer.cpp

void ClangdServer::signatureHelp(PathRef File, Position Pos,
   };
 
   WorkScheduler.runWithPreamble("SignatureHelp", File,
                                 Bind(Action, File.str(), std::move(CB)));
 }
 
 llvm::Expected<tooling::Replacements>
 ClangdServer::formatRange(StringRef Code, PathRef File, Range Rng) {
-  size_t Begin = positionToOffset(Code, Rng.start);
-  size_t Len = positionToOffset(Code, Rng.end) - Begin;
-  return formatCode(Code, File, {tooling::Range(Begin, Len)});
+  llvm::Expected<size_t> Begin = positionToOffset(Code, Rng.start);
+  if (!Begin)
+    return Begin.takeError();
+  llvm::Expected<size_t> End = positionToOffset(Code, Rng.end);
+  if (!End)
+    return End.takeError();
+  return formatCode(Code, File, {tooling::Range(*Begin, *End - *Begin)});
 }
 
 llvm::Expected<tooling::Replacements> ClangdServer::formatFile(StringRef Code,
                                                                PathRef File) {
   // Format everything.
   return formatCode(Code, File, {tooling::Range(0, Code.size())});
 }
 
 llvm::Expected<tooling::Replacements>
 ClangdServer::formatOnType(StringRef Code, PathRef File, Position Pos) {
   // Look for the previous opening brace from the character position and
   // format starting from there.
-  size_t CursorPos = positionToOffset(Code, Pos);
-  size_t PreviousLBracePos = StringRef(Code).find_last_of('{', CursorPos);
+  llvm::Expected<size_t> CursorPos = positionToOffset(Code, Pos);
+  if (!CursorPos)
+    return CursorPos.takeError();
+  size_t PreviousLBracePos = StringRef(Code).find_last_of('{', *CursorPos);
   if (PreviousLBracePos == StringRef::npos)
-    PreviousLBracePos = CursorPos;
-  size_t Len = CursorPos - PreviousLBracePos;
+    PreviousLBracePos = *CursorPos;
+  size_t Len = *CursorPos - PreviousLBracePos;
 
   return formatCode(Code, File, {tooling::Range(PreviousLBracePos, Len)});
 }
 
 void ClangdServer::rename(PathRef File, Position Pos, llvm::StringRef NewName,
                           Callback<std::vector<tooling::Replacement>> CB) {
   auto Action = [Pos](Path File, std::string NewName,
                       Callback<std::vector<tooling::Replacement>> CB,

clangd/SourceCode.h

 #include "clang/Basic/SourceLocation.h"
 
 namespace clang {
 class SourceManager;
 
 namespace clangd {
 
 /// Turn a [line, column] pair into an offset in Code.
-size_t positionToOffset(llvm::StringRef Code, Position P);
+///
+/// If the character value is greater than the line length, the behavior depends
+/// on AllowColumnsBeyondLineLength:
+///
+/// - if true: default back to the end of the line
+/// - if false: return an error
+///
+/// If the line number is greater than the number of lines in the document,
+/// always return an error.
+///
+/// The returned value is in the range [0, Code.size()].
+llvm::Expected<size_t>
+positionToOffset(llvm::StringRef Code, Position P,
+                 bool AllowColumnsBeyondLineLength = true);
 
 /// Turn an offset in Code into a [line, column] pair.
+/// FIXME: This should return an error if the offset is invalid.
 Position offsetToPosition(llvm::StringRef Code, size_t Offset);
 
 /// Turn a SourceLocation into a [line, column] pair.
+/// FIXME: This should return an error if the location is invalid.
 Position sourceLocToPosition(const SourceManager &SM, SourceLocation Loc);
 
 // Converts a half-open clang source range to an LSP range.
 // Note that clang also uses closed source ranges, which this can't handle!
 Range halfOpenToRange(const SourceManager &SM, CharSourceRange R);
 
 } // namespace clangd
 } // namespace clang
 #endif

clangd/SourceCode.cpp

 //===--- SourceCode.h - Manipulating source code as strings -----*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 #include "SourceCode.h"
 
 #include "clang/Basic/SourceManager.h"
+#include "llvm/Support/Errc.h"
+#include "llvm/Support/Error.h"
 
 namespace clang {
 namespace clangd {
 using namespace llvm;
 
-size_t positionToOffset(StringRef Code, Position P) {
+llvm::Expected<size_t> positionToOffset(StringRef Code, Position P,
+                                        bool AllowColumnsBeyondLineLength) {
   if (P.line < 0)
-    return 0;
+    return llvm::make_error<llvm::StringError>(
+        llvm::formatv("Line value can't be negative ({0})", P.line),
+        llvm::errc::invalid_argument);
+  if (P.character < 0)
+    return llvm::make_error<llvm::StringError>(
+        llvm::formatv("Character value can't be negative ({0})", P.character),
+        llvm::errc::invalid_argument);
   size_t StartOfLine = 0;
   for (int I = 0; I != P.line; ++I) {
     size_t NextNL = Code.find('\n', StartOfLine);
     if (NextNL == StringRef::npos)
-      return Code.size();
+      return llvm::make_error<llvm::StringError>(
+          llvm::formatv("Line value is out of range ({0})", P.line),
+          llvm::errc::invalid_argument);
     StartOfLine = NextNL + 1;
   }
+
+  size_t NextNL = Code.find('\n', StartOfLine);
+  if (NextNL == StringRef::npos)
+    NextNL = Code.size();
+
+  if (StartOfLine + P.character > NextNL && !AllowColumnsBeyondLineLength)
+    return llvm::make_error<llvm::StringError>(
+        llvm::formatv("Character value is out of range ({0})", P.character),
+        llvm::errc::invalid_argument);
   // FIXME: officially P.character counts UTF-16 code units, not UTF-8 bytes!
-  return std::min(Code.size(), StartOfLine + std::max(0, P.character));
+  return std::min(NextNL, StartOfLine + P.character);
 }
 
 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);

unittests/clangd/Annotations.cpp

 std::vector<Range> Annotations::ranges(llvm::StringRef Name) const {
   auto R = Ranges.lookup(Name);
   return {R.begin(), R.end()};
 }
 
 std::pair<std::size_t, std::size_t>
 Annotations::offsetRange(llvm::StringRef Name) const {
   auto R = range(Name);
-  return {positionToOffset(Code, R.start), positionToOffset(Code, R.end)};
+  llvm::Expected<size_t> Start = positionToOffset(Code, R.start);
+  llvm::Expected<size_t> End = positionToOffset(Code, R.end);
+  assert(Start);
+  assert(End);
+  return {*Start, *End};
 }
 
 } // namespace clangd
 } // namespace clang

unittests/clangd/CMakeLists.txt

target_link_libraries(ClangdTests
   clangFormat
   clangFrontend
   clangIndex
   clangLex
   clangSema
   clangTooling
   clangToolingCore
   LLVMSupport
+  LLVMTestingSupport
   )

unittests/clangd/SourceCodeTests.cpp

 //===-- SourceCodeTests.cpp  ------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 #include "SourceCode.h"
+#include "llvm/Support/Error.h"
 #include "llvm/Support/raw_os_ostream.h"
+#include "llvm/Testing/Support/Error.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 namespace clang{
 namespace clangd {
 namespace {
 
+using llvm::Failed;
+using llvm::HasValue;
+
 MATCHER_P2(Pos, Line, Col, "") {
   return arg.line == Line && arg.character == Col;
 }
 
 const char File[] = R"(0:0 = 0
 1:0 = 8
 2:0 = 16)";
 
 /// A helper to make tests easier to read.
 Position position(int line, int character) {
   Position Pos;
   Pos.line = line;
   Pos.character = character;
   return Pos;
 }
 
 TEST(SourceCodeTests, PositionToOffset) {
   // line out of bounds
-  EXPECT_EQ(0u, positionToOffset(File, position(-1, 2)));
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(-1, 2)), Failed());
   // first line
-  EXPECT_EQ(0u, positionToOffset(File, position(0, -1))); // out of range
-  EXPECT_EQ(0u, positionToOffset(File, position(0, 0)));  // first character
-  EXPECT_EQ(3u, positionToOffset(File, position(0, 3)));  // middle character
-  EXPECT_EQ(6u, positionToOffset(File, position(0, 6)));  // last character
-  EXPECT_EQ(7u, positionToOffset(File, position(0, 7)));  // the newline itself
-  EXPECT_EQ(8u, positionToOffset(File, position(0, 8)));  // out of range
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(0, -1)),
+                       Failed()); // out of range
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(0, 0)),
+                       HasValue(0)); // first character
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(0, 3)),
+                       HasValue(3)); // middle character
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(0, 6)),
+                       HasValue(6)); // last character
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(0, 7)),
+                       HasValue(7)); // the newline itself
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(0, 7), false),
+                       HasValue(7));
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(0, 8)),
+                       HasValue(7)); // out of range
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(0, 8), false),
+                       Failed()); // out of range
   // middle line
-  EXPECT_EQ(8u, positionToOffset(File, position(1, -1))); // out of range
-  EXPECT_EQ(8u, positionToOffset(File, position(1, 0)));  // first character
-  EXPECT_EQ(11u, positionToOffset(File, position(1, 3))); // middle character
-  EXPECT_EQ(14u, positionToOffset(File, position(1, 6))); // last character
-  EXPECT_EQ(15u, positionToOffset(File, position(1, 7))); // the newline itself
-  EXPECT_EQ(16u, positionToOffset(File, position(1, 8))); // out of range
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(1, -1)),
+                       Failed()); // out of range
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(1, 0)),
+                       HasValue(8)); // first character
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(1, 3)),
+                       HasValue(11)); // middle character
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(1, 3), false),
+                       HasValue(11));
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(1, 6)),
+                       HasValue(14)); // last character
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(1, 7)),
+                       HasValue(15)); // the newline itself
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(1, 8)),
+                       HasValue(15)); // out of range
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(1, 8), false),
+                       Failed()); // out of range
   // last line
-  EXPECT_EQ(16u, positionToOffset(File, position(2, -1))); // out of range
-  EXPECT_EQ(16u, positionToOffset(File, position(2, 0)));  // first character
-  EXPECT_EQ(19u, positionToOffset(File, position(2, 3)));  // middle character
-  EXPECT_EQ(23u, positionToOffset(File, position(2, 7)));  // last character
-  EXPECT_EQ(24u, positionToOffset(File, position(2, 8)));  // EOF
-  EXPECT_EQ(24u, positionToOffset(File, position(2, 9)));  // out of range
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(2, -1)),
+                       Failed()); // out of range
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(2, 0)),
+                       HasValue(16)); // first character
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(2, 3)),
+                       HasValue(19)); // middle character
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(2, 7)),
+                       HasValue(23)); // last character
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(2, 8)),
+                       HasValue(24)); // EOF
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(2, 9), false),
+                       Failed()); // out of range
   // line out of bounds
-  EXPECT_EQ(24u, positionToOffset(File, position(3, 1)));
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(3, 0)), Failed());
+  EXPECT_THAT_EXPECTED(positionToOffset(File, position(3, 1)), Failed());
 }
 
 TEST(SourceCodeTests, OffsetToPosition) {
   EXPECT_THAT(offsetToPosition(File, 0), Pos(0, 0)) << "start of file";
   EXPECT_THAT(offsetToPosition(File, 3), Pos(0, 3)) << "in first line";
   EXPECT_THAT(offsetToPosition(File, 6), Pos(0, 6)) << "end of first line";
   EXPECT_THAT(offsetToPosition(File, 7), Pos(0, 7)) << "first newline";
   EXPECT_THAT(offsetToPosition(File, 8), Pos(1, 0)) << "start of second line";