Adding upstream version 124.0.1.upstream/124.0.1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 574 insertions, 0 deletions

diff --git a/third_party/rust/zerovec/src/varzerovec/components.rs b/third_party/rust/zerovec/src/varzerovec/components.rs
new file mode 100644
index 0000000000..9b48a5bd60
--- /dev/null
+++ b/third_party/rust/zerovec/src/varzerovec/components.rs
@@ -0,0 +1,574 @@
+// 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) types.
+#[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;
+    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
+#[derive(Debug)]
+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 {
+        *self
+    }
+}
+
+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 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> {
+        // The empty VZV is special-cased to the empty slice
+        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,
+            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 {
+        // The empty VZV is special-cased to the empty slice
+        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([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_non_empty<T, A, F>(elements: &[A]) -> Option<Vec<u8>>
+where
+    T: VarULE + ?Sized,
+    A: EncodeAsVarULE<T>,
+    F: VarZeroVecFormat,
+{
+    debug_assert!(!elements.is_empty());
+    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())
+        .try_fold(0u32, |s, 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
+}