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 } else {
2011 break;
2012 }
2013 } else {
2014 change = Some(Edit {
2015 old_bytes: self.old_offset..self.old_offset,
2016 new_bytes: self.new_offset..self.new_offset + fragment.len,
2017 old_lines: self.old_point..self.old_point,
2018 new_lines: self.new_point..self.new_point + fragment_lines,
2019 });
2020 }
2021
2022 self.new_offset += fragment.len;
2023 self.new_point += &fragment_lines;
2024 } else if fragment.was_visible(&self.since, &self.undos) && !fragment.visible {
2025 let deleted_start = cursor.start().deleted;
2026 let fragment_lines = self.deleted_text.to_point(deleted_start + fragment.len)
2027 - self.deleted_text.to_point(deleted_start);
2028 if let Some(ref mut change) = change {
2029 if change.new_bytes.end == self.new_offset {
2030 change.old_bytes.end += fragment.len;
2031 change.old_lines.end += &fragment_lines;
2032 } else {
2033 break;
2034 }
2035 } else {
2036 change = Some(Edit {
2037 old_bytes: self.old_offset..self.old_offset + fragment.len,
2038 new_bytes: self.new_offset..self.new_offset,
2039 old_lines: self.old_point..self.old_point + &fragment_lines,
2040 new_lines: self.new_point..self.new_point,
2041 });
2042 }
2043
2044 self.old_offset += fragment.len;
2045 self.old_point += &fragment_lines;
2046 }
2047
2048 cursor.next(&None);
2049 }
2050
2051 change
2052 }
2053}
2054
2055impl Fragment {
2056 fn is_visible(&self, undos: &UndoMap) -> bool {
2057 !undos.is_undone(self.timestamp.local())
2058 && self.deletions.iter().all(|d| undos.is_undone(*d))
2059 }
2060
2061 fn was_visible(&self, version: &clock::Global, undos: &UndoMap) -> bool {
2062 (version.observed(self.timestamp.local())
2063 && !undos.was_undone(self.timestamp.local(), version))
2064 && self
2065 .deletions
2066 .iter()
2067 .all(|d| !version.observed(*d) || undos.was_undone(*d, version))
2068 }
2069}
2070
2071impl sum_tree::Item for Fragment {
2072 type Summary = FragmentSummary;
2073
2074 fn summary(&self) -> Self::Summary {
2075 let mut max_version = clock::Global::new();
2076 max_version.observe(self.timestamp.local());
2077 for deletion in &self.deletions {
2078 max_version.observe(*deletion);
2079 }
2080 max_version.join(&self.max_undos);
2081
2082 let mut min_insertion_version = clock::Global::new();
2083 min_insertion_version.observe(self.timestamp.local());
2084 let max_insertion_version = min_insertion_version.clone();
2085 if self.visible {
2086 FragmentSummary {
2087 text: FragmentTextSummary {
2088 visible: self.len,
2089 deleted: 0,
2090 },
2091 max_version,
2092 min_insertion_version,
2093 max_insertion_version,
2094 }
2095 } else {
2096 FragmentSummary {
2097 text: FragmentTextSummary {
2098 visible: 0,
2099 deleted: self.len,
2100 },
2101 max_version,
2102 min_insertion_version,
2103 max_insertion_version,
2104 }
2105 }
2106 }
2107}
2108
2109impl sum_tree::Summary for FragmentSummary {
2110 type Context = Option<clock::Global>;
2111
2112 fn add_summary(&mut self, other: &Self, _: &Self::Context) {
2113 self.text.visible += &other.text.visible;
2114 self.text.deleted += &other.text.deleted;
2115 self.max_version.join(&other.max_version);
2116 self.min_insertion_version
2117 .meet(&other.min_insertion_version);
2118 self.max_insertion_version
2119 .join(&other.max_insertion_version);
2120 }
2121}
2122
2123impl Default for FragmentSummary {
2124 fn default() -> Self {
2125 FragmentSummary {
2126 text: FragmentTextSummary::default(),
2127 max_version: clock::Global::new(),
2128 min_insertion_version: clock::Global::new(),
2129 max_insertion_version: clock::Global::new(),
2130 }
2131 }
2132}
2133
2134#[derive(Copy, Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
2135pub struct FullOffset(usize);
2136
2137impl FullOffset {
2138 const MAX: Self = FullOffset(usize::MAX);
2139
2140 fn to_proto(self) -> u64 {
2141 self.0 as u64
2142 }
2143
2144 fn from_proto(value: u64) -> Self {
2145 Self(value as usize)
2146 }
2147}
2148
2149impl ops::AddAssign<usize> for FullOffset {
2150 fn add_assign(&mut self, rhs: usize) {
2151 self.0 += rhs;
2152 }
2153}
2154
2155impl ops::Add<usize> for FullOffset {
2156 type Output = Self;
2157
2158 fn add(mut self, rhs: usize) -> Self::Output {
2159 self += rhs;
2160 self
2161 }
2162}
2163
2164impl ops::Sub for FullOffset {
2165 type Output = usize;
2166
2167 fn sub(self, rhs: Self) -> Self::Output {
2168 self.0 - rhs.0
2169 }
2170}
2171
2172impl<'a> sum_tree::Dimension<'a, FragmentSummary> for usize {
2173 fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
2174 *self += summary.text.visible;
2175 }
2176}
2177
2178impl<'a> sum_tree::Dimension<'a, FragmentSummary> for FullOffset {
2179 fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
2180 self.0 += summary.text.visible + summary.text.deleted;
2181 }
2182}
2183
2184impl<'a> sum_tree::SeekTarget<'a, FragmentSummary, FragmentTextSummary> for usize {
2185 fn cmp(
2186 &self,
2187 cursor_location: &FragmentTextSummary,
2188 _: &Option<clock::Global>,
2189 ) -> cmp::Ordering {
2190 Ord::cmp(self, &cursor_location.visible)
2191 }
2192}
2193
2194#[derive(Copy, Clone, Debug, Eq, PartialEq)]
2195enum VersionedFullOffset {
2196 Offset(FullOffset),
2197 Invalid,
2198}
2199
2200impl VersionedFullOffset {
2201 fn full_offset(&self) -> FullOffset {
2202 if let Self::Offset(position) = self {
2203 *position
2204 } else {
2205 panic!("invalid version")
2206 }
2207 }
2208}
2209
2210impl Default for VersionedFullOffset {
2211 fn default() -> Self {
2212 Self::Offset(Default::default())
2213 }
2214}
2215
2216impl<'a> sum_tree::Dimension<'a, FragmentSummary> for VersionedFullOffset {
2217 fn add_summary(&mut self, summary: &'a FragmentSummary, cx: &Option<clock::Global>) {
2218 if let Self::Offset(offset) = self {
2219 let version = cx.as_ref().unwrap();
2220 if *version >= summary.max_insertion_version {
2221 *offset += summary.text.visible + summary.text.deleted;
2222 } else if !summary
2223 .min_insertion_version
2224 .iter()
2225 .all(|t| !version.observed(*t))
2226 {
2227 *self = Self::Invalid;
2228 }
2229 }
2230 }
2231}
2232
2233impl<'a> sum_tree::SeekTarget<'a, FragmentSummary, Self> for VersionedFullOffset {
2234 fn cmp(&self, cursor_position: &Self, _: &Option<clock::Global>) -> cmp::Ordering {
2235 match (self, cursor_position) {
2236 (Self::Offset(a), Self::Offset(b)) => Ord::cmp(a, b),
2237 (Self::Offset(_), Self::Invalid) => cmp::Ordering::Less,
2238 (Self::Invalid, _) => unreachable!(),
2239 }
2240 }
2241}
2242
2243impl Operation {
2244 fn replica_id(&self) -> ReplicaId {
2245 self.lamport_timestamp().replica_id
2246 }
2247
2248 fn lamport_timestamp(&self) -> clock::Lamport {
2249 match self {
2250 Operation::Edit(edit) => edit.timestamp.lamport(),
2251 Operation::Undo {
2252 lamport_timestamp, ..
2253 } => *lamport_timestamp,
2254 Operation::UpdateSelections {
2255 lamport_timestamp, ..
2256 } => *lamport_timestamp,
2257 Operation::SetActiveSelections {
2258 lamport_timestamp, ..
2259 } => *lamport_timestamp,
2260 #[cfg(test)]
2261 Operation::Test(lamport_timestamp) => *lamport_timestamp,
2262 }
2263 }
2264
2265 pub fn is_edit(&self) -> bool {
2266 match self {
2267 Operation::Edit { .. } => true,
2268 _ => false,
2269 }
2270 }
2271}
2272
2273impl<'a> Into<proto::Operation> for &'a Operation {
2274 fn into(self) -> proto::Operation {
2275 proto::Operation {
2276 variant: Some(match self {
2277 Operation::Edit(edit) => proto::operation::Variant::Edit(edit.into()),
2278 Operation::Undo {
2279 undo,
2280 lamport_timestamp,
2281 } => proto::operation::Variant::Undo(proto::operation::Undo {
2282 replica_id: undo.id.replica_id as u32,
2283 local_timestamp: undo.id.value,
2284 lamport_timestamp: lamport_timestamp.value,
2285 ranges: undo
2286 .ranges
2287 .iter()
2288 .map(|r| proto::Range {
2289 start: r.start.to_proto(),
2290 end: r.end.to_proto(),
2291 })
2292 .collect(),
2293 counts: undo
2294 .counts
2295 .iter()
2296 .map(|(edit_id, count)| proto::operation::UndoCount {
2297 replica_id: edit_id.replica_id as u32,
2298 local_timestamp: edit_id.value,
2299 count: *count,
2300 })
2301 .collect(),
2302 version: From::from(&undo.version),
2303 }),
2304 Operation::UpdateSelections {
2305 set_id,
2306 selections,
2307 lamport_timestamp,
2308 } => proto::operation::Variant::UpdateSelections(
2309 proto::operation::UpdateSelections {
2310 replica_id: set_id.replica_id as u32,
2311 local_timestamp: set_id.value,
2312 lamport_timestamp: lamport_timestamp.value,
2313 set: selections.as_ref().map(|selections| proto::SelectionSet {
2314 selections: selections.iter().map(Into::into).collect(),
2315 }),
2316 },
2317 ),
2318 Operation::SetActiveSelections {
2319 set_id,
2320 lamport_timestamp,
2321 } => proto::operation::Variant::SetActiveSelections(
2322 proto::operation::SetActiveSelections {
2323 replica_id: lamport_timestamp.replica_id as u32,
2324 local_timestamp: set_id.map(|set_id| set_id.value),
2325 lamport_timestamp: lamport_timestamp.value,
2326 },
2327 ),
2328 #[cfg(test)]
2329 Operation::Test(_) => unimplemented!(),
2330 }),
2331 }
2332 }
2333}
2334
2335impl<'a> Into<proto::operation::Edit> for &'a EditOperation {
2336 fn into(self) -> proto::operation::Edit {
2337 let ranges = self
2338 .ranges
2339 .iter()
2340 .map(|range| proto::Range {
2341 start: range.start.to_proto(),
2342 end: range.end.to_proto(),
2343 })
2344 .collect();
2345 proto::operation::Edit {
2346 replica_id: self.timestamp.replica_id as u32,
2347 local_timestamp: self.timestamp.local,
2348 lamport_timestamp: self.timestamp.lamport,
2349 version: From::from(&self.version),
2350 ranges,
2351 new_text: self.new_text.clone(),
2352 }
2353 }
2354}
2355
2356impl<'a> Into<proto::Anchor> for &'a Anchor {
2357 fn into(self) -> proto::Anchor {
2358 proto::Anchor {
2359 version: (&self.version).into(),
2360 offset: self.full_offset.to_proto(),
2361 bias: match self.bias {
2362 Bias::Left => proto::anchor::Bias::Left as i32,
2363 Bias::Right => proto::anchor::Bias::Right as i32,
2364 },
2365 }
2366 }
2367}
2368
2369impl<'a> Into<proto::Selection> for &'a Selection {
2370 fn into(self) -> proto::Selection {
2371 proto::Selection {
2372 id: self.id as u64,
2373 start: Some((&self.start).into()),
2374 end: Some((&self.end).into()),
2375 reversed: self.reversed,
2376 }
2377 }
2378}
2379
2380impl TryFrom<proto::Operation> for Operation {
2381 type Error = anyhow::Error;
2382
2383 fn try_from(message: proto::Operation) -> Result<Self, Self::Error> {
2384 Ok(
2385 match message
2386 .variant
2387 .ok_or_else(|| anyhow!("missing operation variant"))?
2388 {
2389 proto::operation::Variant::Edit(edit) => Operation::Edit(edit.into()),
2390 proto::operation::Variant::Undo(undo) => Operation::Undo {
2391 lamport_timestamp: clock::Lamport {
2392 replica_id: undo.replica_id as ReplicaId,
2393 value: undo.lamport_timestamp,
2394 },
2395 undo: UndoOperation {
2396 id: clock::Local {
2397 replica_id: undo.replica_id as ReplicaId,
2398 value: undo.local_timestamp,
2399 },
2400 counts: undo
2401 .counts
2402 .into_iter()
2403 .map(|c| {
2404 (
2405 clock::Local {
2406 replica_id: c.replica_id as ReplicaId,
2407 value: c.local_timestamp,
2408 },
2409 c.count,
2410 )
2411 })
2412 .collect(),
2413 ranges: undo
2414 .ranges
2415 .into_iter()
2416 .map(|r| FullOffset::from_proto(r.start)..FullOffset::from_proto(r.end))
2417 .collect(),
2418 version: undo.version.into(),
2419 },
2420 },
2421 proto::operation::Variant::UpdateSelections(message) => {
2422 let selections: Option<Vec<Selection>> = if let Some(set) = message.set {
2423 Some(
2424 set.selections
2425 .into_iter()
2426 .map(TryFrom::try_from)
2427 .collect::<Result<_, _>>()?,
2428 )
2429 } else {
2430 None
2431 };
2432 Operation::UpdateSelections {
2433 set_id: clock::Lamport {
2434 replica_id: message.replica_id as ReplicaId,
2435 value: message.local_timestamp,
2436 },
2437 lamport_timestamp: clock::Lamport {
2438 replica_id: message.replica_id as ReplicaId,
2439 value: message.lamport_timestamp,
2440 },
2441 selections: selections.map(Arc::from),
2442 }
2443 }
2444 proto::operation::Variant::SetActiveSelections(message) => {
2445 Operation::SetActiveSelections {
2446 set_id: message.local_timestamp.map(|value| clock::Lamport {
2447 replica_id: message.replica_id as ReplicaId,
2448 value,
2449 }),
2450 lamport_timestamp: clock::Lamport {
2451 replica_id: message.replica_id as ReplicaId,
2452 value: message.lamport_timestamp,
2453 },
2454 }
2455 }
2456 },
2457 )
2458 }
2459}
2460
2461impl From<proto::operation::Edit> for EditOperation {
2462 fn from(edit: proto::operation::Edit) -> Self {
2463 let ranges = edit
2464 .ranges
2465 .into_iter()
2466 .map(|range| FullOffset::from_proto(range.start)..FullOffset::from_proto(range.end))
2467 .collect();
2468 EditOperation {
2469 timestamp: InsertionTimestamp {
2470 replica_id: edit.replica_id as ReplicaId,
2471 local: edit.local_timestamp,
2472 lamport: edit.lamport_timestamp,
2473 },
2474 version: edit.version.into(),
2475 ranges,
2476 new_text: edit.new_text,
2477 }
2478 }
2479}
2480
2481impl TryFrom<proto::Anchor> for Anchor {
2482 type Error = anyhow::Error;
2483
2484 fn try_from(message: proto::Anchor) -> Result<Self, Self::Error> {
2485 let mut version = clock::Global::new();
2486 for entry in message.version {
2487 version.observe(clock::Local {
2488 replica_id: entry.replica_id as ReplicaId,
2489 value: entry.timestamp,
2490 });
2491 }
2492
2493 Ok(Self {
2494 full_offset: FullOffset::from_proto(message.offset),
2495 bias: if message.bias == proto::anchor::Bias::Left as i32 {
2496 Bias::Left
2497 } else if message.bias == proto::anchor::Bias::Right as i32 {
2498 Bias::Right
2499 } else {
2500 Err(anyhow!("invalid anchor bias {}", message.bias))?
2501 },
2502 version,
2503 })
2504 }
2505}
2506
2507impl TryFrom<proto::Selection> for Selection {
2508 type Error = anyhow::Error;
2509
2510 fn try_from(selection: proto::Selection) -> Result<Self, Self::Error> {
2511 Ok(Selection {
2512 id: selection.id as usize,
2513 start: selection
2514 .start
2515 .ok_or_else(|| anyhow!("missing selection start"))?
2516 .try_into()?,
2517 end: selection
2518 .end
2519 .ok_or_else(|| anyhow!("missing selection end"))?
2520 .try_into()?,
2521 reversed: selection.reversed,
2522 goal: SelectionGoal::None,
2523 })
2524 }
2525}
2526
2527pub trait ToOffset {
2528 fn to_offset<'a>(&self, content: impl Into<Content<'a>>) -> usize;
2529
2530 fn to_full_offset<'a>(&self, content: impl Into<Content<'a>>, bias: Bias) -> FullOffset {
2531 let content = content.into();
2532 let offset = self.to_offset(&content);
2533 let mut cursor = content.fragments.cursor::<FragmentTextSummary>();
2534 cursor.seek(&offset, bias, &None);
2535 FullOffset(offset + cursor.start().deleted)
2536 }
2537}
2538
2539impl ToOffset for Point {
2540 fn to_offset<'a>(&self, content: impl Into<Content<'a>>) -> usize {
2541 content.into().visible_text.to_offset(*self)
2542 }
2543}
2544
2545impl ToOffset for usize {
2546 fn to_offset<'a>(&self, content: impl Into<Content<'a>>) -> usize {
2547 assert!(*self <= content.into().len(), "offset is out of range");
2548 *self
2549 }
2550}
2551
2552impl ToOffset for Anchor {
2553 fn to_offset<'a>(&self, content: impl Into<Content<'a>>) -> usize {
2554 content.into().summary_for_anchor(self).bytes
2555 }
2556}
2557
2558impl<'a> ToOffset for &'a Anchor {
2559 fn to_offset<'b>(&self, content: impl Into<Content<'b>>) -> usize {
2560 content.into().summary_for_anchor(self).bytes
2561 }
2562}
2563
2564pub trait ToPoint {
2565 fn to_point<'a>(&self, content: impl Into<Content<'a>>) -> Point;
2566}
2567
2568impl ToPoint for Anchor {
2569 fn to_point<'a>(&self, content: impl Into<Content<'a>>) -> Point {
2570 content.into().summary_for_anchor(self).lines
2571 }
2572}
2573
2574impl ToPoint for usize {
2575 fn to_point<'a>(&self, content: impl Into<Content<'a>>) -> Point {
2576 content.into().visible_text.to_point(*self)
2577 }
2578}
2579
2580pub trait FromAnchor {
2581 fn from_anchor<'a>(anchor: &Anchor, content: &Content<'a>) -> Self;
2582}
2583
2584impl FromAnchor for Point {
2585 fn from_anchor<'a>(anchor: &Anchor, content: &Content<'a>) -> Self {
2586 anchor.to_point(content)
2587 }
2588}
2589
2590impl FromAnchor for usize {
2591 fn from_anchor<'a>(anchor: &Anchor, content: &Content<'a>) -> Self {
2592 anchor.to_offset(content)
2593 }
2594}