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