1/// A fragment of a computed diff.
2#[derive(Clone, Debug, PartialEq)]
3pub enum Result<T> {
4 /// An element that only exists in the left input.
5 Left(T),
6 /// Elements that exist in both inputs.
7 Both(T, T),
8 /// An element that only exists in the right input.
9 Right(T),
10}
11
12/// Computes the diff between two slices.
13pub fn slice<'a, T: PartialEq>(left: &'a [T], right: &'a [T]) -> Vec<Result<&'a T>> {
14 do_diff(left, right, |t: &T| t)
15}
16
17/// Computes the diff between the lines of two strings.
18pub fn lines<'a>(left: &'a str, right: &'a str) -> Vec<Result<&'a str>> {
19 let mut diff: Vec> = do_diff(
20 &left.lines().collect::<Vec<_>>(),
21 &right.lines().collect::<Vec<_>>(),
22 |str: &&str| *str,
23 );
24 // str::lines() does not yield an empty str at the end if the str ends with
25 // '\n'. We handle this special case by inserting one last diff item,
26 // depending on whether the left string ends with '\n', or the right one,
27 // or both.
28 match (
29 left.as_bytes().last().cloned(),
30 right.as_bytes().last().cloned(),
31 ) {
32 (Some(b'\n'), Some(b'\n')) => {
33 diff.push(Result::Both(&left[left.len()..], &right[right.len()..]))
34 }
35 (Some(b'\n'), _) => diff.push(Result::Left(&left[left.len()..])),
36 (_, Some(b'\n')) => diff.push(Result::Right(&right[right.len()..])),
37 _ => {}
38 }
39 diff
40}
41
42/// Computes the diff between the chars of two strings.
43pub fn chars<'a>(left: &'a str, right: &'a str) -> Vec<Result<char>> {
44 do_diff(
45 &left.chars().collect::<Vec<_>>(),
46 &right.chars().collect::<Vec<_>>(),
47 |char: &char| *char,
48 )
49}
50
51fn do_diff<'a, T, F, U>(left: &'a [T], right: &'a [T], mapper: F) -> Vec<Result<U>>
52where
53 T: PartialEq,
54 F: Fn(&'a T) -> U,
55{
56 let leading_equals = left
57 .iter()
58 .zip(right.iter())
59 .take_while(|(l, r)| l == r)
60 .count();
61 let trailing_equals = left[leading_equals..]
62 .iter()
63 .rev()
64 .zip(right[leading_equals..].iter().rev())
65 .take_while(|(l, r)| l == r)
66 .count();
67
68 let table: Vec2<u32> = {
69 let left_diff_size = left.len() - leading_equals - trailing_equals;
70 let right_diff_size = right.len() - leading_equals - trailing_equals;
71
72 let mut table = Vec2::new(0, [left_diff_size + 1, right_diff_size + 1]);
73
74 let left_skip = &left[leading_equals..left.len() - trailing_equals];
75 let right_skip = &right[leading_equals..right.len() - trailing_equals];
76
77 for (i, l) in left_skip.iter().enumerate() {
78 for (j, r) in right_skip.iter().enumerate() {
79 table.set(
80 [i + 1, j + 1],
81 if l == r {
82 table.get([i, j]) + 1
83 } else {
84 *table.get([i, j + 1]).max(table.get([i + 1, j]))
85 },
86 );
87 }
88 }
89
90 table
91 };
92
93 let mut diff = Vec::with_capacity(left.len().max(right.len()));
94
95 diff.extend(
96 left[..leading_equals]
97 .iter()
98 .zip(&right[..leading_equals])
99 .map(|(l, r)| Result::Both(mapper(l), mapper(r))),
100 );
101
102 {
103 let start = diff.len();
104 let mut i = table.len[0] - 1;
105 let mut j = table.len[1] - 1;
106 let left = &left[leading_equals..];
107 let right = &right[leading_equals..];
108
109 loop {
110 if j > 0 && (i == 0 || table.get([i, j]) == table.get([i, j - 1])) {
111 j -= 1;
112 diff.push(Result::Right(mapper(&right[j])));
113 } else if i > 0 && (j == 0 || table.get([i, j]) == table.get([i - 1, j])) {
114 i -= 1;
115 diff.push(Result::Left(mapper(&left[i])));
116 } else if i > 0 && j > 0 {
117 i -= 1;
118 j -= 1;
119 diff.push(Result::Both(mapper(&left[i]), mapper(&right[j])));
120 } else {
121 break;
122 }
123 }
124 diff[start..].reverse();
125 }
126
127 diff.extend(
128 left[left.len() - trailing_equals..]
129 .iter()
130 .zip(&right[right.len() - trailing_equals..])
131 .map(|(l, r)| Result::Both(mapper(l), mapper(r))),
132 );
133
134 diff
135}
136
137struct Vec2<T> {
138 len: [usize; 2],
139 data: Vec<T>,
140}
141
142impl<T> Vec2<T> {
143 #[inline]
144 fn new(value: T, len: [usize; 2]) -> Self
145 where
146 T: Clone,
147 {
148 Vec2 {
149 len,
150 data: vec![value; len[0] * len[1]],
151 }
152 }
153
154 #[inline]
155 fn get(&self, index: [usize; 2]) -> &T {
156 debug_assert!(index[0] < self.len[0]);
157 debug_assert!(index[1] < self.len[1]);
158 &self.data[index[0] * self.len[1] + index[1]]
159 }
160
161 #[inline]
162 fn set(&mut self, index: [usize; 2], value: T) {
163 debug_assert!(index[0] < self.len[0]);
164 debug_assert!(index[1] < self.len[1]);
165 self.data[index[0] * self.len[1] + index[1]] = value;
166 }
167}
168