1use std::hash::Hash;
2use std::ops::{Index, Range};
3use std::time::Instant;
4
5use crate::algorithms::{diff_deadline, Capture, Compact, Replace};
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, deadline: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<'_, '_, Old, New, …> = Compact::new(d: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, deadline: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, old_range:0..old.len(), new, new_range: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: usize = opsimpl Iterator
82 .iter()
83 .map(|op: &DiffOp| {
84 if let DiffOp::Equal { len: usize, .. } = *op {
85 len
86 } else {
87 0
88 }
89 })
90 .sum::<usize>();
91 let len: usize = 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}
186