omnidiff 0.2.0

Fast, robust, syntax-aware code diffing using tree-sitter ASTs
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

/*  This file is part of the OmniDiff code diffing tool.
 *
 *  Copyright (C) 2026 Marko Ivankovic
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Affero General Public License as published
 *  by the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 *  GNU Affero General Public License for more details.
 *
 *  You should have received a copy of the GNU Affero General Public License
 *  along with this program. If not, see <https://www.gnu.org/licenses/>.
 */
use rand::{Rng, RngExt};

/// LOC buckets for stratified sampling, keyed by the larger of a pair's before/after line count.
///
/// Lines, not AST nodes, though nodes drive diff cost: candidates are bucketed during a commit
/// walk, where a line count is cheap and a node count would mean parsing every candidate.
pub const LOC_BUCKETS: &[(usize, &str)] = &[
    (10, "0-10"),
    (30, "10-30"),
    (100, "30-100"),
    (300, "100-300"),
    (1_000, "300-1000"),
    (3_000, "1000-3000"),
    (usize::MAX, "3000+"),
];

/// Which of [`LOC_BUCKETS`] `loc` falls into: the first whose upper bound exceeds it.
///
/// Callers write it to a CSV column named `size_bucket`, a name committed CSVs and their readers
/// depend on; older files there hold byte-based labels.
pub fn loc_bucket(loc: usize) -> &'static str {
    LOC_BUCKETS
        .iter()
        .find(|(upper, _)| loc < *upper)
        .map(|(_, name)| *name)
        .unwrap_or("3000+")
}

/// Reservoir sampling (Algorithm R): picks a uniform random sample of `capacity` items from a
/// stream of unknown length in a single pass, without holding the whole stream in memory.
pub struct Reservoir<T> {
    pub items: Vec<T>,
    seen: u64,
}

// Hand-written instead of derived so `T` itself doesn't need to be `Default`.
impl<T> Default for Reservoir<T> {
    fn default() -> Self {
        Self {
            items: Vec::new(),
            seen: 0,
        }
    }
}

impl<T> Reservoir<T> {
    pub fn offer(&mut self, item: T, capacity: usize, rng: &mut impl Rng) {
        self.seen += 1;
        if self.items.len() < capacity {
            self.items.push(item);
        } else {
            let j = rng.random_range(0..self.seen) as usize;
            if j < capacity {
                self.items[j] = item;
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use rand::SeedableRng;
    use rand::rngs::StdRng;

    #[test]
    fn reservoir_never_exceeds_capacity() {
        let mut rng = StdRng::seed_from_u64(7);
        let mut reservoir = Reservoir::default();
        for i in 0..1000u32 {
            reservoir.offer(i, 5, &mut rng);
        }
        assert_eq!(reservoir.items.len(), 5);
        assert_eq!(reservoir.seen, 1000);
    }

    #[test]
    fn reservoir_keeps_everything_below_capacity() {
        let mut rng = StdRng::seed_from_u64(7);
        let mut reservoir = Reservoir::default();
        for i in 0..3u32 {
            reservoir.offer(i, 5, &mut rng);
        }
        assert_eq!(reservoir.items, vec![0, 1, 2]);
    }

    #[test]
    fn loc_bucket_boundaries() {
        assert_eq!(loc_bucket(0), "0-10");
        assert_eq!(loc_bucket(9), "0-10");
        assert_eq!(loc_bucket(10), "10-30");
        assert_eq!(loc_bucket(29), "10-30");
        assert_eq!(loc_bucket(30), "30-100");
        assert_eq!(loc_bucket(99), "30-100");
        assert_eq!(loc_bucket(100), "100-300");
        assert_eq!(loc_bucket(299), "100-300");
        assert_eq!(loc_bucket(300), "300-1000");
        assert_eq!(loc_bucket(999), "300-1000");
        assert_eq!(loc_bucket(1_000), "1000-3000");
        assert_eq!(loc_bucket(2_999), "1000-3000");
        assert_eq!(loc_bucket(3_000), "3000+");
        assert_eq!(loc_bucket(usize::MAX), "3000+");
    }
}