#![allow(clippy::unwrap_used, reason = "deterministic graph controls")]
use std::collections::HashMap;
use std::sync::Arc;
use dive_core::plan::{Action, Arith, Code, CompileStats, Effects, GNode, Node};
use dive_core::{Error, Handle, Heap, Opts, Plan, Store};
use crate::graph::{GraphSink, SourceRow, Step, Stopped};
use crate::{Config, Stats, Verdict, explore_with_storage, storage};
const N: i64 = 37;
const STATES: usize = 37;
fn plan(store: &Arc<Store>) -> Result<Plan, Error> {
let mut heap = Heap::new(Arc::clone(store), true, false);
let initial = heap.interval(0, 1);
let initial = heap.intern_const(initial)?;
let int = |v| Handle::int(v).ok_or_else(|| Error::internal("small integer"));
let action = |name: &str, g| Action {
name: name.into(),
g,
frame: 0,
preset: Vec::new(),
};
Ok(Plan {
code: Code {
nodes: vec![
Node::Const(initial),
Node::Var(0),
Node::Const(int(1)?),
Node::Arith(Arith::Add, 1, 2),
Node::Const(int(N)?),
Node::Arith(Arith::Mod, 3, 4),
Node::Const(int(2)?),
Node::Arith(Arith::Mul, 1, 6),
Node::Arith(Arith::Mod, 7, 4),
],
gnodes: vec![
GNode::AssignIn { var: 0, set: 0 },
GNode::Assign { var: 0, rhs: 5 },
GNode::Assign { var: 0, rhs: 8 },
],
..Code::default()
},
vars: vec!["x".into()],
init: vec![action("Init", 0)],
next: vec![action("Inc", 1), action("Dbl", 2)],
invariants: Vec::new(),
constraints: Vec::new(),
action_constraints: Vec::new(),
implied_inits: Vec::new(),
implied_actions: Vec::new(),
check_deadlock: true,
symmetry: None,
effects: Effects::default(),
view: None,
stats: CompileStats::default(),
bound_preset: Vec::new(),
startup_assumptions: Vec::new(),
startup_assumption_false: None,
})
}
#[derive(Clone, Debug, PartialEq, Eq)]
enum Event {
Emitted(u64, Option<u64>),
State {
key: u64,
new: Option<(u64, Vec<i64>)>,
seen: Option<u64>,
original: Vec<i64>,
parent: Option<u64>,
ordinal: u64,
action: Option<usize>,
},
Stutter(u64),
Source(u64, u64),
Level(u64, Stats),
}
#[derive(Default)]
struct Recorder {
events: Vec<Event>,
}
fn ints(row: &[Handle]) -> Vec<i64> {
row.iter().map(|h| h.as_int().unwrap()).collect()
}
impl GraphSink for Recorder {
fn max_expansion_units(&self) -> usize {
64
}
fn max_successors_per_unit(&self) -> u64 {
1 << 20
}
fn emitted(&mut self, generated: u64, ordinal: Option<u64>) -> Result<(), Stopped> {
self.events.push(Event::Emitted(generated, ordinal));
Ok(())
}
fn state(&mut self, _heap: &mut Heap, step: Step<'_>) -> Result<(), Stopped> {
self.events.push(Event::State {
key: step.key,
new: step.new.map(|(id, row)| (id, ints(row))),
seen: step.seen,
original: ints(step.original),
parent: step.parent,
ordinal: step.ordinal,
action: step.action,
});
Ok(())
}
fn stutter(&mut self, source: u64) -> Result<(), Stopped> {
self.events.push(Event::Stutter(source));
Ok(())
}
fn source_row(&mut self, _heap: &mut Heap, row: SourceRow<'_>) -> Result<(), Stopped> {
self.events.push(Event::Source(row.source, row.emitted));
Ok(())
}
fn level_done(&mut self, level: u64, stats: Stats) -> Result<bool, Stopped> {
self.events.push(Event::Level(level, stats));
Ok(false)
}
}
fn run(exact: bool, collide: Option<u64>, workers: usize) -> (Verdict, Stats, usize, Vec<Event>) {
let store = Arc::new(Store::new(true));
let plan = plan(&store).unwrap();
let mut sink = Recorder::default();
let out = explore_with_storage(
&plan,
&store,
Config {
opts: Opts::default(),
max_states: None,
max_depth: None,
workers,
warn: true,
sample: None,
},
&|| false,
Some(&mut sink),
None,
&storage::Storage {
exact,
collide_keys: collide,
..storage::Storage::default()
},
);
(
out.verdict,
out.stats,
out.metrics.storage.exact_states,
sink.events,
)
}
fn resolved(events: &[Event]) -> Vec<Event> {
let mut by_key = HashMap::new();
let mut rows = HashMap::new();
events
.iter()
.map(|event| match event {
Event::State {
key,
new,
seen,
original,
parent,
ordinal,
action,
} => {
let target = if let Some((id, row)) = new {
assert_eq!(*seen, None, "a new state carries no seen id");
by_key.insert(*key, *id);
rows.insert(*id, row.clone());
*id
} else {
let id = seen.unwrap_or_else(|| by_key[key]);
assert_eq!(
rows[&id], *original,
"a seen target's id names a vertex with its own values"
);
id
};
Event::State {
key: 0,
new: new.clone(),
seen: Some(target),
original: original.clone(),
parent: *parent,
ordinal: *ordinal,
action: *action,
}
}
other => other.clone(),
})
.collect()
}
#[test]
fn exact_collisions_report_the_fingerprint_graph_with_discovery_ids() {
let (verdict, stats, _, reference) = run(false, None, 1);
assert_eq!(verdict, Verdict::Success);
assert_eq!(stats.distinct, STATES as u64);
assert!(stats.depth > 3, "several levels: {stats:?}");
let expected = resolved(&reference);
for workers in [1, 2, 4] {
let (fp_verdict, fp_stats, _, fp_events) = run(false, None, workers);
assert_eq!((fp_verdict, fp_stats), (Verdict::Success, stats));
assert_eq!(fp_events, reference, "fingerprint at {workers} workers");
for collide in [None, Some(0), Some(7)] {
let (verdict, exact_stats, retained, events) = run(true, collide, workers);
assert_eq!(verdict, Verdict::Success, "{workers} {collide:?}");
assert_eq!(exact_stats, stats, "{workers} {collide:?}");
assert_eq!(retained, STATES);
let mut seen_steps = 0;
for event in &events {
if let Event::State {
new: None, seen, ..
} = event
{
assert!(seen.is_some(), "exact seen steps carry their id");
seen_steps += 1;
}
if let (Event::State { key, .. }, Some(collide)) = (event, collide) {
assert_eq!(*key, collide);
}
}
assert!(seen_steps > STATES, "many seen targets");
assert_eq!(
resolved(&events),
expected,
"exact at {workers} workers with keys {collide:?}"
);
}
}
}
#[test]
fn fingerprint_collisions_merge_states_without_ids() {
let (_, stats, retained, events) = run(false, Some(0), 1);
assert_eq!(stats.distinct, 1);
assert_eq!(retained, 0);
assert!(events.iter().all(|event| match event {
Event::State { seen, .. } => seen.is_none(),
_ => true,
}));
}