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