use crate::linear::proofs::{Node, NodeId};
use crate::linear::search::Reason;
use crate::linear::search::memory::{Account, Charged, bytes_of};
use std::sync::Mutex;
pub(crate) enum Kept<'a> {
Own(Vec<Node>),
#[cfg_attr(
not(feature = "parallel"),
expect(dead_code, reason = "only a pool shares its kept arena")
)]
Shared(&'a Mutex<Vec<Node>>),
}
pub(super) const PENDING: u32 = 1 << 31;
const ROOT_POLL: usize = 1 << 16;
pub(crate) struct Arena<'a> {
pub(super) kept: Kept<'a>,
pending: Vec<Node>,
held: Vec<NodeId>,
most: usize,
overflowed: bool,
pub(super) account: &'a Account,
own: Charged<'a>,
}
impl<'a> Arena<'a> {
pub(crate) fn new(kept: Kept<'a>, account: &'a Account) -> Self {
Self {
kept,
pending: Vec::new(),
held: Vec::new(),
most: PENDING as usize,
overflowed: false,
account,
own: Charged::new(account),
}
}
pub(super) fn push(&mut self, node: Node) -> NodeId {
if self.pending.len() >= self.most {
self.overflowed = true;
return NodeId::new(PENDING);
}
let id = NodeId::new(PENDING | self.pending.len() as u32);
let before = bytes_of(&self.pending);
self.pending.push(node);
if bytes_of(&self.pending) != before {
self.own.resize(before, bytes_of(&self.pending));
}
id
}
pub(super) fn mark(&self) -> usize {
self.pending.len()
}
pub(super) fn release(&mut self, mark: usize) {
self.pending.truncate(mark);
}
pub(super) fn hold(&mut self, node: NodeId) -> usize {
self.held.push(node);
self.held.len() - 1
}
pub(super) fn unhold(&mut self, point: usize) -> NodeId {
let node = self.held[point];
self.held.truncate(point);
node
}
pub(super) fn keep(&mut self, mark: usize, node: NodeId) -> Result<NodeId, Reason> {
if self.overflowed {
return Err(Reason::IndexLimit);
}
let (most, account) = (self.most, self.account);
match &mut self.kept {
Kept::Own(kept) => Self::append(kept, &mut self.pending, mark, node, most, account),
Kept::Shared(kept) => {
let mut kept = crate::linear::search::lock(kept);
Self::append(&mut kept, &mut self.pending, mark, node, most, account)
}
}
}
pub(super) fn keep_all(
&mut self,
node: NodeId,
stopped: &mut dyn FnMut() -> bool,
) -> Result<NodeId, Reason> {
let Kept::Own(kept) = &mut self.kept else {
return self.keep(0, node);
};
if self.overflowed || !kept.is_empty() {
return self.keep(0, node);
}
let pending = bytes_of(&self.pending);
std::mem::swap(kept, &mut self.pending);
self.own.resize(pending, 0);
self.account.resize(0, pending);
let renamed = |id: NodeId| NodeId::new(id.get() & !PENDING);
for (i, n) in kept.iter_mut().enumerate() {
if i % ROOT_POLL == 0 && stopped() {
return Err(Reason::Stopped);
}
*n = n.map_premises(renamed);
}
Ok(renamed(node))
}
fn append(
kept: &mut Vec<Node>,
pending: &mut Vec<Node>,
mark: usize,
node: NodeId,
most: usize,
account: &Account,
) -> Result<NodeId, Reason> {
let base = kept.len();
if base + (pending.len() - mark) > most {
return Err(Reason::IndexLimit);
}
let renamed = |id: NodeId| {
if id.get() & PENDING == 0 {
return id;
}
let index = (id.get() & !PENDING) as usize;
debug_assert!(index >= mark, "a pending node below the mark");
NodeId::new((base + index - mark) as u32)
};
let before = bytes_of(kept);
kept.extend(pending.drain(mark..).map(|n| n.map_premises(renamed)));
if bytes_of(kept) != before {
account.resize(before, bytes_of(kept));
}
Ok(renamed(node))
}
pub(super) fn collect(&mut self, root: Option<NodeId>, tight: bool) -> Option<NodeId> {
const DEAD: u32 = u32::MAX;
const LIVE: u32 = 0;
let Kept::Own(kept) = &mut self.kept else {
return root;
};
let before = bytes_of(kept);
let mut moved = vec![DEAD; kept.len()];
let is_kept = |id: &NodeId| id.get() & PENDING == 0;
for id in self
.pending
.iter()
.flat_map(|node| node.premises())
.chain(self.held.iter().copied())
.chain(root)
.filter(is_kept)
{
moved[id.index()] = LIVE;
}
for i in (0..kept.len()).rev() {
if moved[i] == LIVE {
for premise in kept[i].premises() {
moved[premise.index()] = LIVE;
}
}
}
let mut next = 0;
for i in 0..kept.len() {
if moved[i] == LIVE {
kept[next] = kept[i].map_premises(|p| NodeId::new(moved[p.index()]));
moved[i] = next as u32;
next += 1;
}
}
kept.truncate(next);
let renamed = |id: NodeId| {
if is_kept(&id) {
NodeId::new(moved[id.index()])
} else {
id
}
};
for node in &mut self.pending {
*node = node.map_premises(renamed);
}
for id in &mut self.held {
*id = renamed(*id);
}
let root = root.map(renamed);
if tight {
kept.shrink_to_fit();
} else if kept.capacity() > 4 * kept.len().max(1024) {
kept.shrink_to(2 * kept.len().max(1024));
}
self.account.resize(before, bytes_of(kept));
root
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::linear::occurrences::Member;
#[test]
fn arena() {
let o = Member::new;
let account = Account::new(None);
let mut arena = Arena::new(Kept::Own(Vec::new()), &account);
let ax = arena.push(Node::Ax(o(0), o(1)));
let mark = arena.mark();
let one = arena.push(Node::One(o(2)));
arena.push(Node::Tensor(o(3), ax, one));
arena.release(mark);
let top = arena.push(Node::Top(o(4)));
let top = arena.keep(mark, top).unwrap();
assert_eq!(top, NodeId::new(0));
let tensor = arena.push(Node::Tensor(o(5), ax, top));
let root = arena.keep(0, tensor).unwrap();
assert_eq!(root, NodeId::new(2));
let Kept::Own(kept) = arena.kept else {
unreachable!()
};
assert_eq!(
kept,
[
Node::Top(o(4)),
Node::Ax(o(0), o(1)),
Node::Tensor(o(5), NodeId::new(1), NodeId::new(0))
]
);
}
#[test]
fn collection() {
let o = Member::new;
let account = Account::new(None);
let mut arena = Arena::new(Kept::Own(Vec::new()), &account);
let kept = |arena: &mut Arena, node| {
let id = arena.push(node);
arena.keep(0, id).unwrap()
};
let dead = kept(&mut arena, Node::One(o(0)));
let below = kept(&mut arena, Node::Top(o(1)));
let held = kept(&mut arena, Node::Bot(o(2), below));
kept(&mut arena, Node::Bot(o(3), dead));
let rooted = kept(&mut arena, Node::One(o(4)));
let under = kept(&mut arena, Node::Top(o(5)));
let pending = arena.push(Node::Bot(o(6), under));
let point = arena.hold(held);
let before = account.used();
let rooted = arena.collect(Some(rooted), true).unwrap();
assert!(account.used() < before);
assert_eq!(arena.unhold(point), NodeId::new(1));
assert_eq!(rooted, NodeId::new(2));
let root = arena.keep(0, pending).unwrap();
assert_eq!(root, NodeId::new(4));
let Kept::Own(kept) = arena.kept else {
unreachable!()
};
assert_eq!(
kept,
[
Node::Top(o(1)),
Node::Bot(o(2), NodeId::new(0)),
Node::One(o(4)),
Node::Top(o(5)),
Node::Bot(o(6), NodeId::new(3))
]
);
}
#[test]
fn full_arena() {
let o = Member::new;
let account = Account::new(None);
let mut arena = Arena::new(Kept::Own(Vec::new()), &account);
arena.most = 2;
for id in 0..2 {
let node = arena.push(Node::One(o(id)));
assert!(arena.keep(0, node).is_ok());
}
let third = arena.push(Node::One(o(2)));
assert_eq!(arena.keep(0, third), Err(Reason::IndexLimit));
let mut arena = Arena::new(Kept::Own(Vec::new()), &account);
arena.most = 2;
let first = arena.push(Node::One(o(0)));
arena.push(Node::One(o(1)));
arena.push(Node::One(o(2)));
assert_eq!(arena.keep(0, first), Err(Reason::IndexLimit));
}
}