multitude 0.2.0

// Copyright (c) Microsoft Corporation.
// Licensed under the MIT License.

#![allow(
    clippy::type_repetition_in_bounds,
    clippy::cast_sign_loss,
    reason = "trait-impl `where` clauses are kept uniform across all forwarding impls; numeric casts are bounded by upstream `usize` checks documented at call sites"
)]

use core::borrow::BorrowMut;
use core::iter::FusedIterator;
use core::marker::PhantomData;
use core::mem::{self, MaybeUninit};
use core::ops::DerefMut;
use core::pin::Pin;
use core::ptr::{self, NonNull};

use allocator_api2::alloc::{Allocator, Global};
use ptr_meta::Pointee;

use crate::internal::chunk_ref::ChunkRef;
use crate::thin_smart_ptr_common::impl_thin_smart_ptr_common;

/// An owned, mutable smart pointer to a `T` stored in an
/// [`Arena`](crate::Arena).
///
/// Created via [`Arena::alloc_box`](crate::Arena::alloc_box).
///
/// Unlike [`Arc`](crate::Arc):
///
/// - Provides `&mut T` through `DerefMut` (exclusive ownership).
/// - **Not** [`Clone`] — single owner.
///
/// Like [`Arc`](crate::Arc), `Box` keeps its containing chunk alive by
/// holding a +1 refcount, so it can outlive the arena it came from and
/// survives [`Arena::reset`](crate::Arena::reset). Unlike `Arc`, the
/// `T` destructor runs eagerly when the `Box` itself is dropped
/// (single owner), not at chunk teardown.
///
/// # `Send` and `Sync`
///
/// `Box<T, A>` is [`Send`] when `T: Send` and `A: Send`, and [`Sync`]
/// when `T: Sync` and `A: Sync` — matching the auto-trait contract of
/// `std::boxed::Box<T, A>`. The backing storage lives in a shared
/// chunk whose refcount is atomic, so dropping the `Box` on a thread
/// other than the one that created it is sound.
///
/// # Pinning
///
/// `Box` implements [`Unpin`] unconditionally (like `std::Box`).
/// Pinning a `Box` is sound: because `Box` holds a +1 refcount on its
/// chunk, the backing memory cannot be freed or reused while the
/// `Box` exists. If a pinned `Box` is leaked via [`core::mem::forget`],
/// the refcount is never decremented and the chunk's storage persists
/// for the lifetime of the process — satisfying [`Pin`](core::pin::Pin)'s
/// drop guarantee (the pinned value's memory is never reclaimed).
///
/// # Example
///
/// ```
/// use multitude::Arena;
///
/// let arena = Arena::new();
/// let mut b = arena.alloc_box(vec![1, 2, 3]);
/// b.push(4);
/// assert_eq!(*b, vec![1, 2, 3, 4]);
/// ```
pub struct Box<T: ?Sized + Pointee, A: Allocator + Clone = Global> {
    /// **Thin** pointer to the first byte of the contained value, which
    /// lives in a 64K-aligned [`SharedChunk`]'s payload. The chunk
    /// header is recovered by masking, and `T`'s pointer metadata (if
    /// any) is stored in the `size_of::<T::Metadata>()` bytes
    /// immediately preceding the payload (read with
    /// [`core::ptr::read_unaligned`]). This makes `Box<T>` 8 bytes
    /// uniformly, even for DST `T`.
    ptr: NonNull<u8>,
    /// Marker for variance and dropck. The raw-pointer wrapping keeps
    /// auto-derivation conservative; the desired `Send`/`Sync` are
    /// re-introduced via the explicit `unsafe impl`s below so the
    /// bounds match `std::boxed::Box<T, A>`.
    _phantom: PhantomData<(*const T, A)>,
}

// SAFETY: `Box<T, A>` owns its `T` uniquely (no aliasing), and the
// storage refcount is managed by the chunk's atomic counter, so the
// `dec_ref` performed in `Drop` is thread-safe regardless of which
// thread allocated the `Box`. Sending the `Box` to another thread is
// therefore sound when `T: Send` (the value moves) and `A: Send` (the
// chunk header reaches the allocator via a `Weak<ChunkProvider<A>>` on
// teardown). Mirrors `std::boxed::Box<T, A>`'s `Send` bound.
// SAFETY: see `Box::Send`/`Box::Sync` rationale comments above. The
// `Pointee` bound is implicit (already on the `Box` struct).
unsafe impl<T: ?Sized + Pointee + Send, A: Allocator + Clone + Send> Send for Box<T, A> {}
// SAFETY: see the `Send` impl above for the cross-thread invariants.
// Sharing `&Box<T, A>` across threads exposes only `&T` (`Deref` is
// `&self -> &T`); `DerefMut` requires `&mut self` and is serialized
// by the borrow checker. So `Sync` follows `T: Sync`, with `A: Sync`
// mirrored from `std::boxed::Box<T, A>`.
unsafe impl<T: ?Sized + Pointee + Sync, A: Allocator + Clone + Sync> Sync for Box<T, A> {}

impl<T: ?Sized + Pointee, A: Allocator + Clone> Box<T, A> {
    /// Builds a `Box` from a thin payload pointer.
    ///
    /// See [`crate::Arc::from_raw`] for the metadata-recovery contract.
    ///
    /// # Safety
    ///
    /// - `thin` must reference the payload of a fully-initialized `T`
    ///   whose storage was bump-allocated from a [`SharedChunk<A>`].
    ///   For DST `T` the chunk prefix must carry the matching
    ///   `T::Metadata`.
    /// - The caller must have just acquired a +1 refcount on that
    ///   chunk in the new `Box`'s name. The returned `Box` takes
    ///   ownership of that +1 and releases it in [`Drop`].
    /// - `thin` must lie within the first `CHUNK_ALIGN` bytes of the
    ///   chunk's allocation so the header-from-mask helper recovers
    ///   the chunk address correctly.
    #[inline]
    pub(crate) unsafe fn from_raw(thin: NonNull<u8>) -> Self {
        Self {
            ptr: thin,
            _phantom: PhantomData,
        }
    }

    /// Returns the thin chunk pointer (see [`crate::Arc::thin_ptr`]).
    #[inline]
    pub(crate) fn thin_ptr(&self) -> NonNull<u8> {
        self.ptr
    }

    /// Returns a raw mutable pointer to the value (fat if `T: ?Sized` is a DST).
    #[allow(
        clippy::needless_pass_by_ref_mut,
        reason = "associated-fn convention (like alloc::rc::Rc::as_ptr); &mut self conveys exclusive access"
    )]
    #[must_use]
    #[inline]
    pub fn as_mut_ptr(this: &mut Self) -> *mut T {
        this.as_fat_ptr().as_ptr()
    }
}

impl_thin_smart_ptr_common!(Box);

// No `leak`: dropping the refcount risks UAF; keeping it leaks the chunk.

impl<T: ?Sized + Pointee, A: Allocator + Clone> Drop for Box<T, A> {
    #[inline]
    fn drop(&mut self) {
        // Adopt the chunk's +1 first, so that if `T::drop` panics,
        // the `ChunkRef`'s own `Drop` releases the refcount during
        // unwinding (the in-chunk slot itself is leaked, matching the
        // documented panic semantics).
        //
        // SAFETY: `ptr` is hosted in a 64K-aligned `SharedChunk` we
        // hold a +1 strong reference on. `ChunkRef::from_value_ptr`
        // adopts that +1 and releases it on its own drop. We then run
        // `T::drop` in place; the compiler elides this when
        // `needs_drop::<T>()` is false.
        unsafe {
            let _ref: ChunkRef<A> = ChunkRef::from_value_ptr(self.ptr);
            let fat = self.as_fat_ptr();
            ptr::drop_in_place(fat.as_ptr());
        }
    }
}

impl<T, A: Allocator + Clone> Box<MaybeUninit<T>, A> {
    /// Convert an [`Box<MaybeUninit<T>, A>`] whose value has been
    /// fully initialized into an [`Box<T, A>`]. O(1) — no copy,
    /// no allocation.
    ///
    /// # Safety
    ///
    /// The `MaybeUninit<T>` must contain a fully-initialized, valid `T`.
    #[must_use]
    #[inline]
    pub unsafe fn assume_init(self) -> Box<T, A> {
        let thin = self.ptr;
        mem::forget(self);
        // SAFETY: see scalar `Arc::<MaybeUninit<T>>::assume_init` —
        // sized `T` shares the same chunk layout (no prefix) as
        // `MaybeUninit<T>`.
        unsafe { Box::from_raw(thin) }
    }

    /// Convert a pinned `Pin<Box<MaybeUninit<T>, A>>` whose value has
    /// been fully initialized into a `Pin<Box<T, A>>`. O(1).
    ///
    /// The pin is preserved across the cast: the value's address is
    /// the same `Box` allocation's address; nothing moves.
    ///
    /// # Safety
    ///
    /// The `MaybeUninit<T>` must contain a fully-initialized, valid `T`.
    #[must_use]
    #[inline]
    pub unsafe fn assume_init_pin(this: Pin<Self>) -> Pin<Box<T, A>>
    where
        A: 'static,
    {
        // SAFETY: see `Pin::map_unchecked` + `Self::assume_init`; the
        // value's address is unchanged across this cast, and the
        // caller asserts the contents are a valid `T`.
        unsafe {
            let inner: Self = Pin::into_inner_unchecked(this);
            Box::into_pin(inner.assume_init())
        }
    }
}

impl<T, A: Allocator + Clone> Box<[MaybeUninit<T>], A> {
    /// Convert an [`Box<[MaybeUninit<T>], A>`](crate::Box) whose elements have
    /// all been fully initialized into an [`Box<[T], A>`](crate::Box). O(1) —
    /// no copy, no allocation.
    ///
    /// # Safety
    ///
    /// Every element of the slice must contain a fully-initialized,
    /// valid `T`.
    #[must_use]
    #[inline]
    pub unsafe fn assume_init(self) -> Box<[T], A> {
        let thin = self.ptr;
        mem::forget(self);
        // SAFETY: see scalar `assume_init`; `Box<[MaybeUninit<T>]>` and
        // `Box<[T]>` share the same chunk prefix layout (slice length
        // as `usize`), so the length stored there already matches the
        // new fat pointer's metadata.
        unsafe { Box::from_raw(thin) }
    }

    /// Pinned-slice variant of [`Self::assume_init_pin`]. The slice's
    /// element addresses don't change across the cast.
    ///
    /// # Safety
    ///
    /// Every element must contain a fully-initialized, valid `T`.
    #[must_use]
    #[inline]
    pub unsafe fn assume_init_pin_slice(this: Pin<Self>) -> Pin<Box<[T], A>>
    where
        A: 'static,
    {
        // SAFETY: see `Pin::map_unchecked` + `Self::assume_init`; the
        // value's address is unchanged across this cast, and the
        // caller asserts every element is a valid `T`.
        unsafe {
            let inner: Self = Pin::into_inner_unchecked(this);
            Box::into_pin(inner.assume_init())
        }
    }
}

impl<T: ?Sized + Pointee, A: Allocator + Clone> DerefMut for Box<T, A> {
    #[inline]
    fn deref_mut(&mut self) -> &mut T {
        // SAFETY: see `Deref`; `&mut self` confirms exclusive access.
        unsafe { self.as_fat_ptr().as_mut() }
    }
}

impl<T: ?Sized + Pointee, A: Allocator + Clone> AsMut<T> for Box<T, A> {
    #[inline]
    fn as_mut(&mut self) -> &mut T {
        self
    }
}

impl<T: ?Sized + Pointee, A: Allocator + Clone> BorrowMut<T> for Box<T, A> {
    #[inline]
    fn borrow_mut(&mut self) -> &mut T {
        self
    }
}

impl<I: Iterator + ?Sized + Pointee, A: Allocator + Clone> Iterator for Box<I, A> {
    type Item = I::Item;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        (**self).next()
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (**self).size_hint()
    }

    #[inline]
    fn nth(&mut self, n: usize) -> Option<Self::Item> {
        (**self).nth(n)
    }
}

impl<I: DoubleEndedIterator + ?Sized + Pointee, A: Allocator + Clone> DoubleEndedIterator for Box<I, A> {
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        (**self).next_back()
    }

    #[inline]
    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
        (**self).nth_back(n)
    }
}

impl<I: ExactSizeIterator + ?Sized + Pointee, A: Allocator + Clone> ExactSizeIterator for Box<I, A> {
    #[inline]
    fn len(&self) -> usize {
        (**self).len()
    }
}

impl<I: FusedIterator + ?Sized + Pointee, A: Allocator + Clone> FusedIterator for Box<I, A> {}