//
// Copyright (C) 2023 Nathan Sharp.
//
// This file is available under either the terms of the Apache License, Version
// 2.0 or the MIT License, at your discretion.
//

#![no_std]
#![feature(extern_types)]
#![feature(layout_for_ptr)]
#![feature(ptr_metadata)]
#![feature(unsize)]

//! `fat_type` provides the type [`Fat<T, U>`], which combines a value of type
//! `U` with the metadata needed to construct references to it as a `T`.
//!
//! Because the metadata is stored with the value instead of in references,
//! [`Fat<T>`] is [`Thin`]. This property is mainly useful in niche
//! foreign-function-interface use-cases or in memory-constrained environments.
//! As such, this library is [`no_std`].
//!
//! # See Also
//! Signifiant additional documentation is provided on the [`Fat`] type.
//!
//! # License
//! `fat_type` is licensed under the terms of the
//! [Apache License, Version 2.0][Apache2] or the [MIT License][MIT].
//!
//! # Development
//! `fat_type` is developed at [GitLab].
//!
//! This crate is rigorously tested with [Miri] and fully compliant with
//! [strict pointer provenance].
//!
//! [`no_std`]: https://docs.rust-embedded.org/book/intro/no-std.html
//! [Apache2]: https://www.apache.org/licenses/LICENSE-2.0
//! [GitLab]: https://gitlab.com/nwsharp/fat_type
//! [MIT]: https://opensource.org/licenses/MIT
//! [Miri]: https://github.com/rust-lang/miri
//! [strict pointer provenance]: https://doc.rust-lang.org/nightly/std/ptr/index.html#strict-provenance
//! [`Thin`]: core::ptr::Thin

#[cfg(test)]
mod tests;

use core::alloc::Layout;
use core::any::type_name;
use core::borrow::{Borrow, BorrowMut};
use core::cmp::Ordering;
use core::fmt::{self, Debug, Display, Formatter};
use core::hash::{Hash, Hasher};
use core::iter::IntoIterator;
use core::marker::{PhantomData, Unsize};
use core::ops::{Deref, DerefMut, Index, IndexMut};
use core::panic::{RefUnwindSafe, UnwindSafe};
use core::ptr::{self, NonNull, Pointee};

// Wrapper type to make Pointee::Metadata UnwindSafe and Debug.
// See https://github.com/rust-lang/rust/issues/86235.
#[repr(transparent)]
struct Metadata<T: ?Sized>(<T as Pointee>::Metadata);

impl<T: ?Sized> Clone for Metadata<T> {
    fn clone(&self) -> Self {
        Self(self.0)
    }
}

impl<T: ?Sized> Debug for Metadata<T>
where <T as Pointee>::Metadata: Debug
{
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        self.0.fmt(f)
    }
}

impl<T: ?Sized> Copy for Metadata<T> {}
impl<T: ?Sized> UnwindSafe for Metadata<T> {}
impl<T: ?Sized> RefUnwindSafe for Metadata<T> {}

extern "C" {
    /// A value with an erased type. Values of this type cannot be created or
    /// accessed and support no operations.
    ///
    /// As such, this type implements all of the standard [auto traits]. As a
    /// convenience it also implements the [`Debug`] trait, which simply prints
    /// `"Erased"`.
    ///
    /// # Example
    /// ```compile_fail,E0277
    /// # use fat_type::{Erased, Fat};
    /// # use core::fmt::Debug;
    /// # use core::mem;
    /// let fat1 = Fat::<dyn Debug, u32>::new(42);
    /// let thin1: &mut Fat<dyn Debug, Erased> = Fat::erase_mut(&mut fat1);
    ///
    /// let fat2 = Fat::<dyn Debug, u64>::new(43);
    /// let thin2: &mut Fat<dyn Debug, Erased> = Fat::erase_mut(&mut fat2);
    ///
    /// // Even though thin1 and thin2 have the same type, we can't swap them
    /// // because Erased is an extern type.
    /// mem::swap(thin1, thin2); //E0227
    /// ```
    ///
    /// [auto traits]: https://doc.rust-lang.org/reference/special-types-and-traits.html#auto-traits
    /// [`Debug`]: core::fmt::Debug
    pub type Erased;
}

impl Debug for Erased {
    /// Prints `"Erased"`. The value is not accessed in any way.
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        write!(f, "Erased")
    }
}

impl RefUnwindSafe for Erased {}
impl UnwindSafe for Erased {}
impl Unpin for Erased {}
unsafe impl Send for Erased {}
unsafe impl Sync for Erased {}

/// A type which combines a value with the metadata used to construct references
/// to it.
///
/// A value of the type `Fat<T: ?Sized, U: `[`Unsize<T>`]`>`, created by
/// [`new`], supports pointer-sized "thin" references `&Fat<T>` (via
/// [`erase_ref`]) and `&mut Fat<T>` (via [`erase_mut`]), even when `T`
/// is not [`Thin`], such as in the case of [slices] or [trait objects].
///
/// # Terminology
/// * The value of type `T` is referred to as the *unsized referent*.
/// * The value of type `U` is referred to as the *sized referent*.
/// * `Fat<T>` references are produced from `Fat<T, U>` references through
///   *erasure*, where [`Erased`] replaces `U`. The original `U` is referred to
///   as the *un-erased type*.
///
/// # Auto-Deref
/// `Fat<T>` is [`Deref`] and [`DerefMut`] as `T`. All operations are provided
/// as [associated functions] to prevent name collisions. This means that you
/// use references to `Fat<T>` as-if they were to `T`.
///
/// # Safety
/// * Incoherent tyes can be named but cannot be constructed by safe code
///   because [`new`] is only provided when `U: `[`Unsize<T>`].
/// * The ability to incoherently mutate metadata is prevented by [`Erased`],
///   which is a fully-opaque [extern type].
/// * There is no constructor to create a bare `Fat<T>`. As such, the type can
///   only exist behind a reference, which can only safely be created by
///   [`erase_ref`] and [`erase_mut`].
///
/// # Example
/// ```
/// # use core::mem;
/// # use core::fmt::Debug;
/// # use fat_type::Fat;
/// // References to wrapped trait objects are smaller than the bare references.
/// assert!(mem::size_of::<&Fat<dyn Debug>>() < mem::size_of::<&dyn Debug>());
///
/// // References to wrapped trait objects are, in fact, pointer sized.
/// assert!(mem::size_of::<&Fat<dyn Debug>>() == mem::size_of::<&()>());
/// ```
///
/// # See Also
/// * [`new`] -- To create a `Fat` value.
/// * [`erase_ref`], [`erase_mut`] -- To obtain a thin reference from a `Fat`
///   reference.
///
/// [associated functions]: https://doc.rust-lang.org/book/ch05-03-method-syntax.html#associated-functions
/// [`Deref`]: core::ops::Deref
/// [`DerefMut`]: core::ops::DerefMut
/// [`erase_ref`]: Self::erase_ref
/// [`erase_mut`]: Self::erase_mut
/// [extern type]: https://github.com/rust-lang/rfcs/blob/master/text/1861-extern-types.md
/// [`new`]: Self::new
/// [Sized]: core::marker::Sized
/// [slices]: https://doc.rust-lang.org/std/primitive.slice.html
/// [`Thin`]: core::ptr::Thin
/// [trait objects]: https://doc.rust-lang.org/std/keyword.dyn.html
/// [unsized]: core::marker::Sized
#[repr(C)]
pub struct Fat<T: ?Sized, U: ?Sized = Erased> {
    _phantom: PhantomData<T>,
    metadata: Metadata<T>,
    data: U,
}

impl<T: ?Sized, U: Unsize<T>> Fat<T, U> {
    /// Constructs a new `Fat` value with [metadata] from unsizing `value` as a
    /// `T`.
    ///
    /// # Example
    /// ```
    /// # use fat_type::Fat;
    /// # use core::fmt::Debug;
    /// # use core::mem;
    /// let fat = Fat::<dyn Debug, u8>::new(42);
    /// let thin: &Fat<dyn Debug> = Fat::erase_ref(&fat);
    /// assert_eq!(mem::size_of_val(&thin), mem::size_of::<&()>());
    ///
    /// dbg!(thin); // 42
    /// ```
    ///
    /// [metadata]: core::ptr::Pointee::Metadata
    #[must_use]
    pub fn new(value: U) -> Self {
        Self { _phantom: PhantomData, metadata: Metadata(ptr::metadata(&value as &T)), data: value }
    }
}

impl<T: ?Sized, U> Fat<T, U> {
    /// Extracts the [sized referent], discarding the [associated metadata].
    ///
    /// [associated metadata]: core::ptr::Pointee
    /// [sized referent]: Fat#terminology
    #[must_use]
    pub fn into_inner(fat: Self) -> U {
        fat.data
    }

    /// Obtains an immutable reference to the [sized referent].
    ///
    /// [sized referent]: Fat#terminology
    #[must_use]
    pub fn inner_ref(fat: &Self) -> &U {
        &fat.data
    }

    /// Obtains a mutable reference to the [sized referent].
    ///
    /// [sized referent]: Fat#terminology
    #[must_use]
    pub fn inner_mut(fat: &mut Self) -> &mut U {
        &mut fat.data
    }
}

impl<T: ?Sized> Fat<T> {
    /// Obtains a pointer to the `Fat<T>` containing the specified
    /// [unsized referent].
    ///
    /// # Safety
    /// `referent` must be the unsized referent of some `Fat<T>`, such as the
    /// reference obtained from `deref`.
    ///
    /// # Safety Considerations
    /// [`core::ptr::NonNull`] provides methods that treat the contained pointer
    /// as-if it were a pointer to mutable data. Use of these operations may
    /// lead to undefined behavior.
    ///
    /// # Strict Pointer Provenance
    /// The [provenance] of the returned pointer is inherited from the argument.
    ///
    /// [provenance]: https://doc.rust-lang.org/nightly/std/ptr/index.html#strict-provenance
    /// [unsized referent]: Fat#terminology
    #[must_use]
    pub unsafe fn container_of(referent: *const T) -> NonNull<Self> {
        // Safety: Caller required to uphold invariants.
        let offset = unsafe { Self::layout_for(&ptr::metadata(referent)).1 };

        // Safety: The result of the subtraction is non-null and inbounds because
        //         `referent` is required to be the data inside of a`Fat<T, U>`.
        unsafe { NonNull::new_unchecked((referent as *const u8).sub(offset) as *mut Self) }
    }
}

impl<T: ?Sized, U: ?Sized> Fat<T, U> {
    /// Obtains a thin immutable reference by erasing the type of the [sized
    /// referent].
    ///
    /// [sized referent]: Fat#terminology
    #[inline(always)] // nop
    #[must_use]
    pub fn erase_ref(fat: &Self) -> &Fat<T> {
        // Safety: `Erased` is an extern type with no operations.
        unsafe { &*(fat as *const Self as *const Fat<T>) }
    }

    /// Obtains a thin mutable reference by erasing the type of the [sized
    /// referent].
    ///
    /// [sized referent]: Fat#terminology
    #[inline(always)] // nop
    #[must_use]
    pub fn erase_mut(fat: &mut Self) -> &mut Fat<T> {
        // Safety: `Erased` is an extern type with no operations.
        unsafe { &mut *(fat as *mut Self as *mut Fat<T>) }
    }

    /// Returns a thin pointer to the [sized referent], suitable for use with
    /// [`core::ptr::from_raw_parts`].
    ///
    /// # Safety Considerations
    /// [`core::ptr::NonNull`] provides methods that treat the contained pointer
    /// as-if it were a pointer to mutable data. Use of these operations may
    /// lead to undefined behavior. Consider using [`Fat::data_addr_mut`]
    /// instead, if possible.
    ///
    /// # Strict Pointer Provenance
    /// The [provenance] of the returned pointer is inherited from the argument.
    ///
    /// [provenance]: https://doc.rust-lang.org/nightly/std/ptr/index.html#strict-provenance
    /// [sized referent]: Fat#terminology
    #[must_use]
    pub fn data_addr(fat: &Self) -> NonNull<()> {
        let base = fat as *const Self as *const u8;
        let offset = Self::layout_of(fat).1;

        // Safety: This is a pointer to the unsized referent.
        unsafe { NonNull::new_unchecked(base.add(offset) as *mut ()) }
    }

    /// Returns a thin pointer to the [sized referent], suitable for use with
    /// [`core::ptr::from_raw_parts_mut`].
    ///
    /// # Strict Pointer Provenance
    /// The [provenance] of the returned pointer is inherited from the argument.
    ///
    /// [provenance]: https://doc.rust-lang.org/nightly/std/ptr/index.html#strict-provenance
    /// [sized referent]: Fat#terminology
    #[must_use]
    pub fn data_addr_mut(fat: &mut Self) -> NonNull<()> {
        let base = fat as *mut Self as *mut u8;
        let offset = Self::layout_of(fat).1;

        // Safety: This is a pointer to the unsized referent.
        unsafe { NonNull::new_unchecked(base.add(offset) as *mut ()) }
    }

    /// Obtains an immutable reference to the metadata used to construct
    /// references to the [unsized referent].
    ///
    /// [unsized referent]: Fat#terminology
    #[inline(always)] // nop
    #[must_use]
    pub fn metadata(fat: &Self) -> &<T as Pointee>::Metadata {
        &fat.metadata.0
    }

    /// Obtains layout information for the specified value.
    ///
    /// See [`Fat::layout_for`].
    ///
    /// # Example
    /// ```
    /// # use fat_type::Fat;
    /// # use core::alloc::Layout;
    /// # use core::fmt::Debug;
    /// let fat = Fat::<dyn Debug, u32>::new(42);
    /// let thin: &Fat<dyn Debug> = Fat::erase_ref(&fat);
    ///
    /// // Despite type erasure, we can obtain the original layout.
    /// assert_eq!(Fat::layout_of(thin).0, Layout::for_value(&fat));
    /// ```
    ///
    /// [un-erased type]: Fat#terminology
    #[inline(always)] // nop
    #[must_use]
    pub fn layout_of(fat: &Self) -> (Layout, usize) {
        // Safety: `fat.metadata.0` was produced by unsizing `U as T`.
        unsafe { Self::layout_for(&fat.metadata.0) }
    }

    /// Obtains layout information for a `Fat<T, U>` having the provided
    /// [pointer metadata].
    ///
    /// # Returns
    /// * The allocation [`Layout`] of a `Fat<T, U>` with the specified
    ///   metadata.
    /// * The corresponding pointer offset of the [unsized referent].
    ///
    /// The returned layout information is correct in the sense that unsafe code
    /// may rely on it being the actual layout of a `Fat<T, U>` with the
    /// specified metadata.
    ///
    /// # Safety
    /// The provided `metadata` must be the result of the [unsizing operation]
    /// `T as U`.
    ///
    /// [pointer metadata]: core::ptr::Pointee
    /// [unsized referent]: Fat#terminology
    /// [unsizing operation]: core::marker::Unsize
    #[must_use]
    pub unsafe fn layout_for(metadata: &<T as Pointee>::Metadata) -> (Layout, usize) {
        let layout_ptr = ptr::from_raw_parts::<T>(ptr::null(), *metadata);

        // Safety: `layout_ptr` has valid metadata.
        let data_layout = unsafe { Layout::for_value_raw(layout_ptr) };

        // Safety: This is the layout of `Fat<T, U>`, which is a valid type because this
        //         fn is an impl of it.
        let (layout, data_offset) =
            unsafe { Layout::new::<Metadata<T>>().extend(data_layout).unwrap_unchecked() };

        (layout.pad_to_align(), data_offset)
    }
}

impl<T: ?Sized, U: ?Sized> AsRef<Fat<T>> for Fat<T, U> {
    fn as_ref(&self) -> &Fat<T> {
        Self::erase_ref(self)
    }
}

impl<T: ?Sized, U: ?Sized> AsMut<Fat<T>> for Fat<T, U> {
    fn as_mut(&mut self) -> &mut Fat<T> {
        Self::erase_mut(self)
    }
}

impl<T: ?Sized, U: ?Sized> AsRef<T> for Fat<T, U> {
    fn as_ref(&self) -> &T {
        self
    }
}

impl<T: ?Sized, U: ?Sized> AsMut<T> for Fat<T, U> {
    fn as_mut(&mut self) -> &mut T {
        self
    }
}

impl<T: ?Sized, U> Borrow<Fat<T>> for Fat<T, U> {
    fn borrow(&self) -> &Fat<T> {
        Self::erase_ref(self)
    }
}

impl<T: ?Sized, U: ?Sized> Borrow<T> for Fat<T, U> {
    fn borrow(&self) -> &T {
        self
    }
}

impl<T: ?Sized, U: ?Sized> BorrowMut<T> for Fat<T, U> {
    fn borrow_mut(&mut self) -> &mut T {
        self
    }
}

impl<T: ?Sized, U> BorrowMut<Fat<T>> for Fat<T, U> {
    fn borrow_mut(&mut self) -> &mut Fat<T> {
        Self::erase_mut(self)
    }
}

impl<T: ?Sized, U: Unsize<T> + Clone> Clone for Fat<T, U> {
    fn clone(&self) -> Self {
        Self::new(self.data.clone())
    }
}

impl<T: ?Sized, U: Unsize<T> + Copy> Copy for Fat<T, U> {}

impl<T: ?Sized, U: ?Sized> Debug for Fat<T, U>
where <T as Pointee>::Metadata: Debug
{
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        f.debug_struct(type_name::<Self>())
            .field("metadata", &self.metadata)
            .field("data_addr", &Self::data_addr(self).as_ptr())
            .field("layout", &Self::layout_of(self))
            .finish()
    }
}

impl<T: ?Sized, U: Default + Unsize<T>> Default for Fat<T, U> {
    fn default() -> Self {
        Self::new(U::default())
    }
}

impl<T: ?Sized, U: ?Sized> Deref for Fat<T, U> {
    type Target = T;

    fn deref(&self) -> &T {
        let ptr = NonNull::from_raw_parts(Self::data_addr(self), self.metadata.0);

        // Safety: Address is the unsized referent of type `U`.
        //         Metadata is from unsizing the referent as `T`.
        //         Provenance is from `&self`, which contains the unsized referent.
        unsafe { ptr.as_ref() }
    }
}

impl<T: ?Sized, U: ?Sized> DerefMut for Fat<T, U> {
    fn deref_mut(&mut self) -> &mut T {
        let mut ptr = NonNull::from_raw_parts(Self::data_addr_mut(self), self.metadata.0);

        // Safety: Address is the unsized referent of type `U`.
        //         Metadata is from unsizing the referent as `T`.
        //         Provenance is from `&mut self`, which contains the unsized referent.
        unsafe { ptr.as_mut() }
    }
}

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

impl<T: Eq + ?Sized, U: ?Sized> Eq for Fat<T, U> {}

impl<T: ?Sized, U: Unsize<T>> From<U> for Fat<T, U> {
    fn from(value: U) -> Self {
        Self::new(value)
    }
}

impl<T: Hash + ?Sized, U: ?Sized> Hash for Fat<T, U> {
    fn hash<H: Hasher>(&self, h: &mut H) {
        Deref::deref(self).hash(h)
    }
}

impl<'a, T: ?Sized, U: ?Sized> IntoIterator for &'a Fat<T, U>
where &'a T: IntoIterator
{
    type Item = <&'a T as IntoIterator>::Item;
    type IntoIter = <&'a T as IntoIterator>::IntoIter;

    fn into_iter(self) -> Self::IntoIter {
        Deref::deref(self).into_iter()
    }
}

impl<'a, T: ?Sized, U: ?Sized> IntoIterator for &'a mut Fat<T, U>
where &'a mut T: IntoIterator
{
    type Item = <&'a mut T as IntoIterator>::Item;
    type IntoIter = <&'a mut T as IntoIterator>::IntoIter;

    fn into_iter(self) -> Self::IntoIter {
        DerefMut::deref_mut(self).into_iter()
    }
}

impl<T: Index<Idx> + ?Sized, U: ?Sized, Idx> Index<Idx> for Fat<T, U> {
    type Output = T::Output;

    fn index(&self, index: Idx) -> &Self::Output {
        Deref::deref(self).index(index)
    }
}

impl<T: IndexMut<Idx> + ?Sized, U: ?Sized, Idx> IndexMut<Idx> for Fat<T, U> {
    fn index_mut(&mut self, index: Idx) -> &mut Self::Output {
        DerefMut::deref_mut(self).index_mut(index)
    }
}

impl<T: Ord + ?Sized, U: ?Sized> Ord for Fat<T, U> {
    fn cmp(&self, other: &Self) -> Ordering {
        Deref::deref(self).cmp(other)
    }
}

impl<T: PartialEq + ?Sized, U: ?Sized, V: ?Sized> PartialEq<Fat<T, V>> for Fat<T, U> {
    fn eq(&self, other: &Fat<T, V>) -> bool {
        Deref::deref(self).eq(other)
    }
}

impl<T: PartialEq + ?Sized, U: ?Sized> PartialEq<T> for Fat<T, U> {
    fn eq(&self, other: &T) -> bool {
        Deref::deref(self).eq(other)
    }
}

impl<T: PartialOrd + ?Sized, U: ?Sized, V: ?Sized> PartialOrd<Fat<T, V>> for Fat<T, U> {
    fn partial_cmp(&self, other: &Fat<T, V>) -> Option<Ordering> {
        Deref::deref(self).partial_cmp(other)
    }
}

impl<T: PartialOrd + ?Sized, U: ?Sized> PartialOrd<T> for Fat<T, U> {
    fn partial_cmp(&self, other: &T) -> Option<Ordering> {
        Deref::deref(self).partial_cmp(other)
    }
}