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 super::super::region::traverse;
use alloc::rc;
use alloc::rc::Rc;
use core::cell::{Cell, RefCell};
use core::fmt::{Debug, Formatter};

use crate::types::{Ix, IxCell, Root, SpotVariant, Weak};

/**
 * Entry which contains a valid instance of T
 * with full header.
 *
 * It implements traverse::Entry
 */
pub struct PresentData<T> {
    rc: RefCell<Option<Root<T>>>,
    t: T,
}
impl<T> PresentData<T> {
    // NOTE: SAFETY requires that this be single-threaded
    // We can't afford RefCell due to the extra overhead
    pub(crate) fn get_cell(&self, ix: Ix<T>) -> Root<T> {
        let x = self.rc.borrow();
        match *x {
            Some(ref rc) => rc.clone(),
            None => {
                //early drop for RefCell
                core::mem::drop(x);
                let rc = Root {
                    cell: Rc::new(Cell::new(ix)),
                };
                *self.rc.borrow_mut() = Some(rc.clone());
                rc
            }
        }
    }

    pub(crate) fn weak(&self, ix: Ix<T>) -> Weak<T> {
        let r = self.get_cell(ix);
        debug_assert!(rc::Rc::strong_count(&r.cell) >= 2);
        r.weak()
    }

    // Upgrade this entry to a root.
    // Doesn't push the root onto the roots list.
    // We'll need to use strong_count to do so
    pub(crate) fn root(&self, ix: Ix<T>) -> Root<T> {
        let r = self.get_cell(ix);
        debug_assert!(rc::Rc::strong_count(&r.cell) >= 2);
        r
    }

    #[inline(always)]
    pub fn get(&self) -> &T {
        &self.t
    }
    #[inline(always)]
    pub fn get_mut(&mut self) -> &mut T {
        &mut self.t
    }

    pub(crate) fn move_to(&mut self, other: Ix<T>) {
        self.check_clear_rc();
        if let Some(ref mut rc) = &mut *self.rc.borrow_mut() {
            rc.cell.set(other)
        }
    }

    pub(crate) fn check_clear_rc(&mut self) {
        let x = self.rc.borrow();
        if let Some(ref root) = *x {
            if !root.is_otherwise_rooted() && !root.is_weaked() {
                // early drop for RefCell
                core::mem::drop(x);
                *self.rc.borrow_mut() = None;
            }
        }
    }

    pub(crate) fn new(t: T) -> Self {
        PresentData {
            t,
            rc: RefCell::new(None),
        }
    }

    pub(crate) fn into_t(self) -> T {
        self.t
    }

    fn swap_header(&mut self, other: &mut Self) {
        core::mem::swap(&mut self.rc, &mut other.rc)
    }

    #[inline(always)]
    pub(crate) fn reborrow(&mut self) -> MutPresent<T> {
        self
    }
}

pub(crate) enum Spot<T> {
    Present(bool, PresentData<T>),
    BrokenHeart(Ix<T>, Option<T>),
}
impl<T> core::fmt::Debug for Spot<T> {
    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
        match self {
            Self::Present(m, d) => write!(f, "Present({:?}, _)", m),
            Self::BrokenHeart(ix, d) => write!(f, "BrokenHeart({:?}, _)", ix),
        }
    }
}

impl<T> Spot<T> {
    pub(crate) fn new(t: T) -> Self {
        Spot::Present(false, PresentData::new(t))
    }

    pub(crate) fn variant(&mut self) -> SpotVariant<MutPresent<T>, T> {
        match self {
            Spot::Present(_, e) => SpotVariant::Present(e),
            Spot::BrokenHeart(i, _) => SpotVariant::BrokenHeart(*i),
        }
    }

    pub(crate) fn get(&self) -> Option<Present<T>> {
        match self {
            Spot::Present(_, e) => Some(e),
            _ => None,
        }
    }

    pub(crate) fn get_mut(&mut self) -> Option<MutPresent<T>> {
        match self {
            Spot::Present(_, e) => Some(e),
            _ => None,
        }
    }

    pub(crate) fn forward(&mut self, dest: Ix<T>) -> Spot<T> {
        // FIXME
        core::mem::replace(self, Spot::BrokenHeart(dest, None))
    }

    pub(crate) fn forward_keep(&mut self, dest: Ix<T>) -> Option<Root<T>> {
        match core::mem::replace(self, Spot::BrokenHeart(dest, None)) {
            Spot::Present(_, e) => match self {
                Spot::BrokenHeart(_, ref mut t) => {
                    *t = Some(e.t);
                    e.rc.into_inner()
                }
                _ => unreachable!(),
            },
            _ => None,
        }
    }

    pub(crate) fn recover_kept(&mut self, mark: bool, dest_header: MutPresent<T>) {
        match self {
            Spot::BrokenHeart(_, t) => {
                let t = t.take();
                *self = Spot::Present(mark, PresentData::new(t.unwrap()));
                match self {
                    Spot::Present(_, ref mut e) => e.swap_header(dest_header),
                    _ => unreachable!(),
                }
            }
            _ => unreachable!("GC Internal error: Invalid state for recover"),
        }
    }

    #[inline(always)]
    pub(crate) fn put(&mut self, mark: bool, t: T) {
        *self = Spot::Present(mark, PresentData::new(t));
    }

    #[allow(unused)]
    pub(crate) fn into_t(self) -> Option<T> {
        match self {
            Spot::Present(_, e) => Some(e.t),
            Spot::BrokenHeart(_, _) => None,
        }
    }
    // Change this into a broken heart to other,
    // updating the external reference
    #[allow(unused)]
    pub(crate) fn move_to(&mut self, other: Ix<T>) -> Spot<T> {
        let mut e0 = core::mem::replace(self, Spot::BrokenHeart(other, None));
        if let Spot::Present(_, ref mut e) = e0 {
            e.move_to(other);
        };
        e0
    }

    // Marking functions.
    //
    // Both of these use raw pointers so
    // that we don't have overlapping mutable borrows on
    // a particular spot (specifically, they would overlap
    // at the instance of T; we still need disjointness
    // of the header from T)
    //
    pub(crate) fn mark(&mut self, mark: bool) {
        if let Spot::Present(ref mut m, _) = *self {
            *m = mark;
        }
    }
    pub(crate) unsafe fn is_marked(this: *const Self) -> Option<bool> {
        if let Spot::Present(m, _) = *this {
            Some(m)
        } else {
            None
        }
    }
    pub(crate) unsafe fn is_forwarding(this: *const Self) -> Option<Ix<T>> {
        if let Spot::BrokenHeart(i, _) = *this {
            Some(i)
        } else {
            None
        }
    }

    pub(crate) fn process<F>(&mut self, ix: Ix<T>, mut f: F)
    where
        F: FnMut(Ix<T>, &mut T),
    {
        if let Spot::Present(_, e) = self {
            f(ix, e.get_mut())
        }
    }
    pub(crate) fn move_to_keep_with<C>(&mut self, other: Ix<T>, mut clone: C) -> Spot<T>
    where
        C: FnMut(MutPresent<T>) -> T,
    {
        let mut e0 = core::mem::replace(self, Spot::BrokenHeart(other, None));
        let (t0, mut e1) = (
            match &mut e0 {
                Spot::Present(_, e) => {
                    let t1 = clone(e);
                    core::mem::replace(e.get_mut(), t1)
                }
                _ => unreachable!(),
            },
            e0,
        );
        core::mem::replace(self, Spot::BrokenHeart(other, Some(t0)));
        e1
    }
}

impl<T: Clone> Spot<T> {
    pub(crate) fn move_to_keep(&mut self, other: Ix<T>) -> Spot<T> where {
        self.move_to_keep_with(other, |e| e.get().clone())
    }
}
pub struct Header<T> {
    rc: RefCell<Option<Root<T>>>,
}

pub type MutPresent<'a, T> = &'a mut PresentData<T>;
pub type Present<'a, T> = &'a PresentData<T>;