Merging upstream version 1.67.1+dfsg1.

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

8 files changed, 2347 insertions, 0 deletions

diff --git a/vendor/zerovec/src/map/borrowed.rs b/vendor/zerovec/src/map/borrowed.rs
new file mode 100644
index 000000000..4c1d1aef6
--- /dev/null
+++ b/vendor/zerovec/src/map/borrowed.rs
@@ -0,0 +1,332 @@
+// 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::AsULE;
+use crate::ZeroSlice;
+
+use core::cmp::Ordering;
+use core::fmt;
+
+pub use super::kv::ZeroMapKV;
+pub use super::vecs::{MutableZeroVecLike, ZeroVecLike};
+
+/// A borrowed-only version of [`ZeroMap`](super::ZeroMap)
+///
+/// This is useful for fully-zero-copy deserialization from non-human-readable
+/// serialization formats. It also has the advantage that it can return references that live for
+/// the lifetime of the backing buffer as opposed to that of the [`ZeroMapBorrowed`] instance.
+///
+/// # Examples
+///
+/// ```
+/// use zerovec::maps::ZeroMapBorrowed;
+///
+/// // Example byte buffer representing the map { 1: "one" }
+/// let BINCODE_BYTES: &[u8; 29] = &[
+///     4, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
+///     0, 0, 111, 110, 101,
+/// ];
+///
+/// // Deserializing to ZeroMap requires no heap allocations.
+/// let zero_map: ZeroMapBorrowed<u32, str> =
+///     bincode::deserialize(BINCODE_BYTES)
+///         .expect("Should deserialize successfully");
+/// assert_eq!(zero_map.get(&1), Some("one"));
+/// ```
+///
+/// This can be obtained from a [`ZeroMap`](super::ZeroMap) via [`ZeroMap::as_borrowed`](super::ZeroMap::as_borrowed)
+pub struct ZeroMapBorrowed<'a, K, V>
+where
+    K: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K: ?Sized,
+    V: ?Sized,
+{
+    pub(crate) keys: &'a <K as ZeroMapKV<'a>>::Slice,
+    pub(crate) values: &'a <V as ZeroMapKV<'a>>::Slice,
+}
+
+impl<'a, K, V> Copy for ZeroMapBorrowed<'a, K, V>
+where
+    K: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K: ?Sized,
+    V: ?Sized,
+{
+}
+impl<'a, K, V> Clone for ZeroMapBorrowed<'a, K, V>
+where
+    K: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K: ?Sized,
+    V: ?Sized,
+{
+    fn clone(&self) -> Self {
+        ZeroMapBorrowed {
+            keys: self.keys,
+            values: self.values,
+        }
+    }
+}
+
+impl<'a, K, V> Default for ZeroMapBorrowed<'a, K, V>
+where
+    K: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K::Slice: 'static,
+    V::Slice: 'static,
+    K: ?Sized,
+    V: ?Sized,
+{
+    fn default() -> Self {
+        Self::new()
+    }
+}
+
+impl<'a, K, V> ZeroMapBorrowed<'a, K, V>
+where
+    K: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K::Slice: 'static,
+    V::Slice: 'static,
+    K: ?Sized,
+    V: ?Sized,
+{
+    /// Creates a new, empty `ZeroMapBorrowed<K, V>`.
+    ///
+    /// Note: Since [`ZeroMapBorrowed`] is not mutable, the return value will be a stub unless
+    /// converted into a [`ZeroMap`](super::ZeroMap).
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use zerovec::maps::ZeroMapBorrowed;
+    ///
+    /// let zm: ZeroMapBorrowed<u16, str> = ZeroMapBorrowed::new();
+    /// assert!(zm.is_empty());
+    /// ```
+    pub fn new() -> Self {
+        Self {
+            keys: K::Container::zvl_new_borrowed(),
+            values: V::Container::zvl_new_borrowed(),
+        }
+    }
+}
+
+impl<'a, K, V> ZeroMapBorrowed<'a, K, V>
+where
+    K: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K: ?Sized,
+    V: ?Sized,
+{
+    #[doc(hidden)] // databake internal
+    pub const unsafe fn from_parts_unchecked(
+        keys: &'a <K as ZeroMapKV<'a>>::Slice,
+        values: &'a <V as ZeroMapKV<'a>>::Slice,
+    ) -> Self {
+        Self { keys, values }
+    }
+
+    /// The number of elements in the [`ZeroMapBorrowed`]
+    pub fn len(&self) -> usize {
+        self.values.zvl_len()
+    }
+
+    /// Whether the [`ZeroMapBorrowed`] is empty
+    pub fn is_empty(&self) -> bool {
+        self.values.zvl_len() == 0
+    }
+}
+
+impl<'a, K, V> ZeroMapBorrowed<'a, K, V>
+where
+    K: ZeroMapKV<'a> + Ord,
+    V: ZeroMapKV<'a>,
+    K: ?Sized,
+    V: ?Sized,
+{
+    /// Get the value associated with `key`, if it exists.
+    ///
+    /// This is able to return values that live longer than the map itself
+    /// since they borrow directly from the backing buffer. This is the
+    /// primary advantage of using [`ZeroMapBorrowed`](super::ZeroMapBorrowed) over [`ZeroMap`](super::ZeroMap).
+    ///
+    /// ```rust
+    /// use zerovec::maps::ZeroMapBorrowed;
+    /// use zerovec::ZeroMap;
+    ///
+    /// let mut map = ZeroMap::new();
+    /// map.insert(&1, "one");
+    /// map.insert(&2, "two");
+    /// let borrowed = map.as_borrowed();
+    /// assert_eq!(borrowed.get(&1), Some("one"));
+    /// assert_eq!(borrowed.get(&3), None);
+    ///
+    /// let borrow = borrowed.get(&1);
+    /// drop(borrowed);
+    /// // still exists after the ZeroMapBorrowed has been dropped
+    /// assert_eq!(borrow, Some("one"));
+    /// ```
+    pub fn get(&self, key: &K) -> Option<&'a V::GetType> {
+        let index = self.keys.zvl_binary_search(key).ok()?;
+        self.values.zvl_get(index)
+    }
+
+    /// Binary search the map with `predicate` to find a key, returning the value.
+    ///
+    /// This is able to return values that live longer than the map itself
+    /// since they borrow directly from the backing buffer. This is the
+    /// primary advantage of using [`ZeroMapBorrowed`](super::ZeroMapBorrowed) over [`ZeroMap`](super::ZeroMap).
+    ///
+    /// ```rust
+    /// use zerovec::maps::ZeroMapBorrowed;
+    /// use zerovec::ZeroMap;
+    ///
+    /// let mut map = ZeroMap::new();
+    /// map.insert(&1, "one");
+    /// map.insert(&2, "two");
+    /// let borrowed = map.as_borrowed();
+    /// assert_eq!(borrowed.get_by(|probe| probe.cmp(&1)), Some("one"));
+    /// assert_eq!(borrowed.get_by(|probe| probe.cmp(&3)), None);
+    ///
+    /// let borrow = borrowed.get_by(|probe| probe.cmp(&1));
+    /// drop(borrowed);
+    /// // still exists after the ZeroMapBorrowed has been dropped
+    /// assert_eq!(borrow, Some("one"));
+    /// ```
+    pub fn get_by(&self, predicate: impl FnMut(&K) -> Ordering) -> Option<&'a V::GetType> {
+        let index = self.keys.zvl_binary_search_by(predicate).ok()?;
+        self.values.zvl_get(index)
+    }
+
+    /// Returns whether `key` is contained in this map
+    ///
+    /// ```rust
+    /// use zerovec::maps::ZeroMapBorrowed;
+    /// use zerovec::ZeroMap;
+    ///
+    /// let mut map = ZeroMap::new();
+    /// map.insert(&1, "one");
+    /// map.insert(&2, "two");
+    /// let borrowed = map.as_borrowed();
+    /// assert_eq!(borrowed.contains_key(&1), true);
+    /// assert_eq!(borrowed.contains_key(&3), false);
+    /// ```
+    pub fn contains_key(&self, key: &K) -> bool {
+        self.keys.zvl_binary_search(key).is_ok()
+    }
+}
+
+impl<'a, K, V> ZeroMapBorrowed<'a, K, V>
+where
+    K: ZeroMapKV<'a> + ?Sized,
+    V: ZeroMapKV<'a> + ?Sized,
+{
+    /// Produce an ordered iterator over key-value pairs
+    pub fn iter<'b>(
+        &'b self,
+    ) -> impl Iterator<
+        Item = (
+            &'a <K as ZeroMapKV<'a>>::GetType,
+            &'a <V as ZeroMapKV<'a>>::GetType,
+        ),
+    > + 'b {
+        self.iter_keys().zip(self.iter_values())
+    }
+
+    /// Produce an ordered iterator over keys
+    pub fn iter_keys<'b>(&'b self) -> impl Iterator<Item = &'a <K as ZeroMapKV<'a>>::GetType> + 'b {
+        #[allow(clippy::unwrap_used)] // idx in 0..keys.zvl_len()
+        (0..self.keys.zvl_len()).map(move |idx| self.keys.zvl_get(idx).unwrap())
+    }
+
+    /// Produce an iterator over values, ordered by keys
+    pub fn iter_values<'b>(
+        &'b self,
+    ) -> impl Iterator<Item = &'a <V as ZeroMapKV<'a>>::GetType> + 'b {
+        #[allow(clippy::unwrap_used)] // idx in 0..keys.zvl_len() == values.zvl_len()
+        (0..self.values.zvl_len()).map(move |idx| self.values.zvl_get(idx).unwrap())
+    }
+}
+
+impl<'a, K, V> ZeroMapBorrowed<'a, K, V>
+where
+    K: ZeroMapKV<'a> + Ord + ?Sized,
+    V: ZeroMapKV<'a, Slice = ZeroSlice<V>> + AsULE + Copy + 'static,
+{
+    /// For cases when `V` is fixed-size, obtain a direct copy of `V` instead of `V::ULE`
+    pub fn get_copied(&self, key: &K) -> Option<V> {
+        let index = self.keys.zvl_binary_search(key).ok()?;
+        self.values.get(index)
+    }
+
+    /// Similar to [`Self::iter()`] except it returns a direct copy of the values instead of references
+    /// to `V::ULE`, in cases when `V` is fixed-size
+    pub fn iter_copied_values<'b>(
+        &'b self,
+    ) -> impl Iterator<Item = (&'b <K as ZeroMapKV<'a>>::GetType, V)> {
+        (0..self.keys.zvl_len()).map(move |idx| {
+            (
+                #[allow(clippy::unwrap_used)] // idx in 0..keys.zvl_len()
+                self.keys.zvl_get(idx).unwrap(),
+                #[allow(clippy::unwrap_used)] // idx in 0..keys.zvl_len() = values.zvl_len()
+                self.values.get(idx).unwrap(),
+            )
+        })
+    }
+}
+
+impl<'a, K, V> ZeroMapBorrowed<'a, K, V>
+where
+    K: ZeroMapKV<'a, Slice = ZeroSlice<K>> + AsULE + Copy + Ord + 'static,
+    V: ZeroMapKV<'a, Slice = ZeroSlice<V>> + AsULE + Copy + 'static,
+{
+    /// Similar to [`Self::iter()`] except it returns a direct copy of the keys values instead of references
+    /// to `K::ULE` and `V::ULE`, in cases when `K` and `V` are fixed-size
+    #[allow(clippy::needless_lifetimes)] // Lifetime is necessary in impl Trait
+    pub fn iter_copied<'b: 'a>(&'b self) -> impl Iterator<Item = (K, V)> + 'b {
+        let keys = &*self.keys;
+        let values = &*self.values;
+        let len = self.keys.zvl_len();
+        (0..len).map(move |idx| {
+            (
+                #[allow(clippy::unwrap_used)] // idx in 0..keys.zvl_len()
+                ZeroSlice::get(keys, idx).unwrap(),
+                #[allow(clippy::unwrap_used)] // idx in 0..keys.zvl_len() = values.zvl_len()
+                ZeroSlice::get(values, idx).unwrap(),
+            )
+        })
+    }
+}
+
+// We can't use the default PartialEq because ZeroMap is invariant
+// so otherwise rustc will not automatically allow you to compare ZeroMaps
+// with different lifetimes
+impl<'a, 'b, K, V> PartialEq<ZeroMapBorrowed<'b, K, V>> for ZeroMapBorrowed<'a, K, V>
+where
+    K: for<'c> ZeroMapKV<'c> + ?Sized,
+    V: for<'c> ZeroMapKV<'c> + ?Sized,
+    <K as ZeroMapKV<'a>>::Slice: PartialEq<<K as ZeroMapKV<'b>>::Slice>,
+    <V as ZeroMapKV<'a>>::Slice: PartialEq<<V as ZeroMapKV<'b>>::Slice>,
+{
+    fn eq(&self, other: &ZeroMapBorrowed<'b, K, V>) -> bool {
+        self.keys.eq(other.keys) && self.values.eq(other.values)
+    }
+}
+
+impl<'a, K, V> fmt::Debug for ZeroMapBorrowed<'a, K, V>
+where
+    K: ZeroMapKV<'a> + ?Sized,
+    V: ZeroMapKV<'a> + ?Sized,
+    K::Slice: fmt::Debug,
+    V::Slice: fmt::Debug,
+{
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
+        f.debug_struct("ZeroMapBorrowed")
+            .field("keys", &self.keys)
+            .field("values", &self.values)
+            .finish()
+    }
+}
diff --git a/vendor/zerovec/src/map/databake.rs b/vendor/zerovec/src/map/databake.rs
new file mode 100644
index 000000000..d98b48f9f
--- /dev/null
+++ b/vendor/zerovec/src/map/databake.rs
@@ -0,0 +1,86 @@
+// 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::{maps::ZeroMapBorrowed, maps::ZeroMapKV, ZeroMap};
+use databake::*;
+
+impl<'a, K, V> Bake for ZeroMap<'a, K, V>
+where
+    K: ZeroMapKV<'a> + ?Sized,
+    V: ZeroMapKV<'a> + ?Sized,
+    K::Container: Bake,
+    V::Container: Bake,
+{
+    fn bake(&self, env: &CrateEnv) -> TokenStream {
+        env.insert("zerovec");
+        let keys = self.keys.bake(env);
+        let values = self.values.bake(env);
+        quote! { unsafe { #[allow(unused_unsafe)] ::zerovec::ZeroMap::from_parts_unchecked(#keys, #values) } }
+    }
+}
+
+impl<'a, K, V> Bake for ZeroMapBorrowed<'a, K, V>
+where
+    K: ZeroMapKV<'a> + ?Sized,
+    V: ZeroMapKV<'a> + ?Sized,
+    &'a K::Slice: Bake,
+    &'a V::Slice: Bake,
+{
+    fn bake(&self, env: &CrateEnv) -> TokenStream {
+        env.insert("zerovec");
+        let keys = self.keys.bake(env);
+        let values = self.values.bake(env);
+        quote! { unsafe { #[allow(unused_unsafe)] ::zerovec::maps::ZeroMapBorrowed::from_parts_unchecked(#keys, #values) } }
+    }
+}
+
+#[test]
+fn test_baked_map() {
+    test_bake!(
+        ZeroMap<str, str>,
+        const: unsafe {
+            #[allow(unused_unsafe)]
+            crate::ZeroMap::from_parts_unchecked(
+                unsafe {
+                    crate::VarZeroVec::from_bytes_unchecked(&[
+                        2u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 2u8, 0u8, 0u8, 0u8, 97u8,
+                        100u8, 98u8, 99u8,
+                    ])
+                },
+                unsafe {
+                    crate::VarZeroVec::from_bytes_unchecked(&[
+                        2u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 4u8, 0u8, 0u8, 0u8, 69u8, 82u8,
+                        65u8, 49u8, 69u8, 82u8, 65u8, 48u8,
+                    ])
+                },
+            )
+        },
+        zerovec
+    );
+}
+
+#[test]
+fn test_baked_borrowed_map() {
+    test_bake!(
+        ZeroMapBorrowed<str, str>,
+        const: unsafe {
+            #[allow(unused_unsafe)]
+            crate::maps::ZeroMapBorrowed::from_parts_unchecked(
+                unsafe {
+                    crate::VarZeroSlice::from_bytes_unchecked(&[
+                        2u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 2u8, 0u8, 0u8, 0u8, 97u8,
+                        100u8, 98u8, 99u8,
+                    ])
+                },
+                unsafe {
+                    crate::VarZeroSlice::from_bytes_unchecked(&[
+                        2u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 4u8, 0u8, 0u8, 0u8, 69u8, 82u8,
+                        65u8, 49u8, 69u8, 82u8, 65u8, 48u8,
+                    ])
+                },
+            )
+        },
+        zerovec
+    );
+}
diff --git a/vendor/zerovec/src/map/kv.rs b/vendor/zerovec/src/map/kv.rs
new file mode 100644
index 000000000..1923ed991
--- /dev/null
+++ b/vendor/zerovec/src/map/kv.rs
@@ -0,0 +1,131 @@
+// 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::vecs::{MutableZeroVecLike, ZeroVecLike};
+use crate::ule::*;
+use crate::vecs::{FlexZeroSlice, FlexZeroVec};
+use crate::vecs::{VarZeroSlice, VarZeroVec};
+use crate::zerovec::{ZeroSlice, ZeroVec};
+use alloc::boxed::Box;
+
+/// Trait marking types which are allowed to be keys or values in [`ZeroMap`](super::ZeroMap).
+///
+/// Users should not be calling methods of this trait directly, however if you are
+/// implementing your own [`AsULE`] or [`VarULE`] type you may wish to implement
+/// this trait.
+// this lifetime should be a GAT on Container once that is possible
+#[allow(clippy::upper_case_acronyms)] // KV is not an acronym
+pub trait ZeroMapKV<'a> {
+    /// The container that can be used with this type: [`ZeroVec`] or [`VarZeroVec`].
+    type Container: MutableZeroVecLike<
+            'a,
+            Self,
+            SliceVariant = Self::Slice,
+            GetType = Self::GetType,
+            OwnedType = Self::OwnedType,
+        > + Sized;
+    type Slice: ZeroVecLike<Self, GetType = Self::GetType> + ?Sized;
+    /// The type produced by `Container::get()`
+    ///
+    /// This type will be predetermined by the choice of `Self::Container`:
+    /// For sized types this must be `T::ULE`, and for unsized types this must be `T`
+    type GetType: ?Sized + 'static;
+    /// The type produced by `Container::replace()` and `Container::remove()`,
+    /// also used during deserialization. If `Self` is human readable serialized,
+    /// deserializing to `Self::OwnedType` should produce the same value once
+    /// passed through `Self::owned_as_self()`
+    ///
+    /// This type will be predetermined by the choice of `Self::Container`:
+    /// For sized types this must be `T` and for unsized types this must be `Box<T>`
+    type OwnedType: 'static;
+}
+
+macro_rules! impl_sized_kv {
+    ($ty:ident) => {
+        impl<'a> ZeroMapKV<'a> for $ty {
+            type Container = ZeroVec<'a, $ty>;
+            type Slice = ZeroSlice<$ty>;
+            type GetType = <$ty as AsULE>::ULE;
+            type OwnedType = $ty;
+        }
+    };
+}
+
+impl_sized_kv!(u8);
+impl_sized_kv!(u16);
+impl_sized_kv!(u32);
+impl_sized_kv!(u64);
+impl_sized_kv!(u128);
+impl_sized_kv!(i8);
+impl_sized_kv!(i16);
+impl_sized_kv!(i32);
+impl_sized_kv!(i64);
+impl_sized_kv!(i128);
+impl_sized_kv!(char);
+impl_sized_kv!(f32);
+impl_sized_kv!(f64);
+
+impl<'a> ZeroMapKV<'a> for usize {
+    type Container = FlexZeroVec<'a>;
+    type Slice = FlexZeroSlice;
+    type GetType = [u8];
+    type OwnedType = usize;
+}
+
+impl<'a, T> ZeroMapKV<'a> for Option<T>
+where
+    Option<T>: AsULE + 'static,
+{
+    type Container = ZeroVec<'a, Option<T>>;
+    type Slice = ZeroSlice<Option<T>>;
+    type GetType = <Option<T> as AsULE>::ULE;
+    type OwnedType = Option<T>;
+}
+
+impl<'a, T> ZeroMapKV<'a> for OptionVarULE<T>
+where
+    T: VarULE + ?Sized,
+{
+    type Container = VarZeroVec<'a, OptionVarULE<T>>;
+    type Slice = VarZeroSlice<OptionVarULE<T>>;
+    type GetType = OptionVarULE<T>;
+    type OwnedType = Box<OptionVarULE<T>>;
+}
+
+impl<'a> ZeroMapKV<'a> for str {
+    type Container = VarZeroVec<'a, str>;
+    type Slice = VarZeroSlice<str>;
+    type GetType = str;
+    type OwnedType = Box<str>;
+}
+
+impl<'a, T> ZeroMapKV<'a> for [T]
+where
+    T: ULE + AsULE<ULE = T>,
+{
+    type Container = VarZeroVec<'a, [T]>;
+    type Slice = VarZeroSlice<[T]>;
+    type GetType = [T];
+    type OwnedType = Box<[T]>;
+}
+
+impl<'a, T, const N: usize> ZeroMapKV<'a> for [T; N]
+where
+    T: AsULE + 'static,
+{
+    type Container = ZeroVec<'a, [T; N]>;
+    type Slice = ZeroSlice<[T; N]>;
+    type GetType = [T::ULE; N];
+    type OwnedType = [T; N];
+}
+
+impl<'a, T> ZeroMapKV<'a> for ZeroSlice<T>
+where
+    T: AsULE + 'static,
+{
+    type Container = VarZeroVec<'a, ZeroSlice<T>>;
+    type Slice = VarZeroSlice<ZeroSlice<T>>;
+    type GetType = ZeroSlice<T>;
+    type OwnedType = Box<ZeroSlice<T>>;
+}
diff --git a/vendor/zerovec/src/map/map.rs b/vendor/zerovec/src/map/map.rs
new file mode 100644
index 000000000..379b22667
--- /dev/null
+++ b/vendor/zerovec/src/map/map.rs
@@ -0,0 +1,567 @@
+// 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::*;
+use crate::ule::{AsULE, EncodeAsVarULE, VarULE};
+use crate::{VarZeroVec, ZeroSlice, ZeroVec};
+use alloc::borrow::Borrow;
+use alloc::boxed::Box;
+use core::cmp::Ordering;
+use core::fmt;
+use core::iter::FromIterator;
+
+/// A zero-copy map datastructure, built on sorted binary-searchable [`ZeroVec`]
+/// and [`VarZeroVec`].
+///
+/// This type, like [`ZeroVec`] and [`VarZeroVec`], is able to zero-copy
+/// deserialize from appropriately formatted byte buffers. It is internally copy-on-write, so it can be mutated
+/// afterwards as necessary.
+///
+/// Internally, a `ZeroMap` is a zero-copy vector for keys paired with a zero-copy vector for
+/// values, sorted by the keys. Therefore, all types used in `ZeroMap` need to work with either
+/// [`ZeroVec`] or [`VarZeroVec`].
+///
+/// This does mean that for fixed-size data, one must use the regular type (`u32`, `u8`, `char`, etc),
+/// whereas for variable-size data, `ZeroMap` will use the dynamically sized version (`str` not `String`,
+/// `ZeroSlice` not `ZeroVec`, `FooULE` not `Foo` for custom types)
+///
+/// # Examples
+///
+/// ```
+/// use zerovec::ZeroMap;
+///
+/// #[derive(serde::Serialize, serde::Deserialize)]
+/// struct Data<'a> {
+///     #[serde(borrow)]
+///     map: ZeroMap<'a, u32, str>,
+/// }
+///
+/// let mut map = ZeroMap::new();
+/// map.insert(&1, "one");
+/// map.insert(&2, "two");
+/// map.insert(&4, "four");
+///
+/// let data = Data { map };
+///
+/// let bincode_bytes =
+///     bincode::serialize(&data).expect("Serialization should be successful");
+///
+/// // Will deserialize without any allocations
+/// let deserialized: Data = bincode::deserialize(&bincode_bytes)
+///     .expect("Deserialization should be successful");
+///
+/// assert_eq!(data.map.get(&1), Some("one"));
+/// assert_eq!(data.map.get(&2), Some("two"));
+/// ```
+///
+/// [`VarZeroVec`]: crate::VarZeroVec
+// ZeroMap has only one invariant: keys.len() == values.len()
+// It is also expected that the keys are sorted, but this is not an invariant. See #1433
+pub struct ZeroMap<'a, K, V>
+where
+    K: ZeroMapKV<'a> + ?Sized,
+    V: ZeroMapKV<'a> + ?Sized,
+{
+    pub(crate) keys: K::Container,
+    pub(crate) values: V::Container,
+}
+
+impl<'a, K, V> Default for ZeroMap<'a, K, V>
+where
+    K: ZeroMapKV<'a> + ?Sized,
+    V: ZeroMapKV<'a> + ?Sized,
+{
+    fn default() -> Self {
+        Self::new()
+    }
+}
+
+impl<'a, K, V> ZeroMap<'a, K, V>
+where
+    K: ZeroMapKV<'a> + ?Sized,
+    V: ZeroMapKV<'a> + ?Sized,
+{
+    /// Creates a new, empty `ZeroMap<K, V>`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use zerovec::ZeroMap;
+    ///
+    /// let zm: ZeroMap<u16, str> = ZeroMap::new();
+    /// assert!(zm.is_empty());
+    /// ```
+    pub fn new() -> Self {
+        Self {
+            keys: K::Container::zvl_with_capacity(0),
+            values: V::Container::zvl_with_capacity(0),
+        }
+    }
+
+    #[doc(hidden)] // databake internal
+    pub const unsafe fn from_parts_unchecked(keys: K::Container, values: V::Container) -> Self {
+        Self { keys, values }
+    }
+
+    /// Construct a new [`ZeroMap`] with a given capacity
+    pub fn with_capacity(capacity: usize) -> Self {
+        Self {
+            keys: K::Container::zvl_with_capacity(capacity),
+            values: V::Container::zvl_with_capacity(capacity),
+        }
+    }
+
+    /// Obtain a borrowed version of this map
+    pub fn as_borrowed(&'a self) -> ZeroMapBorrowed<'a, K, V> {
+        ZeroMapBorrowed {
+            keys: self.keys.zvl_as_borrowed(),
+            values: self.values.zvl_as_borrowed(),
+        }
+    }
+
+    /// The number of elements in the [`ZeroMap`]
+    pub fn len(&self) -> usize {
+        self.values.zvl_len()
+    }
+
+    /// Whether the [`ZeroMap`] is empty
+    pub fn is_empty(&self) -> bool {
+        self.values.zvl_len() == 0
+    }
+
+    /// Remove all elements from the [`ZeroMap`]
+    pub fn clear(&mut self) {
+        self.keys.zvl_clear();
+        self.values.zvl_clear();
+    }
+
+    /// Reserve capacity for `additional` more elements to be inserted into
+    /// the [`ZeroMap`] to avoid frequent reallocations.
+    ///
+    /// See [`Vec::reserve()`](alloc::vec::Vec::reserve) for more information.
+    pub fn reserve(&mut self, additional: usize) {
+        self.keys.zvl_reserve(additional);
+        self.values.zvl_reserve(additional);
+    }
+}
+impl<'a, K, V> ZeroMap<'a, K, V>
+where
+    K: ZeroMapKV<'a> + ?Sized + Ord,
+    V: ZeroMapKV<'a> + ?Sized,
+{
+    /// Get the value associated with `key`, if it exists.
+    ///
+    /// For fixed-size ([`AsULE`]) `V` types, this _will_ return
+    /// their corresponding [`AsULE::ULE`] type. If you wish to work with the `V`
+    /// type directly, [`Self::get_copied()`] exists for convenience.
+    ///
+    /// ```rust
+    /// use zerovec::ZeroMap;
+    ///
+    /// let mut map = ZeroMap::new();
+    /// map.insert(&1, "one");
+    /// map.insert(&2, "two");
+    /// assert_eq!(map.get(&1), Some("one"));
+    /// assert_eq!(map.get(&3), None);
+    /// ```
+    pub fn get(&self, key: &K) -> Option<&V::GetType> {
+        let index = self.keys.zvl_binary_search(key).ok()?;
+        self.values.zvl_get(index)
+    }
+
+    /// Binary search the map with `predicate` to find a key, returning the value.
+    ///
+    /// ```rust
+    /// use zerovec::ZeroMap;
+    ///
+    /// let mut map = ZeroMap::new();
+    /// map.insert(&1, "one");
+    /// map.insert(&2, "two");
+    /// assert_eq!(map.get_by(|probe| probe.cmp(&1)), Some("one"));
+    /// assert_eq!(map.get_by(|probe| probe.cmp(&3)), None);
+    /// ```
+    pub fn get_by(&self, predicate: impl FnMut(&K) -> Ordering) -> Option<&V::GetType> {
+        let index = self.keys.zvl_binary_search_by(predicate).ok()?;
+        self.values.zvl_get(index)
+    }
+
+    /// Returns whether `key` is contained in this map
+    ///
+    /// ```rust
+    /// use zerovec::ZeroMap;
+    ///
+    /// let mut map = ZeroMap::new();
+    /// map.insert(&1, "one");
+    /// map.insert(&2, "two");
+    /// assert_eq!(map.contains_key(&1), true);
+    /// assert_eq!(map.contains_key(&3), false);
+    /// ```
+    pub fn contains_key(&self, key: &K) -> bool {
+        self.keys.zvl_binary_search(key).is_ok()
+    }
+
+    /// Insert `value` with `key`, returning the existing value if it exists.
+    ///
+    /// ```rust
+    /// use zerovec::ZeroMap;
+    ///
+    /// let mut map = ZeroMap::new();
+    /// map.insert(&1, "one");
+    /// map.insert(&2, "two");
+    /// assert_eq!(map.get(&1), Some("one"));
+    /// assert_eq!(map.get(&3), None);
+    /// ```
+    pub fn insert(&mut self, key: &K, value: &V) -> Option<V::OwnedType> {
+        match self.keys.zvl_binary_search(key) {
+            Ok(index) => Some(self.values.zvl_replace(index, value)),
+            Err(index) => {
+                self.keys.zvl_insert(index, key);
+                self.values.zvl_insert(index, value);
+                None
+            }
+        }
+    }
+
+    /// Remove the value at `key`, returning it if it exists.
+    ///
+    /// ```rust
+    /// use zerovec::ZeroMap;
+    ///
+    /// let mut map = ZeroMap::new();
+    /// map.insert(&1, "one");
+    /// map.insert(&2, "two");
+    /// assert_eq!(map.remove(&1), Some("one".to_owned().into_boxed_str()));
+    /// assert_eq!(map.get(&1), None);
+    /// ```
+    pub fn remove(&mut self, key: &K) -> Option<V::OwnedType> {
+        let idx = self.keys.zvl_binary_search(key).ok()?;
+        self.keys.zvl_remove(idx);
+        Some(self.values.zvl_remove(idx))
+    }
+
+    /// Appends `value` with `key` to the end of the underlying vector, returning
+    /// `key` and `value` _if it failed_. Useful for extending with an existing
+    /// sorted list.
+    /// ```rust
+    /// use zerovec::ZeroMap;
+    ///
+    /// let mut map = ZeroMap::new();
+    /// assert!(map.try_append(&1, "uno").is_none());
+    /// assert!(map.try_append(&3, "tres").is_none());
+    ///
+    /// let unsuccessful = map.try_append(&3, "tres-updated");
+    /// assert!(unsuccessful.is_some(), "append duplicate of last key");
+    ///
+    /// let unsuccessful = map.try_append(&2, "dos");
+    /// assert!(unsuccessful.is_some(), "append out of order");
+    ///
+    /// assert_eq!(map.get(&1), Some("uno"));
+    ///
+    /// // contains the original value for the key: 3
+    /// assert_eq!(map.get(&3), Some("tres"));
+    ///
+    /// // not appended since it wasn't in order
+    /// assert_eq!(map.get(&2), None);
+    /// ```
+    #[must_use]
+    pub fn try_append<'b>(&mut self, key: &'b K, value: &'b V) -> Option<(&'b K, &'b V)> {
+        if self.keys.zvl_len() != 0 {
+            if let Some(last) = self.keys.zvl_get(self.keys.zvl_len() - 1) {
+                if K::Container::t_cmp_get(key, last) != Ordering::Greater {
+                    return Some((key, value));
+                }
+            }
+        }
+
+        self.keys.zvl_push(key);
+        self.values.zvl_push(value);
+        None
+    }
+}
+
+impl<'a, K, V> ZeroMap<'a, K, V>
+where
+    K: ZeroMapKV<'a> + ?Sized,
+    V: ZeroMapKV<'a> + ?Sized,
+{
+    /// Produce an ordered iterator over key-value pairs
+    pub fn iter<'b>(
+        &'b self,
+    ) -> impl ExactSizeIterator<
+        Item = (
+            &'b <K as ZeroMapKV<'a>>::GetType,
+            &'b <V as ZeroMapKV<'a>>::GetType,
+        ),
+    > {
+        (0..self.keys.zvl_len()).map(move |idx| {
+            (
+                #[allow(clippy::unwrap_used)] // idx is in-range
+                self.keys.zvl_get(idx).unwrap(),
+                #[allow(clippy::unwrap_used)] // idx is in-range
+                self.values.zvl_get(idx).unwrap(),
+            )
+        })
+    }
+
+    /// Produce an ordered iterator over keys
+    pub fn iter_keys<'b>(
+        &'b self,
+    ) -> impl ExactSizeIterator<Item = &'b <K as ZeroMapKV<'a>>::GetType> {
+        #[allow(clippy::unwrap_used)] // idx is in-range
+        (0..self.keys.zvl_len()).map(move |idx| self.keys.zvl_get(idx).unwrap())
+    }
+
+    /// Produce an iterator over values, ordered by keys
+    pub fn iter_values<'b>(
+        &'b self,
+    ) -> impl ExactSizeIterator<Item = &'b <V as ZeroMapKV<'a>>::GetType> {
+        #[allow(clippy::unwrap_used)] // idx is in-range
+        (0..self.values.zvl_len()).map(move |idx| self.values.zvl_get(idx).unwrap())
+    }
+}
+
+impl<'a, K, V> ZeroMap<'a, K, V>
+where
+    K: ZeroMapKV<'a> + ?Sized + Ord,
+    V: ZeroMapKV<'a, Container = VarZeroVec<'a, V>> + ?Sized,
+    V: VarULE,
+{
+    /// Same as `insert()`, but allows using [EncodeAsVarULE](crate::ule::EncodeAsVarULE)
+    /// types with the value to avoid an extra allocation when dealing with custom ULE types.
+    ///
+    /// ```rust
+    /// use std::borrow::Cow;
+    /// use zerovec::ZeroMap;
+    ///
+    /// #[zerovec::make_varule(PersonULE)]
+    /// #[derive(Clone, Eq, PartialEq, Ord, PartialOrd)]
+    /// struct Person<'a> {
+    ///     age: u8,
+    ///     name: Cow<'a, str>,
+    /// }
+    ///
+    /// let mut map: ZeroMap<u32, PersonULE> = ZeroMap::new();
+    /// map.insert_var_v(
+    ///     &1,
+    ///     &Person {
+    ///         age: 20,
+    ///         name: "Joseph".into(),
+    ///     },
+    /// );
+    /// map.insert_var_v(
+    ///     &1,
+    ///     &Person {
+    ///         age: 35,
+    ///         name: "Carla".into(),
+    ///     },
+    /// );
+    /// assert_eq!(&map.get(&1).unwrap().name, "Carla");
+    /// assert!(map.get(&3).is_none());
+    /// ```
+    pub fn insert_var_v<VE: EncodeAsVarULE<V>>(&mut self, key: &K, value: &VE) -> Option<Box<V>> {
+        match self.keys.zvl_binary_search(key) {
+            Ok(index) => {
+                #[allow(clippy::unwrap_used)] // binary search
+                let ret = self.values.get(index).unwrap().to_boxed();
+                self.values.make_mut().replace(index, value);
+                Some(ret)
+            }
+            Err(index) => {
+                self.keys.zvl_insert(index, key);
+                self.values.make_mut().insert(index, value);
+                None
+            }
+        }
+    }
+
+    // insert_var_k, insert_var_kv are not possible since one cannot perform the binary search with EncodeAsVarULE
+    // though we might be able to do it in the future if we add a trait for cross-Ord requirements
+}
+
+impl<'a, K, V> ZeroMap<'a, K, V>
+where
+    K: ZeroMapKV<'a> + ?Sized + Ord,
+    V: ZeroMapKV<'a> + ?Sized,
+    V: Copy,
+{
+    /// For cases when `V` is fixed-size, obtain a direct copy of `V` instead of `V::ULE`.
+    ///
+    /// # Examples
+    ///
+    /// ```rust
+    /// use zerovec::ZeroMap;
+    ///
+    /// let mut map = ZeroMap::new();
+    /// map.insert(&1, &'a');
+    /// map.insert(&2, &'b');
+    /// assert_eq!(map.get_copied(&1), Some('a'));
+    /// assert_eq!(map.get_copied(&3), None);
+    #[inline]
+    pub fn get_copied(&self, key: &K) -> Option<V> {
+        let index = self.keys.zvl_binary_search(key).ok()?;
+        self.get_copied_at(index)
+    }
+
+    /// Binary search the map with `predicate` to find a key, returning the value.
+    ///
+    /// For cases when `V` is fixed-size, use this method to obtain a direct copy of `V`
+    /// instead of `V::ULE`.
+    ///
+    /// # Examples
+    ///
+    /// ```rust
+    /// use zerovec::ZeroMap;
+    ///
+    /// let mut map = ZeroMap::new();
+    /// map.insert(&1, &'a');
+    /// map.insert(&2, &'b');
+    /// assert_eq!(map.get_copied_by(|probe| probe.cmp(&1)), Some('a'));
+    /// assert_eq!(map.get_copied_by(|probe| probe.cmp(&3)), None);
+    /// ```
+    #[inline]
+    pub fn get_copied_by(&self, predicate: impl FnMut(&K) -> Ordering) -> Option<V> {
+        let index = self.keys.zvl_binary_search_by(predicate).ok()?;
+        self.get_copied_at(index)
+    }
+
+    fn get_copied_at(&self, index: usize) -> Option<V> {
+        let ule = self.values.zvl_get(index)?;
+        let mut result = Option::<V>::None;
+        V::Container::zvl_get_as_t(ule, |v| result.replace(*v));
+        #[allow(clippy::unwrap_used)] // `zvl_get_as_t` guarantees that the callback is invoked
+        Some(result.unwrap())
+    }
+}
+
+impl<'a, K, V> ZeroMap<'a, K, V>
+where
+    K: ZeroMapKV<'a> + ?Sized,
+    V: ZeroMapKV<'a, Container = ZeroVec<'a, V>> + ?Sized,
+    V: AsULE + Copy,
+{
+    /// Similar to [`Self::iter()`] except it returns a direct copy of the values instead of references
+    /// to `V::ULE`, in cases when `V` is fixed-size
+    pub fn iter_copied_values<'b>(
+        &'b self,
+    ) -> impl Iterator<Item = (&'b <K as ZeroMapKV<'a>>::GetType, V)> {
+        (0..self.keys.zvl_len()).map(move |idx| {
+            (
+                #[allow(clippy::unwrap_used)] // idx in 0..keys.zvl_len()
+                self.keys.zvl_get(idx).unwrap(),
+                #[allow(clippy::unwrap_used)] // idx in 0..keys.zvl_len() = values.zvl_len()
+                ZeroSlice::get(&*self.values, idx).unwrap(),
+            )
+        })
+    }
+}
+
+impl<'a, K, V> ZeroMap<'a, K, V>
+where
+    K: ZeroMapKV<'a, Container = ZeroVec<'a, K>> + ?Sized,
+    V: ZeroMapKV<'a, Container = ZeroVec<'a, V>> + ?Sized,
+    K: AsULE + Copy,
+    V: AsULE + Copy,
+{
+    /// Similar to [`Self::iter()`] except it returns a direct copy of the keys values instead of references
+    /// to `K::ULE` and `V::ULE`, in cases when `K` and `V` are fixed-size
+    #[allow(clippy::needless_lifetimes)] // Lifetime is necessary in impl Trait
+    pub fn iter_copied<'b>(&'b self) -> impl Iterator<Item = (K, V)> + 'b {
+        let keys = &self.keys;
+        let values = &self.values;
+        (0..keys.len()).map(move |idx| {
+            (
+                #[allow(clippy::unwrap_used)] // idx in 0..keys.zvl_len()
+                ZeroSlice::get(&**keys, idx).unwrap(),
+                #[allow(clippy::unwrap_used)] // idx in 0..keys.zvl_len() = values.zvl_len()
+                ZeroSlice::get(&**values, idx).unwrap(),
+            )
+        })
+    }
+}
+
+impl<'a, K, V> From<ZeroMapBorrowed<'a, K, V>> for ZeroMap<'a, K, V>
+where
+    K: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K: ?Sized,
+    V: ?Sized,
+{
+    fn from(other: ZeroMapBorrowed<'a, K, V>) -> Self {
+        Self {
+            keys: K::Container::zvl_from_borrowed(other.keys),
+            values: V::Container::zvl_from_borrowed(other.values),
+        }
+    }
+}
+
+// We can't use the default PartialEq because ZeroMap is invariant
+// so otherwise rustc will not automatically allow you to compare ZeroMaps
+// with different lifetimes
+impl<'a, 'b, K, V> PartialEq<ZeroMap<'b, K, V>> for ZeroMap<'a, K, V>
+where
+    K: for<'c> ZeroMapKV<'c> + ?Sized,
+    V: for<'c> ZeroMapKV<'c> + ?Sized,
+    <K as ZeroMapKV<'a>>::Container: PartialEq<<K as ZeroMapKV<'b>>::Container>,
+    <V as ZeroMapKV<'a>>::Container: PartialEq<<V as ZeroMapKV<'b>>::Container>,
+{
+    fn eq(&self, other: &ZeroMap<'b, K, V>) -> bool {
+        self.keys.eq(&other.keys) && self.values.eq(&other.values)
+    }
+}
+
+impl<'a, K, V> fmt::Debug for ZeroMap<'a, K, V>
+where
+    K: ZeroMapKV<'a> + ?Sized,
+    V: ZeroMapKV<'a> + ?Sized,
+    <K as ZeroMapKV<'a>>::Container: fmt::Debug,
+    <V as ZeroMapKV<'a>>::Container: fmt::Debug,
+{
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
+        f.debug_struct("ZeroMap")
+            .field("keys", &self.keys)
+            .field("values", &self.values)
+            .finish()
+    }
+}
+
+impl<'a, K, V> Clone for ZeroMap<'a, K, V>
+where
+    K: ZeroMapKV<'a> + ?Sized,
+    V: ZeroMapKV<'a> + ?Sized,
+    <K as ZeroMapKV<'a>>::Container: Clone,
+    <V as ZeroMapKV<'a>>::Container: Clone,
+{
+    fn clone(&self) -> Self {
+        Self {
+            keys: self.keys.clone(),
+            values: self.values.clone(),
+        }
+    }
+}
+
+impl<'a, A, B, K, V> FromIterator<(A, B)> for ZeroMap<'a, K, V>
+where
+    A: Borrow<K>,
+    B: Borrow<V>,
+    K: ZeroMapKV<'a> + ?Sized + Ord,
+    V: ZeroMapKV<'a> + ?Sized,
+{
+    fn from_iter<T>(iter: T) -> Self
+    where
+        T: IntoIterator<Item = (A, B)>,
+    {
+        let iter = iter.into_iter();
+        let mut map = match iter.size_hint() {
+            (_, Some(upper)) => Self::with_capacity(upper),
+            (lower, None) => Self::with_capacity(lower),
+        };
+
+        for (key, value) in iter {
+            if let Some((key, value)) = map.try_append(key.borrow(), value.borrow()) {
+                map.insert(key, value);
+            }
+        }
+        map
+    }
+}
diff --git a/vendor/zerovec/src/map/mod.rs b/vendor/zerovec/src/map/mod.rs
new file mode 100644
index 000000000..fcad0cff7
--- /dev/null
+++ b/vendor/zerovec/src/map/mod.rs
@@ -0,0 +1,23 @@
+// 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 [`ZeroMap`](crate::ZeroMap) for details.
+
+mod borrowed;
+mod kv;
+#[allow(clippy::module_inception)] // module is purely internal
+pub(crate) mod map;
+mod vecs;
+
+#[cfg(feature = "databake")]
+mod databake;
+#[cfg(feature = "serde")]
+mod serde;
+#[cfg(feature = "serde")]
+mod serde_helpers;
+
+pub use crate::ZeroMap;
+pub use borrowed::ZeroMapBorrowed;
+pub use kv::ZeroMapKV;
+pub use vecs::{MutableZeroVecLike, ZeroVecLike};
diff --git a/vendor/zerovec/src/map/serde.rs b/vendor/zerovec/src/map/serde.rs
new file mode 100644
index 000000000..dbe4b433d
--- /dev/null
+++ b/vendor/zerovec/src/map/serde.rs
@@ -0,0 +1,313 @@
+// 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::{MutableZeroVecLike, ZeroMap, ZeroMapBorrowed, ZeroMapKV, ZeroVecLike};
+use core::fmt;
+use core::marker::PhantomData;
+use serde::de::{self, Deserialize, Deserializer, MapAccess, SeqAccess, Visitor};
+#[cfg(feature = "serde")]
+use serde::ser::{Serialize, SerializeMap, SerializeSeq, Serializer};
+
+/// This impl can be made available by enabling the optional `serde` feature of the `zerovec` crate
+#[cfg(feature = "serde")]
+impl<'a, K, V> Serialize for ZeroMap<'a, K, V>
+where
+    K: ZeroMapKV<'a> + Serialize + ?Sized + Ord,
+    V: ZeroMapKV<'a> + Serialize + ?Sized,
+    K::Container: Serialize,
+    V::Container: Serialize,
+{
+    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+    where
+        S: Serializer,
+    {
+        if serializer.is_human_readable() {
+            // Many human-readable formats don't support values other
+            // than numbers and strings as map keys. For them, we can serialize
+            // as a vec of tuples instead
+            if let Some(k) = self.iter_keys().next() {
+                if !K::Container::zvl_get_as_t(k, super::serde_helpers::is_num_or_string) {
+                    let mut seq = serializer.serialize_seq(Some(self.len()))?;
+                    for (k, v) in self.iter() {
+                        K::Container::zvl_get_as_t(k, |k| {
+                            V::Container::zvl_get_as_t(v, |v| seq.serialize_element(&(k, v)))
+                        })?;
+                    }
+                    return seq.end();
+                }
+            }
+            let mut map = serializer.serialize_map(Some(self.len()))?;
+            for (k, v) in self.iter() {
+                K::Container::zvl_get_as_t(k, |k| map.serialize_key(k))?;
+                V::Container::zvl_get_as_t(v, |v| map.serialize_value(v))?;
+            }
+            map.end()
+        } else {
+            (&self.keys, &self.values).serialize(serializer)
+        }
+    }
+}
+
+/// This impl can be made available by enabling the optional `serde` feature of the `zerovec` crate
+#[cfg(feature = "serde")]
+impl<'a, K, V> Serialize for ZeroMapBorrowed<'a, K, V>
+where
+    K: ZeroMapKV<'a> + Serialize + ?Sized + Ord,
+    V: ZeroMapKV<'a> + Serialize + ?Sized,
+    K::Container: Serialize,
+    V::Container: Serialize,
+{
+    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+    where
+        S: Serializer,
+    {
+        ZeroMap::<K, V>::from(*self).serialize(serializer)
+    }
+}
+
+/// Modified example from https://serde.rs/deserialize-map.html
+struct ZeroMapMapVisitor<'a, K, V>
+where
+    K: ZeroMapKV<'a> + ?Sized + Ord,
+    V: ZeroMapKV<'a> + ?Sized,
+{
+    #[allow(clippy::type_complexity)] // it's a marker type, complexity doesn't matter
+    marker: PhantomData<fn() -> (&'a K::OwnedType, &'a V::OwnedType)>,
+}
+
+impl<'a, K, V> ZeroMapMapVisitor<'a, K, V>
+where
+    K: ZeroMapKV<'a> + ?Sized + Ord,
+    V: ZeroMapKV<'a> + ?Sized,
+{
+    fn new() -> Self {
+        ZeroMapMapVisitor {
+            marker: PhantomData,
+        }
+    }
+}
+
+impl<'a, 'de, K, V> Visitor<'de> for ZeroMapMapVisitor<'a, K, V>
+where
+    K: ZeroMapKV<'a> + Ord + ?Sized,
+    V: ZeroMapKV<'a> + ?Sized,
+    K::OwnedType: Deserialize<'de>,
+    V::OwnedType: Deserialize<'de>,
+{
+    type Value = ZeroMap<'a, K, V>;
+
+    fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
+        formatter.write_str("a map produced by ZeroMap")
+    }
+
+    fn visit_seq<S>(self, mut access: S) -> Result<Self::Value, S::Error>
+    where
+        S: SeqAccess<'de>,
+    {
+        let mut map = ZeroMap::with_capacity(access.size_hint().unwrap_or(0));
+
+        // While there are entries remaining in the input, add them
+        // into our map.
+        while let Some((key, value)) = access.next_element::<(K::OwnedType, V::OwnedType)>()? {
+            // Try to append it at the end, hoping for a sorted map.
+            // If not sorted, return an error
+            // a serialized map that came from another ZeroMap
+            if map
+                .try_append(
+                    K::Container::owned_as_t(&key),
+                    V::Container::owned_as_t(&value),
+                )
+                .is_some()
+            {
+                return Err(de::Error::custom(
+                    "ZeroMap's keys must be sorted while deserializing",
+                ));
+            }
+        }
+
+        Ok(map)
+    }
+
+    fn visit_map<M>(self, mut access: M) -> Result<Self::Value, M::Error>
+    where
+        M: MapAccess<'de>,
+    {
+        let mut map = ZeroMap::with_capacity(access.size_hint().unwrap_or(0));
+
+        // While there are entries remaining in the input, add them
+        // into our map.
+        while let Some((key, value)) = access.next_entry::<K::OwnedType, V::OwnedType>()? {
+            // Try to append it at the end, hoping for a sorted map.
+            // If not sorted, return an error
+            // a serialized map that came from another ZeroMap
+            if map
+                .try_append(
+                    K::Container::owned_as_t(&key),
+                    V::Container::owned_as_t(&value),
+                )
+                .is_some()
+            {
+                return Err(de::Error::custom(
+                    "ZeroMap's keys must be sorted while deserializing",
+                ));
+            }
+        }
+
+        Ok(map)
+    }
+}
+
+/// This impl can be made available by enabling the optional `serde` feature of the `zerovec` crate
+impl<'de, 'a, K, V> Deserialize<'de> for ZeroMap<'a, K, V>
+where
+    K: ZeroMapKV<'a> + Ord + ?Sized,
+    V: ZeroMapKV<'a> + ?Sized,
+    K::Container: Deserialize<'de>,
+    V::Container: Deserialize<'de>,
+    K::OwnedType: Deserialize<'de>,
+    V::OwnedType: Deserialize<'de>,
+    'de: 'a,
+{
+    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+    where
+        D: Deserializer<'de>,
+    {
+        if deserializer.is_human_readable() {
+            deserializer.deserialize_any(ZeroMapMapVisitor::<'a, K, V>::new())
+        } else {
+            let (keys, values): (K::Container, V::Container) =
+                Deserialize::deserialize(deserializer)?;
+            if keys.zvl_len() != values.zvl_len() {
+                return Err(de::Error::custom(
+                    "Mismatched key and value sizes in ZeroMap",
+                ));
+            }
+            // #1433: If keys are out of order, treat it as GIGO.
+            debug_assert!(keys.zvl_is_ascending());
+            Ok(Self { keys, values })
+        }
+    }
+}
+
+// /// This impl can be made available by enabling the optional `serde` feature of the `zerovec` crate
+impl<'de, 'a, K, V> Deserialize<'de> for ZeroMapBorrowed<'a, K, V>
+where
+    K: ZeroMapKV<'a> + Ord + ?Sized,
+    V: ZeroMapKV<'a> + ?Sized,
+    K::Container: Deserialize<'de>,
+    V::Container: Deserialize<'de>,
+    K::OwnedType: Deserialize<'de>,
+    V::OwnedType: Deserialize<'de>,
+    'de: 'a,
+{
+    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+    where
+        D: Deserializer<'de>,
+    {
+        if deserializer.is_human_readable() {
+            Err(de::Error::custom(
+                "ZeroMapBorrowed cannot be deserialized from human-readable formats",
+            ))
+        } else {
+            let deserialized: ZeroMap<'a, K, V> = ZeroMap::deserialize(deserializer)?;
+            let keys = if let Some(keys) = deserialized.keys.zvl_as_borrowed_inner() {
+                keys
+            } else {
+                return Err(de::Error::custom(
+                    "ZeroMapBorrowed can only deserialize in zero-copy ways",
+                ));
+            };
+            let values = if let Some(values) = deserialized.values.zvl_as_borrowed_inner() {
+                values
+            } else {
+                return Err(de::Error::custom(
+                    "ZeroMapBorrowed can only deserialize in zero-copy ways",
+                ));
+            };
+            Ok(Self { keys, values })
+        }
+    }
+}
+
+#[cfg(test)]
+#[allow(non_camel_case_types)]
+mod test {
+    use crate::{map::ZeroMapBorrowed, ZeroMap};
+
+    #[derive(serde::Serialize, serde::Deserialize)]
+    struct DeriveTest_ZeroMap<'data> {
+        #[serde(borrow)]
+        _data: ZeroMap<'data, str, [u8]>,
+    }
+
+    #[derive(serde::Serialize, serde::Deserialize)]
+    struct DeriveTest_ZeroMapBorrowed<'data> {
+        #[serde(borrow)]
+        _data: ZeroMapBorrowed<'data, str, [u8]>,
+    }
+
+    const JSON_STR: &str = "{\"1\":\"uno\",\"2\":\"dos\",\"3\":\"tres\"}";
+    const BINCODE_BYTES: &[u8] = &[
+        12, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 20, 0, 0, 0, 0, 0, 0, 0, 3, 0,
+        0, 0, 0, 0, 3, 0, 6, 0, 117, 110, 111, 100, 111, 115, 116, 114, 101, 115,
+    ];
+
+    fn make_map() -> ZeroMap<'static, u32, str> {
+        let mut map = ZeroMap::new();
+        map.insert(&1, "uno");
+        map.insert(&2, "dos");
+        map.insert(&3, "tres");
+        map
+    }
+
+    #[test]
+    fn test_serde_json() {
+        let map = make_map();
+        let json_str = serde_json::to_string(&map).expect("serialize");
+        assert_eq!(JSON_STR, json_str);
+        let new_map: ZeroMap<u32, str> = serde_json::from_str(&json_str).expect("deserialize");
+        assert_eq!(
+            new_map.iter().collect::<Vec<_>>(),
+            map.iter().collect::<Vec<_>>()
+        );
+    }
+
+    #[test]
+    fn test_serde_json_complex_key() {
+        let mut map = ZeroMap::new();
+        map.insert(&(1, 1), "uno");
+        map.insert(&(2, 2), "dos");
+        map.insert(&(3, 3), "tres");
+        let json_str = serde_json::to_string(&map).expect("serialize");
+        assert_eq!(
+            json_str,
+            "[[[1,1],\"uno\"],[[2,2],\"dos\"],[[3,3],\"tres\"]]"
+        );
+        let new_map: ZeroMap<(u32, u32), str> =
+            serde_json::from_str(&json_str).expect("deserialize");
+        assert_eq!(
+            new_map.iter().collect::<Vec<_>>(),
+            map.iter().collect::<Vec<_>>()
+        );
+    }
+
+    #[test]
+    fn test_bincode() {
+        let map = make_map();
+        let bincode_bytes = bincode::serialize(&map).expect("serialize");
+        assert_eq!(BINCODE_BYTES, bincode_bytes);
+        let new_map: ZeroMap<u32, str> = bincode::deserialize(&bincode_bytes).expect("deserialize");
+        assert_eq!(
+            new_map.iter().collect::<Vec<_>>(),
+            map.iter().collect::<Vec<_>>()
+        );
+
+        let new_map: ZeroMapBorrowed<u32, str> =
+            bincode::deserialize(&bincode_bytes).expect("deserialize");
+        assert_eq!(
+            new_map.iter().collect::<Vec<_>>(),
+            map.iter().collect::<Vec<_>>()
+        );
+    }
+}
diff --git a/vendor/zerovec/src/map/serde_helpers.rs b/vendor/zerovec/src/map/serde_helpers.rs
new file mode 100644
index 000000000..b1ead938a
--- /dev/null
+++ b/vendor/zerovec/src/map/serde_helpers.rs
@@ -0,0 +1,168 @@
+// 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 ).
+
+// @@@@@@@@@@@@@@@@
+// THIS FILE IS SHARED BETWEEN LITEMAP AND ZEROVEC. PLEASE KEEP IT IN SYNC FOR ALL EDITS
+// @@@@@@@@@@@@@@@@
+
+use serde::ser::{Impossible, Serialize, Serializer};
+
+pub fn is_num_or_string<T: Serialize + ?Sized>(k: &T) -> bool {
+    // Serializer that errors in the same cases as serde_json::ser::MapKeySerializer
+    struct MapKeySerializerDryRun;
+    impl Serializer for MapKeySerializerDryRun {
+        type Ok = ();
+        // Singleton error type that implements serde::ser::Error
+        type Error = core::fmt::Error;
+
+        type SerializeSeq = Impossible<(), Self::Error>;
+        type SerializeTuple = Impossible<(), Self::Error>;
+        type SerializeTupleStruct = Impossible<(), Self::Error>;
+        type SerializeTupleVariant = Impossible<(), Self::Error>;
+        type SerializeMap = Impossible<(), Self::Error>;
+        type SerializeStruct = Impossible<(), Self::Error>;
+        type SerializeStructVariant = Impossible<(), Self::Error>;
+
+        fn serialize_str(self, _value: &str) -> Result<Self::Ok, Self::Error> {
+            Ok(())
+        }
+        fn serialize_unit_variant(
+            self,
+            _name: &'static str,
+            _variant_index: u32,
+            _variant: &'static str,
+        ) -> Result<Self::Ok, Self::Error> {
+            Ok(())
+        }
+        fn serialize_newtype_struct<T: Serialize + ?Sized>(
+            self,
+            _name: &'static str,
+            value: &T,
+        ) -> Result<Self::Ok, Self::Error> {
+            // Recurse
+            value.serialize(self)
+        }
+        fn serialize_bool(self, _value: bool) -> Result<Self::Ok, Self::Error> {
+            Err(core::fmt::Error)
+        }
+        fn serialize_i8(self, _value: i8) -> Result<Self::Ok, Self::Error> {
+            Ok(())
+        }
+        fn serialize_i16(self, _value: i16) -> Result<Self::Ok, Self::Error> {
+            Ok(())
+        }
+        fn serialize_i32(self, _value: i32) -> Result<Self::Ok, Self::Error> {
+            Ok(())
+        }
+        fn serialize_i64(self, _value: i64) -> Result<Self::Ok, Self::Error> {
+            Ok(())
+        }
+        serde::serde_if_integer128! {
+            fn serialize_i128(self, _value: i128) -> Result<Self::Ok, Self::Error> {
+                Ok(())
+            }
+        }
+        fn serialize_u8(self, _value: u8) -> Result<Self::Ok, Self::Error> {
+            Ok(())
+        }
+        fn serialize_u16(self, _value: u16) -> Result<Self::Ok, Self::Error> {
+            Ok(())
+        }
+        fn serialize_u32(self, _value: u32) -> Result<Self::Ok, Self::Error> {
+            Ok(())
+        }
+        fn serialize_u64(self, _value: u64) -> Result<Self::Ok, Self::Error> {
+            Ok(())
+        }
+        serde::serde_if_integer128! {
+            fn serialize_u128(self, _value: u128) -> Result<Self::Ok, Self::Error> {
+                Ok(())
+            }
+        }
+        fn serialize_f32(self, _value: f32) -> Result<Self::Ok, Self::Error> {
+            Err(core::fmt::Error)
+        }
+        fn serialize_f64(self, _value: f64) -> Result<Self::Ok, Self::Error> {
+            Err(core::fmt::Error)
+        }
+        fn serialize_char(self, _value: char) -> Result<Self::Ok, Self::Error> {
+            Ok(())
+        }
+        fn serialize_bytes(self, _value: &[u8]) -> Result<Self::Ok, Self::Error> {
+            Err(core::fmt::Error)
+        }
+        fn serialize_unit(self) -> Result<Self::Ok, Self::Error> {
+            Err(core::fmt::Error)
+        }
+        fn serialize_unit_struct(self, _name: &'static str) -> Result<Self::Ok, Self::Error> {
+            Err(core::fmt::Error)
+        }
+        fn serialize_newtype_variant<T: Serialize + ?Sized>(
+            self,
+            _name: &'static str,
+            _variant_index: u32,
+            _variant: &'static str,
+            _value: &T,
+        ) -> Result<Self::Ok, Self::Error> {
+            Err(core::fmt::Error)
+        }
+        fn serialize_none(self) -> Result<Self::Ok, Self::Error> {
+            Err(core::fmt::Error)
+        }
+        fn serialize_some<T: Serialize + ?Sized>(
+            self,
+            _value: &T,
+        ) -> Result<Self::Ok, Self::Error> {
+            Err(core::fmt::Error)
+        }
+        fn serialize_seq(self, _len: Option<usize>) -> Result<Self::SerializeSeq, Self::Error> {
+            Err(core::fmt::Error)
+        }
+        fn serialize_tuple(self, _len: usize) -> Result<Self::SerializeTuple, Self::Error> {
+            Err(core::fmt::Error)
+        }
+        fn serialize_tuple_struct(
+            self,
+            _name: &'static str,
+            _len: usize,
+        ) -> Result<Self::SerializeTupleStruct, Self::Error> {
+            Err(core::fmt::Error)
+        }
+        fn serialize_tuple_variant(
+            self,
+            _name: &'static str,
+            _variant_index: u32,
+            _variant: &'static str,
+            _len: usize,
+        ) -> Result<Self::SerializeTupleVariant, Self::Error> {
+            Err(core::fmt::Error)
+        }
+        fn serialize_map(self, _len: Option<usize>) -> Result<Self::SerializeMap, Self::Error> {
+            Err(core::fmt::Error)
+        }
+        fn serialize_struct(
+            self,
+            _name: &'static str,
+            _len: usize,
+        ) -> Result<Self::SerializeStruct, Self::Error> {
+            Err(core::fmt::Error)
+        }
+        fn serialize_struct_variant(
+            self,
+            _name: &'static str,
+            _variant_index: u32,
+            _variant: &'static str,
+            _len: usize,
+        ) -> Result<Self::SerializeStructVariant, Self::Error> {
+            Err(core::fmt::Error)
+        }
+        fn collect_str<T: core::fmt::Display + ?Sized>(
+            self,
+            _value: &T,
+        ) -> Result<Self::Ok, Self::Error> {
+            Ok(())
+        }
+    }
+    k.serialize(MapKeySerializerDryRun).is_ok()
+}
diff --git a/vendor/zerovec/src/map/vecs.rs b/vendor/zerovec/src/map/vecs.rs
new file mode 100644
index 000000000..b460e5967
--- /dev/null
+++ b/vendor/zerovec/src/map/vecs.rs
@@ -0,0 +1,727 @@
+// 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 crate::varzerovec::owned::VarZeroVecOwned;
+use crate::vecs::{FlexZeroSlice, FlexZeroVec, FlexZeroVecOwned, VarZeroVecFormat};
+use crate::{VarZeroSlice, VarZeroVec};
+use crate::{ZeroSlice, ZeroVec};
+use alloc::boxed::Box;
+use alloc::vec::Vec;
+use core::cmp::Ordering;
+use core::mem;
+use core::ops::Range;
+
+/// Trait abstracting over [`ZeroVec`] and [`VarZeroVec`], for use in [`ZeroMap`](super::ZeroMap). **You
+/// should not be implementing or calling this trait directly.**
+///
+/// The T type is the type received by [`Self::zvl_binary_search()`], as well as the one used
+/// for human-readable serialization.
+///
+/// Methods are prefixed with `zvl_*` to avoid clashes with methods on the types themselves
+pub trait ZeroVecLike<T: ?Sized> {
+    /// The type returned by `Self::get()`
+    type GetType: ?Sized + 'static;
+    /// A fully borrowed version of this
+    type SliceVariant: ZeroVecLike<T, GetType = Self::GetType> + ?Sized;
+
+    /// Create a new, empty borrowed variant
+    fn zvl_new_borrowed() -> &'static Self::SliceVariant;
+
+    /// Search for a key in a sorted vector, returns `Ok(index)` if found,
+    /// returns `Err(insert_index)` if not found, where `insert_index` is the
+    /// index where it should be inserted to maintain sort order.
+    fn zvl_binary_search(&self, k: &T) -> Result<usize, usize>
+    where
+        T: Ord;
+    /// Search for a key within a certain range in a sorted vector.
+    /// Returns `None` if the range is out of bounds, and
+    /// `Ok` or `Err` in the same way as `zvl_binary_search`.
+    /// Indices are returned relative to the start of the range.
+    fn zvl_binary_search_in_range(
+        &self,
+        k: &T,
+        range: Range<usize>,
+    ) -> Option<Result<usize, usize>>
+    where
+        T: Ord;
+
+    /// Search for a key in a sorted vector by a predicate, returns `Ok(index)` if found,
+    /// returns `Err(insert_index)` if not found, where `insert_index` is the
+    /// index where it should be inserted to maintain sort order.
+    fn zvl_binary_search_by(&self, predicate: impl FnMut(&T) -> Ordering) -> Result<usize, usize>;
+    /// Search for a key within a certain range in a sorted vector by a predicate.
+    /// Returns `None` if the range is out of bounds, and
+    /// `Ok` or `Err` in the same way as `zvl_binary_search`.
+    /// Indices are returned relative to the start of the range.
+    fn zvl_binary_search_in_range_by(
+        &self,
+        predicate: impl FnMut(&T) -> Ordering,
+        range: Range<usize>,
+    ) -> Option<Result<usize, usize>>;
+
+    /// Get element at `index`
+    fn zvl_get(&self, index: usize) -> Option<&Self::GetType>;
+    /// The length of this vector
+    fn zvl_len(&self) -> usize;
+    /// Check if this vector is in ascending order according to `T`s `Ord` impl
+    fn zvl_is_ascending(&self) -> bool
+    where
+        T: Ord,
+    {
+        if let Some(first) = self.zvl_get(0) {
+            let mut prev = first;
+            for i in 1..self.zvl_len() {
+                #[allow(clippy::unwrap_used)] // looping over the valid indices
+                let curr = self.zvl_get(i).unwrap();
+                if Self::get_cmp_get(prev, curr) != Ordering::Less {
+                    return false;
+                }
+                prev = curr;
+            }
+        }
+        true
+    }
+    /// Check if this vector is empty
+    fn zvl_is_empty(&self) -> bool {
+        self.zvl_len() == 0
+    }
+
+    /// Construct a borrowed variant by borrowing from `&self`.
+    ///
+    /// This function behaves like `&'b self -> Self::SliceVariant<'b>`,
+    /// where `'b` is the lifetime of the reference to this object.
+    ///
+    /// Note: We rely on the compiler recognizing `'a` and `'b` as covariant and
+    /// casting `&'b Self<'a>` to `&'b Self<'b>` when this gets called, which works
+    /// out for `ZeroVec` and `VarZeroVec` containers just fine.
+    fn zvl_as_borrowed(&self) -> &Self::SliceVariant;
+
+    /// Compare this type with a `Self::GetType`. This must produce the same result as
+    /// if `g` were converted to `Self`
+    #[inline]
+    fn t_cmp_get(t: &T, g: &Self::GetType) -> Ordering
+    where
+        T: Ord,
+    {
+        Self::zvl_get_as_t(g, |g| t.cmp(g))
+    }
+
+    /// Compare two values of `Self::GetType`. This must produce the same result as
+    /// if both `a` and `b` were converted to `Self`
+    #[inline]
+    fn get_cmp_get(a: &Self::GetType, b: &Self::GetType) -> Ordering
+    where
+        T: Ord,
+    {
+        Self::zvl_get_as_t(a, |a| Self::zvl_get_as_t(b, |b| a.cmp(b)))
+    }
+
+    /// Obtain a reference to T, passed to a closure
+    ///
+    /// This uses a callback because it's not possible to return owned-or-borrowed
+    /// types without GATs
+    ///
+    /// Impls should guarantee that the callback function is be called exactly once.
+    fn zvl_get_as_t<R>(g: &Self::GetType, f: impl FnOnce(&T) -> R) -> R;
+}
+
+/// Trait abstracting over [`ZeroVec`] and [`VarZeroVec`], for use in [`ZeroMap`](super::ZeroMap). **You
+/// should not be implementing or calling this trait directly.**
+///
+/// This trait augments [`ZeroVecLike`] with methods allowing for mutation of the underlying
+/// vector for owned vector types.
+///
+/// Methods are prefixed with `zvl_*` to avoid clashes with methods on the types themselves
+pub trait MutableZeroVecLike<'a, T: ?Sized>: ZeroVecLike<T> {
+    /// The type returned by `Self::remove()` and `Self::replace()`
+    type OwnedType;
+
+    /// Insert an element at `index`
+    fn zvl_insert(&mut self, index: usize, value: &T);
+    /// Remove the element at `index` (panicking if nonexistant)
+    fn zvl_remove(&mut self, index: usize) -> Self::OwnedType;
+    /// Replace the element at `index` with another one, returning the old element
+    fn zvl_replace(&mut self, index: usize, value: &T) -> Self::OwnedType;
+    /// Push an element to the end of this vector
+    fn zvl_push(&mut self, value: &T);
+    /// Create a new, empty vector, with given capacity
+    fn zvl_with_capacity(cap: usize) -> Self;
+    /// Remove all elements from the vector
+    fn zvl_clear(&mut self);
+    /// Reserve space for `addl` additional elements
+    fn zvl_reserve(&mut self, addl: usize);
+    /// Applies the permutation such that `before.zvl_get(permutation[i]) == after.zvl_get(i)`.
+    ///
+    /// # Panics
+    /// If `permutation` is not a valid permutation of length `zvl_len()`.
+    fn zvl_permute(&mut self, permutation: &mut [usize]);
+
+    /// Convert an owned value to a borrowed T
+    fn owned_as_t(o: &Self::OwnedType) -> &T;
+
+    /// Construct from the borrowed version of the type
+    ///
+    /// These are useful to ensure serialization parity between borrowed and owned versions
+    fn zvl_from_borrowed(b: &'a Self::SliceVariant) -> Self;
+    /// Extract the inner borrowed variant if possible. Returns `None` if the data is owned.
+    ///
+    /// This function behaves like `&'_ self -> Self::SliceVariant<'a>`,
+    /// where `'a` is the lifetime of this object's borrowed data.
+    ///
+    /// This function is similar to matching the `Borrowed` variant of `ZeroVec`
+    /// or `VarZeroVec`, returning the inner borrowed type.
+    fn zvl_as_borrowed_inner(&self) -> Option<&'a Self::SliceVariant>;
+}
+
+impl<'a, T> ZeroVecLike<T> for ZeroVec<'a, T>
+where
+    T: 'a + AsULE + Copy,
+{
+    type GetType = T::ULE;
+    type SliceVariant = ZeroSlice<T>;
+
+    fn zvl_new_borrowed() -> &'static Self::SliceVariant {
+        ZeroSlice::<T>::new_empty()
+    }
+    fn zvl_binary_search(&self, k: &T) -> Result<usize, usize>
+    where
+        T: Ord,
+    {
+        ZeroSlice::binary_search(self, k)
+    }
+    fn zvl_binary_search_in_range(&self, k: &T, range: Range<usize>) -> Option<Result<usize, usize>>
+    where
+        T: Ord,
+    {
+        let zs: &ZeroSlice<T> = &*self;
+        zs.zvl_binary_search_in_range(k, range)
+    }
+    fn zvl_binary_search_by(
+        &self,
+        mut predicate: impl FnMut(&T) -> Ordering,
+    ) -> Result<usize, usize> {
+        ZeroSlice::binary_search_by(self, |probe| predicate(&probe))
+    }
+    fn zvl_binary_search_in_range_by(
+        &self,
+        predicate: impl FnMut(&T) -> Ordering,
+        range: Range<usize>,
+    ) -> Option<Result<usize, usize>> {
+        let zs: &ZeroSlice<T> = &*self;
+        zs.zvl_binary_search_in_range_by(predicate, range)
+    }
+    fn zvl_get(&self, index: usize) -> Option<&T::ULE> {
+        self.get_ule_ref(index)
+    }
+    fn zvl_len(&self) -> usize {
+        ZeroSlice::len(self)
+    }
+
+    fn zvl_as_borrowed(&self) -> &ZeroSlice<T> {
+        &*self
+    }
+
+    #[inline]
+    fn zvl_get_as_t<R>(g: &Self::GetType, f: impl FnOnce(&T) -> R) -> R {
+        f(&T::from_unaligned(*g))
+    }
+}
+
+impl<T> ZeroVecLike<T> for ZeroSlice<T>
+where
+    T: AsULE + Copy,
+{
+    type GetType = T::ULE;
+    type SliceVariant = ZeroSlice<T>;
+
+    fn zvl_new_borrowed() -> &'static Self::SliceVariant {
+        ZeroSlice::<T>::new_empty()
+    }
+    fn zvl_binary_search(&self, k: &T) -> Result<usize, usize>
+    where
+        T: Ord,
+    {
+        ZeroSlice::binary_search(self, k)
+    }
+    fn zvl_binary_search_in_range(&self, k: &T, range: Range<usize>) -> Option<Result<usize, usize>>
+    where
+        T: Ord,
+    {
+        let subslice = self.get_subslice(range)?;
+        Some(ZeroSlice::binary_search(subslice, k))
+    }
+    fn zvl_binary_search_by(
+        &self,
+        mut predicate: impl FnMut(&T) -> Ordering,
+    ) -> Result<usize, usize> {
+        ZeroSlice::binary_search_by(self, |probe| predicate(&probe))
+    }
+    fn zvl_binary_search_in_range_by(
+        &self,
+        mut predicate: impl FnMut(&T) -> Ordering,
+        range: Range<usize>,
+    ) -> Option<Result<usize, usize>> {
+        let subslice = self.get_subslice(range)?;
+        Some(ZeroSlice::binary_search_by(subslice, |probe| {
+            predicate(&probe)
+        }))
+    }
+    fn zvl_get(&self, index: usize) -> Option<&T::ULE> {
+        self.get_ule_ref(index)
+    }
+    fn zvl_len(&self) -> usize {
+        ZeroSlice::len(self)
+    }
+
+    fn zvl_as_borrowed(&self) -> &ZeroSlice<T> {
+        self
+    }
+
+    #[inline]
+    fn zvl_get_as_t<R>(g: &Self::GetType, f: impl FnOnce(&T) -> R) -> R {
+        f(&T::from_unaligned(*g))
+    }
+}
+
+impl<'a, T> MutableZeroVecLike<'a, T> for ZeroVec<'a, T>
+where
+    T: AsULE + Copy + 'static,
+{
+    type OwnedType = T;
+    fn zvl_insert(&mut self, index: usize, value: &T) {
+        self.with_mut(|v| v.insert(index, value.to_unaligned()))
+    }
+    fn zvl_remove(&mut self, index: usize) -> T {
+        T::from_unaligned(self.with_mut(|v| v.remove(index)))
+    }
+    fn zvl_replace(&mut self, index: usize, value: &T) -> T {
+        #[allow(clippy::indexing_slicing)]
+        let unaligned = self.with_mut(|vec| {
+            debug_assert!(index < vec.len());
+            mem::replace(&mut vec[index], value.to_unaligned())
+        });
+        T::from_unaligned(unaligned)
+    }
+    fn zvl_push(&mut self, value: &T) {
+        self.with_mut(|v| v.push(value.to_unaligned()))
+    }
+    fn zvl_with_capacity(cap: usize) -> Self {
+        if cap == 0 {
+            ZeroVec::new()
+        } else {
+            ZeroVec::new_owned(Vec::with_capacity(cap))
+        }
+    }
+    fn zvl_clear(&mut self) {
+        self.with_mut(|v| v.clear())
+    }
+    fn zvl_reserve(&mut self, addl: usize) {
+        self.with_mut(|v| v.reserve(addl))
+    }
+
+    fn owned_as_t(o: &Self::OwnedType) -> &T {
+        o
+    }
+
+    fn zvl_from_borrowed(b: &'a ZeroSlice<T>) -> Self {
+        b.as_zerovec()
+    }
+    fn zvl_as_borrowed_inner(&self) -> Option<&'a ZeroSlice<T>> {
+        self.as_maybe_borrowed()
+    }
+
+    #[allow(clippy::indexing_slicing)] // documented panic
+    fn zvl_permute(&mut self, permutation: &mut [usize]) {
+        assert_eq!(permutation.len(), self.zvl_len());
+
+        let vec = self.to_mut_slice();
+
+        for cycle_start in 0..permutation.len() {
+            let mut curr = cycle_start;
+            let mut next = permutation[curr];
+
+            while next != cycle_start {
+                vec.swap(curr, next);
+                // Make curr a self-cycle so we don't use it as a cycle_start later
+                permutation[curr] = curr;
+                curr = next;
+                next = permutation[next];
+            }
+            permutation[curr] = curr;
+        }
+    }
+}
+
+impl<'a, T, F> ZeroVecLike<T> for VarZeroVec<'a, T, F>
+where
+    T: VarULE,
+    T: ?Sized,
+    F: VarZeroVecFormat,
+{
+    type GetType = T;
+    type SliceVariant = VarZeroSlice<T, F>;
+
+    fn zvl_new_borrowed() -> &'static Self::SliceVariant {
+        VarZeroSlice::<T, F>::new_empty()
+    }
+    fn zvl_binary_search(&self, k: &T) -> Result<usize, usize>
+    where
+        T: Ord,
+    {
+        self.binary_search(k)
+    }
+    fn zvl_binary_search_in_range(&self, k: &T, range: Range<usize>) -> Option<Result<usize, usize>>
+    where
+        T: Ord,
+    {
+        self.binary_search_in_range(k, range)
+    }
+    fn zvl_binary_search_by(&self, predicate: impl FnMut(&T) -> Ordering) -> Result<usize, usize> {
+        self.binary_search_by(predicate)
+    }
+    fn zvl_binary_search_in_range_by(
+        &self,
+        predicate: impl FnMut(&T) -> Ordering,
+        range: Range<usize>,
+    ) -> Option<Result<usize, usize>> {
+        self.binary_search_in_range_by(predicate, range)
+    }
+    fn zvl_get(&self, index: usize) -> Option<&T> {
+        self.get(index)
+    }
+    fn zvl_len(&self) -> usize {
+        self.len()
+    }
+
+    fn zvl_as_borrowed(&self) -> &VarZeroSlice<T, F> {
+        self.as_slice()
+    }
+
+    #[inline]
+    fn zvl_get_as_t<R>(g: &Self::GetType, f: impl FnOnce(&T) -> R) -> R {
+        f(g)
+    }
+}
+
+impl<T, F> ZeroVecLike<T> for VarZeroSlice<T, F>
+where
+    T: VarULE,
+    T: ?Sized,
+    F: VarZeroVecFormat,
+{
+    type GetType = T;
+    type SliceVariant = VarZeroSlice<T, F>;
+
+    fn zvl_new_borrowed() -> &'static Self::SliceVariant {
+        VarZeroSlice::<T, F>::new_empty()
+    }
+    fn zvl_binary_search(&self, k: &T) -> Result<usize, usize>
+    where
+        T: Ord,
+    {
+        self.binary_search(k)
+    }
+    fn zvl_binary_search_in_range(&self, k: &T, range: Range<usize>) -> Option<Result<usize, usize>>
+    where
+        T: Ord,
+    {
+        self.binary_search_in_range(k, range)
+    }
+    fn zvl_binary_search_by(&self, predicate: impl FnMut(&T) -> Ordering) -> Result<usize, usize> {
+        self.binary_search_by(predicate)
+    }
+    fn zvl_binary_search_in_range_by(
+        &self,
+        predicate: impl FnMut(&T) -> Ordering,
+        range: Range<usize>,
+    ) -> Option<Result<usize, usize>> {
+        self.binary_search_in_range_by(predicate, range)
+    }
+    fn zvl_get(&self, index: usize) -> Option<&T> {
+        self.get(index)
+    }
+    fn zvl_len(&self) -> usize {
+        self.len()
+    }
+
+    fn zvl_as_borrowed(&self) -> &VarZeroSlice<T, F> {
+        self
+    }
+
+    #[inline]
+    fn zvl_get_as_t<R>(g: &Self::GetType, f: impl FnOnce(&T) -> R) -> R {
+        f(g)
+    }
+}
+
+impl<'a, T, F> MutableZeroVecLike<'a, T> for VarZeroVec<'a, T, F>
+where
+    T: VarULE,
+    T: ?Sized,
+    F: VarZeroVecFormat,
+{
+    type OwnedType = Box<T>;
+    fn zvl_insert(&mut self, index: usize, value: &T) {
+        self.make_mut().insert(index, value)
+    }
+    fn zvl_remove(&mut self, index: usize) -> Box<T> {
+        let vec = self.make_mut();
+        debug_assert!(index < vec.len());
+        #[allow(clippy::unwrap_used)]
+        let old = vec.get(index).unwrap().to_boxed();
+        vec.remove(index);
+        old
+    }
+    fn zvl_replace(&mut self, index: usize, value: &T) -> Box<T> {
+        let vec = self.make_mut();
+        debug_assert!(index < vec.len());
+        #[allow(clippy::unwrap_used)]
+        let old = vec.get(index).unwrap().to_boxed();
+        vec.replace(index, value);
+        old
+    }
+    fn zvl_push(&mut self, value: &T) {
+        let len = self.len();
+        self.make_mut().insert(len, value)
+    }
+    fn zvl_with_capacity(cap: usize) -> Self {
+        if cap == 0 {
+            VarZeroVec::new()
+        } else {
+            VarZeroVec::Owned(VarZeroVecOwned::with_capacity(cap))
+        }
+    }
+    fn zvl_clear(&mut self) {
+        self.make_mut().clear()
+    }
+    fn zvl_reserve(&mut self, addl: usize) {
+        self.make_mut().reserve(addl)
+    }
+
+    fn owned_as_t(o: &Self::OwnedType) -> &T {
+        o
+    }
+
+    fn zvl_from_borrowed(b: &'a VarZeroSlice<T, F>) -> Self {
+        b.as_varzerovec()
+    }
+    fn zvl_as_borrowed_inner(&self) -> Option<&'a VarZeroSlice<T, F>> {
+        if let VarZeroVec::Borrowed(b) = *self {
+            Some(b)
+        } else {
+            None
+        }
+    }
+
+    #[allow(clippy::unwrap_used)] // documented panic
+    fn zvl_permute(&mut self, permutation: &mut [usize]) {
+        assert_eq!(permutation.len(), self.zvl_len());
+
+        let mut result = VarZeroVecOwned::new();
+        for &i in permutation.iter() {
+            result.push(self.get(i).unwrap());
+        }
+        *self = VarZeroVec::Owned(result);
+    }
+}
+
+impl<'a> ZeroVecLike<usize> for FlexZeroVec<'a> {
+    type GetType = [u8];
+    type SliceVariant = FlexZeroSlice;
+
+    fn zvl_new_borrowed() -> &'static Self::SliceVariant {
+        FlexZeroSlice::new_empty()
+    }
+    fn zvl_binary_search(&self, k: &usize) -> Result<usize, usize> {
+        FlexZeroSlice::binary_search(self, *k)
+    }
+    fn zvl_binary_search_in_range(
+        &self,
+        k: &usize,
+        range: Range<usize>,
+    ) -> Option<Result<usize, usize>> {
+        FlexZeroSlice::binary_search_in_range(self, *k, range)
+    }
+    fn zvl_binary_search_by(
+        &self,
+        mut predicate: impl FnMut(&usize) -> Ordering,
+    ) -> Result<usize, usize> {
+        FlexZeroSlice::binary_search_by(self, |probe| predicate(&probe))
+    }
+    fn zvl_binary_search_in_range_by(
+        &self,
+        mut predicate: impl FnMut(&usize) -> Ordering,
+        range: Range<usize>,
+    ) -> Option<Result<usize, usize>> {
+        FlexZeroSlice::binary_search_in_range_by(self, |probe| predicate(&probe), range)
+    }
+    fn zvl_get(&self, index: usize) -> Option<&[u8]> {
+        self.get_chunk(index)
+    }
+    fn zvl_len(&self) -> usize {
+        FlexZeroSlice::len(self)
+    }
+
+    fn zvl_as_borrowed(&self) -> &FlexZeroSlice {
+        &*self
+    }
+
+    #[inline]
+    fn zvl_get_as_t<R>(g: &[u8], f: impl FnOnce(&usize) -> R) -> R {
+        f(&crate::chunk_to_usize(g, g.len()))
+    }
+}
+
+impl ZeroVecLike<usize> for FlexZeroSlice {
+    type GetType = [u8];
+    type SliceVariant = FlexZeroSlice;
+
+    fn zvl_new_borrowed() -> &'static Self::SliceVariant {
+        FlexZeroSlice::new_empty()
+    }
+    fn zvl_binary_search(&self, k: &usize) -> Result<usize, usize> {
+        FlexZeroSlice::binary_search(self, *k)
+    }
+    fn zvl_binary_search_in_range(
+        &self,
+        k: &usize,
+        range: Range<usize>,
+    ) -> Option<Result<usize, usize>> {
+        FlexZeroSlice::binary_search_in_range(self, *k, range)
+    }
+    fn zvl_binary_search_by(
+        &self,
+        mut predicate: impl FnMut(&usize) -> Ordering,
+    ) -> Result<usize, usize> {
+        FlexZeroSlice::binary_search_by(self, |probe| predicate(&probe))
+    }
+    fn zvl_binary_search_in_range_by(
+        &self,
+        mut predicate: impl FnMut(&usize) -> Ordering,
+        range: Range<usize>,
+    ) -> Option<Result<usize, usize>> {
+        FlexZeroSlice::binary_search_in_range_by(self, |probe| predicate(&probe), range)
+    }
+    fn zvl_get(&self, index: usize) -> Option<&[u8]> {
+        self.get_chunk(index)
+    }
+    fn zvl_len(&self) -> usize {
+        FlexZeroSlice::len(self)
+    }
+
+    fn zvl_as_borrowed(&self) -> &FlexZeroSlice {
+        self
+    }
+
+    #[inline]
+    fn zvl_get_as_t<R>(g: &Self::GetType, f: impl FnOnce(&usize) -> R) -> R {
+        f(&crate::chunk_to_usize(g, g.len()))
+    }
+}
+
+impl<'a> MutableZeroVecLike<'a, usize> for FlexZeroVec<'a> {
+    type OwnedType = usize;
+    fn zvl_insert(&mut self, index: usize, value: &usize) {
+        self.to_mut().insert(index, *value)
+    }
+    fn zvl_remove(&mut self, index: usize) -> usize {
+        self.to_mut().remove(index)
+    }
+    fn zvl_replace(&mut self, index: usize, value: &usize) -> usize {
+        // TODO(#2028): Make this a single operation instead of two operations.
+        let mutable = self.to_mut();
+        let old_value = mutable.remove(index);
+        mutable.insert(index, *value);
+        old_value
+    }
+    fn zvl_push(&mut self, value: &usize) {
+        self.to_mut().push(*value)
+    }
+    fn zvl_with_capacity(_cap: usize) -> Self {
+        // There is no `FlexZeroVec::with_capacity()` because it is variable-width
+        FlexZeroVec::Owned(FlexZeroVecOwned::new_empty())
+    }
+    fn zvl_clear(&mut self) {
+        self.to_mut().clear()
+    }
+    fn zvl_reserve(&mut self, _addl: usize) {
+        // There is no `FlexZeroVec::reserve()` because it is variable-width
+    }
+
+    fn owned_as_t(o: &Self::OwnedType) -> &usize {
+        o
+    }
+
+    fn zvl_from_borrowed(b: &'a FlexZeroSlice) -> Self {
+        b.as_flexzerovec()
+    }
+    fn zvl_as_borrowed_inner(&self) -> Option<&'a FlexZeroSlice> {
+        if let FlexZeroVec::Borrowed(b) = *self {
+            Some(b)
+        } else {
+            None
+        }
+    }
+
+    #[allow(clippy::unwrap_used)] // documented panic
+    fn zvl_permute(&mut self, permutation: &mut [usize]) {
+        assert_eq!(permutation.len(), self.zvl_len());
+        *self = permutation.iter().map(|&i| self.get(i).unwrap()).collect();
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+
+    #[test]
+    fn test_zerovec_binary_search_in_range() {
+        let zv: ZeroVec<u16> = ZeroVec::from_slice_or_alloc(&[11, 22, 33, 44, 55, 66, 77]);
+
+        // Full range search
+        assert_eq!(zv.zvl_binary_search_in_range(&11, 0..7), Some(Ok(0)));
+        assert_eq!(zv.zvl_binary_search_in_range(&12, 0..7), Some(Err(1)));
+        assert_eq!(zv.zvl_binary_search_in_range(&44, 0..7), Some(Ok(3)));
+        assert_eq!(zv.zvl_binary_search_in_range(&45, 0..7), Some(Err(4)));
+        assert_eq!(zv.zvl_binary_search_in_range(&77, 0..7), Some(Ok(6)));
+        assert_eq!(zv.zvl_binary_search_in_range(&78, 0..7), Some(Err(7)));
+
+        // Out-of-range search
+        assert_eq!(zv.zvl_binary_search_in_range(&44, 0..2), Some(Err(2)));
+        assert_eq!(zv.zvl_binary_search_in_range(&44, 5..7), Some(Err(0)));
+
+        // Offset search
+        assert_eq!(zv.zvl_binary_search_in_range(&44, 2..5), Some(Ok(1)));
+        assert_eq!(zv.zvl_binary_search_in_range(&45, 2..5), Some(Err(2)));
+
+        // Out-of-bounds
+        assert_eq!(zv.zvl_binary_search_in_range(&44, 0..100), None);
+        assert_eq!(zv.zvl_binary_search_in_range(&44, 100..200), None);
+    }
+
+    #[test]
+    fn test_permute() {
+        let mut zv: ZeroVec<u16> = ZeroVec::from_slice_or_alloc(&[11, 22, 33, 44, 55, 66, 77]);
+        let mut permutation = vec![3, 2, 1, 0, 6, 5, 4];
+        zv.zvl_permute(&mut permutation);
+        assert_eq!(&zv, &[44, 33, 22, 11, 77, 66, 55]);
+
+        let mut vzv: VarZeroVec<str> = VarZeroVec::Owned(
+            VarZeroVecOwned::try_from_elements(&["11", "22", "33", "44", "55", "66", "77"])
+                .unwrap(),
+        );
+        let mut permutation = vec![3, 2, 1, 0, 6, 5, 4];
+        vzv.zvl_permute(&mut permutation);
+        assert_eq!(&vzv, &["44", "33", "22", "11", "77", "66", "55"]);
+
+        let mut fzv: FlexZeroVec = [11, 22, 33, 44, 55, 66, 77].into_iter().collect();
+        let mut permutation = vec![3, 2, 1, 0, 6, 5, 4];
+        fzv.zvl_permute(&mut permutation);
+        assert_eq!(
+            fzv.iter().collect::<Vec<_>>(),
+            [44, 33, 22, 11, 77, 66, 55].into_iter().collect::<Vec<_>>()
+        );
+    }
+}