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