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