Skip to main content

dive_explore/
graph.rs

1//! The behavior graph of a run, as events for a temporal check.
2//!
3//! A [`GraphSink`] passed to [`crate::explore_with`] receives, in the
4//! one-worker commit order at any worker count, the events from which the
5//! `dive-runtime`'s capture collector builds its `BehaviorGraph`:
6//!
7//! - [`GraphSink::emitted`] for every generated state, before its checks;
8//! - [`GraphSink::state`] for every state inside the model that passed its
9//!   checks, new or already seen, with its source, ordinal and action;
10//! - [`GraphSink::stutter`] once a source is fully expanded;
11//! - [`GraphSink::level_done`] after each completed level, which may stop
12//!   the search there ([`crate::Verdict::PrefixStop`]).
13//!
14//! States outside the model are not reported. Vertex ids are discovery
15//! indexes, which are the ids of the predecessor log.
16
17use dive_core::{Handle, Heap};
18
19use crate::Stats;
20
21/// The sink ended the search; it keeps its own reason
22/// ([`crate::Verdict::GraphStop`]).
23#[derive(Clone, Copy, Debug, PartialEq, Eq)]
24pub struct Stopped;
25
26/// One accepted state inside the model.
27#[derive(Clone, Copy, Debug, PartialEq, Eq)]
28pub struct Step<'a> {
29    /// The state's key in the seen set. Without [`Self::seen`] ids, equal
30    /// keys are one vertex.
31    pub key: u64,
32    /// Its values (persistent handles) when it is new, with its new id.
33    pub new: Option<(u64, &'a [Handle])>,
34    /// The discovery id of an already-seen target, when the seen set retains
35    /// ids (the in-memory exact store); otherwise `None`, and the target is
36    /// resolved by [`Self::key`]. Always `None` for a new state.
37    pub seen: Option<u64>,
38    /// The actual accepted target, including already seen states. These
39    /// persistent handles retain the original closed representation (kind and
40    /// flags); equal keys do not permit replacing them with a representative.
41    pub original: &'a [Handle],
42    /// The expanded source (`None` for an initial state).
43    pub parent: Option<u64>,
44    /// Its position among the states generated from the same source (or
45    /// among the initial states), from 0.
46    pub ordinal: u64,
47    /// The index of the next-state action that emitted it (`None` for an
48    /// initial state).
49    pub action: Option<usize>,
50}
51
52/// Actual end of one source expansion, including a generator-error boundary.
53/// A terminal row has no implied successful stutter or completed-row evidence.
54#[derive(Clone, Copy, Debug)]
55pub struct SourceRow<'a> {
56    /// Original source discovery/predecessor identity.
57    pub source: u64,
58    /// Original persistent source values, distinct from a canonical key image.
59    pub original: &'a [Handle],
60    /// Actual complete candidates generated by this source before the event.
61    pub emitted: u64,
62    /// Actual generator failure, absent after successful generation.
63    pub next_error: Option<&'a crate::Failure>,
64    /// Producer counters at this source boundary, excluding it from the queue.
65    pub stats: Stats,
66}
67
68/// Receives the behavior graph of a run.
69pub trait GraphSink {
70    /// Maximum source states buffered by a parallel capture wave. This uses
71    /// the collector's existing source-wave bound, independently of workers.
72    fn max_expansion_units(&self) -> usize;
73
74    /// Maximum emitted successors of one source, before retaining values.
75    /// [`Self::emitted`] must refuse an ordinal at or above this bound, so
76    /// speculative admission is reported in the ordinary commit order.
77    fn max_successors_per_unit(&self) -> u64;
78
79    /// The `generated`-th generated state, the `ordinal`-th of its source
80    /// (`None` for an initial state), before its checks.
81    ///
82    /// # Errors
83    /// [`Stopped`] ends the search.
84    fn emitted(&mut self, generated: u64, ordinal: Option<u64>) -> Result<(), Stopped>;
85
86    /// An accepted state inside the model. `heap` reads its values. A sink
87    /// retaining handles must also keep `heap.store()` alive; the borrowed
88    /// slices themselves last only for this call.
89    ///
90    /// # Errors
91    /// [`Stopped`] ends the search.
92    fn state(&mut self, heap: &mut Heap, step: Step<'_>) -> Result<(), Stopped>;
93
94    /// The fully expanded source `source`: its implicit stutter.
95    ///
96    /// # Errors
97    /// [`Stopped`] ends the search.
98    fn stutter(&mut self, source: u64) -> Result<(), Stopped>;
99
100    /// Receives an actual successful or terminal source boundary. The default
101    /// observer does no work. A generator failure reaches this before stutter;
102    /// successful generation reaches it after stutter and deadlock checks.
103    ///
104    /// # Errors
105    /// [`Stopped`] ends the search with its original source diagnostic word.
106    fn source_row(&mut self, _heap: &mut Heap, _row: SourceRow<'_>) -> Result<(), Stopped> {
107        Ok(())
108    }
109
110    /// The level `level` was expanded and committed (the initial states are
111    /// level 1); `stats.left_on_queue` is the next level's size. Returns
112    /// whether the search stops here.
113    ///
114    /// # Errors
115    /// [`Stopped`] ends the search.
116    fn level_done(&mut self, level: u64, stats: Stats) -> Result<bool, Stopped>;
117}