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