bones_schema/alloc/
vec.rs

1use std::{
2    any::{type_name, TypeId},
3    ffi::c_void,
4    fmt::Debug,
5    iter::Iterator,
6    marker::PhantomData,
7    mem::MaybeUninit,
8    sync::OnceLock,
9};
10
11use bones_utils::{default, HashMap};
12use fxhash::FxHasher;
13use parking_lot::RwLock;
14
15use crate::{prelude::*, raw_fns::*};
16
17use super::ResizableAlloc;
18
19/// A type-erased [`Vec`]-like collection that for items with the same [`Schema`].
20pub struct SchemaVec {
21    /// The allocation for stored items.
22    buffer: ResizableAlloc,
23    /// The number of items actually stored in the vec.
24    len: usize,
25    /// The schema of the items stored in the vec.
26    schema: &'static Schema,
27}
28
29impl std::fmt::Debug for SchemaVec {
30    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
31        f.debug_struct("SchemaVec")
32            .field("buffer", &"ResizableAlloc")
33            .field("len", &self.len)
34            .field("schema", &self.schema)
35            .finish()
36    }
37}
38
39// SOUND: the SchemaVec may only contain `HasSchema` types which are required to be `Sync + Send`.
40unsafe impl Sync for SchemaVec {}
41unsafe impl Send for SchemaVec {}
42
43impl SchemaVec {
44    /// Initialize an empty [`SchemaVec`] for items with the given schema.
45    pub fn new(schema: &'static Schema) -> Self {
46        Self {
47            buffer: ResizableAlloc::new(schema.layout()),
48            len: 0,
49            schema,
50        }
51    }
52
53    /// Grow the backing buffer to fit more elements.
54    fn grow(&mut self) {
55        let cap = self.buffer.capacity();
56        if cap == 0 {
57            self.buffer.resize(1).unwrap();
58        } else {
59            self.buffer.resize(cap * 2).unwrap();
60        }
61    }
62
63    /// Push an item unsafely to the vector.
64    /// # Safety
65    /// - The item must be a pointer to data with the same schema.
66    /// - You must ensure the `item` pointer is not used after pusing.
67    unsafe fn push_raw(&mut self, item: *mut c_void) {
68        // Make room for more elements if necessary
69        if self.len == self.buffer.capacity() {
70            self.grow();
71        }
72
73        // Copy the item into the vec
74        unsafe {
75            self.buffer
76                .unchecked_idx(self.len)
77                .copy_from_nonoverlapping(item, self.buffer.layout().size());
78        }
79
80        // Extend the length. This cannot overflow because we will run out of memory before we
81        // exhaust `usize`.
82        self.len += 1;
83    }
84
85    /// Push an item to the vec.
86    /// # Errors
87    /// Errors if the schema of `T` doesn't match the vec.
88    pub fn try_push<T: HasSchema>(&mut self, mut item: T) -> Result<(), SchemaMismatchError> {
89        // Ensure matching schema
90        if self.schema != T::schema() {
91            return Err(SchemaMismatchError);
92        }
93
94        unsafe {
95            self.push_raw(&mut item as *mut T as *mut c_void);
96            std::mem::forget(item);
97        }
98
99        Ok(())
100    }
101
102    /// Push an item to the vec.
103    /// # Panics
104    /// Panics if the schema of `T` doesn't match the vec.
105    #[inline]
106    #[track_caller]
107    pub fn push<T: HasSchema>(&mut self, item: T) {
108        self.try_push(item).unwrap()
109    }
110
111    /// Push the item into the end of the vector.
112    pub fn try_push_box(&mut self, mut item: SchemaBox) -> Result<(), SchemaMismatchError> {
113        // Ensure matching schema
114        if self.schema != item.schema() {
115            return Err(SchemaMismatchError);
116        }
117
118        // We validated matching schemas.
119        unsafe {
120            self.push_raw(item.as_mut().as_ptr());
121        }
122
123        // Don't run the item's destructor, it's the responsibility of the vec
124        item.forget();
125
126        Ok(())
127    }
128
129    /// Push the item into the end of the vector.
130    #[track_caller]
131    #[inline]
132    pub fn push_box(&mut self, item: SchemaBox) {
133        self.try_push_box(item).unwrap()
134    }
135
136    /// Pop the last item off of the end of the vector.
137    pub fn pop_box(&mut self) -> Option<SchemaBox> {
138        if self.len == 0 {
139            None
140        } else {
141            unsafe { self.raw_pop() }.map(|ptr| unsafe {
142                let mut b = SchemaBox::uninitialized(self.schema);
143                b.as_mut()
144                    .as_ptr()
145                    .copy_from_nonoverlapping(ptr, self.buffer.layout().size());
146                b
147            })
148        }
149    }
150
151    /// Pop an item off the vec.
152    /// # Errors
153    /// Errors if the schema of `T` doesn't match.
154    pub fn try_pop<T: HasSchema>(&mut self) -> Result<Option<T>, SchemaMismatchError> {
155        if self.schema != T::schema() {
156            Err(SchemaMismatchError)
157        } else {
158            let ret = unsafe { self.raw_pop() }.map(|ptr| {
159                let mut data = MaybeUninit::<T>::uninit();
160                unsafe {
161                    (data.as_mut_ptr() as *mut c_void)
162                        .copy_from_nonoverlapping(ptr, self.buffer.layout().size());
163                    data.assume_init()
164                }
165            });
166            Ok(ret)
167        }
168    }
169
170    /// # Safety
171    /// The pointer may only be used immediately after calling raw_pop to read the data out of the
172    /// popped item. Any further mutations to the vector may make the pointer invalid.
173    unsafe fn raw_pop(&mut self) -> Option<*mut c_void> {
174        if self.len == 0 {
175            None
176        } else {
177            // Decrement our length
178            self.len -= 1;
179
180            // Return the pointer to the item that is being popped off.
181            Some(unsafe { self.buffer.unchecked_idx(self.len) })
182        }
183    }
184
185    /// Pop an item off the vec.
186    /// # Panics
187    /// Panics if the schema of `T` doesn't match.
188    #[inline]
189    #[track_caller]
190    pub fn pop<T: HasSchema>(&mut self) -> Option<T> {
191        self.try_pop().unwrap()
192    }
193
194    /// Get an item in the vec.
195    /// # Errors
196    /// Errors if the schema doesn't match.
197    pub fn try_get<T: HasSchema>(&self, idx: usize) -> Result<Option<&T>, SchemaMismatchError> {
198        self.get_ref(idx).map(|x| x.try_cast()).transpose()
199    }
200
201    /// Get an item in the vec.
202    /// # Panics
203    /// Panics if the schema doesn't match.
204    #[inline]
205    #[track_caller]
206    pub fn get<T: HasSchema>(&self, idx: usize) -> Option<&T> {
207        self.try_get(idx).unwrap()
208    }
209
210    /// Get the item with the given index.
211    pub fn get_ref(&self, idx: usize) -> Option<SchemaRef<'_>> {
212        if idx >= self.len {
213            None
214        } else {
215            let ptr = unsafe { self.buffer.unchecked_idx(idx) };
216            unsafe { Some(SchemaRef::from_ptr_schema(ptr, self.schema)) }
217        }
218    }
219
220    /// Get an item in the vec.
221    /// # Errors
222    /// Errors if the schema doesn't match.
223    pub fn try_get_mut<T: HasSchema>(
224        &mut self,
225        idx: usize,
226    ) -> Result<Option<&mut T>, SchemaMismatchError> {
227        self.get_ref_mut(idx)
228            // SOUND: We are extending the lifetime of the cast to the lifetime of our borrow of
229            // `&mut self`, which is valid.
230            .map(|mut x| unsafe { x.try_cast_mut().map(|x| transmute_lifetime(x)) })
231            .transpose()
232    }
233
234    /// Get an item in the vec.
235    /// # Panics
236    /// Panics if the schema doesn't match.
237    #[inline]
238    #[track_caller]
239    pub fn get_mut<T: HasSchema>(&mut self, idx: usize) -> Option<&mut T> {
240        self.try_get_mut(idx).unwrap()
241    }
242
243    /// Get an item with the given index.
244    pub fn get_ref_mut(&mut self, idx: usize) -> Option<SchemaRefMut<'_>> {
245        if idx >= self.len {
246            None
247        } else {
248            let ptr = unsafe { self.buffer.unchecked_idx(idx) };
249            unsafe { Some(SchemaRefMut::from_ptr_schema(ptr, self.schema)) }
250        }
251    }
252
253    /// Get the number of items in the vector.
254    #[inline]
255    pub fn len(&self) -> usize {
256        self.len
257    }
258
259    /// Returns `true` if the vector has zero items in it.
260    #[inline]
261    pub fn is_empty(&self) -> bool {
262        self.len() == 0
263    }
264
265    /// Get the capacity of the backing buffer.
266    #[inline]
267    pub fn capacity(&self) -> usize {
268        self.buffer.capacity()
269    }
270
271    /// Get the schema of items in this [`SchemaVec`].
272    #[inline]
273    pub fn schema(&self) -> &'static Schema {
274        self.schema
275    }
276
277    /// Iterate over values in the vec
278    pub fn iter(&self) -> SchemaVecIter<'_> {
279        SchemaVecIter { vec: self, idx: 0 }
280    }
281
282    /// Iterate mutably over values in the vec
283    pub fn iter_mut(&mut self) -> SchemaVecIterMut<'_> {
284        SchemaVecIterMut { vec: self, idx: 0 }
285    }
286
287    /// Convert into a typed [`SVec`].
288    /// # Panics
289    /// Panics if the schema of `T` doesn't match this [`SchemaVec`]'s schema.
290    #[track_caller]
291    pub fn into_svec<T: HasSchema>(self) -> SVec<T> {
292        self.try_into_svec().unwrap()
293    }
294
295    /// Try to convert into a typed [`SVec`].
296    /// # Errors
297    /// Errors if the schema of `T` doesn't match this [`SchemaVec`]'s schema.
298    pub fn try_into_svec<T: HasSchema>(self) -> Result<SVec<T>, SchemaMismatchError> {
299        if T::schema() == self.schema {
300            Ok(SVec {
301                vec: self,
302                _phantom: PhantomData,
303            })
304        } else {
305            Err(SchemaMismatchError)
306        }
307    }
308
309    /// Get the hash of this [`SchemaVec`].
310    /// # Panics
311    /// Panics if the inner type doesn't implement hash.
312    #[track_caller]
313    pub fn hash(&self) -> u64 {
314        use std::hash::{Hash, Hasher};
315        let Some(hash_fn) = &self.schema.hash_fn else {
316            panic!("Schema doesn't specify a hash_fn");
317        };
318        let mut hasher = FxHasher::default();
319        for item_ptr in self.buffer.iter() {
320            let item_hash = unsafe { (hash_fn.get())(item_ptr) };
321            item_hash.hash(&mut hasher);
322        }
323        hasher.finish()
324    }
325
326    /// Raw version of the [`hash()`][Self::hash] function. Not meant for normal use.
327    /// # Safety
328    /// Pointer must be a valid pointer to a [`SchemaVec`].
329    pub unsafe fn raw_hash(ptr: *const c_void) -> u64 {
330        let this = unsafe { &*(ptr as *const Self) };
331        this.hash()
332    }
333
334    /// Raw version of the [`eq()`][PartialEq::eq] function. Not meant for normal use.
335    /// # Safety
336    /// Pointers must be valid pointers to [`SchemaVec`]s.
337    pub unsafe fn raw_eq(a: *const c_void, b: *const c_void) -> bool {
338        let a = &*(a as *const Self);
339        let b = &*(b as *const Self);
340        a.eq(b)
341    }
342
343    /// Remove and return the element at position `index` within the vector,
344    /// shifting all elements after it to the left.
345    /// # Panics
346    /// Panics if `index` is out of bounds.
347    pub fn remove(&mut self, index: usize) -> SchemaBox {
348        if index >= self.len {
349            panic!("index out of bounds");
350        }
351        let item = unsafe {
352            let ptr = self.buffer.unchecked_idx(index);
353            let mut boxed = SchemaBox::uninitialized(self.schema);
354            boxed
355                .as_mut()
356                .as_ptr()
357                .copy_from_nonoverlapping(ptr, self.schema.layout().size());
358
359            // Shift elements
360            let to_move = self.len - index - 1;
361            if to_move > 0 {
362                std::ptr::copy(
363                    self.buffer.unchecked_idx(index + 1),
364                    self.buffer.unchecked_idx(index),
365                    to_move * self.schema.layout().size(),
366                );
367            }
368
369            self.len -= 1;
370            boxed
371        };
372        item
373    }
374
375    /// Clears the vector, removing all values.
376    pub fn clear(&mut self) {
377        while self.pop_box().is_some() {}
378    }
379
380    /// Shortens the vector, keeping the first `len` elements and dropping the rest.
381    ///
382    /// If `len` is greater than the vector's current length, this has no effect.
383    pub fn truncate(&mut self, len: usize) {
384        while self.len > len {
385            self.pop_box();
386        }
387    }
388}
389
390impl<T: HasSchema> FromIterator<T> for SVec<T> {
391    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
392        let mut this = Self::default();
393        for item in iter {
394            this.push(item);
395        }
396        this
397    }
398}
399
400impl<'a> IntoIterator for &'a SchemaVec {
401    type Item = SchemaRef<'a>;
402    type IntoIter = SchemaVecIter<'a>;
403    fn into_iter(self) -> Self::IntoIter {
404        self.iter()
405    }
406}
407impl<'a> IntoIterator for &'a mut SchemaVec {
408    type Item = SchemaRefMut<'a>;
409    type IntoIter = SchemaVecIterMut<'a>;
410    fn into_iter(self) -> Self::IntoIter {
411        self.iter_mut()
412    }
413}
414
415/// Iterator over [`SchemaVec`].
416pub struct SchemaVecIter<'a> {
417    vec: &'a SchemaVec,
418    idx: usize,
419}
420
421impl<'a> Iterator for SchemaVecIter<'a> {
422    type Item = SchemaRef<'a>;
423    fn next(&mut self) -> Option<Self::Item> {
424        let item = self.vec.get_ref(self.idx);
425        if item.is_some() {
426            self.idx += 1;
427        }
428        item
429    }
430}
431
432/// Mutable iterator over [`SchemaVec`].
433pub struct SchemaVecIterMut<'a> {
434    vec: &'a mut SchemaVec,
435    idx: usize,
436}
437impl<'a> Iterator for SchemaVecIterMut<'a> {
438    type Item = SchemaRefMut<'a>;
439
440    fn next(&mut self) -> Option<Self::Item> {
441        let item = self
442            .vec
443            .get_ref_mut(self.idx)
444            // SOUND: We are returning data with the lifetime of the SchemaVec, which is accurate
445            // and sound as long as we don't return two mutable references to the same item.
446            .map(|x| unsafe { SchemaRefMut::from_ptr_schema(x.as_ptr(), x.schema()) });
447        if item.is_some() {
448            self.idx += 1;
449        }
450        item
451    }
452}
453
454impl Eq for SchemaVec {}
455impl PartialEq for SchemaVec {
456    #[track_caller]
457    fn eq(&self, other: &Self) -> bool {
458        if self.schema != other.schema {
459            panic!("Cannot compare two `SchemaVec`s with different schemas.");
460        }
461        let Some(eq_fn) = &self.schema.eq_fn else {
462            panic!("Schema doesn't have an eq_fn");
463        };
464
465        for i in 0..self.len {
466            unsafe {
467                let a = self.buffer.unchecked_idx(i);
468                let b = self.buffer.unchecked_idx(i);
469                if !(eq_fn.get())(a, b) {
470                    return false;
471                }
472            }
473        }
474        true
475    }
476}
477
478impl Clone for SchemaVec {
479    fn clone(&self) -> Self {
480        let Some(clone_fn) = &self.schema.clone_fn else {
481            panic!("This type cannot be cloned");
482        };
483        let mut buffer_clone = ResizableAlloc::new(self.schema.layout());
484        buffer_clone.resize(self.len).unwrap();
485
486        // Clone each item in the vec
487        for i in 0..self.len {
488            // SOUND: we've check that the index is within bounds, and the schema asserts the
489            // validity of the clone function.
490            unsafe {
491                let item = self.buffer.unchecked_idx(i);
492                (clone_fn.get())(item, buffer_clone.unchecked_idx(i));
493            }
494        }
495
496        SchemaVec {
497            buffer: buffer_clone,
498            len: self.len,
499            schema: self.schema,
500        }
501    }
502}
503
504impl Drop for SchemaVec {
505    fn drop(&mut self) {
506        for _ in 0..self.len {
507            drop(self.pop_box().unwrap());
508        }
509    }
510}
511
512/// A typed version of a [`SchemaVec`].
513///
514/// This type exists as an alternative to [`Vec`] that properly implements [`HasSchema`].
515///
516/// Additionally, accessing an [`SVec`] is more efficient than using a [`SchemaVec`] because it
517/// avoids runtime schema checks after construction.
518#[repr(transparent)]
519#[derive(Eq, PartialEq)]
520pub struct SVec<T: HasSchema> {
521    vec: SchemaVec,
522    _phantom: PhantomData<T>,
523}
524
525impl<T: HasSchema> SVec<T> {
526    /// Create a new, empty [`SVec`].
527    pub fn new() -> Self {
528        Self {
529            vec: SchemaVec::new(T::schema()),
530            _phantom: PhantomData,
531        }
532    }
533
534    /// Push an item onto the vector.
535    pub fn push(&mut self, mut item: T) {
536        // SOUND: We know that the schema matches, and we forget the item after pushing.
537        unsafe {
538            self.vec.push_raw(&mut item as *mut T as *mut c_void);
539        }
540        std::mem::forget(item);
541    }
542
543    /// Pop an item off of the vector.
544    pub fn pop(&mut self) -> Option<T> {
545        unsafe {
546            self.vec.raw_pop().map(|ptr| {
547                let mut ret = MaybeUninit::<T>::uninit();
548                ret.as_mut_ptr().copy_from_nonoverlapping(ptr as *mut T, 1);
549                ret.assume_init()
550            })
551        }
552    }
553
554    /// Get an item from the vec.
555    pub fn get(&self, idx: usize) -> Option<&T> {
556        // SOUND: We know that the pointer is to a type T
557        self.vec
558            .get_ref(idx)
559            .map(|x| unsafe { x.cast_into_unchecked() })
560    }
561
562    /// Get an item from the vec.
563    pub fn get_mut(&mut self, idx: usize) -> Option<&mut T> {
564        // SOUND: We know that the pointer is to a type T
565        self.vec
566            .get_ref_mut(idx)
567            .map(|x| unsafe { x.cast_into_mut_unchecked() })
568    }
569
570    /// Iterate over references to the items in the vec.
571    pub fn iter(&self) -> SVecIter<'_, T> {
572        SVecIter {
573            vec: self,
574            idx: 0,
575            end: self.len() as isize - 1,
576        }
577    }
578
579    /// Iterate over mutable references to the items in the vec.
580    pub fn iter_mut(&mut self) -> SVecIterMut<'_, T> {
581        SVecIterMut {
582            idx: 0,
583            end: self.len() as isize - 1,
584            vec: self,
585        }
586    }
587
588    /// Get the length of the vector.
589    #[inline]
590    pub fn len(&self) -> usize {
591        self.vec.len()
592    }
593
594    /// Returns `true` if there are no items in the vector.
595    #[inline]
596    pub fn is_empty(&self) -> bool {
597        self.vec.is_empty()
598    }
599
600    /// Get the capacity of the vec.
601    #[inline]
602    pub fn capacity(&self) -> usize {
603        self.vec.capacity()
604    }
605
606    /// Convert to an untyped [`SchemaVec`].
607    #[inline]
608    pub fn into_schema_vec(self) -> SchemaVec {
609        self.vec
610    }
611
612    /// Get the hash of the [`SVec`].
613    pub fn hash(&self) -> u64 {
614        self.vec.hash()
615    }
616
617    /// Remove and return the element at position `index` within the vector,
618    /// shifting all elements after it to the left.
619    /// # Panics
620    /// Panics if `index` is out of bounds.
621    pub fn remove(&mut self, index: usize) -> T {
622        let boxed = self.vec.remove(index);
623        // SAFETY: We know that the SchemaBox contains a value of type T
624        unsafe { boxed.cast_into_unchecked() }
625    }
626
627    /// Clears the vector, removing all values.
628    pub fn clear(&mut self) {
629        self.vec.clear();
630    }
631
632    /// Shortens the vector, keeping the first `len` elements and dropping the rest.
633    ///
634    /// If `len` is greater than the vector's current length, this has no effect.
635    pub fn truncate(&mut self, len: usize) {
636        self.vec.truncate(len);
637    }
638
639    /// Extends the vector with the contents of an iterator.
640    pub fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
641        for item in iter {
642            self.push(item);
643        }
644    }
645
646    /// Retains only the elements specified by the predicate.
647    pub fn retain<F>(&mut self, mut f: F)
648    where
649        F: FnMut(&T) -> bool,
650    {
651        let mut i = 0;
652        while i < self.len() {
653            if !f(&self[i]) {
654                self.remove(i);
655            } else {
656                i += 1;
657            }
658        }
659    }
660
661    /// Retains only the elements specified by the predicate, passing a mutable reference to it.
662    pub fn retain_mut<F>(&mut self, mut f: F)
663    where
664        F: FnMut(&mut T) -> bool,
665    {
666        let mut i = 0;
667        while i < self.len() {
668            if !f(self.get_mut(i).unwrap()) {
669                self.remove(i);
670            } else {
671                i += 1;
672            }
673        }
674    }
675
676    /// Removes and returns the last element of the vector if the predicate returns true.
677    pub fn pop_if<F>(&mut self, f: F) -> Option<T>
678    where
679        F: FnOnce(&T) -> bool,
680    {
681        if let Some(last) = self.last() {
682            if f(last) {
683                self.pop()
684            } else {
685                None
686            }
687        } else {
688            None
689        }
690    }
691
692    /// Returns a reference to the first element of the vector, or None if it is empty.
693    pub fn first(&self) -> Option<&T> {
694        self.get(0)
695    }
696
697    /// Returns a mutable reference to the first element of the vector, or None if it is empty.
698    pub fn first_mut(&mut self) -> Option<&mut T> {
699        self.get_mut(0)
700    }
701
702    /// Returns a reference to the last element of the vector, or None if it is empty.
703    pub fn last(&self) -> Option<&T> {
704        self.get(self.len().wrapping_sub(1))
705    }
706
707    /// Returns a mutable reference to the last element of the vector, or None if it is empty.
708    pub fn last_mut(&mut self) -> Option<&mut T> {
709        let len = self.len();
710        self.get_mut(len.wrapping_sub(1))
711    }
712
713    /// Reverses the order of elements in the vector, in place.
714    pub fn reverse(&mut self) {
715        let mut i = 0;
716        let mut j = self.len().saturating_sub(1);
717        while i < j {
718            // SAFETY: We know that i and j are within bounds and not equal.
719            unsafe {
720                let ptr_i = self.get_mut(i).unwrap() as *mut T;
721                let ptr_j = self.get_mut(j).unwrap() as *mut T;
722                std::ptr::swap(ptr_i, ptr_j);
723            }
724            i += 1;
725            j -= 1;
726        }
727    }
728}
729
730/// Iterator over [`SVec`].
731pub struct SVecIntoIter<T: HasSchema> {
732    svec: SVec<T>,
733    index: usize,
734}
735
736impl<T: HasSchema + Debug> std::fmt::Debug for SVec<T> {
737    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
738        let mut l = f.debug_list();
739        for item in self.iter() {
740            l.entry(item);
741        }
742        l.finish()
743    }
744}
745
746impl<T: HasSchema> From<SVec<T>> for Vec<T> {
747    fn from(svec: SVec<T>) -> Self {
748        let mut vec = Vec::with_capacity(svec.len());
749        for item in svec {
750            vec.push(item);
751        }
752        vec
753    }
754}
755
756impl<T: HasSchema> From<Vec<T>> for SVec<T> {
757    fn from(vec: Vec<T>) -> Self {
758        let mut svec = SVec::new();
759        for item in vec {
760            svec.push(item);
761        }
762        svec
763    }
764}
765
766// Implement IntoIterator for SVec<T>
767impl<T: HasSchema> IntoIterator for SVec<T> {
768    type Item = T;
769    type IntoIter = SVecIntoIter<T>;
770
771    fn into_iter(self) -> Self::IntoIter {
772        SVecIntoIter {
773            svec: self,
774            index: 0,
775        }
776    }
777}
778
779impl<T: HasSchema> Iterator for SVecIntoIter<T> {
780    type Item = T;
781
782    fn next(&mut self) -> Option<Self::Item> {
783        if self.index < self.svec.len() {
784            let item = self.svec.remove(self.index);
785            Some(item)
786        } else {
787            None
788        }
789    }
790
791    fn size_hint(&self) -> (usize, Option<usize>) {
792        let remaining = self.svec.len() - self.index;
793        (remaining, Some(remaining))
794    }
795}
796
797impl<T: HasSchema> Drop for SVecIntoIter<T> {
798    fn drop(&mut self) {
799        // Ensure all remaining elements are properly dropped
800        for _ in self.by_ref() {}
801    }
802}
803
804impl<T: HasSchema, const N: usize> From<[T; N]> for SVec<T> {
805    fn from(arr: [T; N]) -> Self {
806        arr.into_iter().collect()
807    }
808}
809
810impl<T: HasSchema> std::ops::Index<usize> for SVec<T> {
811    type Output = T;
812
813    #[track_caller]
814    fn index(&self, idx: usize) -> &Self::Output {
815        self.get(idx).unwrap()
816    }
817}
818
819impl<T: HasSchema> std::ops::IndexMut<usize> for SVec<T> {
820    #[track_caller]
821    fn index_mut(&mut self, idx: usize) -> &mut Self::Output {
822        self.get_mut(idx).unwrap()
823    }
824}
825
826impl<T: HasSchema> std::ops::Deref for SVec<T> {
827    type Target = [T];
828
829    fn deref(&self) -> &Self::Target {
830        // SOUND: we know that the schema matches T, and the internal buffer of a SchemaVec stores
831        // the types contiguously in memory.
832        unsafe { std::slice::from_raw_parts(self.vec.buffer.as_ptr() as *const T, self.len()) }
833    }
834}
835impl<T: HasSchema> std::ops::DerefMut for SVec<T> {
836    fn deref_mut(&mut self) -> &mut Self::Target {
837        // SOUND: we know that the schema matches T, and the internal buffer of a SchemaVec stores
838        // the types contiguously in memory.
839        unsafe { std::slice::from_raw_parts_mut(self.vec.buffer.as_ptr() as *mut T, self.len()) }
840    }
841}
842
843unsafe impl<T: HasSchema> HasSchema for SVec<T> {
844    fn schema() -> &'static Schema {
845        static S: OnceLock<RwLock<HashMap<TypeId, &'static Schema>>> = OnceLock::new();
846        let schema = {
847            S.get_or_init(default)
848                .read()
849                .get(&TypeId::of::<Self>())
850                .copied()
851        };
852        schema.unwrap_or_else(|| {
853            let schema = SCHEMA_REGISTRY.register(SchemaData {
854                name: type_name::<Self>().into(),
855                full_name: format!("{}::{}", module_path!(), type_name::<Self>()).into(),
856                kind: SchemaKind::Vec(T::schema()),
857                type_id: Some(TypeId::of::<Self>()),
858                clone_fn: Some(<Self as RawClone>::raw_clone_cb()),
859                drop_fn: Some(<Self as RawDrop>::raw_drop_cb()),
860                default_fn: Some(<Self as RawDefault>::raw_default_cb()),
861                hash_fn: Some(unsafe {
862                    Unsafe::new(Box::leak(Box::new(|a| SchemaVec::raw_hash(a))))
863                }),
864                eq_fn: Some(unsafe {
865                    Unsafe::new(Box::leak(Box::new(|a, b| SchemaVec::raw_eq(a, b))))
866                }),
867                type_data: Default::default(),
868            });
869
870            S.get_or_init(default)
871                .write()
872                .insert(TypeId::of::<Self>(), schema);
873
874            schema
875        })
876    }
877}
878
879impl<T: HasSchema> Default for SVec<T> {
880    fn default() -> Self {
881        Self {
882            vec: SchemaVec::new(T::schema()),
883            _phantom: Default::default(),
884        }
885    }
886}
887impl<T: HasSchema> Clone for SVec<T> {
888    fn clone(&self) -> Self {
889        Self {
890            vec: self.vec.clone(),
891            _phantom: self._phantom,
892        }
893    }
894}
895
896impl<'a, T: HasSchema> IntoIterator for &'a SVec<T> {
897    type Item = &'a T;
898    type IntoIter = SVecIter<'a, T>;
899    fn into_iter(self) -> Self::IntoIter {
900        self.iter()
901    }
902}
903impl<'a, T: HasSchema> IntoIterator for &'a mut SVec<T> {
904    type Item = &'a mut T;
905    type IntoIter = SVecIterMut<'a, T>;
906    fn into_iter(self) -> Self::IntoIter {
907        self.iter_mut()
908    }
909}
910
911/// Iterator over items in an [`SVec`].
912pub struct SVecIter<'a, T: HasSchema> {
913    vec: &'a SVec<T>,
914    idx: usize,
915    end: isize,
916}
917impl<'a, T: HasSchema> Iterator for SVecIter<'a, T> {
918    type Item = &'a T;
919
920    fn next(&mut self) -> Option<Self::Item> {
921        if self.end < 0 {
922            return None;
923        }
924        let item = (self.idx <= self.end as usize).then(|| self.vec.get(self.idx).unwrap());
925        if item.is_some() {
926            self.idx += 1;
927        }
928        item
929    }
930}
931impl<'a, T: HasSchema> DoubleEndedIterator for SVecIter<'a, T> {
932    fn next_back(&mut self) -> Option<Self::Item> {
933        if self.end < 0 {
934            return None;
935        }
936        let item =
937            (self.end as usize >= self.idx).then(|| self.vec.get(self.end as usize).unwrap());
938        if item.is_some() {
939            self.end -= 1;
940        }
941        item
942    }
943}
944
945/// Iterator over items in an [`SVec`].
946pub struct SVecIterMut<'a, T: HasSchema> {
947    vec: &'a mut SVec<T>,
948    idx: usize,
949    end: isize,
950}
951impl<'a, T: HasSchema> Iterator for SVecIterMut<'a, T> {
952    type Item = &'a mut T;
953
954    fn next(&mut self) -> Option<Self::Item> {
955        if self.end < 0 {
956            return None;
957        }
958        let item = (self.idx <= self.end as usize).then(|| self.vec.get_mut(self.idx).unwrap());
959        if item.is_some() {
960            self.idx += 1;
961        }
962        // SOUND: we are returning data with the lifetime of the vec which is valid and sound,
963        // assuming we don't return two mutable references to the same item.
964        item.map(|x| unsafe { transmute_lifetime(x) })
965    }
966}
967impl<'a, T: HasSchema> DoubleEndedIterator for SVecIterMut<'a, T> {
968    fn next_back(&mut self) -> Option<Self::Item> {
969        if self.end < 0 {
970            return None;
971        }
972        let item =
973            (self.end as usize >= self.idx).then(|| self.vec.get_mut(self.end as usize).unwrap());
974        if item.is_some() {
975            self.end -= 1;
976        }
977        // SOUND: we are returning data with the lifetime of the vec which is valid and sound,
978        // assuming we don't return two mutable references to the same item.
979        item.map(|x| unsafe { transmute_lifetime(x) })
980    }
981}
982
983/// Helper to transmute a lifetime unsafely.
984///
985/// This is safer than just calling [`transmute`][std::mem::transmute] because it can only transmut
986/// the lifetime, not the type of the reference.
987unsafe fn transmute_lifetime<'b, T>(v: &mut T) -> &'b mut T {
988    std::mem::transmute(v)
989}
990
991#[cfg(test)]
992mod test {
993    use super::*;
994
995    #[test]
996    fn double_ended() {
997        let mut v = [1, 2, 3, 4, 5, 6].into_iter().collect::<SVec<_>>();
998
999        let mut iter = v.iter();
1000        assert_eq!(iter.next_back(), Some(&6));
1001        assert_eq!(iter.next_back(), Some(&5));
1002        assert_eq!(iter.next(), Some(&1));
1003        assert_eq!(iter.next(), Some(&2));
1004        assert_eq!(iter.next_back(), Some(&4));
1005        assert_eq!(iter.next(), Some(&3));
1006        assert_eq!(iter.next_back(), None);
1007        assert_eq!(iter.next(), None);
1008
1009        let mut iter = v.iter_mut();
1010        assert_eq!(iter.next_back(), Some(&mut 6));
1011        assert_eq!(iter.next_back(), Some(&mut 5));
1012        assert_eq!(iter.next(), Some(&mut 1));
1013        assert_eq!(iter.next(), Some(&mut 2));
1014        assert_eq!(iter.next_back(), Some(&mut 4));
1015        assert_eq!(iter.next(), Some(&mut 3));
1016        assert_eq!(iter.next_back(), None);
1017        assert_eq!(iter.next(), None);
1018
1019        let v = [].into_iter().collect::<SVec<u8>>();
1020        let mut iter = v.iter();
1021        assert_eq!(iter.next(), None);
1022        assert_eq!(iter.next(), None);
1023        assert_eq!(iter.next_back(), None);
1024        let mut iter = v.iter();
1025        assert_eq!(iter.next_back(), None);
1026        assert_eq!(iter.next(), None);
1027    }
1028
1029    #[test]
1030    fn test_vec_and_svec_conversions() {
1031        // Test Vec to SVec conversion
1032        let vec = vec![1, 2, 3, 4, 5];
1033        let svec: SVec<i32> = vec.clone().into();
1034        assert_eq!(svec.len(), 5);
1035        // Test SVec to Vec conversion
1036        let vec_from_svec: Vec<i32> = svec.into();
1037        assert_eq!(vec, vec_from_svec);
1038        // Test direct array conversion to SVec
1039        let svec_direct: SVec<i32> = [11, 12, 13].into();
1040        assert_eq!(svec_direct.len(), 3);
1041        // Test SVec to Vec conversion for array-created SVec
1042        let vec_from_array_svec: Vec<i32> = svec_direct.into();
1043        assert_eq!(vec_from_array_svec, vec![11, 12, 13]);
1044    }
1045
1046    #[test]
1047    fn test_remove() {
1048        let mut svec: SVec<i32> = vec![10, 20, 30, 40, 50].into();
1049
1050        // Remove from the middle
1051        let removed = svec.remove(2);
1052        assert_eq!(removed, 30);
1053        assert_eq!(svec.len(), 4);
1054        assert_eq!(svec[0], 10);
1055
1056        // Remove from the beginning
1057        let removed = svec.remove(0);
1058        assert_eq!(removed, 10);
1059        assert_eq!(svec.len(), 3);
1060        assert_eq!(svec[0], 20);
1061
1062        // Remove from the end
1063        let removed = svec.remove(2);
1064        assert_eq!(removed, 50);
1065        assert_eq!(svec.len(), 2);
1066        assert_eq!(svec[1], 40);
1067
1068        // Test removing the last element
1069        let removed = svec.remove(1);
1070        assert_eq!(removed, 40);
1071        assert_eq!(svec.len(), 1);
1072        assert_eq!(svec[0], 20);
1073
1074        // Test removing the very last element
1075        let removed = svec.remove(0);
1076        assert_eq!(removed, 20);
1077        assert_eq!(svec.len(), 0);
1078    }
1079
1080    #[test]
1081    fn test_svec_operations() {
1082        let mut vec: SVec<i32> = SVec::new();
1083
1084        // Test push and len
1085        vec.push(1);
1086        vec.push(2);
1087        vec.push(3);
1088        assert_eq!(vec.len(), 3);
1089
1090        // Test get
1091        assert_eq!(vec.get(1), Some(&2));
1092        assert_eq!(vec.get(3), None);
1093
1094        // Test remove
1095        let removed = vec.remove(2);
1096        assert_eq!(removed, 3);
1097        assert_eq!(vec.len(), 2);
1098
1099        // Test iteration
1100        let sum: i32 = vec.iter().copied().sum();
1101        assert_eq!(sum, 3); // 1 + 2
1102
1103        // Test extend
1104        vec.extend(vec![5, 6]);
1105        assert_eq!(vec.len(), 4);
1106        assert_eq!(vec.get(2), Some(&5));
1107        assert_eq!(vec.get(3), Some(&6));
1108
1109        // Test retain
1110        vec.retain(|&x| x % 2 == 0);
1111        assert_eq!(vec.len(), 2);
1112        assert_eq!(vec[0], 2);
1113        assert_eq!(vec[1], 6);
1114
1115        // Test retain_mut
1116        vec.retain_mut(|x| {
1117            *x *= 2;
1118            true
1119        });
1120        assert_eq!(vec.len(), 2);
1121        assert_eq!(vec[0], 4);
1122        assert_eq!(vec[1], 12);
1123
1124        // Test truncate
1125        vec.truncate(1);
1126        assert_eq!(vec.len(), 1);
1127        assert_eq!(vec[0], 4);
1128        assert_eq!(vec.get(1), None);
1129
1130        // Prepare for further tests
1131        vec.extend(vec![7, 9, 11]);
1132
1133        // Test first() and first_mut()
1134        assert_eq!(vec.first(), Some(&4));
1135        if let Some(first) = vec.first_mut() {
1136            *first = 1;
1137        }
1138        assert_eq!(vec[0], 1);
1139
1140        // Test last() and last_mut()
1141        assert_eq!(vec.last(), Some(&11));
1142        if let Some(last) = vec.last_mut() {
1143            *last = 15;
1144        }
1145        assert_eq!(vec[3], 15);
1146
1147        // Test pop_if()
1148        assert_eq!(vec.pop_if(|&x| x > 10), Some(15));
1149        assert_eq!(vec.len(), 3);
1150        assert_eq!(vec.pop_if(|&x| x < 0), None);
1151        assert_eq!(vec.len(), 3);
1152
1153        // Test clear
1154        vec.clear();
1155        assert_eq!(vec.len(), 0);
1156        assert!(vec.is_empty());
1157
1158        // Test pop on empty vector
1159        assert_eq!(vec.pop(), None);
1160
1161        // Test Vec and SVec conversions
1162        let original_vec = vec![1, 2, 3, 4, 5];
1163        let svec: SVec<i32> = original_vec.clone().into();
1164        let vec_from_svec: Vec<i32> = svec.into();
1165        assert_eq!(original_vec, vec_from_svec);
1166
1167        // Test reverse
1168        let mut reversed_vec = original_vec.clone();
1169        reversed_vec.reverse();
1170        assert_eq!(reversed_vec, vec![5, 4, 3, 2, 1]);
1171    }
1172
1173    #[test]
1174    fn miri_error_001() {
1175        let mut vec: SVec<i32> = SVec::new();
1176        vec.push(10);
1177        vec.pop();
1178    }
1179}
bones_schema/alloc/vec.rs

bones_schema/alloc/
vec.rs
