dive-runtime 0.1.0

The run contract shared by dive's checking engines: options, budgets, results and capture evidence
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
//! Bounded behavior-graph capture: the graph, evidence and admission types
//! every producer shares (ADR 0155).
//!
//! A complete graph is exploration evidence, not a temporal verdict. A
//! producer (the execution core, through [`GraphBuilder`] and [`CsrCapture`])
//! retains every
//! accepted generated edge, including duplicates, and adds explicit implicit
//! stutters.

use std::collections::BTreeMap;

use dive_eval::next::{StateVals, Successor};
use dive_model::{Model, UnsupportedKind};

use crate::admission as engine;
use crate::{CheckOptions, CheckResult, Collision, Stats, Verdict, Workers};

mod csr;
mod evidence;
pub use csr::{CsrCapture, CsrCaptureInput, CsrComplete, CsrPrefix};
pub use evidence::{CompleteEvidence, PrefixEvidence};

/// Refuses an actual Next or action-candidate error whose TLC primary depends
/// on unproved later temporal demand. This is an admission guard, not evidence that fairness
/// failed, and never changes an error into GENERAL.
///
/// TLC's worker continues liveness-row processing after a Next exception.
/// A reached row error can clear `keepCallStack`, preserving the original
/// primary instead of the ordinary replay class. Neither a temporal clause nor
/// an unconfirmed Next word certifies that subsequent demand/replay. This
/// guard adds no authority to existing `EvalException` classifications; measured
/// division-by-zero Next controls retain their existing behavior.
///
/// Statistics, output, workers and elapsed time remain the actual producer's.
/// The old uncertified error-ending claim and TLC-class/reporting flag are
/// removed. Successful searches and safety-only errors are unchanged.
///
/// ```no_run
/// # fn stopped(model: &dive_model::Model, result: &mut dive_runtime::CheckResult) {
/// if dive_runtime::capture::refuse_unproved_temporal_next_error(model, result) {
///     assert!(!result.verdict.is_verdict());
///     assert!(result.verdict.tlc().is_none());
/// }
/// # }
/// ```
pub fn refuse_unproved_temporal_next_error(model: &Model, result: &mut CheckResult) -> bool {
    if model.implied_temporals.is_empty() {
        return false;
    }
    let Verdict::EvaluationError { site, cause, .. } = &result.verdict else {
        return false;
    };
    if !matches!(
        site,
        crate::ErrorSite::Next
            | crate::ErrorSite::ActionConstraint
            | crate::ErrorSite::ImpliedAction
    ) {
        return false;
    }
    if cause.is_eval_exception() {
        return false;
    }
    let observed = format!("Observed {site:?} evaluation error: {}", cause.tool_text());
    result.verdict = Verdict::Unsupported {
        feature: "post-Next temporal-demand primary error classification without a reached-row replay certificate".into(),
    };
    result.tlc_prints_stats = false;
    result.counterexample = None;
    result.notes.push(observed);
    true
}

/// Maximum concurrently expanded source units during parallel capture.
/// Fixed waves use this cap regardless of physical worker pool width.
pub const MAX_EXPANSION_UNITS: usize = 8;

/// Explicit entry-count bounds for retained graph data.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Limits {
    /// Maximum retained graph representatives. The ordinary engine may insert
    /// the deciding state before collector admission fails; stopping distinct
    /// counts can therefore exceed this bound by that state. This is not a
    /// complete seen-set or aggregate heap budget.
    pub states: usize,
    /// Maximum generated and implicit-stutter edges combined.
    pub edges: usize,
    /// Maximum generated states, including duplicates and out-of-model states.
    pub generated: u64,
    /// Maximum emitted successors of one expanded source. This separate scratch
    /// admission bound applies before successor checks in either engine. Parallel
    /// capture buffers at most eight sources at once, regardless of worker count.
    /// TLC setting: no such capture bound; exceeding it is a resource refusal,
    /// never a complete exploration or evidence of TLC agreement.
    pub successors_per_unit: u64,
}
impl Default for Limits {
    fn default() -> Self {
        Self {
            states: 1_000_000,
            edges: 8_000_000,
            generated: 32_000_000,
            successors_per_unit: 65_536,
        }
    }
}

/// A generated transition or an implicit full-state stutter.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Edge {
    /// Dense destination state id.
    pub to: usize,
    /// Original successor ordinal, or `None` for the implicit stutter.
    pub ordinal: Option<u64>,
    /// TLC's action label, absent for an implicit stutter.
    pub label: Option<String>,
}

/// An accepted generated successor, before stored representative replacement.
/// This excludes the engine-added stutter.
#[derive(Clone, Debug)]
pub struct ConcreteSuccessor {
    /// Original concrete IR-ordered values, including already seen states.
    pub state: StateVals,
    /// Original source-wide generation ordinal.
    pub ordinal: u64,
    /// Original action label.
    pub label: String,
}

/// Actual retained safety graph completion. Public graph fields, copied
/// statistics and a zero queue cannot construct this producer-owned receipt.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct GraphCompletion {
    states: usize,
    edges: usize,
    concrete_successors: usize,
    roots: usize,
    limits: Limits,
}
impl GraphCompletion {
    fn finalize(graph: &BehaviorGraph, counters: Stats, limits: Limits) -> Result<Self, Verdict> {
        let states = graph.states.len();
        Self::check_header(states, &graph.roots, counters, limits, None)?;
        if graph.edges.len() != states || graph.concrete.len() != states {
            return Err(bug("incomplete graph/statistics at successful EOF"));
        }
        let mut edges = 0usize;
        let mut concrete_successors = 0usize;
        // The already-admitted retention limits bound this structural scan.
        // No values are hashed, normalized, compared or evaluated here.
        for (source, (row, concrete)) in graph.edges.iter().zip(&graph.concrete).enumerate() {
            edges = edges
                .checked_add(row.len())
                .filter(|&n| n <= limits.edges)
                .ok_or_else(|| limit("completion edges"))?;
            concrete_successors = concrete_successors
                .checked_add(concrete.len())
                .ok_or_else(|| limit("completion concrete successors"))?;
            if row.len()
                != concrete
                    .len()
                    .checked_add(1)
                    .ok_or_else(|| limit("completion row"))?
                || row
                    .last()
                    .is_none_or(|e| e.to != source || e.ordinal.is_some() || e.label.is_some())
            {
                return Err(bug("missing completed source/stutter row"));
            }
            for (edge, original) in row.iter().zip(concrete) {
                if edge.to >= states
                    || edge.ordinal != Some(original.ordinal)
                    || edge.label.as_deref() != Some(original.label.as_str())
                {
                    return Err(bug("inconsistent completed concrete transition"));
                }
            }
        }
        Ok(Self {
            states,
            edges,
            concrete_successors,
            roots: graph.roots.len(),
            limits,
        })
    }

    // Both retained-value and CSR producers use the same completion header.
    // Successful safety EOF is necessary; the representation-specific checks
    // must additionally establish every expanded row and original successor.
    fn check_header(
        states: usize,
        roots: &[usize],
        counters: Stats,
        limits: Limits,
        control: Option<&crate::budget::EvaluationControl>,
    ) -> Result<(), Verdict> {
        if let Some(control) = control {
            csr::poll(control)?;
        }
        if states > limits.states || counters.generated > limits.generated {
            return Err(limit("completion entries"));
        }
        if counters.distinct != u64::try_from(states).map_err(|_| bug("state count range"))?
            || counters.left_on_queue != 0
            || (states != 0 && roots.is_empty())
        {
            return Err(bug("incomplete graph/statistics at successful EOF"));
        }
        let mut previous = None;
        for (index, &root) in roots.iter().enumerate() {
            if let Some(control) = control {
                csr::checkpoint(control, index)?;
            }
            if root >= states || previous.is_some_and(|p| p >= root) {
                return Err(bug("invalid completed initial roots"));
            }
            previous = Some(root);
        }
        Ok(())
    }
    /// Retained representatives, generated edges plus implicit stutters,
    /// original concrete successors, and distinct initial roots, respectively.
    #[must_use]
    pub fn entries(&self) -> (usize, usize, usize, usize) {
        (
            self.states,
            self.edges,
            self.concrete_successors,
            self.roots,
        )
    }
    /// Actual supplied capture entry limits; these are not aggregate byte bounds.
    #[must_use]
    pub fn limits(&self) -> Limits {
        self.limits
    }
}

/// Receives committed initialization and completed BFS levels on the coordinator.
///
/// All methods are inert by default. Initial events follow successful Init;
/// edge events follow a fully committed level, in source and generator order.
/// A failed or partial level emits no edge or level event. Callback errors stop
/// exploration without a completed graph. These hooks establish no temporal verdict.
///
pub trait Observer: Send {
    /// Requests a prefix stop after a successful completed-level callback.
    /// Exhausted frontiers cannot stop as prefixes. The default preserves all existing observation behavior.
    fn stop_after_level(&self) -> bool {
        false
    }

    /// A distinct accepted initial state after every Init check succeeded.
    /// Counters describe the complete initialization, including excluded candidates.
    ///
    /// # Errors
    /// Return a diagnostic to stop exploration at the initialization boundary.
    fn init(&mut self, _id: usize, _state: &StateVals, _stats: Stats) -> Result<(), String> {
        Ok(())
    }

    /// An accepted transition or implicit stutter from a completed level.
    /// `successor` is the original concrete state, including seen-state occurrences.
    /// Counters include all generated candidates at the completed level.
    ///
    /// # Errors
    /// Return a diagnostic to stop exploration at this completed-level boundary.
    fn edge(
        &mut self,
        _from: usize,
        _edge: &Edge,
        _successor: &StateVals,
        _stats: Stats,
    ) -> Result<(), String> {
        Ok(())
    }

    /// A fully committed level and its borrowed graph, after frontier append.
    /// Unexpanded frontier states have empty outgoing rows. A prefix without a
    /// violation does not prove a temporal property; exhaustion is still required.
    ///
    /// # Errors
    /// Return a diagnostic to stop exploration at this completed-level boundary.
    fn level_done(
        &mut self,
        _level: u64,
        _graph: &BehaviorGraph,
        _stats: Stats,
    ) -> Result<(), String> {
        Ok(())
    }
}

/// A fully explored behavior graph in the engine's discovery order.
/// States use the bound model's IR variable order. Fingerprint-mode identity
/// has the same collision qualifications as the safety engine.
#[derive(Clone, Debug)]
pub struct BehaviorGraph {
    /// Concrete state representatives, including all variable assignments.
    pub states: Vec<StateVals>,
    /// Outgoing edges in generator order, then the implicit stutter.
    pub edges: Vec<Vec<Edge>>,
    /// Accepted original generated successors in source-wide generator order.
    /// Rows include duplicates and seen successors, and exclude implicit stutter.
    /// Their concrete values must not be reconstructed from `states[edge.to]`.
    pub concrete: Vec<Vec<ConcreteSuccessor>>,
    /// Distinct in-model initial states in discovery order.
    pub roots: Vec<usize>,
}

/// Evidence from a completed safety exploration. Standard capture does not
/// evaluate temporal predicates. An observed capture can evaluate caller-owned
/// predicates, but this evidence never certifies temporal acceptance.
#[derive(Clone, Debug)]
pub struct Complete {
    evidence: CompleteEvidence,
    /// Run settings, including the reported seed, profile and store mode.
    pub options: CheckOptions,
    /// The complete graph, including seen-state edges and implicit stutters.
    pub graph: BehaviorGraph,
    /// The shared engine's counters. Implicit stutters do not inflate them.
    pub stats: Stats,
    /// The safety engine's collision figures, absent for exact mode.
    pub collision: Option<Collision>,
    /// Requested and actual execution pool widths. Fixed waves contain at most
    /// eight source states; a smaller frontier can use fewer concurrent units.
    pub workers: Workers,
    /// Start-up, assumption and search output in order.
    pub output: Vec<String>,
    /// Binding warnings, retaining their TLC message codes.
    pub warnings: Vec<(u32, String)>,
}

impl Complete {
    /// Immutable producer completion fact, independent of later edits to the
    /// publicly inspectable graph or counters. Edited fields cannot recertify it.
    #[must_use]
    pub fn completion(&self) -> &GraphCompletion {
        self.evidence.completion()
    }
    /// Actual ordinary safety-engine outcome, retained without reconstructing
    /// counts, diagnostics, stopping facts or worker metadata from the graph.
    /// This receipt does not certify any temporal obligation.
    #[must_use]
    pub fn safety_result(&self) -> &CheckResult {
        self.evidence.safety_result()
    }

    /// Original graph-independent producer facts. Public capture-field edits do
    /// not recertify the completed graph or change these facts.
    #[must_use]
    pub fn evidence(&self) -> &CompleteEvidence {
        &self.evidence
    }

    /// Releases graph storage and retains only original producer facts.
    /// This operation performs no temporal check and creates no holding verdict.
    #[must_use]
    pub fn into_evidence(self) -> CompleteEvidence {
        self.evidence
    }

    fn from_producer(
        graph: BehaviorGraph,
        result: CheckResult,
        options: CheckOptions,
        stats: Stats,
        completion: GraphCompletion,
    ) -> Self {
        Self {
            collision: result.collision.clone(),
            workers: result.workers.clone(),
            output: result.output.clone(),
            warnings: result.warnings.clone(),
            evidence: CompleteEvidence::new(result, options.clone(), stats, completion),
            options,
            graph,
            stats,
        }
    }
}

/// Actual committed-level exploration prefix, explicitly not completion.
#[derive(Clone, Debug)]
pub struct Prefix {
    evidence: PrefixEvidence,
    /// Original run settings.
    pub options: CheckOptions,
    /// Retained graph; unexpanded rows remain empty.
    pub graph: BehaviorGraph,
    /// Actual counters at the committed boundary.
    pub stats: Stats,
    /// Fingerprint qualifications, absent for exact storage.
    pub collision: Option<Collision>,
    /// Actual requested and used workers after joined work.
    pub workers: Workers,
    /// Startup and exploration output in order.
    pub output: Vec<String>,
    /// Actual startup warnings.
    pub warnings: Vec<(u32, String)>,
}
impl Prefix {
    /// Last fully committed expansion level. No complete verdict is implied.
    #[must_use]
    pub const fn level(&self) -> u64 {
        self.evidence.level()
    }

    /// Original facts from the successful committed boundary, without completion.
    #[must_use]
    pub fn evidence(&self) -> &PrefixEvidence {
        &self.evidence
    }

    /// Releases the partial graph and retains the actual incomplete-prefix facts.
    /// It cannot promote a prefix to completed exploration.
    #[must_use]
    pub fn into_evidence(self) -> PrefixEvidence {
        self.evidence
    }

    fn from_producer(
        graph: BehaviorGraph,
        result: CheckResult,
        options: CheckOptions,
        stats: Stats,
        level: u64,
    ) -> Self {
        Self {
            collision: result.collision.clone(),
            workers: result.workers.clone(),
            output: result.output.clone(),
            warnings: result.warnings.clone(),
            evidence: PrefixEvidence::new(result, options.clone(), stats, level),
            options,
            graph,
            stats,
        }
    }
}

/// Controlled capture distinguishes a real prefix from completed exploration.
#[derive(Clone, Debug)]
pub enum ControlledExploration {
    /// Actual complete exploration, without a temporal verdict.
    Complete(Box<Complete>),
    /// Requested stop after a fully committed, unexhausted level.
    Prefix(Box<Prefix>),
    /// Safety, resource or unsupported stop.
    Stopped(Box<CheckResult>),
}
impl From<Exploration> for ControlledExploration {
    fn from(value: Exploration) -> Self {
        match value {
            Exploration::Complete(c) => Self::Complete(c),
            Exploration::Stopped(s) => Self::Stopped(s),
        }
    }
}

#[doc(hidden)]
pub fn elapsed(result: &mut Exploration, duration: std::time::Duration) {
    match result {
        Exploration::Stopped(stop) => stop.elapsed = duration,
        Exploration::Complete(complete) => complete.evidence.set_elapsed(duration),
    }
}

/// Graph capture cannot turn an incomplete or unsupported search into success.
#[derive(Clone, Debug)]
pub enum Exploration {
    /// Complete safety exploration; explicitly not a temporal verdict.
    Complete(Box<Complete>),
    /// A safety stop, unsupported feature, resource bound or internal failure.
    /// No partial graph is exposed as complete.
    Stopped(Box<CheckResult>),
}

#[derive(Debug)]
#[doc(hidden)]
pub struct Collector<K> {
    ids: BTreeMap<K, usize>,
    graph: BehaviorGraph,
    limits: Limits,
    count: usize,
}

impl<K: Ord> Collector<K> {
    #[doc(hidden)]
    #[must_use]
    pub fn new(limits: Limits) -> Self {
        Self {
            ids: BTreeMap::new(),
            graph: BehaviorGraph {
                states: vec![],
                edges: vec![],
                concrete: vec![],
                roots: vec![],
            },
            limits,
            count: 0,
        }
    }

    #[doc(hidden)]
    #[must_use]
    pub fn graph(&self) -> &BehaviorGraph {
        &self.graph
    }

    #[doc(hidden)]
    #[must_use]
    pub fn limits(&self) -> Limits {
        self.limits
    }

    #[doc(hidden)]
    pub fn allow_emitted(&self, n: u64, ordinal: Option<u64>) -> Result<(), Verdict> {
        self.allow_generated(n)?;
        if ordinal.is_some_and(|ordinal| ordinal >= self.limits.successors_per_unit) {
            Err(limit("successors per source (scratch admission)"))
        } else {
            Ok(())
        }
    }

    #[doc(hidden)]
    pub fn state(&mut self, key: K, vals: StateVals, id: Option<u64>) -> Result<usize, Verdict> {
        if let Some(id) = id {
            let id = usize::try_from(id).map_err(|_| bug("state id exceeds address space"))?;
            if id != self.graph.states.len() || self.ids.contains_key(&key) {
                return Err(bug("graph discovery ids differ from trace log"));
            }
            if id >= self.limits.states {
                return Err(limit("states"));
            }
            self.ids.insert(key, id);
            self.graph.states.push(vals);
            self.graph.edges.push(vec![]);
            self.graph.concrete.push(vec![]);
            Ok(id)
        } else {
            self.ids
                .get(&key)
                .copied()
                .ok_or_else(|| bug("seen graph state has no discovery id"))
        }
    }

    #[doc(hidden)]
    pub fn edge(&mut self, from: u64, edge: Edge) -> Result<(), Verdict> {
        if self.count >= self.limits.edges {
            return Err(limit("edges"));
        }
        let from = usize::try_from(from).map_err(|_| bug("edge source exceeds address space"))?;
        let row = self
            .graph
            .edges
            .get_mut(from)
            .ok_or_else(|| bug("edge source was not discovered"))?;
        row.push(edge);
        self.count += 1;
        Ok(())
    }

    /// Derive per-source speculative retention quotas independent of worker
    /// width. Reserve every implicit stutter before starting the worker pool.
    #[doc(hidden)]
    pub fn quotas(&self, sources: usize, generated: u64) -> Result<(usize, u64), Verdict> {
        let edges = self
            .limits
            .edges
            .checked_sub(self.count)
            .and_then(|n| n.checked_sub(sources))
            .ok_or_else(|| limit("implicit stutters"))?;
        let sources_u64 = u64::try_from(sources).map_err(|_| limit("source count"))?;
        let remaining = self
            .limits
            .generated
            .checked_sub(generated)
            .ok_or_else(|| limit("generated states"))?;
        Ok((edges / sources, remaining / sources_u64))
    }

    #[doc(hidden)]
    pub fn allow_generated(&self, n: u64) -> Result<(), Verdict> {
        if n > self.limits.generated {
            Err(limit("generated states"))
        } else {
            Ok(())
        }
    }

    #[doc(hidden)]
    pub fn record(
        &mut self,
        key: K,
        vals: StateVals,
        id: Option<u64>,
        parent: Option<u64>,
        succ: &Successor<'_>,
    ) -> Result<(), Verdict> {
        self.record_fields(key, vals, id, parent, succ.ordinal, succ.action.label())
    }

    #[doc(hidden)]
    pub fn record_fields(
        &mut self,
        key: K,
        vals: StateVals,
        id: Option<u64>,
        parent: Option<u64>,
        ordinal: u64,
        label: &str,
    ) -> Result<(), Verdict> {
        let concrete = vals.clone();
        let target = self.state(key, vals, id)?;
        if let Some(from) = parent {
            self.edge(
                from,
                Edge {
                    to: target,
                    ordinal: Some(ordinal),
                    label: Some(label.to_owned()),
                },
            )?;
            // edge() charges the retained-entry bound before this clone is
            // retained. The original source value survives identity deduplication.
            let from = usize::try_from(from).map_err(|_| bug("source exceeds address space"))?;
            let row = self
                .graph
                .concrete
                .get_mut(from)
                .ok_or_else(|| bug("concrete edge source was not discovered"))?;
            row.push(ConcreteSuccessor {
                state: concrete,
                ordinal,
                label: label.to_owned(),
            });
        } else {
            self.root(target);
        }
        Ok(())
    }

    #[doc(hidden)]
    pub fn stutter(&mut self, from: u64) -> Result<(), Verdict> {
        let to = usize::try_from(from).map_err(|_| bug("stutter id exceeds address space"))?;
        self.edge(
            from,
            Edge {
                to,
                ordinal: None,
                label: None,
            },
        )
    }

    #[doc(hidden)]
    pub fn root(&mut self, id: usize) {
        if let Err(at) = self.graph.roots.binary_search(&id) {
            self.graph.roots.insert(at, id);
        }
    }

    #[doc(hidden)]
    #[must_use]
    pub fn finish(self) -> BehaviorGraph {
        self.graph
    }
}

/// A behavior graph built by a producer outside this crate, such as the
/// execution core: the same collector, limits and messages as capture
/// through the shared safety engine, and the same completion checks.
///
/// The producer reports, in its commit order, each accepted state inside the
/// model ([`Self::record`]) and each fully expanded source
/// ([`Self::stutter`]), as the shared engine does. States are identified by
/// a caller key; equal keys are one vertex. Before the search, the producer
/// applies [`refusal`].
///
/// ```
/// use dive_runtime::capture::{GraphBuilder, Limits};
/// use dive_eval::next::StateVals;
/// let mut graph = GraphBuilder::new(Limits::default());
/// let s: StateVals = vec![Some(dive_value::Value::Bool(true))].into();
/// graph.record(7, s.clone(), Some(0), None, 0, "Init")?;
/// graph.record(7, s, None, Some(0), 0, "Next")?;
/// graph.stutter(0)?;
/// assert_eq!(graph.graph().edges[0].len(), 2);
/// assert_eq!(graph.graph().roots, [0]);
/// # Ok::<(), dive_runtime::Verdict>(())
/// ```
#[derive(Debug)]
pub struct GraphBuilder {
    collector: Collector<u64>,
}

impl GraphBuilder {
    /// An empty graph with the given entry limits.
    #[must_use]
    pub fn new(limits: Limits) -> Self {
        Self {
            collector: Collector::new(limits),
        }
    }

    /// Admits the `generated`-th generated state, emitted at `ordinal` of its
    /// source (`None` for an initial state), before its checks.
    ///
    /// # Errors
    /// The capture's generated-state or per-source resource limit.
    pub fn allow_emitted(&self, generated: u64, ordinal: Option<u64>) -> Result<(), Verdict> {
        self.collector.allow_emitted(generated, ordinal)
    }

    /// Records an accepted state inside the model with key `key` and values
    /// `state`. `id` is its new discovery index when it is new, `None` when it
    /// was seen. `parent` is the expanded source (`None` for an initial
    /// state), `ordinal` its emission index there and `label` the action's
    /// label.
    ///
    /// # Errors
    /// A capture resource limit, or an id that is not the next discovery
    /// index (an internal error).
    pub fn record(
        &mut self,
        key: u64,
        state: StateVals,
        id: Option<u64>,
        parent: Option<u64>,
        ordinal: u64,
        label: &str,
    ) -> Result<(), Verdict> {
        self.collector
            .record_fields(key, state, id, parent, ordinal, label)
    }

    /// The implicit stutter of the fully expanded source `from`.
    ///
    /// # Errors
    /// The capture's edge limit.
    pub fn stutter(&mut self, from: u64) -> Result<(), Verdict> {
        self.collector.stutter(from)
    }

    /// The graph so far.
    #[must_use]
    pub fn graph(&self) -> &BehaviorGraph {
        self.collector.graph()
    }

    /// The completed exploration: `safety` is the producer's successful
    /// safety result, with its statistics.
    ///
    /// # Errors
    /// The original non-success safety verdict, missing statistics, or a graph whose shape disagrees with them
    /// (internal errors), or a capture entry limit.
    pub fn complete(self, safety: CheckResult, options: CheckOptions) -> Result<Complete, Verdict> {
        if safety.verdict != Verdict::Success {
            return Err(safety.verdict);
        }
        let limits = self.collector.limits();
        let graph = self.collector.finish();
        let Some(stats) = safety.stats else {
            return Err(bug("completed exploration did not return statistics"));
        };
        let completion = GraphCompletion::finalize(&graph, stats, limits)?;
        Ok(Complete::from_producer(
            graph, safety, options, stats, completion,
        ))
    }

    /// The exploration stopped after the fully committed `level`, whose
    /// frontier is not exhausted.
    ///
    /// # Errors
    /// The original non-success safety verdict, missing statistics or an
    /// exhausted frontier (internal errors). Successful unexhausted prefixes
    /// remain incomplete and cannot establish a holding temporal verdict.
    pub fn prefix(
        self,
        level: u64,
        safety: CheckResult,
        options: CheckOptions,
    ) -> Result<Prefix, Verdict> {
        if safety.verdict != Verdict::Success {
            return Err(safety.verdict);
        }
        let graph = self.collector.finish();
        let Some(stats) = safety.stats else {
            return Err(bug("prefix did not return statistics"));
        };
        if stats.left_on_queue == 0 {
            return Err(bug("prefix has exhausted frontier"));
        }
        Ok(Prefix::from_producer(graph, safety, options, stats, level))
    }
}

#[doc(hidden)]
#[must_use]
pub fn bug(s: &str) -> Verdict {
    Verdict::InternalError {
        message: format!("graph capture: {s}"),
    }
}
#[doc(hidden)]
#[must_use]
pub fn limit(s: &str) -> Verdict {
    Verdict::ResourceLimit {
        message: format!("behavior graph capture {s}"),
    }
}

/// Whether only runtime-name scheduling blocks a parallel producer.
///
/// This grants no producer or evaluation authority: a native caller must prove
/// its actual fixed name domains separately. Reference pool refusal is unchanged.
/// All source/configured/captured effects retain the conservative shared check.
#[must_use]
pub fn runtime_names_only(model: &Model) -> bool {
    !model.sequential.is_empty()
        && model.sequential_names_only
        && !crate::admission::effectful(model)
}

/// Why graph capture refuses `model` under `opts` before any search, or
/// `None`: the admission checks of the shared capture entry points, in their
/// order, with their messages. `parallel` selects the concrete-pool checks.
/// A producer outside this crate ([`GraphBuilder`]) applies the same checks,
/// so that it refuses exactly what capture refuses.
#[must_use]
pub fn refusal(model: &Model, opts: &CheckOptions, parallel: bool) -> Option<String> {
    if opts.candidate_memory_bytes.is_some() || opts.candidate_directory.is_some() {
        return Some("candidate spill with behavior graph capture is not implemented".into());
    }
    if opts.frontier_memory_bytes.is_some() {
        return Some("frontier spill with behavior graph capture is not yet certified".into());
    }
    if opts.predecessor_memory_bytes.is_some() || opts.predecessor_directory.is_some() {
        return Some("predecessor spill with behavior graph capture is not implemented".into());
    }
    if parallel
        && model
            .evaluator
            .validate_model_context(&model.ir, &model.names)
            .is_err()
    {
        return Some("concrete pool capture foreign IR or name table".into());
    }
    if model.evaluator.options() != &opts.eval {
        return Some("graph capture evaluator profile mismatch".into());
    }
    if model.symmetry.is_some() && model.symmetry_liveness().requested() != opts.symmetry_liveness {
        return Some("graph capture symmetry-liveness policy mismatch".into());
    }
    if model.view.is_some() {
        return Some(
            "graph capture with VIEW requires quotient edge and closing-state evidence".into(),
        );
    }
    if model.symmetry_reduction.is_some()
        || (model.symmetry.is_some() && !model.unreduced_symmetry_liveness())
    {
        if !model.symmetry_liveness().genuine_temporal() {
            return Some(
                "graph capture with SYMMETRY needs a genuine temporal unreduced policy".into(),
            );
        }
        return Some(match opts.symmetry_liveness {
            dive_model::SymmetryLiveness::Refuse => {
                "SYMMETRY with liveness explicitly refused".into()
            }
            dive_model::SymmetryLiveness::Tlc => {
                "TLC quotient liveness with SYMMETRY is not implemented".into()
            }
            dive_model::SymmetryLiveness::Unreduced => {
                "graph capture with active or inconsistent SYMMETRY".into()
            }
        });
    }
    match engine::bound_configured_random(model) {
        Ok(true) => {
            return Some("graph capture with configured native random replacements".into());
        }
        Err(error) => return Some(format!("graph capture invalid native authority: {error}")),
        Ok(false) => {}
    }
    if engine::uses_random_after_startup(model) {
        return Some("graph capture with random operators".into());
    }
    if let Some(s) = model.stateful_checking() {
        return Some(format!("graph capture with stateful checking: {s}"));
    }
    if let Some(u) = model
        .unsupported
        .iter()
        .find(|u| u.kind != UnsupportedKind::TemporalProperty)
    {
        return Some(u.feature.clone());
    }
    if parallel && (!model.sequential.is_empty() || crate::admission::effectful(model)) {
        return Some("concrete pool capture with effects or runtime names".into());
    }
    None
}

#[cfg(test)]
#[allow(clippy::panic, reason = "controlled internal thread failure")]
mod evidence_controls {
    use super::{BehaviorGraph, Edge, GraphCompletion, Limits};
    use crate::Stats;
    #[test]
    fn completed_graph_requires_actual_rows_roots_stutters_and_statistics() {
        let graph = BehaviorGraph {
            states: vec![Vec::new().into()],
            edges: vec![vec![Edge {
                to: 0,
                ordinal: None,
                label: None,
            }]],
            concrete: vec![vec![]],
            roots: vec![0],
        };
        let stats = Stats {
            generated: 1,
            distinct: 1,
            initial_generated: 1,
            depth: 1,
            left_on_queue: 0,
        };
        let limits = Limits::default();
        assert!(GraphCompletion::finalize(&graph, stats, limits).is_ok());
        for edit in 0..7 {
            let mut bad = graph.clone();
            match edit {
                0 => bad.edges.clear(),
                1 => bad.edges[0].clear(),
                2 => bad.edges[0][0].to = 1,
                3 => bad.concrete.clear(),
                4 => bad.roots.clear(),
                5 => bad.roots.push(0),
                _ => bad.roots[0] = 1,
            }
            assert!(GraphCompletion::finalize(&bad, stats, limits).is_err());
        }
        for stats in [
            Stats {
                distinct: 2,
                ..stats
            },
            Stats {
                left_on_queue: 1,
                ..stats
            },
        ] {
            assert!(GraphCompletion::finalize(&graph, stats, limits).is_err());
        }
        assert!(GraphCompletion::finalize(&graph, stats, Limits { edges: 0, ..limits }).is_err());
        let empty = BehaviorGraph {
            states: vec![],
            edges: vec![],
            concrete: vec![],
            roots: vec![],
        };
        assert!(GraphCompletion::finalize(&empty, Stats::default(), limits).is_ok());
    }
}