[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 ↗

(On Diff #230065)

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

444

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 ↗

(On Diff #230065)

removed now, not needed.

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

444

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

453

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).

458

NIT: braces are redundant and can be dropped.

459

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/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 occurrences with the
+/// NewName.
+/// Exposed for testing only.
+llvm::Expected<Edit> buildRenameEdit(llvm::StringRef InitialCode,
+                                     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

 #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/Error.h"
+#include "llvm/Support/FormatVariadic.h"
 
 namespace clang {
 namespace clangd {
 namespace {
 
 llvm::Optional<std::string> filePath(const SymbolLocation &Loc,
                                      llvm::StringRef HintFilePath) {
   if (!Loc)
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(
   if (AffectedFiles.size() >= MaxLimitFiles)
     return llvm::make_error<llvm::StringError>(
         llvm::formatv(
             "The number of affected files exceeds the max limit {0}: {1}",
             MaxLimitFiles, AffectedFiles.size()),
         llvm::inconvertibleErrorCode());
 
   FileEdits Results;
-  for (const auto &FileAndOccurrences : AffectedFiles) {
+  for (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();
+    auto RenameEdit = buildRenameEdit(
+        *AffectedFileCode, std::move(FileAndOccurrences.second), NewName);
+    if (!RenameEdit) {
+      return llvm::make_error<llvm::StringError>(
+          llvm::formatv("fail to build rename edit for file {0}: {1}", FilePath,
+                        llvm::toString(RenameEdit.takeError())),
+          llvm::inconvertibleErrorCode());
+    }
     if (!RenameEdit->Replacements.empty())
       Results.insert({FilePath, std::move(*RenameEdit)});
   }
   return Results;
 }
 
 } // namespace
 
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,
+                                     std::vector<Range> Occurrences,
+                                     llvm::StringRef NewName) {
+  llvm::sort(Occurrences);
+  // These two always correspond to the same position.
+  Position LastPos{0, 0};
+  size_t LastOffset = 0;
+
+  auto Offset = [&](const Position &P) -> llvm::Expected<size_t> {
+    assert(LastPos <= P && "malformed input");
+    Position Shifted = {
+        P.line - LastPos.line,
+        P.line > LastPos.line ? P.character : P.character - LastPos.character};
+    auto ShiftedOffset =
+        positionToOffset(InitialCode.substr(LastOffset), Shifted);
+    if (!ShiftedOffset)
+      return llvm::make_error<llvm::StringError>(
+          llvm::formatv("fail to convert the position {0} to offset ({1})", P,
+                        llvm::toString(ShiftedOffset.takeError())),
+          llvm::inconvertibleErrorCode());
+    LastPos = P;
+    LastOffset += *ShiftedOffset;
+    return LastOffset;
+  };
+
+  std::vector<std::pair</*start*/ size_t, /*end*/ size_t>> OccurrencesOffsets;
+  for (const auto &R : Occurrences) {
+    auto StartOffset = Offset(R.start);
+    if (!StartOffset)
+      return StartOffset.takeError();
+    auto EndOffset = Offset(R.end);
+    if (!EndOffset)
+      return EndOffset.takeError();
+    OccurrencesOffsets.push_back({*StartOffset, *EndOffset});
+  }
+
+  tooling::Replacements RenameEdit;
+  for (const auto &R : OccurrencesOffsets) {
+    auto ByteLength = R.second - R.first;
+    if (auto Err = RenameEdit.add(
+            tooling::Replacement(InitialCode, R.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)) << Edit.takeError();
+  ASSERT_EQ(1UL, Edit->Replacements.size());
+  EXPECT_EQ(4UL, Edit->Replacements.begin()->getLength());
+
+  // Test invalid range.
+  LSPRange.end = {10, 0}; // out of range
+  Edit = buildRenameEdit(Code.code(), {LSPRange}, "abc");
+  EXPECT_FALSE(Edit);
+  EXPECT_THAT(llvm::toString(Edit.takeError()),
+              testing::HasSubstr("fail to convert"));
+
+  // Normal ascii characters.
+  Annotations T(R"cpp(
+    [[range]]
+              [[range]]
+      [[range]]
+  )cpp");
+  Edit = buildRenameEdit(T.code(), T.ranges(), "abc");
+  ASSERT_TRUE(bool(Edit)) << Edit.takeError();
+  EXPECT_EQ(applyEdits(FileEdits{{T.code(), std::move(*Edit)}}).front().second,
+            expectedResult(Code, expectedResult(T, "abc")));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang