1use 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#[derive(Clone, Copy, Debug)]
16pub struct CsrCaptureInput<'a> {
17 pub offsets: &'a [usize],
19 pub targets: &'a [u32],
21 pub ordinals: &'a [Option<u64>],
23 pub actions: &'a [Option<u32>],
25 pub edge_rows: &'a [u32],
27 pub representatives: &'a [u32],
29 pub roots: &'a [usize],
31 pub action_labels: &'a [String],
33 pub retained_rows: usize,
35 pub closed_rows: usize,
37}
38
39#[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 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 #[must_use]
146 pub fn state_count(&self) -> usize {
147 self.input.representatives.len()
148 }
149
150 #[must_use]
152 pub const fn limits(&self) -> Limits {
153 self.limits
154 }
155
156 #[must_use]
158 pub fn offsets(&self) -> &'a [usize] {
159 self.input.offsets
160 }
161
162 #[must_use]
164 pub fn targets(&self) -> &'a [u32] {
165 self.input.targets
166 }
167
168 #[must_use]
170 pub fn roots(&self) -> &'a [usize] {
171 self.input.roots
172 }
173
174 #[must_use]
176 pub const fn closed_rows(&self) -> usize {
177 self.input.closed_rows
178 }
179
180 #[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 #[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 #[must_use]
194 pub fn ordinal(&self, edge: usize) -> Option<Option<u64>> {
195 self.input.ordinals.get(edge).copied()
196 }
197
198 #[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 #[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 #[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 #[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#[derive(Clone, Debug)]
243pub struct CsrComplete<'a> {
244 graph: CsrCapture<'a>,
245 evidence: CompleteEvidence,
246}
247
248impl<'a> CsrComplete<'a> {
249 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 #[must_use]
293 pub const fn graph(&self) -> &CsrCapture<'a> {
294 &self.graph
295 }
296
297 #[must_use]
299 pub const fn evidence(&self) -> &CompleteEvidence {
300 &self.evidence
301 }
302
303 #[must_use]
305 pub fn into_evidence(self) -> CompleteEvidence {
306 self.evidence
307 }
308}
309
310#[derive(Clone, Debug)]
312pub struct CsrPrefix<'a> {
313 graph: CsrCapture<'a>,
314 evidence: PrefixEvidence,
315}
316
317impl<'a> CsrPrefix<'a> {
318 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 #[must_use]
365 pub const fn graph(&self) -> &CsrCapture<'a> {
366 &self.graph
367 }
368
369 #[must_use]
371 pub const fn evidence(&self) -> &PrefixEvidence {
372 &self.evidence
373 }
374
375 #[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}