vj-sim 0.3.0

//! The `randc` cyclic permutation engine (plan C5; LRM 1800-2023 18.4.2).
//!
//! # What the LRM requires
//!
//! A `randc` variable "cycles through all the values in a random permutation
//! of its declared range", and "the permutation sequence for any given randc
//! variable is recomputed whenever the constraints on that variable change, or
//! when none of the remaining values in the permutation can satisfy the
//! constraints". So one variable has a *cycle state*: the values of its legal
//! set it has not yet produced in the current permutation, in permutation
//! order. A draw takes the next value of the permutation, a new permutation
//! is drawn when the cycle is exhausted, and a change to the legal set starts a
//! new permutation too (Figure 18-1: no value repeats within a cycle).
//!
//! # What this module is
//!
//! Only the per-variable state machine ([`RandcState`], [`pick`]); it knows
//! nothing about BDDs. The solver ([`super::solve::Solver::sample_plan`])
//! supplies the legal set (a closure, evaluated only when a permutation is
//! drawn) and a feasibility test (the value must be consistent with the other
//! constraints and with the `randc` values picked before it).
//!
//! # Choices that go beyond the LRM text
//!
//! * *Fingerprint*. "The constraints on that variable change" is detected by a
//!   caller-supplied 64-bit fingerprint of the variable's legal set (a hash of
//!   the canonical BDD that [`super::solve`] projects onto the variable).
//!   Another random variable changing does not change it (the projection
//!   existentially quantifies the others), a state variable read by the
//!   constraints does.
//! * *Skipping*. A value of the permutation that is infeasible *right now*
//!   (it conflicts with an earlier `randc` pick of the same call) is skipped,
//!   not consumed: it stays in the permutation for a later call. If nothing
//!   left in the permutation is feasible a new permutation is drawn (the LRM's
//!   "none of the remaining values ... can satisfy the constraints").
//! * *Width*. The permutation is materialised, so a `randc` variable is limited
//!   to [`MAX_RANDC_WIDTH`] bits (the LRM allows an implementation limit and
//!   requires it to be at least 8, 18.4.2).

use super::rng;
use num_bigint::BigUint;
use num_traits::ToPrimitive;

/// The widest `randc` variable this implementation accepts. LRM 18.4.2: "The
/// size of randc variables may be restricted. The restriction shall be that
/// randc variables of 8 bits or less must be supported" (the permutation is
/// stored explicitly, so 16 bits is 64Ki entries).
pub const MAX_RANDC_WIDTH: u32 = 16;

/// The cycle state of one `randc` variable of one object.
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct RandcState {
    /// Whether a permutation has been drawn at all.
    pub live: bool,
    /// The fingerprint of the legal set the permutation was drawn from.
    pub fingerprint: u64,
    /// The values of the current permutation not yet produced, next first.
    pub remaining: Vec<u32>,
}

/// FNV-1a over `bytes`: the fingerprint of a serialised legal set.
pub fn fingerprint_of(bytes: &[u8]) -> u64 {
    let mut h = 0xcbf2_9ce4_8422_2325u64;
    for &b in bytes {
        h ^= u64::from(b);
        h = h.wrapping_mul(0x0100_0000_01b3);
    }
    h
}

/// Fisher-Yates over `values`, drawing from `seed`.
fn shuffle(values: &mut [u32], seed: &mut u64) {
    for i in (1..values.len()).rev() {
        let j = rng::below(seed, &BigUint::from(i as u64 + 1))
            .to_usize()
            .expect("a draw below a usize bound fits a usize");
        values.swap(i, j);
    }
}

/// Starts a new permutation of `legal` in `state`.
fn reshuffle(state: &mut RandcState, fingerprint: u64, mut legal: Vec<u32>, seed: &mut u64) {
    shuffle(&mut legal, seed);
    state.live = true;
    state.fingerprint = fingerprint;
    state.remaining = legal;
}

/// The next value of `state`'s cycle (module docs), or `None` if no value of
/// the legal set is feasible at all.
///
/// `legal` lists the variable's legal values (ascending); it is only called
/// when a permutation is drawn. `feasible` says whether a value can be
/// completed to a full solution right now.
pub fn pick(
    state: &mut RandcState,
    fingerprint: u64,
    legal: &mut dyn FnMut() -> Vec<u32>,
    feasible: &mut dyn FnMut(u32) -> bool,
    seed: &mut u64,
) -> Option<u32> {
    let mut fresh = false;
    if !state.live || state.fingerprint != fingerprint {
        reshuffle(state, fingerprint, legal(), seed);
        fresh = true;
    }
    loop {
        if let Some(i) = state.remaining.iter().position(|&v| feasible(v)) {
            return Some(state.remaining.remove(i));
        }
        if fresh {
            // A whole permutation of the legal set and nothing feasible.
            return None;
        }
        // Exhausted (or only infeasible values left): the next cycle.
        reshuffle(state, fingerprint, legal(), seed);
        fresh = true;
    }
}

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

    fn draw(state: &mut RandcState, legal: &[u32], seed: &mut u64) -> u32 {
        pick(state, 1, &mut || legal.to_vec(), &mut |_| true, seed).expect("a value")
    }

    #[test]
    fn a_cycle_visits_every_value_once_then_starts_again() {
        // LRM Figure 18-1: a 2-bit randc variable cycles through all four
        // values before any repeats, then does it again.
        let mut st = RandcState::default();
        let mut seed = 7;
        let legal = [0, 1, 2, 3];
        for _ in 0..50 {
            let mut cycle: Vec<u32> = (0..4).map(|_| draw(&mut st, &legal, &mut seed)).collect();
            cycle.sort_unstable();
            assert_eq!(cycle, vec![0, 1, 2, 3]);
        }
    }

    #[test]
    fn permutations_differ_between_cycles() {
        let mut st = RandcState::default();
        let mut seed = 99;
        let legal: Vec<u32> = (0..16).collect();
        let cycles: Vec<Vec<u32>> = (0..20)
            .map(|_| (0..16).map(|_| draw(&mut st, &legal, &mut seed)).collect())
            .collect();
        let distinct: std::collections::BTreeSet<_> = cycles.iter().collect();
        assert!(distinct.len() > 15, "{} distinct of 20", distinct.len());
    }

    #[test]
    fn every_position_of_the_permutation_is_uniform() {
        // The first value of a fresh permutation is uniform over the legal
        // set (a biased shuffle would show here).
        let mut counts = [0u32; 5];
        let mut seed = 3;
        for _ in 0..5000 {
            let mut st = RandcState::default();
            counts[draw(&mut st, &[0, 1, 2, 3, 4], &mut seed) as usize] += 1;
        }
        for c in counts {
            assert!((880..1120).contains(&c), "{counts:?}");
        }
    }

    #[test]
    fn a_changed_fingerprint_starts_a_new_permutation() {
        let mut st = RandcState::default();
        let mut seed = 5;
        let first = pick(
            &mut st,
            1,
            &mut || vec![0, 1, 2, 3],
            &mut |_| true,
            &mut seed,
        )
        .unwrap();
        assert_eq!(st.remaining.len(), 3);
        // The legal set shrinks (the constraint changed): values consumed in
        // the old cycle are available again.
        let mut seen = std::collections::BTreeSet::new();
        for _ in 0..2 {
            seen.insert(pick(&mut st, 2, &mut || vec![0, 1], &mut |_| true, &mut seed).unwrap());
        }
        assert_eq!(seen, [0, 1].into_iter().collect());
        assert_eq!(st.fingerprint, 2);
        assert!(first < 4);
    }

    #[test]
    fn an_infeasible_value_is_skipped_not_consumed() {
        let mut st = RandcState::default();
        let mut seed = 11;
        // 2 is infeasible this call, feasible later.
        let a = pick(
            &mut st,
            1,
            &mut || vec![0, 1, 2],
            &mut |v| v != 2,
            &mut seed,
        )
        .unwrap();
        let b = pick(
            &mut st,
            1,
            &mut || vec![0, 1, 2],
            &mut |v| v != 2,
            &mut seed,
        )
        .unwrap();
        assert_ne!(a, b);
        assert!(a != 2 && b != 2);
        assert_eq!(st.remaining, vec![2], "2 stays in the permutation");
        let c = pick(&mut st, 1, &mut || vec![0, 1, 2], &mut |_| true, &mut seed).unwrap();
        assert_eq!(c, 2, "and is produced once it is feasible");
    }

    #[test]
    fn nothing_feasible_in_the_rest_of_the_cycle_draws_a_new_one() {
        let mut st = RandcState::default();
        let mut seed = 13;
        assert!(pick(&mut st, 1, &mut || vec![0, 1], &mut |v| v == 0, &mut seed).is_some());
        // Only 1 is left, and it is infeasible: new permutation, 0 again.
        let v = pick(&mut st, 1, &mut || vec![0, 1], &mut |v| v == 0, &mut seed).unwrap();
        assert_eq!(v, 0);
    }

    #[test]
    fn no_feasible_value_at_all_is_none_and_the_state_stays_usable() {
        let mut st = RandcState::default();
        let mut seed = 17;
        assert_eq!(
            pick(&mut st, 1, &mut || vec![0, 1], &mut |_| false, &mut seed),
            None
        );
        assert!(pick(&mut st, 1, &mut || vec![0, 1], &mut |_| true, &mut seed).is_some());
    }

    #[test]
    fn the_draws_are_a_pure_function_of_the_seed() {
        let run = |s0: u64| {
            let mut st = RandcState::default();
            let mut seed = s0;
            (0..40)
                .map(|_| draw(&mut st, &[0, 1, 2, 3, 4, 5], &mut seed))
                .collect::<Vec<_>>()
        };
        assert_eq!(run(1), run(1));
        assert_ne!(run(1), run(2));
    }

    #[test]
    fn fingerprints_tell_different_byte_strings_apart() {
        assert_eq!(fingerprint_of(b"abc"), fingerprint_of(b"abc"));
        assert_ne!(fingerprint_of(b"abc"), fingerprint_of(b"abd"));
        assert_ne!(fingerprint_of(b""), fingerprint_of(b"\0"));
    }
}