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