Try similar librarytry_similar_lib

3 files changed, 39 insertions, 12 deletions

diff --git a/Cargo.lock b/Cargo.lock
index e93ea5091..4eb8484f5 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -258,6 +258,7 @@ dependencies = [
  "rayon",
  "regex",
  "rustc-hash",
+ "similar",
  "strsim",
  "strum",
  "tree-sitter",
@@ -761,6 +762,12 @@ dependencies = [
 ]
 
 [[package]]
+name = "similar"
+version = "2.2.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "420acb44afdae038210c99e69aae24109f32f15500aa708e81d46c9f29d55fcf"
+
+[[package]]
 name = "smallvec"
 version = "1.10.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/Cargo.toml b/Cargo.toml
index 9d7ce38a2..b3d1b9883 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -61,6 +61,7 @@ glob = "0.3.1"
 strum = { version = "0.25", features = ["derive"] }
 # hashbrown 0.13 requires rust 1.61
 hashbrown = "0.12.3"
+similar = "2.2.1"
 
 [dev-dependencies]
 # assert_cmd 2.0.6 requires rust 1.60
diff --git a/src/diff/myers_diff.rs b/src/diff/myers_diff.rs
index 35ad26bcb..7acdc54c6 100644
--- a/src/diff/myers_diff.rs
+++ b/src/diff/myers_diff.rs
@@ -14,19 +14,38 @@ pub enum DiffResult<T> {
 
 /// Compute a linear diff between `lhs` and `rhs`. This is the
 /// traditional Myer's diff algorithm.
-pub fn slice<'a, T: PartialEq + Clone>(lhs: &'a [T], rhs: &'a [T]) -> Vec<DiffResult<&'a T>> {
-    wu_diff::diff(lhs, rhs)
-        .into_iter()
-        .map(|result| match result {
-            wu_diff::DiffResult::Removed(r) => DiffResult::Left(&lhs[r.old_index.unwrap()]),
-            wu_diff::DiffResult::Common(c) => {
-                let lhs_id = c.old_index.unwrap();
-                let rhs_id = c.new_index.unwrap();
-                DiffResult::Both(&lhs[lhs_id], &rhs[rhs_id])
+pub fn slice<'a, T: PartialEq + Clone + Hash + Ord>(
+    lhs: &'a [T],
+    rhs: &'a [T],
+) -> Vec<DiffResult<&'a T>> {
+    use similar::{capture_diff_slices, Algorithm};
+
+    let mut res = vec![];
+    for result in capture_diff_slices(Algorithm::Patience, lhs, rhs) {
+        match result {
+            similar::DiffOp::Equal {
+                old_index,
+                new_index,
+                ..
+            } => res.push(DiffResult::Both(&lhs[old_index], &rhs[new_index])),
+            similar::DiffOp::Delete { old_index, .. } => {
+                res.push(DiffResult::Left(&lhs[old_index]))
             }
-            wu_diff::DiffResult::Added(a) => DiffResult::Right(&rhs[a.new_index.unwrap()]),
-        })
-        .collect::<Vec<_>>()
+            similar::DiffOp::Insert { new_index, .. } => {
+                res.push(DiffResult::Right(&rhs[new_index]))
+            }
+            similar::DiffOp::Replace {
+                old_index,
+                new_index,
+                ..
+            } => {
+                res.push(DiffResult::Left(&lhs[old_index]));
+                res.push(DiffResult::Right(&rhs[new_index]));
+            }
+        }
+    }
+
+    res
 }
 
 /// Compute a linear diff between `lhs` and `rhs`, but use hashed