//! Deterministic, reproducible RNG (spec §4.4, §7).
//!
//! [`Rng`] wraps [`rand_chacha::ChaCha8Rng`] — a portable, byte-stable stream
//! cipher RNG. The same seed yields the same sequence on every machine and
//! every run; we never touch `thread_rng`/`rand::random()`.
//!
//! The keystone feature is [`Rng::fork`]: it derives an *independent* child
//! stream from the parent's **basis seed** plus a label. Forking does not draw
//! from or otherwise mutate the parent (`fork(&self)`), so a child stream is a
//! pure function of `(basis_seed, label)` — independent of how many values were
//! pulled from the parent first. The [`Pipeline`](crate) leans on this to give
//! each pass its own sub-stream keyed by `"<pass name>#<occurrence>"`, which is
//! what makes inserting or reordering a pass non-destructive to existing seeds.

use rand_chacha::ChaCha8Rng;
// `rand_core` is not a direct dependency; reach its traits through the
// re-export on `rand_chacha` so the two stay version-locked. `Rng` carries
// `next_u64`; `SeedableRng` carries `seed_from_u64`.
use rand_chacha::rand_core::{Rng as _, SeedableRng};

/// A deterministic random number generator backed by ChaCha8.
///
/// Construct one with [`Rng::from_seed`], draw values with [`range`](Rng::range),
/// [`chance`](Rng::chance), [`choose`](Rng::choose) and [`shuffle`](Rng::shuffle),
/// and derive isolated child streams with [`fork`](Rng::fork).
#[derive(Clone, Debug)]
pub struct Rng {
    /// The stable basis used for all forks: the seed this `Rng` was built from.
    /// Forking mixes *this* (never the live ChaCha state) with the label, so a
    /// fork is independent of how many draws the parent has taken.
    basis_seed: u64,
    /// The live ChaCha8 stream that actually produces random words.
    inner: ChaCha8Rng,
}

impl Rng {
    /// Create an `Rng` from a 64-bit seed, storing the seed as the fork basis.
    ///
    /// The seed is expanded into ChaCha8's 256-bit key by ChaCha8's own
    /// portable `seed_from_u64`, so two `Rng`s built from the same `u64`
    /// produce identical streams everywhere.
    pub fn from_seed(seed: u64) -> Self {
        Self {
            basis_seed: seed,
            inner: ChaCha8Rng::seed_from_u64(seed),
        }
    }

    /// Derive an independent child `Rng` from a stable basis (this `Rng`'s
    /// originating seed) combined with `label`.
    ///
    /// This **does not** advance or otherwise mutate `self` (note `&self`), and
    /// the result depends only on `(self.basis_seed, label)` — never on how many
    /// values have already been drawn from `self`. Distinct labels (including
    /// `"name#0"` vs `"name#1"`) yield distinct streams.
    ///
    /// The label→seed mix is the explicit, fixed integer routine in
    /// [`mix_seed`] (splitmix64 + FNV-1a), chosen because it is stable across
    /// runs and crate versions. We deliberately avoid
    /// `std::collections::hash_map::DefaultHasher`, whose output is
    /// unspecified and version-unstable (spec §7).
    pub fn fork(&self, label: &str) -> Rng {
        Rng::from_seed(mix_seed(self.basis_seed, label))
    }

    /// Draw a `u64` of raw randomness from the live stream.
    fn next_u64(&mut self) -> u64 {
        self.inner.next_u64()
    }

    /// Return an integer in the **half-open** range `[lo, hi)` — `lo` inclusive,
    /// `hi` exclusive (so `range(0, 3)` yields one of `0, 1, 2`).
    ///
    /// If `hi <= lo` the range is empty; we return `lo` rather than panicking
    /// (no panics on valid input — spec §8). Uniformity is achieved with
    /// Lemire-style rejection sampling over the `u64` span, so the result is
    /// unbiased across the whole range.
    pub fn range(&mut self, lo: i32, hi: i32) -> i32 {
        if hi <= lo {
            return lo;
        }
        // Width fits in u64: (hi - lo) where hi > lo and both are i32.
        let span = (hi as i64 - lo as i64) as u64;
        lo + self.below(span) as i32
    }

    /// Uniform integer in `[0, span)` for `span > 0`, via rejection sampling to
    /// avoid modulo bias. `span` is assumed non-zero by callers.
    fn below(&mut self, span: u64) -> u64 {
        // Largest multiple of `span` that fits in u64; anything at or above the
        // threshold would skew the distribution, so we reject and redraw.
        let threshold = u64::MAX - (u64::MAX % span);
        loop {
            let x = self.next_u64();
            if x < threshold {
                return x % span;
            }
        }
    }

    /// Return `true` with probability `p`.
    ///
    /// `p` is clamped to `[0.0, 1.0]`, so out-of-range probabilities are
    /// saturated rather than panicking. `p <= 0.0` is always `false`,
    /// `p >= 1.0` is always `true`.
    pub fn chance(&mut self, p: f64) -> bool {
        if p <= 0.0 {
            return false;
        }
        if p >= 1.0 {
            return true;
        }
        // Map the next u64 into a uniform f64 in [0, 1) and compare.
        // 53 bits gives the full mantissa precision of an f64.
        let bits = self.next_u64() >> 11; // top 53 bits
        let unit = bits as f64 / (1u64 << 53) as f64;
        unit < p
    }

    /// Return a reference to a uniformly chosen element of `items`, or `None`
    /// if the slice is empty.
    pub fn choose<'a, T>(&mut self, items: &'a [T]) -> Option<&'a T> {
        if items.is_empty() {
            return None;
        }
        let idx = self.below(items.len() as u64) as usize;
        items.get(idx)
    }

    /// Shuffle `items` in place into a uniformly random permutation.
    ///
    /// Uses an in-place Fisher–Yates shuffle built on our own [`range`] so the
    /// permutation is fully determined by the stream and identical on every
    /// machine. A slice of length 0 or 1 is left unchanged.
    pub fn shuffle<T>(&mut self, items: &mut [T]) {
        let len = items.len();
        if len < 2 {
            return;
        }
        // Walk from the end; swap each element with a random earlier-or-equal
        // index. Iterate down to 1 because index 0 has nothing left to swap.
        for i in (1..len).rev() {
            let j = self.below((i + 1) as u64) as usize;
            items.swap(i, j);
        }
    }
}

/// Mix a 64-bit basis seed with a label into a fresh 64-bit seed for [`Rng::fork`].
///
/// This is the load-bearing determinism primitive (spec §7), so the algorithm
/// is spelled out explicitly and uses only fixed integer arithmetic — no
/// `DefaultHasher`, no version-unstable hashing.
///
/// Recipe:
/// 1. Start from a splitmix64 scramble of the basis seed (so the basis is well
///    diffused before any label bytes are folded in).
/// 2. Fold each label byte in with the FNV-1a step (`xor` then multiply by the
///    64-bit FNV prime), which makes the result order-sensitive across bytes —
///    so `"name#0"` and `"name#1"` diverge.
/// 3. Run one final splitmix64 finalizer to avalanche the combined value.
fn mix_seed(basis: u64, label: &str) -> u64 {
    // The 64-bit FNV-1a offset basis and prime (fixed, well-known constants).
    const FNV_PRIME: u64 = 0x0000_0100_0000_01B3;

    let mut state = splitmix64(basis);
    for &byte in label.as_bytes() {
        state ^= byte as u64;
        state = state.wrapping_mul(FNV_PRIME);
    }
    splitmix64(state)
}

/// One round of the splitmix64 finalizer: a fixed, portable integer avalanche.
fn splitmix64(seed: u64) -> u64 {
    // Constants from the reference splitmix64 (Steele, Lea & Flood 2014).
    let mut z = seed.wrapping_add(0x9E37_79B9_7F4A_7C15);
    z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
    z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
    z ^ (z >> 31)
}

#[cfg(test)]
mod tests {
    use super::*;

    /// Same seed → identical sequence of `range` draws.
    #[test]
    fn same_seed_reproduces_sequence() {
        let mut a = Rng::from_seed(0xABCD_1234);
        let mut b = Rng::from_seed(0xABCD_1234);
        let seq_a: Vec<i32> = (0..64).map(|_| a.range(0, 1000)).collect();
        let seq_b: Vec<i32> = (0..64).map(|_| b.range(0, 1000)).collect();
        assert_eq!(seq_a, seq_b);
    }

    /// Different seeds should (overwhelmingly) produce different sequences.
    #[test]
    fn distinct_seeds_diverge() {
        let mut a = Rng::from_seed(1);
        let mut b = Rng::from_seed(2);
        let seq_a: Vec<i32> = (0..64).map(|_| a.range(0, 1_000_000)).collect();
        let seq_b: Vec<i32> = (0..64).map(|_| b.range(0, 1_000_000)).collect();
        assert_ne!(seq_a, seq_b);
    }

    /// `fork` is order-independent: the child stream does not depend on how many
    /// values were drawn from the parent beforehand, and forking does not mutate
    /// the parent.
    #[test]
    fn fork_is_order_independent() {
        let parent = Rng::from_seed(99);

        // Fork immediately.
        let mut early = parent.fork("a");

        // Now draw a bunch from a *clone* of the parent, then fork.
        let mut drained = parent.clone();
        for _ in 0..50 {
            let _ = drained.range(0, 100);
        }
        let mut late = drained.fork("a");

        let early_seq: Vec<i32> = (0..32).map(|_| early.range(0, 10_000)).collect();
        let late_seq: Vec<i32> = (0..32).map(|_| late.range(0, 10_000)).collect();
        assert_eq!(early_seq, late_seq, "fork must depend only on basis seed + label");
    }

    /// `fork(&self)` does not advance the parent's own stream.
    #[test]
    fn fork_does_not_mutate_parent() {
        let mut parent = Rng::from_seed(7);
        let before: Vec<i32> = {
            let mut probe = parent.clone();
            (0..16).map(|_| probe.range(0, 1000)).collect()
        };
        // Forking should leave `parent`'s stream untouched.
        let _child = parent.fork("whatever");
        let after: Vec<i32> = (0..16).map(|_| parent.range(0, 1000)).collect();
        assert_eq!(before, after);
    }

    /// Distinct labels produce distinct streams.
    #[test]
    fn distinct_labels_diverge() {
        let parent = Rng::from_seed(42);
        let mut a = parent.fork("a");
        let mut b = parent.fork("b");
        let seq_a: Vec<i32> = (0..32).map(|_| a.range(0, 1_000_000)).collect();
        let seq_b: Vec<i32> = (0..32).map(|_| b.range(0, 1_000_000)).collect();
        assert_ne!(seq_a, seq_b);
    }

    /// The pipeline's occurrence-keying scheme works: `"name#0"` and `"name#1"`
    /// must yield distinct streams.
    #[test]
    fn occurrence_keys_diverge() {
        let parent = Rng::from_seed(2024);
        let mut zero = parent.fork("name#0");
        let mut one = parent.fork("name#1");
        let seq_zero: Vec<i32> = (0..32).map(|_| zero.range(0, 1_000_000)).collect();
        let seq_one: Vec<i32> = (0..32).map(|_| one.range(0, 1_000_000)).collect();
        assert_ne!(seq_zero, seq_one);
    }

    /// `choose` on an empty slice returns `None`; on a non-empty slice it
    /// returns an in-bounds element.
    #[test]
    fn choose_empty_and_nonempty() {
        let mut rng = Rng::from_seed(5);
        let empty: [i32; 0] = [];
        assert_eq!(rng.choose(&empty), None);

        let items = [10, 20, 30, 40];
        for _ in 0..64 {
            let picked = rng.choose(&items).copied();
            assert!(picked.map(|v| items.contains(&v)).unwrap_or(false));
        }
    }

    /// `shuffle` is a permutation: it preserves the multiset of elements.
    #[test]
    fn shuffle_is_a_permutation() {
        let mut rng = Rng::from_seed(123);
        let mut items: Vec<i32> = (0..50).collect();
        let original = items.clone();
        rng.shuffle(&mut items);

        // Same multiset.
        let mut sorted = items.clone();
        sorted.sort_unstable();
        assert_eq!(sorted, original);

        // And the same shuffle reproduces under the same seed.
        let mut rng2 = Rng::from_seed(123);
        let mut items2: Vec<i32> = (0..50).collect();
        rng2.shuffle(&mut items2);
        assert_eq!(items, items2);
    }

    /// Tiny / empty slices are left untouched by `shuffle`.
    #[test]
    fn shuffle_trivial_slices() {
        let mut rng = Rng::from_seed(1);
        let mut empty: Vec<i32> = vec![];
        rng.shuffle(&mut empty);
        assert!(empty.is_empty());

        let mut single = vec![42];
        rng.shuffle(&mut single);
        assert_eq!(single, vec![42]);
    }

    /// `range` honors the half-open convention and the degenerate `hi <= lo`
    /// contract (returns `lo`, never panics).
    #[test]
    fn range_bounds_are_half_open() {
        let mut rng = Rng::from_seed(77);
        for _ in 0..256 {
            let v = rng.range(3, 7);
            assert!((3..7).contains(&v), "expected [3,7), got {v}");
        }
        // Degenerate ranges return `lo`.
        assert_eq!(rng.range(5, 5), 5);
        assert_eq!(rng.range(5, 2), 5);
        // Negative bounds work too.
        for _ in 0..256 {
            let v = rng.range(-5, -1);
            assert!((-5..-1).contains(&v), "expected [-5,-1), got {v}");
        }
    }

    /// `chance` saturates outside `[0, 1]` and is reproducible.
    #[test]
    fn chance_saturates_and_reproduces() {
        let mut rng = Rng::from_seed(9);
        assert!(!rng.chance(0.0));
        assert!(!rng.chance(-1.0));
        assert!(rng.chance(1.0));
        assert!(rng.chance(2.0));

        // p = 0.5 over many draws should land somewhere in the middle.
        let mut a = Rng::from_seed(2);
        let hits = (0..10_000).filter(|_| a.chance(0.5)).count();
        assert!((4000..6000).contains(&hits), "0.5 chance produced {hits}/10000");
    }
}