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