use std::fmt;
use crate::ctx::ThreadCtx;
use crate::diag::Report;
use crate::launch::LaunchConfig;
use crate::sched::{Choices, SplitMix64};
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Schedule {
plan: Vec<u32>,
}
impl Schedule {
pub fn new(plan: Vec<u32>) -> Self {
Schedule { plan }
}
pub fn plan(&self) -> &[u32] {
&self.plan
}
pub fn len(&self) -> usize {
self.plan.len()
}
pub fn is_empty(&self) -> bool {
self.plan.is_empty()
}
pub fn switches(&self) -> usize {
self.plan.windows(2).filter(|w| w[0] != w[1]).count()
}
}
impl fmt::Display for Schedule {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(
f,
"{} decision(s), {} switch(es)",
self.len(),
self.switches()
)
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Shrink {
Minimised(Schedule),
Disabled,
TraceTruncated,
NotReproducible,
}
impl Shrink {
pub fn schedule(&self) -> Option<&Schedule> {
match self {
Shrink::Minimised(s) => Some(s),
_ => None,
}
}
}
impl fmt::Display for Shrink {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Shrink::Minimised(s) => write!(f, "shrunk to {s}"),
Shrink::Disabled => write!(f, "not shrunk, minimisation disabled"),
Shrink::TraceTruncated => write!(f, "not shrunk, the schedule was too long to record"),
Shrink::NotReproducible => {
write!(
f,
"not shrunk, the kernel did not behave the same way twice"
)
}
}
}
}
#[derive(Clone, Debug)]
pub struct Failure {
pub seed: u64,
pub report: Report,
pub shrink: Shrink,
pub decisions: usize,
}
impl Failure {
pub fn target(&self) -> Option<String> {
self.report.diagnostics.first().map(|d| d.fingerprint())
}
}
#[derive(Clone, Debug)]
pub struct Exploration {
pub seeds_tried: u64,
pub failure: Option<Failure>,
}
impl Exploration {
pub fn is_clean(&self) -> bool {
self.failure.is_none()
}
#[track_caller]
pub fn assert_clean(&self) {
if !self.is_clean() {
panic!("{self}");
}
}
}
impl fmt::Display for Exploration {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match &self.failure {
None => writeln!(f, "riri: explored {} seed(s), all clean", self.seeds_tried),
Some(fail) => {
writeln!(
f,
"riri: explored {} seed(s), seed {} failed in {} decision(s), {}",
self.seeds_tried, fail.seed, fail.decisions, fail.shrink
)?;
for d in &fail.report.diagnostics {
writeln!(f, " - {d}")?;
}
if let Some(s) = fail.shrink.schedule() {
writeln!(f, " schedule: {:?}", s.plan())?;
}
Ok(())
}
}
}
}
pub struct Explore {
base: LaunchConfig,
seeds: u64,
minimise: bool,
budget: usize,
}
impl Explore {
pub fn new(config: &LaunchConfig) -> Self {
Explore {
base: *config,
seeds: 64,
minimise: true,
budget: 256,
}
}
pub fn seeds(mut self, seeds: u64) -> Self {
self.seeds = seeds;
self
}
pub fn minimise(mut self, minimise: bool) -> Self {
self.minimise = minimise;
self
}
pub fn budget(mut self, replays: usize) -> Self {
self.budget = replays;
self
}
pub fn run<F>(&self, kernel: F) -> Exploration
where
F: Fn(&ThreadCtx<'_>) + Sync,
{
self.search(|config, choices| crate::launch::run(config, choices, &kernel))
}
pub fn run_with<S, K>(&self, setup: S) -> Exploration
where
S: Fn() -> K,
K: Fn(&ThreadCtx<'_>) + Sync,
{
self.search(|config, choices| crate::launch::run(config, choices, setup()))
}
fn search<R>(&self, run_once: R) -> Exploration
where
R: Fn(&LaunchConfig, Choices) -> (Report, Vec<u32>, bool),
{
for i in 0..self.seeds {
let seed = self.base.seed.wrapping_add(i);
let mut config = self.base;
config.seed = seed;
let (report, trace, complete) = run_once(&config, Choices::Random(SplitMix64(seed)));
if report.is_clean() {
continue;
}
let decisions = trace.len();
let shrink = self.shrink(&config, &report, trace, complete, &run_once);
return Exploration {
seeds_tried: i + 1,
failure: Some(Failure {
seed,
report,
shrink,
decisions,
}),
};
}
Exploration {
seeds_tried: self.seeds,
failure: None,
}
}
fn shrink<R>(
&self,
config: &LaunchConfig,
report: &Report,
trace: Vec<u32>,
complete: bool,
run_once: &R,
) -> Shrink
where
R: Fn(&LaunchConfig, Choices) -> (Report, Vec<u32>, bool),
{
if !self.minimise {
return Shrink::Disabled;
}
if !complete {
return Shrink::TraceTruncated;
}
let Some(target) = report.diagnostics.first().map(|d| d.fingerprint()) else {
return Shrink::Disabled;
};
let mut budget = self.budget;
let reproduces = |plan: &[u32], budget: &mut usize| {
if *budget == 0 {
return false;
}
*budget -= 1;
let choices = Choices::Replay {
plan: plan.to_vec(),
cursor: 0,
};
run_once(config, choices).0.contains(&target)
};
if !reproduces(&trace, &mut budget) {
return Shrink::NotReproducible;
}
let n = trace.len();
let mut hi = n;
if reproduces(&[], &mut budget) {
hi = 0;
} else {
let mut lo = 0;
let mut step = 1;
while step < n {
if reproduces(&trace[..step], &mut budget) {
hi = step;
break;
}
lo = step;
step *= 2;
}
while lo + 1 < hi {
let mid = lo + (hi - lo) / 2;
if reproduces(&trace[..mid], &mut budget) {
hi = mid;
} else {
lo = mid;
}
}
}
let mut plan = trace[..hi].to_vec();
for i in 1..plan.len() {
if budget == 0 {
break;
}
if plan[i] == plan[i - 1] {
continue;
}
let mut candidate = plan.clone();
candidate[i] = candidate[i - 1];
if reproduces(&candidate, &mut budget) {
plan = candidate;
}
}
Shrink::Minimised(Schedule::new(plan))
}
}
pub fn explore<F>(config: &LaunchConfig, seeds: u64, kernel: F) -> Exploration
where
F: Fn(&ThreadCtx<'_>) + Sync,
{
Explore::new(config).seeds(seeds).run(kernel)
}
pub fn replay<F>(config: &LaunchConfig, schedule: &Schedule, kernel: F) -> Report
where
F: Fn(&ThreadCtx<'_>) + Sync,
{
let choices = Choices::Replay {
plan: schedule.plan().to_vec(),
cursor: 0,
};
crate::launch::run(config, choices, kernel).0
}