Something went wrong. Try again.
A public mirror for the whole atmosphere hubble.microcosm.blue
Something went wrong. Try again.
8.9 kB · 266 lines
Rust
at main
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267//! MST keys: the `collection/rkey` paths that records live at.
use std::fmt;
use sha2::{Digest, Sha256};
/// Deepest layer any key can reach.////// A key's layer is half its sha2-256 leading zero bits, and sha2-256 produces/// 256 of them, so nothing can hash deeper than this.////// the layer is basically a proof-of-work with a practical limit somewhere less/// than 80.pub const MAX_LAYER: u8 = 128;
/// Longest record key (the part after the slash), per/// [draft-holmgren-at-repository-02 §3.1][spec]: "Length between 1 and 512/// characters (inclusive)".////// [spec]: https://www.ietf.org/archive/id/draft-holmgren-at-repository-02.html#name-record-pathspub const MAX_RKEY_LEN: usize = 512;
/// Longest collection name, which is an NSID: "can have a maximum total length/// of 317 characters".pub const MAX_COLLECTION_LEN: usize = 317;
/// Longest legal record path, and so the longest legal MST key: a collection,/// a slash, and a record key.pub const MAX_KEY_LEN: usize = MAX_COLLECTION_LEN + 1 + MAX_RKEY_LEN;
#[derive(Debug, thiserror::Error)]pub enum KeyError { #[error("empty key")] Empty, #[error("key {key:?} is not of the form `collection/rkey`")] NotTwoParts { key: String }, #[error("collection is {len} characters, over the {MAX_COLLECTION_LEN} limit")] CollectionTooLong { len: usize }, #[error("record key is {len} characters, over the {MAX_RKEY_LEN} limit")] RkeyTooLong { len: usize }, #[error("collection {collection:?} has a character outside the NSID charset")] BadCollection { collection: String }, #[error("record key {rkey:?} has a character outside the record key charset")] BadRkey { rkey: String }, #[error("record key {rkey:?} is reserved")] ReservedRkey { rkey: String },}
/// A validated MST key.////// Keys are compared as bytes, which is what the tree's ordering is defined/// over. The charset is ASCII-only, so byte order and `str` order agree.#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]pub struct Key(Box<[u8]>);
impl Key { /// Validate `key` as a record path. /// /// Checks the shape, charsets and lengths the repository spec states for /// paths. It does not fully validate the collection as an NSID. Segment /// counts, leading-digit rule, etc not checked. pub fn new(key: &str) -> Result<Self, KeyError> { if key.is_empty() { return Err(KeyError::Empty); } let too_many_parts = |()| KeyError::NotTwoParts { key: key.to_string(), }; let mut parts = key.split('/'); let (Some(collection), Some(rkey), None) = (parts.next(), parts.next(), parts.next()) else { return Err(too_many_parts(())); }; if collection.is_empty() || rkey.is_empty() { return Err(too_many_parts(())); }
if collection.len() > MAX_COLLECTION_LEN { return Err(KeyError::CollectionTooLong { len: collection.len(), }); } if !collection .bytes() .all(|b| b.is_ascii_alphanumeric() || matches!(b, b'.' | b'-')) { return Err(KeyError::BadCollection { collection: collection.to_string(), }); }
if rkey.len() > MAX_RKEY_LEN { return Err(KeyError::RkeyTooLong { len: rkey.len() }); } if !rkey .bytes() .all(|b| b.is_ascii_alphanumeric() || matches!(b, b'.' | b'-' | b'_' | b':' | b'~')) { return Err(KeyError::BadRkey { rkey: rkey.to_string(), }); } if matches!(rkey, "." | "..") { return Err(KeyError::ReservedRkey { rkey: rkey.to_string(), }); }
Ok(Self(key.as_bytes().into())) }
pub fn as_bytes(&self) -> &[u8] { &self.0 }
/// The tree layer this key belongs at. pub fn layer(&self) -> u8 { layer_of(&self.0) }}
impl fmt::Debug for Key { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { // keys are ASCII by construction, but Debug must not panic on a Key // built from tree bytes we did not validate write!(f, "{:?}", String::from_utf8_lossy(&self.0)) }}
impl fmt::Display for Key { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { write!(f, "{}", String::from_utf8_lossy(&self.0)) }}
/// The layer a key belongs at: half the leading zero bits of its sha2-256 hash.////// Counting two bits at a time gives an average fanout of 4. The layer is a/// property of the key alone, never of the tree it sits in.pub fn layer_of(key: &[u8]) -> u8 { let hash = Sha256::digest(key); let mut zeros: u32 = 0; for byte in hash { if byte == 0 { zeros += 8; } else { zeros += byte.leading_zeros(); break; } } // 256 leading zeros would give 128, which fits; nothing can exceed it (zeros / 2) as u8}
/// Length of the longest byte prefix `a` and `b` share.pub fn shared_prefix_len(a: &[u8], b: &[u8]) -> usize { a.iter().zip(b.iter()).take_while(|(x, y)| x == y).count()}
#[cfg(test)]mod tests { use super::*;
#[test] fn validates() { assert!(Key::new("app.bsky.feed.post/3lrbpi5ot35kpjb").is_ok()); assert!(matches!(Key::new(""), Err(KeyError::Empty))); assert!(matches!( Key::new("no-slash"), Err(KeyError::NotTwoParts { .. }) )); assert!(matches!( Key::new("a/b/c"), Err(KeyError::NotTwoParts { .. }) )); assert!(matches!(Key::new("a/"), Err(KeyError::NotTwoParts { .. }))); assert!(matches!(Key::new("/b"), Err(KeyError::NotTwoParts { .. }))); assert!(matches!( Key::new("app.bsky.feed.post/what a key"), Err(KeyError::BadRkey { .. }) )); assert!(matches!( Key::new("app.bsky.feed.post/."), Err(KeyError::ReservedRkey { .. }) )); // colons and tildes are legal in record keys but not in collections assert!(Key::new("app.bsky.feed.post/self~1:2").is_ok()); assert!(matches!( Key::new("app.bsky~feed.post/abc"), Err(KeyError::BadCollection { .. }) ));
// the spec's own bounds, checked at the boundary assert!(Key::new(&format!("a.b.c/{}", "x".repeat(MAX_RKEY_LEN))).is_ok()); assert!(matches!( Key::new(&format!("a.b.c/{}", "x".repeat(MAX_RKEY_LEN + 1))), Err(KeyError::RkeyTooLong { .. }) )); assert!(Key::new(&format!("{}/rkey", "a".repeat(MAX_COLLECTION_LEN))).is_ok()); assert!(matches!( Key::new(&format!("{}/rkey", "a".repeat(MAX_COLLECTION_LEN + 1))), Err(KeyError::CollectionTooLong { .. }) )); }
#[test] fn layers_never_exceed_the_bound() { for i in 0..2000u32 { assert!(layer_of(format!("a/{i}").as_bytes()) <= MAX_LAYER); } }
/// Vectors from bluesky-social/atproto-interop-tests. #[test] fn interop_key_heights() { #[derive(serde::Deserialize)] struct Case { key: String, height: u8, } let json = include_str!("../tests/fixtures/atproto-interop/key_heights.json"); let cases: Vec<Case> = serde_json::from_str(json).expect("fixtures parse"); assert!(!cases.is_empty()); for case in cases { assert_eq!( layer_of(case.key.as_bytes()), case.height, "layer of {:?}", case.key ); } }
/// Vectors from bluesky-social/atproto-interop-tests. #[test] fn interop_common_prefix() { #[derive(serde::Deserialize)] struct Case { left: String, right: String, len: usize, } let json = include_str!("../tests/fixtures/atproto-interop/common_prefix.json"); let cases: Vec<Case> = serde_json::from_str(json).expect("fixtures parse"); assert!(!cases.is_empty()); for case in cases { assert_eq!( shared_prefix_len(case.left.as_bytes(), case.right.as_bytes()), case.len, "prefix of {:?} and {:?}", case.left, case.right ); } }
#[test] fn layer_distribution_matches_fanout_4() { // ~3/4 of keys should land at layer 0 let at_zero = (0..10_000u32) .filter(|i| layer_of(format!("a/{i:08}").as_bytes()) == 0) .count(); let share = at_zero as f64 / 10_000.0; assert!(share > 0.70 && share < 0.80, "got {share}"); }}