Adding upstream version 124.0.1.upstream/124.0.1

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

6 files changed, 2130 insertions, 0 deletions

diff --git a/third_party/rust/zerovec/src/map2d/borrowed.rs b/third_party/rust/zerovec/src/map2d/borrowed.rs
new file mode 100644
index 0000000000..166f1be743
--- /dev/null
+++ b/third_party/rust/zerovec/src/map2d/borrowed.rs
@@ -0,0 +1,339 @@
+// 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::ZeroSlice;
+
+use core::cmp::Ordering;
+use core::fmt;
+
+use crate::map::ZeroMapKV;
+use crate::map::ZeroVecLike;
+use crate::map2d::ZeroMap2dCursor;
+
+/// A borrowed-only version of [`ZeroMap2d`](super::ZeroMap2d)
+///
+/// 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 [`ZeroMap2dBorrowed`] instance.
+///
+/// # Examples
+///
+/// ```
+/// use zerovec::maps::ZeroMap2dBorrowed;
+///
+/// // Example byte buffer representing the map { 1: {2: "three" } }
+/// let BINCODE_BYTES: &[u8; 51] = &[
+///     2, 0, 0, 0, 0, 0, 0, 0, 1, 0, 4, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0,
+///     0, 0, 0, 0, 0, 0, 2, 0, 11, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 116,
+///     104, 114, 101, 101,
+/// ];
+///
+/// // Deserializing to ZeroMap2d requires no heap allocations.
+/// let zero_map: ZeroMap2dBorrowed<u16, u16, str> =
+///     bincode::deserialize(BINCODE_BYTES)
+///         .expect("Should deserialize successfully");
+/// assert_eq!(zero_map.get_2d(&1, &2), Some("three"));
+/// ```
+///
+/// This can be obtained from a [`ZeroMap2d`](super::ZeroMap2d) via [`ZeroMap2d::as_borrowed`](super::ZeroMap2d::as_borrowed)
+pub struct ZeroMap2dBorrowed<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a>,
+    K1: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K0: ?Sized,
+    K1: ?Sized,
+    V: ?Sized,
+{
+    pub(crate) keys0: &'a K0::Slice,
+    pub(crate) joiner: &'a ZeroSlice<u32>,
+    pub(crate) keys1: &'a K1::Slice,
+    pub(crate) values: &'a V::Slice,
+}
+
+impl<'a, K0, K1, V> Copy for ZeroMap2dBorrowed<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a>,
+    K1: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K0: ?Sized,
+    K1: ?Sized,
+    V: ?Sized,
+{
+}
+
+impl<'a, K0, K1, V> Clone for ZeroMap2dBorrowed<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a>,
+    K1: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K0: ?Sized,
+    K1: ?Sized,
+    V: ?Sized,
+{
+    fn clone(&self) -> Self {
+        *self
+    }
+}
+
+impl<'a, K0, K1, V> Default for ZeroMap2dBorrowed<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a>,
+    K1: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K0::Slice: 'static,
+    K1::Slice: 'static,
+    V::Slice: 'static,
+    K0: ?Sized,
+    K1: ?Sized,
+    V: ?Sized,
+{
+    fn default() -> Self {
+        Self::new()
+    }
+}
+
+impl<'a, K0, K1, V> ZeroMap2dBorrowed<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a>,
+    K1: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K0::Slice: 'static,
+    K1::Slice: 'static,
+    V::Slice: 'static,
+    K0: ?Sized,
+    K1: ?Sized,
+    V: ?Sized,
+{
+    /// Creates a new, empty `ZeroMap2dBorrowed<K0, K1, V>`.
+    ///
+    /// Note: Since [`ZeroMap2dBorrowed`] is not mutable, the return value will be a stub unless
+    /// converted into a [`ZeroMap2d`](super::ZeroMap2d).
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use zerovec::maps::ZeroMap2dBorrowed;
+    ///
+    /// let zm: ZeroMap2dBorrowed<u16, u16, str> = ZeroMap2dBorrowed::new();
+    /// assert!(zm.is_empty());
+    /// ```
+    pub fn new() -> Self {
+        Self {
+            keys0: K0::Container::zvl_new_borrowed(),
+            joiner: Default::default(),
+            keys1: K1::Container::zvl_new_borrowed(),
+            values: V::Container::zvl_new_borrowed(),
+        }
+    }
+}
+
+impl<'a, K0, K1, V> ZeroMap2dBorrowed<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a>,
+    K1: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K0: ?Sized,
+    K1: ?Sized,
+    V: ?Sized,
+{
+    #[doc(hidden)] // databake internal
+    pub const unsafe fn from_parts_unchecked(
+        keys0: &'a K0::Slice,
+        joiner: &'a ZeroSlice<u32>,
+        keys1: &'a K1::Slice,
+        values: &'a V::Slice,
+    ) -> Self {
+        Self {
+            keys0,
+            joiner,
+            keys1,
+            values,
+        }
+    }
+
+    /// The number of elements in the [`ZeroMap2dBorrowed`]
+    pub fn len(&self) -> usize {
+        self.values.zvl_len()
+    }
+
+    /// Whether the [`ZeroMap2dBorrowed`] is empty
+    pub fn is_empty(&self) -> bool {
+        self.values.zvl_len() == 0
+    }
+}
+
+impl<'a, K0, K1, V> ZeroMap2dBorrowed<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a> + Ord,
+    K1: ZeroMapKV<'a> + Ord,
+    V: ZeroMapKV<'a>,
+    K0: ?Sized,
+    K1: ?Sized,
+    V: ?Sized,
+{
+    /// Get the value associated with `key0` and `key1`, 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 [`ZeroMap2dBorrowed`](super::ZeroMap2dBorrowed) over [`ZeroMap2d`](super::ZeroMap2d).
+    ///
+    /// ```rust
+    /// use zerovec::maps::ZeroMap2dBorrowed;
+    /// use zerovec::ZeroMap2d;
+    ///
+    /// let mut map = ZeroMap2d::new();
+    /// map.insert(&1, "one", "foo");
+    /// map.insert(&2, "one", "bar");
+    /// map.insert(&2, "two", "baz");
+    ///
+    /// let borrowed = map.as_borrowed();
+    /// assert_eq!(borrowed.get_2d(&1, "one"), Some("foo"));
+    /// assert_eq!(borrowed.get_2d(&1, "two"), None);
+    /// assert_eq!(borrowed.get_2d(&2, "one"), Some("bar"));
+    /// assert_eq!(borrowed.get_2d(&2, "two"), Some("baz"));
+    /// assert_eq!(borrowed.get_2d(&3, "three"), None);
+    /// ```
+    pub fn get_2d(&self, key0: &K0, key1: &K1) -> Option<&'a V::GetType> {
+        self.get0(key0)?.get1(key1)
+    }
+}
+
+impl<'a, K0, K1, V> ZeroMap2dBorrowed<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a> + Ord,
+    K1: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K0: ?Sized,
+    K1: ?Sized,
+    V: ?Sized,
+{
+    /// Gets a cursor for `key0`. If `None`, then `key0` is not in the map. If `Some`,
+    /// then `key0` is in the map, and `key1` can be queried.
+    ///
+    /// ```rust
+    /// use zerovec::maps::ZeroMap2dBorrowed;
+    /// use zerovec::ZeroMap2d;
+    ///
+    /// let mut map = ZeroMap2d::new();
+    /// map.insert(&1, "one", "foo");
+    /// map.insert(&2, "two", "bar");
+    /// let borrowed = map.as_borrowed();
+    /// assert!(matches!(borrowed.get0(&1), Some(_)));
+    /// assert!(matches!(borrowed.get0(&3), None));
+    /// ```
+    #[inline]
+    pub fn get0<'l>(&'l self, key0: &K0) -> Option<ZeroMap2dCursor<'a, 'a, K0, K1, V>> {
+        let key0_index = self.keys0.zvl_binary_search(key0).ok()?;
+        Some(ZeroMap2dCursor::from_borrowed(self, key0_index))
+    }
+
+    /// Binary search the map for `key0`, returning a cursor.
+    ///
+    /// ```rust
+    /// use zerovec::maps::ZeroMap2dBorrowed;
+    /// use zerovec::ZeroMap2d;
+    ///
+    /// let mut map = ZeroMap2d::new();
+    /// map.insert(&1, "one", "foo");
+    /// map.insert(&2, "two", "bar");
+    /// let borrowed = map.as_borrowed();
+    /// assert!(matches!(borrowed.get0_by(|probe| probe.cmp(&1)), Some(_)));
+    /// assert!(matches!(borrowed.get0_by(|probe| probe.cmp(&3)), None));
+    /// ```
+    pub fn get0_by<'l>(
+        &'l self,
+        predicate: impl FnMut(&K0) -> Ordering,
+    ) -> Option<ZeroMap2dCursor<'a, 'a, K0, K1, V>> {
+        let key0_index = self.keys0.zvl_binary_search_by(predicate).ok()?;
+        Some(ZeroMap2dCursor::from_borrowed(self, key0_index))
+    }
+
+    /// Returns whether `key0` is contained in this map
+    ///
+    /// ```rust
+    /// use zerovec::maps::ZeroMap2dBorrowed;
+    /// use zerovec::ZeroMap2d;
+    ///
+    /// let mut map = ZeroMap2d::new();
+    /// map.insert(&1, "one", "foo");
+    /// map.insert(&2, "two", "bar");
+    /// let borrowed = map.as_borrowed();
+    /// assert!(borrowed.contains_key0(&1));
+    /// assert!(!borrowed.contains_key0(&3));
+    /// ```
+    pub fn contains_key0(&self, key0: &K0) -> bool {
+        self.keys0.zvl_binary_search(key0).is_ok()
+    }
+}
+
+impl<'a, K0, K1, V> ZeroMap2dBorrowed<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a>,
+    K1: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K0: ?Sized,
+    K1: ?Sized,
+    V: ?Sized,
+{
+    /// Produce an ordered iterator over keys0
+    pub fn iter0<'l>(&'l self) -> impl Iterator<Item = ZeroMap2dCursor<'a, 'a, K0, K1, V>> + '_ {
+        (0..self.keys0.zvl_len()).map(move |idx| ZeroMap2dCursor::from_borrowed(self, idx))
+    }
+}
+
+impl<'a, K0, K1, V> ZeroMap2dBorrowed<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a> + Ord,
+    K1: ZeroMapKV<'a> + Ord,
+    V: ZeroMapKV<'a>,
+    V: Copy,
+    K0: ?Sized,
+    K1: ?Sized,
+{
+    /// For cases when `V` is fixed-size, obtain a direct copy of `V` instead of `V::ULE`
+    pub fn get_copied_2d(&self, key0: &K0, key1: &K1) -> Option<V> {
+        self.get0(key0)?.get1_copied(key1)
+    }
+}
+
+// We can't use the default PartialEq because ZeroMap2d is invariant
+// so otherwise rustc will not automatically allow you to compare ZeroMaps
+// with different lifetimes
+impl<'a, 'b, K0, K1, V> PartialEq<ZeroMap2dBorrowed<'b, K0, K1, V>>
+    for ZeroMap2dBorrowed<'a, K0, K1, V>
+where
+    K0: for<'c> ZeroMapKV<'c> + ?Sized,
+    K1: for<'c> ZeroMapKV<'c> + ?Sized,
+    V: for<'c> ZeroMapKV<'c> + ?Sized,
+    <K0 as ZeroMapKV<'a>>::Slice: PartialEq<<K0 as ZeroMapKV<'b>>::Slice>,
+    <K1 as ZeroMapKV<'a>>::Slice: PartialEq<<K1 as ZeroMapKV<'b>>::Slice>,
+    <V as ZeroMapKV<'a>>::Slice: PartialEq<<V as ZeroMapKV<'b>>::Slice>,
+{
+    fn eq(&self, other: &ZeroMap2dBorrowed<'b, K0, K1, V>) -> bool {
+        self.keys0.eq(other.keys0)
+            && self.joiner.eq(other.joiner)
+            && self.keys1.eq(other.keys1)
+            && self.values.eq(other.values)
+    }
+}
+
+impl<'a, K0, K1, V> fmt::Debug for ZeroMap2dBorrowed<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a> + ?Sized,
+    K1: ZeroMapKV<'a> + ?Sized,
+    V: ZeroMapKV<'a> + ?Sized,
+    K0::Slice: fmt::Debug,
+    K1::Slice: fmt::Debug,
+    V::Slice: fmt::Debug,
+{
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
+        f.debug_struct("ZeroMap2dBorrowed")
+            .field("keys0", &self.keys0)
+            .field("joiner", &self.joiner)
+            .field("keys1", &self.keys1)
+            .field("values", &self.values)
+            .finish()
+    }
+}
diff --git a/third_party/rust/zerovec/src/map2d/cursor.rs b/third_party/rust/zerovec/src/map2d/cursor.rs
new file mode 100644
index 0000000000..4802187bec
--- /dev/null
+++ b/third_party/rust/zerovec/src/map2d/cursor.rs
@@ -0,0 +1,358 @@
+// 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::{ZeroMap2d, ZeroSlice};
+
+use core::cmp::Ordering;
+use core::fmt;
+use core::ops::Range;
+
+use crate::map::ZeroMapKV;
+use crate::map::ZeroVecLike;
+
+use super::ZeroMap2dBorrowed;
+
+/// An intermediate state of queries over [`ZeroMap2d`] and [`ZeroMap2dBorrowed`].
+pub struct ZeroMap2dCursor<'l, 'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a>,
+    K1: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K0: ?Sized,
+    K1: ?Sized,
+    V: ?Sized,
+{
+    // Invariant: these fields have the same invariants as they do in ZeroMap2d
+    keys0: &'l K0::Slice,
+    joiner: &'l ZeroSlice<u32>,
+    keys1: &'l K1::Slice,
+    values: &'l V::Slice,
+    // Invariant: key0_index is in range
+    key0_index: usize,
+}
+
+impl<'a, K0, K1, V> ZeroMap2dCursor<'a, 'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a>,
+    K1: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K0: ?Sized,
+    K1: ?Sized,
+    V: ?Sized,
+{
+    /// `key0_index` must be in range
+    pub(crate) fn from_borrowed(
+        borrowed: &ZeroMap2dBorrowed<'a, K0, K1, V>,
+        key0_index: usize,
+    ) -> Self {
+        debug_assert!(key0_index < borrowed.joiner.len());
+        ZeroMap2dCursor {
+            keys0: borrowed.keys0,
+            joiner: borrowed.joiner,
+            keys1: borrowed.keys1,
+            values: borrowed.values,
+            key0_index,
+        }
+    }
+}
+
+impl<'l, 'a, K0, K1, V> ZeroMap2dCursor<'l, 'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a>,
+    K1: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K0: ?Sized,
+    K1: ?Sized,
+    V: ?Sized,
+{
+    /// `key0_index` must be in range
+    pub(crate) fn from_cow(cow: &'l ZeroMap2d<'a, K0, K1, V>, key0_index: usize) -> Self {
+        debug_assert!(key0_index < cow.joiner.len());
+        Self {
+            keys0: cow.keys0.zvl_as_borrowed(),
+            joiner: &cow.joiner,
+            keys1: cow.keys1.zvl_as_borrowed(),
+            values: cow.values.zvl_as_borrowed(),
+            key0_index,
+        }
+    }
+
+    /// Returns the key0 corresponding to the cursor position.
+    ///
+    /// ```rust
+    /// use zerovec::ZeroMap2d;
+    ///
+    /// let mut map = ZeroMap2d::new();
+    /// map.insert("one", &1u32, "foo");
+    /// assert_eq!(map.get0("one").unwrap().key0(), "one");
+    /// ```
+    pub fn key0(&self) -> &'l K0::GetType {
+        #[allow(clippy::unwrap_used)] // safe by invariant on `self.key0_index`
+        self.keys0.zvl_get(self.key0_index).unwrap()
+    }
+
+    /// Borrow an ordered iterator over keys1 and values for a particular key0.
+    ///
+    /// To get the values as copy types, see [`Self::iter1_copied`].
+    ///
+    /// For an example, see [`ZeroMap2d::iter0()`].
+    pub fn iter1(
+        &self,
+    ) -> impl Iterator<
+        Item = (
+            &'l <K1 as ZeroMapKV<'a>>::GetType,
+            &'l <V as ZeroMapKV<'a>>::GetType,
+        ),
+    > + '_ {
+        let range = self.get_range();
+        #[allow(clippy::unwrap_used)] // `self.get_range()` returns a valid range
+        range.map(move |idx| {
+            (
+                self.keys1.zvl_get(idx).unwrap(),
+                self.values.zvl_get(idx).unwrap(),
+            )
+        })
+    }
+
+    /// Transform this cursor into an ordered iterator over keys1 for a particular key0.
+    pub fn into_iter1(
+        self,
+    ) -> impl Iterator<
+        Item = (
+            &'l <K1 as ZeroMapKV<'a>>::GetType,
+            &'l <V as ZeroMapKV<'a>>::GetType,
+        ),
+    > {
+        let range = self.get_range();
+        #[allow(clippy::unwrap_used)] // `self.get_range()` returns a valid range
+        range.map(move |idx| {
+            (
+                self.keys1.zvl_get(idx).unwrap(),
+                self.values.zvl_get(idx).unwrap(),
+            )
+        })
+    }
+
+    /// Given key0_index, returns the corresponding range of keys1, which will be valid
+    pub(super) fn get_range(&self) -> Range<usize> {
+        debug_assert!(self.key0_index < self.joiner.len());
+        let start = if self.key0_index == 0 {
+            0
+        } else {
+            #[allow(clippy::unwrap_used)] // protected by the debug_assert above
+            self.joiner.get(self.key0_index - 1).unwrap()
+        };
+        #[allow(clippy::unwrap_used)] // protected by the debug_assert above
+        let limit = self.joiner.get(self.key0_index).unwrap();
+        // These two assertions are true based on the invariants of ZeroMap2d
+        debug_assert!(start < limit);
+        debug_assert!((limit as usize) <= self.values.zvl_len());
+        (start as usize)..(limit as usize)
+    }
+}
+
+impl<'l, 'a, K0, K1, V> ZeroMap2dCursor<'l, 'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a>,
+    K1: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K0: ?Sized,
+    K1: ?Sized,
+    V: Copy,
+{
+    /// Borrow an ordered iterator over keys1 and values for a particular key0.
+    ///
+    /// The values are returned as copy types.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use zerovec::ZeroMap2d;
+    ///
+    /// let zm2d: ZeroMap2d<str, u8, usize> = [
+    ///     ("a", 0u8, 1usize),
+    ///     ("b", 1u8, 1000usize),
+    ///     ("b", 2u8, 2000usize),
+    /// ]
+    /// .into_iter()
+    /// .collect();
+    ///
+    /// let mut total_value = 0;
+    ///
+    /// for cursor in zm2d.iter0() {
+    ///     for (_, value) in cursor.iter1_copied() {
+    ///         total_value += value;
+    ///     }
+    /// }
+    ///
+    /// assert_eq!(total_value, 3001);
+    /// ```
+    pub fn iter1_copied(
+        &self,
+    ) -> impl Iterator<Item = (&'l <K1 as ZeroMapKV<'a>>::GetType, V)> + '_ {
+        let range = self.get_range();
+        #[allow(clippy::unwrap_used)] // `self.get_range()` returns a valid range
+        range.map(move |idx| {
+            (
+                self.keys1.zvl_get(idx).unwrap(),
+                self.get1_copied_at(idx).unwrap(),
+            )
+        })
+    }
+
+    fn get1_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<'l, 'a, K0, K1, V> ZeroMap2dCursor<'l, 'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a>,
+    K1: ZeroMapKV<'a> + Ord,
+    V: ZeroMapKV<'a>,
+    K0: ?Sized,
+    K1: ?Sized,
+    V: ?Sized,
+{
+    /// Gets the value for a key1 from this cursor, or `None` if key1 is not in the map.
+    ///
+    /// ```rust
+    /// use zerovec::ZeroMap2d;
+    ///
+    /// let mut map = ZeroMap2d::new();
+    /// map.insert("one", &1u32, "foo");
+    /// assert_eq!(map.get0("one").unwrap().get1(&1), Some("foo"));
+    /// assert_eq!(map.get0("one").unwrap().get1(&2), None);
+    /// ```
+    pub fn get1(&self, key1: &K1) -> Option<&'l V::GetType> {
+        let key1_index = self.get_key1_index(key1)?;
+        #[allow(clippy::unwrap_used)] // key1_index is valid
+        Some(self.values.zvl_get(key1_index).unwrap())
+    }
+
+    /// Gets the value for a predicate from this cursor, or `None` if key1 is not in the map.
+    ///
+    /// ```rust
+    /// use zerovec::ZeroMap2d;
+    ///
+    /// let mut map = ZeroMap2d::new();
+    /// map.insert("one", &1u32, "foo");
+    /// assert_eq!(map.get0("one").unwrap().get1_by(|v| v.cmp(&1)), Some("foo"));
+    /// assert_eq!(map.get0("one").unwrap().get1_by(|v| v.cmp(&2)), None);
+    /// ```
+    pub fn get1_by(&self, predicate: impl FnMut(&K1) -> Ordering) -> Option<&'l V::GetType> {
+        let key1_index = self.get_key1_index_by(predicate)?;
+        #[allow(clippy::unwrap_used)] // key1_index is valid
+        Some(self.values.zvl_get(key1_index).unwrap())
+    }
+
+    /// Given key0_index and predicate, returns the index into the values array
+    fn get_key1_index_by(&self, predicate: impl FnMut(&K1) -> Ordering) -> Option<usize> {
+        let range = self.get_range();
+        debug_assert!(range.start < range.end); // '<' because every key0 should have a key1
+        debug_assert!(range.end <= self.keys1.zvl_len());
+        let start = range.start;
+        #[allow(clippy::expect_used)] // protected by the debug_assert above
+        let binary_search_result = self
+            .keys1
+            .zvl_binary_search_in_range_by(predicate, range)
+            .expect("in-bounds range");
+        binary_search_result.ok().map(move |s| s + start)
+    }
+
+    /// Given key0_index and key1, returns the index into the values array
+    fn get_key1_index(&self, key1: &K1) -> Option<usize> {
+        let range = self.get_range();
+        debug_assert!(range.start < range.end); // '<' because every key0 should have a key1
+        debug_assert!(range.end <= self.keys1.zvl_len());
+        let start = range.start;
+        #[allow(clippy::expect_used)] // protected by the debug_assert above
+        let binary_search_result = self
+            .keys1
+            .zvl_binary_search_in_range(key1, range)
+            .expect("in-bounds range");
+        binary_search_result.ok().map(move |s| s + start)
+    }
+}
+
+impl<'l, 'a, K0, K1, V> ZeroMap2dCursor<'l, 'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a>,
+    K1: ZeroMapKV<'a> + Ord,
+    V: ZeroMapKV<'a>,
+    V: Copy,
+    K0: ?Sized,
+    K1: ?Sized,
+{
+    /// For cases when `V` is fixed-size, obtain a direct copy of `V` instead of `V::ULE`
+    ///
+    /// ```rust
+    /// use zerovec::ZeroMap2d;
+    ///
+    /// let mut map: ZeroMap2d<u16, u16, u16> = ZeroMap2d::new();
+    /// map.insert(&1, &2, &3);
+    /// map.insert(&1, &4, &5);
+    /// map.insert(&6, &7, &8);
+    ///
+    /// assert_eq!(map.get0(&6).unwrap().get1_copied(&7), Some(8));
+    /// ```
+    #[inline]
+    pub fn get1_copied(&self, key1: &K1) -> Option<V> {
+        let key1_index = self.get_key1_index(key1)?;
+        self.get1_copied_at(key1_index)
+    }
+
+    /// For cases when `V` is fixed-size, obtain a direct copy of `V` instead of `V::ULE`
+    #[inline]
+    pub fn get1_copied_by(&self, predicate: impl FnMut(&K1) -> Ordering) -> Option<V> {
+        let key1_index = self.get_key1_index_by(predicate)?;
+        self.get1_copied_at(key1_index)
+    }
+}
+
+// We can't use the default PartialEq because ZeroMap2d is invariant
+// so otherwise rustc will not automatically allow you to compare ZeroMaps
+// with different lifetimes
+impl<'m, 'n, 'a, 'b, K0, K1, V> PartialEq<ZeroMap2dCursor<'n, 'b, K0, K1, V>>
+    for ZeroMap2dCursor<'m, 'a, K0, K1, V>
+where
+    K0: for<'c> ZeroMapKV<'c> + ?Sized,
+    K1: for<'c> ZeroMapKV<'c> + ?Sized,
+    V: for<'c> ZeroMapKV<'c> + ?Sized,
+    <K0 as ZeroMapKV<'a>>::Slice: PartialEq<<K0 as ZeroMapKV<'b>>::Slice>,
+    <K1 as ZeroMapKV<'a>>::Slice: PartialEq<<K1 as ZeroMapKV<'b>>::Slice>,
+    <V as ZeroMapKV<'a>>::Slice: PartialEq<<V as ZeroMapKV<'b>>::Slice>,
+{
+    fn eq(&self, other: &ZeroMap2dCursor<'n, 'b, K0, K1, V>) -> bool {
+        self.keys0.eq(other.keys0)
+            && self.joiner.eq(other.joiner)
+            && self.keys1.eq(other.keys1)
+            && self.values.eq(other.values)
+            && self.key0_index.eq(&other.key0_index)
+    }
+}
+
+impl<'l, 'a, K0, K1, V> fmt::Debug for ZeroMap2dCursor<'l, 'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a> + ?Sized,
+    K1: ZeroMapKV<'a> + ?Sized,
+    V: ZeroMapKV<'a> + ?Sized,
+    K0::Slice: fmt::Debug,
+    K1::Slice: fmt::Debug,
+    V::Slice: fmt::Debug,
+{
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
+        f.debug_struct("ZeroMap2d")
+            .field("keys0", &self.keys0)
+            .field("joiner", &self.joiner)
+            .field("keys1", &self.keys1)
+            .field("values", &self.values)
+            .field("key0_index", &self.key0_index)
+            .finish()
+    }
+}
diff --git a/third_party/rust/zerovec/src/map2d/databake.rs b/third_party/rust/zerovec/src/map2d/databake.rs
new file mode 100644
index 0000000000..c5b9aca546
--- /dev/null
+++ b/third_party/rust/zerovec/src/map2d/databake.rs
@@ -0,0 +1,110 @@
+// 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::ZeroMap2dBorrowed, maps::ZeroMapKV, ZeroMap2d};
+use databake::*;
+
+impl<'a, K0, K1, V> Bake for ZeroMap2d<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a> + ?Sized,
+    K1: ZeroMapKV<'a> + ?Sized,
+    V: ZeroMapKV<'a> + ?Sized,
+    K0::Container: Bake,
+    K1::Container: Bake,
+    V::Container: Bake,
+{
+    fn bake(&self, env: &CrateEnv) -> TokenStream {
+        env.insert("zerovec");
+        let keys0 = self.keys0.bake(env);
+        let joiner = self.joiner.bake(env);
+        let keys1 = self.keys1.bake(env);
+        let values = self.values.bake(env);
+        quote! { unsafe { #[allow(unused_unsafe)] zerovec::ZeroMap2d::from_parts_unchecked(#keys0, #joiner, #keys1, #values) } }
+    }
+}
+
+impl<'a, K0, K1, V> Bake for ZeroMap2dBorrowed<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a> + ?Sized,
+    K1: ZeroMapKV<'a> + ?Sized,
+    V: ZeroMapKV<'a> + ?Sized,
+    &'a K0::Slice: Bake,
+    &'a K1::Slice: Bake,
+    &'a V::Slice: Bake,
+{
+    fn bake(&self, env: &CrateEnv) -> TokenStream {
+        env.insert("zerovec");
+        let keys0 = self.keys0.bake(env);
+        let joiner = self.joiner.bake(env);
+        let keys1 = self.keys1.bake(env);
+        let values = self.values.bake(env);
+        quote! { unsafe { #[allow(unused_unsafe)] zerovec::maps::ZeroMap2dBorrowed::from_parts_unchecked(#keys0, #joiner, #keys1, #values) } }
+    }
+}
+
+#[test]
+fn test_baked_map() {
+    test_bake!(
+        ZeroMap2d<str, str, str>,
+        const: unsafe {
+            #[allow(unused_unsafe)]
+            crate::ZeroMap2d::from_parts_unchecked(
+                unsafe {
+                    crate::VarZeroVec::from_bytes_unchecked(
+                        b"\x0E\0\0\0\0\0\x05\0\x07\0\t\0\x0B\0\x10\0\x12\0\x14\0\x1C\0\x1E\0#\0%\0'\0,\0arcazcuenffgrckkkukylifmanmnpapalsdtgugunruzyuezh"
+                    )
+                },
+                unsafe {
+                    crate::ZeroVec::from_bytes_unchecked(
+                        b"\x02\0\0\0\x03\0\0\0\x04\0\0\0\x05\0\0\0\x06\0\0\0\x07\0\0\0\x08\0\0\0\n\0\0\0\x0C\0\0\0\r\0\0\0\x0E\0\0\0\x0F\0\0\0\x10\0\0\0\x11\0\0\0\x14\0\0\0\x15\0\0\0\x16\0\0\0\x17\0\0\0\x18\0\0\0\x19\0\0\0\x1C\0\0\0"
+                    )
+                },
+                unsafe {
+                    crate::VarZeroVec::from_bytes_unchecked(
+                        b"\x1C\0\0\0\0\0\x04\0\x08\0\x0C\0\x10\0\x14\0\x18\0\x1C\0 \0$\0(\0,\x000\x004\08\0<\0@\0D\0H\0L\0P\0T\0X\0\\\0`\0d\0h\0l\0NbatPalmArabGlagShawAdlmLinbArabArabYeziArabLatnLimbNkooMongArabPhlpDevaKhojSindArabCyrlDevaArabHansBopoHanbHant"
+                    )
+                },
+                unsafe {
+                    crate::VarZeroVec::from_bytes_unchecked(
+                        b"\x1C\0\0\0\0\0\x02\0\x04\0\x06\0\x08\0\n\0\x0C\0\x0E\0\x10\0\x12\0\x14\0\x16\0\x18\0\x1A\0\x1C\0\x1E\0 \0\"\0$\0&\0(\0*\0,\0.\x000\x002\x004\x006\0JOSYIRBGGBGNGRCNIQGECNTRINGNCNPKCNINININPKKZNPAFCNTWTWTW"
+                    )
+                },
+            )
+        },
+        zerovec
+    );
+}
+
+#[test]
+fn test_baked_borrowed_map() {
+    test_bake!(
+        ZeroMap2dBorrowed<str, str, str>,
+        const: unsafe {
+            #[allow(unused_unsafe)]
+            crate::maps::ZeroMap2dBorrowed::from_parts_unchecked(
+                unsafe {
+                    crate::VarZeroSlice::from_bytes_unchecked(
+                        b"\x0E\0\0\0\0\0\x05\0\x07\0\t\0\x0B\0\x10\0\x12\0\x14\0\x1C\0\x1E\0#\0%\0'\0,\0arcazcuenffgrckkkukylifmanmnpapalsdtgugunruzyuezh"
+                    )
+                },
+                unsafe {
+                    crate::ZeroSlice::from_bytes_unchecked(
+                        b"\x02\0\0\0\x03\0\0\0\x04\0\0\0\x05\0\0\0\x06\0\0\0\x07\0\0\0\x08\0\0\0\n\0\0\0\x0C\0\0\0\r\0\0\0\x0E\0\0\0\x0F\0\0\0\x10\0\0\0\x11\0\0\0\x14\0\0\0\x15\0\0\0\x16\0\0\0\x17\0\0\0\x18\0\0\0\x19\0\0\0\x1C\0\0\0"
+                    )
+                },
+                unsafe {
+                    crate::VarZeroSlice::from_bytes_unchecked(
+                        b"\x1C\0\0\0\0\0\x04\0\x08\0\x0C\0\x10\0\x14\0\x18\0\x1C\0 \0$\0(\0,\x000\x004\08\0<\0@\0D\0H\0L\0P\0T\0X\0\\\0`\0d\0h\0l\0NbatPalmArabGlagShawAdlmLinbArabArabYeziArabLatnLimbNkooMongArabPhlpDevaKhojSindArabCyrlDevaArabHansBopoHanbHant"
+                    )
+                },
+                unsafe {
+                    crate::VarZeroSlice::from_bytes_unchecked(
+                        b"\x1C\0\0\0\0\0\x02\0\x04\0\x06\0\x08\0\n\0\x0C\0\x0E\0\x10\0\x12\0\x14\0\x16\0\x18\0\x1A\0\x1C\0\x1E\0 \0\"\0$\0&\0(\0*\0,\0.\x000\x002\x004\x006\0JOSYIRBGGBGNGRCNIQGECNTRINGNCNPKCNINININPKKZNPAFCNTWTWTW"
+                    )
+                },
+            )
+        },
+        zerovec
+    );
+}
diff --git a/third_party/rust/zerovec/src/map2d/map.rs b/third_party/rust/zerovec/src/map2d/map.rs
new file mode 100644
index 0000000000..1975387a43
--- /dev/null
+++ b/third_party/rust/zerovec/src/map2d/map.rs
@@ -0,0 +1,875 @@
+// 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::ZeroVec;
+use alloc::borrow::Borrow;
+use core::cmp::Ordering;
+use core::convert::TryFrom;
+use core::fmt;
+use core::iter::FromIterator;
+use core::ops::Range;
+
+use super::*;
+use crate::map::ZeroMapKV;
+use crate::map::{MutableZeroVecLike, ZeroVecLike};
+
+/// A zero-copy, two-dimensional map datastructure .
+///
+/// This is an extension of [`ZeroMap`] that supports two layers of keys. For example,
+/// to map a pair of an integer and a string to a buffer, you can write:
+///
+/// ```no_run
+/// # use zerovec::ZeroMap2d;
+/// let _: ZeroMap2d<u32, str, [u8]> = unimplemented!();
+/// ```
+///
+/// Internally, `ZeroMap2d` stores four zero-copy vectors, one for each type argument plus
+/// one more to match between the two vectors of keys.
+///
+/// # Examples
+///
+/// ```
+/// use zerovec::ZeroMap2d;
+///
+/// // Example byte buffer representing the map { 1: {2: "three" } }
+/// let BINCODE_BYTES: &[u8; 51] = &[
+///     2, 0, 0, 0, 0, 0, 0, 0, 1, 0, 4, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0,
+///     0, 0, 0, 0, 0, 0, 2, 0, 11, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 116,
+///     104, 114, 101, 101,
+/// ];
+///
+/// // Deserializing to ZeroMap requires no heap allocations.
+/// let zero_map: ZeroMap2d<u16, u16, str> =
+///     bincode::deserialize(BINCODE_BYTES)
+///         .expect("Should deserialize successfully");
+/// assert_eq!(zero_map.get_2d(&1, &2), Some("three"));
+/// ```
+///
+/// [`VarZeroVec`]: crate::VarZeroVec
+/// [`ZeroMap`]: crate::ZeroMap
+// ZeroMap2d contains 4 fields:
+//
+// - keys0 = sorted list of all K0 in the map
+// - joiner = helper vec that maps from a K0 to a range of keys1
+// - keys1 = list of all K1 in the map, sorted in ranges for each K0
+// - values = list of all values in the map, sorted by (K0, K1)
+//
+// For a particular K0 at index i, the range of keys1 corresponding to K0 is
+// (joiner[i-1]..joiner[i]), where the first range starts at 0.
+//
+// Required Invariants:
+//
+// 1. len(keys0) == len(joiner)
+// 2. len(keys1) == len(values)
+// 3. joiner is sorted
+// 4. the last element of joiner is the length of keys1
+//
+// Optional Invariants:
+//
+// 5. keys0 is sorted (for binary_search)
+// 6. ranges within keys1 are sorted (for binary_search)
+// 7. every K0 is associated with at least one K1 (no empty ranges)
+//
+// During deserialization, these three invariants are not checked, because they put the
+// ZeroMap2d in a deterministic state, even though it may have unexpected behavior.
+pub struct ZeroMap2d<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a>,
+    K1: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K0: ?Sized,
+    K1: ?Sized,
+    V: ?Sized,
+{
+    pub(crate) keys0: K0::Container,
+    pub(crate) joiner: ZeroVec<'a, u32>,
+    pub(crate) keys1: K1::Container,
+    pub(crate) values: V::Container,
+}
+
+impl<'a, K0, K1, V> Default for ZeroMap2d<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a>,
+    K1: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K0: ?Sized,
+    K1: ?Sized,
+    V: ?Sized,
+{
+    fn default() -> Self {
+        Self::new()
+    }
+}
+
+impl<'a, K0, K1, V> ZeroMap2d<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a>,
+    K1: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K0: ?Sized,
+    K1: ?Sized,
+    V: ?Sized,
+{
+    /// Creates a new, empty `ZeroMap2d`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use zerovec::ZeroMap2d;
+    ///
+    /// let zm: ZeroMap2d<u16, str, str> = ZeroMap2d::new();
+    /// assert!(zm.is_empty());
+    /// ```
+    pub fn new() -> Self {
+        Self {
+            keys0: K0::Container::zvl_with_capacity(0),
+            joiner: ZeroVec::new(),
+            keys1: K1::Container::zvl_with_capacity(0),
+            values: V::Container::zvl_with_capacity(0),
+        }
+    }
+
+    #[doc(hidden)] // databake internal
+    pub const unsafe fn from_parts_unchecked(
+        keys0: K0::Container,
+        joiner: ZeroVec<'a, u32>,
+        keys1: K1::Container,
+        values: V::Container,
+    ) -> Self {
+        Self {
+            keys0,
+            joiner,
+            keys1,
+            values,
+        }
+    }
+
+    /// Construct a new [`ZeroMap2d`] with a given capacity
+    pub fn with_capacity(capacity: usize) -> Self {
+        Self {
+            keys0: K0::Container::zvl_with_capacity(capacity),
+            joiner: ZeroVec::with_capacity(capacity),
+            keys1: K1::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) -> ZeroMap2dBorrowed<'a, K0, K1, V> {
+        ZeroMap2dBorrowed {
+            keys0: self.keys0.zvl_as_borrowed(),
+            joiner: &self.joiner,
+            keys1: self.keys1.zvl_as_borrowed(),
+            values: self.values.zvl_as_borrowed(),
+        }
+    }
+
+    /// The number of values in the [`ZeroMap2d`]
+    pub fn len(&self) -> usize {
+        self.values.zvl_len()
+    }
+
+    /// Whether the [`ZeroMap2d`] is empty
+    pub fn is_empty(&self) -> bool {
+        self.values.zvl_len() == 0
+    }
+
+    /// Remove all elements from the [`ZeroMap2d`]
+    pub fn clear(&mut self) {
+        self.keys0.zvl_clear();
+        self.joiner.clear();
+        self.keys1.zvl_clear();
+        self.values.zvl_clear();
+    }
+
+    /// Reserve capacity for `additional` more elements to be inserted into
+    /// the [`ZeroMap2d`] to avoid frequent reallocations.
+    ///
+    /// See [`Vec::reserve()`](alloc::vec::Vec::reserve) for more information.
+    pub fn reserve(&mut self, additional: usize) {
+        self.keys0.zvl_reserve(additional);
+        self.joiner.zvl_reserve(additional);
+        self.keys1.zvl_reserve(additional);
+        self.values.zvl_reserve(additional);
+    }
+
+    /// Produce an ordered iterator over keys0, which can then be used to get an iterator
+    /// over keys1 for a particular key0.
+    ///
+    /// # Example
+    ///
+    /// Loop over all elements of a ZeroMap2d:
+    ///
+    /// ```
+    /// use zerovec::ZeroMap2d;
+    ///
+    /// let mut map: ZeroMap2d<u16, u16, str> = ZeroMap2d::new();
+    /// map.insert(&1, &1, "foo");
+    /// map.insert(&2, &3, "bar");
+    /// map.insert(&2, &4, "baz");
+    ///
+    /// let mut total_value = 0;
+    ///
+    /// for cursor in map.iter0() {
+    ///     for (key1, value) in cursor.iter1() {
+    ///         // This code runs for every (key0, key1) pair
+    ///         total_value += cursor.key0().as_unsigned_int() as usize;
+    ///         total_value += key1.as_unsigned_int() as usize;
+    ///         total_value += value.len();
+    ///     }
+    /// }
+    ///
+    /// assert_eq!(total_value, 22);
+    /// ```
+    pub fn iter0<'l>(&'l self) -> impl Iterator<Item = ZeroMap2dCursor<'l, 'a, K0, K1, V>> + 'l {
+        (0..self.keys0.zvl_len()).map(move |idx| ZeroMap2dCursor::from_cow(self, idx))
+    }
+
+    // INTERNAL ROUTINES FOLLOW //
+
+    /// Given an index into the joiner array, returns the corresponding range of keys1
+    fn get_range_for_key0_index(&self, key0_index: usize) -> Range<usize> {
+        ZeroMap2dCursor::from_cow(self, key0_index).get_range()
+    }
+
+    /// Removes key0_index from the keys0 array and the joiner array
+    fn remove_key0_index(&mut self, key0_index: usize) {
+        self.keys0.zvl_remove(key0_index);
+        self.joiner.with_mut(|v| v.remove(key0_index));
+    }
+
+    /// Shifts all joiner ranges from key0_index onward one index up
+    fn joiner_expand(&mut self, key0_index: usize) {
+        #[allow(clippy::expect_used)] // slice overflow
+        self.joiner
+            .to_mut_slice()
+            .iter_mut()
+            .skip(key0_index)
+            .for_each(|ref mut v| {
+                // TODO(#1410): Make this fallible
+                **v = v
+                    .as_unsigned_int()
+                    .checked_add(1)
+                    .expect("Attempted to add more than 2^32 elements to a ZeroMap2d")
+                    .to_unaligned()
+            })
+    }
+
+    /// Shifts all joiner ranges from key0_index onward one index down
+    fn joiner_shrink(&mut self, key0_index: usize) {
+        self.joiner
+            .to_mut_slice()
+            .iter_mut()
+            .skip(key0_index)
+            .for_each(|ref mut v| **v = (v.as_unsigned_int() - 1).to_unaligned())
+    }
+}
+
+impl<'a, K0, K1, V> ZeroMap2d<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a> + Ord,
+    K1: ZeroMapKV<'a> + Ord,
+    V: ZeroMapKV<'a>,
+    K0: ?Sized,
+    K1: ?Sized,
+    V: ?Sized,
+{
+    /// Get the value associated with `key0` and `key1`, if it exists.
+    ///
+    /// For more fine-grained error handling, use [`ZeroMap2d::get0`].
+    ///
+    /// ```rust
+    /// use zerovec::ZeroMap2d;
+    ///
+    /// let mut map = ZeroMap2d::new();
+    /// map.insert(&1, "one", "foo");
+    /// map.insert(&2, "one", "bar");
+    /// map.insert(&2, "two", "baz");
+    /// assert_eq!(map.get_2d(&1, "one"), Some("foo"));
+    /// assert_eq!(map.get_2d(&1, "two"), None);
+    /// assert_eq!(map.get_2d(&2, "one"), Some("bar"));
+    /// assert_eq!(map.get_2d(&2, "two"), Some("baz"));
+    /// assert_eq!(map.get_2d(&3, "three"), None);
+    /// ```
+    pub fn get_2d(&self, key0: &K0, key1: &K1) -> Option<&V::GetType> {
+        self.get0(key0)?.get1(key1)
+    }
+
+    /// Insert `value` with `key`, returning the existing value if it exists.
+    ///
+    /// ```rust
+    /// use zerovec::ZeroMap2d;
+    ///
+    /// let mut map = ZeroMap2d::new();
+    /// assert_eq!(map.insert(&0, "zero", "foo"), None,);
+    /// assert_eq!(map.insert(&1, "one", "bar"), None,);
+    /// assert_eq!(map.insert(&1, "one", "baz").as_deref(), Some("bar"),);
+    /// assert_eq!(map.get_2d(&1, "one").as_deref(), Some("baz"));
+    /// assert_eq!(map.len(), 2);
+    /// ```
+    pub fn insert(&mut self, key0: &K0, key1: &K1, value: &V) -> Option<V::OwnedType> {
+        let (key0_index, range) = self.get_or_insert_range_for_key0(key0);
+        debug_assert!(range.start <= range.end); // '<=' because we may have inserted a new key0
+        debug_assert!(range.end <= self.keys1.zvl_len());
+        let range_start = range.start;
+        #[allow(clippy::unwrap_used)] // by debug_assert! invariants
+        let index = range_start
+            + match self.keys1.zvl_binary_search_in_range(key1, range).unwrap() {
+                Ok(index) => return Some(self.values.zvl_replace(range_start + index, value)),
+                Err(index) => index,
+            };
+        self.keys1.zvl_insert(index, key1);
+        self.values.zvl_insert(index, value);
+        self.joiner_expand(key0_index);
+        #[cfg(debug_assertions)]
+        self.check_invariants();
+        None
+    }
+
+    /// Remove the value at `key`, returning it if it exists.
+    ///
+    /// ```rust
+    /// use zerovec::ZeroMap2d;
+    ///
+    /// let mut map = ZeroMap2d::new();
+    /// map.insert(&1, "one", "foo");
+    /// map.insert(&2, "two", "bar");
+    /// assert_eq!(
+    ///     map.remove(&1, "one"),
+    ///     Some("foo".to_owned().into_boxed_str())
+    /// );
+    /// assert_eq!(map.get_2d(&1, "one"), None);
+    /// assert_eq!(map.remove(&1, "one"), None);
+    /// ```
+    pub fn remove(&mut self, key0: &K0, key1: &K1) -> Option<V::OwnedType> {
+        let key0_index = self.keys0.zvl_binary_search(key0).ok()?;
+        let range = self.get_range_for_key0_index(key0_index);
+        debug_assert!(range.start < range.end); // '<' because every key0 should have a key1
+        debug_assert!(range.end <= self.keys1.zvl_len());
+        let is_singleton_range = range.start + 1 == range.end;
+        #[allow(clippy::unwrap_used)] // by debug_assert invariants
+        let index = range.start
+            + self
+                .keys1
+                .zvl_binary_search_in_range(key1, range)
+                .unwrap()
+                .ok()?;
+        self.keys1.zvl_remove(index);
+        let removed = self.values.zvl_remove(index);
+        self.joiner_shrink(key0_index);
+        if is_singleton_range {
+            self.remove_key0_index(key0_index);
+        }
+        #[cfg(debug_assertions)]
+        self.check_invariants();
+        Some(removed)
+    }
+
+    /// 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::ZeroMap2d;
+    ///
+    /// let mut map = ZeroMap2d::new();
+    /// assert!(map.try_append(&1, "one", "uno").is_none());
+    /// assert!(map.try_append(&3, "three", "tres").is_none());
+    ///
+    /// let unsuccessful = map.try_append(&3, "three", "tres-updated");
+    /// assert!(unsuccessful.is_some(), "append duplicate of last key");
+    ///
+    /// let unsuccessful = map.try_append(&2, "two", "dos");
+    /// assert!(unsuccessful.is_some(), "append out of order");
+    ///
+    /// assert_eq!(map.get_2d(&1, "one"), Some("uno"));
+    ///
+    /// // contains the original value for the key: 3
+    /// assert_eq!(map.get_2d(&3, "three"), Some("tres"));
+    ///
+    /// // not appended since it wasn't in order
+    /// assert_eq!(map.get_2d(&2, "two"), None);
+    /// ```
+    #[must_use]
+    pub fn try_append<'b>(
+        &mut self,
+        key0: &'b K0,
+        key1: &'b K1,
+        value: &'b V,
+    ) -> Option<(&'b K0, &'b K1, &'b V)> {
+        if self.is_empty() {
+            self.keys0.zvl_push(key0);
+            self.joiner.with_mut(|v| v.push(1u32.to_unaligned()));
+            self.keys1.zvl_push(key1);
+            self.values.zvl_push(value);
+            return None;
+        }
+
+        // The unwraps are protected by the fact that we are not empty
+        #[allow(clippy::unwrap_used)]
+        let last_key0 = self.keys0.zvl_get(self.keys0.zvl_len() - 1).unwrap();
+        let key0_cmp = K0::Container::t_cmp_get(key0, last_key0);
+        #[allow(clippy::unwrap_used)]
+        let last_key1 = self.keys1.zvl_get(self.keys1.zvl_len() - 1).unwrap();
+        let key1_cmp = K1::Container::t_cmp_get(key1, last_key1);
+
+        // Check for error case (out of order)
+        match key0_cmp {
+            Ordering::Less => {
+                // Error case
+                return Some((key0, key1, value));
+            }
+            Ordering::Equal => {
+                match key1_cmp {
+                    Ordering::Less | Ordering::Equal => {
+                        // Error case
+                        return Some((key0, key1, value));
+                    }
+                    _ => {}
+                }
+            }
+            _ => {}
+        }
+
+        #[allow(clippy::expect_used)] // slice overflow
+        let joiner_value = u32::try_from(self.keys1.zvl_len() + 1)
+            .expect("Attempted to add more than 2^32 elements to a ZeroMap2d");
+
+        // All OK to append
+        #[allow(clippy::unwrap_used)]
+        if key0_cmp == Ordering::Greater {
+            self.keys0.zvl_push(key0);
+            self.joiner
+                .with_mut(|v| v.push(joiner_value.to_unaligned()));
+        } else {
+            // This unwrap is protected because we are not empty
+            *self.joiner.to_mut_slice().last_mut().unwrap() = joiner_value.to_unaligned();
+        }
+        self.keys1.zvl_push(key1);
+        self.values.zvl_push(value);
+
+        #[cfg(debug_assertions)]
+        self.check_invariants();
+
+        None
+    }
+
+    // INTERNAL ROUTINES FOLLOW //
+
+    #[cfg(debug_assertions)]
+    #[allow(clippy::unwrap_used)] // this is an assertion function
+    pub(crate) fn check_invariants(&self) {
+        debug_assert_eq!(self.keys0.zvl_len(), self.joiner.len());
+        debug_assert_eq!(self.keys1.zvl_len(), self.values.zvl_len());
+        debug_assert!(self.keys0.zvl_is_ascending());
+        debug_assert!(self.joiner.zvl_is_ascending());
+        if let Some(last_joiner) = self.joiner.last() {
+            debug_assert_eq!(last_joiner as usize, self.keys1.zvl_len());
+        }
+        for i in 0..self.joiner.len() {
+            let j0 = if i == 0 {
+                0
+            } else {
+                self.joiner.get(i - 1).unwrap() as usize
+            };
+            let j1 = self.joiner.get(i).unwrap() as usize;
+            debug_assert_ne!(j0, j1);
+            for j in (j0 + 1)..j1 {
+                let m0 = self.keys1.zvl_get(j - 1).unwrap();
+                let m1 = self.keys1.zvl_get(j).unwrap();
+                debug_assert_eq!(Ordering::Less, K1::Container::get_cmp_get(m0, m1));
+            }
+        }
+    }
+}
+
+impl<'a, K0, K1, V> ZeroMap2d<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a> + Ord,
+    K1: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K0: ?Sized,
+    K1: ?Sized,
+    V: ?Sized,
+{
+    /// Gets a cursor for `key0`. If `None`, then `key0` is not in the map. If `Some`,
+    /// then `key0` is in the map, and `key1` can be queried.
+    ///
+    /// ```rust
+    /// use zerovec::ZeroMap2d;
+    ///
+    /// let mut map = ZeroMap2d::new();
+    /// map.insert(&1u32, "one", "foo");
+    /// map.insert(&2, "one", "bar");
+    /// map.insert(&2, "two", "baz");
+    /// assert_eq!(map.get0(&1).unwrap().get1("one").unwrap(), "foo");
+    /// assert_eq!(map.get0(&1).unwrap().get1("two"), None);
+    /// assert_eq!(map.get0(&2).unwrap().get1("one").unwrap(), "bar");
+    /// assert_eq!(map.get0(&2).unwrap().get1("two").unwrap(), "baz");
+    /// assert_eq!(map.get0(&3), None);
+    /// ```
+    #[inline]
+    pub fn get0<'l>(&'l self, key0: &K0) -> Option<ZeroMap2dCursor<'l, 'a, K0, K1, V>> {
+        let key0_index = self.keys0.zvl_binary_search(key0).ok()?;
+        Some(ZeroMap2dCursor::from_cow(self, key0_index))
+    }
+
+    /// Binary search the map for `key0`, returning a cursor.
+    ///
+    /// ```rust
+    /// use zerovec::maps::ZeroMap2dBorrowed;
+    /// use zerovec::ZeroMap2d;
+    ///
+    /// let mut map = ZeroMap2d::new();
+    /// map.insert(&1, "one", "foo");
+    /// map.insert(&2, "two", "bar");
+    /// assert!(matches!(map.get0_by(|probe| probe.cmp(&1)), Some(_)));
+    /// assert!(matches!(map.get0_by(|probe| probe.cmp(&3)), None));
+    /// ```
+    pub fn get0_by<'l>(
+        &'l self,
+        predicate: impl FnMut(&K0) -> Ordering,
+    ) -> Option<ZeroMap2dCursor<'l, 'a, K0, K1, V>> {
+        let key0_index = self.keys0.zvl_binary_search_by(predicate).ok()?;
+        Some(ZeroMap2dCursor::from_cow(self, key0_index))
+    }
+
+    /// Returns whether `key0` is contained in this map
+    ///
+    /// ```rust
+    /// use zerovec::ZeroMap2d;
+    ///
+    /// let mut map = ZeroMap2d::new();
+    /// map.insert(&1, "one", "foo");
+    /// map.insert(&2, "two", "bar");
+    /// assert!(map.contains_key0(&1));
+    /// assert!(!map.contains_key0(&3));
+    /// ```
+    pub fn contains_key0(&self, key0: &K0) -> bool {
+        self.keys0.zvl_binary_search(key0).is_ok()
+    }
+
+    // INTERNAL ROUTINES FOLLOW //
+
+    /// Same as `get_range_for_key0`, but creates key0 if it doesn't already exist
+    fn get_or_insert_range_for_key0(&mut self, key0: &K0) -> (usize, Range<usize>) {
+        match self.keys0.zvl_binary_search(key0) {
+            Ok(key0_index) => (key0_index, self.get_range_for_key0_index(key0_index)),
+            Err(key0_index) => {
+                // Add an entry to self.keys0 and self.joiner
+                let joiner_value = if key0_index == 0 {
+                    0
+                } else {
+                    debug_assert!(key0_index <= self.joiner.len());
+                    // The unwrap is protected by the debug_assert above and key0_index != 0
+                    #[allow(clippy::unwrap_used)]
+                    self.joiner.get(key0_index - 1).unwrap()
+                };
+                self.keys0.zvl_insert(key0_index, key0);
+                self.joiner
+                    .with_mut(|v| v.insert(key0_index, joiner_value.to_unaligned()));
+                (key0_index, (joiner_value as usize)..(joiner_value as usize))
+            }
+        }
+    }
+}
+
+impl<'a, K0, K1, V> ZeroMap2d<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a> + Ord,
+    K1: ZeroMapKV<'a> + Ord,
+    V: ZeroMapKV<'a>,
+    V: Copy,
+    K0: ?Sized,
+    K1: ?Sized,
+{
+    /// For cases when `V` is fixed-size, obtain a direct copy of `V` instead of `V::ULE`
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use zerovec::ZeroMap2d;
+    /// let mut map: ZeroMap2d<u16, u16, u16> = ZeroMap2d::new();
+    /// map.insert(&1, &2, &3);
+    /// map.insert(&1, &4, &5);
+    /// map.insert(&6, &7, &8);
+    ///
+    /// assert_eq!(map.get_copied_2d(&6, &7), Some(8));
+    /// ```
+    #[inline]
+    pub fn get_copied_2d(&self, key0: &K0, key1: &K1) -> Option<V> {
+        self.get0(key0)?.get1_copied(key1)
+    }
+}
+
+impl<'a, K0, K1, V> From<ZeroMap2dBorrowed<'a, K0, K1, V>> for ZeroMap2d<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a>,
+    K1: ZeroMapKV<'a>,
+    V: ZeroMapKV<'a>,
+    K0: ?Sized,
+    K1: ?Sized,
+    V: ?Sized,
+{
+    fn from(other: ZeroMap2dBorrowed<'a, K0, K1, V>) -> Self {
+        Self {
+            keys0: K0::Container::zvl_from_borrowed(other.keys0),
+            joiner: other.joiner.as_zerovec(),
+            keys1: K1::Container::zvl_from_borrowed(other.keys1),
+            values: V::Container::zvl_from_borrowed(other.values),
+        }
+    }
+}
+
+// We can't use the default PartialEq because ZeroMap2d is invariant
+// so otherwise rustc will not automatically allow you to compare ZeroMaps
+// with different lifetimes
+impl<'a, 'b, K0, K1, V> PartialEq<ZeroMap2d<'b, K0, K1, V>> for ZeroMap2d<'a, K0, K1, V>
+where
+    K0: for<'c> ZeroMapKV<'c> + ?Sized,
+    K1: for<'c> ZeroMapKV<'c> + ?Sized,
+    V: for<'c> ZeroMapKV<'c> + ?Sized,
+    <K0 as ZeroMapKV<'a>>::Container: PartialEq<<K0 as ZeroMapKV<'b>>::Container>,
+    <K1 as ZeroMapKV<'a>>::Container: PartialEq<<K1 as ZeroMapKV<'b>>::Container>,
+    <V as ZeroMapKV<'a>>::Container: PartialEq<<V as ZeroMapKV<'b>>::Container>,
+{
+    fn eq(&self, other: &ZeroMap2d<'b, K0, K1, V>) -> bool {
+        self.keys0.eq(&other.keys0)
+            && self.joiner.eq(&other.joiner)
+            && self.keys1.eq(&other.keys1)
+            && self.values.eq(&other.values)
+    }
+}
+
+impl<'a, K0, K1, V> fmt::Debug for ZeroMap2d<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a> + ?Sized,
+    K1: ZeroMapKV<'a> + ?Sized,
+    V: ZeroMapKV<'a> + ?Sized,
+    <K0 as ZeroMapKV<'a>>::Container: fmt::Debug,
+    <K1 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("ZeroMap2d")
+            .field("keys0", &self.keys0)
+            .field("joiner", &self.joiner)
+            .field("keys1", &self.keys1)
+            .field("values", &self.values)
+            .finish()
+    }
+}
+
+impl<'a, K0, K1, V> Clone for ZeroMap2d<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a> + ?Sized,
+    K1: ZeroMapKV<'a> + ?Sized,
+    V: ZeroMapKV<'a> + ?Sized,
+    <K0 as ZeroMapKV<'a>>::Container: Clone,
+    <K1 as ZeroMapKV<'a>>::Container: Clone,
+    <V as ZeroMapKV<'a>>::Container: Clone,
+{
+    fn clone(&self) -> Self {
+        Self {
+            keys0: self.keys0.clone(),
+            joiner: self.joiner.clone(),
+            keys1: self.keys1.clone(),
+            values: self.values.clone(),
+        }
+    }
+}
+
+impl<'a, A, B, C, K0, K1, V> FromIterator<(A, B, C)> for ZeroMap2d<'a, K0, K1, V>
+where
+    A: Borrow<K0>,
+    B: Borrow<K1>,
+    C: Borrow<V>,
+    K0: ZeroMapKV<'a> + ?Sized + Ord,
+    K1: ZeroMapKV<'a> + ?Sized + Ord,
+    V: ZeroMapKV<'a> + ?Sized,
+{
+    fn from_iter<T>(iter: T) -> Self
+    where
+        T: IntoIterator<Item = (A, B, C)>,
+    {
+        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 (key0, key1, value) in iter {
+            if let Some((key0, key1, value)) =
+                map.try_append(key0.borrow(), key1.borrow(), value.borrow())
+            {
+                map.insert(key0, key1, value);
+            }
+        }
+        #[cfg(debug_assertions)]
+        map.check_invariants();
+        map
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+    use alloc::collections::BTreeMap;
+
+    #[test]
+    fn stress_test() {
+        let mut zm2d = ZeroMap2d::<u16, str, str>::new();
+
+        assert_eq!(
+            format!("{zm2d:?}"),
+            "ZeroMap2d { keys0: ZeroVec([]), joiner: ZeroVec([]), keys1: [], values: [] }"
+        );
+        assert_eq!(zm2d.get0(&0), None);
+
+        let result = zm2d.try_append(&3, "ccc", "CCC");
+        assert!(result.is_none());
+
+        assert_eq!(format!("{zm2d:?}"), "ZeroMap2d { keys0: ZeroVec([3]), joiner: ZeroVec([1]), keys1: [\"ccc\"], values: [\"CCC\"] }");
+        assert_eq!(zm2d.get0(&0), None);
+        assert_eq!(zm2d.get0(&3).unwrap().get1(""), None);
+        assert_eq!(zm2d.get_2d(&3, "ccc"), Some("CCC"));
+        assert_eq!(zm2d.get0(&99), None);
+
+        let result = zm2d.try_append(&3, "eee", "EEE");
+        assert!(result.is_none());
+
+        assert_eq!(format!("{zm2d:?}"), "ZeroMap2d { keys0: ZeroVec([3]), joiner: ZeroVec([2]), keys1: [\"ccc\", \"eee\"], values: [\"CCC\", \"EEE\"] }");
+        assert_eq!(zm2d.get0(&0), None);
+        assert_eq!(zm2d.get0(&3).unwrap().get1(""), None);
+        assert_eq!(zm2d.get_2d(&3, "ccc"), Some("CCC"));
+        assert_eq!(zm2d.get_2d(&3, "eee"), Some("EEE"));
+        assert_eq!(zm2d.get0(&3).unwrap().get1("five"), None);
+        assert_eq!(zm2d.get0(&99), None);
+
+        // Out of order
+        let result = zm2d.try_append(&3, "ddd", "DD0");
+        assert!(result.is_some());
+
+        // Append a few more elements
+        let result = zm2d.try_append(&5, "ddd", "DD1");
+        assert!(result.is_none());
+        let result = zm2d.try_append(&7, "ddd", "DD2");
+        assert!(result.is_none());
+        let result = zm2d.try_append(&7, "eee", "EEE");
+        assert!(result.is_none());
+        let result = zm2d.try_append(&7, "www", "WWW");
+        assert!(result.is_none());
+        let result = zm2d.try_append(&9, "yyy", "YYY");
+        assert!(result.is_none());
+
+        assert_eq!(format!("{zm2d:?}"), "ZeroMap2d { keys0: ZeroVec([3, 5, 7, 9]), joiner: ZeroVec([2, 3, 6, 7]), keys1: [\"ccc\", \"eee\", \"ddd\", \"ddd\", \"eee\", \"www\", \"yyy\"], values: [\"CCC\", \"EEE\", \"DD1\", \"DD2\", \"EEE\", \"WWW\", \"YYY\"] }");
+        assert_eq!(zm2d.get0(&0), None);
+        assert_eq!(zm2d.get0(&3).unwrap().get1(""), None);
+        assert_eq!(zm2d.get_2d(&3, "ccc"), Some("CCC"));
+        assert_eq!(zm2d.get_2d(&3, "eee"), Some("EEE"));
+        assert_eq!(zm2d.get0(&3).unwrap().get1("zzz"), None);
+        assert_eq!(zm2d.get0(&4), None);
+        assert_eq!(zm2d.get0(&5).unwrap().get1("aaa"), None);
+        assert_eq!(zm2d.get_2d(&5, "ddd"), Some("DD1"));
+        assert_eq!(zm2d.get0(&5).unwrap().get1("zzz"), None);
+        assert_eq!(zm2d.get0(&6), None);
+        assert_eq!(zm2d.get0(&7).unwrap().get1("aaa"), None);
+        assert_eq!(zm2d.get_2d(&7, "ddd"), Some("DD2"));
+        assert_eq!(zm2d.get_2d(&7, "eee"), Some("EEE"));
+        assert_eq!(zm2d.get_2d(&7, "www"), Some("WWW"));
+        assert_eq!(zm2d.get0(&7).unwrap().get1("yyy"), None);
+        assert_eq!(zm2d.get0(&7).unwrap().get1("zzz"), None);
+        assert_eq!(zm2d.get0(&8), None);
+        assert_eq!(zm2d.get0(&9).unwrap().get1("aaa"), None);
+        assert_eq!(zm2d.get0(&9).unwrap().get1("www"), None);
+        assert_eq!(zm2d.get_2d(&9, "yyy"), Some("YYY"));
+        assert_eq!(zm2d.get0(&9).unwrap().get1("zzz"), None);
+        assert_eq!(zm2d.get0(&10), None);
+        assert_eq!(zm2d.get0(&99), None);
+
+        // Insert some elements
+        zm2d.insert(&3, "mmm", "MM0");
+        zm2d.insert(&6, "ddd", "DD3");
+        zm2d.insert(&6, "mmm", "MM1");
+        zm2d.insert(&6, "nnn", "NNN");
+
+        assert_eq!(format!("{zm2d:?}"), "ZeroMap2d { keys0: ZeroVec([3, 5, 6, 7, 9]), joiner: ZeroVec([3, 4, 7, 10, 11]), keys1: [\"ccc\", \"eee\", \"mmm\", \"ddd\", \"ddd\", \"mmm\", \"nnn\", \"ddd\", \"eee\", \"www\", \"yyy\"], values: [\"CCC\", \"EEE\", \"MM0\", \"DD1\", \"DD3\", \"MM1\", \"NNN\", \"DD2\", \"EEE\", \"WWW\", \"YYY\"] }");
+        assert_eq!(zm2d.get0(&0), None);
+        assert_eq!(zm2d.get0(&3).unwrap().get1(""), None);
+        assert_eq!(zm2d.get_2d(&3, "ccc"), Some("CCC"));
+        assert_eq!(zm2d.get_2d(&3, "eee"), Some("EEE"));
+        assert_eq!(zm2d.get_2d(&3, "mmm"), Some("MM0"));
+        assert_eq!(zm2d.get0(&3).unwrap().get1("zzz"), None);
+        assert_eq!(zm2d.get0(&4), None);
+        assert_eq!(zm2d.get0(&5).unwrap().get1("aaa"), None);
+        assert_eq!(zm2d.get_2d(&5, "ddd"), Some("DD1"));
+        assert_eq!(zm2d.get0(&5).unwrap().get1("zzz"), None);
+        assert_eq!(zm2d.get0(&6).unwrap().get1("aaa"), None);
+        assert_eq!(zm2d.get_2d(&6, "ddd"), Some("DD3"));
+        assert_eq!(zm2d.get_2d(&6, "mmm"), Some("MM1"));
+        assert_eq!(zm2d.get_2d(&6, "nnn"), Some("NNN"));
+        assert_eq!(zm2d.get0(&6).unwrap().get1("zzz"), None);
+        assert_eq!(zm2d.get0(&7).unwrap().get1("aaa"), None);
+        assert_eq!(zm2d.get_2d(&7, "ddd"), Some("DD2"));
+        assert_eq!(zm2d.get_2d(&7, "eee"), Some("EEE"));
+        assert_eq!(zm2d.get_2d(&7, "www"), Some("WWW"));
+        assert_eq!(zm2d.get0(&7).unwrap().get1("yyy"), None);
+        assert_eq!(zm2d.get0(&7).unwrap().get1("zzz"), None);
+        assert_eq!(zm2d.get0(&8), None);
+        assert_eq!(zm2d.get0(&9).unwrap().get1("aaa"), None);
+        assert_eq!(zm2d.get0(&9).unwrap().get1("www"), None);
+        assert_eq!(zm2d.get_2d(&9, "yyy"), Some("YYY"));
+        assert_eq!(zm2d.get0(&9).unwrap().get1("zzz"), None);
+        assert_eq!(zm2d.get0(&10), None);
+        assert_eq!(zm2d.get0(&99), None);
+
+        // Remove some elements
+        let result = zm2d.remove(&3, "ccc"); // first element
+        assert_eq!(result.as_deref(), Some("CCC"));
+        let result = zm2d.remove(&3, "mmm"); // middle element
+        assert_eq!(result.as_deref(), Some("MM0"));
+        let result = zm2d.remove(&5, "ddd"); // singleton K0
+        assert_eq!(result.as_deref(), Some("DD1"));
+        let result = zm2d.remove(&9, "yyy"); // last element
+        assert_eq!(result.as_deref(), Some("YYY"));
+
+        assert_eq!(format!("{zm2d:?}"), "ZeroMap2d { keys0: ZeroVec([3, 6, 7]), joiner: ZeroVec([1, 4, 7]), keys1: [\"eee\", \"ddd\", \"mmm\", \"nnn\", \"ddd\", \"eee\", \"www\"], values: [\"EEE\", \"DD3\", \"MM1\", \"NNN\", \"DD2\", \"EEE\", \"WWW\"] }");
+    }
+
+    #[test]
+    fn zeromap2d_metazone() {
+        let source_data = [
+            (*b"aedxb", 0, Some(*b"gulf")),
+            (*b"afkbl", 0, Some(*b"afgh")),
+            (*b"ushnl", 0, None),
+            (*b"ushnl", 7272660, Some(*b"haal")),
+            (*b"ushnl", 0, None),
+            (*b"ushnl", 7272660, Some(*b"haal")),
+        ];
+
+        let btreemap: BTreeMap<([u8; 5], i32), Option<[u8; 4]>> = source_data
+            .iter()
+            .copied()
+            .map(|(a, b, c)| ((a, b), c))
+            .collect();
+
+        let zeromap2d: ZeroMap2d<[u8; 5], i32, Option<[u8; 4]>> =
+            source_data.iter().copied().collect();
+
+        let mut btreemap_iter = btreemap.iter();
+
+        for cursor in zeromap2d.iter0() {
+            for (key1, value) in cursor.iter1() {
+                // This code runs for every (key0, key1) pair in order
+                let expected = btreemap_iter.next().unwrap();
+                assert_eq!(
+                    (expected.0 .0, expected.0 .1, expected.1),
+                    (*cursor.key0(), key1.as_unsigned_int() as i32, &value.get())
+                );
+            }
+        }
+        assert!(btreemap_iter.next().is_none());
+    }
+}
diff --git a/third_party/rust/zerovec/src/map2d/mod.rs b/third_party/rust/zerovec/src/map2d/mod.rs
new file mode 100644
index 0000000000..f5465fcf24
--- /dev/null
+++ b/third_party/rust/zerovec/src/map2d/mod.rs
@@ -0,0 +1,18 @@
+// 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 [`ZeroMap2d`](crate::ZeroMap2d) for details.
+
+mod borrowed;
+mod cursor;
+pub(crate) mod map;
+
+#[cfg(feature = "databake")]
+mod databake;
+#[cfg(feature = "serde")]
+mod serde;
+
+pub use crate::ZeroMap2d;
+pub use borrowed::ZeroMap2dBorrowed;
+pub use cursor::ZeroMap2dCursor;
diff --git a/third_party/rust/zerovec/src/map2d/serde.rs b/third_party/rust/zerovec/src/map2d/serde.rs
new file mode 100644
index 0000000000..53e3284b31
--- /dev/null
+++ b/third_party/rust/zerovec/src/map2d/serde.rs
@@ -0,0 +1,430 @@
+// 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::{ZeroMap2d, ZeroMap2dBorrowed, ZeroMap2dCursor};
+use crate::map::{MutableZeroVecLike, ZeroMapKV, ZeroVecLike};
+use crate::ZeroVec;
+use alloc::vec::Vec;
+use core::fmt;
+use core::marker::PhantomData;
+use serde::de::{self, Deserialize, Deserializer, MapAccess, Visitor};
+#[cfg(feature = "serde")]
+use serde::ser::{Serialize, SerializeMap, Serializer};
+
+/// This impl requires enabling the optional `serde` Cargo feature of the `zerovec` crate
+#[cfg(feature = "serde")]
+impl<'a, K0, K1, V> Serialize for ZeroMap2d<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a> + Serialize + ?Sized + Ord,
+    K1: ZeroMapKV<'a> + Serialize + ?Sized + Ord,
+    V: ZeroMapKV<'a> + Serialize + ?Sized,
+    K0::Container: Serialize,
+    K1::Container: Serialize,
+    V::Container: Serialize,
+{
+    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+    where
+        S: Serializer,
+    {
+        if serializer.is_human_readable() {
+            let mut serde_map = serializer.serialize_map(None)?;
+            for cursor in self.iter0() {
+                K0::Container::zvl_get_as_t(cursor.key0(), |k| serde_map.serialize_key(k))?;
+                let inner_map = ZeroMap2dInnerMapSerialize { cursor };
+                serde_map.serialize_value(&inner_map)?;
+            }
+            serde_map.end()
+        } else {
+            (&self.keys0, &self.joiner, &self.keys1, &self.values).serialize(serializer)
+        }
+    }
+}
+
+/// Helper struct for human-serializing the inner map of a ZeroMap2d
+#[cfg(feature = "serde")]
+struct ZeroMap2dInnerMapSerialize<'a, 'l, K0, K1, V>
+where
+    K0: ZeroMapKV<'a> + ?Sized + Ord,
+    K1: ZeroMapKV<'a> + ?Sized + Ord,
+    V: ZeroMapKV<'a> + ?Sized,
+{
+    pub cursor: ZeroMap2dCursor<'l, 'a, K0, K1, V>,
+}
+
+#[cfg(feature = "serde")]
+impl<'a, 'l, K0, K1, V> Serialize for ZeroMap2dInnerMapSerialize<'a, 'l, K0, K1, V>
+where
+    K0: ZeroMapKV<'a> + Serialize + ?Sized + Ord,
+    K1: ZeroMapKV<'a> + Serialize + ?Sized + Ord,
+    V: ZeroMapKV<'a> + Serialize + ?Sized,
+    K0::Container: Serialize,
+    K1::Container: Serialize,
+    V::Container: Serialize,
+{
+    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+    where
+        S: Serializer,
+    {
+        let mut serde_map = serializer.serialize_map(None)?;
+        for (key1, v) in self.cursor.iter1() {
+            K1::Container::zvl_get_as_t(key1, |k| serde_map.serialize_key(k))?;
+            V::Container::zvl_get_as_t(v, |v| serde_map.serialize_value(v))?;
+        }
+        serde_map.end()
+    }
+}
+
+/// This impl requires enabling the optional `serde` Cargo feature of the `zerovec` crate
+#[cfg(feature = "serde")]
+impl<'a, K0, K1, V> Serialize for ZeroMap2dBorrowed<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a> + Serialize + ?Sized + Ord,
+    K1: ZeroMapKV<'a> + Serialize + ?Sized + Ord,
+    V: ZeroMapKV<'a> + Serialize + ?Sized,
+    K0::Container: Serialize,
+    K1::Container: Serialize,
+    V::Container: Serialize,
+{
+    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+    where
+        S: Serializer,
+    {
+        ZeroMap2d::<K0, K1, V>::from(*self).serialize(serializer)
+    }
+}
+
+/// Modified example from https://serde.rs/deserialize-map.html
+struct ZeroMap2dMapVisitor<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a> + ?Sized + Ord,
+    K1: 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 K0::OwnedType, &'a K1::OwnedType, &'a V::OwnedType)>,
+}
+
+impl<'a, K0, K1, V> ZeroMap2dMapVisitor<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a> + ?Sized + Ord,
+    K1: ZeroMapKV<'a> + ?Sized + Ord,
+    V: ZeroMapKV<'a> + ?Sized,
+{
+    fn new() -> Self {
+        ZeroMap2dMapVisitor {
+            marker: PhantomData,
+        }
+    }
+}
+
+impl<'a, 'de, K0, K1, V> Visitor<'de> for ZeroMap2dMapVisitor<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a> + Ord + ?Sized + Ord,
+    K1: ZeroMapKV<'a> + Ord + ?Sized + Ord,
+    V: ZeroMapKV<'a> + ?Sized,
+    K1::Container: Deserialize<'de>,
+    V::Container: Deserialize<'de>,
+    K0::OwnedType: Deserialize<'de>,
+    K1::OwnedType: Deserialize<'de>,
+    V::OwnedType: Deserialize<'de>,
+{
+    type Value = ZeroMap2d<'a, K0, K1, V>;
+
+    fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
+        formatter.write_str("a map produced by ZeroMap2d")
+    }
+
+    fn visit_map<M>(self, mut access: M) -> Result<Self::Value, M::Error>
+    where
+        M: MapAccess<'de>,
+    {
+        let mut map = ZeroMap2d::with_capacity(access.size_hint().unwrap_or(0));
+
+        // On the first level, pull out the K0s and a TupleVecMap of the
+        // K1s and Vs, and then collect them into a ZeroMap2d
+        while let Some((key0, inner_map)) =
+            access.next_entry::<K0::OwnedType, TupleVecMap<K1::OwnedType, V::OwnedType>>()?
+        {
+            for (key1, value) in inner_map.entries.iter() {
+                if map
+                    .try_append(
+                        K0::Container::owned_as_t(&key0),
+                        K1::Container::owned_as_t(key1),
+                        V::Container::owned_as_t(value),
+                    )
+                    .is_some()
+                {
+                    return Err(de::Error::custom(
+                        "ZeroMap2d's keys must be sorted while deserializing",
+                    ));
+                }
+            }
+        }
+
+        Ok(map)
+    }
+}
+
+/// Helper struct for human-deserializing the inner map of a ZeroMap2d
+struct TupleVecMap<K1, V> {
+    pub entries: Vec<(K1, V)>,
+}
+
+struct TupleVecMapVisitor<K1, V> {
+    #[allow(clippy::type_complexity)] // it's a marker type, complexity doesn't matter
+    marker: PhantomData<fn() -> (K1, V)>,
+}
+
+impl<K1, V> TupleVecMapVisitor<K1, V> {
+    fn new() -> Self {
+        TupleVecMapVisitor {
+            marker: PhantomData,
+        }
+    }
+}
+
+impl<'de, K1, V> Visitor<'de> for TupleVecMapVisitor<K1, V>
+where
+    K1: Deserialize<'de>,
+    V: Deserialize<'de>,
+{
+    type Value = TupleVecMap<K1, V>;
+
+    fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
+        formatter.write_str("an inner map produced by ZeroMap2d")
+    }
+
+    fn visit_map<M>(self, mut access: M) -> Result<Self::Value, M::Error>
+    where
+        M: MapAccess<'de>,
+    {
+        let mut result = Vec::with_capacity(access.size_hint().unwrap_or(0));
+        while let Some((key1, value)) = access.next_entry::<K1, V>()? {
+            result.push((key1, value));
+        }
+        Ok(TupleVecMap { entries: result })
+    }
+}
+
+impl<'de, K1, V> Deserialize<'de> for TupleVecMap<K1, V>
+where
+    K1: Deserialize<'de>,
+    V: Deserialize<'de>,
+{
+    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+    where
+        D: Deserializer<'de>,
+    {
+        deserializer.deserialize_map(TupleVecMapVisitor::<K1, V>::new())
+    }
+}
+
+/// This impl requires enabling the optional `serde` Cargo feature of the `zerovec` crate
+impl<'de, 'a, K0, K1, V> Deserialize<'de> for ZeroMap2d<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a> + Ord + ?Sized,
+    K1: ZeroMapKV<'a> + Ord + ?Sized,
+    V: ZeroMapKV<'a> + ?Sized,
+    K0::Container: Deserialize<'de>,
+    K1::Container: Deserialize<'de>,
+    V::Container: Deserialize<'de>,
+    K0::OwnedType: Deserialize<'de>,
+    K1::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_map(ZeroMap2dMapVisitor::<'a, K0, K1, V>::new())
+        } else {
+            let (keys0, joiner, keys1, values): (
+                K0::Container,
+                ZeroVec<u32>,
+                K1::Container,
+                V::Container,
+            ) = Deserialize::deserialize(deserializer)?;
+            // Invariant 1: len(keys0) == len(joiner)
+            if keys0.zvl_len() != joiner.len() {
+                return Err(de::Error::custom(
+                    "Mismatched keys0 and joiner sizes in ZeroMap2d",
+                ));
+            }
+            // Invariant 2: len(keys1) == len(values)
+            if keys1.zvl_len() != values.zvl_len() {
+                return Err(de::Error::custom(
+                    "Mismatched keys1 and value sizes in ZeroMap2d",
+                ));
+            }
+            // Invariant 3: joiner is sorted
+            if !joiner.zvl_is_ascending() {
+                return Err(de::Error::custom(
+                    "ZeroMap2d deserializing joiner array out of order",
+                ));
+            }
+            // Invariant 4: the last element of joiner is the length of keys1
+            if let Some(last_joiner0) = joiner.last() {
+                if keys1.zvl_len() != last_joiner0 as usize {
+                    return Err(de::Error::custom(
+                        "ZeroMap2d deserializing joiner array malformed",
+                    ));
+                }
+            }
+            let result = Self {
+                keys0,
+                joiner,
+                keys1,
+                values,
+            };
+            // In debug mode, check the optional invariants, too
+            #[cfg(debug_assertions)]
+            result.check_invariants();
+            Ok(result)
+        }
+    }
+}
+
+/// This impl requires enabling the optional `serde` Cargo feature of the `zerovec` crate
+impl<'de, 'a, K0, K1, V> Deserialize<'de> for ZeroMap2dBorrowed<'a, K0, K1, V>
+where
+    K0: ZeroMapKV<'a> + Ord + ?Sized,
+    K1: ZeroMapKV<'a> + Ord + ?Sized,
+    V: ZeroMapKV<'a> + ?Sized,
+    K0::Container: Deserialize<'de>,
+    K1::Container: Deserialize<'de>,
+    V::Container: Deserialize<'de>,
+    K0::OwnedType: Deserialize<'de>,
+    K1::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(
+                "ZeroMap2dBorrowed cannot be deserialized from human-readable formats",
+            ))
+        } else {
+            let deserialized: ZeroMap2d<'a, K0, K1, V> = ZeroMap2d::deserialize(deserializer)?;
+            let keys0 = if let Some(keys0) = deserialized.keys0.zvl_as_borrowed_inner() {
+                keys0
+            } else {
+                return Err(de::Error::custom(
+                    "ZeroMap2dBorrowed can only deserialize in zero-copy ways",
+                ));
+            };
+            let joiner = if let Some(joiner) = deserialized.joiner.zvl_as_borrowed_inner() {
+                joiner
+            } else {
+                return Err(de::Error::custom(
+                    "ZeroMap2dBorrowed can only deserialize in zero-copy ways",
+                ));
+            };
+            let keys1 = if let Some(keys1) = deserialized.keys1.zvl_as_borrowed_inner() {
+                keys1
+            } else {
+                return Err(de::Error::custom(
+                    "ZeroMap2dBorrowed 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(
+                    "ZeroMap2dBorrowed can only deserialize in zero-copy ways",
+                ));
+            };
+            Ok(Self {
+                keys0,
+                joiner,
+                keys1,
+                values,
+            })
+        }
+    }
+}
+
+#[cfg(test)]
+#[allow(non_camel_case_types)]
+mod test {
+    use crate::map2d::{ZeroMap2d, ZeroMap2dBorrowed};
+
+    #[derive(serde::Serialize, serde::Deserialize)]
+    struct DeriveTest_ZeroMap2d<'data> {
+        #[serde(borrow)]
+        _data: ZeroMap2d<'data, u16, str, [u8]>,
+    }
+
+    #[derive(serde::Serialize, serde::Deserialize)]
+    struct DeriveTest_ZeroMap2dBorrowed<'data> {
+        #[serde(borrow)]
+        _data: ZeroMap2dBorrowed<'data, u16, str, [u8]>,
+    }
+
+    const JSON_STR: &str = "{\"1\":{\"1\":\"uno\"},\"2\":{\"2\":\"dos\",\"3\":\"tres\"}}";
+    const BINCODE_BYTES: &[u8] = &[
+        8, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 3, 0,
+        0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 0, 3, 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() -> ZeroMap2d<'static, u32, u16, str> {
+        let mut map = ZeroMap2d::new();
+        map.insert(&1, &1, "uno");
+        map.insert(&2, &2, "dos");
+        map.insert(&2, &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: ZeroMap2d<u32, u16, str> =
+            serde_json::from_str(&json_str).expect("deserialize");
+        assert_eq!(format!("{new_map:?}"), format!("{map:?}"));
+    }
+
+    #[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: ZeroMap2d<u32, u16, str> =
+            bincode::deserialize(&bincode_bytes).expect("deserialize");
+        assert_eq!(
+            format!("{new_map:?}"),
+            format!("{map:?}").replace("Owned", "Borrowed"),
+        );
+
+        let new_map: ZeroMap2dBorrowed<u32, u16, str> =
+            bincode::deserialize(&bincode_bytes).expect("deserialize");
+        assert_eq!(
+            format!("{new_map:?}"),
+            format!("{map:?}")
+                .replace("Owned", "Borrowed")
+                .replace("ZeroMap2d", "ZeroMap2dBorrowed")
+        );
+    }
+
+    #[test]
+    fn test_sample_bincode() {
+        // This is the map from the main docs page for ZeroMap2d
+        let mut map: ZeroMap2d<u16, u16, str> = ZeroMap2d::new();
+        map.insert(&1, &2, "three");
+        let bincode_bytes: Vec<u8> = bincode::serialize(&map).expect("serialize");
+        assert_eq!(
+            bincode_bytes.as_slice(),
+            &[
+                2, 0, 0, 0, 0, 0, 0, 0, 1, 0, 4, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0,
+                0, 0, 2, 0, 11, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 116, 104, 114, 101, 101
+            ]
+        );
+    }
+}