logicaffeine_runtime/
seed.rs

1//! Seed, deterministic RNG, and the choice trace — the determinism contract.
2//!
3//! Every nondeterministic scheduling decision flows through a single choke point,
4//! [`Chooser::decide`]. In *record* mode it draws from a seeded RNG and logs a
5//! [`ChoicePoint`]; in *replay* mode it returns the next recorded choice and
6//! asserts the decision shape still matches (divergence detection). This is what
7//! makes a concurrent program a deterministic function of `(program, seed)` and
8//! exactly reproducible from `(program, trace)` — the property the interpreter,
9//! VM, and translation validation all rely on.
10
11/// The scheduling seed. A fixed seed makes execution fully deterministic.
12#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
13pub struct SchedSeed(pub u64);
14
15/// A small, deterministic, WASM-safe PRNG (SplitMix64).
16///
17/// SplitMix64 is chosen for being tiny, allocation-free, and identical on every
18/// target (no platform `Rng`, no `Math.random`), so a seed reproduces bit-for-bit
19/// across native and WASM.
20#[derive(Debug, Clone)]
21pub struct SeededRng {
22    state: u64,
23}
24
25impl SeededRng {
26    /// A fresh RNG from a seed.
27    pub fn new(seed: SchedSeed) -> Self {
28        SeededRng { state: seed.0 }
29    }
30
31    /// Next 64-bit value (SplitMix64).
32    pub fn next_u64(&mut self) -> u64 {
33        self.state = self.state.wrapping_add(0x9E37_79B9_7F4A_7C15);
34        let mut z = self.state;
35        z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
36        z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
37        z ^ (z >> 31)
38    }
39
40    /// A uniformly-distributed index in `[0, n)`. Returns 0 when `n <= 1`.
41    pub fn below(&mut self, n: usize) -> usize {
42        if n <= 1 {
43            return 0;
44        }
45        (self.next_u64() % n as u64) as usize
46    }
47}
48
49/// The class of a scheduling decision — recorded so replay can detect divergence.
50#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
51pub enum ChoiceKind {
52    /// Which ready task to run next.
53    TaskPick,
54    /// Which ready branch of a `Select` wins.
55    SelectWinner,
56    /// Which blocked channel waiter to wake.
57    ChanWaiterWake,
58    /// Tie-break order among timers firing on the same logical tick.
59    TimerTieBreak,
60    /// Which worker a newly spawned task is placed on (M:N work-stealing).
61    WorkerPlacement,
62}
63
64/// One recorded nondeterministic decision: its kind, how many options were
65/// available, and which index was taken. This shape is intentionally
66/// id-agnostic, so the trace format does not depend on `TaskId`/`ChanId`/etc.
67#[derive(Debug, Clone, Copy, PartialEq, Eq)]
68pub struct ChoicePoint {
69    /// What kind of decision this was.
70    pub kind: ChoiceKind,
71    /// The number of options that were available.
72    pub options: usize,
73    /// The index chosen, in `[0, options)`.
74    pub chosen: usize,
75}
76
77/// A full record of the scheduling decisions a run made. Replay it for an exact
78/// re-execution, or compare two traces to detect a divergence.
79#[derive(Debug, Clone, PartialEq)]
80pub struct SchedTrace {
81    /// The seed the run was recorded under.
82    pub seed: SchedSeed,
83    /// The decisions, in the order they were made.
84    pub choices: Vec<ChoicePoint>,
85}
86
87/// The decision choke point: records (seeded) or replays scheduling choices.
88///
89/// THE single source of nondeterminism in the runtime — every scheduler choice
90/// goes through [`Chooser::decide`]. Nothing else draws entropy.
91#[derive(Debug, Clone)]
92pub enum Chooser {
93    /// Recording: draw from the seeded RNG and log each choice.
94    Record {
95        rng: SeededRng,
96        seed: SchedSeed,
97        choices: Vec<ChoicePoint>,
98    },
99    /// Replaying: re-issue the recorded choices, asserting the shapes still match.
100    Replay { trace: SchedTrace, pos: usize },
101}
102
103impl Chooser {
104    /// A fresh recording chooser seeded by `seed`.
105    pub fn record(seed: SchedSeed) -> Self {
106        Chooser::Record {
107            rng: SeededRng::new(seed),
108            seed,
109            choices: Vec::new(),
110        }
111    }
112
113    /// A replaying chooser that re-issues the decisions in `trace`.
114    pub fn replay(trace: SchedTrace) -> Self {
115        Chooser::Replay { trace, pos: 0 }
116    }
117
118    /// Resolve one decision among `options` choices, returning the chosen index.
119    ///
120    /// Record mode draws from the seeded RNG and logs the choice. Replay mode
121    /// returns the recorded choice, panicking if the decision shape diverges from
122    /// what was recorded (a different `kind` or `options` count, or running past
123    /// the end of the trace).
124    pub fn decide(&mut self, kind: ChoiceKind, options: usize) -> usize {
125        match self {
126            Chooser::Record { rng, choices, .. } => {
127                let chosen = rng.below(options);
128                choices.push(ChoicePoint { kind, options, chosen });
129                chosen
130            }
131            Chooser::Replay { trace, pos } => {
132                let cp = trace.choices.get(*pos).copied().unwrap_or_else(|| {
133                    panic!(
134                        "replay divergence: ran out of recorded choices at index {} \
135                         (live decision was {:?} over {} options)",
136                        pos, kind, options
137                    )
138                });
139                assert_eq!(
140                    cp.kind, kind,
141                    "replay divergence at {}: recorded {:?}, live {:?}",
142                    *pos, cp.kind, kind
143                );
144                assert_eq!(
145                    cp.options, options,
146                    "replay divergence at {}: recorded {} options, live {}",
147                    *pos, cp.options, options
148                );
149                *pos += 1;
150                cp.chosen
151            }
152        }
153    }
154
155    /// Finish and return the trace (returns the original trace for a replay chooser).
156    pub fn into_trace(self) -> SchedTrace {
157        match self {
158            Chooser::Record { seed, choices, .. } => SchedTrace { seed, choices },
159            Chooser::Replay { trace, .. } => trace,
160        }
161    }
162}
163
164#[cfg(test)]
165mod tests {
166    use super::*;
167
168    #[test]
169    fn seed_rng_is_deterministic() {
170        let mut a = SeededRng::new(SchedSeed(42));
171        let mut b = SeededRng::new(SchedSeed(42));
172        let seq_a: Vec<u64> = (0..16).map(|_| a.next_u64()).collect();
173        let seq_b: Vec<u64> = (0..16).map(|_| b.next_u64()).collect();
174        assert_eq!(seq_a, seq_b, "same seed must yield the same stream");
175
176        let mut c = SeededRng::new(SchedSeed(43));
177        let seq_c: Vec<u64> = (0..16).map(|_| c.next_u64()).collect();
178        assert_ne!(seq_a, seq_c, "different seeds must (almost surely) differ");
179    }
180
181    #[test]
182    fn seed_below_is_in_range() {
183        let mut r = SeededRng::new(SchedSeed(7));
184        for _ in 0..1000 {
185            assert!(r.below(5) < 5);
186        }
187        assert_eq!(r.below(0), 0, "below(0) is 0");
188        assert_eq!(r.below(1), 0, "below(1) is 0");
189    }
190
191    #[test]
192    fn replay_roundtrip_is_bit_identical() {
193        let shapes = [
194            (ChoiceKind::TaskPick, 3usize),
195            (ChoiceKind::SelectWinner, 2),
196            (ChoiceKind::TaskPick, 4),
197            (ChoiceKind::TimerTieBreak, 2),
198            (ChoiceKind::WorkerPlacement, 8),
199        ];
200        let mut rec = Chooser::record(SchedSeed(1234));
201        let recorded: Vec<usize> = shapes.iter().map(|(k, n)| rec.decide(*k, *n)).collect();
202        let trace = rec.into_trace();
203
204        let mut rep = Chooser::replay(trace.clone());
205        let replayed: Vec<usize> = shapes.iter().map(|(k, n)| rep.decide(*k, *n)).collect();
206        assert_eq!(recorded, replayed, "replay reproduces the recorded choices");
207
208        // Same seed + same shapes records identically (reproducibility).
209        let mut rec2 = Chooser::record(SchedSeed(1234));
210        let recorded2: Vec<usize> = shapes.iter().map(|(k, n)| rec2.decide(*k, *n)).collect();
211        assert_eq!(recorded, recorded2, "same seed is reproducible");
212        assert_eq!(trace.seed, SchedSeed(1234));
213        assert_eq!(trace.choices.len(), shapes.len());
214    }
215
216    #[test]
217    #[should_panic(expected = "replay divergence")]
218    fn replay_divergence_panics_on_option_mismatch() {
219        let mut rec = Chooser::record(SchedSeed(9));
220        rec.decide(ChoiceKind::TaskPick, 3);
221        let trace = rec.into_trace();
222
223        let mut rep = Chooser::replay(trace);
224        // Feed a different option count than was recorded -> divergence.
225        rep.decide(ChoiceKind::TaskPick, 5);
226    }
227
228    #[test]
229    #[should_panic(expected = "replay divergence")]
230    fn replay_divergence_panics_on_kind_mismatch() {
231        let mut rec = Chooser::record(SchedSeed(9));
232        rec.decide(ChoiceKind::TaskPick, 3);
233        let trace = rec.into_trace();
234
235        let mut rep = Chooser::replay(trace);
236        rep.decide(ChoiceKind::SelectWinner, 3);
237    }
238}
logicaffeine_runtime/seed.rs

logicaffeine_runtime/
seed.rs
