agentd/state/
ulid.rs

1// SPDX-License-Identifier: AGPL-3.0-only
2//! A dependency-free **ULID** (Universally Unique Lexicographically Sortable
3//! Identifier): 48-bit ms timestamp + 80 random bits, Crockford base32, 26
4//! chars, monotonic within one process for the same millisecond. Used for
5//! inbox events, runs, artifacts, audit records — sortable by time in the
6//! store's `list` and stable across restarts.
7
8use std::sync::Mutex;
9
10const ALPHABET: &[u8; 32] = b"0123456789ABCDEFGHJKMNPQRSTVWXYZ";
11
12struct Last {
13    ms: u64,
14    rand: u128, // low 80 bits used
15}
16
17static LAST: Mutex<Last> = Mutex::new(Last { ms: 0, rand: 0 });
18
19/// A new ULID for `now`.
20pub fn new() -> String {
21    let ms = super::now_ms();
22    let mut last = LAST.lock().unwrap_or_else(|e| e.into_inner());
23    let rand = if ms == last.ms {
24        // Same millisecond: increment (monotonic), wrapping inside 80 bits.
25        (last.rand + 1) & ((1u128 << 80) - 1)
26    } else {
27        random80()
28    };
29    last.ms = ms;
30    last.rand = rand;
31    encode(ms, rand)
32}
33
34/// The timestamp (ms) encoded in a ULID, if it parses.
35pub fn timestamp_ms(ulid: &str) -> Option<u64> {
36    if ulid.len() != 26 {
37        return None;
38    }
39    let mut ts: u64 = 0;
40    for c in ulid.bytes().take(10) {
41        let v = decode_char(c)?;
42        ts = (ts << 5) | v as u64;
43    }
44    Some(ts)
45}
46
47fn encode(ms: u64, rand: u128) -> String {
48    let mut out = [0u8; 26];
49    let mut t = ms;
50    for i in (0..10).rev() {
51        out[i] = ALPHABET[(t & 31) as usize];
52        t >>= 5;
53    }
54    let mut r = rand;
55    for i in (10..26).rev() {
56        out[i] = ALPHABET[(r & 31) as usize];
57        r >>= 5;
58    }
59    String::from_utf8_lossy(&out).into_owned()
60}
61
62fn decode_char(c: u8) -> Option<u8> {
63    ALPHABET
64        .iter()
65        .position(|&a| a == c.to_ascii_uppercase())
66        .map(|p| p as u8)
67}
68
69fn random80() -> u128 {
70    let mut buf = [0u8; 16];
71    let ok = std::fs::File::open("/dev/urandom")
72        .and_then(|mut f| std::io::Read::read_exact(&mut f, &mut buf))
73        .is_ok();
74    if !ok {
75        // Fallback: a splitmix over time+pid+counter (never the primary path
76        // on Linux, but never a duplicate within a process either).
77        static CTR: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(0);
78        let seed = super::now_ms()
79            ^ (std::process::id() as u64).rotate_left(32)
80            ^ CTR.fetch_add(0x9E37_79B9_7F4A_7C15, std::sync::atomic::Ordering::Relaxed);
81        let mut z = seed.wrapping_add(0x9E37_79B9_7F4A_7C15);
82        let mut mix = || {
83            z = z.wrapping_add(0x9E37_79B9_7F4A_7C15);
84            let mut x = z;
85            x = (x ^ (x >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
86            x = (x ^ (x >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
87            x ^ (x >> 31)
88        };
89        let a = mix();
90        let b = mix();
91        buf[..8].copy_from_slice(&a.to_le_bytes());
92        buf[8..].copy_from_slice(&b.to_le_bytes());
93    }
94    u128::from_le_bytes(buf) & ((1u128 << 80) - 1)
95}
96
97#[cfg(test)]
98mod tests {
99    use super::*;
100
101    #[test]
102    fn ulids_are_26_chars_sortable_and_unique() {
103        let a = new();
104        let b = new();
105        assert_eq!(a.len(), 26);
106        assert!(a.bytes().all(|c| ALPHABET.contains(&c)));
107        assert_ne!(a, b);
108        assert!(a < b, "monotonic within a process: {a} < {b}");
109        let ts = timestamp_ms(&a).unwrap();
110        let now = super::super::now_ms();
111        assert!(now >= ts && now - ts < 5_000);
112        assert_eq!(timestamp_ms("short"), None);
113        // Many in a tight loop stay unique and ordered.
114        let mut prev = new();
115        for _ in 0..1000 {
116            let n = new();
117            assert!(n > prev);
118            prev = n;
119        }
120    }
121}
agentd/state/ulid.rs

agentd/state/
ulid.rs
