cycle_ptr 0.1.0

//! Edges for the object reachability graph.
use super::ControlBlock;
#[cfg(feature = "multi_thread")]
use super::MTControlBlock;
use crate::list::{ListElement, ListEntry};
use crate::util::NonNull;
use std::cell::UnsafeCell;
use std::fmt;
use std::pin::Pin;

/// Tag used by [List][crate::list::List], to permit linking the edges on a control-block.
pub(super) struct EdgeTag;

/// An edge represents the directed edges in the object reachability graph.
///
/// Each edge is formed by a member pointer, pointing from an origin object to a destination object.
/// During garbage collection, the garbage collector walks all the edges, to find all reachable objects.
pub(crate) struct Edge {
    /// Control-block of the object that the edge points at.
    #[cfg(not(feature = "multi_thread"))]
    destination: NonNull<ControlBlock>,
    /// Control-block of the object that the edge points at.
    /// In the multi-thread case, an edge can either point at a [ControlBlock] or an [MTControlBlock].
    /// Since we only use edges during garbage collection,
    /// and the garbage collector does not care about cross-generation objects,
    /// we only track the [ControlBlock] and don't care about the [MTControlBlock].
    #[cfg(feature = "multi_thread")]
    destination: Option<NonNull<ControlBlock>>,
    /// Allow edges to be linked onto a control block.
    link: UnsafeCell<ListEntry<Edge>>,
}

/// An edge represents the directed edges in the object reachability graph.
///
/// Each edge is formed by a member pointer, pointing from an origin object to a destination object.
/// During garbage collection, the garbage collector walks all the edges, to find all reachable objects.
#[cfg(feature = "multi_thread")]
pub(crate) struct MTEdge {
    /// Control-block of the object that the edge points at.
    destination: NonNull<MTControlBlock>,
    /// Allow edges to be linked onto a control block.
    link: UnsafeCell<ListEntry<MTEdge>>,
}

impl Edge {
    /// Create a new edge.
    #[inline]
    #[allow(
        clippy::missing_const_for_fn,
        reason = "Const context makes no sense, edges are always heap-allocated."
    )]
    pub(crate) fn new(cb: Pin<&ControlBlock>) -> Self {
        Edge {
            #[cfg(not(feature = "multi_thread"))]
            destination: NonNull::from_ref(cb.get_ref()),
            #[cfg(feature = "multi_thread")]
            destination: Some(NonNull::from_ref(cb.get_ref())),
            link: UnsafeCell::new(ListEntry::default()),
        }
    }

    /// Create a new edge pointing at a multi-thread object.
    #[cfg(feature = "multi_thread")]
    #[inline]
    #[allow(
        clippy::missing_const_for_fn,
        reason = "Const context makes no sense, edges are always heap-allocated."
    )]
    pub(crate) fn new_mt(_: Pin<&MTControlBlock>) -> Self {
        Edge {
            destination: None,
            link: UnsafeCell::new(ListEntry::default()),
        }
    }

    /// Get the control-block of the destination of this edge.
    #[cfg(not(feature = "multi_thread"))]
    #[inline]
    #[allow(
        clippy::missing_const_for_fn,
        reason = "Const context makes no sense, edges are always heap-allocated."
    )]
    pub(super) fn get_control_block(&self) -> Pin<&ControlBlock> {
        unsafe { Pin::new_unchecked(self.destination.as_ref()) }
    }

    /// Get the control-block of the destination of this edge.
    #[cfg(feature = "multi_thread")]
    #[inline]
    #[allow(
        clippy::missing_const_for_fn,
        reason = "Const context makes no sense, edges are always heap-allocated."
    )]
    pub(super) fn get_control_block(&self) -> Option<Pin<&ControlBlock>> {
        self.destination
            .as_ref()
            .map(|ptr| unsafe { Pin::new_unchecked(ptr.as_ref()) })
    }
}

#[cfg(feature = "multi_thread")]
impl MTEdge {
    /// Create a new edge.
    #[inline]
    #[allow(
        clippy::missing_const_for_fn,
        reason = "Const context makes no sense, edges are always heap-allocated."
    )]
    pub(crate) fn new(cb: Pin<&MTControlBlock>) -> Self {
        MTEdge {
            destination: NonNull::from_ref(cb.get_ref()),
            link: UnsafeCell::new(ListEntry::default()),
        }
    }

    /// Get the control-block of the destination of this edge.
    #[inline]
    #[allow(
        clippy::missing_const_for_fn,
        reason = "Const context makes no sense, edges are always heap-allocated."
    )]
    pub(super) fn get_control_block(&self) -> Pin<&MTControlBlock> {
        unsafe { Pin::new_unchecked(self.destination.as_ref()) }
    }
}

impl ListElement<EdgeTag> for Edge {
    type Type = Edge;

    #[inline]
    fn get_entry(&self) -> &ListEntry<Self::Type> {
        unsafe { &*self.link.get() }
    }

    #[inline]
    fn get_entry_mut(&self) -> &mut ListEntry<Self::Type> {
        unsafe { &mut *self.link.get() }
    }
}

#[cfg(feature = "multi_thread")]
impl ListElement<EdgeTag> for MTEdge {
    type Type = MTEdge;

    #[inline]
    fn get_entry(&self) -> &ListEntry<Self::Type> {
        unsafe { &*self.link.get() }
    }

    #[inline]
    fn get_entry_mut(&self) -> &mut ListEntry<Self::Type> {
        unsafe { &mut *self.link.get() }
    }
}

impl fmt::Debug for Edge {
    /// Debug formatting for [Edge].
    ///
    /// We don't debug-lock the destination object, in case it recurses back to us.
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
        let mut d = f.debug_struct("Edge");
        d.field("link", &self.link);
        d.finish_non_exhaustive()
    }
}

#[cfg(feature = "multi_thread")]
impl fmt::Debug for MTEdge {
    /// Debug formatting for [MTEdge].
    ///
    /// We don't debug-lock the destination object, in case it recurses back to us.
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
        let mut d = f.debug_struct("MTEdge");
        d.field("link", &self.link);
        d.finish_non_exhaustive()
    }
}

#[cfg(feature = "multi_thread")]
unsafe impl Send for MTEdge {}

#[cfg(feature = "multi_thread")]
unsafe impl Sync for MTEdge {}