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)]
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 remote_id,
575 visible_text,
576 deleted_text: Rope::new(),
577 fragments,
578 insertions,
579 version,
580 undo_map: Default::default(),
581 },
582 history,
583 deferred_ops: OperationQueue::new(),
584 deferred_replicas: HashSet::default(),
585 replica_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 buffer_id: Some(self.remote_id),
1809 }
1810 }
1811 }
1812
1813 pub fn can_resolve(&self, anchor: &Anchor) -> bool {
1814 *anchor == Anchor::MIN
1815 || *anchor == Anchor::MAX
1816 || (Some(self.remote_id) == anchor.buffer_id && self.version.observed(anchor.timestamp))
1817 }
1818
1819 pub fn clip_offset(&self, offset: usize, bias: Bias) -> usize {
1820 self.visible_text.clip_offset(offset, bias)
1821 }
1822
1823 pub fn clip_point(&self, point: Point, bias: Bias) -> Point {
1824 self.visible_text.clip_point(point, bias)
1825 }
1826
1827 pub fn clip_point_utf16(&self, point: PointUtf16, bias: Bias) -> PointUtf16 {
1828 self.visible_text.clip_point_utf16(point, bias)
1829 }
1830
1831 pub fn edits_since<'a, D>(
1832 &'a self,
1833 since: &'a clock::Global,
1834 ) -> impl 'a + Iterator<Item = Edit<D>>
1835 where
1836 D: TextDimension + Ord,
1837 {
1838 self.edits_since_in_range(since, Anchor::MIN..Anchor::MAX)
1839 }
1840
1841 pub fn edited_ranges_for_transaction<'a, D>(
1842 &'a self,
1843 transaction: &'a Transaction,
1844 ) -> impl 'a + Iterator<Item = Range<D>>
1845 where
1846 D: TextDimension,
1847 {
1848 let mut cursor = self.fragments.cursor::<(VersionedFullOffset, usize)>();
1849 let mut rope_cursor = self.visible_text.cursor(0);
1850 let cx = Some(transaction.end.clone());
1851 let mut position = D::default();
1852 transaction.ranges.iter().map(move |range| {
1853 cursor.seek_forward(&VersionedFullOffset::Offset(range.start), Bias::Right, &cx);
1854 let mut start_offset = cursor.start().1;
1855 if cursor
1856 .item()
1857 .map_or(false, |fragment| fragment.is_visible(&self.undo_map))
1858 {
1859 start_offset += range.start - cursor.start().0.full_offset()
1860 }
1861 position.add_assign(&rope_cursor.summary(start_offset));
1862 let start = position.clone();
1863
1864 cursor.seek_forward(&VersionedFullOffset::Offset(range.end), Bias::Left, &cx);
1865 let mut end_offset = cursor.start().1;
1866 if cursor
1867 .item()
1868 .map_or(false, |fragment| fragment.is_visible(&self.undo_map))
1869 {
1870 end_offset += range.end - cursor.start().0.full_offset();
1871 }
1872 position.add_assign(&rope_cursor.summary(end_offset));
1873 start..position.clone()
1874 })
1875 }
1876
1877 pub fn edits_since_in_range<'a, D>(
1878 &'a self,
1879 since: &'a clock::Global,
1880 range: Range<Anchor>,
1881 ) -> impl 'a + Iterator<Item = Edit<D>>
1882 where
1883 D: TextDimension + Ord,
1884 {
1885 let fragments_cursor = if *since == self.version {
1886 None
1887 } else {
1888 let mut cursor = self
1889 .fragments
1890 .filter(move |summary| !since.observed_all(&summary.max_version));
1891 cursor.next(&None);
1892 Some(cursor)
1893 };
1894 let mut cursor = self
1895 .fragments
1896 .cursor::<(Option<&Locator>, FragmentTextSummary)>();
1897
1898 let start_fragment_id = self.fragment_id_for_anchor(&range.start);
1899 cursor.seek(&Some(start_fragment_id), Bias::Left, &None);
1900 let mut visible_start = cursor.start().1.visible;
1901 let mut deleted_start = cursor.start().1.deleted;
1902 if let Some(fragment) = cursor.item() {
1903 let overshoot = range.start.offset - fragment.insertion_offset;
1904 if fragment.visible {
1905 visible_start += overshoot;
1906 } else {
1907 deleted_start += overshoot;
1908 }
1909 }
1910 let end_fragment_id = self.fragment_id_for_anchor(&range.end);
1911
1912 Edits {
1913 visible_cursor: self.visible_text.cursor(visible_start),
1914 deleted_cursor: self.deleted_text.cursor(deleted_start),
1915 fragments_cursor,
1916 undos: &self.undo_map,
1917 since,
1918 old_end: Default::default(),
1919 new_end: Default::default(),
1920 range: (start_fragment_id, range.start.offset)..(end_fragment_id, range.end.offset),
1921 }
1922 }
1923}
1924
1925struct RopeBuilder<'a> {
1926 old_visible_cursor: rope::Cursor<'a>,
1927 old_deleted_cursor: rope::Cursor<'a>,
1928 new_visible: Rope,
1929 new_deleted: Rope,
1930}
1931
1932impl<'a> RopeBuilder<'a> {
1933 fn new(old_visible_cursor: rope::Cursor<'a>, old_deleted_cursor: rope::Cursor<'a>) -> Self {
1934 Self {
1935 old_visible_cursor,
1936 old_deleted_cursor,
1937 new_visible: Rope::new(),
1938 new_deleted: Rope::new(),
1939 }
1940 }
1941
1942 fn push_tree(&mut self, len: FragmentTextSummary) {
1943 self.push(len.visible, true, true);
1944 self.push(len.deleted, false, false);
1945 }
1946
1947 fn push_fragment(&mut self, fragment: &Fragment, was_visible: bool) {
1948 debug_assert!(fragment.len > 0);
1949 self.push(fragment.len, was_visible, fragment.visible)
1950 }
1951
1952 fn push(&mut self, len: usize, was_visible: bool, is_visible: bool) {
1953 let text = if was_visible {
1954 self.old_visible_cursor
1955 .slice(self.old_visible_cursor.offset() + len)
1956 } else {
1957 self.old_deleted_cursor
1958 .slice(self.old_deleted_cursor.offset() + len)
1959 };
1960 if is_visible {
1961 self.new_visible.append(text);
1962 } else {
1963 self.new_deleted.append(text);
1964 }
1965 }
1966
1967 fn push_str(&mut self, text: &str) {
1968 self.new_visible.push(text);
1969 }
1970
1971 fn finish(mut self) -> (Rope, Rope) {
1972 self.new_visible.append(self.old_visible_cursor.suffix());
1973 self.new_deleted.append(self.old_deleted_cursor.suffix());
1974 (self.new_visible, self.new_deleted)
1975 }
1976}
1977
1978impl<'a, D: TextDimension + Ord, F: FnMut(&FragmentSummary) -> bool> Iterator for Edits<'a, D, F> {
1979 type Item = Edit<D>;
1980
1981 fn next(&mut self) -> Option<Self::Item> {
1982 let mut pending_edit: Option<Edit<D>> = None;
1983 let cursor = self.fragments_cursor.as_mut()?;
1984
1985 while let Some(fragment) = cursor.item() {
1986 if fragment.id < *self.range.start.0 {
1987 cursor.next(&None);
1988 continue;
1989 } else if fragment.id > *self.range.end.0 {
1990 break;
1991 }
1992
1993 if cursor.start().visible > self.visible_cursor.offset() {
1994 let summary = self.visible_cursor.summary(cursor.start().visible);
1995 self.old_end.add_assign(&summary);
1996 self.new_end.add_assign(&summary);
1997 }
1998
1999 if pending_edit
2000 .as_ref()
2001 .map_or(false, |change| change.new.end < self.new_end)
2002 {
2003 break;
2004 }
2005
2006 if !fragment.was_visible(&self.since, &self.undos) && fragment.visible {
2007 let mut visible_end = cursor.end(&None).visible;
2008 if fragment.id == *self.range.end.0 {
2009 visible_end = cmp::min(
2010 visible_end,
2011 cursor.start().visible + (self.range.end.1 - fragment.insertion_offset),
2012 );
2013 }
2014
2015 let fragment_summary = self.visible_cursor.summary(visible_end);
2016 let mut new_end = self.new_end.clone();
2017 new_end.add_assign(&fragment_summary);
2018 if let Some(pending_edit) = pending_edit.as_mut() {
2019 pending_edit.new.end = new_end.clone();
2020 } else {
2021 pending_edit = Some(Edit {
2022 old: self.old_end.clone()..self.old_end.clone(),
2023 new: self.new_end.clone()..new_end.clone(),
2024 });
2025 }
2026
2027 self.new_end = new_end;
2028 } else if fragment.was_visible(&self.since, &self.undos) && !fragment.visible {
2029 let mut deleted_end = cursor.end(&None).deleted;
2030 if fragment.id == *self.range.end.0 {
2031 deleted_end = cmp::min(
2032 deleted_end,
2033 cursor.start().deleted + (self.range.end.1 - fragment.insertion_offset),
2034 );
2035 }
2036
2037 if cursor.start().deleted > self.deleted_cursor.offset() {
2038 self.deleted_cursor.seek_forward(cursor.start().deleted);
2039 }
2040 let fragment_summary = self.deleted_cursor.summary(deleted_end);
2041 let mut old_end = self.old_end.clone();
2042 old_end.add_assign(&fragment_summary);
2043 if let Some(pending_edit) = pending_edit.as_mut() {
2044 pending_edit.old.end = old_end.clone();
2045 } else {
2046 pending_edit = Some(Edit {
2047 old: self.old_end.clone()..old_end.clone(),
2048 new: self.new_end.clone()..self.new_end.clone(),
2049 });
2050 }
2051
2052 self.old_end = old_end;
2053 }
2054
2055 cursor.next(&None);
2056 }
2057
2058 pending_edit
2059 }
2060}
2061
2062impl Fragment {
2063 fn is_visible(&self, undos: &UndoMap) -> bool {
2064 !undos.is_undone(self.insertion_timestamp.local())
2065 && self.deletions.iter().all(|d| undos.is_undone(*d))
2066 }
2067
2068 fn was_visible(&self, version: &clock::Global, undos: &UndoMap) -> bool {
2069 (version.observed(self.insertion_timestamp.local())
2070 && !undos.was_undone(self.insertion_timestamp.local(), version))
2071 && self
2072 .deletions
2073 .iter()
2074 .all(|d| !version.observed(*d) || undos.was_undone(*d, version))
2075 }
2076}
2077
2078impl sum_tree::Item for Fragment {
2079 type Summary = FragmentSummary;
2080
2081 fn summary(&self) -> Self::Summary {
2082 let mut max_version = clock::Global::new();
2083 max_version.observe(self.insertion_timestamp.local());
2084 for deletion in &self.deletions {
2085 max_version.observe(*deletion);
2086 }
2087 max_version.join(&self.max_undos);
2088
2089 let mut min_insertion_version = clock::Global::new();
2090 min_insertion_version.observe(self.insertion_timestamp.local());
2091 let max_insertion_version = min_insertion_version.clone();
2092 if self.visible {
2093 FragmentSummary {
2094 max_id: self.id.clone(),
2095 text: FragmentTextSummary {
2096 visible: self.len,
2097 deleted: 0,
2098 },
2099 max_version,
2100 min_insertion_version,
2101 max_insertion_version,
2102 }
2103 } else {
2104 FragmentSummary {
2105 max_id: self.id.clone(),
2106 text: FragmentTextSummary {
2107 visible: 0,
2108 deleted: self.len,
2109 },
2110 max_version,
2111 min_insertion_version,
2112 max_insertion_version,
2113 }
2114 }
2115 }
2116}
2117
2118impl sum_tree::Summary for FragmentSummary {
2119 type Context = Option<clock::Global>;
2120
2121 fn add_summary(&mut self, other: &Self, _: &Self::Context) {
2122 self.max_id.assign(&other.max_id);
2123 self.text.visible += &other.text.visible;
2124 self.text.deleted += &other.text.deleted;
2125 self.max_version.join(&other.max_version);
2126 self.min_insertion_version
2127 .meet(&other.min_insertion_version);
2128 self.max_insertion_version
2129 .join(&other.max_insertion_version);
2130 }
2131}
2132
2133impl Default for FragmentSummary {
2134 fn default() -> Self {
2135 FragmentSummary {
2136 max_id: Locator::min(),
2137 text: FragmentTextSummary::default(),
2138 max_version: clock::Global::new(),
2139 min_insertion_version: clock::Global::new(),
2140 max_insertion_version: clock::Global::new(),
2141 }
2142 }
2143}
2144
2145impl sum_tree::Item for InsertionFragment {
2146 type Summary = InsertionFragmentKey;
2147
2148 fn summary(&self) -> Self::Summary {
2149 InsertionFragmentKey {
2150 timestamp: self.timestamp,
2151 split_offset: self.split_offset,
2152 }
2153 }
2154}
2155
2156impl sum_tree::KeyedItem for InsertionFragment {
2157 type Key = InsertionFragmentKey;
2158
2159 fn key(&self) -> Self::Key {
2160 sum_tree::Item::summary(self)
2161 }
2162}
2163
2164impl InsertionFragment {
2165 fn new(fragment: &Fragment) -> Self {
2166 Self {
2167 timestamp: fragment.insertion_timestamp.local(),
2168 split_offset: fragment.insertion_offset,
2169 fragment_id: fragment.id.clone(),
2170 }
2171 }
2172
2173 fn insert_new(fragment: &Fragment) -> sum_tree::Edit<Self> {
2174 sum_tree::Edit::Insert(Self::new(fragment))
2175 }
2176}
2177
2178impl sum_tree::Summary for InsertionFragmentKey {
2179 type Context = ();
2180
2181 fn add_summary(&mut self, summary: &Self, _: &()) {
2182 *self = *summary;
2183 }
2184}
2185
2186#[derive(Copy, Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
2187pub struct FullOffset(pub usize);
2188
2189impl ops::AddAssign<usize> for FullOffset {
2190 fn add_assign(&mut self, rhs: usize) {
2191 self.0 += rhs;
2192 }
2193}
2194
2195impl ops::Add<usize> for FullOffset {
2196 type Output = Self;
2197
2198 fn add(mut self, rhs: usize) -> Self::Output {
2199 self += rhs;
2200 self
2201 }
2202}
2203
2204impl ops::Sub for FullOffset {
2205 type Output = usize;
2206
2207 fn sub(self, rhs: Self) -> Self::Output {
2208 self.0 - rhs.0
2209 }
2210}
2211
2212impl<'a> sum_tree::Dimension<'a, FragmentSummary> for usize {
2213 fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
2214 *self += summary.text.visible;
2215 }
2216}
2217
2218impl<'a> sum_tree::Dimension<'a, FragmentSummary> for FullOffset {
2219 fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
2220 self.0 += summary.text.visible + summary.text.deleted;
2221 }
2222}
2223
2224impl<'a> sum_tree::Dimension<'a, FragmentSummary> for Option<&'a Locator> {
2225 fn add_summary(&mut self, summary: &'a FragmentSummary, _: &Option<clock::Global>) {
2226 *self = Some(&summary.max_id);
2227 }
2228}
2229
2230impl<'a> sum_tree::SeekTarget<'a, FragmentSummary, FragmentTextSummary> for usize {
2231 fn cmp(
2232 &self,
2233 cursor_location: &FragmentTextSummary,
2234 _: &Option<clock::Global>,
2235 ) -> cmp::Ordering {
2236 Ord::cmp(self, &cursor_location.visible)
2237 }
2238}
2239
2240#[derive(Copy, Clone, Debug, Eq, PartialEq)]
2241enum VersionedFullOffset {
2242 Offset(FullOffset),
2243 Invalid,
2244}
2245
2246impl VersionedFullOffset {
2247 fn full_offset(&self) -> FullOffset {
2248 if let Self::Offset(position) = self {
2249 *position
2250 } else {
2251 panic!("invalid version")
2252 }
2253 }
2254}
2255
2256impl Default for VersionedFullOffset {
2257 fn default() -> Self {
2258 Self::Offset(Default::default())
2259 }
2260}
2261
2262impl<'a> sum_tree::Dimension<'a, FragmentSummary> for VersionedFullOffset {
2263 fn add_summary(&mut self, summary: &'a FragmentSummary, cx: &Option<clock::Global>) {
2264 if let Self::Offset(offset) = self {
2265 let version = cx.as_ref().unwrap();
2266 if version.observed_all(&summary.max_insertion_version) {
2267 *offset += summary.text.visible + summary.text.deleted;
2268 } else if version.observed_any(&summary.min_insertion_version) {
2269 *self = Self::Invalid;
2270 }
2271 }
2272 }
2273}
2274
2275impl<'a> sum_tree::SeekTarget<'a, FragmentSummary, Self> for VersionedFullOffset {
2276 fn cmp(&self, cursor_position: &Self, _: &Option<clock::Global>) -> cmp::Ordering {
2277 match (self, cursor_position) {
2278 (Self::Offset(a), Self::Offset(b)) => Ord::cmp(a, b),
2279 (Self::Offset(_), Self::Invalid) => cmp::Ordering::Less,
2280 (Self::Invalid, _) => unreachable!(),
2281 }
2282 }
2283}
2284
2285impl Operation {
2286 fn replica_id(&self) -> ReplicaId {
2287 operation_queue::Operation::lamport_timestamp(self).replica_id
2288 }
2289
2290 pub fn local_timestamp(&self) -> clock::Local {
2291 match self {
2292 Operation::Edit(edit) => edit.timestamp.local(),
2293 Operation::Undo { undo, .. } => undo.id,
2294 }
2295 }
2296
2297 pub fn as_edit(&self) -> Option<&EditOperation> {
2298 match self {
2299 Operation::Edit(edit) => Some(edit),
2300 _ => None,
2301 }
2302 }
2303
2304 pub fn is_edit(&self) -> bool {
2305 match self {
2306 Operation::Edit { .. } => true,
2307 _ => false,
2308 }
2309 }
2310}
2311
2312impl operation_queue::Operation for Operation {
2313 fn lamport_timestamp(&self) -> clock::Lamport {
2314 match self {
2315 Operation::Edit(edit) => edit.timestamp.lamport(),
2316 Operation::Undo {
2317 lamport_timestamp, ..
2318 } => *lamport_timestamp,
2319 }
2320 }
2321}
2322
2323pub trait ToOffset {
2324 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize;
2325}
2326
2327impl ToOffset for Point {
2328 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2329 snapshot.point_to_offset(*self)
2330 }
2331}
2332
2333impl ToOffset for PointUtf16 {
2334 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2335 snapshot.point_utf16_to_offset(*self)
2336 }
2337}
2338
2339impl ToOffset for usize {
2340 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2341 assert!(*self <= snapshot.len(), "offset is out of range");
2342 *self
2343 }
2344}
2345
2346impl ToOffset for Anchor {
2347 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2348 snapshot.summary_for_anchor(self)
2349 }
2350}
2351
2352impl<'a, T: ToOffset> ToOffset for &'a T {
2353 fn to_offset(&self, content: &BufferSnapshot) -> usize {
2354 (*self).to_offset(content)
2355 }
2356}
2357
2358pub trait ToPoint {
2359 fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point;
2360}
2361
2362impl ToPoint for Anchor {
2363 fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point {
2364 snapshot.summary_for_anchor(self)
2365 }
2366}
2367
2368impl ToPoint for usize {
2369 fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point {
2370 snapshot.offset_to_point(*self)
2371 }
2372}
2373
2374impl ToPoint for PointUtf16 {
2375 fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point {
2376 snapshot.point_utf16_to_point(*self)
2377 }
2378}
2379
2380impl ToPoint for Point {
2381 fn to_point<'a>(&self, _: &BufferSnapshot) -> Point {
2382 *self
2383 }
2384}
2385
2386pub trait ToPointUtf16 {
2387 fn to_point_utf16<'a>(&self, snapshot: &BufferSnapshot) -> PointUtf16;
2388}
2389
2390impl ToPointUtf16 for Anchor {
2391 fn to_point_utf16<'a>(&self, snapshot: &BufferSnapshot) -> PointUtf16 {
2392 snapshot.summary_for_anchor(self)
2393 }
2394}
2395
2396impl ToPointUtf16 for usize {
2397 fn to_point_utf16<'a>(&self, snapshot: &BufferSnapshot) -> PointUtf16 {
2398 snapshot.offset_to_point_utf16(*self)
2399 }
2400}
2401
2402impl ToPointUtf16 for PointUtf16 {
2403 fn to_point_utf16<'a>(&self, _: &BufferSnapshot) -> PointUtf16 {
2404 *self
2405 }
2406}
2407
2408impl ToPointUtf16 for Point {
2409 fn to_point_utf16<'a>(&self, snapshot: &BufferSnapshot) -> PointUtf16 {
2410 snapshot.point_to_point_utf16(*self)
2411 }
2412}
2413
2414pub trait Clip {
2415 fn clip(&self, bias: Bias, snapshot: &BufferSnapshot) -> Self;
2416}
2417
2418impl Clip for usize {
2419 fn clip(&self, bias: Bias, snapshot: &BufferSnapshot) -> Self {
2420 snapshot.clip_offset(*self, bias)
2421 }
2422}
2423
2424impl Clip for Point {
2425 fn clip(&self, bias: Bias, snapshot: &BufferSnapshot) -> Self {
2426 snapshot.clip_point(*self, bias)
2427 }
2428}
2429
2430impl Clip for PointUtf16 {
2431 fn clip(&self, bias: Bias, snapshot: &BufferSnapshot) -> Self {
2432 snapshot.clip_point_utf16(*self, bias)
2433 }
2434}
2435
2436pub trait FromAnchor {
2437 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self;
2438}
2439
2440impl FromAnchor for Point {
2441 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
2442 snapshot.summary_for_anchor(anchor)
2443 }
2444}
2445
2446impl FromAnchor for PointUtf16 {
2447 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
2448 snapshot.summary_for_anchor(anchor)
2449 }
2450}
2451
2452impl FromAnchor for usize {
2453 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
2454 snapshot.summary_for_anchor(anchor)
2455 }
2456}