Merging upstream version 1.67.1+dfsg1.

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

8 files changed, 1711 insertions, 0 deletions

diff --git a/vendor/litemap/src/lib.rs b/vendor/litemap/src/lib.rs
new file mode 100644
index 000000000..3647ccfcb
--- /dev/null
+++ b/vendor/litemap/src/lib.rs
@@ -0,0 +1,57 @@
+// 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 ).
+
+//! # `litemap`
+//!
+//! `litemap` is a crate providing [`LiteMap`], a highly simplistic "flat" key-value map
+//! based off of a single sorted vector.
+//!
+//! The goal of this crate is to provide a map that is good enough for small
+//! sizes, and does not carry the binary size impact of [`HashMap`](std::collections::HashMap)
+//! or [`BTreeMap`](alloc::collections::BTreeMap).
+//!
+//! If binary size is not a concern, [`std::collections::BTreeMap`] may be a better choice
+//! for your use case. It behaves very similarly to [`LiteMap`] for less than 12 elements,
+//! and upgrades itself gracefully for larger inputs.
+//!
+//! ## Pluggable Backends
+//!
+//! By default, [`LiteMap`] is backed by a [`Vec`]; however, it can be backed by any appropriate
+//! random-access data store, giving that data store a map-like interface. See the [`store`]
+//! module for more details.
+//!
+//! [`Vec`]: alloc::vec::Vec
+
+// https://github.com/unicode-org/icu4x/blob/main/docs/process/boilerplate.md#library-annotations
+#![cfg_attr(not(test), no_std)]
+#![cfg_attr(
+    not(test),
+    deny(
+        clippy::indexing_slicing,
+        clippy::unwrap_used,
+        clippy::expect_used,
+        clippy::panic,
+        clippy::exhaustive_structs,
+        clippy::exhaustive_enums,
+        missing_debug_implementations,
+    )
+)]
+
+// for intra doc links
+#[cfg(doc)]
+extern crate std;
+
+extern crate alloc;
+
+mod map;
+#[cfg(feature = "serde")]
+mod serde;
+#[cfg(feature = "serde")]
+mod serde_helpers;
+pub mod store;
+
+#[cfg(feature = "testing")]
+pub mod testing;
+
+pub use map::LiteMap;
diff --git a/vendor/litemap/src/map.rs b/vendor/litemap/src/map.rs
new file mode 100644
index 000000000..f86383337
--- /dev/null
+++ b/vendor/litemap/src/map.rs
@@ -0,0 +1,672 @@
+// 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::store::*;
+use alloc::borrow::Borrow;
+use alloc::vec::Vec;
+use core::cmp::Ordering;
+use core::iter::FromIterator;
+use core::marker::PhantomData;
+use core::mem;
+use core::ops::{Index, IndexMut};
+
+/// A simple "flat" map based on a sorted vector
+///
+/// See the [module level documentation][super] for why one should use this.
+///
+/// The API is roughly similar to that of [`std::collections::BTreeMap`].
+#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
+#[cfg_attr(feature = "yoke", derive(yoke::Yokeable))]
+pub struct LiteMap<K: ?Sized, V: ?Sized, S = alloc::vec::Vec<(K, V)>> {
+    pub(crate) values: S,
+    pub(crate) _key_type: PhantomData<K>,
+    pub(crate) _value_type: PhantomData<V>,
+}
+
+impl<K, V> LiteMap<K, V> {
+    /// Construct a new [`LiteMap`] backed by Vec
+    pub const fn new_vec() -> Self {
+        Self {
+            values: alloc::vec::Vec::new(),
+            _key_type: PhantomData,
+            _value_type: PhantomData,
+        }
+    }
+}
+
+impl<K, V, S> LiteMap<K, V, S> {
+    /// Construct a new [`LiteMap`] using the given values
+    ///
+    /// The store must be sorted and have no duplicate keys.
+    pub const fn from_sorted_store_unchecked(values: S) -> Self {
+        Self {
+            values,
+            _key_type: PhantomData,
+            _value_type: PhantomData,
+        }
+    }
+}
+
+impl<K, V> LiteMap<K, V, Vec<(K, V)>> {
+    /// Convert a [`LiteMap`] into a sorted `Vec<(K, V)>`.
+    #[inline]
+    pub fn into_tuple_vec(self) -> Vec<(K, V)> {
+        self.values
+    }
+}
+
+impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S>
+where
+    S: StoreConstEmpty<K, V>,
+{
+    /// Create a new empty [`LiteMap`]
+    pub const fn new() -> Self {
+        Self {
+            values: S::EMPTY,
+            _key_type: PhantomData,
+            _value_type: PhantomData,
+        }
+    }
+}
+
+impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S>
+where
+    S: Store<K, V>,
+{
+    /// The number of elements in the [`LiteMap`]
+    pub fn len(&self) -> usize {
+        self.values.lm_len()
+    }
+
+    /// Whether the [`LiteMap`] is empty
+    pub fn is_empty(&self) -> bool {
+        self.values.lm_is_empty()
+    }
+
+    /// Get the key-value pair residing at a particular index
+    ///
+    /// In most cases, prefer [`LiteMap::get()`] over this method.
+    #[inline]
+    pub fn get_indexed(&self, index: usize) -> Option<(&K, &V)> {
+        self.values.lm_get(index)
+    }
+}
+
+impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S>
+where
+    K: Ord,
+    S: Store<K, V>,
+{
+    /// Get the value associated with `key`, if it exists.
+    ///
+    /// ```rust
+    /// use litemap::LiteMap;
+    ///
+    /// let mut map = LiteMap::new_vec();
+    /// map.insert(1, "one");
+    /// map.insert(2, "two");
+    /// assert_eq!(map.get(&1), Some(&"one"));
+    /// assert_eq!(map.get(&3), None);
+    /// ```
+    pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
+    where
+        K: Borrow<Q>,
+        Q: Ord,
+    {
+        match self.find_index(key) {
+            #[allow(clippy::unwrap_used)] // find_index returns a valid index
+            Ok(found) => Some(self.values.lm_get(found).unwrap().1),
+            Err(_) => None,
+        }
+    }
+
+    /// Binary search the map with `predicate` to find a key, returning the value.
+    pub fn get_by(&self, predicate: impl FnMut(&K) -> Ordering) -> Option<&V> {
+        let index = self.values.lm_binary_search_by(predicate).ok()?;
+        self.values.lm_get(index).map(|(_, v)| v)
+    }
+
+    /// Returns whether `key` is contained in this map
+    ///
+    /// ```rust
+    /// use litemap::LiteMap;
+    ///
+    /// let mut map = LiteMap::new_vec();
+    /// 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<Q: ?Sized>(&self, key: &Q) -> bool
+    where
+        K: Borrow<Q>,
+        Q: Ord,
+    {
+        self.find_index(key).is_ok()
+    }
+
+    /// Get the lowest-rank key/value pair from the `LiteMap`, if it exists.
+    ///
+    /// # Examples
+    ///
+    /// ```rust
+    /// use litemap::LiteMap;
+    ///
+    /// let mut map = LiteMap::new_vec();
+    /// assert!(map.try_append(1, "uno").is_none());
+    /// assert!(map.try_append(3, "tres").is_none());
+    ///
+    /// assert_eq!(map.first(), Some((&1, &"uno")));
+    /// ```
+    #[inline]
+    pub fn first(&self) -> Option<(&K, &V)> {
+        self.values.lm_get(0).map(|(k, v)| (k, v))
+    }
+
+    /// Get the highest-rank key/value pair from the `LiteMap`, if it exists.
+    ///
+    /// # Examples
+    ///
+    /// ```rust
+    /// use litemap::LiteMap;
+    ///
+    /// let mut map = LiteMap::new_vec();
+    /// assert!(map.try_append(1, "uno").is_none());
+    /// assert!(map.try_append(3, "tres").is_none());
+    ///
+    /// assert_eq!(map.last(), Some((&3, &"tres")));
+    /// ```
+    #[inline]
+    pub fn last(&self) -> Option<(&K, &V)> {
+        self.values.lm_get(self.len() - 1).map(|(k, v)| (k, v))
+    }
+
+    /// Obtain the index for a given key, or if the key is not found, the index
+    /// at which it would be inserted.
+    ///
+    /// (The return value works equivalently to [`slice::binary_search_by()`])
+    ///
+    /// The indices returned can be used with [`Self::get_indexed()`]. Prefer using
+    /// [`Self::get()`] directly where possible.
+    #[inline]
+    pub fn find_index<Q: ?Sized>(&self, key: &Q) -> Result<usize, usize>
+    where
+        K: Borrow<Q>,
+        Q: Ord,
+    {
+        self.values.lm_binary_search_by(|k| k.borrow().cmp(key))
+    }
+}
+
+impl<K, V, S> LiteMap<K, V, S>
+where
+    S: StoreMut<K, V>,
+{
+    /// Construct a new [`LiteMap`] with a given capacity
+    pub fn with_capacity(capacity: usize) -> Self {
+        Self {
+            values: S::lm_with_capacity(capacity),
+            _key_type: PhantomData,
+            _value_type: PhantomData,
+        }
+    }
+
+    /// Remove all elements from the [`LiteMap`]
+    pub fn clear(&mut self) {
+        self.values.lm_clear()
+    }
+
+    /// Reserve capacity for `additional` more elements to be inserted into
+    /// the [`LiteMap`] to avoid frequent reallocations.
+    ///
+    /// See [`Vec::reserve()`] for more information.
+    ///
+    /// [`Vec::reserve()`]: alloc::vec::Vec::reserve
+    pub fn reserve(&mut self, additional: usize) {
+        self.values.lm_reserve(additional)
+    }
+}
+
+impl<K, V, S> LiteMap<K, V, S>
+where
+    K: Ord,
+    S: StoreMut<K, V>,
+{
+    /// Get the value associated with `key`, if it exists, as a mutable reference.
+    ///
+    /// ```rust
+    /// use litemap::LiteMap;
+    ///
+    /// let mut map = LiteMap::new_vec();
+    /// map.insert(1, "one");
+    /// map.insert(2, "two");
+    /// if let Some(mut v) = map.get_mut(&1) {
+    ///     *v = "uno";
+    /// }
+    /// assert_eq!(map.get(&1), Some(&"uno"));
+    /// ```
+    pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
+    where
+        K: Borrow<Q>,
+        Q: Ord,
+    {
+        match self.find_index(key) {
+            #[allow(clippy::unwrap_used)] // find_index returns a valid index
+            Ok(found) => Some(self.values.lm_get_mut(found).unwrap().1),
+            Err(_) => None,
+        }
+    }
+
+    /// 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 litemap::LiteMap;
+    ///
+    /// let mut map = LiteMap::new_vec();
+    /// assert!(map.try_append(1, "uno").is_none());
+    /// assert!(map.try_append(3, "tres").is_none());
+    ///
+    /// assert!(
+    ///     matches!(map.try_append(3, "tres-updated"), Some((3, "tres-updated"))),
+    ///     "append duplicate of last key",
+    /// );
+    ///
+    /// assert!(
+    ///     matches!(map.try_append(2, "dos"), Some((2, "dos"))),
+    ///     "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(&mut self, key: K, value: V) -> Option<(K, V)> {
+        if let Some(last) = self.values.lm_last() {
+            if last.0 >= &key {
+                return Some((key, value));
+            }
+        }
+
+        self.values.lm_push(key, value);
+        None
+    }
+
+    /// Insert `value` with `key`, returning the existing value if it exists.
+    ///
+    /// ```rust
+    /// use litemap::LiteMap;
+    ///
+    /// let mut map = LiteMap::new_vec();
+    /// 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> {
+        self.insert_save_key(key, value).map(|(_, v)| v)
+    }
+
+    /// Version of [`Self::insert()`] that returns both the key and the old value.
+    fn insert_save_key(&mut self, key: K, value: V) -> Option<(K, V)> {
+        match self.values.lm_binary_search_by(|k| k.cmp(&key)) {
+            #[allow(clippy::unwrap_used)] // Index came from binary_search
+            Ok(found) => Some((
+                key,
+                mem::replace(self.values.lm_get_mut(found).unwrap().1, value),
+            )),
+            Err(ins) => {
+                self.values.lm_insert(ins, key, value);
+                None
+            }
+        }
+    }
+
+    /// Attempts to insert a unique entry into the map.
+    ///
+    /// If `key` is not already in the map, inserts it with the corresponding `value`
+    /// and returns `None`.
+    ///
+    /// If `key` is already in the map, no change is made to the map, and the key and value
+    /// are returned back to the caller.
+    ///
+    /// ```
+    /// use litemap::LiteMap;
+    ///
+    /// let mut map = LiteMap::new_vec();
+    /// map.insert(1, "one");
+    /// map.insert(3, "three");
+    ///
+    /// // 2 is not yet in the map...
+    /// assert_eq!(map.try_insert(2, "two"), None);
+    /// assert_eq!(map.len(), 3);
+    ///
+    /// // ...but now it is.
+    /// assert_eq!(map.try_insert(2, "TWO"), Some((2, "TWO")));
+    /// assert_eq!(map.len(), 3);
+    /// ```
+    pub fn try_insert(&mut self, key: K, value: V) -> Option<(K, V)> {
+        match self.values.lm_binary_search_by(|k| k.cmp(&key)) {
+            Ok(_) => Some((key, value)),
+            Err(ins) => {
+                self.values.lm_insert(ins, key, value);
+                None
+            }
+        }
+    }
+
+    /// Remove the value at `key`, returning it if it exists.
+    ///
+    /// ```rust
+    /// use litemap::LiteMap;
+    ///
+    /// let mut map = LiteMap::new_vec();
+    /// map.insert(1, "one");
+    /// map.insert(2, "two");
+    /// assert_eq!(map.remove(&1), Some("one"));
+    /// assert_eq!(map.get(&1), None);
+    /// ```
+    pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
+    where
+        K: Borrow<Q>,
+        Q: Ord,
+    {
+        match self.values.lm_binary_search_by(|k| k.borrow().cmp(key)) {
+            Ok(found) => Some(self.values.lm_remove(found).1),
+            Err(_) => None,
+        }
+    }
+}
+
+impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S>
+where
+    K: Ord,
+    S: StoreIterableMut<'a, K, V> + StoreFromIterator<K, V>,
+{
+    /// Insert all elements from `other` into this `LiteMap`.
+    ///
+    /// If `other` contains keys that already exist in `self`, the values in `other` replace the
+    /// corresponding ones in `self`, and the rejected items from `self` are returned as a new
+    /// `LiteMap`. Otherwise, `None` is returned.
+    ///
+    /// The implementation of this function is optimized if `self` and `other` have no overlap.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use litemap::LiteMap;
+    ///
+    /// let mut map1 = LiteMap::new_vec();
+    /// map1.insert(1, "one");
+    /// map1.insert(2, "two");
+    ///
+    /// let mut map2 = LiteMap::new_vec();
+    /// map2.insert(2, "TWO");
+    /// map2.insert(4, "FOUR");
+    ///
+    /// let leftovers = map1.extend_from_litemap(map2);
+    ///
+    /// assert_eq!(map1.len(), 3);
+    /// assert_eq!(map1.get(&1), Some("one").as_ref());
+    /// assert_eq!(map1.get(&2), Some("TWO").as_ref());
+    /// assert_eq!(map1.get(&4), Some("FOUR").as_ref());
+    ///
+    /// let map3 = leftovers.expect("Duplicate keys");
+    /// assert_eq!(map3.len(), 1);
+    /// assert_eq!(map3.get(&2), Some("two").as_ref());
+    /// ```
+    pub fn extend_from_litemap(&mut self, other: Self) -> Option<Self> {
+        if self.is_empty() {
+            self.values = other.values;
+            return None;
+        }
+        if other.is_empty() {
+            return None;
+        }
+        if self.last().map(|(k, _)| k) < other.first().map(|(k, _)| k) {
+            // append other to self
+            self.values.lm_extend_end(other.values);
+            None
+        } else if self.first().map(|(k, _)| k) > other.last().map(|(k, _)| k) {
+            // prepend other to self
+            self.values.lm_extend_start(other.values);
+            None
+        } else {
+            // insert every element
+            let leftover_tuples = other
+                .values
+                .lm_into_iter()
+                .filter_map(|(k, v)| self.insert_save_key(k, v))
+                .collect();
+            let ret = LiteMap {
+                values: leftover_tuples,
+                _key_type: PhantomData,
+                _value_type: PhantomData,
+            };
+            if ret.is_empty() {
+                None
+            } else {
+                Some(ret)
+            }
+        }
+    }
+}
+
+impl<K, V, S> Default for LiteMap<K, V, S>
+where
+    S: Store<K, V> + Default,
+{
+    fn default() -> Self {
+        Self {
+            values: S::default(),
+            _key_type: PhantomData,
+            _value_type: PhantomData,
+        }
+    }
+}
+impl<K, V, S> Index<&'_ K> for LiteMap<K, V, S>
+where
+    K: Ord,
+    S: Store<K, V>,
+{
+    type Output = V;
+    fn index(&self, key: &K) -> &V {
+        #[allow(clippy::panic)] // documented
+        match self.get(key) {
+            Some(v) => v,
+            None => panic!("no entry found for key"),
+        }
+    }
+}
+impl<K, V, S> IndexMut<&'_ K> for LiteMap<K, V, S>
+where
+    K: Ord,
+    S: StoreMut<K, V>,
+{
+    fn index_mut(&mut self, key: &K) -> &mut V {
+        #[allow(clippy::panic)] // documented
+        match self.get_mut(key) {
+            Some(v) => v,
+            None => panic!("no entry found for key"),
+        }
+    }
+}
+impl<K, V, S> FromIterator<(K, V)> for LiteMap<K, V, S>
+where
+    K: Ord,
+    S: StoreMut<K, V>,
+{
+    fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
+        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, value) {
+                map.insert(key, value);
+            }
+        }
+
+        map
+    }
+}
+
+impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S>
+where
+    S: StoreIterable<'a, K, V>,
+{
+    /// Produce an ordered iterator over key-value pairs
+    pub fn iter(&'a self) -> impl Iterator<Item = (&'a K, &'a V)> + DoubleEndedIterator {
+        self.values.lm_iter()
+    }
+
+    /// Produce an ordered iterator over keys
+    pub fn iter_keys(&'a self) -> impl Iterator<Item = &'a K> + DoubleEndedIterator {
+        self.values.lm_iter().map(|val| val.0)
+    }
+
+    /// Produce an iterator over values, ordered by their keys
+    pub fn iter_values(&'a self) -> impl Iterator<Item = &'a V> + DoubleEndedIterator {
+        self.values.lm_iter().map(|val| val.1)
+    }
+}
+
+impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S>
+where
+    S: StoreIterableMut<'a, K, V>,
+{
+    /// Produce an ordered mutable iterator over key-value pairs
+    pub fn iter_mut(
+        &'a mut self,
+    ) -> impl Iterator<Item = (&'a K, &'a mut V)> + DoubleEndedIterator {
+        self.values.lm_iter_mut()
+    }
+}
+
+impl<K, V, S> LiteMap<K, V, S>
+where
+    S: StoreMut<K, V>,
+{
+    /// Retains only the elements specified by the predicate.
+    ///
+    /// In other words, remove all elements such that `f((&k, &v))` returns `false`.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// use litemap::LiteMap;
+    ///
+    /// let mut map = LiteMap::new_vec();
+    /// map.insert(1, "one");
+    /// map.insert(2, "two");
+    /// map.insert(3, "three");
+    ///
+    /// // Retain elements with odd keys
+    /// map.retain(|k, _| k % 2 == 1);
+    ///
+    /// assert_eq!(map.get(&1), Some(&"one"));
+    /// assert_eq!(map.get(&2), None);
+    /// ```
+    #[inline]
+    pub fn retain<F>(&mut self, predicate: F)
+    where
+        F: FnMut(&K, &V) -> bool,
+    {
+        self.values.lm_retain(predicate)
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use crate::LiteMap;
+
+    #[test]
+    fn from_iterator() {
+        let mut expected = LiteMap::with_capacity(4);
+        expected.insert(1, "updated-one");
+        expected.insert(2, "original-two");
+        expected.insert(3, "original-three");
+        expected.insert(4, "updated-four");
+
+        let actual = vec![
+            (1, "original-one"),
+            (2, "original-two"),
+            (4, "original-four"),
+            (4, "updated-four"),
+            (1, "updated-one"),
+            (3, "original-three"),
+        ]
+        .into_iter()
+        .collect::<LiteMap<_, _>>();
+
+        assert_eq!(expected, actual);
+    }
+
+    fn make_13() -> LiteMap<usize, &'static str> {
+        let mut result = LiteMap::new();
+        result.insert(1, "one");
+        result.insert(3, "three");
+        result
+    }
+
+    fn make_24() -> LiteMap<usize, &'static str> {
+        let mut result = LiteMap::new();
+        result.insert(2, "TWO");
+        result.insert(4, "FOUR");
+        result
+    }
+
+    fn make_46() -> LiteMap<usize, &'static str> {
+        let mut result = LiteMap::new();
+        result.insert(4, "four");
+        result.insert(6, "six");
+        result
+    }
+
+    #[test]
+    fn extend_from_litemap_append() {
+        let mut map = LiteMap::new();
+        map.extend_from_litemap(make_13())
+            .ok_or(())
+            .expect_err("Append to empty map");
+        map.extend_from_litemap(make_46())
+            .ok_or(())
+            .expect_err("Append to lesser map");
+        assert_eq!(map.len(), 4);
+    }
+
+    #[test]
+    fn extend_from_litemap_prepend() {
+        let mut map = LiteMap::new();
+        map.extend_from_litemap(make_46())
+            .ok_or(())
+            .expect_err("Prepend to empty map");
+        map.extend_from_litemap(make_13())
+            .ok_or(())
+            .expect_err("Prepend to lesser map");
+        assert_eq!(map.len(), 4);
+    }
+
+    #[test]
+    fn extend_from_litemap_insert() {
+        let mut map = LiteMap::new();
+        map.extend_from_litemap(make_13())
+            .ok_or(())
+            .expect_err("Append to empty map");
+        map.extend_from_litemap(make_24())
+            .ok_or(())
+            .expect_err("Insert with no conflict");
+        map.extend_from_litemap(make_46())
+            .ok_or(())
+            .expect("Insert with conflict");
+        assert_eq!(map.len(), 5);
+    }
+}
diff --git a/vendor/litemap/src/serde.rs b/vendor/litemap/src/serde.rs
new file mode 100644
index 000000000..7550fb7a9
--- /dev/null
+++ b/vendor/litemap/src/serde.rs
@@ -0,0 +1,214 @@
+// 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::LiteMap;
+use crate::store::*;
+use core::fmt;
+use core::marker::PhantomData;
+use serde::de::{MapAccess, SeqAccess, Visitor};
+use serde::{Deserialize, Deserializer};
+
+#[cfg(feature = "serde")]
+use serde::{ser::SerializeMap, Serialize, Serializer};
+
+#[cfg(feature = "serde")]
+impl<K, V, R> Serialize for LiteMap<K, V, R>
+where
+    K: Serialize,
+    V: Serialize,
+    R: Store<K, V> + Serialize,
+{
+    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+    where
+        S: Serializer,
+    {
+        // 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 serializer.is_human_readable() {
+            if let Some((ref k, _)) = self.values.lm_get(0) {
+                if !super::serde_helpers::is_num_or_string(k) {
+                    return self.values.serialize(serializer);
+                }
+                // continue to regular serialization
+            }
+        }
+        let mut map = serializer.serialize_map(Some(self.len()))?;
+        let mut i = 0;
+        while i < self.values.lm_len() {
+            #[allow(clippy::unwrap_used)] // i is in range
+            let (k, v) = self.values.lm_get(i).unwrap();
+            map.serialize_entry(k, v)?;
+            i += 1;
+        }
+        map.end()
+    }
+}
+
+/// Modified example from https://serde.rs/deserialize-map.html
+#[allow(clippy::type_complexity)]
+struct LiteMapVisitor<K, V, R> {
+    marker: PhantomData<fn() -> LiteMap<K, V, R>>,
+}
+
+impl<K, V, R> LiteMapVisitor<K, V, R> {
+    fn new() -> Self {
+        Self {
+            marker: PhantomData,
+        }
+    }
+}
+
+impl<'de, K, V, R> Visitor<'de> for LiteMapVisitor<K, V, R>
+where
+    K: Deserialize<'de> + Ord,
+    V: Deserialize<'de>,
+    R: StoreMut<K, V>,
+{
+    type Value = LiteMap<K, V, R>;
+
+    fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
+        formatter.write_str("a map produced by LiteMap")
+    }
+
+    fn visit_seq<S>(self, mut access: S) -> Result<Self::Value, S::Error>
+    where
+        S: SeqAccess<'de>,
+    {
+        let mut map = LiteMap::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()? {
+            // Try to append it at the end, hoping for a sorted map.
+            // If not sorted, insert as usual.
+            // This allows for arbitrary maps (e.g. from user JSON)
+            // to be deserialized into LiteMap
+            // without impacting performance in the case of deserializing
+            // a serialized map that came from another LiteMap
+            if let Some((key, value)) = map.try_append(key, value) {
+                // Note: this effectively selection sorts the map,
+                // which isn't efficient for large maps
+                map.insert(key, value);
+            }
+        }
+
+        Ok(map)
+    }
+
+    fn visit_map<M>(self, mut access: M) -> Result<Self::Value, M::Error>
+    where
+        M: MapAccess<'de>,
+    {
+        let mut map = LiteMap::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()? {
+            // Try to append it at the end, hoping for a sorted map.
+            // If not sorted, insert as usual.
+            // This allows for arbitrary maps (e.g. from user JSON)
+            // to be deserialized into LiteMap
+            // without impacting performance in the case of deserializing
+            // a serialized map that came from another LiteMap
+            if let Some((key, value)) = map.try_append(key, value) {
+                // Note: this effectively selection sorts the map,
+                // which isn't efficient for large maps
+                map.insert(key, value);
+            }
+        }
+
+        Ok(map)
+    }
+}
+
+impl<'de, K, V, R> Deserialize<'de> for LiteMap<K, V, R>
+where
+    K: Ord + Deserialize<'de>,
+    V: Deserialize<'de>,
+    R: StoreMut<K, V>,
+{
+    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+    where
+        D: Deserializer<'de>,
+    {
+        if deserializer.is_human_readable() {
+            // deserialize_any only works on self-describing (human-readable)
+            // formats
+            deserializer.deserialize_any(LiteMapVisitor::new())
+        } else {
+            deserializer.deserialize_map(LiteMapVisitor::new())
+        }
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use crate::LiteMap;
+    use alloc::borrow::ToOwned;
+    use alloc::string::String;
+    use alloc::vec;
+
+    fn get_simple_map() -> LiteMap<u32, String> {
+        vec![
+            (1, "one".to_owned()),
+            (2, "two".to_owned()),
+            (4, "four".to_owned()),
+            (5, "five".to_owned()),
+        ]
+        .into_iter()
+        .collect()
+    }
+
+    fn get_tuple_map() -> LiteMap<(u32, String), String> {
+        vec![
+            ((1, "en".to_owned()), "one".to_owned()),
+            ((1, "zh".to_owned()), "一".to_owned()),
+            ((2, "en".to_owned()), "two".to_owned()),
+            ((2, "zh".to_owned()), "二".to_owned()),
+            ((4, "en".to_owned()), "four".to_owned()),
+            ((5, "en".to_owned()), "five".to_owned()),
+            ((5, "zh".to_owned()), "五".to_owned()),
+            ((7, "zh".to_owned()), "七".to_owned()),
+        ]
+        .into_iter()
+        .collect()
+    }
+
+    #[test]
+    fn test_roundtrip_json() {
+        let map = get_simple_map();
+        let json = serde_json::to_string(&map).unwrap();
+        assert_eq!(
+            json,
+            "{\"1\":\"one\",\"2\":\"two\",\"4\":\"four\",\"5\":\"five\"}"
+        );
+        let deserialized: LiteMap<u32, String> = serde_json::from_str(&json).unwrap();
+        assert_eq!(map, deserialized);
+
+        let map = get_tuple_map();
+        let json = serde_json::to_string(&map).unwrap();
+        assert_eq!(
+            json,
+            "[[[1,\"en\"],\"one\"],[[1,\"zh\"],\"一\"],[[2,\"en\"],\"two\"],\
+                          [[2,\"zh\"],\"二\"],[[4,\"en\"],\"four\"],[[5,\"en\"],\"five\"],\
+                          [[5,\"zh\"],\"五\"],[[7,\"zh\"],\"七\"]]"
+        );
+        let deserialized: LiteMap<(u32, String), String> = serde_json::from_str(&json).unwrap();
+        assert_eq!(map, deserialized);
+    }
+
+    #[test]
+    fn test_roundtrip_postcard() {
+        let map = get_simple_map();
+        let postcard = postcard::to_stdvec(&map).unwrap();
+        let deserialized: LiteMap<u32, String> = postcard::from_bytes(&postcard).unwrap();
+        assert_eq!(map, deserialized);
+
+        let map = get_tuple_map();
+        let postcard = postcard::to_stdvec(&map).unwrap();
+        let deserialized: LiteMap<(u32, String), String> = postcard::from_bytes(&postcard).unwrap();
+        assert_eq!(map, deserialized);
+    }
+}
diff --git a/vendor/litemap/src/serde_helpers.rs b/vendor/litemap/src/serde_helpers.rs
new file mode 100644
index 000000000..b1ead938a
--- /dev/null
+++ b/vendor/litemap/src/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/litemap/src/store/mod.rs b/vendor/litemap/src/store/mod.rs
new file mode 100644
index 000000000..e4ba6f7b9
--- /dev/null
+++ b/vendor/litemap/src/store/mod.rs
@@ -0,0 +1,165 @@
+// 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 ).
+
+//! Traits for pluggable LiteMap backends.
+//!
+//! By default, LiteMap is backed by a `Vec`. However, in some environments, it may be desirable
+//! to use a different data store while still using LiteMap to manage proper ordering of items.
+//!
+//! The general guidelines for a performant data store are:
+//!
+//! 1. Must support efficient random access for binary search
+//! 2. Should support efficient append operations for deserialization
+//!
+//! To plug a custom data store into LiteMap, implement:
+//!
+//! - [`Store`] for most of the methods
+//! - [`StoreIterable`] for methods that return iterators
+//! - [`StoreFromIterator`] to enable `FromIterator` for LiteMap
+//!
+//! To test your implementation, enable the `"testing"` feature and use [`check_store()`].
+//!
+//! [`check_store()`]: crate::testing::check_store
+
+mod slice_impl;
+#[cfg(feature = "alloc")]
+mod vec_impl;
+
+use core::cmp::Ordering;
+use core::iter::DoubleEndedIterator;
+use core::iter::FromIterator;
+use core::iter::Iterator;
+
+/// Trait to enable const construction of empty store.
+pub trait StoreConstEmpty<K: ?Sized, V: ?Sized> {
+    /// An empty store
+    const EMPTY: Self;
+}
+
+/// Trait to enable pluggable backends for LiteMap.
+///
+/// Some methods have default implementations provided for convenience; however, it is generally
+/// better to implement all methods that your data store supports.
+pub trait Store<K: ?Sized, V: ?Sized>: Sized {
+    /// Returns the number of elements in the store.
+    fn lm_len(&self) -> usize;
+
+    /// Returns whether the store is empty (contains 0 elements).
+    fn lm_is_empty(&self) -> bool {
+        self.lm_len() == 0
+    }
+
+    /// Gets a key/value pair at the specified index.
+    fn lm_get(&self, index: usize) -> Option<(&K, &V)>;
+
+    /// Gets the last element in the store, or None if the store is empty.
+    fn lm_last(&self) -> Option<(&K, &V)> {
+        let len = self.lm_len();
+        if len == 0 {
+            None
+        } else {
+            self.lm_get(len - 1)
+        }
+    }
+
+    /// Searches the store for a particular element with a comparator function.
+    ///
+    /// See the binary search implementation on `slice` for more information.
+    fn lm_binary_search_by<F>(&self, cmp: F) -> Result<usize, usize>
+    where
+        F: FnMut(&K) -> Ordering;
+}
+
+pub trait StoreMut<K, V>: Store<K, V> {
+    /// Creates a new store with the specified capacity hint.
+    ///
+    /// Implementations may ignore the argument if they do not support pre-allocating capacity.
+    fn lm_with_capacity(capacity: usize) -> Self;
+
+    /// Reserves additional capacity in the store.
+    ///
+    /// Implementations may ignore the argument if they do not support pre-allocating capacity.
+    fn lm_reserve(&mut self, additional: usize);
+
+    /// Gets a key/value pair at the specified index, with a mutable value.
+    fn lm_get_mut(&mut self, index: usize) -> Option<(&K, &mut V)>;
+    /// Pushes one additional item onto the store.
+    fn lm_push(&mut self, key: K, value: V);
+
+    /// Inserts an item at a specific index in the store.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `index` is greater than the length.
+    fn lm_insert(&mut self, index: usize, key: K, value: V);
+
+    /// Removes an item at a specific index in the store.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `index` is greater than the length.
+    fn lm_remove(&mut self, index: usize) -> (K, V);
+
+    /// Removes all items from the store.
+    fn lm_clear(&mut self);
+
+    /// Retains items satisfying a predicate in this store.
+    fn lm_retain<F>(&mut self, mut predicate: F)
+    where
+        F: FnMut(&K, &V) -> bool,
+    {
+        let mut i = 0;
+        while i < self.lm_len() {
+            #[allow(clippy::unwrap_used)] // i is in range
+            let (k, v) = self.lm_get(i).unwrap();
+            if predicate(k, v) {
+                i += 1;
+            } else {
+                self.lm_remove(i);
+            }
+        }
+    }
+}
+
+/// Iterator methods for the LiteMap store.
+pub trait StoreIterable<'a, K: 'a, V: 'a>: Store<K, V> {
+    type KeyValueIter: Iterator<Item = (&'a K, &'a V)> + DoubleEndedIterator + 'a;
+
+    /// Returns an iterator over key/value pairs.
+    fn lm_iter(&'a self) -> Self::KeyValueIter;
+}
+
+pub trait StoreIterableMut<'a, K: 'a, V: 'a>: StoreMut<K, V> + StoreIterable<'a, K, V> {
+    type KeyValueIterMut: Iterator<Item = (&'a K, &'a mut V)> + DoubleEndedIterator + 'a;
+    type KeyValueIntoIter: Iterator<Item = (K, V)>;
+
+    /// Returns an iterator over key/value pairs, with a mutable value.
+    fn lm_iter_mut(&'a mut self) -> Self::KeyValueIterMut;
+
+    /// Returns an iterator that moves every item from this store.
+    fn lm_into_iter(self) -> Self::KeyValueIntoIter;
+
+    /// Adds items from another store to the end of this store.
+    fn lm_extend_end(&mut self, other: Self)
+    where
+        Self: Sized,
+    {
+        for item in other.lm_into_iter() {
+            self.lm_push(item.0, item.1);
+        }
+    }
+
+    /// Adds items from another store to the beginning of this store.
+    fn lm_extend_start(&mut self, other: Self)
+    where
+        Self: Sized,
+    {
+        for (i, item) in other.lm_into_iter().enumerate() {
+            self.lm_insert(i, item.0, item.1);
+        }
+    }
+}
+
+/// A store that can be built from a tuple iterator.
+pub trait StoreFromIterator<K, V>: FromIterator<(K, V)> {}
diff --git a/vendor/litemap/src/store/slice_impl.rs b/vendor/litemap/src/store/slice_impl.rs
new file mode 100644
index 000000000..4afb4fac2
--- /dev/null
+++ b/vendor/litemap/src/store/slice_impl.rs
@@ -0,0 +1,55 @@
+// 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::*;
+
+type MapF<K, V> = fn(&(K, V)) -> (&K, &V);
+
+#[inline]
+fn map_f<K, V>(input: &(K, V)) -> (&K, &V) {
+    (&input.0, &input.1)
+}
+
+impl<'a, K: 'a, V: 'a> StoreConstEmpty<K, V> for &'a [(K, V)] {
+    const EMPTY: &'a [(K, V)] = &[];
+}
+
+impl<'a, K: 'a, V: 'a> Store<K, V> for &'a [(K, V)] {
+    #[inline]
+    fn lm_len(&self) -> usize {
+        self.len()
+    }
+
+    #[inline]
+    fn lm_is_empty(&self) -> bool {
+        self.is_empty()
+    }
+
+    #[inline]
+    fn lm_get(&self, index: usize) -> Option<(&K, &V)> {
+        self.get(index).map(map_f)
+    }
+
+    #[inline]
+    fn lm_last(&self) -> Option<(&K, &V)> {
+        self.last().map(map_f)
+    }
+
+    #[inline]
+    fn lm_binary_search_by<F>(&self, mut cmp: F) -> Result<usize, usize>
+    where
+        F: FnMut(&K) -> Ordering,
+    {
+        self.binary_search_by(|(k, _)| cmp(k))
+    }
+}
+
+impl<'a, K: 'a, V: 'a> StoreIterable<'a, K, V> for &'a [(K, V)] {
+    type KeyValueIter = core::iter::Map<core::slice::Iter<'a, (K, V)>, MapF<K, V>>;
+
+    #[inline]
+    fn lm_iter(&'a self) -> Self::KeyValueIter {
+        self.iter().map(map_f)
+    }
+}
diff --git a/vendor/litemap/src/store/vec_impl.rs b/vendor/litemap/src/store/vec_impl.rs
new file mode 100644
index 000000000..e94e0fb7f
--- /dev/null
+++ b/vendor/litemap/src/store/vec_impl.rs
@@ -0,0 +1,140 @@
+// 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 alloc::vec::Vec;
+
+type MapF<K, V> = fn(&(K, V)) -> (&K, &V);
+
+#[inline]
+fn map_f<K, V>(input: &(K, V)) -> (&K, &V) {
+    (&input.0, &input.1)
+}
+
+type MapFMut<K, V> = fn(&mut (K, V)) -> (&K, &mut V);
+
+#[inline]
+fn map_f_mut<K, V>(input: &mut (K, V)) -> (&K, &mut V) {
+    (&input.0, &mut input.1)
+}
+
+impl<K, V> StoreConstEmpty<K, V> for Vec<(K, V)> {
+    const EMPTY: Vec<(K, V)> = Vec::new();
+}
+
+impl<K, V> Store<K, V> for Vec<(K, V)> {
+    #[inline]
+    fn lm_len(&self) -> usize {
+        self.as_slice().len()
+    }
+
+    #[inline]
+    fn lm_is_empty(&self) -> bool {
+        self.as_slice().is_empty()
+    }
+
+    #[inline]
+    fn lm_get(&self, index: usize) -> Option<(&K, &V)> {
+        self.as_slice().get(index).map(map_f)
+    }
+
+    #[inline]
+    fn lm_last(&self) -> Option<(&K, &V)> {
+        self.as_slice().last().map(map_f)
+    }
+
+    #[inline]
+    fn lm_binary_search_by<F>(&self, mut cmp: F) -> Result<usize, usize>
+    where
+        F: FnMut(&K) -> Ordering,
+    {
+        self.as_slice().binary_search_by(|(k, _)| cmp(k))
+    }
+}
+
+impl<K, V> StoreMut<K, V> for Vec<(K, V)> {
+    #[inline]
+    fn lm_with_capacity(capacity: usize) -> Self {
+        Self::with_capacity(capacity)
+    }
+
+    #[inline]
+    fn lm_reserve(&mut self, additional: usize) {
+        self.reserve(additional)
+    }
+
+    #[inline]
+    fn lm_get_mut(&mut self, index: usize) -> Option<(&K, &mut V)> {
+        self.as_mut_slice().get_mut(index).map(map_f_mut)
+    }
+
+    #[inline]
+    fn lm_push(&mut self, key: K, value: V) {
+        self.push((key, value))
+    }
+
+    #[inline]
+    fn lm_insert(&mut self, index: usize, key: K, value: V) {
+        self.insert(index, (key, value))
+    }
+
+    #[inline]
+    fn lm_remove(&mut self, index: usize) -> (K, V) {
+        self.remove(index)
+    }
+
+    #[inline]
+    fn lm_clear(&mut self) {
+        self.clear()
+    }
+
+    #[inline]
+    fn lm_retain<F>(&mut self, mut predicate: F)
+    where
+        F: FnMut(&K, &V) -> bool,
+    {
+        self.retain(|(k, v)| predicate(k, v))
+    }
+}
+
+impl<'a, K: 'a, V: 'a> StoreIterable<'a, K, V> for Vec<(K, V)> {
+    type KeyValueIter = core::iter::Map<core::slice::Iter<'a, (K, V)>, MapF<K, V>>;
+
+    #[inline]
+    fn lm_iter(&'a self) -> Self::KeyValueIter {
+        self.as_slice().iter().map(map_f)
+    }
+}
+
+impl<'a, K: 'a, V: 'a> StoreIterableMut<'a, K, V> for Vec<(K, V)> {
+    type KeyValueIterMut = core::iter::Map<core::slice::IterMut<'a, (K, V)>, MapFMut<K, V>>;
+    type KeyValueIntoIter = alloc::vec::IntoIter<(K, V)>;
+
+    #[inline]
+    fn lm_iter_mut(&'a mut self) -> Self::KeyValueIterMut {
+        self.as_mut_slice().iter_mut().map(map_f_mut)
+    }
+
+    #[inline]
+    fn lm_into_iter(self) -> Self::KeyValueIntoIter {
+        IntoIterator::into_iter(self)
+    }
+
+    #[inline]
+    fn lm_extend_end(&mut self, other: Self) {
+        self.extend(other)
+    }
+
+    #[inline]
+    fn lm_extend_start(&mut self, other: Self) {
+        self.splice(0..0, other);
+    }
+}
+
+impl<K, V> StoreFromIterator<K, V> for Vec<(K, V)> {}
+
+#[test]
+fn test_vec_impl() {
+    crate::testing::check_store_full::<Vec<(u32, u64)>>();
+}
diff --git a/vendor/litemap/src/testing.rs b/vendor/litemap/src/testing.rs
new file mode 100644
index 000000000..827c8dd23
--- /dev/null
+++ b/vendor/litemap/src/testing.rs
@@ -0,0 +1,240 @@
+// 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 ).
+
+//! Test utilities, primarily targeted to custom LiteMap stores.
+
+use crate::store::*;
+use crate::LiteMap;
+use alloc::vec::Vec;
+use core::fmt::Debug;
+
+// Test code
+#[allow(clippy::expect_used)]
+fn check_equivalence<'a, K, V, S0, S1>(mut a: S0, mut b: S1)
+where
+    K: Ord + Debug + PartialEq + 'a,
+    V: Debug + PartialEq + 'a,
+    S0: StoreMut<K, V> + StoreIterable<'a, K, V>,
+    S1: StoreMut<K, V> + StoreIterable<'a, K, V>,
+{
+    let len = a.lm_len();
+    assert_eq!(len, b.lm_len());
+    if len == 0 {
+        assert!(a.lm_is_empty());
+        assert!(b.lm_is_empty());
+    }
+    for i in 0..len {
+        let a_kv = a.lm_get(i);
+        let b_kv = b.lm_get(i);
+        assert!(a_kv.is_some());
+        assert_eq!(a_kv, b_kv);
+        let a_kv_mut = a.lm_get_mut(i);
+        let b_kv_mut = b.lm_get_mut(i);
+        assert!(a_kv_mut.is_some());
+        assert_eq!(a_kv_mut, b_kv_mut);
+    }
+    for j in 0..len {
+        let needle = a.lm_get(j).expect("j is in range").0;
+        let a_binary = a.lm_binary_search_by(|k| k.cmp(needle));
+        let b_binary = a.lm_binary_search_by(|k| k.cmp(needle));
+        assert_eq!(Ok(j), a_binary);
+        assert_eq!(Ok(j), b_binary);
+    }
+    assert!(a.lm_get(len).is_none());
+    assert!(b.lm_get(len).is_none());
+    assert_eq!(a.lm_last(), b.lm_last());
+}
+
+// Test code
+#[allow(clippy::expect_used)]
+fn check_into_iter_equivalence<'a, K, V, S0, S1>(a: S0, b: S1)
+where
+    K: Ord + Debug + PartialEq + 'a,
+    V: Debug + PartialEq + 'a,
+    S0: StoreIterableMut<'a, K, V>,
+    S1: StoreIterableMut<'a, K, V>,
+{
+    let a_vec = a.lm_into_iter().collect::<Vec<_>>();
+    let b_vec = b.lm_into_iter().collect::<Vec<_>>();
+    assert_eq!(a_vec, b_vec);
+}
+
+const SORTED_DATA: &[(u32, u64)] = &[
+    (106, 4816),
+    (147, 9864),
+    (188, 8588),
+    (252, 6031),
+    (434, 2518),
+    (574, 8500),
+    (607, 3756),
+    (619, 4965),
+    (663, 2669),
+    (724, 9211),
+];
+
+const RANDOM_DATA: &[(u32, u64)] = &[
+    (546, 7490),
+    (273, 4999),
+    (167, 8078),
+    (176, 2101),
+    (373, 1304),
+    (339, 9613),
+    (561, 3620),
+    (301, 1214),
+    (483, 4453),
+    (704, 5359),
+];
+
+// Test code
+#[allow(clippy::expect_used)]
+#[allow(clippy::panic)]
+fn populate_litemap<S>(map: &mut LiteMap<u32, u64, S>)
+where
+    S: StoreMut<u32, u64> + Debug,
+{
+    assert_eq!(0, map.len());
+    assert!(map.is_empty());
+    for (k, v) in SORTED_DATA.iter() {
+        #[allow(clippy::single_match)] // for clarity
+        match map.try_append(*k, *v) {
+            Some(_) => panic!("appending sorted data: {:?} to {:?}", k, map),
+            None => (), // OK
+        };
+    }
+    assert_eq!(10, map.len());
+    for (k, v) in RANDOM_DATA.iter() {
+        #[allow(clippy::single_match)] // for clarity
+        match map.try_append(*k, *v) {
+            Some(_) => (), // OK
+            None => panic!("cannot append random data: {:?} to{:?}", k, map),
+        };
+    }
+    assert_eq!(10, map.len());
+    for (k, v) in RANDOM_DATA.iter() {
+        map.insert(*k, *v);
+    }
+    assert_eq!(20, map.len());
+}
+
+/// Tests that a litemap that uses the given store as backend has behavior consistent with the
+/// reference impl.
+///
+/// Call this function in a test with the store impl to test as a valid backend for LiteMap.
+// Test code
+#[allow(clippy::expect_used)]
+pub fn check_store<'a, S>()
+where
+    S: StoreConstEmpty<u32, u64>
+        + StoreMut<u32, u64>
+        + StoreIterable<'a, u32, u64>
+        + StoreFromIterator<u32, u64>
+        + Clone
+        + Debug
+        + PartialEq
+        + 'a,
+{
+    let mut litemap_test: LiteMap<u32, u64, S> = LiteMap::new();
+    assert!(litemap_test.is_empty());
+    let mut litemap_std = LiteMap::<u32, u64>::new();
+    populate_litemap(&mut litemap_test);
+    populate_litemap(&mut litemap_std);
+    check_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+
+    litemap_test.retain(|_, v| v % 2 == 0);
+    litemap_std.retain(|_, v| v % 2 == 0);
+    assert_eq!(11, litemap_test.len());
+    assert_eq!(11, litemap_std.len());
+    check_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+
+    litemap_test
+        .remove(&175)
+        .ok_or(())
+        .expect_err("does not exist");
+    litemap_test.remove(&147).ok_or(()).expect("exists");
+    litemap_std
+        .remove(&175)
+        .ok_or(())
+        .expect_err("does not exist");
+    litemap_std.remove(&147).ok_or(()).expect("exists");
+
+    assert_eq!(10, litemap_test.len());
+    assert_eq!(10, litemap_std.len());
+    check_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+
+    litemap_test.clear();
+    litemap_std.clear();
+    check_equivalence(litemap_test.values, litemap_std.values);
+}
+
+/// Similar to [`check_store`] function, but also checks the validitiy of [`StoreIterableMut`]
+/// trait.
+// Test code
+#[allow(clippy::expect_used)]
+pub fn check_store_full<'a, S>()
+where
+    S: StoreConstEmpty<u32, u64>
+        + StoreIterableMut<'a, u32, u64>
+        + StoreFromIterator<u32, u64>
+        + Clone
+        + Debug
+        + PartialEq
+        + 'a,
+{
+    let mut litemap_test: LiteMap<u32, u64, S> = LiteMap::new();
+    assert!(litemap_test.is_empty());
+    let mut litemap_std = LiteMap::<u32, u64>::new();
+    populate_litemap(&mut litemap_test);
+    populate_litemap(&mut litemap_std);
+    check_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+    check_into_iter_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+
+    let extras_test = litemap_test.clone();
+    let extras_test = litemap_test
+        .extend_from_litemap(extras_test)
+        .expect("duplicates");
+    assert_eq!(extras_test, litemap_test);
+    let extras_std = litemap_std.clone();
+    check_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+    check_into_iter_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+
+    litemap_test.retain(|_, v| v % 2 == 0);
+    litemap_std.retain(|_, v| v % 2 == 0);
+    assert_eq!(11, litemap_test.len());
+    assert_eq!(11, litemap_std.len());
+    check_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+    check_into_iter_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+
+    let extras_test = litemap_test
+        .extend_from_litemap(extras_test)
+        .expect("duplicates");
+    let extras_std = litemap_std
+        .extend_from_litemap(extras_std)
+        .expect("duplicates");
+    assert_eq!(11, extras_test.len());
+    assert_eq!(11, extras_std.len());
+    assert_eq!(20, litemap_test.len());
+    assert_eq!(20, litemap_std.len());
+    check_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+    check_into_iter_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+
+    litemap_test
+        .remove(&175)
+        .ok_or(())
+        .expect_err("does not exist");
+    litemap_test.remove(&176).ok_or(()).expect("exists");
+    litemap_std
+        .remove(&175)
+        .ok_or(())
+        .expect_err("does not exist");
+    litemap_std.remove(&176).ok_or(()).expect("exists");
+    assert_eq!(19, litemap_test.len());
+    assert_eq!(19, litemap_std.len());
+    check_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+    check_into_iter_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+
+    litemap_test.clear();
+    litemap_std.clear();
+    check_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+    check_into_iter_equivalence(litemap_test.values, litemap_std.values);
+}