1mod anchor;
2pub mod locator;
3#[cfg(any(test, feature = "test-support"))]
4pub mod network;
5pub mod operation_queue;
6mod patch;
7mod point;
8mod point_utf16;
9#[cfg(any(test, feature = "test-support"))]
10pub mod random_char_iter;
11pub mod rope;
12mod selection;
13pub mod subscription;
14#[cfg(test)]
15mod tests;
16
17pub use anchor::*;
18use anyhow::Result;
19use clock::ReplicaId;
20use collections::{HashMap, HashSet};
21use locator::Locator;
22use operation_queue::OperationQueue;
23pub use patch::Patch;
24pub use point::*;
25pub use point_utf16::*;
26use postage::{barrier, oneshot, prelude::*};
27#[cfg(any(test, feature = "test-support"))]
28pub use random_char_iter::*;
29use rope::TextDimension;
30pub use rope::{Chunks, Rope, TextSummary};
31pub use selection::*;
32use std::{
33 cmp::{self, Ordering},
34 future::Future,
35 iter::Iterator,
36 ops::{self, Deref, Range, Sub},
37 str,
38 sync::Arc,
39 time::{Duration, Instant},
40};
41pub use subscription::*;
42pub use sum_tree::Bias;
43use sum_tree::{FilterCursor, SumTree};
44
45pub type TransactionId = clock::Local;
46
47pub struct Buffer {
48 snapshot: BufferSnapshot,
49 history: History,
50 deferred_ops: OperationQueue<Operation>,
51 deferred_replicas: HashSet<ReplicaId>,
52 replica_id: ReplicaId,
53 local_clock: clock::Local,
54 pub lamport_clock: clock::Lamport,
55 subscriptions: Topic,
56 edit_id_resolvers: HashMap<clock::Local, Vec<oneshot::Sender<()>>>,
57 version_barriers: Vec<(clock::Global, barrier::Sender)>,
58}
59
60#[derive(Clone, Debug)]
61pub struct BufferSnapshot {
62 replica_id: ReplicaId,
63 remote_id: u64,
64 visible_text: Rope,
65 deleted_text: Rope,
66 undo_map: UndoMap,
67 fragments: SumTree<Fragment>,
68 insertions: SumTree<InsertionFragment>,
69 pub version: clock::Global,
70}
71
72#[derive(Clone, Debug)]
73pub struct HistoryEntry {
74 transaction: Transaction,
75 first_edit_at: Instant,
76 last_edit_at: Instant,
77 suppress_grouping: bool,
78}
79
80#[derive(Clone, Debug)]
81pub struct Transaction {
82 pub id: TransactionId,
83 pub edit_ids: Vec<clock::Local>,
84 pub start: clock::Global,
85 pub end: clock::Global,
86 pub ranges: Vec<Range<FullOffset>>,
87}
88
89impl HistoryEntry {
90 pub fn transaction_id(&self) -> TransactionId {
91 self.transaction.id
92 }
93
94 fn push_edit(&mut self, edit_operation: &EditOperation) {
95 self.transaction
96 .edit_ids
97 .push(edit_operation.timestamp.local());
98 self.transaction
99 .end
100 .observe(edit_operation.timestamp.local());
101
102 let mut edits = edit_operation
103 .ranges
104 .iter()
105 .zip(edit_operation.new_text.iter())
106 .peekable();
107 let mut new_ranges = Vec::new();
108 let mut delta = 0;
109
110 for mut self_range in self.transaction.ranges.iter().cloned() {
111 self_range.start += delta;
112 self_range.end += delta;
113
114 while let Some((other_range, new_text)) = edits.peek() {
115 let insertion_len = new_text.len();
116 let mut other_range = (*other_range).clone();
117 other_range.start += delta;
118 other_range.end += delta;
119
120 if other_range.start <= self_range.end {
121 edits.next().unwrap();
122 delta += insertion_len;
123
124 if other_range.end < self_range.start {
125 new_ranges.push(other_range.start..other_range.end + insertion_len);
126 self_range.start += insertion_len;
127 self_range.end += insertion_len;
128 } else {
129 self_range.start = cmp::min(self_range.start, other_range.start);
130 self_range.end = cmp::max(self_range.end, other_range.end) + insertion_len;
131 }
132 } else {
133 break;
134 }
135 }
136
137 new_ranges.push(self_range);
138 }
139
140 for (other_range, new_text) in edits {
141 let insertion_len = new_text.len();
142 new_ranges.push(other_range.start + delta..other_range.end + delta + insertion_len);
143 delta += insertion_len;
144 }
145
146 self.transaction.ranges = new_ranges;
147 }
148}
149
150#[derive(Clone)]
151struct History {
152 // TODO: Turn this into a String or Rope, maybe.
153 base_text: Arc<str>,
154 operations: HashMap<clock::Local, Operation>,
155 undo_stack: Vec<HistoryEntry>,
156 redo_stack: Vec<HistoryEntry>,
157 transaction_depth: usize,
158 group_interval: Duration,
159}
160
161impl History {
162 pub fn new(base_text: Arc<str>) -> Self {
163 Self {
164 base_text,
165 operations: Default::default(),
166 undo_stack: Vec::new(),
167 redo_stack: Vec::new(),
168 transaction_depth: 0,
169 group_interval: Duration::from_millis(300),
170 }
171 }
172
173 fn push(&mut self, op: Operation) {
174 self.operations.insert(op.local_timestamp(), op);
175 }
176
177 fn start_transaction(
178 &mut self,
179 start: clock::Global,
180 now: Instant,
181 local_clock: &mut clock::Local,
182 ) -> Option<TransactionId> {
183 self.transaction_depth += 1;
184 if self.transaction_depth == 1 {
185 let id = local_clock.tick();
186 self.undo_stack.push(HistoryEntry {
187 transaction: Transaction {
188 id,
189 start: start.clone(),
190 end: start,
191 edit_ids: Default::default(),
192 ranges: Default::default(),
193 },
194 first_edit_at: now,
195 last_edit_at: now,
196 suppress_grouping: false,
197 });
198 Some(id)
199 } else {
200 None
201 }
202 }
203
204 fn end_transaction(&mut self, now: Instant) -> Option<&HistoryEntry> {
205 assert_ne!(self.transaction_depth, 0);
206 self.transaction_depth -= 1;
207 if self.transaction_depth == 0 {
208 if self
209 .undo_stack
210 .last()
211 .unwrap()
212 .transaction
213 .ranges
214 .is_empty()
215 {
216 self.undo_stack.pop();
217 None
218 } else {
219 self.redo_stack.clear();
220 let entry = self.undo_stack.last_mut().unwrap();
221 entry.last_edit_at = now;
222 Some(entry)
223 }
224 } else {
225 None
226 }
227 }
228
229 fn group(&mut self) -> Option<TransactionId> {
230 let mut new_len = self.undo_stack.len();
231 let mut entries = self.undo_stack.iter_mut();
232
233 if let Some(mut entry) = entries.next_back() {
234 while let Some(prev_entry) = entries.next_back() {
235 if !prev_entry.suppress_grouping
236 && entry.first_edit_at - prev_entry.last_edit_at <= self.group_interval
237 && entry.transaction.start == prev_entry.transaction.end
238 {
239 entry = prev_entry;
240 new_len -= 1;
241 } else {
242 break;
243 }
244 }
245 }
246
247 let (entries_to_keep, entries_to_merge) = self.undo_stack.split_at_mut(new_len);
248 if let Some(last_entry) = entries_to_keep.last_mut() {
249 for entry in &*entries_to_merge {
250 for edit_id in &entry.transaction.edit_ids {
251 last_entry.push_edit(self.operations[edit_id].as_edit().unwrap());
252 }
253 }
254
255 if let Some(entry) = entries_to_merge.last_mut() {
256 last_entry.last_edit_at = entry.last_edit_at;
257 last_entry.transaction.end = entry.transaction.end.clone();
258 }
259 }
260
261 self.undo_stack.truncate(new_len);
262 self.undo_stack.last().map(|e| e.transaction.id)
263 }
264
265 fn finalize_last_transaction(&mut self) -> Option<&Transaction> {
266 self.undo_stack.last_mut().map(|entry| {
267 entry.suppress_grouping = true;
268 &entry.transaction
269 })
270 }
271
272 fn push_transaction(&mut self, transaction: Transaction, now: Instant) {
273 assert_eq!(self.transaction_depth, 0);
274 self.undo_stack.push(HistoryEntry {
275 transaction,
276 first_edit_at: now,
277 last_edit_at: now,
278 suppress_grouping: false,
279 });
280 self.redo_stack.clear();
281 }
282
283 fn push_undo(&mut self, op_id: clock::Local) {
284 assert_ne!(self.transaction_depth, 0);
285 if let Some(Operation::Edit(edit)) = self.operations.get(&op_id) {
286 let last_transaction = self.undo_stack.last_mut().unwrap();
287 last_transaction.push_edit(&edit);
288 }
289 }
290
291 fn pop_undo(&mut self) -> Option<&HistoryEntry> {
292 assert_eq!(self.transaction_depth, 0);
293 if let Some(entry) = self.undo_stack.pop() {
294 self.redo_stack.push(entry);
295 self.redo_stack.last()
296 } else {
297 None
298 }
299 }
300
301 fn remove_from_undo(&mut self, transaction_id: TransactionId) -> &[HistoryEntry] {
302 assert_eq!(self.transaction_depth, 0);
303
304 let redo_stack_start_len = self.redo_stack.len();
305 if let Some(entry_ix) = self
306 .undo_stack
307 .iter()
308 .rposition(|entry| entry.transaction.id == transaction_id)
309 {
310 self.redo_stack
311 .extend(self.undo_stack.drain(entry_ix..).rev());
312 }
313 &self.redo_stack[redo_stack_start_len..]
314 }
315
316 fn forget(&mut self, transaction_id: TransactionId) {
317 assert_eq!(self.transaction_depth, 0);
318 if let Some(entry_ix) = self
319 .undo_stack
320 .iter()
321 .rposition(|entry| entry.transaction.id == transaction_id)
322 {
323 self.undo_stack.remove(entry_ix);
324 } else if let Some(entry_ix) = self
325 .redo_stack
326 .iter()
327 .rposition(|entry| entry.transaction.id == transaction_id)
328 {
329 self.undo_stack.remove(entry_ix);
330 }
331 }
332
333 fn pop_redo(&mut self) -> Option<&HistoryEntry> {
334 assert_eq!(self.transaction_depth, 0);
335 if let Some(entry) = self.redo_stack.pop() {
336 self.undo_stack.push(entry);
337 self.undo_stack.last()
338 } else {
339 None
340 }
341 }
342
343 fn remove_from_redo(&mut self, transaction_id: TransactionId) -> &[HistoryEntry] {
344 assert_eq!(self.transaction_depth, 0);
345
346 let undo_stack_start_len = self.undo_stack.len();
347 if let Some(entry_ix) = self
348 .redo_stack
349 .iter()
350 .rposition(|entry| entry.transaction.id == transaction_id)
351 {
352 self.undo_stack
353 .extend(self.redo_stack.drain(entry_ix..).rev());
354 }
355 &self.undo_stack[undo_stack_start_len..]
356 }
357}
358
359#[derive(Clone, Default, Debug)]
360struct UndoMap(HashMap<clock::Local, Vec<(clock::Local, u32)>>);
361
362impl UndoMap {
363 fn insert(&mut self, undo: &UndoOperation) {
364 for (edit_id, count) in &undo.counts {
365 self.0.entry(*edit_id).or_default().push((undo.id, *count));
366 }
367 }
368
369 fn is_undone(&self, edit_id: clock::Local) -> bool {
370 self.undo_count(edit_id) % 2 == 1
371 }
372
373 fn was_undone(&self, edit_id: clock::Local, version: &clock::Global) -> bool {
374 let undo_count = self
375 .0
376 .get(&edit_id)
377 .unwrap_or(&Vec::new())
378 .iter()
379 .filter(|(undo_id, _)| version.observed(*undo_id))
380 .map(|(_, undo_count)| *undo_count)
381 .max()
382 .unwrap_or(0);
383 undo_count % 2 == 1
384 }
385
386 fn undo_count(&self, edit_id: clock::Local) -> u32 {
387 self.0
388 .get(&edit_id)
389 .unwrap_or(&Vec::new())
390 .iter()
391 .map(|(_, undo_count)| *undo_count)
392 .max()
393 .unwrap_or(0)
394 }
395}
396
397struct Edits<'a, D: TextDimension, F: FnMut(&FragmentSummary) -> bool> {
398 visible_cursor: rope::Cursor<'a>,
399 deleted_cursor: rope::Cursor<'a>,
400 fragments_cursor: Option<FilterCursor<'a, F, Fragment, FragmentTextSummary>>,
401 undos: &'a UndoMap,
402 since: &'a clock::Global,
403 old_end: D,
404 new_end: D,
405 range: Range<(&'a Locator, usize)>,
406}
407
408#[derive(Clone, Debug, Default, Eq, PartialEq)]
409pub struct Edit<D> {
410 pub old: Range<D>,
411 pub new: Range<D>,
412}
413
414impl<D> Edit<D>
415where
416 D: Sub<D, Output = D> + PartialEq + Copy,
417{
418 pub fn old_len(&self) -> D {
419 self.old.end - self.old.start
420 }
421
422 pub fn new_len(&self) -> D {
423 self.new.end - self.new.start
424 }
425
426 pub fn is_empty(&self) -> bool {
427 self.old.start == self.old.end && self.new.start == self.new.end
428 }
429}
430
431impl<D1, D2> Edit<(D1, D2)> {
432 pub fn flatten(self) -> (Edit<D1>, Edit<D2>) {
433 (
434 Edit {
435 old: self.old.start.0..self.old.end.0,
436 new: self.new.start.0..self.new.end.0,
437 },
438 Edit {
439 old: self.old.start.1..self.old.end.1,
440 new: self.new.start.1..self.new.end.1,
441 },
442 )
443 }
444}
445
446#[derive(Copy, Clone, Debug, Default, Eq, PartialEq, PartialOrd, Ord)]
447pub struct InsertionTimestamp {
448 pub replica_id: ReplicaId,
449 pub local: clock::Seq,
450 pub lamport: clock::Seq,
451}
452
453impl InsertionTimestamp {
454 pub fn local(&self) -> clock::Local {
455 clock::Local {
456 replica_id: self.replica_id,
457 value: self.local,
458 }
459 }
460
461 pub fn lamport(&self) -> clock::Lamport {
462 clock::Lamport {
463 replica_id: self.replica_id,
464 value: self.lamport,
465 }
466 }
467}
468
469#[derive(Eq, PartialEq, Clone, Debug)]
470pub struct Fragment {
471 pub id: Locator,
472 pub insertion_timestamp: InsertionTimestamp,
473 pub insertion_offset: usize,
474 pub len: usize,
475 pub visible: bool,
476 pub deletions: HashSet<clock::Local>,
477 pub max_undos: clock::Global,
478}
479
480#[derive(Eq, PartialEq, Clone, Debug)]
481pub struct FragmentSummary {
482 text: FragmentTextSummary,
483 max_id: Locator,
484 max_version: clock::Global,
485 min_insertion_version: clock::Global,
486 max_insertion_version: clock::Global,
487}
488
489#[derive(Copy, Default, Clone, Debug, PartialEq, Eq)]
490struct FragmentTextSummary {
491 visible: usize,
492 deleted: usize,
493}
494
495impl<'a> sum_tree::Dimension<'a, FragmentSummary> for FragmentTextSummary {
496 fn add_summary(&mut self, summary: &'a FragmentSummary, _: &Option<clock::Global>) {
497 self.visible += summary.text.visible;
498 self.deleted += summary.text.deleted;
499 }
500}
501
502#[derive(Eq, PartialEq, Clone, Debug)]
503struct InsertionFragment {
504 timestamp: clock::Local,
505 split_offset: usize,
506 fragment_id: Locator,
507}
508
509#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord)]
510struct InsertionFragmentKey {
511 timestamp: clock::Local,
512 split_offset: usize,
513}
514
515#[derive(Clone, Debug, Eq, PartialEq)]
516pub enum Operation {
517 Edit(EditOperation),
518 Undo {
519 undo: UndoOperation,
520 lamport_timestamp: clock::Lamport,
521 },
522}
523
524#[derive(Clone, Debug, Eq, PartialEq)]
525pub struct EditOperation {
526 pub timestamp: InsertionTimestamp,
527 pub version: clock::Global,
528 pub ranges: Vec<Range<FullOffset>>,
529 pub new_text: Vec<Arc<str>>,
530}
531
532#[derive(Clone, Debug, Eq, PartialEq)]
533pub struct UndoOperation {
534 pub id: clock::Local,
535 pub counts: HashMap<clock::Local, u32>,
536 pub transaction_ranges: Vec<Range<FullOffset>>,
537 pub transaction_version: clock::Global,
538 pub version: clock::Global,
539}
540
541impl Buffer {
542 pub fn new(replica_id: u16, remote_id: u64, base_text: String) -> Buffer {
543 let history = History::new(base_text.into());
544 let mut fragments = SumTree::new();
545 let mut insertions = SumTree::new();
546
547 let mut local_clock = clock::Local::new(replica_id);
548 let mut lamport_clock = clock::Lamport::new(replica_id);
549 let mut version = clock::Global::new();
550 let visible_text = Rope::from(history.base_text.as_ref());
551 if visible_text.len() > 0 {
552 let insertion_timestamp = InsertionTimestamp {
553 replica_id: 0,
554 local: 1,
555 lamport: 1,
556 };
557 local_clock.observe(insertion_timestamp.local());
558 lamport_clock.observe(insertion_timestamp.lamport());
559 version.observe(insertion_timestamp.local());
560 let fragment_id = Locator::between(&Locator::min(), &Locator::max());
561 let fragment = Fragment {
562 id: fragment_id,
563 insertion_timestamp,
564 insertion_offset: 0,
565 len: visible_text.len(),
566 visible: true,
567 deletions: Default::default(),
568 max_undos: Default::default(),
569 };
570 insertions.push(InsertionFragment::new(&fragment), &());
571 fragments.push(fragment, &None);
572 }
573
574 Buffer {
575 snapshot: BufferSnapshot {
576 replica_id,
577 remote_id,
578 visible_text,
579 deleted_text: Rope::new(),
580 fragments,
581 insertions,
582 version,
583 undo_map: Default::default(),
584 },
585 history,
586 deferred_ops: OperationQueue::new(),
587 deferred_replicas: HashSet::default(),
588 replica_id,
589 local_clock,
590 lamport_clock,
591 subscriptions: Default::default(),
592 edit_id_resolvers: Default::default(),
593 version_barriers: Default::default(),
594 }
595 }
596
597 pub fn version(&self) -> clock::Global {
598 self.version.clone()
599 }
600
601 pub fn snapshot(&self) -> BufferSnapshot {
602 self.snapshot.clone()
603 }
604
605 pub fn replica_id(&self) -> ReplicaId {
606 self.local_clock.replica_id
607 }
608
609 pub fn remote_id(&self) -> u64 {
610 self.remote_id
611 }
612
613 pub fn deferred_ops_len(&self) -> usize {
614 self.deferred_ops.len()
615 }
616
617 pub fn transaction_group_interval(&self) -> Duration {
618 self.history.group_interval
619 }
620
621 pub fn edit<R, I, S, T>(&mut self, edits: R) -> Operation
622 where
623 R: IntoIterator<IntoIter = I>,
624 I: ExactSizeIterator<Item = (Range<S>, T)>,
625 S: ToOffset,
626 T: Into<Arc<str>>,
627 {
628 let edits = edits
629 .into_iter()
630 .map(|(range, new_text)| (range, new_text.into()));
631
632 self.start_transaction();
633 let timestamp = InsertionTimestamp {
634 replica_id: self.replica_id,
635 local: self.local_clock.tick().value,
636 lamport: self.lamport_clock.tick().value,
637 };
638 let operation = Operation::Edit(self.apply_local_edit(edits, timestamp));
639
640 self.history.push(operation.clone());
641 self.history.push_undo(operation.local_timestamp());
642 self.snapshot.version.observe(operation.local_timestamp());
643 self.end_transaction();
644 operation
645 }
646
647 fn apply_local_edit<S: ToOffset, T: Into<Arc<str>>>(
648 &mut self,
649 edits: impl ExactSizeIterator<Item = (Range<S>, T)>,
650 timestamp: InsertionTimestamp,
651 ) -> EditOperation {
652 let mut edits_patch = Patch::default();
653 let mut edit_op = EditOperation {
654 timestamp,
655 version: self.version(),
656 ranges: Vec::with_capacity(edits.len()),
657 new_text: Vec::with_capacity(edits.len()),
658 };
659 let mut new_insertions = Vec::new();
660 let mut insertion_offset = 0;
661
662 let mut ranges = edits
663 .map(|(range, new_text)| (range.to_offset(&*self), new_text))
664 .peekable();
665
666 let mut new_ropes =
667 RopeBuilder::new(self.visible_text.cursor(0), self.deleted_text.cursor(0));
668 let mut old_fragments = self.fragments.cursor::<FragmentTextSummary>();
669 let mut new_fragments =
670 old_fragments.slice(&ranges.peek().unwrap().0.start, Bias::Right, &None);
671 new_ropes.push_tree(new_fragments.summary().text);
672
673 let mut fragment_start = old_fragments.start().visible;
674 for (range, new_text) in ranges {
675 let new_text = new_text.into();
676 let fragment_end = old_fragments.end(&None).visible;
677
678 // If the current fragment ends before this range, then jump ahead to the first fragment
679 // that extends past the start of this range, reusing any intervening fragments.
680 if fragment_end < range.start {
681 // If the current fragment has been partially consumed, then consume the rest of it
682 // and advance to the next fragment before slicing.
683 if fragment_start > old_fragments.start().visible {
684 if fragment_end > fragment_start {
685 let mut suffix = old_fragments.item().unwrap().clone();
686 suffix.len = fragment_end - fragment_start;
687 suffix.insertion_offset += fragment_start - old_fragments.start().visible;
688 new_insertions.push(InsertionFragment::insert_new(&suffix));
689 new_ropes.push_fragment(&suffix, suffix.visible);
690 new_fragments.push(suffix, &None);
691 }
692 old_fragments.next(&None);
693 }
694
695 let slice = old_fragments.slice(&range.start, Bias::Right, &None);
696 new_ropes.push_tree(slice.summary().text);
697 new_fragments.push_tree(slice, &None);
698 fragment_start = old_fragments.start().visible;
699 }
700
701 let full_range_start = FullOffset(range.start + old_fragments.start().deleted);
702
703 // Preserve any portion of the current fragment that precedes this range.
704 if fragment_start < range.start {
705 let mut prefix = old_fragments.item().unwrap().clone();
706 prefix.len = range.start - fragment_start;
707 prefix.insertion_offset += fragment_start - old_fragments.start().visible;
708 prefix.id = Locator::between(&new_fragments.summary().max_id, &prefix.id);
709 new_insertions.push(InsertionFragment::insert_new(&prefix));
710 new_ropes.push_fragment(&prefix, prefix.visible);
711 new_fragments.push(prefix, &None);
712 fragment_start = range.start;
713 }
714
715 // Insert the new text before any existing fragments within the range.
716 if !new_text.is_empty() {
717 let new_start = new_fragments.summary().text.visible;
718 edits_patch.push(Edit {
719 old: fragment_start..fragment_start,
720 new: new_start..new_start + new_text.len(),
721 });
722 let fragment = Fragment {
723 id: Locator::between(
724 &new_fragments.summary().max_id,
725 old_fragments
726 .item()
727 .map_or(&Locator::max(), |old_fragment| &old_fragment.id),
728 ),
729 insertion_timestamp: timestamp,
730 insertion_offset,
731 len: new_text.len(),
732 deletions: Default::default(),
733 max_undos: Default::default(),
734 visible: true,
735 };
736 new_insertions.push(InsertionFragment::insert_new(&fragment));
737 new_ropes.push_str(new_text.as_ref());
738 new_fragments.push(fragment, &None);
739 insertion_offset += new_text.len();
740 }
741
742 // Advance through every fragment that intersects this range, marking the intersecting
743 // portions as deleted.
744 while fragment_start < range.end {
745 let fragment = old_fragments.item().unwrap();
746 let fragment_end = old_fragments.end(&None).visible;
747 let mut intersection = fragment.clone();
748 let intersection_end = cmp::min(range.end, fragment_end);
749 if fragment.visible {
750 intersection.len = intersection_end - fragment_start;
751 intersection.insertion_offset += fragment_start - old_fragments.start().visible;
752 intersection.id =
753 Locator::between(&new_fragments.summary().max_id, &intersection.id);
754 intersection.deletions.insert(timestamp.local());
755 intersection.visible = false;
756 }
757 if intersection.len > 0 {
758 if fragment.visible && !intersection.visible {
759 let new_start = new_fragments.summary().text.visible;
760 edits_patch.push(Edit {
761 old: fragment_start..intersection_end,
762 new: new_start..new_start,
763 });
764 }
765 new_insertions.push(InsertionFragment::insert_new(&intersection));
766 new_ropes.push_fragment(&intersection, fragment.visible);
767 new_fragments.push(intersection, &None);
768 fragment_start = intersection_end;
769 }
770 if fragment_end <= range.end {
771 old_fragments.next(&None);
772 }
773 }
774
775 let full_range_end = FullOffset(range.end + old_fragments.start().deleted);
776 edit_op.ranges.push(full_range_start..full_range_end);
777 edit_op.new_text.push(new_text);
778 }
779
780 // If the current fragment has been partially consumed, then consume the rest of it
781 // and advance to the next fragment before slicing.
782 if fragment_start > old_fragments.start().visible {
783 let fragment_end = old_fragments.end(&None).visible;
784 if fragment_end > fragment_start {
785 let mut suffix = old_fragments.item().unwrap().clone();
786 suffix.len = fragment_end - fragment_start;
787 suffix.insertion_offset += fragment_start - old_fragments.start().visible;
788 new_insertions.push(InsertionFragment::insert_new(&suffix));
789 new_ropes.push_fragment(&suffix, suffix.visible);
790 new_fragments.push(suffix, &None);
791 }
792 old_fragments.next(&None);
793 }
794
795 let suffix = old_fragments.suffix(&None);
796 new_ropes.push_tree(suffix.summary().text);
797 new_fragments.push_tree(suffix, &None);
798 let (visible_text, deleted_text) = new_ropes.finish();
799 drop(old_fragments);
800
801 self.snapshot.fragments = new_fragments;
802 self.snapshot.insertions.edit(new_insertions, &());
803 self.snapshot.visible_text = visible_text;
804 self.snapshot.deleted_text = deleted_text;
805 self.subscriptions.publish_mut(&edits_patch);
806 edit_op
807 }
808
809 pub fn apply_ops<I: IntoIterator<Item = Operation>>(&mut self, ops: I) -> Result<()> {
810 let mut deferred_ops = Vec::new();
811 for op in ops {
812 self.history.push(op.clone());
813 if self.can_apply_op(&op) {
814 self.apply_op(op)?;
815 } else {
816 self.deferred_replicas.insert(op.replica_id());
817 deferred_ops.push(op);
818 }
819 }
820 self.deferred_ops.insert(deferred_ops);
821 self.flush_deferred_ops()?;
822 Ok(())
823 }
824
825 fn apply_op(&mut self, op: Operation) -> Result<()> {
826 match op {
827 Operation::Edit(edit) => {
828 if !self.version.observed(edit.timestamp.local()) {
829 self.apply_remote_edit(
830 &edit.version,
831 &edit.ranges,
832 &edit.new_text,
833 edit.timestamp,
834 );
835 self.snapshot.version.observe(edit.timestamp.local());
836 self.local_clock.observe(edit.timestamp.local());
837 self.lamport_clock.observe(edit.timestamp.lamport());
838 self.resolve_edit(edit.timestamp.local());
839 }
840 }
841 Operation::Undo {
842 undo,
843 lamport_timestamp,
844 } => {
845 if !self.version.observed(undo.id) {
846 self.apply_undo(&undo)?;
847 self.snapshot.version.observe(undo.id);
848 self.local_clock.observe(undo.id);
849 self.lamport_clock.observe(lamport_timestamp);
850 }
851 }
852 }
853 self.version_barriers
854 .retain(|(version, _)| !self.snapshot.version().observed_all(version));
855 Ok(())
856 }
857
858 fn apply_remote_edit(
859 &mut self,
860 version: &clock::Global,
861 ranges: &[Range<FullOffset>],
862 new_text: &[Arc<str>],
863 timestamp: InsertionTimestamp,
864 ) {
865 if ranges.is_empty() {
866 return;
867 }
868
869 let edits = ranges.into_iter().zip(new_text.into_iter());
870 let mut edits_patch = Patch::default();
871 let cx = Some(version.clone());
872 let mut new_insertions = Vec::new();
873 let mut insertion_offset = 0;
874 let mut new_ropes =
875 RopeBuilder::new(self.visible_text.cursor(0), self.deleted_text.cursor(0));
876 let mut old_fragments = self.fragments.cursor::<(VersionedFullOffset, usize)>();
877 let mut new_fragments = old_fragments.slice(
878 &VersionedFullOffset::Offset(ranges[0].start),
879 Bias::Left,
880 &cx,
881 );
882 new_ropes.push_tree(new_fragments.summary().text);
883
884 let mut fragment_start = old_fragments.start().0.full_offset();
885 for (range, new_text) in edits {
886 let fragment_end = old_fragments.end(&cx).0.full_offset();
887
888 // If the current fragment ends before this range, then jump ahead to the first fragment
889 // that extends past the start of this range, reusing any intervening fragments.
890 if fragment_end < range.start {
891 // If the current fragment has been partially consumed, then consume the rest of it
892 // and advance to the next fragment before slicing.
893 if fragment_start > old_fragments.start().0.full_offset() {
894 if fragment_end > fragment_start {
895 let mut suffix = old_fragments.item().unwrap().clone();
896 suffix.len = fragment_end.0 - fragment_start.0;
897 suffix.insertion_offset +=
898 fragment_start - old_fragments.start().0.full_offset();
899 new_insertions.push(InsertionFragment::insert_new(&suffix));
900 new_ropes.push_fragment(&suffix, suffix.visible);
901 new_fragments.push(suffix, &None);
902 }
903 old_fragments.next(&cx);
904 }
905
906 let slice =
907 old_fragments.slice(&VersionedFullOffset::Offset(range.start), Bias::Left, &cx);
908 new_ropes.push_tree(slice.summary().text);
909 new_fragments.push_tree(slice, &None);
910 fragment_start = old_fragments.start().0.full_offset();
911 }
912
913 // If we are at the end of a non-concurrent fragment, advance to the next one.
914 let fragment_end = old_fragments.end(&cx).0.full_offset();
915 if fragment_end == range.start && fragment_end > fragment_start {
916 let mut fragment = old_fragments.item().unwrap().clone();
917 fragment.len = fragment_end.0 - fragment_start.0;
918 fragment.insertion_offset += fragment_start - old_fragments.start().0.full_offset();
919 new_insertions.push(InsertionFragment::insert_new(&fragment));
920 new_ropes.push_fragment(&fragment, fragment.visible);
921 new_fragments.push(fragment, &None);
922 old_fragments.next(&cx);
923 fragment_start = old_fragments.start().0.full_offset();
924 }
925
926 // Skip over insertions that are concurrent to this edit, but have a lower lamport
927 // timestamp.
928 while let Some(fragment) = old_fragments.item() {
929 if fragment_start == range.start
930 && fragment.insertion_timestamp.lamport() > timestamp.lamport()
931 {
932 new_ropes.push_fragment(fragment, fragment.visible);
933 new_fragments.push(fragment.clone(), &None);
934 old_fragments.next(&cx);
935 debug_assert_eq!(fragment_start, range.start);
936 } else {
937 break;
938 }
939 }
940 debug_assert!(fragment_start <= range.start);
941
942 // Preserve any portion of the current fragment that precedes this range.
943 if fragment_start < range.start {
944 let mut prefix = old_fragments.item().unwrap().clone();
945 prefix.len = range.start.0 - fragment_start.0;
946 prefix.insertion_offset += fragment_start - old_fragments.start().0.full_offset();
947 prefix.id = Locator::between(&new_fragments.summary().max_id, &prefix.id);
948 new_insertions.push(InsertionFragment::insert_new(&prefix));
949 fragment_start = range.start;
950 new_ropes.push_fragment(&prefix, prefix.visible);
951 new_fragments.push(prefix, &None);
952 }
953
954 // Insert the new text before any existing fragments within the range.
955 if !new_text.is_empty() {
956 let mut old_start = old_fragments.start().1;
957 if old_fragments.item().map_or(false, |f| f.visible) {
958 old_start += fragment_start.0 - old_fragments.start().0.full_offset().0;
959 }
960 let new_start = new_fragments.summary().text.visible;
961 edits_patch.push(Edit {
962 old: old_start..old_start,
963 new: new_start..new_start + new_text.len(),
964 });
965 let fragment = Fragment {
966 id: Locator::between(
967 &new_fragments.summary().max_id,
968 old_fragments
969 .item()
970 .map_or(&Locator::max(), |old_fragment| &old_fragment.id),
971 ),
972 insertion_timestamp: timestamp,
973 insertion_offset,
974 len: new_text.len(),
975 deletions: Default::default(),
976 max_undos: Default::default(),
977 visible: true,
978 };
979 new_insertions.push(InsertionFragment::insert_new(&fragment));
980 new_ropes.push_str(new_text);
981 new_fragments.push(fragment, &None);
982 insertion_offset += new_text.len();
983 }
984
985 // Advance through every fragment that intersects this range, marking the intersecting
986 // portions as deleted.
987 while fragment_start < range.end {
988 let fragment = old_fragments.item().unwrap();
989 let fragment_end = old_fragments.end(&cx).0.full_offset();
990 let mut intersection = fragment.clone();
991 let intersection_end = cmp::min(range.end, fragment_end);
992 if fragment.was_visible(version, &self.undo_map) {
993 intersection.len = intersection_end.0 - fragment_start.0;
994 intersection.insertion_offset +=
995 fragment_start - old_fragments.start().0.full_offset();
996 intersection.id =
997 Locator::between(&new_fragments.summary().max_id, &intersection.id);
998 intersection.deletions.insert(timestamp.local());
999 intersection.visible = false;
1000 }
1001 if intersection.len > 0 {
1002 if fragment.visible && !intersection.visible {
1003 let old_start = old_fragments.start().1
1004 + (fragment_start.0 - old_fragments.start().0.full_offset().0);
1005 let new_start = new_fragments.summary().text.visible;
1006 edits_patch.push(Edit {
1007 old: old_start..old_start + intersection.len,
1008 new: new_start..new_start,
1009 });
1010 }
1011 new_insertions.push(InsertionFragment::insert_new(&intersection));
1012 new_ropes.push_fragment(&intersection, fragment.visible);
1013 new_fragments.push(intersection, &None);
1014 fragment_start = intersection_end;
1015 }
1016 if fragment_end <= range.end {
1017 old_fragments.next(&cx);
1018 }
1019 }
1020 }
1021
1022 // If the current fragment has been partially consumed, then consume the rest of it
1023 // and advance to the next fragment before slicing.
1024 if fragment_start > old_fragments.start().0.full_offset() {
1025 let fragment_end = old_fragments.end(&cx).0.full_offset();
1026 if fragment_end > fragment_start {
1027 let mut suffix = old_fragments.item().unwrap().clone();
1028 suffix.len = fragment_end.0 - fragment_start.0;
1029 suffix.insertion_offset += fragment_start - old_fragments.start().0.full_offset();
1030 new_insertions.push(InsertionFragment::insert_new(&suffix));
1031 new_ropes.push_fragment(&suffix, suffix.visible);
1032 new_fragments.push(suffix, &None);
1033 }
1034 old_fragments.next(&cx);
1035 }
1036
1037 let suffix = old_fragments.suffix(&cx);
1038 new_ropes.push_tree(suffix.summary().text);
1039 new_fragments.push_tree(suffix, &None);
1040 let (visible_text, deleted_text) = new_ropes.finish();
1041 drop(old_fragments);
1042
1043 self.snapshot.fragments = new_fragments;
1044 self.snapshot.visible_text = visible_text;
1045 self.snapshot.deleted_text = deleted_text;
1046 self.snapshot.insertions.edit(new_insertions, &());
1047 self.subscriptions.publish_mut(&edits_patch)
1048 }
1049
1050 fn apply_undo(&mut self, undo: &UndoOperation) -> Result<()> {
1051 let mut edits = Patch::default();
1052 self.snapshot.undo_map.insert(undo);
1053
1054 let mut cx = undo.transaction_version.clone();
1055 for edit_id in undo.counts.keys().copied() {
1056 cx.observe(edit_id);
1057 }
1058 let cx = Some(cx);
1059
1060 let mut old_fragments = self.fragments.cursor::<(VersionedFullOffset, usize)>();
1061 let mut new_fragments = old_fragments.slice(
1062 &VersionedFullOffset::Offset(undo.transaction_ranges[0].start),
1063 Bias::Right,
1064 &cx,
1065 );
1066 let mut new_ropes =
1067 RopeBuilder::new(self.visible_text.cursor(0), self.deleted_text.cursor(0));
1068 new_ropes.push_tree(new_fragments.summary().text);
1069
1070 for range in &undo.transaction_ranges {
1071 let mut end_offset = old_fragments.end(&cx).0.full_offset();
1072
1073 if end_offset < range.start {
1074 let preceding_fragments = old_fragments.slice(
1075 &VersionedFullOffset::Offset(range.start),
1076 Bias::Right,
1077 &cx,
1078 );
1079 new_ropes.push_tree(preceding_fragments.summary().text);
1080 new_fragments.push_tree(preceding_fragments, &None);
1081 }
1082
1083 while end_offset <= range.end {
1084 if let Some(fragment) = old_fragments.item() {
1085 let mut fragment = fragment.clone();
1086 let fragment_was_visible = fragment.visible;
1087
1088 if fragment.was_visible(&undo.transaction_version, &self.undo_map)
1089 || undo
1090 .counts
1091 .contains_key(&fragment.insertion_timestamp.local())
1092 {
1093 fragment.visible = fragment.is_visible(&self.undo_map);
1094 fragment.max_undos.observe(undo.id);
1095 }
1096
1097 let old_start = old_fragments.start().1;
1098 let new_start = new_fragments.summary().text.visible;
1099 if fragment_was_visible && !fragment.visible {
1100 edits.push(Edit {
1101 old: old_start..old_start + fragment.len,
1102 new: new_start..new_start,
1103 });
1104 } else if !fragment_was_visible && fragment.visible {
1105 edits.push(Edit {
1106 old: old_start..old_start,
1107 new: new_start..new_start + fragment.len,
1108 });
1109 }
1110 new_ropes.push_fragment(&fragment, fragment_was_visible);
1111 new_fragments.push(fragment, &None);
1112
1113 old_fragments.next(&cx);
1114 if end_offset == old_fragments.end(&cx).0.full_offset() {
1115 let unseen_fragments = old_fragments.slice(
1116 &VersionedFullOffset::Offset(end_offset),
1117 Bias::Right,
1118 &cx,
1119 );
1120 new_ropes.push_tree(unseen_fragments.summary().text);
1121 new_fragments.push_tree(unseen_fragments, &None);
1122 }
1123 end_offset = old_fragments.end(&cx).0.full_offset();
1124 } else {
1125 break;
1126 }
1127 }
1128 }
1129
1130 let suffix = old_fragments.suffix(&cx);
1131 new_ropes.push_tree(suffix.summary().text);
1132 new_fragments.push_tree(suffix, &None);
1133
1134 drop(old_fragments);
1135 let (visible_text, deleted_text) = new_ropes.finish();
1136 self.snapshot.fragments = new_fragments;
1137 self.snapshot.visible_text = visible_text;
1138 self.snapshot.deleted_text = deleted_text;
1139 self.subscriptions.publish_mut(&edits);
1140 Ok(())
1141 }
1142
1143 fn flush_deferred_ops(&mut self) -> Result<()> {
1144 self.deferred_replicas.clear();
1145 let mut deferred_ops = Vec::new();
1146 for op in self.deferred_ops.drain().iter().cloned() {
1147 if self.can_apply_op(&op) {
1148 self.apply_op(op)?;
1149 } else {
1150 self.deferred_replicas.insert(op.replica_id());
1151 deferred_ops.push(op);
1152 }
1153 }
1154 self.deferred_ops.insert(deferred_ops);
1155 Ok(())
1156 }
1157
1158 fn can_apply_op(&self, op: &Operation) -> bool {
1159 if self.deferred_replicas.contains(&op.replica_id()) {
1160 false
1161 } else {
1162 match op {
1163 Operation::Edit(edit) => self.version.observed_all(&edit.version),
1164 Operation::Undo { undo, .. } => self.version.observed_all(&undo.version),
1165 }
1166 }
1167 }
1168
1169 pub fn peek_undo_stack(&self) -> Option<&HistoryEntry> {
1170 self.history.undo_stack.last()
1171 }
1172
1173 pub fn peek_redo_stack(&self) -> Option<&HistoryEntry> {
1174 self.history.redo_stack.last()
1175 }
1176
1177 pub fn start_transaction(&mut self) -> Option<TransactionId> {
1178 self.start_transaction_at(Instant::now())
1179 }
1180
1181 pub fn start_transaction_at(&mut self, now: Instant) -> Option<TransactionId> {
1182 self.history
1183 .start_transaction(self.version.clone(), now, &mut self.local_clock)
1184 }
1185
1186 pub fn end_transaction(&mut self) -> Option<(TransactionId, clock::Global)> {
1187 self.end_transaction_at(Instant::now())
1188 }
1189
1190 pub fn end_transaction_at(&mut self, now: Instant) -> Option<(TransactionId, clock::Global)> {
1191 if let Some(entry) = self.history.end_transaction(now) {
1192 let since = entry.transaction.start.clone();
1193 let id = self.history.group().unwrap();
1194 Some((id, since))
1195 } else {
1196 None
1197 }
1198 }
1199
1200 pub fn finalize_last_transaction(&mut self) -> Option<&Transaction> {
1201 self.history.finalize_last_transaction()
1202 }
1203
1204 pub fn base_text(&self) -> &Arc<str> {
1205 &self.history.base_text
1206 }
1207
1208 pub fn history(&self) -> impl Iterator<Item = &Operation> {
1209 self.history.operations.values()
1210 }
1211
1212 pub fn undo_history(&self) -> impl Iterator<Item = (&clock::Local, &[(clock::Local, u32)])> {
1213 self.undo_map
1214 .0
1215 .iter()
1216 .map(|(edit_id, undo_counts)| (edit_id, undo_counts.as_slice()))
1217 }
1218
1219 pub fn undo(&mut self) -> Option<(TransactionId, Operation)> {
1220 if let Some(entry) = self.history.pop_undo() {
1221 let transaction = entry.transaction.clone();
1222 let transaction_id = transaction.id;
1223 let op = self.undo_or_redo(transaction).unwrap();
1224 Some((transaction_id, op))
1225 } else {
1226 None
1227 }
1228 }
1229
1230 pub fn undo_to_transaction(&mut self, transaction_id: TransactionId) -> Vec<Operation> {
1231 let transactions = self
1232 .history
1233 .remove_from_undo(transaction_id)
1234 .iter()
1235 .map(|entry| entry.transaction.clone())
1236 .collect::<Vec<_>>();
1237 transactions
1238 .into_iter()
1239 .map(|transaction| self.undo_or_redo(transaction).unwrap())
1240 .collect()
1241 }
1242
1243 pub fn forget_transaction(&mut self, transaction_id: TransactionId) {
1244 self.history.forget(transaction_id);
1245 }
1246
1247 pub fn redo(&mut self) -> Option<(TransactionId, Operation)> {
1248 if let Some(entry) = self.history.pop_redo() {
1249 let transaction = entry.transaction.clone();
1250 let transaction_id = transaction.id;
1251 let op = self.undo_or_redo(transaction).unwrap();
1252 Some((transaction_id, op))
1253 } else {
1254 None
1255 }
1256 }
1257
1258 pub fn redo_to_transaction(&mut self, transaction_id: TransactionId) -> Vec<Operation> {
1259 let transactions = self
1260 .history
1261 .remove_from_redo(transaction_id)
1262 .iter()
1263 .map(|entry| entry.transaction.clone())
1264 .collect::<Vec<_>>();
1265 transactions
1266 .into_iter()
1267 .map(|transaction| self.undo_or_redo(transaction).unwrap())
1268 .collect()
1269 }
1270
1271 fn undo_or_redo(&mut self, transaction: Transaction) -> Result<Operation> {
1272 let mut counts = HashMap::default();
1273 for edit_id in transaction.edit_ids {
1274 counts.insert(edit_id, self.undo_map.undo_count(edit_id) + 1);
1275 }
1276
1277 let undo = UndoOperation {
1278 id: self.local_clock.tick(),
1279 version: self.version(),
1280 counts,
1281 transaction_ranges: transaction.ranges,
1282 transaction_version: transaction.start.clone(),
1283 };
1284 self.apply_undo(&undo)?;
1285 let operation = Operation::Undo {
1286 undo,
1287 lamport_timestamp: self.lamport_clock.tick(),
1288 };
1289 self.snapshot.version.observe(operation.local_timestamp());
1290 self.history.push(operation.clone());
1291 Ok(operation)
1292 }
1293
1294 pub fn push_transaction(&mut self, transaction: Transaction, now: Instant) {
1295 self.history.push_transaction(transaction, now);
1296 self.history.finalize_last_transaction();
1297 }
1298
1299 pub fn subscribe(&mut self) -> Subscription {
1300 self.subscriptions.subscribe()
1301 }
1302
1303 pub fn wait_for_edits(
1304 &mut self,
1305 edit_ids: impl IntoIterator<Item = clock::Local>,
1306 ) -> impl 'static + Future<Output = ()> {
1307 let mut futures = Vec::new();
1308 for edit_id in edit_ids {
1309 if !self.version.observed(edit_id) {
1310 let (tx, rx) = oneshot::channel();
1311 self.edit_id_resolvers.entry(edit_id).or_default().push(tx);
1312 futures.push(rx);
1313 }
1314 }
1315
1316 async move {
1317 for mut future in futures {
1318 future.recv().await;
1319 }
1320 }
1321 }
1322
1323 pub fn wait_for_anchors<'a>(
1324 &mut self,
1325 anchors: impl IntoIterator<Item = &'a Anchor>,
1326 ) -> impl 'static + Future<Output = ()> {
1327 let mut futures = Vec::new();
1328 for anchor in anchors {
1329 if !self.version.observed(anchor.timestamp)
1330 && *anchor != Anchor::MAX
1331 && *anchor != Anchor::MIN
1332 {
1333 let (tx, rx) = oneshot::channel();
1334 self.edit_id_resolvers
1335 .entry(anchor.timestamp)
1336 .or_default()
1337 .push(tx);
1338 futures.push(rx);
1339 }
1340 }
1341
1342 async move {
1343 for mut future in futures {
1344 future.recv().await;
1345 }
1346 }
1347 }
1348
1349 pub fn wait_for_version(&mut self, version: clock::Global) -> impl Future<Output = ()> {
1350 let (tx, mut rx) = barrier::channel();
1351 if !self.snapshot.version.observed_all(&version) {
1352 self.version_barriers.push((version, tx));
1353 }
1354 async move {
1355 rx.recv().await;
1356 }
1357 }
1358
1359 fn resolve_edit(&mut self, edit_id: clock::Local) {
1360 for mut tx in self
1361 .edit_id_resolvers
1362 .remove(&edit_id)
1363 .into_iter()
1364 .flatten()
1365 {
1366 let _ = tx.try_send(());
1367 }
1368 }
1369}
1370
1371#[cfg(any(test, feature = "test-support"))]
1372impl Buffer {
1373 pub fn check_invariants(&self) {
1374 // Ensure every fragment is ordered by locator in the fragment tree and corresponds
1375 // to an insertion fragment in the insertions tree.
1376 let mut prev_fragment_id = Locator::min();
1377 for fragment in self.snapshot.fragments.items(&None) {
1378 assert!(fragment.id > prev_fragment_id);
1379 prev_fragment_id = fragment.id.clone();
1380
1381 let insertion_fragment = self
1382 .snapshot
1383 .insertions
1384 .get(
1385 &InsertionFragmentKey {
1386 timestamp: fragment.insertion_timestamp.local(),
1387 split_offset: fragment.insertion_offset,
1388 },
1389 &(),
1390 )
1391 .unwrap();
1392 assert_eq!(
1393 insertion_fragment.fragment_id, fragment.id,
1394 "fragment: {:?}\ninsertion: {:?}",
1395 fragment, insertion_fragment
1396 );
1397 }
1398
1399 let mut cursor = self.snapshot.fragments.cursor::<Option<&Locator>>();
1400 for insertion_fragment in self.snapshot.insertions.cursor::<()>() {
1401 cursor.seek(&Some(&insertion_fragment.fragment_id), Bias::Left, &None);
1402 let fragment = cursor.item().unwrap();
1403 assert_eq!(insertion_fragment.fragment_id, fragment.id);
1404 assert_eq!(insertion_fragment.split_offset, fragment.insertion_offset);
1405 }
1406
1407 let fragment_summary = self.snapshot.fragments.summary();
1408 assert_eq!(
1409 fragment_summary.text.visible,
1410 self.snapshot.visible_text.len()
1411 );
1412 assert_eq!(
1413 fragment_summary.text.deleted,
1414 self.snapshot.deleted_text.len()
1415 );
1416 }
1417
1418 pub fn set_group_interval(&mut self, group_interval: Duration) {
1419 self.history.group_interval = group_interval;
1420 }
1421
1422 pub fn random_byte_range(&self, start_offset: usize, rng: &mut impl rand::Rng) -> Range<usize> {
1423 let end = self.clip_offset(rng.gen_range(start_offset..=self.len()), Bias::Right);
1424 let start = self.clip_offset(rng.gen_range(start_offset..=end), Bias::Right);
1425 start..end
1426 }
1427
1428 pub fn randomly_edit<T>(
1429 &mut self,
1430 rng: &mut T,
1431 edit_count: usize,
1432 ) -> (Vec<(Range<usize>, Arc<str>)>, Operation)
1433 where
1434 T: rand::Rng,
1435 {
1436 let mut edits: Vec<(Range<usize>, Arc<str>)> = Vec::new();
1437 let mut last_end = None;
1438 for _ in 0..edit_count {
1439 if last_end.map_or(false, |last_end| last_end >= self.len()) {
1440 break;
1441 }
1442 let new_start = last_end.map_or(0, |last_end| last_end + 1);
1443 let range = self.random_byte_range(new_start, rng);
1444 last_end = Some(range.end);
1445
1446 let new_text_len = rng.gen_range(0..10);
1447 let new_text: String = crate::random_char_iter::RandomCharIter::new(&mut *rng)
1448 .take(new_text_len)
1449 .collect();
1450
1451 edits.push((range, new_text.into()));
1452 }
1453
1454 log::info!("mutating buffer {} with {:?}", self.replica_id, edits);
1455 let op = self.edit(edits.iter().cloned());
1456 (edits, op)
1457 }
1458
1459 pub fn randomly_undo_redo(&mut self, rng: &mut impl rand::Rng) -> Vec<Operation> {
1460 use rand::prelude::*;
1461
1462 let mut ops = Vec::new();
1463 for _ in 0..rng.gen_range(1..=5) {
1464 if let Some(entry) = self.history.undo_stack.choose(rng) {
1465 let transaction = entry.transaction.clone();
1466 log::info!(
1467 "undoing buffer {} transaction {:?}",
1468 self.replica_id,
1469 transaction
1470 );
1471 ops.push(self.undo_or_redo(transaction).unwrap());
1472 }
1473 }
1474 ops
1475 }
1476}
1477
1478impl Deref for Buffer {
1479 type Target = BufferSnapshot;
1480
1481 fn deref(&self) -> &Self::Target {
1482 &self.snapshot
1483 }
1484}
1485
1486impl BufferSnapshot {
1487 pub fn as_rope(&self) -> &Rope {
1488 &self.visible_text
1489 }
1490
1491 pub fn replica_id(&self) -> ReplicaId {
1492 self.replica_id
1493 }
1494
1495 pub fn row_count(&self) -> u32 {
1496 self.max_point().row + 1
1497 }
1498
1499 pub fn len(&self) -> usize {
1500 self.visible_text.len()
1501 }
1502
1503 pub fn chars(&self) -> impl Iterator<Item = char> + '_ {
1504 self.chars_at(0)
1505 }
1506
1507 pub fn chars_for_range<T: ToOffset>(&self, range: Range<T>) -> impl Iterator<Item = char> + '_ {
1508 self.text_for_range(range).flat_map(str::chars)
1509 }
1510
1511 pub fn contains_str_at<T>(&self, position: T, needle: &str) -> bool
1512 where
1513 T: ToOffset,
1514 {
1515 let position = position.to_offset(self);
1516 position == self.clip_offset(position, Bias::Left)
1517 && self
1518 .bytes_in_range(position..self.len())
1519 .flatten()
1520 .copied()
1521 .take(needle.len())
1522 .eq(needle.bytes())
1523 }
1524
1525 pub fn common_prefix_at<T>(&self, position: T, needle: &str) -> Range<T>
1526 where
1527 T: ToOffset + TextDimension,
1528 {
1529 let offset = position.to_offset(self);
1530 let common_prefix_len = needle
1531 .char_indices()
1532 .map(|(index, _)| index)
1533 .chain([needle.len()])
1534 .take_while(|&len| len <= offset)
1535 .filter(|&len| {
1536 let left = self
1537 .chars_for_range(offset - len..offset)
1538 .flat_map(|c| char::to_lowercase(c));
1539 let right = needle[..len].chars().flat_map(|c| char::to_lowercase(c));
1540 left.eq(right)
1541 })
1542 .last()
1543 .unwrap_or(0);
1544 let start_offset = offset - common_prefix_len;
1545 let start = self.text_summary_for_range(0..start_offset);
1546 start..position
1547 }
1548
1549 pub fn text(&self) -> String {
1550 self.visible_text.to_string()
1551 }
1552
1553 pub fn deleted_text(&self) -> String {
1554 self.deleted_text.to_string()
1555 }
1556
1557 pub fn fragments(&self) -> impl Iterator<Item = &Fragment> {
1558 self.fragments.iter()
1559 }
1560
1561 pub fn text_summary(&self) -> TextSummary {
1562 self.visible_text.summary()
1563 }
1564
1565 pub fn max_point(&self) -> Point {
1566 self.visible_text.max_point()
1567 }
1568
1569 pub fn max_point_utf16(&self) -> PointUtf16 {
1570 self.visible_text.max_point_utf16()
1571 }
1572
1573 pub fn point_to_offset(&self, point: Point) -> usize {
1574 self.visible_text.point_to_offset(point)
1575 }
1576
1577 pub fn point_utf16_to_offset(&self, point: PointUtf16) -> usize {
1578 self.visible_text.point_utf16_to_offset(point)
1579 }
1580
1581 pub fn point_utf16_to_point(&self, point: PointUtf16) -> Point {
1582 self.visible_text.point_utf16_to_point(point)
1583 }
1584
1585 pub fn offset_to_point(&self, offset: usize) -> Point {
1586 self.visible_text.offset_to_point(offset)
1587 }
1588
1589 pub fn offset_to_point_utf16(&self, offset: usize) -> PointUtf16 {
1590 self.visible_text.offset_to_point_utf16(offset)
1591 }
1592
1593 pub fn point_to_point_utf16(&self, point: Point) -> PointUtf16 {
1594 self.visible_text.point_to_point_utf16(point)
1595 }
1596
1597 pub fn version(&self) -> &clock::Global {
1598 &self.version
1599 }
1600
1601 pub fn chars_at<'a, T: ToOffset>(&'a self, position: T) -> impl Iterator<Item = char> + 'a {
1602 let offset = position.to_offset(self);
1603 self.visible_text.chars_at(offset)
1604 }
1605
1606 pub fn reversed_chars_at<'a, T: ToOffset>(
1607 &'a self,
1608 position: T,
1609 ) -> impl Iterator<Item = char> + 'a {
1610 let offset = position.to_offset(self);
1611 self.visible_text.reversed_chars_at(offset)
1612 }
1613
1614 pub fn reversed_chunks_in_range<T: ToOffset>(&self, range: Range<T>) -> rope::Chunks {
1615 let range = range.start.to_offset(self)..range.end.to_offset(self);
1616 self.visible_text.reversed_chunks_in_range(range)
1617 }
1618
1619 pub fn bytes_in_range<'a, T: ToOffset>(&'a self, range: Range<T>) -> rope::Bytes<'a> {
1620 let start = range.start.to_offset(self);
1621 let end = range.end.to_offset(self);
1622 self.visible_text.bytes_in_range(start..end)
1623 }
1624
1625 pub fn text_for_range<'a, T: ToOffset>(&'a self, range: Range<T>) -> Chunks<'a> {
1626 let start = range.start.to_offset(self);
1627 let end = range.end.to_offset(self);
1628 self.visible_text.chunks_in_range(start..end)
1629 }
1630
1631 pub fn line_len(&self, row: u32) -> u32 {
1632 let row_start_offset = Point::new(row, 0).to_offset(self);
1633 let row_end_offset = if row >= self.max_point().row {
1634 self.len()
1635 } else {
1636 Point::new(row + 1, 0).to_offset(self) - 1
1637 };
1638 (row_end_offset - row_start_offset) as u32
1639 }
1640
1641 pub fn is_line_blank(&self, row: u32) -> bool {
1642 self.text_for_range(Point::new(row, 0)..Point::new(row, self.line_len(row)))
1643 .all(|chunk| chunk.matches(|c: char| !c.is_whitespace()).next().is_none())
1644 }
1645
1646 pub fn text_summary_for_range<'a, D, O: ToOffset>(&'a self, range: Range<O>) -> D
1647 where
1648 D: TextDimension,
1649 {
1650 self.visible_text
1651 .cursor(range.start.to_offset(self))
1652 .summary(range.end.to_offset(self))
1653 }
1654
1655 pub fn summaries_for_anchors<'a, D, A>(&'a self, anchors: A) -> impl 'a + Iterator<Item = D>
1656 where
1657 D: 'a + TextDimension,
1658 A: 'a + IntoIterator<Item = &'a Anchor>,
1659 {
1660 let anchors = anchors.into_iter();
1661 let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>();
1662 let mut fragment_cursor = self.fragments.cursor::<(Option<&Locator>, usize)>();
1663 let mut text_cursor = self.visible_text.cursor(0);
1664 let mut position = D::default();
1665
1666 anchors.map(move |anchor| {
1667 if *anchor == Anchor::MIN {
1668 return D::default();
1669 } else if *anchor == Anchor::MAX {
1670 return D::from_text_summary(&self.visible_text.summary());
1671 }
1672
1673 let anchor_key = InsertionFragmentKey {
1674 timestamp: anchor.timestamp,
1675 split_offset: anchor.offset,
1676 };
1677 insertion_cursor.seek(&anchor_key, anchor.bias, &());
1678 if let Some(insertion) = insertion_cursor.item() {
1679 let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
1680 if comparison == Ordering::Greater
1681 || (anchor.bias == Bias::Left
1682 && comparison == Ordering::Equal
1683 && anchor.offset > 0)
1684 {
1685 insertion_cursor.prev(&());
1686 }
1687 } else {
1688 insertion_cursor.prev(&());
1689 }
1690 let insertion = insertion_cursor.item().expect("invalid insertion");
1691 assert_eq!(insertion.timestamp, anchor.timestamp, "invalid insertion");
1692
1693 fragment_cursor.seek_forward(&Some(&insertion.fragment_id), Bias::Left, &None);
1694 let fragment = fragment_cursor.item().unwrap();
1695 let mut fragment_offset = fragment_cursor.start().1;
1696 if fragment.visible {
1697 fragment_offset += anchor.offset - insertion.split_offset;
1698 }
1699
1700 position.add_assign(&text_cursor.summary(fragment_offset));
1701 position.clone()
1702 })
1703 }
1704
1705 fn summary_for_anchor<'a, D>(&'a self, anchor: &Anchor) -> D
1706 where
1707 D: TextDimension,
1708 {
1709 if *anchor == Anchor::MIN {
1710 D::default()
1711 } else if *anchor == Anchor::MAX {
1712 D::from_text_summary(&self.visible_text.summary())
1713 } else {
1714 let anchor_key = InsertionFragmentKey {
1715 timestamp: anchor.timestamp,
1716 split_offset: anchor.offset,
1717 };
1718 let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>();
1719 insertion_cursor.seek(&anchor_key, anchor.bias, &());
1720 if let Some(insertion) = insertion_cursor.item() {
1721 let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
1722 if comparison == Ordering::Greater
1723 || (anchor.bias == Bias::Left
1724 && comparison == Ordering::Equal
1725 && anchor.offset > 0)
1726 {
1727 insertion_cursor.prev(&());
1728 }
1729 } else {
1730 insertion_cursor.prev(&());
1731 }
1732 let insertion = insertion_cursor.item().expect("invalid insertion");
1733 assert_eq!(insertion.timestamp, anchor.timestamp, "invalid insertion");
1734
1735 let mut fragment_cursor = self.fragments.cursor::<(Option<&Locator>, usize)>();
1736 fragment_cursor.seek(&Some(&insertion.fragment_id), Bias::Left, &None);
1737 let fragment = fragment_cursor.item().unwrap();
1738 let mut fragment_offset = fragment_cursor.start().1;
1739 if fragment.visible {
1740 fragment_offset += anchor.offset - insertion.split_offset;
1741 }
1742 self.text_summary_for_range(0..fragment_offset)
1743 }
1744 }
1745
1746 fn fragment_id_for_anchor(&self, anchor: &Anchor) -> &Locator {
1747 if *anchor == Anchor::MIN {
1748 &locator::MIN
1749 } else if *anchor == Anchor::MAX {
1750 &locator::MAX
1751 } else {
1752 let anchor_key = InsertionFragmentKey {
1753 timestamp: anchor.timestamp,
1754 split_offset: anchor.offset,
1755 };
1756 let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>();
1757 insertion_cursor.seek(&anchor_key, anchor.bias, &());
1758 if let Some(insertion) = insertion_cursor.item() {
1759 let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
1760 if comparison == Ordering::Greater
1761 || (anchor.bias == Bias::Left
1762 && comparison == Ordering::Equal
1763 && anchor.offset > 0)
1764 {
1765 insertion_cursor.prev(&());
1766 }
1767 } else {
1768 insertion_cursor.prev(&());
1769 }
1770 let insertion = insertion_cursor.item().expect("invalid insertion");
1771 debug_assert_eq!(insertion.timestamp, anchor.timestamp, "invalid insertion");
1772 &insertion.fragment_id
1773 }
1774 }
1775
1776 pub fn anchor_before<T: ToOffset>(&self, position: T) -> Anchor {
1777 self.anchor_at(position, Bias::Left)
1778 }
1779
1780 pub fn anchor_after<T: ToOffset>(&self, position: T) -> Anchor {
1781 self.anchor_at(position, Bias::Right)
1782 }
1783
1784 pub fn anchor_at<T: ToOffset>(&self, position: T, bias: Bias) -> Anchor {
1785 let offset = position.to_offset(self);
1786 if bias == Bias::Left && offset == 0 {
1787 Anchor::MIN
1788 } else if bias == Bias::Right && offset == self.len() {
1789 Anchor::MAX
1790 } else {
1791 let mut fragment_cursor = self.fragments.cursor::<usize>();
1792 fragment_cursor.seek(&offset, bias, &None);
1793 let fragment = fragment_cursor.item().unwrap();
1794 let overshoot = offset - *fragment_cursor.start();
1795 Anchor {
1796 timestamp: fragment.insertion_timestamp.local(),
1797 offset: fragment.insertion_offset + overshoot,
1798 bias,
1799 buffer_id: Some(self.remote_id),
1800 }
1801 }
1802 }
1803
1804 pub fn can_resolve(&self, anchor: &Anchor) -> bool {
1805 *anchor == Anchor::MIN
1806 || *anchor == Anchor::MAX
1807 || (Some(self.remote_id) == anchor.buffer_id && self.version.observed(anchor.timestamp))
1808 }
1809
1810 pub fn clip_offset(&self, offset: usize, bias: Bias) -> usize {
1811 self.visible_text.clip_offset(offset, bias)
1812 }
1813
1814 pub fn clip_point(&self, point: Point, bias: Bias) -> Point {
1815 self.visible_text.clip_point(point, bias)
1816 }
1817
1818 pub fn clip_point_utf16(&self, point: PointUtf16, bias: Bias) -> PointUtf16 {
1819 self.visible_text.clip_point_utf16(point, bias)
1820 }
1821
1822 pub fn edits_since<'a, D>(
1823 &'a self,
1824 since: &'a clock::Global,
1825 ) -> impl 'a + Iterator<Item = Edit<D>>
1826 where
1827 D: TextDimension + Ord,
1828 {
1829 self.edits_since_in_range(since, Anchor::MIN..Anchor::MAX)
1830 }
1831
1832 pub fn edited_ranges_for_transaction<'a, D>(
1833 &'a self,
1834 transaction: &'a Transaction,
1835 ) -> impl 'a + Iterator<Item = Range<D>>
1836 where
1837 D: TextDimension,
1838 {
1839 let mut cursor = self.fragments.cursor::<(VersionedFullOffset, usize)>();
1840 let mut rope_cursor = self.visible_text.cursor(0);
1841 let cx = Some(transaction.end.clone());
1842 let mut position = D::default();
1843 transaction.ranges.iter().map(move |range| {
1844 cursor.seek_forward(&VersionedFullOffset::Offset(range.start), Bias::Right, &cx);
1845 let mut start_offset = cursor.start().1;
1846 if cursor
1847 .item()
1848 .map_or(false, |fragment| fragment.is_visible(&self.undo_map))
1849 {
1850 start_offset += range.start - cursor.start().0.full_offset()
1851 }
1852 position.add_assign(&rope_cursor.summary(start_offset));
1853 let start = position.clone();
1854
1855 cursor.seek_forward(&VersionedFullOffset::Offset(range.end), Bias::Left, &cx);
1856 let mut end_offset = cursor.start().1;
1857 if cursor
1858 .item()
1859 .map_or(false, |fragment| fragment.is_visible(&self.undo_map))
1860 {
1861 end_offset += range.end - cursor.start().0.full_offset();
1862 }
1863 position.add_assign(&rope_cursor.summary(end_offset));
1864 start..position.clone()
1865 })
1866 }
1867
1868 pub fn edits_since_in_range<'a, D>(
1869 &'a self,
1870 since: &'a clock::Global,
1871 range: Range<Anchor>,
1872 ) -> impl 'a + Iterator<Item = Edit<D>>
1873 where
1874 D: TextDimension + Ord,
1875 {
1876 let fragments_cursor = if *since == self.version {
1877 None
1878 } else {
1879 let mut cursor = self
1880 .fragments
1881 .filter(move |summary| !since.observed_all(&summary.max_version));
1882 cursor.next(&None);
1883 Some(cursor)
1884 };
1885 let mut cursor = self
1886 .fragments
1887 .cursor::<(Option<&Locator>, FragmentTextSummary)>();
1888
1889 let start_fragment_id = self.fragment_id_for_anchor(&range.start);
1890 cursor.seek(&Some(start_fragment_id), Bias::Left, &None);
1891 let mut visible_start = cursor.start().1.visible;
1892 let mut deleted_start = cursor.start().1.deleted;
1893 if let Some(fragment) = cursor.item() {
1894 let overshoot = range.start.offset - fragment.insertion_offset;
1895 if fragment.visible {
1896 visible_start += overshoot;
1897 } else {
1898 deleted_start += overshoot;
1899 }
1900 }
1901 let end_fragment_id = self.fragment_id_for_anchor(&range.end);
1902
1903 Edits {
1904 visible_cursor: self.visible_text.cursor(visible_start),
1905 deleted_cursor: self.deleted_text.cursor(deleted_start),
1906 fragments_cursor,
1907 undos: &self.undo_map,
1908 since,
1909 old_end: Default::default(),
1910 new_end: Default::default(),
1911 range: (start_fragment_id, range.start.offset)..(end_fragment_id, range.end.offset),
1912 }
1913 }
1914}
1915
1916struct RopeBuilder<'a> {
1917 old_visible_cursor: rope::Cursor<'a>,
1918 old_deleted_cursor: rope::Cursor<'a>,
1919 new_visible: Rope,
1920 new_deleted: Rope,
1921}
1922
1923impl<'a> RopeBuilder<'a> {
1924 fn new(old_visible_cursor: rope::Cursor<'a>, old_deleted_cursor: rope::Cursor<'a>) -> Self {
1925 Self {
1926 old_visible_cursor,
1927 old_deleted_cursor,
1928 new_visible: Rope::new(),
1929 new_deleted: Rope::new(),
1930 }
1931 }
1932
1933 fn push_tree(&mut self, len: FragmentTextSummary) {
1934 self.push(len.visible, true, true);
1935 self.push(len.deleted, false, false);
1936 }
1937
1938 fn push_fragment(&mut self, fragment: &Fragment, was_visible: bool) {
1939 debug_assert!(fragment.len > 0);
1940 self.push(fragment.len, was_visible, fragment.visible)
1941 }
1942
1943 fn push(&mut self, len: usize, was_visible: bool, is_visible: bool) {
1944 let text = if was_visible {
1945 self.old_visible_cursor
1946 .slice(self.old_visible_cursor.offset() + len)
1947 } else {
1948 self.old_deleted_cursor
1949 .slice(self.old_deleted_cursor.offset() + len)
1950 };
1951 if is_visible {
1952 self.new_visible.append(text);
1953 } else {
1954 self.new_deleted.append(text);
1955 }
1956 }
1957
1958 fn push_str(&mut self, text: &str) {
1959 self.new_visible.push(text);
1960 }
1961
1962 fn finish(mut self) -> (Rope, Rope) {
1963 self.new_visible.append(self.old_visible_cursor.suffix());
1964 self.new_deleted.append(self.old_deleted_cursor.suffix());
1965 (self.new_visible, self.new_deleted)
1966 }
1967}
1968
1969impl<'a, D: TextDimension + Ord, F: FnMut(&FragmentSummary) -> bool> Iterator for Edits<'a, D, F> {
1970 type Item = Edit<D>;
1971
1972 fn next(&mut self) -> Option<Self::Item> {
1973 let mut pending_edit: Option<Edit<D>> = None;
1974 let cursor = self.fragments_cursor.as_mut()?;
1975
1976 while let Some(fragment) = cursor.item() {
1977 if fragment.id < *self.range.start.0 {
1978 cursor.next(&None);
1979 continue;
1980 } else if fragment.id > *self.range.end.0 {
1981 break;
1982 }
1983
1984 if cursor.start().visible > self.visible_cursor.offset() {
1985 let summary = self.visible_cursor.summary(cursor.start().visible);
1986 self.old_end.add_assign(&summary);
1987 self.new_end.add_assign(&summary);
1988 }
1989
1990 if pending_edit
1991 .as_ref()
1992 .map_or(false, |change| change.new.end < self.new_end)
1993 {
1994 break;
1995 }
1996
1997 if !fragment.was_visible(&self.since, &self.undos) && fragment.visible {
1998 let mut visible_end = cursor.end(&None).visible;
1999 if fragment.id == *self.range.end.0 {
2000 visible_end = cmp::min(
2001 visible_end,
2002 cursor.start().visible + (self.range.end.1 - fragment.insertion_offset),
2003 );
2004 }
2005
2006 let fragment_summary = self.visible_cursor.summary(visible_end);
2007 let mut new_end = self.new_end.clone();
2008 new_end.add_assign(&fragment_summary);
2009 if let Some(pending_edit) = pending_edit.as_mut() {
2010 pending_edit.new.end = new_end.clone();
2011 } else {
2012 pending_edit = Some(Edit {
2013 old: self.old_end.clone()..self.old_end.clone(),
2014 new: self.new_end.clone()..new_end.clone(),
2015 });
2016 }
2017
2018 self.new_end = new_end;
2019 } else if fragment.was_visible(&self.since, &self.undos) && !fragment.visible {
2020 let mut deleted_end = cursor.end(&None).deleted;
2021 if fragment.id == *self.range.end.0 {
2022 deleted_end = cmp::min(
2023 deleted_end,
2024 cursor.start().deleted + (self.range.end.1 - fragment.insertion_offset),
2025 );
2026 }
2027
2028 if cursor.start().deleted > self.deleted_cursor.offset() {
2029 self.deleted_cursor.seek_forward(cursor.start().deleted);
2030 }
2031 let fragment_summary = self.deleted_cursor.summary(deleted_end);
2032 let mut old_end = self.old_end.clone();
2033 old_end.add_assign(&fragment_summary);
2034 if let Some(pending_edit) = pending_edit.as_mut() {
2035 pending_edit.old.end = old_end.clone();
2036 } else {
2037 pending_edit = Some(Edit {
2038 old: self.old_end.clone()..old_end.clone(),
2039 new: self.new_end.clone()..self.new_end.clone(),
2040 });
2041 }
2042
2043 self.old_end = old_end;
2044 }
2045
2046 cursor.next(&None);
2047 }
2048
2049 pending_edit
2050 }
2051}
2052
2053impl Fragment {
2054 fn is_visible(&self, undos: &UndoMap) -> bool {
2055 !undos.is_undone(self.insertion_timestamp.local())
2056 && self.deletions.iter().all(|d| undos.is_undone(*d))
2057 }
2058
2059 fn was_visible(&self, version: &clock::Global, undos: &UndoMap) -> bool {
2060 (version.observed(self.insertion_timestamp.local())
2061 && !undos.was_undone(self.insertion_timestamp.local(), version))
2062 && self
2063 .deletions
2064 .iter()
2065 .all(|d| !version.observed(*d) || undos.was_undone(*d, version))
2066 }
2067}
2068
2069impl sum_tree::Item for Fragment {
2070 type Summary = FragmentSummary;
2071
2072 fn summary(&self) -> Self::Summary {
2073 let mut max_version = clock::Global::new();
2074 max_version.observe(self.insertion_timestamp.local());
2075 for deletion in &self.deletions {
2076 max_version.observe(*deletion);
2077 }
2078 max_version.join(&self.max_undos);
2079
2080 let mut min_insertion_version = clock::Global::new();
2081 min_insertion_version.observe(self.insertion_timestamp.local());
2082 let max_insertion_version = min_insertion_version.clone();
2083 if self.visible {
2084 FragmentSummary {
2085 max_id: self.id.clone(),
2086 text: FragmentTextSummary {
2087 visible: self.len,
2088 deleted: 0,
2089 },
2090 max_version,
2091 min_insertion_version,
2092 max_insertion_version,
2093 }
2094 } else {
2095 FragmentSummary {
2096 max_id: self.id.clone(),
2097 text: FragmentTextSummary {
2098 visible: 0,
2099 deleted: self.len,
2100 },
2101 max_version,
2102 min_insertion_version,
2103 max_insertion_version,
2104 }
2105 }
2106 }
2107}
2108
2109impl sum_tree::Summary for FragmentSummary {
2110 type Context = Option<clock::Global>;
2111
2112 fn add_summary(&mut self, other: &Self, _: &Self::Context) {
2113 self.max_id.assign(&other.max_id);
2114 self.text.visible += &other.text.visible;
2115 self.text.deleted += &other.text.deleted;
2116 self.max_version.join(&other.max_version);
2117 self.min_insertion_version
2118 .meet(&other.min_insertion_version);
2119 self.max_insertion_version
2120 .join(&other.max_insertion_version);
2121 }
2122}
2123
2124impl Default for FragmentSummary {
2125 fn default() -> Self {
2126 FragmentSummary {
2127 max_id: Locator::min(),
2128 text: FragmentTextSummary::default(),
2129 max_version: clock::Global::new(),
2130 min_insertion_version: clock::Global::new(),
2131 max_insertion_version: clock::Global::new(),
2132 }
2133 }
2134}
2135
2136impl sum_tree::Item for InsertionFragment {
2137 type Summary = InsertionFragmentKey;
2138
2139 fn summary(&self) -> Self::Summary {
2140 InsertionFragmentKey {
2141 timestamp: self.timestamp,
2142 split_offset: self.split_offset,
2143 }
2144 }
2145}
2146
2147impl sum_tree::KeyedItem for InsertionFragment {
2148 type Key = InsertionFragmentKey;
2149
2150 fn key(&self) -> Self::Key {
2151 sum_tree::Item::summary(self)
2152 }
2153}
2154
2155impl InsertionFragment {
2156 fn new(fragment: &Fragment) -> Self {
2157 Self {
2158 timestamp: fragment.insertion_timestamp.local(),
2159 split_offset: fragment.insertion_offset,
2160 fragment_id: fragment.id.clone(),
2161 }
2162 }
2163
2164 fn insert_new(fragment: &Fragment) -> sum_tree::Edit<Self> {
2165 sum_tree::Edit::Insert(Self::new(fragment))
2166 }
2167}
2168
2169impl sum_tree::Summary for InsertionFragmentKey {
2170 type Context = ();
2171
2172 fn add_summary(&mut self, summary: &Self, _: &()) {
2173 *self = *summary;
2174 }
2175}
2176
2177#[derive(Copy, Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
2178pub struct FullOffset(pub usize);
2179
2180impl ops::AddAssign<usize> for FullOffset {
2181 fn add_assign(&mut self, rhs: usize) {
2182 self.0 += rhs;
2183 }
2184}
2185
2186impl ops::Add<usize> for FullOffset {
2187 type Output = Self;
2188
2189 fn add(mut self, rhs: usize) -> Self::Output {
2190 self += rhs;
2191 self
2192 }
2193}
2194
2195impl ops::Sub for FullOffset {
2196 type Output = usize;
2197
2198 fn sub(self, rhs: Self) -> Self::Output {
2199 self.0 - rhs.0
2200 }
2201}
2202
2203impl<'a> sum_tree::Dimension<'a, FragmentSummary> for usize {
2204 fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
2205 *self += summary.text.visible;
2206 }
2207}
2208
2209impl<'a> sum_tree::Dimension<'a, FragmentSummary> for FullOffset {
2210 fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
2211 self.0 += summary.text.visible + summary.text.deleted;
2212 }
2213}
2214
2215impl<'a> sum_tree::Dimension<'a, FragmentSummary> for Option<&'a Locator> {
2216 fn add_summary(&mut self, summary: &'a FragmentSummary, _: &Option<clock::Global>) {
2217 *self = Some(&summary.max_id);
2218 }
2219}
2220
2221impl<'a> sum_tree::SeekTarget<'a, FragmentSummary, FragmentTextSummary> for usize {
2222 fn cmp(
2223 &self,
2224 cursor_location: &FragmentTextSummary,
2225 _: &Option<clock::Global>,
2226 ) -> cmp::Ordering {
2227 Ord::cmp(self, &cursor_location.visible)
2228 }
2229}
2230
2231#[derive(Copy, Clone, Debug, Eq, PartialEq)]
2232enum VersionedFullOffset {
2233 Offset(FullOffset),
2234 Invalid,
2235}
2236
2237impl VersionedFullOffset {
2238 fn full_offset(&self) -> FullOffset {
2239 if let Self::Offset(position) = self {
2240 *position
2241 } else {
2242 panic!("invalid version")
2243 }
2244 }
2245}
2246
2247impl Default for VersionedFullOffset {
2248 fn default() -> Self {
2249 Self::Offset(Default::default())
2250 }
2251}
2252
2253impl<'a> sum_tree::Dimension<'a, FragmentSummary> for VersionedFullOffset {
2254 fn add_summary(&mut self, summary: &'a FragmentSummary, cx: &Option<clock::Global>) {
2255 if let Self::Offset(offset) = self {
2256 let version = cx.as_ref().unwrap();
2257 if version.observed_all(&summary.max_insertion_version) {
2258 *offset += summary.text.visible + summary.text.deleted;
2259 } else if version.observed_any(&summary.min_insertion_version) {
2260 *self = Self::Invalid;
2261 }
2262 }
2263 }
2264}
2265
2266impl<'a> sum_tree::SeekTarget<'a, FragmentSummary, Self> for VersionedFullOffset {
2267 fn cmp(&self, cursor_position: &Self, _: &Option<clock::Global>) -> cmp::Ordering {
2268 match (self, cursor_position) {
2269 (Self::Offset(a), Self::Offset(b)) => Ord::cmp(a, b),
2270 (Self::Offset(_), Self::Invalid) => cmp::Ordering::Less,
2271 (Self::Invalid, _) => unreachable!(),
2272 }
2273 }
2274}
2275
2276impl Operation {
2277 fn replica_id(&self) -> ReplicaId {
2278 operation_queue::Operation::lamport_timestamp(self).replica_id
2279 }
2280
2281 pub fn local_timestamp(&self) -> clock::Local {
2282 match self {
2283 Operation::Edit(edit) => edit.timestamp.local(),
2284 Operation::Undo { undo, .. } => undo.id,
2285 }
2286 }
2287
2288 pub fn as_edit(&self) -> Option<&EditOperation> {
2289 match self {
2290 Operation::Edit(edit) => Some(edit),
2291 _ => None,
2292 }
2293 }
2294
2295 pub fn is_edit(&self) -> bool {
2296 match self {
2297 Operation::Edit { .. } => true,
2298 _ => false,
2299 }
2300 }
2301}
2302
2303impl operation_queue::Operation for Operation {
2304 fn lamport_timestamp(&self) -> clock::Lamport {
2305 match self {
2306 Operation::Edit(edit) => edit.timestamp.lamport(),
2307 Operation::Undo {
2308 lamport_timestamp, ..
2309 } => *lamport_timestamp,
2310 }
2311 }
2312}
2313
2314pub trait ToOffset {
2315 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize;
2316}
2317
2318impl ToOffset for Point {
2319 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2320 snapshot.point_to_offset(*self)
2321 }
2322}
2323
2324impl ToOffset for PointUtf16 {
2325 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2326 snapshot.point_utf16_to_offset(*self)
2327 }
2328}
2329
2330impl ToOffset for usize {
2331 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2332 assert!(*self <= snapshot.len(), "offset is out of range");
2333 *self
2334 }
2335}
2336
2337impl ToOffset for Anchor {
2338 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2339 snapshot.summary_for_anchor(self)
2340 }
2341}
2342
2343impl<'a, T: ToOffset> ToOffset for &'a T {
2344 fn to_offset(&self, content: &BufferSnapshot) -> usize {
2345 (*self).to_offset(content)
2346 }
2347}
2348
2349pub trait ToPoint {
2350 fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point;
2351}
2352
2353impl ToPoint for Anchor {
2354 fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point {
2355 snapshot.summary_for_anchor(self)
2356 }
2357}
2358
2359impl ToPoint for usize {
2360 fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point {
2361 snapshot.offset_to_point(*self)
2362 }
2363}
2364
2365impl ToPoint for PointUtf16 {
2366 fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point {
2367 snapshot.point_utf16_to_point(*self)
2368 }
2369}
2370
2371impl ToPoint for Point {
2372 fn to_point<'a>(&self, _: &BufferSnapshot) -> Point {
2373 *self
2374 }
2375}
2376
2377pub trait ToPointUtf16 {
2378 fn to_point_utf16<'a>(&self, snapshot: &BufferSnapshot) -> PointUtf16;
2379}
2380
2381impl ToPointUtf16 for Anchor {
2382 fn to_point_utf16<'a>(&self, snapshot: &BufferSnapshot) -> PointUtf16 {
2383 snapshot.summary_for_anchor(self)
2384 }
2385}
2386
2387impl ToPointUtf16 for usize {
2388 fn to_point_utf16<'a>(&self, snapshot: &BufferSnapshot) -> PointUtf16 {
2389 snapshot.offset_to_point_utf16(*self)
2390 }
2391}
2392
2393impl ToPointUtf16 for PointUtf16 {
2394 fn to_point_utf16<'a>(&self, _: &BufferSnapshot) -> PointUtf16 {
2395 *self
2396 }
2397}
2398
2399impl ToPointUtf16 for Point {
2400 fn to_point_utf16<'a>(&self, snapshot: &BufferSnapshot) -> PointUtf16 {
2401 snapshot.point_to_point_utf16(*self)
2402 }
2403}
2404
2405pub trait Clip {
2406 fn clip(&self, bias: Bias, snapshot: &BufferSnapshot) -> Self;
2407}
2408
2409impl Clip for usize {
2410 fn clip(&self, bias: Bias, snapshot: &BufferSnapshot) -> Self {
2411 snapshot.clip_offset(*self, bias)
2412 }
2413}
2414
2415impl Clip for Point {
2416 fn clip(&self, bias: Bias, snapshot: &BufferSnapshot) -> Self {
2417 snapshot.clip_point(*self, bias)
2418 }
2419}
2420
2421impl Clip for PointUtf16 {
2422 fn clip(&self, bias: Bias, snapshot: &BufferSnapshot) -> Self {
2423 snapshot.clip_point_utf16(*self, bias)
2424 }
2425}
2426
2427pub trait FromAnchor {
2428 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self;
2429}
2430
2431impl FromAnchor for Point {
2432 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
2433 snapshot.summary_for_anchor(anchor)
2434 }
2435}
2436
2437impl FromAnchor for PointUtf16 {
2438 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
2439 snapshot.summary_for_anchor(anchor)
2440 }
2441}
2442
2443impl FromAnchor for usize {
2444 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
2445 snapshot.summary_for_anchor(anchor)
2446 }
2447}