Skip to main content

dive_runtime/
capture.rs

1//! Bounded behavior-graph capture: the graph, evidence and admission types
2//! every producer shares (ADR 0155).
3//!
4//! A complete graph is exploration evidence, not a temporal verdict. A
5//! producer (the execution core, through [`GraphBuilder`] and [`CsrCapture`])
6//! retains every
7//! accepted generated edge, including duplicates, and adds explicit implicit
8//! stutters.
9
10use 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
23/// Refuses an actual Next or action-candidate error whose TLC primary depends
24/// on unproved later temporal demand. This is an admission guard, not evidence that fairness
25/// failed, and never changes an error into GENERAL.
26///
27/// TLC's worker continues liveness-row processing after a Next exception.
28/// A reached row error can clear `keepCallStack`, preserving the original
29/// primary instead of the ordinary replay class. Neither a temporal clause nor
30/// an unconfirmed Next word certifies that subsequent demand/replay. This
31/// guard adds no authority to existing `EvalException` classifications; measured
32/// division-by-zero Next controls retain their existing behavior.
33///
34/// Statistics, output, workers and elapsed time remain the actual producer's.
35/// The old uncertified error-ending claim and TLC-class/reporting flag are
36/// removed. Successful searches and safety-only errors are unchanged.
37///
38/// ```no_run
39/// # fn stopped(model: &dive_model::Model, result: &mut dive_runtime::CheckResult) {
40/// if dive_runtime::capture::refuse_unproved_temporal_next_error(model, result) {
41///     assert!(!result.verdict.is_verdict());
42///     assert!(result.verdict.tlc().is_none());
43/// }
44/// # }
45/// ```
46pub 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
74/// Maximum concurrently expanded source units during parallel capture.
75/// Fixed waves use this cap regardless of physical worker pool width.
76pub const MAX_EXPANSION_UNITS: usize = 8;
77
78/// Explicit entry-count bounds for retained graph data.
79#[derive(Clone, Copy, Debug, PartialEq, Eq)]
80pub struct Limits {
81    /// Maximum retained graph representatives. The ordinary engine may insert
82    /// the deciding state before collector admission fails; stopping distinct
83    /// counts can therefore exceed this bound by that state. This is not a
84    /// complete seen-set or aggregate heap budget.
85    pub states: usize,
86    /// Maximum generated and implicit-stutter edges combined.
87    pub edges: usize,
88    /// Maximum generated states, including duplicates and out-of-model states.
89    pub generated: u64,
90    /// Maximum emitted successors of one expanded source. This separate scratch
91    /// admission bound applies before successor checks in either engine. Parallel
92    /// capture buffers at most eight sources at once, regardless of worker count.
93    /// TLC setting: no such capture bound; exceeding it is a resource refusal,
94    /// never a complete exploration or evidence of TLC agreement.
95    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/// A generated transition or an implicit full-state stutter.
109#[derive(Clone, Debug, PartialEq, Eq)]
110pub struct Edge {
111    /// Dense destination state id.
112    pub to: usize,
113    /// Original successor ordinal, or `None` for the implicit stutter.
114    pub ordinal: Option<u64>,
115    /// TLC's action label, absent for an implicit stutter.
116    pub label: Option<String>,
117}
118
119/// An accepted generated successor, before stored representative replacement.
120/// This excludes the engine-added stutter.
121#[derive(Clone, Debug)]
122pub struct ConcreteSuccessor {
123    /// Original concrete IR-ordered values, including already seen states.
124    pub state: StateVals,
125    /// Original source-wide generation ordinal.
126    pub ordinal: u64,
127    /// Original action label.
128    pub label: String,
129}
130
131/// Actual retained safety graph completion. Public graph fields, copied
132/// statistics and a zero queue cannot construct this producer-owned receipt.
133#[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        // The already-admitted retention limits bound this structural scan.
151        // No values are hashed, normalized, compared or evaluated here.
152        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    // Both retained-value and CSR producers use the same completion header.
190    // Successful safety EOF is necessary; the representation-specific checks
191    // must additionally establish every expanded row and original successor.
192    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    /// Retained representatives, generated edges plus implicit stutters,
224    /// original concrete successors, and distinct initial roots, respectively.
225    #[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    /// Actual supplied capture entry limits; these are not aggregate byte bounds.
235    #[must_use]
236    pub fn limits(&self) -> Limits {
237        self.limits
238    }
239}
240
241/// Receives committed initialization and completed BFS levels on the coordinator.
242///
243/// All methods are inert by default. Initial events follow successful Init;
244/// edge events follow a fully committed level, in source and generator order.
245/// A failed or partial level emits no edge or level event. Callback errors stop
246/// exploration without a completed graph. These hooks establish no temporal verdict.
247///
248pub trait Observer: Send {
249    /// Requests a prefix stop after a successful completed-level callback.
250    /// Exhausted frontiers cannot stop as prefixes. The default preserves all existing observation behavior.
251    fn stop_after_level(&self) -> bool {
252        false
253    }
254
255    /// A distinct accepted initial state after every Init check succeeded.
256    /// Counters describe the complete initialization, including excluded candidates.
257    ///
258    /// # Errors
259    /// Return a diagnostic to stop exploration at the initialization boundary.
260    fn init(&mut self, _id: usize, _state: &StateVals, _stats: Stats) -> Result<(), String> {
261        Ok(())
262    }
263
264    /// An accepted transition or implicit stutter from a completed level.
265    /// `successor` is the original concrete state, including seen-state occurrences.
266    /// Counters include all generated candidates at the completed level.
267    ///
268    /// # Errors
269    /// Return a diagnostic to stop exploration at this completed-level boundary.
270    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    /// A fully committed level and its borrowed graph, after frontier append.
281    /// Unexpanded frontier states have empty outgoing rows. A prefix without a
282    /// violation does not prove a temporal property; exhaustion is still required.
283    ///
284    /// # Errors
285    /// Return a diagnostic to stop exploration at this completed-level boundary.
286    fn level_done(
287        &mut self,
288        _level: u64,
289        _graph: &BehaviorGraph,
290        _stats: Stats,
291    ) -> Result<(), String> {
292        Ok(())
293    }
294}
295
296/// A fully explored behavior graph in the engine's discovery order.
297/// States use the bound model's IR variable order. Fingerprint-mode identity
298/// has the same collision qualifications as the safety engine.
299#[derive(Clone, Debug)]
300pub struct BehaviorGraph {
301    /// Concrete state representatives, including all variable assignments.
302    pub states: Vec<StateVals>,
303    /// Outgoing edges in generator order, then the implicit stutter.
304    pub edges: Vec<Vec<Edge>>,
305    /// Accepted original generated successors in source-wide generator order.
306    /// Rows include duplicates and seen successors, and exclude implicit stutter.
307    /// Their concrete values must not be reconstructed from `states[edge.to]`.
308    pub concrete: Vec<Vec<ConcreteSuccessor>>,
309    /// Distinct in-model initial states in discovery order.
310    pub roots: Vec<usize>,
311}
312
313/// Evidence from a completed safety exploration. Standard capture does not
314/// evaluate temporal predicates. An observed capture can evaluate caller-owned
315/// predicates, but this evidence never certifies temporal acceptance.
316#[derive(Clone, Debug)]
317pub struct Complete {
318    evidence: CompleteEvidence,
319    /// Run settings, including the reported seed, profile and store mode.
320    pub options: CheckOptions,
321    /// The complete graph, including seen-state edges and implicit stutters.
322    pub graph: BehaviorGraph,
323    /// The shared engine's counters. Implicit stutters do not inflate them.
324    pub stats: Stats,
325    /// The safety engine's collision figures, absent for exact mode.
326    pub collision: Option<Collision>,
327    /// Requested and actual execution pool widths. Fixed waves contain at most
328    /// eight source states; a smaller frontier can use fewer concurrent units.
329    pub workers: Workers,
330    /// Start-up, assumption and search output in order.
331    pub output: Vec<String>,
332    /// Binding warnings, retaining their TLC message codes.
333    pub warnings: Vec<(u32, String)>,
334}
335
336impl Complete {
337    /// Immutable producer completion fact, independent of later edits to the
338    /// publicly inspectable graph or counters. Edited fields cannot recertify it.
339    #[must_use]
340    pub fn completion(&self) -> &GraphCompletion {
341        self.evidence.completion()
342    }
343    /// Actual ordinary safety-engine outcome, retained without reconstructing
344    /// counts, diagnostics, stopping facts or worker metadata from the graph.
345    /// This receipt does not certify any temporal obligation.
346    #[must_use]
347    pub fn safety_result(&self) -> &CheckResult {
348        self.evidence.safety_result()
349    }
350
351    /// Original graph-independent producer facts. Public capture-field edits do
352    /// not recertify the completed graph or change these facts.
353    #[must_use]
354    pub fn evidence(&self) -> &CompleteEvidence {
355        &self.evidence
356    }
357
358    /// Releases graph storage and retains only original producer facts.
359    /// This operation performs no temporal check and creates no holding verdict.
360    #[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/// Actual committed-level exploration prefix, explicitly not completion.
386#[derive(Clone, Debug)]
387pub struct Prefix {
388    evidence: PrefixEvidence,
389    /// Original run settings.
390    pub options: CheckOptions,
391    /// Retained graph; unexpanded rows remain empty.
392    pub graph: BehaviorGraph,
393    /// Actual counters at the committed boundary.
394    pub stats: Stats,
395    /// Fingerprint qualifications, absent for exact storage.
396    pub collision: Option<Collision>,
397    /// Actual requested and used workers after joined work.
398    pub workers: Workers,
399    /// Startup and exploration output in order.
400    pub output: Vec<String>,
401    /// Actual startup warnings.
402    pub warnings: Vec<(u32, String)>,
403}
404impl Prefix {
405    /// Last fully committed expansion level. No complete verdict is implied.
406    #[must_use]
407    pub const fn level(&self) -> u64 {
408        self.evidence.level()
409    }
410
411    /// Original facts from the successful committed boundary, without completion.
412    #[must_use]
413    pub fn evidence(&self) -> &PrefixEvidence {
414        &self.evidence
415    }
416
417    /// Releases the partial graph and retains the actual incomplete-prefix facts.
418    /// It cannot promote a prefix to completed exploration.
419    #[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/// Controlled capture distinguishes a real prefix from completed exploration.
445#[derive(Clone, Debug)]
446pub enum ControlledExploration {
447    /// Actual complete exploration, without a temporal verdict.
448    Complete(Box<Complete>),
449    /// Requested stop after a fully committed, unexhausted level.
450    Prefix(Box<Prefix>),
451    /// Safety, resource or unsupported stop.
452    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/// Graph capture cannot turn an incomplete or unsupported search into success.
472#[derive(Clone, Debug)]
473pub enum Exploration {
474    /// Complete safety exploration; explicitly not a temporal verdict.
475    Complete(Box<Complete>),
476    /// A safety stop, unsupported feature, resource bound or internal failure.
477    /// No partial graph is exposed as complete.
478    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    /// Derive per-source speculative retention quotas independent of worker
569    /// width. Reserve every implicit stutter before starting the worker pool.
570    #[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            // edge() charges the retained-entry bound before this clone is
630            // retained. The original source value survives identity deduplication.
631            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/// A behavior graph built by a producer outside this crate, such as the
676/// execution core: the same collector, limits and messages as capture
677/// through the shared safety engine, and the same completion checks.
678///
679/// The producer reports, in its commit order, each accepted state inside the
680/// model ([`Self::record`]) and each fully expanded source
681/// ([`Self::stutter`]), as the shared engine does. States are identified by
682/// a caller key; equal keys are one vertex. Before the search, the producer
683/// applies [`refusal`].
684///
685/// ```
686/// use dive_runtime::capture::{GraphBuilder, Limits};
687/// use dive_eval::next::StateVals;
688/// let mut graph = GraphBuilder::new(Limits::default());
689/// let s: StateVals = vec![Some(dive_value::Value::Bool(true))].into();
690/// graph.record(7, s.clone(), Some(0), None, 0, "Init")?;
691/// graph.record(7, s, None, Some(0), 0, "Next")?;
692/// graph.stutter(0)?;
693/// assert_eq!(graph.graph().edges[0].len(), 2);
694/// assert_eq!(graph.graph().roots, [0]);
695/// # Ok::<(), dive_runtime::Verdict>(())
696/// ```
697#[derive(Debug)]
698pub struct GraphBuilder {
699    collector: Collector<u64>,
700}
701
702impl GraphBuilder {
703    /// An empty graph with the given entry limits.
704    #[must_use]
705    pub fn new(limits: Limits) -> Self {
706        Self {
707            collector: Collector::new(limits),
708        }
709    }
710
711    /// Admits the `generated`-th generated state, emitted at `ordinal` of its
712    /// source (`None` for an initial state), before its checks.
713    ///
714    /// # Errors
715    /// The capture's generated-state or per-source resource limit.
716    pub fn allow_emitted(&self, generated: u64, ordinal: Option<u64>) -> Result<(), Verdict> {
717        self.collector.allow_emitted(generated, ordinal)
718    }
719
720    /// Records an accepted state inside the model with key `key` and values
721    /// `state`. `id` is its new discovery index when it is new, `None` when it
722    /// was seen. `parent` is the expanded source (`None` for an initial
723    /// state), `ordinal` its emission index there and `label` the action's
724    /// label.
725    ///
726    /// # Errors
727    /// A capture resource limit, or an id that is not the next discovery
728    /// index (an internal error).
729    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    /// The implicit stutter of the fully expanded source `from`.
743    ///
744    /// # Errors
745    /// The capture's edge limit.
746    pub fn stutter(&mut self, from: u64) -> Result<(), Verdict> {
747        self.collector.stutter(from)
748    }
749
750    /// The graph so far.
751    #[must_use]
752    pub fn graph(&self) -> &BehaviorGraph {
753        self.collector.graph()
754    }
755
756    /// The completed exploration: `safety` is the producer's successful
757    /// safety result, with its statistics.
758    ///
759    /// # Errors
760    /// The original non-success safety verdict, missing statistics, or a graph whose shape disagrees with them
761    /// (internal errors), or a capture entry limit.
762    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    /// The exploration stopped after the fully committed `level`, whose
778    /// frontier is not exhausted.
779    ///
780    /// # Errors
781    /// The original non-success safety verdict, missing statistics or an
782    /// exhausted frontier (internal errors). Successful unexhausted prefixes
783    /// remain incomplete and cannot establish a holding temporal verdict.
784    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/// Whether only runtime-name scheduling blocks a parallel producer.
820///
821/// This grants no producer or evaluation authority: a native caller must prove
822/// its actual fixed name domains separately. Reference pool refusal is unchanged.
823/// All source/configured/captured effects retain the conservative shared check.
824#[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/// Why graph capture refuses `model` under `opts` before any search, or
832/// `None`: the admission checks of the shared capture entry points, in their
833/// order, with their messages. `parallel` selects the concrete-pool checks.
834/// A producer outside this crate ([`GraphBuilder`]) applies the same checks,
835/// so that it refuses exactly what capture refuses.
836#[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}