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::Rc, sync::Arc},
};

/// Place that can store a smart pointer.
///
/// # Safety
///
/// Types that implement this trait assert that:
///
/// 1. The `insert` and `remove` methods are true inverses of each other with no side effects.
/// 2. The pointer to the data is stable on [`Deref`] and [`DerefMut`] (if implemented), *and* this
///    pointer is the same as the one that is returned by [`remove`].
/// 3. The data may be read even when outside the well.
/// 4. If [`DerefMut`] is implemented, the data may be mutated even when outside the well.
///
/// [`insert`]: Well::insert
/// [`remove`]: Well::remove
pub unsafe trait Well: Deref<Target: Sized> {
    /// 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>;
}

/// 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 {}
    }
}

trait_alias! {
    /// Alias for <code>[Well] + [DerefMut]</code>.
    pub trait WellMut = (DerefMut + Well);
}

// SAFETY: A pointer in its almost-rawest form.
unsafe impl<T> Well for &T {
    #[inline]
    unsafe fn insert(ptr: NonNull<T>) -> Self {
        // SAFETY: Ensured by caller.
        unsafe { ptr.as_ref() }
    }

    #[inline]
    fn remove(self) -> NonNull<T> {
        NonNull::from(self)
    }
}

// SAFETY: A pointer in its almost-rawest form.
unsafe impl<T> Well for Pin<&T> {
    #[inline]
    unsafe fn insert(ptr: NonNull<T>) -> Self {
        // SAFETY: Ensured by caller.
        unsafe { Pin::new_unchecked(ptr.as_ref()) }
    }

    #[inline]
    fn remove(self) -> NonNull<T> {
        NonNull::from(self.get_ref())
    }
}

// SAFETY: A pointer in its almost-rawest form.
unsafe impl<T> Well for &mut 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: A pointer in its almost-rawest form.
unsafe impl<T> Well for Pin<&mut T> {
    #[inline]
    unsafe fn insert(mut ptr: NonNull<T>) -> Self {
        // SAFETY: Ensured by caller.
        unsafe { Pin::new_unchecked(ptr.as_mut()) }
    }

    #[inline]
    fn remove(self) -> NonNull<T> {
        // SAFETY: We can only get a pinned version back out of the well.
        unsafe { NonNull::from(self.get_unchecked_mut()) }
    }
}

#[cfg(any(test, feature = "alloc"))]
// SAFETY: `Box` just wraps a pointer.
unsafe impl<T> Well for Box<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(any(test, feature = "alloc"))]
// SAFETY: If we keep the pin, everything works out.
unsafe impl<T> Well for Pin<Box<T>> {
    #[inline]
    unsafe fn insert(ptr: NonNull<T>) -> Self {
        // SAFETY: Ensured by caller.
        unsafe { Pin::new_unchecked(Box::from_raw(ptr.as_ptr())) }
    }

    #[inline]
    fn remove(self) -> NonNull<T> {
        // SAFETY: Box's pointer is always non-null, and we're not moving anything out of the box.
        unsafe { NonNull::new_unchecked(Box::into_raw(Pin::into_inner_unchecked(self))) }
    }
}

#[cfg(feature = "alloc")]
// SAFETY: `Rc` accounts for the reference-counter offsets in `into_raw` and `from_raw`.
unsafe impl<T> Well for Rc<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: If we keep the pin, everything works out.
unsafe impl<T> Well for Pin<Rc<T>> {
    #[inline]
    unsafe fn insert(ptr: NonNull<T>) -> Self {
        // SAFETY: Ensured by caller.
        unsafe { Pin::new_unchecked(Rc::from_raw(ptr.as_ptr())) }
    }

    #[inline]
    fn remove(self) -> NonNull<T> {
        // SAFETY: Rc's pointer is always non-null, and we're not moving anything out of the `Rc`.
        unsafe { NonNull::new_unchecked(Rc::into_raw(Pin::into_inner_unchecked(self)).cast_mut()) }
    }
}

#[cfg(feature = "alloc")]
// SAFETY: `Arc` accounts for the reference-counter offsets in `into_raw` and `from_raw`.
unsafe impl<T> Well for Arc<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: If we keep the pin, everything works out.
unsafe impl<T> Well for Pin<Arc<T>> {
    #[inline]
    unsafe fn insert(ptr: NonNull<T>) -> Self {
        // SAFETY: Ensured by caller.
        unsafe { Pin::new_unchecked(Arc::from_raw(ptr.as_ptr())) }
    }

    #[inline]
    fn remove(self) -> NonNull<T> {
        // SAFETY: Arc's pointer is always non-null, and we're not moving anything out of the `Arc`.
        unsafe { NonNull::new_unchecked(Arc::into_raw(Pin::into_inner_unchecked(self)).cast_mut()) }
    }
}

/// 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 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)
    }
}

/// 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<()>>>;