diff options
Diffstat (limited to 'vendor/zerovec/src/varzerovec/components.rs')
| -rw-r--r-- | vendor/zerovec/src/varzerovec/components.rs | 578 |
1 files changed, 578 insertions, 0 deletions
diff --git a/vendor/zerovec/src/varzerovec/components.rs b/vendor/zerovec/src/varzerovec/components.rs new file mode 100644 index 000000000..bf70c83c5 --- /dev/null +++ b/vendor/zerovec/src/varzerovec/components.rs @@ -0,0 +1,578 @@ +// This file is part of ICU4X. For terms of use, please see the file +// called LICENSE at the top level of the ICU4X source tree +// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ). + +use crate::ule::*; +use alloc::boxed::Box; +use alloc::format; +use alloc::string::String; +use alloc::vec::Vec; +use core::cmp::Ordering; +use core::convert::TryFrom; +use core::marker::PhantomData; +use core::ops::Range; + +// Also used by owned.rs +pub(super) const LENGTH_WIDTH: usize = 4; +pub(super) const METADATA_WIDTH: usize = 0; +pub(super) const MAX_LENGTH: usize = u32::MAX as usize; +pub(super) const MAX_INDEX: usize = u32::MAX as usize; + +/// This trait allows switching between different possible internal +/// representations of VarZeroVec. +/// +/// Currently this crate supports two formats: [`Index16`] and [`Index32`], +/// with [`Index16`] being the default for all [`VarZeroVec`](super::VarZeroVec) +/// types unless explicitly specified otherwise. +/// +/// Do not implement this trait, its internals may be changed in the future, +/// and all of its associated items are hidden from the docs. +#[allow(clippy::missing_safety_doc)] // no safety section for you, don't implement this trait period +pub unsafe trait VarZeroVecFormat: 'static + Sized { + #[doc(hidden)] + const INDEX_WIDTH: usize; + #[doc(hidden)] + const MAX_VALUE: u32; + /// This is always `RawBytesULE<Self::INDEX_WIDTH>` however + /// Rust does not currently support using associated constants in const + /// generics + #[doc(hidden)] + type RawBytes: ULE; + + // various conversions because RawBytes is an associated constant now + #[doc(hidden)] + fn rawbytes_to_usize(raw: Self::RawBytes) -> usize; + #[doc(hidden)] + fn usize_to_rawbytes(u: usize) -> Self::RawBytes; + + #[doc(hidden)] + fn rawbytes_from_byte_slice_unchecked_mut(bytes: &mut [u8]) -> &mut [Self::RawBytes]; +} + +/// This is a [`VarZeroVecFormat`] that stores u16s in the index array. +/// Will have a smaller data size, but it's more likely for larger arrays +/// to be unrepresentable (and error on construction) +/// +/// This is the default index size used by all [`VarZeroVec`](super::VarZeroVec) tyoes. +#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)] +#[allow(clippy::exhaustive_structs)] // marker +pub struct Index16; + +/// This is a [`VarZeroVecFormat`] that stores u32s in the index array. +/// Will have a larger data size, but will support large arrays without +/// problems. +#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)] +#[allow(clippy::exhaustive_structs)] // marker +pub struct Index32; + +unsafe impl VarZeroVecFormat for Index16 { + const INDEX_WIDTH: usize = 2; + const MAX_VALUE: u32 = u16::MAX as u32; + type RawBytes = RawBytesULE<2>; + #[inline] + fn rawbytes_to_usize(raw: Self::RawBytes) -> usize { + raw.as_unsigned_int() as usize + } + #[inline] + fn usize_to_rawbytes(u: usize) -> Self::RawBytes { + (u as u16).to_unaligned() + } + #[inline] + fn rawbytes_from_byte_slice_unchecked_mut(bytes: &mut [u8]) -> &mut [Self::RawBytes] { + Self::RawBytes::from_byte_slice_unchecked_mut(bytes) + } +} + +unsafe impl VarZeroVecFormat for Index32 { + const INDEX_WIDTH: usize = 4; + const MAX_VALUE: u32 = u32::MAX as u32; + type RawBytes = RawBytesULE<4>; + #[inline] + fn rawbytes_to_usize(raw: Self::RawBytes) -> usize { + raw.as_unsigned_int() as usize + } + #[inline] + fn usize_to_rawbytes(u: usize) -> Self::RawBytes { + (u as u32).to_unaligned() + } + #[inline] + fn rawbytes_from_byte_slice_unchecked_mut(bytes: &mut [u8]) -> &mut [Self::RawBytes] { + Self::RawBytes::from_byte_slice_unchecked_mut(bytes) + } +} + +/// A more parsed version of `VarZeroSlice`. This type is where most of the VarZeroVec +/// internal representation code lies. +/// +/// This is *basically* an `&'a [u8]` to a zero copy buffer, but split out into +/// the buffer components. Logically this is capable of behaving as +/// a `&'a [T::VarULE]`, but since `T::VarULE` is unsized that type does not actually +/// exist. +/// +/// See [`VarZeroVecComponents::parse_byte_slice()`] for information on the internal invariants involved +pub struct VarZeroVecComponents<'a, T: ?Sized, F> { + /// The number of elements + len: u32, + /// The list of indices into the `things` slice + indices: &'a [u8], + /// The contiguous list of `T::VarULE`s + things: &'a [u8], + /// The original slice this was constructed from + entire_slice: &'a [u8], + marker: PhantomData<(&'a T, F)>, +} + +// #[derive()] won't work here since we do not want it to be +// bound on T: Copy +impl<'a, T: ?Sized, F> Copy for VarZeroVecComponents<'a, T, F> {} +impl<'a, T: ?Sized, F> Clone for VarZeroVecComponents<'a, T, F> { + fn clone(&self) -> Self { + VarZeroVecComponents { + len: self.len, + indices: self.indices, + things: self.things, + entire_slice: self.entire_slice, + marker: PhantomData, + } + } +} + +impl<'a, T: VarULE + ?Sized, F> Default for VarZeroVecComponents<'a, T, F> { + #[inline] + fn default() -> Self { + Self::new() + } +} + +impl<'a, T: VarULE + ?Sized, F> VarZeroVecComponents<'a, T, F> { + #[inline] + pub fn new() -> Self { + Self { + len: 0, + indices: &[], + things: &[], + entire_slice: &[], + marker: PhantomData, + } + } +} +impl<'a, T: VarULE + ?Sized, F: VarZeroVecFormat> VarZeroVecComponents<'a, T, F> { + /// Construct a new VarZeroVecComponents, checking invariants about the overall buffer size: + /// + /// - There must be either zero or at least four bytes (if four, this is the "length" parsed as a usize) + /// - There must be at least `4*length + 4` bytes total, to form the the array `indices` of indices + /// - `indices[i]..indices[i+1]` must index into a valid section of + /// `things`, such that it parses to a `T::VarULE` + /// - `indices[len - 1]..things.len()` must index into a valid section of + /// `things`, such that it parses to a `T::VarULE` + #[inline] + pub fn parse_byte_slice(slice: &'a [u8]) -> Result<Self, ZeroVecError> { + if slice.is_empty() { + return Ok(VarZeroVecComponents { + len: 0, + indices: &[], + things: &[], + entire_slice: slice, + marker: PhantomData, + }); + } + let len_bytes = slice + .get(0..LENGTH_WIDTH) + .ok_or(ZeroVecError::VarZeroVecFormatError)?; + let len_ule = RawBytesULE::<LENGTH_WIDTH>::parse_byte_slice(len_bytes) + .map_err(|_| ZeroVecError::VarZeroVecFormatError)?; + + let len = len_ule + .get(0) + .ok_or(ZeroVecError::VarZeroVecFormatError)? + .as_unsigned_int(); + let indices_bytes = slice + .get( + LENGTH_WIDTH + METADATA_WIDTH + ..LENGTH_WIDTH + METADATA_WIDTH + F::INDEX_WIDTH * (len as usize), + ) + .ok_or(ZeroVecError::VarZeroVecFormatError)?; + let things = slice + .get(F::INDEX_WIDTH * (len as usize) + LENGTH_WIDTH + METADATA_WIDTH..) + .ok_or(ZeroVecError::VarZeroVecFormatError)?; + + let borrowed = VarZeroVecComponents { + len: len as u32, + indices: indices_bytes, + things, + entire_slice: slice, + marker: PhantomData, + }; + + borrowed.check_indices_and_things()?; + + Ok(borrowed) + } + + /// Construct a [`VarZeroVecComponents`] from a byte slice that has previously + /// successfully returned a [`VarZeroVecComponents`] when passed to + /// [`VarZeroVecComponents::parse_byte_slice()`]. Will return the same + /// object as one would get from calling [`VarZeroVecComponents::parse_byte_slice()`]. + /// + /// # Safety + /// The bytes must have previously successfully run through + /// [`VarZeroVecComponents::parse_byte_slice()`] + pub unsafe fn from_bytes_unchecked(slice: &'a [u8]) -> Self { + if slice.is_empty() { + return VarZeroVecComponents { + len: 0, + indices: &[], + things: &[], + entire_slice: slice, + marker: PhantomData, + }; + } + let len_bytes = slice.get_unchecked(0..LENGTH_WIDTH); + let len_ule = RawBytesULE::<LENGTH_WIDTH>::from_byte_slice_unchecked(len_bytes); + + let len = len_ule.get_unchecked(0).as_unsigned_int(); + let indices_bytes = slice.get_unchecked( + LENGTH_WIDTH + METADATA_WIDTH + ..LENGTH_WIDTH + METADATA_WIDTH + F::INDEX_WIDTH * (len as usize), + ); + let things = + slice.get_unchecked(LENGTH_WIDTH + METADATA_WIDTH + F::INDEX_WIDTH * (len as usize)..); + + VarZeroVecComponents { + len, + indices: indices_bytes, + things, + entire_slice: slice, + marker: PhantomData, + } + } + + /// Get the number of elements in this vector + #[inline] + pub fn len(self) -> usize { + self.len as usize + } + + /// Returns `true` if the vector contains no elements. + #[inline] + pub fn is_empty(self) -> bool { + self.indices.is_empty() + } + + /// Get the idx'th element out of this slice. Returns `None` if out of bounds. + #[inline] + pub fn get(self, idx: usize) -> Option<&'a T> { + if idx >= self.len() { + return None; + } + Some(unsafe { self.get_unchecked(idx) }) + } + + /// Get the idx'th element out of this slice. Does not bounds check. + /// + /// Safety: + /// - `idx` must be in bounds (`idx < self.len()`) + #[inline] + pub(crate) unsafe fn get_unchecked(self, idx: usize) -> &'a T { + let range = self.get_things_range(idx); + let things_slice = self.things.get_unchecked(range); + T::from_byte_slice_unchecked(things_slice) + } + + /// Get the range in `things` for the element at `idx`. Does not bounds check. + /// + /// Safety: + /// - `idx` must be in bounds (`idx < self.len()`) + #[inline] + unsafe fn get_things_range(self, idx: usize) -> Range<usize> { + let start = F::rawbytes_to_usize(*self.indices_slice().get_unchecked(idx)); + let end = if idx + 1 == self.len() { + self.things.len() + } else { + F::rawbytes_to_usize(*self.indices_slice().get_unchecked(idx + 1)) + }; + debug_assert!(start <= end); + start..end + } + + /// Get the range in `entire_slice` for the element at `idx`. Does not bounds check. + /// + /// Safety: + /// - `idx` must be in bounds (`idx < self.len()`) + #[inline] + pub(crate) unsafe fn get_range(self, idx: usize) -> Range<usize> { + let range = self.get_things_range(idx); + let offset = (self.things as *const [u8] as *const u8) + .offset_from(self.entire_slice as *const [u8] as *const u8) + as usize; + range.start + offset..range.end + offset + } + + /// Check the internal invariants of VarZeroVecComponents: + /// + /// - `indices[i]..indices[i+1]` must index into a valid section of + /// `things`, such that it parses to a `T::VarULE` + /// - `indices[len - 1]..things.len()` must index into a valid section of + /// `things`, such that it parses to a `T::VarULE` + /// - `indices` is monotonically increasing + /// + /// This method is NOT allowed to call any other methods on VarZeroVecComponents since all other methods + /// assume that the slice has been passed through check_indices_and_things + #[inline] + #[allow(clippy::len_zero)] // more explicit to enforce safety invariants + fn check_indices_and_things(self) -> Result<(), ZeroVecError> { + assert_eq!(self.len(), self.indices_slice().len()); + if self.len() == 0 { + if self.things.len() > 0 { + return Err(ZeroVecError::VarZeroVecFormatError); + } else { + return Ok(()); + } + } + // Safety: i is in bounds (assertion above) + let mut start = F::rawbytes_to_usize(unsafe { *self.indices_slice().get_unchecked(0) }); + if start != 0 { + return Err(ZeroVecError::VarZeroVecFormatError); + } + for i in 0..self.len() { + let end = if i == self.len() - 1 { + self.things.len() + } else { + // Safety: i+1 is in bounds (assertion above) + F::rawbytes_to_usize(unsafe { *self.indices_slice().get_unchecked(i + 1) }) + }; + if start > end { + return Err(ZeroVecError::VarZeroVecFormatError); + } + if end > self.things.len() { + return Err(ZeroVecError::VarZeroVecFormatError); + } + // Safety: start..end is a valid range in self.things + let bytes = unsafe { self.things.get_unchecked(start..end) }; + T::parse_byte_slice(bytes)?; + start = end; + } + Ok(()) + } + + /// Create an iterator over the Ts contained in VarZeroVecComponents + #[inline] + pub fn iter(self) -> impl Iterator<Item = &'a T> { + self.indices_slice() + .iter() + .copied() + .map(F::rawbytes_to_usize) + .zip( + self.indices_slice() + .iter() + .copied() + .map(F::rawbytes_to_usize) + .skip(1) + .chain(core::iter::once(self.things.len())), + ) + .map(move |(start, end)| unsafe { self.things.get_unchecked(start..end) }) + .map(|bytes| unsafe { T::from_byte_slice_unchecked(bytes) }) + } + + pub fn to_vec(self) -> Vec<Box<T>> { + self.iter().map(T::to_boxed).collect() + } + + #[inline] + fn indices_slice(&self) -> &'a [F::RawBytes] { + unsafe { F::RawBytes::from_byte_slice_unchecked(self.indices) } + } + + // Dump a debuggable representation of this type + #[allow(unused)] // useful for debugging + pub(crate) fn dump(&self) -> String { + let indices = self + .indices_slice() + .iter() + .copied() + .map(F::rawbytes_to_usize) + .collect::<Vec<_>>(); + format!("VarZeroVecComponents {{ indices: {:?} }}", indices) + } +} + +impl<'a, T, F> VarZeroVecComponents<'a, T, F> +where + T: VarULE, + T: ?Sized, + T: Ord, + F: VarZeroVecFormat, +{ + /// Binary searches a sorted `VarZeroVecComponents<T>` for the given element. For more information, see + /// the primitive function [`binary_search`](slice::binary_search). + pub fn binary_search(&self, needle: &T) -> Result<usize, usize> { + self.binary_search_impl(|probe| probe.cmp(needle), self.indices_slice()) + } + + pub fn binary_search_in_range( + &self, + needle: &T, + range: Range<usize>, + ) -> Option<Result<usize, usize>> { + let indices_slice = self.indices_slice().get(range)?; + Some(self.binary_search_impl(|probe| probe.cmp(needle), indices_slice)) + } +} + +impl<'a, T, F> VarZeroVecComponents<'a, T, F> +where + T: VarULE, + T: ?Sized, + F: VarZeroVecFormat, +{ + /// Binary searches a sorted `VarZeroVecComponents<T>` for the given predicate. For more information, see + /// the primitive function [`binary_search_by`](slice::binary_search_by). + pub fn binary_search_by(&self, predicate: impl FnMut(&T) -> Ordering) -> Result<usize, usize> { + self.binary_search_impl(predicate, self.indices_slice()) + } + + pub fn binary_search_in_range_by( + &self, + predicate: impl FnMut(&T) -> Ordering, + range: Range<usize>, + ) -> Option<Result<usize, usize>> { + let indices_slice = self.indices_slice().get(range)?; + Some(self.binary_search_impl(predicate, indices_slice)) + } + + /// Binary searches a sorted `VarZeroVecComponents<T>` with the given predicate. For more information, see + /// the primitive function [`binary_search`](slice::binary_search). + fn binary_search_impl( + &self, + mut predicate: impl FnMut(&T) -> Ordering, + indices_slice: &[F::RawBytes], + ) -> Result<usize, usize> { + // This code is an absolute atrocity. This code is not a place of honor. This + // code is known to the State of California to cause cancer. + // + // Unfortunately, the stdlib's `binary_search*` functions can only operate on slices. + // We do not have a slice. We have something we can .get() and index on, but that is not + // a slice. + // + // The `binary_search*` functions also do not have a variant where they give you the element's + // index, which we could otherwise use to directly index `self`. + // We do have `self.indices`, but these are indices into a byte buffer, which cannot in + // isolation be used to recoup the logical index of the element they refer to. + // + // However, `binary_search_by()` provides references to the elements of the slice being iterated. + // Since the layout of Rust slices is well-defined, we can do pointer arithmetic on these references + // to obtain the index being used by the search. + // + // It's worth noting that the slice we choose to search is irrelevant, as long as it has the appropriate + // length. `self.indices` is defined to have length `self.len()`, so it is convenient to use + // here and does not require additional allocations. + // + // The alternative to doing this is to implement our own binary search. This is significantly less fun. + + // Note: We always use zero_index relative to the whole indices array, even if we are + // only searching a subslice of it. + let zero_index = self.indices.as_ptr() as *const _ as usize; + indices_slice.binary_search_by(|probe: &_| { + // `self.indices` is a vec of unaligned F::INDEX_WIDTH values, so we divide by F::INDEX_WIDTH + // to get the actual index + let index = (probe as *const _ as usize - zero_index) / F::INDEX_WIDTH; + // safety: we know this is in bounds + let actual_probe = unsafe { self.get_unchecked(index) }; + predicate(actual_probe) + }) + } +} + +/// Collects the bytes for a VarZeroSlice into a Vec. +pub fn get_serializable_bytes<T, A, F>(elements: &[A]) -> Option<Vec<u8>> +where + T: VarULE + ?Sized, + A: EncodeAsVarULE<T>, + F: VarZeroVecFormat, +{ + let len = compute_serializable_len::<T, A, F>(elements)?; + debug_assert!(len >= LENGTH_WIDTH as u32); + let mut output: Vec<u8> = alloc::vec![0; len as usize]; + write_serializable_bytes::<T, A, F>(elements, &mut output); + Some(output) +} + +/// Writes the bytes for a VarZeroSlice into an output buffer. +/// +/// Every byte in the buffer will be initialized after calling this function. +/// +/// # Panics +/// +/// Panics if the buffer is not exactly the correct length. +pub fn write_serializable_bytes<T, A, F>(elements: &[A], output: &mut [u8]) +where + T: VarULE + ?Sized, + A: EncodeAsVarULE<T>, + F: VarZeroVecFormat, +{ + assert!(elements.len() <= MAX_LENGTH); + let num_elements_bytes = elements.len().to_le_bytes(); + #[allow(clippy::indexing_slicing)] // Function contract allows panicky behavior + output[0..LENGTH_WIDTH].copy_from_slice(&num_elements_bytes[0..LENGTH_WIDTH]); + + // idx_offset = offset from the start of the buffer for the next index + let mut idx_offset: usize = LENGTH_WIDTH + METADATA_WIDTH; + // first_dat_offset = offset from the start of the buffer of the first data block + let first_dat_offset: usize = idx_offset + elements.len() * F::INDEX_WIDTH; + // dat_offset = offset from the start of the buffer of the next data block + let mut dat_offset: usize = first_dat_offset; + + for element in elements.iter() { + let element_len = element.encode_var_ule_len(); + + let idx_limit = idx_offset + F::INDEX_WIDTH; + #[allow(clippy::indexing_slicing)] // Function contract allows panicky behavior + let idx_slice = &mut output[idx_offset..idx_limit]; + // VZV expects data offsets to be stored relative to the first data block + let idx = dat_offset - first_dat_offset; + assert!(idx <= MAX_INDEX); + #[allow(clippy::indexing_slicing)] // this function is explicitly panicky + idx_slice.copy_from_slice(&idx.to_le_bytes()[..F::INDEX_WIDTH]); + + let dat_limit = dat_offset + element_len; + #[allow(clippy::indexing_slicing)] // Function contract allows panicky behavior + let dat_slice = &mut output[dat_offset..dat_limit]; + element.encode_var_ule_write(dat_slice); + debug_assert_eq!(T::validate_byte_slice(dat_slice), Ok(())); + + idx_offset = idx_limit; + dat_offset = dat_limit; + } + + debug_assert_eq!( + idx_offset, + LENGTH_WIDTH + METADATA_WIDTH + F::INDEX_WIDTH * elements.len() + ); + assert_eq!(dat_offset, output.len()); +} + +pub fn compute_serializable_len<T, A, F>(elements: &[A]) -> Option<u32> +where + T: VarULE + ?Sized, + A: EncodeAsVarULE<T>, + F: VarZeroVecFormat, +{ + let idx_len: u32 = u32::try_from(elements.len()) + .ok()? + .checked_mul(F::INDEX_WIDTH as u32)? + .checked_add(LENGTH_WIDTH as u32)? + .checked_add(METADATA_WIDTH as u32)?; + let data_len: u32 = elements + .iter() + .map(|v| u32::try_from(v.encode_var_ule_len()).ok()) + .fold(Some(0u32), |s, v| { + s.and_then(|s| v.and_then(|v| s.checked_add(v))) + })?; + let ret = idx_len.checked_add(data_len); + if let Some(r) = ret { + if r >= F::MAX_VALUE { + return None; + } + } + ret +} |