Skip to main content

uuid/
timestamp.rs

1//! Generating UUIDs from timestamps.
2//!
3//! Timestamps are used in a few UUID versions as a source of decentralized
4//! uniqueness (as in versions 1 and 6), and as a way to enable sorting (as
5//! in versions 6 and 7). Timestamps aren't encoded the same way by all UUID
6//! versions so this module provides a single [`Timestamp`] type that can
7//! convert between them.
8//!
9//! # Timestamp representations in UUIDs
10//!
11//! Versions 1 and 6 UUIDs use a bespoke timestamp that consists of the
12//! number of 100ns ticks since `1582-10-15 00:00:00`, along with
13//! a counter value to avoid duplicates.
14//!
15//! Version 7 UUIDs use a more standard timestamp that consists of the
16//! number of millisecond ticks since the Unix epoch (`1970-01-01 00:00:00`).
17//!
18//! # References
19//!
20//! * [UUID Version 1 in RFC 9562](https://www.ietf.org/rfc/rfc9562.html#section-5.1)
21//! * [UUID Version 7 in RFC 9562](https://www.ietf.org/rfc/rfc9562.html#section-5.7)
22//! * [Timestamp Considerations in RFC 9562](https://www.ietf.org/rfc/rfc9562.html#section-6.1)
23
24use core::cmp;
25
26use crate::Uuid;
27
28/// The number of 100 nanosecond ticks between the RFC 9562 epoch
29/// (`1582-10-15 00:00:00`) and the Unix epoch (`1970-01-01 00:00:00`).
30pub const UUID_TICKS_BETWEEN_EPOCHS: u64 = 0x01B2_1DD2_1381_4000;
31
32/// A timestamp that can be encoded into a UUID.
33///
34/// This type abstracts the specific encoding, so versions 1, 6, and 7
35/// UUIDs can both be supported through the same type, even
36/// though they have a different representation of a timestamp.
37///
38/// # References
39///
40/// * [Timestamp Considerations in RFC 9562](https://www.ietf.org/rfc/rfc9562.html#section-6.1)
41/// * [UUID Generator States in RFC 9562](https://www.ietf.org/rfc/rfc9562.html#section-6.3)
42#[derive(#[automatically_derived]impl ::core::fmt::Debug for Timestamp {
    #[inline]
    #[rustc_trivial_field_reads]
    fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
        ::core::fmt::Formatter::debug_struct_field3_finish(f,
            "Timestamp unix_nanos counter usable_counter_bits",
            &self.unix_nanos, &self.counter, &&self.usable_counter_bits)
    }
}Debug, #[automatically_derived]#[doc(hidden)]unsafe impl ::core::clone::TrivialClone
    for Timestamp {
}
#[automatically_derived]impl ::core::clone::Clone for Timestamp {
    #[inline]
    #[rustc_trivial_field_reads]
    fn clone(&self) -> Self {
        let _: ::core::clone::AssertParamIsClone<u128>;
        let _: ::core::clone::AssertParamIsClone<u8>;
        *self
    }
}Clone, #[automatically_derived]impl ::core::marker::Copy for Timestamp { }Copy, #[automatically_derived]impl ::core::marker::StructuralPartialEq for Timestamp
    {
}
#[automatically_derived]impl ::core::cmp::PartialEq for Timestamp {
    #[inline]
    fn eq(&self, other: &Self) -> bool {
        self.unix_nanos == other.unix_nanos && self.counter == other.counter
            && self.usable_counter_bits == other.usable_counter_bits
    }
}PartialEq, #[automatically_derived]impl ::core::cmp::Eq for Timestamp {
    #[inline]
    #[doc(hidden)]
    #[coverage(off)]
    fn assert_fields_are_eq(&self) {
        let _: ::core::cmp::AssertParamIsEq<u128>;
        let _: ::core::cmp::AssertParamIsEq<u8>;
    }
}Eq, #[automatically_derived]impl ::core::hash::Hash for Timestamp {
    #[inline]
    fn hash<__H: ::core::hash::Hasher>(&self, state: &mut __H) {
        ::core::hash::Hash::hash(&self.unix_nanos, state);
        ::core::hash::Hash::hash(&self.counter, state);
        ::core::hash::Hash::hash(&self.usable_counter_bits, state)
    }
}Hash)]
43pub struct Timestamp {
44    unix_nanos: u128,
45    counter: u128,
46    usable_counter_bits: u8,
47}
48
49impl Timestamp {
50    /// Get a timestamp representing the current system time and up to a 128-bit counter.
51    ///
52    /// This method defers to the standard library's `SystemTime` type.
53    #[cfg(feature = "std")]
54    pub fn now(context: impl ClockSequence<Output = impl Into<u128>>) -> Self {
55        let (seconds, subsec_nanos) = nanos_to_parts(now());
56
57        let (counter, seconds, subsec_nanos) =
58            context.generate_timestamp_sequence(seconds, subsec_nanos);
59        let counter = counter.into();
60        let usable_counter_bits = context.usable_bits() as u8;
61
62        Timestamp {
63            unix_nanos: parts_to_nanos(seconds, subsec_nanos),
64            counter,
65            usable_counter_bits,
66        }
67    }
68
69    /// Construct a `Timestamp` from the number of 100 nanosecond ticks since 00:00:00.00,
70    /// 15 October 1582 (the date of Gregorian reform to the Christian calendar) and a 14-bit
71    /// counter, as used in versions 1 and 6 UUIDs.
72    ///
73    /// # Overflow
74    ///
75    /// If conversion from RFC 9562 ticks to the internal timestamp format would overflow
76    /// it will wrap.
77    pub const fn from_gregorian_time(ticks: u64, counter: u16) -> Self {
78        let (seconds, subsec_nanos) = Self::gregorian_to_unix(ticks);
79
80        Timestamp {
81            unix_nanos: parts_to_nanos(seconds, subsec_nanos),
82            counter: counter as u128,
83            usable_counter_bits: 14,
84        }
85    }
86
87    /// Construct a `Timestamp` from a Unix timestamp and up to a 128-bit counter, as used in version 7 UUIDs.
88    pub const fn from_unix_time(
89        seconds: u64,
90        subsec_nanos: u32,
91        counter: u128,
92        usable_counter_bits: u8,
93    ) -> Self {
94        Timestamp {
95            unix_nanos: parts_to_nanos(seconds, subsec_nanos),
96            counter,
97            usable_counter_bits,
98        }
99    }
100
101    /// Construct a `Timestamp` from a Unix timestamp and up to a 128-bit counter, as used in version 7 UUIDs.
102    pub fn from_unix(
103        context: impl ClockSequence<Output = impl Into<u128>>,
104        seconds: u64,
105        subsec_nanos: u32,
106    ) -> Self {
107        let (counter, seconds, subsec_nanos) =
108            context.generate_timestamp_sequence(seconds, subsec_nanos);
109        let counter = counter.into();
110        let usable_counter_bits = context.usable_bits() as u8;
111
112        Timestamp {
113            unix_nanos: parts_to_nanos(seconds, subsec_nanos),
114            counter,
115            usable_counter_bits,
116        }
117    }
118
119    /// Get the value of the timestamp as the number of 100 nanosecond ticks since 00:00:00.00,
120    /// 15 October 1582 and a 14-bit counter, as used in versions 1 and 6 UUIDs.
121    ///
122    /// # Overflow
123    ///
124    /// If conversion from the internal timestamp format to ticks would overflow
125    /// then it will wrap.
126    ///
127    /// If the internal counter is wider than 14 bits then it will be truncated to 14 bits.
128    pub const fn to_gregorian(&self) -> (u64, u16) {
129        let (seconds, subsec_nanos) = nanos_to_parts(self.unix_nanos);
130
131        (
132            Self::unix_to_gregorian_ticks(seconds, subsec_nanos),
133            (self.counter as u16) & 0x3FFF,
134        )
135    }
136
137    // NOTE: This method is not public; the usable counter bits are lost in a version 7 UUID
138    // so can't be reliably recovered.
139    #[cfg(feature = "v7")]
140    pub(crate) const fn counter(&self) -> (u128, u8) {
141        (self.counter, self.usable_counter_bits)
142    }
143
144    /// Get the value of the timestamp as a Unix timestamp, as used in version 7 UUIDs.
145    pub const fn to_unix(&self) -> (u64, u32) {
146        nanos_to_parts(self.unix_nanos)
147    }
148
149    const fn unix_to_gregorian_ticks(seconds: u64, nanos: u32) -> u64 {
150        UUID_TICKS_BETWEEN_EPOCHS
151            .wrapping_add(seconds.wrapping_mul(10_000_000))
152            .wrapping_add(nanos as u64 / 100)
153    }
154
155    const fn gregorian_to_unix(ticks: u64) -> (u64, u32) {
156        (
157            ticks.wrapping_sub(UUID_TICKS_BETWEEN_EPOCHS) / 10_000_000,
158            (ticks.wrapping_sub(UUID_TICKS_BETWEEN_EPOCHS) % 10_000_000) as u32 * 100,
159        )
160    }
161}
162
163#[doc(hidden)]
164impl Timestamp {
165    #[deprecated(
166        since = "1.10.0",
167        note = "use `Timestamp::from_gregorian_time(ticks, counter)`"
168    )]
169    pub const fn from_rfc4122(ticks: u64, counter: u16) -> Self {
170        Timestamp::from_gregorian_time(ticks, counter)
171    }
172
173    #[deprecated(since = "1.10.0", note = "use `Timestamp::to_gregorian()`")]
174    pub const fn to_rfc4122(&self) -> (u64, u16) {
175        self.to_gregorian()
176    }
177
178    #[deprecated(
179        since = "1.2.0",
180        note = "`Timestamp::to_unix_nanos()` is deprecated and will be removed: use `Timestamp::to_unix()`"
181    )]
182    pub const fn to_unix_nanos(&self) -> u32 {
183        {
    ::core::panicking::panic_fmt(format_args!("`Timestamp::to_unix_nanos()` is deprecated and will be removed: use `Timestamp::to_unix()`"));
}panic!("`Timestamp::to_unix_nanos()` is deprecated and will be removed: use `Timestamp::to_unix()`")
184    }
185
186    #[deprecated(
187        since = "1.23.0",
188        note = "use `Timestamp::from_gregorian_time(ticks, counter)`"
189    )]
190    pub const fn from_gregorian(ticks: u64, counter: u16) -> Self {
191        Timestamp::from_gregorian_time(ticks, counter)
192    }
193}
194
195#[cfg(feature = "std")]
196impl TryFrom<std::time::SystemTime> for Timestamp {
197    type Error = crate::Error;
198
199    /// Perform the conversion.
200    ///
201    /// This method will fail if the system time is earlier than the Unix Epoch.
202    /// On some platforms it may panic instead.
203    fn try_from(st: std::time::SystemTime) -> Result<Self, Self::Error> {
204        let dur = st.duration_since(std::time::UNIX_EPOCH).map_err(|_| {
205            crate::Error(crate::error::ErrorKind::InvalidSystemTime(
206                "unable to convert the system tie into a Unix timestamp",
207            ))
208        })?;
209
210        Ok(Self::from_unix_time(
211            dur.as_secs(),
212            dur.subsec_nanos(),
213            0,
214            0,
215        ))
216    }
217}
218
219#[cfg(feature = "std")]
220impl From<Timestamp> for std::time::SystemTime {
221    /// Perform the conversion.
222    ///
223    /// If the conversion would fail, an undefined `SystemTime` will be returned instead.
224    /// This can happen if the `Timestamp` would overflow the max value allowed by `SystemTime` on the target platform.
225    /// Use `TryFrom` to catch conversion failures and handle them explicitly.
226    fn from(ts: Timestamp) -> Self {
227        let (seconds, subsec_nanos) = ts.to_unix();
228
229        // NOTE: The actual value on overflow is undefined and may change
230        // See: https://github.com/rust-lang/rust/issues/151199
231        std::time::Duration::from_secs(seconds)
232            .checked_add(std::time::Duration::from_nanos(subsec_nanos as u64))
233            .and_then(|dur| Self::UNIX_EPOCH.checked_add(dur))
234            .unwrap_or(std::time::SystemTime::UNIX_EPOCH)
235    }
236}
237
238pub(crate) const fn encode_gregorian_timestamp(
239    ticks: u64,
240    counter: u16,
241    node_id: &[u8; 6],
242) -> Uuid {
243    let time_low = (ticks & 0xFFFF_FFFF) as u32;
244    let time_mid = ((ticks >> 32) & 0xFFFF) as u16;
245    let time_high_and_version = (((ticks >> 48) & 0x0FFF) as u16) | (1 << 12);
246
247    let mut d4 = [0; 8];
248
249    d4[0] = (((counter & 0x3F00) >> 8) as u8) | 0x80;
250    d4[1] = (counter & 0xFF) as u8;
251    d4[2] = node_id[0];
252    d4[3] = node_id[1];
253    d4[4] = node_id[2];
254    d4[5] = node_id[3];
255    d4[6] = node_id[4];
256    d4[7] = node_id[5];
257
258    Uuid::from_fields(time_low, time_mid, time_high_and_version, &d4)
259}
260
261pub(crate) const fn decode_gregorian_timestamp(uuid: &Uuid) -> (u64, u16) {
262    let bytes = uuid.as_bytes();
263
264    let ticks: u64 = ((bytes[6] & 0x0F) as u64) << 56
265        | (bytes[7] as u64) << 48
266        | (bytes[4] as u64) << 40
267        | (bytes[5] as u64) << 32
268        | (bytes[0] as u64) << 24
269        | (bytes[1] as u64) << 16
270        | (bytes[2] as u64) << 8
271        | (bytes[3] as u64);
272
273    let counter: u16 = ((bytes[8] & 0x3F) as u16) << 8 | (bytes[9] as u16);
274
275    (ticks, counter)
276}
277
278pub(crate) const fn encode_sorted_gregorian_timestamp(
279    ticks: u64,
280    counter: u16,
281    node_id: &[u8; 6],
282) -> Uuid {
283    let time_high = ((ticks >> 28) & 0xFFFF_FFFF) as u32;
284    let time_mid = ((ticks >> 12) & 0xFFFF) as u16;
285    let time_low_and_version = ((ticks & 0x0FFF) as u16) | (0x6 << 12);
286
287    let mut d4 = [0; 8];
288
289    d4[0] = (((counter & 0x3F00) >> 8) as u8) | 0x80;
290    d4[1] = (counter & 0xFF) as u8;
291    d4[2] = node_id[0];
292    d4[3] = node_id[1];
293    d4[4] = node_id[2];
294    d4[5] = node_id[3];
295    d4[6] = node_id[4];
296    d4[7] = node_id[5];
297
298    Uuid::from_fields(time_high, time_mid, time_low_and_version, &d4)
299}
300
301pub(crate) const fn decode_sorted_gregorian_timestamp(uuid: &Uuid) -> (u64, u16) {
302    let bytes = uuid.as_bytes();
303
304    let ticks: u64 = ((bytes[0]) as u64) << 52
305        | (bytes[1] as u64) << 44
306        | (bytes[2] as u64) << 36
307        | (bytes[3] as u64) << 28
308        | (bytes[4] as u64) << 20
309        | (bytes[5] as u64) << 12
310        | ((bytes[6] & 0xF) as u64) << 8
311        | (bytes[7] as u64);
312
313    let counter: u16 = ((bytes[8] & 0x3F) as u16) << 8 | (bytes[9] as u16);
314
315    (ticks, counter)
316}
317
318pub(crate) const fn encode_unix_timestamp_millis(
319    millis: u64,
320    counter_random_bytes: &[u8; 10],
321) -> Uuid {
322    let millis_high = ((millis >> 16) & 0xFFFF_FFFF) as u32;
323    let millis_low = (millis & 0xFFFF) as u16;
324
325    let counter_random_version = (counter_random_bytes[1] as u16
326        | ((counter_random_bytes[0] as u16) << 8) & 0x0FFF)
327        | (0x7 << 12);
328
329    let mut d4 = [0; 8];
330
331    d4[0] = (counter_random_bytes[2] & 0x3F) | 0x80;
332    d4[1] = counter_random_bytes[3];
333    d4[2] = counter_random_bytes[4];
334    d4[3] = counter_random_bytes[5];
335    d4[4] = counter_random_bytes[6];
336    d4[5] = counter_random_bytes[7];
337    d4[6] = counter_random_bytes[8];
338    d4[7] = counter_random_bytes[9];
339
340    Uuid::from_fields(millis_high, millis_low, counter_random_version, &d4)
341}
342
343pub(crate) const fn decode_unix_timestamp_millis(uuid: &Uuid) -> u64 {
344    let bytes = uuid.as_bytes();
345
346    let millis: u64 = (bytes[0] as u64) << 40
347        | (bytes[1] as u64) << 32
348        | (bytes[2] as u64) << 24
349        | (bytes[3] as u64) << 16
350        | (bytes[4] as u64) << 8
351        | (bytes[5] as u64);
352
353    millis
354}
355
356#[cfg(all(
357    feature = "std",
358    feature = "js",
359    all(target_family = "wasm", any(target_os = "unknown", target_os = "none"))
360))]
361fn now() -> u128 {
362    use wasm_bindgen::prelude::*;
363
364    #[wasm_bindgen]
365    extern "C" {
366        // NOTE: This signature works around https://bugzilla.mozilla.org/show_bug.cgi?id=1787770
367        #[wasm_bindgen(js_namespace = Date, catch)]
368        fn now() -> Result<f64, JsValue>;
369    }
370
371    let now = now().unwrap_throw();
372
373    (now * 1_000_000.0) as u128
374}
375
376#[cfg(all(
377    feature = "std",
378    not(miri),
379    any(
380        not(feature = "js"),
381        not(all(target_family = "wasm", any(target_os = "unknown", target_os = "none")))
382    )
383))]
384fn now() -> u128 {
385    let dur = std::time::SystemTime::UNIX_EPOCH.elapsed().expect(
386        "Getting elapsed time since UNIX_EPOCH. If this fails, we've somehow violated causality",
387    );
388
389    dur.as_nanos()
390}
391
392#[cfg(all(feature = "std", miri))]
393fn now() -> u128 {
394    use std::{sync::Mutex, time::Duration};
395
396    static TS: Mutex<u128> = Mutex::new(0);
397
398    let mut ts = TS.lock().unwrap();
399    *ts += 1;
400    *ts
401}
402
403/**
404Convert a 128bit nanosecond value into a pair of 64bit seconds, and 32bit subsecond nanos.
405
406The 32bit subsecond nano value is normalized to be less than `1_000_000_000` wherever the 64bit
407seconds can hold the carry. Above `(u64::MAX, 999_999_999)` the remainder is left in the subsecond
408nanos instead, so every value produced by `parts_to_nanos` converts back exactly.
409
410Only values beyond `(u64::MAX, u32::MAX)` saturate to it. A `Timestamp` never holds one.
411*/
412const fn nanos_to_parts(nanos: u128) -> (u64, u32) {
413    const MAX_NANOS: u128 = parts_to_nanos(u64::MAX, u32::MAX);
414
415    if nanos > MAX_NANOS {
416        return (u64::MAX, u32::MAX);
417    }
418
419    let secs = nanos / 1_000_000_000;
420
421    if secs > u64::MAX as u128 {
422        // Seconds can't take the carry, so leave the rest in the subsecond nanos (at most `u32::MAX`)
423        (u64::MAX, (nanos - u64::MAX as u128 * 1_000_000_000) as u32)
424    } else {
425        (secs as u64, (nanos % 1_000_000_000) as u32)
426    }
427}
428
429/**
430Convert a potentially un-normalized part of 64bit seconds and 32bit subsecond nanos to a single
431128bit number of nanoseconds.
432
433This function will never overflow. `subsec_nanos` isn't required to be less than `1_000_000_000`.
434*/
435const fn parts_to_nanos(secs: u64, subsec_nanos: u32) -> u128 {
436    (secs as u128 * 1_000_000_000) + subsec_nanos as u128
437}
438
439/// A counter that can be used by versions 1 and 6 UUIDs to support
440/// the uniqueness of timestamps.
441///
442/// # References
443///
444/// * [UUID Version 1 in RFC 9562](https://www.ietf.org/rfc/rfc9562.html#section-5.1)
445/// * [UUID Version 6 in RFC 9562](https://www.ietf.org/rfc/rfc9562.html#section-5.6)
446/// * [UUID Generator States in RFC 9562](https://www.ietf.org/rfc/rfc9562.html#section-6.3)
447pub trait ClockSequence {
448    /// The type of sequence returned by this counter.
449    type Output;
450
451    /// Get the next value in the sequence to feed into a timestamp.
452    ///
453    /// This method will be called each time a [`Timestamp`] is constructed.
454    ///
455    /// Any bits beyond [`ClockSequence::usable_bits`] in the output must be unset.
456    ///
457    /// Note that a caller is not required to pass normalized values, so `subsec_nanos` may
458    /// be greater than the actual number of nanoseconds in a second (1,000,000,000).
459    /// Implementations are also not required to return normalized values, but values
460    /// outside the range supported by a given UUID variant may weaken uniqueness or monotonicity.
461    fn generate_sequence(&self, seconds: u64, subsec_nanos: u32) -> Self::Output;
462
463    /// Get the next value in the sequence, potentially also adjusting the timestamp.
464    ///
465    /// This method should be preferred over `generate_sequence`.
466    ///
467    /// Any bits beyond [`ClockSequence::usable_bits`] in the output must be unset.
468    ///
469    /// Note that a caller is not required to pass normalized values, so `subsec_nanos` may
470    /// be greater than the actual number of nanoseconds in a second (1,000,000,000).
471    /// Implementations are also not required to return normalized values, but values
472    /// outside the range supported by a given UUID variant may weaken uniqueness or monotonicity.
473    ///
474    /// The returned timestamp isn't required to be normalized either. Any `(seconds, subsec_nanos)`
475    /// value is preserved exactly by [`Timestamp`], and [`Timestamp::to_unix`] normalizes it where possible.
476    fn generate_timestamp_sequence(
477        &self,
478        seconds: u64,
479        subsec_nanos: u32,
480    ) -> (Self::Output, u64, u32) {
481        (
482            self.generate_sequence(seconds, subsec_nanos),
483            seconds,
484            subsec_nanos,
485        )
486    }
487
488    /// The number of usable bits from the least significant bit in the result of [`ClockSequence::generate_sequence`]
489    /// or [`ClockSequence::generate_timestamp_sequence`].
490    ///
491    /// The number of usable bits must not exceed 128.
492    ///
493    /// The number of usable bits is not expected to change between calls. An implementation of `ClockSequence` should
494    /// always return the same value from this method.
495    fn usable_bits(&self) -> usize
496    where
497        Self::Output: Sized,
498    {
499        cmp::min(128, core::mem::size_of::<Self::Output>() * 8)
500    }
501}
502
503impl<T: ClockSequence + ?Sized> ClockSequence for &T {
504    type Output = T::Output;
505
506    fn generate_sequence(&self, seconds: u64, subsec_nanos: u32) -> Self::Output {
507        (**self).generate_sequence(seconds, subsec_nanos)
508    }
509
510    fn generate_timestamp_sequence(
511        &self,
512        seconds: u64,
513        subsec_nanos: u32,
514    ) -> (Self::Output, u64, u32) {
515        (**self).generate_timestamp_sequence(seconds, subsec_nanos)
516    }
517
518    fn usable_bits(&self) -> usize
519    where
520        Self::Output: Sized,
521    {
522        (**self).usable_bits()
523    }
524}
525
526/// Default implementations for the [`ClockSequence`] trait.
527pub mod context {
528    use super::ClockSequence;
529
530    #[cfg(any(feature = "v1", feature = "v6"))]
531    mod v1_support {
532        use super::*;
533
534        #[cfg(all(feature = "std", feature = "rng"))]
535        use crate::std::sync::LazyLock;
536
537        #[cfg(all(feature = "std", feature = "rng"))]
538        static CONTEXT: LazyLock<ContextV1> = LazyLock::new(ContextV1::new_random);
539
540        #[cfg(all(feature = "std", feature = "rng"))]
541        pub(crate) fn shared_context_v1() -> &'static ContextV1 {
542            &CONTEXT
543        }
544
545        /// An internally synchronized, wrapping counter that produces 14-bit values for version 1 and version 6 UUIDs.
546        ///
547        /// This type is:
548        ///
549        /// - **Non-reseeding:** The counter is not reseeded on each time interval (100ns).
550        /// - **Non-adjusting:** The timestamp is not incremented when the counter wraps within a time interval (100ns).
551        /// - **Thread-safe:** The underlying counter is atomic, so can be shared across threads.
552        ///
553        /// This type should be used when constructing versions 1 and 6 UUIDs.
554        ///
555        /// This type should not be used when constructing version 7 UUIDs. When used to
556        /// construct a version 7 UUID, the 14-bit counter will be padded with random data.
557        /// Counter overflows are more likely with a 14-bit counter than they are with a
558        /// 42-bit counter when working at millisecond precision. This type doesn't attempt
559        /// to adjust the timestamp on overflow.
560        #[derive(Debug)]
561        pub struct ContextV1 {
562            count: AtomicU16,
563        }
564
565        impl ContextV1 {
566            /// Construct a new context that's initialized with the given value.
567            ///
568            /// The starting value should be a random number, so that UUIDs from
569            /// different systems with the same timestamps are less likely to collide.
570            /// When the `rng` feature is enabled, prefer the [`ContextV1::new_random`] method.
571            pub const fn new(count: u16) -> Self {
572                Self {
573                    count: AtomicU16::new(count),
574                }
575            }
576
577            /// Construct a new context that's initialized with a random value.
578            #[cfg(feature = "rng")]
579            pub fn new_random() -> Self {
580                Self {
581                    count: AtomicU16::new(crate::rng::u16()),
582                }
583            }
584        }
585
586        impl ClockSequence for ContextV1 {
587            type Output = u16;
588
589            fn generate_sequence(&self, _seconds: u64, _nanos: u32) -> Self::Output {
590                // RFC 9562 reserves 2 bits of the clock sequence so the actual
591                // maximum value is smaller than `u16::MAX`. Since we unconditionally
592                // increment the clock sequence we want to wrap once it becomes larger
593                // than what we can represent in a "u14". Otherwise there'd be patches
594                // where the clock sequence doesn't change regardless of the timestamp
595                fetch_increment(&self.count) & (u16::MAX >> 2)
596            }
597
598            fn usable_bits(&self) -> usize {
599                14
600            }
601        }
602
603        #[cfg(target_has_atomic = "16")]
604        type AtomicU16 = crate::std::sync::atomic::AtomicU16;
605        #[cfg(not(target_has_atomic = "16"))]
606        type AtomicU16 = crate::std::cell::Cell<u16>;
607
608        fn fetch_increment(slot: &AtomicU16) -> u16 {
609            #[cfg(target_has_atomic = "16")]
610            {
611                slot.fetch_add(1, crate::std::sync::atomic::Ordering::AcqRel)
612            }
613            #[cfg(not(target_has_atomic = "16"))]
614            {
615                slot.replace(slot.get().wrapping_add(1))
616            }
617        }
618
619        #[deprecated(since = "1.23.0", note = "renamed to `ContextV1`")]
620        #[doc(hidden)]
621        pub type Context = ContextV1;
622
623        #[cfg(test)]
624        mod tests {
625            use crate::Timestamp;
626
627            use super::*;
628
629            #[test]
630            fn context() {
631                let seconds = 1_496_854_535;
632                let subsec_nanos = 812_946_000;
633
634                let context = ContextV1::new(u16::MAX >> 2);
635
636                let ts = Timestamp::from_unix(&context, seconds, subsec_nanos);
637                assert_eq!(16383, ts.counter);
638                assert_eq!(14, ts.usable_counter_bits);
639
640                let seconds = 1_496_854_536;
641
642                let ts = Timestamp::from_unix(&context, seconds, subsec_nanos);
643                assert_eq!(0, ts.counter);
644
645                let seconds = 1_496_854_535;
646
647                let ts = Timestamp::from_unix(&context, seconds, subsec_nanos);
648                assert_eq!(1, ts.counter);
649            }
650
651            #[test]
652            fn context_overflow() {
653                let seconds = u64::MAX;
654                let subsec_nanos = u32::MAX;
655
656                let context = ContextV1::new(u16::MAX);
657
658                // Ensure we don't panic
659                Timestamp::from_unix(&context, seconds, subsec_nanos);
660            }
661        }
662    }
663
664    #[cfg(any(feature = "v1", feature = "v6"))]
665    pub use v1_support::*;
666
667    #[cfg(feature = "std")]
668    mod std_support {
669        use super::*;
670
671        use core::panic::{AssertUnwindSafe, RefUnwindSafe};
672        use std::{sync::Mutex, thread::LocalKey};
673
674        /// A wrapper for a context that uses thread-local storage.
675        pub struct ThreadLocalContext<C: 'static>(&'static LocalKey<C>);
676
677        impl<C> std::fmt::Debug for ThreadLocalContext<C> {
678            fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
679                f.debug_struct("ThreadLocalContext").finish_non_exhaustive()
680            }
681        }
682
683        impl<C: 'static> ThreadLocalContext<C> {
684            /// Wrap a thread-local container with a context.
685            pub const fn new(local_key: &'static LocalKey<C>) -> Self {
686                ThreadLocalContext(local_key)
687            }
688        }
689
690        impl<C: ClockSequence + 'static> ClockSequence for ThreadLocalContext<C> {
691            type Output = C::Output;
692
693            fn generate_sequence(&self, seconds: u64, subsec_nanos: u32) -> Self::Output {
694                self.0
695                    .with(|ctxt| ctxt.generate_sequence(seconds, subsec_nanos))
696            }
697
698            fn generate_timestamp_sequence(
699                &self,
700                seconds: u64,
701                subsec_nanos: u32,
702            ) -> (Self::Output, u64, u32) {
703                self.0
704                    .with(|ctxt| ctxt.generate_timestamp_sequence(seconds, subsec_nanos))
705            }
706
707            fn usable_bits(&self) -> usize {
708                self.0.with(|ctxt| ctxt.usable_bits())
709            }
710        }
711
712        impl<C: ClockSequence> ClockSequence for AssertUnwindSafe<C> {
713            type Output = C::Output;
714
715            fn generate_sequence(&self, seconds: u64, subsec_nanos: u32) -> Self::Output {
716                self.0.generate_sequence(seconds, subsec_nanos)
717            }
718
719            fn generate_timestamp_sequence(
720                &self,
721                seconds: u64,
722                subsec_nanos: u32,
723            ) -> (Self::Output, u64, u32) {
724                self.0.generate_timestamp_sequence(seconds, subsec_nanos)
725            }
726
727            fn usable_bits(&self) -> usize
728            where
729                Self::Output: Sized,
730            {
731                self.0.usable_bits()
732            }
733        }
734
735        impl<C: ClockSequence + RefUnwindSafe> ClockSequence for Mutex<C> {
736            type Output = C::Output;
737
738            fn generate_sequence(&self, seconds: u64, subsec_nanos: u32) -> Self::Output {
739                self.lock()
740                    .unwrap_or_else(|err| err.into_inner())
741                    .generate_sequence(seconds, subsec_nanos)
742            }
743
744            fn generate_timestamp_sequence(
745                &self,
746                seconds: u64,
747                subsec_nanos: u32,
748            ) -> (Self::Output, u64, u32) {
749                self.lock()
750                    .unwrap_or_else(|err| err.into_inner())
751                    .generate_timestamp_sequence(seconds, subsec_nanos)
752            }
753
754            fn usable_bits(&self) -> usize
755            where
756                Self::Output: Sized,
757            {
758                self.lock()
759                    .unwrap_or_else(|err| err.into_inner())
760                    .usable_bits()
761            }
762        }
763    }
764
765    #[cfg(feature = "std")]
766    pub use std_support::*;
767
768    #[cfg(feature = "v7")]
769    mod v7_support {
770        use super::*;
771
772        use crate::timestamp::parts_to_nanos;
773        use core::{cell::Cell, cmp, panic::RefUnwindSafe};
774
775        #[cfg(feature = "std")]
776        static CONTEXT_V7: SharedContextV7 =
777            SharedContextV7(std::sync::Mutex::new(ContextV7::new()));
778
779        #[cfg(feature = "std")]
780        pub(crate) fn shared_context_v7() -> &'static SharedContextV7 {
781            &CONTEXT_V7
782        }
783
784        const USABLE_BITS: usize = 42;
785
786        // Leave the most significant bit unset
787        // This guarantees the counter has at least 2,199,023,255,552
788        // values before it will overflow, which is exceptionally unlikely
789        // even in the worst case
790        const RESEED_MASK: u64 = u64::MAX >> 23;
791        const MAX_COUNTER: u64 = u64::MAX >> 22;
792
793        /// An unsynchronized, reseeding counter that produces 42-bit values for version 7 UUIDs.
794        ///
795        /// This type is:
796        ///
797        /// - **Reseeding:** The counter is reseeded on each time interval (1ms) with a random 41-bit value.
798        ///   The 42nd bit is left unset so the counter can safely increment over the millisecond.
799        /// - **Adjusting:** The timestamp is incremented when the counter wraps within a time interval (1ms).
800        ///   All subsequent timestamps in that same interval will also be incremented until it changes and
801        ///   the counter is reseeded.
802        /// - **Non-thread-safe:** The underlying counter uses unsynchronized cells, so needs to be wrapped in
803        ///   a mutex to share.
804        ///
805        /// The counter can use additional sub-millisecond precision from the timestamp to better
806        /// synchronize UUID sorting in distributed systems. In these cases, the additional precision
807        /// is masked into the left-most 12 bits of the counter. The counter is still reseeded on
808        /// each new millisecond, and incremented within the millisecond. This behavior may change
809        /// in the future. The only guarantee is monotonicity.
810        ///
811        /// This type can be used when constructing version 7 UUIDs. When used to construct a
812        /// version 7 UUID, the 42-bit counter will be padded with random data. This type can
813        /// be used to maintain ordering of UUIDs within the same millisecond.
814        ///
815        /// This type should not be used when constructing version 1 or version 6 UUIDs.
816        /// When used to construct a version 1 or version 6 UUID, only the 14 least significant
817        /// bits of the counter will be used.
818        #[derive(Debug, Default)]
819        pub struct ContextV7 {
820            timestamp: Cell<ReseedingTimestamp>,
821            counter: Cell<Counter>,
822            adjust: Adjust,
823            precision: Precision,
824        }
825
826        impl RefUnwindSafe for ContextV7 {}
827
828        impl ContextV7 {
829            /// Construct a new context that will reseed its counter on the first
830            /// non-zero timestamp it receives.
831            pub const fn new() -> Self {
832                ContextV7 {
833                    timestamp: Cell::new(ReseedingTimestamp {
834                        last_seed: 0,
835                        unix_nanos: 0,
836                    }),
837                    counter: Cell::new(Counter { value: 0 }),
838                    adjust: Adjust { by_ns: 0 },
839                    precision: Precision {
840                        bits: 0,
841                        mask: 0,
842                        factor: 0,
843                        shift: 0,
844                    },
845                }
846            }
847
848            /// Specify an amount to shift timestamps by to obfuscate their actual generation time.
849            pub fn with_adjust_by_millis(mut self, millis: u32) -> Self {
850                self.adjust = Adjust::by_millis(millis);
851                self
852            }
853
854            /// Use the leftmost 12 bits of the counter for additional timestamp precision.
855            ///
856            /// This method can provide better sorting for distributed applications that generate frequent UUIDs
857            /// by trading a small amount of entropy for better counter synchronization. Note that the counter
858            /// will still be reseeded on millisecond boundaries, even though some of its storage will be
859            /// dedicated to the timestamp.
860            pub fn with_additional_precision(self) -> Self {
861                self.with_additional_precision_bits(12)
862            }
863
864            /// Use the leftmost `bits` bits of the counter for additional timestamp precision.
865            ///
866            /// This is a more general form of [`ContextV7::with_additional_precision`] for platforms
867            /// whose clocks don't have the resolution to make use of the full 12 bits. A platform with
868            /// microsecond precision can set 10 bits here, leaving the remaining 2 bits of the `rand_a`
869            /// field free for random data.
870            ///
871            /// `bits` is capped at 12, matching the size of the `rand_a` field in a version 7 UUID.
872            /// Passing 0 disables additional precision, the same as never calling this method.
873            pub fn with_additional_precision_bits(mut self, bits: usize) -> Self {
874                self.precision = Precision::new(cmp::min(bits, 12));
875                self
876            }
877        }
878
879        impl ClockSequence for ContextV7 {
880            type Output = u64;
881
882            fn generate_sequence(&self, seconds: u64, subsec_nanos: u32) -> Self::Output {
883                self.generate_timestamp_sequence(seconds, subsec_nanos).0
884            }
885
886            fn generate_timestamp_sequence(
887                &self,
888                seconds: u64,
889                subsec_nanos: u32,
890            ) -> (Self::Output, u64, u32) {
891                let unix_nanos = self.adjust.apply(parts_to_nanos(seconds, subsec_nanos));
892
893                let mut counter;
894                let (mut timestamp, should_reseed) = self.timestamp.get().advance(unix_nanos);
895
896                if should_reseed {
897                    // If the observed system time has shifted forwards then regenerate the counter
898                    counter = Counter::reseed(&self.precision, &timestamp);
899                } else {
900                    // If the observed system time has not shifted forwards then increment the counter
901
902                    // If the incoming timestamp is earlier than the last observed one then
903                    // use it instead. This may happen if the system clock jitters, or if the counter
904                    // has wrapped and the timestamp is artificially incremented
905
906                    counter = self.counter.get().increment(&self.precision, &timestamp);
907
908                    // Unlikely: If the counter has overflowed its 42-bit storage then wrap it
909                    // and increment the timestamp. Until the observed system time shifts past
910                    // this incremented value, all timestamps will use it to maintain monotonicity
911                    if counter.has_overflowed() {
912                        // Increment the timestamp by 1 milli and reseed the counter
913                        timestamp = timestamp.increment();
914                        counter = Counter::reseed(&self.precision, &timestamp);
915                    }
916                };
917
918                self.timestamp.set(timestamp);
919                self.counter.set(counter);
920
921                let (seconds, subsec_nanos) = timestamp.to_parts();
922
923                (counter.value, seconds, subsec_nanos)
924            }
925
926            fn usable_bits(&self) -> usize {
927                USABLE_BITS
928            }
929        }
930
931        /// A timestamp that keeps track of whether a reseed is necessary.
932        #[derive(Debug, Default, Clone, Copy)]
933        struct ReseedingTimestamp {
934            last_seed: u64,
935            unix_nanos: u128,
936        }
937
938        impl ReseedingTimestamp {
939            #[inline]
940            fn saturating_from_unix_nanos(unix_nanos: u128) -> Self {
941                const MAX_UNIX_NANOS: u128 = (u64::MAX as u128) * 1_000_000 + 999_999;
942
943                let unix_nanos = cmp::min(unix_nanos, MAX_UNIX_NANOS);
944
945                // Reseed when the millisecond advances
946                let last_seed = (unix_nanos / 1_000_000) as u64;
947
948                ReseedingTimestamp {
949                    last_seed,
950                    unix_nanos,
951                }
952            }
953
954            #[inline]
955            fn to_parts(&self) -> (u64, u32) {
956                // Guaranteed never to overflow `(u64::MAX, 999_999_999)`
957                (
958                    (self.unix_nanos / 1_000_000_000) as u64,
959                    (self.unix_nanos % 1_000_000_000) as u32,
960                )
961            }
962
963            /// Advance the timestamp to a new value, returning whether a reseed is necessary.
964            #[inline]
965            fn advance(&self, unix_nanos: u128) -> (Self, bool) {
966                let incoming = ReseedingTimestamp::saturating_from_unix_nanos(unix_nanos);
967
968                (
969                    ReseedingTimestamp::saturating_from_unix_nanos(cmp::max(
970                        self.unix_nanos,
971                        unix_nanos,
972                    )),
973                    incoming.last_seed > self.last_seed,
974                )
975            }
976
977            /// Advance the timestamp by a millisecond.
978            #[inline]
979            fn increment(&self) -> Self {
980                ReseedingTimestamp::saturating_from_unix_nanos(
981                    Adjust::by_millis(1).apply(self.unix_nanos),
982                )
983            }
984        }
985
986        /// A counter that initializes to a safe random seed and tracks overflow.
987        #[derive(Debug, Default, Clone, Copy)]
988        struct Counter {
989            value: u64,
990        }
991
992        impl Counter {
993            #[inline]
994            fn reseed(precision: &Precision, timestamp: &ReseedingTimestamp) -> Self {
995                Counter {
996                    value: precision.apply(crate::rng::u64() & RESEED_MASK, timestamp),
997                }
998            }
999
1000            /// Advance the counter.
1001            ///
1002            /// This method is guaranteed to return a counter with a higher value than the current one.
1003            /// Additional precision from the timestamp will be used, unless it cause the counter
1004            /// to shift backwards.
1005            #[inline]
1006            fn increment(&self, precision: &Precision, timestamp: &ReseedingTimestamp) -> Self {
1007                // We unconditionally increment the counter even though the precision
1008                // may have set higher bits anyway. This could technically be avoided,
1009                // but the higher bits are a coarse approximation so we just avoid the
1010                // `if` branch and increment it either way
1011
1012                // Guaranteed to never overflow u64
1013                let next = self.value + 1;
1014
1015                Counter {
1016                    value: cmp::max(next, precision.apply(next, timestamp)),
1017                }
1018            }
1019
1020            #[inline]
1021            fn has_overflowed(&self) -> bool {
1022                self.value > MAX_COUNTER
1023            }
1024        }
1025
1026        /// A utility that adjusts an input timestamp by a given number of nanoseconds.
1027        #[derive(Debug, Default)]
1028        struct Adjust {
1029            by_ns: u128,
1030        }
1031
1032        impl Adjust {
1033            #[inline]
1034            fn by_millis(millis: u32) -> Self {
1035                Adjust {
1036                    by_ns: (millis as u128).saturating_mul(1_000_000),
1037                }
1038            }
1039
1040            /// Apply the adjustment, returning the adjusted timestamp.
1041            #[inline]
1042            fn apply(&self, nanos: u128) -> u128 {
1043                nanos.saturating_add(self.by_ns)
1044            }
1045        }
1046
1047        /// A utility that overwrites some number of counter bits with additional timestamp precision.
1048        #[derive(Debug, Default)]
1049        struct Precision {
1050            bits: usize,
1051            factor: u64,
1052            mask: u64,
1053            shift: u64,
1054        }
1055
1056        impl Precision {
1057            fn new(bits: usize) -> Self {
1058                // The mask and shift are used to paste the sub-millisecond precision
1059                // into the most significant bits of the counter
1060                let mask = u64::MAX >> (64 - USABLE_BITS + bits);
1061                let shift = (USABLE_BITS - bits) as u64;
1062
1063                // The factor reduces the size of the sub-millisecond precision to
1064                // fit into the specified number of bits
1065                let factor = (999_999 / u64::pow(2, bits as u32)) + 1;
1066
1067                Precision {
1068                    bits,
1069                    factor,
1070                    mask,
1071                    shift,
1072                }
1073            }
1074
1075            /// Apply additional precision from the given timestamp to the counter.
1076            #[inline]
1077            fn apply(&self, counter: u64, timestamp: &ReseedingTimestamp) -> u64 {
1078                if self.bits == 0 {
1079                    // No additional precision is being used
1080                    return counter;
1081                }
1082
1083                let additional = (timestamp.unix_nanos % 1_000_000) as u64 / self.factor;
1084
1085                (counter & self.mask) | (additional << self.shift)
1086            }
1087        }
1088
1089        #[cfg(feature = "std")]
1090        pub(crate) struct SharedContextV7(std::sync::Mutex<ContextV7>);
1091
1092        #[cfg(feature = "std")]
1093        impl ClockSequence for SharedContextV7 {
1094            type Output = u64;
1095
1096            fn generate_sequence(&self, seconds: u64, subsec_nanos: u32) -> Self::Output {
1097                self.0.generate_sequence(seconds, subsec_nanos)
1098            }
1099
1100            fn generate_timestamp_sequence(
1101                &self,
1102                seconds: u64,
1103                subsec_nanos: u32,
1104            ) -> (Self::Output, u64, u32) {
1105                self.0.generate_timestamp_sequence(seconds, subsec_nanos)
1106            }
1107
1108            fn usable_bits(&self) -> usize
1109            where
1110                Self::Output: Sized,
1111            {
1112                USABLE_BITS
1113            }
1114        }
1115
1116        #[cfg(test)]
1117        mod tests {
1118            use core::time::Duration;
1119            use std::boxed::Box;
1120
1121            use super::*;
1122
1123            use crate::{Timestamp, Uuid};
1124
1125            fn builder(f: impl Fn() -> ContextV7 + 'static) -> Box<dyn Fn() -> ContextV7> {
1126                Box::new(f)
1127            }
1128
1129            #[test]
1130            fn context() {
1131                let seconds = 1_496_854_535;
1132                let subsec_nanos = 812_946_000;
1133
1134                let context = ContextV7::new();
1135
1136                let ts1 = Timestamp::from_unix(&context, seconds, subsec_nanos);
1137                assert_eq!(42, ts1.usable_counter_bits);
1138
1139                // Backwards second
1140                let seconds = 1_496_854_534;
1141
1142                let ts2 = Timestamp::from_unix(&context, seconds, subsec_nanos);
1143
1144                // The backwards time should be ignored
1145                // The counter should still increment
1146                assert_eq!(ts1.unix_nanos, ts2.unix_nanos);
1147                assert_eq!(ts1.counter + 1, ts2.counter);
1148
1149                // Forwards second
1150                let seconds = 1_496_854_536;
1151
1152                let ts3 = Timestamp::from_unix(&context, seconds, subsec_nanos);
1153
1154                // The counter should have reseeded
1155                assert_ne!(ts2.counter + 1, ts3.counter);
1156                assert_ne!(0, ts3.counter);
1157            }
1158
1159            #[test]
1160            fn context_wrap() {
1161                let seconds = 1_496_854_535u64;
1162                let subsec_nanos = 812_946_000u32;
1163
1164                // This context will wrap
1165                let context = ContextV7 {
1166                    timestamp: Cell::new(ReseedingTimestamp::saturating_from_unix_nanos(
1167                        parts_to_nanos(seconds, subsec_nanos),
1168                    )),
1169                    adjust: Adjust::by_millis(0),
1170                    precision: Precision {
1171                        bits: 0,
1172                        mask: 0,
1173                        factor: 0,
1174                        shift: 0,
1175                    },
1176                    counter: Cell::new(Counter {
1177                        value: u64::MAX >> 22,
1178                    }),
1179                };
1180
1181                let ts = Timestamp::from_unix(&context, seconds, subsec_nanos);
1182
1183                // The timestamp should be incremented by 1ms
1184                let expected_ts = Duration::new(seconds, subsec_nanos) + Duration::from_millis(1);
1185                assert_eq!(expected_ts.as_secs(), ts.to_unix().0);
1186                assert_eq!(expected_ts.subsec_nanos(), ts.to_unix().1);
1187
1188                // The counter should have reseeded
1189                assert!(ts.counter < (u64::MAX >> 22) as u128);
1190                assert_ne!(0, ts.counter);
1191            }
1192
1193            #[test]
1194            fn context_shift() {
1195                let seconds = 1_496_854_535;
1196                let subsec_nanos = 812_946_000;
1197
1198                let context = ContextV7::new().with_adjust_by_millis(1);
1199
1200                let ts = Timestamp::from_unix(&context, seconds, subsec_nanos);
1201
1202                assert_eq!((1_496_854_535, 813_946_000), ts.to_unix());
1203            }
1204
1205            #[test]
1206            fn context_additional_precision() {
1207                let seconds = 1_496_854_535;
1208                let subsec_nanos = 812_946_000;
1209
1210                let context = ContextV7::new().with_additional_precision();
1211
1212                let ts1 = Timestamp::from_unix(&context, seconds, subsec_nanos);
1213
1214                // NOTE: Future changes in rounding may change this value slightly
1215                assert_eq!(3861, ts1.counter >> 30);
1216
1217                assert!(ts1.counter < (u64::MAX >> 22) as u128);
1218
1219                // Generate another timestamp; it should continue to sort
1220                let ts2 = Timestamp::from_unix(&context, seconds, subsec_nanos);
1221
1222                assert!(Uuid::new_v7(ts2) > Uuid::new_v7(ts1));
1223
1224                // Generate another timestamp with an extra nanosecond
1225                let subsec_nanos = subsec_nanos + 1;
1226
1227                let ts3 = Timestamp::from_unix(&context, seconds, subsec_nanos);
1228
1229                assert!(Uuid::new_v7(ts3) > Uuid::new_v7(ts2));
1230            }
1231
1232            #[test]
1233            fn context_additional_precision_bits() {
1234                let seconds = 1_496_854_535;
1235                let subsec_nanos = 812_946_000;
1236
1237                // 10 bits leaves the low 2 bits of `rand_a` for random data, which suits
1238                // platforms with microsecond precision
1239                let context = ContextV7::new().with_additional_precision_bits(10);
1240
1241                let ts = Timestamp::from_unix(&context, seconds, subsec_nanos);
1242
1243                // The submillisecond precision occupies the leftmost 10 of the 42 counter bits
1244                // NOTE: Future changes in rounding may change this value slightly
1245                assert_eq!(968, ts.counter >> 32);
1246
1247                assert!(ts.counter < (u64::MAX >> 22) as u128);
1248
1249                // The full method is just the 12-bit form of this one
1250                let full = Timestamp::from_unix(
1251                    &ContextV7::new().with_additional_precision(),
1252                    seconds,
1253                    subsec_nanos,
1254                );
1255                let bits12 = Timestamp::from_unix(
1256                    &ContextV7::new().with_additional_precision_bits(12),
1257                    seconds,
1258                    subsec_nanos,
1259                );
1260                assert_eq!(full.counter >> 30, bits12.counter >> 30);
1261
1262                // Values above 12 are capped at 12
1263                let capped = Timestamp::from_unix(
1264                    &ContextV7::new().with_additional_precision_bits(64),
1265                    seconds,
1266                    subsec_nanos,
1267                );
1268                assert_eq!(bits12.counter >> 30, capped.counter >> 30);
1269
1270                // Zero bits disables additional precision entirely
1271                let none = ContextV7::new().with_additional_precision_bits(0);
1272                assert_eq!(0, none.precision.bits);
1273            }
1274
1275            #[test]
1276            fn context_additional_precision_carry() {
1277                let seconds = 1_496_854_535;
1278                let subsec_nanos = 812_946_000;
1279
1280                for bits in 1..=12 {
1281                    let precision = Precision::new(bits);
1282                    let timestamp = ReseedingTimestamp::saturating_from_unix_nanos(parts_to_nanos(
1283                        seconds,
1284                        subsec_nanos,
1285                    ));
1286
1287                    // This context will carry into the additional precision
1288                    let context = ContextV7 {
1289                        counter: Cell::new(Counter {
1290                            value: precision.apply(u64::MAX, &timestamp),
1291                        }),
1292                        timestamp: Cell::new(timestamp),
1293                        adjust: Adjust::by_millis(0),
1294                        precision,
1295                    };
1296
1297                    let a = Timestamp::from_unix(&context, seconds, subsec_nanos);
1298                    let b = Timestamp::from_unix(&context, seconds, subsec_nanos);
1299                    let c = Timestamp::from_unix(&context, seconds, subsec_nanos);
1300
1301                    assert!(Uuid::new_v7(a) < Uuid::new_v7(b), "a: {a:?} < b: {b:?}");
1302                    assert!(Uuid::new_v7(b) < Uuid::new_v7(c), "b: {b:?} < c: {c:?}");
1303                }
1304            }
1305
1306            #[test]
1307            fn context_overflow() {
1308                let seconds = u64::MAX;
1309                let subsec_nanos = u32::MAX;
1310
1311                // Ensure we don't panic
1312                for context in [
1313                    builder(|| ContextV7::new()),
1314                    builder(|| ContextV7::new().with_additional_precision()),
1315                    builder(|| ContextV7::new().with_adjust_by_millis(u32::MAX)),
1316                    builder(|| {
1317                        ContextV7::new()
1318                            .with_additional_precision()
1319                            .with_adjust_by_millis(u32::MAX)
1320                    }),
1321                ] {
1322                    Timestamp::from_unix(&context(), seconds, subsec_nanos);
1323                }
1324            }
1325
1326            #[test]
1327            fn context_subsec_ordering() {
1328                for context in [
1329                    builder(|| ContextV7::new()),
1330                    builder(|| ContextV7::new().with_additional_precision()),
1331                    builder(|| ContextV7::new().with_adjust_by_millis(u32::MAX)),
1332                    builder(|| {
1333                        ContextV7::new()
1334                            .with_additional_precision()
1335                            .with_adjust_by_millis(u32::MAX)
1336                    }),
1337                ] {
1338                    for (a, b, c) in [
1339                        // Wall-clock order of incoming timestamps is b, a, c
1340                        ((100, 0), (99, 2_000_000), (100, 1_000_000)),
1341                        ((100, 0), (99, 1_000_900_000), (100, 1_000_000)),
1342                    ] {
1343                        let context = context();
1344
1345                        // UUID order is a, b, c
1346                        let a = Timestamp::from_unix(&context, a.0, a.1);
1347                        let b = Timestamp::from_unix(&context, b.0, b.1);
1348                        let c = Timestamp::from_unix(&context, c.0, c.1);
1349
1350                        assert!(Uuid::new_v7(a) < Uuid::new_v7(b), "a: {a:?} < b: {b:?}");
1351                        assert!(Uuid::new_v7(b) < Uuid::new_v7(c), "b: {b:?} < c: {c:?}");
1352                    }
1353                }
1354            }
1355
1356            #[test]
1357            fn context_subsec_saturated_ordering() {
1358                for context in [
1359                    builder(|| ContextV7::new()),
1360                    builder(|| ContextV7::new().with_additional_precision()),
1361                    builder(|| ContextV7::new().with_adjust_by_millis(u32::MAX)),
1362                    builder(|| {
1363                        ContextV7::new()
1364                            .with_additional_precision()
1365                            .with_adjust_by_millis(u32::MAX)
1366                    }),
1367                ] {
1368                    let context = context();
1369
1370                    let secs = (u64::MAX / 1_000) + 1;
1371
1372                    let a = Timestamp::from_unix(&context, secs, 900_000);
1373                    let b = Timestamp::from_unix(&context, secs, 1_000_000);
1374
1375                    assert!(Uuid::new_v7(a) < Uuid::new_v7(b), "a: {a:?} < b: {b:?}");
1376                }
1377            }
1378
1379            #[test]
1380            fn context_additional_precision_within_millisecond() {
1381                let seconds = 1_496_854_535;
1382                let subsec_nanos = 812_100_000;
1383
1384                let context = ContextV7::new().with_additional_precision();
1385
1386                let ts1 = Timestamp::from_unix(&context, seconds, subsec_nanos);
1387
1388                // Later in the same millisecond
1389                let ts2 = Timestamp::from_unix(&context, seconds, subsec_nanos + 500_000);
1390
1391                assert!(
1392                    ts2.counter >> 30 > ts1.counter >> 30,
1393                    "ts1: {ts1:?}, ts2: {ts2:?}"
1394                );
1395
1396                // Earlier in the same millisecond
1397                let ts3 = Timestamp::from_unix(&context, seconds, subsec_nanos);
1398
1399                assert_eq!(
1400                    ts2.counter >> 30,
1401                    ts3.counter >> 30,
1402                    "ts2: {ts2:?}, ts3: {ts3:?}"
1403                );
1404                assert_eq!(ts2.to_unix(), ts3.to_unix());
1405
1406                assert!(Uuid::new_v7(ts1) < Uuid::new_v7(ts2));
1407                assert!(Uuid::new_v7(ts2) < Uuid::new_v7(ts3));
1408            }
1409
1410            #[test]
1411            fn reseeding_timestamp_saturating() {
1412                const MAX_UNIX_NANOS: u128 = (u64::MAX as u128) * 1_000_000 + 999_999;
1413                const MAX_PARTS: (u64, u32) = (u64::MAX / 1_000, 615_999_999);
1414
1415                // Values at or below the ceiling pass through
1416                let below =
1417                    ReseedingTimestamp::saturating_from_unix_nanos(MAX_UNIX_NANOS - 1_000_000);
1418                assert_eq!(MAX_UNIX_NANOS - 1_000_000, below.unix_nanos);
1419                assert_eq!(u64::MAX - 1, below.last_seed);
1420                assert_eq!((u64::MAX / 1_000, 614_999_999), below.to_parts());
1421
1422                // Values beyond the ceiling are clamped to it
1423                for unix_nanos in [
1424                    MAX_UNIX_NANOS,
1425                    MAX_UNIX_NANOS + 1,
1426                    parts_to_nanos(u64::MAX / 1_000 + 1, 0),
1427                    parts_to_nanos(u64::MAX, 999_999_999),
1428                    parts_to_nanos(u64::MAX, u32::MAX),
1429                    u128::MAX,
1430                ] {
1431                    let ts = ReseedingTimestamp::saturating_from_unix_nanos(unix_nanos);
1432
1433                    assert_eq!(MAX_UNIX_NANOS, ts.unix_nanos, "{unix_nanos}");
1434                    assert_eq!(u64::MAX, ts.last_seed, "{unix_nanos}");
1435                    assert_eq!(MAX_PARTS, ts.to_parts(), "{unix_nanos}");
1436                }
1437
1438                // Incrementing at the ceiling stays there instead of wrapping
1439                let max = ReseedingTimestamp::saturating_from_unix_nanos(MAX_UNIX_NANOS);
1440                let incremented = max.increment();
1441                assert_eq!(MAX_UNIX_NANOS, incremented.unix_nanos);
1442                assert_eq!(u64::MAX, incremented.last_seed);
1443            }
1444
1445            #[test]
1446            fn context_saturated_parts() {
1447                const MAX_PARTS: (u64, u32) = (u64::MAX / 1_000, 615_999_999);
1448
1449                for context in [
1450                    builder(|| ContextV7::new()),
1451                    builder(|| ContextV7::new().with_adjust_by_millis(u32::MAX)),
1452                ] {
1453                    for (seconds, subsec_nanos) in [
1454                        MAX_PARTS,
1455                        (u64::MAX / 1_000 + 1, 0),
1456                        (u64::MAX, 999_999_999),
1457                        (u64::MAX, u32::MAX),
1458                    ] {
1459                        let ts = Timestamp::from_unix(&context(), seconds, subsec_nanos);
1460
1461                        assert_eq!(MAX_PARTS, ts.to_unix(), "{seconds}, {subsec_nanos}");
1462                    }
1463                }
1464
1465                // A counter overflow at the ceiling can't advance the timestamp, but it mustn't wrap it either
1466                let context = ContextV7 {
1467                    timestamp: Cell::new(ReseedingTimestamp::saturating_from_unix_nanos(u128::MAX)),
1468                    adjust: Adjust::by_millis(0),
1469                    precision: Precision::new(0),
1470                    counter: Cell::new(Counter {
1471                        value: u64::MAX >> 22,
1472                    }),
1473                };
1474
1475                let ts = Timestamp::from_unix(&context, u64::MAX, u32::MAX);
1476
1477                assert_eq!(MAX_PARTS, ts.to_unix());
1478            }
1479        }
1480    }
1481
1482    #[cfg(feature = "v7")]
1483    pub use v7_support::*;
1484
1485    /// An empty counter that will always return the value `0`.
1486    ///
1487    /// This type can be used when constructing version 7 UUIDs. When used to
1488    /// construct a version 7 UUID, the entire counter segment of the UUID will be
1489    /// filled with a random value. This type does not maintain ordering of UUIDs
1490    /// within a millisecond but is efficient.
1491    ///
1492    /// This type should not be used when constructing version 1 or version 6 UUIDs.
1493    /// When used to construct a version 1 or version 6 UUID, the counter
1494    /// segment will remain zero.
1495    #[derive(#[automatically_derived]impl ::core::fmt::Debug for NoContext {
    #[inline]
    #[rustc_trivial_field_reads]
    fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
        ::core::fmt::Formatter::write_str(f, "NoContext")
    }
}Debug, #[automatically_derived]#[doc(hidden)]unsafe impl ::core::clone::TrivialClone
    for NoContext {
}
#[automatically_derived]impl ::core::clone::Clone for NoContext {
    #[inline]
    #[rustc_trivial_field_reads]
    fn clone(&self) -> Self { *self }
}Clone, #[automatically_derived]impl ::core::marker::Copy for NoContext { }Copy, #[automatically_derived]impl ::core::default::Default for NoContext {
    #[inline]
    fn default() -> Self { NoContext {} }
}Default)]
1496    pub struct NoContext;
1497
1498    impl ClockSequence for NoContext {
1499        type Output = u16;
1500
1501        fn generate_sequence(&self, _seconds: u64, _nanos: u32) -> Self::Output {
1502            0
1503        }
1504
1505        fn usable_bits(&self) -> usize {
1506            0
1507        }
1508    }
1509}
1510
1511#[cfg(all(test, any(feature = "v1", feature = "v6")))]
1512mod tests {
1513    use super::*;
1514
1515    #[cfg(all(target_family = "wasm", any(target_os = "unknown", target_os = "none")))]
1516    use wasm_bindgen_test::*;
1517
1518    #[test]
1519    #[cfg_attr(
1520        all(target_family = "wasm", any(target_os = "unknown", target_os = "none")),
1521        wasm_bindgen_test
1522    )]
1523    fn gregorian_unix_does_not_panic() {
1524        // Ensure timestamp conversions never panic
1525        Timestamp::unix_to_gregorian_ticks(u64::MAX, 0);
1526        Timestamp::unix_to_gregorian_ticks(0, u32::MAX);
1527        Timestamp::unix_to_gregorian_ticks(u64::MAX, u32::MAX);
1528
1529        Timestamp::gregorian_to_unix(u64::MAX);
1530    }
1531
1532    #[test]
1533    #[cfg_attr(
1534        all(target_family = "wasm", any(target_os = "unknown", target_os = "none")),
1535        wasm_bindgen_test
1536    )]
1537    fn to_gregorian_truncates_to_usable_bits() {
1538        let ts = Timestamp::from_gregorian_time(123, u16::MAX);
1539
1540        assert_eq!((123, u16::MAX >> 2), ts.to_gregorian());
1541    }
1542
1543    #[test]
1544    #[cfg_attr(
1545        all(target_family = "wasm", any(target_os = "unknown", target_os = "none")),
1546        wasm_bindgen_test
1547    )]
1548    fn clock_sequence_usable_bits() {
1549        struct MyContext;
1550
1551        impl ClockSequence for MyContext {
1552            type Output = u16;
1553
1554            fn generate_sequence(&self, _: u64, _: u32) -> Self::Output {
1555                0
1556            }
1557        }
1558
1559        assert_eq!(16, MyContext.usable_bits());
1560    }
1561
1562    const MAX_PARTS_NANOS: u128 = (u64::MAX as u128) * 1_000_000_000 + 999_999_999;
1563
1564    #[test]
1565    fn nanos_to_parts_roundtrip() {
1566        for case in [
1567            0,
1568            1,
1569            999_999_999,
1570            1_000_000_000,
1571            u64::MAX as u128,
1572            u64::MAX as u128 + 1,
1573            u64::MAX as u128 + u32::MAX as u128,
1574            u64::MAX as u128 + u32::MAX as u128 + 1,
1575            (u64::MAX as u128) * 1_000_000 + 999_999,
1576            (u64::MAX as u128) * 1_000_000_000,
1577            MAX_PARTS_NANOS - 1,
1578            MAX_PARTS_NANOS,
1579        ] {
1580            let (seconds, subsec_nanos) = nanos_to_parts(case);
1581
1582            assert!(subsec_nanos < 1_000_000_000, "{case}");
1583            assert_eq!(case, parts_to_nanos(seconds, subsec_nanos), "{case}");
1584        }
1585    }
1586
1587    #[test]
1588    fn nanos_to_parts_unnormalized_roundtrip() {
1589        // Beyond the largest normalized value, seconds can't take the carry,
1590        // so the remainder stays in the subsecond nanos
1591        for (case, expected) in [
1592            (MAX_PARTS_NANOS + 1, (u64::MAX, 1_000_000_000)),
1593            (MAX_PARTS_NANOS + 2, (u64::MAX, 1_000_000_001)),
1594            (
1595                parts_to_nanos(u64::MAX, u32::MAX) - 1,
1596                (u64::MAX, u32::MAX - 1),
1597            ),
1598            (parts_to_nanos(u64::MAX, u32::MAX), (u64::MAX, u32::MAX)),
1599        ] {
1600            let (seconds, subsec_nanos) = nanos_to_parts(case);
1601
1602            assert_eq!(expected, (seconds, subsec_nanos), "{case}");
1603            assert_eq!(case, parts_to_nanos(seconds, subsec_nanos), "{case}");
1604        }
1605    }
1606
1607    #[test]
1608    fn nanos_to_parts_saturating() {
1609        for case in [parts_to_nanos(u64::MAX, u32::MAX) + 1, u128::MAX] {
1610            let (seconds, subsec_nanos) = nanos_to_parts(case);
1611
1612            assert_eq!(u64::MAX, seconds, "{case}");
1613            assert_eq!(u32::MAX, subsec_nanos, "{case}");
1614        }
1615    }
1616
1617    #[test]
1618    fn parts_to_nanos_unnormalized() {
1619        assert_eq!(2_500_000_000, parts_to_nanos(1, 1_500_000_000));
1620        assert_eq!(
1621            parts_to_nanos(2, 500_000_000),
1622            parts_to_nanos(1, 1_500_000_000)
1623        );
1624
1625        // The largest input doesn't overflow
1626        assert_eq!(
1627            (u64::MAX as u128) * 1_000_000_000 + u32::MAX as u128,
1628            parts_to_nanos(u64::MAX, u32::MAX)
1629        );
1630    }
1631
1632    #[test]
1633    fn timestamp_unix_parts_boundaries() {
1634        // Normalized values round-trip
1635        for (seconds, subsec_nanos) in [
1636            (0, 0),
1637            (1, 999_999_999),
1638            (u64::MAX, 0),
1639            (u64::MAX, 999_999_999),
1640        ] {
1641            let ts = Timestamp::from_unix_time(seconds, subsec_nanos, 0, 0);
1642
1643            assert_eq!((seconds, subsec_nanos), ts.to_unix());
1644        }
1645
1646        // Unnormalized values are normalized
1647        let ts = Timestamp::from_unix_time(1, 1_500_000_000, 0, 0);
1648        assert_eq!((2, 500_000_000), ts.to_unix());
1649
1650        // Values beyond the largest normalized are preserved
1651        for (seconds, subsec_nanos) in [(u64::MAX, 1_000_000_000), (u64::MAX, u32::MAX)] {
1652            let ts = Timestamp::from_unix_time(seconds, subsec_nanos, 0, 0);
1653
1654            assert_eq!((seconds, subsec_nanos), ts.to_unix());
1655        }
1656
1657        let ts = Timestamp::from_unix_time(u64::MAX - 1, u32::MAX, 0, 0);
1658        assert_eq!((u64::MAX, u32::MAX - 1_000_000_000), ts.to_unix());
1659    }
1660
1661    #[cfg(all(test, feature = "std", not(miri)))]
1662    mod std_support {
1663        use super::*;
1664
1665        use std::time::{Duration, SystemTime};
1666
1667        // Components of an arbitrary timestamp with non-zero nanoseconds.
1668        const KNOWN_SECONDS: u64 = 1_501_520_400;
1669        const KNOWN_NANOS: u32 = 1_000;
1670
1671        fn known_system_time() -> SystemTime {
1672            SystemTime::UNIX_EPOCH
1673                .checked_add(Duration::new(KNOWN_SECONDS, KNOWN_NANOS))
1674                .unwrap()
1675        }
1676
1677        fn known_timestamp() -> Timestamp {
1678            Timestamp::from_unix_time(KNOWN_SECONDS, KNOWN_NANOS, 0, 0)
1679        }
1680
1681        #[test]
1682        fn to_system_time() {
1683            let st: SystemTime = known_timestamp().into();
1684
1685            assert_eq!(known_system_time(), st);
1686        }
1687
1688        #[test]
1689        fn from_system_time() {
1690            let ts: Timestamp = known_system_time().try_into().unwrap();
1691
1692            assert_eq!(known_timestamp(), ts);
1693        }
1694
1695        #[test]
1696        fn from_system_time_before_epoch() {
1697            let before_epoch = match SystemTime::UNIX_EPOCH.checked_sub(Duration::from_nanos(1_000))
1698            {
1699                Some(st) => st,
1700                None => return,
1701            };
1702
1703            Timestamp::try_from(before_epoch)
1704                .expect_err("Timestamp should not be created from before epoch");
1705        }
1706
1707        #[test]
1708        fn from_system_time_max() {
1709            for (seconds, subsec_nanos) in [
1710                (u64::MAX, 999_999_999),
1711                (u64::MAX, 1_000_000_000),
1712                (u64::MAX, u32::MAX),
1713            ] {
1714                let ts = Timestamp::from_unix_time(seconds, subsec_nanos, 0, 0);
1715
1716                // Just make sure we don't panic
1717                let _: SystemTime = ts.into();
1718            }
1719        }
1720    }
1721}