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}