sofie_core/
uuid.rs

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

sofie_core/
uuid.rs
