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 bytes_in_range<'a, T: ToOffset>(&'a self, range: Range<T>) -> rope::Bytes<'a> {
1336 let start = range.start.to_offset(self);
1337 let end = range.end.to_offset(self);
1338 self.visible_text.bytes_in_range(start..end)
1339 }
1340
1341 pub fn text_for_range<'a, T: ToOffset>(&'a self, range: Range<T>) -> Chunks<'a> {
1342 let start = range.start.to_offset(self);
1343 let end = range.end.to_offset(self);
1344 self.visible_text.chunks_in_range(start..end)
1345 }
1346
1347 pub fn line_len(&self, row: u32) -> u32 {
1348 let row_start_offset = Point::new(row, 0).to_offset(self);
1349 let row_end_offset = if row >= self.max_point().row {
1350 self.len()
1351 } else {
1352 Point::new(row + 1, 0).to_offset(self) - 1
1353 };
1354 (row_end_offset - row_start_offset) as u32
1355 }
1356
1357 pub fn is_line_blank(&self, row: u32) -> bool {
1358 self.text_for_range(Point::new(row, 0)..Point::new(row, self.line_len(row)))
1359 .all(|chunk| chunk.matches(|c: char| !c.is_whitespace()).next().is_none())
1360 }
1361
1362 pub fn indent_column_for_line(&self, row: u32) -> u32 {
1363 let mut result = 0;
1364 for c in self.chars_at(Point::new(row, 0)) {
1365 if c == ' ' {
1366 result += 1;
1367 } else {
1368 break;
1369 }
1370 }
1371 result
1372 }
1373
1374 pub fn text_summary_for_range<'a, D, O: ToOffset>(&'a self, range: Range<O>) -> D
1375 where
1376 D: TextDimension,
1377 {
1378 self.visible_text
1379 .cursor(range.start.to_offset(self))
1380 .summary(range.end.to_offset(self))
1381 }
1382
1383 pub fn summaries_for_anchors<'a, D, A>(&'a self, anchors: A) -> impl 'a + Iterator<Item = D>
1384 where
1385 D: 'a + TextDimension,
1386 A: 'a + IntoIterator<Item = &'a Anchor>,
1387 {
1388 let anchors = anchors.into_iter();
1389 let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>();
1390 let mut fragment_cursor = self.fragments.cursor::<(Option<&Locator>, usize)>();
1391 let mut text_cursor = self.visible_text.cursor(0);
1392 let mut position = D::default();
1393
1394 anchors.map(move |anchor| {
1395 if *anchor == Anchor::min() {
1396 return D::default();
1397 } else if *anchor == Anchor::max() {
1398 return D::from_text_summary(&self.visible_text.summary());
1399 }
1400
1401 let anchor_key = InsertionFragmentKey {
1402 timestamp: anchor.timestamp,
1403 split_offset: anchor.offset,
1404 };
1405 insertion_cursor.seek(&anchor_key, anchor.bias, &());
1406 if let Some(insertion) = insertion_cursor.item() {
1407 let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
1408 if comparison == Ordering::Greater
1409 || (anchor.bias == Bias::Left
1410 && comparison == Ordering::Equal
1411 && anchor.offset > 0)
1412 {
1413 insertion_cursor.prev(&());
1414 }
1415 } else {
1416 insertion_cursor.prev(&());
1417 }
1418 let insertion = insertion_cursor.item().expect("invalid insertion");
1419 debug_assert_eq!(insertion.timestamp, anchor.timestamp, "invalid insertion");
1420
1421 fragment_cursor.seek_forward(&Some(&insertion.fragment_id), Bias::Left, &None);
1422 let fragment = fragment_cursor.item().unwrap();
1423 let mut fragment_offset = fragment_cursor.start().1;
1424 if fragment.visible {
1425 fragment_offset += anchor.offset - insertion.split_offset;
1426 }
1427
1428 position.add_assign(&text_cursor.summary(fragment_offset));
1429 position.clone()
1430 })
1431 }
1432
1433 fn summary_for_anchor<'a, D>(&'a self, anchor: &Anchor) -> D
1434 where
1435 D: TextDimension,
1436 {
1437 if *anchor == Anchor::min() {
1438 D::default()
1439 } else if *anchor == Anchor::max() {
1440 D::from_text_summary(&self.visible_text.summary())
1441 } else {
1442 let anchor_key = InsertionFragmentKey {
1443 timestamp: anchor.timestamp,
1444 split_offset: anchor.offset,
1445 };
1446 let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>();
1447 insertion_cursor.seek(&anchor_key, anchor.bias, &());
1448 if let Some(insertion) = insertion_cursor.item() {
1449 let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
1450 if comparison == Ordering::Greater
1451 || (anchor.bias == Bias::Left
1452 && comparison == Ordering::Equal
1453 && anchor.offset > 0)
1454 {
1455 insertion_cursor.prev(&());
1456 }
1457 } else {
1458 insertion_cursor.prev(&());
1459 }
1460 let insertion = insertion_cursor.item().expect("invalid insertion");
1461 debug_assert_eq!(insertion.timestamp, anchor.timestamp, "invalid insertion");
1462
1463 let mut fragment_cursor = self.fragments.cursor::<(Option<&Locator>, usize)>();
1464 fragment_cursor.seek(&Some(&insertion.fragment_id), Bias::Left, &None);
1465 let fragment = fragment_cursor.item().unwrap();
1466 let mut fragment_offset = fragment_cursor.start().1;
1467 if fragment.visible {
1468 fragment_offset += anchor.offset - insertion.split_offset;
1469 }
1470 self.text_summary_for_range(0..fragment_offset)
1471 }
1472 }
1473
1474 fn fragment_id_for_anchor(&self, anchor: &Anchor) -> &Locator {
1475 if *anchor == Anchor::min() {
1476 &locator::MIN
1477 } else if *anchor == Anchor::max() {
1478 &locator::MAX
1479 } else {
1480 let anchor_key = InsertionFragmentKey {
1481 timestamp: anchor.timestamp,
1482 split_offset: anchor.offset,
1483 };
1484 let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>();
1485 insertion_cursor.seek(&anchor_key, anchor.bias, &());
1486 if let Some(insertion) = insertion_cursor.item() {
1487 let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
1488 if comparison == Ordering::Greater
1489 || (anchor.bias == Bias::Left
1490 && comparison == Ordering::Equal
1491 && anchor.offset > 0)
1492 {
1493 insertion_cursor.prev(&());
1494 }
1495 } else {
1496 insertion_cursor.prev(&());
1497 }
1498 let insertion = insertion_cursor.item().expect("invalid insertion");
1499 debug_assert_eq!(insertion.timestamp, anchor.timestamp, "invalid insertion");
1500 &insertion.fragment_id
1501 }
1502 }
1503
1504 pub fn anchor_before<T: ToOffset>(&self, position: T) -> Anchor {
1505 self.anchor_at(position, Bias::Left)
1506 }
1507
1508 pub fn anchor_after<T: ToOffset>(&self, position: T) -> Anchor {
1509 self.anchor_at(position, Bias::Right)
1510 }
1511
1512 pub fn anchor_at<T: ToOffset>(&self, position: T, bias: Bias) -> Anchor {
1513 let offset = position.to_offset(self);
1514 if bias == Bias::Left && offset == 0 {
1515 Anchor::min()
1516 } else if bias == Bias::Right && offset == self.len() {
1517 Anchor::max()
1518 } else {
1519 let mut fragment_cursor = self.fragments.cursor::<usize>();
1520 fragment_cursor.seek(&offset, bias, &None);
1521 let fragment = fragment_cursor.item().unwrap();
1522 let overshoot = offset - *fragment_cursor.start();
1523 Anchor {
1524 timestamp: fragment.insertion_timestamp.local(),
1525 offset: fragment.insertion_offset + overshoot,
1526 bias,
1527 }
1528 }
1529 }
1530
1531 pub fn clip_offset(&self, offset: usize, bias: Bias) -> usize {
1532 self.visible_text.clip_offset(offset, bias)
1533 }
1534
1535 pub fn clip_point(&self, point: Point, bias: Bias) -> Point {
1536 self.visible_text.clip_point(point, bias)
1537 }
1538
1539 pub fn clip_point_utf16(&self, point: PointUtf16, bias: Bias) -> PointUtf16 {
1540 self.visible_text.clip_point_utf16(point, bias)
1541 }
1542
1543 // pub fn point_for_offset(&self, offset: usize) -> Result<Point> {
1544 // if offset <= self.len() {
1545 // Ok(self.text_summary_for_range(0..offset))
1546 // } else {
1547 // Err(anyhow!("offset out of bounds"))
1548 // }
1549 // }
1550
1551 pub fn edits_since<'a, D>(
1552 &'a self,
1553 since: &'a clock::Global,
1554 ) -> impl 'a + Iterator<Item = Edit<D>>
1555 where
1556 D: TextDimension + Ord,
1557 {
1558 self.edits_since_in_range(since, Anchor::min()..Anchor::max())
1559 }
1560
1561 pub fn edits_since_in_range<'a, D>(
1562 &'a self,
1563 since: &'a clock::Global,
1564 range: Range<Anchor>,
1565 ) -> impl 'a + Iterator<Item = Edit<D>>
1566 where
1567 D: TextDimension + Ord,
1568 {
1569 let fragments_cursor = if *since == self.version {
1570 None
1571 } else {
1572 Some(
1573 self.fragments
1574 .filter(move |summary| !since.ge(&summary.max_version), &None),
1575 )
1576 };
1577 let mut cursor = self
1578 .fragments
1579 .cursor::<(Option<&Locator>, FragmentTextSummary)>();
1580
1581 let start_fragment_id = self.fragment_id_for_anchor(&range.start);
1582 cursor.seek(&Some(start_fragment_id), Bias::Left, &None);
1583 let mut visible_start = cursor.start().1.visible;
1584 let mut deleted_start = cursor.start().1.deleted;
1585 if let Some(fragment) = cursor.item() {
1586 let overshoot = range.start.offset - fragment.insertion_offset;
1587 if fragment.visible {
1588 visible_start += overshoot;
1589 } else {
1590 deleted_start += overshoot;
1591 }
1592 }
1593 let end_fragment_id = self.fragment_id_for_anchor(&range.end);
1594
1595 Edits {
1596 visible_cursor: self.visible_text.cursor(visible_start),
1597 deleted_cursor: self.deleted_text.cursor(deleted_start),
1598 fragments_cursor,
1599 undos: &self.undo_map,
1600 since,
1601 old_end: Default::default(),
1602 new_end: Default::default(),
1603 range: (start_fragment_id, range.start.offset)..(end_fragment_id, range.end.offset),
1604 }
1605 }
1606}
1607
1608struct RopeBuilder<'a> {
1609 old_visible_cursor: rope::Cursor<'a>,
1610 old_deleted_cursor: rope::Cursor<'a>,
1611 new_visible: Rope,
1612 new_deleted: Rope,
1613}
1614
1615impl<'a> RopeBuilder<'a> {
1616 fn new(old_visible_cursor: rope::Cursor<'a>, old_deleted_cursor: rope::Cursor<'a>) -> Self {
1617 Self {
1618 old_visible_cursor,
1619 old_deleted_cursor,
1620 new_visible: Rope::new(),
1621 new_deleted: Rope::new(),
1622 }
1623 }
1624
1625 fn push_tree(&mut self, len: FragmentTextSummary) {
1626 self.push(len.visible, true, true);
1627 self.push(len.deleted, false, false);
1628 }
1629
1630 fn push_fragment(&mut self, fragment: &Fragment, was_visible: bool) {
1631 debug_assert!(fragment.len > 0);
1632 self.push(fragment.len, was_visible, fragment.visible)
1633 }
1634
1635 fn push(&mut self, len: usize, was_visible: bool, is_visible: bool) {
1636 let text = if was_visible {
1637 self.old_visible_cursor
1638 .slice(self.old_visible_cursor.offset() + len)
1639 } else {
1640 self.old_deleted_cursor
1641 .slice(self.old_deleted_cursor.offset() + len)
1642 };
1643 if is_visible {
1644 self.new_visible.append(text);
1645 } else {
1646 self.new_deleted.append(text);
1647 }
1648 }
1649
1650 fn push_str(&mut self, text: &str) {
1651 self.new_visible.push(text);
1652 }
1653
1654 fn finish(mut self) -> (Rope, Rope) {
1655 self.new_visible.append(self.old_visible_cursor.suffix());
1656 self.new_deleted.append(self.old_deleted_cursor.suffix());
1657 (self.new_visible, self.new_deleted)
1658 }
1659}
1660
1661impl<'a, D: TextDimension + Ord, F: FnMut(&FragmentSummary) -> bool> Iterator for Edits<'a, D, F> {
1662 type Item = Edit<D>;
1663
1664 fn next(&mut self) -> Option<Self::Item> {
1665 let mut pending_edit: Option<Edit<D>> = None;
1666 let cursor = self.fragments_cursor.as_mut()?;
1667
1668 while let Some(fragment) = cursor.item() {
1669 if fragment.id < *self.range.start.0 {
1670 cursor.next(&None);
1671 continue;
1672 } else if fragment.id > *self.range.end.0 {
1673 break;
1674 }
1675
1676 if cursor.start().visible > self.visible_cursor.offset() {
1677 let summary = self.visible_cursor.summary(cursor.start().visible);
1678 self.old_end.add_assign(&summary);
1679 self.new_end.add_assign(&summary);
1680 }
1681
1682 if pending_edit
1683 .as_ref()
1684 .map_or(false, |change| change.new.end < self.new_end)
1685 {
1686 break;
1687 }
1688
1689 if !fragment.was_visible(&self.since, &self.undos) && fragment.visible {
1690 let mut visible_end = cursor.end(&None).visible;
1691 if fragment.id == *self.range.end.0 {
1692 visible_end = cmp::min(
1693 visible_end,
1694 cursor.start().visible + (self.range.end.1 - fragment.insertion_offset),
1695 );
1696 }
1697
1698 let fragment_summary = self.visible_cursor.summary(visible_end);
1699 let mut new_end = self.new_end.clone();
1700 new_end.add_assign(&fragment_summary);
1701 if let Some(pending_edit) = pending_edit.as_mut() {
1702 pending_edit.new.end = new_end.clone();
1703 } else {
1704 pending_edit = Some(Edit {
1705 old: self.old_end.clone()..self.old_end.clone(),
1706 new: self.new_end.clone()..new_end.clone(),
1707 });
1708 }
1709
1710 self.new_end = new_end;
1711 } else if fragment.was_visible(&self.since, &self.undos) && !fragment.visible {
1712 let mut deleted_end = cursor.end(&None).deleted;
1713 if fragment.id == *self.range.end.0 {
1714 deleted_end = cmp::min(
1715 deleted_end,
1716 cursor.start().deleted + (self.range.end.1 - fragment.insertion_offset),
1717 );
1718 }
1719
1720 if cursor.start().deleted > self.deleted_cursor.offset() {
1721 self.deleted_cursor.seek_forward(cursor.start().deleted);
1722 }
1723 let fragment_summary = self.deleted_cursor.summary(deleted_end);
1724 let mut old_end = self.old_end.clone();
1725 old_end.add_assign(&fragment_summary);
1726 if let Some(pending_edit) = pending_edit.as_mut() {
1727 pending_edit.old.end = old_end.clone();
1728 } else {
1729 pending_edit = Some(Edit {
1730 old: self.old_end.clone()..old_end.clone(),
1731 new: self.new_end.clone()..self.new_end.clone(),
1732 });
1733 }
1734
1735 self.old_end = old_end;
1736 }
1737
1738 cursor.next(&None);
1739 }
1740
1741 pending_edit
1742 }
1743}
1744
1745impl Fragment {
1746 fn is_visible(&self, undos: &UndoMap) -> bool {
1747 !undos.is_undone(self.insertion_timestamp.local())
1748 && self.deletions.iter().all(|d| undos.is_undone(*d))
1749 }
1750
1751 fn was_visible(&self, version: &clock::Global, undos: &UndoMap) -> bool {
1752 (version.observed(self.insertion_timestamp.local())
1753 && !undos.was_undone(self.insertion_timestamp.local(), version))
1754 && self
1755 .deletions
1756 .iter()
1757 .all(|d| !version.observed(*d) || undos.was_undone(*d, version))
1758 }
1759}
1760
1761impl sum_tree::Item for Fragment {
1762 type Summary = FragmentSummary;
1763
1764 fn summary(&self) -> Self::Summary {
1765 let mut max_version = clock::Global::new();
1766 max_version.observe(self.insertion_timestamp.local());
1767 for deletion in &self.deletions {
1768 max_version.observe(*deletion);
1769 }
1770 max_version.join(&self.max_undos);
1771
1772 let mut min_insertion_version = clock::Global::new();
1773 min_insertion_version.observe(self.insertion_timestamp.local());
1774 let max_insertion_version = min_insertion_version.clone();
1775 if self.visible {
1776 FragmentSummary {
1777 max_id: self.id.clone(),
1778 text: FragmentTextSummary {
1779 visible: self.len,
1780 deleted: 0,
1781 },
1782 max_version,
1783 min_insertion_version,
1784 max_insertion_version,
1785 }
1786 } else {
1787 FragmentSummary {
1788 max_id: self.id.clone(),
1789 text: FragmentTextSummary {
1790 visible: 0,
1791 deleted: self.len,
1792 },
1793 max_version,
1794 min_insertion_version,
1795 max_insertion_version,
1796 }
1797 }
1798 }
1799}
1800
1801impl sum_tree::Summary for FragmentSummary {
1802 type Context = Option<clock::Global>;
1803
1804 fn add_summary(&mut self, other: &Self, _: &Self::Context) {
1805 self.max_id.assign(&other.max_id);
1806 self.text.visible += &other.text.visible;
1807 self.text.deleted += &other.text.deleted;
1808 self.max_version.join(&other.max_version);
1809 self.min_insertion_version
1810 .meet(&other.min_insertion_version);
1811 self.max_insertion_version
1812 .join(&other.max_insertion_version);
1813 }
1814}
1815
1816impl Default for FragmentSummary {
1817 fn default() -> Self {
1818 FragmentSummary {
1819 max_id: Locator::min(),
1820 text: FragmentTextSummary::default(),
1821 max_version: clock::Global::new(),
1822 min_insertion_version: clock::Global::new(),
1823 max_insertion_version: clock::Global::new(),
1824 }
1825 }
1826}
1827
1828impl sum_tree::Item for InsertionFragment {
1829 type Summary = InsertionFragmentKey;
1830
1831 fn summary(&self) -> Self::Summary {
1832 InsertionFragmentKey {
1833 timestamp: self.timestamp,
1834 split_offset: self.split_offset,
1835 }
1836 }
1837}
1838
1839impl sum_tree::KeyedItem for InsertionFragment {
1840 type Key = InsertionFragmentKey;
1841
1842 fn key(&self) -> Self::Key {
1843 sum_tree::Item::summary(self)
1844 }
1845}
1846
1847impl InsertionFragment {
1848 fn new(fragment: &Fragment) -> Self {
1849 Self {
1850 timestamp: fragment.insertion_timestamp.local(),
1851 split_offset: fragment.insertion_offset,
1852 fragment_id: fragment.id.clone(),
1853 }
1854 }
1855
1856 fn insert_new(fragment: &Fragment) -> sum_tree::Edit<Self> {
1857 sum_tree::Edit::Insert(Self::new(fragment))
1858 }
1859}
1860
1861impl sum_tree::Summary for InsertionFragmentKey {
1862 type Context = ();
1863
1864 fn add_summary(&mut self, summary: &Self, _: &()) {
1865 *self = *summary;
1866 }
1867}
1868
1869#[derive(Copy, Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
1870pub struct FullOffset(pub usize);
1871
1872impl ops::AddAssign<usize> for FullOffset {
1873 fn add_assign(&mut self, rhs: usize) {
1874 self.0 += rhs;
1875 }
1876}
1877
1878impl ops::Add<usize> for FullOffset {
1879 type Output = Self;
1880
1881 fn add(mut self, rhs: usize) -> Self::Output {
1882 self += rhs;
1883 self
1884 }
1885}
1886
1887impl ops::Sub for FullOffset {
1888 type Output = usize;
1889
1890 fn sub(self, rhs: Self) -> Self::Output {
1891 self.0 - rhs.0
1892 }
1893}
1894
1895impl<'a> sum_tree::Dimension<'a, FragmentSummary> for usize {
1896 fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
1897 *self += summary.text.visible;
1898 }
1899}
1900
1901impl<'a> sum_tree::Dimension<'a, FragmentSummary> for FullOffset {
1902 fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
1903 self.0 += summary.text.visible + summary.text.deleted;
1904 }
1905}
1906
1907impl<'a> sum_tree::Dimension<'a, FragmentSummary> for Option<&'a Locator> {
1908 fn add_summary(&mut self, summary: &'a FragmentSummary, _: &Option<clock::Global>) {
1909 *self = Some(&summary.max_id);
1910 }
1911}
1912
1913impl<'a> sum_tree::SeekTarget<'a, FragmentSummary, FragmentTextSummary> for usize {
1914 fn cmp(
1915 &self,
1916 cursor_location: &FragmentTextSummary,
1917 _: &Option<clock::Global>,
1918 ) -> cmp::Ordering {
1919 Ord::cmp(self, &cursor_location.visible)
1920 }
1921}
1922
1923#[derive(Copy, Clone, Debug, Eq, PartialEq)]
1924enum VersionedFullOffset {
1925 Offset(FullOffset),
1926 Invalid,
1927}
1928
1929impl VersionedFullOffset {
1930 fn full_offset(&self) -> FullOffset {
1931 if let Self::Offset(position) = self {
1932 *position
1933 } else {
1934 panic!("invalid version")
1935 }
1936 }
1937}
1938
1939impl Default for VersionedFullOffset {
1940 fn default() -> Self {
1941 Self::Offset(Default::default())
1942 }
1943}
1944
1945impl<'a> sum_tree::Dimension<'a, FragmentSummary> for VersionedFullOffset {
1946 fn add_summary(&mut self, summary: &'a FragmentSummary, cx: &Option<clock::Global>) {
1947 if let Self::Offset(offset) = self {
1948 let version = cx.as_ref().unwrap();
1949 if version.ge(&summary.max_insertion_version) {
1950 *offset += summary.text.visible + summary.text.deleted;
1951 } else if version.observed_any(&summary.min_insertion_version) {
1952 *self = Self::Invalid;
1953 }
1954 }
1955 }
1956}
1957
1958impl<'a> sum_tree::SeekTarget<'a, FragmentSummary, Self> for VersionedFullOffset {
1959 fn cmp(&self, cursor_position: &Self, _: &Option<clock::Global>) -> cmp::Ordering {
1960 match (self, cursor_position) {
1961 (Self::Offset(a), Self::Offset(b)) => Ord::cmp(a, b),
1962 (Self::Offset(_), Self::Invalid) => cmp::Ordering::Less,
1963 (Self::Invalid, _) => unreachable!(),
1964 }
1965 }
1966}
1967
1968impl Operation {
1969 fn replica_id(&self) -> ReplicaId {
1970 operation_queue::Operation::lamport_timestamp(self).replica_id
1971 }
1972
1973 pub fn is_edit(&self) -> bool {
1974 match self {
1975 Operation::Edit { .. } => true,
1976 _ => false,
1977 }
1978 }
1979}
1980
1981impl operation_queue::Operation for Operation {
1982 fn lamport_timestamp(&self) -> clock::Lamport {
1983 match self {
1984 Operation::Edit(edit) => edit.timestamp.lamport(),
1985 Operation::Undo {
1986 lamport_timestamp, ..
1987 } => *lamport_timestamp,
1988 }
1989 }
1990}
1991
1992pub trait ToOffset {
1993 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize;
1994}
1995
1996impl ToOffset for Point {
1997 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
1998 snapshot.point_to_offset(*self)
1999 }
2000}
2001
2002impl ToOffset for PointUtf16 {
2003 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2004 snapshot.point_utf16_to_offset(*self)
2005 }
2006}
2007
2008impl ToOffset for usize {
2009 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2010 assert!(*self <= snapshot.len(), "offset is out of range");
2011 *self
2012 }
2013}
2014
2015impl ToOffset for Anchor {
2016 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2017 snapshot.summary_for_anchor(self)
2018 }
2019}
2020
2021impl<'a, T: ToOffset> ToOffset for &'a T {
2022 fn to_offset(&self, content: &BufferSnapshot) -> usize {
2023 (*self).to_offset(content)
2024 }
2025}
2026
2027pub trait ToPoint {
2028 fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point;
2029}
2030
2031impl ToPoint for Anchor {
2032 fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point {
2033 snapshot.summary_for_anchor(self)
2034 }
2035}
2036
2037impl ToPoint for usize {
2038 fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point {
2039 snapshot.offset_to_point(*self)
2040 }
2041}
2042
2043impl ToPoint for Point {
2044 fn to_point<'a>(&self, _: &BufferSnapshot) -> Point {
2045 *self
2046 }
2047}
2048
2049pub trait FromAnchor {
2050 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self;
2051}
2052
2053impl FromAnchor for Point {
2054 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
2055 anchor.to_point(snapshot)
2056 }
2057}
2058
2059impl FromAnchor for usize {
2060 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
2061 anchor.to_offset(snapshot)
2062 }
2063}