dive-explore 0.1.0

Breadth-first state-space exploration over compiled TLA+ plans
Documentation
//! The behavior graph of a run, as events for a temporal check.
//!
//! A [`GraphSink`] passed to [`crate::explore_with`] receives, in the
//! one-worker commit order at any worker count, the events from which the
//! `dive-runtime`'s capture collector builds its `BehaviorGraph`:
//!
//! - [`GraphSink::emitted`] for every generated state, before its checks;
//! - [`GraphSink::state`] for every state inside the model that passed its
//!   checks, new or already seen, with its source, ordinal and action;
//! - [`GraphSink::stutter`] once a source is fully expanded;
//! - [`GraphSink::level_done`] after each completed level, which may stop
//!   the search there ([`crate::Verdict::PrefixStop`]).
//!
//! States outside the model are not reported. Vertex ids are discovery
//! indexes, which are the ids of the predecessor log.

use dive_core::{Handle, Heap};

use crate::Stats;

/// The sink ended the search; it keeps its own reason
/// ([`crate::Verdict::GraphStop`]).
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Stopped;

/// One accepted state inside the model.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Step<'a> {
    /// The state's key in the seen set. Without [`Self::seen`] ids, equal
    /// keys are one vertex.
    pub key: u64,
    /// Its values (persistent handles) when it is new, with its new id.
    pub new: Option<(u64, &'a [Handle])>,
    /// The discovery id of an already-seen target, when the seen set retains
    /// ids (the in-memory exact store); otherwise `None`, and the target is
    /// resolved by [`Self::key`]. Always `None` for a new state.
    pub seen: Option<u64>,
    /// The actual accepted target, including already seen states. These
    /// persistent handles retain the original closed representation (kind and
    /// flags); equal keys do not permit replacing them with a representative.
    pub original: &'a [Handle],
    /// The expanded source (`None` for an initial state).
    pub parent: Option<u64>,
    /// Its position among the states generated from the same source (or
    /// among the initial states), from 0.
    pub ordinal: u64,
    /// The index of the next-state action that emitted it (`None` for an
    /// initial state).
    pub action: Option<usize>,
}

/// Actual end of one source expansion, including a generator-error boundary.
/// A terminal row has no implied successful stutter or completed-row evidence.
#[derive(Clone, Copy, Debug)]
pub struct SourceRow<'a> {
    /// Original source discovery/predecessor identity.
    pub source: u64,
    /// Original persistent source values, distinct from a canonical key image.
    pub original: &'a [Handle],
    /// Actual complete candidates generated by this source before the event.
    pub emitted: u64,
    /// Actual generator failure, absent after successful generation.
    pub next_error: Option<&'a crate::Failure>,
    /// Producer counters at this source boundary, excluding it from the queue.
    pub stats: Stats,
}

/// Receives the behavior graph of a run.
pub trait GraphSink {
    /// Maximum source states buffered by a parallel capture wave. This uses
    /// the collector's existing source-wave bound, independently of workers.
    fn max_expansion_units(&self) -> usize;

    /// Maximum emitted successors of one source, before retaining values.
    /// [`Self::emitted`] must refuse an ordinal at or above this bound, so
    /// speculative admission is reported in the ordinary commit order.
    fn max_successors_per_unit(&self) -> u64;

    /// The `generated`-th generated state, the `ordinal`-th of its source
    /// (`None` for an initial state), before its checks.
    ///
    /// # Errors
    /// [`Stopped`] ends the search.
    fn emitted(&mut self, generated: u64, ordinal: Option<u64>) -> Result<(), Stopped>;

    /// An accepted state inside the model. `heap` reads its values. A sink
    /// retaining handles must also keep `heap.store()` alive; the borrowed
    /// slices themselves last only for this call.
    ///
    /// # Errors
    /// [`Stopped`] ends the search.
    fn state(&mut self, heap: &mut Heap, step: Step<'_>) -> Result<(), Stopped>;

    /// The fully expanded source `source`: its implicit stutter.
    ///
    /// # Errors
    /// [`Stopped`] ends the search.
    fn stutter(&mut self, source: u64) -> Result<(), Stopped>;

    /// Receives an actual successful or terminal source boundary. The default
    /// observer does no work. A generator failure reaches this before stutter;
    /// successful generation reaches it after stutter and deadlock checks.
    ///
    /// # Errors
    /// [`Stopped`] ends the search with its original source diagnostic word.
    fn source_row(&mut self, _heap: &mut Heap, _row: SourceRow<'_>) -> Result<(), Stopped> {
        Ok(())
    }

    /// The level `level` was expanded and committed (the initial states are
    /// level 1); `stats.left_on_queue` is the next level's size. Returns
    /// whether the search stops here.
    ///
    /// # Errors
    /// [`Stopped`] ends the search.
    fn level_done(&mut self, level: u64, stats: Stats) -> Result<bool, Stopped>;
}