Skip to main content

zerovec/varzerovec/
owned.rs

1// This file is part of ICU4X. For terms of use, please see the file
2// called LICENSE at the top level of the ICU4X source tree
3// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).
4
5// The mutation operations in this file should panic to prevent undefined behavior
6#![allow(clippy::unwrap_used)]
7#![allow(clippy::expect_used)]
8#![allow(clippy::indexing_slicing)]
9#![allow(clippy::panic)]
10
11use super::*;
12use crate::ule::*;
13use alloc::vec::Vec;
14use core::any;
15use core::convert::TryInto;
16use core::marker::PhantomData;
17use core::ops::Deref;
18use core::ops::Range;
19use core::{fmt, ptr, slice};
20
21use super::components::IntegerULE;
22
23/// A fully-owned [`VarZeroVec`]. This type has no lifetime but has the same
24/// internal buffer representation of [`VarZeroVec`], making it cheaply convertible to
25/// [`VarZeroVec`] and [`VarZeroSlice`].
26///
27/// The `F` type parameter is a [`VarZeroVecFormat`] (see its docs for more details), which can be used to select the
28/// precise format of the backing buffer with various size and performance tradeoffs. It defaults to [`Index16`].
29///
30/// ✨ *Enabled with the `alloc` Cargo feature.*
31pub struct VarZeroVecOwned<T: ?Sized, F = Index16> {
32    marker1: PhantomData<T>,
33    marker2: PhantomData<F>,
34    // safety invariant: must parse into a valid VarZeroVecComponents
35    entire_slice: Vec<u8>,
36}
37
38impl<T: ?Sized, F> Clone for VarZeroVecOwned<T, F> {
39    fn clone(&self) -> Self {
40        VarZeroVecOwned {
41            marker1: PhantomData,
42            marker2: PhantomData,
43            entire_slice: self.entire_slice.clone(),
44        }
45    }
46}
47
48// The effect of a shift on the indices in the varzerovec.
49#[derive(PartialEq)]
50enum ShiftType {
51    Insert,
52    Replace,
53    Remove,
54}
55
56impl<T: VarULE + ?Sized, F: VarZeroVecFormat> Deref for VarZeroVecOwned<T, F> {
57    type Target = VarZeroSlice<T, F>;
58    fn deref(&self) -> &VarZeroSlice<T, F> {
59        self.as_slice()
60    }
61}
62
63impl<T: VarULE + ?Sized, F> VarZeroVecOwned<T, F> {
64    /// Construct an empty [`VarZeroVecOwned`]
65    pub fn new() -> Self {
66        Self {
67            marker1: PhantomData,
68            marker2: PhantomData,
69            entire_slice: Vec::new(),
70        }
71    }
72}
73
74impl<T: VarULE + ?Sized, F: VarZeroVecFormat> VarZeroVecOwned<T, F> {
75    /// Construct a [`VarZeroVecOwned`] from a [`VarZeroSlice`] by cloning the internal data
76    pub fn from_slice(slice: &VarZeroSlice<T, F>) -> Self {
77        Self {
78            marker1: PhantomData,
79            marker2: PhantomData,
80            entire_slice: slice.as_bytes().into(),
81        }
82    }
83
84    /// Construct a [`VarZeroVecOwned`] from a list of elements
85    pub fn try_from_elements<A>(elements: &[A]) -> Result<Self, &'static str>
86    where
87        A: EncodeAsVarULE<T>,
88    {
89        Ok(if elements.is_empty() {
90            Self::from_slice(VarZeroSlice::new_empty())
91        } else {
92            Self {
93                marker1: PhantomData,
94                marker2: PhantomData,
95                // TODO(#1410): Rethink length errors in VZV.
96                entire_slice: components::get_serializable_bytes_non_empty::<T, A, F>(elements)
97                    .ok_or(F::Index::TOO_LARGE_ERROR)?,
98            }
99        })
100    }
101
102    /// Obtain this `VarZeroVec` as a [`VarZeroSlice`]
103    pub fn as_slice(&self) -> &VarZeroSlice<T, F> {
104        let slice: &[u8] = &self.entire_slice;
105        unsafe {
106            // safety: the slice is known to come from a valid parsed VZV
107            VarZeroSlice::from_bytes_unchecked(slice)
108        }
109    }
110
111    /// Try to allocate a buffer with enough capacity for `capacity`
112    /// elements. Since `T` can take up an arbitrary size this will
113    /// just allocate enough space for 4-byte Ts
114    pub(crate) fn with_capacity(capacity: usize) -> Self {
115        Self {
116            marker1: PhantomData,
117            marker2: PhantomData,
118            entire_slice: Vec::with_capacity(capacity * (F::Index::SIZE + 4)),
119        }
120    }
121
122    /// Try to reserve space for `capacity`
123    /// elements. Since `T` can take up an arbitrary size this will
124    /// just allocate enough space for 4-byte Ts
125    pub(crate) fn reserve(&mut self, capacity: usize) {
126        self.entire_slice.reserve(capacity * (F::Index::SIZE + 4))
127    }
128
129    /// Get the position of a specific element in the data segment.
130    ///
131    /// If `idx == self.len()`, it will return the size of the data segment (where a new element would go).
132    ///
133    /// ## Safety
134    /// `idx <= self.len()` and `self.as_encoded_bytes()` is well-formed.
135    unsafe fn element_position_unchecked(&self, idx: usize) -> usize {
136        let len = self.len();
137        if len == 0 {
138            return 0;
139        }
140        let out = if idx == len {
141            let indices_size = F::Index::SIZE
142                .checked_mul(len - 1)
143                .expect(F::Index::TOO_LARGE_ERROR);
144            self.entire_slice.len() - F::Len::SIZE - indices_size
145        } else if let Some(idx) = self.index_data(idx) {
146            idx.iule_to_usize()
147        } else {
148            0
149        };
150        let indices_size = F::Index::SIZE
151            .checked_mul(len - 1)
152            .expect(F::Index::TOO_LARGE_ERROR);
153        debug_assert!(out + F::Len::SIZE + indices_size <= self.entire_slice.len());
154        out
155    }
156
157    /// Get the range of a specific element in the data segment.
158    ///
159    /// ## Safety
160    /// `idx < self.len()` and `self.as_encoded_bytes()` is well-formed.
161    unsafe fn element_range_unchecked(&self, idx: usize) -> Range<usize> {
162        let start = self.element_position_unchecked(idx);
163        let end = self.element_position_unchecked(idx + 1);
164        debug_assert!(start <= end, "{start} > {end}");
165        start..end
166    }
167
168    /// Set the number of elements in the list without any checks.
169    ///
170    /// ## Safety
171    /// No safe functions may be called until `self.as_encoded_bytes()` is well-formed.
172    unsafe fn set_len(&mut self, len: usize) {
173        assert!(len <= F::Len::MAX_VALUE as usize);
174        let len_bytes = len.to_le_bytes();
175        let len_ule = F::Len::iule_from_usize(len).expect(F::Len::TOO_LARGE_ERROR);
176        self.entire_slice[0..F::Len::SIZE].copy_from_slice(ULE::slice_as_bytes(&[len_ule]));
177        // Double-check that the length fits in the length field
178        assert_eq!(len_bytes[F::Len::SIZE..].iter().sum::<u8>(), 0);
179    }
180
181    /// Get the range in the full data for a given index. Returns None for index 0
182    /// since there is no stored index for it.
183    fn index_range(index: usize) -> Option<Range<usize>> {
184        let index_minus_one = index.checked_sub(1)?;
185        let pos = F::Len::SIZE
186            + F::Index::SIZE
187                .checked_mul(index_minus_one)
188                .expect(F::Index::TOO_LARGE_ERROR);
189        Some(pos..pos + F::Index::SIZE)
190    }
191
192    /// Return the raw bytes representing the given `index`. Returns None when given index 0
193    ///
194    /// ## Safety
195    /// The index must be valid, and `self.as_encoded_bytes()` must be well-formed
196    unsafe fn index_data(&self, index: usize) -> Option<&F::Index> {
197        let index_range = Self::index_range(index)?;
198        Some(&F::Index::slice_from_bytes_unchecked(&self.entire_slice[index_range])[0])
199    }
200
201    /// Return the mutable slice representing the given `index`. Returns None when given index 0
202    ///
203    /// ## Safety
204    /// The index must be valid. `self.as_encoded_bytes()` must have allocated space
205    /// for this index, but need not have its length appropriately set.
206    unsafe fn index_data_mut(&mut self, index: usize) -> Option<&mut F::Index> {
207        let ptr = self.entire_slice.as_mut_ptr();
208        let range = Self::index_range(index)?;
209
210        // Doing this instead of just `get_unchecked_mut()` because it's unclear
211        // if `get_unchecked_mut()` can be called out of bounds on a slice even
212        // if we know the buffer is larger.
213        let data = slice::from_raw_parts_mut(ptr.add(range.start), F::Index::SIZE);
214        Some(&mut F::Index::iule_from_bytes_unchecked_mut(data)[0])
215    }
216
217    /// Shift the indices starting with and after `starting_index` by the provided `amount`.
218    ///
219    /// ## Panics
220    /// Should never be called with a starting index of 0, since that index cannot be shifted.
221    ///
222    /// ## Safety
223    /// Adding `amount` to each index after `starting_index` must not result in the slice from becoming malformed.
224    /// The length of the slice must be correctly set.
225    unsafe fn shift_indices(&mut self, starting_index: usize, amount: i32) {
226        let normalized_idx = starting_index
227            .checked_sub(1)
228            .expect("shift_indices called with a 0 starting index");
229        let len = self.len();
230        let indices_size = F::Index::SIZE
231            .checked_mul(len - 1)
232            .expect(F::Index::TOO_LARGE_ERROR);
233        let indices = F::Index::iule_from_bytes_unchecked_mut(
234            &mut self.entire_slice[F::Len::SIZE..F::Len::SIZE + indices_size],
235        );
236        for idx in &mut indices[normalized_idx..] {
237            let mut new_idx = idx.iule_to_usize();
238            if amount > 0 {
239                new_idx = new_idx.checked_add(amount.try_into().unwrap()).unwrap();
240            } else {
241                new_idx = new_idx.checked_sub((-amount).try_into().unwrap()).unwrap();
242            }
243            *idx = F::Index::iule_from_usize(new_idx).expect(F::Index::TOO_LARGE_ERROR);
244        }
245    }
246
247    /// Get this [`VarZeroVecOwned`] as a borrowed [`VarZeroVec`]
248    ///
249    /// If you wish to repeatedly call methods on this [`VarZeroVecOwned`],
250    /// it is more efficient to perform this conversion first
251    pub fn as_varzerovec<'a>(&'a self) -> VarZeroVec<'a, T, F> {
252        self.as_slice().into()
253    }
254
255    /// Empty the vector
256    pub fn clear(&mut self) {
257        self.entire_slice.clear()
258    }
259
260    /// Consume this vector and return the backing buffer
261    #[inline]
262    pub fn into_bytes(self) -> Vec<u8> {
263        self.entire_slice
264    }
265
266    /// Invalidate and resize the data at an index, optionally inserting or removing the index.
267    /// Also updates affected indices and the length.
268    ///
269    /// `new_size` is the encoded byte size of the element that is going to be inserted
270    ///
271    /// Returns a slice to the new element data - it doesn't contain uninitialized data but its value is indeterminate.
272    ///
273    /// ## Safety
274    /// - `index` must be a valid index, or, if `shift_type == ShiftType::Insert`, `index == self.len()` is allowed.
275    /// - `new_size` musn't result in the data segment growing larger than `F::Index::MAX_VALUE`.
276    unsafe fn shift(&mut self, index: usize, new_size: usize, shift_type: ShiftType) -> &mut [u8] {
277        // The format of the encoded data is:
278        //  - four bytes of "len"
279        //  - len*4 bytes for an array of indices
280        //  - the actual data to which the indices point
281        //
282        // When inserting or removing an element, the size of the indices segment must be changed,
283        // so the data before the target element must be shifted by 4 bytes in addition to the
284        // shifting needed for the new element size.
285        let len = self.len();
286        let slice_len = self.entire_slice.len();
287
288        let prev_element = match shift_type {
289            ShiftType::Insert => {
290                let pos = self.element_position_unchecked(index);
291                // In the case of an insert, there's no previous element,
292                // so it's an empty range at the new position.
293                pos..pos
294            }
295            _ => self.element_range_unchecked(index),
296        };
297
298        // How much shifting must be done in bytes due to removal/insertion of an index.
299        let index_shift: i64 = match shift_type {
300            ShiftType::Insert => F::Index::SIZE as i64,
301            ShiftType::Replace => 0,
302            ShiftType::Remove => -(F::Index::SIZE as i64),
303        };
304        // The total shift in byte size of the owned slice.
305        let shift: i64 =
306            new_size as i64 - (prev_element.end - prev_element.start) as i64 + index_shift;
307        let new_slice_len = slice_len.wrapping_add(shift as usize);
308        if shift > 0 {
309            if new_slice_len > F::Index::MAX_VALUE as usize {
310                panic!(
311                    "Attempted to grow VarZeroVec to an encoded size that does not fit within the length size used by {}",
312                    any::type_name::<F>()
313                );
314            }
315            self.entire_slice.resize(new_slice_len, 0);
316        }
317
318        // Now that we've ensured there's enough space, we can shift the data around.
319        {
320            // Note: There are no references introduced between pointer creation and pointer use, and all
321            //       raw pointers are derived from a single &mut. This preserves pointer provenance.
322            let slice_range = self.entire_slice.as_mut_ptr_range();
323            // The start of the indices buffer
324            let indices_start = slice_range.start.add(F::Len::SIZE);
325            let old_slice_end = slice_range.start.add(slice_len);
326            let indices_size = F::Index::SIZE
327                .checked_mul(len - 1)
328                .expect(F::Index::TOO_LARGE_ERROR);
329            let data_start = indices_start.add(indices_size);
330            let prev_element_p =
331                data_start.add(prev_element.start)..data_start.add(prev_element.end);
332
333            // The memory range of the affected index.
334            // When inserting: where the new index goes.
335            // When removing:  where the index being removed is.
336            // When replacing: unused.
337            // Will be None when the affected index is index 0, which is special
338            let index_range = if let Some(index_minus_one) = index.checked_sub(1) {
339                let index_offset = F::Index::SIZE
340                    .checked_mul(index_minus_one)
341                    .expect(F::Index::TOO_LARGE_ERROR);
342                let index_start = indices_start.add(index_offset);
343                Some(index_start..index_start.add(F::Index::SIZE))
344            } else {
345                None
346            };
347
348            unsafe fn shift_bytes(block: Range<*const u8>, to: *mut u8) {
349                debug_assert!(block.end >= block.start);
350                ptr::copy(block.start, to, block.end.offset_from(block.start) as usize);
351            }
352
353            if shift_type == ShiftType::Remove {
354                if let Some(ref index_range) = index_range {
355                    shift_bytes(index_range.end..prev_element_p.start, index_range.start);
356                } else {
357                    // We are removing the first index, so we skip the second index and copy it over. The second index
358                    // is now zero and unnecessary.
359                    shift_bytes(
360                        indices_start.add(F::Index::SIZE)..prev_element_p.start,
361                        indices_start,
362                    )
363                }
364            }
365
366            // Shift data after the element to its new position.
367            shift_bytes(
368                prev_element_p.end..old_slice_end,
369                prev_element_p
370                    .start
371                    .offset((new_size as i64 + index_shift) as isize),
372            );
373
374            let first_affected_index = match shift_type {
375                ShiftType::Insert => {
376                    if let Some(index_range) = index_range {
377                        // Move data before the element forward by 4 to make space for a new index.
378                        shift_bytes(index_range.start..prev_element_p.start, index_range.end);
379                        let index_data = self
380                            .index_data_mut(index)
381                            .expect("If index_range is some, index is > 0 and should not panic in index_data_mut");
382                        *index_data = F::Index::iule_from_usize(prev_element.start)
383                            .expect(F::Index::TOO_LARGE_ERROR);
384                    } else {
385                        // We are adding a new index 0. There's nothing in the indices array for index 0, but the element
386                        // that is currently at index 0 will become index 1 and need a value
387                        // We first shift bytes to make space
388                        shift_bytes(
389                            indices_start..prev_element_p.start,
390                            indices_start.add(F::Index::SIZE),
391                        );
392                        // And then we write a temporary zero to the zeroeth index, which will get shifted later
393                        let index_data = self
394                            .index_data_mut(1)
395                            .expect("Should be able to write to index 1");
396                        *index_data = F::Index::iule_from_usize(0).expect("0 is always valid!");
397                    }
398
399                    self.set_len(len + 1);
400                    index + 1
401                }
402                ShiftType::Remove => {
403                    self.set_len(len - 1);
404                    if index == 0 {
405                        // We don't need to shift index 0 since index 0 is not stored in the indices buffer
406                        index + 1
407                    } else {
408                        index
409                    }
410                }
411                ShiftType::Replace => index + 1,
412            };
413            // No raw pointer use should occur after this point (because of self.index_data and self.set_len).
414
415            // Set the new slice length. This must be done after shifting data around to avoid uninitialized data.
416            self.entire_slice.set_len(new_slice_len);
417            // Shift the affected indices.
418            self.shift_indices(first_affected_index, (shift - index_shift) as i32);
419        };
420
421        debug_assert!(self.verify_integrity());
422
423        // Return a mut slice to the new element data.
424        let indices_size = F::Index::SIZE
425            .checked_mul(self.len() - 1)
426            .expect(F::Index::TOO_LARGE_ERROR);
427        let element_pos = F::Len::SIZE + indices_size + self.element_position_unchecked(index);
428        &mut self.entire_slice[element_pos..element_pos + new_size]
429    }
430
431    /// Checks the internal invariants of the vec to ensure safe code will not cause UB.
432    /// Returns whether integrity was verified.
433    ///
434    /// Note: an index is valid if it doesn't point to data past the end of the slice and is
435    /// less than or equal to all future indices. The length of the index segment is not part of each index.
436    fn verify_integrity(&self) -> bool {
437        if self.is_empty() {
438            if self.entire_slice.is_empty() {
439                return true;
440            } else {
441                panic!(
442                    "VarZeroVecOwned integrity: Found empty VarZeroVecOwned with a nonempty slice"
443                );
444            }
445        }
446        let len = unsafe {
447            <F::Len as ULE>::slice_from_bytes_unchecked(&self.entire_slice[..F::Len::SIZE])[0]
448                .iule_to_usize()
449        };
450        if len == 0 {
451            // An empty vec must have an empty slice: there is only a single valid byte representation.
452            panic!("VarZeroVecOwned integrity: Found empty VarZeroVecOwned with a nonempty slice");
453        }
454        let indices_size = F::Index::SIZE
455            .checked_mul(len - 1)
456            .expect(F::Index::TOO_LARGE_ERROR);
457        if self.entire_slice.len() < F::Len::SIZE + indices_size {
458            panic!("VarZeroVecOwned integrity: Not enough room for the indices");
459        }
460        let data_len = self.entire_slice.len() - F::Len::SIZE - indices_size;
461        if data_len > F::Index::MAX_VALUE as usize {
462            panic!("VarZeroVecOwned integrity: Data segment is too long");
463        }
464
465        // Test index validity.
466        let indices = unsafe {
467            F::Index::slice_from_bytes_unchecked(
468                &self.entire_slice[F::Len::SIZE..F::Len::SIZE + indices_size],
469            )
470        };
471        for idx in indices {
472            if idx.iule_to_usize() > data_len {
473                panic!("VarZeroVecOwned integrity: Indices must not point past the data segment");
474            }
475        }
476        for window in indices.windows(2) {
477            if window[0].iule_to_usize() > window[1].iule_to_usize() {
478                panic!("VarZeroVecOwned integrity: Indices must be in non-decreasing order");
479            }
480        }
481        true
482    }
483
484    /// Insert an element at the end of this vector
485    pub fn push<A: EncodeAsVarULE<T> + ?Sized>(&mut self, element: &A) {
486        self.insert(self.len(), element)
487    }
488
489    /// Insert an element at index `idx`
490    pub fn insert<A: EncodeAsVarULE<T> + ?Sized>(&mut self, index: usize, element: &A) {
491        let len = self.len();
492        if index > len {
493            panic!("Called out-of-bounds insert() on VarZeroVec, index {index} len {len}");
494        }
495
496        let value_len = element.encode_var_ule_len();
497        assert!(value_len < F::Index::MAX_VALUE as usize);
498
499        if len == 0 {
500            let header_len = F::Len::SIZE; // Index array is size 0 for len = 1
501            let cap = header_len + value_len;
502            let guard = ClearOnPanic(self);
503            guard.0.entire_slice.resize(cap, 0);
504            guard.0.entire_slice[0] = 1; // set length
505            element.encode_var_ule_write(&mut guard.0.entire_slice[header_len..]);
506            debug_assert_eq!(
507                T::validate_bytes(&guard.0.entire_slice[header_len..]),
508                Ok(())
509            );
510            core::mem::forget(guard);
511            return;
512        }
513
514        let guard = ClearOnPanic(self);
515        // SAFETY:
516        // - `index <= self.len()` is checked above (`ShiftType::Insert` allows `index == self.len()`).
517        // - `value_len < F::Index::MAX_VALUE` is asserted above, and `shift` checks that the
518        //   total grown slice length fits within `F::Index::MAX_VALUE`.
519        // - `guard` clears `entire_slice` if `shift` or `encode_var_ule_write` panics,
520        //   preventing partially-mutated state from being observed after unwinding.
521        unsafe {
522            let place = guard.0.shift(index, value_len, ShiftType::Insert);
523            element.encode_var_ule_write(place);
524            debug_assert_eq!(T::validate_bytes(place), Ok(()));
525        }
526        core::mem::forget(guard);
527    }
528
529    /// Remove the element at index `idx`
530    pub fn remove(&mut self, index: usize) {
531        let len = self.len();
532        if index >= len {
533            panic!("Called out-of-bounds remove() on VarZeroVec, index {index} len {len}");
534        }
535        if len == 1 {
536            // This is removing the last element. Set the slice to empty to ensure all empty vecs have empty data slices.
537            self.entire_slice.clear();
538            return;
539        }
540        let guard = ClearOnPanic(self);
541        // SAFETY:
542        // - `index < self.len()` is checked above.
543        // - `new_size` is 0, so the data segment does not grow.
544        // - `guard` clears `entire_slice` if `shift` panics.
545        unsafe {
546            guard.0.shift(index, 0, ShiftType::Remove);
547        }
548        core::mem::forget(guard);
549    }
550
551    /// Replace the element at index `idx` with another
552    pub fn replace<A: EncodeAsVarULE<T> + ?Sized>(&mut self, index: usize, element: &A) {
553        let len = self.len();
554        if index >= len {
555            panic!("Called out-of-bounds replace() on VarZeroVec, index {index} len {len}");
556        }
557
558        let value_len = element.encode_var_ule_len();
559
560        assert!(value_len < F::Index::MAX_VALUE as usize);
561        let guard = ClearOnPanic(self);
562        // SAFETY:
563        // - `index < self.len()` is checked above.
564        // - `value_len < F::Index::MAX_VALUE` is asserted above, and `shift` checks that the
565        //   total grown slice length fits within `F::Index::MAX_VALUE`.
566        // - `guard` clears `entire_slice` if `shift` or `encode_var_ule_write` panics,
567        //   preventing partially-mutated state from being observed after unwinding.
568        unsafe {
569            let place = guard.0.shift(index, value_len, ShiftType::Replace);
570            element.encode_var_ule_write(place);
571            debug_assert_eq!(T::validate_bytes(place), Ok(()));
572        }
573        core::mem::forget(guard);
574    }
575}
576
577/// Drop guard that clears `entire_slice` if a panic occurs during an in-place
578/// mutation (e.g. inside `shift` or a user-provided `EncodeAsVarULE::encode_var_ule_write`),
579/// restoring the safety invariant that `entire_slice` is a valid (empty) `VarZeroVecComponents`.
580struct ClearOnPanic<'a, T: ?Sized, F>(&'a mut VarZeroVecOwned<T, F>);
581
582impl<T: ?Sized, F> Drop for ClearOnPanic<'_, T, F> {
583    fn drop(&mut self) {
584        self.0.entire_slice.clear();
585    }
586}
587
588impl<T: VarULE + ?Sized, F: VarZeroVecFormat> fmt::Debug for VarZeroVecOwned<T, F>
589where
590    T: fmt::Debug,
591{
592    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
593        VarZeroSlice::fmt(self, f)
594    }
595}
596
597impl<T: VarULE + ?Sized, F> Default for VarZeroVecOwned<T, F> {
598    fn default() -> Self {
599        Self::new()
600    }
601}
602
603impl<T, A, F> PartialEq<&'_ [A]> for VarZeroVecOwned<T, F>
604where
605    T: VarULE + ?Sized,
606    T: PartialEq,
607    A: AsRef<T>,
608    F: VarZeroVecFormat,
609{
610    #[inline]
611    fn eq(&self, other: &&[A]) -> bool {
612        self.iter().eq(other.iter().map(|t| t.as_ref()))
613    }
614}
615
616impl<'a, T: ?Sized + VarULE, F: VarZeroVecFormat> From<&'a VarZeroSlice<T, F>>
617    for VarZeroVecOwned<T, F>
618{
619    fn from(other: &'a VarZeroSlice<T, F>) -> Self {
620        Self::from_slice(other)
621    }
622}
623
624#[cfg(test)]
625mod test {
626    use super::VarZeroVecOwned;
627    #[test]
628    fn test_insert_integrity() {
629        let mut items: Vec<String> = Vec::new();
630        let mut zerovec = VarZeroVecOwned::<str>::new();
631
632        // Insert into an empty vec.
633        items.insert(0, "1234567890".into());
634        zerovec.insert(0, "1234567890");
635        assert_eq!(zerovec, &*items);
636
637        zerovec.insert(1, "foo3");
638        items.insert(1, "foo3".into());
639        assert_eq!(zerovec, &*items);
640
641        // Insert at the end.
642        items.insert(items.len(), "qwertyuiop".into());
643        zerovec.insert(zerovec.len(), "qwertyuiop");
644        assert_eq!(zerovec, &*items);
645
646        items.insert(0, "asdfghjkl;".into());
647        zerovec.insert(0, "asdfghjkl;");
648        assert_eq!(zerovec, &*items);
649
650        items.insert(2, "".into());
651        zerovec.insert(2, "");
652        assert_eq!(zerovec, &*items);
653    }
654
655    #[test]
656    // ensure that inserting empty items works
657    fn test_empty_inserts() {
658        let mut items: Vec<String> = Vec::new();
659        let mut zerovec = VarZeroVecOwned::<str>::new();
660
661        // Insert into an empty vec.
662        items.insert(0, "".into());
663        zerovec.insert(0, "");
664        assert_eq!(zerovec, &*items);
665
666        items.insert(0, "".into());
667        zerovec.insert(0, "");
668        assert_eq!(zerovec, &*items);
669
670        items.insert(0, "1234567890".into());
671        zerovec.insert(0, "1234567890");
672        assert_eq!(zerovec, &*items);
673
674        items.insert(0, "".into());
675        zerovec.insert(0, "");
676        assert_eq!(zerovec, &*items);
677    }
678
679    #[test]
680    fn test_small_insert_integrity() {
681        // Tests that insert() works even when there
682        // is not enough space for the new index in entire_slice.len()
683        let mut items: Vec<String> = Vec::new();
684        let mut zerovec = VarZeroVecOwned::<str>::new();
685
686        // Insert into an empty vec.
687        items.insert(0, "abc".into());
688        zerovec.insert(0, "abc");
689        assert_eq!(zerovec, &*items);
690
691        zerovec.insert(1, "def");
692        items.insert(1, "def".into());
693        assert_eq!(zerovec, &*items);
694    }
695
696    #[test]
697    #[should_panic]
698    fn test_insert_past_end() {
699        VarZeroVecOwned::<str>::new().insert(1, "");
700    }
701
702    #[test]
703    fn test_remove_integrity() {
704        let mut items: Vec<&str> = vec!["apples", "bananas", "eeples", "", "baneenees", "five", ""];
705        let mut zerovec = VarZeroVecOwned::<str>::try_from_elements(&items).unwrap();
706
707        for index in [0, 2, 4, 0, 1, 1, 0] {
708            items.remove(index);
709            zerovec.remove(index);
710            assert_eq!(zerovec, &*items, "index {}, len {}", index, items.len());
711        }
712    }
713
714    #[test]
715    fn test_removing_last_element_clears() {
716        let mut zerovec = VarZeroVecOwned::<str>::try_from_elements(&["buy some apples"]).unwrap();
717        assert!(!zerovec.as_bytes().is_empty());
718        zerovec.remove(0);
719        assert!(zerovec.as_bytes().is_empty());
720    }
721
722    #[test]
723    #[should_panic]
724    fn test_remove_past_end() {
725        VarZeroVecOwned::<str>::new().remove(0);
726    }
727
728    #[test]
729    fn test_replace_integrity() {
730        let mut items: Vec<&str> = vec!["apples", "bananas", "eeples", "", "baneenees", "five", ""];
731        let mut zerovec = VarZeroVecOwned::<str>::try_from_elements(&items).unwrap();
732
733        // Replace with an element of the same size (and the first element)
734        items[0] = "blablah";
735        zerovec.replace(0, "blablah");
736        assert_eq!(zerovec, &*items);
737
738        // Replace with a smaller element
739        items[1] = "twily";
740        zerovec.replace(1, "twily");
741        assert_eq!(zerovec, &*items);
742
743        // Replace an empty element
744        items[3] = "aoeuidhtns";
745        zerovec.replace(3, "aoeuidhtns");
746        assert_eq!(zerovec, &*items);
747
748        // Replace the last element
749        items[6] = "0123456789";
750        zerovec.replace(6, "0123456789");
751        assert_eq!(zerovec, &*items);
752
753        // Replace with an empty element
754        items[2] = "";
755        zerovec.replace(2, "");
756        assert_eq!(zerovec, &*items);
757    }
758
759    #[test]
760    #[should_panic]
761    fn test_replace_past_end() {
762        VarZeroVecOwned::<str>::new().replace(0, "");
763    }
764
765    #[test]
766    #[cfg(feature = "std")]
767    fn test_panic_safety() {
768        use crate::ule::EncodeAsVarULE;
769        use std::panic::{catch_unwind, AssertUnwindSafe};
770
771        struct PanicAfterWrite {
772            invalid: &'static [u8],
773        }
774
775        // SAFETY: `encode_var_ule_write` always panics and never returns normally,
776        // so callers must not observe the invalid bytes written before unwinding.
777        unsafe impl EncodeAsVarULE<str> for PanicAfterWrite {
778            fn encode_var_ule_as_slices<R>(&self, cb: impl FnOnce(&[&[u8]]) -> R) -> R {
779                cb(&[self.invalid])
780            }
781
782            fn encode_var_ule_len(&self) -> usize {
783                self.invalid.len()
784            }
785
786            fn encode_var_ule_write(&self, dst: &mut [u8]) {
787                dst.copy_from_slice(self.invalid);
788                panic!("encode_var_ule_write panicked after writing invalid bytes");
789            }
790        }
791
792        let panicker = PanicAfterWrite {
793            invalid: &[0x80, 0xC0, 0xFF],
794        };
795
796        // 1. `replace` on non-empty vector
797        let mut v = VarZeroVecOwned::<str>::try_from_elements(&["hello"]).unwrap();
798        let res = catch_unwind(AssertUnwindSafe(|| {
799            v.replace(0, &panicker);
800        }));
801        assert!(res.is_err());
802        assert!(v.is_empty());
803        assert_eq!(v.get(0), None);
804        assert!(v.verify_integrity());
805
806        // 2. `insert` into empty vector (`len == 0` fast-path)
807        let mut v = VarZeroVecOwned::<str>::new();
808        let res = catch_unwind(AssertUnwindSafe(|| {
809            v.insert(0, &panicker);
810        }));
811        assert!(res.is_err());
812        assert!(v.is_empty());
813        assert_eq!(v.get(0), None);
814        assert!(v.verify_integrity());
815
816        // 3. `insert` into non-empty vector (`len > 0` shift path)
817        let mut v = VarZeroVecOwned::<str>::try_from_elements(&["hello", "world"]).unwrap();
818        let res = catch_unwind(AssertUnwindSafe(|| {
819            v.insert(1, &panicker);
820        }));
821        assert!(res.is_err());
822        assert!(v.is_empty());
823        assert_eq!(v.get(0), None);
824        assert!(v.verify_integrity());
825    }
826}