#![doc(html_root_url = "https://docs.rs/singleton-trait/0.2.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] {}
// 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> {}

/*********************/
// 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.
 *
 * 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 usually 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(Clone, Copy)]
pub struct Erased<T> {
    _phantom: PhantomData<ManuallyDrop<T>>,
}
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>
     */
    #[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>
     */
    #[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> {
            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> {
    #[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) }
    }
}
impl<T> From<T> for Erased<T> {
    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> {
        // SAFETY: Deref on reference is pure
        unsafe { self.map(|r: &'a T| &*r) }
    }
}
impl<'a, 'b: 'a, T> Exists<&'a T> for Erased<&'b mut T> {
    #[inline(always)]
    fn erase(self) -> Erased<&'a T> {
        // SAFETY: Deref on reference is pure
        unsafe { self.map(|r: &'a mut T| &*r) }
    }
}
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> {
        // SAFETY: Deref on reference is pure
        unsafe { self.map(|r: &'a T| &*r) }
    }
}
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
        unsafe { self.map_borrow(|r: &'a &'b mut T| &**r) }
    }
}
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
        unsafe { self.map_borrow_mut(|r: &'a mut &'b mut T| &mut **r) }
    }
}

#[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);
    }
}