potential_well/

traits.rs

//! [`Well`] and [`WellMut`] traits.
use core::{
    ops::{Deref, DerefMut},
    pin::Pin,
    ptr::NonNull,
};

#[cfg(feature = "alloc")]
use {
    crate::atomic::{PotentialAtomic, PotentialAtomicOption},
    alloc::{
        boxed::Box,
        rc::{self, Rc},
        sync::{self as arc, Arc},
    },
};

/// Place that can store a smart pointer.
///
/// # Safety
///
/// Types that implement this trait assert that the [`insert`] and [`remove`] methods are true
/// inverses of each other with no side effects.
///
/// [`insert`]: Well::insert
/// [`remove`]: Well::remove
pub unsafe trait Well {
    /// Data stored in the pointer.
    type Target;

    /// Put the data back into the well.
    ///
    /// # Safety
    ///
    /// The pointer passed to [`insert`] must previously have been received from [`remove`].
    ///
    /// [`insert`]: Well::insert
    /// [`remove`]: Well::remove
    unsafe fn insert(ptr: NonNull<Self::Target>) -> Self;

    /// Take the data out of the well.
    fn remove(self) -> NonNull<Self::Target>;
}

/// Gets the target for a [`Well`].
pub type Bucket<W> = <W as Well>::Target;

/// Implementation of trait alias that uses trait aliases.
#[cfg(feature = "nightly")]
macro_rules! trait_alias {
    (
        $(#[$attr:meta])*
        $vis:vis trait $t:ident = ($($bound:tt)*);
    ) => {
        $(#[$attr])*
        ///
        /// Implemented as a trait alias with the `nightly` feature,
        /// and an automatically-implemented trait otherwise.
        $vis trait $t = $($bound)*;
    }
}

/// Implementation of trait alias that uses traits.
#[cfg(not(feature = "nightly"))]
macro_rules! trait_alias {
    (
        $(#[$attr:meta])*
        $vis:vis trait $t:ident = ($($bound:tt)*);
    ) => {
        $(#[$attr])*
        ///
        /// Implemented as a trait alias with the `nightly` feature,
        /// and an automatically-implemented trait otherwise.
        $vis trait $t: $($bound)* {}
        impl<T: $($bound)*> $t for T {}
    }
}

/// Smart pointer without direct access to its data.
///
/// # Safety
///
/// Implementors of this trait assert that [`insert`] and [`remove`] calls of themselves and their
/// [`Access`] variant can be interchanged as long as the number of "weak" and "strong" versions
/// remain the same.
///
/// [`Access`]: WeakWell::Access
/// [`insert`]: Well::insert
/// [`remove`]: Well::remove
pub unsafe trait WeakWell: Well {
    /// Smart pointer that can directly access data.
    type Access: StrongWell + Deref<Target = Self::Target>;

    /// Attempts to access data inside the well.
    fn access(&self) -> Option<Self::Access>;
}

/// Smart pointer with direct access to its data.
///
/// # Safety
///
/// Types that implement this trait assert, in addition to the requirements of [`Well`], that the
/// pointers returned/received by [`insert`] and [`remove`] are also valid to deref directly
/// whenever a valid reference to the pointer is obtained, *and* that if they implement
/// [`DerefMut`], the same applies to mutable dereferences.
///
/// Additionally, implementations guarantee that their contents are implicitly pinned, and thus
/// [`Pin::new_unchecked`] and [`Pin::into_inner_unchecked`] have the correct semantics for the
/// generic [`Pin`]ned implementation.
///
/// [`insert`]: Well::insert
/// [`remove`]: Well::remove
pub unsafe trait StrongWell:
    Deref<Target: Sized> + Well<Target = <Self as Deref>::Target>
{
}

// SAFETY: Ensured by contract for `StrongWell`.
unsafe impl<W: StrongWell> Well for Pin<W> {
    type Target = Bucket<W>;

    #[inline]
    unsafe fn insert(ptr: NonNull<Bucket<W>>) -> Pin<W> {
        // SAFETY: Ensured by contract for `StrongWell`.
        unsafe { Pin::new_unchecked(W::insert(ptr)) }
    }

    #[inline]
    fn remove(self) -> NonNull<Bucket<W>> {
        // SAFETY: Ensured by contract for `StrongWell`.
        unsafe { Pin::into_inner_unchecked(self).remove() }
    }
}
// SAFETY: Ensured by contract for `StrongWell`.
unsafe impl<W: StrongWell> StrongWell for Pin<W> {}

trait_alias! {
    /// Alias for <code>[StrongWell] + [DerefMut]</code>.
    ///
    /// Since [`StrongWell`] is unsafe to implement, it can assert that its guarantees apply to
    /// [`DerefMut`] implementations as well.
    pub trait StrongWellMut = (StrongWell + DerefMut);
}

// SAFETY: `NonNull::from` and `NonNull::as_ref` are direct inverses.
unsafe impl<'w, T> Well for &'w T {
    type Target = T;

    #[inline]
    unsafe fn insert(ptr: NonNull<T>) -> &'w T {
        // SAFETY: Ensured by caller.
        unsafe { ptr.as_ref() }
    }

    #[inline]
    fn remove(self) -> NonNull<T> {
        NonNull::from(self)
    }
}
// SAFETY: `Deref for &T` is stable.
unsafe impl<T> StrongWell for &T {}

// SAFETY: `NonNull::from` and `NonNull::as_mut` are direct inverses.
unsafe impl<T> Well for &mut T {
    type Target = T;

    #[inline]
    unsafe fn insert(mut ptr: NonNull<T>) -> Self {
        // SAFETY: Ensured by caller.
        unsafe { ptr.as_mut() }
    }

    #[inline]
    fn remove(self) -> NonNull<T> {
        NonNull::from(self)
    }
}
// SAFETY: `Deref for &mut T` is stable.
unsafe impl<T> StrongWell for &mut T {}

#[cfg(any(test, feature = "alloc"))]
// SAFETY: `Box::from_raw` and `Box::into_raw` are direct inverses.
unsafe impl<T> Well for Box<T> {
    type Target = T;

    #[inline]
    unsafe fn insert(ptr: NonNull<T>) -> Self {
        // SAFETY: Ensured by caller.
        unsafe { Box::from_raw(ptr.as_ptr()) }
    }

    #[inline]
    fn remove(self) -> NonNull<T> {
        // SAFETY: Box's pointer is always non-null.
        unsafe { NonNull::new_unchecked(Box::into_raw(self)) }
    }
}
#[cfg(feature = "alloc")]
// SAFETY: `Deref for Box<T>` is stable.
unsafe impl<T> StrongWell for Box<T> {}

#[cfg(feature = "alloc")]
// SAFETY: `Rc::from_raw` and `Rc::into_raw` are direct inverses.
unsafe impl<T> Well for Rc<T> {
    type Target = T;

    #[inline]
    unsafe fn insert(ptr: NonNull<T>) -> Self {
        // SAFETY: Ensured by caller.
        unsafe { Rc::from_raw(ptr.as_ptr()) }
    }

    #[inline]
    fn remove(self) -> NonNull<T> {
        // SAFETY: Rc's pointer is always non-null.
        unsafe { NonNull::new_unchecked(Rc::into_raw(self).cast_mut()) }
    }
}
#[cfg(feature = "alloc")]
// SAFETY: `Deref for Rc<T>` is stable.
unsafe impl<T> StrongWell for Rc<T> {}

#[cfg(feature = "alloc")]
// SAFETY: `Weak::from_raw` and `Weak::into_raw` are direct inverses.
unsafe impl<T> Well for rc::Weak<T> {
    type Target = T;

    #[inline]
    unsafe fn insert(ptr: NonNull<T>) -> Self {
        // SAFETY: Ensured by caller.
        unsafe { rc::Weak::from_raw(ptr.as_ptr()) }
    }

    #[inline]
    fn remove(self) -> NonNull<T> {
        // SAFETY: WeakArc's pointer is always non-null.
        unsafe { NonNull::new_unchecked(rc::Weak::into_raw(self).cast_mut()) }
    }
}
#[cfg(feature = "alloc")]
// SAFETY: `Rc` and `Weak` share the same pointers.
unsafe impl<T> WeakWell for rc::Weak<T> {
    type Access = Rc<T>;

    #[inline]
    fn access(&self) -> Option<Rc<T>> {
        self.upgrade()
    }
}

#[cfg(feature = "alloc")]
// SAFETY: `Arc::from_raw` and `Arc::into_raw` are direct inverses.
unsafe impl<T> Well for Arc<T> {
    type Target = T;

    #[inline]
    unsafe fn insert(ptr: NonNull<T>) -> Self {
        // SAFETY: Ensured by caller.
        unsafe { Arc::from_raw(ptr.as_ptr()) }
    }

    #[inline]
    fn remove(self) -> NonNull<T> {
        // SAFETY: Arc's pointer is always non-null.
        unsafe { NonNull::new_unchecked(Arc::into_raw(self).cast_mut()) }
    }
}
#[cfg(feature = "alloc")]
// SAFETY: `Deref for Arc<T>` is stable.
unsafe impl<T> StrongWell for Arc<T> {}

#[cfg(feature = "alloc")]
// SAFETY: `Weak::from_raw` and `Weak::into_raw` are direct inverses.
unsafe impl<T> Well for arc::Weak<T> {
    type Target = T;

    #[inline]
    unsafe fn insert(ptr: NonNull<T>) -> Self {
        // SAFETY: Ensured by caller.
        unsafe { arc::Weak::from_raw(ptr.as_ptr()) }
    }

    #[inline]
    fn remove(self) -> NonNull<T> {
        // SAFETY: WeakArc's pointer is always non-null.
        unsafe { NonNull::new_unchecked(arc::Weak::into_raw(self).cast_mut()) }
    }
}
#[cfg(feature = "alloc")]
// SAFETY: `Arc` and `Weak` share the same pointers.
unsafe impl<T> WeakWell for arc::Weak<T> {
    type Access = Arc<T>;

    #[inline]
    fn access(&self) -> Option<Arc<T>> {
        self.upgrade()
    }
}

/// Potential well, representing a generic container.
///
/// Useful for recursive data structures, since it avoids recursive types.
///
/// # Examples
///
/// Atomic linked list via [`PotentialWell`]:
///
/// ```
/// use potential_well::{PotentialWell, PotentialAtomicOption};
///
/// struct Link<T, W: PotentialWell = Box<()>> {
///     data: T,
///     next: PotentialAtomicOption<Link<T, W>, W>
/// }
/// struct List<T, W: PotentialWell = Box<()>> {
///     root: PotentialAtomicOption<Link<T, W>, W>,
/// }
///
/// let list: List<u32> = List {
///     root: PotentialAtomicOption::some(Box::new(Link {
///         data: 1,
///         next: PotentialAtomicOption::some(Box::new(Link {
///             data: 2,
///             next: PotentialAtomicOption::some(Box::new(Link {
///                 data: 3,
///                 next: PotentialAtomicOption::none(),
///             }))
///         })),
///     })),
/// };
///
/// // no Drop implementation needed!
/// drop(list);
/// ```
///
/// Without [`PotentialWell`], you immediately run into trouble:
///
/// ```compile_fail
/// use potential_well::{Well, AtomicOption};
///
/// // recursive type: Link<T, Box<Link<T, Box<Link<T, ...>>>>>
/// struct Link<T, W: Well<Target = Link<T, Self>>> {
///     data: T,
///     next: AtomicOption<W>,
/// }
/// struct List<T, W: Well<Target = Link<T, Self>>> {
///     root: AtomicOption<W>,
/// }
///
/// let list: List<u32, Box<_>> = List {
///     root: AtomicOption::some(Box::new(Link {
///         data: 1,
///         next: AtomicOption::some(Box::new(Link {
///             data: 2,
///             next: AtomicOption::some(Box::new(Link {
///                 data: 3,
///                 next: AtomicOption::none(),
///             }))
///         })),
///     })),
/// };
/// ```
pub trait PotentialWell {
    /// Makes a well of a particular type.
    type Well<T>: Well<Target = T>;

    /// Makes that well.
    fn new<T>(data: T) -> Self::Well<T>;
}

#[cfg(any(test, feature = "alloc"))]
impl PotentialWell for Box<()> {
    type Well<T> = Box<T>;

    #[inline]
    fn new<T>(data: T) -> Box<T> {
        Box::new(data)
    }
}

#[cfg(any(test, feature = "alloc"))]
impl PotentialWell for Pin<Box<()>> {
    type Well<T> = Pin<Box<T>>;

    #[inline]
    fn new<T>(data: T) -> Pin<Box<T>> {
        Box::pin(data)
    }
}

#[cfg(feature = "alloc")]
impl PotentialWell for Rc<()> {
    type Well<T> = Rc<T>;

    #[inline]
    fn new<T>(data: T) -> Rc<T> {
        Rc::new(data)
    }
}

#[cfg(feature = "alloc")]
impl PotentialWell for Pin<Rc<()>> {
    type Well<T> = Pin<Rc<T>>;

    #[inline]
    fn new<T>(data: T) -> Pin<Rc<T>> {
        Rc::pin(data)
    }
}

#[cfg(feature = "alloc")]
impl PotentialWell for rc::Weak<()> {
    type Well<T> = rc::Weak<T>;

    #[inline]
    fn new<T>(_: T) -> rc::Weak<T> {
        rc::Weak::default()
    }
}

#[cfg(feature = "alloc")]
impl PotentialWell for Arc<()> {
    type Well<T> = Arc<T>;

    #[inline]
    fn new<T>(data: T) -> Arc<T> {
        Arc::new(data)
    }
}

#[cfg(feature = "alloc")]
impl PotentialWell for Pin<Arc<()>> {
    type Well<T> = Pin<Arc<T>>;

    #[inline]
    fn new<T>(data: T) -> Pin<Arc<T>> {
        Arc::pin(data)
    }
}

#[cfg(feature = "alloc")]
impl PotentialWell for arc::Weak<()> {
    type Well<T> = arc::Weak<T>;

    #[inline]
    fn new<T>(_: T) -> arc::Weak<T> {
        arc::Weak::default()
    }
}

/// Gets a well from a [`PotentialWell`].
///
/// In case you haven't gotten the joke by now, an "atom in a box" is called a [potential well] in
/// physics, and well, kinetic energy is the opposite of potential energy.
///
/// It's a bad joke. But this type shouldn't be necessary unless you're writing *really* generic
/// code, since most of the time, you'll be using one of the many aliases for [`PotentialAtomic`]
/// and [`PotentialAtomicOption`], which will just turn something like
/// <code>[KineticWell]&lt;T, W&lt;()&gt;&gt;</code> into <code>W&lt;T&gt;</code>.
///
/// [potential well]: https://en.wikipedia.org/wiki/Potential_well
pub type KineticWell<T, W> = <W as PotentialWell>::Well<T>;

/// Alias for <code>[PotentialAtomic]&lt;T, [Box]&lt;()&gt;&gt;</code>
#[cfg(feature = "alloc")]
pub type AtomicBox<T> = PotentialAtomic<T, Box<()>>;

/// Alias for <code>[PotentialAtomic]&lt;T, [Pin]&lt;[Box]&lt;()&gt;&gt;&gt;</code>
#[cfg(feature = "alloc")]
pub type AtomicPinBox<T> = PotentialAtomic<T, Pin<Box<()>>>;

/// Alias for <code>[PotentialAtomic]&lt;T, [Rc]&lt;()&gt;&gt;</code>
#[cfg(feature = "alloc")]
pub type AtomicRc<T> = PotentialAtomic<T, Rc<()>>;

/// Alias for <code>[PotentialAtomic]&lt;T, [Pin]&lt;[Rc]&lt;()&gt;&gt;&gt;</code>
#[cfg(feature = "alloc")]
pub type AtomicPinRc<T> = PotentialAtomic<T, Pin<Rc<()>>>;

/// Alias for <code>[PotentialAtomic]&lt;T, [Arc]&lt;()&gt;&gt;</code>
#[cfg(feature = "alloc")]
pub type AtomicArc<T> = PotentialAtomic<T, Arc<()>>;

/// Alias for <code>[PotentialAtomic]&lt;T, [Pin]&lt;[Arc]&lt;()&gt;&gt;&gt;</code>
#[cfg(feature = "alloc")]
pub type AtomicPinArc<T> = PotentialAtomic<T, Pin<Arc<()>>>;

/// Alias for <code>[PotentialAtomicOption]&lt;T, [Box]&lt;()&gt;&gt;</code>
#[cfg(feature = "alloc")]
pub type AtomicOptionBox<T> = PotentialAtomicOption<T, Box<()>>;

/// Alias for <code>[PotentialAtomicOption]&lt;T, [Pin]&lt;[Box]&lt;()&gt;&gt;&gt;</code>
#[cfg(feature = "alloc")]
pub type AtomicOptionPinBox<T> = PotentialAtomicOption<T, Pin<Box<()>>>;

/// Alias for <code>[PotentialAtomicOption]&lt;T, [Rc]&lt;()&gt;&gt;</code>
#[cfg(feature = "alloc")]
pub type AtomicOptionRc<T> = PotentialAtomicOption<T, Rc<()>>;

/// Alias for <code>[PotentialAtomicOption]&lt;T, [Pin]&lt;[Rc]&lt;()&gt;&gt;&gt;</code>
#[cfg(feature = "alloc")]
pub type AtomicOptionPinRc<T> = PotentialAtomicOption<T, Pin<Rc<()>>>;

/// Alias for <code>[PotentialAtomicOption]&lt;T, [Arc]&lt;()&gt;&gt;</code>
#[cfg(feature = "alloc")]
pub type AtomicOptionArc<T> = PotentialAtomicOption<T, Arc<()>>;

/// Alias for <code>[PotentialAtomicOption]&lt;T, [Pin]&lt;[Arc]&lt;()&gt;&gt;&gt;</code>
#[cfg(feature = "alloc")]
pub type AtomicOptionPinArc<T> = PotentialAtomicOption<T, Pin<Arc<()>>>;