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