use std::collections::BTreeMap;
use dive_eval::next::{StateVals, Successor};
use dive_model::{Model, UnsupportedKind};
use crate::admission as engine;
use crate::{CheckOptions, CheckResult, Collision, Stats, Verdict, Workers};
mod csr;
mod evidence;
pub use csr::{CsrCapture, CsrCaptureInput, CsrComplete, CsrPrefix};
pub use evidence::{CompleteEvidence, PrefixEvidence};
pub fn refuse_unproved_temporal_next_error(model: &Model, result: &mut CheckResult) -> bool {
if model.implied_temporals.is_empty() {
return false;
}
let Verdict::EvaluationError { site, cause, .. } = &result.verdict else {
return false;
};
if !matches!(
site,
crate::ErrorSite::Next
| crate::ErrorSite::ActionConstraint
| crate::ErrorSite::ImpliedAction
) {
return false;
}
if cause.is_eval_exception() {
return false;
}
let observed = format!("Observed {site:?} evaluation error: {}", cause.tool_text());
result.verdict = Verdict::Unsupported {
feature: "post-Next temporal-demand primary error classification without a reached-row replay certificate".into(),
};
result.tlc_prints_stats = false;
result.counterexample = None;
result.notes.push(observed);
true
}
pub const MAX_EXPANSION_UNITS: usize = 8;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Limits {
pub states: usize,
pub edges: usize,
pub generated: u64,
pub successors_per_unit: u64,
}
impl Default for Limits {
fn default() -> Self {
Self {
states: 1_000_000,
edges: 8_000_000,
generated: 32_000_000,
successors_per_unit: 65_536,
}
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Edge {
pub to: usize,
pub ordinal: Option<u64>,
pub label: Option<String>,
}
#[derive(Clone, Debug)]
pub struct ConcreteSuccessor {
pub state: StateVals,
pub ordinal: u64,
pub label: String,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct GraphCompletion {
states: usize,
edges: usize,
concrete_successors: usize,
roots: usize,
limits: Limits,
}
impl GraphCompletion {
fn finalize(graph: &BehaviorGraph, counters: Stats, limits: Limits) -> Result<Self, Verdict> {
let states = graph.states.len();
Self::check_header(states, &graph.roots, counters, limits, None)?;
if graph.edges.len() != states || graph.concrete.len() != states {
return Err(bug("incomplete graph/statistics at successful EOF"));
}
let mut edges = 0usize;
let mut concrete_successors = 0usize;
for (source, (row, concrete)) in graph.edges.iter().zip(&graph.concrete).enumerate() {
edges = edges
.checked_add(row.len())
.filter(|&n| n <= limits.edges)
.ok_or_else(|| limit("completion edges"))?;
concrete_successors = concrete_successors
.checked_add(concrete.len())
.ok_or_else(|| limit("completion concrete successors"))?;
if row.len()
!= concrete
.len()
.checked_add(1)
.ok_or_else(|| limit("completion row"))?
|| row
.last()
.is_none_or(|e| e.to != source || e.ordinal.is_some() || e.label.is_some())
{
return Err(bug("missing completed source/stutter row"));
}
for (edge, original) in row.iter().zip(concrete) {
if edge.to >= states
|| edge.ordinal != Some(original.ordinal)
|| edge.label.as_deref() != Some(original.label.as_str())
{
return Err(bug("inconsistent completed concrete transition"));
}
}
}
Ok(Self {
states,
edges,
concrete_successors,
roots: graph.roots.len(),
limits,
})
}
fn check_header(
states: usize,
roots: &[usize],
counters: Stats,
limits: Limits,
control: Option<&crate::budget::EvaluationControl>,
) -> Result<(), Verdict> {
if let Some(control) = control {
csr::poll(control)?;
}
if states > limits.states || counters.generated > limits.generated {
return Err(limit("completion entries"));
}
if counters.distinct != u64::try_from(states).map_err(|_| bug("state count range"))?
|| counters.left_on_queue != 0
|| (states != 0 && roots.is_empty())
{
return Err(bug("incomplete graph/statistics at successful EOF"));
}
let mut previous = None;
for (index, &root) in roots.iter().enumerate() {
if let Some(control) = control {
csr::checkpoint(control, index)?;
}
if root >= states || previous.is_some_and(|p| p >= root) {
return Err(bug("invalid completed initial roots"));
}
previous = Some(root);
}
Ok(())
}
#[must_use]
pub fn entries(&self) -> (usize, usize, usize, usize) {
(
self.states,
self.edges,
self.concrete_successors,
self.roots,
)
}
#[must_use]
pub fn limits(&self) -> Limits {
self.limits
}
}
pub trait Observer: Send {
fn stop_after_level(&self) -> bool {
false
}
fn init(&mut self, _id: usize, _state: &StateVals, _stats: Stats) -> Result<(), String> {
Ok(())
}
fn edge(
&mut self,
_from: usize,
_edge: &Edge,
_successor: &StateVals,
_stats: Stats,
) -> Result<(), String> {
Ok(())
}
fn level_done(
&mut self,
_level: u64,
_graph: &BehaviorGraph,
_stats: Stats,
) -> Result<(), String> {
Ok(())
}
}
#[derive(Clone, Debug)]
pub struct BehaviorGraph {
pub states: Vec<StateVals>,
pub edges: Vec<Vec<Edge>>,
pub concrete: Vec<Vec<ConcreteSuccessor>>,
pub roots: Vec<usize>,
}
#[derive(Clone, Debug)]
pub struct Complete {
evidence: CompleteEvidence,
pub options: CheckOptions,
pub graph: BehaviorGraph,
pub stats: Stats,
pub collision: Option<Collision>,
pub workers: Workers,
pub output: Vec<String>,
pub warnings: Vec<(u32, String)>,
}
impl Complete {
#[must_use]
pub fn completion(&self) -> &GraphCompletion {
self.evidence.completion()
}
#[must_use]
pub fn safety_result(&self) -> &CheckResult {
self.evidence.safety_result()
}
#[must_use]
pub fn evidence(&self) -> &CompleteEvidence {
&self.evidence
}
#[must_use]
pub fn into_evidence(self) -> CompleteEvidence {
self.evidence
}
fn from_producer(
graph: BehaviorGraph,
result: CheckResult,
options: CheckOptions,
stats: Stats,
completion: GraphCompletion,
) -> Self {
Self {
collision: result.collision.clone(),
workers: result.workers.clone(),
output: result.output.clone(),
warnings: result.warnings.clone(),
evidence: CompleteEvidence::new(result, options.clone(), stats, completion),
options,
graph,
stats,
}
}
}
#[derive(Clone, Debug)]
pub struct Prefix {
evidence: PrefixEvidence,
pub options: CheckOptions,
pub graph: BehaviorGraph,
pub stats: Stats,
pub collision: Option<Collision>,
pub workers: Workers,
pub output: Vec<String>,
pub warnings: Vec<(u32, String)>,
}
impl Prefix {
#[must_use]
pub const fn level(&self) -> u64 {
self.evidence.level()
}
#[must_use]
pub fn evidence(&self) -> &PrefixEvidence {
&self.evidence
}
#[must_use]
pub fn into_evidence(self) -> PrefixEvidence {
self.evidence
}
fn from_producer(
graph: BehaviorGraph,
result: CheckResult,
options: CheckOptions,
stats: Stats,
level: u64,
) -> Self {
Self {
collision: result.collision.clone(),
workers: result.workers.clone(),
output: result.output.clone(),
warnings: result.warnings.clone(),
evidence: PrefixEvidence::new(result, options.clone(), stats, level),
options,
graph,
stats,
}
}
}
#[derive(Clone, Debug)]
pub enum ControlledExploration {
Complete(Box<Complete>),
Prefix(Box<Prefix>),
Stopped(Box<CheckResult>),
}
impl From<Exploration> for ControlledExploration {
fn from(value: Exploration) -> Self {
match value {
Exploration::Complete(c) => Self::Complete(c),
Exploration::Stopped(s) => Self::Stopped(s),
}
}
}
#[doc(hidden)]
pub fn elapsed(result: &mut Exploration, duration: std::time::Duration) {
match result {
Exploration::Stopped(stop) => stop.elapsed = duration,
Exploration::Complete(complete) => complete.evidence.set_elapsed(duration),
}
}
#[derive(Clone, Debug)]
pub enum Exploration {
Complete(Box<Complete>),
Stopped(Box<CheckResult>),
}
#[derive(Debug)]
#[doc(hidden)]
pub struct Collector<K> {
ids: BTreeMap<K, usize>,
graph: BehaviorGraph,
limits: Limits,
count: usize,
}
impl<K: Ord> Collector<K> {
#[doc(hidden)]
#[must_use]
pub fn new(limits: Limits) -> Self {
Self {
ids: BTreeMap::new(),
graph: BehaviorGraph {
states: vec![],
edges: vec![],
concrete: vec![],
roots: vec![],
},
limits,
count: 0,
}
}
#[doc(hidden)]
#[must_use]
pub fn graph(&self) -> &BehaviorGraph {
&self.graph
}
#[doc(hidden)]
#[must_use]
pub fn limits(&self) -> Limits {
self.limits
}
#[doc(hidden)]
pub fn allow_emitted(&self, n: u64, ordinal: Option<u64>) -> Result<(), Verdict> {
self.allow_generated(n)?;
if ordinal.is_some_and(|ordinal| ordinal >= self.limits.successors_per_unit) {
Err(limit("successors per source (scratch admission)"))
} else {
Ok(())
}
}
#[doc(hidden)]
pub fn state(&mut self, key: K, vals: StateVals, id: Option<u64>) -> Result<usize, Verdict> {
if let Some(id) = id {
let id = usize::try_from(id).map_err(|_| bug("state id exceeds address space"))?;
if id != self.graph.states.len() || self.ids.contains_key(&key) {
return Err(bug("graph discovery ids differ from trace log"));
}
if id >= self.limits.states {
return Err(limit("states"));
}
self.ids.insert(key, id);
self.graph.states.push(vals);
self.graph.edges.push(vec![]);
self.graph.concrete.push(vec![]);
Ok(id)
} else {
self.ids
.get(&key)
.copied()
.ok_or_else(|| bug("seen graph state has no discovery id"))
}
}
#[doc(hidden)]
pub fn edge(&mut self, from: u64, edge: Edge) -> Result<(), Verdict> {
if self.count >= self.limits.edges {
return Err(limit("edges"));
}
let from = usize::try_from(from).map_err(|_| bug("edge source exceeds address space"))?;
let row = self
.graph
.edges
.get_mut(from)
.ok_or_else(|| bug("edge source was not discovered"))?;
row.push(edge);
self.count += 1;
Ok(())
}
#[doc(hidden)]
pub fn quotas(&self, sources: usize, generated: u64) -> Result<(usize, u64), Verdict> {
let edges = self
.limits
.edges
.checked_sub(self.count)
.and_then(|n| n.checked_sub(sources))
.ok_or_else(|| limit("implicit stutters"))?;
let sources_u64 = u64::try_from(sources).map_err(|_| limit("source count"))?;
let remaining = self
.limits
.generated
.checked_sub(generated)
.ok_or_else(|| limit("generated states"))?;
Ok((edges / sources, remaining / sources_u64))
}
#[doc(hidden)]
pub fn allow_generated(&self, n: u64) -> Result<(), Verdict> {
if n > self.limits.generated {
Err(limit("generated states"))
} else {
Ok(())
}
}
#[doc(hidden)]
pub fn record(
&mut self,
key: K,
vals: StateVals,
id: Option<u64>,
parent: Option<u64>,
succ: &Successor<'_>,
) -> Result<(), Verdict> {
self.record_fields(key, vals, id, parent, succ.ordinal, succ.action.label())
}
#[doc(hidden)]
pub fn record_fields(
&mut self,
key: K,
vals: StateVals,
id: Option<u64>,
parent: Option<u64>,
ordinal: u64,
label: &str,
) -> Result<(), Verdict> {
let concrete = vals.clone();
let target = self.state(key, vals, id)?;
if let Some(from) = parent {
self.edge(
from,
Edge {
to: target,
ordinal: Some(ordinal),
label: Some(label.to_owned()),
},
)?;
let from = usize::try_from(from).map_err(|_| bug("source exceeds address space"))?;
let row = self
.graph
.concrete
.get_mut(from)
.ok_or_else(|| bug("concrete edge source was not discovered"))?;
row.push(ConcreteSuccessor {
state: concrete,
ordinal,
label: label.to_owned(),
});
} else {
self.root(target);
}
Ok(())
}
#[doc(hidden)]
pub fn stutter(&mut self, from: u64) -> Result<(), Verdict> {
let to = usize::try_from(from).map_err(|_| bug("stutter id exceeds address space"))?;
self.edge(
from,
Edge {
to,
ordinal: None,
label: None,
},
)
}
#[doc(hidden)]
pub fn root(&mut self, id: usize) {
if let Err(at) = self.graph.roots.binary_search(&id) {
self.graph.roots.insert(at, id);
}
}
#[doc(hidden)]
#[must_use]
pub fn finish(self) -> BehaviorGraph {
self.graph
}
}
#[derive(Debug)]
pub struct GraphBuilder {
collector: Collector<u64>,
}
impl GraphBuilder {
#[must_use]
pub fn new(limits: Limits) -> Self {
Self {
collector: Collector::new(limits),
}
}
pub fn allow_emitted(&self, generated: u64, ordinal: Option<u64>) -> Result<(), Verdict> {
self.collector.allow_emitted(generated, ordinal)
}
pub fn record(
&mut self,
key: u64,
state: StateVals,
id: Option<u64>,
parent: Option<u64>,
ordinal: u64,
label: &str,
) -> Result<(), Verdict> {
self.collector
.record_fields(key, state, id, parent, ordinal, label)
}
pub fn stutter(&mut self, from: u64) -> Result<(), Verdict> {
self.collector.stutter(from)
}
#[must_use]
pub fn graph(&self) -> &BehaviorGraph {
self.collector.graph()
}
pub fn complete(self, safety: CheckResult, options: CheckOptions) -> Result<Complete, Verdict> {
if safety.verdict != Verdict::Success {
return Err(safety.verdict);
}
let limits = self.collector.limits();
let graph = self.collector.finish();
let Some(stats) = safety.stats else {
return Err(bug("completed exploration did not return statistics"));
};
let completion = GraphCompletion::finalize(&graph, stats, limits)?;
Ok(Complete::from_producer(
graph, safety, options, stats, completion,
))
}
pub fn prefix(
self,
level: u64,
safety: CheckResult,
options: CheckOptions,
) -> Result<Prefix, Verdict> {
if safety.verdict != Verdict::Success {
return Err(safety.verdict);
}
let graph = self.collector.finish();
let Some(stats) = safety.stats else {
return Err(bug("prefix did not return statistics"));
};
if stats.left_on_queue == 0 {
return Err(bug("prefix has exhausted frontier"));
}
Ok(Prefix::from_producer(graph, safety, options, stats, level))
}
}
#[doc(hidden)]
#[must_use]
pub fn bug(s: &str) -> Verdict {
Verdict::InternalError {
message: format!("graph capture: {s}"),
}
}
#[doc(hidden)]
#[must_use]
pub fn limit(s: &str) -> Verdict {
Verdict::ResourceLimit {
message: format!("behavior graph capture {s}"),
}
}
#[must_use]
pub fn runtime_names_only(model: &Model) -> bool {
!model.sequential.is_empty()
&& model.sequential_names_only
&& !crate::admission::effectful(model)
}
#[must_use]
pub fn refusal(model: &Model, opts: &CheckOptions, parallel: bool) -> Option<String> {
if opts.candidate_memory_bytes.is_some() || opts.candidate_directory.is_some() {
return Some("candidate spill with behavior graph capture is not implemented".into());
}
if opts.frontier_memory_bytes.is_some() {
return Some("frontier spill with behavior graph capture is not yet certified".into());
}
if opts.predecessor_memory_bytes.is_some() || opts.predecessor_directory.is_some() {
return Some("predecessor spill with behavior graph capture is not implemented".into());
}
if parallel
&& model
.evaluator
.validate_model_context(&model.ir, &model.names)
.is_err()
{
return Some("concrete pool capture foreign IR or name table".into());
}
if model.evaluator.options() != &opts.eval {
return Some("graph capture evaluator profile mismatch".into());
}
if model.symmetry.is_some() && model.symmetry_liveness().requested() != opts.symmetry_liveness {
return Some("graph capture symmetry-liveness policy mismatch".into());
}
if model.view.is_some() {
return Some(
"graph capture with VIEW requires quotient edge and closing-state evidence".into(),
);
}
if model.symmetry_reduction.is_some()
|| (model.symmetry.is_some() && !model.unreduced_symmetry_liveness())
{
if !model.symmetry_liveness().genuine_temporal() {
return Some(
"graph capture with SYMMETRY needs a genuine temporal unreduced policy".into(),
);
}
return Some(match opts.symmetry_liveness {
dive_model::SymmetryLiveness::Refuse => {
"SYMMETRY with liveness explicitly refused".into()
}
dive_model::SymmetryLiveness::Tlc => {
"TLC quotient liveness with SYMMETRY is not implemented".into()
}
dive_model::SymmetryLiveness::Unreduced => {
"graph capture with active or inconsistent SYMMETRY".into()
}
});
}
match engine::bound_configured_random(model) {
Ok(true) => {
return Some("graph capture with configured native random replacements".into());
}
Err(error) => return Some(format!("graph capture invalid native authority: {error}")),
Ok(false) => {}
}
if engine::uses_random_after_startup(model) {
return Some("graph capture with random operators".into());
}
if let Some(s) = model.stateful_checking() {
return Some(format!("graph capture with stateful checking: {s}"));
}
if let Some(u) = model
.unsupported
.iter()
.find(|u| u.kind != UnsupportedKind::TemporalProperty)
{
return Some(u.feature.clone());
}
if parallel && (!model.sequential.is_empty() || crate::admission::effectful(model)) {
return Some("concrete pool capture with effects or runtime names".into());
}
None
}
#[cfg(test)]
#[allow(clippy::panic, reason = "controlled internal thread failure")]
mod evidence_controls {
use super::{BehaviorGraph, Edge, GraphCompletion, Limits};
use crate::Stats;
#[test]
fn completed_graph_requires_actual_rows_roots_stutters_and_statistics() {
let graph = BehaviorGraph {
states: vec![Vec::new().into()],
edges: vec![vec![Edge {
to: 0,
ordinal: None,
label: None,
}]],
concrete: vec![vec![]],
roots: vec![0],
};
let stats = Stats {
generated: 1,
distinct: 1,
initial_generated: 1,
depth: 1,
left_on_queue: 0,
};
let limits = Limits::default();
assert!(GraphCompletion::finalize(&graph, stats, limits).is_ok());
for edit in 0..7 {
let mut bad = graph.clone();
match edit {
0 => bad.edges.clear(),
1 => bad.edges[0].clear(),
2 => bad.edges[0][0].to = 1,
3 => bad.concrete.clear(),
4 => bad.roots.clear(),
5 => bad.roots.push(0),
_ => bad.roots[0] = 1,
}
assert!(GraphCompletion::finalize(&bad, stats, limits).is_err());
}
for stats in [
Stats {
distinct: 2,
..stats
},
Stats {
left_on_queue: 1,
..stats
},
] {
assert!(GraphCompletion::finalize(&graph, stats, limits).is_err());
}
assert!(GraphCompletion::finalize(&graph, stats, Limits { edges: 0, ..limits }).is_err());
let empty = BehaviorGraph {
states: vec![],
edges: vec![],
concrete: vec![],
roots: vec![],
};
assert!(GraphCompletion::finalize(&empty, Stats::default(), limits).is_ok());
}
}