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