oxc_allocator/
vec.rs

1//! Arena Vec.
2//!
3//! Originally based on [jsparagus](https://github.com/mozilla-spidermonkey/jsparagus/blob/24004745a8ed4939fc0dc7332bfd1268ac52285f/crates/ast/src/arena.rs)
4
5// All methods which just delegate to `allocator_api2::vec::Vec` methods marked `#[inline(always)]`
6#![expect(clippy::inline_always)]
7
8use std::{
9    self,
10    fmt::{self, Debug},
11    hash::{Hash, Hasher},
12    ops,
13    ptr::NonNull,
14    slice::SliceIndex,
15};
16
17#[cfg(any(feature = "serialize", test))]
18use serde::{Serialize, Serializer as SerdeSerializer};
19
20#[cfg(any(feature = "serialize", test))]
21use oxc_estree::{ConcatElement, ESTree, SequenceSerializer, Serializer as ESTreeSerializer};
22
23use crate::{Allocator, Box, bump::Bump, vec2::Vec as InnerVecGeneric};
24
25type InnerVec<'a, T> = InnerVecGeneric<'a, T, Bump>;
26
27/// A `Vec` without [`Drop`], which stores its data in the arena allocator.
28///
29/// # No `Drop`s
30///
31/// Objects allocated into Oxc memory arenas are never [`Dropped`](Drop). Memory is released in bulk
32/// when the allocator is dropped, without dropping the individual objects in the arena.
33///
34/// Therefore, it would produce a memory leak if you allocated [`Drop`] types into the arena
35/// which own memory allocations outside the arena.
36///
37/// Static checks make this impossible to do. [`Vec::new_in`] and all other methods which create
38/// a [`Vec`] will refuse to compile if called with a [`Drop`] type.
39#[derive(PartialEq, Eq)]
40#[repr(transparent)]
41pub struct Vec<'alloc, T>(InnerVec<'alloc, T>);
42
43/// SAFETY: Even though `Bump` is not `Sync`, we can make `Vec<T>` `Sync` if `T` is `Sync` because:
44///
45/// 1. No public methods allow access to the `&Bump` that `Vec` contains (in `RawVec`),
46///    so user cannot illegally obtain 2 `&Bump`s on different threads via `Vec`.
47///
48/// 2. All internal methods which access the `&Bump` take a `&mut self`.
49///    `&mut Vec` cannot be transferred across threads, and nor can an owned `Vec` (`Vec` is not `Send`).
50///    Therefore these methods taking `&mut self` can be sure they're not operating on a `Vec`
51///    which has been moved across threads.
52///
53/// Note: `Vec` CANNOT be `Send`, even if `T` is `Send`, because that would allow 2 `Vec`s on different
54/// threads to both allocate into same arena simultaneously. `Bump` is not thread-safe, and this would
55/// be undefined behavior.
56unsafe impl<T: Sync> Sync for Vec<'_, T> {}
57
58impl<'alloc, T> Vec<'alloc, T> {
59    /// Const assertion that `T` is not `Drop`.
60    /// Must be referenced in all methods which create a `Vec`.
61    const ASSERT_T_IS_NOT_DROP: () =
62        assert!(!std::mem::needs_drop::<T>(), "Cannot create a Vec<T> where T is a Drop type");
63
64    /// Constructs a new, empty `Vec<T>`.
65    ///
66    /// The vector will not allocate until elements are pushed onto it.
67    ///
68    /// # Examples
69    /// ```
70    /// use oxc_allocator::{Allocator, Vec};
71    ///
72    /// let allocator = Allocator::default();
73    ///
74    /// let mut vec: Vec<i32> = Vec::new_in(&allocator);
75    /// assert!(vec.is_empty());
76    /// ```
77    #[inline(always)]
78    pub fn new_in(allocator: &'alloc Allocator) -> Self {
79        const { Self::ASSERT_T_IS_NOT_DROP };
80
81        Self(InnerVec::new_in(allocator.bump()))
82    }
83
84    /// Constructs a new, empty `Vec<T>` with at least the specified capacity
85    /// with the provided allocator.
86    ///
87    /// The vector will be able to hold at least `capacity` elements without
88    /// reallocating. This method is allowed to allocate for more elements than
89    /// `capacity`. If `capacity` is 0, the vector will not allocate.
90    ///
91    /// It is important to note that although the returned vector has the
92    /// minimum *capacity* specified, the vector will have a zero *length*.
93    ///
94    /// For `Vec<T>` where `T` is a zero-sized type, there will be no allocation
95    /// and the capacity will always be `u32::MAX`.
96    ///
97    /// # Panics
98    ///
99    /// Panics if the new capacity exceeds `isize::MAX` bytes.
100    ///
101    /// # Examples
102    /// ```
103    /// use oxc_allocator::{Allocator, Vec};
104    ///
105    /// let allocator = Allocator::default();
106    ///
107    /// let mut vec = Vec::with_capacity_in(10, &allocator);
108    ///
109    /// // The vector contains no items, even though it has capacity for more
110    /// assert_eq!(vec.len(), 0);
111    /// assert_eq!(vec.capacity(), 10);
112    ///
113    /// // These are all done without reallocating...
114    /// for i in 0..10 {
115    ///     vec.push(i);
116    /// }
117    /// assert_eq!(vec.len(), 10);
118    /// assert_eq!(vec.capacity(), 10);
119    ///
120    /// // ...but this may make the vector reallocate
121    /// vec.push(11);
122    /// assert_eq!(vec.len(), 11);
123    /// assert!(vec.capacity() >= 11);
124    ///
125    /// // A vector of a zero-sized type will always over-allocate, since no
126    /// // allocation is necessary
127    /// let vec_units = Vec::<()>::with_capacity_in(10, &allocator);
128    /// assert_eq!(vec_units.capacity(), usize::MAX);
129    /// ```
130    #[inline(always)]
131    pub fn with_capacity_in(capacity: usize, allocator: &'alloc Allocator) -> Self {
132        const { Self::ASSERT_T_IS_NOT_DROP };
133
134        Self(InnerVec::with_capacity_in(capacity, allocator.bump()))
135    }
136
137    /// Create a new [`Vec`] whose elements are taken from an iterator and
138    /// allocated in the given `allocator`.
139    ///
140    /// This is behaviorially identical to [`FromIterator::from_iter`].
141    #[inline]
142    pub fn from_iter_in<I: IntoIterator<Item = T>>(iter: I, allocator: &'alloc Allocator) -> Self {
143        const { Self::ASSERT_T_IS_NOT_DROP };
144
145        let iter = iter.into_iter();
146        let hint = iter.size_hint();
147        let capacity = hint.1.unwrap_or(hint.0);
148        let mut vec = InnerVec::with_capacity_in(capacity, allocator.bump());
149        vec.extend(iter);
150        Self(vec)
151    }
152
153    /// Create a new [`Vec`] from a fixed-size array, allocated in the given `allocator`.
154    ///
155    /// This is preferable to `from_iter_in` where source is an array, as size is statically known,
156    /// and compiler is more likely to construct the values directly in arena, rather than constructing
157    /// on stack and then copying to arena.
158    ///
159    /// # Examples
160    /// ```
161    /// use oxc_allocator::{Allocator, Vec};
162    ///
163    /// let allocator = Allocator::default();
164    ///
165    /// let array: [u32; 4] = [1, 2, 3, 4];
166    /// let vec = Vec::from_array_in(array, &allocator);
167    /// ```
168    #[inline]
169    pub fn from_array_in<const N: usize>(array: [T; N], allocator: &'alloc Allocator) -> Self {
170        const { Self::ASSERT_T_IS_NOT_DROP };
171
172        let boxed = Box::new_in(array, allocator);
173        let ptr = Box::into_non_null(boxed).as_ptr().cast::<T>();
174        // SAFETY: `ptr` has correct alignment - it was just allocated as `[T; N]`.
175        // `ptr` was allocated with correct size for `[T; N]`.
176        // `len` and `capacity` are both `N`.
177        // Allocated size cannot be larger than `isize::MAX`, or `Box::new_in` would have failed.
178        let vec = unsafe { InnerVec::from_raw_parts_in(ptr, N, N, allocator.bump()) };
179        Self(vec)
180    }
181
182    /// Convert [`Vec<T>`] into [`Box<[T]>`].
183    ///
184    /// Any spare capacity in the `Vec` is lost.
185    ///
186    /// [`Box<[T]>`]: Box
187    #[inline]
188    pub fn into_boxed_slice(self) -> Box<'alloc, [T]> {
189        let slice = self.0.into_bump_slice_mut();
190        let ptr = NonNull::from(slice);
191        // SAFETY: `ptr` points to a valid `[T]`.
192        // Contents of the `Vec` are in an arena.
193        // The returned `Box` has same lifetime as the `Vec`.
194        // `Vec` is not `Drop`, so we don't need to free any unused capacity in the `Vec`.
195        unsafe { Box::from_non_null(ptr) }
196    }
197
198    /// Converts [`Vec<T>`] into [`&'alloc [T]`].
199    ///
200    /// # Examples
201    ///
202    /// ```
203    /// use oxc_allocator::{Allocator, Vec};
204    ///
205    /// let allocator = Allocator::default();
206    ///
207    /// let mut vec = Vec::from_iter_in([1, 2, 3], &allocator);
208    /// let slice = vec.into_bump_slice();
209    /// assert_eq!(slice, [1, 2, 3]);
210    /// ```
211    #[inline]
212    pub fn into_bump_slice(self) -> &'alloc [T] {
213        self.0.into_bump_slice()
214    }
215}
216
217impl<'alloc, T> ops::Deref for Vec<'alloc, T> {
218    type Target = InnerVec<'alloc, T>;
219
220    #[inline]
221    fn deref(&self) -> &Self::Target {
222        &self.0
223    }
224}
225
226impl<'alloc, T> ops::DerefMut for Vec<'alloc, T> {
227    #[inline]
228    fn deref_mut(&mut self) -> &mut InnerVec<'alloc, T> {
229        &mut self.0
230    }
231}
232
233impl<'alloc, T> IntoIterator for Vec<'alloc, T> {
234    type IntoIter = <InnerVec<'alloc, T> as IntoIterator>::IntoIter;
235    type Item = T;
236
237    #[inline(always)]
238    fn into_iter(self) -> Self::IntoIter {
239        self.0.into_iter()
240    }
241}
242
243impl<'i, T> IntoIterator for &'i Vec<'_, T> {
244    type IntoIter = std::slice::Iter<'i, T>;
245    type Item = &'i T;
246
247    #[inline(always)]
248    fn into_iter(self) -> Self::IntoIter {
249        self.0.iter()
250    }
251}
252
253impl<'i, T> IntoIterator for &'i mut Vec<'_, T> {
254    type IntoIter = std::slice::IterMut<'i, T>;
255    type Item = &'i mut T;
256
257    #[inline(always)]
258    fn into_iter(self) -> Self::IntoIter {
259        self.0.iter_mut()
260    }
261}
262
263impl<T, I> ops::Index<I> for Vec<'_, T>
264where
265    I: SliceIndex<[T]>,
266{
267    type Output = I::Output;
268
269    #[inline(always)]
270    fn index(&self, index: I) -> &Self::Output {
271        self.0.index(index)
272    }
273}
274
275impl<T, I> ops::IndexMut<I> for Vec<'_, T>
276where
277    I: SliceIndex<[T]>,
278{
279    #[inline(always)]
280    fn index_mut(&mut self, index: I) -> &mut Self::Output {
281        self.0.index_mut(index)
282    }
283}
284
285impl<'a, T: 'a> From<Vec<'a, T>> for Box<'a, [T]> {
286    #[inline(always)]
287    fn from(v: Vec<'a, T>) -> Box<'a, [T]> {
288        v.into_boxed_slice()
289    }
290}
291
292#[cfg(any(feature = "serialize", test))]
293impl<T: Serialize> Serialize for Vec<'_, T> {
294    fn serialize<S: SerdeSerializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
295        self.as_slice().serialize(serializer)
296    }
297}
298
299#[cfg(any(feature = "serialize", test))]
300impl<T: ESTree> ESTree for Vec<'_, T> {
301    fn serialize<S: ESTreeSerializer>(&self, serializer: S) {
302        self.as_slice().serialize(serializer);
303    }
304}
305
306#[cfg(feature = "serialize")]
307impl<T: ESTree> ConcatElement for Vec<'_, T> {
308    fn push_to_sequence<S: SequenceSerializer>(&self, seq: &mut S) {
309        for element in self {
310            seq.serialize_element(element);
311        }
312    }
313}
314
315impl<T: Hash> Hash for Vec<'_, T> {
316    #[inline(always)]
317    fn hash<H: Hasher>(&self, state: &mut H) {
318        self.0.hash(state);
319    }
320}
321
322impl<T: Debug> Debug for Vec<'_, T> {
323    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
324        f.debug_tuple("Vec").field(&self.0).finish()
325    }
326}
327
328#[cfg(test)]
329mod test {
330    use super::Vec;
331    use crate::Allocator;
332
333    #[test]
334    fn vec_with_capacity() {
335        let allocator = Allocator::default();
336        let v: Vec<i32> = Vec::with_capacity_in(10, &allocator);
337        assert!(v.is_empty());
338    }
339
340    #[test]
341    fn vec_debug() {
342        let allocator = Allocator::default();
343        let mut v = Vec::new_in(&allocator);
344        v.push("x");
345        let v = format!("{v:?}");
346        assert_eq!(v, "Vec([\"x\"])");
347    }
348
349    #[test]
350    fn vec_into_boxed_slice() {
351        let allocator = Allocator::default();
352        let mut v = Vec::with_capacity_in(4, &allocator);
353        v.push("x");
354        v.push("y");
355        let boxed_slice = v.into_boxed_slice();
356        assert_eq!(boxed_slice.as_ref(), &["x", "y"]);
357    }
358
359    #[test]
360    fn vec_serialize() {
361        let allocator = Allocator::default();
362        let mut v = Vec::new_in(&allocator);
363        v.push("x");
364        let s = serde_json::to_string(&v).unwrap();
365        assert_eq!(s, r#"["x"]"#);
366    }
367
368    #[test]
369    fn vec_serialize_estree() {
370        use oxc_estree::{CompactTSSerializer, ESTree};
371
372        let allocator = Allocator::default();
373        let mut v = Vec::new_in(&allocator);
374        v.push("x");
375
376        let mut serializer = CompactTSSerializer::default();
377        v.serialize(&mut serializer);
378        let s = serializer.into_string();
379        assert_eq!(s, r#"["x"]"#);
380    }
381
382    #[test]
383    fn lifetime_variance() {
384        fn _assert_vec_variant_lifetime<'a: 'b, 'b, T>(program: Vec<'a, T>) -> Vec<'b, T> {
385            program
386        }
387    }
388}
oxc_allocator/vec.rs

oxc_allocator/
vec.rs
