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 for fragment_id in self.fragment_ids_for_edits(undo.counts.keys()) {
1087 let preceding_fragments = old_fragments.slice(&Some(fragment_id), Bias::Left, &None);
1088 new_ropes.push_tree(preceding_fragments.summary().text);
1089 new_fragments.push_tree(preceding_fragments, &None);
1090
1091 if let Some(fragment) = old_fragments.item() {
1092 let mut fragment = fragment.clone();
1093 let fragment_was_visible = fragment.visible;
1094
1095 if fragment.was_visible(&undo.transaction_version, &self.undo_map)
1096 || undo
1097 .counts
1098 .contains_key(&fragment.insertion_timestamp.local())
1099 {
1100 fragment.visible = fragment.is_visible(&self.undo_map);
1101 fragment.max_undos.observe(undo.id);
1102 }
1103
1104 let old_start = old_fragments.start().1;
1105 let new_start = new_fragments.summary().text.visible;
1106 if fragment_was_visible && !fragment.visible {
1107 edits.push(Edit {
1108 old: old_start..old_start + fragment.len,
1109 new: new_start..new_start,
1110 });
1111 } else if !fragment_was_visible && fragment.visible {
1112 edits.push(Edit {
1113 old: old_start..old_start,
1114 new: new_start..new_start + fragment.len,
1115 });
1116 }
1117 new_ropes.push_fragment(&fragment, fragment_was_visible);
1118 new_fragments.push(fragment, &None);
1119
1120 old_fragments.next(&None);
1121 }
1122 }
1123
1124 let suffix = old_fragments.suffix(&None);
1125 new_ropes.push_tree(suffix.summary().text);
1126 new_fragments.push_tree(suffix, &None);
1127
1128 drop(old_fragments);
1129 let (visible_text, deleted_text) = new_ropes.finish();
1130 self.snapshot.fragments = new_fragments;
1131 self.snapshot.visible_text = visible_text;
1132 self.snapshot.deleted_text = deleted_text;
1133 self.subscriptions.publish_mut(&edits);
1134 Ok(())
1135 }
1136
1137 fn flush_deferred_ops(&mut self) -> Result<()> {
1138 self.deferred_replicas.clear();
1139 let mut deferred_ops = Vec::new();
1140 for op in self.deferred_ops.drain().iter().cloned() {
1141 if self.can_apply_op(&op) {
1142 self.apply_op(op)?;
1143 } else {
1144 self.deferred_replicas.insert(op.replica_id());
1145 deferred_ops.push(op);
1146 }
1147 }
1148 self.deferred_ops.insert(deferred_ops);
1149 Ok(())
1150 }
1151
1152 fn can_apply_op(&self, op: &Operation) -> bool {
1153 if self.deferred_replicas.contains(&op.replica_id()) {
1154 false
1155 } else {
1156 match op {
1157 Operation::Edit(edit) => self.version.observed_all(&edit.version),
1158 Operation::Undo { undo, .. } => self.version.observed_all(&undo.version),
1159 }
1160 }
1161 }
1162
1163 pub fn peek_undo_stack(&self) -> Option<&HistoryEntry> {
1164 self.history.undo_stack.last()
1165 }
1166
1167 pub fn peek_redo_stack(&self) -> Option<&HistoryEntry> {
1168 self.history.redo_stack.last()
1169 }
1170
1171 pub fn start_transaction(&mut self) -> Option<TransactionId> {
1172 self.start_transaction_at(Instant::now())
1173 }
1174
1175 pub fn start_transaction_at(&mut self, now: Instant) -> Option<TransactionId> {
1176 self.history
1177 .start_transaction(self.version.clone(), now, &mut self.local_clock)
1178 }
1179
1180 pub fn end_transaction(&mut self) -> Option<(TransactionId, clock::Global)> {
1181 self.end_transaction_at(Instant::now())
1182 }
1183
1184 pub fn end_transaction_at(&mut self, now: Instant) -> Option<(TransactionId, clock::Global)> {
1185 if let Some(entry) = self.history.end_transaction(now) {
1186 let since = entry.transaction.start.clone();
1187 let id = self.history.group().unwrap();
1188 Some((id, since))
1189 } else {
1190 None
1191 }
1192 }
1193
1194 pub fn finalize_last_transaction(&mut self) -> Option<&Transaction> {
1195 self.history.finalize_last_transaction()
1196 }
1197
1198 pub fn base_text(&self) -> &Arc<str> {
1199 &self.history.base_text
1200 }
1201
1202 pub fn history(&self) -> impl Iterator<Item = &Operation> {
1203 self.history.operations.values()
1204 }
1205
1206 pub fn undo_history(&self) -> impl Iterator<Item = (&clock::Local, &[(clock::Local, u32)])> {
1207 self.undo_map
1208 .0
1209 .iter()
1210 .map(|(edit_id, undo_counts)| (edit_id, undo_counts.as_slice()))
1211 }
1212
1213 pub fn undo(&mut self) -> Option<(TransactionId, Operation)> {
1214 if let Some(entry) = self.history.pop_undo() {
1215 let transaction = entry.transaction.clone();
1216 let transaction_id = transaction.id;
1217 let op = self.undo_or_redo(transaction).unwrap();
1218 Some((transaction_id, op))
1219 } else {
1220 None
1221 }
1222 }
1223
1224 pub fn undo_to_transaction(&mut self, transaction_id: TransactionId) -> Vec<Operation> {
1225 let transactions = self
1226 .history
1227 .remove_from_undo(transaction_id)
1228 .iter()
1229 .map(|entry| entry.transaction.clone())
1230 .collect::<Vec<_>>();
1231 transactions
1232 .into_iter()
1233 .map(|transaction| self.undo_or_redo(transaction).unwrap())
1234 .collect()
1235 }
1236
1237 pub fn forget_transaction(&mut self, transaction_id: TransactionId) {
1238 self.history.forget(transaction_id);
1239 }
1240
1241 pub fn redo(&mut self) -> Option<(TransactionId, Operation)> {
1242 if let Some(entry) = self.history.pop_redo() {
1243 let transaction = entry.transaction.clone();
1244 let transaction_id = transaction.id;
1245 let op = self.undo_or_redo(transaction).unwrap();
1246 Some((transaction_id, op))
1247 } else {
1248 None
1249 }
1250 }
1251
1252 pub fn redo_to_transaction(&mut self, transaction_id: TransactionId) -> Vec<Operation> {
1253 let transactions = self
1254 .history
1255 .remove_from_redo(transaction_id)
1256 .iter()
1257 .map(|entry| entry.transaction.clone())
1258 .collect::<Vec<_>>();
1259 transactions
1260 .into_iter()
1261 .map(|transaction| self.undo_or_redo(transaction).unwrap())
1262 .collect()
1263 }
1264
1265 fn undo_or_redo(&mut self, transaction: Transaction) -> Result<Operation> {
1266 let mut counts = HashMap::default();
1267 for edit_id in transaction.edit_ids {
1268 counts.insert(edit_id, self.undo_map.undo_count(edit_id) + 1);
1269 }
1270
1271 let undo = UndoOperation {
1272 id: self.local_clock.tick(),
1273 version: self.version(),
1274 counts,
1275 transaction_version: transaction.start.clone(),
1276 };
1277 self.apply_undo(&undo)?;
1278 let operation = Operation::Undo {
1279 undo,
1280 lamport_timestamp: self.lamport_clock.tick(),
1281 };
1282 self.snapshot.version.observe(operation.local_timestamp());
1283 self.history.push(operation.clone());
1284 Ok(operation)
1285 }
1286
1287 pub fn push_transaction(&mut self, transaction: Transaction, now: Instant) {
1288 self.history.push_transaction(transaction, now);
1289 self.history.finalize_last_transaction();
1290 }
1291
1292 pub fn edited_ranges_for_transaction<'a, D>(
1293 &'a self,
1294 transaction: &'a Transaction,
1295 ) -> impl 'a + Iterator<Item = Range<D>>
1296 where
1297 D: TextDimension,
1298 {
1299 // get fragment ranges
1300 let mut cursor = self.fragments.cursor::<(Option<&Locator>, usize)>();
1301 let offset_ranges = self
1302 .fragment_ids_for_edits(transaction.edit_ids.iter())
1303 .into_iter()
1304 .filter_map(move |fragment_id| {
1305 cursor.seek_forward(&Some(fragment_id), Bias::Left, &None);
1306 let fragment = cursor.item()?;
1307 let start_offset = cursor.start().1;
1308 let end_offset = start_offset + if fragment.visible { fragment.len } else { 0 };
1309 Some(start_offset..end_offset)
1310 });
1311
1312 // combine adjacent ranges
1313 let mut prev_range: Option<Range<usize>> = None;
1314 let disjoint_ranges = offset_ranges
1315 .map(Some)
1316 .chain([None])
1317 .filter_map(move |range| {
1318 if let Some((range, prev_range)) = range.as_ref().zip(prev_range.as_mut()) {
1319 if prev_range.end == range.start {
1320 prev_range.end = range.end;
1321 return None;
1322 }
1323 }
1324 let result = prev_range.clone();
1325 prev_range = range;
1326 result
1327 });
1328
1329 // convert to the desired text dimension.
1330 let mut position = D::default();
1331 let mut rope_cursor = self.visible_text.cursor(0);
1332 disjoint_ranges.map(move |range| {
1333 position.add_assign(&rope_cursor.summary(range.start));
1334 let start = position.clone();
1335 position.add_assign(&rope_cursor.summary(range.end));
1336 let end = position.clone();
1337 start..end
1338 })
1339 }
1340
1341 pub fn subscribe(&mut self) -> Subscription {
1342 self.subscriptions.subscribe()
1343 }
1344
1345 pub fn wait_for_edits(
1346 &mut self,
1347 edit_ids: impl IntoIterator<Item = clock::Local>,
1348 ) -> impl 'static + Future<Output = ()> {
1349 let mut futures = Vec::new();
1350 for edit_id in edit_ids {
1351 if !self.version.observed(edit_id) {
1352 let (tx, rx) = oneshot::channel();
1353 self.edit_id_resolvers.entry(edit_id).or_default().push(tx);
1354 futures.push(rx);
1355 }
1356 }
1357
1358 async move {
1359 for mut future in futures {
1360 future.recv().await;
1361 }
1362 }
1363 }
1364
1365 pub fn wait_for_anchors<'a>(
1366 &mut self,
1367 anchors: impl IntoIterator<Item = &'a Anchor>,
1368 ) -> impl 'static + Future<Output = ()> {
1369 let mut futures = Vec::new();
1370 for anchor in anchors {
1371 if !self.version.observed(anchor.timestamp)
1372 && *anchor != Anchor::MAX
1373 && *anchor != Anchor::MIN
1374 {
1375 let (tx, rx) = oneshot::channel();
1376 self.edit_id_resolvers
1377 .entry(anchor.timestamp)
1378 .or_default()
1379 .push(tx);
1380 futures.push(rx);
1381 }
1382 }
1383
1384 async move {
1385 for mut future in futures {
1386 future.recv().await;
1387 }
1388 }
1389 }
1390
1391 pub fn wait_for_version(&mut self, version: clock::Global) -> impl Future<Output = ()> {
1392 let (tx, mut rx) = barrier::channel();
1393 if !self.snapshot.version.observed_all(&version) {
1394 self.version_barriers.push((version, tx));
1395 }
1396 async move {
1397 rx.recv().await;
1398 }
1399 }
1400
1401 fn resolve_edit(&mut self, edit_id: clock::Local) {
1402 for mut tx in self
1403 .edit_id_resolvers
1404 .remove(&edit_id)
1405 .into_iter()
1406 .flatten()
1407 {
1408 let _ = tx.try_send(());
1409 }
1410 }
1411}
1412
1413#[cfg(any(test, feature = "test-support"))]
1414impl Buffer {
1415 pub fn check_invariants(&self) {
1416 // Ensure every fragment is ordered by locator in the fragment tree and corresponds
1417 // to an insertion fragment in the insertions tree.
1418 let mut prev_fragment_id = Locator::min();
1419 for fragment in self.snapshot.fragments.items(&None) {
1420 assert!(fragment.id > prev_fragment_id);
1421 prev_fragment_id = fragment.id.clone();
1422
1423 let insertion_fragment = self
1424 .snapshot
1425 .insertions
1426 .get(
1427 &InsertionFragmentKey {
1428 timestamp: fragment.insertion_timestamp.local(),
1429 split_offset: fragment.insertion_offset,
1430 },
1431 &(),
1432 )
1433 .unwrap();
1434 assert_eq!(
1435 insertion_fragment.fragment_id, fragment.id,
1436 "fragment: {:?}\ninsertion: {:?}",
1437 fragment, insertion_fragment
1438 );
1439 }
1440
1441 let mut cursor = self.snapshot.fragments.cursor::<Option<&Locator>>();
1442 for insertion_fragment in self.snapshot.insertions.cursor::<()>() {
1443 cursor.seek(&Some(&insertion_fragment.fragment_id), Bias::Left, &None);
1444 let fragment = cursor.item().unwrap();
1445 assert_eq!(insertion_fragment.fragment_id, fragment.id);
1446 assert_eq!(insertion_fragment.split_offset, fragment.insertion_offset);
1447 }
1448
1449 let fragment_summary = self.snapshot.fragments.summary();
1450 assert_eq!(
1451 fragment_summary.text.visible,
1452 self.snapshot.visible_text.len()
1453 );
1454 assert_eq!(
1455 fragment_summary.text.deleted,
1456 self.snapshot.deleted_text.len()
1457 );
1458
1459 assert!(!self.text().contains("\r\n"));
1460 }
1461
1462 pub fn set_group_interval(&mut self, group_interval: Duration) {
1463 self.history.group_interval = group_interval;
1464 }
1465
1466 pub fn random_byte_range(&self, start_offset: usize, rng: &mut impl rand::Rng) -> Range<usize> {
1467 let end = self.clip_offset(rng.gen_range(start_offset..=self.len()), Bias::Right);
1468 let start = self.clip_offset(rng.gen_range(start_offset..=end), Bias::Right);
1469 start..end
1470 }
1471
1472 pub fn randomly_edit<T>(
1473 &mut self,
1474 rng: &mut T,
1475 edit_count: usize,
1476 ) -> (Vec<(Range<usize>, Arc<str>)>, Operation)
1477 where
1478 T: rand::Rng,
1479 {
1480 let mut edits: Vec<(Range<usize>, Arc<str>)> = Vec::new();
1481 let mut last_end = None;
1482 for _ in 0..edit_count {
1483 if last_end.map_or(false, |last_end| last_end >= self.len()) {
1484 break;
1485 }
1486 let new_start = last_end.map_or(0, |last_end| last_end + 1);
1487 let range = self.random_byte_range(new_start, rng);
1488 last_end = Some(range.end);
1489
1490 let new_text_len = rng.gen_range(0..10);
1491 let new_text: String = crate::random_char_iter::RandomCharIter::new(&mut *rng)
1492 .take(new_text_len)
1493 .collect();
1494
1495 edits.push((range, new_text.into()));
1496 }
1497
1498 log::info!("mutating buffer {} with {:?}", self.replica_id, edits);
1499 let op = self.edit(edits.iter().cloned());
1500 if let Operation::Edit(edit) = &op {
1501 assert_eq!(edits.len(), edit.new_text.len());
1502 for (edit, new_text) in edits.iter_mut().zip(&edit.new_text) {
1503 edit.1 = new_text.clone();
1504 }
1505 } else {
1506 unreachable!()
1507 }
1508
1509 (edits, op)
1510 }
1511
1512 pub fn randomly_undo_redo(&mut self, rng: &mut impl rand::Rng) -> Vec<Operation> {
1513 use rand::prelude::*;
1514
1515 let mut ops = Vec::new();
1516 for _ in 0..rng.gen_range(1..=5) {
1517 if let Some(entry) = self.history.undo_stack.choose(rng) {
1518 let transaction = entry.transaction.clone();
1519 log::info!(
1520 "undoing buffer {} transaction {:?}",
1521 self.replica_id,
1522 transaction
1523 );
1524 ops.push(self.undo_or_redo(transaction).unwrap());
1525 }
1526 }
1527 ops
1528 }
1529}
1530
1531impl Deref for Buffer {
1532 type Target = BufferSnapshot;
1533
1534 fn deref(&self) -> &Self::Target {
1535 &self.snapshot
1536 }
1537}
1538
1539impl BufferSnapshot {
1540 pub fn as_rope(&self) -> &Rope {
1541 &self.visible_text
1542 }
1543
1544 pub fn replica_id(&self) -> ReplicaId {
1545 self.replica_id
1546 }
1547
1548 pub fn row_count(&self) -> u32 {
1549 self.max_point().row + 1
1550 }
1551
1552 pub fn len(&self) -> usize {
1553 self.visible_text.len()
1554 }
1555
1556 pub fn chars(&self) -> impl Iterator<Item = char> + '_ {
1557 self.chars_at(0)
1558 }
1559
1560 pub fn chars_for_range<T: ToOffset>(&self, range: Range<T>) -> impl Iterator<Item = char> + '_ {
1561 self.text_for_range(range).flat_map(str::chars)
1562 }
1563
1564 pub fn contains_str_at<T>(&self, position: T, needle: &str) -> bool
1565 where
1566 T: ToOffset,
1567 {
1568 let position = position.to_offset(self);
1569 position == self.clip_offset(position, Bias::Left)
1570 && self
1571 .bytes_in_range(position..self.len())
1572 .flatten()
1573 .copied()
1574 .take(needle.len())
1575 .eq(needle.bytes())
1576 }
1577
1578 pub fn common_prefix_at<T>(&self, position: T, needle: &str) -> Range<T>
1579 where
1580 T: ToOffset + TextDimension,
1581 {
1582 let offset = position.to_offset(self);
1583 let common_prefix_len = needle
1584 .char_indices()
1585 .map(|(index, _)| index)
1586 .chain([needle.len()])
1587 .take_while(|&len| len <= offset)
1588 .filter(|&len| {
1589 let left = self
1590 .chars_for_range(offset - len..offset)
1591 .flat_map(|c| char::to_lowercase(c));
1592 let right = needle[..len].chars().flat_map(|c| char::to_lowercase(c));
1593 left.eq(right)
1594 })
1595 .last()
1596 .unwrap_or(0);
1597 let start_offset = offset - common_prefix_len;
1598 let start = self.text_summary_for_range(0..start_offset);
1599 start..position
1600 }
1601
1602 pub fn text(&self) -> String {
1603 self.visible_text.to_string()
1604 }
1605
1606 pub fn line_ending(&self) -> LineEnding {
1607 self.line_ending
1608 }
1609
1610 pub fn deleted_text(&self) -> String {
1611 self.deleted_text.to_string()
1612 }
1613
1614 pub fn fragments(&self) -> impl Iterator<Item = &Fragment> {
1615 self.fragments.iter()
1616 }
1617
1618 pub fn text_summary(&self) -> TextSummary {
1619 self.visible_text.summary()
1620 }
1621
1622 pub fn max_point(&self) -> Point {
1623 self.visible_text.max_point()
1624 }
1625
1626 pub fn max_point_utf16(&self) -> PointUtf16 {
1627 self.visible_text.max_point_utf16()
1628 }
1629
1630 pub fn point_to_offset(&self, point: Point) -> usize {
1631 self.visible_text.point_to_offset(point)
1632 }
1633
1634 pub fn point_utf16_to_offset(&self, point: PointUtf16) -> usize {
1635 self.visible_text.point_utf16_to_offset(point)
1636 }
1637
1638 pub fn point_utf16_to_point(&self, point: PointUtf16) -> Point {
1639 self.visible_text.point_utf16_to_point(point)
1640 }
1641
1642 pub fn offset_utf16_to_offset(&self, offset: OffsetUtf16) -> usize {
1643 self.visible_text.offset_utf16_to_offset(offset)
1644 }
1645
1646 pub fn offset_to_offset_utf16(&self, offset: usize) -> OffsetUtf16 {
1647 self.visible_text.offset_to_offset_utf16(offset)
1648 }
1649
1650 pub fn offset_to_point(&self, offset: usize) -> Point {
1651 self.visible_text.offset_to_point(offset)
1652 }
1653
1654 pub fn offset_to_point_utf16(&self, offset: usize) -> PointUtf16 {
1655 self.visible_text.offset_to_point_utf16(offset)
1656 }
1657
1658 pub fn point_to_point_utf16(&self, point: Point) -> PointUtf16 {
1659 self.visible_text.point_to_point_utf16(point)
1660 }
1661
1662 pub fn version(&self) -> &clock::Global {
1663 &self.version
1664 }
1665
1666 pub fn chars_at<'a, T: ToOffset>(&'a self, position: T) -> impl Iterator<Item = char> + 'a {
1667 let offset = position.to_offset(self);
1668 self.visible_text.chars_at(offset)
1669 }
1670
1671 pub fn reversed_chars_at<'a, T: ToOffset>(
1672 &'a self,
1673 position: T,
1674 ) -> impl Iterator<Item = char> + 'a {
1675 let offset = position.to_offset(self);
1676 self.visible_text.reversed_chars_at(offset)
1677 }
1678
1679 pub fn reversed_chunks_in_range<T: ToOffset>(&self, range: Range<T>) -> rope::Chunks {
1680 let range = range.start.to_offset(self)..range.end.to_offset(self);
1681 self.visible_text.reversed_chunks_in_range(range)
1682 }
1683
1684 pub fn bytes_in_range<'a, T: ToOffset>(&'a self, range: Range<T>) -> rope::Bytes<'a> {
1685 let start = range.start.to_offset(self);
1686 let end = range.end.to_offset(self);
1687 self.visible_text.bytes_in_range(start..end)
1688 }
1689
1690 pub fn text_for_range<'a, T: ToOffset>(&'a self, range: Range<T>) -> Chunks<'a> {
1691 let start = range.start.to_offset(self);
1692 let end = range.end.to_offset(self);
1693 self.visible_text.chunks_in_range(start..end)
1694 }
1695
1696 pub fn line_len(&self, row: u32) -> u32 {
1697 let row_start_offset = Point::new(row, 0).to_offset(self);
1698 let row_end_offset = if row >= self.max_point().row {
1699 self.len()
1700 } else {
1701 Point::new(row + 1, 0).to_offset(self) - 1
1702 };
1703 (row_end_offset - row_start_offset) as u32
1704 }
1705
1706 pub fn is_line_blank(&self, row: u32) -> bool {
1707 self.text_for_range(Point::new(row, 0)..Point::new(row, self.line_len(row)))
1708 .all(|chunk| chunk.matches(|c: char| !c.is_whitespace()).next().is_none())
1709 }
1710
1711 pub fn text_summary_for_range<'a, D, O: ToOffset>(&'a self, range: Range<O>) -> D
1712 where
1713 D: TextDimension,
1714 {
1715 self.visible_text
1716 .cursor(range.start.to_offset(self))
1717 .summary(range.end.to_offset(self))
1718 }
1719
1720 pub fn summaries_for_anchors<'a, D, A>(&'a self, anchors: A) -> impl 'a + Iterator<Item = D>
1721 where
1722 D: 'a + TextDimension,
1723 A: 'a + IntoIterator<Item = &'a Anchor>,
1724 {
1725 let anchors = anchors.into_iter();
1726 let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>();
1727 let mut fragment_cursor = self.fragments.cursor::<(Option<&Locator>, usize)>();
1728 let mut text_cursor = self.visible_text.cursor(0);
1729 let mut position = D::default();
1730
1731 anchors.map(move |anchor| {
1732 if *anchor == Anchor::MIN {
1733 return D::default();
1734 } else if *anchor == Anchor::MAX {
1735 return D::from_text_summary(&self.visible_text.summary());
1736 }
1737
1738 let anchor_key = InsertionFragmentKey {
1739 timestamp: anchor.timestamp,
1740 split_offset: anchor.offset,
1741 };
1742 insertion_cursor.seek(&anchor_key, anchor.bias, &());
1743 if let Some(insertion) = insertion_cursor.item() {
1744 let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
1745 if comparison == Ordering::Greater
1746 || (anchor.bias == Bias::Left
1747 && comparison == Ordering::Equal
1748 && anchor.offset > 0)
1749 {
1750 insertion_cursor.prev(&());
1751 }
1752 } else {
1753 insertion_cursor.prev(&());
1754 }
1755 let insertion = insertion_cursor.item().expect("invalid insertion");
1756 assert_eq!(insertion.timestamp, anchor.timestamp, "invalid insertion");
1757
1758 fragment_cursor.seek_forward(&Some(&insertion.fragment_id), Bias::Left, &None);
1759 let fragment = fragment_cursor.item().unwrap();
1760 let mut fragment_offset = fragment_cursor.start().1;
1761 if fragment.visible {
1762 fragment_offset += anchor.offset - insertion.split_offset;
1763 }
1764
1765 position.add_assign(&text_cursor.summary(fragment_offset));
1766 position.clone()
1767 })
1768 }
1769
1770 fn summary_for_anchor<'a, D>(&'a self, anchor: &Anchor) -> D
1771 where
1772 D: TextDimension,
1773 {
1774 if *anchor == Anchor::MIN {
1775 D::default()
1776 } else if *anchor == Anchor::MAX {
1777 D::from_text_summary(&self.visible_text.summary())
1778 } else {
1779 let anchor_key = InsertionFragmentKey {
1780 timestamp: anchor.timestamp,
1781 split_offset: anchor.offset,
1782 };
1783 let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>();
1784 insertion_cursor.seek(&anchor_key, anchor.bias, &());
1785 if let Some(insertion) = insertion_cursor.item() {
1786 let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
1787 if comparison == Ordering::Greater
1788 || (anchor.bias == Bias::Left
1789 && comparison == Ordering::Equal
1790 && anchor.offset > 0)
1791 {
1792 insertion_cursor.prev(&());
1793 }
1794 } else {
1795 insertion_cursor.prev(&());
1796 }
1797 let insertion = insertion_cursor.item().expect("invalid insertion");
1798 assert_eq!(insertion.timestamp, anchor.timestamp, "invalid insertion");
1799
1800 let mut fragment_cursor = self.fragments.cursor::<(Option<&Locator>, usize)>();
1801 fragment_cursor.seek(&Some(&insertion.fragment_id), Bias::Left, &None);
1802 let fragment = fragment_cursor.item().unwrap();
1803 let mut fragment_offset = fragment_cursor.start().1;
1804 if fragment.visible {
1805 fragment_offset += anchor.offset - insertion.split_offset;
1806 }
1807 self.text_summary_for_range(0..fragment_offset)
1808 }
1809 }
1810
1811 fn fragment_id_for_anchor(&self, anchor: &Anchor) -> &Locator {
1812 if *anchor == Anchor::MIN {
1813 &locator::MIN
1814 } else if *anchor == Anchor::MAX {
1815 &locator::MAX
1816 } else {
1817 let anchor_key = InsertionFragmentKey {
1818 timestamp: anchor.timestamp,
1819 split_offset: anchor.offset,
1820 };
1821 let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>();
1822 insertion_cursor.seek(&anchor_key, anchor.bias, &());
1823 if let Some(insertion) = insertion_cursor.item() {
1824 let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
1825 if comparison == Ordering::Greater
1826 || (anchor.bias == Bias::Left
1827 && comparison == Ordering::Equal
1828 && anchor.offset > 0)
1829 {
1830 insertion_cursor.prev(&());
1831 }
1832 } else {
1833 insertion_cursor.prev(&());
1834 }
1835 let insertion = insertion_cursor.item().expect("invalid insertion");
1836 debug_assert_eq!(insertion.timestamp, anchor.timestamp, "invalid insertion");
1837 &insertion.fragment_id
1838 }
1839 }
1840
1841 pub fn anchor_before<T: ToOffset>(&self, position: T) -> Anchor {
1842 self.anchor_at(position, Bias::Left)
1843 }
1844
1845 pub fn anchor_after<T: ToOffset>(&self, position: T) -> Anchor {
1846 self.anchor_at(position, Bias::Right)
1847 }
1848
1849 pub fn anchor_at<T: ToOffset>(&self, position: T, bias: Bias) -> Anchor {
1850 let offset = position.to_offset(self);
1851 if bias == Bias::Left && offset == 0 {
1852 Anchor::MIN
1853 } else if bias == Bias::Right && offset == self.len() {
1854 Anchor::MAX
1855 } else {
1856 let mut fragment_cursor = self.fragments.cursor::<usize>();
1857 fragment_cursor.seek(&offset, bias, &None);
1858 let fragment = fragment_cursor.item().unwrap();
1859 let overshoot = offset - *fragment_cursor.start();
1860 Anchor {
1861 timestamp: fragment.insertion_timestamp.local(),
1862 offset: fragment.insertion_offset + overshoot,
1863 bias,
1864 buffer_id: Some(self.remote_id),
1865 }
1866 }
1867 }
1868
1869 pub fn can_resolve(&self, anchor: &Anchor) -> bool {
1870 *anchor == Anchor::MIN
1871 || *anchor == Anchor::MAX
1872 || (Some(self.remote_id) == anchor.buffer_id && self.version.observed(anchor.timestamp))
1873 }
1874
1875 pub fn clip_offset(&self, offset: usize, bias: Bias) -> usize {
1876 self.visible_text.clip_offset(offset, bias)
1877 }
1878
1879 pub fn clip_point(&self, point: Point, bias: Bias) -> Point {
1880 self.visible_text.clip_point(point, bias)
1881 }
1882
1883 pub fn clip_point_utf16(&self, point: PointUtf16, bias: Bias) -> PointUtf16 {
1884 self.visible_text.clip_point_utf16(point, bias)
1885 }
1886
1887 pub fn edits_since<'a, D>(
1888 &'a self,
1889 since: &'a clock::Global,
1890 ) -> impl 'a + Iterator<Item = Edit<D>>
1891 where
1892 D: TextDimension + Ord,
1893 {
1894 self.edits_since_in_range(since, Anchor::MIN..Anchor::MAX)
1895 }
1896
1897 pub fn edits_since_in_range<'a, D>(
1898 &'a self,
1899 since: &'a clock::Global,
1900 range: Range<Anchor>,
1901 ) -> impl 'a + Iterator<Item = Edit<D>>
1902 where
1903 D: TextDimension + Ord,
1904 {
1905 let fragments_cursor = if *since == self.version {
1906 None
1907 } else {
1908 let mut cursor = self
1909 .fragments
1910 .filter(move |summary| !since.observed_all(&summary.max_version));
1911 cursor.next(&None);
1912 Some(cursor)
1913 };
1914 let mut cursor = self
1915 .fragments
1916 .cursor::<(Option<&Locator>, FragmentTextSummary)>();
1917
1918 let start_fragment_id = self.fragment_id_for_anchor(&range.start);
1919 cursor.seek(&Some(start_fragment_id), Bias::Left, &None);
1920 let mut visible_start = cursor.start().1.visible;
1921 let mut deleted_start = cursor.start().1.deleted;
1922 if let Some(fragment) = cursor.item() {
1923 let overshoot = range.start.offset - fragment.insertion_offset;
1924 if fragment.visible {
1925 visible_start += overshoot;
1926 } else {
1927 deleted_start += overshoot;
1928 }
1929 }
1930 let end_fragment_id = self.fragment_id_for_anchor(&range.end);
1931
1932 Edits {
1933 visible_cursor: self.visible_text.cursor(visible_start),
1934 deleted_cursor: self.deleted_text.cursor(deleted_start),
1935 fragments_cursor,
1936 undos: &self.undo_map,
1937 since,
1938 old_end: Default::default(),
1939 new_end: Default::default(),
1940 range: (start_fragment_id, range.start.offset)..(end_fragment_id, range.end.offset),
1941 }
1942 }
1943}
1944
1945struct RopeBuilder<'a> {
1946 old_visible_cursor: rope::Cursor<'a>,
1947 old_deleted_cursor: rope::Cursor<'a>,
1948 new_visible: Rope,
1949 new_deleted: Rope,
1950}
1951
1952impl<'a> RopeBuilder<'a> {
1953 fn new(old_visible_cursor: rope::Cursor<'a>, old_deleted_cursor: rope::Cursor<'a>) -> Self {
1954 Self {
1955 old_visible_cursor,
1956 old_deleted_cursor,
1957 new_visible: Rope::new(),
1958 new_deleted: Rope::new(),
1959 }
1960 }
1961
1962 fn push_tree(&mut self, len: FragmentTextSummary) {
1963 self.push(len.visible, true, true);
1964 self.push(len.deleted, false, false);
1965 }
1966
1967 fn push_fragment(&mut self, fragment: &Fragment, was_visible: bool) {
1968 debug_assert!(fragment.len > 0);
1969 self.push(fragment.len, was_visible, fragment.visible)
1970 }
1971
1972 fn push(&mut self, len: usize, was_visible: bool, is_visible: bool) {
1973 let text = if was_visible {
1974 self.old_visible_cursor
1975 .slice(self.old_visible_cursor.offset() + len)
1976 } else {
1977 self.old_deleted_cursor
1978 .slice(self.old_deleted_cursor.offset() + len)
1979 };
1980 if is_visible {
1981 self.new_visible.append(text);
1982 } else {
1983 self.new_deleted.append(text);
1984 }
1985 }
1986
1987 fn push_str(&mut self, text: &str) {
1988 self.new_visible.push(text);
1989 }
1990
1991 fn finish(mut self) -> (Rope, Rope) {
1992 self.new_visible.append(self.old_visible_cursor.suffix());
1993 self.new_deleted.append(self.old_deleted_cursor.suffix());
1994 (self.new_visible, self.new_deleted)
1995 }
1996}
1997
1998impl<'a, D: TextDimension + Ord, F: FnMut(&FragmentSummary) -> bool> Iterator for Edits<'a, D, F> {
1999 type Item = Edit<D>;
2000
2001 fn next(&mut self) -> Option<Self::Item> {
2002 let mut pending_edit: Option<Edit<D>> = None;
2003 let cursor = self.fragments_cursor.as_mut()?;
2004
2005 while let Some(fragment) = cursor.item() {
2006 if fragment.id < *self.range.start.0 {
2007 cursor.next(&None);
2008 continue;
2009 } else if fragment.id > *self.range.end.0 {
2010 break;
2011 }
2012
2013 if cursor.start().visible > self.visible_cursor.offset() {
2014 let summary = self.visible_cursor.summary(cursor.start().visible);
2015 self.old_end.add_assign(&summary);
2016 self.new_end.add_assign(&summary);
2017 }
2018
2019 if pending_edit
2020 .as_ref()
2021 .map_or(false, |change| change.new.end < self.new_end)
2022 {
2023 break;
2024 }
2025
2026 if !fragment.was_visible(&self.since, &self.undos) && fragment.visible {
2027 let mut visible_end = cursor.end(&None).visible;
2028 if fragment.id == *self.range.end.0 {
2029 visible_end = cmp::min(
2030 visible_end,
2031 cursor.start().visible + (self.range.end.1 - fragment.insertion_offset),
2032 );
2033 }
2034
2035 let fragment_summary = self.visible_cursor.summary(visible_end);
2036 let mut new_end = self.new_end.clone();
2037 new_end.add_assign(&fragment_summary);
2038 if let Some(pending_edit) = pending_edit.as_mut() {
2039 pending_edit.new.end = new_end.clone();
2040 } else {
2041 pending_edit = Some(Edit {
2042 old: self.old_end.clone()..self.old_end.clone(),
2043 new: self.new_end.clone()..new_end.clone(),
2044 });
2045 }
2046
2047 self.new_end = new_end;
2048 } else if fragment.was_visible(&self.since, &self.undos) && !fragment.visible {
2049 let mut deleted_end = cursor.end(&None).deleted;
2050 if fragment.id == *self.range.end.0 {
2051 deleted_end = cmp::min(
2052 deleted_end,
2053 cursor.start().deleted + (self.range.end.1 - fragment.insertion_offset),
2054 );
2055 }
2056
2057 if cursor.start().deleted > self.deleted_cursor.offset() {
2058 self.deleted_cursor.seek_forward(cursor.start().deleted);
2059 }
2060 let fragment_summary = self.deleted_cursor.summary(deleted_end);
2061 let mut old_end = self.old_end.clone();
2062 old_end.add_assign(&fragment_summary);
2063 if let Some(pending_edit) = pending_edit.as_mut() {
2064 pending_edit.old.end = old_end.clone();
2065 } else {
2066 pending_edit = Some(Edit {
2067 old: self.old_end.clone()..old_end.clone(),
2068 new: self.new_end.clone()..self.new_end.clone(),
2069 });
2070 }
2071
2072 self.old_end = old_end;
2073 }
2074
2075 cursor.next(&None);
2076 }
2077
2078 pending_edit
2079 }
2080}
2081
2082impl Fragment {
2083 fn insertion_slice(&self) -> InsertionSlice {
2084 InsertionSlice {
2085 insertion_id: self.insertion_timestamp.local(),
2086 range: self.insertion_offset..self.insertion_offset + self.len,
2087 }
2088 }
2089
2090 fn is_visible(&self, undos: &UndoMap) -> bool {
2091 !undos.is_undone(self.insertion_timestamp.local())
2092 && self.deletions.iter().all(|d| undos.is_undone(*d))
2093 }
2094
2095 fn was_visible(&self, version: &clock::Global, undos: &UndoMap) -> bool {
2096 (version.observed(self.insertion_timestamp.local())
2097 && !undos.was_undone(self.insertion_timestamp.local(), version))
2098 && self
2099 .deletions
2100 .iter()
2101 .all(|d| !version.observed(*d) || undos.was_undone(*d, version))
2102 }
2103}
2104
2105impl sum_tree::Item for Fragment {
2106 type Summary = FragmentSummary;
2107
2108 fn summary(&self) -> Self::Summary {
2109 let mut max_version = clock::Global::new();
2110 max_version.observe(self.insertion_timestamp.local());
2111 for deletion in &self.deletions {
2112 max_version.observe(*deletion);
2113 }
2114 max_version.join(&self.max_undos);
2115
2116 let mut min_insertion_version = clock::Global::new();
2117 min_insertion_version.observe(self.insertion_timestamp.local());
2118 let max_insertion_version = min_insertion_version.clone();
2119 if self.visible {
2120 FragmentSummary {
2121 max_id: self.id.clone(),
2122 text: FragmentTextSummary {
2123 visible: self.len,
2124 deleted: 0,
2125 },
2126 max_version,
2127 min_insertion_version,
2128 max_insertion_version,
2129 }
2130 } else {
2131 FragmentSummary {
2132 max_id: self.id.clone(),
2133 text: FragmentTextSummary {
2134 visible: 0,
2135 deleted: self.len,
2136 },
2137 max_version,
2138 min_insertion_version,
2139 max_insertion_version,
2140 }
2141 }
2142 }
2143}
2144
2145impl sum_tree::Summary for FragmentSummary {
2146 type Context = Option<clock::Global>;
2147
2148 fn add_summary(&mut self, other: &Self, _: &Self::Context) {
2149 self.max_id.assign(&other.max_id);
2150 self.text.visible += &other.text.visible;
2151 self.text.deleted += &other.text.deleted;
2152 self.max_version.join(&other.max_version);
2153 self.min_insertion_version
2154 .meet(&other.min_insertion_version);
2155 self.max_insertion_version
2156 .join(&other.max_insertion_version);
2157 }
2158}
2159
2160impl Default for FragmentSummary {
2161 fn default() -> Self {
2162 FragmentSummary {
2163 max_id: Locator::min(),
2164 text: FragmentTextSummary::default(),
2165 max_version: clock::Global::new(),
2166 min_insertion_version: clock::Global::new(),
2167 max_insertion_version: clock::Global::new(),
2168 }
2169 }
2170}
2171
2172impl sum_tree::Item for InsertionFragment {
2173 type Summary = InsertionFragmentKey;
2174
2175 fn summary(&self) -> Self::Summary {
2176 InsertionFragmentKey {
2177 timestamp: self.timestamp,
2178 split_offset: self.split_offset,
2179 }
2180 }
2181}
2182
2183impl sum_tree::KeyedItem for InsertionFragment {
2184 type Key = InsertionFragmentKey;
2185
2186 fn key(&self) -> Self::Key {
2187 sum_tree::Item::summary(self)
2188 }
2189}
2190
2191impl InsertionFragment {
2192 fn new(fragment: &Fragment) -> Self {
2193 Self {
2194 timestamp: fragment.insertion_timestamp.local(),
2195 split_offset: fragment.insertion_offset,
2196 fragment_id: fragment.id.clone(),
2197 }
2198 }
2199
2200 fn insert_new(fragment: &Fragment) -> sum_tree::Edit<Self> {
2201 sum_tree::Edit::Insert(Self::new(fragment))
2202 }
2203}
2204
2205impl sum_tree::Summary for InsertionFragmentKey {
2206 type Context = ();
2207
2208 fn add_summary(&mut self, summary: &Self, _: &()) {
2209 *self = *summary;
2210 }
2211}
2212
2213#[derive(Copy, Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
2214pub struct FullOffset(pub usize);
2215
2216impl ops::AddAssign<usize> for FullOffset {
2217 fn add_assign(&mut self, rhs: usize) {
2218 self.0 += rhs;
2219 }
2220}
2221
2222impl ops::Add<usize> for FullOffset {
2223 type Output = Self;
2224
2225 fn add(mut self, rhs: usize) -> Self::Output {
2226 self += rhs;
2227 self
2228 }
2229}
2230
2231impl ops::Sub for FullOffset {
2232 type Output = usize;
2233
2234 fn sub(self, rhs: Self) -> Self::Output {
2235 self.0 - rhs.0
2236 }
2237}
2238
2239impl<'a> sum_tree::Dimension<'a, FragmentSummary> for usize {
2240 fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
2241 *self += summary.text.visible;
2242 }
2243}
2244
2245impl<'a> sum_tree::Dimension<'a, FragmentSummary> for FullOffset {
2246 fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
2247 self.0 += summary.text.visible + summary.text.deleted;
2248 }
2249}
2250
2251impl<'a> sum_tree::Dimension<'a, FragmentSummary> for Option<&'a Locator> {
2252 fn add_summary(&mut self, summary: &'a FragmentSummary, _: &Option<clock::Global>) {
2253 *self = Some(&summary.max_id);
2254 }
2255}
2256
2257impl<'a> sum_tree::SeekTarget<'a, FragmentSummary, FragmentTextSummary> for usize {
2258 fn cmp(
2259 &self,
2260 cursor_location: &FragmentTextSummary,
2261 _: &Option<clock::Global>,
2262 ) -> cmp::Ordering {
2263 Ord::cmp(self, &cursor_location.visible)
2264 }
2265}
2266
2267#[derive(Copy, Clone, Debug, Eq, PartialEq)]
2268enum VersionedFullOffset {
2269 Offset(FullOffset),
2270 Invalid,
2271}
2272
2273impl VersionedFullOffset {
2274 fn full_offset(&self) -> FullOffset {
2275 if let Self::Offset(position) = self {
2276 *position
2277 } else {
2278 panic!("invalid version")
2279 }
2280 }
2281}
2282
2283impl Default for VersionedFullOffset {
2284 fn default() -> Self {
2285 Self::Offset(Default::default())
2286 }
2287}
2288
2289impl<'a> sum_tree::Dimension<'a, FragmentSummary> for VersionedFullOffset {
2290 fn add_summary(&mut self, summary: &'a FragmentSummary, cx: &Option<clock::Global>) {
2291 if let Self::Offset(offset) = self {
2292 let version = cx.as_ref().unwrap();
2293 if version.observed_all(&summary.max_insertion_version) {
2294 *offset += summary.text.visible + summary.text.deleted;
2295 } else if version.observed_any(&summary.min_insertion_version) {
2296 *self = Self::Invalid;
2297 }
2298 }
2299 }
2300}
2301
2302impl<'a> sum_tree::SeekTarget<'a, FragmentSummary, Self> for VersionedFullOffset {
2303 fn cmp(&self, cursor_position: &Self, _: &Option<clock::Global>) -> cmp::Ordering {
2304 match (self, cursor_position) {
2305 (Self::Offset(a), Self::Offset(b)) => Ord::cmp(a, b),
2306 (Self::Offset(_), Self::Invalid) => cmp::Ordering::Less,
2307 (Self::Invalid, _) => unreachable!(),
2308 }
2309 }
2310}
2311
2312impl Operation {
2313 fn replica_id(&self) -> ReplicaId {
2314 operation_queue::Operation::lamport_timestamp(self).replica_id
2315 }
2316
2317 pub fn local_timestamp(&self) -> clock::Local {
2318 match self {
2319 Operation::Edit(edit) => edit.timestamp.local(),
2320 Operation::Undo { undo, .. } => undo.id,
2321 }
2322 }
2323
2324 pub fn as_edit(&self) -> Option<&EditOperation> {
2325 match self {
2326 Operation::Edit(edit) => Some(edit),
2327 _ => None,
2328 }
2329 }
2330
2331 pub fn is_edit(&self) -> bool {
2332 match self {
2333 Operation::Edit { .. } => true,
2334 _ => false,
2335 }
2336 }
2337}
2338
2339impl operation_queue::Operation for Operation {
2340 fn lamport_timestamp(&self) -> clock::Lamport {
2341 match self {
2342 Operation::Edit(edit) => edit.timestamp.lamport(),
2343 Operation::Undo {
2344 lamport_timestamp, ..
2345 } => *lamport_timestamp,
2346 }
2347 }
2348}
2349
2350impl Default for LineEnding {
2351 fn default() -> Self {
2352 #[cfg(unix)]
2353 return Self::Unix;
2354
2355 #[cfg(not(unix))]
2356 return Self::CRLF;
2357 }
2358}
2359
2360impl LineEnding {
2361 pub fn as_str(&self) -> &'static str {
2362 match self {
2363 LineEnding::Unix => "\n",
2364 LineEnding::Windows => "\r\n",
2365 }
2366 }
2367
2368 pub fn detect(text: &str) -> Self {
2369 let mut max_ix = cmp::min(text.len(), 1000);
2370 while !text.is_char_boundary(max_ix) {
2371 max_ix -= 1;
2372 }
2373
2374 if let Some(ix) = text[..max_ix].find(&['\n']) {
2375 if ix > 0 && text.as_bytes()[ix - 1] == b'\r' {
2376 Self::Windows
2377 } else {
2378 Self::Unix
2379 }
2380 } else {
2381 Self::default()
2382 }
2383 }
2384
2385 pub fn normalize(text: &mut String) {
2386 if let Cow::Owned(replaced) = CARRIAGE_RETURNS_REGEX.replace_all(text, "\n") {
2387 *text = replaced;
2388 }
2389 }
2390
2391 fn normalize_arc(text: Arc<str>) -> Arc<str> {
2392 if let Cow::Owned(replaced) = CARRIAGE_RETURNS_REGEX.replace_all(&text, "\n") {
2393 replaced.into()
2394 } else {
2395 text
2396 }
2397 }
2398}
2399
2400pub trait ToOffset {
2401 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize;
2402}
2403
2404impl ToOffset for Point {
2405 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2406 snapshot.point_to_offset(*self)
2407 }
2408}
2409
2410impl ToOffset for PointUtf16 {
2411 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2412 snapshot.point_utf16_to_offset(*self)
2413 }
2414}
2415
2416impl ToOffset for usize {
2417 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2418 assert!(*self <= snapshot.len(), "offset is out of range");
2419 *self
2420 }
2421}
2422
2423impl ToOffset for OffsetUtf16 {
2424 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2425 snapshot.offset_utf16_to_offset(*self)
2426 }
2427}
2428
2429impl ToOffset for Anchor {
2430 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2431 snapshot.summary_for_anchor(self)
2432 }
2433}
2434
2435impl<'a, T: ToOffset> ToOffset for &'a T {
2436 fn to_offset(&self, content: &BufferSnapshot) -> usize {
2437 (*self).to_offset(content)
2438 }
2439}
2440
2441pub trait ToPoint {
2442 fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point;
2443}
2444
2445impl ToPoint for Anchor {
2446 fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point {
2447 snapshot.summary_for_anchor(self)
2448 }
2449}
2450
2451impl ToPoint for usize {
2452 fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point {
2453 snapshot.offset_to_point(*self)
2454 }
2455}
2456
2457impl ToPoint for PointUtf16 {
2458 fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point {
2459 snapshot.point_utf16_to_point(*self)
2460 }
2461}
2462
2463impl ToPoint for Point {
2464 fn to_point<'a>(&self, _: &BufferSnapshot) -> Point {
2465 *self
2466 }
2467}
2468
2469pub trait ToPointUtf16 {
2470 fn to_point_utf16<'a>(&self, snapshot: &BufferSnapshot) -> PointUtf16;
2471}
2472
2473impl ToPointUtf16 for Anchor {
2474 fn to_point_utf16<'a>(&self, snapshot: &BufferSnapshot) -> PointUtf16 {
2475 snapshot.summary_for_anchor(self)
2476 }
2477}
2478
2479impl ToPointUtf16 for usize {
2480 fn to_point_utf16<'a>(&self, snapshot: &BufferSnapshot) -> PointUtf16 {
2481 snapshot.offset_to_point_utf16(*self)
2482 }
2483}
2484
2485impl ToPointUtf16 for PointUtf16 {
2486 fn to_point_utf16<'a>(&self, _: &BufferSnapshot) -> PointUtf16 {
2487 *self
2488 }
2489}
2490
2491impl ToPointUtf16 for Point {
2492 fn to_point_utf16<'a>(&self, snapshot: &BufferSnapshot) -> PointUtf16 {
2493 snapshot.point_to_point_utf16(*self)
2494 }
2495}
2496
2497pub trait ToOffsetUtf16 {
2498 fn to_offset_utf16<'a>(&self, snapshot: &BufferSnapshot) -> OffsetUtf16;
2499}
2500
2501impl ToOffsetUtf16 for Anchor {
2502 fn to_offset_utf16<'a>(&self, snapshot: &BufferSnapshot) -> OffsetUtf16 {
2503 snapshot.summary_for_anchor(self)
2504 }
2505}
2506
2507impl ToOffsetUtf16 for usize {
2508 fn to_offset_utf16<'a>(&self, snapshot: &BufferSnapshot) -> OffsetUtf16 {
2509 snapshot.offset_to_offset_utf16(*self)
2510 }
2511}
2512
2513impl ToOffsetUtf16 for OffsetUtf16 {
2514 fn to_offset_utf16<'a>(&self, _snapshot: &BufferSnapshot) -> OffsetUtf16 {
2515 *self
2516 }
2517}
2518
2519pub trait Clip {
2520 fn clip(&self, bias: Bias, snapshot: &BufferSnapshot) -> Self;
2521}
2522
2523impl Clip for usize {
2524 fn clip(&self, bias: Bias, snapshot: &BufferSnapshot) -> Self {
2525 snapshot.clip_offset(*self, bias)
2526 }
2527}
2528
2529impl Clip for Point {
2530 fn clip(&self, bias: Bias, snapshot: &BufferSnapshot) -> Self {
2531 snapshot.clip_point(*self, bias)
2532 }
2533}
2534
2535impl Clip for PointUtf16 {
2536 fn clip(&self, bias: Bias, snapshot: &BufferSnapshot) -> Self {
2537 snapshot.clip_point_utf16(*self, bias)
2538 }
2539}
2540
2541pub trait FromAnchor {
2542 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self;
2543}
2544
2545impl FromAnchor for Point {
2546 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
2547 snapshot.summary_for_anchor(anchor)
2548 }
2549}
2550
2551impl FromAnchor for PointUtf16 {
2552 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
2553 snapshot.summary_for_anchor(anchor)
2554 }
2555}
2556
2557impl FromAnchor for usize {
2558 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
2559 snapshot.summary_for_anchor(anchor)
2560 }
2561}