oxc_allocator 0.143.0

//! Arena Box.
//!
//! Originally based on [jsparagus](https://github.com/mozilla-spidermonkey/jsparagus/blob/24004745a8ed4939fc0dc7332bfd1268ac52285f/crates/ast/src/arena.rs)

use std::{
    self,
    fmt::{self, Debug, Display, Formatter},
    hash::{Hash, Hasher},
    marker::PhantomData,
    mem,
    ops::{Deref, DerefMut},
    ptr::{self, NonNull},
};

#[cfg(feature = "serialize")]
use oxc_estree::{ESTree, Serializer as ESTreeSerializer};
#[cfg(feature = "serialize")]
use serde::{Serialize, Serializer as SerdeSerializer};

use crate::GetAllocator;

/// A `Box` without [`Drop`], which stores its data in the arena allocator.
///
/// # No `Drop`s
///
/// Objects allocated into Oxc memory arenas are never [`Dropped`](Drop). Memory is released in bulk
/// when the allocator is dropped, without dropping the individual objects in the arena.
///
/// Therefore, it would produce a memory leak if you allocated [`Drop`] types into the arena
/// which own memory allocations outside the arena.
///
/// Static checks make this impossible to do. [`Box::new_in`] will refuse to compile if called
/// with a [`Drop`] type.
#[repr(transparent)]
pub struct Box<'alloc, T: ?Sized>(NonNull<T>, PhantomData<(&'alloc (), T)>);

/// SAFETY: A [`Box`] has exclusive access to the `T` it points to, and grants access to nothing else,
/// so it gets the same auto traits as the `&'alloc mut T` it stands in for.
///
/// Unlike [`Vec`], a `Box` holds no `&Arena`. There is no way from a `Box` to the [`Allocator`]
/// it points into, so 2 `Box`es on different threads cannot both allocate from the same arena -
/// which is the reason `Vec` cannot be `Send`. [`new_in`] is the only method which touches an
/// [`Allocator`], and it receives one as a param, so it runs on a thread which has one already.
///
/// A `Box` is never [`Drop`], so sending one to another thread cannot free arena memory there.
/// `'alloc` borrows the arena, so it cannot be reset or dropped while a `Box` into it is alive
/// on any thread.
///
/// A `T` which itself holds arena data keeps its own bound - a `Box<Vec<T>>` is not `Send`,
/// because [`Vec`] is not.
///
/// [`Vec`]: crate::Vec
/// [`Allocator`]: crate::Allocator
/// [`new_in`]: Box::new_in
unsafe impl<T: Send + ?Sized> Send for Box<'_, T> {}

/// SAFETY: Sharing a `&Box<T>` shares only a `&T`, so `T` being [`Sync`] is what it takes.
/// The [`Send`] impl above covers why a `Box` grants access to nothing else.
unsafe impl<T: Sync + ?Sized> Sync for Box<'_, T> {}

impl<T: ?Sized> Box<'_, T> {
    /// Const assertion that `T` is not `Drop`.
    /// Must be referenced in all methods which create a `Box`.
    const ASSERT_T_IS_NOT_DROP: () =
        assert!(!std::mem::needs_drop::<T>(), "Cannot create a Box<T> where T is a Drop type");
}

impl<'alloc, T> Box<'alloc, T> {
    /// Allocate `value` into the memory arena, and receive a [`Box`] which owns the value.
    ///
    /// # Examples
    ///
    /// ```
    /// use oxc_allocator::{Allocator, Box};
    ///
    /// let arena = Allocator::default();
    /// let arena = &arena;
    /// let in_arena: Box<i32> = Box::new_in(5, &arena);
    /// ```
    ///
    /// The `Box` cannot outlive the `Allocator`. This fails to compile:
    ///
    /// ```compile_fail
    /// use oxc_allocator::{Allocator, Box};
    ///
    /// let boxed = {
    ///     let allocator = Allocator::default();
    ///     let allocator = &allocator;
    ///     Box::new_in(5, &allocator)
    /// };
    /// assert_eq!(*boxed, 5);
    /// ```
    //
    // `#[inline(always)]` because this is a hot path and `Allocator::alloc` is a very small function.
    // We always want it to be inlined.
    #[expect(clippy::inline_always)]
    #[inline(always)]
    pub fn new_in(value: T, allocator: &impl GetAllocator<'alloc>) -> Self {
        const { Self::ASSERT_T_IS_NOT_DROP };

        Self(NonNull::from(allocator.allocator().alloc(value)), PhantomData)
    }

    /// Take ownership of the value stored in this [`Box`], consuming the box in
    /// the process.
    ///
    /// # Examples
    /// ```
    /// use oxc_allocator::{Allocator, Box};
    ///
    /// let arena = Allocator::default();
    /// let arena = &arena;
    ///
    /// // Put `5` into the arena and on the heap.
    /// let boxed: Box<i32> = Box::new_in(5, &arena);
    /// // Move it back to the stack. `boxed` has been consumed.
    /// let i = boxed.unbox();
    ///
    /// assert_eq!(i, 5);
    /// ```
    #[inline]
    pub fn unbox(self) -> T {
        // SAFETY:
        // This pointer read is safe because the reference `self.0` is
        // guaranteed to be unique - not just now, but we're guaranteed it's not
        // borrowed from some other reference. This in turn is because we never
        // construct a `Box` with a borrowed reference, only with a fresh
        // one just allocated from an `Arena`.
        unsafe { ptr::read(self.0.as_ptr()) }
    }
}

impl<T: ?Sized> Box<'_, T> {
    /// Get a [`NonNull`] pointer pointing to the [`Box`]'s contents.
    ///
    /// The pointer is not valid for writes.
    ///
    /// The caller must ensure that the `Box` outlives the pointer this
    /// function returns, or else it will end up dangling.
    ///
    /// # Example
    ///
    /// ```
    /// use oxc_allocator::{Allocator, Box};
    ///
    /// let allocator = Allocator::new();
    /// let allocator = &allocator;
    /// let boxed = Box::new_in(123_u64, &allocator);
    /// let ptr = Box::as_non_null(&boxed);
    /// ```
    //
    // `#[inline(always)]` because this is a no-op
    #[expect(clippy::inline_always)]
    #[inline(always)]
    pub fn as_non_null(boxed: &Self) -> NonNull<T> {
        boxed.0
    }

    /// Consume a [`Box`] and return a [`NonNull`] pointer to its contents.
    //
    // `#[inline(always)]` because this is a no-op
    #[expect(clippy::inline_always, clippy::needless_pass_by_value)]
    #[inline(always)]
    pub fn into_non_null(boxed: Self) -> NonNull<T> {
        boxed.0
    }

    /// Create a [`Box`] from a [`NonNull`] pointer.
    ///
    /// # SAFETY
    ///
    /// * Pointer must point to a valid `T`.
    /// * Pointer must point to within an `Allocator`.
    /// * Caller must ensure that the pointer is valid for the lifetime of the `Box`.
    pub const unsafe fn from_non_null(ptr: NonNull<T>) -> Self {
        const { Self::ASSERT_T_IS_NOT_DROP };

        Self(ptr, PhantomData)
    }
}

impl<T> Box<'static, [T]> {
    /// Create a new empty `Box<[T]>`.
    ///
    /// This method does not allocate. The returned boxed slice is represented by a dangling,
    /// correctly-aligned pointer with length 0, similar to how `Vec::new_in` produces an empty vector.
    #[inline]
    pub fn new_empty_boxed_slice() -> Self {
        const { Self::ASSERT_T_IS_NOT_DROP };

        // `NonNull::<T>::dangling()` yields a non-null, properly aligned pointer.
        // We pair it with length 0 to construct a `NonNull<[T]>` representing an empty slice.
        // Correct alignment is the only requirement for it to be sound to dereference this pointer
        // to a slice, because the slice is empty.
        // See: https://doc.rust-lang.org/std/slice/fn.from_raw_parts.html
        let ptr = NonNull::dangling();
        let slice_ptr = NonNull::slice_from_raw_parts(ptr, 0);

        Self(slice_ptr, PhantomData)
    }
}

impl<'alloc, T> Box<'alloc, [T]> {
    /// Convert a boxed slice [`Box<[T]>`] into slice [`&'alloc [T]`].
    ///
    /// The returned slice has the same lifetime as the allocator.
    //
    // `#[inline(always)]` because this is a no-op. `Box<[T]>` and `&[T]` have the same layout.
    #[expect(clippy::inline_always)]
    #[inline(always)]
    pub fn into_arena_slice(self) -> &'alloc [T] {
        let r = self.as_ref();
        // Extend lifetime of reference to lifetime of the allocator.
        // SAFETY: `self` is consumed by this method, so there cannot be any mutable references to it.
        // The reference lives until the allocator is dropped or reset (`'alloc` lifetime).
        // Don't need `mem::forget(self)` here, because `Box` does not implement `Drop`.
        unsafe { mem::transmute::<&[T], &'alloc [T]>(r) }
    }

    /// Convert a boxed slice [`Box<[T]>`] into mutable slice [`&'alloc mut [T]`].
    ///
    /// The returned slice has the same lifetime as the allocator.
    //
    // `#[inline(always)]` because this is a no-op. `Box<[T]>` and `&mut [T]` have the same layout.
    #[expect(clippy::inline_always)]
    #[inline(always)]
    pub fn into_arena_slice_mut(mut self) -> &'alloc mut [T] {
        let r = self.as_mut();
        // Extend lifetime of reference to lifetime of the allocator.
        // SAFETY: `self` is consumed by this method, so there cannot be any other references to it.
        // The reference lives until the allocator is dropped or reset (`'alloc` lifetime).
        // Don't need `mem::forget(self)` here, because `Box` does not implement `Drop`.
        unsafe { mem::transmute::<&mut [T], &'alloc mut [T]>(r) }
    }
}

impl<T: ?Sized> Deref for Box<'_, T> {
    type Target = T;

    #[inline]
    fn deref(&self) -> &T {
        // SAFETY: `self.0` is always a unique reference allocated from an `Arena` in `Box::new_in`,
        // or an empty slice allocated from `Box::new_empty_boxed_slice`
        unsafe { self.0.as_ref() }
    }
}

impl<T: ?Sized> DerefMut for Box<'_, T> {
    #[inline]
    fn deref_mut(&mut self) -> &mut T {
        // SAFETY: `self.0` is always a unique reference allocated from an `Arena` in `Box::new_in`,
        // or an empty slice allocated from `Box::new_empty_boxed_slice`
        unsafe { self.0.as_mut() }
    }
}

impl<T: ?Sized> AsRef<T> for Box<'_, T> {
    #[inline]
    fn as_ref(&self) -> &T {
        self
    }
}

impl<T: ?Sized> AsMut<T> for Box<'_, T> {
    #[inline]
    fn as_mut(&mut self) -> &mut T {
        self
    }
}

impl<T: ?Sized + Display> Display for Box<'_, T> {
    #[inline]
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        self.deref().fmt(f)
    }
}

impl<T: ?Sized + Debug> Debug for Box<'_, T> {
    #[inline]
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        self.deref().fmt(f)
    }
}

// Unused right now.
// impl<'alloc, T> PartialEq for Box<'alloc, T>
// where
// T: PartialEq<T> + ?Sized,
// {
// fn eq(&self, other: &Box<'alloc, T>) -> bool {
// PartialEq::eq(&**self, &**other)
// }
// }

#[cfg(feature = "serialize")]
impl<T: Serialize> Serialize for Box<'_, T> {
    fn serialize<S: SerdeSerializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
        self.deref().serialize(serializer)
    }
}

#[cfg(feature = "serialize")]
impl<T: ESTree> ESTree for Box<'_, T> {
    fn serialize<S: ESTreeSerializer>(&self, serializer: S) {
        self.deref().serialize(serializer);
    }
}

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

#[cfg(test)]
mod test {
    use std::{
        cell::Cell,
        hash::{DefaultHasher, Hash, Hasher},
    };

    use oxc_data_structures::types::implements;

    use crate::{Allocator, Vec};

    use super::Box;

    // A `Box` grants what a `&mut T` does, so it gets the same auto traits.
    // See `unsafe impl Send for Box`.
    #[test]
    fn box_send_sync() {
        assert!(implements!(Box<u32>: Send));
        assert!(implements!(Box<u32>: Sync));

        // `Cell` is `Send` but not `Sync`
        assert!(implements!(Box<Cell<u32>>: Send));
        assert!(implements!(Box<Cell<u32>>: !Sync));
        // `Vec` is `Sync` but not `Send`
        assert!(implements!(Box<Vec<u32>>: !Send));
        assert!(implements!(Box<Vec<u32>>: Sync));
    }

    #[test]
    fn box_deref_mut() {
        let allocator = Allocator::default();
        let allocator = &allocator;
        let mut b = Box::new_in("x", &allocator);
        let b = &mut *b;
        *b = allocator.alloc("v");
        assert_eq!(*b, "v");
    }

    #[test]
    fn new_empty_boxed_slice() {
        let b = Box::<[u32]>::new_empty_boxed_slice();
        assert!(b.is_empty());
        assert_eq!(b.len(), 0);
        assert_eq!(&*b, &[] as &[u32]);
    }

    #[test]
    fn boxed_slice_into_arena_slice() {
        let allocator = Allocator::default();
        let allocator = &allocator;
        let v = Vec::from_iter_in([1, 2, 3], &allocator);
        let b = v.into_boxed_slice();
        let slice = b.into_arena_slice();
        assert_eq!(slice, &[1, 2, 3]);
    }

    #[test]
    fn boxed_slice_into_arena_slice_mut() {
        let allocator = Allocator::default();
        let allocator = &allocator;
        let v = Vec::from_iter_in([10, 20, 30], &allocator);
        let b = v.into_boxed_slice();
        let slice = b.into_arena_slice_mut();
        slice[1] = 99;
        assert_eq!(slice, &[10, 99, 30]);
    }

    #[test]
    fn box_debug() {
        let allocator = Allocator::default();
        let allocator = &allocator;
        let b = Box::new_in("x", &allocator);
        let b = format!("{b:?}");
        assert_eq!(b, "\"x\"");
    }

    #[test]
    fn box_hash() {
        fn hash(val: &impl Hash) -> u64 {
            let mut hasher = DefaultHasher::default();
            val.hash(&mut hasher);
            hasher.finish()
        }

        let allocator = Allocator::default();
        let allocator = &allocator;
        let a = Box::new_in("x", &allocator);
        let b = Box::new_in("x", &allocator);

        assert_eq!(hash(&a), hash(&b));
    }

    #[cfg(feature = "serialize")]
    #[test]
    fn box_serialize() {
        let allocator = Allocator::default();
        let allocator = &allocator;
        let b = Box::new_in("x", &allocator);
        let s = serde_json::to_string(&b).unwrap();
        assert_eq!(s, r#""x""#);
    }

    #[cfg(feature = "serialize")]
    #[test]
    fn box_serialize_estree() {
        use oxc_estree::{CompactSerializer, ESTree};

        let allocator = Allocator::default();
        let allocator = &allocator;
        let b = Box::new_in("x", &allocator);

        let mut serializer = CompactSerializer::default();
        b.serialize(&mut serializer);
        let s = serializer.into_string();
        assert_eq!(s, r#""x""#);
    }

    #[test]
    fn lifetime_variance() {
        fn _assert_box_variant_lifetime<'a: 'b, 'b, T>(program: Box<'a, T>) -> Box<'b, T> {
            program
        }
    }
}