Skip to main content

hyprstream_pds/
tid.rs

1//! atproto TID (Timestamp Identifier) — lexicographically-sortable record keys.
2//!
3//! A TID is a 13-character base32-sortable integer. A timestamp constructor
4//! packs 53 microsecond-timestamp bits above a 10-bit per-actor clock id.
5//! The sorted alphabet makes string order agree with numeric order.
6//!
7//! # Format
8//!
9//! The alphabet is `234567abcdefghijklmnopqrstuvwxyz` (32 symbols). The raw
10//! 64-bit integer is represented by 13 radix-32 digits, with a zero 65th bit
11//! at the LEFT. Thus the first digit is restricted to `2..7` or `a..j`, while
12//! the final digit carries all five low bits. This is integer encoding, not
13//! byte-oriented base32 with right-side padding bits.
14
15use std::fmt;
16
17use anyhow::{bail, Result};
18
19/// The 32-symbol TID base32 alphabet (sorted: '2' < ... < 'z').
20const TID_ALPHABET: &[u8; 32] = b"234567abcdefghijklmnopqrstuvwxyz";
21const TID_LEN: usize = 13;
22
23/// A 64-bit atproto TID.
24#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash, Ord, PartialOrd)]
25pub struct Tid(u64);
26
27impl Tid {
28    /// Construct a TID from raw 64-bit integer bits.
29    pub const fn from_raw(bits: u64) -> Self {
30        Tid(bits)
31    }
32
33    /// The raw 64-bit integer value of this TID.
34    ///
35    /// Used by callers that need to advance a revision monotonically (the
36    /// atproto commit `rev` must strictly increase), e.g. bumping past a
37    /// previous commit's rev when the wall clock has not moved.
38    pub const fn to_raw(self) -> u64 {
39        self.0
40    }
41
42    /// Build a TID from a microsecond timestamp (high 53 bits) and a 10-bit
43    /// clock id (low 10 bits).
44    ///
45    /// `clock_id` is masked to 10 bits. For tie-breaking across records written
46    /// in the same microsecond, callers should use a random per-actor value.
47    pub fn from_micros(micros: u64, clock_id: u16) -> Self {
48        let ts = micros & ((1u64 << 53) - 1);
49        let clk = (clock_id as u64) & 0x3ff;
50        Tid((ts << 10) | clk)
51    }
52
53    /// Current TID from the system clock, with a fixed clock id of 0.
54    ///
55    /// Production callers should pass a per-actor random clock id via
56    /// [`Tid::from_micros`]; this convenience is for tests/initial state.
57    pub fn now() -> Self {
58        let micros = std::time::SystemTime::now()
59            .duration_since(std::time::UNIX_EPOCH)
60            .map(|d| d.as_micros() as u64)
61            .unwrap_or(0);
62        Tid::from_micros(micros, 0)
63    }
64
65    /// Encode to the canonical 13-character base32 string.
66    ///
67    /// (Named `encode` rather than `to_string` to avoid shadowing the
68    /// `ToString` blanket impl that `Display` would otherwise recurse through.)
69    pub fn encode(self) -> String {
70        // Zero-extend the raw integer on the left: digits carry bits
71        // [64..60], [59..55], ..., [4..0]. Never shift the value left.
72        let mut out = vec![TID_ALPHABET[0]; TID_LEN];
73        for (i, slot) in out.iter_mut().enumerate() {
74            // Symbol i carries bits [64-5i .. 60-5i] of the 65-bit field.
75            // Shift the group's least significant bit down to bit zero.
76            let shift = 60 - 5 * i;
77            let idx = ((self.0 >> shift) & 0x1f) as usize;
78            *slot = TID_ALPHABET[idx];
79        }
80        // TID_ALPHABET is ASCII, so from_utf8 is infallible in practice; use
81        // from_utf8_unchecked's safe equivalent (unwrap_or with a fallback) to
82        // satisfy the workspace's `expect_used = "deny"` lint without panicking.
83        String::from_utf8(out).unwrap_or_else(|_| String::new())
84    }
85
86    /// Parse a 13-character base32 TID string.
87    ///
88    /// (Named `parse` rather than `from_str` to avoid confusion with the
89    /// `std::str::FromStr` trait, which we intentionally do not implement
90    /// because it would require a blanket `Sized` bound we don't want here.)
91    pub fn parse(s: &str) -> Result<Self> {
92        if s.len() != TID_LEN {
93            bail!("TID must be {TID_LEN} chars, got {}", s.len());
94        }
95        let mut value = 0u64;
96        for (position, &byte) in s.as_bytes().iter().enumerate() {
97            let digit = match TID_ALPHABET.iter().position(|&a| a == byte) {
98                Some(i) => i as u64,
99                None => bail!("invalid TID char {byte:?}"),
100            };
101            if position == 0 && digit >= 16 {
102                bail!("TID leading digit exceeds the 64-bit range");
103            }
104            value = value
105                .checked_mul(32)
106                .and_then(|value| value.checked_add(digit))
107                .ok_or_else(|| anyhow::anyhow!("TID overflow"))?;
108        }
109        Ok(Tid(value))
110    }
111}
112
113impl fmt::Display for Tid {
114    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
115        f.write_str(&self.encode())
116    }
117}
118
119#[cfg(test)]
120mod tests {
121    #![allow(
122        clippy::unwrap_used,
123        clippy::expect_used,
124        clippy::indexing_slicing,
125        clippy::panic
126    )]
127    use super::*;
128
129    #[test]
130    fn tid_raw_integer_vectors_cover_low_bits_and_full_range() {
131        for (raw, text) in [
132            (0, "2222222222222"),
133            (1, "2222222222223"),
134            (31, "222222222222z"),
135            (32, "2222222222232"),
136            (1u64 << 60, "3222222222222"),
137            ((1u64 << 63) - 1, "bzzzzzzzzzzzz"),
138            (1u64 << 63, "c222222222222"),
139            (u64::MAX, "jzzzzzzzzzzzz"),
140        ] {
141            assert_eq!(Tid::from_raw(raw).encode(), text);
142            assert_eq!(Tid::parse(text).unwrap().to_raw(), raw);
143        }
144        let maximum_timestamp = Tid::from_micros((1u64 << 53) - 1, 1023);
145        assert_eq!(maximum_timestamp.to_raw(), (1u64 << 63) - 1);
146        assert_eq!(maximum_timestamp.encode(), "bzzzzzzzzzzzz");
147    }
148
149    #[test]
150    fn tid_preserves_every_final_digit_and_valid_odd_low_bit() {
151        let even = Tid::parse("3jzfcijpj2z2a").unwrap();
152        let odd = Tid::parse("3jzfcijpj2z2b").unwrap();
153        assert_eq!(odd.to_raw(), even.to_raw() + 1);
154        assert_eq!(odd.encode(), "3jzfcijpj2z2b");
155        for &digit in TID_ALPHABET {
156            let text = format!("3jzfcijpj2z2{}", digit as char);
157            assert_eq!(Tid::parse(&text).unwrap().encode(), text);
158        }
159    }
160
161    #[test]
162    fn tid_rejects_out_of_range_leading_digits_and_noncanonical_text() {
163        for (index, &digit) in TID_ALPHABET.iter().enumerate() {
164            let text = format!("{}jzfcijpj2z2a", digit as char);
165            assert_eq!(Tid::parse(&text).is_ok(), index < 16, "{text}");
166        }
167        for text in [
168            "kjzfcijpj2z2a",
169            "KJZFCIJPJ2Z2A",
170            "3JZFCIJPJ2Z2B",
171            "3jzfcijpj2z2b=",
172            "3jzfcijpj2z2",
173            "3jzfcijpj2z21",
174        ] {
175            assert!(Tid::parse(text).is_err(), "{text}");
176        }
177    }
178
179    #[test]
180    fn tid_string_round_trip() {
181        for raw in [0u64, 1, 0x1234_5678, 0x7fff_ffff_ffff, 1u64 << 63, u64::MAX] {
182            let tid = Tid::from_raw(raw);
183            let s = tid.encode();
184            assert_eq!(s.len(), TID_LEN, "tid {raw}");
185            let back = Tid::parse(&s).expect("round-trip");
186            assert_eq!(tid, back, "tid {raw}: {s}");
187        }
188    }
189
190    #[test]
191    fn tid_lexicographic_matches_chrono() {
192        // String sort == integer sort == chronological sort.
193        let earlier = Tid::from_micros(1_000_000, 0); // 1s
194        let later = Tid::from_micros(2_000_000, 0); // 2s
195        assert!(earlier < later);
196        assert!(
197            earlier.encode() < later.encode(),
198            "string order must match chrono"
199        );
200    }
201
202    #[test]
203    fn tid_clock_id_breaks_ties() {
204        let a = Tid::from_micros(5_000_000, 1);
205        let b = Tid::from_micros(5_000_000, 2);
206        assert!(a < b, "clock id must break microsecond ties");
207    }
208
209    #[test]
210    fn tid_rejects_bad_length() {
211        assert!(Tid::parse("too-short").is_err());
212        assert!(Tid::parse("0uppercase!").is_err());
213    }
214}