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 crate::ule::*;
6use alloc::boxed::Box;
7use alloc::format;
8use alloc::string::String;
9use alloc::vec::Vec;
10use core::cmp::Ordering;
11use core::convert::TryFrom;
12use core::marker::PhantomData;
13use core::ops::Range;
14
15// Also used by owned.rs
16pub(super) const LENGTH_WIDTH: usize = 4;
17pub(super) const METADATA_WIDTH: usize = 0;
18pub(super) const MAX_LENGTH: usize = u32::MAX as usize;
19pub(super) const MAX_INDEX: usize = u32::MAX as usize;
20
21/// This trait allows switching between different possible internal
22/// representations of VarZeroVec.
23///
24/// Currently this crate supports two formats: [`Index16`] and [`Index32`],
25/// with [`Index16`] being the default for all [`VarZeroVec`](super::VarZeroVec)
26/// types unless explicitly specified otherwise.
27///
28/// Do not implement this trait, its internals may be changed in the future,
29/// and all of its associated items are hidden from the docs.
30#[allow(clippy::missing_safety_doc)] // no safety section for you, don't implement this trait period
31pub unsafe trait VarZeroVecFormat: 'static + Sized {
32 #[doc(hidden)]
33 const INDEX_WIDTH: usize;
34 #[doc(hidden)]
35 const MAX_VALUE: u32;
36 /// This is always `RawBytesULE<Self::INDEX_WIDTH>` however
37 /// Rust does not currently support using associated constants in const
38 /// generics
39 #[doc(hidden)]
40 type RawBytes: ULE;
41
42 // various conversions because RawBytes is an associated constant now
43 #[doc(hidden)]
44 fn rawbytes_to_usize(raw: Self::RawBytes) -> usize;
45 #[doc(hidden)]
46 fn usize_to_rawbytes(u: usize) -> Self::RawBytes;
47
48 #[doc(hidden)]
49 fn rawbytes_from_byte_slice_unchecked_mut(bytes: &mut [u8]) -> &mut [Self::RawBytes];
50}
51
52/// This is a [`VarZeroVecFormat`] that stores u16s in the index array.
53/// Will have a smaller data size, but it's more likely for larger arrays
54/// to be unrepresentable (and error on construction)
55///
56/// This is the default index size used by all [`VarZeroVec`](super::VarZeroVec) types.
57#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
58#[allow(clippy::exhaustive_structs)] // marker
59pub struct Index16;
60
61/// This is a [`VarZeroVecFormat`] that stores u32s in the index array.
62/// Will have a larger data size, but will support large arrays without
63/// problems.
64#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
65#[allow(clippy::exhaustive_structs)] // marker
66pub struct Index32;
67
68unsafe impl VarZeroVecFormat for Index16 {
69 const INDEX_WIDTH: usize = 2;
70 const MAX_VALUE: u32 = u16::MAX as u32;
71 type RawBytes = RawBytesULE<2>;
72 #[inline]
73 fn rawbytes_to_usize(raw: Self::RawBytes) -> usize {
74 raw.as_unsigned_int() as usize
75 }
76 #[inline]
77 fn usize_to_rawbytes(u: usize) -> Self::RawBytes {
78 (u as u16).to_unaligned()
79 }
80 #[inline]
81 fn rawbytes_from_byte_slice_unchecked_mut(bytes: &mut [u8]) -> &mut [Self::RawBytes] {
82 Self::RawBytes::from_byte_slice_unchecked_mut(bytes)
83 }
84}
85
86unsafe impl VarZeroVecFormat for Index32 {
87 const INDEX_WIDTH: usize = 4;
88 const MAX_VALUE: u32 = u32::MAX;
89 type RawBytes = RawBytesULE<4>;
90 #[inline]
91 fn rawbytes_to_usize(raw: Self::RawBytes) -> usize {
92 raw.as_unsigned_int() as usize
93 }
94 #[inline]
95 fn usize_to_rawbytes(u: usize) -> Self::RawBytes {
96 (u as u32).to_unaligned()
97 }
98 #[inline]
99 fn rawbytes_from_byte_slice_unchecked_mut(bytes: &mut [u8]) -> &mut [Self::RawBytes] {
100 Self::RawBytes::from_byte_slice_unchecked_mut(bytes)
101 }
102}
103
104/// A more parsed version of `VarZeroSlice`. This type is where most of the VarZeroVec
105/// internal representation code lies.
106///
107/// This is *basically* an `&'a [u8]` to a zero copy buffer, but split out into
108/// the buffer components. Logically this is capable of behaving as
109/// a `&'a [T::VarULE]`, but since `T::VarULE` is unsized that type does not actually
110/// exist.
111///
112/// See [`VarZeroVecComponents::parse_byte_slice()`] for information on the internal invariants involved
113#[derive(Debug)]
114pub struct VarZeroVecComponents<'a, T: ?Sized, F> {
115 /// The number of elements
116 len: u32,
117 /// The list of indices into the `things` slice
118 indices: &'a [u8],
119 /// The contiguous list of `T::VarULE`s
120 things: &'a [u8],
121 /// The original slice this was constructed from
122 entire_slice: &'a [u8],
123 marker: PhantomData<(&'a T, F)>,
124}
125
126// #[derive()] won't work here since we do not want it to be
127// bound on T: Copy
128impl<'a, T: ?Sized, F> Copy for VarZeroVecComponents<'a, T, F> {}
129impl<'a, T: ?Sized, F> Clone for VarZeroVecComponents<'a, T, F> {
130 fn clone(&self) -> Self {
131 *self
132 }
133}
134
135impl<'a, T: VarULE + ?Sized, F> Default for VarZeroVecComponents<'a, T, F> {
136 #[inline]
137 fn default() -> Self {
138 Self::new()
139 }
140}
141
142impl<'a, T: VarULE + ?Sized, F> VarZeroVecComponents<'a, T, F> {
143 #[inline]
144 pub fn new() -> Self {
145 Self {
146 len: 0,
147 indices: &[],
148 things: &[],
149 entire_slice: &[],
150 marker: PhantomData,
151 }
152 }
153}
154impl<'a, T: VarULE + ?Sized, F: VarZeroVecFormat> VarZeroVecComponents<'a, T, F> {
155 /// Construct a new VarZeroVecComponents, checking invariants about the overall buffer size:
156 ///
157 /// - There must be either zero or at least four bytes (if four, this is the "length" parsed as a usize)
158 /// - There must be at least `4*length + 4` bytes total, to form the array `indices` of indices
159 /// - `indices[i]..indices[i+1]` must index into a valid section of
160 /// `things`, such that it parses to a `T::VarULE`
161 /// - `indices[len - 1]..things.len()` must index into a valid section of
162 /// `things`, such that it parses to a `T::VarULE`
163 #[inline]
164 pub fn parse_byte_slice(slice: &'a [u8]) -> Result<Self, ZeroVecError> {
165 // The empty VZV is special-cased to the empty slice
166 if slice.is_empty() {
167 return Ok(VarZeroVecComponents {
168 len: 0,
169 indices: &[],
170 things: &[],
171 entire_slice: slice,
172 marker: PhantomData,
173 });
174 }
175 let len_bytes = slice
176 .get(0..LENGTH_WIDTH)
177 .ok_or(ZeroVecError::VarZeroVecFormatError)?;
178 let len_ule = RawBytesULE::<LENGTH_WIDTH>::parse_byte_slice(len_bytes)
179 .map_err(|_| ZeroVecError::VarZeroVecFormatError)?;
180
181 let len = len_ule
182 .get(0)
183 .ok_or(ZeroVecError::VarZeroVecFormatError)?
184 .as_unsigned_int();
185 let indices_bytes = slice
186 .get(
187 LENGTH_WIDTH + METADATA_WIDTH
188 ..LENGTH_WIDTH + METADATA_WIDTH + F::INDEX_WIDTH * (len as usize),
189 )
190 .ok_or(ZeroVecError::VarZeroVecFormatError)?;
191 let things = slice
192 .get(F::INDEX_WIDTH * (len as usize) + LENGTH_WIDTH + METADATA_WIDTH..)
193 .ok_or(ZeroVecError::VarZeroVecFormatError)?;
194
195 let borrowed = VarZeroVecComponents {
196 len,
197 indices: indices_bytes,
198 things,
199 entire_slice: slice,
200 marker: PhantomData,
201 };
202
203 borrowed.check_indices_and_things()?;
204
205 Ok(borrowed)
206 }
207
208 /// Construct a [`VarZeroVecComponents`] from a byte slice that has previously
209 /// successfully returned a [`VarZeroVecComponents`] when passed to
210 /// [`VarZeroVecComponents::parse_byte_slice()`]. Will return the same
211 /// object as one would get from calling [`VarZeroVecComponents::parse_byte_slice()`].
212 ///
213 /// # Safety
214 /// The bytes must have previously successfully run through
215 /// [`VarZeroVecComponents::parse_byte_slice()`]
216 pub unsafe fn from_bytes_unchecked(slice: &'a [u8]) -> Self {
217 // The empty VZV is special-cased to the empty slice
218 if slice.is_empty() {
219 return VarZeroVecComponents {
220 len: 0,
221 indices: &[],
222 things: &[],
223 entire_slice: slice,
224 marker: PhantomData,
225 };
226 }
227 let len_bytes = slice.get_unchecked(0..LENGTH_WIDTH);
228 let len_ule = RawBytesULE::<LENGTH_WIDTH>::from_byte_slice_unchecked(len_bytes);
229
230 let len = len_ule.get_unchecked(0).as_unsigned_int();
231 let indices_bytes = slice.get_unchecked(
232 LENGTH_WIDTH + METADATA_WIDTH
233 ..LENGTH_WIDTH + METADATA_WIDTH + F::INDEX_WIDTH * (len as usize),
234 );
235 let things =
236 slice.get_unchecked(LENGTH_WIDTH + METADATA_WIDTH + F::INDEX_WIDTH * (len as usize)..);
237
238 VarZeroVecComponents {
239 len,
240 indices: indices_bytes,
241 things,
242 entire_slice: slice,
243 marker: PhantomData,
244 }
245 }
246
247 /// Get the number of elements in this vector
248 #[inline]
249 pub fn len(self) -> usize {
250 self.len as usize
251 }
252
253 /// Returns `true` if the vector contains no elements.
254 #[inline]
255 pub fn is_empty(self) -> bool {
256 self.indices.is_empty()
257 }
258
259 /// Get the idx'th element out of this slice. Returns `None` if out of bounds.
260 #[inline]
261 pub fn get(self, idx: usize) -> Option<&'a T> {
262 if idx >= self.len() {
263 return None;
264 }
265 Some(unsafe { self.get_unchecked(idx) })
266 }
267
268 /// Get the idx'th element out of this slice. Does not bounds check.
269 ///
270 /// Safety:
271 /// - `idx` must be in bounds (`idx < self.len()`)
272 #[inline]
273 pub(crate) unsafe fn get_unchecked(self, idx: usize) -> &'a T {
274 let range = self.get_things_range(idx);
275 let things_slice = self.things.get_unchecked(range);
276 T::from_byte_slice_unchecked(things_slice)
277 }
278
279 /// Get the range in `things` for the element at `idx`. Does not bounds check.
280 ///
281 /// Safety:
282 /// - `idx` must be in bounds (`idx < self.len()`)
283 #[inline]
284 unsafe fn get_things_range(self, idx: usize) -> Range<usize> {
285 let start = F::rawbytes_to_usize(*self.indices_slice().get_unchecked(idx));
286 let end = if idx + 1 == self.len() {
287 self.things.len()
288 } else {
289 F::rawbytes_to_usize(*self.indices_slice().get_unchecked(idx + 1))
290 };
291 debug_assert!(start <= end);
292 start..end
293 }
294
295 /// Get the range in `entire_slice` for the element at `idx`. Does not bounds check.
296 ///
297 /// Safety:
298 /// - `idx` must be in bounds (`idx < self.len()`)
299 #[inline]
300 pub(crate) unsafe fn get_range(self, idx: usize) -> Range<usize> {
301 let range = self.get_things_range(idx);
302 let offset = (self.things as *const [u8] as *const u8)
303 .offset_from(self.entire_slice as *const [u8] as *const u8)
304 as usize;
305 range.start + offset..range.end + offset
306 }
307
308 /// Check the internal invariants of VarZeroVecComponents:
309 ///
310 /// - `indices[i]..indices[i+1]` must index into a valid section of
311 /// `things`, such that it parses to a `T::VarULE`
312 /// - `indices[len - 1]..things.len()` must index into a valid section of
313 /// `things`, such that it parses to a `T::VarULE`
314 /// - `indices` is monotonically increasing
315 ///
316 /// This method is NOT allowed to call any other methods on VarZeroVecComponents since all other methods
317 /// assume that the slice has been passed through check_indices_and_things
318 #[inline]
319 #[allow(clippy::len_zero)] // more explicit to enforce safety invariants
320 fn check_indices_and_things(self) -> Result<(), ZeroVecError> {
321 assert_eq!(self.len(), self.indices_slice().len());
322 if self.len() == 0 {
323 if self.things.len() > 0 {
324 return Err(ZeroVecError::VarZeroVecFormatError);
325 } else {
326 return Ok(());
327 }
328 }
329 // Safety: i is in bounds (assertion above)
330 let mut start = F::rawbytes_to_usize(unsafe { *self.indices_slice().get_unchecked(0) });
331 if start != 0 {
332 return Err(ZeroVecError::VarZeroVecFormatError);
333 }
334 for i in 0..self.len() {
335 let end = if i == self.len() - 1 {
336 self.things.len()
337 } else {
338 // Safety: i+1 is in bounds (assertion above)
339 F::rawbytes_to_usize(unsafe { *self.indices_slice().get_unchecked(i + 1) })
340 };
341 if start > end {
342 return Err(ZeroVecError::VarZeroVecFormatError);
343 }
344 if end > self.things.len() {
345 return Err(ZeroVecError::VarZeroVecFormatError);
346 }
347 // Safety: start..end is a valid range in self.things
348 let bytes = unsafe { self.things.get_unchecked(start..end) };
349 T::parse_byte_slice(bytes)?;
350 start = end;
351 }
352 Ok(())
353 }
354
355 /// Create an iterator over the Ts contained in VarZeroVecComponents
356 #[inline]
357 pub fn iter(self) -> impl Iterator<Item = &'a T> {
358 self.indices_slice()
359 .iter()
360 .copied()
361 .map(F::rawbytes_to_usize)
362 .zip(
363 self.indices_slice()
364 .iter()
365 .copied()
366 .map(F::rawbytes_to_usize)
367 .skip(1)
368 .chain([self.things.len()]),
369 )
370 .map(move |(start, end)| unsafe { self.things.get_unchecked(start..end) })
371 .map(|bytes| unsafe { T::from_byte_slice_unchecked(bytes) })
372 }
373
374 pub fn to_vec(self) -> Vec<Box<T>> {
375 self.iter().map(T::to_boxed).collect()
376 }
377
378 #[inline]
379 fn indices_slice(&self) -> &'a [F::RawBytes] {
380 unsafe { F::RawBytes::from_byte_slice_unchecked(self.indices) }
381 }
382
383 // Dump a debuggable representation of this type
384 #[allow(unused)] // useful for debugging
385 pub(crate) fn dump(&self) -> String {
386 let indices = self
387 .indices_slice()
388 .iter()
389 .copied()
390 .map(F::rawbytes_to_usize)
391 .collect::<Vec<_>>();
392 format!("VarZeroVecComponents {{ indices: {indices:?} }}")
393 }
394}
395
396impl<'a, T, F> VarZeroVecComponents<'a, T, F>
397where
398 T: VarULE,
399 T: ?Sized,
400 T: Ord,
401 F: VarZeroVecFormat,
402{
403 /// Binary searches a sorted `VarZeroVecComponents<T>` for the given element. For more information, see
404 /// the primitive function [`binary_search`](slice::binary_search).
405 pub fn binary_search(&self, needle: &T) -> Result<usize, usize> {
406 self.binary_search_impl(|probe: &T| probe.cmp(needle), self.indices_slice())
407 }
408
409 pub fn binary_search_in_range(
410 &self,
411 needle: &T,
412 range: Range<usize>,
413 ) -> Option<Result<usize, usize>> {
414 let indices_slice: &[::RawBytes] = self.indices_slice().get(index:range)?;
415 Some(self.binary_search_impl(|probe: &T| probe.cmp(needle), indices_slice))
416 }
417}
418
419impl<'a, T, F> VarZeroVecComponents<'a, T, F>
420where
421 T: VarULE,
422 T: ?Sized,
423 F: VarZeroVecFormat,
424{
425 /// Binary searches a sorted `VarZeroVecComponents<T>` for the given predicate. For more information, see
426 /// the primitive function [`binary_search_by`](slice::binary_search_by).
427 pub fn binary_search_by(&self, predicate: impl FnMut(&T) -> Ordering) -> Result<usize, usize> {
428 self.binary_search_impl(predicate, self.indices_slice())
429 }
430
431 pub fn binary_search_in_range_by(
432 &self,
433 predicate: impl FnMut(&T) -> Ordering,
434 range: Range<usize>,
435 ) -> Option<Result<usize, usize>> {
436 let indices_slice = self.indices_slice().get(range)?;
437 Some(self.binary_search_impl(predicate, indices_slice))
438 }
439
440 /// Binary searches a sorted `VarZeroVecComponents<T>` with the given predicate. For more information, see
441 /// the primitive function [`binary_search`](slice::binary_search).
442 fn binary_search_impl(
443 &self,
444 mut predicate: impl FnMut(&T) -> Ordering,
445 indices_slice: &[F::RawBytes],
446 ) -> Result<usize, usize> {
447 // This code is an absolute atrocity. This code is not a place of honor. This
448 // code is known to the State of California to cause cancer.
449 //
450 // Unfortunately, the stdlib's `binary_search*` functions can only operate on slices.
451 // We do not have a slice. We have something we can .get() and index on, but that is not
452 // a slice.
453 //
454 // The `binary_search*` functions also do not have a variant where they give you the element's
455 // index, which we could otherwise use to directly index `self`.
456 // We do have `self.indices`, but these are indices into a byte buffer, which cannot in
457 // isolation be used to recoup the logical index of the element they refer to.
458 //
459 // However, `binary_search_by()` provides references to the elements of the slice being iterated.
460 // Since the layout of Rust slices is well-defined, we can do pointer arithmetic on these references
461 // to obtain the index being used by the search.
462 //
463 // It's worth noting that the slice we choose to search is irrelevant, as long as it has the appropriate
464 // length. `self.indices` is defined to have length `self.len()`, so it is convenient to use
465 // here and does not require additional allocations.
466 //
467 // The alternative to doing this is to implement our own binary search. This is significantly less fun.
468
469 // Note: We always use zero_index relative to the whole indices array, even if we are
470 // only searching a subslice of it.
471 let zero_index = self.indices.as_ptr() as *const _ as usize;
472 indices_slice.binary_search_by(|probe: &_| {
473 // `self.indices` is a vec of unaligned F::INDEX_WIDTH values, so we divide by F::INDEX_WIDTH
474 // to get the actual index
475 let index = (probe as *const _ as usize - zero_index) / F::INDEX_WIDTH;
476 // safety: we know this is in bounds
477 let actual_probe = unsafe { self.get_unchecked(index) };
478 predicate(actual_probe)
479 })
480 }
481}
482
483/// Collects the bytes for a VarZeroSlice into a Vec.
484pub fn get_serializable_bytes_non_empty<T, A, F>(elements: &[A]) -> Option<Vec<u8>>
485where
486 T: VarULE + ?Sized,
487 A: EncodeAsVarULE<T>,
488 F: VarZeroVecFormat,
489{
490 debug_assert!(!elements.is_empty());
491 let len: u32 = compute_serializable_len::<T, A, F>(elements)?;
492 debug_assert!(len >= LENGTH_WIDTH as u32);
493 let mut output: Vec<u8> = alloc::vec![0; len as usize];
494 write_serializable_bytes::<T, A, F>(elements, &mut output);
495 Some(output)
496}
497
498/// Writes the bytes for a VarZeroSlice into an output buffer.
499///
500/// Every byte in the buffer will be initialized after calling this function.
501///
502/// # Panics
503///
504/// Panics if the buffer is not exactly the correct length.
505pub fn write_serializable_bytes<T, A, F>(elements: &[A], output: &mut [u8])
506where
507 T: VarULE + ?Sized,
508 A: EncodeAsVarULE<T>,
509 F: VarZeroVecFormat,
510{
511 assert!(elements.len() <= MAX_LENGTH);
512 let num_elements_bytes = elements.len().to_le_bytes();
513 #[allow(clippy::indexing_slicing)] // Function contract allows panicky behavior
514 output[0..LENGTH_WIDTH].copy_from_slice(&num_elements_bytes[0..LENGTH_WIDTH]);
515
516 // idx_offset = offset from the start of the buffer for the next index
517 let mut idx_offset: usize = LENGTH_WIDTH + METADATA_WIDTH;
518 // first_dat_offset = offset from the start of the buffer of the first data block
519 let first_dat_offset: usize = idx_offset + elements.len() * F::INDEX_WIDTH;
520 // dat_offset = offset from the start of the buffer of the next data block
521 let mut dat_offset: usize = first_dat_offset;
522
523 for element in elements.iter() {
524 let element_len = element.encode_var_ule_len();
525
526 let idx_limit = idx_offset + F::INDEX_WIDTH;
527 #[allow(clippy::indexing_slicing)] // Function contract allows panicky behavior
528 let idx_slice = &mut output[idx_offset..idx_limit];
529 // VZV expects data offsets to be stored relative to the first data block
530 let idx = dat_offset - first_dat_offset;
531 assert!(idx <= MAX_INDEX);
532 #[allow(clippy::indexing_slicing)] // this function is explicitly panicky
533 idx_slice.copy_from_slice(&idx.to_le_bytes()[..F::INDEX_WIDTH]);
534
535 let dat_limit = dat_offset + element_len;
536 #[allow(clippy::indexing_slicing)] // Function contract allows panicky behavior
537 let dat_slice = &mut output[dat_offset..dat_limit];
538 element.encode_var_ule_write(dat_slice);
539 debug_assert_eq!(T::validate_byte_slice(dat_slice), Ok(()));
540
541 idx_offset = idx_limit;
542 dat_offset = dat_limit;
543 }
544
545 debug_assert_eq!(
546 idx_offset,
547 LENGTH_WIDTH + METADATA_WIDTH + F::INDEX_WIDTH * elements.len()
548 );
549 assert_eq!(dat_offset, output.len());
550}
551
552pub fn compute_serializable_len<T, A, F>(elements: &[A]) -> Option<u32>
553where
554 T: VarULE + ?Sized,
555 A: EncodeAsVarULE<T>,
556 F: VarZeroVecFormat,
557{
558 let idx_len: u32 = u32u32::try_from(elements.len())
559 .ok()?
560 .checked_mul(F::INDEX_WIDTH as u32)?
561 .checked_add(LENGTH_WIDTH as u32)?
562 .checked_add(METADATA_WIDTH as u32)?;
563 let data_len: u32 = elements
564 .iter()
565 .map(|v| u32::try_from(v.encode_var_ule_len()).ok())
566 .try_fold(init:0u32, |s: u32, v: Option| s.checked_add(v?))?;
567 let ret: Option = idx_len.checked_add(data_len);
568 if let Some(r: u32) = ret {
569 if r >= F::MAX_VALUE {
570 return None;
571 }
572 }
573 ret
574}
575