use std::ops::Range;
use dive_eval::HostControl;
use super::{CompleteEvidence, GraphCompletion, Limits, PrefixEvidence, bug, limit};
use crate::budget::EvaluationControl;
use crate::{CheckOptions, CheckResult, Verdict};
#[derive(Clone, Copy, Debug)]
pub struct CsrCaptureInput<'a> {
pub offsets: &'a [usize],
pub targets: &'a [u32],
pub ordinals: &'a [Option<u64>],
pub actions: &'a [Option<u32>],
pub edge_rows: &'a [u32],
pub representatives: &'a [u32],
pub roots: &'a [usize],
pub action_labels: &'a [String],
pub retained_rows: usize,
pub closed_rows: usize,
}
#[derive(Clone, Copy, Debug)]
pub struct CsrCapture<'a> {
input: CsrCaptureInput<'a>,
limits: Limits,
concrete: usize,
}
impl<'a> CsrCapture<'a> {
pub fn checked(
input: CsrCaptureInput<'a>,
limits: Limits,
control: &EvaluationControl,
) -> Result<Self, Verdict> {
poll(control)?;
let states = input.representatives.len();
let edges = input.targets.len();
if states > limits.states || edges > limits.edges {
return Err(limit("CSR entries"));
}
if input.offsets.len() != states.checked_add(1).ok_or_else(|| limit("CSR offsets"))?
|| input.offsets.first() != Some(&0)
|| input.offsets.last() != Some(&edges)
|| input.ordinals.len() != edges
|| input.actions.len() != edges
|| input.edge_rows.len() != edges
|| input.closed_rows > states
|| (states != 0 && input.roots.is_empty())
{
return Err(bug("inconsistent CSR array dimensions"));
}
let mut previous_root = None;
for (i, &root) in input.roots.iter().enumerate() {
checkpoint(control, i)?;
if root >= states || previous_root.is_some_and(|p| p >= root) {
return Err(bug("invalid CSR initial roots"));
}
previous_root = Some(root);
}
let mut concrete = 0usize;
for (source, &representative) in input.representatives.iter().enumerate() {
checkpoint(control, source)?;
if representative as usize >= input.retained_rows {
return Err(bug("CSR representative row out of range"));
}
let start = input.offsets[source];
let end = input.offsets[source + 1];
if start > end || end > edges {
return Err(bug("invalid CSR source offsets"));
}
if source >= input.closed_rows {
if start != end {
return Err(bug("unexpanded CSR frontier has outgoing edges"));
}
continue;
}
let Some(last) = end.checked_sub(1).filter(|&last| last >= start) else {
return Err(bug("missing CSR source/stutter row"));
};
if input.targets[last] as usize != source
|| input.ordinals[last].is_some()
|| input.actions[last].is_some()
|| input.edge_rows[last] != representative
{
return Err(bug("invalid CSR implicit stutter"));
}
let mut previous_ordinal = None;
for edge in start..last {
checkpoint(control, edge)?;
let Some(ordinal) = input.ordinals[edge] else {
return Err(bug("CSR generated edge lacks original ordinal"));
};
if ordinal >= limits.successors_per_unit {
return Err(limit("CSR source successors"));
}
if input.targets[edge] as usize >= states
|| input.edge_rows[edge] as usize >= input.retained_rows
|| input.actions[edge]
.is_some_and(|action| action as usize >= input.action_labels.len())
|| previous_ordinal.is_some_and(|previous| previous >= ordinal)
{
return Err(bug("invalid CSR original transition"));
}
previous_ordinal = Some(ordinal);
}
concrete = concrete
.checked_add(last - start)
.ok_or_else(|| limit("CSR concrete successors"))?;
}
poll(control)?;
Ok(Self {
input,
limits,
concrete,
})
}
#[must_use]
pub fn state_count(&self) -> usize {
self.input.representatives.len()
}
#[must_use]
pub const fn limits(&self) -> Limits {
self.limits
}
#[must_use]
pub fn offsets(&self) -> &'a [usize] {
self.input.offsets
}
#[must_use]
pub fn targets(&self) -> &'a [u32] {
self.input.targets
}
#[must_use]
pub fn roots(&self) -> &'a [usize] {
self.input.roots
}
#[must_use]
pub const fn closed_rows(&self) -> usize {
self.input.closed_rows
}
#[must_use]
pub fn outgoing_range(&self, source: usize) -> Option<Range<usize>> {
Some(*self.input.offsets.get(source)?..*self.input.offsets.get(source.checked_add(1)?)?)
}
#[must_use]
pub fn target(&self, edge: usize) -> Option<usize> {
self.input.targets.get(edge).map(|&target| target as usize)
}
#[must_use]
pub fn ordinal(&self, edge: usize) -> Option<Option<u64>> {
self.input.ordinals.get(edge).copied()
}
#[must_use]
pub fn label(&self, edge: usize) -> Option<Option<&'a str>> {
let ordinal = self.input.ordinals.get(edge)?;
if ordinal.is_none() {
return Some(None);
}
Some(Some(match self.input.actions.get(edge)? {
Some(action) => self.input.action_labels.get(*action as usize)?.as_str(),
None => "",
}))
}
#[must_use]
pub fn representative_row(&self, vertex: usize) -> Option<usize> {
self.input
.representatives
.get(vertex)
.map(|&row| row as usize)
}
#[must_use]
pub fn original_row(&self, source: usize, position: usize) -> Option<usize> {
let range = self.outgoing_range(source)?;
let edge = range.start.checked_add(position)?;
if edge >= range.end || self.input.ordinals.get(edge)?.is_none() {
return None;
}
self.input.edge_rows.get(edge).map(|&row| row as usize)
}
#[must_use]
pub fn original_count(&self, source: usize) -> Option<usize> {
let range = self.outgoing_range(source)?;
Some(range.len().saturating_sub(1))
}
}
#[derive(Clone, Debug)]
pub struct CsrComplete<'a> {
graph: CsrCapture<'a>,
evidence: CompleteEvidence,
}
impl<'a> CsrComplete<'a> {
pub fn from_producer(
input: CsrCaptureInput<'a>,
safety: CheckResult,
options: CheckOptions,
limits: Limits,
control: &EvaluationControl,
) -> Result<Self, Verdict> {
if safety.verdict != Verdict::Success {
return Err(safety.verdict);
}
let stats = safety
.stats
.ok_or_else(|| bug("CSR EOF did not return statistics"))?;
GraphCompletion::check_header(
input.representatives.len(),
input.roots,
stats,
limits,
Some(control),
)?;
let graph = CsrCapture::checked(input, limits, control)?;
if graph.closed_rows() != graph.state_count() {
return Err(bug("CSR EOF has unexpanded sources"));
}
let completion = GraphCompletion {
states: graph.state_count(),
edges: graph.targets().len(),
concrete_successors: graph.concrete,
roots: graph.roots().len(),
limits,
};
Ok(Self {
graph,
evidence: CompleteEvidence::new(safety, options, stats, completion),
})
}
#[must_use]
pub const fn graph(&self) -> &CsrCapture<'a> {
&self.graph
}
#[must_use]
pub const fn evidence(&self) -> &CompleteEvidence {
&self.evidence
}
#[must_use]
pub fn into_evidence(self) -> CompleteEvidence {
self.evidence
}
}
#[derive(Clone, Debug)]
pub struct CsrPrefix<'a> {
graph: CsrCapture<'a>,
evidence: PrefixEvidence,
}
impl<'a> CsrPrefix<'a> {
pub fn from_producer(
input: CsrCaptureInput<'a>,
level: u64,
safety: CheckResult,
options: CheckOptions,
limits: Limits,
control: &EvaluationControl,
) -> Result<Self, Verdict> {
if safety.verdict != Verdict::Success {
return Err(safety.verdict);
}
let stats = safety
.stats
.ok_or_else(|| bug("CSR prefix did not return statistics"))?;
if stats.generated > limits.generated {
return Err(limit("CSR prefix generated states"));
}
if stats.left_on_queue == 0
|| stats.distinct
!= u64::try_from(input.representatives.len())
.map_err(|_| bug("state count range"))?
|| input.closed_rows >= input.representatives.len()
|| stats.left_on_queue
!= u64::try_from(
input
.representatives
.len()
.saturating_sub(input.closed_rows),
)
.map_err(|_| bug("CSR frontier count range"))?
{
return Err(bug("inconsistent CSR prefix frontier/statistics"));
}
let graph = CsrCapture::checked(input, limits, control)?;
Ok(Self {
graph,
evidence: PrefixEvidence::new(safety, options, stats, level),
})
}
#[must_use]
pub const fn graph(&self) -> &CsrCapture<'a> {
&self.graph
}
#[must_use]
pub const fn evidence(&self) -> &PrefixEvidence {
&self.evidence
}
#[must_use]
pub fn into_evidence(self) -> PrefixEvidence {
self.evidence
}
}
#[doc(hidden)]
pub fn checkpoint(control: &EvaluationControl, position: usize) -> Result<(), Verdict> {
if position.is_multiple_of(256) {
poll(control)?;
}
Ok(())
}
#[doc(hidden)]
pub fn poll(control: &EvaluationControl) -> Result<(), Verdict> {
control.check().map_err(|interrupted| {
control
.verdict(&dive_eval::EvalError::interrupted(interrupted))
.unwrap_or_else(|| bug("CSR control interrupted without matching exhaustion"))
})
}