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

use std::ops::Range;

use crate::histogram::lcs::find_lcs;
use crate::histogram::list_pool::{ListHandle, ListPool};
use crate::intern::Token;
use crate::util::{strip_common_postfix, strip_common_prefix};
use crate::{myers, Sink};

mod lcs;
mod list_pool;

const MAX_CHAIN_LEN: u32 = 63;

struct Histogram {
    token_occurances: Vec<ListHandle>,
    pool: ListPool,
}

pub fn diff<S: Sink>(
    mut before: &[Token],
    mut after: &[Token],
    num_tokens: u32,
    mut sink: S,
) -> S::Out {
    let mut histogram = Histogram::new(num_tokens);
    let prefix = strip_common_prefix(&mut before, &mut after);
    strip_common_postfix(&mut before, &mut after);
    histogram.run(before, prefix, after, prefix, &mut sink);
    sink.finish()
}

impl Histogram {
    fn new(num_buckets: u32) -> Histogram {
        Histogram {
            token_occurances: vec![ListHandle::default(); num_buckets as usize],
            pool: ListPool::new(2 * num_buckets),
        }
    }

    fn clear(&mut self) {
        self.pool.clear();
    }

    fn token_occurances(&self, token: Token) -> &[u32] {
        self.token_occurances[token.0 as usize].as_slice(&self.pool)
    }

    fn num_token_occurances(&self, token: Token) -> u32 {
        self.token_occurances[token.0 as usize].len(&self.pool)
    }

    fn populate(&mut self, file: &[Token]) {
        for (i, &token) in file.iter().enumerate() {
            self.token_occurances[token.0 as usize].push(i as u32, &mut self.pool);
        }
    }

    fn run(
        &mut self,
        mut before: &[Token],
        mut before_off: u32,
        mut after: &[Token],
        mut after_off: u32,
        sink: &mut impl Sink,
    ) {
        loop {
            if before.is_empty() {
                if !after.is_empty() {
                    sink.process_change(
                        before_off..before_off,
                        after_off..after_off + after.len() as u32,
                    );
                }
                return;
            } else if after.is_empty() {
                sink.process_change(
                    before_off..before_off + before.len() as u32,
                    after_off..after_off,
                );
                return;
            }

            self.populate(before);
            match find_lcs(before, after, self) {
                // no lcs was found, that means that file1 and file2 two have nothing in common
                Some(lcs) if lcs.len == 0 => {
                    sink.process_change(
                        before_off..before_off + before.len() as u32,
                        after_off..after_off + after.len() as u32,
                    );
                    return;
                }
                Some(lcs) => {
                    self.run(
                        &before[..lcs.before_start as usize],
                        before_off,
                        &after[..lcs.after_start as usize],
                        after_off,
                        sink,
                    );

                    // this is equivalent to (tail) recursion but implement as a loop for efficeny reasons
                    let before_end = lcs.before_start + lcs.len;
                    before = &before[before_end as usize..];
                    before_off += before_end;

                    let after_end = lcs.after_start + lcs.len;
                    after = &after[after_end as usize..];
                    after_off += after_end;
                }
                None => {
                    // we are diffing two extremly large repetitive file
                    // this is a worst case for histogram diff with O(N^2) performance
                    // fallback to myers to maintain linear time complxity
                    myers::diff(
                        before,
                        after,
                        0, // not used by myers
                        |mut before: Range<u32>, mut after: Range<u32>| {
                            before.start += before_off;
                            before.end += before_off;
                            after.start += after_off;
                            after.end += after_off;
                            sink.process_change(before, after)
                        },
                        false,
                    );
                    return;
                }
            }
        }
    }
}