1use std::collections::BTreeMap;
11
12use dive_eval::next::{StateVals, Successor};
13use dive_model::{Model, UnsupportedKind};
14
15use crate::admission as engine;
16use crate::{CheckOptions, CheckResult, Collision, Stats, Verdict, Workers};
17
18mod csr;
19mod evidence;
20pub use csr::{CsrCapture, CsrCaptureInput, CsrComplete, CsrPrefix};
21pub use evidence::{CompleteEvidence, PrefixEvidence};
22
23pub fn refuse_unproved_temporal_next_error(model: &Model, result: &mut CheckResult) -> bool {
47 if model.implied_temporals.is_empty() {
48 return false;
49 }
50 let Verdict::EvaluationError { site, cause, .. } = &result.verdict else {
51 return false;
52 };
53 if !matches!(
54 site,
55 crate::ErrorSite::Next
56 | crate::ErrorSite::ActionConstraint
57 | crate::ErrorSite::ImpliedAction
58 ) {
59 return false;
60 }
61 if cause.is_eval_exception() {
62 return false;
63 }
64 let observed = format!("Observed {site:?} evaluation error: {}", cause.tool_text());
65 result.verdict = Verdict::Unsupported {
66 feature: "post-Next temporal-demand primary error classification without a reached-row replay certificate".into(),
67 };
68 result.tlc_prints_stats = false;
69 result.counterexample = None;
70 result.notes.push(observed);
71 true
72}
73
74pub const MAX_EXPANSION_UNITS: usize = 8;
77
78#[derive(Clone, Copy, Debug, PartialEq, Eq)]
80pub struct Limits {
81 pub states: usize,
86 pub edges: usize,
88 pub generated: u64,
90 pub successors_per_unit: u64,
96}
97impl Default for Limits {
98 fn default() -> Self {
99 Self {
100 states: 1_000_000,
101 edges: 8_000_000,
102 generated: 32_000_000,
103 successors_per_unit: 65_536,
104 }
105 }
106}
107
108#[derive(Clone, Debug, PartialEq, Eq)]
110pub struct Edge {
111 pub to: usize,
113 pub ordinal: Option<u64>,
115 pub label: Option<String>,
117}
118
119#[derive(Clone, Debug)]
122pub struct ConcreteSuccessor {
123 pub state: StateVals,
125 pub ordinal: u64,
127 pub label: String,
129}
130
131#[derive(Clone, Debug, PartialEq, Eq)]
134pub struct GraphCompletion {
135 states: usize,
136 edges: usize,
137 concrete_successors: usize,
138 roots: usize,
139 limits: Limits,
140}
141impl GraphCompletion {
142 fn finalize(graph: &BehaviorGraph, counters: Stats, limits: Limits) -> Result<Self, Verdict> {
143 let states = graph.states.len();
144 Self::check_header(states, &graph.roots, counters, limits, None)?;
145 if graph.edges.len() != states || graph.concrete.len() != states {
146 return Err(bug("incomplete graph/statistics at successful EOF"));
147 }
148 let mut edges = 0usize;
149 let mut concrete_successors = 0usize;
150 for (source, (row, concrete)) in graph.edges.iter().zip(&graph.concrete).enumerate() {
153 edges = edges
154 .checked_add(row.len())
155 .filter(|&n| n <= limits.edges)
156 .ok_or_else(|| limit("completion edges"))?;
157 concrete_successors = concrete_successors
158 .checked_add(concrete.len())
159 .ok_or_else(|| limit("completion concrete successors"))?;
160 if row.len()
161 != concrete
162 .len()
163 .checked_add(1)
164 .ok_or_else(|| limit("completion row"))?
165 || row
166 .last()
167 .is_none_or(|e| e.to != source || e.ordinal.is_some() || e.label.is_some())
168 {
169 return Err(bug("missing completed source/stutter row"));
170 }
171 for (edge, original) in row.iter().zip(concrete) {
172 if edge.to >= states
173 || edge.ordinal != Some(original.ordinal)
174 || edge.label.as_deref() != Some(original.label.as_str())
175 {
176 return Err(bug("inconsistent completed concrete transition"));
177 }
178 }
179 }
180 Ok(Self {
181 states,
182 edges,
183 concrete_successors,
184 roots: graph.roots.len(),
185 limits,
186 })
187 }
188
189 fn check_header(
193 states: usize,
194 roots: &[usize],
195 counters: Stats,
196 limits: Limits,
197 control: Option<&crate::budget::EvaluationControl>,
198 ) -> Result<(), Verdict> {
199 if let Some(control) = control {
200 csr::poll(control)?;
201 }
202 if states > limits.states || counters.generated > limits.generated {
203 return Err(limit("completion entries"));
204 }
205 if counters.distinct != u64::try_from(states).map_err(|_| bug("state count range"))?
206 || counters.left_on_queue != 0
207 || (states != 0 && roots.is_empty())
208 {
209 return Err(bug("incomplete graph/statistics at successful EOF"));
210 }
211 let mut previous = None;
212 for (index, &root) in roots.iter().enumerate() {
213 if let Some(control) = control {
214 csr::checkpoint(control, index)?;
215 }
216 if root >= states || previous.is_some_and(|p| p >= root) {
217 return Err(bug("invalid completed initial roots"));
218 }
219 previous = Some(root);
220 }
221 Ok(())
222 }
223 #[must_use]
226 pub fn entries(&self) -> (usize, usize, usize, usize) {
227 (
228 self.states,
229 self.edges,
230 self.concrete_successors,
231 self.roots,
232 )
233 }
234 #[must_use]
236 pub fn limits(&self) -> Limits {
237 self.limits
238 }
239}
240
241pub trait Observer: Send {
249 fn stop_after_level(&self) -> bool {
252 false
253 }
254
255 fn init(&mut self, _id: usize, _state: &StateVals, _stats: Stats) -> Result<(), String> {
261 Ok(())
262 }
263
264 fn edge(
271 &mut self,
272 _from: usize,
273 _edge: &Edge,
274 _successor: &StateVals,
275 _stats: Stats,
276 ) -> Result<(), String> {
277 Ok(())
278 }
279
280 fn level_done(
287 &mut self,
288 _level: u64,
289 _graph: &BehaviorGraph,
290 _stats: Stats,
291 ) -> Result<(), String> {
292 Ok(())
293 }
294}
295
296#[derive(Clone, Debug)]
300pub struct BehaviorGraph {
301 pub states: Vec<StateVals>,
303 pub edges: Vec<Vec<Edge>>,
305 pub concrete: Vec<Vec<ConcreteSuccessor>>,
309 pub roots: Vec<usize>,
311}
312
313#[derive(Clone, Debug)]
317pub struct Complete {
318 evidence: CompleteEvidence,
319 pub options: CheckOptions,
321 pub graph: BehaviorGraph,
323 pub stats: Stats,
325 pub collision: Option<Collision>,
327 pub workers: Workers,
330 pub output: Vec<String>,
332 pub warnings: Vec<(u32, String)>,
334}
335
336impl Complete {
337 #[must_use]
340 pub fn completion(&self) -> &GraphCompletion {
341 self.evidence.completion()
342 }
343 #[must_use]
347 pub fn safety_result(&self) -> &CheckResult {
348 self.evidence.safety_result()
349 }
350
351 #[must_use]
354 pub fn evidence(&self) -> &CompleteEvidence {
355 &self.evidence
356 }
357
358 #[must_use]
361 pub fn into_evidence(self) -> CompleteEvidence {
362 self.evidence
363 }
364
365 fn from_producer(
366 graph: BehaviorGraph,
367 result: CheckResult,
368 options: CheckOptions,
369 stats: Stats,
370 completion: GraphCompletion,
371 ) -> Self {
372 Self {
373 collision: result.collision.clone(),
374 workers: result.workers.clone(),
375 output: result.output.clone(),
376 warnings: result.warnings.clone(),
377 evidence: CompleteEvidence::new(result, options.clone(), stats, completion),
378 options,
379 graph,
380 stats,
381 }
382 }
383}
384
385#[derive(Clone, Debug)]
387pub struct Prefix {
388 evidence: PrefixEvidence,
389 pub options: CheckOptions,
391 pub graph: BehaviorGraph,
393 pub stats: Stats,
395 pub collision: Option<Collision>,
397 pub workers: Workers,
399 pub output: Vec<String>,
401 pub warnings: Vec<(u32, String)>,
403}
404impl Prefix {
405 #[must_use]
407 pub const fn level(&self) -> u64 {
408 self.evidence.level()
409 }
410
411 #[must_use]
413 pub fn evidence(&self) -> &PrefixEvidence {
414 &self.evidence
415 }
416
417 #[must_use]
420 pub fn into_evidence(self) -> PrefixEvidence {
421 self.evidence
422 }
423
424 fn from_producer(
425 graph: BehaviorGraph,
426 result: CheckResult,
427 options: CheckOptions,
428 stats: Stats,
429 level: u64,
430 ) -> Self {
431 Self {
432 collision: result.collision.clone(),
433 workers: result.workers.clone(),
434 output: result.output.clone(),
435 warnings: result.warnings.clone(),
436 evidence: PrefixEvidence::new(result, options.clone(), stats, level),
437 options,
438 graph,
439 stats,
440 }
441 }
442}
443
444#[derive(Clone, Debug)]
446pub enum ControlledExploration {
447 Complete(Box<Complete>),
449 Prefix(Box<Prefix>),
451 Stopped(Box<CheckResult>),
453}
454impl From<Exploration> for ControlledExploration {
455 fn from(value: Exploration) -> Self {
456 match value {
457 Exploration::Complete(c) => Self::Complete(c),
458 Exploration::Stopped(s) => Self::Stopped(s),
459 }
460 }
461}
462
463#[doc(hidden)]
464pub fn elapsed(result: &mut Exploration, duration: std::time::Duration) {
465 match result {
466 Exploration::Stopped(stop) => stop.elapsed = duration,
467 Exploration::Complete(complete) => complete.evidence.set_elapsed(duration),
468 }
469}
470
471#[derive(Clone, Debug)]
473pub enum Exploration {
474 Complete(Box<Complete>),
476 Stopped(Box<CheckResult>),
479}
480
481#[derive(Debug)]
482#[doc(hidden)]
483pub struct Collector<K> {
484 ids: BTreeMap<K, usize>,
485 graph: BehaviorGraph,
486 limits: Limits,
487 count: usize,
488}
489
490impl<K: Ord> Collector<K> {
491 #[doc(hidden)]
492 #[must_use]
493 pub fn new(limits: Limits) -> Self {
494 Self {
495 ids: BTreeMap::new(),
496 graph: BehaviorGraph {
497 states: vec![],
498 edges: vec![],
499 concrete: vec![],
500 roots: vec![],
501 },
502 limits,
503 count: 0,
504 }
505 }
506
507 #[doc(hidden)]
508 #[must_use]
509 pub fn graph(&self) -> &BehaviorGraph {
510 &self.graph
511 }
512
513 #[doc(hidden)]
514 #[must_use]
515 pub fn limits(&self) -> Limits {
516 self.limits
517 }
518
519 #[doc(hidden)]
520 pub fn allow_emitted(&self, n: u64, ordinal: Option<u64>) -> Result<(), Verdict> {
521 self.allow_generated(n)?;
522 if ordinal.is_some_and(|ordinal| ordinal >= self.limits.successors_per_unit) {
523 Err(limit("successors per source (scratch admission)"))
524 } else {
525 Ok(())
526 }
527 }
528
529 #[doc(hidden)]
530 pub fn state(&mut self, key: K, vals: StateVals, id: Option<u64>) -> Result<usize, Verdict> {
531 if let Some(id) = id {
532 let id = usize::try_from(id).map_err(|_| bug("state id exceeds address space"))?;
533 if id != self.graph.states.len() || self.ids.contains_key(&key) {
534 return Err(bug("graph discovery ids differ from trace log"));
535 }
536 if id >= self.limits.states {
537 return Err(limit("states"));
538 }
539 self.ids.insert(key, id);
540 self.graph.states.push(vals);
541 self.graph.edges.push(vec![]);
542 self.graph.concrete.push(vec![]);
543 Ok(id)
544 } else {
545 self.ids
546 .get(&key)
547 .copied()
548 .ok_or_else(|| bug("seen graph state has no discovery id"))
549 }
550 }
551
552 #[doc(hidden)]
553 pub fn edge(&mut self, from: u64, edge: Edge) -> Result<(), Verdict> {
554 if self.count >= self.limits.edges {
555 return Err(limit("edges"));
556 }
557 let from = usize::try_from(from).map_err(|_| bug("edge source exceeds address space"))?;
558 let row = self
559 .graph
560 .edges
561 .get_mut(from)
562 .ok_or_else(|| bug("edge source was not discovered"))?;
563 row.push(edge);
564 self.count += 1;
565 Ok(())
566 }
567
568 #[doc(hidden)]
571 pub fn quotas(&self, sources: usize, generated: u64) -> Result<(usize, u64), Verdict> {
572 let edges = self
573 .limits
574 .edges
575 .checked_sub(self.count)
576 .and_then(|n| n.checked_sub(sources))
577 .ok_or_else(|| limit("implicit stutters"))?;
578 let sources_u64 = u64::try_from(sources).map_err(|_| limit("source count"))?;
579 let remaining = self
580 .limits
581 .generated
582 .checked_sub(generated)
583 .ok_or_else(|| limit("generated states"))?;
584 Ok((edges / sources, remaining / sources_u64))
585 }
586
587 #[doc(hidden)]
588 pub fn allow_generated(&self, n: u64) -> Result<(), Verdict> {
589 if n > self.limits.generated {
590 Err(limit("generated states"))
591 } else {
592 Ok(())
593 }
594 }
595
596 #[doc(hidden)]
597 pub fn record(
598 &mut self,
599 key: K,
600 vals: StateVals,
601 id: Option<u64>,
602 parent: Option<u64>,
603 succ: &Successor<'_>,
604 ) -> Result<(), Verdict> {
605 self.record_fields(key, vals, id, parent, succ.ordinal, succ.action.label())
606 }
607
608 #[doc(hidden)]
609 pub fn record_fields(
610 &mut self,
611 key: K,
612 vals: StateVals,
613 id: Option<u64>,
614 parent: Option<u64>,
615 ordinal: u64,
616 label: &str,
617 ) -> Result<(), Verdict> {
618 let concrete = vals.clone();
619 let target = self.state(key, vals, id)?;
620 if let Some(from) = parent {
621 self.edge(
622 from,
623 Edge {
624 to: target,
625 ordinal: Some(ordinal),
626 label: Some(label.to_owned()),
627 },
628 )?;
629 let from = usize::try_from(from).map_err(|_| bug("source exceeds address space"))?;
632 let row = self
633 .graph
634 .concrete
635 .get_mut(from)
636 .ok_or_else(|| bug("concrete edge source was not discovered"))?;
637 row.push(ConcreteSuccessor {
638 state: concrete,
639 ordinal,
640 label: label.to_owned(),
641 });
642 } else {
643 self.root(target);
644 }
645 Ok(())
646 }
647
648 #[doc(hidden)]
649 pub fn stutter(&mut self, from: u64) -> Result<(), Verdict> {
650 let to = usize::try_from(from).map_err(|_| bug("stutter id exceeds address space"))?;
651 self.edge(
652 from,
653 Edge {
654 to,
655 ordinal: None,
656 label: None,
657 },
658 )
659 }
660
661 #[doc(hidden)]
662 pub fn root(&mut self, id: usize) {
663 if let Err(at) = self.graph.roots.binary_search(&id) {
664 self.graph.roots.insert(at, id);
665 }
666 }
667
668 #[doc(hidden)]
669 #[must_use]
670 pub fn finish(self) -> BehaviorGraph {
671 self.graph
672 }
673}
674
675#[derive(Debug)]
698pub struct GraphBuilder {
699 collector: Collector<u64>,
700}
701
702impl GraphBuilder {
703 #[must_use]
705 pub fn new(limits: Limits) -> Self {
706 Self {
707 collector: Collector::new(limits),
708 }
709 }
710
711 pub fn allow_emitted(&self, generated: u64, ordinal: Option<u64>) -> Result<(), Verdict> {
717 self.collector.allow_emitted(generated, ordinal)
718 }
719
720 pub fn record(
730 &mut self,
731 key: u64,
732 state: StateVals,
733 id: Option<u64>,
734 parent: Option<u64>,
735 ordinal: u64,
736 label: &str,
737 ) -> Result<(), Verdict> {
738 self.collector
739 .record_fields(key, state, id, parent, ordinal, label)
740 }
741
742 pub fn stutter(&mut self, from: u64) -> Result<(), Verdict> {
747 self.collector.stutter(from)
748 }
749
750 #[must_use]
752 pub fn graph(&self) -> &BehaviorGraph {
753 self.collector.graph()
754 }
755
756 pub fn complete(self, safety: CheckResult, options: CheckOptions) -> Result<Complete, Verdict> {
763 if safety.verdict != Verdict::Success {
764 return Err(safety.verdict);
765 }
766 let limits = self.collector.limits();
767 let graph = self.collector.finish();
768 let Some(stats) = safety.stats else {
769 return Err(bug("completed exploration did not return statistics"));
770 };
771 let completion = GraphCompletion::finalize(&graph, stats, limits)?;
772 Ok(Complete::from_producer(
773 graph, safety, options, stats, completion,
774 ))
775 }
776
777 pub fn prefix(
785 self,
786 level: u64,
787 safety: CheckResult,
788 options: CheckOptions,
789 ) -> Result<Prefix, Verdict> {
790 if safety.verdict != Verdict::Success {
791 return Err(safety.verdict);
792 }
793 let graph = self.collector.finish();
794 let Some(stats) = safety.stats else {
795 return Err(bug("prefix did not return statistics"));
796 };
797 if stats.left_on_queue == 0 {
798 return Err(bug("prefix has exhausted frontier"));
799 }
800 Ok(Prefix::from_producer(graph, safety, options, stats, level))
801 }
802}
803
804#[doc(hidden)]
805#[must_use]
806pub fn bug(s: &str) -> Verdict {
807 Verdict::InternalError {
808 message: format!("graph capture: {s}"),
809 }
810}
811#[doc(hidden)]
812#[must_use]
813pub fn limit(s: &str) -> Verdict {
814 Verdict::ResourceLimit {
815 message: format!("behavior graph capture {s}"),
816 }
817}
818
819#[must_use]
825pub fn runtime_names_only(model: &Model) -> bool {
826 !model.sequential.is_empty()
827 && model.sequential_names_only
828 && !crate::admission::effectful(model)
829}
830
831#[must_use]
837pub fn refusal(model: &Model, opts: &CheckOptions, parallel: bool) -> Option<String> {
838 if opts.candidate_memory_bytes.is_some() || opts.candidate_directory.is_some() {
839 return Some("candidate spill with behavior graph capture is not implemented".into());
840 }
841 if opts.frontier_memory_bytes.is_some() {
842 return Some("frontier spill with behavior graph capture is not yet certified".into());
843 }
844 if opts.predecessor_memory_bytes.is_some() || opts.predecessor_directory.is_some() {
845 return Some("predecessor spill with behavior graph capture is not implemented".into());
846 }
847 if parallel
848 && model
849 .evaluator
850 .validate_model_context(&model.ir, &model.names)
851 .is_err()
852 {
853 return Some("concrete pool capture foreign IR or name table".into());
854 }
855 if model.evaluator.options() != &opts.eval {
856 return Some("graph capture evaluator profile mismatch".into());
857 }
858 if model.symmetry.is_some() && model.symmetry_liveness().requested() != opts.symmetry_liveness {
859 return Some("graph capture symmetry-liveness policy mismatch".into());
860 }
861 if model.view.is_some() {
862 return Some(
863 "graph capture with VIEW requires quotient edge and closing-state evidence".into(),
864 );
865 }
866 if model.symmetry_reduction.is_some()
867 || (model.symmetry.is_some() && !model.unreduced_symmetry_liveness())
868 {
869 if !model.symmetry_liveness().genuine_temporal() {
870 return Some(
871 "graph capture with SYMMETRY needs a genuine temporal unreduced policy".into(),
872 );
873 }
874 return Some(match opts.symmetry_liveness {
875 dive_model::SymmetryLiveness::Refuse => {
876 "SYMMETRY with liveness explicitly refused".into()
877 }
878 dive_model::SymmetryLiveness::Tlc => {
879 "TLC quotient liveness with SYMMETRY is not implemented".into()
880 }
881 dive_model::SymmetryLiveness::Unreduced => {
882 "graph capture with active or inconsistent SYMMETRY".into()
883 }
884 });
885 }
886 match engine::bound_configured_random(model) {
887 Ok(true) => {
888 return Some("graph capture with configured native random replacements".into());
889 }
890 Err(error) => return Some(format!("graph capture invalid native authority: {error}")),
891 Ok(false) => {}
892 }
893 if engine::uses_random_after_startup(model) {
894 return Some("graph capture with random operators".into());
895 }
896 if let Some(s) = model.stateful_checking() {
897 return Some(format!("graph capture with stateful checking: {s}"));
898 }
899 if let Some(u) = model
900 .unsupported
901 .iter()
902 .find(|u| u.kind != UnsupportedKind::TemporalProperty)
903 {
904 return Some(u.feature.clone());
905 }
906 if parallel && (!model.sequential.is_empty() || crate::admission::effectful(model)) {
907 return Some("concrete pool capture with effects or runtime names".into());
908 }
909 None
910}
911
912#[cfg(test)]
913#[allow(clippy::panic, reason = "controlled internal thread failure")]
914mod evidence_controls {
915 use super::{BehaviorGraph, Edge, GraphCompletion, Limits};
916 use crate::Stats;
917 #[test]
918 fn completed_graph_requires_actual_rows_roots_stutters_and_statistics() {
919 let graph = BehaviorGraph {
920 states: vec![Vec::new().into()],
921 edges: vec![vec![Edge {
922 to: 0,
923 ordinal: None,
924 label: None,
925 }]],
926 concrete: vec![vec![]],
927 roots: vec![0],
928 };
929 let stats = Stats {
930 generated: 1,
931 distinct: 1,
932 initial_generated: 1,
933 depth: 1,
934 left_on_queue: 0,
935 };
936 let limits = Limits::default();
937 assert!(GraphCompletion::finalize(&graph, stats, limits).is_ok());
938 for edit in 0..7 {
939 let mut bad = graph.clone();
940 match edit {
941 0 => bad.edges.clear(),
942 1 => bad.edges[0].clear(),
943 2 => bad.edges[0][0].to = 1,
944 3 => bad.concrete.clear(),
945 4 => bad.roots.clear(),
946 5 => bad.roots.push(0),
947 _ => bad.roots[0] = 1,
948 }
949 assert!(GraphCompletion::finalize(&bad, stats, limits).is_err());
950 }
951 for stats in [
952 Stats {
953 distinct: 2,
954 ..stats
955 },
956 Stats {
957 left_on_queue: 1,
958 ..stats
959 },
960 ] {
961 assert!(GraphCompletion::finalize(&graph, stats, limits).is_err());
962 }
963 assert!(GraphCompletion::finalize(&graph, stats, Limits { edges: 0, ..limits }).is_err());
964 let empty = BehaviorGraph {
965 states: vec![],
966 edges: vec![],
967 concrete: vec![],
968 roots: vec![],
969 };
970 assert!(GraphCompletion::finalize(&empty, Stats::default(), limits).is_ok());
971 }
972}