[clangd] Add correctness checks for index-based rename

[kbobyrev]

Summary

In some cases the candidate ranges for rename final stage (textual
replacements) are invalid and do not contain references to identifier being
renamed. Examples of such behavior include implicit references that are
currently not filtered out (though in the future they should be dealt with
during the references collection stage).

This patch addresses this issue by explicitly checking whether the text in each
candidate range is equivalent to the renamed identifier's name. It does not make
index-based rename absolutely correct, but it is a cheap way to filter out some
replacements that are clearly incorrect.

[kbobyrev]

@sammccall Indexed.size() > Lexed.size() is one of the assumptions that I think might not hold in real-world scenarios. I was reading patch heuristics code a lot and trying to understand whether anything breaks when this check is not in place, but I couldn't come up with some cases, so I thought it'd be OK to remove it.

I have written down some thoughts on the topic in the issue I opened on GitHub:

https://github.com/clangd/clangd/issues/238

We have briefly discussed range patching heuristics in D71598, @kadircet has more context if you are interested.

I'd be happy to discuss more details once I'm back, let me know if you have any thoughts/comments on the issue.

[kbobyrev]

Improve wording in the comment

[merge_guards_bot]

Unit tests: pass. 61168 tests passed, 0 failed and 728 were skipped.

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[merge_guards_bot]

Unit tests: pass. 61168 tests passed, 0 failed and 728 were skipped.

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[kadircet]

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

378

nit: move both this and invocation above(line 363) out of the loop into a std::string OldName

565

maybe I am missing it but, it is unclear whether start to end is half-open/closed intervals.
could you add a test case with a single character identifier(you might want to accept equality, if this is a closed interval) and add some comments to the OccurrencesOffsets?

[sammccall]

Postfiltering non-textual references won't work for the index-based rename, as the whole adjust-the-ranges algorithm relies on the index references being a subset of textual matches. More details in https://github.com/clangd/clangd/issues/238

It looks like this code change only affects index-based rename, but the attached test is only for AST-based rename.

I thought the plan of record was to make sure the index knew whether the reference was textual or not, and filter them out before calling adjustRenameRanges?

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

798

this isn't valid c++

882

If you want to be sure of fixing this bug, I'd like to see a test case:

• where the index is out of date
• where the macro name is unrelated to the symbol name
• where the macro usages are interleaved with the non-macro usages
• where the macro usages are in the file which is renamed based on the index, not the one where renamed based on ast

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

 
 /// Generates rename edits that replaces all given occurrences with the
 /// NewName.
 /// Exposed for testing only.
 /// REQUIRED: Occurrences is sorted and doesn't have duplicated ranges.
 llvm::Expected<Edit> buildRenameEdit(llvm::StringRef AbsFilePath,
                                      llvm::StringRef InitialCode,
                                      std::vector<Range> Occurrences,
-                                     llvm::StringRef NewName);
+                                     llvm::StringRef NewName,
+                                     llvm::StringRef OldName);
 
 /// Adjusts indexed occurrences to match the current state of the file.
 ///
 /// The Index is not always up to date. Blindly editing at the locations
 /// reported by the index may mangle the code in such cases.
 /// This function determines whether the indexed occurrences can be applied to
 /// this file, and heuristically repairs the occurrences if necessary.
 ///

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

if (!RenameRanges) {
       // entire rename.
       return llvm::make_error<llvm::StringError>(
           llvm::formatv("Index results don't match the content of file {0} "
                         "(the index may be stale)",
                         FilePath),
           llvm::inconvertibleErrorCode());
     }
     auto RenameEdit =
-        buildRenameEdit(FilePath, *AffectedFileCode, *RenameRanges, NewName);
+        buildRenameEdit(FilePath, *AffectedFileCode, *RenameRanges, NewName,
+                        RenameDecl.getNameAsString());
     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)});
llvm::Expected<FileEdits> rename(const RenameInputs &RInputs) {
   Results.try_emplace(RInputs.MainFilePath, MainFileCode,
                       std::move(*MainFileRenameEdit));
   return Results;
 }
 
 llvm::Expected<Edit> buildRenameEdit(llvm::StringRef AbsFilePath,
                                      llvm::StringRef InitialCode,
                                      std::vector<Range> Occurrences,
-                                     llvm::StringRef NewName) {
+                                     llvm::StringRef NewName,
+                                     llvm::StringRef OldName) {
   assert(std::is_sorted(Occurrences.begin(), Occurrences.end()));
   assert(std::unique(Occurrences.begin(), Occurrences.end()) ==
              Occurrences.end() &&
          "Occurrences must be unique");
 
   // These two always correspond to the same position.
   Position LastPos{0, 0};
   size_t LastOffset = 0;
llvm::Expected<Edit> buildRenameEdit(llvm::StringRef AbsFilePath,
   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();
+    // FIXME: We should not generate invalid replacements in the first place,
+    // but it currently happens for implicit references and in some complicated
+    // cases where the might be incorrectly captured tokens.
+    if (*EndOffset > *StartOffset &&
+        InitialCode.slice(*StartOffset, *EndOffset) == OldName)
       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(AbsFilePath, R.first, ByteLength, NewName)))
       return std::move(Err);

 }
 
 llvm::Optional<std::vector<Range>> getMappedRanges(ArrayRef<Range> Indexed,
                                                    ArrayRef<Range> Lexed) {
   assert(!Indexed.empty());
   assert(std::is_sorted(Indexed.begin(), Indexed.end()));
   assert(std::is_sorted(Lexed.begin(), Lexed.end()));
 
-  if (Indexed.size() > Lexed.size()) {
-    vlog("The number of lexed occurrences is less than indexed occurrences");
-    return llvm::None;
-  }
   // Fast check for the special subset case.
   if (std::includes(Indexed.begin(), Indexed.end(), Lexed.begin(), Lexed.end()))
     return Indexed.vec();
 
   std::vector<size_t> Best;
   size_t BestCost = std::numeric_limits<size_t>::max();
   bool HasMultiple = 0;
   std::vector<size_t> ResultStorage;

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

llvm::StringRef FooCC;
       )cpp",
           R"cpp(
         #include "foo.h"
         [[Foo]]::[[Foo]]() {}
         [[Foo]]::~[[Foo]]() {}
 
         void func() {
           [[Foo]] foo;
+          foo.~[[Foo]];
         }
       )cpp",
       },
       {
           // functions.
           R"cpp(
         void [[f^oo]]();
       )cpp",
llvm::StringRef FooCC;
       )cpp",
           R"cpp(
         #include "foo.h"
         Kind ff() {
           return Kind::[[ABC]];
         }
       )cpp",
       },
+      {
+          // Macros and implicit references.
+          R"cpp(
+        class [[Fo^o]] {};
+        #define FooFoo Foo
+      )cpp",
+          R"cpp(
+        #include "foo.h"
+        void bar() {
+          [[Foo]] foo;
+          FooFoo z;
+        }
+      )cpp",
+      },
   };
 
   for (const auto& T : Cases) {
     Annotations FooH(T.FooH);
     Annotations FooCC(T.FooCC);
     std::string FooHPath = testPath("foo.h");
     std::string FooCCPath = testPath("foo.cc");
 
EXPECT_THAT(
       UnorderedElementsAre(Pair(Eq(Path), Eq(expectedResult(Code, NewName)))));
 }
 
 TEST(CrossFileRenameTests, BuildRenameEdits) {
   Annotations Code("[[😂]]");
   auto LSPRange = Code.range();
   llvm::StringRef FilePath = "/test/TestTU.cpp";
   llvm::StringRef NewName = "abc";
-  auto Edit = buildRenameEdit(FilePath, Code.code(), {LSPRange}, NewName);
+  auto Edit = buildRenameEdit(FilePath, Code.code(), {LSPRange}, NewName, "😂");
   ASSERT_TRUE(bool(Edit)) << Edit.takeError();
   ASSERT_EQ(1UL, Edit->Replacements.size());
   EXPECT_EQ(FilePath, Edit->Replacements.begin()->getFilePath());
   EXPECT_EQ(4UL, Edit->Replacements.begin()->getLength());
 
   // Test invalid range.
   LSPRange.end = {10, 0}; // out of range
-  Edit = buildRenameEdit(FilePath, Code.code(), {LSPRange}, NewName);
+  Edit = buildRenameEdit(FilePath, Code.code(), {LSPRange}, NewName, "😂");
   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(FilePath, T.code(), T.ranges(), NewName);
+  Edit = buildRenameEdit(FilePath, T.code(), T.ranges(), NewName, "range");
   ASSERT_TRUE(bool(Edit)) << Edit.takeError();
   EXPECT_EQ(applyEdits(FileEdits{{T.code(), std::move(*Edit)}}).front().second,
             expectedResult(T, NewName));
 }
 
 TEST(CrossFileRenameTests, adjustRenameRanges) {
   // Ranges in IndexedCode indicate the indexed occurrences;
   // ranges in DraftCode indicate the expected mapped result, empty indicates

 TEST(RangePatchingHeuristic, GetMappedRanges) {
   // ^ in LexedCode marks the ranges we expect to be mapped; no ^ indicates
   // there are no mapped ranges.
   struct {
     llvm::StringRef IndexedCode;
     llvm::StringRef LexedCode;
   } Tests[] = {
     {
-      // no lexed ranges.
-      "[[]]",
-      "",
-    },
-    {
       // both line and column are changed, not a near miss.
       R"([[]])",
       R"(
         [[]]
       )",
     },
     {
       // subset.