use crate::handle::Handle;
use crate::node::{Kind, View};
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,
}
#[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,
pub(crate) interned: Vec<Handle>,
stale: std::cell::Cell<bool>,
peak_nodes: usize,
peak_pool: usize,
resets: u64,
rollbacks: u64,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Mark {
resets: u64,
nodes: usize,
pool: usize,
boxed: usize,
}
impl Arena {
#[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;
}
}
#[must_use]
pub fn mark(&self) -> Mark {
Mark {
resets: self.resets,
nodes: self.nodes.len(),
pool: self.pool.len(),
boxed: self.boxed.len(),
}
}
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();
}
#[must_use]
pub fn rollbacks(&self) -> u64 {
self.rollbacks
}
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();
}
#[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>()
}
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)
}
#[must_use]
pub fn epoch(&self) -> u32 {
self.epoch
}
#[must_use]
pub fn stale(&self) -> bool {
self.stale.get()
}
#[must_use]
pub fn len(&self) -> usize {
self.nodes.len()
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.nodes.is_empty()
}
#[must_use]
pub fn peak(&self) -> (usize, usize) {
(
self.peak_nodes.max(self.nodes.len()),
self.peak_pool.max(self.pool.len()),
)
}
#[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)
}
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))
}
#[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,
})
}
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)
}
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");
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());
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);
let e = a.epoch();
let m = a.mark();
a.rollback(m);
assert_eq!(a.epoch(), e);
assert!(!a.stale());
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());
}
}
}