```  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);

.zip(right.clone())
.take_while(|p| p.0 == p.1)
.count();
let trailing_equals = left.clone()
.rev()
.zip(right.clone().rev())
.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];

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())