singleton_trait/

lib.rs

#![doc(html_root_url = "https://docs.rs/singleton-trait/0.4.0")]
#![no_std]

use core::cell::{Cell, UnsafeCell};
use core::marker::PhantomData;
use core::mem::ManuallyDrop;

/*******************/
/* Singleton trait */
/*******************/

/**
 * This trait denotes a type which has at most one logical identity at all times.
 * This is sufficient to make borrowing decisions based only on the type, without
 * regards to value identity.
 *
 * Implementers of the trait must uphold this contract, that any point
 * during the execution of the program, there is at most one accessible
 * logical value of this type. Much like how re-borrowings can
 * make a type inaccessible, it is allowed for there to be more than one
 * such binding, if the others are inaccessible due to unique borrowing.
 *
 * Some examples would include:
 * * A type with exactly one instance constructed during the main method
 * * A type with only one static instance (including one wrapped behind e.g. a Mutex)
 * * An uninhabited type
 * * A type which is constructed with a unique lifetime brand
 *
 * Any type which has a public constructor cannot meet this,
 * Some non-examples include ZSTs like ()
 * and the Exists<T> struct in this crate (when T is not a Singleton itself)
 * Any type which implements Clone
 */
pub unsafe trait Singleton {}

/*****************/
/* Blanket Impls */
/*****************/

// Anything which is backed by at least one T
// can be given an implementation
//
// This can be witnessed by a function
// S -> T where T is a singleton

// SAFETY:
// These types are all backed by exactly one, unique T
unsafe impl<T: Singleton> Singleton for Cell<T> {}
unsafe impl<T: Singleton> Singleton for UnsafeCell<T> {}
unsafe impl<T: Singleton> Singleton for [T; 1] {}
// Not many other interesting cases, but some like Box require alloc

// SAFETY:
// 1. Every mutable reference points to a value of T
// 2. No two mutable references alias
// 3. By the contract of Singleton for T, there is at most one logical value of T
unsafe impl<'a, T: Singleton> Singleton for &'a mut T {}
// SAFETY:
// Exists<T> witnesses strict ownership of a value of type T
unsafe impl<'a, T: Singleton> Singleton for Erased<T> {}

/*******************/
/* Single-threaded */
/*******************/

/**
 * A type `T` implements SingleThread if at any time there
 * is a single thread from which all values/references to
 * values of this type may be accessed.
 *
 * Usually, it is sufficient that `T` is `!Sync` and `Singleton`.
 *
 * Since Sending `T` denies access in the original thread, this
 * property is maintained regardless of Sendability.
 */
pub unsafe trait SingleThread { }

/*****************/
/* Blanket Impls */
/*****************/

// SAFETY:
// These cases are structurally Sync
unsafe impl<T: SingleThread> SingleThread for Cell<T> {}
unsafe impl<T: SingleThread> SingleThread for [T; 1] {}
// other interesting cases generally require alloc, or could be changed.

// SAFETY:
// From `&&mut T` we can produce `&T`, and by the contract for
// T: SingleThread, this is locked to one thread, so
// we can assume that `&&mut T` is also locked to one thread
unsafe impl<'a, T: SingleThread> SingleThread for &'a mut T {}
unsafe impl<'a, T: SingleThread> SingleThread for &'a T {}

// SAFETY:
// Exists<T> witnesses strict ownership of a value of type T
unsafe impl<'a, T: SingleThread> SingleThread for Erased<T> {}

/*********************/
/* Phantom existence */
/*********************/

/**
 * The Erased struct witnesses the logical ownership of a value of type T
 * while remaining zero-sized. This can be used for ghost proofs of soundness.
 *
 * Erased<T> should be thought of a zero-sized owner of T. It is useful for inclusion
 * in data structures where the value might not be eliminated by the compiler.
 * It likely is not necessary for short-lived data.
 *
 * NOTE: drop implementations will never be called, as Exists<T> guarantees the existence
 * of a valid T, which might not be true if they were called. On the other hand, since
 * it does not hold a T, it cannot drop T when it is itself dropped
 *
 * Secondly, keep in mind that while Erased<T> serves as evidence, it does not include
 * sufficient provenance for Stacked Borrows or LLVM, and so it is not techinically sound
 * to recover a reference `&T` from an `Exists<&T>` and `*mut T` or `&UnsafeCell<T>`
 * even when T is Singleton, but this could be possible if T is zero-sized.
 * Because of the missing provenance, creating a reference this way could invalidate
 * the original reference on which this Exists instance was based.
 */
#[derive(Copy)]
pub struct Erased<T> {
    _phantom: PhantomData<ManuallyDrop<T>>,
}
impl<T: Copy> Clone for Erased<T> {
    #[inline(always)]
    fn clone(&self) -> Self {
        *self
    }
}
impl<T> Erased<T> {
    #[inline(always)]
    pub const fn new(t: T) -> Self {
        let _ = ManuallyDrop::new(t);
        // SAFETY: we have taken ownership of a T value above
        unsafe { Self::new_unchecked() }
    }

    /**
     * This function constructs a value of Erased<T> without taking logical ownership of a T.
     *
     * # Safety
     *
     * Constructing this asserts that there is a value of type T which has been leaked, or
     * in which it is guaranteed that the program behaves the same up to observation as if a
     * zero-sized copy of T were being passed.
     *
     */
    #[inline(always)]
    pub const unsafe fn new_unchecked() -> Self {
        Erased {
            _phantom: PhantomData,
        }
    }

    /**
     * Turns a &Erased<T> into an Erased<&T>
     *
     * This can be especially useful when storing
     * the Erased<T> inside another wrapper type
     *
     * ```
     * # use singleton_trait::Erased;
     * use core::cell::RefCell;
     * struct Token;
     * let lock = RefCell::new(Erased::new(Token));
     *
     * let locked = lock.borrow();
     * let _: Erased<&Token> = locked.borrow();
     * ```
     */
    #[inline(always)]
    pub fn borrow(&self) -> Erased<&T> {
        // Safety:
        // the identity function is pure
        unsafe { self.map_borrow(|r| r) }
    }

    /**
     * Turns a &mut Erased<T> into an Erased<&mut T>
     *
     * This can be especially useful when storing
     * the Erased<T> inside another wrapper type
     *
     * ```
     * # use singleton_trait::Erased;
     * use core::cell::RefCell;
     * struct Token;
     * let lock = RefCell::new(Erased::new(Token));
     *
     * let mut locked = lock.borrow_mut();
     * let _: Erased<&mut Token> = locked.borrow_mut();
     * ```
     */
    #[inline(always)]
    pub fn borrow_mut(&mut self) -> Erased<&mut T> {
        // Safety:
        // the identity function is pure
        unsafe { self.map_borrow_mut(|r| r) }
    }

    /**
     * Maps a function on the inside of the Erased field.
     *
     * # Safety
     *
     * Due to the strictness guarantees, the passed closure must not cause any visible
     * side effects, including side effects caused by owning R
     */
    #[inline(always)]
    pub unsafe fn map<R, F: FnOnce(T) -> R>(self, _: impl Exists<F>) -> Erased<R> {
        // Safety:
        //
        // By the contract for the passed function, this is equivalent to calling it on the value of type T
        Erased::<R>::new_unchecked()
    }

    /**
     * Maps a function on the borrow of the Erased field.
     *
     * # Safety
     *
     * Due to the strictness guarantees, the passed closure must not cause any visible
     * side effects, including side effects caused by owning R
     */
    #[inline(always)]
    pub unsafe fn map_borrow<'a, R, F: FnOnce(&'a T) -> R>(
        &'a self,
        _: impl Exists<F>,
    ) -> Erased<R> {
        // Safety:
        //
        // By the contract for the passed function, this is equivalent to calling it on the borrow of T
        Erased::<R>::new_unchecked()
    }
    /**
     * Maps a function on the mutable borrow of the Erased field.
     *
     * # Safety
     *
     * Due to the strictness guarantees, the passed closure must not cause any visible
     * side effects, including side effects caused by owning R
     */
    #[inline(always)]
    pub unsafe fn map_borrow_mut<'a, R, F: FnOnce(&'a mut T) -> R>(
        &'a mut self,
        _: impl Exists<F>,
    ) -> Erased<R> {
        // Safety:
        //
        // By the contract for the passed function, this is equivalent to calling it on the mutable borrow of T
        Erased::<R>::new_unchecked()
    }

    /**
     * Fallback function which converts this Erased value into an Exists
     * implementer.
     *
     * This exists because we cannot allow general trait implementations
     * due to coherence rules, but we can't be sufficiently flexible in
     * trait implementations due to a lack of subtyping constraints or
     * trait covariance, which would mean references would be too inflexible
     */
    #[inline(always)]
    pub fn exists(self) -> impl Exists<T> {
        struct Internal<T> {
            er: Erased<T>,
        }
        impl<T> Exists<T> for Internal<T> {
            #[inline(always)]
            fn erase(self) -> Erased<T> {
                self.er
            }
        }
        Internal { er: self }
    }
}
impl<T> Erased<Erased<T>> {
    /**
     * An erased erased value can be flattened into a single erasure,
     * since Erased<T> is notionally equivalent to T
     */
    #[inline(always)]
    pub fn flatten(self) -> Erased<T> {
        // SAFETY:
        //
        // By existential induction since the constructor for Erased is pure
        unsafe { Erased::<T>::new_unchecked() }
    }
}
impl<'a, T> Erased<&'a mut T> {
    /**
     * Re-borrow this erased mutable borrow. Usually
     * this is implicit in Rust, but not for general wrappers.
     * This can be seen as a "clone" method for mutable borrows,
     * as it allows you to retain the erased borrow after the
     * end of the lifetime.
     *
     * The Exists trait can perform this conversion automatically.
     *
     * ```
     * # use singleton_trait::Erased;
     * struct Token;
     * fn recursively(mut b: Erased<&mut Token>) {
     *  recursively(b.reborrow());
     *  recursively(b);
     * }
     * ```
     */
    #[inline(always)]
    pub fn reborrow<'b>(&'b mut self) -> Erased<&'b mut T> {
        // SAFETY
        //
        // Refs and derefs on reference types are pure
        unsafe { self.map_borrow_mut(|r: &'b mut &'a mut T| &mut **r) }
    }

    /**
     * Borrow this erased mutable borrow as immutable.
     * This is effectively a Deref method under Erased
     *
     * The Exists trait can perform this conversion automatically.
     *
     * ```
     * # use singleton_trait::Erased;
     * struct Lock;
     * fn use_lock(write: Erased<&mut Lock>) {
     *   read_from(write.read());
     * }
     *
     * fn read_from(read: Erased<&Lock>) { }
     * ```
     */
    #[inline(always)]
    pub fn read<'b>(&'b self) -> Erased<&'b T> {
        // SAFETY
        //
        // Refs and derefs on reference types are pure
        unsafe { self.map_borrow(|r: &'b &'a mut T| &**r) }
    }

    /**
     * Consume this erased mutable borrow to
     * turn it into an immutable borrow.
     *
     * The Exists trait can perform this conversion automatically.
     *
     * See also `read`, which is often more useful.
     * This method uses the full inner lifetime
     * without needing to borrow.
     * ```
     * # use singleton_trait::Erased;
     * struct Lock;
     * struct MutWrapper<'a> (Erased<&'a mut Lock>);
     * struct Wrapper<'a> (Erased<&'a Lock>);
     * impl<'a> MutWrapper<'a> {
     *   pub fn into_read(self) -> Wrapper<'a> {
     *      Wrapper(self.0.into_shared())
     *   }
     * }
     *
     * ```
     */
    #[inline(always)]
    pub fn into_shared(self) -> Erased<&'a T> {
        // SAFETY
        //
        // Refs and derefs on reference types are pure
        unsafe { self.map(|r: &'a mut T| &*r) }
    }
}
impl<T> From<T> for Erased<T> {
    #[inline(always)]
    fn from(t: T) -> Self {
        Self::new(t)
    }
}
/**
 * The Exists trait is intended to be used with `impl`, to denote
 * an argument where the existence of a value is sufficient as an argument
 *
 *
 */
pub trait Exists<T: Sized> {
    fn erase(self) -> Erased<T>;
}
impl<T> Exists<T> for T {
    #[inline(always)]
    fn erase(self) -> Erased<T> {
        self.into()
    }
}

impl<'a, 'b: 'a, T> Exists<&'a T> for Erased<&'b T> {
    #[inline(always)]
    fn erase(self) -> Erased<&'a T> {
        self
    }
}
impl<'a, 'b: 'a, T> Exists<&'a T> for Erased<&'b mut T> {
    #[inline(always)]
    fn erase(self) -> Erased<&'a T> {
        self.into_shared()
    }
}
impl<'a, 'b: 'a, T> Exists<&'a mut T> for Erased<&'b mut T> {
    #[inline(always)]
    fn erase(self) -> Erased<&'a mut T> {
        // SAFETY: Deref on reference is pure
        unsafe { self.map(|r: &'a mut T| &mut *r) }
    }
}
impl<'a, 'b, T> Exists<&'a T> for &'a Erased<&'b T> {
    #[inline(always)]
    fn erase(self) -> Erased<&'a T> {
        *self
    }
}
impl<'a, 'b: 'a, T> Exists<&'a T> for &'a Erased<&'b mut T> {
    #[inline(always)]
    fn erase(self) -> Erased<&'a T> {
        // SAFETY: Deref on reference is pure
        self.read()
    }
}
impl<'a, 'b: 'a, T> Exists<&'a mut T> for &'a mut Erased<&'b mut T> {
    #[inline(always)]
    fn erase(self) -> Erased<&'a mut T> {
        // SAFETY: Deref on reference is pure
        self.reborrow()
    }
}

#[cfg(test)]
mod tests {
    use crate::*;

    // this test should fail to compile if we're missing impls
    // that can coerce between different lifetimes
    #[test]
    fn test_impls() {
        /* Invariant type parameter to strictly test subtyping */
        struct NonCopy;
        impl Drop for NonCopy {
            fn drop(&mut self) {}
        }
        struct Guard<'a>(PhantomData<fn(&'a ()) -> &'a ()>, &'a NonCopy);

        fn takes_ref<'a>(_: &Guard<'a>, _: impl Exists<&'a ()>) {}
        fn takes_mut<'a>(_: &Guard<'a>, _: impl Exists<&'a mut ()>) {}

        let nc = NonCopy;
        let guard = Guard(PhantomData, &nc);

        let er = Erased::new(&());
        takes_ref(&guard, er);

        let mut x = ();
        let er = Erased::new(&mut x);
        takes_ref(&guard, er);

        let mut x = ();
        let er = Erased::new(&mut x);
        takes_mut(&guard, er);
    }
}