lambda-ref-cat 0.1.0

//! Persistent heap of mutable cells.
//!
//! The heap is a [`BTreeMap`] from monotonically-allocated [`Address`]es to
//! [`Value`]s.  Every operation that conceptually mutates the heap (`alloc`,
//! `store`, `retain`) instead returns a new [`Heap`] value; the receiver is
//! left untouched.  No `Rc`, `Arc`, `RefCell`, `Cell`, or `Mutex` is used to
//! provide shared mutability.
//!
//! The trade-off is performance: each non-read operation clones the existing
//! cell map.  This is acceptable for a falsification spike and an explicit
//! mirror of the persistent-data-structure pattern that the user's no-
//! interior-mutability rule pushes the design toward.

use std::collections::{BTreeMap, BTreeSet};

use crate::value::Value;

/// An address of a cell on the heap.
///
/// Addresses are allocated monotonically and never reused, including across
/// garbage collections.  This keeps every previously-issued address either
/// resolvable to its surviving cell or detectable as dangling.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Address(usize);

impl Address {
    /// The underlying numeric address.
    #[must_use]
    pub fn value(&self) -> usize {
        self.0
    }
}

impl From<usize> for Address {
    fn from(value: usize) -> Self {
        Self(value)
    }
}

impl std::fmt::Display for Address {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "#{}", self.0)
    }
}

/// A persistent map of addresses to cell values.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Heap {
    cells: BTreeMap<Address, Value>,
    next: usize,
}

impl Heap {
    /// An empty heap with the address counter at zero.
    #[must_use]
    pub fn empty() -> Self {
        Self {
            cells: BTreeMap::new(),
            next: 0,
        }
    }

    /// The number of cells currently live in the heap.
    #[must_use]
    pub fn len(&self) -> usize {
        self.cells.len()
    }

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

    /// Whether the heap has a cell at `address`.
    #[must_use]
    pub fn contains(&self, address: Address) -> bool {
        self.cells.contains_key(&address)
    }

    /// All addresses currently live in the heap, in ascending order.
    pub fn addresses(&self) -> impl Iterator<Item = Address> + '_ {
        self.cells.keys().copied()
    }

    /// Allocate a fresh cell holding `value`, returning the resulting heap
    /// and the new cell's address.
    #[must_use]
    pub fn alloc(&self, value: Value) -> (Self, Address) {
        let addr = Address(self.next);
        let cells: BTreeMap<Address, Value> = self
            .cells
            .iter()
            .map(|(k, v)| (*k, v.clone()))
            .chain(std::iter::once((addr, value)))
            .collect();
        (
            Self {
                cells,
                next: self.next + 1,
            },
            addr,
        )
    }

    /// Read the value held at `address`, or `None` if the address is dangling.
    #[must_use]
    pub fn load(&self, address: Address) -> Option<&Value> {
        self.cells.get(&address)
    }

    /// Return a heap with the cell at `address` set to `value`, or `None` if
    /// the address is dangling.  Address counter is preserved.
    #[must_use]
    pub fn store(&self, address: Address, value: Value) -> Option<Self> {
        self.cells.contains_key(&address).then(|| {
            let cells: BTreeMap<Address, Value> = self
                .cells
                .iter()
                .filter(|(k, _)| **k != address)
                .map(|(k, v)| (*k, v.clone()))
                .chain(std::iter::once((address, value)))
                .collect();
            Self {
                cells,
                next: self.next,
            }
        })
    }

    /// Return a heap containing only cells whose addresses are in `live`.
    /// The next-address counter is preserved so the surviving addresses
    /// stay stable and no future address ever collides with a freed one.
    #[must_use]
    pub fn retain(&self, live: &BTreeSet<Address>) -> Self {
        let cells: BTreeMap<Address, Value> = self
            .cells
            .iter()
            .filter(|(k, _)| live.contains(k))
            .map(|(k, v)| (*k, v.clone()))
            .collect();
        Self {
            cells,
            next: self.next,
        }
    }
}

impl Default for Heap {
    fn default() -> Self {
        Self::empty()
    }
}

impl std::fmt::Display for Heap {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let entries = self
            .cells
            .iter()
            .map(|(k, v)| format!("{k} = {v}"))
            .collect::<Vec<_>>()
            .join(", ");
        write!(f, "[{entries}]")
    }
}