use crate::ule::*;
use alloc::boxed::Box;
use alloc::format;
use alloc::string::String;
use alloc::vec::Vec;
use core::cmp::Ordering;
use core::convert::TryFrom;
use core::marker::PhantomData;
use core::ops::Range;
pub(super) const LENGTH_WIDTH: usize = 4;
pub(super) const METADATA_WIDTH: usize = 0;
pub(super) const MAX_LENGTH: usize = u32::MAX as usize;
pub(super) const MAX_INDEX: usize = u32::MAX as usize;
#[allow(clippy::missing_safety_doc)] pub unsafe trait VarZeroVecFormat: 'static + Sized {
#[doc(hidden)]
const INDEX_WIDTH: usize;
#[doc(hidden)]
const MAX_VALUE: u32;
#[doc(hidden)]
type RawBytes: ULE;
#[doc(hidden)]
fn rawbytes_to_usize(raw: Self::RawBytes) -> usize;
#[doc(hidden)]
fn usize_to_rawbytes(u: usize) -> Self::RawBytes;
#[doc(hidden)]
fn rawbytes_from_byte_slice_unchecked_mut(bytes: &mut [u8]) -> &mut [Self::RawBytes];
}
#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
#[allow(clippy::exhaustive_structs)] pub struct Index16;
#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
#[allow(clippy::exhaustive_structs)] pub struct Index32;
unsafe impl VarZeroVecFormat for Index16 {
const INDEX_WIDTH: usize = 2;
const MAX_VALUE: u32 = u16::MAX as u32;
type RawBytes = RawBytesULE<2>;
#[inline]
fn rawbytes_to_usize(raw: Self::RawBytes) -> usize {
raw.as_unsigned_int() as usize
}
#[inline]
fn usize_to_rawbytes(u: usize) -> Self::RawBytes {
(u as u16).to_unaligned()
}
#[inline]
fn rawbytes_from_byte_slice_unchecked_mut(bytes: &mut [u8]) -> &mut [Self::RawBytes] {
Self::RawBytes::from_byte_slice_unchecked_mut(bytes)
}
}
unsafe impl VarZeroVecFormat for Index32 {
const INDEX_WIDTH: usize = 4;
const MAX_VALUE: u32 = u32::MAX as u32;
type RawBytes = RawBytesULE<4>;
#[inline]
fn rawbytes_to_usize(raw: Self::RawBytes) -> usize {
raw.as_unsigned_int() as usize
}
#[inline]
fn usize_to_rawbytes(u: usize) -> Self::RawBytes {
(u as u32).to_unaligned()
}
#[inline]
fn rawbytes_from_byte_slice_unchecked_mut(bytes: &mut [u8]) -> &mut [Self::RawBytes] {
Self::RawBytes::from_byte_slice_unchecked_mut(bytes)
}
}
pub struct VarZeroVecComponents<'a, T: ?Sized, F> {
len: u32,
indices: &'a [u8],
things: &'a [u8],
entire_slice: &'a [u8],
marker: PhantomData<(&'a T, F)>,
}
impl<'a, T: ?Sized, F> Copy for VarZeroVecComponents<'a, T, F> {}
impl<'a, T: ?Sized, F> Clone for VarZeroVecComponents<'a, T, F> {
fn clone(&self) -> Self {
VarZeroVecComponents {
len: self.len,
indices: self.indices,
things: self.things,
entire_slice: self.entire_slice,
marker: PhantomData,
}
}
}
impl<'a, T: VarULE + ?Sized, F> Default for VarZeroVecComponents<'a, T, F> {
#[inline]
fn default() -> Self {
Self::new()
}
}
impl<'a, T: VarULE + ?Sized, F> VarZeroVecComponents<'a, T, F> {
#[inline]
pub fn new() -> Self {
Self {
len: 0,
indices: &[],
things: &[],
entire_slice: &[],
marker: PhantomData,
}
}
}
impl<'a, T: VarULE + ?Sized, F: VarZeroVecFormat> VarZeroVecComponents<'a, T, F> {
#[inline]
pub fn parse_byte_slice(slice: &'a [u8]) -> Result<Self, ZeroVecError> {
if slice.is_empty() {
return Ok(VarZeroVecComponents {
len: 0,
indices: &[],
things: &[],
entire_slice: slice,
marker: PhantomData,
});
}
let len_bytes = slice
.get(0..LENGTH_WIDTH)
.ok_or(ZeroVecError::VarZeroVecFormatError)?;
let len_ule = RawBytesULE::<LENGTH_WIDTH>::parse_byte_slice(len_bytes)
.map_err(|_| ZeroVecError::VarZeroVecFormatError)?;
let len = len_ule
.get(0)
.ok_or(ZeroVecError::VarZeroVecFormatError)?
.as_unsigned_int();
let indices_bytes = slice
.get(
LENGTH_WIDTH + METADATA_WIDTH
..LENGTH_WIDTH + METADATA_WIDTH + F::INDEX_WIDTH * (len as usize),
)
.ok_or(ZeroVecError::VarZeroVecFormatError)?;
let things = slice
.get(F::INDEX_WIDTH * (len as usize) + LENGTH_WIDTH + METADATA_WIDTH..)
.ok_or(ZeroVecError::VarZeroVecFormatError)?;
let borrowed = VarZeroVecComponents {
len: len as u32,
indices: indices_bytes,
things,
entire_slice: slice,
marker: PhantomData,
};
borrowed.check_indices_and_things()?;
Ok(borrowed)
}
pub unsafe fn from_bytes_unchecked(slice: &'a [u8]) -> Self {
if slice.is_empty() {
return VarZeroVecComponents {
len: 0,
indices: &[],
things: &[],
entire_slice: slice,
marker: PhantomData,
};
}
let len_bytes = slice.get_unchecked(0..LENGTH_WIDTH);
let len_ule = RawBytesULE::<LENGTH_WIDTH>::from_byte_slice_unchecked(len_bytes);
let len = len_ule.get_unchecked(0).as_unsigned_int();
let indices_bytes = slice.get_unchecked(
LENGTH_WIDTH + METADATA_WIDTH
..LENGTH_WIDTH + METADATA_WIDTH + F::INDEX_WIDTH * (len as usize),
);
let things =
slice.get_unchecked(LENGTH_WIDTH + METADATA_WIDTH + F::INDEX_WIDTH * (len as usize)..);
VarZeroVecComponents {
len,
indices: indices_bytes,
things,
entire_slice: slice,
marker: PhantomData,
}
}
#[inline]
pub fn len(self) -> usize {
self.len as usize
}
#[inline]
pub fn is_empty(self) -> bool {
self.indices.is_empty()
}
#[inline]
pub fn get(self, idx: usize) -> Option<&'a T> {
if idx >= self.len() {
return None;
}
Some(unsafe { self.get_unchecked(idx) })
}
#[inline]
pub(crate) unsafe fn get_unchecked(self, idx: usize) -> &'a T {
let range = self.get_things_range(idx);
let things_slice = self.things.get_unchecked(range);
T::from_byte_slice_unchecked(things_slice)
}
#[inline]
unsafe fn get_things_range(self, idx: usize) -> Range<usize> {
let start = F::rawbytes_to_usize(*self.indices_slice().get_unchecked(idx));
let end = if idx + 1 == self.len() {
self.things.len()
} else {
F::rawbytes_to_usize(*self.indices_slice().get_unchecked(idx + 1))
};
debug_assert!(start <= end);
start..end
}
#[inline]
pub(crate) unsafe fn get_range(self, idx: usize) -> Range<usize> {
let range = self.get_things_range(idx);
let offset = (self.things as *const [u8] as *const u8)
.offset_from(self.entire_slice as *const [u8] as *const u8)
as usize;
range.start + offset..range.end + offset
}
#[inline]
#[allow(clippy::len_zero)] fn check_indices_and_things(self) -> Result<(), ZeroVecError> {
assert_eq!(self.len(), self.indices_slice().len());
if self.len() == 0 {
if self.things.len() > 0 {
return Err(ZeroVecError::VarZeroVecFormatError);
} else {
return Ok(());
}
}
let mut start = F::rawbytes_to_usize(unsafe { *self.indices_slice().get_unchecked(0) });
if start != 0 {
return Err(ZeroVecError::VarZeroVecFormatError);
}
for i in 0..self.len() {
let end = if i == self.len() - 1 {
self.things.len()
} else {
F::rawbytes_to_usize(unsafe { *self.indices_slice().get_unchecked(i + 1) })
};
if start > end {
return Err(ZeroVecError::VarZeroVecFormatError);
}
if end > self.things.len() {
return Err(ZeroVecError::VarZeroVecFormatError);
}
let bytes = unsafe { self.things.get_unchecked(start..end) };
T::parse_byte_slice(bytes)?;
start = end;
}
Ok(())
}
#[inline]
pub fn iter(self) -> impl Iterator<Item = &'a T> {
self.indices_slice()
.iter()
.copied()
.map(F::rawbytes_to_usize)
.zip(
self.indices_slice()
.iter()
.copied()
.map(F::rawbytes_to_usize)
.skip(1)
.chain(core::iter::once(self.things.len())),
)
.map(move |(start, end)| unsafe { self.things.get_unchecked(start..end) })
.map(|bytes| unsafe { T::from_byte_slice_unchecked(bytes) })
}
pub fn to_vec(self) -> Vec<Box<T>> {
self.iter().map(T::to_boxed).collect()
}
#[inline]
fn indices_slice(&self) -> &'a [F::RawBytes] {
unsafe { F::RawBytes::from_byte_slice_unchecked(self.indices) }
}
#[allow(unused)] pub(crate) fn dump(&self) -> String {
let indices = self
.indices_slice()
.iter()
.copied()
.map(F::rawbytes_to_usize)
.collect::<Vec<_>>();
format!("VarZeroVecComponents {{ indices: {:?} }}", indices)
}
}
impl<'a, T, F> VarZeroVecComponents<'a, T, F>
where
T: VarULE,
T: ?Sized,
T: Ord,
F: VarZeroVecFormat,
{
pub fn binary_search(&self, needle: &T) -> Result<usize, usize> {
self.binary_search_impl(|probe| probe.cmp(needle), self.indices_slice())
}
pub fn binary_search_in_range(
&self,
needle: &T,
range: Range<usize>,
) -> Option<Result<usize, usize>> {
let indices_slice = self.indices_slice().get(range)?;
Some(self.binary_search_impl(|probe| probe.cmp(needle), indices_slice))
}
}
impl<'a, T, F> VarZeroVecComponents<'a, T, F>
where
T: VarULE,
T: ?Sized,
F: VarZeroVecFormat,
{
pub fn binary_search_by(&self, predicate: impl FnMut(&T) -> Ordering) -> Result<usize, usize> {
self.binary_search_impl(predicate, self.indices_slice())
}
pub fn binary_search_in_range_by(
&self,
predicate: impl FnMut(&T) -> Ordering,
range: Range<usize>,
) -> Option<Result<usize, usize>> {
let indices_slice = self.indices_slice().get(range)?;
Some(self.binary_search_impl(predicate, indices_slice))
}
fn binary_search_impl(
&self,
mut predicate: impl FnMut(&T) -> Ordering,
indices_slice: &[F::RawBytes],
) -> Result<usize, usize> {
let zero_index = self.indices.as_ptr() as *const _ as usize;
indices_slice.binary_search_by(|probe: &_| {
let index = (probe as *const _ as usize - zero_index) / F::INDEX_WIDTH;
let actual_probe = unsafe { self.get_unchecked(index) };
predicate(actual_probe)
})
}
}
pub fn get_serializable_bytes<T, A, F>(elements: &[A]) -> Option<Vec<u8>>
where
T: VarULE + ?Sized,
A: EncodeAsVarULE<T>,
F: VarZeroVecFormat,
{
let len = compute_serializable_len::<T, A, F>(elements)?;
debug_assert!(len >= LENGTH_WIDTH as u32);
let mut output: Vec<u8> = alloc::vec![0; len as usize];
write_serializable_bytes::<T, A, F>(elements, &mut output);
Some(output)
}
pub fn write_serializable_bytes<T, A, F>(elements: &[A], output: &mut [u8])
where
T: VarULE + ?Sized,
A: EncodeAsVarULE<T>,
F: VarZeroVecFormat,
{
assert!(elements.len() <= MAX_LENGTH);
let num_elements_bytes = elements.len().to_le_bytes();
#[allow(clippy::indexing_slicing)] output[0..LENGTH_WIDTH].copy_from_slice(&num_elements_bytes[0..LENGTH_WIDTH]);
let mut idx_offset: usize = LENGTH_WIDTH + METADATA_WIDTH;
let first_dat_offset: usize = idx_offset + elements.len() * F::INDEX_WIDTH;
let mut dat_offset: usize = first_dat_offset;
for element in elements.iter() {
let element_len = element.encode_var_ule_len();
let idx_limit = idx_offset + F::INDEX_WIDTH;
#[allow(clippy::indexing_slicing)] let idx_slice = &mut output[idx_offset..idx_limit];
let idx = dat_offset - first_dat_offset;
assert!(idx <= MAX_INDEX);
#[allow(clippy::indexing_slicing)] idx_slice.copy_from_slice(&idx.to_le_bytes()[..F::INDEX_WIDTH]);
let dat_limit = dat_offset + element_len;
#[allow(clippy::indexing_slicing)] let dat_slice = &mut output[dat_offset..dat_limit];
element.encode_var_ule_write(dat_slice);
debug_assert_eq!(T::validate_byte_slice(dat_slice), Ok(()));
idx_offset = idx_limit;
dat_offset = dat_limit;
}
debug_assert_eq!(
idx_offset,
LENGTH_WIDTH + METADATA_WIDTH + F::INDEX_WIDTH * elements.len()
);
assert_eq!(dat_offset, output.len());
}
pub fn compute_serializable_len<T, A, F>(elements: &[A]) -> Option<u32>
where
T: VarULE + ?Sized,
A: EncodeAsVarULE<T>,
F: VarZeroVecFormat,
{
let idx_len: u32 = u32::try_from(elements.len())
.ok()?
.checked_mul(F::INDEX_WIDTH as u32)?
.checked_add(LENGTH_WIDTH as u32)?
.checked_add(METADATA_WIDTH as u32)?;
let data_len: u32 = elements
.iter()
.map(|v| u32::try_from(v.encode_var_ule_len()).ok())
.fold(Some(0u32), |s, v| {
s.and_then(|s| v.and_then(|v| s.checked_add(v)))
})?;
let ret = idx_len.checked_add(data_len);
if let Some(r) = ret {
if r >= F::MAX_VALUE {
return None;
}
}
ret
}