//
// Copyright (C) 2020 Nathan Sharp.
//
// This Source Code Form is subject to the terms of the Mozilla Public License,
// v. 2.0. If a copy of the MPL was not distributed with this file, You can
// obtain one at https://mozilla.org/MPL/2.0/
//
// This Source Code Form is "Incompatible With Secondary Licenses", as defined
// by the Mozilla Public License, v. 2.0.
//

#![feature(raw)]
#![feature(unsize)]

//! `thinbox` provides an alternative implementation of the standard Rust
//! [`Box`] container which has a pointer-sized representation in all cases.
//!
//! This property is mainly useful in niche Foreign-Function-Interface
//! use-cases. You should probably not use `thinbox` unless you wish to use
//! unsized types as opaque data crossing an FFI boundary.
//!
//! In particular, the author has found this crate useful in passing around Rust
//! closure types as *userdata* pointers in several C-language FFI projects.
//!
//! # Example
//! This use-case for [`ThinBox`] is achieved by leveraging the [`unsize`]
//! function to create a representation of a trait which is single-pointer-
//! sized.
//!
//! ```
//! use std::mem;
//! use thinbox::ThinBox;
//!
//! trait Animal {
//!     fn speak(&self);
//! }
//!
//! struct Dog {
//!     name: &'static str,
//!     loud: bool,
//! }
//!
//! impl Animal for Dog {
//!     fn speak(&self) {
//!         if self.loud {
//!             println!("WOOF!");
//!         } else {
//!             println!("woof!");
//!         }
//!     }
//! }
//!
//! fn main() {
//!     // Create a loud dog named "Woofers", but forget that he's a dog and that
//!     // he's loud by unsizing.
//!     let thin: ThinBox<dyn Animal> = ThinBox::unsize(Dog { name: "Woofers", loud: true });
//!
//!     // Move to a single-pointer-sized representation.
//!     let raw = ThinBox::into_raw(thin);
//!     assert_eq!(mem::size_of_val(&raw), mem::size_of::<*mut ()>());
//!
//!     // Restore the dynamic representation from the raw representation.
//!     let thin = unsafe { ThinBox::<dyn Animal>::from_raw(raw) };
//!
//!     // "WOOF!"
//!     thin.speak();
//! }
//! ```
//!
//! # Testing
//! `thinbox` has been tested with [Miri], which has revealed no violations of
//! [Stacked Borrows].
//!
//! # Implementation Details
//! [`ThinBox`] is currently implemented as a pointer to [`Box`]-managed memory
//! if `T` is sized and as a pointer to a [`Box`]-managed structure containing a
//! *vptr* and value if `T` is unsized. Since the *vptr* is not stored in the
//! [`Box`], [`ThinBox`] is thus single-pointer-sized in all cases.
//!
//! These implementation details are not guaranteed to be preserved across
//! releases.
//!
//! [`Box`]: std::boxed::Box
//! [Miri]: https://github.com/rust-lang/miri
//! [Stacked Borrows]: https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md
//! [`ThinBox`]: crate::ThinBox
//! [`unsize`]: crate::ThinBox::unsize

use std::borrow::Borrow;
use std::borrow::BorrowMut;
use std::fmt;
use std::hash::Hash;
use std::hash::Hasher;
use std::marker::PhantomData;
use std::marker::Unsize;
use std::mem;
use std::mem::ManuallyDrop;
use std::ops::Deref;
use std::ops::DerefMut;
use std::panic::UnwindSafe;
use std::ptr;
use std::ptr::NonNull;
use std::raw::TraitObject;

#[cfg(test)]
mod tests;

/// Returns `true` if `T` is unsized and `false` [otherwise].
///
/// # Notes
/// This method is required since Rust does not currently support negative or
/// mutually-exclusive trait bounds.
///
/// # Implementation Details
/// Unsized types are detected by examining the statically-known size of
/// `&mut T`.
///
/// [otherwise]: std::marker::Sized
#[inline(always)]
pub const fn is_unsized<T: ?Sized>() -> bool {
    mem::size_of::<&mut T>() == mem::size_of::<TraitObject>()
}

/// Allocates a `Box` and immediately switches to its [raw representation].
///
/// [raw representation]: std::boxed::Box::into_raw
fn box_into_raw<T>(value: T) -> *mut T {
    Box::into_raw(Box::new(value))
}

/// [Leaks] a boxed pointee.
///
/// [Leaks]: std::boxed::Box::leak
unsafe fn leak_boxed<'a, T: ?Sized>(ptr: *mut T) -> &'a mut T {
    Box::leak(Box::from_raw(ptr))
}

/// Deallocates a `Box` without dropping the boxed value.
fn forget_inner<T: ?Sized>(boxed: Box<T>) {
    mem::drop(unsafe { mem::transmute::<Box<T>, Box<ManuallyDrop<T>>>(boxed) });
}

/// Combines a value and its virtual-table pointer in a manner which supports
/// unsizing.
#[derive(Copy, Clone, Debug)]
#[repr(C)]
struct VCell<T: ?Sized> {
    /// The virtual-table pointer for `value`.
    vtable: NonNull<()>,
    /// The value contained in the cell.
    value: T,
}

/// A consistently-sized pointer type for heap allocation.
///
/// See the [crate documentation] for an example using `ThinBox`.
///
/// [crate documentation]: crate
pub struct ThinBox<T: ?Sized> {
    ptr: NonNull<()>,
    phantom_cell: PhantomData<Box<VCell<T>>>,
    phantom_value: PhantomData<Box<T>>,
}

impl<T: ?Sized> ThinBox<T> {
    unsafe fn from_boxed_vcell(boxed: *mut VCell<T>) -> Self {
        let ptr: TraitObject = mem::transmute_copy(&boxed);
        (*boxed).vtable = NonNull::new_unchecked(ptr.vtable);
        Self::from_raw(ptr.data)
    }

    unsafe fn from_boxed_value(boxed: *mut T) -> Self {
        Self::from_raw(mem::transmute_copy(&boxed))
    }

    unsafe fn to_vcell_ptr(raw: *mut ()) -> *mut VCell<T> {
        mem::transmute_copy(&TraitObject { vtable: *(raw as *const *mut ()), data: raw })
    }

    #[inline(always)]
    unsafe fn to_value_ptr(raw: *mut ()) -> *mut T {
        mem::transmute_copy(&raw)
    }

    unsafe fn into_vcell_ptr(thin: Self) -> *mut VCell<T> {
        Self::to_vcell_ptr(Self::into_raw(thin))
    }

    #[inline(always)]
    unsafe fn into_value_ptr(thin: Self) -> *mut T {
        Self::to_value_ptr(Self::into_raw(thin))
    }

    unsafe fn as_vcell_ptr(thin: &Self) -> *mut VCell<T> {
        Self::to_vcell_ptr(thin.ptr.as_ptr())
    }

    #[inline(always)]
    unsafe fn as_value_ptr(thin: &Self) -> *mut T {
        Self::to_value_ptr(thin.ptr.as_ptr())
    }

    /// Creates a new `ThinBox` by unsizing a value and placing it on the heap.
    pub fn unsize<U: Unsize<T>>(value: U) -> Self {
        unsafe {
            Self::from_boxed_vcell(Box::into_raw(Box::new(VCell {
                vtable: NonNull::dangling(),
                value,
            }) as Box<VCell<T>>))
        }
    }

    /// Recovers `ThinBox` ownership of a pointee.
    ///
    /// # Safety
    /// * `raw` must be result of [`Box::<U>::into_raw`]` as *mut ()` or
    ///   [`ThinBox::<U>::into_raw`] where `U` safe to [`transmute`] into `T`.
    /// * The alignment requirements of `T` must not be more strict than those
    ///   of `U`.
    /// * It must be generally safe to dereference `raw`, keeping in mind that
    ///   `raw` does not actually point to `()` and does not necessarily even
    ///   point to a `U`.
    ///
    /// The first requirement implies that:
    /// * `U: `[`Sized`] and/or `U` is `T`.
    /// * `raw` is neither null nor [dangling].
    ///
    /// Furthermore, support for [`Box::<U>::into_raw`] is *not* guaranteed to
    /// be preserved across major versions of `thinbox`.
    ///
    /// [`Box::<U>::into_raw`]: std::boxed::Box::into_raw
    /// [dangling]: std::ptr::NonNull::dangling
    /// [`Sized`]: std::marker::Sized
    /// [`ThinBox::<T>::into_raw`]: crate::ThinBox::into_raw
    /// [`ThinBox::<U>::into_raw`]: crate::ThinBox::into_raw
    /// [`transmute`]: std::mem::transmute
    pub unsafe fn from_raw(raw: *mut ()) -> Self {
        debug_assert!(!raw.is_null());

        Self {
            ptr: NonNull::new_unchecked(raw),
            phantom_cell: PhantomData,
            phantom_value: PhantomData,
        }
    }

    /// Converts the `ThinBox` to a single-pointer-sized representation.
    ///
    /// # Notes
    /// It is not safe to dereference this representation. The type of the
    /// pointee depends not only on `T` but also on whether or not `T` is
    /// unsized.
    #[inline(always)]
    pub fn into_raw(thin: Self) -> *mut () {
        let ptr = thin.ptr.as_ptr();
        mem::forget(thin);
        ptr
    }

    /// Obtains a raw pointer to the boxed value.
    ///
    /// The pointee remains owned by the `ThinBox`. If you wish to relinquish
    /// ownership, use [`into_raw`].
    ///
    /// # Notes
    /// This method returns a raw mutable pointer, which is dangerous to use.
    /// However `ThinBox` is guaranteed to never store an internal reference to
    /// its owned value so dereferencing this pointer does not *necessarily*
    /// cause undefined-behavior.
    ///
    /// [`into_raw`]: crate::ThinBox::into_raw
    pub fn as_ptr(thin: &Self) -> *mut T {
        unsafe {
            if is_unsized::<T>() {
                &mut (*Self::as_vcell_ptr(thin)).value
            } else {
                Self::as_value_ptr(thin)
            }
        }
    }

    /// Leaks the contained value in a manner similar to [`Box::leak`].
    ///
    /// Unlike [`Box::leak`], if `T` is unsized it is *not* valid to pass the
    /// returned reference to [`Box::from_raw`] or [`ThinBox::from_raw`].
    ///
    /// [`Box::leak`]: std::boxed::Box::leak
    /// [`ThinBox::from_raw`]: crate::ThinBox::from_raw
    pub fn leak<'a>(thin: Self) -> &'a mut T {
        unsafe {
            if is_unsized::<T>() {
                &mut leak_boxed(Self::into_vcell_ptr(thin)).value
            } else {
                leak_boxed(Self::into_value_ptr(thin))
            }
        }
    }

    /// Moves the owned value into `dest` by transmuting into `U`.
    ///
    /// # Notes
    /// The value pointed to by `dest`, if any, is *not* dropped.
    /// The owned value of the `ThinBox` does not need to be properly aligned as
    /// a `U`.
    ///
    /// # Safety
    /// Immediate undefined behavior occurs if `U` is larger in size than the
    /// owned value or if `dest` is not valid for writes. Otherwise any
    /// undefined behavior is deferred to later operations which dereference
    /// `dest` and thereby observe the result of the transmutation.
    pub unsafe fn transmute_into<U>(thin: Self, dest: *mut U) {
        if is_unsized::<T>() {
            let boxed = Box::from_raw(Self::into_vcell_ptr(thin));
            dest.write(ptr::read_unaligned(&boxed.as_ref().value as *const T as *const U));
            forget_inner(boxed);
        } else {
            let boxed = Box::from_raw(Self::into_value_ptr(thin));
            dest.write(ptr::read_unaligned(boxed.as_ref() as *const T as *const U));
            forget_inner(boxed);
        }
    }
}

impl<T> ThinBox<T> {
    /// Creates a new `ThinBox` by moving a sized value to the heap.
    ///
    /// # Notes
    /// Doing this passes up your opportunity to coerce the value to an unsized
    /// type, thereby defeating most of the usefulness of `ThinBox`. You should
    /// strongly consider using [`Box`] instead if you are not constrained by
    /// some other library which consumes instances of [`ThinBox`].
    pub fn new(value: T) -> Self {
        unsafe { Self::from_boxed_value(box_into_raw(value)) }
    }

    /// Converts a sized [`Box`] into a `ThinBox`. This operation is zero-cost.
    ///
    /// [`Box`]: std::boxed::Box
    #[inline]
    pub fn from_box(boxed: Box<T>) -> Self {
        unsafe { ThinBox::from_boxed_value(Box::into_raw(boxed)) }
    }

    /// Converts a sized `ThinBox` into a [`Box`]. This operation is zero-cost.
    ///
    /// [`Box`]: std::boxed::Box
    #[inline]
    pub fn into_box(thin: Self) -> Box<T> {
        unsafe { Box::from_raw(ThinBox::into_value_ptr(thin)) }
    }

    /// Moves the owned value out of the sized `ThinBox`.
    pub fn into_inner(thin: Self) -> T {
        unsafe {
            if is_unsized::<T>() {
                Box::from_raw(Self::into_vcell_ptr(thin)).value
            } else {
                *Box::from_raw(Self::into_value_ptr(thin))
            }
        }
    }
}

impl<T: ?Sized> AsMut<T> for ThinBox<T> {
    #[inline]
    fn as_mut(&mut self) -> &mut T {
        unsafe { &mut *Self::as_ptr(self) }
    }
}

impl<T: ?Sized> AsRef<T> for ThinBox<T> {
    #[inline]
    fn as_ref(&self) -> &T {
        unsafe { &*Self::as_ptr(self) }
    }
}

impl<T: ?Sized> Borrow<T> for ThinBox<T> {
    #[inline]
    fn borrow(&self) -> &T {
        self.as_ref()
    }
}

impl<T: ?Sized> BorrowMut<T> for ThinBox<T> {
    #[inline]
    fn borrow_mut(&mut self) -> &mut T {
        self.as_mut()
    }
}

impl<T: Clone> Clone for ThinBox<T> {
    fn clone(&self) -> Self {
        unsafe { Self::from_boxed_value(box_into_raw((*Self::as_value_ptr(self)).clone())) }
    }
}

impl<T: fmt::Debug + ?Sized> fmt::Debug for ThinBox<T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        self.as_ref().fmt(f)
    }
}

impl<T: ?Sized> Deref for ThinBox<T> {
    type Target = T;

    #[inline]
    fn deref(&self) -> &Self::Target {
        self.as_ref()
    }
}

impl<T: ?Sized> DerefMut for ThinBox<T> {
    #[inline]
    fn deref_mut(&mut self) -> &mut Self::Target {
        self.as_mut()
    }
}

impl<T: fmt::Display + ?Sized> fmt::Display for ThinBox<T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        self.as_ref().fmt(f)
    }
}

impl<T: ?Sized> Drop for ThinBox<T> {
    fn drop(&mut self) {
        unsafe {
            if is_unsized::<T>() {
                Box::from_raw(Self::as_vcell_ptr(self));
            } else {
                Box::from_raw(Self::as_value_ptr(self));
            }
        }
    }
}

impl<T> From<T> for ThinBox<T> {
    fn from(value: T) -> Self {
        Self::new(value)
    }
}

impl<T: Hash + ?Sized> Hash for ThinBox<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.as_ref().hash(state)
    }
}

impl<T> fmt::Pointer for ThinBox<T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        self.ptr.fmt(f)
    }
}

impl<T: UnwindSafe + ?Sized> UnwindSafe for ThinBox<T> {}
unsafe impl<T: Send + ?Sized> Send for ThinBox<T> {}
unsafe impl<T: Sync + ?Sized> Sync for ThinBox<T> {}