[clangd] Deduplicate refs from index for cross-file rename.

Summary:
If the index returns duplicated refs, it will trigger the assertion in
BuildRenameEdit (we expect the processing position is always larger the
the previous one, but it is not true if we have duplication), and also
breaks our heuristics.

This patch make the code robost enough to handle duplications, also
save some cost of redundnat llvm::sort.

Though clangd's index doesn't return duplications, our internal index
kythe will.

Reviewers: ilya-biryukov

Subscribers: MaskRay, jkorous, mgrang, arphaman, kadircet, usaxena95, cfe-commits

Tags: #clang

Differential Revision: https://reviews.llvm.org/D71300

3 files changed, 77 insertions, 14 deletions

diff --git a/clang-tools-extra/clangd/refactor/Rename.cpp b/clang-tools-extra/clangd/refactor/Rename.cpp
index 103f59bc307..8ca90afba69 100644
--- a/clang-tools-extra/clangd/refactor/Rename.cpp
+++ b/clang-tools-extra/clangd/refactor/Rename.cpp
@@ -319,7 +319,12 @@ findOccurrencesOutsideFile(const NamedDecl &RenameDecl,
                       RenameDecl.getQualifiedNameAsString()),
         llvm::inconvertibleErrorCode());
   }
-
+  // Sort and deduplicate the results, in case that index returns duplications.
+  for (auto &FileAndOccurrences : AffectedFiles) {
+    auto &Ranges = FileAndOccurrences.getValue();
+    llvm::sort(Ranges);
+    Ranges.erase(std::unique(Ranges.begin(), Ranges.end()), Ranges.end());
+  }
   return AffectedFiles;
 }
 
@@ -514,7 +519,11 @@ llvm::Expected<Edit> buildRenameEdit(llvm::StringRef AbsFilePath,
                                      llvm::StringRef InitialCode,
                                      std::vector<Range> Occurrences,
                                      llvm::StringRef NewName) {
-  llvm::sort(Occurrences);
+  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;
@@ -574,9 +583,9 @@ llvm::Optional<std::vector<Range>>
 adjustRenameRanges(llvm::StringRef DraftCode, llvm::StringRef Identifier,
                    std::vector<Range> Indexed, const LangOptions &LangOpts) {
   assert(!Indexed.empty());
+  assert(std::is_sorted(Indexed.begin(), Indexed.end()));
   std::vector<Range> Lexed =
       collectIdentifierRanges(Identifier, DraftCode, LangOpts);
-  llvm::sort(Indexed);
   llvm::sort(Lexed);
   return getMappedRanges(Indexed, Lexed);
 }
diff --git a/clang-tools-extra/clangd/refactor/Rename.h b/clang-tools-extra/clangd/refactor/Rename.h
index 68821fa8a78..3cd69d46888 100644
--- a/clang-tools-extra/clangd/refactor/Rename.h
+++ b/clang-tools-extra/clangd/refactor/Rename.h
@@ -51,6 +51,7 @@ llvm::Expected<FileEdits> rename(const RenameInputs &RInputs);
 /// 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,
@@ -65,6 +66,7 @@ llvm::Expected<Edit> buildRenameEdit(llvm::StringRef AbsFilePath,
 ///
 /// The API assumes that Indexed contains only named occurrences (each
 /// occurrence has the same length).
+/// REQUIRED: Indexed is sorted.
 llvm::Optional<std::vector<Range>>
 adjustRenameRanges(llvm::StringRef DraftCode, llvm::StringRef Identifier,
                    std::vector<Range> Indexed, const LangOptions &LangOpts);
diff --git a/clang-tools-extra/clangd/unittests/RenameTests.cpp b/clang-tools-extra/clangd/unittests/RenameTests.cpp
index fc2b6fe62cb..f253625ed03 100644
--- a/clang-tools-extra/clangd/unittests/RenameTests.cpp
+++ b/clang-tools-extra/clangd/unittests/RenameTests.cpp
@@ -30,6 +30,18 @@ using testing::IsEmpty;
 using testing::UnorderedElementsAre;
 using testing::UnorderedElementsAreArray;
 
+// Covnert a Range to a Ref.
+Ref refWithRange(const clangd::Range &Range, const std::string &URI) {
+  Ref Result;
+  Result.Kind = RefKind::Reference;
+  Result.Location.Start.setLine(Range.start.line);
+  Result.Location.Start.setColumn(Range.start.character);
+  Result.Location.End.setLine(Range.end.line);
+  Result.Location.End.setColumn(Range.end.character);
+  Result.Location.FileURI = URI.c_str();
+  return Result;
+}
+
 // Build a RefSlab from all marked ranges in the annotation. The ranges are
 // assumed to associate with the given SymbolName.
 std::unique_ptr<RefSlab> buildRefSlab(const Annotations &Code,
@@ -40,17 +52,9 @@ std::unique_ptr<RefSlab> buildRefSlab(const Annotations &Code,
   TU.HeaderCode = Code.code();
   auto Symbols = TU.headerSymbols();
   const auto &SymbolID = findSymbol(Symbols, SymbolName).ID;
-  for (const auto &Range : Code.ranges()) {
-    Ref R;
-    R.Kind = RefKind::Reference;
-    R.Location.Start.setLine(Range.start.line);
-    R.Location.Start.setColumn(Range.start.character);
-    R.Location.End.setLine(Range.end.line);
-    R.Location.End.setColumn(Range.end.character);
-    auto U = URI::create(Path).toString();
-    R.Location.FileURI = U.c_str();
-    Builder.insert(SymbolID, R);
-  }
+  std::string PathURI = URI::create(Path).toString();
+  for (const auto &Range : Code.ranges())
+    Builder.insert(SymbolID, refWithRange(Range, PathURI));
 
   return std::make_unique<RefSlab>(std::move(Builder).build());
 }
@@ -664,6 +668,54 @@ TEST(CrossFileRenameTests, DirtyBuffer) {
               testing::HasSubstr("too many occurrences"));
 }
 
+TEST(CrossFileRenameTests, DeduplicateRefsFromIndex) {
+  auto MainCode = Annotations("int [[^x]] = 2;");
+  auto MainFilePath = testPath("main.cc");
+  auto BarCode = Annotations("int [[x]];");
+  auto BarPath = testPath("bar.cc");
+  auto TU = TestTU::withCode(MainCode.code());
+  // Set a file "bar.cc" on disk.
+  TU.AdditionalFiles["bar.cc"] = BarCode.code();
+  auto AST = TU.build();
+  std::string BarPathURI = URI::create(BarPath).toString();
+  Ref XRefInBarCC = refWithRange(BarCode.range(), BarPathURI);
+  // The index will return duplicated refs, our code should be robost to handle
+  // it.
+  class DuplicatedXRefIndex : public SymbolIndex {
+  public:
+    DuplicatedXRefIndex(const Ref &ReturnedRef) : ReturnedRef(ReturnedRef) {}
+    bool refs(const RefsRequest &Req,
+              llvm::function_ref<void(const Ref &)> Callback) const override {
+      // Return two duplicated refs.
+      Callback(ReturnedRef);
+      Callback(ReturnedRef);
+      return false;
+    }
+
+    bool fuzzyFind(const FuzzyFindRequest &,
+                   llvm::function_ref<void(const Symbol &)>) const override {
+      return false;
+    }
+    void lookup(const LookupRequest &,
+                llvm::function_ref<void(const Symbol &)>) const override {}
+
+    void relations(const RelationsRequest &,
+                   llvm::function_ref<void(const SymbolID &, const Symbol &)>)
+        const override {}
+    size_t estimateMemoryUsage() const override { return 0; }
+    Ref ReturnedRef;
+  } DIndex(XRefInBarCC);
+  llvm::StringRef NewName = "newName";
+  auto Results = rename({MainCode.point(), NewName, AST, MainFilePath, &DIndex,
+                         /*CrossFile=*/true});
+  ASSERT_TRUE(bool(Results)) << Results.takeError();
+  EXPECT_THAT(
+      applyEdits(std::move(*Results)),
+      UnorderedElementsAre(
+          Pair(Eq(BarPath), Eq(expectedResult(BarCode, NewName))),
+          Pair(Eq(MainFilePath), Eq(expectedResult(MainCode, NewName)))));
+}
+
 TEST(CrossFileRenameTests, WithUpToDateIndex) {
   MockCompilationDatabase CDB;
   CDB.ExtraClangFlags = {"-xc++"};