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