diff/
lib.rs

Help
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)
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 = do_diff(
20        &left.lines().collect::<Vec<_>>(),
21        &right.lines().collect::<Vec<_>>(),
22        |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,
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}
diff/lib.rs

diff/
lib.rs
