diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:18:21 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:18:21 +0000 |
commit | 4e8199b572f2035b7749cba276ece3a26630d23e (patch) | |
tree | f09feeed6a0fe39d027b1908aa63ea6b35e4b631 /vendor/zerovec/src/map2d | |
parent | Adding upstream version 1.66.0+dfsg1. (diff) | |
download | rustc-4e8199b572f2035b7749cba276ece3a26630d23e.tar.xz rustc-4e8199b572f2035b7749cba276ece3a26630d23e.zip |
Adding upstream version 1.67.1+dfsg1.upstream/1.67.1+dfsg1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'vendor/zerovec/src/map2d')
-rw-r--r-- | vendor/zerovec/src/map2d/borrowed.rs | 349 | ||||
-rw-r--r-- | vendor/zerovec/src/map2d/cursor.rs | 306 | ||||
-rw-r--r-- | vendor/zerovec/src/map2d/databake.rs | 160 | ||||
-rw-r--r-- | vendor/zerovec/src/map2d/map.rs | 827 | ||||
-rw-r--r-- | vendor/zerovec/src/map2d/mod.rs | 18 | ||||
-rw-r--r-- | vendor/zerovec/src/map2d/serde.rs | 430 |
6 files changed, 2090 insertions, 0 deletions
diff --git a/vendor/zerovec/src/map2d/borrowed.rs b/vendor/zerovec/src/map2d/borrowed.rs new file mode 100644 index 000000000..d9972fae9 --- /dev/null +++ b/vendor/zerovec/src/map2d/borrowed.rs @@ -0,0 +1,349 @@ +// 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 { + ZeroMap2dBorrowed { + keys0: self.keys0, + joiner: self.joiner, + keys1: self.keys1, + values: self.values, + } + } +} + +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); + /// + /// let borrow = borrowed.get_2d(&1, "one"); + /// drop(borrowed); + /// // still exists after the ZeroMap2dBorrowed has been dropped + /// assert_eq!(borrow, Some("foo")); + /// ``` + 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_eq!(borrowed.contains_key0(&1), true); + /// assert_eq!(borrowed.contains_key0(&3), false); + /// ``` + 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/vendor/zerovec/src/map2d/cursor.rs b/vendor/zerovec/src/map2d/cursor.rs new file mode 100644 index 000000000..0654ee794 --- /dev/null +++ b/vendor/zerovec/src/map2d/cursor.rs @@ -0,0 +1,306 @@ +// 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 for a particular key0. + /// + /// 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> + 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) + } + + 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()) + } +} + +// 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/vendor/zerovec/src/map2d/databake.rs b/vendor/zerovec/src/map2d/databake.rs new file mode 100644 index 000000000..90ab970bb --- /dev/null +++ b/vendor/zerovec/src/map2d/databake.rs @@ -0,0 +1,160 @@ +// 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(&[ + 97u8, 114u8, 99u8, 97u8, 122u8, 0u8, 99u8, 117u8, 0u8, 101u8, 110u8, 0u8, + 102u8, 102u8, 0u8, 103u8, 114u8, 99u8, 107u8, 107u8, 0u8, 107u8, 117u8, + 0u8, 107u8, 121u8, 0u8, 108u8, 105u8, 102u8, 109u8, 97u8, 110u8, 109u8, + 110u8, 0u8, 112u8, 97u8, 0u8, 112u8, 97u8, 108u8, 115u8, 100u8, 0u8, 116u8, + 103u8, 0u8, 117u8, 103u8, 0u8, 117u8, 110u8, 114u8, 117u8, 122u8, 0u8, + 121u8, 117u8, 101u8, 122u8, 104u8, 0u8, + ]) + }, + unsafe { + crate::ZeroVec::from_bytes_unchecked(&[ + 2u8, 0u8, 0u8, 0u8, 3u8, 0u8, 0u8, 0u8, 4u8, 0u8, 0u8, 0u8, 5u8, 0u8, 0u8, + 0u8, 6u8, 0u8, 0u8, 0u8, 7u8, 0u8, 0u8, 0u8, 8u8, 0u8, 0u8, 0u8, 10u8, 0u8, + 0u8, 0u8, 12u8, 0u8, 0u8, 0u8, 13u8, 0u8, 0u8, 0u8, 14u8, 0u8, 0u8, 0u8, + 15u8, 0u8, 0u8, 0u8, 16u8, 0u8, 0u8, 0u8, 17u8, 0u8, 0u8, 0u8, 20u8, 0u8, + 0u8, 0u8, 21u8, 0u8, 0u8, 0u8, 22u8, 0u8, 0u8, 0u8, 23u8, 0u8, 0u8, 0u8, + 24u8, 0u8, 0u8, 0u8, 25u8, 0u8, 0u8, 0u8, 28u8, 0u8, 0u8, 0u8, + ]) + }, + unsafe { + crate::VarZeroVec::from_bytes_unchecked(&[ + 78u8, 98u8, 97u8, 116u8, 80u8, 97u8, 108u8, 109u8, 65u8, 114u8, 97u8, 98u8, + 71u8, 108u8, 97u8, 103u8, 83u8, 104u8, 97u8, 119u8, 65u8, 100u8, 108u8, + 109u8, 76u8, 105u8, 110u8, 98u8, 65u8, 114u8, 97u8, 98u8, 65u8, 114u8, + 97u8, 98u8, 89u8, 101u8, 122u8, 105u8, 65u8, 114u8, 97u8, 98u8, 76u8, 97u8, + 116u8, 110u8, 76u8, 105u8, 109u8, 98u8, 78u8, 107u8, 111u8, 111u8, 77u8, + 111u8, 110u8, 103u8, 65u8, 114u8, 97u8, 98u8, 80u8, 104u8, 108u8, 112u8, + 68u8, 101u8, 118u8, 97u8, 75u8, 104u8, 111u8, 106u8, 83u8, 105u8, 110u8, + 100u8, 65u8, 114u8, 97u8, 98u8, 67u8, 121u8, 114u8, 108u8, 68u8, 101u8, + 118u8, 97u8, 65u8, 114u8, 97u8, 98u8, 72u8, 97u8, 110u8, 115u8, 66u8, + 111u8, 112u8, 111u8, 72u8, 97u8, 110u8, 98u8, 72u8, 97u8, 110u8, 116u8, + ]) + }, + unsafe { + crate::VarZeroVec::from_bytes_unchecked(&[ + 74u8, 79u8, 0u8, 83u8, 89u8, 0u8, 73u8, 82u8, 0u8, 66u8, 71u8, 0u8, 71u8, + 66u8, 0u8, 71u8, 78u8, 0u8, 71u8, 82u8, 0u8, 67u8, 78u8, 0u8, 73u8, 81u8, + 0u8, 71u8, 69u8, 0u8, 67u8, 78u8, 0u8, 84u8, 82u8, 0u8, 73u8, 78u8, 0u8, + 71u8, 78u8, 0u8, 67u8, 78u8, 0u8, 80u8, 75u8, 0u8, 67u8, 78u8, 0u8, 73u8, + 78u8, 0u8, 73u8, 78u8, 0u8, 73u8, 78u8, 0u8, 80u8, 75u8, 0u8, 75u8, 90u8, + 0u8, 78u8, 80u8, 0u8, 65u8, 70u8, 0u8, 67u8, 78u8, 0u8, 84u8, 87u8, 0u8, + 84u8, 87u8, 0u8, 84u8, 87u8, 0u8, + ]) + }, + ) + }, + 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(&[ + 97u8, 114u8, 99u8, 97u8, 122u8, 0u8, 99u8, 117u8, 0u8, 101u8, 110u8, 0u8, + 102u8, 102u8, 0u8, 103u8, 114u8, 99u8, 107u8, 107u8, 0u8, 107u8, 117u8, + 0u8, 107u8, 121u8, 0u8, 108u8, 105u8, 102u8, 109u8, 97u8, 110u8, 109u8, + 110u8, 0u8, 112u8, 97u8, 0u8, 112u8, 97u8, 108u8, 115u8, 100u8, 0u8, 116u8, + 103u8, 0u8, 117u8, 103u8, 0u8, 117u8, 110u8, 114u8, 117u8, 122u8, 0u8, + 121u8, 117u8, 101u8, 122u8, 104u8, 0u8, + ]) + }, + unsafe { + crate::ZeroSlice::from_bytes_unchecked(&[ + 2u8, 0u8, 0u8, 0u8, 3u8, 0u8, 0u8, 0u8, 4u8, 0u8, 0u8, 0u8, 5u8, 0u8, 0u8, + 0u8, 6u8, 0u8, 0u8, 0u8, 7u8, 0u8, 0u8, 0u8, 8u8, 0u8, 0u8, 0u8, 10u8, 0u8, + 0u8, 0u8, 12u8, 0u8, 0u8, 0u8, 13u8, 0u8, 0u8, 0u8, 14u8, 0u8, 0u8, 0u8, + 15u8, 0u8, 0u8, 0u8, 16u8, 0u8, 0u8, 0u8, 17u8, 0u8, 0u8, 0u8, 20u8, 0u8, + 0u8, 0u8, 21u8, 0u8, 0u8, 0u8, 22u8, 0u8, 0u8, 0u8, 23u8, 0u8, 0u8, 0u8, + 24u8, 0u8, 0u8, 0u8, 25u8, 0u8, 0u8, 0u8, 28u8, 0u8, 0u8, 0u8, + ]) + }, + unsafe { + crate::VarZeroSlice::from_bytes_unchecked(&[ + 78u8, 98u8, 97u8, 116u8, 80u8, 97u8, 108u8, 109u8, 65u8, 114u8, 97u8, 98u8, + 71u8, 108u8, 97u8, 103u8, 83u8, 104u8, 97u8, 119u8, 65u8, 100u8, 108u8, + 109u8, 76u8, 105u8, 110u8, 98u8, 65u8, 114u8, 97u8, 98u8, 65u8, 114u8, + 97u8, 98u8, 89u8, 101u8, 122u8, 105u8, 65u8, 114u8, 97u8, 98u8, 76u8, 97u8, + 116u8, 110u8, 76u8, 105u8, 109u8, 98u8, 78u8, 107u8, 111u8, 111u8, 77u8, + 111u8, 110u8, 103u8, 65u8, 114u8, 97u8, 98u8, 80u8, 104u8, 108u8, 112u8, + 68u8, 101u8, 118u8, 97u8, 75u8, 104u8, 111u8, 106u8, 83u8, 105u8, 110u8, + 100u8, 65u8, 114u8, 97u8, 98u8, 67u8, 121u8, 114u8, 108u8, 68u8, 101u8, + 118u8, 97u8, 65u8, 114u8, 97u8, 98u8, 72u8, 97u8, 110u8, 115u8, 66u8, + 111u8, 112u8, 111u8, 72u8, 97u8, 110u8, 98u8, 72u8, 97u8, 110u8, 116u8, + ]) + }, + unsafe { + crate::VarZeroSlice::from_bytes_unchecked(&[ + 74u8, 79u8, 0u8, 83u8, 89u8, 0u8, 73u8, 82u8, 0u8, 66u8, 71u8, 0u8, 71u8, + 66u8, 0u8, 71u8, 78u8, 0u8, 71u8, 82u8, 0u8, 67u8, 78u8, 0u8, 73u8, 81u8, + 0u8, 71u8, 69u8, 0u8, 67u8, 78u8, 0u8, 84u8, 82u8, 0u8, 73u8, 78u8, 0u8, + 71u8, 78u8, 0u8, 67u8, 78u8, 0u8, 80u8, 75u8, 0u8, 67u8, 78u8, 0u8, 73u8, + 78u8, 0u8, 73u8, 78u8, 0u8, 73u8, 78u8, 0u8, 80u8, 75u8, 0u8, 75u8, 90u8, + 0u8, 78u8, 80u8, 0u8, 65u8, 70u8, 0u8, 67u8, 78u8, 0u8, 84u8, 87u8, 0u8, + 84u8, 87u8, 0u8, 84u8, 87u8, 0u8, + ]) + }, + ) + }, + zerovec + ); +} diff --git a/vendor/zerovec/src/map2d/map.rs b/vendor/zerovec/src/map2d/map.rs new file mode 100644 index 000000000..ab6eded4e --- /dev/null +++ b/vendor/zerovec/src/map2d/map.rs @@ -0,0 +1,827 @@ +// 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. + /// + /// See example in [`Self::get_2d()`]. + 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()); + #[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(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_eq!(map.contains_key0(&1), true); + /// assert_eq!(map.contains_key0(&3), false); + /// ``` + 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); + } + } + map + } +} + +#[cfg(test)] +mod test { + use super::*; + + #[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!(matches!(result, 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!(matches!(result, 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!(matches!(result, Some(_))); + + // Append a few more elements + let result = zm2d.try_append(&5, "ddd", "DD1"); + assert!(matches!(result, None)); + let result = zm2d.try_append(&7, "ddd", "DD2"); + assert!(matches!(result, None)); + let result = zm2d.try_append(&7, "eee", "EEE"); + assert!(matches!(result, None)); + let result = zm2d.try_append(&7, "www", "WWW"); + assert!(matches!(result, None)); + let result = zm2d.try_append(&9, "yyy", "YYY"); + assert!(matches!(result, 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, Some(String::from("CCC").into_boxed_str())); + let result = zm2d.remove(&3, "mmm"); // middle element + assert_eq!(result, Some(String::from("MM0").into_boxed_str())); + let result = zm2d.remove(&5, "ddd"); // singleton K0 + assert_eq!(result, Some(String::from("DD1").into_boxed_str())); + let result = zm2d.remove(&9, "yyy"); // last element + assert_eq!(result, Some(String::from("YYY").into_boxed_str())); + + 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\"] }"); + } +} diff --git a/vendor/zerovec/src/map2d/mod.rs b/vendor/zerovec/src/map2d/mod.rs new file mode 100644 index 000000000..f5465fcf2 --- /dev/null +++ b/vendor/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/vendor/zerovec/src/map2d/serde.rs b/vendor/zerovec/src/map2d/serde.rs new file mode 100644 index 000000000..f8b5f147b --- /dev/null +++ b/vendor/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 can be made available by enabling the optional `serde` 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 can be made available by enabling the optional `serde` 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 can be made available by enabling the optional `serde` 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 can be made available by enabling the optional `serde` 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 + ] + ); + } +} |