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