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