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