grit_lib/objects/
oid_hashtable.rs

1//! Fast [`HashMap`] / [`HashSet`] keys for [`ObjectId`].
2//!
3//! Git object ids are already cryptographic digests; hashing them again with
4//! SipHash over the full 20–32 byte value is wasted work on hot paths. These
5//! types use only the first eight digest bytes for bucket selection. [`OidHasher::finish`]
6//! XORs that prefix with a process-wide random value from [`OidBuildHasher::default`]
7//! so bucket placement is not predictable to an attacker who can choose object ids.
8//!
9//! Backing storage is [`hashbrown`] (same approach as `gix-hashtable`): it
10//! lowers insert and lookup overhead versus the standard library map for large
11//! OID-keyed tables while keeping the same semantics.
12//!
13//! [`ObjectId`] must be hashed with [`Hash::hash`] (which feeds the active digest
14//! bytes only) when used as a key in [`OidHashMap`] or [`OidHashSet`].
15
16use std::hash::{BuildHasher, Hasher};
17use std::sync::OnceLock;
18
19use getrandom::getrandom;
20use hashbrown::{HashMap, HashSet};
21
22use super::ObjectId;
23
24/// Build hasher for [`OidHashMap`] and [`OidHashSet`].
25#[derive(Clone, Copy, Debug)]
26pub struct OidBuildHasher {
27    multiplier: u64,
28}
29
30impl Default for OidBuildHasher {
31    fn default() -> Self {
32        shared_oid_build_hasher()
33    }
34}
35
36impl OidBuildHasher {
37    /// Creates a hasher with a fresh process-local random value for [`OidHasher::finish`].
38    #[must_use]
39    pub fn new() -> Self {
40        Self {
41            multiplier: random_odd_multiplier(),
42        }
43    }
44}
45
46impl BuildHasher for OidBuildHasher {
47    type Hasher = OidHasher;
48
49    #[inline]
50    fn build_hasher(&self) -> Self::Hasher {
51        OidHasher {
52            prefix: 0,
53            multiplier: self.multiplier,
54        }
55    }
56}
57
58/// Hasher state for OID-keyed maps.
59#[derive(Clone, Copy, Debug)]
60pub struct OidHasher {
61    prefix: u64,
62    multiplier: u64,
63}
64
65impl Hasher for OidHasher {
66    #[inline(always)]
67    fn finish(&self) -> u64 {
68        self.prefix ^ self.multiplier
69    }
70
71    #[inline(always)]
72    fn write(&mut self, bytes: &[u8]) {
73        self.prefix = u64::from_ne_bytes([
74            bytes[0], bytes[1], bytes[2], bytes[3], bytes[4], bytes[5], bytes[6], bytes[7],
75        ]);
76    }
77
78    fn write_u8(&mut self, _i: u8) {
79        oid_hasher_reject_typed_write("u8");
80    }
81
82    fn write_u16(&mut self, _i: u16) {
83        oid_hasher_reject_typed_write("u16");
84    }
85
86    fn write_u32(&mut self, _i: u32) {
87        oid_hasher_reject_typed_write("u32");
88    }
89
90    fn write_u64(&mut self, _i: u64) {
91        oid_hasher_reject_typed_write("u64");
92    }
93
94    fn write_usize(&mut self, _i: usize) {
95        oid_hasher_reject_typed_write("usize");
96    }
97
98    fn write_i8(&mut self, _i: i8) {
99        oid_hasher_reject_typed_write("i8");
100    }
101
102    fn write_i16(&mut self, _i: i16) {
103        oid_hasher_reject_typed_write("i16");
104    }
105
106    fn write_i32(&mut self, _i: i32) {
107        oid_hasher_reject_typed_write("i32");
108    }
109
110    fn write_i64(&mut self, _i: i64) {
111        oid_hasher_reject_typed_write("i64");
112    }
113
114    fn write_isize(&mut self, _i: isize) {
115        oid_hasher_reject_typed_write("isize");
116    }
117}
118
119#[cold]
120fn oid_hasher_reject_typed_write(label: &str) -> ! {
121    panic!("OidHasher only supports ObjectId::hash (write), not write_{label}");
122}
123
124/// [`HashMap`] keyed by [`ObjectId`] with [`OidBuildHasher`] (hashbrown table).
125pub type OidHashMap<V> = HashMap<ObjectId, V, OidBuildHasher>;
126
127/// [`HashSet`] of [`ObjectId`] with [`OidBuildHasher`] (hashbrown table).
128pub type OidHashSet = HashSet<ObjectId, OidBuildHasher>;
129
130/// Shared [`OidBuildHasher`] for this process (one process-wide random value for [`OidHasher::finish`]).
131#[inline]
132fn shared_oid_build_hasher() -> OidBuildHasher {
133    // hygiene: process-wide shared OID map hasher seed
134    static HASHER: OnceLock<OidBuildHasher> = OnceLock::new();
135    *HASHER.get_or_init(OidBuildHasher::new)
136}
137
138/// Empty [`OidHashMap`].
139#[inline]
140pub fn oid_hash_map<V>() -> OidHashMap<V> {
141    HashMap::with_hasher(shared_oid_build_hasher())
142}
143
144/// Empty [`OidHashMap`] with room for at least `capacity` entries without rehashing.
145#[inline]
146pub fn oid_hash_map_with_capacity<V>(capacity: usize) -> OidHashMap<V> {
147    HashMap::with_capacity_and_hasher(capacity, shared_oid_build_hasher())
148}
149
150/// Empty [`OidHashSet`].
151#[inline]
152pub fn oid_hash_set() -> OidHashSet {
153    HashSet::with_hasher(shared_oid_build_hasher())
154}
155
156/// Empty [`OidHashSet`] with room for at least `capacity` entries without rehashing.
157#[inline]
158pub fn oid_hash_set_with_capacity(capacity: usize) -> OidHashSet {
159    HashSet::with_capacity_and_hasher(capacity, shared_oid_build_hasher())
160}
161
162/// Shared empty OID set for borrow-only call sites (avoids per-call allocation).
163#[must_use]
164pub fn empty_oid_set() -> &'static OidHashSet {
165    // hygiene: shared empty OID set singleton for borrow-only APIs
166    static EMPTY: OnceLock<OidHashSet> = OnceLock::new();
167    EMPTY.get_or_init(oid_hash_set)
168}
169
170/// Copy a standard OID set into an [`OidHashSet`].
171#[inline]
172pub fn oid_hash_set_from(set: &std::collections::HashSet<ObjectId>) -> OidHashSet {
173    let mut out = oid_hash_set_with_capacity(set.len());
174    out.extend(set.iter().copied());
175    out
176}
177
178/// Copy a standard OID map into an [`OidHashMap`].
179#[inline]
180pub fn oid_hash_map_from<V: Clone>(map: &std::collections::HashMap<ObjectId, V>) -> OidHashMap<V> {
181    let mut out = oid_hash_map_with_capacity(map.len());
182    for (k, v) in map {
183        out.insert(*k, v.clone());
184    }
185    out
186}
187
188/// Shared empty standard OID set for public API boundaries (avoids per-call allocation).
189#[must_use]
190pub fn empty_object_id_hash_set() -> &'static std::collections::HashSet<ObjectId> {
191    // hygiene: shared empty standard OID set for API boundaries
192    static EMPTY: OnceLock<std::collections::HashSet<ObjectId>> = OnceLock::new();
193    EMPTY.get_or_init(std::collections::HashSet::new)
194}
195
196/// Shared empty OID → bytes map for commit-graph filter tests and call sites.
197#[must_use]
198pub fn empty_oid_byte_filter_map() -> &'static OidHashMap<Vec<u8>> {
199    // hygiene: shared empty OID byte map for filter call sites
200    static EMPTY: OnceLock<OidHashMap<Vec<u8>>> = OnceLock::new();
201    EMPTY.get_or_init(oid_hash_map)
202}
203
204fn random_odd_multiplier() -> u64 {
205    let mut buf = [0u8; 8];
206    if getrandom(&mut buf).is_err() {
207        return 1;
208    }
209    let mut m = u64::from_ne_bytes(buf);
210    m |= 1;
211    m
212}
213
214#[cfg(test)]
215mod tests {
216    use std::collections::hash_map::DefaultHasher;
217    use std::hash::{Hash, Hasher};
218
219    use super::*;
220
221    #[test]
222    fn hasher_uses_only_first_eight_id_bytes() {
223        let build = OidBuildHasher::new();
224        let id_bytes = [0xab_u8; 20];
225
226        let mut h = build.build_hasher();
227        h.write(&id_bytes);
228        let once = h.finish();
229
230        let mut h2 = build.build_hasher();
231        h2.write(&id_bytes[..8]);
232        assert_eq!(once, h2.finish());
233    }
234
235    #[test]
236    fn equal_oids_hash_the_same_in_oid_maps() {
237        let a = ObjectId::from_hex("4b825dc642cb6eb9a060e54bf8d69288fbee4904").expect("hex");
238        let b = ObjectId::from_hex("4b825dc642cb6eb9a060e54bf8d69288fbee4904").expect("hex");
239        assert_eq!(a, b);
240
241        let build = OidBuildHasher::new();
242        let mut ha = build.build_hasher();
243        let mut hb = build.build_hasher();
244        a.hash(&mut ha);
245        b.hash(&mut hb);
246        assert_eq!(ha.finish(), hb.finish());
247    }
248
249    #[test]
250    fn map_lookup_follows_eq() {
251        let sha1 = ObjectId::from_hex("4b825dc642cb6eb9a060e54bf8d69288fbee4904").expect("hex");
252        let altered = ObjectId::from_hex("4b825dc642cb6eb9a060e54bf8d69288fbee4905").expect("hex");
253        assert_ne!(sha1, altered);
254
255        let mut map: OidHashMap<&str> = oid_hash_map();
256        map.insert(sha1, "a");
257        assert_eq!(map.get(&sha1), Some(&"a"));
258        assert_eq!(map.get(&altered), None);
259    }
260
261    #[test]
262    fn oid_hash_map_set_roundtrip() {
263        let id = ObjectId::from_hex("deadbeefdeadbeefdeadbeefdeadbeefdeadbeef").expect("hex");
264        let mut set: OidHashSet = oid_hash_set();
265        assert!(set.insert(id));
266        assert!(!set.insert(id));
267        assert!(set.contains(&id));
268    }
269
270    #[test]
271    fn object_id_hash_feeds_active_digest_only() {
272        let id = ObjectId::from_hex("0102030405060708090a0b0c0d0e0f1011121314").expect("hex");
273        let build = OidBuildHasher::new();
274        let mut oid_hasher = build.build_hasher();
275        id.hash(&mut oid_hasher);
276        let oid_finish = oid_hasher.finish();
277
278        let mut raw = build.build_hasher();
279        raw.write(id.as_bytes());
280        assert_eq!(oid_finish, raw.finish());
281
282        let mut std_hasher = DefaultHasher::new();
283        id.hash(&mut std_hasher);
284        let _ = std_hasher.finish();
285    }
286}
grit_lib/objects/oid_hashtable.rs

grit_lib/objects/
oid_hashtable.rs
