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