#![forbid(unsafe_code)]
mod candidate;
pub mod checkpoint;
pub mod distributed;
pub mod ending;
#[cfg(test)]
mod exact_identity_tests;
pub mod graph;
mod parallel;
mod reclaim;
pub mod sample;
pub mod storage;
pub mod trace;
use std::sync::Arc;
use std::time::{Duration, Instant};
use dive_core::handle::{K_STATE, fin, state_term};
use dive_core::memo::{Memo, SiteStats};
use dive_core::plan::{Check, Code};
use dive_core::store::{StoreMemory, StoreStats};
use dive_core::{Error, ErrorKind, Handle, Machine, Opts, Plan, Sink, Store};
use dive_store::predecessor::PredecessorLog;
use dive_store::trace::StateId;
pub use ending::{Failure, Replayed, Site};
pub use trace::TraceState;
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Verdict {
Success,
InvariantViolated {
property: String,
initial: bool,
},
Deadlock,
NoNextAction,
PropertyViolatedInitially {
property: String,
},
ActionPropertyViolated {
property: String,
},
Failed,
Unsupported {
feature: String,
},
Budget,
Admission {
limit: Limit,
max: u64,
observed: u64,
},
GraphStop,
PrefixStop {
level: u64,
},
CheckpointPaused {
next_level: u64,
},
CheckpointError {
message: String,
},
Internal {
message: String,
},
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Limit {
States,
Depth,
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct Stats {
pub generated: u64,
pub distinct: u64,
pub depth: u64,
pub left_on_queue: u64,
pub initial_generated: u64,
}
#[derive(Clone, Debug, Default)]
pub struct Metrics {
pub distributed: Option<distributed::Usage>,
pub storage: storage::Usage,
pub discarded_before_intern: u64,
pub probed: u64,
pub conjuncts_total: u64,
pub conjuncts_skipped: u64,
pub store: StoreStats,
pub store_memory: StoreMemory,
pub memo: Vec<(String, SiteStats)>,
pub arena_peak: (usize, usize),
pub thunks: (u64, u64),
pub explore_time: Duration,
pub expand_time: Duration,
pub commit_time: Duration,
}
#[derive(Clone, Debug)]
pub struct Outcome {
pub verdict: Verdict,
pub stats: Stats,
pub metrics: Metrics,
pub warnings: Vec<(u16, u32)>,
pub trace: Option<Result<Vec<TraceState>, String>>,
pub failure: Option<Failure>,
pub in_init: bool,
pub expanded: bool,
pub replayed: Option<Replayed>,
pub sampled: Vec<sample::SampledState>,
pub printed: Vec<String>,
}
#[derive(Clone, Copy, Debug)]
pub struct Config {
pub opts: Opts,
pub max_states: Option<u64>,
pub max_depth: Option<u64>,
pub workers: usize,
pub warn: bool,
pub sample: Option<sample::Sample>,
}
#[derive(Debug)]
pub struct Seen {
table: Vec<u64>,
len: usize,
exact: Option<storage::Exact>,
#[cfg(test)]
collide_keys: Option<u64>,
}
impl Default for Seen {
fn default() -> Self {
Self {
table: vec![0; 1 << 16],
len: 0,
exact: None,
#[cfg(test)]
collide_keys: None,
}
}
}
impl Seen {
fn with_detached_exact(exact: bool, detached: bool) -> Self {
Self {
exact: exact.then(|| {
if detached {
storage::Exact::detached()
} else {
storage::Exact::default()
}
}),
..Self::default()
}
}
fn empty_like(&self) -> Self {
Self {
#[cfg(test)]
collide_keys: self.collide_keys,
..Self::with_detached_exact(
self.exact.is_some(),
self.exact.as_ref().is_some_and(storage::Exact::is_detached),
)
}
}
#[cfg(test)]
fn key(&self, key: u64) -> u64 {
self.collide_keys.unwrap_or(key)
}
#[cfg(not(test))]
#[inline]
#[allow(clippy::unused_self, reason = "the test build reads a key override")]
const fn key(&self, key: u64) -> u64 {
key
}
fn contains_row(
&self,
key: u64,
row: &[Handle],
heap: &dive_core::Heap,
poll: &(dyn Fn() -> bool + Sync),
) -> Result<bool, Error> {
self.exact.as_ref().map_or_else(
|| Ok(self.contains(key)),
|exact| exact.contains_controlled(key, row, heap, poll),
)
}
fn insert_row(
&mut self,
key: u64,
row: &[Handle],
heap: &dive_core::Heap,
id: u64,
poll: &(dyn Fn() -> bool + Sync),
) -> Result<storage::Inserted, Error> {
if let Some(exact) = &mut self.exact {
exact.insert_controlled(key, row, heap, id, poll)
} else if self.insert(key) {
Ok(storage::Inserted::New)
} else {
Ok(storage::Inserted::Seen(None))
}
}
fn fix(k: u64) -> u64 {
if k == 0 { 1 } else { k }
}
fn mask(&self) -> usize {
self.table.len() - 1
}
#[allow(clippy::cast_possible_truncation, reason = "masked to the table size")]
fn start(&self, k: u64) -> usize {
(k as usize) & self.mask()
}
#[must_use]
pub fn contains(&self, k: u64) -> bool {
let k = Self::fix(k);
let mut i = self.start(k);
loop {
match self.table[i] {
0 => return false,
x if x == k => return true,
_ => i = (i + 1) & self.mask(),
}
}
}
pub fn insert(&mut self, k: u64) -> bool {
if (self.len + 1) * 4 > self.table.len() * 3 {
self.grow();
}
let k = Self::fix(k);
let mut i = self.start(k);
loop {
match self.table[i] {
0 => {
self.table[i] = k;
self.len += 1;
return true;
}
x if x == k => return false,
_ => i = (i + 1) & self.mask(),
}
}
}
fn grow(&mut self) {
let size = self.table.len() * 2;
let old = std::mem::replace(&mut self.table, vec![0; size]);
for k in old.into_iter().filter(|&k| k != 0) {
let mut i = self.start(k);
while self.table[i] != 0 {
i = (i + 1) & self.mask();
}
self.table[i] = k;
}
}
#[must_use]
pub fn len(&self) -> usize {
self.len
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.len == 0
}
}
fn state_identity(
m: &mut Machine,
plan: &Plan,
identity: Option<&mut Vec<Handle>>,
) -> Result<u64, Error> {
if let Some(view) = &plan.view {
return view_key(m, plan, view, identity);
}
let image;
let state: &[Handle] = match &plan.symmetry {
Some(sym) => {
let mut out = Vec::with_capacity(m.s1.len());
let s1 = m.s1.clone();
sym.canonical_from(&mut m.heap, &s1, &m.s0, &mut out)?;
image = out;
&image
}
None => &m.s1,
};
let mut sum = 0u64;
for (i, &h) in state.iter().enumerate() {
sum = sum.wrapping_add(state_term(i, m.heap.hash(h)));
}
if let Some(identity) = identity {
capture_reserve(identity, state.len())?;
if m.heap.is_speculative() {
identity.extend(m.heap.close_identity_row_local(state)?);
} else {
for &handle in state {
identity.push(m.heap.intern(handle)?);
}
}
}
Ok(fin(K_STATE, state.len() as u64, sum))
}
fn view_key(
m: &mut Machine,
plan: &Plan,
view: &Check,
identity: Option<&mut Vec<Handle>>,
) -> Result<u64, Error> {
let Some(conj) = view.conjuncts.first() else {
return Err(Error::internal("a VIEW without its expression"));
};
if !fingerprintable(m, true)? {
return Err(Error::unsupported(
"a VIEW over a state holding an infinite or lazily represented set (core)",
));
}
let image = match &plan.symmetry {
Some(sym) => {
let mut out = Vec::with_capacity(m.s1.len());
let s1 = m.s1.clone();
sym.canonical_from(&mut m.heap, &s1, &m.s0, &mut out)?;
Some(out)
}
None => None,
};
let saved = if let Some(image) = image {
Some(std::mem::replace(&mut m.s0, image))
} else {
std::mem::swap(&mut m.s0, &mut m.s1);
None
};
let old = m.enter(view.frame);
let r = m.eval_norm(&plan.code, conj.p);
m.leave(old);
if let Some(s0) = saved {
m.s0 = s0;
} else {
std::mem::swap(&mut m.s0, &mut m.s1);
}
let v = m.heap.state_identity(r?)?;
if !closed_fingerprintable(&m.heap, v) {
return Err(Error::unsupported(
"a VIEW value holding an infinite or lazily represented set (core)",
));
}
if let Some(identity) = identity {
capture_reserve(identity, 1)?;
identity.push(v);
}
Ok(fin(K_STATE, 1, state_term(0, m.heap.hash(v))))
}
pub(crate) fn capture_reserve<T>(values: &mut Vec<T>, additional: usize) -> Result<(), Error> {
values
.len()
.checked_add(additional)
.and_then(|n| n.checked_mul(std::mem::size_of::<T>()))
.ok_or_else(|| Error::unsupported("capture buffer address space"))?;
values
.try_reserve(additional)
.map_err(|_| Error::unsupported("capture buffer allocation"))
}
pub(crate) fn capture_copy(values: &[Handle]) -> Result<Vec<Handle>, Error> {
let mut copy = Vec::new();
capture_reserve(&mut copy, values.len())?;
copy.extend_from_slice(values);
Ok(copy)
}
struct Explorer<'p> {
plan: &'p Plan,
graph: Option<&'p mut dyn graph::GraphSink>,
stats: Stats,
metrics: Metrics,
seen: Seen,
disk: Option<storage::Disk>,
checkpoint: Option<&'p mut checkpoint::Session>,
distributed: Option<&'p distributed::Coordinator>,
next: Vec<Handle>,
frontier: Option<storage::Frontiers>,
candidates: Option<candidate::Account>,
candidate_storage: storage::Storage,
next_originals: Vec<Handle>,
emitted: u64,
initial: bool,
changed: u64,
level: u64,
expanded: bool,
opts: Opts,
stop: Option<Verdict>,
action: Option<usize>,
init_action: Option<usize>,
log: PredecessorLog,
next_ids: Vec<StateId>,
cur_id: Option<StateId>,
predicted: Option<StateId>,
end: Option<End>,
in_model: bool,
action_start: u64,
failure: Option<Failure>,
poll: &'p (dyn Fn() -> bool + Sync),
max_states: Option<u64>,
max_depth: Option<u64>,
warnings: Vec<(u16, u32)>,
}
#[derive(Clone, Copy, Debug)]
enum Recorded {
New,
Seen(Option<StateId>),
}
struct End {
upto: Option<StateId>,
last: Option<(Option<usize>, Vec<Handle>)>,
expect: Vec<Handle>,
}
enum Probe {
Seen(Option<StateId>),
New,
}
impl Explorer<'_> {
fn seen_contains(
&mut self,
key: u64,
row: &[Handle],
heap: &dive_core::Heap,
phase: (&'static str, Option<u64>),
) -> Result<bool, Error> {
let exact = self.seen.exact.is_some();
let position = (
phase.0,
self.stats.generated,
self.cur_id,
phase.1.unwrap_or_else(|| self.emitted.saturating_sub(1)),
);
self.disk.as_mut().map_or_else(
|| self.seen.contains_row(key, row, heap, self.poll),
|disk| disk.operation(exact, key, row, heap, false, position, self.poll),
)
}
fn seen_insert(
&mut self,
key: u64,
row: &[Handle],
heap: &dive_core::Heap,
phase: (&'static str, Option<u64>),
) -> Result<storage::Inserted, Error> {
let exact = self.seen.exact.is_some();
let position = (
phase.0,
self.stats.generated,
self.cur_id,
phase.1.unwrap_or_else(|| self.emitted.saturating_sub(1)),
);
if let Some(disk) = &mut self.disk {
return disk
.operation(exact, key, row, heap, true, position, self.poll)
.map(|new| {
if new {
storage::Inserted::New
} else {
storage::Inserted::Seen(None)
}
});
}
if !exact {
return self.seen.insert_row(key, row, heap, 0, self.poll);
}
if self.predicted.is_some() {
return Err(Error::internal(
"an exact discovery id was recorded for a state that was never logged",
));
}
let predicted = self.log.len();
let inserted = self.seen.insert_row(key, row, heap, predicted, self.poll)?;
if inserted.is_new() {
self.predicted = Some(predicted);
}
Ok(inserted)
}
fn confirm_logged(&mut self, id: StateId) -> Result<(), Error> {
match self.predicted.take() {
Some(predicted) if predicted != id => Err(Error::internal(format!(
"the exact seen set recorded discovery id {predicted} for a state logged as {id}"
))),
None if self.seen.exact.is_some() && self.disk.is_none() => Err(Error::internal(
"a state was logged without its exact discovery id",
)),
_ => Ok(()),
}
}
fn queued_states(&self) -> usize {
if self.plan.vars.is_empty() {
return 0;
}
self.frontier.as_ref().map_or_else(
|| self.next.len() / self.plan.vars.len(),
storage::Frontiers::next_len,
)
}
fn advance_frontier(&mut self) -> Result<(), Error> {
let queued = self.queued_states();
if let Some(frontier) = &mut self.frontier {
match frontier.advance(self.poll) {
Ok(true) => {}
Ok(false) => {
self.stats.left_on_queue = queued as u64;
self.stop = Some(Verdict::Budget);
return Err(Error::stop());
}
Err(error) => {
self.stats.left_on_queue = queued as u64;
return Err(error);
}
}
}
Ok(())
}
fn check(&mut self, m: &mut Machine, code: &Code, c: &Check) -> Result<bool, Error> {
let skip = self.opts.parent_skip && !self.initial;
eval_check(m, code, c, skip.then_some(self.changed), &mut self.metrics)
}
fn in_model_of(&mut self, m: &mut Machine) -> Result<bool, (Site, Error)> {
let skip = self.opts.parent_skip && !self.initial;
in_model(
m,
self.plan,
!self.initial,
skip.then_some(self.changed),
&mut self.metrics,
)
}
fn probe(&mut self, m: &mut Machine) -> Result<(Probe, bool, u64), Error> {
let in_model = match self.in_model_of(m) {
Ok(b) => b,
Err((site, e)) => {
let e = self.fail_check(m, site, e);
if self.failure.is_some() {
self.end_here(m)?;
}
return Err(e);
}
};
self.in_model = in_model;
if !self.opts.early_probe {
for i in 0..m.s1.len() {
m.s1[i] = m.heap.intern(m.s1[i])?;
}
}
if !in_model && (self.plan.symmetry.is_some() || self.plan.view.is_some()) {
return Ok((Probe::New, false, 0));
}
let mut identity = Vec::new();
let key = match state_identity(
m,
self.plan,
self.seen.exact.as_ref().map(|_| &mut identity),
) {
Ok(k) => self.seen.key(k),
Err(e) if e.kind() == ErrorKind::Eval && self.plan.view.is_some() => {
self.failure = Some(self.failure_at(m, Site::View, e.message().to_owned())?);
self.end_here(m)?;
return Err(Error::stop());
}
Err(e) => return Err(e),
};
self.metrics.probed += 1;
if in_model
&& (self.max_states.is_some() || self.max_depth.is_some())
&& !self.seen_contains(key, &identity, &m.heap, ("AdmissionMembership", None))?
{
self.admit_new()?;
}
let inserted = if in_model {
self.seen_insert(key, &identity, &m.heap, ("Insertion", None))?
} else if self.seen_contains(key, &identity, &m.heap, ("AdmissionMembership", None))? {
storage::Inserted::Seen(None)
} else {
storage::Inserted::New
};
if let storage::Inserted::Seen(id) = inserted {
self.metrics.discarded_before_intern +=
u64::from(self.opts.early_probe && (!in_model || self.graph.is_none()));
return Ok((Probe::Seen(id), in_model, key));
}
Ok((Probe::New, in_model, key))
}
fn accept(&mut self, m: &mut Machine) -> Result<(), Error> {
let plan = self.plan;
let code = &plan.code;
let original = (self.graph.is_some() || self.checkpoint.is_some())
.then(|| capture_copy(&m.s1))
.transpose()?;
if m.assigned != m.s1.len() {
let message = incomplete_message(plan, m);
self.failure = Some(self.failure_at(m, Site::Incomplete, message)?);
self.end_here(m)?;
return Err(Error::stop());
}
if !self.initial {
self.changed = changed_vars(m);
}
let (probe, in_model, key) = self.probe(m)?;
if let Probe::Seen(seen) = probe {
if !self.initial {
self.implied_actions(m)?;
}
return if in_model {
self.record(m, key, Recorded::Seen(seen), original.as_deref())
} else {
Ok(())
};
}
if in_model && self.plan.view.is_none() && !fingerprintable(m, self.initial)? {
self.failure = Some(self.failure_at(m, Site::Fingerprint, FP_MESSAGE.into())?);
self.end_here(m)?;
return Err(Error::stop());
}
if in_model {
self.stats.distinct += 1;
self.stats.depth = self.stats.depth.max(self.level);
}
let enqueue_first = self.initial && in_model;
if enqueue_first {
self.enqueue(m, original.as_deref())?;
}
for (i, c) in plan.invariants.iter().enumerate() {
let holds = match self.check(m, code, c) {
Ok(b) => b,
Err(e) => {
let e = self.fail_check(m, Site::Invariant(i), e);
if self.failure.is_some() {
self.end_here(m)?;
}
return Err(e);
}
};
if !holds {
self.stop = Some(Verdict::InvariantViolated {
property: c.name.clone(),
initial: self.initial,
});
self.end_here(m)?;
return Err(Error::stop());
}
}
if self.initial {
for (i, c) in plan.implied_inits.iter().enumerate() {
let holds = match self.check(m, code, c) {
Ok(b) => b,
Err(e) => {
let e = self.fail_check(m, Site::ImpliedInit(i), e);
if self.failure.is_some() {
self.end_here(m)?;
}
return Err(e);
}
};
if !holds {
self.stop = Some(Verdict::PropertyViolatedInitially {
property: c.name.clone(),
});
self.end_here(m)?;
return Err(Error::stop());
}
}
} else {
self.implied_actions(m)?;
}
if in_model && !enqueue_first {
self.enqueue(m, original.as_deref())?;
}
if in_model {
self.record(m, key, Recorded::New, original.as_deref())?;
}
Ok(())
}
fn record(
&mut self,
m: &mut Machine,
key: u64,
recorded: Recorded,
original: Option<&[Handle]>,
) -> Result<(), Error> {
let (new, seen) = match recorded {
Recorded::New => (true, None),
Recorded::Seen(seen) => (false, seen),
};
if new && let Some(session) = &mut self.checkpoint {
let values = m.s1.clone();
let original = original.unwrap_or(&values);
let ordinal = u32::try_from(self.emitted.saturating_sub(1))
.map_err(|_| Error::unsupported("checkpoint successor ordinal bound"))?;
if let Err(error) =
session.record(&mut m.heap, &values, original, key, self.cur_id, ordinal)
{
self.stop = Some(Verdict::CheckpointError {
message: error.message().to_owned(),
});
return Err(Error::stop());
}
}
let Some(sink) = self.graph.as_deref_mut() else {
return Ok(());
};
let nvars = m.s1.len();
let kept = if new {
Vec::new()
} else {
let values = original.unwrap_or(&m.s1);
let mut kept = Vec::new();
capture_reserve(&mut kept, values.len())?;
for &handle in values {
kept.push(m.heap.intern_exact(handle)?);
}
kept
};
let original = if new {
self.next_originals
.get(self.next_originals.len().saturating_sub(nvars)..)
.ok_or_else(|| Error::internal("a new state's original values were not retained"))?
} else {
&kept
};
let new = if new {
let id = self
.next_ids
.last()
.copied()
.ok_or_else(|| Error::internal("a new state was not enqueued"))?;
let values = self
.next
.get(self.next.len().saturating_sub(nvars)..)
.ok_or_else(|| Error::internal("a new state's values were not enqueued"))?;
Some((id, values))
} else {
None
};
let step = graph::Step {
key,
new,
seen,
original,
parent: self.cur_id,
ordinal: self.emitted.saturating_sub(1),
action: self.action,
};
if sink.state(&mut m.heap, step).is_err() {
self.stop = Some(Verdict::GraphStop);
return Err(Error::stop());
}
Ok(())
}
fn report_emitted(&mut self) -> Result<(), Error> {
if self.checkpoint.is_some() && self.stats.generated > i64::MAX as u64 {
self.stop = Some(Verdict::CheckpointError {
message: "native recovery counter bound exceeded".into(),
});
return Err(Error::stop());
}
let ordinal = (!self.initial).then(|| self.emitted.saturating_sub(1));
let generated = self.stats.generated;
if let Some(sink) = self.graph.as_deref_mut()
&& sink.emitted(generated, ordinal).is_err()
{
self.stop = Some(Verdict::GraphStop);
return Err(Error::stop());
}
Ok(())
}
fn implied_actions(&mut self, m: &mut Machine) -> Result<(), Error> {
m.level -= 1;
let r = self.implied_actions_at(m);
m.level += 1;
r
}
fn implied_actions_at(&mut self, m: &mut Machine) -> Result<(), Error> {
let plan = self.plan;
for (i, c) in plan.implied_actions.iter().enumerate() {
let holds = match check_step(m, &plan.code, c) {
Ok(b) => b,
Err(e) => {
let e = self.fail_check(m, Site::ImpliedAction(i), e);
if self.failure.is_some() {
self.end_here(m)?;
}
return Err(e);
}
};
if !holds {
self.stop = Some(Verdict::ActionPropertyViolated {
property: c.name.clone(),
});
self.end_here(m)?;
return Err(Error::stop());
}
}
Ok(())
}
fn admit_new(&mut self) -> Result<(), Error> {
let states = self.stats.distinct + 1;
let stop = if let Some(max) = self.max_states
&& states > max
{
Some((Limit::States, max, states))
} else if let Some(max) = self.max_depth
&& self.level > max
{
Some((Limit::Depth, max, self.level))
} else {
None
};
if let Some((limit, max, observed)) = stop {
self.stop = Some(Verdict::Admission {
limit,
max,
observed,
});
return Err(Error::stop());
}
Ok(())
}
fn enqueue(&mut self, m: &mut Machine, original: Option<&[Handle]>) -> Result<(), Error> {
if self.frontier.is_some() {
let mut identity = Vec::new();
let mut retained = Vec::new();
capture_reserve(&mut identity, m.s1.len())?;
capture_reserve(&mut retained, m.s1.len())?;
for &value in &m.s1 {
identity.push(m.heap.intern(value)?);
}
for &value in original.unwrap_or(&m.s1) {
retained.push(m.heap.intern_exact(value)?);
}
let ordinal = u32::try_from(self.emitted.saturating_sub(1))
.map_err(|_| Error::unsupported("more than 2^32 successors of one state"))?;
let id = match self.cur_id {
None => self.log.push_initial(ordinal),
Some(parent) => self.log.push(parent, ordinal),
}
.map_err(|e| Error::internal(format!("predecessor log: {e}")))?;
self.confirm_logged(id)?;
return self
.frontier
.as_mut()
.ok_or_else(|| Error::internal("the spilled frontier disappeared"))?
.push(id, &identity, &retained);
}
if self.graph.is_some() || self.checkpoint.is_some() {
capture_reserve(&mut self.next, m.s1.len())?;
capture_reserve(&mut self.next_originals, m.s1.len())?;
capture_reserve(&mut self.next_ids, 1)?;
}
for i in 0..m.s1.len() {
let h = m.heap.intern(m.s1[i])?;
self.next.push(h);
}
if self.graph.is_some() || self.checkpoint.is_some() {
for &h in original.unwrap_or(&m.s1) {
self.next_originals.push(m.heap.intern_exact(h)?);
}
}
let ordinal = u32::try_from(self.emitted.saturating_sub(1))
.map_err(|_| Error::unsupported("more than 2^32 successors of one state"))?;
let id = match self.cur_id {
None => self.log.push_initial(ordinal),
Some(parent) => self.log.push(parent, ordinal),
}
.map_err(|e| Error::internal(format!("predecessor log: {e}")))?;
self.confirm_logged(id)?;
self.next_ids.push(id);
Ok(())
}
fn end_here(&mut self, m: &mut Machine) -> Result<(), Error> {
let mut values = Vec::with_capacity(m.s1.len());
for &h in &m.s1 {
values.push(if h.is_empty() { h } else { m.heap.intern(h)? });
}
let expect = if self.cur_id.is_some() {
if self.graph.is_some() || self.checkpoint.is_some() || self.distributed.is_some() {
m.s0.iter()
.map(|&h| m.heap.intern(h))
.collect::<Result<Vec<_>, _>>()?
} else {
m.s0.clone()
}
} else {
Vec::new()
};
self.end = Some(End {
upto: self.cur_id,
last: Some((self.action, values)),
expect,
});
Ok(())
}
}
pub(crate) fn eval_check(
m: &mut Machine,
code: &Code,
c: &Check,
skip: Option<u64>,
metrics: &mut Metrics,
) -> Result<bool, Error> {
std::mem::swap(&mut m.s0, &mut m.s1);
let old = m.enter(c.frame);
let mut r = Ok(true);
for conj in &c.conjuncts {
metrics.conjuncts_total += 1;
if let Some(changed) = skip
&& conj.skippable
&& conj.reads & changed == 0
{
metrics.conjuncts_skipped += 1;
continue;
}
match m.eval_bool(code, conj.p) {
Ok(true) => {}
Ok(false) => {
r = Ok(false);
break;
}
Err(e) => {
r = Err(e);
break;
}
}
}
m.leave(old);
std::mem::swap(&mut m.s0, &mut m.s1);
r
}
pub(crate) fn in_model(
m: &mut Machine,
plan: &Plan,
step: bool,
skip: Option<u64>,
metrics: &mut Metrics,
) -> Result<bool, (Site, Error)> {
let code = &plan.code;
for (i, c) in plan.constraints.iter().enumerate() {
if !eval_check(m, code, c, skip, metrics).map_err(|e| (Site::Constraint(i), e))? {
return Ok(false);
}
}
if step {
m.level -= 1;
let r = (|| {
for (i, c) in plan.action_constraints.iter().enumerate() {
if !check_step(m, code, c).map_err(|e| (Site::ActionConstraint(i), e))? {
return Ok(false);
}
}
Ok(true)
})();
m.level += 1;
return r;
}
Ok(true)
}
pub(crate) fn incomplete_message(plan: &Plan, m: &Machine) -> String {
let missing: Vec<&str> =
m.s1.iter()
.zip(&plan.vars)
.filter(|(h, _)| h.is_empty())
.map(|(_, n)| n.as_str())
.collect();
format!("not completely specified: {}", missing.join(", "))
}
pub(crate) fn changed_vars(m: &Machine) -> u64 {
let mut changed = 0;
for (i, (a, b)) in m.s0.iter().zip(&m.s1).enumerate() {
if a != b {
changed |= 1u64 << i;
}
}
changed
}
const FP_MESSAGE: &str = "a state holds a set that cannot be fingerprinted";
pub(crate) fn fingerprintable(m: &mut Machine, initial: bool) -> Result<bool, Error> {
fingerprintable_with_identity(m, initial, None)
}
pub(crate) fn fingerprintable_with_identity(
m: &mut Machine,
initial: bool,
identity: Option<&[Handle]>,
) -> Result<bool, Error> {
for i in 0..m.s1.len() {
let h = m.s1[i];
if h.is_empty() || !h.is_compound() || (!initial && m.s0.get(i) == Some(&h)) {
continue;
}
let p = if let Some(identity) = identity {
*identity
.get(i)
.ok_or_else(|| Error::internal("candidate identity row width"))?
} else {
m.heap.state_identity(h)?
};
m.s1[i] = p;
if !closed_fingerprintable(&m.heap, p) {
return Ok(false);
}
}
Ok(true)
}
fn closed_fingerprintable(heap: &dive_core::Heap, h: Handle) -> bool {
use dive_core::node::Kind;
if !h.is_compound() {
return true;
}
let v = heap.view(h);
match v.kind {
Kind::Set | Kind::IntFcn | Kind::Fcn => {
v.data.iter().all(|&d| closed_fingerprintable(heap, d))
}
Kind::BigInt | Kind::Interval => true,
_ => false,
}
}
fn check_step(m: &mut Machine, code: &Code, c: &Check) -> Result<bool, Error> {
let old = m.enter(c.frame);
let mut r = Ok(true);
for conj in &c.conjuncts {
match m.eval_bool(code, conj.p) {
Ok(true) => {}
other => {
r = other;
break;
}
}
}
m.leave(old);
r
}
impl Sink for Explorer<'_> {
fn emit(&mut self, m: &mut Machine, _code: &Code) -> Result<(), Error> {
if self.initial && (self.poll)() {
self.stop = Some(Verdict::Budget);
return Err(Error::stop());
}
if self.graph.is_some() {
self.stats.generated = self
.stats
.generated
.checked_add(1)
.ok_or_else(|| Error::unsupported("capture generated counter overflow"))?;
self.emitted = self
.emitted
.checked_add(1)
.ok_or_else(|| Error::unsupported("capture successor ordinal overflow"))?;
if self.initial {
self.stats.initial_generated = self
.stats
.initial_generated
.checked_add(1)
.ok_or_else(|| Error::unsupported("capture initial counter overflow"))?;
}
} else {
self.stats.generated += 1;
self.emitted += 1;
if self.initial {
self.stats.initial_generated += 1;
}
}
self.report_emitted()?;
if !self.initial && self.graph.is_some() && (self.poll)() {
self.stop = Some(Verdict::Budget);
return Err(Error::stop());
}
let before = m.heap.mark();
let forced = m.thunk_mark();
let draws = m.draws;
let level = m.level;
m.level = i64::try_from(self.level).unwrap_or(i64::MAX);
let r = self.accept(m);
m.level = level;
if m.draws != draws {
return Err(Error::unsupported(
"RandomElement in an invariant, constraint or implied action (M1 core)",
));
}
if r.is_ok() && m.thunks_released(forced) {
m.heap.rollback(before);
}
if m.heap.poisoned() {
return Err(Error::internal("a stale value handle was read"));
}
r
}
}
fn run_actions(
m: &mut Machine,
ex: &mut Explorer<'_>,
actions: &[dive_core::plan::Action],
code: &Code,
) -> Result<(), Error> {
for (i, a) in actions.iter().enumerate() {
ex.action = (!ex.initial).then_some(i);
ex.init_action = ex.initial.then_some(i);
ex.action_start = ex.emitted;
let old = m.enter(a.frame);
for &(slot, v) in &a.preset {
if let Some(x) = m.frame.get_mut(m.base + slot as usize) {
*x = v;
}
}
let r = m.run_action(code, a.g, ex);
m.leave(old);
r?;
}
Ok(())
}
fn workers(plan: &Plan, config: &Config) -> usize {
if plan.effects.any {
1
} else {
config.workers.max(1)
}
}
#[must_use]
pub fn explore(
plan: &Plan,
store: &Arc<Store>,
config: Config,
poll: &(dyn Fn() -> bool + Sync),
) -> Outcome {
explore_with(plan, store, config, poll, None)
}
#[must_use]
#[allow(
clippy::too_many_lines,
reason = "ordered search setup and result assembly stay in one entrypoint"
)]
pub fn explore_with<'p>(
plan: &'p Plan,
store: &Arc<Store>,
config: Config,
poll: &'p (dyn Fn() -> bool + Sync),
graph: Option<&'p mut dyn graph::GraphSink>,
) -> Outcome {
explore_with_control(plan, store, config, poll, graph, None)
}
#[must_use]
#[allow(
clippy::too_many_lines,
reason = "ordered search setup/result assembly"
)]
pub fn explore_with_control<'p>(
plan: &'p Plan,
store: &Arc<Store>,
config: Config,
poll: &'p (dyn Fn() -> bool + Sync),
graph: Option<&'p mut dyn graph::GraphSink>,
control: Option<&Arc<dyn dive_core::eval::WorkControl>>,
) -> Outcome {
explore_with_storage(
plan,
store,
config,
poll,
graph,
control,
&storage::Storage::default(),
)
}
#[must_use]
#[allow(
clippy::too_many_arguments,
clippy::too_many_lines,
reason = "search setup and storage policy"
)]
pub fn explore_with_storage<'p>(
plan: &'p Plan,
store: &Arc<Store>,
config: Config,
poll: &'p (dyn Fn() -> bool + Sync),
graph: Option<&'p mut dyn graph::GraphSink>,
control: Option<&Arc<dyn dive_core::eval::WorkControl>>,
storage: &storage::Storage,
) -> Outcome {
let mut owner = Arc::clone(store);
explore_inner(
plan, &mut owner, config, poll, graph, control, storage, None, None, false, None,
)
}
#[must_use]
#[allow(
clippy::too_many_arguments,
reason = "existing owned search, control and recovery owners"
)]
pub fn explore_owned<'p>(
plan: &'p Plan,
store: &mut Arc<Store>,
config: Config,
poll: &'p (dyn Fn() -> bool + Sync),
control: Option<&Arc<dyn dive_core::eval::WorkControl>>,
storage: &storage::Storage,
session: Option<&'p mut checkpoint::Session>,
permanent: Option<&dive_core::store::compact::Permanent>,
) -> Outcome {
explore_inner(
plan, store, config, poll, None, control, storage, session, permanent, true, None,
)
}
#[must_use]
#[allow(
clippy::too_many_arguments,
reason = "existing search owners and explicit authenticated coordinator"
)]
pub fn explore_distributed<'p>(
plan: &'p Plan,
store: &Arc<Store>,
config: Config,
poll: &'p (dyn Fn() -> bool + Sync),
control: Option<&Arc<dyn dive_core::eval::WorkControl>>,
storage: &storage::Storage,
coordinator: &'p distributed::Coordinator,
) -> Outcome {
let mut owner = Arc::clone(store);
explore_inner(
plan,
&mut owner,
config,
poll,
None,
control,
storage,
None,
None,
false,
Some(coordinator),
)
}
#[allow(
clippy::too_many_arguments,
clippy::too_many_lines,
reason = "one existing search owner with an optional completed-level transaction"
)]
fn explore_inner<'p>(
plan: &'p Plan,
store: &mut Arc<Store>,
config: Config,
poll: &'p (dyn Fn() -> bool + Sync),
graph: Option<&'p mut dyn graph::GraphSink>,
control: Option<&Arc<dyn dive_core::eval::WorkControl>>,
storage: &storage::Storage,
checkpoint: Option<&'p mut checkpoint::Session>,
permanent: Option<&dive_core::store::compact::Permanent>,
owned: bool,
distributed: Option<&'p distributed::Coordinator>,
) -> Outcome {
let start = Instant::now();
let trigger_bytes = storage.store_compact_bytes;
let mut compact = trigger_bytes.is_some();
let mut reclaim_refusal = if compact && distributed.is_some() {
Some("Store reclamation with distributed workers is not implemented")
} else if compact && !owned {
Some("Store reclamation requires the owned exploration entrypoint")
} else if compact && (graph.is_some() || plan.effects.any || config.sample.is_some()) {
Some("Store reclamation with temporal capture, runtime effects or sampling")
} else if compact && checkpoint.as_ref().is_some_and(|s| s.pause_after.is_some()) {
Some("Store reclamation with checkpoint pause (discovery residency is unsupported)")
} else {
None
};
let mut default_skip = None;
if storage.store_compact_default
&& let Some(feature) = reclaim_refusal.take()
{
compact = false;
default_skip = Some(feature.to_owned());
}
let captured_permanent = if compact && permanent.is_none() && reclaim_refusal.is_none() {
Some(dive_core::store::compact::Permanent::capture(
store,
&|| !poll(),
))
} else {
None
};
let (captured_permanent, mut permanent_error) = match captured_permanent.transpose() {
Ok(permanent) => (permanent, None),
Err(error) => (None, Some(error)),
};
if storage.store_compact_default
&& let Some(error) = permanent_error.take_if(|error| reclaim::skippable(error))
{
compact = false;
default_skip = Some(error.message().to_owned());
}
let storage_owned;
let storage = if storage.store_compact_default && !compact {
storage_owned = storage::Storage {
store_compact_bytes: None,
..storage.clone()
};
&storage_owned
} else {
storage
};
let permanent = permanent.or(captured_permanent.as_ref());
let config = if storage.seen_disk.is_some() {
Config {
workers: 1,
..config
}
} else {
config
};
let unsupported_storage = graph.is_some()
&& (storage.seen_disk.is_some()
|| storage.predecessor_memory_bytes.is_some()
|| storage.predecessor_directory.is_some()
|| storage.frontier_memory_bytes.is_some()
|| storage.frontier_directory.is_some()
|| storage.candidate_memory_bytes.is_some()
|| storage.candidate_directory.is_some());
let nvars = plan.vars.len();
let (frontier, storage_setup_error) = match storage
.frontier_memory_bytes
.map(|_| storage::Frontiers::new(store, nvars, storage))
.transpose()
{
Ok(frontier) => (frontier, None),
Err(error) => (None, Some(error)),
};
let mut initial_metrics = Metrics::default();
initial_metrics.storage.reclamation.trigger_bytes = trigger_bytes;
initial_metrics.storage.reclamation.default_trigger = storage.store_compact_default;
initial_metrics.storage.reclamation.skipped = default_skip;
let (disk, disk_setup_error) = match storage
.seen_disk
.as_ref()
.map(|options| storage::Disk::new(storage.exact, options))
.transpose()
{
Ok(disk) => (disk, None),
Err(error) => {
initial_metrics.storage.seen = Some(storage::DiskUsage {
limits: storage
.seen_disk
.as_ref()
.map_or_else(dive_store::seen::Limits::default, |options| options.limits),
admitted_keys: 0,
before_cleanup: None,
after_cleanup: None,
first_failure: Some(storage::DiskFailure {
phase: "Creation",
error: error.clone(),
generated: 0,
predecessor: None,
successor_ordinal: 0,
}),
deciding_event_before_failure: None,
audit_completed: false,
});
(None, Some(Error::internal(error.to_string())))
}
};
let mut seen = Seen::with_detached_exact(storage.exact, compact);
#[cfg(test)]
{
seen.collide_keys = storage.collide_keys;
}
if storage.seen_disk.is_some() {
seen.table = Vec::new();
}
let keys: Vec<usize> = plan
.code
.sites
.iter()
.map(dive_core::plan::MemoSite::key_len)
.collect();
let local_workers = if distributed.is_some() {
1
} else {
workers(plan, &config)
};
let mut machines: Vec<Machine> = (0..local_workers)
.map(|_| {
let mut m = Machine::new(Arc::clone(store), nvars, config.opts, Memo::new(&keys));
m.warn = config.warn;
m.set_work_control(control.cloned());
m.set_debugger(plan.code.debugger.clone());
m
})
.collect();
let mut ex = Explorer {
plan,
graph,
stats: Stats::default(),
metrics: initial_metrics,
seen,
disk,
checkpoint,
distributed,
next: Vec::new(),
frontier,
candidates: storage.candidate_memory_bytes.map(|bytes| {
Arc::new(std::sync::Mutex::new(storage::CandidateUsage {
memory_bytes_per_worker: Some(bytes),
..storage::CandidateUsage::default()
}))
}),
candidate_storage: storage.clone(),
next_originals: Vec::new(),
emitted: 0,
initial: true,
changed: u64::MAX,
level: 1,
expanded: false,
opts: config.opts,
stop: None,
action: None,
init_action: None,
log: PredecessorLog::new(
storage.predecessor_memory_bytes,
storage.predecessor_directory.as_deref(),
),
next_ids: Vec::new(),
cur_id: None,
predicted: None,
end: None,
in_model: true,
action_start: 0,
failure: None,
poll,
max_states: config.max_states,
max_depth: config.max_depth,
warnings: Vec::new(),
};
let mut replayed = None;
let mut reservoir = config.sample.map(sample::Reservoir::new);
let result = if let Some(feature) = reclaim_refusal {
Err(Error::unsupported(feature))
} else if let Some(error) = permanent_error.or(disk_setup_error).or(storage_setup_error) {
Err(error)
} else if distributed.is_some()
&& (ex.graph.is_some()
|| config.sample.is_some()
|| plan.effects.any
|| plan.view.is_some()
|| plan.symmetry.is_some()
|| storage.seen_disk.is_some()
|| storage.candidate_memory_bytes.is_some())
{
Err(Error::unsupported(
"distributed effects, VIEW, symmetry, sampling, disk seen or candidate spill",
))
} else if unsupported_storage {
Err(Error::unsupported(
"spilled native temporal storage (disk seen set, predecessor, frontier or candidate spill)",
))
} else if storage.candidate_directory.is_some() && storage.candidate_memory_bytes.is_none() {
Err(Error::unsupported(
"a candidate directory without a candidate memory budget",
))
} else if storage.candidate_memory_bytes.is_some() && plan.effects.any {
Err(Error::unsupported("candidate spill with runtime effects"))
} else if storage.predecessor_directory.is_some() && storage.predecessor_memory_bytes.is_none()
{
Err(Error::unsupported(
"a predecessor directory without a predecessor memory budget",
))
} else if storage.frontier_directory.is_some() && storage.frontier_memory_bytes.is_none() {
Err(Error::unsupported(
"a frontier directory without a frontier memory budget",
))
} else {
run(
&mut machines,
&mut ex,
plan,
&mut replayed,
reservoir.as_mut(),
store,
permanent,
control,
)
};
let parallel = machines.len() > 1 || ex.candidates.is_some() || ex.distributed.is_some();
if let (Some(coordinator), Err(error)) = (distributed, &result) {
coordinator.record_failure(error);
}
let mut m = machines.swap_remove(0);
if let Err(error) = &result
&& error.message().starts_with("DIVE-S0203:")
{
ex.metrics
.storage
.reclamation
.failures
.push(error.message().to_owned());
}
let mut trace = ex
.end
.take()
.map(|end| reconstruct(plan, store, &config, &ex.log, end));
let mut verdict = match result {
Ok(()) => Verdict::Success,
Err(e) => match e.into_parts() {
(ErrorKind::Stop, _) if ex.failure.is_some() => Verdict::Failed,
(ErrorKind::Stop, _) => match ex.stop.take() {
Some(stop) => stop,
None if (poll)() || m.heap.work_interrupted() => Verdict::Budget,
None => Verdict::Success,
},
(ErrorKind::Unsupported, message) => Verdict::Unsupported { feature: message },
(ErrorKind::Eval, message) => Verdict::Unsupported {
feature: format!("evaluation error classification (M0 core): {message}"),
},
(ErrorKind::Internal, message) => Verdict::Internal { message },
},
};
if let Some(account) = &ex.candidates {
ex.metrics.storage.candidates = account
.lock()
.unwrap_or_else(std::sync::PoisonError::into_inner)
.clone();
if !ex.metrics.storage.candidates.failures.is_empty() {
ex.metrics.storage.candidates.deciding_event_before_failure =
Some(format!("{verdict:?}"));
verdict = Verdict::Internal {
message: ex.metrics.storage.candidates.failures.join("; "),
};
trace = None;
}
}
ex.metrics.storage.exact_states = ex.seen.exact.as_ref().map_or(0, storage::Exact::len);
if let Some(disk) = &mut ex.disk {
let validate = !matches!(
verdict,
Verdict::Budget
| Verdict::Admission { .. }
| Verdict::Unsupported { .. }
| Verdict::Internal { .. }
);
let complete = disk.finish(validate, poll, verdict.clone());
if storage.exact {
ex.metrics.storage.exact_states =
usize::try_from(disk.usage.admitted_keys).unwrap_or(usize::MAX);
}
ex.metrics.storage.seen = Some(disk.usage.clone());
if let Some(failure) = &disk.usage.first_failure {
verdict = Verdict::Internal {
message: failure.error.to_string(),
};
trace = None;
} else if !complete {
verdict = Verdict::Budget;
trace = None;
}
}
ex.metrics.storage.predecessor = ex.log.usage();
if let Some(error) = ex.log.failure() {
ex.metrics
.storage
.predecessor_failures
.push(error.to_string());
}
match ex.log.close() {
Ok(()) => ex.metrics.storage.predecessor_cleanup_completed = true,
Err(error) => ex
.metrics
.storage
.predecessor_failures
.push(error.to_string()),
}
if !ex.metrics.storage.predecessor_failures.is_empty() {
ex.metrics.storage.predecessor_deciding_event = Some(format!("{verdict:?}"));
verdict = Verdict::Internal {
message: ex.metrics.storage.predecessor_failures.join("; "),
};
trace = None;
}
if let Some(frontier) = &mut ex.frontier {
let validate = !matches!(
verdict,
Verdict::Budget
| Verdict::Admission { .. }
| Verdict::Unsupported { .. }
| Verdict::Internal { .. }
);
let completed = frontier.finish(validate, poll);
ex.metrics.storage.frontier = frontier.usage.clone();
if !ex.metrics.storage.frontier.failures.is_empty() {
ex.metrics.storage.frontier.deciding_event_before_failure =
Some(format!("{verdict:?}"));
verdict = Verdict::Internal {
message: ex.metrics.storage.frontier.failures.join("; "),
};
trace = None;
} else if !completed {
verdict = Verdict::Budget;
trace = None;
}
}
let mut metrics = ex.metrics;
metrics.distributed = distributed.map(distributed::Coordinator::usage);
metrics.store = store.stats();
metrics.store_memory = store.memory_usage();
metrics.memo = plan
.code
.sites
.iter()
.map(|s| s.name.clone())
.zip(m.memo.stats())
.collect();
let (nodes, handles) = m.heap.arena().peak();
metrics.arena_peak.0 = metrics.arena_peak.0.max(nodes);
metrics.arena_peak.1 = metrics.arena_peak.1.max(handles);
for worker in &machines {
let (nodes, handles) = worker.heap.arena().peak();
metrics.arena_peak.0 = metrics.arena_peak.0.max(nodes);
metrics.arena_peak.1 = metrics.arena_peak.1.max(handles);
}
metrics.thunks = (m.stats.forced, m.stats.cached);
metrics.explore_time = start.elapsed();
let warnings = if !config.warn {
Vec::new()
} else if parallel {
std::mem::take(&mut ex.warnings)
} else {
std::mem::take(&mut m.warnings)
};
Outcome {
verdict,
stats: ex.stats,
metrics,
warnings,
trace,
failure: ex.failure,
in_init: ex.initial,
expanded: ex.expanded,
replayed,
sampled: reservoir.map(|r| r.states).unwrap_or_default(),
printed: std::mem::take(&mut m.printed),
}
}
fn reconstruct(
plan: &Plan,
store: &Arc<Store>,
config: &Config,
log: &PredecessorLog,
end: End,
) -> Result<Vec<TraceState>, String> {
let mut states = match end.upto {
None => Vec::new(),
Some(id) => {
let path = log.path(id).map_err(|e| format!("predecessor log: {e}"))?;
let states = trace::replay(plan, store, config.opts, config.warn, &path)
.map_err(|e| e.message().to_owned())?;
if !states
.last()
.is_some_and(|s| replay_values_match(store, &s.values, &end.expect))
{
return Err("trace replay produced a different state than the search".into());
}
states
}
};
if let Some((action, values)) = end.last {
states.push(TraceState { action, values });
}
Ok(states)
}
fn replay_values_match(store: &Arc<Store>, actual: &[Handle], expected: &[Handle]) -> bool {
if actual == expected {
return true;
}
if store.hashcons() || actual.len() != expected.len() {
return false;
}
let heap = dive_core::Heap::new(Arc::clone(store), false, false);
actual.iter().zip(expected).all(|(&a, &b)| heap.eq(a, b))
}
fn generator_error(m: &Machine, ex: &mut Explorer<'_>, identity: &[Handle], e: Error) -> Error {
if e.kind() != ErrorKind::Eval || ex.failure.is_some() {
return e;
}
ex.failure = Some(ex.generator_failure(m, e.message().to_owned()));
if let Some(id) = ex.cur_id {
ex.end = Some(End {
upto: Some(id),
last: None,
expect: identity.to_vec(),
});
}
Error::stop()
}
fn source_row(
machine: &mut Machine,
explorer: &mut Explorer<'_>,
identity: &[Handle],
left: u64,
terminal: bool,
) -> Result<(), Error> {
let Some(source) = explorer.cur_id else {
return Ok(());
};
let error = terminal.then_some(explorer.failure.as_ref()).flatten();
let Some(sink) = explorer.graph.as_deref_mut() else {
return Ok(());
};
let row = graph::SourceRow {
source,
original: &machine.s0,
emitted: explorer.emitted,
next_error: error,
stats: Stats {
left_on_queue: left,
..explorer.stats
},
};
if sink.source_row(&mut machine.heap, row).is_err() {
explorer.stats.left_on_queue = left;
explorer.stop = Some(Verdict::GraphStop);
explorer.end = Some(End {
upto: Some(source),
last: None,
expect: identity.to_vec(),
});
return Err(Error::stop());
}
Ok(())
}
pub(crate) fn start_stream(
m: &mut Machine,
plan: &Plan,
state: Option<&[Handle]>,
) -> Result<(), Error> {
if !plan.effects.draws {
return Ok(());
}
let Some(draws) = m.heap.store().draws().cloned() else {
return Err(Error::unsupported(
"RandomElement without the run's random streams (M1 core)",
));
};
m.draw = Some(match state {
None => draws.startup(),
Some(vars) => draws.state(&mut m.heap, vars)?,
});
Ok(())
}
fn level_done(ex: &mut Explorer<'_>, _nvars: usize) -> Result<(), Error> {
let left_on_queue = ex.queued_states() as u64;
let Some(sink) = ex.graph.as_deref_mut() else {
return Ok(());
};
let counts = Stats {
left_on_queue,
..ex.stats
};
let level = ex.level - 1;
let stop = sink.level_done(level, counts);
if stop == Ok(false) {
return Ok(());
}
ex.stats.left_on_queue = counts.left_on_queue;
ex.stop = Some(match stop {
Ok(_) if counts.left_on_queue > 0 => Verdict::PrefixStop { level },
Ok(_) => Verdict::Internal {
message: "a prefix stop with an exhausted frontier".into(),
},
Err(graph::Stopped) => Verdict::GraphStop,
});
Err(Error::stop())
}
const CHUNK_PER_WORKER: usize = 4096;
const FRONTIER_CHUNK_STATES: usize = 1024;
#[allow(
clippy::too_many_lines,
clippy::too_many_arguments,
reason = "TLC's ordered level loop: expansion, stops, replay and deadlock"
)]
fn run(
machines: &mut [Machine],
ex: &mut Explorer<'_>,
plan: &Plan,
replayed: &mut Option<Replayed>,
mut reservoir: Option<&mut sample::Reservoir>,
store: &mut Arc<Store>,
permanent: Option<&dive_core::store::compact::Permanent>,
control: Option<&Arc<dyn dive_core::eval::WorkControl>>,
) -> Result<(), Error> {
let code = &plan.code;
let nvars = plan.vars.len();
let parallel = machines.len() > 1 || ex.candidates.is_some() || ex.distributed.is_some();
let Some(m) = machines.first_mut() else {
return Err(Error::internal("no core machine"));
};
let recovered = checkpoint::restore(ex, m)?;
if !recovered {
start_stream(m, plan, None)?;
m.level = 0;
if let Err(e) = run_actions(m, ex, &plan.init, code) {
ex.stats.left_on_queue = ex.queued_states() as u64;
return Err(generator_error(m, ex, &[], e));
}
ex.stats.depth = ex
.stats
.depth
.max(u64::from(ex.stats.initial_generated > 0));
if plan.next.is_empty() && ex.queued_states() > 0 {
ex.stats.left_on_queue = ex.queued_states() as u64;
ex.stop = Some(Verdict::NoNextAction);
return Err(Error::stop());
}
m.heap.reset();
ex.initial = false;
ex.warnings.clone_from(&m.warnings);
}
checkpoint::boundary(ex)?;
reclaim::boundary(machines, ex, store, permanent, control)?;
let mut cur = std::mem::take(&mut ex.next);
let mut cur_originals = std::mem::take(&mut ex.next_originals);
let mut cur_ids = std::mem::take(&mut ex.next_ids);
ex.advance_frontier()?;
let mut generated_before = 0;
loop {
let states = cur.len().checked_div(nvars).map_or(0, |in_memory| {
ex.frontier
.as_ref()
.map_or(in_memory, storage::Frontiers::current_len)
});
if states == 0 {
break;
}
if (ex.graph.is_some() || ex.checkpoint.is_some())
&& ex.frontier.is_none()
&& cur_originals.len() != cur.len()
{
return Err(Error::internal(
"capture frontier original/identity row mismatch",
));
}
ex.level += 1;
ex.expanded = true;
let estimate = usize::try_from(ex.stats.generated - generated_before).unwrap_or(1 << 20);
generated_before = ex.stats.generated;
let level_started = Instant::now();
let mut expand_time = std::time::Duration::ZERO;
let chunk = ex.graph.as_deref().map_or_else(
|| (machines.len() * CHUNK_PER_WORKER).max(1),
|sink| sink.max_expansion_units().max(1),
);
let chunk = if ex.candidates.is_some() {
machines.len().max(1)
} else {
chunk
};
let chunk = ex
.distributed
.map_or(chunk, |coordinator| chunk.min(coordinator.width()));
let chunk = if ex.frontier.is_some() {
chunk.min(FRONTIER_CHUNK_STATES)
} else {
chunk
};
let mut expanded: Option<Vec<Option<parallel::Expanded>>> = None;
let mut received: Option<Vec<Option<distributed::Received>>> = None;
let mut decoded = storage::Chunk::default();
let mut base = 0;
for k in 0..states {
if k % chunk == 0 {
let queued = ex.queued_states();
if let Some(frontier) = &mut ex.frontier {
decoded = match frontier.chunk(k, (k + chunk).min(states), ex.poll) {
Ok(Some(decoded)) => decoded,
Ok(None) => {
ex.stats.left_on_queue = (states - k + queued) as u64;
ex.stop = Some(Verdict::Budget);
return Err(Error::stop());
}
Err(error) => {
ex.stats.left_on_queue = (states - k + queued) as u64;
return Err(error);
}
};
}
}
let local = k % chunk;
let state = if ex.frontier.is_some() {
&decoded.identity[local * nvars..(local + 1) * nvars]
} else {
&cur[k * nvars..(k + 1) * nvars]
};
if parallel && k % chunk == 0 {
let started = Instant::now();
let end = (k + chunk).min(states);
let mut metrics = Metrics::default();
let r = if let Some(coordinator) = ex.distributed {
coordinator
.expand(
plan,
machines[0].heap.store(),
if ex.frontier.is_some() {
&decoded.original
} else {
&cur[k * nvars..end * nvars]
},
&ex.seen,
ex.level - 1,
ex.poll,
)
.map(|work| {
received = Some(work);
Vec::new()
})
} else {
parallel::expand_level(
plan,
machines,
if ex.frontier.is_some() {
&decoded.original
} else if ex.graph.is_some() || ex.checkpoint.is_some() {
&cur_originals[k * nvars..end * nvars]
} else {
&cur[k * nvars..end * nvars]
},
nvars,
&ex.seen,
ex.opts,
ex.checkpoint.is_some(),
ex.graph
.as_deref()
.map(graph::GraphSink::max_successors_per_unit),
ex.candidates
.as_ref()
.map(|account| (&ex.candidate_storage, account)),
ex.poll,
estimate.saturating_mul(end - k) / states.max(1),
&mut metrics,
)
};
let r = match r {
Ok(r) => r,
Err(error) => {
ex.stats.left_on_queue = (states - k + ex.queued_states()) as u64;
return Err(error);
}
};
ex.metrics.conjuncts_total += metrics.conjuncts_total;
ex.metrics.conjuncts_skipped += metrics.conjuncts_skipped;
ex.metrics.discarded_before_intern += metrics.discarded_before_intern;
expand_time += started.elapsed();
expanded = if received.is_some() { None } else { Some(r) };
base = k;
}
let Some(m) = machines.first_mut() else {
return Err(Error::internal("no core machine"));
};
let have_expansion = expanded.is_some() || received.is_some();
let mut remote_expansion = if let Some(work) = received
.as_mut()
.and_then(|work| work.get_mut(k - base))
.and_then(Option::take)
{
let Some(coordinator) = ex.distributed else {
return Err(Error::internal("remote result without its coordinator"));
};
let started = Instant::now();
let mut metrics = Metrics::default();
let imported = coordinator.import(work, plan, &mut m.heap, ex.poll, &mut metrics);
let imported = match imported {
Ok(imported) => imported,
Err(error) => {
ex.stats.left_on_queue = (states - k + ex.queued_states()) as u64;
return Err(error);
}
};
ex.metrics.conjuncts_total += metrics.conjuncts_total;
ex.metrics.conjuncts_skipped += metrics.conjuncts_skipped;
ex.metrics.discarded_before_intern += metrics.discarded_before_intern;
expand_time += started.elapsed();
Some(imported)
} else {
None
};
let res = remote_expansion.as_mut().or_else(|| {
expanded
.as_mut()
.and_then(|all| all.get_mut(k - base).and_then(Option::as_mut))
});
let exhausted = if have_expansion {
res.is_none()
} else {
(ex.poll)()
};
if exhausted {
ex.stats.left_on_queue = (states - k + ex.queued_states()) as u64;
ex.stop = Some(Verdict::Budget);
return Err(Error::stop());
}
let source = if ex.frontier.is_some() {
&decoded.original[local * nvars..(local + 1) * nvars]
} else if ex.graph.is_some() || ex.checkpoint.is_some() {
cur_originals
.get(k * nvars..(k + 1) * nvars)
.ok_or_else(|| Error::internal("capture source original row missing"))?
} else {
state
};
m.s0.copy_from_slice(source);
let level = i64::try_from(ex.level - 1).unwrap_or(i64::MAX);
if res.is_none() {
start_stream(m, plan, Some(source))?;
m.level = level;
}
if let Some(r) = reservoir.as_deref_mut() {
r.offer(source, level);
}
ex.cur_id = if ex.frontier.is_some() {
decoded.ids.get(local).copied()
} else {
cur_ids.get(k).copied()
};
ex.emitted = 0;
let r = match res {
Some(res) => ex.commit(m, res),
None => run_actions(m, ex, &plan.next, code),
}
.map_err(|e| generator_error(m, ex, state, e));
if r.is_err()
&& ex
.failure
.as_ref()
.is_some_and(|failure| matches!(failure.site, Site::Next(_)))
{
let row_left = (states - k - 1 + ex.queued_states()) as u64;
source_row(m, ex, state, row_left, true)?;
}
if r.is_err()
&& let Some(f) = &ex.failure
&& f.site_resumes()
{
if plan.effects.draws {
return Err(Error::unsupported(
"TLC's replay after a failing check, in a specification that draws (RandomElement) (M1 core)",
));
}
if plan.effects.registers || plan.effects.level {
return Err(Error::unsupported(
"TLC's replay after a failing check, in a specification that uses TLCSet or TLCGet (M1 core)",
));
}
ex.graph = None;
let ordinal = ex.emitted - 1;
let saved = std::mem::take(&mut m.warnings);
*replayed = Some(ending::replay_after(m, ex, ordinal)?);
for w in std::mem::replace(&mut m.warnings, saved) {
if parallel && !ex.warnings.contains(&w) {
ex.warnings.push(w);
} else if !parallel && !m.warnings.contains(&w) {
m.warnings.push(w);
}
}
}
if let Some(all) = &mut expanded {
all[k - base] = None;
}
m.heap.reset();
let left = (states - k - 1 + ex.queued_states()) as u64;
if let Err(e) = r {
ex.stats.left_on_queue = left;
return Err(e);
}
if ex.emitted == 0 && plan.check_deadlock {
ex.stats.left_on_queue = left;
ex.stop = Some(Verdict::Deadlock);
ex.end = Some(End {
upto: ex.cur_id,
last: None,
expect: state.to_vec(),
});
return Err(Error::stop());
}
if let Some(id) = ex.cur_id
&& let Some(sink) = ex.graph.as_deref_mut()
&& sink.stutter(id).is_err()
{
ex.stats.left_on_queue = left;
ex.stop = Some(Verdict::GraphStop);
return Err(Error::stop());
}
source_row(m, ex, state, left, false)?;
}
level_done(ex, nvars)?;
if !parallel {
ex.warnings.clone_from(&machines[0].warnings);
}
checkpoint::boundary(ex)?;
if parallel {
ex.metrics.expand_time += expand_time;
ex.metrics.commit_time += level_started.elapsed().saturating_sub(expand_time);
}
cur.clear();
cur_originals.clear();
cur_ids.clear();
drop(expanded);
drop(decoded);
reclaim::boundary(machines, ex, store, permanent, control)?;
std::mem::swap(&mut cur, &mut ex.next);
std::mem::swap(&mut cur_originals, &mut ex.next_originals);
std::mem::swap(&mut cur_ids, &mut ex.next_ids);
ex.advance_frontier()?;
}
Ok(())
}
#[cfg(test)]
mod tests {
use super::*;
pub(super) fn frontier_plan(store: &Arc<Store>, false_invariant: bool) -> Result<Plan, Error> {
use dive_core::plan::{Action, CompileStats, Conjunct, Effects, GNode, Node};
let mut heap = dive_core::Heap::new(Arc::clone(store), true, false);
let domain = heap.interval(0, 127);
let domain = heap.intern_const(domain)?;
let action = |name: &str, g| Action {
name: name.into(),
g,
frame: 0,
preset: Vec::new(),
};
Ok(Plan {
code: Code {
nodes: vec![
Node::Const(domain),
Node::Var(0),
Node::Const(Handle::FALSE),
],
gnodes: vec![
GNode::AssignIn { var: 0, set: 0 },
GNode::Assign { var: 0, rhs: 1 },
],
..Code::default()
},
vars: vec!["x".into()],
init: vec![action("Init", 0)],
next: vec![action("Next", 1)],
invariants: if false_invariant {
vec![Check {
name: "Inv".into(),
frame: 0,
conjuncts: vec![Conjunct {
p: 2,
reads: 1,
skippable: false,
site: None,
}],
}]
} else {
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, Copy, Debug)]
enum FrontierFault {
Corrupt,
Missing,
Cleanup,
}
#[allow(
clippy::unwrap_used,
clippy::too_many_lines,
reason = "fault mutation and real explorer outcome remain in one deterministic control"
)]
fn frontier_fault(
tlc: bool,
exact: bool,
workers: usize,
initial_violation: bool,
fault: FrontierFault,
) {
use std::fs;
use std::io::{Seek, SeekFrom, Write};
use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
static NEXT: AtomicUsize = AtomicUsize::new(0);
let directory = std::env::temp_dir().join(format!(
"dive-frontier-explorer-{}-{}",
std::process::id(),
NEXT.fetch_add(1, Ordering::Relaxed)
));
fs::create_dir(&directory).unwrap();
let store = Arc::new(Store::with_semantics(
true,
if tlc {
dive_core::Semantics::tlc()
} else {
dive_core::Semantics::default()
},
));
let plan = frontier_plan(&store, initial_violation).unwrap();
let calls = AtomicUsize::new(0);
let injected = AtomicBool::new(false);
let trigger = if initial_violation { 1 } else { 129 };
let poll = || {
if calls.fetch_add(1, Ordering::Relaxed) == trigger {
let owned = fs::read_dir(&directory)
.unwrap()
.next()
.unwrap()
.unwrap()
.path();
match fault {
FrontierFault::Corrupt => {
let mut file = fs::OpenOptions::new()
.write(true)
.open(owned.join("states"))
.unwrap();
file.seek(SeekFrom::End(-1)).unwrap();
file.write_all(&[255]).unwrap();
}
FrontierFault::Missing => fs::remove_file(owned.join("states")).unwrap(),
FrontierFault::Cleanup => {
fs::rename(&owned, directory.join("moved")).unwrap();
fs::write(owned, b"blocks directory cleanup").unwrap();
}
}
injected.store(true, Ordering::Relaxed);
}
false
};
let out = explore_with_storage(
&plan,
&store,
Config {
opts: Opts::default(),
max_states: None,
max_depth: None,
workers,
warn: true,
sample: None,
},
&poll,
None,
None,
&storage::Storage {
exact,
frontier_memory_bytes: Some(0),
frontier_directory: Some(directory.clone()),
..storage::Storage::default()
},
);
assert!(injected.load(Ordering::Relaxed), "{fault:?}");
assert!(
matches!(out.verdict, Verdict::Internal { .. }),
"{fault:?}: {:?}",
out.verdict
);
assert!(
out.trace.is_none(),
"corrupt storage must clear a deciding word"
);
let failures = &out.metrics.storage.frontier.failures;
assert_ne!(failures.as_slice(), [] as [String; 0]);
let expected = match fault {
FrontierFault::Corrupt => "checksum",
FrontierFault::Missing => "open record",
FrontierFault::Cleanup => "cleanup",
};
assert!(
failures.iter().any(|message| message.contains(expected)),
"{failures:?}"
);
if initial_violation {
assert!(
out.metrics
.storage
.frontier
.deciding_event_before_failure
.as_ref()
.unwrap()
.contains("InvariantViolated")
);
}
fs::remove_dir_all(directory).unwrap();
}
#[test]
fn corrupt_read_and_cleanup_failures_prevent_success_and_counterexample_certification() {
for tlc in [false, true] {
for exact in [false, true] {
for workers in [1, 4, 8] {
for initial in [false, true] {
for fault in [
FrontierFault::Corrupt,
FrontierFault::Missing,
FrontierFault::Cleanup,
] {
frontier_fault(tlc, exact, workers, initial, fault);
}
}
}
}
}
}
#[test]
#[allow(
clippy::unwrap_used,
reason = "owned cancellation during final frontier validation"
)]
fn validation_cancellation_is_a_budget_stop_without_storage_failure_or_word() {
use std::sync::atomic::{AtomicUsize, Ordering};
for initial_violation in [false, true] {
for workers in [1, 4, 8] {
let store = Arc::new(Store::new(true));
let plan = frontier_plan(&store, initial_violation).unwrap();
let trigger = if initial_violation { 1 } else { 257 };
let calls = AtomicUsize::new(0);
let poll = || calls.fetch_add(1, Ordering::Relaxed) >= trigger;
let out = explore_with_storage(
&plan,
&store,
Config {
opts: Opts::default(),
max_states: None,
max_depth: None,
workers,
warn: true,
sample: None,
},
&poll,
None,
None,
&storage::Storage {
frontier_memory_bytes: Some(0),
..storage::Storage::default()
},
);
assert_eq!(out.verdict, Verdict::Budget);
assert!(out.trace.is_none());
assert_eq!(out.metrics.storage.frontier.failures, [] as [String; 0]);
assert_eq!(calls.load(Ordering::Relaxed), trigger + 1);
assert_eq!(out.metrics.storage.frontier.retained_bytes, 0);
}
}
}
#[test]
#[allow(
clippy::unwrap_used,
reason = "deterministic owned budget and spilled-frontier control"
)]
fn budget_stop_closes_an_unread_spilled_frontier_without_validation_polls() {
use std::sync::atomic::{AtomicUsize, Ordering};
for tlc in [false, true] {
for exact in [false, true] {
for workers in [1, 4, 8] {
let store = Arc::new(Store::with_semantics(
true,
if tlc {
dive_core::Semantics::tlc()
} else {
dive_core::Semantics::default()
},
));
let plan = frontier_plan(&store, false).unwrap();
let calls = AtomicUsize::new(0);
let poll = || calls.fetch_add(1, Ordering::Relaxed) >= 128;
let out = explore_with_storage(
&plan,
&store,
Config {
opts: Opts::default(),
max_states: None,
max_depth: None,
workers,
warn: true,
sample: None,
},
&poll,
None,
None,
&storage::Storage {
exact,
frontier_memory_bytes: Some(0),
..storage::Storage::default()
},
);
assert_eq!(out.verdict, Verdict::Budget);
assert_eq!(
out.stats,
Stats {
generated: 128,
distinct: 128,
depth: 1,
left_on_queue: 128,
initial_generated: 128
}
);
assert!(out.trace.is_none());
assert_eq!(
calls.load(Ordering::Relaxed),
129,
"cleanup must not scan/poll the unread queue"
);
assert!(out.metrics.storage.frontier.spilled_bytes > 0);
assert_eq!(out.metrics.storage.frontier.retained_bytes, 0);
assert_eq!(out.metrics.storage.frontier.failures, [] as [String; 0]);
}
}
}
}
#[test]
fn impossible_capture_growth_is_fallible_without_modifying_retained_payload() {
let mut values = vec![Handle::EMPTY];
let capacity = values.capacity();
assert!(capture_reserve(&mut values, usize::MAX).is_err());
assert_eq!(values, [Handle::EMPTY]);
assert_eq!(values.capacity(), capacity);
}
#[test]
#[allow(clippy::unwrap_used, reason = "deterministic explorer control")]
fn invariant_frame_thunks_do_not_hold_initial_transients() {
use dive_core::plan::{Action, CompileStats, Conjunct, Effects, GNode, Node};
const WIDTH: usize = 64;
const STATES: u64 = 128;
let store = Arc::new(Store::new(false));
let mut heap = dive_core::Heap::new(Arc::clone(&store), false, false);
let domain = heap.interval(0, 127);
let domain = heap.intern_const(domain).unwrap();
let action = |name: &str, g| Action {
name: name.into(),
g,
frame: 1,
preset: Vec::new(),
};
let plan = Plan {
code: Code {
nodes: vec![
Node::Const(domain),
Node::Var(0),
Node::Tuple(vec![1; WIDTH].into_boxed_slice()),
Node::Lazy { slot: 0, body: 2 },
Node::Eq(3, 3),
],
gnodes: vec![
GNode::AssignIn { var: 0, set: 0 },
GNode::Assign { var: 0, rhs: 1 },
],
..Code::default()
},
vars: vec!["x".into()],
init: vec![action("Init", 0)],
next: vec![action("Next", 1)],
invariants: vec![Check {
name: "Inv".into(),
frame: 1,
conjuncts: vec![Conjunct {
p: 4,
reads: 1,
skippable: false,
site: None,
}],
}],
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,
};
let out = explore(
&plan,
&store,
Config {
opts: Opts::default(),
max_states: None,
max_depth: None,
workers: 1,
warn: true,
sample: None,
},
&|| false,
);
assert_eq!(out.verdict, Verdict::Success);
assert_eq!(out.stats.distinct, STATES);
assert_eq!(out.metrics.thunks, (STATES, STATES));
let (_, handles) = out.metrics.arena_peak;
assert!(
handles < 4 * WIDTH,
"arena peak of {handles} handles holds the initial states' check transients"
);
}
#[test]
fn replay_checks_compound_values_without_hashconsing() -> Result<(), Error> {
let store = Arc::new(Store::new(false));
let mut heap = dive_core::Heap::new(Arc::clone(&store), false, false);
let one = heap.int_from_i64(1);
let two = heap.int_from_i64(2);
let a = heap.tuple(&[one]);
let a = heap.intern(a)?;
let equal = heap.tuple(&[one]);
let equal = heap.intern(equal)?;
let different = heap.tuple(&[two]);
let different = heap.intern(different)?;
assert_ne!(a, equal, "the control must allocate distinct handles");
assert!(replay_values_match(&store, &[a], &[equal]));
assert!(!replay_values_match(&store, &[a], &[different]));
assert!(!replay_values_match(&store, &[a], &[equal, equal]));
assert!(!replay_values_match(&store, &[], &[equal]));
let nested_a = heap.tuple(&[a]);
let nested_a = heap.intern(nested_a)?;
let nested_equal = heap.tuple(&[equal]);
let nested_equal = heap.intern(nested_equal)?;
let nested_different = heap.tuple(&[different]);
let nested_different = heap.intern(nested_different)?;
assert!(replay_values_match(&store, &[nested_a], &[nested_equal]));
assert!(!replay_values_match(
&store,
&[nested_a],
&[nested_different]
));
Ok(())
}
#[test]
fn seen_set_inserts_and_grows() {
let mut s = Seen::default();
for k in 0..200_000u64 {
assert!(s.insert(k.wrapping_mul(0x9e37_79b9_7f4a_7c15)));
}
assert_eq!(s.len(), 200_000);
assert!(!s.insert(0));
assert!(s.contains(5u64.wrapping_mul(0x9e37_79b9_7f4a_7c15)));
assert!(!s.contains(7));
}
}