cycle_ptr 0.1.0

//! The object module declares the [Object] type.
//!
//! These objects are an abstraction of the actual objects used in a program.
//! Each such holds on to the actual object, and a control-block.
pub(crate) mod metadata;
mod ptr;

use crate::generation::{ControlBlock, GenerationPtr, ObjectState};
use crate::util::NonNull;
use std::backtrace::Backtrace;
use std::cell::RefCell;
use std::cell::UnsafeCell;
use std::pin::Pin;
use std::sync::Arc;

#[cfg(feature = "weak_pointer")]
use crate::generation::Colour;
#[cfg(all(feature = "multi_thread", feature = "weak_pointer"))]
use crate::generation::MTRefCount;
#[cfg(feature = "weak_pointer")]
use crate::generation::RefCount;
#[cfg(feature = "multi_thread")]
use crate::generation::{MTControlBlock, MTGenerationPtr};
#[cfg(feature = "weak_pointer")]
use std::fmt;
#[cfg(all(feature = "multi_thread", feature = "weak_pointer"))]
use std::sync::atomic::AtomicBool;
#[cfg(feature = "multi_thread")]
use std::sync::atomic::{AtomicUsize, Ordering};

#[cfg(feature = "multi_thread")]
pub(crate) use ptr::{DynMTObjectPtr, MTObjectPtr};
pub(crate) use ptr::{DynObjectPtr, ObjectPtr};

/// Convenience function, that invokes [Box::leak], but maintains the [Pin].
fn leak_pinned_box<T>(ptr: Pin<Box<T>>) -> Pin<&'static T>
where
    T: ?Sized,
{
    unsafe { Pin::new_unchecked(Box::leak(Pin::into_inner_unchecked(ptr))) }
}

/// An garbage-collectible object.
///
/// The object holds on to the actual object `T`, as well as book-keeping information ([ControlBlock]).
pub(crate) struct Object<T>
where
    T: 'static,
{
    /// The control block for the object.
    control_block: ControlBlock,
    /// The object itself.
    data: UnsafeCell<Option<T>>,
    /// Reference counter for use by [ObjectPtr]/[DynObjectPtr].
    ///
    /// In [Rc][std::rc::Rc]/[Arc][std::sync::Arc] terms, this would be the weak reference count.
    refcount: RefCell<usize>,
}

/// An garbage-collectible object.
///
/// The object holds on to the actual object `T`, as well as book-keeping information ([MTControlBlock]).
#[cfg(feature = "multi_thread")]
pub(crate) struct MTObject<T>
where
    T: 'static,
{
    /// The control block for the object.
    control_block: MTControlBlock,
    /// The object itself.
    data: UnsafeCell<Option<T>>,
    /// Reference counter for use by [MTObjectPtr]/[DynMTObjectPtr].
    ///
    /// In [Rc][std::rc::Rc]/[Arc][std::sync::Arc] terms, this would be the weak reference count.
    refcount: AtomicUsize,
    /// Flag that indicates if `data` has been initialized.
    ///
    /// Weak pointers can be created before `data` has been initialized,
    /// which means `data` will be written to at some point,
    /// while the [Weak::upgrade][crate::Weak::upgrade] will want to read to confirm the presence of `data`.
    /// Since that leads to undefined behaviour, we'll use an extra flag instead.
    #[cfg(feature = "weak_pointer")]
    initialized: AtomicBool,
}

/// Describes the methods of [Object] for type-erasure.
///
/// This interface is defined so that [DynObjectPtr] can point at an object, without requiring dynamic typing.
pub(crate) trait ObjectIntf {
    /// Release the object.
    fn release_object(&self);
    /// Try to acquire a reference to the object.
    ///
    /// Only succeeds if there is at least one active reference.
    fn try_refcount_inc(&self) -> Result<(), ()>;
    /// Acquire a reference to the object.
    ///
    /// As long as there are references, it will remain valid.
    fn refcount_inc(&self);
    /// Release a reference to the object.
    ///
    /// This function will destroy and free `Self`, if the reference count reaches zero.
    fn refcount_dec(&self);
    /// Gain access to the control block.
    fn get_control_block(&self) -> &ControlBlock;
    /// Get access to the generation pointer.
    ///
    /// Access is not protected.
    fn get_generation_ptr(&self) -> GenerationPtr {
        self.get_control_block().generation.borrow().clone()
    }
    /// Check the object state.
    fn object_state(&self) -> ObjectState {
        self.get_control_block().object_state()
    }
    /// Check if the object is initialized.
    fn has_data(&self) -> bool;
    /// Retrieve the backtrace of when this object was created.
    fn created_backtrace(&self) -> &Option<Arc<Backtrace>> {
        &self.get_control_block().created_backtrace
    }
}

/// Describes the methods of [Object] for type-erasure.
///
/// This interface is defined so that [DynObjectPtr] can point at an object, without requiring dynamic typing.
///
/// This is the counterpart of [ObjectIntf] for use in multi-thread context.
#[cfg(feature = "multi_thread")]
pub(crate) trait MTObjectIntf {
    /// Release the object.
    fn release_object(&self);
    /// Try to acquire a reference to the object.
    ///
    /// Only succeeds if there is at least one active reference.
    fn try_refcount_inc(&self) -> Result<(), ()>;
    /// Acquire a reference to the object.
    ///
    /// As long as there are references, it will remain valid.
    fn refcount_inc(&self);
    /// Release a reference to the object.
    ///
    /// This function will destroy and free `Self`, if the reference count reaches zero.
    fn refcount_dec(&self);
    /// Gain access to the control block.
    fn get_control_block(&self) -> &MTControlBlock;
    /// Get access to the generation pointer.
    ///
    /// Access is not protected.
    fn get_generation_ptr(&self) -> MTGenerationPtr {
        self.get_control_block().generation.read().unwrap().clone()
    }
    /// Check the object state.
    fn object_state(&self) -> ObjectState {
        self.get_control_block().object_state()
    }
    /// Check if the object is initialized.
    fn has_data(&self) -> bool;
    /// Retrieve the backtrace of when this object was created.
    fn created_backtrace(&self) -> &Option<Arc<Backtrace>> {
        &self.get_control_block().created_backtrace
    }
}

impl<T> Object<T>
where
    T: 'static,
{
    /// Create a new [Object].
    pub(crate) fn new_ptr<Factory>(
        initial_refcount: usize,
        factory: Factory,
        generation: Option<GenerationPtr>,
    ) -> Pin<ObjectPtr<T>>
    where
        Factory: FnOnce(metadata::Metadata) -> T,
    {
        let mut p = Box::pin(Object {
            control_block: ControlBlock::new(initial_refcount, generation),
            data: UnsafeCell::new(None),
            refcount: RefCell::new(0),
        });

        unsafe {
            // We need to publish the destructor of ourself.
            let destructor = NonNull::<dyn ObjectIntf>::from_ref(&*p);
            p.as_mut()
                .map_unchecked_mut(|p| &mut p.control_block)
                .register(destructor);
        }

        // Now that we have our pointer, we can initialize the data.
        let p = ObjectPtr::new(leak_pinned_box(p));
        unsafe {
            *p.data.get() = Some(factory(metadata::Metadata::new(p.clone().into())));
        }
        p
    }

    /// Create a new [Object], which will be initialized with a non-upgradable [Weak][crate::sync::Weak] pointer, allowing for a cyclic weak reference.
    #[cfg(feature = "weak_pointer")]
    pub(crate) fn new_cyclic_ptr<Factory>(
        initial_refcount: usize,
        factory: Factory,
        generation: Option<GenerationPtr>,
    ) -> Pin<ObjectPtr<T>>
    where
        Factory: FnOnce(crate::Metadata, crate::Weak<T>) -> T,
    {
        let mut p = Box::pin(Object {
            control_block: ControlBlock::new(initial_refcount, generation),
            data: UnsafeCell::new(None),
            refcount: RefCell::new(0),
        });

        unsafe {
            // We need to publish the destructor of ourself.
            let destructor = NonNull::<dyn ObjectIntf>::from_ref(&*p);
            p.as_mut()
                .map_unchecked_mut(|p| &mut p.control_block)
                .register(destructor);
        }

        // Now that we have our pointer, we can initialize the data.
        let p = ObjectPtr::new(leak_pinned_box(p));
        let weak = crate::Weak::new_from_raw(p.clone());
        unsafe {
            *p.data.get() = Some(factory(metadata::Metadata::new(p.clone().into()), weak));
        }
        p
    }

    /// Read the data helf in an object.
    ///
    /// # Panics
    ///
    /// Will panic if the object isn't dereferencable,
    /// which may be due to the object not having been initialized,
    /// or because the object has expired.
    pub(crate) fn get_data(&self) -> &T {
        unsafe {
            let opt_data_ref = &*self.data.get();
            opt_data_ref
                .as_ref()
                .expect("live object should be dereferencable")
        }
    }
}

#[cfg(feature = "multi_thread")]
impl<T> MTObject<T>
where
    T: 'static + Send + Sync,
{
    /// Create a new [Object].
    pub(crate) fn new_ptr<Factory>(
        initial_refcount: usize,
        factory: Factory,
        generation: Option<MTGenerationPtr>,
    ) -> Pin<MTObjectPtr<T>>
    where
        Factory: FnOnce(metadata::sync::Metadata) -> T,
    {
        let mut p = Box::pin(MTObject {
            control_block: MTControlBlock::new(initial_refcount, generation),
            data: UnsafeCell::new(None),
            refcount: AtomicUsize::new(0),
            #[cfg(feature = "weak_pointer")]
            initialized: AtomicBool::new(false),
        });

        unsafe {
            // We need to publish the destructor of ourself.
            let destructor = NonNull::<dyn Send + Sync + MTObjectIntf>::from_ref(&*p);
            p.as_mut()
                .map_unchecked_mut(|p| &mut p.control_block)
                .register(destructor);
        }

        // Now that we have our pointer, we can initialize the data.
        let p = MTObjectPtr::new(leak_pinned_box(p));
        unsafe {
            *p.data.get() = Some(factory(metadata::sync::Metadata::new(p.clone().into())));
        }
        #[cfg(feature = "weak_pointer")]
        p.initialized.store(true, Ordering::Release);
        p
    }

    /// Create a new [Object], which will be initialized with a non-upgradable [Weak][crate::sync::Weak] pointer, allowing for a cyclic weak reference.
    #[cfg(feature = "weak_pointer")]
    pub(crate) fn new_cyclic_ptr<Factory>(
        initial_refcount: usize,
        factory: Factory,
        generation: Option<MTGenerationPtr>,
    ) -> Pin<MTObjectPtr<T>>
    where
        Factory: FnOnce(metadata::sync::Metadata, crate::sync::Weak<T>) -> T,
    {
        let mut p = Box::pin(MTObject {
            control_block: MTControlBlock::new(initial_refcount, generation),
            data: UnsafeCell::new(None),
            refcount: AtomicUsize::new(0),
            #[cfg(feature = "weak_pointer")]
            initialized: AtomicBool::new(false),
        });

        unsafe {
            // We need to publish the destructor of ourself.
            let destructor = NonNull::<dyn Send + Sync + MTObjectIntf>::from_ref(&*p);
            p.as_mut()
                .map_unchecked_mut(|p| &mut p.control_block)
                .register(destructor);
        }

        // Now that we have our pointer, we can initialize the data.
        let p = MTObjectPtr::new(leak_pinned_box(p));
        let weak = crate::sync::Weak::new_from_raw(p.clone());
        unsafe {
            *p.data.get() = Some(factory(
                metadata::sync::Metadata::new(p.clone().into()),
                weak,
            ));
        }
        #[cfg(feature = "weak_pointer")]
        p.initialized.store(true, Ordering::Release);
        p
    }
}

#[cfg(feature = "multi_thread")]
impl<T> MTObject<T>
where
    T: 'static,
{
    /// Read the data helf in an object.
    ///
    /// # Panics
    ///
    /// Will panic if the object isn't dereferencable,
    /// which may be due to the object not having been initialized,
    /// or because the object has expired.
    #[inline]
    pub(crate) fn get_data(&self) -> &T {
        unsafe {
            let opt_data_ref = &*self.data.get();
            opt_data_ref
                .as_ref()
                .expect("live object should be dereferencable")
        }
    }
}

impl<T> ObjectIntf for Object<T>
where
    T: 'static,
{
    fn release_object(&self) {
        unsafe {
            let data = &mut *self.data.get();
            assert!(data.is_some());
            data.take();
        }
    }

    fn try_refcount_inc(&self) -> Result<(), ()> {
        let mut v = self.refcount.borrow_mut();
        match *v {
            0 => Err(()),
            _ => {
                *v += 1;
                Ok(())
            }
        }
    }

    fn refcount_inc(&self) {
        self.refcount.replace_with(|v| *v + 1);
    }

    fn refcount_dec(&self) {
        let old_v = self.refcount.replace_with(|v| {
            assert_ne!(*v, 0);
            *v - 1
        });
        if old_v == 1 {
            // Last reference was dropped.
            //
            // Deregister from generation prior to destroying.
            self.control_block.invalidate_and_deregister();

            // SAFETY: we own the only reference to self,
            // and UnsafeCell<Self> has the same memory layout as <Self>.
            unsafe {
                let this = &*(self as *const Self as *const UnsafeCell<Self>);
                let _ = self;
                drop(Box::from_raw(this.get()));
            }
        }
    }

    fn get_control_block(&self) -> &ControlBlock {
        &self.control_block
    }

    fn has_data(&self) -> bool {
        unsafe { (*self.data.get()).is_some() }
    }
}

#[cfg(feature = "multi_thread")]
impl<T> MTObjectIntf for MTObject<T>
where
    T: 'static,
{
    fn release_object(&self) {
        unsafe {
            let data = &mut *self.data.get();
            assert!(data.is_some());
            data.take();
        }
    }

    fn try_refcount_inc(&self) -> Result<(), ()> {
        let mut v = 1;
        loop {
            match self.refcount.compare_exchange_weak(
                v,
                v + 1,
                Ordering::Relaxed,
                Ordering::Relaxed,
            ) {
                Ok(_) => {
                    return Ok(());
                }
                Err(x) => v = x,
            }

            if v == 0 {
                return Err(());
            }
        }
    }

    fn refcount_inc(&self) {
        self.refcount.fetch_add(1, Ordering::Relaxed);
    }

    fn refcount_dec(&self) {
        let old_v = self.refcount.fetch_sub(1, Ordering::Relaxed);
        assert_ne!(old_v, 0);
        if old_v == 1 {
            // Last reference was dropped.
            //
            // ThreadSanitizer does not support memory fences.
            // Yeah, I copied this from Arc.
            // Note that Arc uses `#[cfg(sanitize)]`, but the compiler won't permit us to do that,
            // because it's experimental.
            let _ = self.refcount.load(Ordering::Acquire);

            // Deregister from generation prior to destroying.
            self.control_block.invalidate_and_deregister();

            // SAFETY: we own the only reference to self,
            // and UnsafeCell<Self> has the same memory layout as <Self>.
            unsafe {
                let this = &*(self as *const Self as *const UnsafeCell<Self>);
                let _ = self;
                drop(Box::from_raw(this.get()));
            }
        }
    }

    fn get_control_block(&self) -> &MTControlBlock {
        &self.control_block
    }

    fn has_data(&self) -> bool {
        #[cfg(feature = "weak_pointer")]
        if !self.initialized.load(Ordering::Relaxed) {
            return false;
        }

        unsafe { (*self.data.get()).is_some() }
    }
}

impl<T> Drop for Object<T>
where
    T: 'static,
{
    fn drop(&mut self) {
        assert_eq!(*self.refcount.borrow(), 0);
    }
}

#[cfg(feature = "multi_thread")]
impl<T> Drop for MTObject<T>
where
    T: 'static,
{
    fn drop(&mut self) {
        assert_eq!(self.refcount.load(Ordering::Relaxed), 0);
    }
}

#[cfg(feature = "weak_pointer")]
impl<T> Object<T>
where
    T: 'static + fmt::Debug,
{
    /// Compute the summary of a reference counter.
    ///
    /// Returns a string representing the object state (stronly-reachable/weakly-reachable/expired/unreachable),
    /// and a boolean indicating if it is safe to dereference the object.
    fn weak_debug_summary(refcount: &RefCount) -> (&'static str, bool) {
        let (refs, colour, state) = refcount.load();
        if refs > 0 {
            ("strongly-reachable", true)
        } else if colour != Colour::White {
            ("weakly-reachable", true)
        } else if state == ObjectState::Expired {
            ("expired", false)
        } else {
            ("unreachable", false)
        }
    }

    /// Print debugging information about a weak reference to this object.
    pub(crate) fn weak_debug_fmt(
        &self,
        typename: &str,
        f: &mut fmt::Formatter<'_>,
    ) -> Result<(), fmt::Error> {
        self.control_block.try_with_weak_lockout(|refcount| {
            let (summary, dereferencable) = Self::weak_debug_summary(refcount);
            if dereferencable {
                match unsafe { &*self.data.get() } {
                    None => write!(f, "{typename}(uninitialized object)", typename = typename),
                    Some(value) => {
                        write!(f, "{summary} {value:?}", summary = summary, value = value)
                    }
                }
            } else {
                write!(
                    f,
                    "{typename}({summary})",
                    typename = typename,
                    summary = summary
                )
            }
        })
    }
}

#[cfg(all(feature = "multi_thread", feature = "weak_pointer"))]
impl<T> MTObject<T>
where
    T: 'static + fmt::Debug,
{
    /// Compute the summary of a reference counter.
    ///
    /// Returns a string representing the object state (stronly-reachable/weakly-reachable/expired/unreachable),
    /// and a boolean indicating if it is safe to dereference the object if the `weak_lockout` is engaged.
    fn weak_debug_summary(refcount: &MTRefCount) -> (&'static str, bool) {
        let (refs, colour, state) = refcount.load();
        if refs > 0 {
            ("strongly-reachable", true)
        } else if colour != Colour::White {
            ("weakly-reachable", true)
        } else if state == ObjectState::Expired {
            ("expired", false)
        } else {
            ("unreachable", false)
        }
    }

    /// Print debugging information about a weak reference to this object.
    ///
    /// This method won't attempt to acquire any weak locks, and thus can only report on if an object is reachable.
    fn weak_debug_fmt_no_lock(
        &self,
        typename: &str,
        f: &mut fmt::Formatter<'_>,
    ) -> Result<(), fmt::Error> {
        write!(
            f,
            "{typename}({summary})",
            typename = typename,
            summary = Self::weak_debug_summary(self.control_block.borrow_refcount_for_debug()).0
        )
    }

    /// Print debugging information about a weak reference to this object.
    ///
    /// Attempts to print the pointee object, if it can do so.
    pub(crate) fn weak_debug_fmt(
        &self,
        typename: &str,
        f: &mut fmt::Formatter<'_>,
    ) -> Result<(), fmt::Error> {
        if !self.initialized.load(Ordering::Relaxed) {
            return write!(f, "{typename}(uninitialized object)", typename = typename);
        }

        // Prevent weak pointers from being collected from under us.
        let attempt = self.control_block.try_with_weak_lockout(|refcount| {
            let (summary, dereferencable) = Self::weak_debug_summary(refcount);
            if dereferencable {
                match unsafe { &*self.data.get() } {
                    None => write!(
                        f,
                        "{typename}({summary} yet unintialized (BUG!))",
                        typename = typename,
                        summary = summary
                    ),
                    Some(value) => {
                        write!(f, "{summary} {value:?}", summary = summary, value = value)
                    }
                }
            } else {
                write!(
                    f,
                    "{typename}({summary})",
                    typename = typename,
                    summary = summary
                )
            }
        });

        match attempt {
            Ok(result) => result,
            Err(_) => self.weak_debug_fmt_no_lock(typename, f),
        }
    }
}

#[cfg(feature = "multi_thread")]
unsafe impl<T> Send for MTObject<T> where T: 'static + Send + Sync {}

#[cfg(feature = "multi_thread")]
unsafe impl<T> Sync for MTObject<T> where T: 'static + Send + Sync {}