Adding upstream version 115.7.0esr.upstream/115.7.0esr

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

1 files changed, 706 insertions, 0 deletions

diff --git a/third_party/rust/fastrand/src/lib.rs b/third_party/rust/fastrand/src/lib.rs
new file mode 100644
index 0000000000..3f3ec3d9f4
--- /dev/null
+++ b/third_party/rust/fastrand/src/lib.rs
@@ -0,0 +1,706 @@
+//! A simple and fast random number generator.
+//!
+//! The implementation uses [Wyrand](https://github.com/wangyi-fudan/wyhash), a simple and fast
+//! generator but **not** cryptographically secure.
+//!
+//! # Examples
+//!
+//! Flip a coin:
+//!
+//! ```
+//! if fastrand::bool() {
+//!     println!("heads");
+//! } else {
+//!     println!("tails");
+//! }
+//! ```
+//!
+//! Generate a random `i32`:
+//!
+//! ```
+//! let num = fastrand::i32(..);
+//! ```
+//!
+//! Choose a random element in an array:
+//!
+//! ```
+//! let v = vec![1, 2, 3, 4, 5];
+//! let i = fastrand::usize(..v.len());
+//! let elem = v[i];
+//! ```
+//!
+//! Shuffle an array:
+//!
+//! ```
+//! let mut v = vec![1, 2, 3, 4, 5];
+//! fastrand::shuffle(&mut v);
+//! ```
+//!
+//! Generate a random [`Vec`] or [`String`]:
+//!
+//! ```
+//! use std::iter::repeat_with;
+//!
+//! let v: Vec<i32> = repeat_with(|| fastrand::i32(..)).take(10).collect();
+//! let s: String = repeat_with(fastrand::alphanumeric).take(10).collect();
+//! ```
+//!
+//! To get reproducible results on every run, initialize the generator with a seed:
+//!
+//! ```
+//! // Pick an arbitrary number as seed.
+//! fastrand::seed(7);
+//!
+//! // Now this prints the same number on every run:
+//! println!("{}", fastrand::u32(..));
+//! ```
+//!
+//! To be more efficient, create a new [`Rng`] instance instead of using the thread-local
+//! generator:
+//!
+//! ```
+//! use std::iter::repeat_with;
+//!
+//! let rng = fastrand::Rng::new();
+//! let mut bytes: Vec<u8> = repeat_with(|| rng.u8(..)).take(10_000).collect();
+//! ```
+
+#![forbid(unsafe_code)]
+#![warn(missing_docs, missing_debug_implementations, rust_2018_idioms)]
+
+use std::cell::Cell;
+use std::collections::hash_map::DefaultHasher;
+use std::convert::TryInto;
+use std::hash::{Hash, Hasher};
+use std::ops::{Bound, RangeBounds};
+use std::thread;
+
+#[cfg(all(target_arch = "wasm32", not(target_os = "wasi")))]
+use instant::Instant;
+#[cfg(not(all(target_arch = "wasm32", not(target_os = "wasi"))))]
+use std::time::Instant;
+
+/// A random number generator.
+#[derive(Debug, PartialEq, Eq)]
+pub struct Rng(Cell<u64>);
+
+impl Default for Rng {
+    #[inline]
+    fn default() -> Rng {
+        Rng::new()
+    }
+}
+
+impl Clone for Rng {
+    /// Clones the generator by deterministically deriving a new generator based on the initial
+    /// seed.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// // Seed two generators equally, and clone both of them.
+    /// let base1 = fastrand::Rng::new();
+    /// base1.seed(0x4d595df4d0f33173);
+    /// base1.bool(); // Use the generator once.
+    ///
+    /// let base2 = fastrand::Rng::new();
+    /// base2.seed(0x4d595df4d0f33173);
+    /// base2.bool(); // Use the generator once.
+    ///
+    /// let rng1 = base1.clone();
+    /// let rng2 = base2.clone();
+    ///
+    /// assert_eq!(rng1.u64(..), rng2.u64(..), "the cloned generators are identical");
+    /// ```
+    fn clone(&self) -> Rng {
+        Rng::with_seed(self.gen_u64())
+    }
+}
+
+impl Rng {
+    /// Generates a random `u32`.
+    #[inline]
+    fn gen_u32(&self) -> u32 {
+        self.gen_u64() as u32
+    }
+
+    /// Generates a random `u64`.
+    #[inline]
+    fn gen_u64(&self) -> u64 {
+        let s = self.0.get().wrapping_add(0xA0761D6478BD642F);
+        self.0.set(s);
+        let t = u128::from(s) * u128::from(s ^ 0xE7037ED1A0B428DB);
+        (t as u64) ^ (t >> 64) as u64
+    }
+
+    /// Generates a random `u128`.
+    #[inline]
+    fn gen_u128(&self) -> u128 {
+        (u128::from(self.gen_u64()) << 64) | u128::from(self.gen_u64())
+    }
+
+    /// Generates a random `u32` in `0..n`.
+    #[inline]
+    fn gen_mod_u32(&self, n: u32) -> u32 {
+        // Adapted from: https://lemire.me/blog/2016/06/30/fast-random-shuffling/
+        let mut r = self.gen_u32();
+        let mut hi = mul_high_u32(r, n);
+        let mut lo = r.wrapping_mul(n);
+        if lo < n {
+            let t = n.wrapping_neg() % n;
+            while lo < t {
+                r = self.gen_u32();
+                hi = mul_high_u32(r, n);
+                lo = r.wrapping_mul(n);
+            }
+        }
+        hi
+    }
+
+    /// Generates a random `u64` in `0..n`.
+    #[inline]
+    fn gen_mod_u64(&self, n: u64) -> u64 {
+        // Adapted from: https://lemire.me/blog/2016/06/30/fast-random-shuffling/
+        let mut r = self.gen_u64();
+        let mut hi = mul_high_u64(r, n);
+        let mut lo = r.wrapping_mul(n);
+        if lo < n {
+            let t = n.wrapping_neg() % n;
+            while lo < t {
+                r = self.gen_u64();
+                hi = mul_high_u64(r, n);
+                lo = r.wrapping_mul(n);
+            }
+        }
+        hi
+    }
+
+    /// Generates a random `u128` in `0..n`.
+    #[inline]
+    fn gen_mod_u128(&self, n: u128) -> u128 {
+        // Adapted from: https://lemire.me/blog/2016/06/30/fast-random-shuffling/
+        let mut r = self.gen_u128();
+        let mut hi = mul_high_u128(r, n);
+        let mut lo = r.wrapping_mul(n);
+        if lo < n {
+            let t = n.wrapping_neg() % n;
+            while lo < t {
+                r = self.gen_u128();
+                hi = mul_high_u128(r, n);
+                lo = r.wrapping_mul(n);
+            }
+        }
+        hi
+    }
+}
+
+thread_local! {
+    static RNG: Rng = Rng(Cell::new({
+        let mut hasher = DefaultHasher::new();
+        Instant::now().hash(&mut hasher);
+        thread::current().id().hash(&mut hasher);
+        let hash = hasher.finish();
+        (hash << 1) | 1
+    }));
+}
+
+/// Computes `(a * b) >> 32`.
+#[inline]
+fn mul_high_u32(a: u32, b: u32) -> u32 {
+    (((a as u64) * (b as u64)) >> 32) as u32
+}
+
+/// Computes `(a * b) >> 64`.
+#[inline]
+fn mul_high_u64(a: u64, b: u64) -> u64 {
+    (((a as u128) * (b as u128)) >> 64) as u64
+}
+
+/// Computes `(a * b) >> 128`.
+#[inline]
+fn mul_high_u128(a: u128, b: u128) -> u128 {
+    // Adapted from: https://stackoverflow.com/a/28904636
+    let a_lo = a as u64 as u128;
+    let a_hi = (a >> 64) as u64 as u128;
+    let b_lo = b as u64 as u128;
+    let b_hi = (b >> 64) as u64 as u128;
+    let carry = (a_lo * b_lo) >> 64;
+    let carry = ((a_hi * b_lo) as u64 as u128 + (a_lo * b_hi) as u64 as u128 + carry) >> 64;
+    a_hi * b_hi + ((a_hi * b_lo) >> 64) + ((a_lo * b_hi) >> 64) + carry
+}
+
+macro_rules! rng_integer {
+    ($t:tt, $unsigned_t:tt, $gen:tt, $mod:tt, $doc:tt) => {
+        #[doc = $doc]
+        ///
+        /// Panics if the range is empty.
+        #[inline]
+        pub fn $t(&self, range: impl RangeBounds<$t>) -> $t {
+            let panic_empty_range = || {
+                panic!(
+                    "empty range: {:?}..{:?}",
+                    range.start_bound(),
+                    range.end_bound()
+                )
+            };
+
+            let low = match range.start_bound() {
+                Bound::Unbounded => std::$t::MIN,
+                Bound::Included(&x) => x,
+                Bound::Excluded(&x) => x.checked_add(1).unwrap_or_else(panic_empty_range),
+            };
+
+            let high = match range.end_bound() {
+                Bound::Unbounded => std::$t::MAX,
+                Bound::Included(&x) => x,
+                Bound::Excluded(&x) => x.checked_sub(1).unwrap_or_else(panic_empty_range),
+            };
+
+            if low > high {
+                panic_empty_range();
+            }
+
+            if low == std::$t::MIN && high == std::$t::MAX {
+                self.$gen() as $t
+            } else {
+                let len = high.wrapping_sub(low).wrapping_add(1);
+                low.wrapping_add(self.$mod(len as $unsigned_t as _) as $t)
+            }
+        }
+    };
+}
+
+impl Rng {
+    /// Creates a new random number generator.
+    #[inline]
+    pub fn new() -> Rng {
+        Rng::with_seed(
+            RNG.try_with(|rng| rng.u64(..))
+                .unwrap_or(0x4d595df4d0f33173),
+        )
+    }
+
+    /// Creates a new random number generator with the initial seed.
+    #[inline]
+    #[must_use = "this creates a new instance of `Rng`; if you want to initialize the thread-local generator, use `fastrand::seed()` instead"]
+    pub fn with_seed(seed: u64) -> Self {
+        let rng = Rng(Cell::new(0));
+
+        rng.seed(seed);
+        rng
+    }
+
+    /// Generates a random `char` in ranges a-z and A-Z.
+    #[inline]
+    pub fn alphabetic(&self) -> char {
+        const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
+        let len = CHARS.len() as u8;
+        let i = self.u8(..len);
+        CHARS[i as usize] as char
+    }
+
+    /// Generates a random `char` in ranges a-z, A-Z and 0-9.
+    #[inline]
+    pub fn alphanumeric(&self) -> char {
+        const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
+        let len = CHARS.len() as u8;
+        let i = self.u8(..len);
+        CHARS[i as usize] as char
+    }
+
+    /// Generates a random `bool`.
+    #[inline]
+    pub fn bool(&self) -> bool {
+        self.u8(..) % 2 == 0
+    }
+
+    /// Generates a random digit in the given `base`.
+    ///
+    /// Digits are represented by `char`s in ranges 0-9 and a-z.
+    ///
+    /// Panics if the base is zero or greater than 36.
+    #[inline]
+    pub fn digit(&self, base: u32) -> char {
+        if base == 0 {
+            panic!("base cannot be zero");
+        }
+        if base > 36 {
+            panic!("base cannot be larger than 36");
+        }
+        let num = self.u8(..base as u8);
+        if num < 10 {
+            (b'0' + num) as char
+        } else {
+            (b'a' + num - 10) as char
+        }
+    }
+
+    /// Generates a random `f32` in range `0..1`.
+    pub fn f32(&self) -> f32 {
+        let b = 32;
+        let f = std::f32::MANTISSA_DIGITS - 1;
+        f32::from_bits((1 << (b - 2)) - (1 << f) + (self.u32(..) >> (b - f))) - 1.0
+    }
+
+    /// Generates a random `f64` in range `0..1`.
+    pub fn f64(&self) -> f64 {
+        let b = 64;
+        let f = std::f64::MANTISSA_DIGITS - 1;
+        f64::from_bits((1 << (b - 2)) - (1 << f) + (self.u64(..) >> (b - f))) - 1.0
+    }
+
+    rng_integer!(
+        i8,
+        u8,
+        gen_u32,
+        gen_mod_u32,
+        "Generates a random `i8` in the given range."
+    );
+
+    rng_integer!(
+        i16,
+        u16,
+        gen_u32,
+        gen_mod_u32,
+        "Generates a random `i16` in the given range."
+    );
+
+    rng_integer!(
+        i32,
+        u32,
+        gen_u32,
+        gen_mod_u32,
+        "Generates a random `i32` in the given range."
+    );
+
+    rng_integer!(
+        i64,
+        u64,
+        gen_u64,
+        gen_mod_u64,
+        "Generates a random `i64` in the given range."
+    );
+
+    rng_integer!(
+        i128,
+        u128,
+        gen_u128,
+        gen_mod_u128,
+        "Generates a random `i128` in the given range."
+    );
+
+    #[cfg(target_pointer_width = "16")]
+    rng_integer!(
+        isize,
+        usize,
+        gen_u32,
+        gen_mod_u32,
+        "Generates a random `isize` in the given range."
+    );
+    #[cfg(target_pointer_width = "32")]
+    rng_integer!(
+        isize,
+        usize,
+        gen_u32,
+        gen_mod_u32,
+        "Generates a random `isize` in the given range."
+    );
+    #[cfg(target_pointer_width = "64")]
+    rng_integer!(
+        isize,
+        usize,
+        gen_u64,
+        gen_mod_u64,
+        "Generates a random `isize` in the given range."
+    );
+
+    /// Generates a random `char` in range a-z.
+    #[inline]
+    pub fn lowercase(&self) -> char {
+        const CHARS: &[u8] = b"abcdefghijklmnopqrstuvwxyz";
+        let len = CHARS.len() as u8;
+        let i = self.u8(..len);
+        CHARS[i as usize] as char
+    }
+
+    /// Initializes this generator with the given seed.
+    #[inline]
+    pub fn seed(&self, seed: u64) {
+        self.0.set(seed);
+    }
+
+    /// Gives back **current** seed that is being held by this generator.
+    #[inline]
+    pub fn get_seed(&self) -> u64 {
+        self.0.get()
+    }
+
+    /// Shuffles a slice randomly.
+    #[inline]
+    pub fn shuffle<T>(&self, slice: &mut [T]) {
+        for i in 1..slice.len() {
+            slice.swap(i, self.usize(..=i));
+        }
+    }
+
+    /// Fill a byte slice with random data.
+    #[inline]
+    pub fn fill(&self, slice: &mut [u8]) {
+        // We fill the slice by chunks of 8 bytes, or one block of
+        // WyRand output per new state.
+        let mut chunks = slice.chunks_exact_mut(core::mem::size_of::<u64>());
+        for chunk in chunks.by_ref() {
+            let n = self.gen_u64().to_ne_bytes();
+            // Safe because the chunks are always 8 bytes exactly.
+            chunk.copy_from_slice(&n);
+        }
+
+        let remainder = chunks.into_remainder();
+
+        // Any remainder will always be less than 8 bytes.
+        if !remainder.is_empty() {
+            // Generate one last block of 8 bytes of entropy
+            let n = self.gen_u64().to_ne_bytes();
+
+            // Use the remaining length to copy from block
+            remainder.copy_from_slice(&n[..remainder.len()]);
+        }
+    }
+
+    rng_integer!(
+        u8,
+        u8,
+        gen_u32,
+        gen_mod_u32,
+        "Generates a random `u8` in the given range."
+    );
+
+    rng_integer!(
+        u16,
+        u16,
+        gen_u32,
+        gen_mod_u32,
+        "Generates a random `u16` in the given range."
+    );
+
+    rng_integer!(
+        u32,
+        u32,
+        gen_u32,
+        gen_mod_u32,
+        "Generates a random `u32` in the given range."
+    );
+
+    rng_integer!(
+        u64,
+        u64,
+        gen_u64,
+        gen_mod_u64,
+        "Generates a random `u64` in the given range."
+    );
+
+    rng_integer!(
+        u128,
+        u128,
+        gen_u128,
+        gen_mod_u128,
+        "Generates a random `u128` in the given range."
+    );
+
+    #[cfg(target_pointer_width = "16")]
+    rng_integer!(
+        usize,
+        usize,
+        gen_u32,
+        gen_mod_u32,
+        "Generates a random `usize` in the given range."
+    );
+    #[cfg(target_pointer_width = "32")]
+    rng_integer!(
+        usize,
+        usize,
+        gen_u32,
+        gen_mod_u32,
+        "Generates a random `usize` in the given range."
+    );
+    #[cfg(target_pointer_width = "64")]
+    rng_integer!(
+        usize,
+        usize,
+        gen_u64,
+        gen_mod_u64,
+        "Generates a random `usize` in the given range."
+    );
+    #[cfg(target_pointer_width = "128")]
+    rng_integer!(
+        usize,
+        usize,
+        gen_u128,
+        gen_mod_u128,
+        "Generates a random `usize` in the given range."
+    );
+
+    /// Generates a random `char` in range A-Z.
+    #[inline]
+    pub fn uppercase(&self) -> char {
+        const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ";
+        let len = CHARS.len() as u8;
+        let i = self.u8(..len);
+        CHARS[i as usize] as char
+    }
+
+    /// Generates a random `char` in the given range.
+    ///
+    /// Panics if the range is empty.
+    #[inline]
+    pub fn char(&self, range: impl RangeBounds<char>) -> char {
+        use std::convert::TryFrom;
+
+        let panic_empty_range = || {
+            panic!(
+                "empty range: {:?}..{:?}",
+                range.start_bound(),
+                range.end_bound()
+            )
+        };
+
+        let surrogate_start = 0xd800u32;
+        let surrogate_len = 0x800u32;
+
+        let low = match range.start_bound() {
+            Bound::Unbounded => 0u8 as char,
+            Bound::Included(&x) => x,
+            Bound::Excluded(&x) => {
+                let scalar = if x as u32 == surrogate_start - 1 {
+                    surrogate_start + surrogate_len
+                } else {
+                    x as u32 + 1
+                };
+                char::try_from(scalar).unwrap_or_else(|_| panic_empty_range())
+            }
+        };
+
+        let high = match range.end_bound() {
+            Bound::Unbounded => std::char::MAX,
+            Bound::Included(&x) => x,
+            Bound::Excluded(&x) => {
+                let scalar = if x as u32 == surrogate_start + surrogate_len {
+                    surrogate_start - 1
+                } else {
+                    (x as u32).wrapping_sub(1)
+                };
+                char::try_from(scalar).unwrap_or_else(|_| panic_empty_range())
+            }
+        };
+
+        if low > high {
+            panic_empty_range();
+        }
+
+        let gap = if (low as u32) < surrogate_start && (high as u32) >= surrogate_start {
+            surrogate_len
+        } else {
+            0
+        };
+        let range = high as u32 - low as u32 - gap;
+        let mut val = self.u32(0..=range) + low as u32;
+        if val >= surrogate_start {
+            val += gap;
+        }
+        val.try_into().unwrap()
+    }
+}
+
+/// Initializes the thread-local generator with the given seed.
+#[inline]
+pub fn seed(seed: u64) {
+    RNG.with(|rng| rng.seed(seed))
+}
+
+/// Gives back **current** seed that is being held by the thread-local generator.
+#[inline]
+pub fn get_seed() -> u64 {
+    RNG.with(|rng| rng.get_seed())
+}
+
+/// Generates a random `bool`.
+#[inline]
+pub fn bool() -> bool {
+    RNG.with(|rng| rng.bool())
+}
+
+/// Generates a random `char` in ranges a-z and A-Z.
+#[inline]
+pub fn alphabetic() -> char {
+    RNG.with(|rng| rng.alphabetic())
+}
+
+/// Generates a random `char` in ranges a-z, A-Z and 0-9.
+#[inline]
+pub fn alphanumeric() -> char {
+    RNG.with(|rng| rng.alphanumeric())
+}
+
+/// Generates a random `char` in range a-z.
+#[inline]
+pub fn lowercase() -> char {
+    RNG.with(|rng| rng.lowercase())
+}
+
+/// Generates a random `char` in range A-Z.
+#[inline]
+pub fn uppercase() -> char {
+    RNG.with(|rng| rng.uppercase())
+}
+
+/// Generates a random digit in the given `base`.
+///
+/// Digits are represented by `char`s in ranges 0-9 and a-z.
+///
+/// Panics if the base is zero or greater than 36.
+#[inline]
+pub fn digit(base: u32) -> char {
+    RNG.with(|rng| rng.digit(base))
+}
+
+/// Shuffles a slice randomly.
+#[inline]
+pub fn shuffle<T>(slice: &mut [T]) {
+    RNG.with(|rng| rng.shuffle(slice))
+}
+
+macro_rules! integer {
+    ($t:tt, $doc:tt) => {
+        #[doc = $doc]
+        ///
+        /// Panics if the range is empty.
+        #[inline]
+        pub fn $t(range: impl RangeBounds<$t>) -> $t {
+            RNG.with(|rng| rng.$t(range))
+        }
+    };
+}
+
+integer!(u8, "Generates a random `u8` in the given range.");
+integer!(i8, "Generates a random `i8` in the given range.");
+integer!(u16, "Generates a random `u16` in the given range.");
+integer!(i16, "Generates a random `i16` in the given range.");
+integer!(u32, "Generates a random `u32` in the given range.");
+integer!(i32, "Generates a random `i32` in the given range.");
+integer!(u64, "Generates a random `u64` in the given range.");
+integer!(i64, "Generates a random `i64` in the given range.");
+integer!(u128, "Generates a random `u128` in the given range.");
+integer!(i128, "Generates a random `i128` in the given range.");
+integer!(usize, "Generates a random `usize` in the given range.");
+integer!(isize, "Generates a random `isize` in the given range.");
+integer!(char, "Generates a random `char` in the given range.");
+
+/// Generates a random `f32` in range `0..1`.
+pub fn f32() -> f32 {
+    RNG.with(|rng| rng.f32())
+}
+
+/// Generates a random `f64` in range `0..1`.
+pub fn f64() -> f64 {
+    RNG.with(|rng| rng.f64())
+}