1#![allow(clippy::unwrap_used)]
7#![allow(clippy::expect_used)]
8#![allow(clippy::indexing_slicing)]
9#![allow(clippy::panic)]
10
11use super::*;
12use crate::ule::*;
13use alloc::vec::Vec;
14use core::any;
15use core::convert::TryInto;
16use core::marker::PhantomData;
17use core::ops::Deref;
18use core::ops::Range;
19use core::{fmt, ptr, slice};
20
21use super::components::IntegerULE;
22
23pub struct VarZeroVecOwned<T: ?Sized, F = Index16> {
32 marker1: PhantomData<T>,
33 marker2: PhantomData<F>,
34 entire_slice: Vec<u8>,
36}
37
38impl<T: ?Sized, F> Clone for VarZeroVecOwned<T, F> {
39 fn clone(&self) -> Self {
40 VarZeroVecOwned {
41 marker1: PhantomData,
42 marker2: PhantomData,
43 entire_slice: self.entire_slice.clone(),
44 }
45 }
46}
47
48#[derive(PartialEq)]
50enum ShiftType {
51 Insert,
52 Replace,
53 Remove,
54}
55
56impl<T: VarULE + ?Sized, F: VarZeroVecFormat> Deref for VarZeroVecOwned<T, F> {
57 type Target = VarZeroSlice<T, F>;
58 fn deref(&self) -> &VarZeroSlice<T, F> {
59 self.as_slice()
60 }
61}
62
63impl<T: VarULE + ?Sized, F> VarZeroVecOwned<T, F> {
64 pub fn new() -> Self {
66 Self {
67 marker1: PhantomData,
68 marker2: PhantomData,
69 entire_slice: Vec::new(),
70 }
71 }
72}
73
74impl<T: VarULE + ?Sized, F: VarZeroVecFormat> VarZeroVecOwned<T, F> {
75 pub fn from_slice(slice: &VarZeroSlice<T, F>) -> Self {
77 Self {
78 marker1: PhantomData,
79 marker2: PhantomData,
80 entire_slice: slice.as_bytes().into(),
81 }
82 }
83
84 pub fn try_from_elements<A>(elements: &[A]) -> Result<Self, &'static str>
86 where
87 A: EncodeAsVarULE<T>,
88 {
89 Ok(if elements.is_empty() {
90 Self::from_slice(VarZeroSlice::new_empty())
91 } else {
92 Self {
93 marker1: PhantomData,
94 marker2: PhantomData,
95 entire_slice: components::get_serializable_bytes_non_empty::<T, A, F>(elements)
97 .ok_or(F::Index::TOO_LARGE_ERROR)?,
98 }
99 })
100 }
101
102 pub fn as_slice(&self) -> &VarZeroSlice<T, F> {
104 let slice: &[u8] = &self.entire_slice;
105 unsafe {
106 VarZeroSlice::from_bytes_unchecked(slice)
108 }
109 }
110
111 pub(crate) fn with_capacity(capacity: usize) -> Self {
115 Self {
116 marker1: PhantomData,
117 marker2: PhantomData,
118 entire_slice: Vec::with_capacity(capacity * (F::Index::SIZE + 4)),
119 }
120 }
121
122 pub(crate) fn reserve(&mut self, capacity: usize) {
126 self.entire_slice.reserve(capacity * (F::Index::SIZE + 4))
127 }
128
129 unsafe fn element_position_unchecked(&self, idx: usize) -> usize {
136 let len = self.len();
137 if len == 0 {
138 return 0;
139 }
140 let out = if idx == len {
141 let indices_size = F::Index::SIZE
142 .checked_mul(len - 1)
143 .expect(F::Index::TOO_LARGE_ERROR);
144 self.entire_slice.len() - F::Len::SIZE - indices_size
145 } else if let Some(idx) = self.index_data(idx) {
146 idx.iule_to_usize()
147 } else {
148 0
149 };
150 let indices_size = F::Index::SIZE
151 .checked_mul(len - 1)
152 .expect(F::Index::TOO_LARGE_ERROR);
153 debug_assert!(out + F::Len::SIZE + indices_size <= self.entire_slice.len());
154 out
155 }
156
157 unsafe fn element_range_unchecked(&self, idx: usize) -> Range<usize> {
162 let start = self.element_position_unchecked(idx);
163 let end = self.element_position_unchecked(idx + 1);
164 debug_assert!(start <= end, "{start} > {end}");
165 start..end
166 }
167
168 unsafe fn set_len(&mut self, len: usize) {
173 assert!(len <= F::Len::MAX_VALUE as usize);
174 let len_bytes = len.to_le_bytes();
175 let len_ule = F::Len::iule_from_usize(len).expect(F::Len::TOO_LARGE_ERROR);
176 self.entire_slice[0..F::Len::SIZE].copy_from_slice(ULE::slice_as_bytes(&[len_ule]));
177 assert_eq!(len_bytes[F::Len::SIZE..].iter().sum::<u8>(), 0);
179 }
180
181 fn index_range(index: usize) -> Option<Range<usize>> {
184 let index_minus_one = index.checked_sub(1)?;
185 let pos = F::Len::SIZE
186 + F::Index::SIZE
187 .checked_mul(index_minus_one)
188 .expect(F::Index::TOO_LARGE_ERROR);
189 Some(pos..pos + F::Index::SIZE)
190 }
191
192 unsafe fn index_data(&self, index: usize) -> Option<&F::Index> {
197 let index_range = Self::index_range(index)?;
198 Some(&F::Index::slice_from_bytes_unchecked(&self.entire_slice[index_range])[0])
199 }
200
201 unsafe fn index_data_mut(&mut self, index: usize) -> Option<&mut F::Index> {
207 let ptr = self.entire_slice.as_mut_ptr();
208 let range = Self::index_range(index)?;
209
210 let data = slice::from_raw_parts_mut(ptr.add(range.start), F::Index::SIZE);
214 Some(&mut F::Index::iule_from_bytes_unchecked_mut(data)[0])
215 }
216
217 unsafe fn shift_indices(&mut self, starting_index: usize, amount: i32) {
226 let normalized_idx = starting_index
227 .checked_sub(1)
228 .expect("shift_indices called with a 0 starting index");
229 let len = self.len();
230 let indices_size = F::Index::SIZE
231 .checked_mul(len - 1)
232 .expect(F::Index::TOO_LARGE_ERROR);
233 let indices = F::Index::iule_from_bytes_unchecked_mut(
234 &mut self.entire_slice[F::Len::SIZE..F::Len::SIZE + indices_size],
235 );
236 for idx in &mut indices[normalized_idx..] {
237 let mut new_idx = idx.iule_to_usize();
238 if amount > 0 {
239 new_idx = new_idx.checked_add(amount.try_into().unwrap()).unwrap();
240 } else {
241 new_idx = new_idx.checked_sub((-amount).try_into().unwrap()).unwrap();
242 }
243 *idx = F::Index::iule_from_usize(new_idx).expect(F::Index::TOO_LARGE_ERROR);
244 }
245 }
246
247 pub fn as_varzerovec<'a>(&'a self) -> VarZeroVec<'a, T, F> {
252 self.as_slice().into()
253 }
254
255 pub fn clear(&mut self) {
257 self.entire_slice.clear()
258 }
259
260 #[inline]
262 pub fn into_bytes(self) -> Vec<u8> {
263 self.entire_slice
264 }
265
266 unsafe fn shift(&mut self, index: usize, new_size: usize, shift_type: ShiftType) -> &mut [u8] {
277 let len = self.len();
286 let slice_len = self.entire_slice.len();
287
288 let prev_element = match shift_type {
289 ShiftType::Insert => {
290 let pos = self.element_position_unchecked(index);
291 pos..pos
294 }
295 _ => self.element_range_unchecked(index),
296 };
297
298 let index_shift: i64 = match shift_type {
300 ShiftType::Insert => F::Index::SIZE as i64,
301 ShiftType::Replace => 0,
302 ShiftType::Remove => -(F::Index::SIZE as i64),
303 };
304 let shift: i64 =
306 new_size as i64 - (prev_element.end - prev_element.start) as i64 + index_shift;
307 let new_slice_len = slice_len.wrapping_add(shift as usize);
308 if shift > 0 {
309 if new_slice_len > F::Index::MAX_VALUE as usize {
310 panic!(
311 "Attempted to grow VarZeroVec to an encoded size that does not fit within the length size used by {}",
312 any::type_name::<F>()
313 );
314 }
315 self.entire_slice.resize(new_slice_len, 0);
316 }
317
318 {
320 let slice_range = self.entire_slice.as_mut_ptr_range();
323 let indices_start = slice_range.start.add(F::Len::SIZE);
325 let old_slice_end = slice_range.start.add(slice_len);
326 let indices_size = F::Index::SIZE
327 .checked_mul(len - 1)
328 .expect(F::Index::TOO_LARGE_ERROR);
329 let data_start = indices_start.add(indices_size);
330 let prev_element_p =
331 data_start.add(prev_element.start)..data_start.add(prev_element.end);
332
333 let index_range = if let Some(index_minus_one) = index.checked_sub(1) {
339 let index_offset = F::Index::SIZE
340 .checked_mul(index_minus_one)
341 .expect(F::Index::TOO_LARGE_ERROR);
342 let index_start = indices_start.add(index_offset);
343 Some(index_start..index_start.add(F::Index::SIZE))
344 } else {
345 None
346 };
347
348 unsafe fn shift_bytes(block: Range<*const u8>, to: *mut u8) {
349 debug_assert!(block.end >= block.start);
350 ptr::copy(block.start, to, block.end.offset_from(block.start) as usize);
351 }
352
353 if shift_type == ShiftType::Remove {
354 if let Some(ref index_range) = index_range {
355 shift_bytes(index_range.end..prev_element_p.start, index_range.start);
356 } else {
357 shift_bytes(
360 indices_start.add(F::Index::SIZE)..prev_element_p.start,
361 indices_start,
362 )
363 }
364 }
365
366 shift_bytes(
368 prev_element_p.end..old_slice_end,
369 prev_element_p
370 .start
371 .offset((new_size as i64 + index_shift) as isize),
372 );
373
374 let first_affected_index = match shift_type {
375 ShiftType::Insert => {
376 if let Some(index_range) = index_range {
377 shift_bytes(index_range.start..prev_element_p.start, index_range.end);
379 let index_data = self
380 .index_data_mut(index)
381 .expect("If index_range is some, index is > 0 and should not panic in index_data_mut");
382 *index_data = F::Index::iule_from_usize(prev_element.start)
383 .expect(F::Index::TOO_LARGE_ERROR);
384 } else {
385 shift_bytes(
389 indices_start..prev_element_p.start,
390 indices_start.add(F::Index::SIZE),
391 );
392 let index_data = self
394 .index_data_mut(1)
395 .expect("Should be able to write to index 1");
396 *index_data = F::Index::iule_from_usize(0).expect("0 is always valid!");
397 }
398
399 self.set_len(len + 1);
400 index + 1
401 }
402 ShiftType::Remove => {
403 self.set_len(len - 1);
404 if index == 0 {
405 index + 1
407 } else {
408 index
409 }
410 }
411 ShiftType::Replace => index + 1,
412 };
413 self.entire_slice.set_len(new_slice_len);
417 self.shift_indices(first_affected_index, (shift - index_shift) as i32);
419 };
420
421 debug_assert!(self.verify_integrity());
422
423 let indices_size = F::Index::SIZE
425 .checked_mul(self.len() - 1)
426 .expect(F::Index::TOO_LARGE_ERROR);
427 let element_pos = F::Len::SIZE + indices_size + self.element_position_unchecked(index);
428 &mut self.entire_slice[element_pos..element_pos + new_size]
429 }
430
431 fn verify_integrity(&self) -> bool {
437 if self.is_empty() {
438 if self.entire_slice.is_empty() {
439 return true;
440 } else {
441 panic!(
442 "VarZeroVecOwned integrity: Found empty VarZeroVecOwned with a nonempty slice"
443 );
444 }
445 }
446 let len = unsafe {
447 <F::Len as ULE>::slice_from_bytes_unchecked(&self.entire_slice[..F::Len::SIZE])[0]
448 .iule_to_usize()
449 };
450 if len == 0 {
451 panic!("VarZeroVecOwned integrity: Found empty VarZeroVecOwned with a nonempty slice");
453 }
454 let indices_size = F::Index::SIZE
455 .checked_mul(len - 1)
456 .expect(F::Index::TOO_LARGE_ERROR);
457 if self.entire_slice.len() < F::Len::SIZE + indices_size {
458 panic!("VarZeroVecOwned integrity: Not enough room for the indices");
459 }
460 let data_len = self.entire_slice.len() - F::Len::SIZE - indices_size;
461 if data_len > F::Index::MAX_VALUE as usize {
462 panic!("VarZeroVecOwned integrity: Data segment is too long");
463 }
464
465 let indices = unsafe {
467 F::Index::slice_from_bytes_unchecked(
468 &self.entire_slice[F::Len::SIZE..F::Len::SIZE + indices_size],
469 )
470 };
471 for idx in indices {
472 if idx.iule_to_usize() > data_len {
473 panic!("VarZeroVecOwned integrity: Indices must not point past the data segment");
474 }
475 }
476 for window in indices.windows(2) {
477 if window[0].iule_to_usize() > window[1].iule_to_usize() {
478 panic!("VarZeroVecOwned integrity: Indices must be in non-decreasing order");
479 }
480 }
481 true
482 }
483
484 pub fn push<A: EncodeAsVarULE<T> + ?Sized>(&mut self, element: &A) {
486 self.insert(self.len(), element)
487 }
488
489 pub fn insert<A: EncodeAsVarULE<T> + ?Sized>(&mut self, index: usize, element: &A) {
491 let len = self.len();
492 if index > len {
493 panic!("Called out-of-bounds insert() on VarZeroVec, index {index} len {len}");
494 }
495
496 let value_len = element.encode_var_ule_len();
497 assert!(value_len < F::Index::MAX_VALUE as usize);
498
499 if len == 0 {
500 let header_len = F::Len::SIZE; let cap = header_len + value_len;
502 let guard = ClearOnPanic(self);
503 guard.0.entire_slice.resize(cap, 0);
504 guard.0.entire_slice[0] = 1; element.encode_var_ule_write(&mut guard.0.entire_slice[header_len..]);
506 debug_assert_eq!(
507 T::validate_bytes(&guard.0.entire_slice[header_len..]),
508 Ok(())
509 );
510 core::mem::forget(guard);
511 return;
512 }
513
514 let guard = ClearOnPanic(self);
515 unsafe {
522 let place = guard.0.shift(index, value_len, ShiftType::Insert);
523 element.encode_var_ule_write(place);
524 debug_assert_eq!(T::validate_bytes(place), Ok(()));
525 }
526 core::mem::forget(guard);
527 }
528
529 pub fn remove(&mut self, index: usize) {
531 let len = self.len();
532 if index >= len {
533 panic!("Called out-of-bounds remove() on VarZeroVec, index {index} len {len}");
534 }
535 if len == 1 {
536 self.entire_slice.clear();
538 return;
539 }
540 let guard = ClearOnPanic(self);
541 unsafe {
546 guard.0.shift(index, 0, ShiftType::Remove);
547 }
548 core::mem::forget(guard);
549 }
550
551 pub fn replace<A: EncodeAsVarULE<T> + ?Sized>(&mut self, index: usize, element: &A) {
553 let len = self.len();
554 if index >= len {
555 panic!("Called out-of-bounds replace() on VarZeroVec, index {index} len {len}");
556 }
557
558 let value_len = element.encode_var_ule_len();
559
560 assert!(value_len < F::Index::MAX_VALUE as usize);
561 let guard = ClearOnPanic(self);
562 unsafe {
569 let place = guard.0.shift(index, value_len, ShiftType::Replace);
570 element.encode_var_ule_write(place);
571 debug_assert_eq!(T::validate_bytes(place), Ok(()));
572 }
573 core::mem::forget(guard);
574 }
575}
576
577struct ClearOnPanic<'a, T: ?Sized, F>(&'a mut VarZeroVecOwned<T, F>);
581
582impl<T: ?Sized, F> Drop for ClearOnPanic<'_, T, F> {
583 fn drop(&mut self) {
584 self.0.entire_slice.clear();
585 }
586}
587
588impl<T: VarULE + ?Sized, F: VarZeroVecFormat> fmt::Debug for VarZeroVecOwned<T, F>
589where
590 T: fmt::Debug,
591{
592 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
593 VarZeroSlice::fmt(self, f)
594 }
595}
596
597impl<T: VarULE + ?Sized, F> Default for VarZeroVecOwned<T, F> {
598 fn default() -> Self {
599 Self::new()
600 }
601}
602
603impl<T, A, F> PartialEq<&'_ [A]> for VarZeroVecOwned<T, F>
604where
605 T: VarULE + ?Sized,
606 T: PartialEq,
607 A: AsRef<T>,
608 F: VarZeroVecFormat,
609{
610 #[inline]
611 fn eq(&self, other: &&[A]) -> bool {
612 self.iter().eq(other.iter().map(|t| t.as_ref()))
613 }
614}
615
616impl<'a, T: ?Sized + VarULE, F: VarZeroVecFormat> From<&'a VarZeroSlice<T, F>>
617 for VarZeroVecOwned<T, F>
618{
619 fn from(other: &'a VarZeroSlice<T, F>) -> Self {
620 Self::from_slice(other)
621 }
622}
623
624#[cfg(test)]
625mod test {
626 use super::VarZeroVecOwned;
627 #[test]
628 fn test_insert_integrity() {
629 let mut items: Vec<String> = Vec::new();
630 let mut zerovec = VarZeroVecOwned::<str>::new();
631
632 items.insert(0, "1234567890".into());
634 zerovec.insert(0, "1234567890");
635 assert_eq!(zerovec, &*items);
636
637 zerovec.insert(1, "foo3");
638 items.insert(1, "foo3".into());
639 assert_eq!(zerovec, &*items);
640
641 items.insert(items.len(), "qwertyuiop".into());
643 zerovec.insert(zerovec.len(), "qwertyuiop");
644 assert_eq!(zerovec, &*items);
645
646 items.insert(0, "asdfghjkl;".into());
647 zerovec.insert(0, "asdfghjkl;");
648 assert_eq!(zerovec, &*items);
649
650 items.insert(2, "".into());
651 zerovec.insert(2, "");
652 assert_eq!(zerovec, &*items);
653 }
654
655 #[test]
656 fn test_empty_inserts() {
658 let mut items: Vec<String> = Vec::new();
659 let mut zerovec = VarZeroVecOwned::<str>::new();
660
661 items.insert(0, "".into());
663 zerovec.insert(0, "");
664 assert_eq!(zerovec, &*items);
665
666 items.insert(0, "".into());
667 zerovec.insert(0, "");
668 assert_eq!(zerovec, &*items);
669
670 items.insert(0, "1234567890".into());
671 zerovec.insert(0, "1234567890");
672 assert_eq!(zerovec, &*items);
673
674 items.insert(0, "".into());
675 zerovec.insert(0, "");
676 assert_eq!(zerovec, &*items);
677 }
678
679 #[test]
680 fn test_small_insert_integrity() {
681 let mut items: Vec<String> = Vec::new();
684 let mut zerovec = VarZeroVecOwned::<str>::new();
685
686 items.insert(0, "abc".into());
688 zerovec.insert(0, "abc");
689 assert_eq!(zerovec, &*items);
690
691 zerovec.insert(1, "def");
692 items.insert(1, "def".into());
693 assert_eq!(zerovec, &*items);
694 }
695
696 #[test]
697 #[should_panic]
698 fn test_insert_past_end() {
699 VarZeroVecOwned::<str>::new().insert(1, "");
700 }
701
702 #[test]
703 fn test_remove_integrity() {
704 let mut items: Vec<&str> = vec!["apples", "bananas", "eeples", "", "baneenees", "five", ""];
705 let mut zerovec = VarZeroVecOwned::<str>::try_from_elements(&items).unwrap();
706
707 for index in [0, 2, 4, 0, 1, 1, 0] {
708 items.remove(index);
709 zerovec.remove(index);
710 assert_eq!(zerovec, &*items, "index {}, len {}", index, items.len());
711 }
712 }
713
714 #[test]
715 fn test_removing_last_element_clears() {
716 let mut zerovec = VarZeroVecOwned::<str>::try_from_elements(&["buy some apples"]).unwrap();
717 assert!(!zerovec.as_bytes().is_empty());
718 zerovec.remove(0);
719 assert!(zerovec.as_bytes().is_empty());
720 }
721
722 #[test]
723 #[should_panic]
724 fn test_remove_past_end() {
725 VarZeroVecOwned::<str>::new().remove(0);
726 }
727
728 #[test]
729 fn test_replace_integrity() {
730 let mut items: Vec<&str> = vec!["apples", "bananas", "eeples", "", "baneenees", "five", ""];
731 let mut zerovec = VarZeroVecOwned::<str>::try_from_elements(&items).unwrap();
732
733 items[0] = "blablah";
735 zerovec.replace(0, "blablah");
736 assert_eq!(zerovec, &*items);
737
738 items[1] = "twily";
740 zerovec.replace(1, "twily");
741 assert_eq!(zerovec, &*items);
742
743 items[3] = "aoeuidhtns";
745 zerovec.replace(3, "aoeuidhtns");
746 assert_eq!(zerovec, &*items);
747
748 items[6] = "0123456789";
750 zerovec.replace(6, "0123456789");
751 assert_eq!(zerovec, &*items);
752
753 items[2] = "";
755 zerovec.replace(2, "");
756 assert_eq!(zerovec, &*items);
757 }
758
759 #[test]
760 #[should_panic]
761 fn test_replace_past_end() {
762 VarZeroVecOwned::<str>::new().replace(0, "");
763 }
764
765 #[test]
766 #[cfg(feature = "std")]
767 fn test_panic_safety() {
768 use crate::ule::EncodeAsVarULE;
769 use std::panic::{catch_unwind, AssertUnwindSafe};
770
771 struct PanicAfterWrite {
772 invalid: &'static [u8],
773 }
774
775 unsafe impl EncodeAsVarULE<str> for PanicAfterWrite {
778 fn encode_var_ule_as_slices<R>(&self, cb: impl FnOnce(&[&[u8]]) -> R) -> R {
779 cb(&[self.invalid])
780 }
781
782 fn encode_var_ule_len(&self) -> usize {
783 self.invalid.len()
784 }
785
786 fn encode_var_ule_write(&self, dst: &mut [u8]) {
787 dst.copy_from_slice(self.invalid);
788 panic!("encode_var_ule_write panicked after writing invalid bytes");
789 }
790 }
791
792 let panicker = PanicAfterWrite {
793 invalid: &[0x80, 0xC0, 0xFF],
794 };
795
796 let mut v = VarZeroVecOwned::<str>::try_from_elements(&["hello"]).unwrap();
798 let res = catch_unwind(AssertUnwindSafe(|| {
799 v.replace(0, &panicker);
800 }));
801 assert!(res.is_err());
802 assert!(v.is_empty());
803 assert_eq!(v.get(0), None);
804 assert!(v.verify_integrity());
805
806 let mut v = VarZeroVecOwned::<str>::new();
808 let res = catch_unwind(AssertUnwindSafe(|| {
809 v.insert(0, &panicker);
810 }));
811 assert!(res.is_err());
812 assert!(v.is_empty());
813 assert_eq!(v.get(0), None);
814 assert!(v.verify_integrity());
815
816 let mut v = VarZeroVecOwned::<str>::try_from_elements(&["hello", "world"]).unwrap();
818 let res = catch_unwind(AssertUnwindSafe(|| {
819 v.insert(1, &panicker);
820 }));
821 assert!(res.is_err());
822 assert!(v.is_empty());
823 assert_eq!(v.get(0), None);
824 assert!(v.verify_integrity());
825 }
826}