//! This crate allows you to safely initialize Dynamically Sized Types (DST) using
//! only safe Rust.
//!
//! ```ignore
//! #[repr(C)]
//! #[derive(DynStruct)]
//! struct MyDynamicType {
//!     pub awesome: bool,
//!     pub number: u32,
//!     pub dynamic: [u32],
//! }
//!
//! // the `new` function is generated by the `DynStruct` macro.
//! let foo: Box<MyDynamicType> = MyDynamicType::new(true, 123, [4, 5, 6, 7]);
//! assert_eq!(foo.awesome, true);
//! assert_eq!(foo.number, 123);
//! assert_eq!(&foo.dynamic, &[4, 5, 6, 7]);
//! ```
//!
//!
//! ## Why Dynamic Types?
//!
//! In Rust, Dynamically Sized Types (DST) are everywhere. Slices (`[T]`) and trait
//! objects (`dyn Trait`) are the most common ones. However, it is also possible
//! to define your own! For example, this can be done by letting the last field in a
//! struct be a dynamically sized array (note the missing `&`):
//!
//! ```ignore
//! struct MyDynamicType {
//!     awesome: bool,
//!     number: u32,
//!     dynamic: [u32],
//! }
//! ```
//!
//! This tells the Rust compiler that contents of the `dynamic`-array is laid out in
//! memory right after the other fields. This can be very preferable in some cases,
//! since remove one level of indirection and increase cache-locality.
//!
//! However, there's a catch! Just as with slices, the compiler does not know how
//! many elements are in `dynamic`. Thus, we need what is called a fat-pointer which
//! stores both a pointer to the actual data, but also the length of the array
//! itself. As of releasing this crate, the only safe way to construct a dynamic
//! type is if we know the size of the array at compile-time. However, for most use
//! cases, that is not possible. Therefore this crate uses some `unsafe` behind the
//! scenes to work around the limitations of the language, all wrapped up in a safe
//! interface.
//!
//!
//! ## The Derive Macro
//!
//! The `DynStruct` macro can be applied to any `#[repr(C)]` struct that contains a
//! dynamically sized array as its last field. Fields only have a single constraint:
//! they have to implement `Copy`.
//!
//! ### Example
//!
//! ```ignore
//! #[repr(C)]
//! #[derive(DynStruct)]
//! struct MyDynamicType {
//!     pub awesome: bool,
//!     pub number: u32,
//!     pub dynamic: [u32],
//! }
//! ```
//!
//! will produce a single `impl`-block with a `new` function. This function accepts all fileds in
//! the same order they were declared. The last field, however, can be anything implementing
//! `IntoIterator`:
//!
//! ```ignore
//! impl MyDynamicType {
//!     pub fn new<I>(awesome: bool, number: u32, dynamic: I) -> Box<MyDynamicType>
//!         where I: IntoIterator<Item = u32>,
//!               I::IntoIter: ExactSizeIterator,
//!     {
//!         // ... implementation details ...
//!     }
//! }
//! ```
//!
//! Due to the nature of dynamically sized types, the resulting value has to be
//! built on the heap. For safety reasons we currently only allow returning `Box`,
//! though in a future version we may also allow `Rc` and `Arc`. In the meantime it
//! is posible to use `Arc::from(MyDynamicType::new(...))`.

#[cfg(feature = "derive")]
pub use dyn_struct_derive::DynStruct;

use std::mem::{align_of, size_of, MaybeUninit};

#[repr(C)]
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct DynStruct<Header, Tail> {
    pub header: Header,
    pub tail: [Tail],
}

impl<Header, Tail> DynStruct<Header, Tail> {
    /// Allocate a new `DynStruct` on the heap. Initialized lazily using an iterator.
    #[inline]
    pub fn new<I>(header: Header, tail: I) -> Box<Self>
    where
        I: IntoIterator<Item = Tail>,
        I::IntoIter: ExactSizeIterator,
    {
        let tail = tail.into_iter();

        let mut writer = BoxWriter::<Header, Tail>::new(header, tail.len());

        for value in tail {
            writer.write_tail::<I::IntoIter>(value);
        }

        writer.finish::<I::IntoIter>()
    }

    /// Allocate a new `DynStruct` on the heap. Uses a slice instead of an iterator (as
    /// [`DynStruct::new`]). This will probably be faster in most cases (provided the slice is
    /// readily available).
    pub fn from_slice(header: Header, tail: &[Tail]) -> Box<Self>
    where
        Tail: Copy,
    {
        let mut writer = BoxWriter::<Header, Tail>::new(header, tail.len());
        unsafe {
            writer.write_slice(tail);
        }
        writer.finish::<()>()
    }

    #[inline]
    fn align() -> usize {
        usize::max(align_of::<Header>(), align_of::<Tail>())
    }

    /// Returns the total size of the `DynStruct<Header, Tail>` structure, provided the length of the
    /// tail.
    #[inline]
    fn size(len: usize) -> usize {
        let header = size_of::<Header>();

        let tail_align = align_of::<Tail>();
        let padding = if header % tail_align == 0 {
            0
        } else {
            tail_align - header % tail_align
        };

        let tail = size_of::<Tail>() * len;

        header + padding + tail
    }
}

struct BoxWriter<Header, Tail> {
    raw: *mut DynStruct<Header, MaybeUninit<Tail>>,
    written: usize,
}

impl<Header, Tail> BoxWriter<Header, Tail> {
    #[inline]
    pub fn new(header: Header, len: usize) -> Self {
        let total_size = DynStruct::<Header, Tail>::size(len);
        let align = DynStruct::<Header, Tail>::align();

        let fat_ptr = if total_size == 0 {
            // We cannot allocate a region of 0 bytes, thus we use `Box` to create a dangling
            // pointer with the correct length.
            let slice: Box<[()]> = Box::from(slice_with_len(len));

            // This is a zero-size-type, so moving it into the allocation has no effect. Instead we
            // just create a new one "out of thin air" by casting the allocation to the appropriate
            // header. We need this call to `forget` to make sure the destructor of the original
            // header does not run.
            std::mem::forget(header);

            Box::into_raw(slice) as *mut DynStruct<Header, MaybeUninit<Tail>>
        } else {
            unsafe {
                // Allocate enough memory to store both the header and tail
                let layout = std::alloc::Layout::from_size_align(total_size, align).unwrap();
                let raw = std::alloc::alloc(layout);
                if raw.is_null() {
                    std::alloc::handle_alloc_error(layout)
                }

                // Initialize the header field
                raw.cast::<Header>().write(header);

                // use a slice as an intermediary to get a fat pointer containing the correct
                // length of the tail
                let slice = std::slice::from_raw_parts_mut(raw as *mut (), len);
                slice as *mut [()] as *mut DynStruct<Header, MaybeUninit<Tail>>
            }
        };

        BoxWriter {
            raw: fat_ptr,
            written: 0,
        }
    }

    #[inline]
    fn write_tail<I>(&mut self, value: Tail) {
        let written = self.written;
        let tail = &mut self.as_mut().tail;

        assert!(
            written < tail.len(),
            "got more items than expected. Probable bug in `ExactSizeIterator` for `{}`?",
            std::any::type_name::<I>(),
        );

        tail[written].write(value);
        self.written += 1;
    }

    #[inline]
    fn finish<I>(mut self) -> Box<DynStruct<Header, Tail>> {
        let len = self.as_mut().tail.len();
        assert_eq!(
            self.written,
            len,
            "got fewer items than expected. Probable bug in `ExactSizeIterator` for `{}`?",
            std::any::type_name::<I>(),
        );

        // This cast from `DynStruct<Header, MaybeUninit<Tail>>` is sound since all tail elements
        // now have been initialized
        let init = self.raw as *mut DynStruct<Header, Tail>;

        // once we have finished constructing the value, don't run the destructor
        std::mem::forget(self);

        unsafe { Box::from_raw(init) }
    }

    fn as_mut(&mut self) -> &mut DynStruct<Header, MaybeUninit<Tail>> {
        unsafe { &mut *self.raw }
    }

    /// # Safety
    ///
    /// Assumes that this writer was created with a capacity for `values.len()`
    unsafe fn write_slice(&mut self, values: &[Tail])
    where
        Tail: Copy,
    {
        self.as_mut()
            .tail
            .as_mut_ptr()
            .copy_from_nonoverlapping(values.as_ptr().cast(), values.len());
        self.written = values.len();
    }
}

impl<Header, Tail> Drop for BoxWriter<Header, Tail> {
    fn drop(&mut self) {
        unsafe {
            // SAFETY: the header field is always initialized
            std::ptr::drop_in_place(self.raw.cast::<Header>());

            let initialized = self.written;
            let tail = &mut self.as_mut().tail;
            for i in 0..initialized {
                tail[i].as_mut_ptr().drop_in_place();
            }
        }
    }
}

impl<T> DynStruct<T, T> {
    /// Get a `DynStruct` as a view over a slice (this does not allocate).
    pub fn slice_view(values: &[T]) -> &Self {
        assert!(
            !values.is_empty(),
            "attempted to create `{}` from empty slice (needs at least 1 element)",
            std::any::type_name::<Self>()
        );
        let slice = &values[..values.len() - 1];
        unsafe { &*(slice as *const [T] as *const Self) }
    }
}

impl<T, const N: usize> DynStruct<[T; N], T> {
    /// Get a `DynStruct` as a view over a slice (this does not allocate).
    pub fn slice_view(values: &[T]) -> &Self {
        assert!(
            values.len() >= N,
            "attempted to create `{}` from empty slice (needs at least {} elements)",
            std::any::type_name::<Self>(),
            N,
        );
        let slice = &values[..values.len() - N];
        unsafe { &*(slice as *const [T] as *const Self) }
    }
}

fn slice_with_len(len: usize) -> &'static [()] {
    static ARBITRARY: [(); usize::MAX] = [(); usize::MAX];
    &ARBITRARY[..len]
}

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

    #[test]
    fn mixed_types() {
        let mixed = DynStruct::new((true, 32u16), [1u64, 2, 3, 4]);
        assert_eq!(mixed.header, (true, 32u16));
        assert_eq!(&mixed.tail, &[1, 2, 3, 4]);
    }

    #[test]
    fn zero_sized_types() {
        let zero = DynStruct::new((), [(), ()]);
        assert_eq!(zero.header, ());
        assert_eq!(&zero.tail, &[(), ()]);
    }

    #[test]
    fn from_slice() {
        let slice = DynStruct::from_slice((true, 32u16), &[1, 2, 3]);
        assert_eq!(slice.header, (true, 32u16));
        assert_eq!(&slice.tail, &[1, 2, 3]);

        let array = DynStruct::<[u32; 3], u32>::slice_view(&[1, 2, 3, 4, 5]);
        assert_eq!(array.header, [1, 2, 3]);
        assert_eq!(&array.tail, &[4, 5]);
    }

    #[test]
    fn slice_view() {
        let same = DynStruct::<u32, u32>::slice_view(&[1, 2, 3]);
        assert_eq!(same.header, 1);
        assert_eq!(&same.tail, &[2, 3]);

        let array = DynStruct::<[u32; 3], u32>::slice_view(&[1, 2, 3, 4, 5]);
        assert_eq!(array.header, [1, 2, 3]);
        assert_eq!(&array.tail, &[4, 5]);
    }
}