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