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