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

[hokein]

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.

[merge_guards_bot]

Build result: pass - 60688 tests passed, 0 failed and 726 were skipped.

Log files: console-log.txt, CMakeCache.txt

[ilya-biryukov]

The fix itself LGTM. Just a few NITs and this is good to go.

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

34

• Returning both storage and Ref is quite a complicated interface. Could we rely on the clients to pass strings with URIs instead? It's not a lot of code to create URIs.
• I think the function name might end up a little confusing when reading the code using it (it certainly did for me). Could we rename it to refWithRange? That seems to describe what this function is doing more accurately.

[hokein]

address review comment -- simplify the unittest code.

[hokein]

thanks for the fast review.

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

34

agree, this is a good point. thanks.

[merge_guards_bot]

Build result: pass - 60688 tests passed, 0 failed and 726 were skipped.

Log files: console-log.txt, CMakeCache.txt

[ilya-biryukov]

LGTM, thanks!

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

 /// 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.
+/// 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);
 
 /// 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.
 ///
 /// 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);
 
 /// Calculates the lexed occurrences that the given indexed occurrences map to.
 /// Returns None if we don't find a mapping.
 ///
 /// Exposed for testing only.

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

return llvm::make_error<llvm::StringError>(
                       MaxLimitFiles),
         llvm::inconvertibleErrorCode());
   if (HasMore) {
     return llvm::make_error<llvm::StringError>(
         llvm::formatv("The symbol {0} has too many occurrences",
                       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;
 }
 
 // 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.
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::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;
 
   auto Offset = [&](const Position &P) -> llvm::Expected<size_t> {
     assert(LastPos <= P && "malformed input");
     Position Shifted = {
         P.line - LastPos.line,

 //      (b) index returns non-candidate results, we attempt to map the indexed
 //          ranges onto candidates in a plausible way (e.g. guess that lines
 //          were inserted). If such a "near miss" is found, the rename is still
 //          possible
 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);
 }
 
 llvm::Optional<std::vector<Range>> getMappedRanges(ArrayRef<Range> Indexed,
                                                    ArrayRef<Range> Lexed) {
   assert(!Indexed.empty());
   assert(std::is_sorted(Indexed.begin(), Indexed.end()));

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

 namespace {
 
 using testing::Eq;
 using testing::Pair;
 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,
                                       llvm::StringRef SymbolName,
                                       llvm::StringRef Path) {
   RefSlab::Builder Builder;
   TestTU TU;
   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());
 }
 
 std::vector<
     std::pair</*FilePath*/ std::string, /*CodeAfterRename*/ std::string>>
 applyEdits(FileEdits FE) {
   std::vector<std::pair<std::string, std::string>> Results;
TEST(CrossFileRenameTests, DirtyBuffer) {
   } PIndex;
   Results = rename({MainCode.point(), NewName, AST, MainFilePath, &PIndex,
                     /*CrossFile=*/true, GetDirtyBuffer});
   EXPECT_FALSE(Results);
   EXPECT_THAT(llvm::toString(Results.takeError()),
               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++"};
   class IgnoreDiagnostics : public DiagnosticsConsumer {
   void onDiagnosticsReady(PathRef File,
                           std::vector<Diag> Diagnostics) override {}
   } DiagConsumer;
   // rename is runnning on the "^" point in FooH, and "[[]]" ranges are the