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::<Selection<usize>>::with_capacity(ranges.len());
1491 for mut range in ranges {
1492 let mut reversed = false;
1493 if range.start > range.end {
1494 reversed = true;
1495 std::mem::swap(&mut range.start, &mut range.end);
1496 }
1497
1498 if let Some(selection) = selections.last_mut() {
1499 if selection.end >= range.start {
1500 selection.end = range.end;
1501 continue;
1502 }
1503 }
1504
1505 selections.push(Selection {
1506 id: NEXT_SELECTION_ID.fetch_add(1, atomic::Ordering::SeqCst),
1507 start: range.start,
1508 end: range.end,
1509 reversed,
1510 goal: SelectionGoal::None,
1511 });
1512 }
1513 Ok(selections)
1514 }
1515
1516 pub fn selection_ranges<'a>(&'a self, set_id: SelectionSetId) -> Result<Vec<Range<usize>>> {
1517 Ok(self
1518 .selection_set(set_id)?
1519 .offset_selections(self)
1520 .map(move |selection| {
1521 if selection.reversed {
1522 selection.end..selection.start
1523 } else {
1524 selection.start..selection.end
1525 }
1526 })
1527 .collect())
1528 }
1529
1530 pub fn all_selection_ranges<'a>(
1531 &'a self,
1532 ) -> impl 'a + Iterator<Item = (SelectionSetId, Vec<Range<usize>>)> {
1533 self.selections
1534 .keys()
1535 .map(move |set_id| (*set_id, self.selection_ranges(*set_id).unwrap()))
1536 }
1537}
1538
1539#[derive(Clone)]
1540pub struct Snapshot {
1541 visible_text: Rope,
1542 fragments: SumTree<Fragment>,
1543 version: clock::Global,
1544}
1545
1546impl Snapshot {
1547 pub fn as_rope(&self) -> &Rope {
1548 &self.visible_text
1549 }
1550
1551 pub fn len(&self) -> usize {
1552 self.visible_text.len()
1553 }
1554
1555 pub fn line_len(&self, row: u32) -> u32 {
1556 self.content().line_len(row)
1557 }
1558
1559 pub fn indent_column_for_line(&self, row: u32) -> u32 {
1560 self.content().indent_column_for_line(row)
1561 }
1562
1563 pub fn text(&self) -> Rope {
1564 self.visible_text.clone()
1565 }
1566
1567 pub fn text_summary(&self) -> TextSummary {
1568 self.visible_text.summary()
1569 }
1570
1571 pub fn max_point(&self) -> Point {
1572 self.visible_text.max_point()
1573 }
1574
1575 pub fn text_for_range<T: ToOffset>(&self, range: Range<T>) -> Chunks {
1576 let range = range.start.to_offset(self)..range.end.to_offset(self);
1577 self.visible_text.chunks_in_range(range)
1578 }
1579
1580 pub fn text_summary_for_range<T>(&self, range: Range<T>) -> TextSummary
1581 where
1582 T: ToOffset,
1583 {
1584 let range = range.start.to_offset(self.content())..range.end.to_offset(self.content());
1585 self.content().text_summary_for_range(range)
1586 }
1587
1588 pub fn point_for_offset(&self, offset: usize) -> Result<Point> {
1589 self.content().point_for_offset(offset)
1590 }
1591
1592 pub fn clip_offset(&self, offset: usize, bias: Bias) -> usize {
1593 self.visible_text.clip_offset(offset, bias)
1594 }
1595
1596 pub fn clip_point(&self, point: Point, bias: Bias) -> Point {
1597 self.visible_text.clip_point(point, bias)
1598 }
1599
1600 pub fn to_offset(&self, point: Point) -> usize {
1601 self.visible_text.to_offset(point)
1602 }
1603
1604 pub fn to_point(&self, offset: usize) -> Point {
1605 self.visible_text.to_point(offset)
1606 }
1607
1608 pub fn anchor_before<T: ToOffset>(&self, position: T) -> Anchor {
1609 self.content().anchor_at(position, Bias::Left)
1610 }
1611
1612 pub fn anchor_after<T: ToOffset>(&self, position: T) -> Anchor {
1613 self.content().anchor_at(position, Bias::Right)
1614 }
1615
1616 pub fn content(&self) -> Content {
1617 self.into()
1618 }
1619}
1620
1621pub struct Content<'a> {
1622 visible_text: &'a Rope,
1623 fragments: &'a SumTree<Fragment>,
1624 version: &'a clock::Global,
1625}
1626
1627impl<'a> From<&'a Snapshot> for Content<'a> {
1628 fn from(snapshot: &'a Snapshot) -> Self {
1629 Self {
1630 visible_text: &snapshot.visible_text,
1631 fragments: &snapshot.fragments,
1632 version: &snapshot.version,
1633 }
1634 }
1635}
1636
1637impl<'a> From<&'a Buffer> for Content<'a> {
1638 fn from(buffer: &'a 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 mut Buffer> for Content<'a> {
1648 fn from(buffer: &'a mut Buffer) -> Self {
1649 Self {
1650 visible_text: &buffer.visible_text,
1651 fragments: &buffer.fragments,
1652 version: &buffer.version,
1653 }
1654 }
1655}
1656
1657impl<'a> From<&'a Content<'a>> for Content<'a> {
1658 fn from(content: &'a Content) -> Self {
1659 Self {
1660 visible_text: &content.visible_text,
1661 fragments: &content.fragments,
1662 version: &content.version,
1663 }
1664 }
1665}
1666
1667impl<'a> Content<'a> {
1668 fn max_point(&self) -> Point {
1669 self.visible_text.max_point()
1670 }
1671
1672 fn len(&self) -> usize {
1673 self.fragments.extent::<usize>(&None)
1674 }
1675
1676 pub fn chars_at<T: ToOffset>(&self, position: T) -> impl Iterator<Item = char> + 'a {
1677 let offset = position.to_offset(self);
1678 self.visible_text.chars_at(offset)
1679 }
1680
1681 pub fn reversed_chars_at<T: ToOffset>(&self, position: T) -> impl Iterator<Item = char> + 'a {
1682 let offset = position.to_offset(self);
1683 self.visible_text.reversed_chars_at(offset)
1684 }
1685
1686 pub fn text_for_range<T: ToOffset>(&self, range: Range<T>) -> Chunks<'a> {
1687 let start = range.start.to_offset(self);
1688 let end = range.end.to_offset(self);
1689 self.visible_text.chunks_in_range(start..end)
1690 }
1691
1692 fn line_len(&self, row: u32) -> u32 {
1693 let row_start_offset = Point::new(row, 0).to_offset(self);
1694 let row_end_offset = if row >= self.max_point().row {
1695 self.len()
1696 } else {
1697 Point::new(row + 1, 0).to_offset(self) - 1
1698 };
1699 (row_end_offset - row_start_offset) as u32
1700 }
1701
1702 pub fn indent_column_for_line(&self, row: u32) -> u32 {
1703 let mut result = 0;
1704 for c in self.chars_at(Point::new(row, 0)) {
1705 if c == ' ' {
1706 result += 1;
1707 } else {
1708 break;
1709 }
1710 }
1711 result
1712 }
1713
1714 fn summary_for_anchor(&self, anchor: &Anchor) -> TextSummary {
1715 let cx = Some(anchor.version.clone());
1716 let mut cursor = self.fragments.cursor::<(VersionedOffset, usize)>();
1717 cursor.seek(&VersionedOffset::Offset(anchor.offset), anchor.bias, &cx);
1718 let overshoot = if cursor.item().map_or(false, |fragment| fragment.visible) {
1719 anchor.offset - cursor.start().0.offset()
1720 } else {
1721 0
1722 };
1723 self.text_summary_for_range(0..cursor.start().1 + overshoot)
1724 }
1725
1726 fn text_summary_for_range(&self, range: Range<usize>) -> TextSummary {
1727 self.visible_text.cursor(range.start).summary(range.end)
1728 }
1729
1730 fn summaries_for_anchors<T>(
1731 &self,
1732 map: &'a AnchorMap<T>,
1733 ) -> impl Iterator<Item = (TextSummary, &'a T)> {
1734 let cx = Some(map.version.clone());
1735 let mut summary = TextSummary::default();
1736 let mut rope_cursor = self.visible_text.cursor(0);
1737 let mut cursor = self.fragments.cursor::<(VersionedOffset, usize)>();
1738 map.entries.iter().map(move |((offset, bias), value)| {
1739 cursor.seek_forward(&VersionedOffset::Offset(*offset), *bias, &cx);
1740 let overshoot = if cursor.item().map_or(false, |fragment| fragment.visible) {
1741 offset - cursor.start().0.offset()
1742 } else {
1743 0
1744 };
1745 summary += rope_cursor.summary(cursor.start().1 + overshoot);
1746 (summary.clone(), value)
1747 })
1748 }
1749
1750 fn summaries_for_anchor_ranges<T>(
1751 &self,
1752 map: &'a AnchorRangeMap<T>,
1753 ) -> impl Iterator<Item = (Range<TextSummary>, &'a T)> {
1754 let cx = Some(map.version.clone());
1755 let mut summary = TextSummary::default();
1756 let mut rope_cursor = self.visible_text.cursor(0);
1757 let mut cursor = self.fragments.cursor::<(VersionedOffset, usize)>();
1758 map.entries.iter().map(move |(range, value)| {
1759 let Range {
1760 start: (start_offset, start_bias),
1761 end: (end_offset, end_bias),
1762 } = range;
1763
1764 cursor.seek_forward(&VersionedOffset::Offset(*start_offset), *start_bias, &cx);
1765 let overshoot = if cursor.item().map_or(false, |fragment| fragment.visible) {
1766 start_offset - cursor.start().0.offset()
1767 } else {
1768 0
1769 };
1770 summary += rope_cursor.summary(cursor.start().1 + overshoot);
1771 let start_summary = summary.clone();
1772
1773 cursor.seek_forward(&VersionedOffset::Offset(*end_offset), *end_bias, &cx);
1774 let overshoot = if cursor.item().map_or(false, |fragment| fragment.visible) {
1775 end_offset - cursor.start().0.offset()
1776 } else {
1777 0
1778 };
1779 summary += rope_cursor.summary(cursor.start().1 + overshoot);
1780 let end_summary = summary.clone();
1781
1782 (start_summary..end_summary, value)
1783 })
1784 }
1785
1786 fn anchor_at<T: ToOffset>(&self, position: T, bias: Bias) -> Anchor {
1787 let offset = position.to_offset(self);
1788 let max_offset = self.len();
1789 assert!(offset <= max_offset, "offset is out of range");
1790 let mut cursor = self.fragments.cursor::<FragmentTextSummary>();
1791 cursor.seek(&offset, bias, &None);
1792 Anchor {
1793 offset: offset + cursor.start().deleted,
1794 bias,
1795 version: self.version.clone(),
1796 }
1797 }
1798
1799 pub fn anchor_map<T, E>(&self, entries: E) -> AnchorMap<T>
1800 where
1801 E: IntoIterator<Item = ((usize, Bias), T)>,
1802 {
1803 let version = self.version.clone();
1804 let mut cursor = self.fragments.cursor::<FragmentTextSummary>();
1805 let entries = entries
1806 .into_iter()
1807 .map(|((offset, bias), value)| {
1808 cursor.seek_forward(&offset, bias, &None);
1809 let full_offset = cursor.start().deleted + offset;
1810 ((full_offset, bias), value)
1811 })
1812 .collect();
1813
1814 AnchorMap { version, entries }
1815 }
1816
1817 pub fn anchor_range_map<T, E>(&self, entries: E) -> AnchorRangeMap<T>
1818 where
1819 E: IntoIterator<Item = (Range<(usize, Bias)>, T)>,
1820 {
1821 let version = self.version.clone();
1822 let mut cursor = self.fragments.cursor::<FragmentTextSummary>();
1823 let entries = entries
1824 .into_iter()
1825 .map(|(range, value)| {
1826 let Range {
1827 start: (start_offset, start_bias),
1828 end: (end_offset, end_bias),
1829 } = range;
1830 cursor.seek_forward(&start_offset, start_bias, &None);
1831 let full_start_offset = cursor.start().deleted + start_offset;
1832 cursor.seek_forward(&end_offset, end_bias, &None);
1833 let full_end_offset = cursor.start().deleted + end_offset;
1834 (
1835 (full_start_offset, start_bias)..(full_end_offset, end_bias),
1836 value,
1837 )
1838 })
1839 .collect();
1840
1841 AnchorRangeMap { version, entries }
1842 }
1843
1844 pub fn anchor_set<E>(&self, entries: E) -> AnchorSet
1845 where
1846 E: IntoIterator<Item = (usize, Bias)>,
1847 {
1848 AnchorSet(self.anchor_map(entries.into_iter().map(|range| (range, ()))))
1849 }
1850
1851 pub fn anchor_range_set<E>(&self, entries: E) -> AnchorRangeSet
1852 where
1853 E: IntoIterator<Item = Range<(usize, Bias)>>,
1854 {
1855 AnchorRangeSet(self.anchor_range_map(entries.into_iter().map(|range| (range, ()))))
1856 }
1857
1858 fn full_offset_for_anchor(&self, anchor: &Anchor) -> usize {
1859 let cx = Some(anchor.version.clone());
1860 let mut cursor = self
1861 .fragments
1862 .cursor::<(VersionedOffset, FragmentTextSummary)>();
1863 cursor.seek(&VersionedOffset::Offset(anchor.offset), anchor.bias, &cx);
1864 let overshoot = if cursor.item().is_some() {
1865 anchor.offset - cursor.start().0.offset()
1866 } else {
1867 0
1868 };
1869 let summary = cursor.start().1;
1870 summary.visible + summary.deleted + overshoot
1871 }
1872
1873 fn point_for_offset(&self, offset: usize) -> Result<Point> {
1874 if offset <= self.len() {
1875 Ok(self.text_summary_for_range(0..offset).lines)
1876 } else {
1877 Err(anyhow!("offset out of bounds"))
1878 }
1879 }
1880}
1881
1882struct RopeBuilder<'a> {
1883 old_visible_cursor: rope::Cursor<'a>,
1884 old_deleted_cursor: rope::Cursor<'a>,
1885 new_visible: Rope,
1886 new_deleted: Rope,
1887}
1888
1889impl<'a> RopeBuilder<'a> {
1890 fn new(old_visible_cursor: rope::Cursor<'a>, old_deleted_cursor: rope::Cursor<'a>) -> Self {
1891 Self {
1892 old_visible_cursor,
1893 old_deleted_cursor,
1894 new_visible: Rope::new(),
1895 new_deleted: Rope::new(),
1896 }
1897 }
1898
1899 fn push_tree(&mut self, len: FragmentTextSummary) {
1900 self.push(len.visible, true, true);
1901 self.push(len.deleted, false, false);
1902 }
1903
1904 fn push_fragment(&mut self, fragment: &Fragment, was_visible: bool) {
1905 debug_assert!(fragment.len > 0);
1906 self.push(fragment.len, was_visible, fragment.visible)
1907 }
1908
1909 fn push(&mut self, len: usize, was_visible: bool, is_visible: bool) {
1910 let text = if was_visible {
1911 self.old_visible_cursor
1912 .slice(self.old_visible_cursor.offset() + len)
1913 } else {
1914 self.old_deleted_cursor
1915 .slice(self.old_deleted_cursor.offset() + len)
1916 };
1917 if is_visible {
1918 self.new_visible.append(text);
1919 } else {
1920 self.new_deleted.append(text);
1921 }
1922 }
1923
1924 fn push_str(&mut self, text: &str) {
1925 self.new_visible.push(text);
1926 }
1927
1928 fn finish(mut self) -> (Rope, Rope) {
1929 self.new_visible.append(self.old_visible_cursor.suffix());
1930 self.new_deleted.append(self.old_deleted_cursor.suffix());
1931 (self.new_visible, self.new_deleted)
1932 }
1933}
1934
1935impl<'a, F: Fn(&FragmentSummary) -> bool> Iterator for Edits<'a, F> {
1936 type Item = Edit;
1937
1938 fn next(&mut self) -> Option<Self::Item> {
1939 let mut change: Option<Edit> = None;
1940 let cursor = self.cursor.as_mut()?;
1941
1942 while let Some(fragment) = cursor.item() {
1943 let bytes = cursor.start().visible - self.new_offset;
1944 let lines = self.visible_text.to_point(cursor.start().visible) - self.new_point;
1945 self.old_offset += bytes;
1946 self.old_point += &lines;
1947 self.new_offset += bytes;
1948 self.new_point += &lines;
1949
1950 if !fragment.was_visible(&self.since, &self.undos) && fragment.visible {
1951 let fragment_lines =
1952 self.visible_text.to_point(self.new_offset + fragment.len) - self.new_point;
1953 if let Some(ref mut change) = change {
1954 if change.new_bytes.end == self.new_offset {
1955 change.new_bytes.end += fragment.len;
1956 } else {
1957 break;
1958 }
1959 } else {
1960 change = Some(Edit {
1961 old_bytes: self.old_offset..self.old_offset,
1962 new_bytes: self.new_offset..self.new_offset + fragment.len,
1963 old_lines: self.old_point..self.old_point,
1964 });
1965 }
1966
1967 self.new_offset += fragment.len;
1968 self.new_point += &fragment_lines;
1969 } else if fragment.was_visible(&self.since, &self.undos) && !fragment.visible {
1970 let deleted_start = cursor.start().deleted;
1971 let fragment_lines = self.deleted_text.to_point(deleted_start + fragment.len)
1972 - self.deleted_text.to_point(deleted_start);
1973 if let Some(ref mut change) = change {
1974 if change.new_bytes.end == self.new_offset {
1975 change.old_bytes.end += fragment.len;
1976 change.old_lines.end += &fragment_lines;
1977 } else {
1978 break;
1979 }
1980 } else {
1981 change = Some(Edit {
1982 old_bytes: self.old_offset..self.old_offset + fragment.len,
1983 new_bytes: self.new_offset..self.new_offset,
1984 old_lines: self.old_point..self.old_point + &fragment_lines,
1985 });
1986 }
1987
1988 self.old_offset += fragment.len;
1989 self.old_point += &fragment_lines;
1990 }
1991
1992 cursor.next(&None);
1993 }
1994
1995 change
1996 }
1997}
1998
1999impl Fragment {
2000 fn is_visible(&self, undos: &UndoMap) -> bool {
2001 !undos.is_undone(self.timestamp.local())
2002 && self.deletions.iter().all(|d| undos.is_undone(*d))
2003 }
2004
2005 fn was_visible(&self, version: &clock::Global, undos: &UndoMap) -> bool {
2006 (version.observed(self.timestamp.local())
2007 && !undos.was_undone(self.timestamp.local(), version))
2008 && self
2009 .deletions
2010 .iter()
2011 .all(|d| !version.observed(*d) || undos.was_undone(*d, version))
2012 }
2013}
2014
2015impl sum_tree::Item for Fragment {
2016 type Summary = FragmentSummary;
2017
2018 fn summary(&self) -> Self::Summary {
2019 let mut max_version = clock::Global::new();
2020 max_version.observe(self.timestamp.local());
2021 for deletion in &self.deletions {
2022 max_version.observe(*deletion);
2023 }
2024 max_version.join(&self.max_undos);
2025
2026 let mut min_insertion_version = clock::Global::new();
2027 min_insertion_version.observe(self.timestamp.local());
2028 let max_insertion_version = min_insertion_version.clone();
2029 if self.visible {
2030 FragmentSummary {
2031 text: FragmentTextSummary {
2032 visible: self.len,
2033 deleted: 0,
2034 },
2035 max_version,
2036 min_insertion_version,
2037 max_insertion_version,
2038 }
2039 } else {
2040 FragmentSummary {
2041 text: FragmentTextSummary {
2042 visible: 0,
2043 deleted: self.len,
2044 },
2045 max_version,
2046 min_insertion_version,
2047 max_insertion_version,
2048 }
2049 }
2050 }
2051}
2052
2053impl sum_tree::Summary for FragmentSummary {
2054 type Context = Option<clock::Global>;
2055
2056 fn add_summary(&mut self, other: &Self, _: &Self::Context) {
2057 self.text.visible += &other.text.visible;
2058 self.text.deleted += &other.text.deleted;
2059 self.max_version.join(&other.max_version);
2060 self.min_insertion_version
2061 .meet(&other.min_insertion_version);
2062 self.max_insertion_version
2063 .join(&other.max_insertion_version);
2064 }
2065}
2066
2067impl Default for FragmentSummary {
2068 fn default() -> Self {
2069 FragmentSummary {
2070 text: FragmentTextSummary::default(),
2071 max_version: clock::Global::new(),
2072 min_insertion_version: clock::Global::new(),
2073 max_insertion_version: clock::Global::new(),
2074 }
2075 }
2076}
2077
2078impl<'a> sum_tree::Dimension<'a, FragmentSummary> for usize {
2079 fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
2080 *self += summary.text.visible;
2081 }
2082}
2083
2084impl<'a> sum_tree::SeekTarget<'a, FragmentSummary, FragmentTextSummary> for usize {
2085 fn cmp(
2086 &self,
2087 cursor_location: &FragmentTextSummary,
2088 _: &Option<clock::Global>,
2089 ) -> cmp::Ordering {
2090 Ord::cmp(self, &cursor_location.visible)
2091 }
2092}
2093
2094#[derive(Copy, Clone, Debug, Eq, PartialEq)]
2095enum VersionedOffset {
2096 Offset(usize),
2097 InvalidVersion,
2098}
2099
2100impl VersionedOffset {
2101 fn offset(&self) -> usize {
2102 if let Self::Offset(offset) = self {
2103 *offset
2104 } else {
2105 panic!("invalid version")
2106 }
2107 }
2108}
2109
2110impl Default for VersionedOffset {
2111 fn default() -> Self {
2112 Self::Offset(0)
2113 }
2114}
2115
2116impl<'a> sum_tree::Dimension<'a, FragmentSummary> for VersionedOffset {
2117 fn add_summary(&mut self, summary: &'a FragmentSummary, cx: &Option<clock::Global>) {
2118 if let Self::Offset(offset) = self {
2119 let version = cx.as_ref().unwrap();
2120 if *version >= summary.max_insertion_version {
2121 *offset += summary.text.visible + summary.text.deleted;
2122 } else if !summary
2123 .min_insertion_version
2124 .iter()
2125 .all(|t| !version.observed(*t))
2126 {
2127 *self = Self::InvalidVersion;
2128 }
2129 }
2130 }
2131}
2132
2133impl<'a> sum_tree::SeekTarget<'a, FragmentSummary, Self> for VersionedOffset {
2134 fn cmp(&self, other: &Self, _: &Option<clock::Global>) -> cmp::Ordering {
2135 match (self, other) {
2136 (Self::Offset(a), Self::Offset(b)) => Ord::cmp(a, b),
2137 (Self::Offset(_), Self::InvalidVersion) => cmp::Ordering::Less,
2138 (Self::InvalidVersion, _) => unreachable!(),
2139 }
2140 }
2141}
2142
2143impl Operation {
2144 fn replica_id(&self) -> ReplicaId {
2145 self.lamport_timestamp().replica_id
2146 }
2147
2148 fn lamport_timestamp(&self) -> clock::Lamport {
2149 match self {
2150 Operation::Edit(edit) => edit.timestamp.lamport(),
2151 Operation::Undo {
2152 lamport_timestamp, ..
2153 } => *lamport_timestamp,
2154 Operation::UpdateSelections {
2155 lamport_timestamp, ..
2156 } => *lamport_timestamp,
2157 Operation::RemoveSelections {
2158 lamport_timestamp, ..
2159 } => *lamport_timestamp,
2160 Operation::SetActiveSelections {
2161 lamport_timestamp, ..
2162 } => *lamport_timestamp,
2163 #[cfg(test)]
2164 Operation::Test(lamport_timestamp) => *lamport_timestamp,
2165 }
2166 }
2167
2168 pub fn is_edit(&self) -> bool {
2169 match self {
2170 Operation::Edit { .. } => true,
2171 _ => false,
2172 }
2173 }
2174}
2175
2176impl<'a> Into<proto::Operation> for &'a Operation {
2177 fn into(self) -> proto::Operation {
2178 proto::Operation {
2179 variant: Some(match self {
2180 Operation::Edit(edit) => proto::operation::Variant::Edit(edit.into()),
2181 Operation::Undo {
2182 undo,
2183 lamport_timestamp,
2184 } => proto::operation::Variant::Undo(proto::operation::Undo {
2185 replica_id: undo.id.replica_id as u32,
2186 local_timestamp: undo.id.value,
2187 lamport_timestamp: lamport_timestamp.value,
2188 ranges: undo
2189 .ranges
2190 .iter()
2191 .map(|r| proto::Range {
2192 start: r.start as u64,
2193 end: r.end as u64,
2194 })
2195 .collect(),
2196 counts: undo
2197 .counts
2198 .iter()
2199 .map(|(edit_id, count)| proto::operation::UndoCount {
2200 replica_id: edit_id.replica_id as u32,
2201 local_timestamp: edit_id.value,
2202 count: *count,
2203 })
2204 .collect(),
2205 version: From::from(&undo.version),
2206 }),
2207 Operation::UpdateSelections {
2208 set_id,
2209 selections,
2210 lamport_timestamp,
2211 } => proto::operation::Variant::UpdateSelections(
2212 proto::operation::UpdateSelections {
2213 replica_id: set_id.replica_id as u32,
2214 local_timestamp: set_id.value,
2215 lamport_timestamp: lamport_timestamp.value,
2216 version: selections.version().into(),
2217 selections: selections
2218 .raw_entries()
2219 .iter()
2220 .map(|(range, state)| proto::Selection {
2221 id: state.id as u64,
2222 start: range.start.0 as u64,
2223 end: range.end.0 as u64,
2224 reversed: state.reversed,
2225 })
2226 .collect(),
2227 },
2228 ),
2229 Operation::RemoveSelections {
2230 set_id,
2231 lamport_timestamp,
2232 } => proto::operation::Variant::RemoveSelections(
2233 proto::operation::RemoveSelections {
2234 replica_id: set_id.replica_id as u32,
2235 local_timestamp: set_id.value,
2236 lamport_timestamp: lamport_timestamp.value,
2237 },
2238 ),
2239 Operation::SetActiveSelections {
2240 set_id,
2241 lamport_timestamp,
2242 } => proto::operation::Variant::SetActiveSelections(
2243 proto::operation::SetActiveSelections {
2244 replica_id: lamport_timestamp.replica_id as u32,
2245 local_timestamp: set_id.map(|set_id| set_id.value),
2246 lamport_timestamp: lamport_timestamp.value,
2247 },
2248 ),
2249 #[cfg(test)]
2250 Operation::Test(_) => unimplemented!(),
2251 }),
2252 }
2253 }
2254}
2255
2256impl<'a> Into<proto::operation::Edit> for &'a EditOperation {
2257 fn into(self) -> proto::operation::Edit {
2258 let ranges = self
2259 .ranges
2260 .iter()
2261 .map(|range| proto::Range {
2262 start: range.start as u64,
2263 end: range.end as u64,
2264 })
2265 .collect();
2266 proto::operation::Edit {
2267 replica_id: self.timestamp.replica_id as u32,
2268 local_timestamp: self.timestamp.local,
2269 lamport_timestamp: self.timestamp.lamport,
2270 version: From::from(&self.version),
2271 ranges,
2272 new_text: self.new_text.clone(),
2273 }
2274 }
2275}
2276
2277impl TryFrom<proto::Operation> for Operation {
2278 type Error = anyhow::Error;
2279
2280 fn try_from(message: proto::Operation) -> Result<Self, Self::Error> {
2281 Ok(
2282 match message
2283 .variant
2284 .ok_or_else(|| anyhow!("missing operation variant"))?
2285 {
2286 proto::operation::Variant::Edit(edit) => Operation::Edit(edit.into()),
2287 proto::operation::Variant::Undo(undo) => Operation::Undo {
2288 lamport_timestamp: clock::Lamport {
2289 replica_id: undo.replica_id as ReplicaId,
2290 value: undo.lamport_timestamp,
2291 },
2292 undo: UndoOperation {
2293 id: clock::Local {
2294 replica_id: undo.replica_id as ReplicaId,
2295 value: undo.local_timestamp,
2296 },
2297 counts: undo
2298 .counts
2299 .into_iter()
2300 .map(|c| {
2301 (
2302 clock::Local {
2303 replica_id: c.replica_id as ReplicaId,
2304 value: c.local_timestamp,
2305 },
2306 c.count,
2307 )
2308 })
2309 .collect(),
2310 ranges: undo
2311 .ranges
2312 .into_iter()
2313 .map(|r| r.start as usize..r.end as usize)
2314 .collect(),
2315 version: undo.version.into(),
2316 },
2317 },
2318 proto::operation::Variant::UpdateSelections(message) => {
2319 let version = message.version.into();
2320 let entries = message
2321 .selections
2322 .iter()
2323 .map(|selection| {
2324 let range = (selection.start as usize, Bias::Left)
2325 ..(selection.end as usize, Bias::Right);
2326 let state = SelectionState {
2327 id: selection.id as usize,
2328 reversed: selection.reversed,
2329 goal: SelectionGoal::None,
2330 };
2331 (range, state)
2332 })
2333 .collect();
2334 let selections = AnchorRangeMap::from_raw(version, entries);
2335
2336 Operation::UpdateSelections {
2337 set_id: clock::Lamport {
2338 replica_id: message.replica_id as ReplicaId,
2339 value: message.local_timestamp,
2340 },
2341 lamport_timestamp: clock::Lamport {
2342 replica_id: message.replica_id as ReplicaId,
2343 value: message.lamport_timestamp,
2344 },
2345 selections: Arc::from(selections),
2346 }
2347 }
2348 proto::operation::Variant::RemoveSelections(message) => {
2349 Operation::RemoveSelections {
2350 set_id: clock::Lamport {
2351 replica_id: message.replica_id as ReplicaId,
2352 value: message.local_timestamp,
2353 },
2354 lamport_timestamp: clock::Lamport {
2355 replica_id: message.replica_id as ReplicaId,
2356 value: message.lamport_timestamp,
2357 },
2358 }
2359 }
2360 proto::operation::Variant::SetActiveSelections(message) => {
2361 Operation::SetActiveSelections {
2362 set_id: message.local_timestamp.map(|value| clock::Lamport {
2363 replica_id: message.replica_id as ReplicaId,
2364 value,
2365 }),
2366 lamport_timestamp: clock::Lamport {
2367 replica_id: message.replica_id as ReplicaId,
2368 value: message.lamport_timestamp,
2369 },
2370 }
2371 }
2372 },
2373 )
2374 }
2375}
2376
2377impl From<proto::operation::Edit> for EditOperation {
2378 fn from(edit: proto::operation::Edit) -> Self {
2379 let ranges = edit
2380 .ranges
2381 .into_iter()
2382 .map(|range| range.start as usize..range.end as usize)
2383 .collect();
2384 EditOperation {
2385 timestamp: InsertionTimestamp {
2386 replica_id: edit.replica_id as ReplicaId,
2387 local: edit.local_timestamp,
2388 lamport: edit.lamport_timestamp,
2389 },
2390 version: edit.version.into(),
2391 ranges,
2392 new_text: edit.new_text,
2393 }
2394 }
2395}
2396
2397pub trait ToOffset {
2398 fn to_offset<'a>(&self, content: impl Into<Content<'a>>) -> usize;
2399}
2400
2401impl ToOffset for Point {
2402 fn to_offset<'a>(&self, content: impl Into<Content<'a>>) -> usize {
2403 content.into().visible_text.to_offset(*self)
2404 }
2405}
2406
2407impl ToOffset for usize {
2408 fn to_offset<'a>(&self, _: impl Into<Content<'a>>) -> usize {
2409 *self
2410 }
2411}
2412
2413impl ToOffset for Anchor {
2414 fn to_offset<'a>(&self, content: impl Into<Content<'a>>) -> usize {
2415 content.into().summary_for_anchor(self).bytes
2416 }
2417}
2418
2419impl<'a> ToOffset for &'a Anchor {
2420 fn to_offset<'b>(&self, content: impl Into<Content<'b>>) -> usize {
2421 content.into().summary_for_anchor(self).bytes
2422 }
2423}
2424
2425pub trait ToPoint {
2426 fn to_point<'a>(&self, content: impl Into<Content<'a>>) -> Point;
2427}
2428
2429impl ToPoint for Anchor {
2430 fn to_point<'a>(&self, content: impl Into<Content<'a>>) -> Point {
2431 content.into().summary_for_anchor(self).lines
2432 }
2433}
2434
2435impl ToPoint for usize {
2436 fn to_point<'a>(&self, content: impl Into<Content<'a>>) -> Point {
2437 content.into().visible_text.to_point(*self)
2438 }
2439}
2440
2441impl ToPoint for Point {
2442 fn to_point<'a>(&self, _: impl Into<Content<'a>>) -> Point {
2443 *self
2444 }
2445}