dive-store 0.1.0

State fingerprints and disk-backed state storage for TLA+ model checking
Documentation
//! The trace log: parent pointers for counterexample replay.
//!
//! Distinct states are numbered in discovery order (𝒪 order): a state's id is the
//! number of states found before it. For each state the log records its parent's id
//! (none for an initial state) and its **ordinal**: its index among the parent's
//! successors in enumeration order, or among the initial states. That is 12 bytes per
//! state.
//!
//! A counterexample is rebuilt by replay: regenerate the initial states and take the
//! one at the root's ordinal, then repeatedly regenerate the successors of the current
//! state and take the one at the next ordinal. No fingerprint matching is involved.

use crate::error::StoreError;

/// A distinct state's number, in discovery order.
pub type StateId = u64;

/// The parent field of an initial state.
const ROOT: u64 = u64::MAX;

/// One step of a path: how to regenerate a state from its parent.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct TraceStep {
    /// The state's id.
    pub id: StateId,
    /// The parent's id, or `None` for an initial state.
    pub parent: Option<StateId>,
    /// The state's index among its parent's successors (or among the initial
    /// states), in enumeration order.
    pub ordinal: u32,
}

/// Parent pointers of every distinct state, in discovery order: the in-memory
/// form of [`crate::predecessor::PredecessorLog`].
#[derive(Clone, Debug, Default)]
pub(crate) struct TraceLog {
    parents: Vec<u64>,
    ordinals: Vec<u32>,
}

impl TraceLog {
    /// An empty log.
    #[must_use]
    pub(crate) fn new() -> Self {
        Self::default()
    }

    /// Exact requested capacity before allocation, including existing spare capacity.
    pub(crate) fn reserved_bytes_for(&self, records: usize) -> Option<usize> {
        self.parents
            .capacity()
            .max(records)
            .checked_mul(8)?
            .checked_add(self.ordinals.capacity().max(records).checked_mul(4)?)
    }

    /// Reserves one record fallibly, without changing IDs or ordinals.
    pub(crate) fn reserve_record(
        &mut self,
        exact: bool,
    ) -> Result<(), std::collections::TryReserveError> {
        if exact {
            self.parents.try_reserve_exact(1)?;
            self.ordinals.try_reserve_exact(1)
        } else {
            self.parents.try_reserve(1)?;
            self.ordinals.try_reserve(1)
        }
    }

    /// Records the next initial state, the `ordinal`-th generated by `Init`.
    pub(crate) fn push_initial(&mut self, ordinal: u32) -> StateId {
        let id = self.parents.len() as u64;
        self.parents.push(ROOT);
        self.ordinals.push(ordinal);
        id
    }

    /// Records the next state, the `ordinal`-th successor of `parent`.
    ///
    /// # Errors
    /// [`StoreError::BadParent`] unless `parent` is an earlier state.
    pub(crate) fn push(&mut self, parent: StateId, ordinal: u32) -> Result<StateId, StoreError> {
        let id = self.parents.len() as u64;
        if parent >= id {
            return Err(StoreError::BadParent { id, parent });
        }
        self.parents.push(parent);
        self.ordinals.push(ordinal);
        Ok(id)
    }

    /// The record of state `id`.
    #[must_use]
    pub(crate) fn get(&self, id: StateId) -> Option<TraceStep> {
        let i = usize::try_from(id).ok()?;
        let parent = *self.parents.get(i)?;
        Some(TraceStep {
            id,
            parent: (parent != ROOT).then_some(parent),
            ordinal: *self.ordinals.get(i)?,
        })
    }

    /// The path from an initial state to `id`, root first.
    #[cfg(test)]
    ///
    /// # Errors
    /// [`StoreError::UnknownState`] if `id` was never recorded.
    pub(crate) fn path(&self, id: StateId) -> Result<Vec<TraceStep>, StoreError> {
        let mut path = Vec::new();
        let mut cur = Some(id);
        while let Some(i) = cur {
            let step = self.get(i).ok_or(StoreError::UnknownState(i))?;
            path.push(step);
            // Parents are strictly earlier, so this terminates.
            cur = step.parent;
        }
        path.reverse();
        Ok(path)
    }

    /// Heap memory held, in bytes (12 per state, plus spare capacity).
    #[must_use]
    pub(crate) fn memory_bytes(&self) -> usize {
        self.parents.capacity() * 8 + self.ordinals.capacity() * 4
    }
}

#[cfg(test)]
#[allow(
    clippy::expect_used,
    reason = "test code: a failed expectation is a test failure"
)]
mod tests {
    use proptest::prelude::*;

    use super::TraceLog;

    proptest! {
        #[test]
        fn trace_paths_follow_parents(
            parents in prop::collection::vec(any::<u16>(), 0..200),
            roots in 1usize..5,
        ) {
            let mut log = TraceLog::new();
            for r in 0..roots {
                log.push_initial(u32::try_from(r).unwrap_or(0));
            }
            let mut want_depth = vec![1usize; roots];
            for (i, p) in parents.iter().enumerate() {
                let id = roots + i;
                let parent = usize::from(*p) % id;
                let got = log.push(parent as u64, u32::from(*p)).expect("earlier parent");
                prop_assert_eq!(got, id as u64);
                want_depth.push(want_depth[parent] + 1);
            }
            let len = want_depth.len() as u64;
            for (id, d) in want_depth.iter().enumerate() {
                let path = log.path(id as u64).expect("recorded");
                prop_assert_eq!(path.len(), *d);
                prop_assert!(path[0].parent.is_none());
                for w in path.windows(2) {
                    prop_assert_eq!(w[1].parent, Some(w[0].id));
                }
            }
            prop_assert!(log.push(len, 0).is_err());
            prop_assert!(log.path(len).is_err());
        }
    }
}