Skip to main content

dive_runtime/capture/
csr.rs

1//! Checked borrowed adjacency for a producer retaining its own state rows.
2
3use std::ops::Range;
4
5use dive_eval::HostControl;
6
7use super::{CompleteEvidence, GraphCompletion, Limits, PrefixEvidence, bug, limit};
8use crate::budget::EvaluationControl;
9use crate::{CheckOptions, CheckResult, Verdict};
10
11/// Borrowed producer arrays before structural checking.
12///
13/// Row ids identify opaque retained state rows, not semantically equal values.
14/// This metadata neither evaluates states nor proves a temporal property.
15#[derive(Clone, Copy, Debug)]
16pub struct CsrCaptureInput<'a> {
17    /// One start offset per representative, followed by the total edge count.
18    pub offsets: &'a [usize],
19    /// Dense representative destination ids, including implicit stutters.
20    pub targets: &'a [u32],
21    /// Original generation ordinals; only implicit stutters have no ordinal.
22    pub ordinals: &'a [Option<u64>],
23    /// Index in `action_labels`, or no named action. Stutters have no action.
24    pub actions: &'a [Option<u32>],
25    /// Exact original state row for each edge, including seen destinations.
26    pub edge_rows: &'a [u32],
27    /// First-discovery state row for every dense representative.
28    pub representatives: &'a [u32],
29    /// Distinct initial representatives, in discovery order.
30    pub roots: &'a [usize],
31    /// Run-local action labels, in the producer's existing order.
32    pub action_labels: &'a [String],
33    /// Number of retained opaque state rows.
34    pub retained_rows: usize,
35    /// Consecutive fully expanded sources. Remaining frontier rows are empty.
36    pub closed_rows: usize,
37}
38
39/// Immutable, structurally checked CSR capture, without completion authority.
40///
41/// Generated duplicates, ordinal gaps, action labels and original row identities
42/// remain intact. A successful shape check alone cannot establish exhaustion.
43#[derive(Clone, Copy, Debug)]
44pub struct CsrCapture<'a> {
45    input: CsrCaptureInput<'a>,
46    limits: Limits,
47    concrete: usize,
48}
49
50impl<'a> CsrCapture<'a> {
51    /// Checks structural invariants under the actual armed run control.
52    /// All closed sources end in exactly one implicit full-state stutter.
53    ///
54    /// # Errors
55    /// Malformed metadata, retained-entry limits, or an actual run interruption.
56    pub fn checked(
57        input: CsrCaptureInput<'a>,
58        limits: Limits,
59        control: &EvaluationControl,
60    ) -> Result<Self, Verdict> {
61        poll(control)?;
62        let states = input.representatives.len();
63        let edges = input.targets.len();
64        if states > limits.states || edges > limits.edges {
65            return Err(limit("CSR entries"));
66        }
67        if input.offsets.len() != states.checked_add(1).ok_or_else(|| limit("CSR offsets"))?
68            || input.offsets.first() != Some(&0)
69            || input.offsets.last() != Some(&edges)
70            || input.ordinals.len() != edges
71            || input.actions.len() != edges
72            || input.edge_rows.len() != edges
73            || input.closed_rows > states
74            || (states != 0 && input.roots.is_empty())
75        {
76            return Err(bug("inconsistent CSR array dimensions"));
77        }
78        let mut previous_root = None;
79        for (i, &root) in input.roots.iter().enumerate() {
80            checkpoint(control, i)?;
81            if root >= states || previous_root.is_some_and(|p| p >= root) {
82                return Err(bug("invalid CSR initial roots"));
83            }
84            previous_root = Some(root);
85        }
86        let mut concrete = 0usize;
87        for (source, &representative) in input.representatives.iter().enumerate() {
88            checkpoint(control, source)?;
89            if representative as usize >= input.retained_rows {
90                return Err(bug("CSR representative row out of range"));
91            }
92            let start = input.offsets[source];
93            let end = input.offsets[source + 1];
94            if start > end || end > edges {
95                return Err(bug("invalid CSR source offsets"));
96            }
97            if source >= input.closed_rows {
98                if start != end {
99                    return Err(bug("unexpanded CSR frontier has outgoing edges"));
100                }
101                continue;
102            }
103            let Some(last) = end.checked_sub(1).filter(|&last| last >= start) else {
104                return Err(bug("missing CSR source/stutter row"));
105            };
106            if input.targets[last] as usize != source
107                || input.ordinals[last].is_some()
108                || input.actions[last].is_some()
109                || input.edge_rows[last] != representative
110            {
111                return Err(bug("invalid CSR implicit stutter"));
112            }
113            let mut previous_ordinal = None;
114            for edge in start..last {
115                checkpoint(control, edge)?;
116                let Some(ordinal) = input.ordinals[edge] else {
117                    return Err(bug("CSR generated edge lacks original ordinal"));
118                };
119                if ordinal >= limits.successors_per_unit {
120                    return Err(limit("CSR source successors"));
121                }
122                if input.targets[edge] as usize >= states
123                    || input.edge_rows[edge] as usize >= input.retained_rows
124                    || input.actions[edge]
125                        .is_some_and(|action| action as usize >= input.action_labels.len())
126                    || previous_ordinal.is_some_and(|previous| previous >= ordinal)
127                {
128                    return Err(bug("invalid CSR original transition"));
129                }
130                previous_ordinal = Some(ordinal);
131            }
132            concrete = concrete
133                .checked_add(last - start)
134                .ok_or_else(|| limit("CSR concrete successors"))?;
135        }
136        poll(control)?;
137        Ok(Self {
138            input,
139            limits,
140            concrete,
141        })
142    }
143
144    /// Number of representative vertices, including the unexpanded frontier.
145    #[must_use]
146    pub fn state_count(&self) -> usize {
147        self.input.representatives.len()
148    }
149
150    /// Actual entry limits used for this shape check; these are not byte bounds.
151    #[must_use]
152    pub const fn limits(&self) -> Limits {
153        self.limits
154    }
155
156    /// Checked adjacency offsets, including the terminal offset.
157    #[must_use]
158    pub fn offsets(&self) -> &'a [usize] {
159        self.input.offsets
160    }
161
162    /// Checked dense edge destinations, including implicit stutters.
163    #[must_use]
164    pub fn targets(&self) -> &'a [u32] {
165        self.input.targets
166    }
167
168    /// Initial representatives in discovery order.
169    #[must_use]
170    pub fn roots(&self) -> &'a [usize] {
171        self.input.roots
172    }
173
174    /// Fully expanded source count at this committed boundary.
175    #[must_use]
176    pub const fn closed_rows(&self) -> usize {
177        self.input.closed_rows
178    }
179
180    /// Physical adjacency range for a source, including its implicit stutter.
181    #[must_use]
182    pub fn outgoing_range(&self, source: usize) -> Option<Range<usize>> {
183        Some(*self.input.offsets.get(source)?..*self.input.offsets.get(source.checked_add(1)?)?)
184    }
185
186    /// Destination of a physical adjacency entry.
187    #[must_use]
188    pub fn target(&self, edge: usize) -> Option<usize> {
189        self.input.targets.get(edge).map(|&target| target as usize)
190    }
191
192    /// Generation ordinal of a physical entry; stutters have `Some(None)`.
193    #[must_use]
194    pub fn ordinal(&self, edge: usize) -> Option<Option<u64>> {
195        self.input.ordinals.get(edge).copied()
196    }
197
198    /// Action label; generated unnamed actions use the empty label.
199    /// Stutters have `Some(None)`, and out-of-range entries have `None`.
200    #[must_use]
201    pub fn label(&self, edge: usize) -> Option<Option<&'a str>> {
202        let ordinal = self.input.ordinals.get(edge)?;
203        if ordinal.is_none() {
204            return Some(None);
205        }
206        Some(Some(match self.input.actions.get(edge)? {
207            Some(action) => self.input.action_labels.get(*action as usize)?.as_str(),
208            None => "",
209        }))
210    }
211
212    /// Opaque first-discovery row for a representative vertex.
213    #[must_use]
214    pub fn representative_row(&self, vertex: usize) -> Option<usize> {
215        self.input
216            .representatives
217            .get(vertex)
218            .map(|&row| row as usize)
219    }
220
221    /// Generated original row at a source's physical generated-edge position.
222    /// Positions exclude the final stutter and do not use generation ordinals.
223    #[must_use]
224    pub fn original_row(&self, source: usize, position: usize) -> Option<usize> {
225        let range = self.outgoing_range(source)?;
226        let edge = range.start.checked_add(position)?;
227        if edge >= range.end || self.input.ordinals.get(edge)?.is_none() {
228            return None;
229        }
230        self.input.edge_rows.get(edge).map(|&row| row as usize)
231    }
232
233    /// Generated originals in one source row, excluding the implicit stutter.
234    #[must_use]
235    pub fn original_count(&self, source: usize) -> Option<usize> {
236        let range = self.outgoing_range(source)?;
237        Some(range.len().saturating_sub(1))
238    }
239}
240
241/// Checked CSR and sealed facts from a successful, exhausted producer.
242#[derive(Clone, Debug)]
243pub struct CsrComplete<'a> {
244    graph: CsrCapture<'a>,
245    evidence: CompleteEvidence,
246}
247
248impl<'a> CsrComplete<'a> {
249    /// Finalizes successful producer EOF without constructing retained values.
250    ///
251    /// # Errors
252    /// The original non-success safety verdict, missing/inconsistent statistics,
253    /// malformed or incomplete CSR, a capture limit, or actual run interruption.
254    pub fn from_producer(
255        input: CsrCaptureInput<'a>,
256        safety: CheckResult,
257        options: CheckOptions,
258        limits: Limits,
259        control: &EvaluationControl,
260    ) -> Result<Self, Verdict> {
261        if safety.verdict != Verdict::Success {
262            return Err(safety.verdict);
263        }
264        let stats = safety
265            .stats
266            .ok_or_else(|| bug("CSR EOF did not return statistics"))?;
267        GraphCompletion::check_header(
268            input.representatives.len(),
269            input.roots,
270            stats,
271            limits,
272            Some(control),
273        )?;
274        let graph = CsrCapture::checked(input, limits, control)?;
275        if graph.closed_rows() != graph.state_count() {
276            return Err(bug("CSR EOF has unexpanded sources"));
277        }
278        let completion = GraphCompletion {
279            states: graph.state_count(),
280            edges: graph.targets().len(),
281            concrete_successors: graph.concrete,
282            roots: graph.roots().len(),
283            limits,
284        };
285        Ok(Self {
286            graph,
287            evidence: CompleteEvidence::new(safety, options, stats, completion),
288        })
289    }
290
291    /// Checked adjacency; state values stay with the original producer.
292    #[must_use]
293    pub const fn graph(&self) -> &CsrCapture<'a> {
294        &self.graph
295    }
296
297    /// Original successful producer facts, independent of adjacency storage.
298    #[must_use]
299    pub const fn evidence(&self) -> &CompleteEvidence {
300        &self.evidence
301    }
302
303    /// Detaches completion facts, releasing the borrowed adjacency.
304    #[must_use]
305    pub fn into_evidence(self) -> CompleteEvidence {
306        self.evidence
307    }
308}
309
310/// Checked committed CSR prefix with an explicitly unfinished frontier.
311#[derive(Clone, Debug)]
312pub struct CsrPrefix<'a> {
313    graph: CsrCapture<'a>,
314    evidence: PrefixEvidence,
315}
316
317impl<'a> CsrPrefix<'a> {
318    /// Finalizes a successful committed prefix. This never proves completion.
319    ///
320    /// # Errors
321    /// The original safety failure, missing/inconsistent statistics, exhausted
322    /// frontier, malformed CSR, a capture limit, or actual run interruption.
323    pub fn from_producer(
324        input: CsrCaptureInput<'a>,
325        level: u64,
326        safety: CheckResult,
327        options: CheckOptions,
328        limits: Limits,
329        control: &EvaluationControl,
330    ) -> Result<Self, Verdict> {
331        if safety.verdict != Verdict::Success {
332            return Err(safety.verdict);
333        }
334        let stats = safety
335            .stats
336            .ok_or_else(|| bug("CSR prefix did not return statistics"))?;
337        if stats.generated > limits.generated {
338            return Err(limit("CSR prefix generated states"));
339        }
340        if stats.left_on_queue == 0
341            || stats.distinct
342                != u64::try_from(input.representatives.len())
343                    .map_err(|_| bug("state count range"))?
344            || input.closed_rows >= input.representatives.len()
345            || stats.left_on_queue
346                != u64::try_from(
347                    input
348                        .representatives
349                        .len()
350                        .saturating_sub(input.closed_rows),
351                )
352                .map_err(|_| bug("CSR frontier count range"))?
353        {
354            return Err(bug("inconsistent CSR prefix frontier/statistics"));
355        }
356        let graph = CsrCapture::checked(input, limits, control)?;
357        Ok(Self {
358            graph,
359            evidence: PrefixEvidence::new(safety, options, stats, level),
360        })
361    }
362
363    /// Checked adjacency, including empty outgoing rows for the frontier.
364    #[must_use]
365    pub const fn graph(&self) -> &CsrCapture<'a> {
366        &self.graph
367    }
368
369    /// Original committed-prefix facts; these cannot be promoted to completion.
370    #[must_use]
371    pub const fn evidence(&self) -> &PrefixEvidence {
372        &self.evidence
373    }
374
375    /// Detaches prefix facts, releasing the borrowed adjacency.
376    #[must_use]
377    pub fn into_evidence(self) -> PrefixEvidence {
378        self.evidence
379    }
380}
381
382#[doc(hidden)]
383pub fn checkpoint(control: &EvaluationControl, position: usize) -> Result<(), Verdict> {
384    if position.is_multiple_of(256) {
385        poll(control)?;
386    }
387    Ok(())
388}
389
390#[doc(hidden)]
391pub fn poll(control: &EvaluationControl) -> Result<(), Verdict> {
392    control.check().map_err(|interrupted| {
393        control
394            .verdict(&dive_eval::EvalError::interrupted(interrupted))
395            .unwrap_or_else(|| bug("CSR control interrupted without matching exhaustion"))
396    })
397}