sui_graph_store/
content_address.rs

1//! BLAKE3-based content addressing.
2//!
3//! Every typed graph is identified by the BLAKE3 of its canonical rkyv
4//! archive bytes. Because rkyv 0.8's wire format is deterministic for
5//! a given type+value, this hash is **stable across machines and
6//! across crate versions within the 0.8 series**.
7//!
8//! ## Encoding
9//!
10//! Displayed and serialized as **Nix-style base32** (the 32-character
11//! alphabet `0-9 a-z` minus `e`, `o`, `t`, `u` — same as `nix-hash`)
12//! truncated to the conventional 52-character store-path digest length.
13//! This makes hashes look right at home next to existing Nix store paths
14//! and shortens filesystem path components below most operating-system
15//! `NAME_MAX` limits (255 bytes) with comfortable headroom.
16//!
17//! Internally the hash is the full 32-byte BLAKE3 digest; only the
18//! display form is truncated.
19
20use std::fmt;
21use std::str::FromStr;
22
23use rkyv::{Archive, Deserialize as RkyvDeserialize, Serialize as RkyvSerialize};
24
25use crate::error::Error;
26
27/// 32-byte BLAKE3 content hash. The canonical identity of every graph
28/// in the store.
29///
30/// Carries rkyv `Archive` derives so wire types in `sui-protocol`
31/// (and any future archived form referring to a stored blob) can embed
32/// it cheaply. The archived form is a fixed-32-byte fixed-layout, so
33/// zero-copy reads of a `GraphHash` are a literal pointer offset.
34#[derive(
35    Archive,
36    RkyvSerialize,
37    RkyvDeserialize,
38    Clone,
39    Copy,
40    PartialEq,
41    Eq,
42    Hash,
43    PartialOrd,
44    Ord,
45)]
46#[rkyv(derive(Debug, PartialEq, Eq))]
47pub struct GraphHash(pub [u8; 32]);
48
49impl GraphHash {
50    /// Compute the BLAKE3 of an arbitrary byte slice. This is the
51    /// canonical "what's the hash of these archive bytes" entry point —
52    /// callers compute it once at archive time and again at retrieve
53    /// time to verify.
54    #[must_use]
55    pub fn of(bytes: &[u8]) -> Self {
56        Self(blake3::hash(bytes).into())
57    }
58
59    /// Raw 32-byte form. Useful when threading into a fixed-width
60    /// keying surface (redb key, protobuf bytes field, etc.).
61    #[must_use]
62    pub fn as_bytes(&self) -> &[u8; 32] {
63        &self.0
64    }
65
66    /// Truncated display form (52 base32 chars, matches Nix store
67    /// digest length). Used in file names and log lines.
68    #[must_use]
69    pub fn display_short(&self) -> String {
70        let full = self.to_string();
71        full.chars().take(52).collect()
72    }
73
74    /// Two-byte/two-byte fan-out prefix for the on-disk path. Returns
75    /// `(aa, bb)` where `aa` and `bb` are the first two and second two
76    /// hex characters of the hash — chosen so the fan-out spans
77    /// 256 × 256 = 65 536 leaf directories without ever stat-ing more
78    /// than ~16 blobs per leaf (Git's proven shape).
79    #[must_use]
80    pub fn shard_prefix(&self) -> (String, String) {
81        let hex = data_encoding::HEXLOWER.encode(&self.0[..2]);
82        (hex[0..2].to_string(), hex[2..4].to_string())
83    }
84}
85
86impl fmt::Debug for GraphHash {
87    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
88        write!(f, "GraphHash({})", self.display_short())
89    }
90}
91
92impl fmt::Display for GraphHash {
93    /// Nix-style base32 of the full 32-byte digest. Stable across runs.
94    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
95        let encoded = nix_base32_encode(&self.0);
96        f.write_str(&encoded)
97    }
98}
99
100impl FromStr for GraphHash {
101    type Err = Error;
102
103    fn from_str(s: &str) -> Result<Self, Self::Err> {
104        let bytes = nix_base32_decode(s).ok_or(Error::BadHash {
105            input: s.to_string(),
106            reason: "not a valid nix-base32 encoding",
107        })?;
108        if bytes.len() != 32 {
109            return Err(Error::BadHash {
110                input: s.to_string(),
111                reason: "wrong digest length (expected 32 bytes)",
112            });
113        }
114        let mut out = [0u8; 32];
115        out.copy_from_slice(&bytes);
116        Ok(Self(out))
117    }
118}
119
120// ── Nix-style base32 codec ───────────────────────────────────────────
121// Mirrors `nix-hash --to-base32` exactly. Alphabet: 0-9, a-z minus e,o,t,u.
122// Bit packing is LSB-first across the input bytes; output length is
123// `(len * 8 + 4) / 5` characters. This is the same routine cppnix uses.
124
125const NIX_BASE32_CHARS: &[u8; 32] = b"0123456789abcdfghijklmnpqrsvwxyz";
126
127fn nix_base32_encode(bytes: &[u8]) -> String {
128    let out_len = (bytes.len() * 8 + 4) / 5;
129    let mut out = String::with_capacity(out_len);
130    for i in (0..out_len).rev() {
131        let b = i * 5;
132        let byte = b / 8;
133        let bit = b % 8;
134        let mut c = u16::from(bytes[byte]) >> bit;
135        if byte + 1 < bytes.len() {
136            c |= u16::from(bytes[byte + 1]) << (8 - bit);
137        }
138        out.push(NIX_BASE32_CHARS[(c & 0x1f) as usize] as char);
139    }
140    out
141}
142
143fn nix_base32_decode(s: &str) -> Option<Vec<u8>> {
144    let s = s.as_bytes();
145    let bytes_len = s.len() * 5 / 8;
146    let mut out = vec![0u8; bytes_len];
147    for (i, &c) in s.iter().rev().enumerate() {
148        let digit = NIX_BASE32_CHARS.iter().position(|&x| x == c)?;
149        let b = i * 5;
150        let byte = b / 8;
151        let bit = b % 8;
152        let lo = (digit as u16) << bit;
153        let hi = (digit as u16) >> (8 - bit);
154        out[byte] |= (lo & 0xff) as u8;
155        if hi != 0 && byte + 1 < bytes_len {
156            out[byte + 1] |= hi as u8;
157        }
158    }
159    Some(out)
160}
161
162#[cfg(test)]
163mod tests {
164    use super::*;
165    use pretty_assertions::assert_eq;
166
167    #[test]
168    fn hash_of_empty_is_blake3_empty() {
169        let h = GraphHash::of(&[]);
170        // BLAKE3 of empty input is a known constant.
171        let expected: [u8; 32] = [
172            0xaf, 0x13, 0x49, 0xb9, 0xf5, 0xf9, 0xa1, 0xa6, 0xa0, 0x40, 0x4d, 0xea, 0x36, 0xdc,
173            0xc9, 0x49, 0x9b, 0xcb, 0x25, 0xc9, 0xad, 0xc1, 0x12, 0xb7, 0xcc, 0x9a, 0x93, 0xca,
174            0xe4, 0x1f, 0x32, 0x62,
175        ];
176        assert_eq!(h.as_bytes(), &expected);
177    }
178
179    #[test]
180    fn base32_roundtrip() {
181        for input in [b"".as_slice(), b"hello", b"sui graph store"] {
182            // BLAKE3 to get exactly 32 bytes.
183            let h = GraphHash::of(input);
184            let s = h.to_string();
185            let back: GraphHash = s.parse().unwrap();
186            assert_eq!(h, back);
187        }
188    }
189
190    #[test]
191    fn shard_prefix_is_two_two_hex() {
192        let h = GraphHash::of(b"shard test");
193        let (a, b) = h.shard_prefix();
194        assert_eq!(a.len(), 2);
195        assert_eq!(b.len(), 2);
196        assert!(a.chars().all(|c| c.is_ascii_hexdigit()));
197        assert!(b.chars().all(|c| c.is_ascii_hexdigit()));
198    }
199
200    #[test]
201    fn display_short_is_52_chars() {
202        let h = GraphHash::of(b"display test");
203        assert_eq!(h.display_short().len(), 52);
204    }
205
206    #[test]
207    fn bad_hash_string_returns_error() {
208        let r: Result<GraphHash, _> = "not a real hash!@#".parse();
209        assert!(r.is_err());
210    }
211}
sui_graph_store/content_address.rs

sui_graph_store/
content_address.rs
