2 files changed, 71 insertions, 0 deletions
diff --git a/helix-core/src/diff.rs b/helix-core/src/diff.rs
new file mode 100644
index 00000000..9c1fc999
--- /dev/null
+++ b/helix-core/src/diff.rs
@@ -0,0 +1,70 @@
+use ropey::Rope;
+
+use crate::{Change, Transaction};
+
+/// Compares `old` and `new` to generate a [`Transaction`] describing
+/// the steps required to get from `old` to `new`.
+pub fn compare_ropes(old: &Rope, new: &Rope) -> Transaction {
+    // `similar` only works on contiguous data, so a `Rope` has
+    // to be temporarily converted into a `String`.
+    let old_converted = old.to_string();
+    let new_converted = new.to_string();
+
+    // A timeout is set so after 1 seconds, the algorithm will start
+    // approximating. This is especially important for big `Rope`s or
+    // `Rope`s that are extremely dissimilar to each other.
+    //
+    // Note: Ignore the clippy warning, as the trait bounds of
+    // `Transaction::change()` require an iterator implementing
+    // `ExactIterator`.
+    let mut config = similar::TextDiff::configure();
+    config.timeout(std::time::Duration::from_secs(1));
+
+    let diff = config.diff_chars(&old_converted, &new_converted);
+
+    // The current position of the change needs to be tracked to
+    // construct the `Change`s.
+    let mut pos = 0;
+    let changes: Vec<Change> = diff
+        .ops()
+        .iter()
+        .map(|op| op.as_tag_tuple())
+        .filter_map(|(tag, old_range, new_range)| {
+            // `old_pos..pos` is equivalent to `start..end` for where
+            // the change should be applied.
+            let old_pos = pos;
+            pos += old_range.end - old_range.start;
+
+            match tag {
+                // Semantically, inserts and replacements are the same thing.
+                similar::DiffTag::Insert | similar::DiffTag::Replace => {
+                    // This is the text from the `new` rope that should be
+                    // inserted into `old`.
+                    let text: &str = {
+                        let start = new.char_to_byte(new_range.start);
+                        let end = new.char_to_byte(new_range.end);
+                        &new_converted[start..end]
+                    };
+                    Some((old_pos, pos, Some(text.into())))
+                }
+                similar::DiffTag::Delete => Some((old_pos, pos, None)),
+                similar::DiffTag::Equal => None,
+            }
+        })
+        .collect();
+    Transaction::change(old, changes.into_iter())
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    quickcheck::quickcheck! {
+        fn test_compare_ropes(a: String, b: String) -> bool {
+            let mut old = Rope::from(a);
+            let new = Rope::from(b);
+            compare_ropes(&old, &new).apply(&mut old);
+            old.to_string() == new.to_string()
+        }
+    }
+}
diff --git a/helix-core/src/lib.rs b/helix-core/src/lib.rs
index dfbbd748..c2bb8c55 100644
--- a/helix-core/src/lib.rs
+++ b/helix-core/src/lib.rs
@@ -2,6 +2,7 @@ pub mod auto_pairs;
 pub mod chars;
 pub mod comment;
 pub mod diagnostic;
+pub mod diff;
 pub mod graphemes;
 pub mod history;
 pub mod indent;