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