similar/
common.rs

Help
1use std::hash::Hash;
2use std::ops::{Index, Range};
3
4use crate::algorithms::{diff_deadline, Capture, Compact, Replace};
5use crate::deadline_support::Instant;
6use crate::{Algorithm, DiffOp};
7
8/// Creates a diff between old and new with the given algorithm capturing the ops.
9///
10/// This is like [`diff`](crate::algorithms::diff) but instead of using an
11/// arbitrary hook this will always use [`Compact`] + [`Replace`] + [`Capture`]
12/// and return the captured [`DiffOp`]s.
13pub fn capture_diff<Old, New>(
14    alg: Algorithm,
15    old: &Old,
16    old_range: Range<usize>,
17    new: &New,
18    new_range: Range<usize>,
19) -> Vec<DiffOp>
20where
21    Old: Index<usize> + ?Sized,
22    New: Index<usize> + ?Sized,
23    Old::Output: Hash + Eq + Ord,
24    New::Output: PartialEq<Old::Output> + Hash + Eq + Ord,
25{
26    capture_diff_deadline(alg, old, old_range, new, new_range, None)
27}
28
29/// Creates a diff between old and new with the given algorithm capturing the ops.
30///
31/// Works like [`capture_diff`] but with an optional deadline.
32pub fn capture_diff_deadline<Old, New>(
33    alg: Algorithm,
34    old: &Old,
35    old_range: Range<usize>,
36    new: &New,
37    new_range: Range<usize>,
38    deadline: Option<Instant>,
39) -> Vec<DiffOp>
40where
41    Old: Index<usize> + ?Sized,
42    New: Index<usize> + ?Sized,
43    Old::Output: Hash + Eq + Ord,
44    New::Output: PartialEq<Old::Output> + Hash + Eq + Ord,
45{
46    let mut d = Compact::new(Replace::new(Capture::new()), old, new);
47    diff_deadline(alg, &mut d, old, old_range, new, new_range, deadline).unwrap();
48    d.into_inner().into_inner().into_ops()
49}
50
51/// Creates a diff between old and new with the given algorithm capturing the ops.
52pub fn capture_diff_slices<T>(alg: Algorithm, old: &[T], new: &[T]) -> Vec<DiffOp>
53where
54    T: Eq + Hash + Ord,
55{
56    capture_diff_slices_deadline(alg, old, new, None)
57}
58
59/// Creates a diff between old and new with the given algorithm capturing the ops.
60///
61/// Works like [`capture_diff_slices`] but with an optional deadline.
62pub fn capture_diff_slices_deadline<T>(
63    alg: Algorithm,
64    old: &[T],
65    new: &[T],
66    deadline: Option<Instant>,
67) -> Vec<DiffOp>
68where
69    T: Eq + Hash + Ord,
70{
71    capture_diff_deadline(alg, old, 0..old.len(), new, 0..new.len(), deadline)
72}
73
74/// Return a measure of similarity in the range `0..=1`.
75///
76/// A ratio of `1.0` means the two sequences are a complete match, a
77/// ratio of `0.0` would indicate completely distinct sequences.  The input
78/// is the sequence of diff operations and the length of the old and new
79/// sequence.
80pub fn get_diff_ratio(ops: &[DiffOp], old_len: usize, new_len: usize) -> f32 {
81    let matches = ops
82        .iter()
83        .map(|op| {
84            if let DiffOp::Equal { len, .. } = *op {
85                len
86            } else {
87                0
88            }
89        })
90        .sum::<usize>();
91    let len = old_len + new_len;
92    if len == 0 {
93        1.0
94    } else {
95        2.0 * matches as f32 / len as f32
96    }
97}
98
99/// Isolate change clusters by eliminating ranges with no changes.
100///
101/// This will leave holes behind in long periods of equal ranges so that
102/// you can build things like unified diffs.
103pub fn group_diff_ops(mut ops: Vec<DiffOp>, n: usize) -> Vec<Vec<DiffOp>> {
104    if ops.is_empty() {
105        return vec![];
106    }
107
108    let mut pending_group = Vec::new();
109    let mut rv = Vec::new();
110
111    if let Some(DiffOp::Equal {
112        old_index,
113        new_index,
114        len,
115    }) = ops.first_mut()
116    {
117        let offset = (*len).saturating_sub(n);
118        *old_index += offset;
119        *new_index += offset;
120        *len -= offset;
121    }
122
123    if let Some(DiffOp::Equal { len, .. }) = ops.last_mut() {
124        *len -= (*len).saturating_sub(n);
125    }
126
127    for op in ops.into_iter() {
128        if let DiffOp::Equal {
129            old_index,
130            new_index,
131            len,
132        } = op
133        {
134            // End the current group and start a new one whenever
135            // there is a large range with no changes.
136            if len > n * 2 {
137                pending_group.push(DiffOp::Equal {
138                    old_index,
139                    new_index,
140                    len: n,
141                });
142                rv.push(pending_group);
143                let offset = len.saturating_sub(n);
144                pending_group = vec![DiffOp::Equal {
145                    old_index: old_index + offset,
146                    new_index: new_index + offset,
147                    len: len - offset,
148                }];
149                continue;
150            }
151        }
152        pending_group.push(op);
153    }
154
155    match &pending_group[..] {
156        &[] | &[DiffOp::Equal { .. }] => {}
157        _ => rv.push(pending_group),
158    }
159
160    rv
161}
162
163#[test]
164fn test_non_string_iter_change() {
165    use crate::ChangeTag;
166
167    let old = vec![1, 2, 3];
168    let new = vec![1, 2, 4];
169    let ops = capture_diff_slices(Algorithm::Myers, &old, &new);
170    let changes: Vec<_> = ops
171        .iter()
172        .flat_map(|x| x.iter_changes(&old, &new))
173        .map(|x| (x.tag(), x.value()))
174        .collect();
175
176    assert_eq!(
177        changes,
178        vec![
179            (ChangeTag::Equal, 1),
180            (ChangeTag::Equal, 2),
181            (ChangeTag::Delete, 3),
182            (ChangeTag::Insert, 4),
183        ]
184    );
185}
similar/common.rs

similar/
common.rs
