1use crate::{Counter, OpID};
2use append_only_bytes::BytesSlice;
3use core::fmt;
4
5use generic_btree::rle::{HasLength, Mergeable, Sliceable};
6use smallvec::SmallVec;
7use std::{
8 ops::{Deref, DerefMut},
9 str::Chars,
10};
11
12use self::{rich_tree_btree_impl::RichTreeTrait, utf16::get_utf16_len};
13
14use super::ann::{AnchorSetDiff, CacheAnchorSet, ElemAnchorSet};
15
16pub(crate) mod query;
17pub(crate) mod rich_tree_btree_impl;
18pub mod utf16;
19
20type AnnIdx = i32;
21#[derive(Clone)]
22pub struct Elem {
23 inner: Box<ElemInner>,
24}
25
26#[derive(Clone)]
27pub struct ElemInner {
28 pub id: OpID,
29 pub left: Option<OpID>,
30 pub right: Option<OpID>,
31 pub string: BytesSlice,
32 pub utf16_len: u32,
33 pub status: Status,
34 pub anchor_set: ElemAnchorSet,
35}
36
37impl Deref for Elem {
38 type Target = ElemInner;
39
40 fn deref(&self) -> &Self::Target {
41 &self.inner
42 }
43}
44
45impl DerefMut for Elem {
46 fn deref_mut(&mut self) -> &mut Self::Target {
47 &mut self.inner
48 }
49}
50
51#[test]
52fn size() {
53 assert_eq!(std::mem::size_of::<Elem>(), 96);
54}
55
56impl std::fmt::Debug for Elem {
57 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
58 f.debug_struct("Elem")
59 .field("id", &self.id)
60 .field("left", &self.left)
61 .field("right", &self.right)
62 .field("string", &std::str::from_utf8(&self.string))
63 .field("utf16_len", &self.utf16_len)
64 .field("status", &self.status)
65 .field("anchor_set", &self.anchor_set)
66 .finish()
67 }
68}
69
70impl Elem {
71 pub fn new(id: OpID, left: Option<OpID>, right: Option<OpID>, string: BytesSlice) -> Self {
72 Elem {
73 inner: Box::new(ElemInner {
74 id,
75 left,
76 right,
77 utf16_len: get_utf16_len(&string),
78 string,
79 status: Status::ALIVE,
80 anchor_set: Default::default(),
81 }),
82 }
83 }
84
85 pub fn id_last(&self) -> OpID {
86 OpID {
87 client: self.id.client,
88 counter: self.id.counter + self.atom_len() as Counter - 1,
89 }
90 }
91
92 #[inline(always)]
93 pub fn content_len(&self) -> usize {
94 if self.status.is_dead() {
95 0
96 } else {
97 self.string.len()
98 }
99 }
100
101 #[inline(always)]
102 pub fn atom_len(&self) -> usize {
103 self.string.len()
104 }
105
106 #[inline(always)]
107 pub fn is_dead(&self) -> bool {
108 self.status.is_dead()
109 }
110
111 pub fn split(&mut self, offset: usize) -> Self {
112 assert!(offset != 0);
113 let start = offset;
114 let s = self.string.slice_clone(offset..);
115 let utf16_len = get_utf16_len(&s);
116 let right = Self {
117 inner: Box::new(ElemInner {
118 anchor_set: self.anchor_set.split(),
119 id: self.id.inc(start as Counter),
120 left: Some(self.id.inc(start as Counter - 1)),
121 right: self.right,
122 string: s,
123 utf16_len,
124 status: self.status,
125 }),
126 };
127 self.utf16_len -= utf16_len;
128 self.string = self.string.slice_clone(..offset);
129 right
130 }
131
132 #[inline(always)]
133 pub fn local_delete(&mut self) -> bool {
134 if !self.is_dead() {
135 self.status.deleted_times += 1;
136 true
137 } else {
138 false
139 }
140 }
141
142 #[inline(always)]
143 pub fn apply_remote_delete(&mut self) {
144 self.status.deleted_times += 1;
145 }
146
147 #[must_use]
148 pub fn update<R>(
149 &mut self,
150 start: usize,
151 end: usize,
152 f: &mut dyn FnMut(&mut Elem) -> R,
153 ) -> (SmallVec<[Elem; 2]>, Option<R>) {
154 let mut ans = SmallVec::new();
155 debug_assert!(start <= end && end <= self.rle_len());
156 if start == end {
157 return (ans, None);
158 }
159
160 assert!(end > start);
161 if start == 0 && end == self.atom_len() {
162 let r = f(self);
163 return (ans, Some(r));
164 }
165 if start == 0 {
166 let right = self.split(end);
167 let r = f(self);
168 ans.push(right);
169 return (ans, Some(r));
170 }
171 if end == self.atom_len() {
172 let mut right = self.split(start);
173 let r = f(&mut right);
174 ans.push(right);
175 return (ans, Some(r));
176 }
177
178 let mut middle = self.split(start);
179 let right = middle.split(end - start);
180 let r = f(&mut middle);
181 ans.push(middle);
182 ans.push(right);
183 (ans, Some(r))
184 }
185
186 #[must_use]
187 pub fn update_twice(
188 &mut self,
189 f_start: usize,
190 f_end_g_start: usize,
191 g_end: usize,
192 f: &mut dyn FnMut(&mut Elem),
193 g: &mut dyn FnMut(&mut Elem),
194 ) -> SmallVec<[Elem; 4]> {
195 let mut ans = SmallVec::new();
196 debug_assert!(f_start < f_end_g_start && f_end_g_start < g_end);
197 debug_assert!(g_end <= self.rle_len());
198 if f_start == 0 && g_end == self.atom_len() {
199 let new = self.split(f_end_g_start);
200 ans.push(new);
201 f(self);
202 g(&mut ans[0]);
203 return ans;
204 }
205
206 if f_start == 0 {
207 let mut middle = self.split(f_end_g_start);
208 let mut new_elems = middle.update(0, g_end - f_end_g_start, g);
209 ans.push(middle);
210 ans.append(&mut new_elems.0);
211 f(self);
212 return ans;
213 }
214
215 if g_end == self.atom_len() {
216 let mut middle = self.split(f_start);
217 let mut new_elems = middle.update(0, f_end_g_start - f_start, f);
218 ans.push(middle);
219 ans.append(&mut new_elems.0);
220 g(ans.last_mut().unwrap());
221 return ans;
222 }
223
224 let len = self.atom_len();
225 let mut left = self.split(f_start);
226 let mut middle0 = left.split(f_end_g_start - f_start);
227 let mut middle1 = middle0.split(g_end - f_end_g_start);
228 let right = middle1.split(len - g_end);
229 f(&mut middle0);
230 g(&mut middle1);
231 ans.push(left);
232 ans.push(middle0);
233 ans.push(middle1);
234 ans.push(right);
235 ans
236 }
237
238 pub fn merge_slice(&mut self, s: &BytesSlice) {
239 self.string.try_merge(s).unwrap();
240 self.utf16_len += get_utf16_len(s);
241 }
242
243 pub fn contains_id(&self, id: OpID) -> bool {
244 id.client == self.id.client
245 && self.id.counter <= id.counter
246 && self.id.counter + self.rle_len() as Counter > id.counter
247 }
248
249 pub fn overlap(&self, id: OpID, len: usize) -> bool {
250 id.client == self.id.client
251 && self.id.counter < id.counter + len as Counter
252 && self.id.counter + self.rle_len() as Counter > id.counter as Counter
253 }
254
255 pub fn try_merge_arr(arr: &mut Vec<Self>, mut from: usize, mut len: usize) -> bool {
256 len = len.min(arr.len() - from);
257 while len > 0 {
258 let mut j = from + 1;
259 while j < arr.len() {
260 let (left, right) = arr.split_at_mut(j);
261 if left[from].can_merge(&right[0]) {
262 left[from].merge_right(&right[0]);
263 j += 1;
264 } else {
265 break;
266 }
267 }
268 if j > from + 1 {
269 arr.drain(from + 1..j);
270 len = len.saturating_sub(j - from);
272 from += 1;
273 } else {
274 len -= 1;
275 from += 1;
276 }
277 }
278
279 false
280 }
281
282 #[inline]
283 pub fn has_after_anchor(&self) -> bool {
284 self.anchor_set.has_after_anchor()
285 }
286
287 #[inline]
288 #[allow(unused)]
289 pub fn has_before_anchor(&self) -> bool {
290 self.anchor_set.has_before_anchor()
291 }
292}
293
294impl Mergeable for Elem {
295 fn can_merge(&self, rhs: &Self) -> bool {
296 self.id.client == rhs.id.client
297 && self.id.counter + self.atom_len() as Counter == rhs.id.counter
298 && rhs.left == Some(self.id_last())
299 && self.right == rhs.right
300 && self.status == rhs.status
301 && self.string.can_merge(&rhs.string)
302 && self.anchor_set.can_merge(&rhs.anchor_set)
303 }
304
305 fn merge_right(&mut self, rhs: &Self) {
306 self.string.try_merge(&rhs.string).unwrap();
307 self.utf16_len += rhs.utf16_len;
308 self.anchor_set.merge_right(&rhs.anchor_set);
309 }
310
311 fn merge_left(&mut self, lhs: &Self) {
312 self.id = lhs.id;
313 self.left = lhs.left;
314 let mut string = lhs.string.clone();
315 string.try_merge(&self.string).unwrap();
316 self.string = string;
317 self.utf16_len += lhs.utf16_len;
318 self.anchor_set.merge_left(&lhs.anchor_set);
319 }
320}
321
322impl HasLength for Elem {
323 fn rle_len(&self) -> usize {
324 self.atom_len()
325 }
326}
327
328impl Sliceable for Elem {
329 fn slice(&self, range: impl std::ops::RangeBounds<usize>) -> Self {
330 let start = match range.start_bound() {
331 std::ops::Bound::Included(x) => *x,
332 std::ops::Bound::Excluded(x) => *x + 1,
333 std::ops::Bound::Unbounded => 0,
334 };
335 let end = match range.end_bound() {
336 std::ops::Bound::Included(x) => *x + 1,
337 std::ops::Bound::Excluded(x) => *x,
338 std::ops::Bound::Unbounded => self.atom_len(),
339 };
340 let s = self.string.slice_clone(range);
341 let utf16_len = get_utf16_len(&s);
342 Self {
343 inner: Box::new(ElemInner {
344 anchor_set: self.anchor_set.trim(start != 0, end != self.rle_len()),
345 id: self.id.inc(start as Counter),
346 left: if start == 0 {
347 self.left
348 } else {
349 Some(self.id.inc(start as Counter - 1))
350 },
351 right: self.right,
352 string: s,
353 utf16_len,
354 status: self.status,
355 }),
356 }
357 }
358
359 fn slice_(&mut self, range: impl std::ops::RangeBounds<usize>)
360 where
361 Self: Sized,
362 {
363 let start = match range.start_bound() {
364 std::ops::Bound::Included(x) => *x,
365 std::ops::Bound::Excluded(x) => *x + 1,
366 std::ops::Bound::Unbounded => 0,
367 };
368 let end = match range.end_bound() {
369 std::ops::Bound::Included(x) => *x + 1,
370 std::ops::Bound::Excluded(x) => *x,
371 std::ops::Bound::Unbounded => self.atom_len(),
372 };
373 if start == 0 && end == self.atom_len() {
374 return;
375 }
376
377 self.inner
378 .anchor_set
379 .trim_(start != 0, end != self.atom_len());
380 self.id = self.id.inc(start as Counter);
381 self.left = if start == 0 {
382 self.left
383 } else {
384 Some(self.id.inc(start as Counter - 1))
385 };
386 self.string = self.string.slice_clone(range);
387 self.utf16_len = get_utf16_len(&self.string);
388 }
389}
390#[derive(Clone, Copy, Debug, PartialEq, Eq)]
391pub struct Status {
392 pub future: bool,
393 pub deleted_times: u16,
394}
395
396impl Status {
397 pub const ALIVE: Status = Status {
398 future: false,
399 deleted_times: 0,
400 };
401
402 #[allow(unused)]
403 pub fn new() -> Self {
404 Status {
405 future: false,
406 deleted_times: 0,
407 }
408 }
409
410 #[inline(always)]
411 fn is_dead(&self) -> bool {
412 self.future || self.deleted_times > 0
413 }
414}
415
416#[derive(Debug, Clone, PartialEq, Eq, Default)]
417pub(crate) struct Cache {
418 pub len: u32,
419 pub utf16_len: u32,
420 pub anchor_set: CacheAnchorSet,
421}
422
423#[derive(Default, Debug)]
424pub(crate) struct CacheDiff {
425 pub(super) anchor_diff: AnchorSetDiff,
426 pub(super) len_diff: isize,
427 pub(super) utf16_len_diff: isize,
428}
429
430impl Cache {
431 fn apply_diff(&mut self, diff: &CacheDiff) {
432 self.len = (self.len as isize + diff.len_diff) as u32;
433 self.utf16_len = (self.utf16_len as isize + diff.utf16_len_diff) as u32;
434 self.anchor_set.apply_diff(&diff.anchor_diff);
435 }
436}
437
438impl CacheDiff {
439 pub fn new_len_diff(diff: isize, utf16_len_diff: isize) -> CacheDiff {
440 CacheDiff {
441 len_diff: diff,
442 utf16_len_diff,
443 anchor_diff: Default::default(),
444 }
445 }
446}