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