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