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(feature = "serialize")]
18use serde::{Serialize, Serializer as SerdeSerializer};
19
20#[cfg(feature = "serialize")]
21use oxc_estree::{ConcatElement, ESTree, SequenceSerializer, Serializer as ESTreeSerializer};
22
23use crate::{Allocator, Box, arena::Arena, vec2::Vec as InnerVecGeneric};
24
25type InnerVec<'a, T> = InnerVecGeneric<'a, T, Arena>;
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 `Arena` is not `Sync`, we can make `Vec<T>` `Sync` if `T` is `Sync` because:
44///
45/// 1. No public methods allow access to the `&Arena` that `Vec` contains (in `RawVec`),
46///    so user cannot illegally obtain 2 `&Arena`s on different threads via `Vec`.
47///
48/// 2. All internal methods which access the `&Arena` 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. `Arena` 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.arena()))
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.arena()))
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.arena());
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.arena()) };
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_arena_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_arena_slice();
209    /// assert_eq!(slice, [1, 2, 3]);
210    /// ```
211    #[inline]
212    pub fn into_arena_slice(self) -> &'alloc [T] {
213        self.0.into_arena_slice()
214    }
215
216    /// Converts [`Vec<T>`] into [`&'alloc mut [T]`].
217    ///
218    /// # Examples
219    ///
220    /// ```
221    /// use oxc_allocator::{Allocator, Vec};
222    ///
223    /// let allocator = Allocator::default();
224    ///
225    /// let vec = Vec::from_iter_in([1, 2, 3], &allocator);
226    /// let slice = vec.into_arena_slice_mut();
227    /// slice[0] = 4;
228    /// assert_eq!(slice, [4, 2, 3]);
229    /// ```
230    #[inline]
231    pub fn into_arena_slice_mut(self) -> &'alloc mut [T] {
232        self.0.into_arena_slice_mut()
233    }
234}
235
236impl<'alloc, T> ops::Deref for Vec<'alloc, T> {
237    type Target = InnerVec<'alloc, T>;
238
239    #[inline]
240    fn deref(&self) -> &Self::Target {
241        &self.0
242    }
243}
244
245impl<'alloc, T> ops::DerefMut for Vec<'alloc, T> {
246    #[inline]
247    fn deref_mut(&mut self) -> &mut InnerVec<'alloc, T> {
248        &mut self.0
249    }
250}
251
252impl<'alloc, T> IntoIterator for Vec<'alloc, T> {
253    type IntoIter = <InnerVec<'alloc, T> as IntoIterator>::IntoIter;
254    type Item = T;
255
256    #[inline(always)]
257    fn into_iter(self) -> Self::IntoIter {
258        self.0.into_iter()
259    }
260}
261
262impl<'i, T> IntoIterator for &'i Vec<'_, T> {
263    type IntoIter = std::slice::Iter<'i, T>;
264    type Item = &'i T;
265
266    #[inline(always)]
267    fn into_iter(self) -> Self::IntoIter {
268        self.0.iter()
269    }
270}
271
272impl<'i, T> IntoIterator for &'i mut Vec<'_, T> {
273    type IntoIter = std::slice::IterMut<'i, T>;
274    type Item = &'i mut T;
275
276    #[inline(always)]
277    fn into_iter(self) -> Self::IntoIter {
278        self.0.iter_mut()
279    }
280}
281
282impl<T, I> ops::Index<I> for Vec<'_, T>
283where
284    I: SliceIndex<[T]>,
285{
286    type Output = I::Output;
287
288    #[inline(always)]
289    fn index(&self, index: I) -> &Self::Output {
290        self.0.index(index)
291    }
292}
293
294impl<T, I> ops::IndexMut<I> for Vec<'_, T>
295where
296    I: SliceIndex<[T]>,
297{
298    #[inline(always)]
299    fn index_mut(&mut self, index: I) -> &mut Self::Output {
300        self.0.index_mut(index)
301    }
302}
303
304impl<'a, T: 'a> From<Vec<'a, T>> for Box<'a, [T]> {
305    #[inline(always)]
306    fn from(v: Vec<'a, T>) -> Box<'a, [T]> {
307        v.into_boxed_slice()
308    }
309}
310
311#[cfg(feature = "serialize")]
312impl<T: Serialize> Serialize for Vec<'_, T> {
313    fn serialize<S: SerdeSerializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
314        self.as_slice().serialize(serializer)
315    }
316}
317
318#[cfg(feature = "serialize")]
319impl<T: ESTree> ESTree for Vec<'_, T> {
320    fn serialize<S: ESTreeSerializer>(&self, serializer: S) {
321        self.as_slice().serialize(serializer);
322    }
323}
324
325#[cfg(feature = "serialize")]
326impl<T: ESTree> ConcatElement for Vec<'_, T> {
327    fn push_to_sequence<S: SequenceSerializer>(&self, seq: &mut S) {
328        for element in self {
329            seq.serialize_element(element);
330        }
331    }
332}
333
334impl<T: Hash> Hash for Vec<'_, T> {
335    #[inline(always)]
336    fn hash<H: Hasher>(&self, state: &mut H) {
337        self.0.hash(state);
338    }
339}
340
341impl<T: Debug> Debug for Vec<'_, T> {
342    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
343        f.debug_tuple("Vec").field(&self.0).finish()
344    }
345}
346
347#[cfg(test)]
348mod test {
349    use super::Vec;
350    use crate::Allocator;
351
352    #[test]
353    fn vec_with_capacity() {
354        let allocator = Allocator::default();
355        let v: Vec<i32> = Vec::with_capacity_in(10, &allocator);
356        assert!(v.is_empty());
357    }
358
359    #[test]
360    fn vec_debug() {
361        let allocator = Allocator::default();
362        let mut v = Vec::new_in(&allocator);
363        v.push("x");
364        let v = format!("{v:?}");
365        assert_eq!(v, "Vec([\"x\"])");
366    }
367
368    #[test]
369    fn vec_into_boxed_slice() {
370        let allocator = Allocator::default();
371        let mut v = Vec::with_capacity_in(4, &allocator);
372        v.push("x");
373        v.push("y");
374        let boxed_slice = v.into_boxed_slice();
375        assert_eq!(boxed_slice.as_ref(), &["x", "y"]);
376    }
377
378    #[cfg(feature = "serialize")]
379    #[test]
380    fn vec_serialize() {
381        let allocator = Allocator::default();
382        let mut v = Vec::new_in(&allocator);
383        v.push("x");
384        let s = serde_json::to_string(&v).unwrap();
385        assert_eq!(s, r#"["x"]"#);
386    }
387
388    #[cfg(feature = "serialize")]
389    #[test]
390    fn vec_serialize_estree() {
391        use oxc_estree::{CompactTSSerializer, ESTree};
392
393        let allocator = Allocator::default();
394        let mut v = Vec::new_in(&allocator);
395        v.push("x");
396
397        let mut serializer = CompactTSSerializer::default();
398        v.serialize(&mut serializer);
399        let s = serializer.into_string();
400        assert_eq!(s, r#"["x"]"#);
401    }
402
403    #[test]
404    fn lifetime_variance() {
405        fn _assert_vec_variant_lifetime<'a: 'b, 'b, T>(program: Vec<'a, T>) -> Vec<'b, T> {
406            program
407        }
408    }
409}
oxc_allocator/vec.rs

oxc_allocator/
vec.rs
