sofie_core/
uuid.rs

1use std::fmt;
2use std::str::FromStr;
3use std::sync::atomic::{AtomicU64, Ordering};
4use std::time::{SystemTime, UNIX_EPOCH};
5
6use serde::{Deserialize, Deserializer, Serialize, Serializer};
7
8use crate::Error;
9use crate::encoding::hex;
10
11/// RFC 9562; ordered by bytes so version 7 ids sort in creation order.
12#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
13pub struct Uuid([u8; 16]);
14
15#[derive(Clone, Copy, Debug, PartialEq, Eq)]
16pub struct ParseUuidError;
17
18#[derive(Clone, Copy, Debug, PartialEq, Eq)]
19pub struct RandomnessUnavailable;
20
21const COUNTER_BITS: u32 = 12;
22const COUNTER_MASK: u64 = (1 << COUNTER_BITS) - 1;
23/// Starts mid-range so at least 2048 ids fit before the timestamp has to advance.
24const SEED_MASK: u64 = COUNTER_MASK >> 1;
25const TIMESTAMP_MAX: u64 = (1 << 48) - 1;
26const HYPHEN_POSITIONS: [usize; 4] = [8, 13, 18, 23];
27
28/// `timestamp << 12 | counter`; process-wide so ids from any thread sort in creation order.
29static LAST_V7: AtomicU64 = AtomicU64::new(0);
30
31impl Uuid {
32    #[must_use]
33    pub const fn from_bytes(bytes: [u8; 16]) -> Self {
34        Self(bytes)
35    }
36
37    #[must_use]
38    pub const fn from_u128(value: u128) -> Self {
39        Self(value.to_be_bytes())
40    }
41
42    #[must_use]
43    pub const fn as_bytes(&self) -> &[u8; 16] {
44        &self.0
45    }
46
47    pub fn push_to(self, out: &mut String) {
48        out.push_str(self.hex().as_str());
49    }
50
51    pub fn now_v7() -> Result<Self, RandomnessUnavailable> {
52        let mut random = [0; 10];
53        crate::random::fill(&mut random)?;
54        let [seed_high, seed_low, rest @ ..] = random;
55        let seed = u64::from(u16::from_be_bytes([seed_high, seed_low])) & SEED_MASK;
56        let state = advance_v7_state(seed);
57        let timestamp_and_counter = (state >> COUNTER_BITS) << 16 | (state & COUNTER_MASK);
58        let mut bytes = [0; 16];
59        bytes[..8].copy_from_slice(&timestamp_and_counter.to_be_bytes());
60        bytes[8..].copy_from_slice(&rest);
61        Ok(Self(bytes).with_version(7))
62    }
63
64    pub fn new_v4() -> Result<Self, RandomnessUnavailable> {
65        let mut bytes = [0; 16];
66        crate::random::fill(&mut bytes)?;
67        Ok(Self(bytes).with_version(4))
68    }
69
70    const fn with_version(mut self, version: u8) -> Self {
71        self.0[6] = (self.0[6] & 0x0f) | (version << 4);
72        self.0[8] = (self.0[8] & 0x3f) | 0x80;
73        self
74    }
75
76    fn hex(self) -> Hex {
77        let mut text = [b'-'; 36];
78        let mut position = 0;
79        for (index, byte) in self.0.into_iter().enumerate() {
80            if matches!(index, 4 | 6 | 8 | 10) {
81                position += 1;
82            }
83            text[position..position + 2].copy_from_slice(&hex::digits(byte));
84            position += 2;
85        }
86        Hex(text)
87    }
88}
89
90struct Hex([u8; 36]);
91
92impl Hex {
93    fn as_str(&self) -> &str {
94        std::str::from_utf8(&self.0).unwrap_or_default()
95    }
96}
97
98/// Lock-free: a thread that loses the race retries from the winner's state.
99fn advance_v7_state(seed: u64) -> u64 {
100    let mut previous = LAST_V7.load(Ordering::Relaxed);
101    loop {
102        let next = next_v7_state(previous, unix_millis(), seed);
103        match LAST_V7.compare_exchange_weak(previous, next, Ordering::Relaxed, Ordering::Relaxed) {
104            Ok(_) => return next,
105            Err(current) => previous = current,
106        }
107    }
108}
109
110fn next_v7_state(previous: u64, now_millis: u64, seed: u64) -> u64 {
111    if now_millis > previous >> COUNTER_BITS {
112        return now_millis << COUNTER_BITS | seed;
113    }
114    previous + 1
115}
116
117/// A clock before 1970 reads as 0; ids still count up from the last one, so order holds.
118fn unix_millis() -> u64 {
119    let elapsed = SystemTime::now()
120        .duration_since(UNIX_EPOCH)
121        .unwrap_or_default();
122    u64::try_from(elapsed.as_millis())
123        .unwrap_or(u64::MAX)
124        .min(TIMESTAMP_MAX)
125}
126
127impl FromStr for Uuid {
128    type Err = ParseUuidError;
129
130    fn from_str(text: &str) -> Result<Self, Self::Err> {
131        let hyphenated = match text.len() {
132            36 => true,
133            32 => false,
134            _ => return Err(ParseUuidError),
135        };
136        let mut value = 0_u128;
137        for (index, byte) in text.bytes().enumerate() {
138            if hyphenated && HYPHEN_POSITIONS.contains(&index) {
139                if byte != b'-' {
140                    return Err(ParseUuidError);
141                }
142                continue;
143            }
144            let digit = hex::digit_value(byte).ok_or(ParseUuidError)?;
145            value = value << 4 | u128::from(digit);
146        }
147        Ok(Self::from_u128(value))
148    }
149}
150
151impl fmt::Display for Uuid {
152    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
153        formatter.write_str(self.hex().as_str())
154    }
155}
156
157impl fmt::Debug for Uuid {
158    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
159        fmt::Display::fmt(self, formatter)
160    }
161}
162
163impl Serialize for Uuid {
164    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
165        serializer.serialize_str(self.hex().as_str())
166    }
167}
168
169impl<'de> Deserialize<'de> for Uuid {
170    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
171        crate::deserialize_parsed(deserializer, "a UUID", str::parse)
172    }
173}
174
175impl fmt::Display for ParseUuidError {
176    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
177        formatter.write_str("not a UUID: expected 32 hex digits, optionally hyphenated 8-4-4-4-12")
178    }
179}
180
181impl std::error::Error for ParseUuidError {}
182
183impl fmt::Display for RandomnessUnavailable {
184    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
185        formatter.write_str("the operating system's random number generator failed")
186    }
187}
188
189impl std::error::Error for RandomnessUnavailable {}
190
191impl From<RandomnessUnavailable> for Error {
192    fn from(error: RandomnessUnavailable) -> Self {
193        Self::internal("generating a UUID", error)
194    }
195}
196
197#[cfg(test)]
198mod tests {
199    use std::collections::HashSet;
200    use std::sync::Mutex;
201    use std::thread;
202
203    use super::*;
204
205    const RFC_V7: &str = "017f22e2-79b0-7cc3-98c4-dc0c0c07398f";
206    const RFC_V4: &str = "919108f7-52d1-4320-9bac-f847db4148a8";
207
208    fn version(id: Uuid) -> u8 {
209        id.as_bytes()[6] >> 4
210    }
211
212    fn variant(id: Uuid) -> u8 {
213        id.as_bytes()[8] >> 6
214    }
215
216    fn assert_strictly_increasing(ids: &[Uuid]) {
217        for pair in ids.windows(2) {
218            assert!(pair[0] < pair[1], "{} then {}", pair[0], pair[1]);
219        }
220    }
221
222    #[test]
223    fn the_rfc_9562_examples_parse_and_format_back() {
224        let v7: Uuid = RFC_V7.parse().unwrap();
225        let v4: Uuid = RFC_V4.parse().unwrap();
226
227        assert_eq!(
228            v7,
229            Uuid::from_u128(0x017f_22e2_79b0_7cc3_98c4_dc0c_0c07_398f)
230        );
231        assert_eq!(v7.to_string(), RFC_V7);
232        assert_eq!(v4.to_string(), RFC_V4);
233        assert_eq!((version(v7), variant(v7)), (7, 0b10));
234        assert_eq!((version(v4), variant(v4)), (4, 0b10));
235    }
236
237    #[test]
238    fn upper_case_and_simple_forms_parse_to_the_same_id() {
239        let expected: Uuid = RFC_V7.parse().unwrap();
240
241        assert_eq!(RFC_V7.to_uppercase().parse::<Uuid>().unwrap(), expected);
242        assert_eq!(
243            "017f22e279b07cc398c4dc0c0c07398f".parse::<Uuid>().unwrap(),
244            expected
245        );
246        assert_eq!(format!("{expected:?}"), RFC_V7);
247    }
248
249    #[test]
250    fn every_nibble_is_written_in_place_between_the_hyphens() {
251        let id = Uuid::from_bytes([
252            0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef, 0xfe, 0xdc, 0xba, 0x98, 0x76, 0x54,
253            0x32, 0x10,
254        ]);
255
256        assert_eq!(id.to_string(), "01234567-89ab-cdef-fedc-ba9876543210");
257    }
258
259    #[test]
260    fn bytes_round_trip_in_network_order() {
261        let id: Uuid = RFC_V7.parse().unwrap();
262
263        assert_eq!(id.as_bytes()[..4], [0x01, 0x7f, 0x22, 0xe2]);
264        assert_eq!(Uuid::from_bytes(*id.as_bytes()), id);
265    }
266
267    #[test]
268    fn anything_but_the_two_forms_is_refused() {
269        let refused = [
270            "",
271            "017f22e2-79b0-7cc3-98c4-dc0c0c07398",
272            "017f22e2-79b0-7cc3-98c4-dc0c0c07398f0",
273            "017f22e279b07cc398c4dc0c0c07398",
274            "017f22e279b07cc398c4dc0c0c07398f0",
275            "017f22e2-79b0-7cc3-98c4-dc0c0c07398g",
276            "017f22e279b0-7cc3-98c4-dc0c0c07398f-",
277            "017f22e2_79b0_7cc3_98c4_dc0c0c07398f",
278            "{017f22e2-79b0-7cc3-98c4-dc0c0c0739}",
279            "urn:uuid:017f22e2-79b0-7cc3-98c4-dc0c0c07398f",
280            " 17f22e279b07cc398c4dc0c0c07398f",
281            "+17f22e279b07cc398c4dc0c0c07398f",
282            "017f22e2-79b0-7cc3-98c4-dc0c0c0739é",
283        ];
284
285        for text in refused {
286            assert_eq!(text.parse::<Uuid>(), Err(ParseUuidError), "{text:?}");
287        }
288    }
289
290    #[test]
291    fn generated_ids_carry_their_version_and_variant() {
292        for _ in 0..1000 {
293            let v7 = Uuid::now_v7().unwrap();
294            let v4 = Uuid::new_v4().unwrap();
295
296            assert_eq!((version(v7), variant(v7)), (7, 0b10));
297            assert_eq!((version(v4), variant(v4)), (4, 0b10));
298        }
299    }
300
301    #[test]
302    fn a_v7_id_starts_with_the_current_unix_milliseconds() {
303        let before = unix_millis();
304        let id = Uuid::now_v7().unwrap();
305        let after = unix_millis();
306
307        let mut timestamp = [0; 8];
308        timestamp[2..].copy_from_slice(&id.as_bytes()[..6]);
309        let millis = u64::from_be_bytes(timestamp);
310        // Parallel tests can overflow the counter, which moves the timestamp ahead of the clock.
311        assert!(
312            before <= millis && millis <= after + 1_000,
313            "{before} {millis} {after}"
314        );
315    }
316
317    #[test]
318    fn ids_made_in_a_tight_loop_sort_in_creation_order() {
319        let ids: Vec<Uuid> = (0..100_000).map(|_| Uuid::now_v7().unwrap()).collect();
320
321        assert_strictly_increasing(&ids);
322    }
323
324    #[test]
325    fn ids_made_on_many_threads_are_unique_and_ordered_per_thread() {
326        let per_thread: Vec<Vec<Uuid>> = thread::scope(|scope| {
327            let handles: Vec<_> = (0..8)
328                .map(|_| scope.spawn(|| (0..20_000).map(|_| Uuid::now_v7().unwrap()).collect()))
329                .collect();
330            handles
331                .into_iter()
332                .map(|handle| handle.join().unwrap())
333                .collect()
334        });
335
336        for ids in &per_thread {
337            assert_strictly_increasing(ids);
338        }
339        let unique: HashSet<Uuid> = per_thread.iter().flatten().copied().collect();
340        assert_eq!(unique.len(), 8 * 20_000);
341    }
342
343    #[test]
344    fn ids_made_one_after_another_across_threads_sort_in_that_order() {
345        let made = Mutex::new(Vec::new());
346        thread::scope(|scope| {
347            for _ in 0..8 {
348                scope.spawn(|| {
349                    for _ in 0..5_000 {
350                        let mut made = made.lock().unwrap();
351                        made.push(Uuid::now_v7().unwrap());
352                    }
353                });
354            }
355        });
356
357        assert_strictly_increasing(&made.into_inner().unwrap());
358    }
359
360    #[test]
361    fn a_new_millisecond_restarts_the_counter_at_the_seed() {
362        let previous = 41 << COUNTER_BITS | 0x384;
363
364        assert_eq!(next_v7_state(previous, 42, 7), 42 << COUNTER_BITS | 7);
365    }
366
367    #[test]
368    fn the_same_or_an_earlier_millisecond_counts_up() {
369        let previous = 42 << COUNTER_BITS | 0x384;
370
371        assert_eq!(next_v7_state(previous, 42, 7), previous + 1);
372        assert_eq!(next_v7_state(previous, 30, 7), previous + 1);
373    }
374
375    #[test]
376    fn counter_overflow_advances_the_timestamp_field() {
377        let previous = 42 << COUNTER_BITS | COUNTER_MASK;
378
379        assert_eq!(next_v7_state(previous, 42, 7), 43 << COUNTER_BITS);
380    }
381
382    #[test]
383    fn serde_uses_the_hyphenated_string() {
384        let id: Uuid = RFC_V7.parse().unwrap();
385
386        let json = serde_json::to_string(&id).unwrap();
387        let owned: Uuid = serde_json::from_value(serde_json::Value::String(RFC_V7.into())).unwrap();
388
389        assert_eq!(json, format!("\"{RFC_V7}\""));
390        assert_eq!(serde_json::from_str::<Uuid>(&json).unwrap(), id);
391        assert_eq!(owned, id);
392        assert!(serde_json::from_str::<Uuid>("\"not a uuid\"").is_err());
393        assert!(serde_json::from_str::<Uuid>("42").is_err());
394    }
395}
sofie_core/uuid.rs

sofie_core/
uuid.rs
