fastarena 0.2.0

use core::marker::PhantomData;
use core::mem::{self, ManuallyDrop};
use core::ptr::{self, NonNull};

use crate::arena::Arena;

/// Error returned by [`ArenaVec::try_reserve`] when allocation fails.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum TryReserveError {
    /// Computed capacity would overflow `usize`.
    CapacityOverflow,
    /// The arena is out of memory.
    AllocError,
}

impl From<core::alloc::LayoutError> for TryReserveError {
    fn from(_: core::alloc::LayoutError) -> Self {
        TryReserveError::CapacityOverflow
    }
}

impl std::fmt::Display for TryReserveError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            TryReserveError::CapacityOverflow => {
                f.write_str("capacity overflow: requested size exceeds usize::MAX")
            }
            TryReserveError::AllocError => f.write_str("arena out of memory"),
        }
    }
}

impl std::error::Error for TryReserveError {}

/// An append-only growable vector backed by arena memory.
///
/// Elements 0..`capacity` are stored in a single arena allocation. Growth
/// copies elements to a larger allocation and abandons the old one — the arena
/// reclaims both on `reset`. This gives amortised O(1) push with the same
/// cache locality as a `Vec`.
///
/// # Destructor behaviour
///
/// - **`finish()`** → elements are arena-owned; `ArenaVec` does not run their
///   destructors. If `drop-tracking` is enabled they will be dropped by
///   [`Arena::reset`] / [`Arena::rewind`].
/// - **`drop` without `finish()`** → element destructors run immediately. The
///   backing memory is not freed (the arena retains it).
///
/// # Example
///
/// ```rust
/// use fastarena::{Arena, ArenaVec};
///
/// let mut arena = Arena::new();
/// let slice: &mut [u32] = {
///     let mut v = ArenaVec::new(&mut arena);
///     v.push(1); v.push(2); v.push(3);
///     v.finish()
/// };
/// assert_eq!(slice, &[1, 2, 3]);
/// ```
pub struct ArenaVec<'arena, T> {
    arena: &'arena mut Arena,
    ptr: NonNull<T>,
    len: usize,
    cap: usize,
    _marker: PhantomData<T>,
}

impl<'arena, T> ArenaVec<'arena, T> {
    /// Create an empty `ArenaVec`. No allocation is made until the first push.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::<u32>::new(&mut arena);
    /// assert!(v.is_empty());
    /// v.push(1);
    /// assert_eq!(v.len(), 1);
    /// ```
    pub fn new(arena: &'arena mut Arena) -> Self {
        ArenaVec {
            arena,
            ptr: NonNull::dangling(),
            len: 0,
            cap: 0,
            _marker: PhantomData,
        }
    }

    /// Create an `ArenaVec` pre-allocated for `cap` elements, avoiding growth
    /// copies when the final size is known upfront.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::<u64>::with_capacity(&mut arena, 32);
    /// assert_eq!(v.capacity(), 32);
    /// for i in 0..32 { v.push(i); }
    /// assert_eq!(v.capacity(), 32); // no reallocation
    /// ```
    pub fn with_capacity(arena: &'arena mut Arena, cap: usize) -> Self {
        let mut v = ArenaVec::new(arena);
        if cap > 0 && mem::size_of::<T>() > 0 {
            v.grow_to(cap);
        } else if mem::size_of::<T>() == 0 {
            v.cap = cap;
        }
        v
    }

    /// Append `val`. Amortised O(1).
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::new(&mut arena);
    /// v.push(10u32);
    /// v.push(20);
    /// assert_eq!(v[0], 10);
    /// assert_eq!(v[1], 20);
    /// ```
    #[inline]
    pub fn push(&mut self, val: T) {
        if self.len == self.cap {
            self.grow();
        }
        unsafe { self.ptr.as_ptr().add(self.len).write(val) };
        self.len += 1;
    }

    /// Try to append `val`, returning it back on OOM.
    ///
    /// Returns `Ok(())` on success, `Err(val)` if the arena is out of memory.
    ///
    /// # Errors
    ///
    /// Returns `Err(val)` if the arena cannot allocate additional capacity.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::new(&mut arena);
    /// assert!(v.try_push(42u32).is_ok());
    /// assert_eq!(v[0], 42);
    /// ```
    #[inline]
    pub fn try_push(&mut self, val: T) -> Result<(), T> {
        if self.len == self.cap && self.try_grow().is_err() {
            return Err(val);
        }
        unsafe { self.ptr.as_ptr().add(self.len).write(val) };
        self.len += 1;
        Ok(())
    }

    /// Remove and return the last element, or `None` if empty.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::new(&mut arena);
    /// v.push(1u32);
    /// v.push(2);
    /// assert_eq!(v.pop(), Some(2));
    /// assert_eq!(v.pop(), Some(1));
    /// assert_eq!(v.pop(), None);
    /// ```
    #[inline]
    pub fn pop(&mut self) -> Option<T> {
        if self.len == 0 {
            return None;
        }
        self.len -= 1;
        Some(unsafe { self.ptr.as_ptr().add(self.len).read() })
    }

    /// Remove all elements from the vector without freeing memory.
    ///
    /// Element destructors are run if `T: Drop`. Capacity is preserved.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::new(&mut arena);
    /// v.extend_exact([1u32, 2, 3]);
    /// v.clear();
    /// assert!(v.is_empty());
    /// assert!(v.capacity() >= 3);
    /// ```
    #[inline]
    pub fn clear(&mut self) {
        if mem::needs_drop::<T>() {
            for i in 0..self.len {
                unsafe { ptr::drop_in_place(self.ptr.as_ptr().add(i)) }
            }
        }
        self.len = 0;
    }

    /// Append all items from `iter`.
    ///
    /// Requires `ExactSizeIterator` to pre-compute capacity and avoid repeated
    /// reallocation during growth.
    ///
    /// # Panics
    ///
    /// Panics if the new length would overflow `usize` or the arena is out of memory.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::new(&mut arena);
    /// v.extend_exact(0u32..5);
    /// assert_eq!(v.as_slice(), &[0, 1, 2, 3, 4]);
    /// ```
    #[inline]
    pub fn extend_exact<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = T>,
        I::IntoIter: ExactSizeIterator,
    {
        let mut iter = iter.into_iter();
        let add_len = iter.len();
        if add_len > 0 {
            let new_len = self
                .len
                .checked_add(add_len)
                .expect("ArenaVec: capacity overflow");
            let size = mem::size_of::<T>();
            if size > 0 && new_len > self.cap {
                self.grow_to(new_len);
            }
            unsafe {
                let dst = self.ptr.as_ptr().add(self.len);
                for i in 0..add_len {
                    dst.add(i).write(iter.next().unwrap());
                }
            }
            self.len = new_len;
        }
    }

    /// Copies elements from a slice into the vector.
    ///
    /// This is more efficient than `extend` when the source is already a slice,
    /// as it can use a single `memcpy`-style copy via `ptr::copy_nonoverlapping`.
    ///
    /// # Panics
    ///
    /// Panics if the new length exceeds the arena's capacity.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::new(&mut arena);
    /// v.extend_from_slice(&[1u32, 2, 3, 4]);
    /// assert_eq!(v.as_slice(), &[1, 2, 3, 4]);
    /// ```
    #[inline]
    pub fn extend_from_slice(&mut self, slice: &[T])
    where
        T: Copy,
    {
        let add_len = slice.len();
        if add_len == 0 {
            return;
        }
        let new_len = self
            .len
            .checked_add(add_len)
            .expect("ArenaVec: capacity overflow");
        if mem::size_of::<T>() > 0 && new_len > self.cap {
            self.grow_to(new_len);
        }
        unsafe {
            let dst = self.ptr.as_ptr().add(self.len);
            ptr::copy_nonoverlapping(slice.as_ptr(), dst, add_len);
        }
        self.len = new_len;
    }

    /// Returns the number of elements in the vector.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::new(&mut arena);
    /// v.extend_exact([1u32, 2, 3]);
    /// assert_eq!(v.len(), 3);
    /// ```
    #[inline(always)]
    #[must_use]
    pub fn len(&self) -> usize {
        self.len
    }

    /// Returns `true` if the vector contains no elements.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::<u32>::new(&mut arena);
    /// assert!(v.is_empty());
    /// v.push(1);
    /// assert!(!v.is_empty());
    /// ```
    #[inline(always)]
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Returns the current capacity of the vector.
    ///
    /// Capacity is the number of elements the vector can hold without
    /// reallocating. For ZSTs (zero-sized types), capacity is tracked
    /// independently of actual memory.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let v = ArenaVec::<u64>::with_capacity(&mut arena, 16);
    /// assert_eq!(v.capacity(), 16);
    /// ```
    #[inline]
    #[must_use]
    pub fn capacity(&self) -> usize {
        self.cap
    }

    /// Reserves capacity for at least `additional` more elements in the vector.
    ///
    /// After calling `reserve`, the vector will have capacity for at least
    /// `self.len() + additional` elements without reallocating. This does not
    /// change the vector's length.
    ///
    /// # Panics
    ///
    /// Panics if the new capacity overflows `usize`.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::new(&mut arena);
    /// v.push(1u32);
    /// v.reserve(10);
    /// assert!(v.capacity() >= 11);
    /// ```
    pub fn reserve(&mut self, additional: usize) {
        let required = self.len.saturating_add(additional);
        if required > self.cap {
            self.grow_to(required);
        }
    }

    /// Reserves exactly `additional` additional elements of capacity.
    ///
    /// For arena-allocated vectors, this is identical to [`reserve`](Self::reserve)
    /// since arena memory is not subject to fragmentation. The capacity may
    /// exceed `len + additional` if the arena's growth strategy requires it.
    ///
    /// # Panics
    ///
    /// Panics if the new capacity overflows `usize`.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::<u32>::new(&mut arena);
    /// v.reserve_exact(10);
    /// assert!(v.capacity() >= 10);
    /// ```
    pub fn reserve_exact(&mut self, additional: usize) {
        let required = self
            .len
            .checked_add(additional)
            .expect("ArenaVec: capacity overflow");
        if required > self.cap {
            self.grow_to(required);
        }
    }

    /// Attempts to reserve exactly `additional` additional elements of capacity.
    ///
    /// Returns an error instead of panicking when the capacity overflows or the
    /// arena is out of memory.
    ///
    /// # Errors
    ///
    /// Returns [`CapacityOverflow`](TryReserveError::CapacityOverflow) if the
    /// required capacity would overflow `usize`. Returns
    /// [`AllocError`](TryReserveError::AllocError) if the arena is out of memory.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::<u64>::new(&mut arena);
    /// assert!(v.try_reserve_exact(64).is_ok());
    /// assert!(v.capacity() >= 64);
    /// ```
    pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> {
        let required = self
            .len
            .checked_add(additional)
            .ok_or(TryReserveError::CapacityOverflow)?;
        if required > self.cap {
            self.try_grow_to(required)?;
        }
        Ok(())
    }

    /// Attempts to reserve capacity for at least `additional` more elements.
    ///
    /// Unlike [`reserve`](Self::reserve), this returns an error instead of
    /// panicking when memory cannot be allocated.
    ///
    /// # Errors
    ///
    /// Returns [`CapacityOverflow`](TryReserveError::CapacityOverflow) if the
    /// required capacity would overflow `usize`. Returns
    /// [`AllocError`](TryReserveError::AllocError) if the arena is out of memory.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v: ArenaVec<u32> = ArenaVec::new(&mut arena);
    /// assert!(v.try_reserve(100).is_ok());
    /// ```
    pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
        let required = self.len.saturating_add(additional);
        if required > self.cap {
            self.try_grow_to(required)?;
        }
        Ok(())
    }

    fn try_grow_to(&mut self, new_cap: usize) -> Result<(), TryReserveError> {
        if mem::size_of::<T>() == 0 {
            self.cap = new_cap;
            return Ok(());
        }
        let elem_size = mem::size_of::<T>();

        // In-place extension: if our tail == arena's cur_ptr, just bump forward.
        if self.cap > 0 && new_cap > self.cap {
            let our_end = self.ptr.as_ptr().wrapping_add(self.cap) as *mut u8;
            if our_end == self.arena.cur_ptr {
                let extra_bytes = (new_cap - self.cap) * elem_size;
                let new_end = our_end.wrapping_add(extra_bytes);
                if new_end <= self.arena.cur_end {
                    self.arena.cur_ptr = new_end;
                    self.cap = new_cap;
                    return Ok(());
                }
            }
        }

        let bytes = new_cap
            .checked_mul(elem_size)
            .ok_or(TryReserveError::CapacityOverflow)?;
        let raw = self
            .arena
            .try_alloc_raw(bytes, mem::align_of::<T>())
            .ok_or(TryReserveError::AllocError)?;
        let new_ptr = raw.as_ptr() as *mut T;
        if self.len > 0 {
            unsafe { ptr::copy_nonoverlapping(self.ptr.as_ptr(), new_ptr, self.len) };
        }
        self.ptr = unsafe { NonNull::new_unchecked(new_ptr) };
        self.cap = new_cap;
        Ok(())
    }

    /// Returns a slice view of the vector's current contents.
    ///
    /// The slice length equals `self.len()` at the time of the call.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::new(&mut arena);
    /// v.extend_exact([10u32, 20, 30]);
    /// assert_eq!(v.as_slice(), &[10, 20, 30]);
    /// ```
    #[inline(always)]
    #[must_use]
    pub fn as_slice(&self) -> &[T] {
        unsafe { core::slice::from_raw_parts(self.ptr.as_ptr() as *const T, self.len) }
    }

    /// Returns a mutable slice view of the vector's current contents.
    ///
    /// The slice length equals `self.len()` at the time of the call.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::new(&mut arena);
    /// v.extend_exact([1u32, 2, 3]);
    /// for x in v.as_mut_slice() { *x *= 10; }
    /// assert_eq!(v.as_slice(), &[10, 20, 30]);
    /// ```
    #[inline(always)]
    #[must_use]
    pub fn as_mut_slice(&mut self) -> &mut [T] {
        unsafe { core::slice::from_raw_parts_mut(self.ptr.as_ptr(), self.len) }
    }

    /// Returns a forward iterator over shared references to the elements.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::new(&mut arena);
    /// v.extend_exact([1u32, 2, 3]);
    /// let sum: u32 = v.iter().sum();
    /// assert_eq!(sum, 6);
    /// ```
    #[inline]
    pub fn iter(&self) -> core::slice::Iter<'_, T> {
        self.as_slice().iter()
    }

    /// Returns a forward iterator over mutable references to the elements.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::new(&mut arena);
    /// v.extend_exact([1u32, 2, 3]);
    /// for x in v.iter_mut() { *x += 10; }
    /// assert_eq!(v.as_slice(), &[11, 12, 13]);
    /// ```
    #[inline]
    pub fn iter_mut(&mut self) -> core::slice::IterMut<'_, T> {
        self.as_mut_slice().iter_mut()
    }

    /// Returns a reference to the element at index `i`, or `None` if `i >= len`.
    ///
    /// Unlike `Index`, this does not panic on out-of-range access.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::new(&mut arena);
    /// v.push(42u32);
    /// assert_eq!(v.get(0), Some(&42));
    /// assert_eq!(v.get(5), None);
    /// ```
    #[inline]
    #[must_use]
    pub fn get(&self, i: usize) -> Option<&T> {
        self.as_slice().get(i)
    }

    /// Returns a mutable reference to the element at index `i`, or `None`.
    #[inline]
    #[must_use]
    pub fn get_mut(&mut self, i: usize) -> Option<&mut T> {
        self.as_mut_slice().get_mut(i)
    }

    /// Returns a reference to the first element, or `None` if empty.
    #[inline]
    #[must_use]
    pub fn first(&self) -> Option<&T> {
        self.as_slice().first()
    }

    /// Returns a mutable reference to the first element, or `None` if empty.
    #[inline]
    #[must_use]
    pub fn first_mut(&mut self) -> Option<&mut T> {
        self.as_mut_slice().first_mut()
    }

    /// Returns a reference to the last element, or `None` if empty.
    #[inline]
    #[must_use]
    pub fn last(&self) -> Option<&T> {
        self.as_slice().last()
    }

    /// Returns a mutable reference to the last element, or `None` if empty.
    #[inline]
    #[must_use]
    pub fn last_mut(&mut self) -> Option<&mut T> {
        self.as_mut_slice().last_mut()
    }

    /// Returns `true` if the slice contains an element with the given value.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::new(&mut arena);
    /// v.extend_exact([1u32, 2, 3]);
    /// assert!(v.contains(&2));
    /// assert!(!v.contains(&7));
    /// ```
    #[inline]
    #[must_use]
    pub fn contains(&self, x: &T) -> bool
    where
        T: PartialEq,
    {
        self.as_slice().contains(x)
    }

    /// Retains only elements specified by the predicate.
    ///
    /// In other words, removes all elements `e` for which `f(&e)` returns
    /// `false`. The retained elements stay in their original order.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::new(&mut arena);
    /// v.extend_exact([1u32, 2, 3, 4, 5]);
    /// v.retain(|&x| x % 2 == 0);
    /// assert_eq!(v.as_slice(), &[2, 4]);
    /// ```
    pub fn retain<F>(&mut self, mut f: F)
    where
        F: FnMut(&T) -> bool,
    {
        self.retain_mut(|t| f(t));
    }

    /// Retains only elements specified by the predicate, with mutable access.
    pub fn retain_mut<F>(&mut self, mut f: F)
    where
        F: FnMut(&mut T) -> bool,
    {
        let len = self.len;
        let ptr = self.ptr.as_ptr();
        let mut write = 0usize;
        let mut read = 0usize;
        // SAFETY: we manually shift retained elements to the front, dropping
        // discarded ones in place.
        unsafe {
            while read < len {
                let elem = ptr.add(read);
                if f(&mut *elem) {
                    if read != write {
                        ptr::copy_nonoverlapping(elem, ptr.add(write), 1);
                    }
                    write += 1;
                } else {
                    ptr::drop_in_place(elem);
                }
                read += 1;
            }
        }
        self.len = write;
    }

    /// Removes consecutive duplicate elements according to `T: PartialEq`.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::new(&mut arena);
    /// v.extend_exact([1u32, 1, 2, 3, 3, 3, 4]);
    /// v.dedup();
    /// assert_eq!(v.as_slice(), &[1, 2, 3, 4]);
    /// ```
    pub fn dedup(&mut self)
    where
        T: PartialEq,
    {
        self.dedup_by(|a, b| a == b);
    }

    /// Removes consecutive elements considered equal by the given comparator.
    pub fn dedup_by<F>(&mut self, mut same_bucket: F)
    where
        F: FnMut(&mut T, &mut T) -> bool,
    {
        let len = self.len;
        if len <= 1 {
            return;
        }
        let ptr = self.ptr.as_ptr();
        let mut write = 1usize;
        // SAFETY: linear scan; we drop in place when discarding duplicates.
        unsafe {
            for read in 1..len {
                let prev = ptr.add(write - 1);
                let curr = ptr.add(read);
                if same_bucket(&mut *curr, &mut *prev) {
                    ptr::drop_in_place(curr);
                } else {
                    if read != write {
                        ptr::copy_nonoverlapping(curr, ptr.add(write), 1);
                    }
                    write += 1;
                }
            }
        }
        self.len = write;
    }

    /// Removes the first instance of `item` from the vector if present and
    /// returns `true`. Returns `false` if no such element existed.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::new(&mut arena);
    /// v.extend_exact([1u32, 2, 3]);
    /// assert!(v.remove_item(&2));
    /// assert_eq!(v.as_slice(), &[1, 3]);
    /// assert!(!v.remove_item(&7));
    /// ```
    pub fn remove_item(&mut self, item: &T) -> bool
    where
        T: PartialEq,
    {
        if let Some(idx) = self.as_slice().iter().position(|x| x == item) {
            self.swap_remove(idx);
            true
        } else {
            false
        }
    }

    /// Removes an element at `index`, replacing it with the last element.
    ///
    /// O(1). Does not preserve element order. Panics if `index >= len`.
    pub fn swap_remove(&mut self, index: usize) -> T {
        assert!(
            index < self.len,
            "swap_remove index {index} out of bounds (len={})",
            self.len
        );
        let last = self.len - 1;
        let ptr = self.ptr.as_ptr();
        unsafe {
            let val = ptr.add(index).read();
            if index != last {
                ptr::copy_nonoverlapping(ptr.add(last), ptr.add(index), 1);
            }
            self.len = last;
            val
        }
    }

    /// Shortens the vector, keeping the first `len` elements and dropping the rest.
    ///
    /// If `len` is greater than the vector's current length, this has no effect.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::new(&mut arena);
    /// v.extend_exact([1u32, 2, 3, 4, 5]);
    /// v.truncate(3);
    /// assert_eq!(v.as_slice(), &[1, 2, 3]);
    /// ```
    #[inline]
    pub fn truncate(&mut self, len: usize) {
        if len < self.len {
            if mem::needs_drop::<T>() {
                for i in len..self.len {
                    unsafe { ptr::drop_in_place(self.ptr.as_ptr().add(i)) }
                }
            }
            self.len = len;
        }
    }

    /// Resizes the vector to `new_len` elements.
    ///
    /// If `new_len` is greater than the current length, `val` is cloned to fill
    /// the difference. If `new_len` is less than the current length, the vector
    /// is truncated.
    ///
    /// # Panics
    ///
    /// Panics if the arena is out of memory and `new_len > self.len()`.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let mut v = ArenaVec::new(&mut arena);
    /// v.extend_exact([1u32, 2, 3]);
    /// v.resize(5, 0);
    /// assert_eq!(v.as_slice(), &[1, 2, 3, 0, 0]);
    /// v.resize(2, 0);
    /// assert_eq!(v.as_slice(), &[1, 2]);
    /// ```
    pub fn resize(&mut self, new_len: usize, val: T)
    where
        T: Clone,
    {
        if new_len > self.len {
            let extra = new_len - self.len;
            if new_len > self.cap {
                self.grow_to(new_len);
            }
            let dst = unsafe { self.ptr.as_ptr().add(self.len) };
            for i in 0..extra {
                unsafe { dst.add(i).write(val.clone()) };
            }
            self.len = new_len;
        } else {
            self.truncate(new_len);
        }
    }

    /// Consume the `ArenaVec`, returning a `&'arena mut [T]` backed by arena
    /// memory.
    ///
    /// The arena borrow is released, so further allocations are possible.
    ///
    /// # Destructor behaviour
    ///
    /// - **Without `drop-tracking`** — element destructors are never called.
    ///   The slice may dangle after [`Arena::reset`] / [`Arena::rewind`].
    /// - **With `drop-tracking`** — the slice is registered with the arena's
    ///   drop registry as part of `finish()`, so its destructors will run in
    ///   LIFO order on the next reset/rewind.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fastarena::{Arena, ArenaVec};
    ///
    /// let mut arena = Arena::new();
    /// let slice: &mut [u32] = {
    ///     let mut v = ArenaVec::new(&mut arena);
    ///     v.extend_exact([1, 2, 3]);
    ///     v.finish()
    /// };
    /// assert_eq!(slice, &[1, 2, 3]);
    /// ```
    #[must_use = "finish() returns the underlying slice; discarding it leaks the elements"]
    pub fn finish(self) -> &'arena mut [T] {
        let mut this = ManuallyDrop::new(self);
        let ptr = this.ptr.as_ptr();
        let len = this.len;

        // With drop-tracking enabled, hand off element destruction to the
        // arena. Without drop-tracking, this is a no-op.
        #[cfg(feature = "drop-tracking")]
        if mem::needs_drop::<T>() && len > 0 {
            // SAFETY: `ptr` points to `len` initialized `T`s allocated from
            // `this.arena`. ArenaVec hasn't registered them previously
            // (push uses raw allocation, not `arena.alloc`), so no double-drop.
            unsafe { this.arena.register_drop_slice(ptr, len) };
        }
        // Suppress the unused mut warning when drop-tracking is disabled.
        let _ = &mut this;

        // SAFETY: ptr..ptr+len is a valid initialized slice in arena memory.
        unsafe { core::slice::from_raw_parts_mut(ptr, len) }
    }

    #[cold]
    #[inline(never)]
    fn grow(&mut self) {
        // Use 1.5x growth (`new = old * 3 / 2`) instead of 2x doubling. In an
        // arena, abandoned old buffers stay resident until reset, so smaller
        // growth factors reduce wasted memory while remaining amortized O(1).
        let new_cap = if self.cap == 0 {
            4
        } else {
            self.cap
                .checked_mul(3)
                .map(|v| v / 2)
                .filter(|v| *v > self.cap)
                .or_else(|| self.cap.checked_add(1))
                .expect("ArenaVec: capacity overflow")
        };
        self.grow_to(new_cap);
    }

    #[cold]
    fn try_grow(&mut self) -> Result<(), TryReserveError> {
        let new_cap = if self.cap == 0 {
            4
        } else {
            // 1.5x growth, mirroring `grow()`.
            self.cap
                .checked_mul(3)
                .map(|v| v / 2)
                .filter(|v| *v > self.cap)
                .or_else(|| self.cap.checked_add(1))
                .ok_or(TryReserveError::CapacityOverflow)?
        };
        self.try_grow_to(new_cap)
    }

    #[cold]
    fn grow_to(&mut self, new_cap: usize) {
        if mem::size_of::<T>() == 0 {
            self.cap = new_cap;
            return;
        }
        let elem_size = mem::size_of::<T>();

        // In-place extension: if our tail == arena's cur_ptr, just bump forward.
        if self.cap > 0 && new_cap > self.cap {
            let our_end = self.ptr.as_ptr().wrapping_add(self.cap) as *mut u8;
            if our_end == self.arena.cur_ptr {
                let extra_bytes = (new_cap - self.cap) * elem_size;
                let new_end = our_end.wrapping_add(extra_bytes);
                if new_end <= self.arena.cur_end {
                    self.arena.cur_ptr = new_end;
                    self.cap = new_cap;
                    return;
                }
            }
        }

        let bytes = new_cap
            .checked_mul(elem_size)
            .expect("ArenaVec: capacity overflow");
        let raw = self.arena.alloc_raw(bytes, mem::align_of::<T>());
        let new_ptr = raw.as_ptr() as *mut T;
        if self.len > 0 {
            unsafe { ptr::copy_nonoverlapping(self.ptr.as_ptr(), new_ptr, self.len) };
        }
        self.ptr = unsafe { NonNull::new_unchecked(new_ptr) };
        self.cap = new_cap;
    }
}

impl<T> core::ops::Deref for ArenaVec<'_, T> {
    type Target = [T];
    #[inline]
    fn deref(&self) -> &[T] {
        self.as_slice()
    }
}

impl<T> core::ops::DerefMut for ArenaVec<'_, T> {
    #[inline]
    fn deref_mut(&mut self) -> &mut [T] {
        self.as_mut_slice()
    }
}

impl<T> AsRef<[T]> for ArenaVec<'_, T> {
    #[inline]
    fn as_ref(&self) -> &[T] {
        self.as_slice()
    }
}

impl<T> AsMut<[T]> for ArenaVec<'_, T> {
    #[inline]
    fn as_mut(&mut self) -> &mut [T] {
        self.as_mut_slice()
    }
}

impl<T> core::borrow::Borrow<[T]> for ArenaVec<'_, T> {
    #[inline]
    fn borrow(&self) -> &[T] {
        self.as_slice()
    }
}

impl<T> core::borrow::BorrowMut<[T]> for ArenaVec<'_, T> {
    #[inline]
    fn borrow_mut(&mut self) -> &mut [T] {
        self.as_mut_slice()
    }
}

impl<T: PartialEq> PartialEq for ArenaVec<'_, T> {
    #[inline]
    fn eq(&self, other: &Self) -> bool {
        self.as_slice() == other.as_slice()
    }
}

impl<T: PartialEq> PartialEq<[T]> for ArenaVec<'_, T> {
    #[inline]
    fn eq(&self, other: &[T]) -> bool {
        self.as_slice() == other
    }
}

impl<T: PartialEq, const N: usize> PartialEq<[T; N]> for ArenaVec<'_, T> {
    #[inline]
    fn eq(&self, other: &[T; N]) -> bool {
        self.as_slice() == other
    }
}

impl<T: Eq> Eq for ArenaVec<'_, T> {}

impl<T: core::hash::Hash> core::hash::Hash for ArenaVec<'_, T> {
    #[inline]
    fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
        self.as_slice().hash(state)
    }
}

impl<T> core::ops::Index<usize> for ArenaVec<'_, T> {
    type Output = T;
    fn index(&self, i: usize) -> &T {
        assert!(i < self.len, "index {i} out of bounds (len={})", self.len);
        unsafe { &*self.ptr.as_ptr().add(i) }
    }
}

impl<T> core::ops::IndexMut<usize> for ArenaVec<'_, T> {
    fn index_mut(&mut self, i: usize) -> &mut T {
        assert!(i < self.len, "index {i} out of bounds (len={})", self.len);
        unsafe { &mut *self.ptr.as_ptr().add(i) }
    }
}

impl<T> Drop for ArenaVec<'_, T> {
    fn drop(&mut self) {
        if mem::needs_drop::<T>() {
            for i in 0..self.len {
                unsafe { ptr::drop_in_place(self.ptr.as_ptr().add(i)) }
            }
        }
    }
}

impl<T: std::fmt::Debug> std::fmt::Debug for ArenaVec<'_, T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_list().entries(self.as_slice().iter()).finish()
    }
}

impl<'arena, T> Extend<T> for ArenaVec<'arena, T> {
    /// Extends the vector by consuming items from the iterator one by one.
    ///
    /// This trait impl accepts any `IntoIterator`, unlike the [`extend_exact`](ArenaVec::extend_exact)
    /// method which requires `ExactSizeIterator` to pre-allocate capacity.
    fn extend<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = T>,
    {
        for item in iter {
            self.push(item);
        }
    }
}

impl<'arena, T> IntoIterator for ArenaVec<'arena, T> {
    type Item = T;
    type IntoIter = ArenaVecIntoIter<'arena, T>;
    fn into_iter(self) -> Self::IntoIter {
        ArenaVecIntoIter {
            inner: self,
            start: 0,
        }
    }
}

/// Owning iterator over an [`ArenaVec`]. Drains elements front-to-back and
/// drops any remaining elements (in LIFO order) when the iterator itself is dropped.
pub struct ArenaVecIntoIter<'arena, T> {
    inner: ArenaVec<'arena, T>,
    start: usize,
}

impl<'arena, T> Iterator for ArenaVecIntoIter<'arena, T> {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        if self.start >= self.inner.len {
            return None;
        }
        let val = unsafe { self.inner.ptr.as_ptr().add(self.start).read() };
        self.start += 1;
        Some(val)
    }
    fn size_hint(&self) -> (usize, Option<usize>) {
        let remaining = self.inner.len - self.start;
        (remaining, Some(remaining))
    }
}

impl<'arena, T> ExactSizeIterator for ArenaVecIntoIter<'arena, T> {}

impl<T> Drop for ArenaVecIntoIter<'_, T> {
    fn drop(&mut self) {
        if core::mem::needs_drop::<T>() {
            for i in self.start..self.inner.len {
                unsafe { core::ptr::drop_in_place(self.inner.ptr.as_ptr().add(i)) }
            }
        }
        self.inner.len = 0;
    }
}

impl<'a, T> IntoIterator for &'a ArenaVec<'_, T> {
    type Item = &'a T;
    type IntoIter = core::slice::Iter<'a, T>;
    fn into_iter(self) -> Self::IntoIter {
        self.as_slice().iter()
    }
}

impl<'a, T> IntoIterator for &'a mut ArenaVec<'_, T> {
    type Item = &'a mut T;
    type IntoIter = core::slice::IterMut<'a, T>;
    fn into_iter(self) -> Self::IntoIter {
        self.as_mut_slice().iter_mut()
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use core::sync::atomic::{AtomicUsize, Ordering};

    #[test]
    fn push_and_index() {
        let mut arena = Arena::new();
        let mut v = ArenaVec::new(&mut arena);
        for i in 0u32..8 {
            v.push(i);
        }
        for i in 0u32..8 {
            assert_eq!(v[i as usize], i);
        }
    }

    #[test]
    fn pop_order() {
        let mut arena = Arena::new();
        let mut v = ArenaVec::new(&mut arena);
        v.push(1u32);
        v.push(2);
        v.push(3);
        assert_eq!(v.pop(), Some(3));
        assert_eq!(v.pop(), Some(2));
        assert_eq!(v.pop(), Some(1));
        assert_eq!(v.pop(), None);
    }

    #[test]
    fn finish_slice() {
        let mut arena = Arena::new();
        let s = {
            let mut v = ArenaVec::new(&mut arena);
            v.extend_exact(0u32..5);
            v.finish()
        };
        assert_eq!(s, &[0, 1, 2, 3, 4]);
        let _ = arena.alloc(99u32);
    }

    #[test]
    fn grow_many() {
        let mut arena = Arena::new();
        let mut v = ArenaVec::new(&mut arena);
        for i in 0u64..256 {
            v.push(i);
        }
        for i in 0u64..256 {
            assert_eq!(v[i as usize], i);
        }
    }

    #[test]
    fn with_capacity_no_realloc() {
        let mut arena = Arena::new();
        let mut v = ArenaVec::<u64>::with_capacity(&mut arena, 16);
        let cap0 = v.capacity();
        for i in 0u64..16 {
            v.push(i);
        }
        assert_eq!(v.capacity(), cap0);
        let _ = v.finish();
    }

    #[test]
    fn drop_runs_dtors() {
        static N: AtomicUsize = AtomicUsize::new(0);
        struct D;
        impl Drop for D {
            fn drop(&mut self) {
                N.fetch_add(1, Ordering::Relaxed);
            }
        }
        N.store(0, Ordering::Relaxed);
        {
            let mut arena = Arena::new();
            let mut v = ArenaVec::new(&mut arena);
            v.push(D);
            v.push(D);
            v.push(D);
        }
        assert_eq!(N.load(Ordering::Relaxed), 3);
    }

    #[test]
    fn finish_skips_dtors() {
        static N: AtomicUsize = AtomicUsize::new(0);
        struct D;
        impl Drop for D {
            fn drop(&mut self) {
                N.fetch_add(1, Ordering::Relaxed);
            }
        }
        N.store(0, Ordering::Relaxed);
        let mut arena = Arena::new();
        let v = {
            let mut av = ArenaVec::new(&mut arena);
            av.push(D);
            av.push(D);
            av.finish()
        };
        assert_eq!(N.load(Ordering::Relaxed), 0);
        let _ = v;
    }

    #[test]
    fn zst_push() {
        let mut arena = Arena::new();
        let mut v: ArenaVec<()> = ArenaVec::new(&mut arena);
        for _ in 0..1000 {
            v.push(());
        }
        assert_eq!(v.len(), 1000);
    }

    #[test]
    #[should_panic = "out of bounds"]
    fn oob_panics() {
        let mut arena = Arena::new();
        let mut v = ArenaVec::new(&mut arena);
        v.push(1u32);
        let _ = v[1];
    }

    #[test]
    fn into_iter_yields_forward_order() {
        let mut arena = Arena::new();
        let mut v = ArenaVec::new(&mut arena);
        v.push(1u32);
        v.push(2);
        v.push(3);
        let collected: Vec<u32> = v.into_iter().collect();
        assert_eq!(collected, &[1, 2, 3]);
    }
}