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