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