Skip to main content

dive_stdlib/random/
seeding.rs

1//! Where each random stream starts: TLC's seeding, and dive's replayable seeding.
2
3use super::source::{JavaRandom, RandomSource};
4
5/// Which seeding a run uses.
6#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
7pub enum RandomMode {
8    /// TLC's seeding with `java.util.Random`, bit-exact (`--compat=tlc`). Requires
9    /// TLC's own state fingerprints for state-level draws.
10    Tlc,
11    /// dive's seeding: every stream is a pure function of the seed, a
12    /// stream key (the state's fingerprint, or a simulation trace number) and the call
13    /// index, so a run replays at any worker count. Any 64-bit state fingerprint works.
14    Dive,
15}
16
17/// The run's seed and seeding: hands out the random stream for each evaluation.
18///
19/// **Model checking** (TLC's `RandomEnumerableValues`, `TLCStateRandom`):
20/// - [`Streams::startup`] is one stream, used in order by the constant definitions
21///   TLC evaluates at start-up, the `ASSUME`s, and the initial predicate, including
22///   invariants checked on initial states. In TLC this is the main thread's
23///   generator: `new Random(seed)`, never reseeded.
24/// - [`Streams::state`] is the stream for everything evaluated while expanding one
25///   state: its next-state relation (all actions, in order), and the checks on the
26///   successors. TLC reseeds the worker's generator to `fingerprint(state) ^ seed`
27///   on the first draw for each newly expanded state, and keeps drawing from it for
28///   the rest of that expansion.
29/// - Trace reconstruction replays with the same streams: [`Streams::startup`] for
30///   the initial states, then [`Streams::state`] per predecessor (TLC resets the
31///   generator, `ConcurrentTLCTrace.getTrace`). In TLC the reset stream does *not*
32///   replay draws made by start-up definitions and `ASSUME`s before `Init`, so a
33///   violation that depends on them can lose its counterexample.
34///
35/// **Simulation** (TLC's `Simulator`, `SimulationWorker`, `DefaultRandom`):
36/// - [`Streams::startup`] serves constants, `ASSUME`s and the initial states, as above.
37/// - Each worker chooses initial states, actions and successors with its own
38///   generator, seeded from [`Streams::tlc_simulation_worker_seeds`].
39/// - Each worker evaluates `RandomElement` and friends with
40///   [`Streams::tlc_simulation_values`], `new Random(seed)` per worker thread,
41///   never reseeded; so in TLC every worker draws the same value sequence.
42///
43/// In [`RandomMode::Dive`], [`Streams::simulation_trace`] replaces both per-worker
44/// generators with one stream per trace number, so traces are reproducible whatever
45/// worker runs them.
46#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
47pub struct Streams {
48    seed: i64,
49    mode: RandomMode,
50}
51
52impl Streams {
53    /// The streams of a run with `seed` (always reported) in `mode`.
54    #[must_use]
55    pub const fn new(seed: i64, mode: RandomMode) -> Self {
56        Self { seed, mode }
57    }
58
59    /// The run's seed, as reported (`TLCGet("config").seed`).
60    #[must_use]
61    pub const fn seed(&self) -> i64 {
62        self.seed
63    }
64
65    /// The seeding mode.
66    #[must_use]
67    pub const fn mode(&self) -> RandomMode {
68        self.mode
69    }
70
71    /// The start-up stream: constant definitions, `ASSUME`s and `Init`, in TLC's
72    /// evaluation order.
73    #[must_use]
74    pub const fn startup(&self) -> Stream {
75        match self.mode {
76            RandomMode::Tlc => Stream::Java(JavaRandom::new(self.seed)),
77            RandomMode::Dive => Stream::Dive(DiveStream::new(self.seed, Domain::Startup, 0)),
78        }
79    }
80
81    /// The stream for expanding the state with fingerprint `fp`: under
82    /// [`RandomMode::Tlc`] TLC's state fingerprint (`TLCState.fingerPrint`), seeding
83    /// `new Random(fp ^ seed)` (`RandomEnumerableValues.TLCStateRandom`).
84    #[must_use]
85    pub const fn state(&self, fp: u64) -> Stream {
86        match self.mode {
87            #[allow(clippy::cast_possible_wrap, reason = "Java's long: same bits")]
88            RandomMode::Tlc => Stream::Java(JavaRandom::new(fp as i64 ^ self.seed)),
89            RandomMode::Dive => Stream::Dive(DiveStream::new(self.seed, Domain::State, fp)),
90        }
91    }
92
93    /// TLC simulation: the seeds of the `workers` simulation workers' generators,
94    /// `rng.nextLong()` each in worker order after `rng.setSeed(seed, aril)`
95    /// (`TLC.process`, `Simulator` constructor). With TLC's default (no `-seed`) the
96    /// seed itself came from an unseeded generator and `aril` is ignored; pass 0.
97    #[must_use]
98    pub fn tlc_simulation_worker_seeds(&self, aril: u64, workers: usize) -> Vec<i64> {
99        let mut rng = JavaRandom::new(self.seed);
100        rng.set_seed_aril(self.seed, aril);
101        (0..workers).map(|_| rng.next_long()).collect()
102    }
103
104    /// TLC simulation: a worker thread's generator for `RandomElement` and the
105    /// `Randomization` operators (`RandomEnumerableValues.DefaultRandom`).
106    #[must_use]
107    pub const fn tlc_simulation_values(&self) -> JavaRandom {
108        JavaRandom::new(self.seed)
109    }
110
111    /// dive simulation: the single stream of trace number `trace` (0-based, in the
112    /// order traces are numbered, not the order workers finish them). It drives the
113    /// choice of initial state, actions and successors, and the operators' draws.
114    #[must_use]
115    pub const fn simulation_trace(&self, trace: u64) -> Stream {
116        Stream::Dive(DiveStream::new(self.seed, Domain::Simulation, trace))
117    }
118}
119
120/// A random stream: TLC's generator or dive's.
121#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
122pub enum Stream {
123    /// `java.util.Random`.
124    Java(JavaRandom),
125    /// dive's counter-based stream.
126    Dive(DiveStream),
127}
128
129impl RandomSource for Stream {
130    fn next_bits(&mut self, bits: u32) -> i32 {
131        match self {
132            Self::Java(r) => r.next_bits(bits),
133            Self::Dive(r) => r.next_bits(bits),
134        }
135    }
136}
137
138/// What a dive stream is keyed by, so that streams of different kinds never
139/// coincide.
140#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
141enum Domain {
142    Startup,
143    State,
144    Simulation,
145}
146
147impl Domain {
148    const fn tag(self) -> u64 {
149        match self {
150            Self::Startup => 0x5354_4152_5455_5021,    // "STARTUP!"
151            Self::State => 0x5354_4154_4521_2121,      // "STATE!!!"
152            Self::Simulation => 0x5349_4d55_4c41_5445, // "SIMULATE"
153        }
154    }
155}
156
157/// dive's random stream: draw `i` of the stream keyed by `(seed, domain, key)` is
158/// `SplitMix64(k + (i + 1) * γ)`, with `k` a mix of the seed, domain and key. It is
159/// counter based, so draw `i` depends only on `(seed, key, i)`: never on which
160/// worker evaluates it or what it evaluated before.
161#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
162pub struct DiveStream {
163    key: u64,
164    counter: u64,
165}
166
167const GOLDEN_GAMMA: u64 = 0x9e37_79b9_7f4a_7c15;
168
169/// `SplitMix64`'s finalizer (Steele, Lea and Flood, "Fast splittable pseudorandom number
170/// generators", OOPSLA 2014), a bijection on 64-bit words.
171const fn mix64(mut z: u64) -> u64 {
172    z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
173    z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
174    z ^ (z >> 31)
175}
176
177impl DiveStream {
178    #[allow(clippy::cast_sign_loss, reason = "the seed's bits")]
179    const fn new(seed: i64, domain: Domain, key: u64) -> Self {
180        let k = mix64(mix64(seed as u64 ^ domain.tag()) ^ key);
181        Self { key: k, counter: 0 }
182    }
183
184    /// How many 64-bit words the stream has produced (the call index).
185    #[must_use]
186    pub const fn position(&self) -> u64 {
187        self.counter
188    }
189}
190
191impl RandomSource for DiveStream {
192    fn next_bits(&mut self, bits: u32) -> i32 {
193        debug_assert!((1..=32).contains(&bits));
194        self.counter = self.counter.wrapping_add(1);
195        let word = mix64(
196            self.key
197                .wrapping_add(self.counter.wrapping_mul(GOLDEN_GAMMA)),
198        );
199        #[allow(clippy::cast_possible_truncation, reason = "the top `bits` bits")]
200        let v = (word >> (64 - bits)) as u32;
201        v.cast_signed()
202    }
203}
204
205/// Parses a seed as TLC's `-seed` does (`Long.parseLong`): an optional `+` or `-`
206/// and decimal digits, within the range of a 64-bit signed integer.
207///
208/// Java also accepts non-ASCII decimal digits (`Character.digit`); dive refuses
209/// them, returning `None` like any other malformed seed.
210#[must_use]
211pub fn parse_seed(text: &str) -> Option<i64> {
212    let digits = text
213        .strip_prefix('+')
214        .or_else(|| text.strip_prefix('-'))
215        .unwrap_or(text);
216    if digits.is_empty() || !digits.bytes().all(|b| b.is_ascii_digit()) {
217        return None;
218    }
219    // `i64::from_str` accepts exactly this grammar (sign, ASCII digits) and range.
220    text.parse().ok()
221}
222
223/// A fresh seed for a run without `--seed`, as TLC draws one without `-seed`
224/// (`new RandomGenerator().nextLong()`, seeded from the clock). dive always
225/// reports the seed it used, so the run can be replayed.
226#[must_use]
227pub fn fresh_seed() -> i64 {
228    use std::hash::{BuildHasher, Hasher};
229    let mut h = std::collections::hash_map::RandomState::new().build_hasher();
230    if let Ok(d) = std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH) {
231        h.write_u128(d.as_nanos());
232    }
233    h.write_u32(std::process::id());
234    h.finish().cast_signed()
235}
236
237#[cfg(test)]
238mod tests {
239    use super::*;
240
241    #[test]
242    fn seeds_parse_like_long_parse_long() {
243        assert_eq!(parse_seed("7"), Some(7));
244        assert_eq!(parse_seed("+7"), Some(7));
245        assert_eq!(parse_seed("-0"), Some(0));
246        assert_eq!(parse_seed("-9223372036854775808"), Some(i64::MIN));
247        assert_eq!(parse_seed("9223372036854775808"), None);
248        for bad in ["", "+", "-", " 7", "7 ", "0x10", "1e3", "--1", "+-1", "٧"] {
249            assert_eq!(parse_seed(bad), None, "{bad:?}");
250        }
251    }
252
253    #[test]
254    fn dive_streams_are_keyed() {
255        let s = Streams::new(42, RandomMode::Dive);
256        let draws = |mut st: Stream| (0..4).map(|_| st.next_long()).collect::<Vec<_>>();
257        assert_eq!(draws(s.state(5)), draws(s.state(5)));
258        assert_ne!(draws(s.state(5)), draws(s.state(6)));
259        assert_ne!(draws(s.state(0)), draws(s.startup()));
260        assert_ne!(draws(s.state(0)), draws(s.simulation_trace(0)));
261        assert_ne!(
262            draws(s.state(5)),
263            draws(Streams::new(43, RandomMode::Dive).state(5))
264        );
265    }
266
267    #[test]
268    fn tlc_state_stream_is_fp_xor_seed() {
269        let s = Streams::new(7, RandomMode::Tlc);
270        assert_eq!(s.state(0x10), Stream::Java(JavaRandom::new(0x17)));
271        assert_eq!(s.startup(), Stream::Java(JavaRandom::new(7)));
272    }
273}