zerovec/zerovec/
slice.rs

1// This file is part of ICU4X. For terms of use, please see the file
2// called LICENSE at the top level of the ICU4X source tree
3// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).
4
5use super::*;
6use alloc::boxed::Box;
7use core::cmp::Ordering;
8use core::ops::Range;
9
10/// A zero-copy "slice", i.e. the zero-copy version of `[T]`. This behaves
11/// similarly to [`ZeroVec<T>`], however [`ZeroVec<T>`] is allowed to contain
12/// owned data and as such is ideal for deserialization since most human readable
13/// serialization formats cannot unconditionally deserialize zero-copy.
14///
15/// This type can be used inside [`VarZeroVec<T>`](crate::VarZeroVec) and [`ZeroMap`](crate::ZeroMap):
16/// This essentially allows for the construction of zero-copy types isomorphic to `Vec<Vec<T>>` by instead
17/// using `VarZeroVec<ZeroSlice<T>>`. See the [`VarZeroVec`](crate::VarZeroVec) docs for an example.
18///
19/// # Examples
20///
21/// Const-construct a ZeroSlice of u16:
22///
23/// ```
24/// use zerovec::ule::AsULE;
25/// use zerovec::ZeroSlice;
26///
27/// const DATA: &ZeroSlice<u16> =
28///     ZeroSlice::<u16>::from_ule_slice(&<u16 as AsULE>::ULE::from_array([
29///         211, 281, 421, 32973,
30///     ]));
31///
32/// assert_eq!(DATA.get(1), Some(281));
33/// ```
34#[repr(transparent)]
35pub struct ZeroSlice<T: AsULE>([T::ULE]);
36
37impl<T> ZeroSlice<T>
38where
39    T: AsULE,
40{
41    /// Returns an empty slice.
42    pub const fn new_empty() -> &'static Self {
43        Self::from_ule_slice(&[])
44    }
45
46    /// Get this [`ZeroSlice`] as a borrowed [`ZeroVec`]
47    ///
48    /// [`ZeroSlice`] does not have most of the methods that [`ZeroVec`] does,
49    /// so it is recommended to convert it to a [`ZeroVec`] before doing anything.
50    #[inline]
51    pub const fn as_zerovec(&self) -> ZeroVec<'_, T> {
52        ZeroVec::new_borrowed(&self.0)
53    }
54
55    /// Attempt to construct a `&ZeroSlice<T>` from a byte slice, returning an error
56    /// if it's not a valid byte sequence
57    pub fn parse_byte_slice(bytes: &[u8]) -> Result<&Self, ZeroVecError> {
58        T::ULE::parse_byte_slice(bytes).map(Self::from_ule_slice)
59    }
60
61    /// Uses a `&[u8]` buffer as a `ZeroVec<T>` without any verification.
62    ///
63    /// # Safety
64    ///
65    /// `bytes` need to be an output from [`ZeroSlice::as_bytes()`].
66    pub const unsafe fn from_bytes_unchecked(bytes: &[u8]) -> &Self {
67        // &[u8] and &[T::ULE] are the same slice with different length metadata.
68        Self::from_ule_slice(core::slice::from_raw_parts(
69            bytes.as_ptr() as *const T::ULE,
70            bytes.len() / core::mem::size_of::<T::ULE>(),
71        ))
72    }
73
74    /// Construct a `&ZeroSlice<T>` from a slice of ULEs.
75    ///
76    /// This function can be used for constructing ZeroVecs in a const context, avoiding
77    /// parsing checks.
78    ///
79    /// See [`ZeroSlice`] for an example.
80    #[inline]
81    pub const fn from_ule_slice(slice: &[T::ULE]) -> &Self {
82        // This is safe because ZeroSlice is transparent over [T::ULE]
83        // so &ZeroSlice<T> can be safely cast from &[T::ULE]
84        unsafe { &*(slice as *const _ as *const Self) }
85    }
86
87    /// Construct a `Box<ZeroSlice<T>>` from a boxed slice of ULEs
88    #[inline]
89    pub fn from_boxed_slice(slice: Box<[T::ULE]>) -> Box<Self> {
90        // This is safe because ZeroSlice is transparent over [T::ULE]
91        // so Box<ZeroSlice<T>> can be safely cast from Box<[T::ULE]>
92        unsafe { Box::from_raw(Box::into_raw(slice) as *mut Self) }
93    }
94
95    /// Returns this slice as its underlying `&[u8]` byte buffer representation.
96    ///
97    /// Useful for serialization.
98    ///
99    /// # Example
100    ///
101    /// ```
102    /// use zerovec::ZeroVec;
103    ///
104    /// // The little-endian bytes correspond to the numbers on the following line.
105    /// let bytes: &[u8] = &[0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x80];
106    /// let nums: &[u16] = &[211, 281, 421, 32973];
107    ///
108    /// let zerovec = ZeroVec::alloc_from_slice(nums);
109    ///
110    /// assert_eq!(bytes, zerovec.as_bytes());
111    /// ```
112    #[inline]
113    pub fn as_bytes(&self) -> &[u8] {
114        T::ULE::as_byte_slice(self.as_ule_slice())
115    }
116
117    /// Dereferences this slice as `&[T::ULE]`.
118    #[inline]
119    pub const fn as_ule_slice(&self) -> &[T::ULE] {
120        &self.0
121    }
122
123    /// Returns the number of elements in this slice.
124    ///
125    /// # Example
126    ///
127    /// ```
128    /// use zerovec::ule::AsULE;
129    /// use zerovec::ZeroVec;
130    ///
131    /// let bytes: &[u8] = &[0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x80];
132    /// let zerovec: ZeroVec<u16> =
133    ///     ZeroVec::parse_byte_slice(bytes).expect("infallible");
134    ///
135    /// assert_eq!(4, zerovec.len());
136    /// assert_eq!(
137    ///     bytes.len(),
138    ///     zerovec.len() * std::mem::size_of::<<u16 as AsULE>::ULE>()
139    /// );
140    /// ```
141    #[inline]
142    pub const fn len(&self) -> usize {
143        self.as_ule_slice().len()
144    }
145
146    /// Returns whether this slice is empty.
147    ///
148    /// # Example
149    ///
150    /// ```
151    /// use zerovec::ZeroVec;
152    ///
153    /// let bytes: &[u8] = &[0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x80];
154    /// let zerovec: ZeroVec<u16> =
155    ///     ZeroVec::parse_byte_slice(bytes).expect("infallible");
156    /// assert!(!zerovec.is_empty());
157    ///
158    /// let emptyvec: ZeroVec<u16> =
159    ///     ZeroVec::parse_byte_slice(&[]).expect("infallible");
160    /// assert!(emptyvec.is_empty());
161    /// ```
162    #[inline]
163    pub const fn is_empty(&self) -> bool {
164        self.as_ule_slice().is_empty()
165    }
166}
167
168impl<T> ZeroSlice<T>
169where
170    T: AsULE,
171{
172    /// Gets the element at the specified index. Returns `None` if out of range.
173    ///
174    /// # Example
175    ///
176    /// ```
177    /// use zerovec::ZeroVec;
178    ///
179    /// let bytes: &[u8] = &[0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x80];
180    /// let zerovec: ZeroVec<u16> =
181    ///     ZeroVec::parse_byte_slice(bytes).expect("infallible");
182    ///
183    /// assert_eq!(zerovec.get(2), Some(421));
184    /// assert_eq!(zerovec.get(4), None);
185    /// ```
186    #[inline]
187    pub fn get(&self, index: usize) -> Option<T> {
188        self.as_ule_slice()
189            .get(index)
190            .copied()
191            .map(T::from_unaligned)
192    }
193
194    /// Gets the entire slice as an array of length `N`. Returns `None` if the slice
195    /// does not have exactly `N` elements.
196    ///
197    /// # Example
198    ///
199    /// ```
200    /// use zerovec::ZeroVec;
201    ///
202    /// let bytes: &[u8] = &[0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x80];
203    /// let zerovec: ZeroVec<u16> =
204    ///     ZeroVec::parse_byte_slice(bytes).expect("infallible");
205    /// let array: [u16; 4] =
206    ///     zerovec.get_as_array().expect("should be 4 items in array");
207    ///
208    /// assert_eq!(array[2], 421);
209    /// ```
210    pub fn get_as_array<const N: usize>(&self) -> Option<[T; N]> {
211        let ule_array = <&[T::ULE; N]>::try_from(self.as_ule_slice()).ok()?;
212        Some(ule_array.map(|u| T::from_unaligned(u)))
213    }
214
215    /// Gets a subslice of elements within a certain range. Returns `None` if the range
216    /// is out of bounds of this `ZeroSlice`.
217    ///
218    /// # Example
219    ///
220    /// ```
221    /// use zerovec::ZeroVec;
222    ///
223    /// let bytes: &[u8] = &[0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x80];
224    /// let zerovec: ZeroVec<u16> =
225    ///     ZeroVec::parse_byte_slice(bytes).expect("infallible");
226    ///
227    /// assert_eq!(
228    ///     zerovec.get_subslice(1..3),
229    ///     Some(&*ZeroVec::from_slice_or_alloc(&[0x0119, 0x01A5]))
230    /// );
231    /// assert_eq!(zerovec.get_subslice(3..5), None);
232    /// ```
233    #[inline]
234    pub fn get_subslice(&self, range: Range<usize>) -> Option<&ZeroSlice<T>> {
235        self.0.get(range).map(ZeroSlice::from_ule_slice)
236    }
237
238    /// Get a borrowed reference to the underlying ULE type at a specified index.
239    ///
240    /// Prefer [`Self::get()`] over this method where possible since working
241    /// directly with `ULE` types is less ergonomic
242    pub fn get_ule_ref(&self, index: usize) -> Option<&T::ULE> {
243        self.as_ule_slice().get(index)
244    }
245
246    /// Casts a `ZeroSlice<T>` to a compatible `ZeroSlice<P>`.
247    ///
248    /// `T` and `P` are compatible if they have the same `ULE` representation.
249    ///
250    /// If the `ULE`s of `T` and `P` are different, use [`Self::try_as_converted()`].
251    ///
252    /// # Examples
253    ///
254    /// ```
255    /// use zerovec::ZeroSlice;
256    ///
257    /// const BYTES: &[u8] = &[0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x80];
258    /// const ZS_U16: &ZeroSlice<u16> = {
259    ///     match ZeroSlice::<u16>::try_from_bytes(BYTES) {
260    ///         Ok(s) => s,
261    ///         Err(_) => unreachable!(),
262    ///     }
263    /// };
264    ///
265    /// let zs_i16: &ZeroSlice<i16> = ZS_U16.cast();
266    ///
267    /// assert_eq!(ZS_U16.get(3), Some(32973));
268    /// assert_eq!(zs_i16.get(3), Some(-32563));
269    /// ```
270    #[inline]
271    pub const fn cast<P>(&self) -> &ZeroSlice<P>
272    where
273        P: AsULE<ULE = T::ULE>,
274    {
275        ZeroSlice::<P>::from_ule_slice(self.as_ule_slice())
276    }
277
278    /// Converts a `&ZeroSlice<T>` into a `&ZeroSlice<P>`.
279    ///
280    /// The resulting slice will have the same length as the original slice
281    /// if and only if `T::ULE` and `P::ULE` are the same size.
282    ///
283    /// If `T` and `P` have the exact same `ULE`, use [`Self::cast()`].
284    ///
285    /// # Examples
286    ///
287    /// ```
288    /// use zerovec::ZeroSlice;
289    ///
290    /// const BYTES: &[u8] = &[0x7F, 0xF3, 0x01, 0x00, 0x49, 0xF6, 0x01, 0x00];
291    /// const ZS_U32: &ZeroSlice<u32> = {
292    ///     match ZeroSlice::<u32>::try_from_bytes(BYTES) {
293    ///         Ok(s) => s,
294    ///         Err(_) => unreachable!(),
295    ///     }
296    /// };
297    ///
298    /// let zs_u8_4: &ZeroSlice<[u8; 4]> =
299    ///     ZS_U32.try_as_converted().expect("valid code points");
300    ///
301    /// assert_eq!(ZS_U32.get(0), Some(127871));
302    /// assert_eq!(zs_u8_4.get(0), Some([0x7F, 0xF3, 0x01, 0x00]));
303    /// ```
304    #[inline]
305    pub fn try_as_converted<P: AsULE>(&self) -> Result<&ZeroSlice<P>, ZeroVecError> {
306        let new_slice = P::ULE::parse_byte_slice(self.as_bytes())?;
307        Ok(ZeroSlice::from_ule_slice(new_slice))
308    }
309
310    /// Gets the first element. Returns `None` if empty.
311    ///
312    /// # Example
313    ///
314    /// ```
315    /// use zerovec::ZeroVec;
316    ///
317    /// let bytes: &[u8] = &[0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x80];
318    /// let zerovec: ZeroVec<u16> =
319    ///     ZeroVec::parse_byte_slice(bytes).expect("infallible");
320    ///
321    /// assert_eq!(zerovec.first(), Some(211));
322    /// ```
323    #[inline]
324    pub fn first(&self) -> Option<T> {
325        self.as_ule_slice().first().copied().map(T::from_unaligned)
326    }
327
328    /// Gets the last element. Returns `None` if empty.
329    ///
330    /// # Example
331    ///
332    /// ```
333    /// use zerovec::ZeroVec;
334    ///
335    /// let bytes: &[u8] = &[0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x80];
336    /// let zerovec: ZeroVec<u16> =
337    ///     ZeroVec::parse_byte_slice(bytes).expect("infallible");
338    ///
339    /// assert_eq!(zerovec.last(), Some(32973));
340    /// ```
341    #[inline]
342    pub fn last(&self) -> Option<T> {
343        self.as_ule_slice().last().copied().map(T::from_unaligned)
344    }
345
346    /// Gets an iterator over the elements.
347    ///
348    /// # Example
349    ///
350    /// ```
351    /// use zerovec::ZeroVec;
352    ///
353    /// let bytes: &[u8] = &[0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x80];
354    /// let zerovec: ZeroVec<u16> =
355    ///     ZeroVec::parse_byte_slice(bytes).expect("infallible");
356    /// let mut it = zerovec.iter();
357    ///
358    /// assert_eq!(it.next(), Some(211));
359    /// assert_eq!(it.next(), Some(281));
360    /// assert_eq!(it.next(), Some(421));
361    /// assert_eq!(it.next(), Some(32973));
362    /// assert_eq!(it.next(), None);
363    /// ```
364    #[inline]
365    pub fn iter(&self) -> impl DoubleEndedIterator<Item = T> + ExactSizeIterator<Item = T> + '_ {
366        self.as_ule_slice().iter().copied().map(T::from_unaligned)
367    }
368
369    /// Returns a tuple with the first element and a subslice of the remaining elements.
370    ///
371    /// # Example
372    ///
373    /// ```
374    /// use zerovec::ule::AsULE;
375    /// use zerovec::ZeroSlice;
376    ///
377    /// const DATA: &ZeroSlice<u16> =
378    ///     ZeroSlice::<u16>::from_ule_slice(&<u16 as AsULE>::ULE::from_array([
379    ///         211, 281, 421, 32973,
380    ///     ]));
381    /// const EXPECTED_VALUE: (u16, &ZeroSlice<u16>) = (
382    ///     211,
383    ///     ZeroSlice::<u16>::from_ule_slice(&<u16 as AsULE>::ULE::from_array([
384    ///         281, 421, 32973,
385    ///     ])),
386    /// );
387    /// assert_eq!(EXPECTED_VALUE, DATA.split_first().unwrap());
388    /// ```
389    #[inline]
390    pub fn split_first(&self) -> Option<(T, &ZeroSlice<T>)> {
391        if let Some(first) = self.first() {
392            return Some((
393                first,
394                // `unwrap()` must succeed, because `first()` returned `Some`.
395                #[allow(clippy::unwrap_used)]
396                self.get_subslice(1..self.len()).unwrap(),
397            ));
398        }
399        None
400    }
401}
402
403impl<T> ZeroSlice<T>
404where
405    T: AsULE + Ord,
406{
407    /// Binary searches a sorted `ZeroVec<T>` for the given element. For more information, see
408    /// the primitive function [`binary_search`].
409    ///
410    /// # Example
411    ///
412    /// ```
413    /// use zerovec::ZeroVec;
414    ///
415    /// let bytes: &[u8] = &[0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x80];
416    /// let zerovec: ZeroVec<u16> =
417    ///     ZeroVec::parse_byte_slice(bytes).expect("infallible");
418    ///
419    /// assert_eq!(zerovec.binary_search(&281), Ok(1));
420    /// assert_eq!(zerovec.binary_search(&282), Err(2));
421    /// ```
422    ///
423    /// [`binary_search`]: https://doc.rust-lang.org/std/primitive.slice.html#method.binary_search
424    #[inline]
425    pub fn binary_search(&self, x: &T) -> Result<usize, usize> {
426        self.as_ule_slice()
427            .binary_search_by(|probe| T::from_unaligned(*probe).cmp(x))
428    }
429}
430
431impl<T> ZeroSlice<T>
432where
433    T: AsULE,
434{
435    /// Binary searches a sorted `ZeroVec<T>` based on a given predicate. For more information, see
436    /// the primitive function [`binary_search_by`].
437    ///
438    /// # Example
439    ///
440    /// ```
441    /// use zerovec::ZeroVec;
442    ///
443    /// let bytes: &[u8] = &[0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x80];
444    /// let zerovec: ZeroVec<u16> =
445    ///     ZeroVec::parse_byte_slice(bytes).expect("infallible");
446    ///
447    /// assert_eq!(zerovec.binary_search_by(|x| x.cmp(&281)), Ok(1));
448    /// assert_eq!(zerovec.binary_search_by(|x| x.cmp(&282)), Err(2));
449    /// ```
450    ///
451    /// [`binary_search_by`]: https://doc.rust-lang.org/std/primitive.slice.html#method.binary_search_by
452    #[inline]
453    pub fn binary_search_by(
454        &self,
455        mut predicate: impl FnMut(T) -> Ordering,
456    ) -> Result<usize, usize> {
457        self.as_ule_slice()
458            .binary_search_by(|probe| predicate(T::from_unaligned(*probe)))
459    }
460}
461
462// Safety (based on the safety checklist on the VarULE trait):
463// (`ZeroSlice<T>` is a transparent wrapper around [T::ULE])
464//  1. [T::ULE] does not include any uninitialized or padding bytes (achieved by being a slice of a ULE type)
465//  2. [T::ULE] is aligned to 1 byte (achieved by being a slice of a ULE type)
466//  3. The impl of `validate_byte_slice()` returns an error if any byte is not valid.
467//  4. The impl of `validate_byte_slice()` returns an error if the slice cannot be used in its entirety
468//  5. The impl of `from_byte_slice_unchecked()` returns a reference to the same data.
469//  6. `as_byte_slice()` and `parse_byte_slice()` are defaulted
470//  7. `[T::ULE]` byte equality is semantic equality (relying on the guideline of the underlying `ULE` type)
471unsafe impl<T: AsULE + 'static> VarULE for ZeroSlice<T> {
472    #[inline]
473    fn validate_byte_slice(bytes: &[u8]) -> Result<(), ZeroVecError> {
474        T::ULE::validate_byte_slice(bytes)
475    }
476
477    #[inline]
478    unsafe fn from_byte_slice_unchecked(bytes: &[u8]) -> &Self {
479        Self::from_ule_slice(T::ULE::from_byte_slice_unchecked(bytes))
480    }
481}
482
483impl<T> Eq for ZeroSlice<T> where T: AsULE + Eq {}
484
485impl<T> PartialEq<ZeroSlice<T>> for ZeroSlice<T>
486where
487    T: AsULE + PartialEq,
488{
489    #[inline]
490    fn eq(&self, other: &ZeroSlice<T>) -> bool {
491        self.as_zerovec().eq(&other.as_zerovec())
492    }
493}
494
495impl<T> PartialEq<[T]> for ZeroSlice<T>
496where
497    T: AsULE + PartialEq,
498{
499    #[inline]
500    fn eq(&self, other: &[T]) -> bool {
501        self.iter().eq(other.iter().copied())
502    }
503}
504
505impl<'a, T> PartialEq<ZeroVec<'a, T>> for ZeroSlice<T>
506where
507    T: AsULE + PartialEq,
508{
509    #[inline]
510    fn eq(&self, other: &ZeroVec<'a, T>) -> bool {
511        self.as_zerovec().eq(other)
512    }
513}
514
515impl<'a, T> PartialEq<ZeroSlice<T>> for ZeroVec<'a, T>
516where
517    T: AsULE + PartialEq,
518{
519    #[inline]
520    fn eq(&self, other: &ZeroSlice<T>) -> bool {
521        self.eq(&other.as_zerovec())
522    }
523}
524
525impl<T> fmt::Debug for ZeroSlice<T>
526where
527    T: AsULE + fmt::Debug,
528{
529    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
530        self.as_zerovec().fmt(f)
531    }
532}
533
534impl<T: AsULE + PartialOrd> PartialOrd for ZeroSlice<T> {
535    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
536        self.iter().partial_cmp(other.iter())
537    }
538}
539
540impl<T: AsULE + Ord> Ord for ZeroSlice<T> {
541    fn cmp(&self, other: &Self) -> Ordering {
542        self.iter().cmp(other.iter())
543    }
544}
545
546impl<T: AsULE> AsRef<ZeroSlice<T>> for Vec<T::ULE> {
547    fn as_ref(&self) -> &ZeroSlice<T> {
548        ZeroSlice::<T>::from_ule_slice(self)
549    }
550}
551
552impl<T: AsULE> AsRef<ZeroSlice<T>> for &[T::ULE] {
553    fn as_ref(&self) -> &ZeroSlice<T> {
554        ZeroSlice::<T>::from_ule_slice(self)
555    }
556}
557
558impl<T> Default for &ZeroSlice<T>
559where
560    T: AsULE,
561{
562    fn default() -> Self {
563        ZeroSlice::from_ule_slice(&[])
564    }
565}
566
567#[cfg(test)]
568mod test {
569    use super::*;
570    use crate::zeroslice;
571
572    #[test]
573    fn test_split_first() {
574        {
575            // empty slice.
576            assert_eq!(None, ZeroSlice::<u16>::new_empty().split_first());
577        }
578        {
579            // single element slice
580            const DATA: &ZeroSlice<u16> =
581                zeroslice!(u16; <u16 as AsULE>::ULE::from_unsigned; [211]);
582            assert_eq!((211, zeroslice![]), DATA.split_first().unwrap());
583        }
584        {
585            // slice with many elements.
586            const DATA: &ZeroSlice<u16> =
587                zeroslice!(u16; <u16 as AsULE>::ULE::from_unsigned; [211, 281, 421, 32973]);
588            const EXPECTED_VALUE: (u16, &ZeroSlice<u16>) = (
589                211,
590                zeroslice!(u16; <u16 as AsULE>::ULE::from_unsigned; [281, 421, 32973]),
591            );
592
593            assert_eq!(EXPECTED_VALUE, DATA.split_first().unwrap());
594        }
595    }
596}
zerovec/zerovec/slice.rs

zerovec/zerovec/
slice.rs
