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