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