spawned_rt/tasks/
sim_test.rs

1//! Seeded test harness that runs one test body on Tokio in normal builds and
2//! over a range of seeds on the deterministic simulator under
3//! `--cfg spawned_sim`. Use it directly, or through `#[spawned_macros::sim_test]`.
4//!
5//! ```ignore
6//! spawned_rt::tasks::sim_test(|seed| async move {
7//!     // test body
8//! });
9//! ```
10//!
11//! Environment (simulation builds only):
12//!
13//! | Variable | Effect |
14//! |---|---|
15//! | `SPAWNED_SIM_SEED=n` | run only seed `n` (also the seed passed to the body on Tokio) |
16//! | `SPAWNED_SIM_SEEDS=n` | run seeds `0..n` (default 8) |
17//! | `SPAWNED_SIM_TAPE=path` | replay a recorded decision tape instead of seeds |
18//! | `SPAWNED_SIM_TAPE_DIR=dir` | where failing tapes are written (default `$TMPDIR/spawned-sim`) |
19//! | `SPAWNED_SIM_SHRINK=n` | runs the tape shrinker may spend on a failure (default 200, 0 = off) |
20//! | `SPAWNED_SIM_STRATEGY=s` | `random` (default), `pct[:d=3][,k=N]` or `dfs[:bound=2][,depth=N]` (see `sim::explore`); overrides the test's `explore` |
21//! | `SPAWNED_SIM_ITERATIONS=n` | runs for that strategy (default 8 for random, 100 otherwise); overrides the test's `iterations` |
22//! | `SPAWNED_SIM_FAIR_AFTER=n` | polls after which a PCT/DFS run switches to a fair scheduler (default 20,000) |
23
24use std::future::Future;
25use std::ops::Range;
26
27/// Builder for one seeded test. See the module docs.
28#[derive(Debug, Clone, Default)]
29pub struct SimTest {
30    package: Option<String>,
31    module: Option<String>,
32    function: Option<String>,
33    seeds: Option<Range<u64>>,
34    workers: Option<usize>,
35    explore: Option<String>,
36    iterations: Option<usize>,
37}
38
39/// Run `body` as a seeded test with the default settings.
40pub fn sim_test<F, Fut>(body: F)
41where
42    F: Fn(u64) -> Fut,
43    Fut: Future<Output = ()>,
44{
45    SimTest::new().run(body)
46}
47
48fn env_u64(name: &str) -> Option<u64> {
49    std::env::var(name).ok().and_then(|v| v.trim().parse().ok())
50}
51
52impl SimTest {
53    pub fn new() -> Self {
54        Self::default()
55    }
56    /// Where the test lives, for the replay command: the package name, the
57    /// test's `module_path!()` and its function name.
58    pub fn named(mut self, package: &str, module: &str, function: &str) -> Self {
59        self.package = Some(package.into());
60        self.module = Some(module.into());
61        self.function = Some(function.into());
62        self
63    }
64    /// Seeds to run under simulation (default `0..SPAWNED_SIM_SEEDS`, or 0..8).
65    pub fn seeds(mut self, seeds: Range<u64>) -> Self {
66        self.seeds = Some(seeds);
67        self
68    }
69    /// Under simulation, choose tasks with this strategy (`random`,
70    /// `pct[:d=3][,k=N]`, `dfs[:bound=2][,depth=N]`); `SPAWNED_SIM_STRATEGY`
71    /// overrides it. Ignored on Tokio.
72    pub fn explore(mut self, strategy: &str) -> Self {
73        self.explore = Some(strategy.into());
74        self
75    }
76    /// Under simulation, how many runs the strategy may spend (for `random`,
77    /// seeds `0..n` unless [`SimTest::seeds`] is set); `SPAWNED_SIM_ITERATIONS`
78    /// overrides it. Ignored on Tokio.
79    pub fn iterations(mut self, runs: usize) -> Self {
80        self.iterations = Some(runs);
81        self
82    }
83    /// On Tokio, use a multi-thread runtime with `workers` workers (the
84    /// default is a current-thread runtime, as `#[tokio::test]`). Ignored
85    /// under simulation, which always has one thread.
86    pub fn multi_thread(mut self, workers: usize) -> Self {
87        self.workers = Some(workers);
88        self
89    }
90
91    /// First seed and number of runs for `strategy`. `SPAWNED_SIM_SEED`
92    /// (`seed`) fixes the body's input: a single run for random and PCT, and
93    /// the input of every schedule for DFS (which varies the schedule, not
94    /// the seed).
95    #[cfg(spawned_sim)]
96    fn runs(
97        &self,
98        strategy: &super::sim::explore::Strategy,
99        seed: Option<u64>,
100        iterations: Option<usize>,
101    ) -> (u64, usize) {
102        use super::sim::explore::Strategy;
103        match (strategy, seed) {
104            (Strategy::Dfs { .. }, seed) => (seed.unwrap_or(0), iterations.unwrap_or(100)),
105            (_, Some(seed)) => (seed, 1),
106            (Strategy::Random, None) => match (&self.seeds, iterations) {
107                (Some(seeds), _) => (seeds.start, seeds.end.saturating_sub(seeds.start) as usize),
108                (None, Some(n)) => (0, n),
109                (None, None) => (0, env_u64("SPAWNED_SIM_SEEDS").unwrap_or(8) as usize),
110            },
111            (Strategy::Pct { .. }, None) => (0, iterations.unwrap_or(100)),
112        }
113    }
114
115    /// The libtest name (`path::to::test`) and a `cargo test` selector.
116    #[cfg_attr(not(spawned_sim), allow(dead_code))]
117    fn locate(&self) -> (String, String) {
118        let thread = std::thread::current();
119        let fallback = thread.name().unwrap_or("test").to_string();
120        let (Some(package), Some(module), Some(function)) =
121            (&self.package, &self.module, &self.function)
122        else {
123            return (
124                fallback.clone(),
125                format!("cargo test -- {fallback} --exact"),
126            );
127        };
128        let mut segments = module.split("::");
129        let krate = segments.next().unwrap_or_default();
130        let path: Vec<&str> = segments.chain(std::iter::once(function.as_str())).collect();
131        let path = path.join("::");
132        let target = if krate == package.replace('-', "_") {
133            "--lib".to_string()
134        } else {
135            format!("--test {krate}")
136        };
137        let command = format!("cargo test -p {package} {target} -- {path} --exact");
138        (path, command)
139    }
140
141    #[cfg(not(spawned_sim))]
142    pub fn run<F, Fut>(self, body: F)
143    where
144        F: Fn(u64) -> Fut,
145        Fut: Future<Output = ()>,
146    {
147        let seed = env_u64("SPAWNED_SIM_SEED").unwrap_or(0);
148        let runtime = match self.workers {
149            Some(workers) => ::tokio::runtime::Builder::new_multi_thread()
150                .worker_threads(workers)
151                .enable_all()
152                .build(),
153            None => ::tokio::runtime::Builder::new_current_thread()
154                .enable_all()
155                .build(),
156        }
157        .expect("failed to build the test runtime");
158        runtime.block_on(body(seed));
159    }
160
161    #[cfg(spawned_sim)]
162    pub fn run<F, Fut>(self, body: F)
163    where
164        F: Fn(u64) -> Fut,
165        Fut: Future<Output = ()>,
166    {
167        use super::sim::explore::{explore, Strategy};
168        use super::sim::{run_once, shrink, Tape};
169        let (name, command) = self.locate();
170        // Scheduling settings that change what a seed does travel with the
171        // replay command (a tape records its own).
172        let settings: String = [
173            "SPAWNED_SIM_SPIN",
174            "SPAWNED_SIM_MAX_STEPS",
175            "SPAWNED_SIM_FAIR_AFTER",
176        ]
177        .iter()
178        .filter_map(|key| std::env::var(key).ok().map(|v| format!("{key}={v} ")))
179        .collect();
180        let replay = |prefix: &str| {
181            format!(
182                "{settings}{prefix} RUSTFLAGS=\"--cfg spawned_sim --cfg tokio_unstable\" {command}"
183            )
184        };
185
186        if let Ok(path) = std::env::var("SPAWNED_SIM_TAPE") {
187            let tape = Tape::load(path.as_ref())
188                .unwrap_or_else(|e| panic!("spawned_sim: cannot load tape {path}: {e}"));
189            let outcome = run_once(tape.seed, Some(&tape), &body);
190            // Strict: a tape that no longer applies fails as `replay diverged`.
191            eprintln!(
192                "spawned_sim: `{name}` replayed tape {path} (seed {}, {} polls)",
193                tape.seed, outcome.stats.steps
194            );
195            if let Some(failure) = outcome.failure {
196                panic!("spawned_sim: `{name}` failed replaying tape {path}: {failure}");
197            }
198            return;
199        }
200
201        let spec = std::env::var("SPAWNED_SIM_STRATEGY")
202            .ok()
203            .or(self.explore.clone())
204            .unwrap_or_else(|| "random".into());
205        let strategy = Strategy::parse(&spec)
206            .unwrap_or_else(|e| panic!("spawned_sim: `{name}`: bad strategy: {e}"));
207        let iterations = env_u64("SPAWNED_SIM_ITERATIONS")
208            .map(|n| n as usize)
209            .or(self.iterations);
210        let (first, runs) = self.runs(&strategy, env_u64("SPAWNED_SIM_SEED"), iterations);
211        let report = explore(&strategy, first, runs, &body);
212        if report.divergences > 0 {
213            panic!(
214                "spawned_sim: `{name}`: {} of {} {strategy} runs did not replay their \
215                 recorded prefix: the body is not deterministic under the simulator",
216                report.divergences, report.runs
217            );
218        }
219        let Some(found) = report.found else {
220            if strategy != Strategy::Random {
221                let space = describe_space(&strategy, report.exhausted, report.truncated);
222                eprintln!(
223                    "spawned_sim: `{name}` passed {} runs of {strategy} ({} distinct schedules{space})",
224                    report.runs, report.schedules,
225                );
226            }
227            return;
228        };
229        let (seed, outcome) = (found.seed, found.outcome);
230        let failure = outcome.failure.clone().unwrap_or_default();
231        let dir = std::env::var_os("SPAWNED_SIM_TAPE_DIR")
232            .map(std::path::PathBuf::from)
233            .unwrap_or_else(|| std::env::temp_dir().join("spawned-sim"));
234        let stem: String = name
235            .chars()
236            .map(|c| if c.is_alphanumeric() { c } else { '_' })
237            .collect();
238        let stem = match &found.strategy {
239            Strategy::Random => format!("{stem}-seed{seed}"),
240            Strategy::Pct { .. } => format!("{stem}-pct-seed{seed}"),
241            Strategy::Dfs { .. } => format!("{stem}-dfs-run{}", found.run),
242        };
243        let full = dir.join(format!("{stem}.tape"));
244        let mut report = format!(
245            "spawned_sim: `{name}` failed under {} at run {} (seed {seed}) after {} polls at virtual time {:?}: {failure}\n",
246            found.strategy, found.run, outcome.stats.steps, outcome.stats.now,
247        );
248        match &found.strategy {
249            Strategy::Random => report.push_str(&format!(
250                "  replay seed: {}\n",
251                replay(&format!("SPAWNED_SIM_SEED={seed}"))
252            )),
253            Strategy::Pct { .. } => report.push_str(&format!(
254                "  replay seed: {}\n",
255                replay(&format!(
256                    "SPAWNED_SIM_STRATEGY={} SPAWNED_SIM_SEED={seed}",
257                    found.strategy
258                ))
259            )),
260            Strategy::Dfs { .. } => {}
261        }
262        match save(&outcome.tape, &found.strategy, &full) {
263            Ok(()) => report.push_str(&format!(
264                "  tape:        {} ({} polls, {} non-canonical)\n  replay tape: {}\n",
265                full.display(),
266                outcome.tape.polls(),
267                outcome.tape.deviations(),
268                replay(&format!("SPAWNED_SIM_TAPE={}", full.display())),
269            )),
270            Err(e) => report.push_str(&format!(
271                "  (could not write tape {}: {e})\n",
272                full.display()
273            )),
274        }
275        let budget = env_u64("SPAWNED_SIM_SHRINK").unwrap_or(200) as usize;
276        if budget > 0 {
277            let (small, runs) = shrink(&outcome.tape, &failure, &body, budget);
278            let min = dir.join(format!("{stem}.min.tape"));
279            if shrunk(&small, &outcome.tape) && save(&small, &found.strategy, &min).is_ok() {
280                report.push_str(&format!(
281                    "  shrunk tape: {} ({} polls, {} non-canonical after {runs} runs)\n  replay:      {}\n",
282                    min.display(),
283                    small.polls(),
284                    small.deviations(),
285                    replay(&format!("SPAWNED_SIM_TAPE={}", min.display())),
286                ));
287            }
288        }
289        eprintln!("{report}");
290        panic!(
291            "spawned_sim: `{name}` failed under {} with seed {seed}: {failure}",
292            found.strategy
293        );
294    }
295}
296
297/// Write `tape` with the strategy that produced it as a header comment
298/// (informational: a strict replay needs only the tape).
299#[cfg(spawned_sim)]
300fn save(
301    tape: &super::sim::Tape,
302    strategy: &super::sim::explore::Strategy,
303    path: &std::path::Path,
304) -> std::io::Result<()> {
305    if let Some(dir) = path.parent() {
306        std::fs::create_dir_all(dir)?;
307    }
308    std::fs::write(path, format!("# strategy {strategy}\n{}", tape.to_text()))
309}
310
311/// How much of a strategy's space a passing exploration covered, naming the
312/// cutoffs that were active when some run had alternatives past them.
313#[cfg(spawned_sim)]
314fn describe_space(
315    strategy: &super::sim::explore::Strategy,
316    exhausted: bool,
317    truncated: bool,
318) -> String {
319    use super::sim::explore::Strategy;
320    let mut cutoffs = Vec::new();
321    if let Strategy::Dfs {
322        depth: Some(depth), ..
323    } = strategy
324    {
325        cutoffs.push(format!("depth {depth}"));
326    }
327    cutoffs.push(format!("fair after {} polls", strategy.fair_after()));
328    let cut = format!(
329        "alternatives past the cutoffs ({}) not explored",
330        cutoffs.join(", ")
331    );
332    match (exhausted, truncated) {
333        (true, false) => ", bounded space exhausted".into(),
334        (true, true) => format!(", bounded space exhausted up to the cutoffs; {cut}"),
335        (false, true) => format!(", budget spent; {cut}"),
336        (false, false) => String::new(),
337    }
338}
339
340/// A shrunk tape is worth writing if it has fewer non-canonical picks or is
341/// shorter (prefix bisection can shorten a tape without removing a pick).
342#[cfg(spawned_sim)]
343fn shrunk(small: &super::sim::Tape, original: &super::sim::Tape) -> bool {
344    small.deviations() < original.deviations() || small.decisions.len() < original.decisions.len()
345}
346
347#[cfg(all(test, spawned_sim))]
348mod tests {
349    use super::super::sim::explore::Strategy;
350    use super::super::sim::{Decision, Tape};
351    use super::{shrunk, SimTest};
352
353    /// agy (round 2): the summary names the active cutoff (a DFS depth, not
354    /// only the fairness cutoff) and reports truncation even when the budget
355    /// ran out before exhaustion.
356    #[test]
357    fn exploration_summary_names_the_active_cutoffs() {
358        use super::describe_space;
359        let dfs = Strategy::parse("dfs:bound=2,depth=10,fair=500").unwrap();
360        let text = describe_space(&dfs, true, true);
361        assert!(
362            text.contains("depth 10") && text.contains("fair after 500"),
363            "{text}"
364        );
365        let text = describe_space(&dfs, false, true);
366        assert!(
367            text.contains("budget spent") && text.contains("not explored"),
368            "{text}"
369        );
370        assert_eq!(
371            describe_space(&dfs, true, false),
372            ", bounded space exhausted"
373        );
374    }
375
376    /// Codex P2 (#218): DFS keeps the requested `SPAWNED_SIM_SEED` as the
377    /// body's input for every schedule instead of always using 0.
378    #[test]
379    fn dfs_keeps_the_requested_seed() {
380        let dfs = Strategy::parse("dfs:bound=1").unwrap();
381        let test = SimTest::new();
382        assert_eq!(test.runs(&dfs, Some(42), Some(7)), (42, 7));
383        assert_eq!(test.runs(&dfs, None, None), (0, 100));
384        let pct = Strategy::parse("pct").unwrap();
385        assert_eq!(test.runs(&pct, Some(42), None), (42, 1));
386    }
387
388    /// agy L1: a shorter tape with as many non-canonical picks is still a
389    /// smaller reproduction.
390    #[test]
391    fn shorter_tape_with_equal_deviations_counts_as_shrunk() {
392        let tape = |n: usize| Tape {
393            seed: 1,
394            spin: None,
395            decisions: std::iter::once(Decision::Poll(3))
396                .chain(std::iter::repeat_n(Decision::Canonical(None), n))
397                .collect(),
398        };
399        assert!(shrunk(&tape(2), &tape(9)));
400        assert!(!shrunk(&tape(9), &tape(9)));
401    }
402}
spawned_rt/tasks/sim_test.rs

spawned_rt/tasks/
sim_test.rs
