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