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