zerovec/varzerovec/
components.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#![allow(unused_qualifications)]
6
7use super::VarZeroVecFormatError;
8use crate::ule::*;
9use core::cmp::Ordering;
10use core::convert::TryFrom;
11use core::marker::PhantomData;
12use core::ops::Range;
13
14/// This trait allows switching between different possible internal
15/// representations of [`VarZeroVec`](super::VarZeroVec).
16///
17/// Currently this crate supports three formats: [`Index8`], [`Index16`] and [`Index32`],
18/// with [`Index16`] being the default for all [`VarZeroVec`](super::VarZeroVec)
19/// types unless explicitly specified otherwise.
20///
21/// Do not implement this trait, its internals may be changed in the future,
22/// and all of its associated items are hidden from the docs.
23pub trait VarZeroVecFormat: 'static + Sized {
24    /// The type to use for the indexing array
25    ///
26    /// Safety: must be a ULE for which all byte sequences are allowed
27    #[doc(hidden)]
28    type Index: IntegerULE;
29    /// The type to use for the length segment
30    ///
31    /// Safety: must be a ULE for which all byte sequences are allowed
32    #[doc(hidden)]
33    type Len: IntegerULE;
34}
35
36/// This trait represents various ULE types that can be used to represent an integer
37///
38/// Do not implement this trait, its internals may be changed in the future,
39/// and all of its associated items are hidden from the docs.
40#[doc(hidden)]
41pub unsafe trait IntegerULE: ULE {
42    /// The error to show when unable to construct a vec
43    #[doc(hidden)]
44    const TOO_LARGE_ERROR: &'static str;
45
46    /// Safety: must be sizeof(self)
47    #[doc(hidden)]
48    const SIZE: usize;
49
50    /// Safety: must be maximum integral value represented here
51    #[doc(hidden)]
52    const MAX_VALUE: u32;
53
54    /// Safety: Must roundtrip with from_usize and represent the correct
55    /// integral value
56    #[doc(hidden)]
57    fn iule_to_usize(self) -> usize;
58
59    #[doc(hidden)]
60    fn iule_from_usize(x: usize) -> Option<Self>;
61
62    /// Safety: Should always convert a buffer into an array of Self with the correct length
63    #[doc(hidden)]
64    #[cfg(feature = "alloc")]
65    fn iule_from_bytes_unchecked_mut(bytes: &mut [u8]) -> &mut [Self];
66}
67
68/// This is a [`VarZeroVecFormat`] that stores u8s in the index array, and a u8 for a length.
69///
70/// Will have a smaller data size, but it's *extremely* likely for larger arrays
71/// to be unrepresentable (and error on construction). Should probably be used
72/// for known-small arrays, where all but the last field are known-small.
73#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
74#[allow(clippy::exhaustive_structs)] // marker
75pub struct Index8;
76
77/// This is a [`VarZeroVecFormat`] that stores u16s in the index array, and a u16 for a length.
78///
79/// Will have a smaller data size, but it's more likely for larger arrays
80/// to be unrepresentable (and error on construction)
81///
82/// This is the default index size used by all [`VarZeroVec`](super::VarZeroVec) types.
83#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
84#[allow(clippy::exhaustive_structs)] // marker
85pub struct Index16;
86
87/// This is a [`VarZeroVecFormat`] that stores u32s in the index array, and a u32 for a length.
88/// Will have a larger data size, but will support large arrays without
89/// problems.
90#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
91#[allow(clippy::exhaustive_structs)] // marker
92pub struct Index32;
93
94impl VarZeroVecFormat for Index8 {
95    type Index = u8;
96    type Len = u8;
97}
98
99impl VarZeroVecFormat for Index16 {
100    type Index = RawBytesULE<2>;
101    type Len = RawBytesULE<2>;
102}
103
104impl VarZeroVecFormat for Index32 {
105    type Index = RawBytesULE<4>;
106    type Len = RawBytesULE<4>;
107}
108
109unsafe impl IntegerULE for u8 {
110    const TOO_LARGE_ERROR: &'static str = "Attempted to build VarZeroVec out of elements that \
111                                     cumulatively are larger than a u8 in size";
112    const SIZE: usize = size_of::<Self>();
113    const MAX_VALUE: u32 = u8::MAX as u32;
114    #[inline]
115    fn iule_to_usize(self) -> usize {
116        self as usize
117    }
118    #[inline]
119    fn iule_from_usize(u: usize) -> Option<Self> {
120        u8::try_from(u).ok()
121    }
122    #[inline]
123    #[cfg(feature = "alloc")]
124    fn iule_from_bytes_unchecked_mut(bytes: &mut [u8]) -> &mut [Self] {
125        bytes
126    }
127}
128
129unsafe impl IntegerULE for RawBytesULE<2> {
130    const TOO_LARGE_ERROR: &'static str = "Attempted to build VarZeroVec out of elements that \
131                                     cumulatively are larger than a u16 in size";
132    const SIZE: usize = size_of::<Self>();
133    const MAX_VALUE: u32 = u16::MAX as u32;
134    #[inline]
135    fn iule_to_usize(self) -> usize {
136        self.as_unsigned_int() as usize
137    }
138    #[inline]
139    fn iule_from_usize(u: usize) -> Option<Self> {
140        u16::try_from(u).ok().map(u16::to_unaligned)
141    }
142    #[inline]
143    #[cfg(feature = "alloc")]
144    fn iule_from_bytes_unchecked_mut(bytes: &mut [u8]) -> &mut [Self] {
145        Self::from_bytes_unchecked_mut(bytes)
146    }
147}
148
149unsafe impl IntegerULE for RawBytesULE<4> {
150    const TOO_LARGE_ERROR: &'static str = "Attempted to build VarZeroVec out of elements that \
151                                     cumulatively are larger than a u32 in size";
152    const SIZE: usize = size_of::<Self>();
153    const MAX_VALUE: u32 = u32::MAX;
154    #[inline]
155    fn iule_to_usize(self) -> usize {
156        self.as_unsigned_int() as usize
157    }
158    #[inline]
159    fn iule_from_usize(u: usize) -> Option<Self> {
160        u32::try_from(u).ok().map(u32::to_unaligned)
161    }
162    #[inline]
163    #[cfg(feature = "alloc")]
164    fn iule_from_bytes_unchecked_mut(bytes: &mut [u8]) -> &mut [Self] {
165        Self::from_bytes_unchecked_mut(bytes)
166    }
167}
168
169/// A more parsed version of [`VarZeroSlice`](super::VarZeroSlice). This type is where most of the[ `VarZeroVec`](super::VarZeroVec)
170/// internal representation code lies.
171///
172/// This is *basically* an `&'a [u8]` to a zero copy buffer, but split out into
173/// the buffer components. Logically this is capable of behaving as
174/// a `&'a [T::VarULE]`, but since `T::VarULE` is unsized that type does not actually
175/// exist.
176///
177/// See [`VarZeroVecComponents::parse_bytes()`] for information on the internal invariants involved
178#[derive(Debug)]
179pub struct VarZeroVecComponents<'a, T: ?Sized, F> {
180    /// The number of elements
181    len: u32,
182    /// The list of indices into the `things` slice
183    /// Since the first element is always at things[0], the first element of the indices array is for the *second* element
184    indices: &'a [u8],
185    /// The contiguous list of `T::VarULE`s
186    things: &'a [u8],
187    marker: PhantomData<(&'a T, F)>,
188}
189
190// #[derive()] won't work here since we do not want it to be
191// bound on T: Copy
192impl<'a, T: ?Sized, F> Copy for VarZeroVecComponents<'a, T, F> {}
193impl<'a, T: ?Sized, F> Clone for VarZeroVecComponents<'a, T, F> {
194    fn clone(&self) -> Self {
195        *self
196    }
197}
198
199impl<'a, T: VarULE + ?Sized, F> Default for VarZeroVecComponents<'a, T, F> {
200    #[inline]
201    fn default() -> Self {
202        Self::new()
203    }
204}
205
206impl<'a, T: VarULE + ?Sized, F> VarZeroVecComponents<'a, T, F> {
207    #[inline]
208    pub fn new() -> Self {
209        Self {
210            len: 0,
211            indices: &[],
212            things: &[],
213            marker: PhantomData,
214        }
215    }
216}
217impl<'a, T: VarULE + ?Sized, F: VarZeroVecFormat> VarZeroVecComponents<'a, T, F> {
218    /// Construct a new [`VarZeroVecComponents`], checking invariants about the overall buffer size:
219    ///
220    /// - There must be either zero or at least four bytes (if four, this is the "length" parsed as a usize)
221    /// - There must be at least `4*(length - 1) + 4` bytes total, to form the array `indices` of indices
222    /// - `0..indices[0]` must index into a valid section of
223    ///   `things` (the data after `indices`), such that it parses to a `T::VarULE`
224    /// - `indices[i - 1]..indices[i]` must index into a valid section of
225    ///   `things` (the data after `indices`), such that it parses to a `T::VarULE`
226    /// - `indices[len - 2]..things.len()` must index into a valid section of
227    ///   `things`, such that it parses to a `T::VarULE`
228    #[inline]
229    pub fn parse_bytes(slice: &'a [u8]) -> Result<Self, VarZeroVecFormatError> {
230        // The empty VZV is special-cased to the empty slice
231        if slice.is_empty() {
232            return Ok(VarZeroVecComponents {
233                len: 0,
234                indices: &[],
235                things: &[],
236                marker: PhantomData,
237            });
238        }
239        let len_bytes = slice
240            .get(0..F::Len::SIZE)
241            .ok_or(VarZeroVecFormatError::Metadata)?;
242        let len_ule =
243            F::Len::parse_bytes_to_slice(len_bytes).map_err(|_| VarZeroVecFormatError::Metadata)?;
244
245        let len = len_ule
246            .first()
247            .ok_or(VarZeroVecFormatError::Metadata)?
248            .iule_to_usize();
249
250        let rest = slice
251            .get(F::Len::SIZE..)
252            .ok_or(VarZeroVecFormatError::Metadata)?;
253        let len_u32 = u32::try_from(len).map_err(|_| VarZeroVecFormatError::Metadata);
254        // We pass down the rest of the invariants
255        Self::parse_bytes_with_length(len_u32?, rest)
256    }
257
258    /// Construct a new [`VarZeroVecComponents`], checking invariants about the overall buffer size:
259    ///
260    /// - There must be at least `4*len` bytes total, to form the array `indices` of indices.
261    /// - `indices[i]..indices[i+1]` must index into a valid section of
262    ///   `things` (the data after `indices`), such that it parses to a `T::VarULE`
263    /// - `indices[len - 1]..things.len()` must index into a valid section of
264    ///   `things`, such that it parses to a `T::VarULE`
265    #[inline]
266    pub fn parse_bytes_with_length(
267        len: u32,
268        slice: &'a [u8],
269    ) -> Result<Self, VarZeroVecFormatError> {
270        let len_minus_one = len.checked_sub(1);
271        // The empty VZV is special-cased to the empty slice
272        let Some(len_minus_one) = len_minus_one else {
273            return Ok(VarZeroVecComponents {
274                len: 0,
275                indices: &[],
276                things: &[],
277                marker: PhantomData,
278            });
279        };
280        // The indices array is one element shorter since the first index is always 0,
281        // so we use len_minus_one
282        //
283        // We do the math in u32 space so that we can be sure that VZVs constructed
284        // on 64 bit computers can still be used on 32 bit ones.
285        let indices_len = u32::try_from(F::Index::SIZE)
286            .ok()
287            .and_then(|x| x.checked_mul(len_minus_one))
288            .and_then(|x| usize::try_from(x).ok())
289            .ok_or(VarZeroVecFormatError::Metadata)?;
290        let indices_bytes = slice
291            .get(..indices_len)
292            .ok_or(VarZeroVecFormatError::Metadata)?;
293        let things = slice
294            .get(indices_len..)
295            .ok_or(VarZeroVecFormatError::Metadata)?;
296
297        let borrowed = VarZeroVecComponents {
298            len,
299            indices: indices_bytes,
300            things,
301            marker: PhantomData,
302        };
303
304        borrowed.check_indices_and_things()?;
305
306        Ok(borrowed)
307    }
308
309    /// Construct a [`VarZeroVecComponents`] from a byte slice that has previously
310    /// successfully returned a [`VarZeroVecComponents`] when passed to
311    /// [`VarZeroVecComponents::parse_bytes()`]. Will return the same
312    /// object as one would get from calling [`VarZeroVecComponents::parse_bytes()`].
313    ///
314    /// # Safety
315    /// The bytes must have previously successfully run through
316    /// [`VarZeroVecComponents::parse_bytes()`]
317    pub unsafe fn from_bytes_unchecked(slice: &'a [u8]) -> Self {
318        // The empty VZV is special-cased to the empty slice
319        if slice.is_empty() {
320            return VarZeroVecComponents {
321                len: 0,
322                indices: &[],
323                things: &[],
324                marker: PhantomData,
325            };
326        }
327        let (len_bytes, data_bytes) = unsafe { slice.split_at_unchecked(F::Len::SIZE) };
328        // Safety: F::Len allows all byte sequences
329        let len_ule = F::Len::slice_from_bytes_unchecked(len_bytes);
330
331        let len = len_ule.get_unchecked(0).iule_to_usize();
332        let len_u32 = len as u32;
333        debug_assert_eq!(len, len_u32 as usize);
334
335        // Safety: This method requires the bytes to have passed through `parse_bytes()`
336        // whereas we're calling something that asks for `parse_bytes_with_length()`.
337        // The two methods perform similar validation, with parse_bytes() validating an additional
338        // 4-byte `length` header.
339        Self::from_bytes_unchecked_with_length(len_u32, data_bytes)
340    }
341
342    /// Construct a [`VarZeroVecComponents`] from a byte slice that has previously
343    /// successfully returned a [`VarZeroVecComponents`] when passed to
344    /// [`VarZeroVecComponents::parse_bytes()`]. Will return the same
345    /// object as one would get from calling [`VarZeroVecComponents::parse_bytes()`].
346    ///
347    /// # Safety
348    /// The len,bytes must have previously successfully run through
349    /// [`VarZeroVecComponents::parse_bytes_with_length()`]
350    pub unsafe fn from_bytes_unchecked_with_length(len: u32, slice: &'a [u8]) -> Self {
351        let len_minus_one = len.checked_sub(1);
352        // The empty VZV is special-cased to the empty slice
353        let Some(len_minus_one) = len_minus_one else {
354            return VarZeroVecComponents {
355                len: 0,
356                indices: &[],
357                things: &[],
358                marker: PhantomData,
359            };
360        };
361        // The indices array is one element shorter since the first index is always 0,
362        // so we use len_minus_one
363        let indices_len = F::Index::SIZE.wrapping_mul(len_minus_one as usize);
364        debug_assert!(F::Index::SIZE.checked_mul(len_minus_one as usize).is_some());
365        let indices_bytes = slice.get_unchecked(..indices_len);
366        let things = slice.get_unchecked(indices_len..);
367
368        VarZeroVecComponents {
369            len,
370            indices: indices_bytes,
371            things,
372            marker: PhantomData,
373        }
374    }
375
376    /// Get the number of elements in this vector
377    #[inline]
378    pub fn len(self) -> usize {
379        self.len as usize
380    }
381
382    /// Returns `true` if the vector contains no elements.
383    #[inline]
384    pub fn is_empty(self) -> bool {
385        self.len == 0
386    }
387
388    /// Get the idx'th element out of this slice. Returns `None` if out of bounds.
389    #[inline]
390    pub fn get(self, idx: usize) -> Option<&'a T> {
391        if idx >= self.len() {
392            return None;
393        }
394        Some(unsafe { self.get_unchecked(idx) })
395    }
396
397    /// Get the idx'th element out of this slice. Does not bounds check.
398    ///
399    /// Safety:
400    /// - `idx` must be in bounds (`idx < self.len()`)
401    #[inline]
402    pub(crate) unsafe fn get_unchecked(self, idx: usize) -> &'a T {
403        let range = self.get_things_range(idx);
404        let things_slice = self.things.get_unchecked(range);
405        T::from_bytes_unchecked(things_slice)
406    }
407
408    /// Get the range in `things` for the element at `idx`. Does not bounds check.
409    ///
410    /// Safety:
411    /// - `idx` must be in bounds (`idx < self.len()`)
412    #[inline]
413    pub(crate) unsafe fn get_things_range(self, idx: usize) -> Range<usize> {
414        let start = if let Some(idx_minus_one) = idx.checked_sub(1) {
415            self.indices_slice()
416                .get_unchecked(idx_minus_one)
417                .iule_to_usize()
418        } else {
419            0
420        };
421        let end = if idx + 1 == self.len() {
422            self.things.len()
423        } else {
424            self.indices_slice().get_unchecked(idx).iule_to_usize()
425        };
426        debug_assert!(start <= end);
427        start..end
428    }
429
430    /// Get the size, in bytes, of the indices array
431    pub(crate) unsafe fn get_indices_size(self) -> usize {
432        self.indices.len()
433    }
434
435    /// Check the internal invariants of [`VarZeroVecComponents`]:
436    ///
437    /// - `indices[i]..indices[i+1]` must index into a valid section of
438    ///   `things`, such that it parses to a `T::VarULE`
439    /// - `indices[len - 1]..things.len()` must index into a valid section of
440    ///   `things`, such that it parses to a `T::VarULE`
441    /// - `indices` is monotonically increasing
442    ///
443    /// This method is NOT allowed to call any other methods on [`VarZeroVecComponents`] since all other methods
444    /// assume that the slice has been passed through [`Self::check_indices_and_things`]
445    #[inline]
446    #[expect(clippy::len_zero)] // more explicit to enforce safety invariants
447    fn check_indices_and_things(self) -> Result<(), VarZeroVecFormatError> {
448        if self.len() == 0 {
449            if self.things.len() > 0 {
450                return Err(VarZeroVecFormatError::Metadata);
451            } else {
452                return Ok(());
453            }
454        }
455        let indices_slice = self.indices_slice();
456        assert_eq!(self.len(), indices_slice.len() + 1);
457        // Safety: i is in bounds (assertion above)
458        let mut start = 0;
459        for i in 0..self.len() {
460            // The indices array is offset by 1: indices[0] is the end of the first
461            // element and the start of the next, since the start of the first element
462            // is always things[0]. So to get the end we get element `i`.
463            let end = if let Some(end) = indices_slice.get(i) {
464                end.iule_to_usize()
465            } else {
466                // This only happens at i = self.len() - 1 = indices_slice.len() + 1 - 1
467                // = indices_slice.len(). This is the last `end`, which is always the size of
468                // `things` and thus never stored in the array
469                self.things.len()
470            };
471
472            if start > end {
473                return Err(VarZeroVecFormatError::Metadata);
474            }
475            if end > self.things.len() {
476                return Err(VarZeroVecFormatError::Metadata);
477            }
478            // Safety: start..end is a valid range in self.things
479            let bytes = unsafe { self.things.get_unchecked(start..end) };
480            T::parse_bytes(bytes).map_err(VarZeroVecFormatError::Values)?;
481            start = end;
482        }
483        Ok(())
484    }
485
486    /// Create an iterator over the Ts contained in [`VarZeroVecComponents`]
487    #[inline]
488    pub fn iter(self) -> VarZeroSliceIter<'a, T, F> {
489        VarZeroSliceIter::new(self)
490    }
491
492    #[cfg(feature = "alloc")]
493    pub fn to_vec(self) -> alloc::vec::Vec<alloc::boxed::Box<T>> {
494        self.iter().map(T::to_boxed).collect()
495    }
496
497    #[inline]
498    fn indices_slice(&self) -> &'a [F::Index] {
499        unsafe { F::Index::slice_from_bytes_unchecked(self.indices) }
500    }
501
502    // Dump a debuggable representation of this type
503    #[allow(unused)] // useful for debugging
504    #[cfg(feature = "alloc")]
505    pub(crate) fn dump(&self) -> alloc::string::String {
506        let indices = self
507            .indices_slice()
508            .iter()
509            .copied()
510            .map(IntegerULE::iule_to_usize)
511            .collect::<alloc::vec::Vec<_>>();
512        alloc::format!("VarZeroVecComponents {{ indices: {indices:?} }}")
513    }
514}
515
516/// An iterator over [`VarZeroSlice`](super::VarZeroSlice)
517#[derive(Debug)]
518pub struct VarZeroSliceIter<'a, T: ?Sized, F = Index16> {
519    components: VarZeroVecComponents<'a, T, F>,
520    index: usize,
521    // Safety invariant: must be a valid index into the data segment of `components`, or an index at the end
522    // i.e. start_index <= components.things.len()
523    //
524    // It must be a valid index into the `things` array of components, coming from `components.indices_slice()`
525    start_index: usize,
526}
527
528impl<'a, T: VarULE + ?Sized, F: VarZeroVecFormat> Clone for VarZeroSliceIter<'a, T, F> {
529    fn clone(&self) -> Self {
530        Self {
531            components: self.components,
532            index: self.index,
533            start_index: self.start_index,
534        }
535    }
536}
537
538impl<'a, T: VarULE + ?Sized, F: VarZeroVecFormat> VarZeroSliceIter<'a, T, F> {
539    fn new(c: VarZeroVecComponents<'a, T, F>) -> Self {
540        Self {
541            components: c,
542            index: 0,
543            // Invariant upheld, 0 is always a valid index-or-end
544            start_index: 0,
545        }
546    }
547}
548impl<'a, T: VarULE + ?Sized, F: VarZeroVecFormat> Iterator for VarZeroSliceIter<'a, T, F> {
549    type Item = &'a T;
550
551    fn next(&mut self) -> Option<Self::Item> {
552        // Note: the indices array doesn't contain 0 or len, we need to specially handle those edges. The 0 is handled
553        // by start_index, and the len is handled by the code for `end`.
554
555        if self.index >= self.components.len() {
556            return None;
557        }
558
559        // Invariant established: self.index is in bounds for self.components.len(),
560        // which means it is in bounds for self.components.indices_slice() since that has the same length
561
562        let end = if self.index + 1 == self.components.len() {
563            // We don't store the end index since it is computable, so the last element should use self.components.things.len()
564            self.components.things.len()
565        } else {
566            // Safety: self.index was known to be in bounds from the bounds check above.
567            unsafe {
568                self.components
569                    .indices_slice()
570                    .get_unchecked(self.index)
571                    .iule_to_usize()
572            }
573        };
574        // Invariant established: end has the same invariant as self.start_index since it comes from indices_slice, which is guaranteed
575        // to only contain valid indexes
576
577        let item = unsafe {
578            // Safety: self.start_index and end both have in-range invariants, plus they are valid indices from indices_slice
579            // which means we can treat this data as a T
580            T::from_bytes_unchecked(self.components.things.get_unchecked(self.start_index..end))
581        };
582        self.index += 1;
583        // Invariant upheld: end has the same invariant as self.start_index
584        self.start_index = end;
585        Some(item)
586    }
587
588    fn size_hint(&self) -> (usize, Option<usize>) {
589        let remainder = self.components.len() - self.index;
590        (remainder, Some(remainder))
591    }
592}
593
594impl<'a, T: VarULE + ?Sized, F: VarZeroVecFormat> ExactSizeIterator for VarZeroSliceIter<'a, T, F> {
595    fn len(&self) -> usize {
596        self.components.len() - self.index
597    }
598}
599
600impl<'a, T, F> VarZeroVecComponents<'a, T, F>
601where
602    T: VarULE,
603    T: ?Sized,
604    T: Ord,
605    F: VarZeroVecFormat,
606{
607    /// Binary searches a sorted `VarZeroVecComponents<T>` for the given element. For more information, see
608    /// the primitive function [`binary_search`](slice::binary_search).
609    pub fn binary_search(&self, needle: &T) -> Result<usize, usize> {
610        self.binary_search_by(|probe| probe.cmp(needle))
611    }
612
613    pub fn binary_search_in_range(
614        &self,
615        needle: &T,
616        range: Range<usize>,
617    ) -> Option<Result<usize, usize>> {
618        self.binary_search_in_range_by(|probe| probe.cmp(needle), range)
619    }
620}
621
622impl<'a, T, F> VarZeroVecComponents<'a, T, F>
623where
624    T: VarULE,
625    T: ?Sized,
626    F: VarZeroVecFormat,
627{
628    /// Binary searches a sorted `VarZeroVecComponents<T>` for the given predicate. For more information, see
629    /// the primitive function [`binary_search_by`](slice::binary_search_by).
630    pub fn binary_search_by(&self, predicate: impl FnMut(&T) -> Ordering) -> Result<usize, usize> {
631        // Safety: 0 and len are in range
632        unsafe { self.binary_search_in_range_unchecked(predicate, 0..self.len()) }
633    }
634
635    // Binary search within a range.
636    // Values returned are relative to the range start!
637    pub fn binary_search_in_range_by(
638        &self,
639        predicate: impl FnMut(&T) -> Ordering,
640        range: Range<usize>,
641    ) -> Option<Result<usize, usize>> {
642        if range.end > self.len() {
643            return None;
644        }
645        if range.end < range.start {
646            return None;
647        }
648        // Safety: We bounds checked above: end is in-bounds or len, and start is <= end
649        let range_absolute =
650            unsafe { self.binary_search_in_range_unchecked(predicate, range.clone()) };
651        // The values returned are relative to the range start
652        Some(
653            range_absolute
654                .map(|o| o - range.start)
655                .map_err(|e| e - range.start),
656        )
657    }
658
659    /// Safety: range must be in range for the slice (start <= len, end <= len, start <= end)
660    unsafe fn binary_search_in_range_unchecked(
661        &self,
662        mut predicate: impl FnMut(&T) -> Ordering,
663        range: Range<usize>,
664    ) -> Result<usize, usize> {
665        // Function invariant: size is always end - start
666        let mut start = range.start;
667        let mut end = range.end;
668        let mut size;
669
670        // Loop invariant: 0 <= start < end <= len
671        // This invariant is initialized by the function safety invariants and the loop condition
672        while start < end {
673            size = end - start;
674            // This establishes mid < end (which implies mid < len)
675            // size is end - start. start + size is end (which is <= len).
676            // mid = start + size/2 will be less than end
677            let mid = start + size / 2;
678
679            // Safety: mid is < end <= len, so in-range
680            let cmp = predicate(self.get_unchecked(mid));
681
682            match cmp {
683                Ordering::Less => {
684                    // This retains the loop invariant since it
685                    // increments start, and we already have 0 <= start
686                    // start < end is enforced by the loop condition
687                    start = mid + 1;
688                }
689                Ordering::Greater => {
690                    // mid < end, so this decreases end.
691                    // This means end <= len is still true, and
692                    // end > start is enforced by the loop condition
693                    end = mid;
694                }
695                Ordering::Equal => return Ok(mid),
696            }
697        }
698        Err(start)
699    }
700}
701
702/// Collects the bytes for a [`VarZeroSlice`](super::VarZeroSlice) into a [`Vec`].
703#[cfg(feature = "alloc")]
704pub fn get_serializable_bytes_non_empty<T, A, F>(elements: &[A]) -> Option<alloc::vec::Vec<u8>>
705where
706    T: VarULE + ?Sized,
707    A: EncodeAsVarULE<T>,
708    F: VarZeroVecFormat,
709{
710    debug_assert!(!elements.is_empty());
711    let len = compute_serializable_len::<T, A, F>(elements)?;
712    debug_assert!(
713        len >= F::Len::SIZE as u32,
714        "Must have at least F::Len::SIZE bytes to hold the length of the vector"
715    );
716    let mut output = alloc::vec![0u8; len as usize];
717    write_serializable_bytes::<T, A, F>(elements, &mut output);
718    Some(output)
719}
720
721/// Writes the bytes for a [`VarZeroLengthlessSlice`](super::lenghtless::VarZeroLengthlessSlice) into an output buffer.
722/// Usable for a [`VarZeroSlice`](super::VarZeroSlice) if you first write the length bytes.
723///
724/// Every byte in the buffer will be initialized after calling this function.
725///
726/// # Panics
727///
728/// Panics if the buffer is not exactly the correct length.
729pub fn write_serializable_bytes_without_length<T, A, F>(elements: &[A], output: &mut [u8])
730where
731    T: VarULE + ?Sized,
732    A: EncodeAsVarULE<T>,
733    F: VarZeroVecFormat,
734{
735    assert!(elements.len() <= F::Len::MAX_VALUE as usize);
736    if elements.is_empty() {
737        return;
738    }
739
740    // idx_offset = offset from the start of the buffer for the next index
741    let mut idx_offset: usize = 0;
742    // first_dat_offset = offset from the start of the buffer of the first data block
743    #[expect(
744        clippy::expect_used,
745        reason = "Function contract allows panicky behavior"
746    )]
747    let indices_size = F::Index::SIZE
748        .checked_mul(elements.len() - 1)
749        .expect(F::Index::TOO_LARGE_ERROR);
750    let first_dat_offset: usize = idx_offset + indices_size;
751    // dat_offset = offset from the start of the buffer of the next data block
752    let mut dat_offset: usize = first_dat_offset;
753
754    for (i, element) in elements.iter().enumerate() {
755        let element_len = element.encode_var_ule_len();
756
757        // The first index is always 0. We don't write it, or update the idx offset.
758        if i != 0 {
759            let idx_limit = idx_offset + F::Index::SIZE;
760            #[expect(clippy::indexing_slicing)] // Function contract allows panicky behavior
761            let idx_slice = &mut output[idx_offset..idx_limit];
762            // VZV expects data offsets to be stored relative to the first data block
763            let idx = dat_offset - first_dat_offset;
764            assert!(idx <= F::Index::MAX_VALUE as usize);
765            #[expect(clippy::expect_used)] // this function is explicitly panicky
766            let bytes_to_write = F::Index::iule_from_usize(idx).expect(F::Index::TOO_LARGE_ERROR);
767            idx_slice.copy_from_slice(ULE::slice_as_bytes(&[bytes_to_write]));
768
769            idx_offset = idx_limit;
770        }
771
772        let dat_limit = dat_offset + element_len;
773        #[expect(
774            clippy::indexing_slicing,
775            reason = "Function contract allows panicky behavior"
776        )]
777        let dat_slice = &mut output[dat_offset..dat_limit];
778        element.encode_var_ule_write(dat_slice);
779        debug_assert_eq!(T::validate_bytes(dat_slice), Ok(()));
780        dat_offset = dat_limit;
781    }
782
783    #[expect(
784        clippy::expect_used,
785        reason = "Function contract allows panicky behavior"
786    )]
787    let indices_size = F::Index::SIZE
788        .checked_mul(elements.len() - 1)
789        .expect(F::Index::TOO_LARGE_ERROR);
790    debug_assert_eq!(idx_offset, indices_size);
791    assert_eq!(dat_offset, output.len());
792}
793
794/// Writes the bytes for a [`VarZeroSlice`](super::VarZeroSlice) into an output buffer.
795///
796/// Every byte in the buffer will be initialized after calling this function.
797///
798/// # Panics
799///
800/// Panics if the buffer is not exactly the correct length.
801pub fn write_serializable_bytes<T, A, F>(elements: &[A], output: &mut [u8])
802where
803    T: VarULE + ?Sized,
804    A: EncodeAsVarULE<T>,
805    F: VarZeroVecFormat,
806{
807    if elements.is_empty() {
808        return;
809    }
810    assert!(elements.len() <= F::Len::MAX_VALUE as usize);
811    #[expect(clippy::expect_used)] // This function is explicitly panicky
812    let num_elements_ule = F::Len::iule_from_usize(elements.len()).expect(F::Len::TOO_LARGE_ERROR);
813    #[expect(clippy::indexing_slicing)] // Function contract allows panicky behavior
814    output[0..F::Len::SIZE].copy_from_slice(ULE::slice_as_bytes(&[num_elements_ule]));
815
816    #[expect(clippy::indexing_slicing)] // Function contract allows panicky behavior
817    write_serializable_bytes_without_length::<T, A, F>(elements, &mut output[F::Len::SIZE..]);
818}
819
820pub fn compute_serializable_len_without_length<T, A, F>(elements: &[A]) -> Option<u32>
821where
822    T: VarULE + ?Sized,
823    A: EncodeAsVarULE<T>,
824    F: VarZeroVecFormat,
825{
826    let elements_len = elements.len();
827    let Some(elements_len_minus_one) = elements_len.checked_sub(1) else {
828        // Empty vec is optimized to an empty byte representation
829        return Some(0);
830    };
831    let idx_len: u32 = u32::try_from(elements_len_minus_one)
832        .ok()?
833        .checked_mul(F::Index::SIZE as u32)?;
834    let data_len: u32 = elements
835        .iter()
836        .map(|v| u32::try_from(v.encode_var_ule_len()).ok())
837        .try_fold(0u32, |s, v| s.checked_add(v?))?;
838    let ret = idx_len.checked_add(data_len);
839    if let Some(r) = ret {
840        if r >= F::Index::MAX_VALUE {
841            return None;
842        }
843    }
844    ret
845}
846
847pub fn compute_serializable_len<T, A, F>(elements: &[A]) -> Option<u32>
848where
849    T: VarULE + ?Sized,
850    A: EncodeAsVarULE<T>,
851    F: VarZeroVecFormat,
852{
853    compute_serializable_len_without_length::<T, A, F>(elements).map(|x| x + F::Len::SIZE as u32)
854}
zerovec/varzerovec/components.rs

zerovec/varzerovec/
components.rs
