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