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 transaction_group_interval(&self) -> Duration {
515 self.history.group_interval
516 }
517
518 pub fn edit<R, I, S, T>(&mut self, ranges: R, new_text: T) -> EditOperation
519 where
520 R: IntoIterator<IntoIter = I>,
521 I: ExactSizeIterator<Item = Range<S>>,
522 S: ToOffset,
523 T: Into<String>,
524 {
525 let new_text = new_text.into();
526 let new_text_len = new_text.len();
527 let new_text = if new_text_len > 0 {
528 Some(new_text)
529 } else {
530 None
531 };
532
533 self.start_transaction();
534 let timestamp = InsertionTimestamp {
535 replica_id: self.replica_id,
536 local: self.local_clock.tick().value,
537 lamport: self.lamport_clock.tick().value,
538 };
539 let edit = self.apply_local_edit(ranges.into_iter(), new_text, timestamp);
540
541 self.history.push(edit.clone());
542 self.history.push_undo(edit.timestamp.local());
543 self.last_edit = edit.timestamp.local();
544 self.snapshot.version.observe(edit.timestamp.local());
545 self.end_transaction();
546 edit
547 }
548
549 fn apply_local_edit<S: ToOffset>(
550 &mut self,
551 ranges: impl ExactSizeIterator<Item = Range<S>>,
552 new_text: Option<String>,
553 timestamp: InsertionTimestamp,
554 ) -> EditOperation {
555 let mut edits = Patch::default();
556 let mut edit_op = EditOperation {
557 timestamp,
558 version: self.version(),
559 ranges: Vec::with_capacity(ranges.len()),
560 new_text: None,
561 };
562 let mut new_insertions = Vec::new();
563 let mut insertion_offset = 0;
564
565 let mut ranges = ranges
566 .map(|range| range.start.to_offset(&*self)..range.end.to_offset(&*self))
567 .peekable();
568
569 let mut new_ropes =
570 RopeBuilder::new(self.visible_text.cursor(0), self.deleted_text.cursor(0));
571 let mut old_fragments = self.fragments.cursor::<FragmentTextSummary>();
572 let mut new_fragments =
573 old_fragments.slice(&ranges.peek().unwrap().start, Bias::Right, &None);
574 new_ropes.push_tree(new_fragments.summary().text);
575
576 let mut fragment_start = old_fragments.start().visible;
577 for range in ranges {
578 let fragment_end = old_fragments.end(&None).visible;
579
580 // If the current fragment ends before this range, then jump ahead to the first fragment
581 // that extends past the start of this range, reusing any intervening fragments.
582 if fragment_end < range.start {
583 // If the current fragment has been partially consumed, then consume the rest of it
584 // and advance to the next fragment before slicing.
585 if fragment_start > old_fragments.start().visible {
586 if fragment_end > fragment_start {
587 let mut suffix = old_fragments.item().unwrap().clone();
588 suffix.len = fragment_end - fragment_start;
589 suffix.insertion_offset += fragment_start - old_fragments.start().visible;
590 new_insertions.push(InsertionFragment::insert_new(&suffix));
591 new_ropes.push_fragment(&suffix, suffix.visible);
592 new_fragments.push(suffix, &None);
593 }
594 old_fragments.next(&None);
595 }
596
597 let slice = old_fragments.slice(&range.start, Bias::Right, &None);
598 new_ropes.push_tree(slice.summary().text);
599 new_fragments.push_tree(slice, &None);
600 fragment_start = old_fragments.start().visible;
601 }
602
603 let full_range_start = FullOffset(range.start + old_fragments.start().deleted);
604
605 // Preserve any portion of the current fragment that precedes this range.
606 if fragment_start < range.start {
607 let mut prefix = old_fragments.item().unwrap().clone();
608 prefix.len = range.start - fragment_start;
609 prefix.insertion_offset += fragment_start - old_fragments.start().visible;
610 prefix.id = Locator::between(&new_fragments.summary().max_id, &prefix.id);
611 new_insertions.push(InsertionFragment::insert_new(&prefix));
612 new_ropes.push_fragment(&prefix, prefix.visible);
613 new_fragments.push(prefix, &None);
614 fragment_start = range.start;
615 }
616
617 // Insert the new text before any existing fragments within the range.
618 if let Some(new_text) = new_text.as_deref() {
619 let new_start = new_fragments.summary().text.visible;
620 edits.push(Edit {
621 old: fragment_start..fragment_start,
622 new: new_start..new_start + new_text.len(),
623 });
624 let fragment = Fragment {
625 id: Locator::between(
626 &new_fragments.summary().max_id,
627 old_fragments
628 .item()
629 .map_or(&Locator::max(), |old_fragment| &old_fragment.id),
630 ),
631 insertion_timestamp: timestamp,
632 insertion_offset,
633 len: new_text.len(),
634 deletions: Default::default(),
635 max_undos: Default::default(),
636 visible: true,
637 };
638 new_insertions.push(InsertionFragment::insert_new(&fragment));
639 new_ropes.push_str(new_text);
640 new_fragments.push(fragment, &None);
641 insertion_offset += new_text.len();
642 }
643
644 // Advance through every fragment that intersects this range, marking the intersecting
645 // portions as deleted.
646 while fragment_start < range.end {
647 let fragment = old_fragments.item().unwrap();
648 let fragment_end = old_fragments.end(&None).visible;
649 let mut intersection = fragment.clone();
650 let intersection_end = cmp::min(range.end, fragment_end);
651 if fragment.visible {
652 intersection.len = intersection_end - fragment_start;
653 intersection.insertion_offset += fragment_start - old_fragments.start().visible;
654 intersection.id =
655 Locator::between(&new_fragments.summary().max_id, &intersection.id);
656 intersection.deletions.insert(timestamp.local());
657 intersection.visible = false;
658 }
659 if intersection.len > 0 {
660 if fragment.visible && !intersection.visible {
661 let new_start = new_fragments.summary().text.visible;
662 edits.push(Edit {
663 old: fragment_start..intersection_end,
664 new: new_start..new_start,
665 });
666 }
667 new_insertions.push(InsertionFragment::insert_new(&intersection));
668 new_ropes.push_fragment(&intersection, fragment.visible);
669 new_fragments.push(intersection, &None);
670 fragment_start = intersection_end;
671 }
672 if fragment_end <= range.end {
673 old_fragments.next(&None);
674 }
675 }
676
677 let full_range_end = FullOffset(range.end + old_fragments.start().deleted);
678 edit_op.ranges.push(full_range_start..full_range_end);
679 }
680
681 // If the current fragment has been partially consumed, then consume the rest of it
682 // and advance to the next fragment before slicing.
683 if fragment_start > old_fragments.start().visible {
684 let fragment_end = old_fragments.end(&None).visible;
685 if fragment_end > fragment_start {
686 let mut suffix = old_fragments.item().unwrap().clone();
687 suffix.len = fragment_end - fragment_start;
688 suffix.insertion_offset += fragment_start - old_fragments.start().visible;
689 new_insertions.push(InsertionFragment::insert_new(&suffix));
690 new_ropes.push_fragment(&suffix, suffix.visible);
691 new_fragments.push(suffix, &None);
692 }
693 old_fragments.next(&None);
694 }
695
696 let suffix = old_fragments.suffix(&None);
697 new_ropes.push_tree(suffix.summary().text);
698 new_fragments.push_tree(suffix, &None);
699 let (visible_text, deleted_text) = new_ropes.finish();
700 drop(old_fragments);
701
702 self.snapshot.fragments = new_fragments;
703 self.snapshot.insertions.edit(new_insertions, &());
704 self.snapshot.visible_text = visible_text;
705 self.snapshot.deleted_text = deleted_text;
706 self.subscriptions.publish_mut(&edits);
707 edit_op.new_text = new_text;
708 edit_op
709 }
710
711 pub fn apply_ops<I: IntoIterator<Item = Operation>>(&mut self, ops: I) -> Result<()> {
712 let mut deferred_ops = Vec::new();
713 for op in ops {
714 if self.can_apply_op(&op) {
715 self.apply_op(op)?;
716 } else {
717 self.deferred_replicas.insert(op.replica_id());
718 deferred_ops.push(op);
719 }
720 }
721 self.deferred_ops.insert(deferred_ops);
722 self.flush_deferred_ops()?;
723 Ok(())
724 }
725
726 fn apply_op(&mut self, op: Operation) -> Result<()> {
727 match op {
728 Operation::Edit(edit) => {
729 if !self.version.observed(edit.timestamp.local()) {
730 self.apply_remote_edit(
731 &edit.version,
732 &edit.ranges,
733 edit.new_text.as_deref(),
734 edit.timestamp,
735 );
736 self.snapshot.version.observe(edit.timestamp.local());
737 self.history.push(edit);
738 }
739 }
740 Operation::Undo {
741 undo,
742 lamport_timestamp,
743 } => {
744 if !self.version.observed(undo.id) {
745 self.apply_undo(&undo)?;
746 self.snapshot.version.observe(undo.id);
747 self.lamport_clock.observe(lamport_timestamp);
748 }
749 }
750 }
751 Ok(())
752 }
753
754 fn apply_remote_edit(
755 &mut self,
756 version: &clock::Global,
757 ranges: &[Range<FullOffset>],
758 new_text: Option<&str>,
759 timestamp: InsertionTimestamp,
760 ) {
761 if ranges.is_empty() {
762 return;
763 }
764
765 let mut edits = Patch::default();
766 let cx = Some(version.clone());
767 let mut new_insertions = Vec::new();
768 let mut insertion_offset = 0;
769 let mut new_ropes =
770 RopeBuilder::new(self.visible_text.cursor(0), self.deleted_text.cursor(0));
771 let mut old_fragments = self.fragments.cursor::<(VersionedFullOffset, usize)>();
772 let mut new_fragments = old_fragments.slice(
773 &VersionedFullOffset::Offset(ranges[0].start),
774 Bias::Left,
775 &cx,
776 );
777 new_ropes.push_tree(new_fragments.summary().text);
778
779 let mut fragment_start = old_fragments.start().0.full_offset();
780 for range in ranges {
781 let fragment_end = old_fragments.end(&cx).0.full_offset();
782
783 // If the current fragment ends before this range, then jump ahead to the first fragment
784 // that extends past the start of this range, reusing any intervening fragments.
785 if fragment_end < range.start {
786 // If the current fragment has been partially consumed, then consume the rest of it
787 // and advance to the next fragment before slicing.
788 if fragment_start > old_fragments.start().0.full_offset() {
789 if fragment_end > fragment_start {
790 let mut suffix = old_fragments.item().unwrap().clone();
791 suffix.len = fragment_end.0 - fragment_start.0;
792 suffix.insertion_offset +=
793 fragment_start - old_fragments.start().0.full_offset();
794 new_insertions.push(InsertionFragment::insert_new(&suffix));
795 new_ropes.push_fragment(&suffix, suffix.visible);
796 new_fragments.push(suffix, &None);
797 }
798 old_fragments.next(&cx);
799 }
800
801 let slice =
802 old_fragments.slice(&VersionedFullOffset::Offset(range.start), Bias::Left, &cx);
803 new_ropes.push_tree(slice.summary().text);
804 new_fragments.push_tree(slice, &None);
805 fragment_start = old_fragments.start().0.full_offset();
806 }
807
808 // If we are at the end of a non-concurrent fragment, advance to the next one.
809 let fragment_end = old_fragments.end(&cx).0.full_offset();
810 if fragment_end == range.start && fragment_end > fragment_start {
811 let mut fragment = old_fragments.item().unwrap().clone();
812 fragment.len = fragment_end.0 - fragment_start.0;
813 fragment.insertion_offset += fragment_start - old_fragments.start().0.full_offset();
814 new_insertions.push(InsertionFragment::insert_new(&fragment));
815 new_ropes.push_fragment(&fragment, fragment.visible);
816 new_fragments.push(fragment, &None);
817 old_fragments.next(&cx);
818 fragment_start = old_fragments.start().0.full_offset();
819 }
820
821 // Skip over insertions that are concurrent to this edit, but have a lower lamport
822 // timestamp.
823 while let Some(fragment) = old_fragments.item() {
824 if fragment_start == range.start
825 && fragment.insertion_timestamp.lamport() > timestamp.lamport()
826 {
827 new_ropes.push_fragment(fragment, fragment.visible);
828 new_fragments.push(fragment.clone(), &None);
829 old_fragments.next(&cx);
830 debug_assert_eq!(fragment_start, range.start);
831 } else {
832 break;
833 }
834 }
835 debug_assert!(fragment_start <= range.start);
836
837 // Preserve any portion of the current fragment that precedes this range.
838 if fragment_start < range.start {
839 let mut prefix = old_fragments.item().unwrap().clone();
840 prefix.len = range.start.0 - fragment_start.0;
841 prefix.insertion_offset += fragment_start - old_fragments.start().0.full_offset();
842 prefix.id = Locator::between(&new_fragments.summary().max_id, &prefix.id);
843 new_insertions.push(InsertionFragment::insert_new(&prefix));
844 fragment_start = range.start;
845 new_ropes.push_fragment(&prefix, prefix.visible);
846 new_fragments.push(prefix, &None);
847 }
848
849 // Insert the new text before any existing fragments within the range.
850 if let Some(new_text) = new_text {
851 let mut old_start = old_fragments.start().1;
852 if old_fragments.item().map_or(false, |f| f.visible) {
853 old_start += fragment_start.0 - old_fragments.start().0.full_offset().0;
854 }
855 let new_start = new_fragments.summary().text.visible;
856 edits.push(Edit {
857 old: old_start..old_start,
858 new: new_start..new_start + new_text.len(),
859 });
860 let fragment = Fragment {
861 id: Locator::between(
862 &new_fragments.summary().max_id,
863 old_fragments
864 .item()
865 .map_or(&Locator::max(), |old_fragment| &old_fragment.id),
866 ),
867 insertion_timestamp: timestamp,
868 insertion_offset,
869 len: new_text.len(),
870 deletions: Default::default(),
871 max_undos: Default::default(),
872 visible: true,
873 };
874 new_insertions.push(InsertionFragment::insert_new(&fragment));
875 new_ropes.push_str(new_text);
876 new_fragments.push(fragment, &None);
877 insertion_offset += new_text.len();
878 }
879
880 // Advance through every fragment that intersects this range, marking the intersecting
881 // portions as deleted.
882 while fragment_start < range.end {
883 let fragment = old_fragments.item().unwrap();
884 let fragment_end = old_fragments.end(&cx).0.full_offset();
885 let mut intersection = fragment.clone();
886 let intersection_end = cmp::min(range.end, fragment_end);
887 if fragment.was_visible(version, &self.undo_map) {
888 intersection.len = intersection_end.0 - fragment_start.0;
889 intersection.insertion_offset +=
890 fragment_start - old_fragments.start().0.full_offset();
891 intersection.id =
892 Locator::between(&new_fragments.summary().max_id, &intersection.id);
893 intersection.deletions.insert(timestamp.local());
894 intersection.visible = false;
895 }
896 if intersection.len > 0 {
897 if fragment.visible && !intersection.visible {
898 let old_start = old_fragments.start().1
899 + (fragment_start.0 - old_fragments.start().0.full_offset().0);
900 let new_start = new_fragments.summary().text.visible;
901 edits.push(Edit {
902 old: old_start..old_start + intersection.len,
903 new: new_start..new_start,
904 });
905 }
906 new_insertions.push(InsertionFragment::insert_new(&intersection));
907 new_ropes.push_fragment(&intersection, fragment.visible);
908 new_fragments.push(intersection, &None);
909 fragment_start = intersection_end;
910 }
911 if fragment_end <= range.end {
912 old_fragments.next(&cx);
913 }
914 }
915 }
916
917 // If the current fragment has been partially consumed, then consume the rest of it
918 // and advance to the next fragment before slicing.
919 if fragment_start > old_fragments.start().0.full_offset() {
920 let fragment_end = old_fragments.end(&cx).0.full_offset();
921 if fragment_end > fragment_start {
922 let mut suffix = old_fragments.item().unwrap().clone();
923 suffix.len = fragment_end.0 - fragment_start.0;
924 suffix.insertion_offset += fragment_start - old_fragments.start().0.full_offset();
925 new_insertions.push(InsertionFragment::insert_new(&suffix));
926 new_ropes.push_fragment(&suffix, suffix.visible);
927 new_fragments.push(suffix, &None);
928 }
929 old_fragments.next(&cx);
930 }
931
932 let suffix = old_fragments.suffix(&cx);
933 new_ropes.push_tree(suffix.summary().text);
934 new_fragments.push_tree(suffix, &None);
935 let (visible_text, deleted_text) = new_ropes.finish();
936 drop(old_fragments);
937
938 self.snapshot.fragments = new_fragments;
939 self.snapshot.visible_text = visible_text;
940 self.snapshot.deleted_text = deleted_text;
941 self.snapshot.insertions.edit(new_insertions, &());
942 self.local_clock.observe(timestamp.local());
943 self.lamport_clock.observe(timestamp.lamport());
944 self.subscriptions.publish_mut(&edits);
945 }
946
947 fn apply_undo(&mut self, undo: &UndoOperation) -> Result<()> {
948 let mut edits = Patch::default();
949 self.snapshot.undo_map.insert(undo);
950
951 let mut cx = undo.version.clone();
952 for edit_id in undo.counts.keys().copied() {
953 cx.observe(edit_id);
954 }
955 let cx = Some(cx);
956
957 let mut old_fragments = self.fragments.cursor::<(VersionedFullOffset, usize)>();
958 let mut new_fragments = old_fragments.slice(
959 &VersionedFullOffset::Offset(undo.ranges[0].start),
960 Bias::Right,
961 &cx,
962 );
963 let mut new_ropes =
964 RopeBuilder::new(self.visible_text.cursor(0), self.deleted_text.cursor(0));
965 new_ropes.push_tree(new_fragments.summary().text);
966
967 for range in &undo.ranges {
968 let mut end_offset = old_fragments.end(&cx).0.full_offset();
969
970 if end_offset < range.start {
971 let preceding_fragments = old_fragments.slice(
972 &VersionedFullOffset::Offset(range.start),
973 Bias::Right,
974 &cx,
975 );
976 new_ropes.push_tree(preceding_fragments.summary().text);
977 new_fragments.push_tree(preceding_fragments, &None);
978 }
979
980 while end_offset <= range.end {
981 if let Some(fragment) = old_fragments.item() {
982 let mut fragment = fragment.clone();
983 let fragment_was_visible = fragment.visible;
984
985 if fragment.was_visible(&undo.version, &self.undo_map)
986 || undo
987 .counts
988 .contains_key(&fragment.insertion_timestamp.local())
989 {
990 fragment.visible = fragment.is_visible(&self.undo_map);
991 fragment.max_undos.observe(undo.id);
992 }
993
994 let old_start = old_fragments.start().1;
995 let new_start = new_fragments.summary().text.visible;
996 if fragment_was_visible && !fragment.visible {
997 edits.push(Edit {
998 old: old_start..old_start + fragment.len,
999 new: new_start..new_start,
1000 });
1001 } else if !fragment_was_visible && fragment.visible {
1002 edits.push(Edit {
1003 old: old_start..old_start,
1004 new: new_start..new_start + fragment.len,
1005 });
1006 }
1007 new_ropes.push_fragment(&fragment, fragment_was_visible);
1008 new_fragments.push(fragment, &None);
1009
1010 old_fragments.next(&cx);
1011 if end_offset == old_fragments.end(&cx).0.full_offset() {
1012 let unseen_fragments = old_fragments.slice(
1013 &VersionedFullOffset::Offset(end_offset),
1014 Bias::Right,
1015 &cx,
1016 );
1017 new_ropes.push_tree(unseen_fragments.summary().text);
1018 new_fragments.push_tree(unseen_fragments, &None);
1019 }
1020 end_offset = old_fragments.end(&cx).0.full_offset();
1021 } else {
1022 break;
1023 }
1024 }
1025 }
1026
1027 let suffix = old_fragments.suffix(&cx);
1028 new_ropes.push_tree(suffix.summary().text);
1029 new_fragments.push_tree(suffix, &None);
1030
1031 drop(old_fragments);
1032 let (visible_text, deleted_text) = new_ropes.finish();
1033 self.snapshot.fragments = new_fragments;
1034 self.snapshot.visible_text = visible_text;
1035 self.snapshot.deleted_text = deleted_text;
1036 self.subscriptions.publish_mut(&edits);
1037 Ok(())
1038 }
1039
1040 fn flush_deferred_ops(&mut self) -> Result<()> {
1041 self.deferred_replicas.clear();
1042 let mut deferred_ops = Vec::new();
1043 for op in self.deferred_ops.drain().iter().cloned() {
1044 if self.can_apply_op(&op) {
1045 self.apply_op(op)?;
1046 } else {
1047 self.deferred_replicas.insert(op.replica_id());
1048 deferred_ops.push(op);
1049 }
1050 }
1051 self.deferred_ops.insert(deferred_ops);
1052 Ok(())
1053 }
1054
1055 fn can_apply_op(&self, op: &Operation) -> bool {
1056 if self.deferred_replicas.contains(&op.replica_id()) {
1057 false
1058 } else {
1059 match op {
1060 Operation::Edit(edit) => self.version.ge(&edit.version),
1061 Operation::Undo { undo, .. } => self.version.ge(&undo.version),
1062 }
1063 }
1064 }
1065
1066 pub fn can_resolve(&self, anchor: &Anchor) -> bool {
1067 *anchor == Anchor::min()
1068 || *anchor == Anchor::max()
1069 || self.version.observed(anchor.timestamp)
1070 }
1071
1072 pub fn peek_undo_stack(&self) -> Option<&Transaction> {
1073 self.history.undo_stack.last()
1074 }
1075
1076 pub fn start_transaction(&mut self) -> Option<TransactionId> {
1077 self.start_transaction_at(Instant::now())
1078 }
1079
1080 pub fn start_transaction_at(&mut self, now: Instant) -> Option<TransactionId> {
1081 self.history.start_transaction(self.version.clone(), now)
1082 }
1083
1084 pub fn end_transaction(&mut self) -> Option<(TransactionId, clock::Global)> {
1085 self.end_transaction_at(Instant::now())
1086 }
1087
1088 pub fn end_transaction_at(&mut self, now: Instant) -> Option<(TransactionId, clock::Global)> {
1089 if let Some(transaction) = self.history.end_transaction(now) {
1090 let id = transaction.id;
1091 let since = transaction.start.clone();
1092 self.history.group();
1093 Some((id, since))
1094 } else {
1095 None
1096 }
1097 }
1098
1099 pub fn base_text(&self) -> &Arc<str> {
1100 &self.history.base_text
1101 }
1102
1103 pub fn history(&self) -> impl Iterator<Item = &EditOperation> {
1104 self.history.ops.values()
1105 }
1106
1107 pub fn undo(&mut self) -> Option<(TransactionId, Operation)> {
1108 if let Some(transaction) = self.history.pop_undo().cloned() {
1109 let transaction_id = transaction.id;
1110 let op = self.undo_or_redo(transaction).unwrap();
1111 Some((transaction_id, op))
1112 } else {
1113 None
1114 }
1115 }
1116
1117 pub fn redo(&mut self) -> Option<(TransactionId, Operation)> {
1118 if let Some(transaction) = self.history.pop_redo().cloned() {
1119 let transaction_id = transaction.id;
1120 let op = self.undo_or_redo(transaction).unwrap();
1121 Some((transaction_id, op))
1122 } else {
1123 None
1124 }
1125 }
1126
1127 fn undo_or_redo(&mut self, transaction: Transaction) -> Result<Operation> {
1128 let mut counts = HashMap::default();
1129 for edit_id in transaction.edits {
1130 counts.insert(edit_id, self.undo_map.undo_count(edit_id) + 1);
1131 }
1132
1133 let undo = UndoOperation {
1134 id: self.local_clock.tick(),
1135 counts,
1136 ranges: transaction.ranges,
1137 version: transaction.start.clone(),
1138 };
1139 self.apply_undo(&undo)?;
1140 self.snapshot.version.observe(undo.id);
1141
1142 Ok(Operation::Undo {
1143 undo,
1144 lamport_timestamp: self.lamport_clock.tick(),
1145 })
1146 }
1147
1148 pub fn subscribe(&mut self) -> Subscription {
1149 self.subscriptions.subscribe()
1150 }
1151}
1152
1153#[cfg(any(test, feature = "test-support"))]
1154impl Buffer {
1155 fn random_byte_range(&mut self, start_offset: usize, rng: &mut impl rand::Rng) -> Range<usize> {
1156 let end = self.clip_offset(rng.gen_range(start_offset..=self.len()), Bias::Right);
1157 let start = self.clip_offset(rng.gen_range(start_offset..=end), Bias::Right);
1158 start..end
1159 }
1160
1161 pub fn randomly_edit<T>(
1162 &mut self,
1163 rng: &mut T,
1164 old_range_count: usize,
1165 ) -> (Vec<Range<usize>>, String, Operation)
1166 where
1167 T: rand::Rng,
1168 {
1169 let mut old_ranges: Vec<Range<usize>> = Vec::new();
1170 for _ in 0..old_range_count {
1171 let last_end = old_ranges.last().map_or(0, |last_range| last_range.end + 1);
1172 if last_end > self.len() {
1173 break;
1174 }
1175 old_ranges.push(self.random_byte_range(last_end, rng));
1176 }
1177 let new_text_len = rng.gen_range(0..10);
1178 let new_text: String = crate::random_char_iter::RandomCharIter::new(&mut *rng)
1179 .take(new_text_len)
1180 .collect();
1181 log::info!(
1182 "mutating buffer {} at {:?}: {:?}",
1183 self.replica_id,
1184 old_ranges,
1185 new_text
1186 );
1187 let op = self.edit(old_ranges.iter().cloned(), new_text.as_str());
1188 (old_ranges, new_text, Operation::Edit(op))
1189 }
1190
1191 pub fn randomly_undo_redo(&mut self, rng: &mut impl rand::Rng) -> Vec<Operation> {
1192 use rand::prelude::*;
1193
1194 let mut ops = Vec::new();
1195 for _ in 0..rng.gen_range(1..=5) {
1196 if let Some(transaction) = self.history.undo_stack.choose(rng).cloned() {
1197 log::info!(
1198 "undoing buffer {} transaction {:?}",
1199 self.replica_id,
1200 transaction
1201 );
1202 ops.push(self.undo_or_redo(transaction).unwrap());
1203 }
1204 }
1205 ops
1206 }
1207}
1208
1209impl Deref for Buffer {
1210 type Target = BufferSnapshot;
1211
1212 fn deref(&self) -> &Self::Target {
1213 &self.snapshot
1214 }
1215}
1216
1217impl BufferSnapshot {
1218 pub fn as_rope(&self) -> &Rope {
1219 &self.visible_text
1220 }
1221
1222 pub fn row_count(&self) -> u32 {
1223 self.max_point().row + 1
1224 }
1225
1226 pub fn len(&self) -> usize {
1227 self.visible_text.len()
1228 }
1229
1230 pub fn chars(&self) -> impl Iterator<Item = char> + '_ {
1231 self.chars_at(0)
1232 }
1233
1234 pub fn chars_for_range<T: ToOffset>(&self, range: Range<T>) -> impl Iterator<Item = char> + '_ {
1235 self.text_for_range(range).flat_map(str::chars)
1236 }
1237
1238 pub fn contains_str_at<T>(&self, position: T, needle: &str) -> bool
1239 where
1240 T: ToOffset,
1241 {
1242 let position = position.to_offset(self);
1243 position == self.clip_offset(position, Bias::Left)
1244 && self
1245 .bytes_in_range(position..self.len())
1246 .flatten()
1247 .copied()
1248 .take(needle.len())
1249 .eq(needle.bytes())
1250 }
1251
1252 pub fn text(&self) -> String {
1253 self.text_for_range(0..self.len()).collect()
1254 }
1255
1256 pub fn text_summary(&self) -> TextSummary {
1257 self.visible_text.summary()
1258 }
1259
1260 pub fn max_point(&self) -> Point {
1261 self.visible_text.max_point()
1262 }
1263
1264 pub fn point_to_offset(&self, point: Point) -> usize {
1265 self.visible_text.point_to_offset(point)
1266 }
1267
1268 pub fn point_utf16_to_offset(&self, point: PointUtf16) -> usize {
1269 self.visible_text.point_utf16_to_offset(point)
1270 }
1271
1272 pub fn offset_to_point(&self, offset: usize) -> Point {
1273 self.visible_text.offset_to_point(offset)
1274 }
1275
1276 pub fn offset_to_point_utf16(&self, offset: usize) -> PointUtf16 {
1277 self.visible_text.offset_to_point_utf16(offset)
1278 }
1279
1280 pub fn version(&self) -> &clock::Global {
1281 &self.version
1282 }
1283
1284 pub fn chars_at<'a, T: ToOffset>(&'a self, position: T) -> impl Iterator<Item = char> + 'a {
1285 let offset = position.to_offset(self);
1286 self.visible_text.chars_at(offset)
1287 }
1288
1289 pub fn reversed_chars_at<'a, T: ToOffset>(
1290 &'a self,
1291 position: T,
1292 ) -> impl Iterator<Item = char> + 'a {
1293 let offset = position.to_offset(self);
1294 self.visible_text.reversed_chars_at(offset)
1295 }
1296
1297 pub fn bytes_in_range<'a, T: ToOffset>(&'a self, range: Range<T>) -> rope::Bytes<'a> {
1298 let start = range.start.to_offset(self);
1299 let end = range.end.to_offset(self);
1300 self.visible_text.bytes_in_range(start..end)
1301 }
1302
1303 pub fn text_for_range<'a, T: ToOffset>(&'a self, range: Range<T>) -> Chunks<'a> {
1304 let start = range.start.to_offset(self);
1305 let end = range.end.to_offset(self);
1306 self.visible_text.chunks_in_range(start..end)
1307 }
1308
1309 pub fn line_len(&self, row: u32) -> u32 {
1310 let row_start_offset = Point::new(row, 0).to_offset(self);
1311 let row_end_offset = if row >= self.max_point().row {
1312 self.len()
1313 } else {
1314 Point::new(row + 1, 0).to_offset(self) - 1
1315 };
1316 (row_end_offset - row_start_offset) as u32
1317 }
1318
1319 pub fn is_line_blank(&self, row: u32) -> bool {
1320 self.text_for_range(Point::new(row, 0)..Point::new(row, self.line_len(row)))
1321 .all(|chunk| chunk.matches(|c: char| !c.is_whitespace()).next().is_none())
1322 }
1323
1324 pub fn indent_column_for_line(&self, row: u32) -> u32 {
1325 let mut result = 0;
1326 for c in self.chars_at(Point::new(row, 0)) {
1327 if c == ' ' {
1328 result += 1;
1329 } else {
1330 break;
1331 }
1332 }
1333 result
1334 }
1335
1336 pub fn text_summary_for_range<'a, D, O: ToOffset>(&'a self, range: Range<O>) -> D
1337 where
1338 D: TextDimension,
1339 {
1340 self.visible_text
1341 .cursor(range.start.to_offset(self))
1342 .summary(range.end.to_offset(self))
1343 }
1344
1345 pub fn summaries_for_anchors<'a, D, A>(&'a self, anchors: A) -> impl 'a + Iterator<Item = D>
1346 where
1347 D: 'a + TextDimension,
1348 A: 'a + IntoIterator<Item = &'a Anchor>,
1349 {
1350 let anchors = anchors.into_iter();
1351 let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>();
1352 let mut fragment_cursor = self.fragments.cursor::<(Option<&Locator>, usize)>();
1353 let mut text_cursor = self.visible_text.cursor(0);
1354 let mut position = D::default();
1355
1356 anchors.map(move |anchor| {
1357 if *anchor == Anchor::min() {
1358 return D::default();
1359 } else if *anchor == Anchor::max() {
1360 return D::from_text_summary(&self.visible_text.summary());
1361 }
1362
1363 let anchor_key = InsertionFragmentKey {
1364 timestamp: anchor.timestamp,
1365 split_offset: anchor.offset,
1366 };
1367 insertion_cursor.seek(&anchor_key, anchor.bias, &());
1368 if let Some(insertion) = insertion_cursor.item() {
1369 let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
1370 if comparison == Ordering::Greater
1371 || (anchor.bias == Bias::Left
1372 && comparison == Ordering::Equal
1373 && anchor.offset > 0)
1374 {
1375 insertion_cursor.prev(&());
1376 }
1377 } else {
1378 insertion_cursor.prev(&());
1379 }
1380 let insertion = insertion_cursor.item().expect("invalid insertion");
1381 debug_assert_eq!(insertion.timestamp, anchor.timestamp, "invalid insertion");
1382
1383 fragment_cursor.seek_forward(&Some(&insertion.fragment_id), Bias::Left, &None);
1384 let fragment = fragment_cursor.item().unwrap();
1385 let mut fragment_offset = fragment_cursor.start().1;
1386 if fragment.visible {
1387 fragment_offset += anchor.offset - insertion.split_offset;
1388 }
1389
1390 position.add_assign(&text_cursor.summary(fragment_offset));
1391 position.clone()
1392 })
1393 }
1394
1395 fn summary_for_anchor<'a, D>(&'a self, anchor: &Anchor) -> D
1396 where
1397 D: TextDimension,
1398 {
1399 if *anchor == Anchor::min() {
1400 D::default()
1401 } else if *anchor == Anchor::max() {
1402 D::from_text_summary(&self.visible_text.summary())
1403 } else {
1404 let anchor_key = InsertionFragmentKey {
1405 timestamp: anchor.timestamp,
1406 split_offset: anchor.offset,
1407 };
1408 let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>();
1409 insertion_cursor.seek(&anchor_key, anchor.bias, &());
1410 if let Some(insertion) = insertion_cursor.item() {
1411 let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
1412 if comparison == Ordering::Greater
1413 || (anchor.bias == Bias::Left
1414 && comparison == Ordering::Equal
1415 && anchor.offset > 0)
1416 {
1417 insertion_cursor.prev(&());
1418 }
1419 } else {
1420 insertion_cursor.prev(&());
1421 }
1422 let insertion = insertion_cursor.item().expect("invalid insertion");
1423 debug_assert_eq!(insertion.timestamp, anchor.timestamp, "invalid insertion");
1424
1425 let mut fragment_cursor = self.fragments.cursor::<(Option<&Locator>, usize)>();
1426 fragment_cursor.seek(&Some(&insertion.fragment_id), Bias::Left, &None);
1427 let fragment = fragment_cursor.item().unwrap();
1428 let mut fragment_offset = fragment_cursor.start().1;
1429 if fragment.visible {
1430 fragment_offset += anchor.offset - insertion.split_offset;
1431 }
1432 self.text_summary_for_range(0..fragment_offset)
1433 }
1434 }
1435
1436 fn fragment_id_for_anchor(&self, anchor: &Anchor) -> &Locator {
1437 if *anchor == Anchor::min() {
1438 &locator::MIN
1439 } else if *anchor == Anchor::max() {
1440 &locator::MAX
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 &insertion.fragment_id
1463 }
1464 }
1465
1466 pub fn anchor_before<T: ToOffset>(&self, position: T) -> Anchor {
1467 self.anchor_at(position, Bias::Left)
1468 }
1469
1470 pub fn anchor_after<T: ToOffset>(&self, position: T) -> Anchor {
1471 self.anchor_at(position, Bias::Right)
1472 }
1473
1474 pub fn anchor_at<T: ToOffset>(&self, position: T, bias: Bias) -> Anchor {
1475 let offset = position.to_offset(self);
1476 if bias == Bias::Left && offset == 0 {
1477 Anchor::min()
1478 } else if bias == Bias::Right && offset == self.len() {
1479 Anchor::max()
1480 } else {
1481 let mut fragment_cursor = self.fragments.cursor::<usize>();
1482 fragment_cursor.seek(&offset, bias, &None);
1483 let fragment = fragment_cursor.item().unwrap();
1484 let overshoot = offset - *fragment_cursor.start();
1485 Anchor {
1486 timestamp: fragment.insertion_timestamp.local(),
1487 offset: fragment.insertion_offset + overshoot,
1488 bias,
1489 }
1490 }
1491 }
1492
1493 pub fn clip_offset(&self, offset: usize, bias: Bias) -> usize {
1494 self.visible_text.clip_offset(offset, bias)
1495 }
1496
1497 pub fn clip_point(&self, point: Point, bias: Bias) -> Point {
1498 self.visible_text.clip_point(point, bias)
1499 }
1500
1501 pub fn clip_point_utf16(&self, point: PointUtf16, bias: Bias) -> PointUtf16 {
1502 self.visible_text.clip_point_utf16(point, bias)
1503 }
1504
1505 // pub fn point_for_offset(&self, offset: usize) -> Result<Point> {
1506 // if offset <= self.len() {
1507 // Ok(self.text_summary_for_range(0..offset))
1508 // } else {
1509 // Err(anyhow!("offset out of bounds"))
1510 // }
1511 // }
1512
1513 pub fn edits_since<'a, D>(
1514 &'a self,
1515 since: &'a clock::Global,
1516 ) -> impl 'a + Iterator<Item = Edit<D>>
1517 where
1518 D: TextDimension + Ord,
1519 {
1520 self.edits_since_in_range(since, Anchor::min()..Anchor::max())
1521 }
1522
1523 pub fn edits_since_in_range<'a, D>(
1524 &'a self,
1525 since: &'a clock::Global,
1526 range: Range<Anchor>,
1527 ) -> impl 'a + Iterator<Item = Edit<D>>
1528 where
1529 D: TextDimension + Ord,
1530 {
1531 let fragments_cursor = if *since == self.version {
1532 None
1533 } else {
1534 Some(
1535 self.fragments
1536 .filter(move |summary| !since.ge(&summary.max_version), &None),
1537 )
1538 };
1539 let mut cursor = self
1540 .fragments
1541 .cursor::<(Option<&Locator>, FragmentTextSummary)>();
1542
1543 let start_fragment_id = self.fragment_id_for_anchor(&range.start);
1544 cursor.seek(&Some(start_fragment_id), Bias::Left, &None);
1545 let mut visible_start = cursor.start().1.visible;
1546 let mut deleted_start = cursor.start().1.deleted;
1547 if let Some(fragment) = cursor.item() {
1548 let overshoot = range.start.offset - fragment.insertion_offset;
1549 if fragment.visible {
1550 visible_start += overshoot;
1551 } else {
1552 deleted_start += overshoot;
1553 }
1554 }
1555 let end_fragment_id = self.fragment_id_for_anchor(&range.end);
1556
1557 Edits {
1558 visible_cursor: self.visible_text.cursor(visible_start),
1559 deleted_cursor: self.deleted_text.cursor(deleted_start),
1560 fragments_cursor,
1561 undos: &self.undo_map,
1562 since,
1563 old_end: Default::default(),
1564 new_end: Default::default(),
1565 range: (start_fragment_id, range.start.offset)..(end_fragment_id, range.end.offset),
1566 }
1567 }
1568}
1569
1570struct RopeBuilder<'a> {
1571 old_visible_cursor: rope::Cursor<'a>,
1572 old_deleted_cursor: rope::Cursor<'a>,
1573 new_visible: Rope,
1574 new_deleted: Rope,
1575}
1576
1577impl<'a> RopeBuilder<'a> {
1578 fn new(old_visible_cursor: rope::Cursor<'a>, old_deleted_cursor: rope::Cursor<'a>) -> Self {
1579 Self {
1580 old_visible_cursor,
1581 old_deleted_cursor,
1582 new_visible: Rope::new(),
1583 new_deleted: Rope::new(),
1584 }
1585 }
1586
1587 fn push_tree(&mut self, len: FragmentTextSummary) {
1588 self.push(len.visible, true, true);
1589 self.push(len.deleted, false, false);
1590 }
1591
1592 fn push_fragment(&mut self, fragment: &Fragment, was_visible: bool) {
1593 debug_assert!(fragment.len > 0);
1594 self.push(fragment.len, was_visible, fragment.visible)
1595 }
1596
1597 fn push(&mut self, len: usize, was_visible: bool, is_visible: bool) {
1598 let text = if was_visible {
1599 self.old_visible_cursor
1600 .slice(self.old_visible_cursor.offset() + len)
1601 } else {
1602 self.old_deleted_cursor
1603 .slice(self.old_deleted_cursor.offset() + len)
1604 };
1605 if is_visible {
1606 self.new_visible.append(text);
1607 } else {
1608 self.new_deleted.append(text);
1609 }
1610 }
1611
1612 fn push_str(&mut self, text: &str) {
1613 self.new_visible.push(text);
1614 }
1615
1616 fn finish(mut self) -> (Rope, Rope) {
1617 self.new_visible.append(self.old_visible_cursor.suffix());
1618 self.new_deleted.append(self.old_deleted_cursor.suffix());
1619 (self.new_visible, self.new_deleted)
1620 }
1621}
1622
1623impl<'a, D: TextDimension + Ord, F: FnMut(&FragmentSummary) -> bool> Iterator for Edits<'a, D, F> {
1624 type Item = Edit<D>;
1625
1626 fn next(&mut self) -> Option<Self::Item> {
1627 let mut pending_edit: Option<Edit<D>> = None;
1628 let cursor = self.fragments_cursor.as_mut()?;
1629
1630 while let Some(fragment) = cursor.item() {
1631 if fragment.id < *self.range.start.0 {
1632 cursor.next(&None);
1633 continue;
1634 } else if fragment.id > *self.range.end.0 {
1635 break;
1636 }
1637
1638 if cursor.start().visible > self.visible_cursor.offset() {
1639 let summary = self.visible_cursor.summary(cursor.start().visible);
1640 self.old_end.add_assign(&summary);
1641 self.new_end.add_assign(&summary);
1642 }
1643
1644 if pending_edit
1645 .as_ref()
1646 .map_or(false, |change| change.new.end < self.new_end)
1647 {
1648 break;
1649 }
1650
1651 if !fragment.was_visible(&self.since, &self.undos) && fragment.visible {
1652 let mut visible_end = cursor.end(&None).visible;
1653 if fragment.id == *self.range.end.0 {
1654 visible_end = cmp::min(
1655 visible_end,
1656 cursor.start().visible + (self.range.end.1 - fragment.insertion_offset),
1657 );
1658 }
1659
1660 let fragment_summary = self.visible_cursor.summary(visible_end);
1661 let mut new_end = self.new_end.clone();
1662 new_end.add_assign(&fragment_summary);
1663 if let Some(pending_edit) = pending_edit.as_mut() {
1664 pending_edit.new.end = new_end.clone();
1665 } else {
1666 pending_edit = Some(Edit {
1667 old: self.old_end.clone()..self.old_end.clone(),
1668 new: self.new_end.clone()..new_end.clone(),
1669 });
1670 }
1671
1672 self.new_end = new_end;
1673 } else if fragment.was_visible(&self.since, &self.undos) && !fragment.visible {
1674 let mut deleted_end = cursor.end(&None).deleted;
1675 if fragment.id == *self.range.end.0 {
1676 deleted_end = cmp::min(
1677 deleted_end,
1678 cursor.start().deleted + (self.range.end.1 - fragment.insertion_offset),
1679 );
1680 }
1681
1682 if cursor.start().deleted > self.deleted_cursor.offset() {
1683 self.deleted_cursor.seek_forward(cursor.start().deleted);
1684 }
1685 let fragment_summary = self.deleted_cursor.summary(deleted_end);
1686 let mut old_end = self.old_end.clone();
1687 old_end.add_assign(&fragment_summary);
1688 if let Some(pending_edit) = pending_edit.as_mut() {
1689 pending_edit.old.end = old_end.clone();
1690 } else {
1691 pending_edit = Some(Edit {
1692 old: self.old_end.clone()..old_end.clone(),
1693 new: self.new_end.clone()..self.new_end.clone(),
1694 });
1695 }
1696
1697 self.old_end = old_end;
1698 }
1699
1700 cursor.next(&None);
1701 }
1702
1703 pending_edit
1704 }
1705}
1706
1707impl Fragment {
1708 fn is_visible(&self, undos: &UndoMap) -> bool {
1709 !undos.is_undone(self.insertion_timestamp.local())
1710 && self.deletions.iter().all(|d| undos.is_undone(*d))
1711 }
1712
1713 fn was_visible(&self, version: &clock::Global, undos: &UndoMap) -> bool {
1714 (version.observed(self.insertion_timestamp.local())
1715 && !undos.was_undone(self.insertion_timestamp.local(), version))
1716 && self
1717 .deletions
1718 .iter()
1719 .all(|d| !version.observed(*d) || undos.was_undone(*d, version))
1720 }
1721}
1722
1723impl sum_tree::Item for Fragment {
1724 type Summary = FragmentSummary;
1725
1726 fn summary(&self) -> Self::Summary {
1727 let mut max_version = clock::Global::new();
1728 max_version.observe(self.insertion_timestamp.local());
1729 for deletion in &self.deletions {
1730 max_version.observe(*deletion);
1731 }
1732 max_version.join(&self.max_undos);
1733
1734 let mut min_insertion_version = clock::Global::new();
1735 min_insertion_version.observe(self.insertion_timestamp.local());
1736 let max_insertion_version = min_insertion_version.clone();
1737 if self.visible {
1738 FragmentSummary {
1739 max_id: self.id.clone(),
1740 text: FragmentTextSummary {
1741 visible: self.len,
1742 deleted: 0,
1743 },
1744 max_version,
1745 min_insertion_version,
1746 max_insertion_version,
1747 }
1748 } else {
1749 FragmentSummary {
1750 max_id: self.id.clone(),
1751 text: FragmentTextSummary {
1752 visible: 0,
1753 deleted: self.len,
1754 },
1755 max_version,
1756 min_insertion_version,
1757 max_insertion_version,
1758 }
1759 }
1760 }
1761}
1762
1763impl sum_tree::Summary for FragmentSummary {
1764 type Context = Option<clock::Global>;
1765
1766 fn add_summary(&mut self, other: &Self, _: &Self::Context) {
1767 self.max_id.assign(&other.max_id);
1768 self.text.visible += &other.text.visible;
1769 self.text.deleted += &other.text.deleted;
1770 self.max_version.join(&other.max_version);
1771 self.min_insertion_version
1772 .meet(&other.min_insertion_version);
1773 self.max_insertion_version
1774 .join(&other.max_insertion_version);
1775 }
1776}
1777
1778impl Default for FragmentSummary {
1779 fn default() -> Self {
1780 FragmentSummary {
1781 max_id: Locator::min(),
1782 text: FragmentTextSummary::default(),
1783 max_version: clock::Global::new(),
1784 min_insertion_version: clock::Global::new(),
1785 max_insertion_version: clock::Global::new(),
1786 }
1787 }
1788}
1789
1790impl sum_tree::Item for InsertionFragment {
1791 type Summary = InsertionFragmentKey;
1792
1793 fn summary(&self) -> Self::Summary {
1794 InsertionFragmentKey {
1795 timestamp: self.timestamp,
1796 split_offset: self.split_offset,
1797 }
1798 }
1799}
1800
1801impl sum_tree::KeyedItem for InsertionFragment {
1802 type Key = InsertionFragmentKey;
1803
1804 fn key(&self) -> Self::Key {
1805 sum_tree::Item::summary(self)
1806 }
1807}
1808
1809impl InsertionFragment {
1810 fn new(fragment: &Fragment) -> Self {
1811 Self {
1812 timestamp: fragment.insertion_timestamp.local(),
1813 split_offset: fragment.insertion_offset,
1814 fragment_id: fragment.id.clone(),
1815 }
1816 }
1817
1818 fn insert_new(fragment: &Fragment) -> sum_tree::Edit<Self> {
1819 sum_tree::Edit::Insert(Self::new(fragment))
1820 }
1821}
1822
1823impl sum_tree::Summary for InsertionFragmentKey {
1824 type Context = ();
1825
1826 fn add_summary(&mut self, summary: &Self, _: &()) {
1827 *self = *summary;
1828 }
1829}
1830
1831#[derive(Copy, Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
1832pub struct FullOffset(pub usize);
1833
1834impl ops::AddAssign<usize> for FullOffset {
1835 fn add_assign(&mut self, rhs: usize) {
1836 self.0 += rhs;
1837 }
1838}
1839
1840impl ops::Add<usize> for FullOffset {
1841 type Output = Self;
1842
1843 fn add(mut self, rhs: usize) -> Self::Output {
1844 self += rhs;
1845 self
1846 }
1847}
1848
1849impl ops::Sub for FullOffset {
1850 type Output = usize;
1851
1852 fn sub(self, rhs: Self) -> Self::Output {
1853 self.0 - rhs.0
1854 }
1855}
1856
1857impl<'a> sum_tree::Dimension<'a, FragmentSummary> for usize {
1858 fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
1859 *self += summary.text.visible;
1860 }
1861}
1862
1863impl<'a> sum_tree::Dimension<'a, FragmentSummary> for FullOffset {
1864 fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
1865 self.0 += summary.text.visible + summary.text.deleted;
1866 }
1867}
1868
1869impl<'a> sum_tree::Dimension<'a, FragmentSummary> for Option<&'a Locator> {
1870 fn add_summary(&mut self, summary: &'a FragmentSummary, _: &Option<clock::Global>) {
1871 *self = Some(&summary.max_id);
1872 }
1873}
1874
1875impl<'a> sum_tree::SeekTarget<'a, FragmentSummary, FragmentTextSummary> for usize {
1876 fn cmp(
1877 &self,
1878 cursor_location: &FragmentTextSummary,
1879 _: &Option<clock::Global>,
1880 ) -> cmp::Ordering {
1881 Ord::cmp(self, &cursor_location.visible)
1882 }
1883}
1884
1885#[derive(Copy, Clone, Debug, Eq, PartialEq)]
1886enum VersionedFullOffset {
1887 Offset(FullOffset),
1888 Invalid,
1889}
1890
1891impl VersionedFullOffset {
1892 fn full_offset(&self) -> FullOffset {
1893 if let Self::Offset(position) = self {
1894 *position
1895 } else {
1896 panic!("invalid version")
1897 }
1898 }
1899}
1900
1901impl Default for VersionedFullOffset {
1902 fn default() -> Self {
1903 Self::Offset(Default::default())
1904 }
1905}
1906
1907impl<'a> sum_tree::Dimension<'a, FragmentSummary> for VersionedFullOffset {
1908 fn add_summary(&mut self, summary: &'a FragmentSummary, cx: &Option<clock::Global>) {
1909 if let Self::Offset(offset) = self {
1910 let version = cx.as_ref().unwrap();
1911 if version.ge(&summary.max_insertion_version) {
1912 *offset += summary.text.visible + summary.text.deleted;
1913 } else if version.observed_any(&summary.min_insertion_version) {
1914 *self = Self::Invalid;
1915 }
1916 }
1917 }
1918}
1919
1920impl<'a> sum_tree::SeekTarget<'a, FragmentSummary, Self> for VersionedFullOffset {
1921 fn cmp(&self, cursor_position: &Self, _: &Option<clock::Global>) -> cmp::Ordering {
1922 match (self, cursor_position) {
1923 (Self::Offset(a), Self::Offset(b)) => Ord::cmp(a, b),
1924 (Self::Offset(_), Self::Invalid) => cmp::Ordering::Less,
1925 (Self::Invalid, _) => unreachable!(),
1926 }
1927 }
1928}
1929
1930impl Operation {
1931 fn replica_id(&self) -> ReplicaId {
1932 operation_queue::Operation::lamport_timestamp(self).replica_id
1933 }
1934
1935 pub fn is_edit(&self) -> bool {
1936 match self {
1937 Operation::Edit { .. } => true,
1938 _ => false,
1939 }
1940 }
1941}
1942
1943impl operation_queue::Operation for Operation {
1944 fn lamport_timestamp(&self) -> clock::Lamport {
1945 match self {
1946 Operation::Edit(edit) => edit.timestamp.lamport(),
1947 Operation::Undo {
1948 lamport_timestamp, ..
1949 } => *lamport_timestamp,
1950 }
1951 }
1952}
1953
1954pub trait ToOffset {
1955 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize;
1956}
1957
1958impl ToOffset for Point {
1959 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
1960 snapshot.point_to_offset(*self)
1961 }
1962}
1963
1964impl ToOffset for PointUtf16 {
1965 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
1966 snapshot.point_utf16_to_offset(*self)
1967 }
1968}
1969
1970impl ToOffset for usize {
1971 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
1972 assert!(*self <= snapshot.len(), "offset is out of range");
1973 *self
1974 }
1975}
1976
1977impl ToOffset for Anchor {
1978 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
1979 snapshot.summary_for_anchor(self)
1980 }
1981}
1982
1983impl<'a, T: ToOffset> ToOffset for &'a T {
1984 fn to_offset(&self, content: &BufferSnapshot) -> usize {
1985 (*self).to_offset(content)
1986 }
1987}
1988
1989pub trait ToPoint {
1990 fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point;
1991}
1992
1993impl ToPoint for Anchor {
1994 fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point {
1995 snapshot.summary_for_anchor(self)
1996 }
1997}
1998
1999impl ToPoint for usize {
2000 fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point {
2001 snapshot.offset_to_point(*self)
2002 }
2003}
2004
2005impl ToPoint for Point {
2006 fn to_point<'a>(&self, _: &BufferSnapshot) -> Point {
2007 *self
2008 }
2009}
2010
2011pub trait FromAnchor {
2012 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self;
2013}
2014
2015impl FromAnchor for Point {
2016 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
2017 anchor.to_point(snapshot)
2018 }
2019}
2020
2021impl FromAnchor for usize {
2022 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
2023 anchor.to_offset(snapshot)
2024 }
2025}