[clangd] Speed up when building rename edit.

[hokein]

Summary

We used to scan the code everytime when computing the LSP position to the offset
(respect the LSP encoding).

[ilya-biryukov]

clang-tools-extra/clangd/SourceCode.h

54

How this is different from positionToOffset with Pos.line = 0 and Pos.column = LSPCharacter?
Why do we need an extra function?

clang-tools-extra/clangd/refactor/Rename.cpp

441

We are aiming to convert all ranges in O(n) instead of O(n^2), right?
I think this could be simpler and also have guaranteed performance even for long lines if we do it slightly differently. WDYT?

assert(llvm::is_sorted(Occurences));
// These two always correspond to the same position.
Position LastPos = Position{0, 0};
size_t LastOffset = 0;

std::vector<pair<size_t, size_t>> Offsets;
for (auto R : Occurences) {
  Position ShiftedStart = R.start - LastPos;
  size_t ShiftedStartOffset = positionToOffset(ShiftedStart, Code.substr(LastOffset);

  LastPos = ShiftedStart;
  LastOffset  = ShiftedStartOffset;
  // Do the same for the end position.
  // ...
}

// Now we can easily replacements.
// ...

[hokein]

address comments.

[hokein]

clang-tools-extra/clangd/SourceCode.h

54

removed now, not needed.

clang-tools-extra/clangd/refactor/Rename.cpp

441

agree, this is smart. note that we need to pay the cost of sorting, but I think it is totally ok as the number is relatively small.

[ilya-biryukov]

LGTM

clang-tools-extra/clangd/refactor/Rename.cpp

450

add assert(LastPos <= P) to protect against malformed inputs (e.g. if one of occurence ranges would have an endpoint that is before the starting point).

455

NIT: braces are redundant and can be dropped.

456

Could we simply propagate error?
I believe we mostly choose simpler code over more detailed error messages in clangd.

[hokein]

address comments.

[hokein]

update the test.

clang-tools-extra/clangd/SourceCode.h

 // 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);
 
+/// Converts the LSP column character (in UTF-16 code units) to the byte offset.
+/// Use of UTF-16 may be overridden by kCurrentOffsetEncoding.
+llvm::Expected<size_t> byteOffset(StringRef LineCode, int LSPCharacter);
+
 /// 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/clangd/SourceCode.cpp

case OffsetEncoding::UTF32:
     });
     break;
   case OffsetEncoding::UnsupportedEncoding:
     llvm_unreachable("unsupported encoding");
   }
   return Count;
 }
 
+llvm::Expected<size_t> byteOffset(llvm::StringRef LineCode, int LSPCharacter) {
+  bool Valid = false;
+  size_t ByteInLine =
+      measureUnits(LineCode, LSPCharacter, lspEncoding(), Valid);
+  if (!Valid)
+    return llvm::make_error<llvm::StringError>(
+        llvm::formatv("{0} offset {1} is invalid for code: {2}", lspEncoding(),
+                      LSPCharacter, LineCode),
+        llvm::errc::invalid_argument);
+  return ByteInLine;
+}
+
 llvm::Expected<size_t> positionToOffset(llvm::StringRef Code, Position P,
                                         bool AllowColumnsBeyondLineLength) {
   if (P.line < 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>(

clang-tools-extra/clangd/refactor/Rename.h

struct RenameInputs {
   DirtyBufferGetter GetDirtyBuffer = nullptr;
 };
 
 /// Renames all occurrences of the symbol.
 /// If AllowCrossFile is false, returns an error if rename a symbol that's used
 /// in another file (per the index).
 llvm::Expected<FileEdits> rename(const RenameInputs &RInputs);
 
+/// Generates rename edits that replaces all given occurreneces with the
+/// NewName.
+/// Exposed for testing only.
+llvm::Expected<Edit> buildRenameEdit(llvm::StringRef InitialCode,
+                                     const std::vector<Range> &Occurrences,
+                                     llvm::StringRef NewName);
+
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_REFACTOR_RENAME_H

clang-tools-extra/clangd/refactor/Rename.cpp

 //===--- Rename.cpp - Symbol-rename refactorings -----------------*- 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 "refactor/Rename.h"
 #include "AST.h"
 #include "FindTarget.h"
 #include "Logger.h"
 #include "ParsedAST.h"
+#include "Protocol.h"
 #include "Selection.h"
 #include "SourceCode.h"
 #include "index/SymbolCollector.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Tooling/Refactoring/Rename/USRFindingAction.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/Errc.h"
 #include "llvm/Support/Error.h"
 
 namespace clang {
 namespace clangd {
 namespace {
 
 llvm::Optional<std::string> filePath(const SymbolLocation &Loc,
                                      llvm::StringRef HintFilePath) {
Index.refs(RQuest, [&](const Ref &R) {
     if (auto RefFilePath = filePath(R.Location, /*HintFilePath=*/MainFile)) {
       if (*RefFilePath != MainFile)
         AffectedFiles[*RefFilePath].push_back(toRange(R.Location));
     }
   });
   return AffectedFiles;
 }
 
-llvm::Expected<std::pair<size_t, size_t>> toRangeOffset(const clangd::Range &R,
-                                                        llvm::StringRef Code) {
-  auto StartOffset = positionToOffset(Code, R.start);
-  if (!StartOffset)
-    return StartOffset.takeError();
-  auto EndOffset = positionToOffset(Code, R.end);
-  if (!EndOffset)
-    return EndOffset.takeError();
-  return std::make_pair(*StartOffset, *EndOffset);
-};
-
-llvm::Expected<Edit> buildRenameEdit(llvm::StringRef InitialCode,
-                                     const std::vector<Range> &Occurrences,
-                                     llvm::StringRef NewName) {
-  tooling::Replacements RenameEdit;
-  for (const Range &Occurrence : Occurrences) {
-    // FIXME: !positionToOffset is O(N), optimize it.
-    auto RangeOffset = toRangeOffset(Occurrence, InitialCode);
-    if (!RangeOffset)
-      return RangeOffset.takeError();
-    auto ByteLength = RangeOffset->second - RangeOffset->first;
-    if (auto Err = RenameEdit.add(tooling::Replacement(
-            InitialCode, RangeOffset->first, ByteLength, NewName)))
-      return std::move(Err);
-  }
-  return Edit(InitialCode, std::move(RenameEdit));
-}
-
 // Index-based rename, it renames all occurrences outside of the main file.
 //
 // The cross-file rename is purely based on the index, as we don't want to
 // build all ASTs for affected files, which may cause a performance hit.
 // We choose to trade off some correctness for performance and scalability.
 //
 // Clangd builds a dynamic index for all opened files on top of the static
 // index of the whole codebase. Dynamic index is up-to-date (respects dirty
llvm::Expected<FileEdits> renameOutsideFile(
   for (const auto &FileAndOccurrences : AffectedFiles) {
     llvm::StringRef FilePath = FileAndOccurrences.first();
 
     auto AffectedFileCode = GetFileContent(FilePath);
     if (!AffectedFileCode) {
       elog("Fail to read file content: {0}", AffectedFileCode.takeError());
       continue;
     }
-
     auto RenameEdit = buildRenameEdit(*AffectedFileCode,
                                       FileAndOccurrences.getValue(), NewName);
     if (!RenameEdit)
       return RenameEdit.takeError();
     if (!RenameEdit->Replacements.empty())
       Results.insert({FilePath, std::move(*RenameEdit)});
   }
   return Results;
if (RInputs.Index) {
     Results = std::move(*OtherFilesEdits);
   }
   // Attach the rename edits for the main file.
   Results.try_emplace(RInputs.MainFilePath, MainFileCode,
                       std::move(*MainFileRenameEdit));
   return Results;
 }
 
+llvm::Expected<Edit> buildRenameEdit(llvm::StringRef InitialCode,
+                                     const std::vector<Range> &Occurrences,
+                                     llvm::StringRef NewName) {
+  struct Line {
+    llvm::StringRef Content; // withiout trailing '\n'.
+    size_t StartOffset;      // the offset where the line starts
+  };
+  std::vector<Line> LineTable; // index is the line number (0-based).
+  // Build the line table.
+  llvm::StringRef CurrentLine, Rest = InitialCode;
+  size_t Offset = 0;
+  while (!Rest.empty()) {
+    std::tie(CurrentLine, Rest) = Rest.split('\n');
+    LineTable.push_back({CurrentLine, Offset});
+    Offset += CurrentLine.size() + 1;
+  }
+  // Helper functions for converting to offset.
+  auto PositionOffset =
+      [&LineTable](const Position &P) -> llvm::Expected<size_t> {
+    if (P.line < 0 || P.line >= (int)LineTable.size()) {
+      return llvm::make_error<llvm::StringError>(
+          llvm::formatv("Line value is out of range ({0})", P.line),
+          llvm::errc::invalid_argument);
+    }
+    if (P.character < 0) {
+      return llvm::make_error<llvm::StringError>(
+          llvm::formatv("Character value is out of range ({0})", P.character),
+          llvm::errc::invalid_argument);
+    }
+    const auto &CurrentLine = LineTable[P.line];
+    auto OffsetInLine = byteOffset(CurrentLine.Content, P.character);
+    if (!OffsetInLine)
+      return OffsetInLine.takeError();
+    return CurrentLine.StartOffset + *OffsetInLine;
+  };
+  auto ToRangeOffset =
+      [PositionOffset](
+          const Range &R) -> llvm::Expected<std::pair<size_t, size_t>> {
+    auto StartOffset = PositionOffset(R.start);
+    if (!StartOffset)
+      return StartOffset.takeError();
+    auto EndOffset = PositionOffset(R.end);
+    if (!EndOffset)
+      return EndOffset.takeError();
+    return std::make_pair(*StartOffset, *EndOffset);
+  };
+
+  tooling::Replacements RenameEdit;
+  for (const Range &Occurrence : Occurrences) {
+    auto ROffset = ToRangeOffset(Occurrence);
+    if (!ROffset)
+      return ROffset.takeError();
+    auto ByteLength = ROffset->second - ROffset->first;
+    if (auto Err = RenameEdit.add(tooling::Replacement(
+            InitialCode, ROffset->first, ByteLength, NewName)))
+      return std::move(Err);
+  }
+  return Edit(InitialCode, std::move(RenameEdit));
+}
+
 } // namespace clangd
 } // namespace clang

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

TEST(CrossFileRenameTests, CrossFileOnLocalSymbol) {
   llvm::StringRef NewName = "newName";
   auto Results = rename({Code.point(), NewName, AST, Path});
   ASSERT_TRUE(bool(Results)) << Results.takeError();
   EXPECT_THAT(
       applyEdits(std::move(*Results)),
       UnorderedElementsAre(Pair(Eq(Path), Eq(expectedResult(Code, NewName)))));
 }
 
+TEST(CrossFileRenameTests, BuildRenameEdits) {
+  Annotations Code("[[😂]]");
+  auto LSPRange = Code.range();
+  auto Edit = buildRenameEdit(Code.code(), {LSPRange}, "abc");
+  ASSERT_TRUE(bool(Edit));
+  ASSERT_EQ(1UL, Edit->Replacements.size());
+  EXPECT_EQ(4UL, Edit->Replacements.begin()->getLength());
+
+  LSPRange.end = {-1, 100}; // out of range
+  Edit = buildRenameEdit(Code.code(), {LSPRange}, "abc");
+  EXPECT_FALSE(Edit);
+  EXPECT_THAT(llvm::toString(Edit.takeError()),
+              testing::HasSubstr("out of range"));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang

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

TEST(SourceCodeTests, lspLength) {
   EXPECT_EQ(lspLength("ascii"), 5UL);
   // BMP
   EXPECT_EQ(lspLength("↓"), 1UL);
   EXPECT_EQ(lspLength("¥"), 1UL);
   // astral
   EXPECT_EQ(lspLength("😂"), 1UL);
 }
 
+TEST(SourceCodeTests, byteOffset) {
+  // UTF-16 encoding.
+  EXPECT_THAT_EXPECTED(byteOffset("", 0UL), llvm::HasValue(0));
+  EXPECT_THAT_EXPECTED(byteOffset("ascii", 5UL), llvm::HasValue(5));
+  // BMP
+  EXPECT_THAT_EXPECTED(byteOffset("↓", 1UL), llvm::HasValue(3));
+  EXPECT_THAT_EXPECTED(byteOffset("¥", 1UL), llvm::HasValue(2));
+  // astral
+  EXPECT_THAT_EXPECTED(byteOffset("😂", 2UL), llvm::HasValue(4));
+}
+
 // The = → 🡆 below are ASCII (1 byte), BMP (3 bytes), and astral (4 bytes).
 const char File[] = R"(0:0 = 0
 1:0 → 8
 2:0 🡆 18)";
 struct Line {
   unsigned Number;
   unsigned Offset;
   unsigned Length;