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