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