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