moving_gc_arena 0.3.2

Lightweight Garbage-collectable regions using indices and explicit roots
Documentation 
/*
 * @Copyright 2020 Jason Carr
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 */

#![doc(html_root_url = "https://docs.rs/moving_gc_arena/0.3.2")]
#![no_std]

#[allow(unused_imports)]
#[macro_use] // vec! in tests
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
    }

    /**
     * Get an identifier for this index.
     * It is unique amongst indices in this region,
     * so long as they have not been invalidated.
     *
     * Like the index itself, uniqueness is only
     * guaranteed as long as the index has not been
     * invalidated.
     */
    #[inline(always)]
    pub fn identifier(self) -> usize {
        self.ix
    }

    /**
     * If this crate has been compiled with support for validity checking,
     * this method will verify that an index is valid. In such cases,
     * a result of Ok indicates that this index points to a valid location
     * in the given region and has been updated.
     *
     * Otherwise, Ok will always be returned.
     */
    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(())
    }

    /**
     * Get the value pointd to by this index in its corresponding region.
     *
     * If the region is incorrect, the behavior of this function is
     * unspecified, and it may panic (but may also return a valid T reference).
     * Use try_get to avoid panics.
     */
    #[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> {
    /**
     * Gets the value at this location, when
     * passed the correct region. As with Ix,
     * the behavior when the region or location is
     * unspecified (but is still safe).
     */
    #[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()
    }
    /**
     * Try to get a reference to this data, possibly returning an error.
     *
     * If the region is correct, then an error always indicates that the pointed-to
     * entry is no longer valid
     */
    #[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)?)
    }

    /**
     * Get the raw index pointed to this by weak.
     * This method will panic if ix is expired. Use
     * try_ix to handle failure
     */
    #[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> {
    // returns true if there are enough roots
    // for this to certainly be rooted already,
    // assuming that it's used twice, once for
    // the entry and once for the roots vec
    pub(crate) fn is_otherwise_rooted(&self) -> bool {
        // 3 because:
        // If we're rooted then we have
        // 1 inside the entry
        // 1 inside the roots list
        // at least 1 outside the region
        Rc::strong_count(&self.cell) >= 3
    }

    pub(crate) fn is_weaked(&self) -> bool {
        Rc::weak_count(&self.cell) >= 1
    }

    /**
     * Gets the value at this location, when
     * passed the correct region. As with Ix,
     * the behavior when the region or location is
     * unspecified (but is still safe).
     */
    #[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()
    }
    /**
     * Try to get a reference to this data, possibly returning an error.
     *
     * If the region is correct, then an error always indicates that the pointed-to
     * entry is no longer valid
     */
    #[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();

        // first is collected by now
        assert!(w1.try_get(&r).is_err());
        assert_eq!(e1_drop.get(), 1);

        // root and new version are both accessible
        assert!(w2.try_get(&r).is_ok());
        assert!(w3.try_get(&r).is_ok());

        // touch r
        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();

        //r1 should have stopped being root on drop
        assert!(w1.try_get(&r).is_err());
        assert_eq!(e1_drop.get(), 1);

        //r2 is still a root
        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()];

        //nothing changed with r4 and w5 during access
        assert!(r4.try_get(&r).is_ok());
        assert_eq!(e4_drop.get(), 0);
        assert!(w5.try_get(&r).is_ok());
        drop(r4);

        r.gc();

        //entries 1 and 2 are still good.
        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),
        });

        // entries 3, 4 and 5 should be collected
        // despite cycles
        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);
        // we'd blow up here, anwyay, but no double free
        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();

        // the new root for 1 is still valid
        assert!(r1.try_get(&r).is_ok());
        assert!(w1.try_get(&r).is_ok());
        // but the old location is gone
        assert!(w2.try_get(&r).is_err());
        assert!(r.len() == 1);
        drop(w1);

        // re-create root from ix,
        // dropping the old one
        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());

        // re-create weak from ix,
        // don't gc
        let i1 = r1.ix();
        drop(r1);
        let w1 = i1.weak(&r);

        // new weak is valid for live location
        assert!(w1.try_get(&r).is_ok());
        r.gc();
        // still weak on the location,
        assert!(w1.try_get(&r).is_err());

        // nothing allocated in r now
        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>();
        // Unfortunately we can't implement
        // std::error::Error until it's
        // available for no_std

        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 {
            // mostly for testing with miri
            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();

        // self loop for extra soundness testing
        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());

        // cause a GC for extra noise
        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));
        // we just made r2 -> 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);
        // ensure that there were no illegal clones of e1
        // e.g. a pointer copy
        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);
        // why not
        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();

        // make sure indices aren't aligned
        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);

        //TODO, maybe this should error
        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))] // performance
    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();
    }
}