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