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