path: root/src/lib.rs

// SelfRef - Pain-free self-referential pinned types
// Copyright (C) 2022 Soni L.
// This software is made with love by a queer trans person.
// With help from quinedot
//
// SPDX-License-Identifier: MIT OR Apache-2.0

#![no_std]
#![cfg_attr(feature="nightly", feature(dropck_eyepatch))]

//! Pain-free self-referential/recursively-referential pinned types.
//!
//! Because this crate optimizes for recursive references, it's much nicer to
//! use for porting/copying C code than alternatives. However, the cost is that
//! it requires generic associated types (GATs). Further, this is the only
//! crate for self-referential types which supports additional lifetimes than
//! the self-referential one (with the small ergonomic caveat that closures
//! don't support where bounds for now, so a proper trait has to be used).
//!
//! When using this crate, all you have to do is define your struct like you
//! would in C, and then tell `selfref` about it. However, do watch out; the
//! following will not be usable, despite compiling:
//!
//! ```rust
//! use selfref::opaque;
//!
//! // This is the actual self-referential struct.
//! struct MySelfRefStruct<'this> {
//!     this: &'this MySelfRefStruct<'this>,
//! }
//!
//! // This is a "marker" type, used to tell `selfref` about the type.
//! // This is actually the "type family" GAT pattern.
//! struct MySelfRefStructKey;
//!
//! // This tells `selfref` about our type.
//! opaque! {
//!     impl Opaque for MySelfRefStructKey {
//!         type Kind<'this> = MySelfRefStruct<'this>;
//!     }
//! }
//! ```
//!
//! That's because there's no way to create the reference
//! `&'this MySelfRefStruct<'this>` before constructing the struct! That is,
//! you cannot do this:
//!
//! ```rust compile_fail
//! struct MySelfRefStruct<'this> {
//!     this: &'this MySelfRefStruct<'this>,
//! }
//!
//! fn main() {
//!     let x = MySelfRefStruct { this: &x };
//! }
//! ```
//!
//! But then, you cannot do this in C either. Instead, to make it usable, we
//! use an `Option` and, to be able to set it, a `Cell`, like so:
//!
//! ```rust
//! use std::cell::Cell;
//!
//! use selfref::opaque;
//!
//! struct MySelfRefStruct<'this> {
//!     this: Cell<Option<&'this MySelfRefStruct<'this>>>,
//! }
//!
//! struct MySelfRefStructKey;
//!
//! opaque! {
//!     impl Opaque for MySelfRefStructKey {
//!         type Kind<'this> = MySelfRefStruct<'this>;
//!     }
//! }
//! ```
//!
//! and then we can use it:
//!
//! ```rust
//! // lines from the above example have been omitted
//!
//! # use std::cell::Cell;
//! #
//! use selfref::Holder;
//! use selfref::new_with_closure;
//! # use selfref::opaque;
//! use selfref::operate_in_closure;
//! #
//! # struct MySelfRefStruct<'this> {
//! #     this: Cell<Option<&'this MySelfRefStruct<'this>>>,
//! # }
//! #
//! # struct MySelfRefStructKey;
//! #
//! # opaque! {
//! #     impl Opaque for MySelfRefStructKey {
//! #         type Kind<'this> = MySelfRefStruct<'this>;
//! #     }
//! # }
//!
//! fn main() {
//!     // first, construct the struct
//!     let holder = Box::pin(Holder::<'_, MySelfRefStructKey>::new_with(
//!         new_with_closure::<MySelfRefStructKey, _>(|_| {
//!             MySelfRefStruct {
//!                 this: Cell::new(None)
//!             }
//!         })
//!     ));
//!
//!     // then, build the self-reference
//!     holder.as_ref().operate_in(
//!         operate_in_closure::<MySelfRefStructKey, _, _>(|this| {
//!             this.this.set(Some(this.get_ref()));
//!         })
//!     );
//! }
//! ```
//!
//! # Examples
//!
//! This is a more complex example borrowing from an external lifetime:
//!
//! ```rust
//! #![feature(pin_macro)]
//!
//! use core::cell::Cell;
//! use core::marker::PhantomData;
//! use core::pin::Pin;
//! use core::pin::pin;
//! 
//! use selfref::Holder;
//! use selfref::NewWith;
//! use selfref::OperateIn;
//! use selfref::opaque;
//!
//! struct Foo<'a, 'b: 'a> {
//!     foo: Cell<Option<&'a Foo<'a, 'b>>>,
//!     t: &'b str,
//! }
//!
//! struct FooKey<'b>(PhantomData<&'b str>);
//! opaque! {
//!     impl['b] Opaque for FooKey<'b> {
//!         type Kind<'a> = Foo<'a, 'b>;
//!     }
//! }
//!
//! fn main() {
//!     // can't use real closure, "hand-roll" a closure.
//!     struct FooBuilder<'b>(&'b str);
//!     impl<'k, 'b: 'k> NewWith<'k, FooKey<'b>> for FooBuilder<'b> {
//!         fn new_with<'a>(self) -> Foo<'a, 'b> where 'k: 'a {
//!             Foo {
//!                 foo: Default::default(),
//!                 t: self.0,
//!             }
//!         }
//!     }
//!
//!     // a non-'static &str
//!     let stack_array: [u8; 5] = *b"hello";
//!     let stack_str = core::str::from_utf8(&stack_array).unwrap();
//!
//!     // construct the struct
//!     let holder = pin!(Holder::new_with(FooBuilder(stack_str)));
//!
//!     // setup the self-reference
//!     struct SetFooRef;
//!     impl<'k, 'b: 'k> OperateIn<'k, FooKey<'b>> for SetFooRef {
//!         type Out = ();
//!         fn operate_in<'a>(self, foo: Pin<&'a Foo<'a, 'b>>)
//!         where 'k: 'a {
//!             foo.foo.set(Some(foo.get_ref()));
//!         }
//!     }
//!     holder.as_ref().operate_in(SetFooRef);
//! }
//! ```
//!
//! # Features
//!
//! Due to [PhantomData is unsound](https://github.com/rust-lang/rust/issues/102810)
//! we currently require the following features for `T: ?Sized` support in
//! `selfref::opaque!`:
//!
//! - `alloc` - `selfref::opaque!` for `T: ?Sized` is provided by `Box`.
//! - `nightly` - `selfref::opaque!` for `T: ?Sized` is provided by a *wrapper*
//!     around `PhantomData`, which works around the above issue. we call this
//!     "PhantomDrop".
//!
//! When enabling both features, `nightly` takes over and we use the wrapper
//! always. This doesn't make a practical difference since the generated UB
//! check is dead code anyway, but `PhantomDrop` should be lighter on compile
//! times.
//!
//! If not using either feature, `T: ?Sized` support requires `unsafe`ly
//! implementing `Opaque`.
//!
//! Note that we do **not** enable any features by default! We assume most
//! folks aren't coming to this crate for its `T: ?Sized` support, so these are
//! the best defaults for crates to depend on. If they do need the `?Sized`
//! support they can just enable one of these (probably `alloc`).

use core::marker::PhantomPinned;
use core::pin::Pin;
use core::mem;

// there's no sound way to dropck T: ?Sized without either alloc or nightly.
//
// so we just have the user opt-in to alloc or nightly as desired.
//
// when using alloc, we use Box<T> for UBCheck.
//
// when using nightly, we use our custom PhantomDrop<T> for UBCheck.
//
// when using neither, we just error on T: ?Sized and require a manual unsafe
// impl of Opaque.

#[cfg(all(feature="alloc", not(feature="nightly")))]
extern crate alloc;

#[cfg(all(feature="alloc", not(feature="nightly")))]
#[doc(hidden)]
pub use alloc::boxed::Box as UBCheck;

#[cfg(feature="nightly")]
#[doc(hidden)]
pub struct UBCheck<T: ?Sized>(core::marker::PhantomData<T>);

#[cfg(all(not(feature="alloc"), not(feature="nightly")))]
#[doc(hidden)]
pub struct UBCheck<T>(T);

#[cfg(feature="nightly")]
// SAFETY: dropck's like a Box<T>, but is no-alloc friendly.
unsafe impl<#[may_dangle] T: ?Sized> Drop for UBCheck<T> {
    fn drop(&mut self) {}
}

/// An opaqueified self-referential struct "key".
///
/// # Safety
///
/// This is unsafe because there are a bunch of soundness invariants that need
/// to be upheld. The following list is non-exhaustive:
///
/// - `Kind` must not have a `Drop` impl in any "path" that may trace back to
///     the original self-referential type, if said `Drop` impl can observe
///     the self-referential type.
/// - We assume `Kind` has the same layout for any `'a`. This is true as of the
///     time of writing this, and relies on Rust not having lifetime
///     specialization.
///
/// It's recommended to use the `selfref::opaque!` macro instead, which
/// enforces these invariants. For example, this doesn't compile:
///
/// ```rust compile_fail
/// use std::cell::Cell;
/// use selfref::opaque;
///
/// struct Foo<'a> {
///     foo: Cell<Option<&'a Foo<'a>>>,
/// }
///
/// impl<'a> Drop for Foo<'a> {
///     fn drop(&mut self) {
///     }
/// }
///
/// struct FooKey;
/// opaque! {
///     impl Opaque for FooKey {
///         type Kind<'a> = Foo<'a>;
///     }
/// }
/// ```
///
/// But by removing the `Drop` impl, it compiles:
///
/// ```rust
/// use std::cell::Cell;
/// use selfref::opaque;
///
/// struct Foo<'a> {
///     foo: Cell<Option<&'a Foo<'a>>>,
/// }
///
/// //impl<'a> Drop for Foo<'a> {
/// //    fn drop(&mut self) {
/// //    }
/// //}
///
/// struct FooKey;
/// opaque! {
///     impl Opaque for FooKey {
///         type Kind<'a> = Foo<'a>;
///     }
/// }
/// ```
///
/// # Examples
///
/// ```rust
/// use core::cell::Cell;
/// 
/// use selfref::Opaque;
///
/// struct Foo<'a> {
///     foo: Cell<Option<&'a Foo<'a>>>,
/// }
///
/// struct FooKey;
/// // SAFETY: Foo has no Drop impl and has the same layout for any 'a.
/// unsafe impl Opaque for FooKey {
///     type Kind<'a> = Foo<'a>;
/// }
/// ```
pub unsafe trait Opaque {
    /// The actual self-referential struct.
    type Kind<'a>: ?Sized where Self: 'a;
    #[doc(hidden)]
    fn ub_check() {
    }
}

/// Creates an opaqueified self-referential struct "key".
///
/// Safe wrapper around [`Opaque`] that checks the soundness requirements at
/// compile-time.
///
/// There are 2 forms of this macro. The second form accepts type parameters.
///
/// Note that where bounds go after the impl block.
///
/// # Examples
///
/// Simple example:
///
/// ```rust
/// use core::cell::Cell;
/// 
/// use selfref::opaque;
///
/// struct Foo<'a> {
///     foo: Cell<Option<&'a Foo<'a>>>,
/// }
///
/// struct FooKey;
/// opaque! {
///     impl Opaque for FooKey {
///         type Kind<'a> = Foo<'a>;
///     }
/// }
/// ```
///
/// Type parameters and where bounds:
///
/// ```rust
/// use core::cell::Cell;
/// use core::fmt::Display;
/// use core::marker::PhantomData;
/// 
/// use selfref::opaque;
///
/// struct Foo<'a, T: Display> {
///     foo: Cell<Option<&'a Foo<'a, T>>>,
///     t: T,
/// }
///
/// struct FooKey<T>(PhantomData<T>);
/// opaque! {
///     impl[T] Opaque for FooKey<T> {
///         type Kind<'a> = Foo<'a, T>;
///     } where T: Display
/// }
/// ```
#[macro_export]
macro_rules! opaque {
    (
        impl Opaque for $key:ty {
            type Kind<$l:lifetime> = $kind:ty;
        } $(where $($bounds:tt)*)?
    ) => {
        unsafe impl $crate::Opaque for $key $(where $($bounds)*)? {
            type Kind<$l> = $kind where Self: $l;
            fn ub_check() {
                fn ub_detect_helper(
                    _f: impl ::core::ops::Fn(
                        for<$l> fn([&$l (); 0]) -> $crate::UBCheck<$kind>,
                        for<$l> fn(&$l $crate::UBCheck<$kind>)
                    )
                ) $(where $($bounds)*)? {
                }
                ub_detect_helper(|f, g| {
                    let x: $crate::UBCheck<Self::Kind<'_>> = f([]);
                    g(&x);
                });
            }
        }
    };
    (
        impl[$($params:tt)+] Opaque for $key:ty {
            type Kind<$l:lifetime> = $kind:ty;
        } $(where $($bounds:tt)*)?
    ) => {
        unsafe impl<$($params)+> $crate::Opaque for $key
        $(where $($bounds)*)? {
            type Kind<$l> = $kind where Self: $l;
            fn ub_check() {
                fn ub_detect_helper<$($params)+>(
                    _f: impl ::core::ops::Fn(
                        for<$l> fn([&$l (); 0]) -> $crate::UBCheck<$kind>,
                        for<$l> fn(&$l $crate::UBCheck<$kind>)
                    )
                ) $(where $($bounds)*)? {
                }
                ub_detect_helper(|f, g| {
                    let x: $crate::UBCheck<Self::Kind<'_>> = f([]);
                    g(&x);
                });
            }
        }
    };
}

/// Holds an "opaqueified" `T::Kind`.
///
/// Note the lifetime, `'k`. This can be anything, as long as `T` outlives it.
/// 
/// # Examples
///
/// ```rust
/// use core::cell::Cell;
/// 
/// use selfref::Holder;
/// use selfref::new_with_closure;
/// use selfref::opaque;
///
/// #[derive(Default)]
/// struct Foo<'a> {
///     foo: Cell<Option<&'a Foo<'a>>>,
/// }
///
/// struct FooKey;
/// opaque! {
///     impl Opaque for FooKey {
///         type Kind<'a> = Foo<'a>;
///     }
/// }
///
/// fn main() {
///     // We can use a closure here, but we need to give the compiler a hint.
///     let holder = Holder::<'_, FooKey>::new_with(
///         new_with_closure::<FooKey, _>(|foo| Foo::default())
///     );
/// }
/// ```
pub struct Holder<'k, T> where T: Opaque + 'k {
  _pinned: PhantomPinned,
  inner: <T as Opaque>::Kind<'k>,
}

/// Helper trait for creating a [`Holder`].
///
/// This is necessary because closures don't work properly here.
///
/// See [`Holder::new_with`] for examples.
pub trait NewWith<'k, T: Opaque + 'k> {
    /// Creates a new `T::Kind` with an unbound lifetime.
    fn new_with<'a>(self) -> T::Kind<'a> where 'k: 'a, T::Kind<'a>: Sized;
}

impl<'k, T: Opaque + 'k, F> NewWith<'k, T> for F
where
    F: for<'a> FnOnce([&'a (); 0]) -> <T as Opaque>::Kind<'a>,
{
    fn new_with<'a>(self) -> T::Kind<'a> where 'k: 'a, T::Kind<'a>: Sized {
        self([])
    }
}

/// Helper for creating a [`Holder`] using a closure.
///
/// This only works if `K` is `'static`.
pub fn new_with_closure<K: Opaque, F>(f: F) -> F
where
    F: for<'a> FnOnce([&'a (); 0]) -> <K as Opaque>::Kind<'a>,
    for<'a> K::Kind<'a>: Sized,
{
    f
}

impl<'k, T> Holder<'k, T> where T: Opaque {
    /// Creates a new holder.
    ///
    /// # Examples
    ///
    /// Simple example:
    ///
    /// ```rust
    /// use core::cell::Cell;
    /// 
    /// use selfref::Holder;
    /// use selfref::new_with_closure;
    /// use selfref::opaque;
    ///
    /// #[derive(Default)]
    /// struct Foo<'a> {
    ///     foo: Cell<Option<&'a Foo<'a>>>,
    /// }
    ///
    /// struct FooKey;
    /// opaque! {
    ///     impl Opaque for FooKey {
    ///         type Kind<'a> = Foo<'a>;
    ///     }
    /// }
    ///
    /// fn main() {
    ///     // We can use a closure here, but we need to help the compiler.
    ///     let holder = Holder::<'_, FooKey>::new_with(
    ///         new_with_closure::<FooKey, _>(|foo| Foo::default())
    ///     );
    /// }
    /// ```
    ///
    /// Lifetime parameters:
    ///
    /// ```rust
    /// use core::cell::Cell;
    /// use core::marker::PhantomData;
    /// 
    /// use selfref::Holder;
    /// use selfref::NewWith;
    /// use selfref::opaque;
    ///
    /// struct Foo<'a, 'b: 'a> {
    ///     foo: Cell<Option<&'a Foo<'a, 'b>>>,
    ///     t: &'b str,
    /// }
    ///
    /// struct FooKey<'b>(PhantomData<&'b str>);
    /// opaque! {
    ///     impl['b] Opaque for FooKey<'b> {
    ///         type Kind<'a> = Foo<'a, 'b>;
    ///     }
    /// }
    ///
    /// fn main() {
    ///     struct FooBuilder<'b>(&'b str);
    ///     impl<'k, 'b: 'k> NewWith<'k, FooKey<'b>> for FooBuilder<'b> {
    ///         fn new_with<'a>(self) -> Foo<'a, 'b> where 'k: 'a {
    ///             Foo {
    ///                 foo: Default::default(),
    ///                 t: self.0,
    ///             }
    ///         }
    ///     }
    ///     let stack_array: [u8; 5] = *b"hello";
    ///     // a non-'static &str
    ///     let stack_str = core::str::from_utf8(&stack_array).unwrap();
    ///     let holder = Holder::new_with(FooBuilder(stack_str));
    /// }
    /// ```
    pub fn new_with<F>(f: F) -> Self
    where
        F: NewWith<'k, T>,  T::Kind<'k>: Sized
    {
        Self {
            // it is important that the constructor cannot observe 'k!
            inner: f.new_with(),
            _pinned: PhantomPinned
        }
    }
}

/// Helper trait for working with a [`Holder`].
///
/// This is necessary because closures don't work properly here.
///
/// See [`Holder::operate_in`] for examples.
pub trait OperateIn<'k, T: Opaque + 'k> {
    /// The value returned by this operation.
    type Out;
    /// Do this operation.
    fn operate_in<'a>(self, x: Pin<&'a T::Kind<'a>>) -> Self::Out where 'k: 'a;
}

impl<'k, T: Opaque + 'k, F, R> OperateIn<'k, T> for F
where F: for<'a> FnOnce(Pin<&'a T::Kind<'a>>) -> R {
    type Out = R;
    fn operate_in<'a>(self, x: Pin<&'a T::Kind<'a>>) -> R where 'k: 'a {
        self(x)
    }
}

/// Helper for working with a [`Holder`] using a closure.
///
/// This only works if `K` is `'static`.
pub fn operate_in_closure<K: Opaque, F, R>(f: F) -> F 
where F: for<'a> FnOnce(Pin<&'a <K as Opaque>::Kind<'a>>) -> R {
    f
}

impl<'k, T> Holder<'k, T> where T: Opaque {
    /// Operates in this (pinned) holder.
    ///
    /// This "unwraps" the value in this holder, and binds its lifetime to a
    /// new stack frame.
    ///
    /// # Examples
    ///
    /// Simple example:
    ///
    /// ```rust
    /// #![feature(pin_macro)]
    ///
    /// use core::cell::Cell;
    /// use core::pin::pin;
    /// 
    /// use selfref::Holder;
    /// use selfref::new_with_closure;
    /// use selfref::opaque;
    /// use selfref::operate_in_closure;
    ///
    /// #[derive(Default)]
    /// struct Foo<'a> {
    ///     foo: Cell<Option<&'a Foo<'a>>>,
    /// }
    ///
    /// struct FooKey;
    /// opaque! {
    ///     impl Opaque for FooKey {
    ///         type Kind<'a> = Foo<'a>;
    ///     }
    /// }
    ///
    /// fn main() {
    ///     let holder = pin!(Holder::<'_, FooKey>::new_with(
    ///         new_with_closure::<FooKey, _>(|foo| Foo::default())
    ///     ));
    ///     // Actually making our Foo refer to itself.
    ///     holder.as_ref().operate_in(
    ///         operate_in_closure::<FooKey, _, _>(|foo| {
    ///             foo.foo.set(Some(foo.get_ref()));
    ///         })
    ///     );
    /// }
    /// ```
    ///
    /// With lifetime parameters:
    ///
    /// ```rust
    /// #![feature(pin_macro)]
    ///
    /// use core::cell::Cell;
    /// use core::marker::PhantomData;
    /// use core::pin::Pin;
    /// use core::pin::pin;
    /// 
    /// use selfref::Holder;
    /// use selfref::NewWith;
    /// use selfref::OperateIn;
    /// use selfref::opaque;
    ///
    /// struct Foo<'a, 'b: 'a> {
    ///     foo: Cell<Option<&'a Foo<'a, 'b>>>,
    ///     t: &'b str,
    /// }
    ///
    /// struct FooKey<'b>(PhantomData<&'b str>);
    /// opaque! {
    ///     impl['b] Opaque for FooKey<'b> {
    ///         type Kind<'a> = Foo<'a, 'b>;
    ///     }
    /// }
    ///
    /// fn main() {
    ///     struct FooBuilder<'b>(&'b str);
    ///     impl<'k, 'b: 'k> NewWith<'k, FooKey<'b>> for FooBuilder<'b> {
    ///         fn new_with<'a>(self) -> Foo<'a, 'b> where 'k: 'a {
    ///             Foo {
    ///                 foo: Default::default(),
    ///                 t: self.0,
    ///             }
    ///         }
    ///     }
    ///     let stack_array: [u8; 5] = *b"hello";
    ///     // a non-'static &str
    ///     let stack_str = core::str::from_utf8(&stack_array).unwrap();
    ///     let holder = pin!(Holder::new_with(FooBuilder(stack_str)));
    ///     // Actually making our Foo refer to itself.
    ///     struct SetFooRef;
    ///     impl<'k, 'b: 'k> OperateIn<'k, FooKey<'b>> for SetFooRef {
    ///         type Out = ();
    ///         fn operate_in<'a>(self, foo: Pin<&'a Foo<'a, 'b>>)
    ///         where 'k: 'a {
    ///             foo.foo.set(Some(foo.get_ref()));
    ///         }
    ///     }
    ///     holder.as_ref().operate_in(SetFooRef);
    /// }
    /// ```
    pub fn operate_in<'i, F, R>(self: Pin<&'i Self>, f: F) -> R
    where 
        F: OperateIn<'k, T, Out=R>
    {
        /// Converts Pin<&'a T::Kind<'k>> to Pin<&'b T::Kind<'b>>
        unsafe fn upcast_dangling<'a, 'b, 'c, T: Opaque + 'c>(
            x: Pin<&'a T::Kind<'c>>,
        ) -> Pin<&'b T::Kind<'b>>
        where T::Kind<'c>: 'a {
            mem::transmute(x)
        }

        f.operate_in(unsafe {
            upcast_dangling::<'i, 'k, '_, T>
            (self.map_unchecked(|self_ref| {
                &self_ref.inner
            }))
        })
    }
}