#![doc(html_root_url = "https://docs.rs/moving_gc_arena/0.3.3")]
#![no_std]
#[allow(unused_imports)]
#[macro_use]
extern crate alloc;
mod entry;
#[cfg(feature = "debug-arena")]
mod nonce;
mod region;
mod types;
use alloc::{rc, rc::Rc};
use core::marker::PhantomData;
pub use region::{traverse, Entry, Region};
pub use types::{Error, HasIx, Ix, Root, Weak};
impl<T> Ix<T> {
pub(crate) fn new(
ix: usize,
#[cfg(feature = "debug-arena")] nonce: u64,
#[cfg(feature = "debug-arena")] generation: u64,
) -> Self {
Ix {
ix,
_t: PhantomData,
#[cfg(feature = "debug-arena")]
nonce,
#[cfg(feature = "debug-arena")]
generation,
}
}
#[inline(always)]
pub(crate) fn ix(self) -> usize {
self.ix
}
#[inline(always)]
pub fn identifier(self) -> usize {
self.ix
}
pub fn check_region(self, region: &Region<T>) -> Result<(), Error> {
region.check_ix(self)
}
#[cfg(feature = "debug-arena")]
pub(crate) fn check_nonce(self, nonce: (u64, u64)) -> Result<(), Error> {
{
if self.nonce != nonce.0 {
return Err(Error::IncorrectRegion);
} else if self.generation < nonce.1 {
return Err(Error::EntryExpired);
} else if self.generation > nonce.1 {
return Err(Error::UnexpectedInternalState);
}
}
Ok(())
}
#[inline]
pub fn get(self, region: &Region<T>) -> &T {
self.try_get(region).expect("Ix::get")
}
#[inline]
pub fn get_mut(self, region: &mut Region<T>) -> &mut T {
self.try_get_mut(region).expect("Ix::get_mut")
}
#[inline]
pub fn try_get(self, region: &Region<T>) -> Result<&T, Error> {
region.try_get(self)
}
#[inline]
pub fn try_get_mut(self, region: &mut Region<T>) -> Result<&mut T, Error> {
region.try_get_mut(self)
}
#[inline]
pub fn weak(self, region: &Region<T>) -> Weak<T> {
self.try_weak(region).unwrap()
}
#[inline]
pub fn try_weak(self, region: &Region<T>) -> Result<Weak<T>, Error> {
region.weak(self)
}
#[inline]
pub fn root(self, region: &Region<T>) -> Root<T> {
self.try_root(region).unwrap()
}
#[inline]
pub fn try_root(self, region: &Region<T>) -> Result<Root<T>, Error> {
region.root(self)
}
}
impl<T> Weak<T> {
#[inline]
pub fn get<'a>(&self, r: &'a Region<T>) -> &'a T {
self.try_get(r).unwrap()
}
#[inline]
pub fn get_mut<'a>(&self, r: &'a mut Region<T>) -> &'a mut T {
self.try_get_mut(r).unwrap()
}
#[inline]
pub fn try_get<'a>(&self, r: &'a Region<T>) -> Result<&'a T, Error> {
Ok(self.try_ix()?.try_get(r)?)
}
#[inline]
pub fn try_get_mut<'a>(&self, r: &'a mut Region<T>) -> Result<&'a mut T, Error> {
Ok(self.try_ix()?.try_get_mut(r)?)
}
#[inline(always)]
pub fn ix(&self) -> Ix<T> {
self.try_ix().unwrap()
}
#[inline(always)]
pub fn try_ix(&self) -> Result<Ix<T>, Error> {
Ok(self.cell.upgrade().ok_or(Error::EntryExpired)?.get())
}
#[inline(always)]
pub fn root(&self, region: &Region<T>) -> Root<T> {
self.try_root(region).unwrap()
}
#[inline(always)]
pub fn try_root(&self, region: &Region<T>) -> Result<Root<T>, Error> {
region.root(self.try_ix()?)
}
}
impl<T> Root<T> {
pub(crate) fn is_otherwise_rooted(&self) -> bool {
Rc::strong_count(&self.cell) >= 3
}
pub(crate) fn is_weaked(&self) -> bool {
Rc::weak_count(&self.cell) >= 1
}
#[inline]
pub fn get<'a>(&self, r: &'a Region<T>) -> &'a T {
self.try_get(r).unwrap()
}
#[inline]
pub fn get_mut<'a>(&self, r: &'a mut Region<T>) -> &'a mut T {
self.try_get_mut(r).unwrap()
}
#[inline]
pub fn try_get<'a>(&self, r: &'a Region<T>) -> Result<&'a T, Error> {
self.ix().try_get(&r)
}
#[inline]
pub fn try_get_mut<'a>(&self, r: &'a mut Region<T>) -> Result<&'a mut T, Error> {
self.ix().try_get_mut(r)
}
#[inline(always)]
pub fn ix(&self) -> Ix<T> {
self.cell.get()
}
#[inline]
pub fn weak(&self) -> Weak<T> {
Weak {
cell: rc::Rc::downgrade(&self.cell),
}
}
}
#[cfg(test)]
mod tests {
use super::{traverse, Entry, HasIx, Ix, Region, Root};
use alloc::rc::Rc;
use alloc::vec::Vec;
use core::cell::Cell;
use core::mem::drop;
#[derive(Debug)]
struct Elem {
ix: Vec<Ix<Elem>>,
blob: usize,
dropped: Option<Rc<Cell<usize>>>,
}
impl Elem {
pub fn new() -> Self {
Self::with(vec![])
}
pub fn with(ix: Vec<Ix<Elem>>) -> Self {
Elem {
ix,
blob: 0,
dropped: None::<Rc<Cell<usize>>>,
}
}
pub fn track(&mut self) -> Rc<Cell<usize>> {
let rc = Rc::new(Cell::new(0usize));
self.dropped = Some(rc.clone());
rc
}
}
impl HasIx<Elem> for Elem {
fn foreach_ix<'b, 'a: 'b, F>(&'a mut self, f: F)
where
F: FnMut(&'b mut Ix<Elem>),
{
self.ix.iter_mut().for_each(f)
}
}
impl Default for Elem {
fn default() -> Self {
Self::new()
}
}
impl Clone for Elem {
fn clone(&self) -> Self {
Elem {
ix: self.ix.clone(),
blob: self.blob,
dropped: match self.dropped {
None => None,
Some(_) => Some(Rc::new(Cell::new(0usize))),
},
}
}
}
impl Drop for Elem {
fn drop(&mut self) {
if let Some(d) = &self.dropped {
d.set(d.get() + 1)
}
}
}
#[test]
pub fn weaks_are_weak() {
let mut r = Region::new();
let w1 = r.alloc(|_| Elem::new()).weak();
let e1_drop = w1.get_mut(&mut r).track();
let e2 = r.alloc(|_| Elem::new());
let w2 = e2.weak();
let r2 = e2.root();
r.gc();
let w3 = r.alloc(|_| Elem::new()).weak();
assert!(w1.try_get(&r).is_err());
assert_eq!(e1_drop.get(), 1);
assert!(w2.try_get(&r).is_ok());
assert!(w3.try_get(&r).is_ok());
drop(r2);
}
#[test]
pub fn roots_are_root() {
let mut r = Region::new();
let mut e1 = r.alloc(|_| Elem::new());
let e1_drop = e1.get_mut().track();
let w1 = e1.weak();
let r1 = e1.root();
let r2 = r.alloc(|_| Elem::new()).root();
drop(r1);
r.gc();
assert!(w1.try_get(&r).is_err());
assert_eq!(e1_drop.get(), 1);
assert!(r2.try_get(&r).is_ok());
}
#[test]
pub fn indirect_correct() {
let mut r = Region::new();
let e1 = r.alloc(|_| Elem::new());
let w1 = e1.weak();
let r1 = e1.root();
let r2 = r.alloc(|_| Elem::with(vec![r1.ix()])).root();
drop(r1);
let mut e3 = r.alloc(|_| Elem::new());
e3.get_mut().ix = vec![e3.ix()];
let w3 = e3.weak();
let e3_drop = e3.get_mut().track();
let r4 = r.alloc(|_| Elem::new()).root();
let e4_drop = r4.get_mut(&mut r).track();
let w5 = r.alloc(|_| Elem::new()).weak();
let e5_drop = w5.get_mut(&mut r).track();
r4.get_mut(&mut r).ix = vec![w5.ix()];
w5.get_mut(&mut r).ix = vec![r4.ix()];
assert!(r4.try_get(&r).is_ok());
assert_eq!(e4_drop.get(), 0);
assert!(w5.try_get(&r).is_ok());
drop(r4);
r.gc();
assert!(match w1.try_get(&r) {
Ok(Elem { ix: s, .. }) => s.is_empty(),
x => panic!("{:?}", x),
});
assert!(match r2.try_get(&r) {
Ok(Elem { ix: s, .. }) => !s.is_empty(),
x => panic!("{:?}", x),
});
assert_eq!(e3_drop.get(), 1);
assert_eq!(e4_drop.get(), 1);
assert_eq!(e5_drop.get(), 1);
assert!(w3.try_get(&r).is_err());
assert!(w5.try_get(&r).is_err());
drop(r);
assert_eq!(e3_drop.get(), 1);
assert_eq!(e4_drop.get(), 1);
assert_eq!(e5_drop.get(), 1);
}
#[test]
pub fn upgrades_well_behaved() {
let mut r = Region::new();
let e1 = r.alloc(|_| Elem::new());
let r1 = e1.root();
let w1 = e1.weak();
let r2 = r.alloc(|_| Elem::with(vec![r1.ix()])).root();
let w2 = r2.weak();
drop(r1);
r.gc();
let r1 = r2.get(&r).ix[0].root(&r);
drop(r2);
r.gc();
assert!(r1.try_get(&r).is_ok());
assert!(w1.try_get(&r).is_ok());
assert!(w2.try_get(&r).is_err());
assert!(r.len() == 1);
drop(w1);
let r1_ = r1.ix().root(&r);
drop(r1);
let r1 = r1_;
r.gc();
let w1 = r1.ix().weak(&r);
assert!(w1.try_get(&r).is_ok());
let i1 = r1.ix();
drop(r1);
let w1 = i1.weak(&r);
assert!(w1.try_get(&r).is_ok());
r.gc();
assert!(w1.try_get(&r).is_err());
assert!(r.is_empty());
}
#[test]
pub fn check_impls() {
struct Anything;
#[derive(Debug)]
struct Debugged;
use crate::region::{Entry, Region};
use crate::types::{Error, Ix, Root, Weak};
use core::fmt::{Debug, Display};
fn is_send<T: Send>() {}
fn is_sync<T: Sync>() {}
fn is_debug<T: Debug>() {}
fn is_display<T: Display>() {}
fn is_eq<T: Eq>() {}
is_send::<Error>();
is_sync::<Error>();
is_debug::<Error>();
is_display::<Error>();
is_debug::<Root<Anything>>();
is_debug::<Weak<Anything>>();
is_debug::<Ix<Anything>>();
is_debug::<Region<Debugged>>();
is_debug::<Entry<Debugged>>();
is_eq::<Ix<Anything>>();
is_eq::<Weak<Anything>>();
is_eq::<Root<Anything>>();
is_send::<Ix<Anything>>();
is_sync::<Ix<Anything>>();
}
#[cfg(all(feature = "packed-headers", not(feature = "debug-arena")))]
#[test]
pub fn header_ix_layout_same() {
use crate::entry::Spot;
use alloc::alloc::Layout;
assert!(Layout::new::<Ix<()>>() == Layout::new::<Spot<()>>());
let mut ix: Ix<()> = Ix::new(0);
let ix2 = ix;
unsafe {
let mut s = Spot::new(());
core::mem::swap(s.header_as_ix(), &mut ix);
core::mem::swap(s.header_as_ix(), &mut ix);
assert!(ix.identifier() == ix2.identifier());
}
}
fn make_triangle(r: &mut Region<Elem>) -> [Root<Elem>; 3] {
let r1 = r.alloc(|_| Default::default()).root();
let r2 = r.alloc(|_| Default::default()).root();
let r3 = r.alloc(|_| Default::default()).root();
r1.get_mut(r).ix.push(r2.ix());
r2.get_mut(r).ix.push(r3.ix());
r3.get_mut(r).ix.push(r1.ix());
[r1, r2, r3]
}
fn component_size(r: &mut Region<Elem>, start: Root<Elem>) -> usize {
let mut c = 0;
r.traverse(traverse::CallStack, &[start.ix()], |_| c += 1, |_| {});
c
}
#[test]
pub fn traverse_sound() {
let mut r = Region::new();
let r1 = make_triangle(&mut r)[0].clone();
let r2 = make_triangle(&mut r)[0].clone();
r1.get_mut(&mut r).ix.push(r1.ix());
let r3 = r.alloc(|_| Elem::with(vec![r1.ix(), r2.ix()])).root();
assert_eq!(component_size(&mut r, r1.clone()), 3);
assert_eq!(component_size(&mut r, r3.clone()), 7);
assert_eq!(component_size(&mut r, r2.clone()), 3);
r2.get_mut(&mut r).ix.push(r3.ix());
let rs = make_triangle(&mut r);
core::mem::drop(rs);
r.gc();
assert!(3 == component_size(&mut r, r1));
assert!(7 == component_size(&mut r, r3));
assert!(7 == component_size(&mut r, r2));
}
#[test]
pub fn traverse_pre_post() {
let mut r = Region::new();
let r1 = make_triangle(&mut r)[0].clone();
r.traverse(traverse::CallStack, &[r1.ix()],
|mut e| e.get_mut().blob += 1,
|mut e| e.get_mut().blob *= 2);
assert_eq!(component_size(&mut r, r1.clone()), 3);
r.traverse(traverse::CallStack, &[r1.ix()],
|e| assert_eq!(e.get().blob, 2),
|_| {});
}
#[test]
pub fn deep_clone_sound() {
let mut r = Region::new();
let rt1 = make_triangle(&mut r)[0].clone();
let w1 = rt1.weak();
let e1_drop = rt1.get_mut(&mut r).track();
r.ensure(40);
let rt2 = r.deep_clone(rt1.clone());
assert!(rt1 != rt2);
assert!(rt1.ix() != rt2.ix());
assert!(3 == component_size(&mut r, rt1.clone()));
assert!(3 == component_size(&mut r, rt2.clone()));
let rt3 = r.alloc(|_| Elem::with(vec![rt1.ix(), rt2.ix()])).root();
assert!(7 == component_size(&mut r, rt3.clone()));
let rt4 = r.deep_clone(rt3.clone());
assert_eq!(component_size(&mut r, rt1.clone()), 3);
assert_eq!(component_size(&mut r, rt2.clone()), 3);
assert_eq!(component_size(&mut r, rt4.clone()), 7);
assert_eq!(rt1.weak(), w1);
assert_eq!(e1_drop.get(), 0);
drop(rt3);
drop(rt4);
drop(rt1);
r.gc();
assert_eq!(e1_drop.get(), 1);
drop(r);
assert_eq!(e1_drop.get(), 1);
}
#[test]
pub fn dfs_diamond() {
let mut r = Region::new();
let rt0 = {
let rt3 = r.alloc(|_| Elem::new()).root();
let rt2 = r.alloc(|_| Elem::with(vec![rt3.ix()])).root();
let rt1 = r.alloc(|_| Elem::with(vec![rt3.ix()])).root();
r.alloc(|_| Elem::with(vec![rt1.ix(), rt2.ix()])).root()
};
assert_eq!(component_size(&mut r, rt0.clone()), 4);
r.gc();
assert_eq!(component_size(&mut r, rt0.clone()), 4);
}
#[test]
pub fn deep_clone_into_with() {
let mut r1 = Region::new();
let mut r2 = Region::new();
let _ = r1.alloc(|_| Elem::new()).root();
let rt1 = make_triangle(&mut r1)[0].clone();
let w1 = rt1.weak();
let mut rt2 = rt1.clone();
let rt3 = rt1.clone();
let rt2 = r1.deep_clone_into_with(&mut r2, rt2, |mut e| {
let t = e.get_mut();
t.blob = 2;
let mut t2: Elem = t.clone();
t2.blob = 3;
t2
});
assert_eq!(component_size(&mut r1, rt1.clone()), 3);
assert_eq!(component_size(&mut r2, rt2.clone()), 3);
r1.traverse(
traverse::CallStack,
&[rt1.ix()],
|mut e| {
assert_eq!(e.get_mut().blob, 2);
},
|_| {},
);
r2.traverse(
traverse::CallStack,
&[rt2.ix()],
|mut e| {
assert_eq!(e.get_mut().blob, 3);
},
|_| {},
);
assert_eq!(rt1.weak(), w1);
assert_eq!(rt1, rt3);
}
#[cfg(feature = "debug-arena")]
#[test]
pub fn check_nonce() {
use crate::types::Error;
let i = Ix::<()>::new(0, 3, 4);
assert_eq!(i.check_nonce((2, 1)), Err(Error::IncorrectRegion));
assert_eq!(i.check_nonce((3, 3)), Err(Error::UnexpectedInternalState));
assert_eq!(i.check_nonce((3, 5)), Err(Error::EntryExpired));
}
#[cfg(feature = "debug-arena")]
#[test]
#[should_panic]
pub fn dfs_checks_nonce() {
let mut r = Region::new();
let rt0 = r.alloc(|_| Elem::new()).root();
let i0 = rt0.ix();
assert_eq!(component_size(&mut r, rt0.clone()), 1);
let i = Ix::<Elem>::new(i0.ix(), r.nonce, r.generation - 1);
let rt = i.root(&r);
extern crate std;
use std::panic::{catch_unwind, AssertUnwindSafe};
let result = catch_unwind(AssertUnwindSafe(move || component_size(&mut r, rt)));
assert!(result.is_err());
}
#[test]
pub fn weak_to_root() {
let mut r = Region::new();
let w0 = r.alloc(|_| Elem::new()).weak();
let rt0 = w0.root(&r);
r.gc();
assert!(rt0.try_get(&r).is_ok());
}
#[test]
pub fn ix_to_root() {
let mut r = Region::new();
let i0 = r.alloc(|_| Elem::new()).ix();
let rt0 = i0.root(&r);
r.gc();
assert!(rt0.try_get(&r).is_ok());
}
#[test]
pub fn root_weak_roundtrip() {
let mut r = Region::new();
let rt0 = r.alloc(|_| Elem::new()).root();
r.gc();
assert_eq!(rt0.weak().root(&r), rt0);
}
#[test]
pub fn root_ix_roundtrip() {
let mut r = Region::new();
let rt0 = r.alloc(|_| Elem::new()).root();
r.gc();
assert_eq!(rt0.ix().root(&r), rt0);
}
#[test]
pub fn weak_ix_roundtrip() {
let mut r = Region::new();
let w0 = r.alloc(|_| Elem::new()).weak();
assert_eq!(w0.ix().weak(&r), w0);
}
#[test]
pub fn entry_ix_weak_commute() {
let mut r = Region::new();
let e0 = r.alloc(|_| Elem::new());
assert_eq!(e0.weak(), e0.ix().weak(&r));
}
#[test]
#[cfg(not(miri))]
pub fn simple_strategy() {
#[derive(Clone, Copy, PartialEq, Eq, Default)]
struct LList {
next: Option<Ix<LList>>,
value: u64,
}
impl HasIx<LList> for LList {
fn foreach_ix<'b, 'a: 'b, F>(&'a mut self, f: F)
where
F: FnMut(&'b mut Ix<LList>),
{
self.next.iter_mut().for_each(f)
}
}
#[derive(Clone, Copy, PartialEq, Eq)]
struct Strategy;
impl traverse::Strategy<LList, traverse::PreOnly> for Strategy {
fn run<'a, F, V>(&self, next: &mut F, visitor: &mut V, start: Entry<LList>)
where
F: FnMut(Ix<LList>) -> Option<Entry<'a, LList>>,
V: traverse::Visitor<LList, traverse::PreOnly>,
{
let mut handle = |mut s: Entry<LList>| -> Option<(Entry<LList>)> {
visitor.visit(traverse::PreOnly::Pre, s.reborrow());
let ix2 = s.get().next?;
next(ix2)
};
let mut s = start;
while let Some(s2) = handle(s) {
s = s2;
}
}
}
let expected_length = 100000;
let mut r = Region::new();
let mut rt = r.alloc(|_| Default::default()).root();
for i in 1..expected_length {
rt = r
.alloc(|_| LList {
next: Some(rt.ix()),
value: i,
})
.root();
}
let mut c = 0;
let visitor = traverse::PrePostVisitor {pre: |_: Entry<'_, _>| c += 1, post: ()};
r.traverse_with(Strategy, &[rt.ix()], visitor);
assert_eq!(c, expected_length);
let i2 = rt.get(&r).next.unwrap().get(&r).next.unwrap();
let mut c = 0;
let visitor = traverse::PrePostVisitor {pre: |_: Entry<'_, _>| c += 1, post: ()};
r.traverse_with(Strategy, &[i2, rt.ix()], visitor);
assert_eq!(c, expected_length);
}
#[test]
pub fn non_static_strategy() {
struct Strategy<'a>(&'a u64);
impl <'a, T: HasIx<T> + 'static> traverse::Strategy<T, traverse::PreOnly> for Strategy<'a> {
fn run<'e, F, V>(&self, get_next: &mut F, visitor: &mut V, mut next: Entry<T>)
where
F: FnMut(Ix<T>) -> Option<Entry<'e, T>>,
V: traverse::Visitor<T, traverse::PreOnly>,
{
visitor.visit(traverse::PreOnly::Pre, next.reborrow());
next.get_mut().foreach_ix(|ix| {
if let Some(next) = get_next(*ix) {
self.run(get_next, visitor, next);
}
});
}
}
impl <'a, T: HasIx<T> + 'static> traverse::Strategy<T, traverse::PreAndPost> for Strategy<'a> {
fn run<'e, F, V>(&self, get_next: &mut F, visitor: &mut V, mut next: Entry<T>)
where
F: FnMut(Ix<T>) -> Option<Entry<'e, T>>,
V: traverse::Visitor<T, traverse::PreAndPost>,
{
visitor.visit(traverse::PreAndPost::Pre, next.reborrow());
next.get_mut().foreach_ix(|ix| {
if let Some(next) = get_next(*ix) {
self.run(get_next, visitor, next);
}
});
visitor.visit(traverse::PreAndPost::Post, next.reborrow());
}
}
let mut r = Region::new();
let rt = r.alloc(|_| ()).root();
let mut i = 0;
r.traverse(Strategy(&i), &[rt.ix()], |_| {}, |_| {});
}
#[test]
#[should_panic]
pub fn invalid_ix_in_gc() {
let mut r = Region::new();
let obj = r.alloc(|_| Elem::new()).root();
let ix2 = r.alloc(|_| Elem::new()).ix();
r.gc();
obj.get_mut(&mut r).ix.push(ix2);
r.gc();
}
#[test]
#[cfg(not(feature = "debug-arena"))]
pub fn print_external_references() {
let mut r = Region::new();
let obj = r.alloc(|_| Elem::new()).root();
assert_eq!(
format!("{:?}", obj.ix()),
format!("{:?}", obj).replace("Root", "Ix"));
assert_eq!(
format!("{:?}", obj.ix()),
format!("{:?}", obj.weak()).replace("Weak", "Ix"));
let w = r.alloc(|_| Elem::new()).weak();
r.gc();
assert_eq!("Weak(None)", format!("{:?}", w));
}
}