devela 0.28.0

// devela::num::prob::rand::rand
//
//! Defines [`RandSeedable`], [`RandTry`], [`Rand`].
//

use crate::{Cast, Infallible, RandQualities, is, whilst};

#[doc = crate::_tags!(rand)]
/// Construction from explicit seed material or another random source.
#[doc = crate::_doc_meta!{location("num/prob/rand")}]
///
/// `RandSeedable` defines a portable byte-backed seed representation and
/// provides construction from explicit seed material or another random source.
///
/// Multi-byte values encoded in seeds use little-endian order, preserving
/// reproducibility across target endianness.
pub trait RandSeedable: Sized {
    /// Byte-backed seed material accepted by this type.
    type RandSeed: Clone + Default + AsRef<[u8]> + AsMut<[u8]>;
    // type RandSeed: Default + AsMut<[u8]>;

    /// Constructs this type from explicit seed material.
    fn rand_from_seed(seed: Self::RandSeed) -> Self;

    /// Attempts to construct this type by drawing seed material from `source`.
    fn rand_try_from_source<R>(source: &mut R) -> Result<Self, R::Error>
    where
        R: RandTry + ?Sized,
    {
        let mut seed = Self::RandSeed::default();
        source.rand_try_fill_bytes(seed.as_mut())?;
        Ok(Self::rand_from_seed(seed))
    }

    /// Constructs this type by drawing seed material from an infallible source.
    #[must_use]
    #[inline(always)]
    fn rand_from_source<R>(source: &mut R) -> Self
    where
        R: Rand + ?Sized,
    {
        match Self::rand_try_from_source(source) {
            Ok(value) => value,
            Err(error) => match error {},
        }
    }
}

#[doc = crate::_tags!(rand)]
/// Fallible source of raw random data.
#[doc = crate::_doc_meta!{location("num/prob/rand")}]
///
/// `RandTry` is the core trait for random sources that may fail, such as
/// OS calls, hardware RNGs, host APIs, finite buffers, and fallible adapters.
///
/// Source behavior and suitability are described by [`RandQualities`].
///
/// Infallible sources use [`Infallible`][crate::Infallible] as their error type.
// and automatically implement [`Rand`]. TODO
pub trait RandTry {
    /* required */

    /// Error returned when complete random data could not be produced.
    type Error;

    /// Number of bits produced per output step.
    ///
    /// Adapters or composite sources may report a conservative value.
    const RAND_OUTPUT_BITS: u32;

    /// Size of the source state owned by this value, in bits.
    ///
    /// External entropy sources that do not store generator state
    /// in the value itself should use `0`.
    const RAND_STATE_BITS: u32;

    /// Semantic qualities of this random source.
    const RAND_QUALITIES: RandQualities;

    /// Attempts to produce the next 64 bits of randomness.
    fn rand_try_next_u64(&mut self) -> Result<u64, Self::Error>;

    /*** provided ***/

    /// Returns the semantic qualities of this random source.
    #[must_use]
    #[inline(always)]
    fn rand_qualities(&self) -> RandQualities {
        Self::RAND_QUALITIES
    }

    /* derived primitives and byte access */

    /// Attempts to produce the next random `u128`.
    #[inline(always)]
    fn rand_try_next_u128(&mut self) -> Result<u128, Self::Error> {
        let pair = [self.rand_try_next_u64()?, self.rand_try_next_u64()?];
        Ok(Cast::<u128>::from_u64_le(pair))
    }
    /// Attempts to produce the next random `u32`.
    #[inline(always)]
    fn rand_try_next_u32(&mut self) -> Result<u32, Self::Error> {
        Ok(self.rand_try_next_u64()? as u32)
    }
    /// Attempts to produce the next random `u16`.
    #[inline(always)]
    fn rand_try_next_u16(&mut self) -> Result<u16, Self::Error> {
        Ok(self.rand_try_next_u64()? as u16)
    }
    /// Attempts to produce the next random `u8`.
    #[inline(always)]
    fn rand_try_next_u8(&mut self) -> Result<u8, Self::Error> {
        Ok(self.rand_try_next_u16()? as u8)
    }
    /// Attempts to produce a random boolean.
    #[inline(always)]
    fn rand_try_next_bool(&mut self) -> Result<bool, Self::Error> {
        Ok((self.rand_try_next_u64()? & 1) != 0)
    }

    /// Attempts to fill the buffer with generated bytes.
    ///
    /// This method must either fill the whole buffer or return an error.
    fn rand_try_fill_bytes(&mut self, buffer: &mut [u8]) -> Result<(), Self::Error> {
        let mut i = 0;
        let len = buffer.len();
        while i + 8 <= len {
            buffer[i..i + 8].copy_from_slice(&self.rand_try_next_u64()?.to_ne_bytes());
            i += 8;
        }
        if i < len {
            let tail = self.rand_try_next_u64()?.to_ne_bytes();
            buffer[i..].copy_from_slice(&tail[..len - i]);
        }
        Ok(())
    }

    /* bounded sampling */

    /// Attempts to return a uniformly random integer in `0..upper`.
    ///
    /// Uses rejection sampling to avoid modulo bias.
    fn rand_try_below(&mut self, upper: u64) -> Result<u64, Self::Error> {
        assert!(upper > 0);
        let zone = u64::MAX - (u64::MAX % upper);
        loop {
            let v = self.rand_try_next_u64()?;
            is! { v < zone, return Ok(v % upper) }
        }
    }
    /// Attempts to return a uniformly random integer in `low..high`.
    ///
    /// # Panics
    /// Panics if `low >= high`.
    #[inline(always)]
    #[track_caller]
    fn rand_try_range(&mut self, low: u64, high: u64) -> Result<u64, Self::Error> {
        assert!(low < high);
        Ok(low + self.rand_try_below(high - low)?)
    }

    /* common discrete helpers */

    /// Attempts to roll a fair die with a number of `sides`.
    ///
    /// Returns a value in `1..=sides`.
    #[inline(always)]
    fn rand_try_roll(&mut self, sides: u64) -> Result<u64, Self::Error> {
        Ok(self.rand_try_below(sides)? + 1)
    }
    /// Attempts to shuffle the elements of the slice in place.
    ///
    /// Uses the Fisher–Yates algorithm.
    fn rand_try_shuffle<T>(&mut self, slice: &mut [T]) -> Result<(), Self::Error> {
        /*
        let mut i = slice.len();
        while i > 1 {
            i -= 1;
            let j = self.rand_try_below((i + 1) as u64)? as usize;
            slice.swap(i, j);
        }
        */

        whilst! { i in rev 1..slice.len(); {
            let j = self.rand_try_below((i + 1) as u64)? as usize;
            slice.swap(i, j);
        }}
        Ok(())
    }

    /* selection helpers */

    /// Attempts to choose one valid item using reservoir sampling.
    ///
    /// This is uniform over all valid items and uses one pass.
    fn rand_try_choose_reservoir<I, F>(
        &mut self,
        iter: I,
        mut valid: F,
    ) -> Result<Option<I::Item>, Self::Error>
    where
        I: IntoIterator,
        F: FnMut(&I::Item) -> bool,
    {
        let (mut seen, mut picked) = (0u64, None);
        for item in iter {
            if valid(&item) {
                seen = seen.checked_add(1).expect("too many valid random candidates");
                is! { self.rand_try_below(seen)? == 0, picked = Some(item) }
            }
        }
        Ok(picked)
    }
    /// Attempts to choose one valid item using random scores.
    ///
    /// Each valid item receives a random score. The highest score wins.
    /// Ties are resolved uniformly.
    fn rand_try_choose_scored<I, F>(
        &mut self,
        iter: I,
        mut valid: F,
    ) -> Result<Option<I::Item>, Self::Error>
    where
        I: IntoIterator,
        F: FnMut(&I::Item) -> bool,
    {
        let (mut picked, mut best_score, mut ties) = (None, 0u64, 0u64);
        for item in iter {
            if valid(&item) {
                let score = self.rand_try_next_u64()?;
                if picked.is_none() || score > best_score {
                    picked = Some(item);
                    best_score = score;
                    ties = 1;
                } else if score == best_score {
                    ties = ties.checked_add(1).expect("too many tied random candidates");
                    is! { self.rand_try_below(ties)? == 0, picked = Some(item) }
                }
            }
        }
        Ok(picked)
    }
}

impl<R> Rand for R where R: RandTry<Error = Infallible> + ?Sized {}

#[doc = crate::_tags!(rand)]
/// Infallible source of raw random data.
#[doc = crate::_doc_meta!{location("num/prob/rand")}]
///
/// `Rand` is implemented automatically for every [`RandTry`] source
/// whose error type is [`Infallible`].
///
/// Determinism, reproducibility, cryptographic suitability, weakness,
/// external state, and blocking behavior are described by the source
/// characteristics inherited from [`RandTry`].
#[rustfmt::skip]
pub trait Rand: RandTry<Error = Infallible> {
    /*** provided ***/

    /* derived primitives and byte access */

    /// Returns the next random `u128`.
    #[inline(always)]
    fn rand_next_u128(&mut self) -> u128 {
        match self.rand_try_next_u128() { Ok(v) => v, Err(e) => match e {} }
    }
    /// Returns the next random `u64`.
    #[inline(always)]
    fn rand_next_u64(&mut self) -> u64 {
        match self.rand_try_next_u64() { Ok(v) => v, Err(e) => match e {} }
    }
    /// Returns the next random `u32`.
    #[inline(always)]
    fn rand_next_u32(&mut self) -> u32 {
        match self.rand_try_next_u32() { Ok(v) => v, Err(e) => match e {} }
    }
    /// Returns the next random `u16`.
    #[inline(always)]
    fn rand_next_u16(&mut self) -> u16 {
        match self.rand_try_next_u16() { Ok(v) => v, Err(e) => match e {} }
    }
    /// Returns the next random `u8`.
    #[inline(always)]
    fn rand_next_u8(&mut self) -> u8 {
        match self.rand_try_next_u8() { Ok(v) => v, Err(e) => match e {} }
    }
    /// Produces a random boolean.
    #[inline(always)]
    fn rand_next_bool(&mut self) -> bool {
        match self.rand_try_next_bool() { Ok(v) => v, Err(e) => match e {} }
    }

    /// Fills the buffer with generated bytes.
    #[inline(always)]
    fn rand_fill_bytes(&mut self, buf: &mut [u8]) {
        match self.rand_try_fill_bytes(buf) { Ok(()) => {} Err(e) => match e {} }
    }

    /* bounded sampling */

    /// Returns a uniformly random integer in `0..upper`.
    ///
    /// Uses rejection sampling to avoid modulo bias.
    #[inline(always)]
    fn rand_below(&mut self, upper: u64) -> u64 {
        match self.rand_try_below(upper) { Ok(v) => v, Err(e) => match e {} }
    }
    /// Returns a uniformly random integer in `low..high`.
    ///
    /// # Panics
    /// Panics if `low >= high`.
    #[inline(always)]
    #[track_caller]
    fn rand_range(&mut self, low: u64, high: u64) -> u64 {
        match self.rand_try_range(low, high) { Ok(v) => v, Err(e) => match e {} }
    }

    /* common discrete helpers */

    /// Rolls a fair die with a number of `sides`.
    ///
    /// Returns a value in `1..=sides`.
    #[inline(always)]
    fn rand_roll(&mut self, sides: u64) -> u64 {
        match self.rand_try_roll(sides) { Ok(v) => v, Err(e) => match e {} }
    }
    /// Shuffles the elements of the slice in place.
    ///
    /// Uses the Fisher–Yates algorithm.
    #[inline(always)]
    fn rand_shuffle<T>(&mut self, slice: &mut [T]) {
        match self.rand_try_shuffle(slice) { Ok(()) => {} Err(e) => match e {} }
    }

    /* selection helpers */

    /// Chooses one valid item using reservoir sampling.
    ///
    /// This is uniform over all valid items and uses one pass.
    #[inline(always)]
    fn rand_choose_reservoir<I, F>(&mut self, iter: I, valid: F) -> Option<I::Item>
    where I: IntoIterator, F: FnMut(&I::Item) -> bool {
        match self.rand_try_choose_reservoir(iter, valid) { Ok(v) => v, Err(e) => match e {} }
    }
    /// Chooses one valid item using random scores.
    ///
    /// Each valid item receives a random score. The highest score wins.
    /// Ties are resolved uniformly.
    #[inline(always)]
    fn rand_choose_scored<I, F>(&mut self, iter: I, valid: F) -> Option<I::Item>
    where I: IntoIterator, F: FnMut(&I::Item) -> bool {
        match self.rand_try_choose_scored(iter, valid) { Ok(v) => v, Err(e) => match e {} }
    }
}