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