git.iko.soy/helix
on bbbbfa9 help sign in
helix/helix-core/src/diff.rs
70 lines 2.6 kB history raw
1use ropey::Rope;
3use crate::{Change, Transaction};
5/// Compares `old` and `new` to generate a [`Transaction`] describing
6/// the steps required to get from `old` to `new`.
7pub fn compare_ropes(old: &Rope, new: &Rope) -> Transaction {
8 // `similar` only works on contiguous data, so a `Rope` has
9 // to be temporarily converted into a `String`.
10 let old_converted = old.to_string();
11 let new_converted = new.to_string();
13 // A timeout is set so after 1 seconds, the algorithm will start
14 // approximating. This is especially important for big `Rope`s or
15 // `Rope`s that are extremely dissimilar to each other.
16 //
17 // Note: Ignore the clippy warning, as the trait bounds of
18 // `Transaction::change()` require an iterator implementing
19 // `ExactIterator`.
20 let mut config = similar::TextDiff::configure();
21 config.timeout(std::time::Duration::from_secs(1));
23 let diff = config.diff_chars(&old_converted, &new_converted);
25 // The current position of the change needs to be tracked to
26 // construct the `Change`s.
27 let mut pos = 0;
28 let changes: Vec<Change> = diff
29 .ops()
30 .iter()
31 .map(|op| op.as_tag_tuple())
32 .filter_map(|(tag, old_range, new_range)| {
33 // `old_pos..pos` is equivalent to `start..end` for where
34 // the change should be applied.
35 let old_pos = pos;
36 pos += old_range.end - old_range.start;
38 match tag {
39 // Semantically, inserts and replacements are the same thing.
40 similar::DiffTag::Insert | similar::DiffTag::Replace => {
41 // This is the text from the `new` rope that should be
42 // inserted into `old`.
43 let text: &str = {
44 let start = new.char_to_byte(new_range.start);
45 let end = new.char_to_byte(new_range.end);
46 &new_converted[start..end]
47 };
48 Some((old_pos, pos, Some(text.into())))
49 }
50 similar::DiffTag::Delete => Some((old_pos, pos, None)),
51 similar::DiffTag::Equal => None,
52 }
53 })
54 .collect();
55 Transaction::change(old, changes.into_iter())
58#[cfg(test)]
59mod tests {
60 use super::*;
62 quickcheck::quickcheck! {
63 fn test_compare_ropes(a: String, b: String) -> bool {
64 let mut old = Rope::from(a);
65 let new = Rope::from(b);
66 compare_ropes(&old, &new).apply(&mut old);
67 old.to_string() == new.to_string()
68 }
69 }