Adding upstream version 124.0.1.upstream/124.0.1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 409 insertions, 0 deletions

diff --git a/third_party/rust/uuid/src/timestamp.rs b/third_party/rust/uuid/src/timestamp.rs
new file mode 100644
index 0000000000..2f95ac4e93
--- /dev/null
+++ b/third_party/rust/uuid/src/timestamp.rs
@@ -0,0 +1,409 @@
+//! Generating UUIDs from timestamps.
+//!
+//! Timestamps are used in a few UUID versions as a source of decentralized
+//! uniqueness (as in versions 1 and 6), and as a way to enable sorting (as
+//! in versions 6 and 7). Timestamps aren't encoded the same way by all UUID
+//! versions so this module provides a single [`Timestamp`] type that can
+//! convert between them.
+//!
+//! # Timestamp representations in UUIDs
+//!
+//! Versions 1 and 6 UUIDs use a bespoke timestamp that consists of the
+//! number of 100ns ticks since `1582-10-15 00:00:00`, along with
+//! a counter value to avoid duplicates.
+//!
+//! Version 7 UUIDs use a more standard timestamp that consists of the
+//! number of millisecond ticks since the Unix epoch (`1970-01-01 00:00:00`).
+//!
+//! # References
+//!
+//! * [Timestamp in RFC4122](https://www.rfc-editor.org/rfc/rfc4122#section-4.1.4)
+//! * [Timestamp in Draft RFC: New UUID Formats, Version 4](https://datatracker.ietf.org/doc/html/draft-peabody-dispatch-new-uuid-format-04#section-6.1)
+
+use crate::Uuid;
+
+/// The number of 100 nanosecond ticks between the RFC4122 epoch
+/// (`1582-10-15 00:00:00`) and the Unix epoch (`1970-01-01 00:00:00`).
+pub const UUID_TICKS_BETWEEN_EPOCHS: u64 = 0x01B2_1DD2_1381_4000;
+
+/// A timestamp that can be encoded into a UUID.
+///
+/// This type abstracts the specific encoding, so versions 1, 6, and 7
+/// UUIDs can both be supported through the same type, even
+/// though they have a different representation of a timestamp.
+///
+/// # References
+///
+/// * [Timestamp in RFC4122](https://www.rfc-editor.org/rfc/rfc4122#section-4.1.4)
+/// * [Timestamp in Draft RFC: New UUID Formats, Version 4](https://datatracker.ietf.org/doc/html/draft-peabody-dispatch-new-uuid-format-04#section-6.1)
+/// * [Clock Sequence in RFC4122](https://datatracker.ietf.org/doc/html/rfc4122#section-4.1.5)
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub struct Timestamp {
+    pub(crate) seconds: u64,
+    pub(crate) nanos: u32,
+    #[cfg(any(feature = "v1", feature = "v6"))]
+    pub(crate) counter: u16,
+}
+
+impl Timestamp {
+    /// Get a timestamp representing the current system time.
+    ///
+    /// This method defers to the standard library's `SystemTime` type.
+    ///
+    /// # Panics
+    ///
+    /// This method will panic if calculating the elapsed time since the Unix epoch fails.
+    #[cfg(feature = "std")]
+    pub fn now(context: impl ClockSequence<Output = u16>) -> Self {
+        #[cfg(not(any(feature = "v1", feature = "v6")))]
+        {
+            let _ = context;
+        }
+
+        let (seconds, nanos) = now();
+
+        Timestamp {
+            seconds,
+            nanos,
+            #[cfg(any(feature = "v1", feature = "v6"))]
+            counter: context.generate_sequence(seconds, nanos),
+        }
+    }
+
+    /// Construct a `Timestamp` from an RFC4122 timestamp and counter, as used
+    /// in versions 1 and 6 UUIDs.
+    pub const fn from_rfc4122(ticks: u64, counter: u16) -> Self {
+        #[cfg(not(any(feature = "v1", feature = "v6")))]
+        {
+            let _ = counter;
+        }
+
+        let (seconds, nanos) = Self::rfc4122_to_unix(ticks);
+
+        Timestamp {
+            seconds,
+            nanos,
+            #[cfg(any(feature = "v1", feature = "v6"))]
+            counter,
+        }
+    }
+
+    /// Construct a `Timestamp` from a Unix timestamp, as used in version 7 UUIDs.
+    pub fn from_unix(context: impl ClockSequence<Output = u16>, seconds: u64, nanos: u32) -> Self {
+        #[cfg(not(any(feature = "v1", feature = "v6")))]
+        {
+            let _ = context;
+
+            Timestamp { seconds, nanos }
+        }
+        #[cfg(any(feature = "v1", feature = "v6"))]
+        {
+            let counter = context.generate_sequence(seconds, nanos);
+
+            Timestamp {
+                seconds,
+                nanos,
+                counter,
+            }
+        }
+    }
+
+    /// Get the value of the timestamp as an RFC4122 timestamp and counter,
+    /// as used in versions 1 and 6 UUIDs.
+    #[cfg(any(feature = "v1", feature = "v6"))]
+    pub const fn to_rfc4122(&self) -> (u64, u16) {
+        (
+            Self::unix_to_rfc4122_ticks(self.seconds, self.nanos),
+            self.counter,
+        )
+    }
+
+    /// Get the value of the timestamp as a Unix timestamp, as used in version 7 UUIDs.
+    pub const fn to_unix(&self) -> (u64, u32) {
+        (self.seconds, self.nanos)
+    }
+
+    #[cfg(any(feature = "v1", feature = "v6"))]
+    const fn unix_to_rfc4122_ticks(seconds: u64, nanos: u32) -> u64 {
+        let ticks = UUID_TICKS_BETWEEN_EPOCHS + seconds * 10_000_000 + nanos as u64 / 100;
+
+        ticks
+    }
+
+    const fn rfc4122_to_unix(ticks: u64) -> (u64, u32) {
+        (
+            (ticks - UUID_TICKS_BETWEEN_EPOCHS) / 10_000_000,
+            ((ticks - UUID_TICKS_BETWEEN_EPOCHS) % 10_000_000) as u32 * 100,
+        )
+    }
+
+    #[deprecated(note = "use `to_unix` instead")]
+    /// Get the number of fractional nanoseconds in the Unix timestamp.
+    ///
+    /// This method is deprecated and probably doesn't do what you're expecting it to.
+    /// It doesn't return the timestamp as nanoseconds since the Unix epoch, it returns
+    /// the fractional seconds of the timestamp.
+    pub const fn to_unix_nanos(&self) -> u32 {
+        // NOTE: This method never did what it said on the tin: instead of
+        // converting the timestamp into nanos it simply returned the nanoseconds
+        // part of the timestamp.
+        //
+        // We can't fix the behavior because the return type is too small to fit
+        // a useful value for nanoseconds since the epoch.
+        self.nanos
+    }
+}
+
+pub(crate) const fn encode_rfc4122_timestamp(ticks: u64, counter: u16, node_id: &[u8; 6]) -> Uuid {
+    let time_low = (ticks & 0xFFFF_FFFF) as u32;
+    let time_mid = ((ticks >> 32) & 0xFFFF) as u16;
+    let time_high_and_version = (((ticks >> 48) & 0x0FFF) as u16) | (1 << 12);
+
+    let mut d4 = [0; 8];
+
+    d4[0] = (((counter & 0x3F00) >> 8) as u8) | 0x80;
+    d4[1] = (counter & 0xFF) as u8;
+    d4[2] = node_id[0];
+    d4[3] = node_id[1];
+    d4[4] = node_id[2];
+    d4[5] = node_id[3];
+    d4[6] = node_id[4];
+    d4[7] = node_id[5];
+
+    Uuid::from_fields(time_low, time_mid, time_high_and_version, &d4)
+}
+
+pub(crate) const fn decode_rfc4122_timestamp(uuid: &Uuid) -> (u64, u16) {
+    let bytes = uuid.as_bytes();
+
+    let ticks: u64 = ((bytes[6] & 0x0F) as u64) << 56
+        | (bytes[7] as u64) << 48
+        | (bytes[4] as u64) << 40
+        | (bytes[5] as u64) << 32
+        | (bytes[0] as u64) << 24
+        | (bytes[1] as u64) << 16
+        | (bytes[2] as u64) << 8
+        | (bytes[3] as u64);
+
+    let counter: u16 = ((bytes[8] & 0x3F) as u16) << 8 | (bytes[9] as u16);
+
+    (ticks, counter)
+}
+
+#[cfg(uuid_unstable)]
+pub(crate) const fn encode_sorted_rfc4122_timestamp(
+    ticks: u64,
+    counter: u16,
+    node_id: &[u8; 6],
+) -> Uuid {
+    let time_high = ((ticks >> 28) & 0xFFFF_FFFF) as u32;
+    let time_mid = ((ticks >> 12) & 0xFFFF) as u16;
+    let time_low_and_version = ((ticks & 0x0FFF) as u16) | (0x6 << 12);
+
+    let mut d4 = [0; 8];
+
+    d4[0] = (((counter & 0x3F00) >> 8) as u8) | 0x80;
+    d4[1] = (counter & 0xFF) as u8;
+    d4[2] = node_id[0];
+    d4[3] = node_id[1];
+    d4[4] = node_id[2];
+    d4[5] = node_id[3];
+    d4[6] = node_id[4];
+    d4[7] = node_id[5];
+
+    Uuid::from_fields(time_high, time_mid, time_low_and_version, &d4)
+}
+
+#[cfg(uuid_unstable)]
+pub(crate) const fn decode_sorted_rfc4122_timestamp(uuid: &Uuid) -> (u64, u16) {
+    let bytes = uuid.as_bytes();
+
+    let ticks: u64 = ((bytes[0]) as u64) << 52
+        | (bytes[1] as u64) << 44
+        | (bytes[2] as u64) << 36
+        | (bytes[3] as u64) << 28
+        | (bytes[4] as u64) << 20
+        | (bytes[5] as u64) << 12
+        | ((bytes[6] & 0xF) as u64) << 8
+        | (bytes[7] as u64);
+
+    let counter: u16 = ((bytes[8] & 0x3F) as u16) << 8 | (bytes[9] as u16);
+
+    (ticks, counter)
+}
+
+#[cfg(uuid_unstable)]
+pub(crate) const fn encode_unix_timestamp_millis(millis: u64, random_bytes: &[u8; 10]) -> Uuid {
+    let millis_high = ((millis >> 16) & 0xFFFF_FFFF) as u32;
+    let millis_low = (millis & 0xFFFF) as u16;
+
+    let random_and_version =
+        (random_bytes[0] as u16 | ((random_bytes[1] as u16) << 8) & 0x0FFF) | (0x7 << 12);
+
+    let mut d4 = [0; 8];
+
+    d4[0] = (random_bytes[2] & 0x3F) | 0x80;
+    d4[1] = random_bytes[3];
+    d4[2] = random_bytes[4];
+    d4[3] = random_bytes[5];
+    d4[4] = random_bytes[6];
+    d4[5] = random_bytes[7];
+    d4[6] = random_bytes[8];
+    d4[7] = random_bytes[9];
+
+    Uuid::from_fields(millis_high, millis_low, random_and_version, &d4)
+}
+
+#[cfg(uuid_unstable)]
+pub(crate) const fn decode_unix_timestamp_millis(uuid: &Uuid) -> u64 {
+    let bytes = uuid.as_bytes();
+
+    let millis: u64 = (bytes[0] as u64) << 40
+        | (bytes[1] as u64) << 32
+        | (bytes[2] as u64) << 24
+        | (bytes[3] as u64) << 16
+        | (bytes[4] as u64) << 8
+        | (bytes[5] as u64);
+
+    millis
+}
+
+#[cfg(all(feature = "std", feature = "js", target_arch = "wasm32"))]
+fn now() -> (u64, u32) {
+    use wasm_bindgen::prelude::*;
+
+    #[wasm_bindgen]
+    extern "C" {
+        #[wasm_bindgen(js_namespace = Date)]
+        fn now() -> f64;
+    }
+
+    let now = now();
+
+    let secs = (now / 1_000.0) as u64;
+    let nanos = ((now % 1_000.0) * 1_000_000.0) as u32;
+
+    dbg!((secs, nanos))
+}
+
+#[cfg(all(feature = "std", any(not(feature = "js"), not(target_arch = "wasm32"))))]
+fn now() -> (u64, u32) {
+    let dur = std::time::SystemTime::UNIX_EPOCH
+        .elapsed()
+        .expect("Getting elapsed time since UNIX_EPOCH. If this fails, we've somehow violated causality");
+
+    (dur.as_secs(), dur.subsec_nanos())
+}
+
+/// A counter that can be used by version 1 and version 6 UUIDs to support
+/// the uniqueness of timestamps.
+///
+/// # References
+///
+/// * [Clock Sequence in RFC4122](https://datatracker.ietf.org/doc/html/rfc4122#section-4.1.5)
+pub trait ClockSequence {
+    /// The type of sequence returned by this counter.
+    type Output;
+
+    /// Get the next value in the sequence to feed into a timestamp.
+    ///
+    /// This method will be called each time a [`Timestamp`] is constructed.
+    fn generate_sequence(&self, seconds: u64, subsec_nanos: u32) -> Self::Output;
+}
+
+impl<'a, T: ClockSequence + ?Sized> ClockSequence for &'a T {
+    type Output = T::Output;
+    fn generate_sequence(&self, seconds: u64, subsec_nanos: u32) -> Self::Output {
+        (**self).generate_sequence(seconds, subsec_nanos)
+    }
+}
+
+/// Default implementations for the [`ClockSequence`] trait.
+pub mod context {
+    use super::ClockSequence;
+
+    #[cfg(any(feature = "v1", feature = "v6"))]
+    use atomic::{Atomic, Ordering};
+
+    /// An empty counter that will always return the value `0`.
+    ///
+    /// This type should be used when constructing timestamps for version 7 UUIDs,
+    /// since they don't need a counter for uniqueness.
+    #[derive(Debug, Clone, Copy, Default)]
+    pub struct NoContext;
+
+    impl ClockSequence for NoContext {
+        type Output = u16;
+
+        fn generate_sequence(&self, _seconds: u64, _nanos: u32) -> Self::Output {
+            0
+        }
+    }
+
+    #[cfg(all(any(feature = "v1", feature = "v6"), feature = "std", feature = "rng"))]
+    static CONTEXT: Context = Context {
+        count: Atomic::new(0),
+    };
+
+    #[cfg(all(any(feature = "v1", feature = "v6"), feature = "std", feature = "rng"))]
+    static CONTEXT_INITIALIZED: Atomic<bool> = Atomic::new(false);
+
+    #[cfg(all(any(feature = "v1", feature = "v6"), feature = "std", feature = "rng"))]
+    pub(crate) fn shared_context() -> &'static Context {
+        // If the context is in its initial state then assign it to a random value
+        // It doesn't matter if multiple threads observe `false` here and initialize the context
+        if CONTEXT_INITIALIZED
+            .compare_exchange(false, true, Ordering::Relaxed, Ordering::Relaxed)
+            .is_ok()
+        {
+            CONTEXT.count.store(crate::rng::u16(), Ordering::Release);
+        }
+
+        &CONTEXT
+    }
+
+    /// A thread-safe, wrapping counter that produces 14-bit numbers.
+    ///
+    /// This type should be used when constructing version 1 and version 6 UUIDs.
+    #[derive(Debug)]
+    #[cfg(any(feature = "v1", feature = "v6"))]
+    pub struct Context {
+        count: Atomic<u16>,
+    }
+
+    #[cfg(any(feature = "v1", feature = "v6"))]
+    impl Context {
+        /// Construct a new context that's initialized with the given value.
+        ///
+        /// The starting value should be a random number, so that UUIDs from
+        /// different systems with the same timestamps are less likely to collide.
+        /// When the `rng` feature is enabled, prefer the [`Context::new_random`] method.
+        pub const fn new(count: u16) -> Self {
+            Self {
+                count: Atomic::<u16>::new(count),
+            }
+        }
+
+        /// Construct a new context that's initialized with a random value.
+        #[cfg(feature = "rng")]
+        pub fn new_random() -> Self {
+            Self {
+                count: Atomic::<u16>::new(crate::rng::u16()),
+            }
+        }
+    }
+
+    #[cfg(any(feature = "v1", feature = "v6"))]
+    impl ClockSequence for Context {
+        type Output = u16;
+
+        fn generate_sequence(&self, _seconds: u64, _nanos: u32) -> Self::Output {
+            // RFC4122 reserves 2 bits of the clock sequence so the actual
+            // maximum value is smaller than `u16::MAX`. Since we unconditionally
+            // increment the clock sequence we want to wrap once it becomes larger
+            // than what we can represent in a "u14". Otherwise there'd be patches
+            // where the clock sequence doesn't change regardless of the timestamp
+            self.count.fetch_add(1, Ordering::AcqRel) % (u16::MAX >> 2)
+        }
+    }
+}