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