loro_delta/
array_vec.rs

1use std::fmt::Debug;
2use std::ops::{Deref, DerefMut};
3
4use generic_btree::rle::{HasLength, Mergeable, Sliceable, TryInsert};
5use heapless::Vec;
6
7use crate::delta_trait::{DeltaAttr, DeltaValue};
8use crate::{DeltaRope, DeltaRopeBuilder};
9
10#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
11#[repr(transparent)]
12pub struct ArrayVec<V, const C: usize> {
13    vec: Vec<V, C>,
14}
15
16impl<V, const C: usize> ArrayVec<V, C> {
17    pub fn new() -> Self {
18        Self { vec: Vec::new() }
19    }
20
21    pub fn insert_many(&mut self, pos: usize, values: Self) -> Result<(), Self> {
22        let self_len = self.len();
23        let values_len = values.len();
24        let Some(new_len) = self_len.checked_add(values_len) else {
25            return Err(values);
26        };
27
28        if pos > self_len || C < new_len {
29            return Err(values);
30        }
31
32        // SAFETY: We have the ownership of the values
33        unsafe {
34            let ptr_start = self.vec.as_mut_ptr().add(pos);
35            ptr_start.copy_to(ptr_start.add(values_len), self_len - pos);
36            ptr_start.copy_from_nonoverlapping(values.as_ptr(), values_len);
37            self.vec.set_len(new_len);
38        }
39
40        // This will not cause memory leak because the vec is on the stack
41        // And we already take the ownership of the elements inside the vec
42        std::mem::forget(values.vec);
43        Ok(())
44    }
45
46    pub fn from_many(mut iter: impl Iterator<Item = V>) -> impl Iterator<Item = Self> {
47        let mut new = Self::new();
48        std::iter::from_fn(move || {
49            let mut v = iter.next();
50            while let Some(iv) = v {
51                if new.vec.push(iv).is_err() {
52                    unreachable!()
53                }
54
55                if new.vec.is_full() {
56                    break;
57                }
58
59                v = iter.next();
60            }
61
62            if new.is_empty() {
63                return None;
64            }
65
66            Some(std::mem::take(&mut new))
67        })
68    }
69
70    // The type system doesn't allow us to use unexported types in trait's associated types
71    // So we don't impl the trait for this
72    #[allow(clippy::should_implement_trait)]
73    pub fn into_iter(self) -> impl Iterator<Item = V> {
74        self.vec.into_iter()
75    }
76}
77
78impl<V: Debug + Clone, const C: usize, Attr: DeltaAttr> DeltaRope<ArrayVec<V, C>, Attr> {
79    pub fn from_many(iter: impl Iterator<Item = V>) -> Self {
80        let mut rope = DeltaRope::new();
81        rope.insert_values(
82            0,
83            ArrayVec::from_many(iter).map(|x| crate::DeltaItem::Replace {
84                value: x,
85                attr: Default::default(),
86                delete: 0,
87            }),
88        );
89
90        rope
91    }
92}
93
94impl<V: Debug + Clone, Attr: DeltaAttr, const C: usize> DeltaRopeBuilder<ArrayVec<V, C>, Attr> {
95    pub fn insert_many(mut self, value_iter: impl IntoIterator<Item = V>, attr: Attr) -> Self {
96        let iter = ArrayVec::from_many(value_iter.into_iter());
97        for value in iter {
98            self = self.insert(value, attr.clone());
99        }
100        self
101    }
102}
103
104impl<V, const C: usize> Default for ArrayVec<V, C> {
105    fn default() -> Self {
106        Self::new()
107    }
108}
109
110impl<V, const C: usize> Deref for ArrayVec<V, C> {
111    type Target = Vec<V, C>;
112
113    fn deref(&self) -> &Self::Target {
114        &self.vec
115    }
116}
117
118impl<V, const C: usize> DerefMut for ArrayVec<V, C> {
119    fn deref_mut(&mut self) -> &mut Self::Target {
120        &mut self.vec
121    }
122}
123
124impl<const C: usize, T> HasLength for ArrayVec<T, C> {
125    fn rle_len(&self) -> usize {
126        self.len()
127    }
128}
129
130impl<const C: usize, T: Clone> Sliceable for ArrayVec<T, C> {
131    fn _slice(&self, range: std::ops::Range<usize>) -> Self {
132        Self {
133            vec: Vec::from_slice(&self.vec.as_slice()[range]).unwrap(),
134        }
135    }
136
137    fn split(&mut self, pos: usize) -> Self {
138        let right = self.slice(pos..);
139        self.vec.truncate(pos);
140        right
141    }
142}
143
144impl<const C: usize, T: Clone> Mergeable for ArrayVec<T, C> {
145    fn can_merge(&self, rhs: &Self) -> bool {
146        C >= self.len() + rhs.len()
147    }
148
149    fn merge_right(&mut self, rhs: &Self) {
150        self.extend_from_slice(rhs.as_slice()).unwrap();
151    }
152
153    fn merge_left(&mut self, left: &Self) {
154        match self.insert_many(0, left.clone()) {
155            Ok(_) => {}
156            Err(_) => unreachable!(),
157        }
158    }
159}
160
161impl<const C: usize, T> TryInsert for ArrayVec<T, C> {
162    fn try_insert(&mut self, pos: usize, elem: Self) -> Result<(), Self>
163    where
164        Self: Sized,
165    {
166        self.insert_many(pos, elem)
167    }
168}
169
170impl<const C: usize, T> DeltaValue for ArrayVec<T, C> where T: Clone + Debug {}
171
172impl<T, const A: usize, const C: usize> From<[T; A]> for ArrayVec<T, C>
173where
174    T: Clone,
175{
176    fn from(array: [T; A]) -> Self {
177        let vec = Vec::from_slice(&array).unwrap();
178        ArrayVec { vec }
179    }
180}
181
182#[cfg(test)]
183mod test {
184    use std::sync::Arc;
185
186    use super::*;
187
188    #[test]
189    fn test_insert() {
190        let mut array_vec: ArrayVec<Arc<i32>, 8> =
191            ArrayVec::from([Arc::new(1), Arc::new(2), Arc::new(3)]);
192        let b = ArrayVec::from([Arc::new(1), Arc::new(2), Arc::new(3)]);
193        array_vec.insert_many(1, b).unwrap();
194    }
195
196    #[cfg(miri)]
197    #[test]
198    fn miri_insert_many_rejects_out_of_bounds_position_before_pointer_arithmetic() {
199        let mut array_vec: ArrayVec<i32, 8> = ArrayVec::from([1, 2, 3]);
200        let values = ArrayVec::from([4]);
201
202        assert!(array_vec.insert_many(usize::MAX, values).is_err());
203        assert_eq!(array_vec.as_slice(), &[1, 2, 3]);
204    }
205
206    #[test]
207    fn test_slice() {
208        let array_vec: ArrayVec<i32, 5> = ArrayVec::from([1, 2, 3, 4, 5]);
209        let sliced = array_vec._slice(1..3);
210        assert_eq!(sliced.as_slice(), &[2, 3]);
211    }
212
213    #[test]
214    fn test_split() {
215        let mut array_vec: ArrayVec<i32, 5> = ArrayVec::from([1, 2, 3, 4, 5]);
216        let right = array_vec.split(2);
217        assert_eq!(array_vec.as_slice(), &[1, 2]);
218        assert_eq!(right.as_slice(), &[3, 4, 5]);
219    }
220
221    #[test]
222    fn test_can_merge() {
223        let array_vec1: ArrayVec<i32, 10> = ArrayVec::from([1, 2, 3]);
224        let array_vec2: ArrayVec<i32, 10> = ArrayVec::from([4, 5, 6]);
225        assert!(array_vec1.can_merge(&array_vec2));
226    }
227
228    #[test]
229    fn test_merge_right() {
230        let mut array_vec1: ArrayVec<i32, 10> = ArrayVec::from([1, 2, 3]);
231        let array_vec2: ArrayVec<i32, 10> = ArrayVec::from([4, 5, 6]);
232        array_vec1.merge_right(&array_vec2);
233        assert_eq!(array_vec1.as_slice(), &[1, 2, 3, 4, 5, 6]);
234    }
235
236    #[test]
237    fn test_merge_left() {
238        let mut array_vec1: ArrayVec<i32, 10> = ArrayVec::from([4, 5, 6]);
239        let array_vec2: ArrayVec<i32, 10> = ArrayVec::from([1, 2, 3]);
240        array_vec1.merge_left(&array_vec2);
241        assert_eq!(array_vec1.as_slice(), &[1, 2, 3, 4, 5, 6]);
242    }
243
244    #[test]
245    fn test_try_insert() {
246        let mut array_vec: ArrayVec<i32, 10> = ArrayVec::from([1, 2, 5]);
247        let result = array_vec.try_insert(2, ArrayVec::from([3, 4]));
248        assert!(result.is_ok());
249        assert_eq!(array_vec.as_slice(), &[1, 2, 3, 4, 5]);
250    }
251
252    #[test]
253    fn test_merge_fail() {
254        let array_vec1: ArrayVec<i32, 5> = ArrayVec::from([1, 2, 3, 4, 5]);
255        let array_vec2: ArrayVec<i32, 5> = ArrayVec::from([6, 7, 8]);
256        let result = array_vec1.can_merge(&array_vec2);
257        assert!(!result);
258    }
259
260    #[test]
261    fn test_try_insert_fail() {
262        let mut array_vec: ArrayVec<i32, 5> = ArrayVec::from([1, 2, 4, 5, 6]);
263        let result = array_vec.try_insert(2, ArrayVec::from([3]));
264        assert!(result.is_err());
265    }
266
267    #[test]
268    fn test_insert_many_fail() {
269        let mut array_vec: ArrayVec<i32, 5> = ArrayVec::from([1, 2, 3]);
270        let result = array_vec.insert_many(1, ArrayVec::from([4, 5, 6]));
271        assert!(result.is_err());
272    }
273
274    #[test]
275    #[should_panic]
276    fn merge_right_overflow() {
277        let mut array_vec: ArrayVec<i32, 5> = ArrayVec::from([1, 2, 3]);
278        array_vec.merge_right(&ArrayVec::from([4, 5, 6]));
279    }
280}
loro_delta/array_vec.rs

loro_delta/
array_vec.rs
