Merging upstream version 1.67.1+dfsg1.

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

6 files changed, 1586 insertions, 0 deletions

diff --git a/vendor/zerovec/src/flexzerovec/databake.rs b/vendor/zerovec/src/flexzerovec/databake.rs
new file mode 100644
index 000000000..23bf156ef
--- /dev/null
+++ b/vendor/zerovec/src/flexzerovec/databake.rs
@@ -0,0 +1,49 @@
+// 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 super::{FlexZeroSlice, FlexZeroVec};
+use databake::*;
+
+impl Bake for FlexZeroVec<'_> {
+    fn bake(&self, env: &CrateEnv) -> TokenStream {
+        env.insert("zerovec");
+        let bytes = self.as_bytes();
+        quote! { unsafe { ::zerovec::vecs::FlexZeroSlice::from_byte_slice_unchecked(&[#(#bytes),*]).as_flexzerovec() } }
+    }
+}
+
+impl Bake for &FlexZeroSlice {
+    fn bake(&self, env: &CrateEnv) -> TokenStream {
+        env.insert("zerovec");
+        let bytes = self.as_bytes();
+        quote! { unsafe { ::zerovec::vecs::FlexZeroSlice::from_byte_slice_unchecked(&[#(#bytes),*]) } }
+    }
+}
+
+#[test]
+fn test_baked_vec() {
+    test_bake!(
+        FlexZeroVec,
+        const: unsafe {
+            crate::vecs::FlexZeroSlice::from_byte_slice_unchecked(&[
+                2u8, 1u8, 0u8, 22u8, 0u8, 77u8, 1u8, 92u8, 17u8,
+            ])
+            .as_flexzerovec()
+        },
+        zerovec
+    );
+}
+
+#[test]
+fn test_baked_slice() {
+    test_bake!(
+        &FlexZeroSlice,
+        const: unsafe {
+            crate::vecs::FlexZeroSlice::from_byte_slice_unchecked(&[
+                2u8, 1u8, 0u8, 22u8, 0u8, 77u8, 1u8, 92u8, 17u8,
+            ])
+        },
+        zerovec
+    );
+}
diff --git a/vendor/zerovec/src/flexzerovec/mod.rs b/vendor/zerovec/src/flexzerovec/mod.rs
new file mode 100644
index 000000000..b6d7e780a
--- /dev/null
+++ b/vendor/zerovec/src/flexzerovec/mod.rs
@@ -0,0 +1,20 @@
+// 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 ).
+
+//! See [`FlexZeroVec`](crate::vecs::FlexZeroVec) for details.
+
+pub(crate) mod owned;
+pub(crate) mod slice;
+pub(crate) mod vec;
+
+#[cfg(feature = "databake")]
+mod databake;
+
+#[cfg(feature = "serde")]
+mod serde;
+
+pub use owned::FlexZeroVecOwned;
+pub(crate) use slice::chunk_to_usize;
+pub use slice::FlexZeroSlice;
+pub use vec::FlexZeroVec;
diff --git a/vendor/zerovec/src/flexzerovec/owned.rs b/vendor/zerovec/src/flexzerovec/owned.rs
new file mode 100644
index 000000000..1039c59ae
--- /dev/null
+++ b/vendor/zerovec/src/flexzerovec/owned.rs
@@ -0,0 +1,350 @@
+// 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 alloc::vec;
+use alloc::vec::Vec;
+use core::fmt;
+use core::iter::FromIterator;
+use core::ops::Deref;
+
+use super::FlexZeroSlice;
+use super::FlexZeroVec;
+
+/// The fully-owned variant of [`FlexZeroVec`]. Contains all mutation methods.
+// Safety invariant: the inner bytes must deref to a valid `FlexZeroSlice`
+#[derive(Clone, PartialEq, Eq)]
+pub struct FlexZeroVecOwned(Vec<u8>);
+
+impl FlexZeroVecOwned {
+    /// Creates a new [`FlexZeroVecOwned`] with zero elements.
+    pub fn new_empty() -> Self {
+        Self(vec![1])
+    }
+
+    /// Creates a [`FlexZeroVecOwned`] from a [`FlexZeroSlice`].
+    pub fn from_slice(other: &FlexZeroSlice) -> FlexZeroVecOwned {
+        // safety: the bytes originate from a valid FlexZeroSlice
+        Self(other.as_bytes().to_vec())
+    }
+
+    /// Obtains this [`FlexZeroVecOwned`] as a [`FlexZeroSlice`].
+    pub fn as_slice(&self) -> &FlexZeroSlice {
+        let slice: &[u8] = &*self.0;
+        unsafe {
+            // safety: the slice is known to come from a valid parsed FlexZeroSlice
+            FlexZeroSlice::from_byte_slice_unchecked(slice)
+        }
+    }
+
+    /// Mutably obtains this `FlexZeroVecOwned` as a [`FlexZeroSlice`].
+    pub(crate) fn as_mut_slice(&mut self) -> &mut FlexZeroSlice {
+        let slice: &mut [u8] = &mut *self.0;
+        unsafe {
+            // safety: the slice is known to come from a valid parsed FlexZeroSlice
+            FlexZeroSlice::from_byte_slice_mut_unchecked(slice)
+        }
+    }
+
+    /// Converts this `FlexZeroVecOwned` into a [`FlexZeroVec::Owned`].
+    #[inline]
+    pub fn into_flexzerovec(self) -> FlexZeroVec<'static> {
+        FlexZeroVec::Owned(self)
+    }
+
+    /// Clears all values out of this `FlexZeroVecOwned`.
+    #[inline]
+    pub fn clear(&mut self) {
+        *self = Self::new_empty()
+    }
+
+    /// Appends an item to the end of the vector.
+    ///
+    /// # Panics
+    ///
+    /// Panics if inserting the element would require allocating more than `usize::MAX` bytes.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use zerovec::vecs::FlexZeroVec;
+    ///
+    /// let mut zv: FlexZeroVec = [22, 44, 66].iter().copied().collect();
+    /// zv.to_mut().push(33);
+    /// assert_eq!(zv.to_vec(), vec![22, 44, 66, 33]);
+    /// ```
+    pub fn push(&mut self, item: usize) {
+        let insert_info = self.get_insert_info(item);
+        self.0.resize(insert_info.new_bytes_len, 0);
+        let insert_index = insert_info.new_count - 1;
+        self.as_mut_slice().insert_impl(insert_info, insert_index);
+    }
+
+    /// Inserts an element into the middle of the vector.
+    ///
+    /// Caution: Both arguments to this function are of type `usize`. Please be careful to pass
+    /// the index first followed by the value second.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `index > len`.
+    ///
+    /// Panics if inserting the element would require allocating more than `usize::MAX` bytes.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use zerovec::vecs::FlexZeroVec;
+    ///
+    /// let mut zv: FlexZeroVec = [22, 44, 66].iter().copied().collect();
+    /// zv.to_mut().insert(2, 33);
+    /// assert_eq!(zv.to_vec(), vec![22, 44, 33, 66]);
+    /// ```
+    pub fn insert(&mut self, index: usize, item: usize) {
+        #[allow(clippy::panic)] // panic is documented in function contract
+        if index > self.len() {
+            panic!("index {} out of range {}", index, self.len());
+        }
+        let insert_info = self.get_insert_info(item);
+        self.0.resize(insert_info.new_bytes_len, 0);
+        self.as_mut_slice().insert_impl(insert_info, index);
+    }
+
+    /// Inserts an element into an ascending sorted vector
+    /// at a position that keeps the vector sorted.
+    ///
+    /// # Panics
+    ///
+    /// Panics if inserting the element would require allocating more than `usize::MAX` bytes.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use zerovec::vecs::FlexZeroVecOwned;
+    ///
+    /// let mut fzv = FlexZeroVecOwned::new_empty();
+    /// fzv.insert_sorted(10);
+    /// fzv.insert_sorted(5);
+    /// fzv.insert_sorted(8);
+    ///
+    /// assert!(Iterator::eq(fzv.iter(), [5, 8, 10].iter().copied()));
+    /// ```
+    pub fn insert_sorted(&mut self, item: usize) {
+        let index = match self.binary_search(item) {
+            Ok(i) => i,
+            Err(i) => i,
+        };
+        let insert_info = self.get_insert_info(item);
+        self.0.resize(insert_info.new_bytes_len, 0);
+        self.as_mut_slice().insert_impl(insert_info, index);
+    }
+
+    /// Removes and returns the element at the specified index.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `index >= len`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use zerovec::vecs::FlexZeroVec;
+    ///
+    /// let mut zv: FlexZeroVec = [22, 44, 66].iter().copied().collect();
+    /// let removed_item = zv.to_mut().remove(1);
+    /// assert_eq!(44, removed_item);
+    /// assert_eq!(zv.to_vec(), vec![22, 66]);
+    /// ```
+    pub fn remove(&mut self, index: usize) -> usize {
+        #[allow(clippy::panic)] // panic is documented in function contract
+        if index >= self.len() {
+            panic!("index {} out of range {}", index, self.len());
+        }
+        let remove_info = self.get_remove_info(index);
+        // Safety: `remove_index` is a valid index
+        let item = unsafe { self.get_unchecked(remove_info.remove_index) };
+        let new_bytes_len = remove_info.new_bytes_len;
+        self.as_mut_slice().remove_impl(remove_info);
+        self.0.truncate(new_bytes_len);
+        item
+    }
+
+    /// Removes and returns the last element from an ascending sorted vector.
+    ///
+    /// If the vector is not sorted, use [`FlexZeroVecOwned::remove()`] instead. Calling this
+    /// function would leave the FlexZeroVec in a safe, well-defined state; however, information
+    /// may be lost and/or the equality invariant might not hold.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `self.is_empty()`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use zerovec::vecs::FlexZeroVec;
+    ///
+    /// let mut zv: FlexZeroVec = [22, 44, 66].iter().copied().collect();
+    /// let popped_item = zv.to_mut().pop_sorted();
+    /// assert_eq!(66, popped_item);
+    /// assert_eq!(zv.to_vec(), vec![22, 44]);
+    /// ```
+    ///
+    /// Calling this function on a non-ascending vector could cause surprising results:
+    ///
+    /// ```
+    /// use zerovec::vecs::FlexZeroVec;
+    ///
+    /// let mut zv1: FlexZeroVec = [444, 222, 111].iter().copied().collect();
+    /// let popped_item = zv1.to_mut().pop_sorted();
+    /// assert_eq!(111, popped_item);
+    ///
+    /// // Oops!
+    /// assert_eq!(zv1.to_vec(), vec![188, 222]);
+    /// ```
+    pub fn pop_sorted(&mut self) -> usize {
+        #[allow(clippy::panic)] // panic is documented in function contract
+        if self.is_empty() {
+            panic!("cannot pop from an empty vector");
+        }
+        let remove_info = self.get_sorted_pop_info();
+        // Safety: `remove_index` is a valid index
+        let item = unsafe { self.get_unchecked(remove_info.remove_index) };
+        let new_bytes_len = remove_info.new_bytes_len;
+        self.as_mut_slice().remove_impl(remove_info);
+        self.0.truncate(new_bytes_len);
+        item
+    }
+}
+
+impl Deref for FlexZeroVecOwned {
+    type Target = FlexZeroSlice;
+    fn deref(&self) -> &Self::Target {
+        self.as_slice()
+    }
+}
+
+impl fmt::Debug for FlexZeroVecOwned {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "{:?}", self.to_vec())
+    }
+}
+
+impl From<&FlexZeroSlice> for FlexZeroVecOwned {
+    fn from(other: &FlexZeroSlice) -> Self {
+        Self::from_slice(other)
+    }
+}
+
+impl FromIterator<usize> for FlexZeroVecOwned {
+    /// Creates a [`FlexZeroVecOwned`] from an iterator of `usize`.
+    fn from_iter<I>(iter: I) -> Self
+    where
+        I: IntoIterator<Item = usize>,
+    {
+        let mut result = FlexZeroVecOwned::new_empty();
+        for item in iter {
+            result.push(item);
+        }
+        result
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+
+    fn check_contents(fzv: &FlexZeroSlice, expected: &[usize]) {
+        assert_eq!(
+            fzv.len(),
+            expected.len(),
+            "len: {:?} != {:?}",
+            fzv,
+            expected
+        );
+        assert_eq!(
+            fzv.is_empty(),
+            expected.is_empty(),
+            "is_empty: {:?} != {:?}",
+            fzv,
+            expected
+        );
+        assert_eq!(
+            fzv.first(),
+            expected.first().copied(),
+            "first: {:?} != {:?}",
+            fzv,
+            expected
+        );
+        assert_eq!(
+            fzv.last(),
+            expected.last().copied(),
+            "last:  {:?} != {:?}",
+            fzv,
+            expected
+        );
+        for i in 0..(expected.len() + 1) {
+            assert_eq!(
+                fzv.get(i),
+                expected.get(i).copied(),
+                "@{}: {:?} != {:?}",
+                i,
+                fzv,
+                expected
+            );
+        }
+    }
+
+    #[test]
+    fn test_basic() {
+        let mut fzv = FlexZeroVecOwned::new_empty();
+        assert_eq!(fzv.get_width(), 1);
+        check_contents(&fzv, &[]);
+
+        fzv.push(42);
+        assert_eq!(fzv.get_width(), 1);
+        check_contents(&fzv, &[42]);
+
+        fzv.push(77);
+        assert_eq!(fzv.get_width(), 1);
+        check_contents(&fzv, &[42, 77]);
+
+        // Scale up
+        fzv.push(300);
+        assert_eq!(fzv.get_width(), 2);
+        check_contents(&fzv, &[42, 77, 300]);
+
+        // Does not need to be sorted
+        fzv.insert(1, 325);
+        assert_eq!(fzv.get_width(), 2);
+        check_contents(&fzv, &[42, 325, 77, 300]);
+
+        fzv.remove(3);
+        assert_eq!(fzv.get_width(), 2);
+        check_contents(&fzv, &[42, 325, 77]);
+
+        // Scale down
+        fzv.remove(1);
+        assert_eq!(fzv.get_width(), 1);
+        check_contents(&fzv, &[42, 77]);
+    }
+
+    #[test]
+    fn test_build_sorted() {
+        let nums: &[usize] = &[0, 50, 0, 77, 831, 29, 89182, 931, 0, 77, 712381];
+        let mut fzv = FlexZeroVecOwned::new_empty();
+
+        for num in nums {
+            fzv.insert_sorted(*num);
+        }
+        assert_eq!(fzv.get_width(), 3);
+        check_contents(&fzv, &[0, 0, 0, 29, 50, 77, 77, 831, 931, 89182, 712381]);
+
+        for num in nums {
+            let index = fzv.binary_search(*num).unwrap();
+            fzv.remove(index);
+        }
+        assert_eq!(fzv.get_width(), 1);
+        check_contents(&fzv, &[]);
+    }
+}
diff --git a/vendor/zerovec/src/flexzerovec/serde.rs b/vendor/zerovec/src/flexzerovec/serde.rs
new file mode 100644
index 000000000..44179be32
--- /dev/null
+++ b/vendor/zerovec/src/flexzerovec/serde.rs
@@ -0,0 +1,175 @@
+// 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 super::{FlexZeroSlice, FlexZeroVec};
+use alloc::vec::Vec;
+use core::fmt;
+use serde::de::{self, Deserialize, Deserializer, SeqAccess, Visitor};
+#[cfg(feature = "serde")]
+use serde::ser::{Serialize, SerializeSeq, Serializer};
+
+#[derive(Default)]
+struct FlexZeroVecVisitor {}
+
+impl<'de> Visitor<'de> for FlexZeroVecVisitor {
+    type Value = FlexZeroVec<'de>;
+
+    fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
+        formatter.write_str("a sequence or borrowed buffer of bytes")
+    }
+
+    fn visit_borrowed_bytes<E>(self, bytes: &'de [u8]) -> Result<Self::Value, E>
+    where
+        E: de::Error,
+    {
+        FlexZeroVec::parse_byte_slice(bytes).map_err(de::Error::custom)
+    }
+
+    fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
+    where
+        A: SeqAccess<'de>,
+    {
+        let mut vec: Vec<usize> = if let Some(capacity) = seq.size_hint() {
+            Vec::with_capacity(capacity)
+        } else {
+            Vec::new()
+        };
+        while let Some(value) = seq.next_element::<usize>()? {
+            vec.push(value);
+        }
+        Ok(vec.into_iter().collect())
+    }
+}
+
+/// This impl can be made available by enabling the optional `serde` feature of the `zerovec` crate
+impl<'de, 'a> Deserialize<'de> for FlexZeroVec<'a>
+where
+    'de: 'a,
+{
+    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+    where
+        D: Deserializer<'de>,
+    {
+        let visitor = FlexZeroVecVisitor::default();
+        if deserializer.is_human_readable() {
+            deserializer.deserialize_seq(visitor)
+        } else {
+            deserializer.deserialize_bytes(visitor)
+        }
+    }
+}
+
+/// This impl can be made available by enabling the optional `serde` feature of the `zerovec` crate
+impl<'de, 'a> Deserialize<'de> for &'a FlexZeroSlice
+where
+    'de: 'a,
+{
+    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+    where
+        D: Deserializer<'de>,
+    {
+        if deserializer.is_human_readable() {
+            Err(de::Error::custom(
+                "&FlexZeroSlice cannot be deserialized from human-readable formats",
+            ))
+        } else {
+            let deserialized: FlexZeroVec<'a> = FlexZeroVec::deserialize(deserializer)?;
+            let borrowed = if let FlexZeroVec::Borrowed(b) = deserialized {
+                b
+            } else {
+                return Err(de::Error::custom(
+                    "&FlexZeroSlice can only deserialize in zero-copy ways",
+                ));
+            };
+            Ok(borrowed)
+        }
+    }
+}
+
+/// This impl can be made available by enabling the optional `serde` feature of the `zerovec` crate
+impl Serialize for FlexZeroVec<'_> {
+    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+    where
+        S: Serializer,
+    {
+        if serializer.is_human_readable() {
+            let mut seq = serializer.serialize_seq(Some(self.len()))?;
+            for value in self.iter() {
+                seq.serialize_element(&value)?;
+            }
+            seq.end()
+        } else {
+            serializer.serialize_bytes(self.as_bytes())
+        }
+    }
+}
+
+/// This impl can be made available by enabling the optional `serde` feature of the `zerovec` crate
+impl Serialize for FlexZeroSlice {
+    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+    where
+        S: Serializer,
+    {
+        self.as_flexzerovec().serialize(serializer)
+    }
+}
+
+#[cfg(test)]
+#[allow(non_camel_case_types)]
+mod test {
+    use super::{FlexZeroSlice, FlexZeroVec};
+
+    #[derive(serde::Serialize, serde::Deserialize)]
+    struct DeriveTest_FlexZeroVec<'data> {
+        #[serde(borrow)]
+        _data: FlexZeroVec<'data>,
+    }
+
+    #[derive(serde::Serialize, serde::Deserialize)]
+    struct DeriveTest_FlexZeroSlice<'data> {
+        #[serde(borrow)]
+        _data: &'data FlexZeroSlice,
+    }
+
+    // [1, 22, 333, 4444];
+    const BYTES: &[u8] = &[2, 0x01, 0x00, 0x16, 0x00, 0x4D, 0x01, 0x5C, 0x11];
+    const JSON_STR: &str = "[1,22,333,4444]";
+    const BINCODE_BUF: &[u8] = &[9, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 22, 0, 77, 1, 92, 17];
+
+    #[test]
+    fn test_serde_json() {
+        let zerovec_orig: FlexZeroVec = FlexZeroVec::parse_byte_slice(BYTES).expect("parse");
+        let json_str = serde_json::to_string(&zerovec_orig).expect("serialize");
+        assert_eq!(JSON_STR, json_str);
+        // FlexZeroVec should deserialize from JSON to either Vec or FlexZeroVec
+        let vec_new: Vec<usize> =
+            serde_json::from_str(&json_str).expect("deserialize from buffer to Vec");
+        assert_eq!(zerovec_orig.to_vec(), vec_new);
+        let zerovec_new: FlexZeroVec =
+            serde_json::from_str(&json_str).expect("deserialize from buffer to FlexZeroVec");
+        assert_eq!(zerovec_orig.to_vec(), zerovec_new.to_vec());
+        assert!(matches!(zerovec_new, FlexZeroVec::Owned(_)));
+    }
+
+    #[test]
+    fn test_serde_bincode() {
+        let zerovec_orig: FlexZeroVec = FlexZeroVec::parse_byte_slice(BYTES).expect("parse");
+        let bincode_buf = bincode::serialize(&zerovec_orig).expect("serialize");
+        assert_eq!(BINCODE_BUF, bincode_buf);
+        let zerovec_new: FlexZeroVec =
+            bincode::deserialize(&bincode_buf).expect("deserialize from buffer to FlexZeroVec");
+        assert_eq!(zerovec_orig.to_vec(), zerovec_new.to_vec());
+        assert!(matches!(zerovec_new, FlexZeroVec::Borrowed(_)));
+    }
+
+    #[test]
+    fn test_vzv_borrowed() {
+        let zerovec_orig: &FlexZeroSlice = FlexZeroSlice::parse_byte_slice(BYTES).expect("parse");
+        let bincode_buf = bincode::serialize(&zerovec_orig).expect("serialize");
+        assert_eq!(BINCODE_BUF, bincode_buf);
+        let zerovec_new: &FlexZeroSlice =
+            bincode::deserialize(&bincode_buf).expect("deserialize from buffer to FlexZeroSlice");
+        assert_eq!(zerovec_orig.to_vec(), zerovec_new.to_vec());
+    }
+}
diff --git a/vendor/zerovec/src/flexzerovec/slice.rs b/vendor/zerovec/src/flexzerovec/slice.rs
new file mode 100644
index 000000000..7cc6f12fa
--- /dev/null
+++ b/vendor/zerovec/src/flexzerovec/slice.rs
@@ -0,0 +1,717 @@
+// 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 super::FlexZeroVec;
+use crate::ZeroVecError;
+use alloc::vec::Vec;
+use core::cmp::Ordering;
+use core::fmt;
+use core::mem;
+use core::ops::Range;
+
+const USIZE_WIDTH: usize = mem::size_of::<usize>();
+
+/// A zero-copy "slice" that efficiently represents `[usize]`.
+#[repr(packed)]
+#[derive(Eq, PartialEq)]
+pub struct FlexZeroSlice {
+    // Hard Invariant: 1 <= width <= USIZE_WIDTH (which is target_pointer_width)
+    // Soft Invariant: width == the width of the largest element
+    width: u8,
+    // Hard Invariant: data.len() % width == 0
+    data: [u8],
+}
+
+/// Helper function to decode a little-endian "chunk" (byte slice of a specific length)
+/// into a `usize`. We cannot call `usize::from_le_bytes` directly because that function
+/// requires the high bits to be set to 0.
+#[inline]
+pub(crate) fn chunk_to_usize(chunk: &[u8], width: usize) -> usize {
+    debug_assert_eq!(chunk.len(), width);
+    let mut bytes = [0; USIZE_WIDTH];
+    #[allow(clippy::indexing_slicing)] // protected by debug_assert above
+    bytes[0..width].copy_from_slice(chunk);
+    usize::from_le_bytes(bytes)
+}
+
+impl FlexZeroSlice {
+    /// Constructs a new empty [`FlexZeroSlice`].
+    ///
+    /// ```
+    /// use zerovec::vecs::FlexZeroSlice;
+    ///
+    /// const EMPTY_SLICE: &FlexZeroSlice = FlexZeroSlice::new_empty();
+    ///
+    /// assert!(EMPTY_SLICE.is_empty());
+    /// assert_eq!(EMPTY_SLICE.len(), 0);
+    /// assert_eq!(EMPTY_SLICE.first(), None);
+    /// ```
+    #[inline]
+    pub const fn new_empty() -> &'static Self {
+        const ARR: &[u8] = &[1u8];
+        // Safety: The slice is a valid empty `FlexZeroSlice`
+        unsafe { Self::from_byte_slice_unchecked(ARR) }
+    }
+
+    /// Safely constructs a [`FlexZeroSlice`] from a byte array.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use zerovec::vecs::FlexZeroSlice;
+    ///
+    /// const FZS: &FlexZeroSlice = match FlexZeroSlice::parse_byte_slice(&[
+    ///     2, // width
+    ///     0x42, 0x00, // first value
+    ///     0x07, 0x09, // second value
+    ///     0xFF, 0xFF, // third value
+    /// ]) {
+    ///     Ok(v) => v,
+    ///     Err(_) => panic!("invalid bytes"),
+    /// };
+    ///
+    /// assert!(!FZS.is_empty());
+    /// assert_eq!(FZS.len(), 3);
+    /// assert_eq!(FZS.first(), Some(0x0042));
+    /// assert_eq!(FZS.get(0), Some(0x0042));
+    /// assert_eq!(FZS.get(1), Some(0x0907));
+    /// assert_eq!(FZS.get(2), Some(0xFFFF));
+    /// assert_eq!(FZS.get(3), None);
+    /// assert_eq!(FZS.last(), Some(0xFFFF));
+    /// ```
+    pub const fn parse_byte_slice(bytes: &[u8]) -> Result<&Self, ZeroVecError> {
+        let (width_u8, data) = match bytes.split_first() {
+            Some(v) => v,
+            None => {
+                return Err(ZeroVecError::InvalidLength {
+                    ty: "FlexZeroSlice",
+                    len: 0,
+                })
+            }
+        };
+        let width = *width_u8 as usize;
+        if width < 1 || width > USIZE_WIDTH {
+            return Err(ZeroVecError::ParseError {
+                ty: "FlexZeroSlice",
+            });
+        }
+        if data.len() % width != 0 {
+            return Err(ZeroVecError::InvalidLength {
+                ty: "FlexZeroSlice",
+                len: bytes.len(),
+            });
+        }
+        // Safety: All hard invariants have been checked.
+        // Note: The soft invariant requires a linear search that we don't do here.
+        Ok(unsafe { Self::from_byte_slice_unchecked(bytes) })
+    }
+
+    /// Constructs a [`FlexZeroSlice`] without checking invariants.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `bytes` is empty.
+    ///
+    /// # Safety
+    ///
+    /// Must be called on a valid [`FlexZeroSlice`] byte array.
+    #[inline]
+    pub const unsafe fn from_byte_slice_unchecked(bytes: &[u8]) -> &Self {
+        // Safety: The DST of FlexZeroSlice is a pointer to the `width` element and has a metadata
+        // equal to the length of the `data` field, which will be one less than the length of the
+        // overall array.
+        #[allow(clippy::panic)] // panic is documented in function contract
+        let (_, remainder) = match bytes.split_last() {
+            Some(v) => v,
+            None => panic!("slice should be non-empty"),
+        };
+        &*(remainder as *const [u8] as *const Self)
+    }
+
+    #[inline]
+    pub(crate) unsafe fn from_byte_slice_mut_unchecked(bytes: &mut [u8]) -> &mut Self {
+        // Safety: See comments in `from_byte_slice_unchecked`
+        let remainder = core::slice::from_raw_parts_mut(bytes.as_mut_ptr(), bytes.len() - 1);
+        &mut *(remainder as *mut [u8] as *mut Self)
+    }
+
+    /// Returns this slice as its underlying `&[u8]` byte buffer representation.
+    ///
+    /// Useful for serialization.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use zerovec::vecs::FlexZeroSlice;
+    ///
+    /// let bytes: &[u8] = &[2, 0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x80];
+    /// let fzv = FlexZeroSlice::parse_byte_slice(bytes).expect("valid bytes");
+    ///
+    /// assert_eq!(bytes, fzv.as_bytes());
+    /// ```
+    #[inline]
+    pub fn as_bytes(&self) -> &[u8] {
+        // Safety: See comments in `from_byte_slice_unchecked`
+        unsafe {
+            core::slice::from_raw_parts(self as *const Self as *const u8, self.data.len() + 1)
+        }
+    }
+
+    /// Borrows this `FlexZeroSlice` as a [`FlexZeroVec::Borrowed`].
+    #[inline]
+    pub const fn as_flexzerovec(&self) -> FlexZeroVec {
+        FlexZeroVec::Borrowed(self)
+    }
+
+    /// Returns the number of elements in the `FlexZeroSlice`.
+    #[inline]
+    pub fn len(&self) -> usize {
+        self.data.len() / self.get_width()
+    }
+
+    #[inline]
+    pub(crate) fn get_width(&self) -> usize {
+        usize::from(self.width)
+    }
+
+    /// Returns whether there are zero elements in the `FlexZeroSlice`.
+    #[inline]
+    pub fn is_empty(&self) -> bool {
+        self.data.len() == 0
+    }
+
+    /// Gets the element at `index`, or `None` if `index >= self.len()`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use zerovec::vecs::FlexZeroVec;
+    ///
+    /// let fzv: FlexZeroVec = [22, 33].iter().copied().collect();
+    /// assert_eq!(fzv.get(0), Some(22));
+    /// assert_eq!(fzv.get(1), Some(33));
+    /// assert_eq!(fzv.get(2), None);
+    /// ```
+    #[inline]
+    pub fn get(&self, index: usize) -> Option<usize> {
+        if index >= self.len() {
+            None
+        } else {
+            Some(unsafe { self.get_unchecked(index) })
+        }
+    }
+
+    /// Gets the element at `index` as a chunk of bytes, or `None` if `index >= self.len()`.
+    #[inline]
+    pub(crate) fn get_chunk(&self, index: usize) -> Option<&[u8]> {
+        let w = self.get_width();
+        self.data.get(index * w..index * w + w)
+    }
+
+    /// Gets the element at `index` without checking bounds.
+    ///
+    /// # Safety
+    ///
+    /// `index` must be in-range.
+    #[inline]
+    pub unsafe fn get_unchecked(&self, index: usize) -> usize {
+        match self.width {
+            1 => *self.data.get_unchecked(index) as usize,
+            2 => {
+                let ptr = self.data.as_ptr().add(index * 2);
+                u16::from_le_bytes(core::ptr::read(ptr as *const [u8; 2])) as usize
+            }
+            _ => {
+                let mut bytes = [0; USIZE_WIDTH];
+                let w = self.get_width();
+                assert!(w <= USIZE_WIDTH);
+                let ptr = self.data.as_ptr().add(index * w);
+                core::ptr::copy_nonoverlapping(ptr, bytes.as_mut_ptr(), w);
+                usize::from_le_bytes(bytes)
+            }
+        }
+    }
+
+    /// Gets the first element of the slice, or `None` if the slice is empty.
+    #[inline]
+    pub fn first(&self) -> Option<usize> {
+        let w = self.get_width();
+        self.data.get(0..w).map(|chunk| chunk_to_usize(chunk, w))
+    }
+
+    /// Gets the last element of the slice, or `None` if the slice is empty.
+    #[inline]
+    pub fn last(&self) -> Option<usize> {
+        let l = self.data.len();
+        if l == 0 {
+            None
+        } else {
+            let w = self.get_width();
+            self.data
+                .get(l - w..l)
+                .map(|chunk| chunk_to_usize(chunk, w))
+        }
+    }
+
+    /// Gets an iterator over the elements of the slice as `usize`.
+    #[inline]
+    pub fn iter(
+        &self,
+    ) -> impl DoubleEndedIterator<Item = usize> + '_ + ExactSizeIterator<Item = usize> {
+        let w = self.get_width();
+        self.data
+            .chunks_exact(w)
+            .map(move |chunk| chunk_to_usize(chunk, w))
+    }
+
+    /// Gets an iterator over pairs of elements.
+    ///
+    /// The second element of the final pair is `None`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use zerovec::vecs::FlexZeroVec;
+    ///
+    /// let nums: &[usize] = &[211, 281, 421, 461];
+    /// let fzv: FlexZeroVec = nums.iter().copied().collect();
+    ///
+    /// let mut pairs_it = fzv.iter_pairs();
+    ///
+    /// assert_eq!(pairs_it.next(), Some((211, Some(281))));
+    /// assert_eq!(pairs_it.next(), Some((281, Some(421))));
+    /// assert_eq!(pairs_it.next(), Some((421, Some(461))));
+    /// assert_eq!(pairs_it.next(), Some((461, None)));
+    /// assert_eq!(pairs_it.next(), None);
+    /// ```
+    pub fn iter_pairs(&self) -> impl Iterator<Item = (usize, Option<usize>)> + '_ {
+        self.iter()
+            .zip(self.iter().skip(1).map(Some).chain(core::iter::once(None)))
+    }
+
+    /// Creates a `Vec<usize>` from a [`FlexZeroSlice`] (or `FlexZeroVec`).
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use zerovec::vecs::FlexZeroVec;
+    ///
+    /// let nums: &[usize] = &[211, 281, 421, 461];
+    /// let fzv: FlexZeroVec = nums.iter().copied().collect();
+    /// let vec: Vec<usize> = fzv.to_vec();
+    ///
+    /// assert_eq!(nums, vec.as_slice());
+    /// ```
+    #[inline]
+    pub fn to_vec(&self) -> Vec<usize> {
+        self.iter().collect()
+    }
+
+    /// Binary searches a sorted `FlexZeroSlice` for the given `usize` value.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use zerovec::vecs::FlexZeroVec;
+    ///
+    /// let nums: &[usize] = &[211, 281, 421, 461];
+    /// let fzv: FlexZeroVec = nums.iter().copied().collect();
+    ///
+    /// assert_eq!(fzv.binary_search(0), Err(0));
+    /// assert_eq!(fzv.binary_search(211), Ok(0));
+    /// assert_eq!(fzv.binary_search(250), Err(1));
+    /// assert_eq!(fzv.binary_search(281), Ok(1));
+    /// assert_eq!(fzv.binary_search(300), Err(2));
+    /// assert_eq!(fzv.binary_search(421), Ok(2));
+    /// assert_eq!(fzv.binary_search(450), Err(3));
+    /// assert_eq!(fzv.binary_search(461), Ok(3));
+    /// assert_eq!(fzv.binary_search(462), Err(4));
+    /// ```
+    #[inline]
+    pub fn binary_search(&self, needle: usize) -> Result<usize, usize> {
+        self.binary_search_by(|probe| probe.cmp(&needle))
+    }
+
+    /// Binary searches a sorted range of a `FlexZeroSlice` for the given `usize` value.
+    ///
+    /// The indices in the return value are relative to the start of the range.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use zerovec::vecs::FlexZeroVec;
+    ///
+    /// // Make a FlexZeroVec with two sorted ranges: 0..3 and 3..5
+    /// let nums: &[usize] = &[111, 222, 444, 333, 555];
+    /// let fzv: FlexZeroVec = nums.iter().copied().collect();
+    ///
+    /// // Search in the first range:
+    /// assert_eq!(fzv.binary_search_in_range(0, 0..3), Some(Err(0)));
+    /// assert_eq!(fzv.binary_search_in_range(111, 0..3), Some(Ok(0)));
+    /// assert_eq!(fzv.binary_search_in_range(199, 0..3), Some(Err(1)));
+    /// assert_eq!(fzv.binary_search_in_range(222, 0..3), Some(Ok(1)));
+    /// assert_eq!(fzv.binary_search_in_range(399, 0..3), Some(Err(2)));
+    /// assert_eq!(fzv.binary_search_in_range(444, 0..3), Some(Ok(2)));
+    /// assert_eq!(fzv.binary_search_in_range(999, 0..3), Some(Err(3)));
+    ///
+    /// // Search in the second range:
+    /// assert_eq!(fzv.binary_search_in_range(0, 3..5), Some(Err(0)));
+    /// assert_eq!(fzv.binary_search_in_range(333, 3..5), Some(Ok(0)));
+    /// assert_eq!(fzv.binary_search_in_range(399, 3..5), Some(Err(1)));
+    /// assert_eq!(fzv.binary_search_in_range(555, 3..5), Some(Ok(1)));
+    /// assert_eq!(fzv.binary_search_in_range(999, 3..5), Some(Err(2)));
+    ///
+    /// // Out-of-bounds range:
+    /// assert_eq!(fzv.binary_search_in_range(0, 4..6), None);
+    /// ```
+    #[inline]
+    pub fn binary_search_in_range(
+        &self,
+        needle: usize,
+        range: Range<usize>,
+    ) -> Option<Result<usize, usize>> {
+        self.binary_search_in_range_by(|probe| probe.cmp(&needle), range)
+    }
+
+    /// Binary searches a sorted `FlexZeroSlice` according to a predicate function.
+    #[inline]
+    pub fn binary_search_by(
+        &self,
+        predicate: impl FnMut(usize) -> Ordering,
+    ) -> Result<usize, usize> {
+        debug_assert!(self.len() <= self.data.len());
+        // Safety: self.len() <= self.data.len()
+        let scaled_slice = unsafe { self.data.get_unchecked(0..self.len()) };
+        self.binary_search_impl(predicate, scaled_slice)
+    }
+
+    /// Binary searches a sorted range of a `FlexZeroSlice` according to a predicate function.
+    ///
+    /// The indices in the return value are relative to the start of the range.
+    #[inline]
+    pub fn binary_search_in_range_by(
+        &self,
+        predicate: impl FnMut(usize) -> Ordering,
+        range: Range<usize>,
+    ) -> Option<Result<usize, usize>> {
+        // Note: We need to check bounds separately, since `self.data.get(range)` does not return
+        // bounds errors, since it is indexing directly into the upscaled data array
+        if range.start > self.len() || range.end > self.len() {
+            return None;
+        }
+        let scaled_slice = self.data.get(range)?;
+        Some(self.binary_search_impl(predicate, scaled_slice))
+    }
+
+    /// Binary searches a `FlexZeroSlice` by its indices.
+    ///
+    /// The `predicate` function is passed in-bounds indices into the `FlexZeroSlice`.
+    #[inline]
+    pub fn binary_search_with_index(
+        &self,
+        predicate: impl FnMut(usize) -> Ordering,
+    ) -> Result<usize, usize> {
+        debug_assert!(self.len() <= self.data.len());
+        // Safety: self.len() <= self.data.len()
+        let scaled_slice = unsafe { self.data.get_unchecked(0..self.len()) };
+        self.binary_search_with_index_impl(predicate, scaled_slice)
+    }
+
+    /// Binary searches a range of a `FlexZeroSlice` by its indices.
+    ///
+    /// The `predicate` function is passed in-bounds indices into the `FlexZeroSlice`, which are
+    /// relative to the start of the entire slice.
+    ///
+    /// The indices in the return value are relative to the start of the range.
+    #[inline]
+    pub fn binary_search_in_range_with_index(
+        &self,
+        predicate: impl FnMut(usize) -> Ordering,
+        range: Range<usize>,
+    ) -> Option<Result<usize, usize>> {
+        // Note: We need to check bounds separately, since `self.data.get(range)` does not return
+        // bounds errors, since it is indexing directly into the upscaled data array
+        if range.start > self.len() || range.end > self.len() {
+            return None;
+        }
+        let scaled_slice = self.data.get(range)?;
+        Some(self.binary_search_with_index_impl(predicate, scaled_slice))
+    }
+
+    /// # Safety
+    ///
+    /// `scaled_slice` must be a subslice of `self.data`
+    #[inline]
+    fn binary_search_impl(
+        &self,
+        mut predicate: impl FnMut(usize) -> Ordering,
+        scaled_slice: &[u8],
+    ) -> Result<usize, usize> {
+        self.binary_search_with_index_impl(
+            |index| {
+                // Safety: The contract of `binary_search_with_index_impl` says `index` is in bounds
+                let actual_probe = unsafe { self.get_unchecked(index) };
+                predicate(actual_probe)
+            },
+            scaled_slice,
+        )
+    }
+
+    /// `predicate` is passed a valid index as an argument.
+    ///
+    /// # Safety
+    ///
+    /// `scaled_slice` must be a subslice of `self.data`
+    fn binary_search_with_index_impl(
+        &self,
+        mut predicate: impl FnMut(usize) -> Ordering,
+        scaled_slice: &[u8],
+    ) -> 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.data.as_ptr() as *const _ as usize;
+        scaled_slice.binary_search_by(|probe: &_| {
+            // Note: `scaled_slice` is a slice of u8
+            let index = probe as *const _ as usize - zero_index;
+            predicate(index)
+        })
+    }
+}
+
+impl fmt::Debug for &FlexZeroSlice {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "{:?}", self.to_vec())
+    }
+}
+
+#[inline]
+pub(crate) fn get_item_width(item_bytes: &[u8; USIZE_WIDTH]) -> usize {
+    USIZE_WIDTH - item_bytes.iter().rev().take_while(|b| **b == 0).count()
+}
+
+/// Pre-computed information about a pending insertion operation.
+///
+/// Do not create one of these directly; call `get_insert_info()`.
+pub(crate) struct InsertInfo {
+    /// The bytes to be inserted, with zero-fill.
+    pub item_bytes: [u8; USIZE_WIDTH],
+    /// The new item width after insertion.
+    pub new_width: usize,
+    /// The new number of items in the vector: self.len() after insertion.
+    pub new_count: usize,
+    /// The new number of bytes required for the entire slice (self.data.len() + 1).
+    pub new_bytes_len: usize,
+}
+
+impl FlexZeroSlice {
+    /// Compute the [`InsertInfo`] for inserting the specified item anywhere into the vector.
+    ///
+    /// # Panics
+    ///
+    /// Panics if inserting the element would require allocating more than `usize::MAX` bytes.
+    pub(crate) fn get_insert_info(&self, new_item: usize) -> InsertInfo {
+        let item_bytes = new_item.to_le_bytes();
+        let item_width = get_item_width(&item_bytes);
+        let old_width = self.get_width();
+        let new_width = core::cmp::max(old_width, item_width);
+        let new_count = 1 + (self.data.len() / old_width);
+        #[allow(clippy::unwrap_used)] // panic is documented in function contract
+        let new_bytes_len = new_count
+            .checked_mul(new_width)
+            .unwrap()
+            .checked_add(1)
+            .unwrap();
+        InsertInfo {
+            item_bytes,
+            new_width,
+            new_count,
+            new_bytes_len,
+        }
+    }
+
+    /// This function should be called on a slice with a data array `new_data_len` long
+    /// which previously held `new_count - 1` elements.
+    ///
+    /// After calling this function, all bytes in the slice will have been written.
+    pub(crate) fn insert_impl(&mut self, insert_info: InsertInfo, insert_index: usize) {
+        let InsertInfo {
+            item_bytes,
+            new_width,
+            new_count,
+            new_bytes_len,
+        } = insert_info;
+        debug_assert!(new_width <= USIZE_WIDTH);
+        debug_assert!(new_width >= self.get_width());
+        debug_assert!(insert_index < new_count);
+        debug_assert_eq!(new_bytes_len, new_count * new_width + 1);
+        debug_assert_eq!(new_bytes_len, self.data.len() + 1);
+        // For efficiency, calculate how many items we can skip copying.
+        let lower_i = if new_width == self.get_width() {
+            insert_index
+        } else {
+            0
+        };
+        // Copy elements starting from the end into the new empty section of the vector.
+        // Note: We could copy fully in place, but we need to set 0 bytes for the high bytes,
+        // so we stage the new value on the stack.
+        for i in (lower_i..new_count).rev() {
+            let bytes_to_write = if i == insert_index {
+                item_bytes
+            } else {
+                let j = if i > insert_index { i - 1 } else { i };
+                debug_assert!(j < new_count - 1);
+                // Safety: j is in range (assertion on previous line), and it has not been
+                // overwritten yet since we are walking backwards.
+                unsafe { self.get_unchecked(j).to_le_bytes() }
+            };
+            // Safety: The vector has capacity for `new_width` items at the new index, which is
+            // later in the array than the bytes that we read above.
+            unsafe {
+                core::ptr::copy_nonoverlapping(
+                    bytes_to_write.as_ptr(),
+                    self.data.as_mut_ptr().add(new_width * i),
+                    new_width,
+                );
+            }
+        }
+        self.width = new_width as u8;
+    }
+}
+
+/// Pre-computed information about a pending removal operation.
+///
+/// Do not create one of these directly; call `get_remove_info()` or `get_sorted_pop_info()`.
+pub(crate) struct RemoveInfo {
+    /// The index of the item to be removed.
+    pub remove_index: usize,
+    /// The new item width after insertion.
+    pub new_width: usize,
+    /// The new number of items in the vector: self.len() after insertion.
+    pub new_count: usize,
+    /// The new number of bytes required for the entire slice (self.data.len() + 1).
+    pub new_bytes_len: usize,
+}
+
+impl FlexZeroSlice {
+    /// Compute the [`RemoveInfo`] for removing the item at the specified index.
+    pub(crate) fn get_remove_info(&self, remove_index: usize) -> RemoveInfo {
+        debug_assert!(remove_index < self.len());
+        // Safety: remove_index is in range (assertion on previous line)
+        let item_bytes = unsafe { self.get_unchecked(remove_index).to_le_bytes() };
+        let item_width = get_item_width(&item_bytes);
+        let old_width = self.get_width();
+        let old_count = self.data.len() / old_width;
+        let new_width = if item_width < old_width {
+            old_width
+        } else {
+            debug_assert_eq!(old_width, item_width);
+            // We might be removing the widest element. If so, we need to scale down.
+            let mut largest_width = 1;
+            for i in 0..old_count {
+                if i == remove_index {
+                    continue;
+                }
+                // Safety: i is in range (between 0 and old_count)
+                let curr_bytes = unsafe { self.get_unchecked(i).to_le_bytes() };
+                let curr_width = get_item_width(&curr_bytes);
+                largest_width = core::cmp::max(curr_width, largest_width);
+            }
+            largest_width
+        };
+        let new_count = old_count - 1;
+        // Note: the following line won't overflow because we are making the slice shorter.
+        let new_bytes_len = new_count * new_width + 1;
+        RemoveInfo {
+            remove_index,
+            new_width,
+            new_count,
+            new_bytes_len,
+        }
+    }
+
+    /// Returns the [`RemoveInfo`] for removing the last element. Should be called
+    /// on a slice sorted in ascending order.
+    ///
+    /// This is more efficient than `get_remove_info()` because it doesn't require a
+    /// linear traversal of the vector in order to calculate `new_width`.
+    pub(crate) fn get_sorted_pop_info(&self) -> RemoveInfo {
+        debug_assert!(!self.is_empty());
+        let remove_index = self.len() - 1;
+        let old_count = self.len();
+        let new_width = if old_count == 1 {
+            1
+        } else {
+            // Safety: the FlexZeroSlice has at least two elements
+            let largest_item = unsafe { self.get_unchecked(remove_index - 1).to_le_bytes() };
+            get_item_width(&largest_item)
+        };
+        let new_count = old_count - 1;
+        // Note: the following line won't overflow because we are making the slice shorter.
+        let new_bytes_len = new_count * new_width + 1;
+        RemoveInfo {
+            remove_index,
+            new_width,
+            new_count,
+            new_bytes_len,
+        }
+    }
+
+    /// This function should be called on a valid slice.
+    ///
+    /// After calling this function, the slice data should be truncated to `new_data_len` bytes.
+    pub(crate) fn remove_impl(&mut self, remove_info: RemoveInfo) {
+        let RemoveInfo {
+            remove_index,
+            new_width,
+            new_count,
+            ..
+        } = remove_info;
+        debug_assert!(new_width <= self.get_width());
+        debug_assert!(new_count < self.len());
+        // For efficiency, calculate how many items we can skip copying.
+        let lower_i = if new_width == self.get_width() {
+            remove_index
+        } else {
+            0
+        };
+        // Copy elements starting from the beginning to compress the vector to fewer bytes.
+        for i in lower_i..new_count {
+            let j = if i < remove_index { i } else { i + 1 };
+            // Safety: j is in range because j <= new_count < self.len()
+            let bytes_to_write = unsafe { self.get_unchecked(j).to_le_bytes() };
+            // Safety: The bytes are being copied to a section of the array that is not after
+            // the section of the array that currently holds the bytes.
+            unsafe {
+                core::ptr::copy_nonoverlapping(
+                    bytes_to_write.as_ptr(),
+                    self.data.as_mut_ptr().add(new_width * i),
+                    new_width,
+                );
+            }
+        }
+        self.width = new_width as u8;
+    }
+}
diff --git a/vendor/zerovec/src/flexzerovec/vec.rs b/vendor/zerovec/src/flexzerovec/vec.rs
new file mode 100644
index 000000000..a08f54e5d
--- /dev/null
+++ b/vendor/zerovec/src/flexzerovec/vec.rs
@@ -0,0 +1,275 @@
+// 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 super::FlexZeroSlice;
+use super::FlexZeroVecOwned;
+use crate::ZeroVecError;
+use core::cmp::Ordering;
+use core::iter::FromIterator;
+use core::ops::Deref;
+
+/// A zero-copy data structure that efficiently stores integer values.
+///
+/// `FlexZeroVec` automatically increases or decreases its storage capacity based on the largest
+/// integer stored in the vector. It therefore results in lower memory usage when smaller numbers
+/// are usually stored, but larger values must sometimes also be stored.
+///
+/// The maximum value that can be stored in `FlexZeroVec` is `usize::MAX` on the current platform.
+///
+/// `FlexZeroVec` is the data structure for storing `usize` in a `ZeroMap`.
+///
+/// `FlexZeroVec` derefs to [`FlexZeroSlice`], which contains most of the methods.
+///
+/// # Examples
+///
+/// Storing a vec of `usize`s in a zero-copy way:
+///
+/// ```
+/// use zerovec::vecs::FlexZeroVec;
+///
+/// // Create a FlexZeroVec and add a few numbers to it
+/// let mut zv1 = FlexZeroVec::new();
+/// zv1.to_mut().push(55);
+/// zv1.to_mut().push(33);
+/// zv1.to_mut().push(999);
+/// assert_eq!(zv1.to_vec(), vec![55, 33, 999]);
+///
+/// // Convert it to bytes and back
+/// let bytes = zv1.as_bytes();
+/// let zv2 =
+///     FlexZeroVec::parse_byte_slice(bytes).expect("bytes should round-trip");
+/// assert_eq!(zv2.to_vec(), vec![55, 33, 999]);
+///
+/// // Verify the compact storage
+/// assert_eq!(7, bytes.len());
+/// assert!(matches!(zv2, FlexZeroVec::Borrowed(_)));
+/// ```
+///
+/// Storing a map of `usize` to `usize` in a zero-copy way:
+///
+/// ```
+/// use zerovec::ZeroMap;
+///
+/// // Append some values to the ZeroMap
+/// let mut zm = ZeroMap::<usize, usize>::new();
+/// assert!(zm.try_append(&29, &92).is_none());
+/// assert!(zm.try_append(&38, &83).is_none());
+/// assert!(zm.try_append(&56, &65).is_none());
+/// assert_eq!(zm.len(), 3);
+///
+/// // Insert another value into the middle
+/// assert!(zm.try_append(&47, &74).is_some());
+/// assert!(zm.insert(&47, &74).is_none());
+/// assert_eq!(zm.len(), 4);
+///
+/// // Verify that the values are correct
+/// assert_eq!(zm.get_copied(&0), None);
+/// assert_eq!(zm.get_copied(&29), Some(92));
+/// assert_eq!(zm.get_copied(&38), Some(83));
+/// assert_eq!(zm.get_copied(&47), Some(74));
+/// assert_eq!(zm.get_copied(&56), Some(65));
+/// assert_eq!(zm.get_copied(&usize::MAX), None);
+/// ```
+#[derive(Debug)]
+#[non_exhaustive]
+pub enum FlexZeroVec<'a> {
+    Owned(FlexZeroVecOwned),
+    Borrowed(&'a FlexZeroSlice),
+}
+
+impl<'a> Deref for FlexZeroVec<'a> {
+    type Target = FlexZeroSlice;
+    fn deref(&self) -> &Self::Target {
+        match self {
+            FlexZeroVec::Owned(v) => v.deref(),
+            FlexZeroVec::Borrowed(v) => v,
+        }
+    }
+}
+
+impl<'a> AsRef<FlexZeroSlice> for FlexZeroVec<'a> {
+    fn as_ref(&self) -> &FlexZeroSlice {
+        self.deref()
+    }
+}
+
+impl Eq for FlexZeroVec<'_> {}
+
+impl<'a, 'b> PartialEq<FlexZeroVec<'b>> for FlexZeroVec<'a> {
+    #[inline]
+    fn eq(&self, other: &FlexZeroVec<'b>) -> bool {
+        self.iter().eq(other.iter())
+    }
+}
+
+impl<'a> Default for FlexZeroVec<'a> {
+    #[inline]
+    fn default() -> Self {
+        Self::new()
+    }
+}
+
+impl<'a> PartialOrd for FlexZeroVec<'a> {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        self.iter().partial_cmp(other.iter())
+    }
+}
+
+impl<'a> Ord for FlexZeroVec<'a> {
+    fn cmp(&self, other: &Self) -> Ordering {
+        self.iter().cmp(other.iter())
+    }
+}
+
+impl<'a> FlexZeroVec<'a> {
+    #[inline]
+    /// Creates a new, borrowed, empty `FlexZeroVec`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use zerovec::vecs::FlexZeroVec;
+    ///
+    /// let zv: FlexZeroVec = FlexZeroVec::new();
+    /// assert!(zv.is_empty());
+    /// ```
+    pub fn new() -> Self {
+        Self::Borrowed(FlexZeroSlice::new_empty())
+    }
+
+    /// Parses a `&[u8]` buffer into a `FlexZeroVec`.
+    ///
+    /// The bytes within the byte buffer must remain constant for the life of the FlexZeroVec.
+    ///
+    /// # Endianness
+    ///
+    /// The byte buffer must be encoded in little-endian, even if running in a big-endian
+    /// environment. This ensures a consistent representation of data across platforms.
+    ///
+    /// # Max Value
+    ///
+    /// The bytes will fail to parse if the high value is greater than the capacity of `usize`
+    /// on this platform. For example, a `FlexZeroVec` created on a 64-bit platform might fail
+    /// to deserialize on a 32-bit platform.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use zerovec::vecs::FlexZeroVec;
+    ///
+    /// let bytes: &[u8] = &[2, 0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x01];
+    /// let zv = FlexZeroVec::parse_byte_slice(bytes).expect("valid slice");
+    ///
+    /// assert!(matches!(zv, FlexZeroVec::Borrowed(_)));
+    /// assert_eq!(zv.get(2), Some(421));
+    /// ```
+    pub fn parse_byte_slice(bytes: &'a [u8]) -> Result<Self, ZeroVecError> {
+        let slice: &'a FlexZeroSlice = FlexZeroSlice::parse_byte_slice(bytes)?;
+        Ok(Self::Borrowed(slice))
+    }
+
+    /// Converts a borrowed FlexZeroVec to an owned FlexZeroVec. No-op if already owned.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use zerovec::vecs::FlexZeroVec;
+    ///
+    /// let bytes: &[u8] = &[2, 0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x01];
+    /// let zv = FlexZeroVec::parse_byte_slice(bytes).expect("valid bytes");
+    /// assert!(matches!(zv, FlexZeroVec::Borrowed(_)));
+    ///
+    /// let owned = zv.into_owned();
+    /// assert!(matches!(owned, FlexZeroVec::Owned(_)));
+    /// ```
+    pub fn into_owned(self) -> FlexZeroVec<'static> {
+        match self {
+            Self::Owned(owned) => FlexZeroVec::Owned(owned),
+            Self::Borrowed(slice) => FlexZeroVec::Owned(FlexZeroVecOwned::from_slice(slice)),
+        }
+    }
+
+    /// Allows the FlexZeroVec to be mutated by converting it to an owned variant, and producing
+    /// a mutable [`FlexZeroVecOwned`].
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use zerovec::vecs::FlexZeroVec;
+    ///
+    /// let bytes: &[u8] = &[2, 0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x01];
+    /// let mut zv = FlexZeroVec::parse_byte_slice(bytes).expect("valid bytes");
+    /// assert!(matches!(zv, FlexZeroVec::Borrowed(_)));
+    ///
+    /// zv.to_mut().push(12);
+    /// assert!(matches!(zv, FlexZeroVec::Owned(_)));
+    /// assert_eq!(zv.get(4), Some(12));
+    /// ```
+    pub fn to_mut(&mut self) -> &mut FlexZeroVecOwned {
+        match self {
+            Self::Owned(ref mut owned) => owned,
+            Self::Borrowed(slice) => {
+                *self = FlexZeroVec::Owned(FlexZeroVecOwned::from_slice(slice));
+                // recursion is limited since we are guaranteed to hit the Owned branch
+                self.to_mut()
+            }
+        }
+    }
+
+    /// Remove all elements from this FlexZeroVec and reset it to an empty borrowed state.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use zerovec::vecs::FlexZeroVec;
+    ///
+    /// let mut zv: FlexZeroVec = [1, 2, 3].iter().copied().collect();
+    /// assert!(!zv.is_empty());
+    /// zv.clear();
+    /// assert!(zv.is_empty());
+    /// ```
+    pub fn clear(&mut self) {
+        *self = Self::Borrowed(FlexZeroSlice::new_empty())
+    }
+}
+
+impl FromIterator<usize> for FlexZeroVec<'_> {
+    /// Creates a [`FlexZeroVec::Owned`] from an iterator of `usize`.
+    fn from_iter<I>(iter: I) -> Self
+    where
+        I: IntoIterator<Item = usize>,
+    {
+        FlexZeroVecOwned::from_iter(iter).into_flexzerovec()
+    }
+}
+
+#[test]
+fn test_zeromap_usize() {
+    use crate::ZeroMap;
+
+    let mut zm = ZeroMap::<usize, usize>::new();
+    assert!(zm.try_append(&29, &92).is_none());
+    assert!(zm.try_append(&38, &83).is_none());
+    assert!(zm.try_append(&47, &74).is_none());
+    assert!(zm.try_append(&56, &65).is_none());
+
+    assert_eq!(zm.keys.get_width(), 1);
+    assert_eq!(zm.values.get_width(), 1);
+
+    assert_eq!(zm.insert(&47, &744), Some(74));
+    assert_eq!(zm.values.get_width(), 2);
+    assert_eq!(zm.insert(&47, &774), Some(744));
+    assert_eq!(zm.values.get_width(), 2);
+    assert!(zm.try_append(&1100, &1).is_none());
+    assert_eq!(zm.keys.get_width(), 2);
+    assert_eq!(zm.remove(&1100), Some(1));
+    assert_eq!(zm.keys.get_width(), 1);
+
+    assert_eq!(zm.get_copied(&0), None);
+    assert_eq!(zm.get_copied(&29), Some(92));
+    assert_eq!(zm.get_copied(&38), Some(83));
+    assert_eq!(zm.get_copied(&47), Some(774));
+    assert_eq!(zm.get_copied(&56), Some(65));
+    assert_eq!(zm.get_copied(&usize::MAX), None);
+}