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