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