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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

use std::cmp;

/// 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>> {
    let mut diff = iter(left.lines(), right.lines());
    // str::lines() does not yield an empty str at the end if the str ends with
    // '\n'. We handle this special case by inserting one last diff item,
    // depending on whether the left string ends with '\n', or the right one,
    // or both.
    match (
        left.as_bytes().last().cloned(),
        right.as_bytes().last().cloned(),
    ) {
        (Some(b'\n'), Some(b'\n')) => {
            diff.push(Result::Both(&left[left.len()..], &right[right.len()..]))
        }
        (Some(b'\n'), _) => diff.push(Result::Left(&left[left.len()..])),
        (_, Some(b'\n')) => diff.push(Result::Right(&right[right.len()..])),
        _ => {}
    }
    diff
}

/// 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<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 min_count = cmp::min(left_count, right_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(min_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 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 || table[i][j] == table[i - 1][j]) {
                i -= 1;
                diff.push(Result::Left(li.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.skip(leading_equals + left_diff_size)
            .zip(right.skip(leading_equals + right_diff_size))
            .map(|(l, r)| Result::Both(l, r)),
    );

    total_diff
}