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