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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
// Copyright 2018-2019 Joe Neeman.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.
//
// See the LICENSE-APACHE or LICENSE-MIT files at the top-level directory
// of this distribution.

#[cfg(test)]
#[macro_use]
extern crate proptest;

use std::collections::hash_map::Entry;
use std::collections::HashMap;
use std::hash::{Hash, Hasher};

mod lis;

#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
pub enum LineDiff {
    /// This line was introduced in the second file, and the `usize` is the line number in the
    /// second file.
    New(usize),
    /// This line was in the first file, but got deleted.
    Delete(usize),
    /// This line was present in both files; the first `usize` is the line number in the first
    /// file, and the second is the line number in the second file.
    Keep(usize, usize),
}

// This is a little trick for associating an element with its line number in a file. The point is
// that our implementation of Hash and Eq will ignore the index, so we can put `WithIndex` in
// hash maps and the index will just be transparently carried along.
#[derive(Eq, PartialOrd)]
struct WithIndex<T> {
    idx: usize,
    elem: T,
}

impl<T: PartialEq> PartialEq for WithIndex<T> {
    fn eq(&self, other: &WithIndex<T>) -> bool {
        self.elem.eq(&other.elem)
    }
}

impl<T: Hash> Hash for WithIndex<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.elem.hash(state);
    }
}

// Returns a map pointing from lines to the number of times they appeared in the file. Each line is
// also associated with the index where it first appeared.
fn line_counts<T: Hash + Eq>(lines: &[T]) -> HashMap<WithIndex<&T>, usize> {
    let mut line_counts = HashMap::new();

    for (line_idx, line) in lines.iter().enumerate() {
        let elem = WithIndex {
            elem: line,
            idx: line_idx,
        };
        *line_counts.entry(elem).or_insert(0) += 1;
    }
    line_counts
}

// The returned value `ret` is the largest number such that the first `ret` elements of `a` are the
// same as the first `ret` elements of `b`.
fn prefix_len<T: Eq>(a: &[T], b: &[T]) -> usize {
    a.iter().zip(b.iter()).take_while(|(x, y)| x == y).count()
}

// The returned value `ret` is the largest number such that the last `ret` elements of `a` are the
// same as the last `ret` elements of `b`.
fn suffix_len<T: Eq>(a: &[T], b: &[T]) -> usize {
    a.iter()
        .rev()
        .zip(b.iter().rev())
        .take_while(|(x, y)| x == y)
        .count()
}

// Returns the tuple (pref_len, a_mid, b_mid, suff_len), where `pref_len` is the length of the
// common prefix of `a` and `b`, `suff_len` is the length of the common suffix of `a` and `b`, and
// `a_mid` and `b_mid` are the parts of `a` and `b` that are left after the prefixes and suffixes
// are removed.
fn match_ends<'a, T: Eq>(a: &'a [T], b: &'a [T]) -> (usize, &'a [T], &'a [T], usize) {
    let pref_len = prefix_len(a, b);
    let suff_len = suffix_len(&a[pref_len..], &b[pref_len..]);
    let a_mid = &a[pref_len..(a.len() - suff_len)];
    let b_mid = &b[pref_len..(b.len() - suff_len)];
    (pref_len, a_mid, b_mid, suff_len)
}

// This function calculates an extremely simple kind of diff: find the longest common prefix and
// suffix of the two files. Everything that isn't part of the prefix and suffix gets marked as
// changed.
//
// We also support adding an offset to the line numbers of the two files, since they might actually
// refer just to smaller parts of larger files.
fn diff_ends<T: Eq>(a: &[T], a_offset: usize, b: &[T], b_offset: usize, diff: &mut Vec<LineDiff>) {
    let (pref_len, a_mid, b_mid, suff_len) = match_ends(a, b);
    for i in 0..pref_len {
        diff.push(LineDiff::Keep(a_offset + i, b_offset + i));
    }
    for i in 0..a_mid.len() {
        diff.push(LineDiff::Delete(a_offset + pref_len + i));
    }
    for i in 0..b_mid.len() {
        diff.push(LineDiff::New(b_offset + pref_len + i));
    }
    for i in 0..suff_len {
        diff.push(LineDiff::Keep(
            a_offset + pref_len + a_mid.len() + i,
            b_offset + pref_len + b_mid.len() + i,
        ));
    }
}

pub fn diff<T: Hash + Eq>(a: &[T], b: &[T]) -> Vec<LineDiff> {
    let (pref_len, a_mid, b_mid, suff_len) = match_ends(a, b);
    let a_line_counts = line_counts(a_mid);
    let mut b_line_counts = line_counts(b_mid);
    let a_unique = a_line_counts
        .into_iter()
        .filter(|(_, count)| *count == 1)
        .map(|(line, _)| line);

    // `both_unique` is a Vec of (usize, usize) pairs corresponding to lines that are unique in
    // both files. The first usize is the index *in file b* and the second is the index in file a,
    // and `both_unique` will be sorted according to the index in file a. The order of the indices
    // seems backwards, but the point is that we'll look for a longest increasing subsequence and
    // we want "increasing" here to mean according to appearance in file b.
    let mut both_unique = a_unique
        .filter_map(|a_line| {
            // TODO: This is a bit awkward, but it can get better if HashMap::get_key_value is
            // stabilized.
            let a_idx = a_line.idx;
            if let Entry::Occupied(entry) = b_line_counts.entry(a_line) {
                if entry.get() == &1 {
                    return Some((entry.key().idx, a_idx));
                }
            }
            None
        })
        .collect::<Vec<(usize, usize)>>();
    both_unique.sort_unstable_by_key(|(_b_idx, a_idx)| *a_idx);

    let mut ret = Vec::with_capacity(a.len().max(b.len()));
    for i in 0..pref_len {
        ret.push(LineDiff::Keep(i, i));
    }

    let lis = lis::longest_increasing_subsequence(&both_unique);
    let mut prev_b_idx = 0;
    let mut prev_a_idx = 0;
    for i in lis {
        let (next_b_idx, next_a_idx) = both_unique[i];
        let a_chunk = &a_mid[prev_a_idx..next_a_idx];
        let b_chunk = &b_mid[prev_b_idx..next_b_idx];
        diff_ends(
            a_chunk,
            pref_len + prev_a_idx,
            b_chunk,
            pref_len + prev_b_idx,
            &mut ret,
        );
        prev_b_idx = next_b_idx;
        prev_a_idx = next_a_idx;
    }

    let a_chunk = &a_mid[prev_a_idx..];
    let b_chunk = &b_mid[prev_b_idx..];
    diff_ends(
        a_chunk,
        pref_len + prev_a_idx,
        b_chunk,
        pref_len + prev_b_idx,
        &mut ret,
    );

    for i in 0..suff_len {
        ret.push(LineDiff::Keep(
            a.len() - suff_len + i,
            b.len() - suff_len + i,
        ));
    }

    ret
}

#[cfg(test)]
mod tests {
    use proptest::prelude::*;
    use std::fmt::Debug;

    use super::LineDiff::*;
    use super::*;

    macro_rules! test_diff_ends {
        ($name:ident, $a:expr, $b:expr, $expected:expr) => {
            #[test]
            fn $name() {
                let a: &[_] = &$a[..];
                let b: &[_] = &$b[..];
                let expected: &[_] = &$expected[..];
                let mut diff = Vec::new();
                diff_ends(a, 0, b, 0, &mut diff);
                assert_eq!(diff.as_slice(), expected);
            }
        };
    }

    test_diff_ends!(
        diff_ends_all,
        [1, 2, 3],
        [1, 2, 3],
        [Keep(0, 0), Keep(1, 1), Keep(2, 2),]
    );
    test_diff_ends!(
        diff_ends_shorter_first,
        [1, 1],
        [1, 1, 1],
        [Keep(0, 0), Keep(1, 1), New(2),]
    );
    test_diff_ends!(
        diff_ends_longer_first,
        [1, 1, 1],
        [1, 1],
        [Keep(0, 0), Keep(1, 1), Delete(2),]
    );

    // A diff between two files is valid if and only if
    // - every input index appears exactly once in the diff, in increasing order
    // - every output index appears exactly once in the diff, in increasing order
    // - for every Keep line in the diff, the input and output lines are the same.
    fn assert_valid<T: Debug + Eq>(a: &[T], b: &[T], diff: &[LineDiff]) {
        let input_indices = diff
            .iter()
            .filter_map(|line| match *line {
                New(_) => None,
                Keep(i, _) => Some(i),
                Delete(i) => Some(i),
            })
            .collect::<Vec<_>>();
        assert_eq!(input_indices, (0..a.len()).into_iter().collect::<Vec<_>>());

        let output_indices = diff
            .iter()
            .filter_map(|line| match *line {
                New(i) => Some(i),
                Keep(_, i) => Some(i),
                Delete(_) => None,
            })
            .collect::<Vec<_>>();
        assert_eq!(output_indices, (0..b.len()).into_iter().collect::<Vec<_>>());

        for line in diff {
            if let &Keep(i, j) = line {
                assert_eq!(a[i], b[j]);
            }
        }
    }

    // We generate files by mostly generating common numbers (up to 10), and occasionally
    // rare numbers (up to 1000). The common numbers are to make diff's job harder, and the rare
    // numbers are to ensure that there are some unique lines.
    fn file() -> BoxedStrategy<Vec<i32>> {
        prop::collection::vec(
            prop::strategy::Union::new_weighted(vec![(10, 0..10), (1, 0..1000)]),
            1..100,
        )
        .boxed()
    }

    // Generates two files for diffing by first generating one, and then making another by changing
    // the first one a bit.
    fn two_files() -> BoxedStrategy<(Vec<i32>, Vec<i32>)> {
        file()
            .prop_perturb(|f, mut rng| {
                let mut g = f.clone();
                // Make between 0 and 19 random changes.
                for _ in 0..rng.gen_range(0, 20) {
                    let g_len = g.len();
                    match rng.choose(&[1, 2, 3]).unwrap() {
                        1 => {
                            // delete a line
                            if !g.is_empty() {
                                g.remove(rng.gen_range(0, g_len));
                            }
                        }
                        2 => {
                            // insert a line
                            g.insert(rng.gen_range(0, g_len + 1), rng.gen_range(0, 10));
                        }
                        3 => {
                            // swap two lines
                            if !g.is_empty() {
                                g.swap(rng.gen_range(0, g_len), rng.gen_range(0, g_len));
                            }
                        }
                        _ => unreachable!(),
                    }
                }
                (f, g)
            })
            .boxed()
    }

    proptest! {
        #[test]
        fn test_valid_diff((f, g) in two_files()) {
            let d = diff(&f, &g);
            assert_valid(&f, &g, &d);
        }
    }
}