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