girt 0.16.0

An incremental, idiomatic Rust implementation of Git
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
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

//! Conservative first-parent changed-path membership from Git-written Bloom chunks.
use super::{Chunks, CommitGraph, word};
use crate::ObjectId;

#[derive(Clone, Debug, Eq, PartialEq)]
pub(super) struct BloomFilter {
    version: u32,
    hashes: u32,
    bits: Vec<u8>,
}

impl CommitGraph {
    /// Tests whether a path might differ from this commit's first parent.
    ///
    /// `Some(false)` is a negative filter answer; `Some(true)` includes false positives.
    /// `None` means no usable filter or indexed commit, an unsupported hash version/count, or
    /// a non-ASCII query against a legacy version 1 filter. Paths are repository-relative bytes,
    /// without a trailing slash. This does not implement pathspec matching or rename following.
    /// The index's claim is not checked against objects. Merge filters describe only the first
    /// parent and cannot exclude differences from other parents.
    pub fn might_change_path(&self, commit: ObjectId, path: &[u8]) -> Option<bool> {
        if path.is_empty()
            || path
                .split(|byte| *byte == b'/')
                .any(|part| part.is_empty() || part == b"." || part == b".." || part.contains(&0))
        {
            return None;
        }
        let filter = self.get(commit)?.bloom.as_ref()?;
        if filter.version == 1 && !path.is_ascii() {
            return None;
        }
        if filter.bits == [0] {
            return Some(false);
        }
        if filter.bits == [255] {
            return Some(true);
        }
        let first = murmur3(path, 0x293ae76f);
        let second = murmur3(path, 0x7e646e2c);
        let size = filter.bits.len() as u64 * 8;
        Some((0..filter.hashes).all(|i| {
            let hash = first.wrapping_add(i.wrapping_mul(second));
            let bit = (u64::from(hash) % size) as usize;
            filter.bits[bit / 8] & (1 << (bit % 8)) != 0
        }))
    }
}

pub(super) struct BloomData<'a> {
    version: u32,
    hashes: u32,
    offsets: &'a [u8],
    data: &'a [u8],
}

impl<'a> BloomData<'a> {
    pub(super) fn parse(chunks: &Chunks<'a>, count: usize) -> Option<Self> {
        let offsets = chunks.optional(b"BIDX")?;
        let data = chunks.optional(b"BDAT")?;
        if offsets.len() != count.checked_mul(4)? || data.len() < 12 {
            return None;
        }
        let version = word(data, 0).ok()?;
        let hashes = word(data, 4).ok()?;
        if !matches!(version, 1 | 2) || !(1..=64).contains(&hashes) || word(data, 8).ok()? == 0 {
            return None;
        }
        let data = &data[12..];
        let mut previous = 0;
        for index in 0..count {
            let end = word(offsets, index * 4).ok()? as usize;
            if end < previous || end > data.len() {
                return None;
            }
            previous = end;
        }
        Some(Self {
            version,
            hashes,
            offsets,
            data,
        })
    }

    pub(super) fn filter(&self, index: usize) -> Option<BloomFilter> {
        let start = if index == 0 {
            0
        } else {
            word(self.offsets, (index - 1) * 4).ok()? as usize
        };
        let end = word(self.offsets, index * 4).ok()? as usize;
        let bits = self.data.get(start..end)?;
        if bits.is_empty() {
            return None;
        }
        Some(BloomFilter {
            version: self.version,
            hashes: self.hashes,
            bits: bits.to_vec(),
        })
    }
}

// MurmurHash3 x86_32 arithmetic, as specified by the format's hash version 2.
fn murmur3(bytes: &[u8], seed: u32) -> u32 {
    let mut hash = seed;
    let (blocks, tail) = bytes.as_chunks::<4>();
    for block in blocks {
        let value = u32::from_le_bytes([block[0], block[1], block[2], block[3]]);
        hash ^= mix(value);
        hash = hash
            .rotate_left(13)
            .wrapping_mul(5)
            .wrapping_add(0xe6546b64);
    }
    let mut value = 0u32;
    for (i, byte) in tail.iter().enumerate() {
        value |= u32::from(*byte) << (i * 8);
    }
    if !tail.is_empty() {
        hash ^= mix(value);
    }
    hash ^= bytes.len() as u32;
    hash ^= hash >> 16;
    hash = hash.wrapping_mul(0x85ebca6b);
    hash ^= hash >> 13;
    hash = hash.wrapping_mul(0xc2b2ae35);
    hash ^ (hash >> 16)
}

fn mix(value: u32) -> u32 {
    value
        .wrapping_mul(0xcc9e2d51)
        .rotate_left(15)
        .wrapping_mul(0x1b873593)
}

#[cfg(test)]
mod tests {
    use std::collections::BTreeMap;

    use rstest::rstest;

    use super::*;

    #[rstest]
    #[case::unknown_version(99, 7, [1,2])]
    #[case::zero_hashes(2, 0, [1,2])]
    #[case::excessive_hashes(2, 65, [1,2])]
    #[case::reversed_offsets(2, 7, [2,1])]
    #[case::outside_data(2, 7, [1,3])]
    fn unusable_filters_are_unknown(
        #[case] version: u32,
        #[case] hashes: u32,
        #[case] ends: [u32; 2],
    ) {
        let mut data = version.to_be_bytes().to_vec();
        data.extend_from_slice(&hashes.to_be_bytes());
        data.extend_from_slice(&10u32.to_be_bytes());
        data.extend_from_slice(&[0, 255]);
        let offsets: Vec<_> = ends.into_iter().flat_map(u32::to_be_bytes).collect();
        let chunks = Chunks(BTreeMap::from([
            (*b"BIDX", offsets.as_slice()),
            (*b"BDAT", data.as_slice()),
        ]));
        assert!(BloomData::parse(&chunks, 2).is_none());
    }
}