#![allow(clippy::unwrap_used)]
#![allow(clippy::expect_used)]
#![allow(clippy::indexing_slicing)]
#![allow(clippy::panic)]
use super::*;
use crate::ule::*;
use alloc::boxed::Box;
use alloc::vec::Vec;
use core::any;
use core::convert::TryInto;
use core::marker::PhantomData;
use core::ops::Deref;
use core::ops::Range;
use core::{fmt, ptr, slice};
use super::components::LENGTH_WIDTH;
use super::components::MAX_INDEX;
use super::components::MAX_LENGTH;
use super::components::METADATA_WIDTH;
pub struct VarZeroVecOwned<T: ?Sized, F = Index16> {
marker: PhantomData<(Box<T>, F)>,
entire_slice: Vec<u8>,
}
impl<T: ?Sized, F> Clone for VarZeroVecOwned<T, F> {
fn clone(&self) -> Self {
VarZeroVecOwned {
marker: self.marker,
entire_slice: self.entire_slice.clone(),
}
}
}
#[derive(PartialEq)]
enum ShiftType {
Insert,
Replace,
Remove,
}
impl<T: VarULE + ?Sized, F: VarZeroVecFormat> Deref for VarZeroVecOwned<T, F> {
type Target = VarZeroSlice<T, F>;
fn deref(&self) -> &VarZeroSlice<T, F> {
self.as_slice()
}
}
impl<T: VarULE + ?Sized, F> VarZeroVecOwned<T, F> {
pub fn new() -> Self {
Self {
marker: PhantomData,
entire_slice: Vec::new(),
}
}
}
impl<T: VarULE + ?Sized, F: VarZeroVecFormat> VarZeroVecOwned<T, F> {
pub fn from_slice(slice: &VarZeroSlice<T, F>) -> Self {
Self {
marker: PhantomData,
entire_slice: slice.as_bytes().into(),
}
}
pub fn try_from_elements<A>(elements: &[A]) -> Result<Self, &'static str>
where
A: EncodeAsVarULE<T>,
{
Ok(Self {
marker: PhantomData,
entire_slice: components::get_serializable_bytes::<T, A, F>(elements).ok_or(
"Attempted to build VarZeroVec out of elements that \
cumulatively are larger than a u32 in size",
)?,
})
}
pub fn as_slice(&self) -> &VarZeroSlice<T, F> {
let slice: &[u8] = &*self.entire_slice;
unsafe {
VarZeroSlice::from_byte_slice_unchecked(slice)
}
}
pub(crate) fn with_capacity(capacity: usize) -> Self {
Self {
marker: PhantomData,
entire_slice: Vec::with_capacity(capacity * (F::INDEX_WIDTH + 4)),
}
}
pub(crate) fn reserve(&mut self, capacity: usize) {
self.entire_slice.reserve(capacity * (F::INDEX_WIDTH + 4))
}
unsafe fn element_position_unchecked(&self, idx: usize) -> usize {
let len = self.len();
let out = if idx == len {
self.entire_slice.len() - LENGTH_WIDTH - METADATA_WIDTH - (F::INDEX_WIDTH * len)
} else {
F::rawbytes_to_usize(*self.index_data(idx))
};
debug_assert!(
out + LENGTH_WIDTH + METADATA_WIDTH + len * F::INDEX_WIDTH <= self.entire_slice.len()
);
out
}
unsafe fn element_range_unchecked(&self, idx: usize) -> core::ops::Range<usize> {
let start = self.element_position_unchecked(idx);
let end = self.element_position_unchecked(idx + 1);
debug_assert!(start <= end, "{} > {}", start, end);
start..end
}
unsafe fn set_len(&mut self, len: usize) {
assert!(len <= MAX_LENGTH);
let len_bytes = len.to_le_bytes();
self.entire_slice[0..LENGTH_WIDTH].copy_from_slice(&len_bytes[0..LENGTH_WIDTH]);
assert_eq!(len_bytes[LENGTH_WIDTH..].iter().sum::<u8>(), 0);
}
fn index_range(index: usize) -> Range<usize> {
let pos = LENGTH_WIDTH + METADATA_WIDTH + F::INDEX_WIDTH * index;
pos..pos + F::INDEX_WIDTH
}
unsafe fn index_data(&self, index: usize) -> &F::RawBytes {
&F::RawBytes::from_byte_slice_unchecked(&self.entire_slice[Self::index_range(index)])[0]
}
unsafe fn index_data_mut(&mut self, index: usize) -> &mut F::RawBytes {
let ptr = self.entire_slice.as_mut_ptr();
let range = Self::index_range(index);
let data = slice::from_raw_parts_mut(ptr.add(range.start), F::INDEX_WIDTH);
&mut F::rawbytes_from_byte_slice_unchecked_mut(data)[0]
}
unsafe fn shift_indices(&mut self, starting_index: usize, amount: i32) {
let len = self.len();
let indices = F::rawbytes_from_byte_slice_unchecked_mut(
&mut self.entire_slice[LENGTH_WIDTH + METADATA_WIDTH
..LENGTH_WIDTH + METADATA_WIDTH + F::INDEX_WIDTH * len],
);
for idx in &mut indices[starting_index..] {
let mut new_idx = F::rawbytes_to_usize(*idx);
if amount > 0 {
new_idx = new_idx.checked_add(amount.try_into().unwrap()).unwrap();
} else {
new_idx = new_idx.checked_sub((-amount).try_into().unwrap()).unwrap();
}
*idx = F::usize_to_rawbytes(new_idx);
}
}
pub fn as_varzerovec<'a>(&'a self) -> VarZeroVec<'a, T, F> {
self.as_slice().into()
}
pub fn clear(&mut self) {
self.entire_slice.clear()
}
#[inline]
pub fn into_bytes(self) -> Vec<u8> {
self.entire_slice
}
unsafe fn shift(&mut self, index: usize, new_size: usize, shift_type: ShiftType) -> &mut [u8] {
let len = self.len();
let slice_len = self.entire_slice.len();
let prev_element = match shift_type {
ShiftType::Insert => {
let pos = self.element_position_unchecked(index);
pos..pos
}
_ => self.element_range_unchecked(index),
};
let index_shift: i64 = match shift_type {
ShiftType::Insert => F::INDEX_WIDTH as i64,
ShiftType::Replace => 0,
ShiftType::Remove => -(F::INDEX_WIDTH as i64),
};
let shift: i64 =
new_size as i64 - (prev_element.end - prev_element.start) as i64 + index_shift;
let new_slice_len = slice_len.wrapping_add(shift as usize);
if shift > 0 {
if new_slice_len > F::MAX_VALUE as usize {
panic!(
"Attempted to grow VarZeroVec to an encoded size that does not fit within the length size used by {}",
any::type_name::<F>()
);
}
self.entire_slice.reserve(shift as usize);
}
{
let slice_range = self.entire_slice.as_mut_ptr_range();
let data_start = slice_range
.start
.add(LENGTH_WIDTH + METADATA_WIDTH + len * F::INDEX_WIDTH);
let prev_element_p =
data_start.add(prev_element.start)..data_start.add(prev_element.end);
let index_range = {
let index_start = slice_range
.start
.add(LENGTH_WIDTH + METADATA_WIDTH + F::INDEX_WIDTH * index);
index_start..index_start.add(F::INDEX_WIDTH)
};
unsafe fn shift_bytes(block: Range<*const u8>, to: *mut u8) {
debug_assert!(block.end >= block.start);
ptr::copy(block.start, to, block.end.offset_from(block.start) as usize);
}
if shift_type == ShiftType::Remove {
shift_bytes(index_range.end..prev_element_p.start, index_range.start);
}
shift_bytes(
prev_element_p.end..slice_range.end,
prev_element_p
.start
.offset((new_size as i64 + index_shift) as isize),
);
let first_affected_index = match shift_type {
ShiftType::Insert => {
shift_bytes(index_range.start..prev_element_p.start, index_range.end);
*self.index_data_mut(index) = F::usize_to_rawbytes(prev_element.start);
self.set_len(len + 1);
index + 1
}
ShiftType::Remove => {
self.set_len(len - 1);
index
}
ShiftType::Replace => index + 1,
};
self.entire_slice.set_len(new_slice_len);
self.shift_indices(first_affected_index, (shift - index_shift) as i32);
};
debug_assert!(self.verify_integrity());
let element_pos = LENGTH_WIDTH
+ METADATA_WIDTH
+ self.len() * F::INDEX_WIDTH
+ self.element_position_unchecked(index);
&mut self.entire_slice[element_pos..element_pos + new_size as usize]
}
fn verify_integrity(&self) -> bool {
if self.is_empty() && !self.entire_slice.is_empty() {
return false;
}
let slice_len = self.entire_slice.len();
match slice_len {
0 => return true,
1..=3 => return false,
_ => (),
}
let len = unsafe {
RawBytesULE::<LENGTH_WIDTH>::from_byte_slice_unchecked(
&self.entire_slice[..LENGTH_WIDTH],
)[0]
.as_unsigned_int()
};
if len == 0 {
return false;
}
if slice_len < LENGTH_WIDTH + METADATA_WIDTH + len as usize * F::INDEX_WIDTH {
return false;
}
let data_len =
self.entire_slice.len() - LENGTH_WIDTH - METADATA_WIDTH - len as usize * F::INDEX_WIDTH;
if data_len > MAX_INDEX {
return false;
}
let indices = unsafe {
F::RawBytes::from_byte_slice_unchecked(
&self.entire_slice[LENGTH_WIDTH + METADATA_WIDTH
..LENGTH_WIDTH + METADATA_WIDTH + len as usize * F::INDEX_WIDTH],
)
};
for idx in indices {
if F::rawbytes_to_usize(*idx) > data_len {
return false;
}
}
for window in indices.windows(2) {
if F::rawbytes_to_usize(window[0]) > F::rawbytes_to_usize(window[1]) {
return false;
}
}
true
}
pub fn push<A: EncodeAsVarULE<T> + ?Sized>(&mut self, element: &A) {
self.insert(self.len(), element)
}
pub fn insert<A: EncodeAsVarULE<T> + ?Sized>(&mut self, index: usize, element: &A) {
let len = self.len();
if index > len {
panic!(
"Called out-of-bounds insert() on VarZeroVec, index {} len {}",
index, len
);
}
let value_len = element.encode_var_ule_len();
if len == 0 {
let header_len = LENGTH_WIDTH + METADATA_WIDTH + F::INDEX_WIDTH;
let cap = header_len + value_len;
self.entire_slice.resize(cap, 0);
self.entire_slice[0] = 1; element.encode_var_ule_write(&mut self.entire_slice[header_len..]);
return;
}
assert!(value_len < MAX_INDEX);
unsafe {
let place = self.shift(index, value_len, ShiftType::Insert);
element.encode_var_ule_write(place);
}
}
pub fn remove(&mut self, index: usize) {
let len = self.len();
if index >= len {
panic!(
"Called out-of-bounds remove() on VarZeroVec, index {} len {}",
index, len
);
}
if len == 1 {
self.entire_slice.clear();
return;
}
unsafe {
self.shift(index, 0, ShiftType::Remove);
}
}
pub fn replace<A: EncodeAsVarULE<T> + ?Sized>(&mut self, index: usize, element: &A) {
let len = self.len();
if index >= len {
panic!(
"Called out-of-bounds replace() on VarZeroVec, index {} len {}",
index, len
);
}
let value_len = element.encode_var_ule_len();
assert!(value_len < MAX_INDEX);
unsafe {
let place = self.shift(index, value_len, ShiftType::Replace);
element.encode_var_ule_write(place);
}
}
}
impl<T: VarULE + ?Sized, F: VarZeroVecFormat> fmt::Debug for VarZeroVecOwned<T, F>
where
T: fmt::Debug,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
VarZeroSlice::fmt(self, f)
}
}
impl<T: VarULE + ?Sized, F> Default for VarZeroVecOwned<T, F> {
fn default() -> Self {
Self::new()
}
}
impl<T, A, F> PartialEq<&'_ [A]> for VarZeroVecOwned<T, F>
where
T: VarULE + ?Sized,
T: PartialEq,
A: AsRef<T>,
F: VarZeroVecFormat,
{
#[inline]
fn eq(&self, other: &&[A]) -> bool {
self.iter().eq(other.iter().map(|t| t.as_ref()))
}
}
impl<'a, T: ?Sized + VarULE, F: VarZeroVecFormat> From<&'a VarZeroSlice<T, F>>
for VarZeroVecOwned<T, F>
{
fn from(other: &'a VarZeroSlice<T, F>) -> Self {
Self::from_slice(other)
}
}
#[cfg(test)]
mod test {
use super::VarZeroVecOwned;
#[test]
fn test_insert_integrity() {
let mut items: Vec<String> = Vec::new();
let mut zerovec = VarZeroVecOwned::<str>::new();
items.insert(0, "1234567890".into());
zerovec.insert(0, "1234567890");
assert_eq!(zerovec, &*items);
zerovec.insert(1, "foo3");
items.insert(1, "foo3".into());
assert_eq!(zerovec, &*items);
items.insert(items.len(), "qwertyuiop".into());
zerovec.insert(zerovec.len(), "qwertyuiop");
assert_eq!(zerovec, &*items);
items.insert(0, "asdfghjkl;".into());
zerovec.insert(0, "asdfghjkl;");
assert_eq!(zerovec, &*items);
items.insert(2, "".into());
zerovec.insert(2, "");
assert_eq!(zerovec, &*items);
}
#[test]
fn test_empty_inserts() {
let mut items: Vec<String> = Vec::new();
let mut zerovec = VarZeroVecOwned::<str>::new();
items.insert(0, "".into());
zerovec.insert(0, "");
assert_eq!(zerovec, &*items);
items.insert(0, "".into());
zerovec.insert(0, "");
assert_eq!(zerovec, &*items);
items.insert(0, "1234567890".into());
zerovec.insert(0, "1234567890");
assert_eq!(zerovec, &*items);
items.insert(0, "".into());
zerovec.insert(0, "");
assert_eq!(zerovec, &*items);
}
#[test]
fn test_small_insert_integrity() {
let mut items: Vec<String> = Vec::new();
let mut zerovec = VarZeroVecOwned::<str>::new();
items.insert(0, "abc".into());
zerovec.insert(0, "abc");
assert_eq!(zerovec, &*items);
zerovec.insert(1, "def");
items.insert(1, "def".into());
assert_eq!(zerovec, &*items);
}
#[test]
#[should_panic]
fn test_insert_past_end() {
VarZeroVecOwned::<str>::new().insert(1, "");
}
#[test]
fn test_remove_integrity() {
let mut items: Vec<&str> = vec!["apples", "bananas", "eeples", "", "baneenees", "five", ""];
let mut zerovec = VarZeroVecOwned::<str>::try_from_elements(&items).unwrap();
for index in [0, 2, 4, 0, 1, 1, 0] {
items.remove(index);
zerovec.remove(index);
assert_eq!(zerovec, &*items, "index {}, len {}", index, items.len());
}
}
#[test]
fn test_removing_last_element_clears() {
let mut zerovec = VarZeroVecOwned::<str>::try_from_elements(&["buy some apples"]).unwrap();
assert!(!zerovec.as_bytes().is_empty());
zerovec.remove(0);
assert!(zerovec.as_bytes().is_empty());
}
#[test]
#[should_panic]
fn test_remove_past_end() {
VarZeroVecOwned::<str>::new().remove(0);
}
#[test]
fn test_replace_integrity() {
let mut items: Vec<&str> = vec!["apples", "bananas", "eeples", "", "baneenees", "five", ""];
let mut zerovec = VarZeroVecOwned::<str>::try_from_elements(&items).unwrap();
items[0] = "blablah";
zerovec.replace(0, "blablah");
assert_eq!(zerovec, &*items);
items[1] = "twily";
zerovec.replace(1, "twily");
assert_eq!(zerovec, &*items);
items[3] = "aoeuidhtns";
zerovec.replace(3, "aoeuidhtns");
assert_eq!(zerovec, &*items);
items[6] = "0123456789";
zerovec.replace(6, "0123456789");
assert_eq!(zerovec, &*items);
items[2] = "";
zerovec.replace(2, "");
assert_eq!(zerovec, &*items);
}
#[test]
#[should_panic]
fn test_replace_past_end() {
VarZeroVecOwned::<str>::new().replace(0, "");
}
}