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