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