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

loro_delta/
array_vec.rs
