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