diff 0.1.6

An LCS based slice and string diffing implementation.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

/// A fragment of a computed diff.
#[derive(Clone, Debug, PartialEq)]
pub enum Result<T> {
    Left(T),
    Both(T, T),
    Right(T)
}

/// Computes the diff between two slices.
pub fn slice<'a, T: PartialEq>(left: &'a [T],
                               right: &'a [T]) -> Vec<Result<&'a T>> {
    iter(left.iter(), right.iter())
}

/// Computes the diff between the lines of two strings.
pub fn lines<'a>(left: &'a str, right: &'a str) -> Vec<Result<&'a str>> {
    iter(left.lines(), right.lines())
}

/// Computes the diff between the chars of two strings.
pub fn chars<'a>(left: &'a str, right: &'a str) -> Vec<Result<char>> {
    iter(left.chars(), right.chars())
}

fn iter<'a, I, T>(left: I, right: I) -> Vec<Result<T>> where
    I: Clone + Iterator<Item = T> + DoubleEndedIterator, T: PartialEq
{
    let left_count = left.clone().count();
    let right_count = right.clone().count();

    let leading_equals = left.clone()
                             .zip(right.clone())
                             .take_while(|p| p.0 == p.1)
                             .count();
    let trailing_equals = left.clone()
                              .rev()
                              .zip(right.clone().rev())
                              .take(left_count - leading_equals)
                              .take_while(|p| p.0 == p.1)
                              .count();

    let left_diff_size = left_count - leading_equals - trailing_equals;
    let right_diff_size = right_count - leading_equals - trailing_equals;

    let table: Vec<Vec<u32>> = {
        let mut table = vec![vec![0; right_diff_size + 1]; left_diff_size + 1];
        let left_skip = left.clone().skip(leading_equals).take(left_diff_size);
        let right_skip = right.clone()
                              .skip(leading_equals)
                              .take(right_diff_size);

        for (i, l) in left_skip.clone().enumerate() {
            for (j, r) in right_skip.clone().enumerate() {
                table[i+1][j+1] = if l == r {
                    table[i][j] + 1
                } else {
                    std::cmp::max(table[i][j+1], table[i+1][j])
                };
            }
        }

        table
    };

    let diff = {
        let mut diff = Vec::with_capacity(left_diff_size + right_diff_size);
        let mut i = left_diff_size;
        let mut j = right_diff_size;
        let mut li = left.clone().rev().skip(trailing_equals);
        let mut ri = right.clone().rev().skip(trailing_equals);

        loop {
            if i > 0 && (j == 0 || table[i][j] == table[i-1][j]) {
                i -= 1;
                diff.push(Result::Left(li.next().unwrap()));
            } else if j > 0 && (i == 0 || table[i][j] == table[i][j-1]) {
                j -= 1;
                diff.push(Result::Right(ri.next().unwrap()));
            } else if i > 0 && j > 0 {
                i -= 1;
                j -= 1;
                diff.push(Result::Both(li.next().unwrap(), ri.next().unwrap()));
            } else {
                break
            }
        }

        diff
    };

    let diff_size = leading_equals + diff.len() + trailing_equals;
    let mut total_diff = Vec::with_capacity(diff_size);

    total_diff.extend(left.clone()
                          .zip(right.clone())
                          .take(leading_equals)
                          .map(|(l, r)| Result::Both(l, r)));
    total_diff.extend(diff.into_iter().rev());
    total_diff.extend(left.rev()
                          .zip(right.rev())
                          .take(trailing_equals)
                          .map(|(l, r)| Result::Both(l, r)));

    total_diff
}