dive-core 0.1.0

The dive execution core for TLA+: value store, plan compiler, interpreter and successor generation
Documentation
//! The per-worker transient arena.
//!
//! Values built while one state is expanded live here: node headers in one
//! vector and their contents in one pool of handles, so building a value does
//! not allocate once both vectors have grown to their steady size. The
//! arena is reset after each expansion and its epoch incremented. A handle
//! carries the epoch it was created in, and so does its node; dereferencing a
//! handle whose node is gone, or whose slot now holds a node of another
//! epoch, is an internal error. The check runs in every build, so a stale
//! handle is reported as a bug, never silently misread.
//!
//! A [`Mark`] and [`Arena::rollback`] free the nodes allocated after the mark
//! (for example a rejected filter candidate) and start a new epoch for later
//! allocations, so a handle to a freed node is detected in the same way.
//!
//! The `-arena` ablation keeps each node's contents in its own heap
//! allocation instead of the pool, freed at reset, which is what a design with
//! one allocation per value pays.

use crate::handle::Handle;
use crate::node::{Kind, View};

/// Epochs use 29 bits of the handle.
const EPOCH_MASK: u32 = (1 << 29) - 1;

#[derive(Clone, Copy, Debug)]
struct ANode {
    kind: Kind,
    flags: u8,
    epoch: u32,
    lo: i64,
    hash: u64,
    sum: u64,
    start: u32,
    len: u32,
}

/// A transient arena.
#[derive(Debug)]
pub struct Arena {
    epoch: u32,
    pub(crate) cache_owner: std::sync::Arc<()>,
    nodes: Vec<ANode>,
    pool: Vec<Handle>,
    boxed: Vec<Box<[Handle]>>,
    heap_mode: bool,
    /// For each node, its interned handle once it has been interned in this
    /// epoch (deep close shares interned subtrees).
    pub(crate) interned: Vec<Handle>,
    stale: std::cell::Cell<bool>,
    peak_nodes: usize,
    peak_pool: usize,
    /// Resets so far: a mark is valid only within the reset it was taken in.
    resets: u64,
    rollbacks: u64,
}

/// A point in an arena's allocation, for [`Arena::rollback`].
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Mark {
    resets: u64,
    nodes: usize,
    pool: usize,
    boxed: usize,
}

impl Arena {
    /// A new arena. `heap_mode` is the `-arena` ablation.
    #[must_use]
    pub fn new(heap_mode: bool) -> Self {
        Self {
            epoch: 1,
            cache_owner: std::sync::Arc::new(()),
            nodes: Vec::new(),
            pool: Vec::new(),
            boxed: Vec::new(),
            heap_mode,
            interned: Vec::new(),
            stale: std::cell::Cell::new(false),
            peak_nodes: 0,
            peak_pool: 0,
            resets: 0,
            rollbacks: 0,
        }
    }

    fn next_epoch(&mut self) {
        self.epoch = (self.epoch + 1) & EPOCH_MASK;
        if self.epoch == 0 {
            self.epoch = 1;
        }
    }

    /// The current allocation point.
    #[must_use]
    pub fn mark(&self) -> Mark {
        Mark {
            resets: self.resets,
            nodes: self.nodes.len(),
            pool: self.pool.len(),
            boxed: self.boxed.len(),
        }
    }

    /// Frees every node allocated after `mark`. Later allocations get a new
    /// epoch, so a kept handle to a freed node is detected as stale. A mark
    /// from before the last reset is a bug: it is recorded as a stale access
    /// and nothing is freed.
    pub fn rollback(&mut self, mark: Mark) {
        if mark.resets != self.resets || mark.nodes > self.nodes.len() {
            self.stale.set(true);
            return;
        }
        if mark.nodes == self.nodes.len() {
            return;
        }
        self.peak_nodes = self.peak_nodes.max(self.nodes.len());
        self.peak_pool = self.peak_pool.max(self.pool.len());
        self.nodes.truncate(mark.nodes);
        self.interned.truncate(mark.nodes);
        self.pool.truncate(mark.pool);
        self.boxed.truncate(mark.boxed);
        self.rollbacks += 1;
        self.next_epoch();
    }

    /// The number of rollbacks that freed at least one node.
    #[must_use]
    pub fn rollbacks(&self) -> u64 {
        self.rollbacks
    }

    /// Frees every transient and starts a new epoch.
    pub fn reset(&mut self) {
        self.peak_nodes = self.peak_nodes.max(self.nodes.len());
        self.peak_pool = self.peak_pool.max(self.pool.len());
        self.nodes.clear();
        self.pool.clear();
        self.boxed.clear();
        self.interned.clear();
        self.resets += 1;
        self.next_epoch();
    }

    /// The bytes the live transients hold, about: node headers, pool
    /// handles and the intern column.
    #[must_use]
    pub(crate) fn footprint(&self) -> usize {
        self.nodes.len() * std::mem::size_of::<ANode>()
            + (self.pool.len() + self.interned.len() + 2 * self.boxed.len())
                * std::mem::size_of::<Handle>()
    }

    /// Frees the capacity of an empty arena (after [`Self::reset`]), which
    /// a large one-off evaluation may have grown.
    pub(crate) fn release(&mut self) {
        if self.nodes.is_empty() {
            self.nodes = Vec::new();
            self.pool = Vec::new();
            self.boxed = Vec::new();
            self.interned = Vec::new();
        }
    }

    pub(crate) fn cache_revision(&self) -> (u64, u64) {
        (self.resets, self.rollbacks)
    }

    /// The current epoch.
    #[must_use]
    pub fn epoch(&self) -> u32 {
        self.epoch
    }

    /// Whether a stale or foreign transient handle was dereferenced (a bug).
    #[must_use]
    pub fn stale(&self) -> bool {
        self.stale.get()
    }

    /// The number of live transient nodes.
    #[must_use]
    pub fn len(&self) -> usize {
        self.nodes.len()
    }

    /// Whether the arena holds no node.
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.nodes.is_empty()
    }

    /// The largest number of nodes and pool handles held in one epoch.
    #[must_use]
    pub fn peak(&self) -> (usize, usize) {
        (
            self.peak_nodes.max(self.nodes.len()),
            self.peak_pool.max(self.pool.len()),
        )
    }

    /// Allocates a node with the given contents.
    #[allow(clippy::too_many_arguments, reason = "the node header, flat")]
    pub(crate) fn alloc(
        &mut self,
        kind: Kind,
        flags: u8,
        lo: i64,
        hash: u64,
        sum: u64,
        data: &[Handle],
    ) -> Handle {
        #[allow(
            clippy::cast_possible_truncation,
            reason = "bounded by the 32-bit index below"
        )]
        let index = self.nodes.len() as u32;
        let (start, len) = if self.heap_mode {
            #[allow(clippy::cast_possible_truncation, reason = "one box per node")]
            let start = self.boxed.len() as u32;
            self.boxed.push(data.into());
            (start, 0)
        } else {
            #[allow(
                clippy::cast_possible_truncation,
                reason = "pools above 2^32 handles are refused by the engine"
            )]
            let start = self.pool.len() as u32;
            self.pool.extend_from_slice(data);
            #[allow(clippy::cast_possible_truncation, reason = "as above")]
            (start, data.len() as u32)
        };
        self.nodes.push(ANode {
            kind,
            flags,
            epoch: self.epoch,
            lo,
            hash,
            sum,
            start,
            len,
        });
        self.interned.push(Handle::EMPTY);
        Handle::transient(self.epoch, index)
    }

    /// Appends a representation header sharing an earlier immutable payload.
    /// The source precedes this node, so rollback cannot retain a projection
    /// while freeing its payload. Only flags and the non-value payload change.
    pub(crate) fn project(&mut self, source: Handle, flags: u8, lo: i64) -> Option<Handle> {
        let index = self.index(source)?;
        let mut node = self.nodes[index];
        let index = u32::try_from(self.nodes.len()).ok()?;
        self.nodes.try_reserve(1).ok()?;
        self.interned.try_reserve(1).ok()?;
        node.flags = flags;
        node.lo = lo;
        node.epoch = self.epoch;
        self.nodes.push(node);
        self.interned.push(Handle::EMPTY);
        Some(Handle::transient(self.epoch, index))
    }

    /// The node behind a transient handle, if it belongs to this epoch,
    /// without recording a miss.
    #[inline]
    pub(crate) fn lookup(&self, h: Handle) -> Option<View<'_>> {
        let (epoch, index) = h.transient_parts();
        let n = self.nodes.get(index as usize)?;
        if n.epoch != epoch {
            return None;
        }
        let data: &[Handle] = if self.heap_mode {
            self.boxed.get(n.start as usize)?
        } else {
            self.pool
                .get(n.start as usize..(n.start + n.len) as usize)?
        };
        Some(View {
            kind: n.kind,
            flags: n.flags,
            lo: n.lo,
            hash: n.hash,
            sum: n.sum,
            data,
        })
    }

    /// The index of a transient handle of this epoch.
    pub(crate) fn index(&self, h: Handle) -> Option<usize> {
        let (epoch, index) = h.transient_parts();
        self.nodes
            .get(index as usize)
            .is_some_and(|n| n.epoch == epoch)
            .then_some(index as usize)
    }

    /// Records a stale access found elsewhere.
    pub(crate) fn mark_stale(&self) {
        self.stale.set(true);
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn handles_from_an_older_epoch_are_refused() {
        for heap in [false, true] {
            let mut a = Arena::new(heap);
            let one = Handle::int(1).unwrap_or(Handle::EMPTY);
            let h = a.alloc(Kind::Set, 0, 0, 7, 7, &[one]);
            assert_eq!(a.lookup(h).map(|v| v.data.len()), Some(1));
            a.reset();
            assert!(a.lookup(h).is_none(), "stale handle must not resolve");
            // A new node at the same index has a new epoch.
            let g = a.alloc(Kind::Set, 0, 0, 9, 9, &[]);
            assert_ne!(g, h);
            assert!(a.lookup(h).is_none());
            assert!(!a.stale(), "a plain lookup does not record a miss");
            assert_eq!(a.lookup(g).map(|v| v.hash), Some(9));
        }
    }

    #[test]
    fn rollback_frees_later_nodes_and_keeps_earlier_ones() {
        for heap in [false, true] {
            let mut a = Arena::new(heap);
            let one = Handle::int(1).unwrap_or(Handle::EMPTY);
            let keep = a.alloc(Kind::Set, 0, 0, 1, 1, &[one]);
            let m = a.mark();
            let gone = a.alloc(Kind::Set, 0, 0, 2, 2, &[one, one]);
            a.rollback(m);
            assert_eq!(a.len(), 1);
            assert_eq!(a.lookup(keep).map(|v| v.hash), Some(1));
            assert!(a.lookup(gone).is_none());
            // The freed slot is reused under a new epoch: the old handle
            // still does not resolve.
            let again = a.alloc(Kind::Set, 0, 0, 3, 3, &[]);
            assert_ne!(again, gone);
            assert!(a.lookup(gone).is_none());
            assert_eq!(a.lookup(again).map(|v| v.hash), Some(3));
            assert_eq!(a.lookup(keep).map(|v| v.data.len()), Some(1));
            assert_eq!(a.rollbacks(), 1);
            // A rollback with nothing to free changes nothing.
            let e = a.epoch();
            let m = a.mark();
            a.rollback(m);
            assert_eq!(a.epoch(), e);
            assert!(!a.stale());
            // A mark from before a reset is a bug.
            a.reset();
            a.rollback(m);
            assert!(a.stale());
        }
    }
    #[test]
    fn projected_payloads_share_storage_and_obey_both_rollback_modes() {
        for heap_mode in [false, true] {
            let mut arena = Arena::new(heap_mode);
            let before = arena.mark();
            let original = arena.alloc(
                Kind::IntFcn,
                crate::node::flags::TUPLE,
                1,
                7,
                7,
                &[Handle::TRUE; 256],
            );
            let after_original = arena.mark();
            let projection = arena.project(original, 0, 1).unwrap_or(Handle::EMPTY);
            assert!(!projection.is_empty());
            assert_eq!(
                arena.lookup(original).map(|v| v.data.as_ptr()),
                arena.lookup(projection).map(|v| v.data.as_ptr())
            );
            assert_eq!(
                arena.lookup(original).map(|v| v.flags),
                Some(crate::node::flags::TUPLE)
            );
            assert_eq!(arena.lookup(projection).map(|v| v.flags), Some(0));
            arena.rollback(after_original);
            assert!(arena.lookup(projection).is_none());
            assert_eq!(arena.lookup(original).map(|v| v.data.len()), Some(256));
            let again = arena.project(original, 0, 1).unwrap_or(Handle::EMPTY);
            assert_ne!(projection, again);
            arena.rollback(before);
            assert!(arena.lookup(original).is_none() && arena.lookup(again).is_none());
            let reused = arena.alloc(Kind::IntFcn, 0, 1, 9, 9, &[Handle::FALSE; 256]);
            assert_ne!(original, reused);
            assert!(arena.lookup(again).is_none());
            assert!(!arena.stale());
        }
    }
}