moving_gc_arena 0.3.2

/*
 * @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/.
 */

use alloc::{rc, rc::Rc};
use core::cell::Cell;
use core::fmt;
use core::marker::PhantomData;
mod has_ix;
pub use has_ix::HasIx;

/**
 * A raw index for a region, that should be used for internal edges.
 *
 * This index is invalidated by many operations. but locations which
 * have always been exposed exactly once by foreach_ix for each collection are
 * guaranteed to have an index which is valid.
 *
 * Furthermore, indices received from a Entry or Root/Weak are
 * valid when retrieved.
 *
 * An Ix is valid so long as no invalidating methods have been called.
 * Borrowing rules ensure several situations in which no invalidating method can be called:
 *  - An immutable reference to the region exists
 *  - A mutable or immutable reference to any element of this region exists, such as those
 *    acquired via Ix::get.
 *  - An Entry for this region exists.
 *
 * If an Ix is not valid for the given region, behavior is unspecified but safe,
 * A valid instance of T may be returned. Panics may occur with get and get_mut.
 * If the index is valid, then it still points to the expected object.
 */
#[repr(C)]
// repr(C) Needed for unsafe header
// Note that Ix<T> can pack any set of
// bits whatsoever
pub struct Ix<T> {
    pub(crate) ix: usize,
    pub(crate) _t: PhantomData<*mut T>,
    #[cfg(feature = "debug-arena")]
    pub(crate) nonce: u64,
    #[cfg(feature = "debug-arena")]
    pub(crate) generation: u64,
}
impl<T> fmt::Debug for Ix<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str("Ix(")?;
        self.ix.fmt(f)?;
        #[cfg(feature = "debug-arena")]
        {
            f.write_str("; ")?;
            self.nonce.fmt(f)?;
            f.write_str(", ")?;
            self.generation.fmt(f)?;
        }
        f.write_str(")")?;
        Ok(())
    }
}
impl<T> Clone for Ix<T> {
    fn clone(&self) -> Self {
        Ix {
            ix: self.ix,
            _t: PhantomData,
            #[cfg(feature = "debug-arena")]
            nonce: self.nonce,
            #[cfg(feature = "debug-arena")]
            generation: self.generation,
        }
    }
}
impl<T> Copy for Ix<T> {}
unsafe impl<T> Send for Ix<T> {}
unsafe impl<T> Sync for Ix<T> {}
impl<T> PartialEq for Ix<T> {
    fn eq(&self, other: &Ix<T>) -> bool {
        #[cfg(feature = "debug-arena")]
        {
            if self.nonce != other.nonce {
                panic!("GC: Tested equality for indices into two different regions");
            }
            if self.generation != other.generation {
                panic!("GC: Tested equality for indices in two different generations");
            }
        }

        self.ix == other.ix
    }
}
/**
 * If indices are in different regions or different generations,
 * then behavior is unspecified: this may return true, false,
 * or panic, obeying symmetry and transitivity.
 *
 * In practice, it will panic if and only if
 * the "debug-arena" feature is active.
 */
impl<T> Eq for Ix<T> {}

pub(crate) type IxCell<T> = Cell<Ix<T>>;

pub enum SpotVariant<E, T> {
    Present(E),
    BrokenHeart(Ix<T>),
}

/**
 * A weak index into a region.
 *
 * This index will never prevent an
 * object from being collected, but
 * can be used to test if an object
 * has been collected, or access
 * it as normal.
 */
pub struct Weak<T> {
    pub(crate) cell: rc::Weak<IxCell<T>>,
}

impl<T> Clone for Weak<T> {
    fn clone(&self) -> Self {
        Weak {
            cell: self.cell.clone(),
        }
    }
}
impl<T> fmt::Debug for Weak<T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.write_str("Weak(")?;
        self.cell.upgrade().map(|c| c.get()).fmt(f)?;
        f.write_str(")")?;
        Ok(())
    }
}
impl<T> PartialEq for Weak<T> {
    fn eq(&self, other: &Weak<T>) -> bool {
        alloc::rc::Weak::ptr_eq(&self.cell, &other.cell)
    }
}
impl<T> Eq for Weak<T> {}

/**
 * An external rooted index into a region.
 *
 * Roots will always keep the objects they
 * point to live in the appropriate region.
 *
 * Roots should generally not be used within a region,
 * instead use [`Ix`](struct.Ix.html).
 * A root that is inside its own region will never
 * be collected and is vulnerable to the same issues
 * as Rc. Similarly, roots between two different regions
 * may cause uncollectable reference cycles.
 *
 * A root is always a valid pointer into its corresponding region, regardless of
 * the presence of any garbage collections.
 */
pub struct Root<T> {
    pub(crate) cell: Rc<IxCell<T>>,
}
impl<T> Clone for Root<T> {
    fn clone(&self) -> Self {
        Root {
            cell: self.cell.clone(),
        }
    }
}
impl<T> fmt::Debug for Root<T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.write_str("Root(")?;
        self.cell.get().fmt(f)?;
        f.write_str(")")?;
        Ok(())
    }
}
impl<T> PartialEq for Root<T> {
    fn eq(&self, other: &Root<T>) -> bool {
        alloc::rc::Rc::ptr_eq(&self.cell, &other.cell)
    }
}
impl<T> Eq for Root<T> {}

#[derive(Debug, PartialEq, Eq)]
#[allow(unused)]
/**
 * Type of region access errors.
 *
 * This does not implement std::Error,
 * which is not available for a no_std crate
 */
pub enum Error {
    /**
     * Incorrect usage resulted in an error,
     * but the system does not have enough data
     * to determine exactly what the error was.
     *
     * Enabling the feature "debug-arena" will
     * allow the library to have appropriate data
     * in most cases, with high costs to space usage.
     */
    Indeterminable,
    /**
     * This index has been used with a region for
     * which it was not created.
     */
    IncorrectRegion,
    /**
     * This index has been invalidated by a garbage
     * collection.
     */
    EntryExpired,
    /**
     * This library is in an unexpected internal state.
     *
     * The only way that this is expected to occur for
     * user code is in the case of a non-compliant
     * function for deep cloning methods, which rely
     * on complex invariants to return to a normal
     * region state.
     */
    UnexpectedInternalState,
}

impl fmt::Display for Error {
    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
        match self {
            Error::Indeterminable => write!(f, "Invalid index"),
            Error::IncorrectRegion => write!(f, "Incorrect region for index"),
            Error::EntryExpired => write!(f, "Index expired"),
            Error::UnexpectedInternalState => write!(f, "Region has invalid internal state"),
        }
    }
}