//! # A `Vec<T: ?Sized>`
//!
//! [`DynVec`], a dynamic length collection of unsized elements, akin to [`std::vec::Vec`].
//!
//! # Examples
//!
//! You can create a vector with [`DynVec::new`]:
//!
//! ```
//! # use std::fmt::Debug;
//! # use dyn_vec::DynVec;
//! let vec: DynVec<dyn Debug> = DynVec::new();
//! # assert_eq!(format!("{:?}", vec), "[]");
//! ```
//!
//! or with the [`dyn_vec!`] macro:
//!
//! ```
//! # use dyn_vec::{dyn_vec, DynVec};
//! # use std::fmt::Debug;
//! let vec: DynVec<i32> = dyn_vec![1, 2, 3];
//! // check the docs for `dyn_vec!` for more info on this syntax
//! let vec_boxed: DynVec<dyn Debug> = dyn_vec![box:
//!     Box::new(1) as _,
//!     Box::new("foo") as _,
//!     Box::new(true) as _
//! ];
//! let vec_unsized: DynVec<dyn Debug> = dyn_vec![unsized: 1, "foo", true];
//! let vec_from_elem: DynVec<i32> = dyn_vec![3; 5];
//! # assert_eq!(vec, [1, 2, 3]);
//! # assert_eq!(format!("{:?}", vec_boxed), r#"[1, "foo", true]"#);
//! # assert_eq!(format!("{:?}", vec_unsized), r#"[1, "foo", true]"#);
//! # assert_eq!(vec_from_elem, [3; 5]);
//! ```
//!
//! A vector can be pushed to with [`DynVec::push`]:
//!
//! ```
//! # use dyn_vec::{dyn_vec, DynVec};
//! let mut vec: DynVec<i32> = dyn_vec![];
//! vec.push(1);
//! vec.push(2);
//! vec.push(3);
//! # assert_eq!(format!("{:?}", vec), "[1, 2, 3]");
//! ```
//!
//! ...and with [`push_box`] and [`push_unsize`] ([`push_unsize_stable`] without the `"unstable"`feature):
//!
//! ```
//! # use dyn_vec::{dyn_vec, DynVec};
//! # use std::fmt::Debug;
//! let mut vec: DynVec<dyn Debug> = dyn_vec![];
//! vec.push_box(Box::new(1));
//! vec.push_box(Box::new("foo"));
//! vec.push_box(Box::new(true));
//!
//! // these closures are only needed for the `_stable` versions
//! vec.push_unsize_stable(2, |v| v as _);
//! vec.push_unsize_stable("bar", |v| v as _);
//! vec.push_unsize_stable(false, |v| v as _);
//! # assert_eq!(format!("{:?}", vec), r#"[1, "foo", true, 2, "bar", false]"#);
//! ```
//!
//! Finally, a vector can be [`unsize`]d to another vector ([`unsize_stable`] on stable):
//!
//! ```
//! # use dyn_vec::{dyn_vec, DynVec};
//! # use std::fmt::Debug;
//! let vec: DynVec<i32> = dyn_vec![1, 2, 3];
//! // vec.push_unsize_stable("foo", |v| v as _); // not yet...
//! let mut vec: DynVec<dyn Debug> = vec.unsize_stable(|v| v as _);
//! vec.push_unsize_stable("foo", |v| v as _); // now we can!
//! # assert_eq!(format!("{:?}", vec), r#"[1, 2, 3, "foo"]"#);
//! ```
//!
//! To use the `_stable` variations, one can generally add the argument `|v| v as _`.
//!
//! # Stability
//!
//! This crate is currently stable, but lacks some functionality. To enable this functionality, use
//! the `"unstable"` crate feature, which depends on the following nightly features:
//!  - [`#![feature(coerce_unsized)]`](https://github.com/rust-lang/rust/issues/18598)
//!
//! and enables the following functionality:
//!  - [`DynVec::push_unsize`]
//!  - [`DynVec::unsize`]
//!  - [`DynVec::extend_unsize`]
//!
//! In addition, the `"unstable"` feature also enables dependence on the following nightly features
//! in order to conform to [strict provenance](https://github.com/rust-lang/rust/issues/95228):
//!  - [`#![feature(set_ptr_value)]`](https://github.com/rust-lang/rust/issues/75091)
//!  - [`#![feature(pointer_byte_offsets)]`](https://github.com/rust-lang/rust/issues/96283)
//!
//! # Data Layout
//!
//! ```text
//! DynVec<T>
//! ┌────┬────┬────┬────┐
//! │ptr │len │cap │end │
//! └─┬──┴────┴─┬──┴─┬──┘
//!   │         │    │
//!   │         └────┼───────────────────────────────────────────────┐
//! ┌─┘              └───────────────────┐                           │
//! │                                    │                           │
//! ▼                                    ▼                           ▼
//! ┌────┬────┬─────┬──────────┬───┬─────┬───────────────┬───┬───┬───┐
//! │pad │elem│pad  │elem      │pad│elem │               │ptr│ptr│ptr│
//! └────┴────┴─────┴──────────┴───┴─────┴───────────────┴─┬─┴─┬─┴─┬─┘
//! ▲    ▲          ▲              ▲                       │   │   │ ▲
//! │    │          │              └───────────────────────┘   │   │ │
//! │    │          └──────────────────────────────────────────┘   │ │
//! │    └─────────────────────────────────────────────────────────┘ │
//! │                                                                │
//! └─────────────── aligned to align_of::<*const T>() ──────────────┘
//! ```
//!
//! [`DynVec<T: ?Sized>`]: DynVec
//! [`DynVec::push_unsize`]: DynVec::push_unsize
//! [`DynVec::unsize`]: DynVec::unsize
//! [`DynVec::extend_unsize`]: DynVec::extend_unsize
//! [`push_box`]: DynVec::push_box
//! [`push_unsize`]: DynVec::push_unsize
//! [`push_unsize_stable`]: DynVec::push_unsize_stable
//! [`unsize`]: DynVec::unsize
//! [`unsize_stable`]: DynVec::unsize_stable

#![cfg_attr(
    feature = "unstable",
    feature(coerce_unsized),
    feature(set_ptr_value),
    feature(pointer_byte_offsets)
)]
#![cfg_attr(doc, feature(doc_cfg))]
#![warn(missing_docs)]
#![warn(clippy::pedantic)]
#![warn(clippy::nursery)]
#![allow(clippy::must_use_candidate)]
#![allow(unstable_name_collisions)]
#![cfg_attr(test, feature(test))]

#[cfg(test)]
mod bench;
#[cfg(test)]
mod test;

mod impls;
mod iter;

mod ptr_ext;
use ptr_ext::{ConstPtrExt, MutPtrExt, PtrExt};

pub use iter::*;

use core::panic;
use std::{
    alloc::{alloc, dealloc, handle_alloc_error, Layout},
    any::Any,
    marker::PhantomData,
    mem::{self, align_of, align_of_val, size_of, size_of_val, ManuallyDrop},
    ops::{Index, IndexMut},
    ptr::{drop_in_place, NonNull},
    slice,
};

#[cfg(any(doc, feature = "unstable"))]
use std::ops::CoerceUnsized;

type Coercer<T, U> = for<'a> fn(&'a T) -> &'a U;

/// A heap allocated, dynamic length collection of `?Sized` elements.
///
/// See [`std::vec::Vec`] (the standard library `Vec` type) for more information.
pub struct DynVec<T: ?Sized> {
    ptr: NonNull<u8>,
    len: usize,
    capacity: usize,
    end_ptr: NonNull<u8>,
    _phantom: PhantomData<T>,
}

/// The extra data stored at the end of the allocation.
type Extra<T> = *const T;

impl<T: ?Sized> DynVec<T> {
    /// Creates a new, empty vector.
    pub const fn new() -> Self {
        let ptr = NonNull::dangling();
        Self {
            ptr,
            len: 0,
            capacity: 0,
            end_ptr: ptr,
            _phantom: PhantomData,
        }
    }

    /// Creates a new vector that holds `len` copies of `v`.
    ///
    /// Only avaliable when `T: Sized`.
    pub fn from_elem(v: T, len: usize) -> Self
    where
        T: Sized + Clone,
    {
        let mut vec = Self::with_capacity(len);

        for _ in 0..len {
            vec.push(v.clone());
        }

        vec
    }

    /// Creates a new vector that can hold the given amount of `T`s.
    ///
    /// Only avaliable when `T: Sized`.
    pub fn with_capacity(cap: usize) -> Self
    where
        T: Sized,
    {
        Self::with_capacity_for::<T>(cap)
    }

    /// Creates a new vector with the given capacity, measured in bytes.
    pub fn with_capacity_bytes(cap: usize) -> Self {
        let mut vec = Self::new();
        unsafe {
            vec.realloc(cap);
        }
        vec
    }

    /// Creates a new vector with enough capacity to hold the given amount of `U`s.
    pub fn with_capacity_for<U>(cap: usize) -> Self {
        Self::with_capacity_bytes(cap * (size_of::<U>() + size_of::<Extra<U>>()))
    }

    /// Decomposes the vector into its raw components.
    ///
    /// Returns the pointer to the underlying alloctaion, the number of elements,
    /// the size of the allocation in bytes, and the total size of all of the
    /// vector's elements.
    pub fn into_raw_parts(self) -> (*mut u8, usize, usize, usize) {
        let mut this = ManuallyDrop::new(self);
        (
            this.as_mut_ptr(),
            this.len(),
            this.capacity(),
            this.data_size(),
        )
    }

    /// Reconstructs a vector from its raw components.
    ///
    /// # Safety
    /// - `ptr` must be non-null and point to an allocation with the proper
    /// data layout, as documented in the crate-level docs.
    /// - `len` must be less than or equal to the number of initialized
    /// elements in the allocation.
    /// - `capacity` must be equal to the size of the allocation in bytes.
    /// - `data_size` must be equal to the number of bytes taken up by the
    /// first `len` elements of the vector, including leading (but not trailing)
    /// padding.
    /// - The allocation must have been allocated with alignment equal to
    /// `align_of::<*const T>()`
    ///
    /// All of these conditions are upheld by the values returned from
    /// `into_raw_parts`.
    pub const unsafe fn from_raw_parts(
        ptr: *mut u8,
        len: usize,
        capacity: usize,
        data_size: usize,
    ) -> Self {
        Self {
            ptr: NonNull::new_unchecked(ptr),
            len,
            capacity,
            end_ptr: NonNull::new_unchecked(ptr.add(data_size)),
            _phantom: PhantomData,
        }
    }

    /// Appends an element to the end of the vector.
    ///
    /// Only avaliable if `T: Sized`.
    pub fn push(&mut self, v: T)
    where
        T: Sized,
    {
        unsafe { self.push_raw(&*ManuallyDrop::new(v)) }
    }

    /// Appends a (possibly unsized) boxed element to the end of the vector.
    pub fn push_box(&mut self, v: Box<T>) {
        let ptr = Box::into_raw(v);
        unsafe {
            let layout = Layout::for_value(&*ptr); // ref it *before* its logically uninit
            self.push_raw(ptr);
            dealloc(ptr.cast(), layout);
        }
    }

    /// Appends a sized element of type `U` to the end of the vector, given that it can be `CoerceUnsized` to a `T`.
    #[cfg(any(doc, feature = "unstable"))]
    #[cfg_attr(doc, doc(cfg(feature = "unstable")))]
    pub fn push_unsize<U>(&mut self, v: U)
    where
        for<'a> &'a U: CoerceUnsized<&'a T>,
    {
        // TODO: maybe make this not call the stable version for perf?
        self.push_unsize_stable(v, |v| v as _);
    }

    /// Appends a sized element of type `U` to the end of the vector, given that it can be `CoerceUnsized` to a `T`.
    ///
    /// The coercion is done through a closure, since `CoerceUnsized` is unstable. Usually you can pass `|v| v as _`.
    pub fn push_unsize_stable<U>(&mut self, v: U, coercer: Coercer<U, T>) {
        let v_unsized: &T = coercer(&v);
        unsafe { self.push_raw(v_unsized) };
        mem::forget(v);
    }

    unsafe fn push_raw(&mut self, v: *const T) {
        if !self.will_fit(&*v) {
            let new_alloc_size = self.capacity * 2 + size_of_val(&*v) * 2 + size_of::<Extra<T>>();
            self.realloc(new_alloc_size);
        }

        self.push_raw_unchecked(v);
    }

    /// Given an element, returns a pointer to where it would be written if it was pushed, assuming no reallocation is needed.
    ///
    /// The pointer will be aligned, but writing to it may overwrite data belonging to the vector.
    /// To check for this, call `will_fit`.
    /// In addition, the extra data for the element must be set using `set_extra_from_ptr`.
    fn get_next_elem_ptr(&self, v: &T) -> *mut u8 {
        self.end_ptr.as_ptr().align_up(align_of_val(v))
    }

    /// Checks if a given element will fit in the vector without reallocations.
    pub fn will_fit(&self, v: &T) -> bool {
        let remaining_space = self.get_ptr_to_extra(self.len).addr() - self.end_ptr.as_ptr().addr();
        let needed_space = size_of_val(v) + size_of::<Extra<T>>();
        remaining_space >= needed_space
    }

    unsafe fn push_raw_unchecked(&mut self, v: *const T) {
        let dest = self.get_next_elem_ptr(&*v).with_meta_from(v);
        v.copy_val_to(dest);
        self.set_extra_from_ptr(self.len, dest);

        self.end_ptr = NonNull::new_unchecked(dest.get_end().cast());
        self.len += 1;
    }

    /// Pops an element off the end of the vector, putting it in a [`Box`].
    pub fn pop(&mut self) -> Option<Box<T>> {
        unsafe {
            self.len = self.len.checked_sub(1)?;
            let el = self.get_ptr(self.len);
            Some(el.read_to_box())
        }
    }

    unsafe fn realloc(&mut self, size: usize) {
        let layout = Layout::from_size_align_unchecked(size, align_of::<Extra<T>>()).pad_to_align();
        let new_alloc = NonNull::new(alloc(layout)).unwrap_or_else(|| handle_alloc_error(layout));
        if self.capacity == 0 {
            // will panic if OOM
            self.ptr = new_alloc;

            self.end_ptr = self.ptr;
        } else {
            // cannot use mem::realloc here

            // data
            let mut ptr = new_alloc.as_ptr();
            for i in 0..self.len {
                let v = self.get_ptr(i);

                ptr = ptr.align_up(align_of_val(&*v));
                v.copy_val_to(ptr);
                self.set_extra_from_ptr(i, ptr.with_meta_from(v));
                ptr = ptr.wrapping_add(size_of_val(&*v));
            }
            self.end_ptr = NonNull::new_unchecked(ptr);

            // extra
            let extra_src = self.get_ptr_to_extra(self.len);
            let extra_dst = {
                let current_alloc_end = self.ptr.as_ptr().wrapping_add(self.capacity);
                let new_alloc_end = new_alloc.as_ptr().wrapping_add(layout.size());
                let extra_len = current_alloc_end.addr() - extra_src.addr();
                new_alloc_end.wrapping_sub(extra_len)
            };
            extra_src.copy_to(extra_dst.cast(), self.len);

            dealloc(
                self.ptr.as_ptr(),
                Layout::from_size_align_unchecked(self.capacity, 8),
            );

            self.ptr = new_alloc;
        }

        self.capacity = layout.size();
    }

    /// for internal use
    ///
    /// # Note: 1-indexed, to allow getting a pointer to the end of the alloc easily
    fn get_ptr_to_extra(&self, index: usize) -> *mut Extra<T> {
        self.ptr
            .as_ptr()
            .add_bytes(self.capacity)
            .cast::<Extra<T>>()
            .wrapping_sub(index)
    }

    unsafe fn set_extra_from_ptr(&self, index: usize, ptr: *const T) {
        self.get_ptr_to_extra(index + 1).write(ptr);
    }

    unsafe fn get_ptr(&self, index: usize) -> *const T {
        *self.get_ptr_to_extra(index + 1)
    }

    unsafe fn get_ptr_before_pad(&self, index: usize) -> *const T {
        self.get_ptr(index).with_addr_from(if index > 0 {
            self.get_ptr(index - 1).get_end().cast()
        } else {
            self.ptr.as_ptr()
        })
    }

    /// Gets a reference to the element at the specified index.
    ///
    /// Returns `None` if the index is out-of-bounds.
    pub fn get(&self, index: usize) -> Option<&T> {
        if index < self.len {
            Some(unsafe { self.get_unchecked(index) })
        } else {
            None
        }
    }

    /// Gets a reference to the element at the specified index.
    ///
    /// # Safety
    ///
    /// Immediate UB if the index is out-of-bounds.
    pub unsafe fn get_unchecked(&self, index: usize) -> &T {
        &*self.get_ptr(index)
    }

    /// Gets a mutable reference to the element at the specified index.
    ///
    /// Returns `None` if the index is out-of-bounds.
    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
        if index < self.len {
            Some(unsafe { self.get_unchecked_mut(index) })
        } else {
            None
        }
    }

    /// Gets a mutable reference to the element at the specified index.
    ///
    /// # Safety
    ///
    /// Immediate UB if the index is out-of-bounds.
    pub unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T {
        &mut *(self.get_ptr(index) as *mut _)
    }

    /// Returns the length of the vector, which is how many items it contains.
    pub const fn len(&self) -> usize {
        self.len
    }

    /// Returns `true` if the vector holds no elements.
    pub const fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Returns the capacity, which is the size of the allocation in bytes.
    ///
    /// Note the distinction from [`std::vec::Vec::capacity`], which returns how many *elements* it can hold.
    pub const fn capacity(&self) -> usize {
        self.capacity
    }

    /// Returns a pointer to the allocation of the vector.
    pub const fn as_ptr(&self) -> *const u8 {
        self.ptr.as_ptr()
    }

    /// Returns a mutable pointer to the allocation of the vector.
    pub fn as_mut_ptr(&mut self) -> *mut u8 {
        self.ptr.as_ptr()
    }

    /// Returns a pointer to the end of the last element of the vector.
    pub const fn as_end_ptr(&self) -> *const u8 {
        self.end_ptr.as_ptr()
    }

    /// Returns a mutable pointer to the end of the last element of the vector.
    pub fn as_end_ptr_mut(&mut self) -> *mut u8 {
        self.end_ptr.as_ptr()
    }

    /// Returns the size (in bytes) of the elements (and padding) of the vector.
    ///
    /// Same as `self.as_end_ptr() as usize - self.as_ptr() as usize`.
    pub fn data_size(&self) -> usize {
        self.as_end_ptr() as usize - self.as_ptr() as usize
    }

    /// Converts a `DynVec<T: Sized>` into a `DynVec<U: ?Sized>`, given that `T` can be `CoerceUnsized` into `U`.
    #[cfg(any(doc, feature = "unstable"))]
    #[cfg_attr(doc, doc(cfg(feature = "unstable")))]
    pub fn unsize<U: ?Sized>(self) -> DynVec<U>
    where
        for<'a> &'a T: CoerceUnsized<&'a U>,
    {
        // TODO: maybe make this not call the stable version for perf?
        self.unsize_stable(|v| v as _)
    }

    /// Converts a `DynVec<T: Sized>` into a `DynVec<U: ?Sized>`, given that `T` can be `CoerceUnsized` into `U`.
    ///
    /// The coercion is done through a closure, since `CoerceUnsized` is unstable. Usually you can pass `|v| v as _`.
    pub fn unsize_stable<U: ?Sized>(mut self, coercer: Coercer<T, U>) -> DynVec<U> {
        if size_of::<Extra<U>>() > size_of::<Extra<T>>() {
            let elem_size = self.end_ptr.as_ptr().addr() - self.ptr.as_ptr().addr();
            let extra_size = self.len * size_of::<Extra<U>>();
            let needed_size = elem_size + extra_size;
            if needed_size > self.capacity {
                unsafe {
                    self.realloc(needed_size);
                }
            }
        }

        let new_vec = DynVec::<U> {
            ptr: self.ptr,
            len: self.len,
            capacity: self.capacity,
            end_ptr: self.end_ptr,
            _phantom: PhantomData,
        };

        if size_of::<Extra<U>>() > size_of::<Extra<T>>() {
            // new extra larger than old extra, must go from back to front

            for i in (0..self.len).rev() {
                // using references here is necessary for unsizing coercion to work
                let current = unsafe { &*self.get_ptr(i) };
                unsafe { new_vec.set_extra_from_ptr(i, coercer(current)) }
            }
        } else {
            // new extra smaller or same size as old extra, must go from front to back

            for i in 0..self.len {
                // using references here is necessary for unsizing coercion to work
                let current = unsafe { &*self.get_ptr(i) };
                unsafe { new_vec.set_extra_from_ptr(i, coercer(current)) }
            }
        }

        mem::forget(self);
        new_vec
    }

    unsafe fn dealloc(&self) {
        if self.capacity != 0 {
            dealloc(
                self.ptr.as_ptr(),
                Layout::from_size_align_unchecked(self.capacity, align_of::<Extra<T>>()),
            );
        }
    }

    /// Extends this vector with an iterator.
    ///
    /// Similar to [`Extend::extend`], but seperate to prevent conflicting implementations.
    #[cfg(any(doc, feature = "unstable"))]
    #[cfg_attr(doc, doc(cfg(feature = "unstable")))]
    pub fn extend_unsize<U, I: IntoIterator<Item = U>>(&mut self, iter: I)
    where
        for<'a> &'a U: CoerceUnsized<&'a T>,
    {
        // TODO: maybe make this not call the stable version for perf?
        self.extend_unsize_stable(iter, |v| v as _);
    }

    /// Extends this vector with an iterator.
    ///
    /// Similar to [`Extend::extend`], but seperate to prevent conflicting implementations.
    ///
    /// The coercion is done through a closure, since `CoerceUnsized` is unstable. Usually you can pass `|v| v as _`.
    pub fn extend_unsize_stable<U, I: IntoIterator<Item = U>>(
        &mut self,
        iter: I,
        coercer: Coercer<U, T>,
    ) {
        for item in iter {
            self.push_unsize_stable(item, coercer);
        }
    }

    /// Removes the element at the specified index, shifting other elements over to fill the gap.
    pub fn remove(&mut self, index: usize) -> Option<Box<T>> {
        if index >= self.len {
            return None;
        }

        if index == self.len - 1 {
            return self.pop();
        }

        unsafe {
            let res = Some(self.get_ptr(index).read_to_box());

            // starting from the now-empty spot, up to but not including the end...
            for index in index..self.len - 1 {
                // get a pointer to the end of the previous element
                let mut new_ptr = self.get_ptr_before_pad(index);
                // align it up to the align of the NEXT element
                let next_ptr = self.get_ptr(index + 1);
                new_ptr = new_ptr.align_up(align_of_val(&*next_ptr));

                // if its the same, we can break as the rest will be useless
                if new_ptr == next_ptr {
                    break;
                }

                // data
                next_ptr.copy_val_to(new_ptr as *mut T);

                // extra
                self.set_extra_from_ptr(index, new_ptr.with_meta_from(next_ptr));
            }

            self.len -= 1;

            res
        }
    }
}

impl<T> DynVec<[T]> {
    /// Returns a slice over all the elements in the vector.
    ///
    /// Only avaliable for `DynVec<[T]>`.
    pub fn as_slice_flatten(&self) -> &[T] {
        if self.len == 0 {
            return unsafe { slice::from_raw_parts(NonNull::dangling().as_ptr(), 0) };
        }

        // SAFETY: the slices should be contiguous by the logic of `push_raw_unchecked`
        unsafe {
            slice::from_raw_parts(self.get_ptr(0).data_ptr().cast(), {
                let start = self.get_ptr(0).addr();
                let end = self.end_ptr.as_ptr().addr();
                debug_assert_eq!((end - start) % size_of::<T>(), 0);
                (end - start) / size_of::<T>() // integer division!
            })
        }
    }

    /// Returns a mutable slice over all the elements in the vector.
    ///
    /// Only avaliable for `DynVec<[T]>`.
    pub fn as_mut_slice_flatten(&mut self) -> &mut [T] {
        if self.len == 0 {
            return unsafe { slice::from_raw_parts_mut(NonNull::dangling().as_ptr(), 0) };
        }

        // SAFETY: the slices should be contiguous by the logic of `push_raw_unchecked`
        unsafe {
            slice::from_raw_parts_mut(self.get_ptr(0).data_ptr() as _, {
                let start = self.get_ptr(0).addr();
                let end = self.end_ptr.as_ptr().addr();
                debug_assert_eq!((end - start) % size_of::<T>(), 0);
                (end - start) / size_of::<T>() // integer division!
            })
        }
    }
}

impl DynVec<dyn Any> {
    /// Gets a reference to the element at then specified index, downcasting it to the specified type.
    ///
    /// Same as `self.get(index).map(|v| v.downcast()).flatten()`.
    pub fn downcast_get<T: Any>(&self, index: usize) -> Option<&T> {
        self.get(index)?.downcast_ref()
    }

    /// Gets a mutable reference to the element at then specified index, downcasting it to the specified type.
    ///
    /// Same as `self.get_mut(index).map(|v| v.downcast_mut()).flatten()`.
    pub fn downcast_get_mut<T: Any>(&mut self, index: usize) -> Option<&mut T> {
        self.get_mut(index)?.downcast_mut()
    }

    /// Pops an element off the end of the vector, downcasting it to the specified type.
    ///
    /// If the element is not of type `T`, the element will not be popped.
    ///
    /// Same as `self.pop().map(|v| v.downcast()).flatten()`, but without an intermediate allocation.
    pub fn downcast_pop<T: Any>(&mut self) -> Option<T> {
        unsafe {
            let el = self.get_unchecked_mut(self.len.checked_sub(1)?);
            let v = Some((el.downcast_mut()? as *mut T).read());
            self.len -= 1;
            v
        }
    }
}

impl<T: ?Sized> Drop for DynVec<T> {
    fn drop(&mut self) {
        unsafe {
            for el in self.iter_mut() {
                drop_in_place(el);
            }

            self.dealloc();
        }
    }
}

impl<T: ?Sized> Index<usize> for DynVec<T> {
    type Output = T;

    #[track_caller]
    fn index(&self, index: usize) -> &Self::Output {
        self.get(index).unwrap_or_else(|| {
            panic!(
                "index out of bounds: the len is {} but the index is {}",
                self.len, index
            )
        })
    }
}

impl<T: ?Sized> IndexMut<usize> for DynVec<T> {
    #[track_caller]
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        let len = self.len;
        self.get_mut(index).unwrap_or_else(|| {
            panic!(
                "index out of bounds: the len is {} but the index is {}",
                len, index
            )
        })
    }
}

/// Creates a [`DynVec`].
///
/// # Examples
///
/// ```
/// # use dyn_vec::{dyn_vec, DynVec};
/// # use std::fmt::Debug;
/// let vec1: DynVec<i32> = dyn_vec![1, 2, 3];
/// let vec2: DynVec<dyn Debug> = dyn_vec![box:
///     Box::new(1) as _,
///     Box::new(String::from("foo")) as _,
///     Box::new(true) as _
/// ];
/// let vec3: DynVec<dyn Debug> = dyn_vec![unsized: 1, String::from("foo"), true];
/// ```
#[macro_export]
macro_rules! dyn_vec {
    () => {
        $crate::DynVec::new();
    };
    (box: $($elem:expr),+ $(,)?) => {{
        let mut vec = $crate::DynVec::new();
        $(vec.push_box($elem);)+
        vec
    }};
    (unsized: $($elem:expr),+ $(,)?) => {{
        let mut vec = $crate::DynVec::new();
        // TODO: when stuff stabilizes change this
        $(vec.push_unsize_stable($elem, |v| v as _);)+
        vec
    }};
    ($elem:expr; $n:expr) => {
        $crate::DynVec::from_elem($elem, $n)
    };
    ($($elem:expr),+ $(,)?) => {{
        let mut vec = $crate::DynVec::new();
        $(vec.push($elem);)+
        vec
    }};
}