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: &'a 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>(
1369 &'a self,
1370 since: &'a clock::Global,
1371 ) -> impl 'a + Iterator<Item = Edit<D>>
1372 where
1373 D: 'a + TextDimension<'a> + Ord,
1374 {
1375 self.content().edits_since(since)
1376 }
1377}
1378
1379#[cfg(any(test, feature = "test-support"))]
1380impl Buffer {
1381 fn random_byte_range(&mut self, start_offset: usize, rng: &mut impl rand::Rng) -> Range<usize> {
1382 let end = self.clip_offset(rng.gen_range(start_offset..=self.len()), Bias::Right);
1383 let start = self.clip_offset(rng.gen_range(start_offset..=end), Bias::Right);
1384 start..end
1385 }
1386
1387 pub fn randomly_edit<T>(
1388 &mut self,
1389 rng: &mut T,
1390 old_range_count: usize,
1391 ) -> (Vec<Range<usize>>, String, Operation)
1392 where
1393 T: rand::Rng,
1394 {
1395 let mut old_ranges: Vec<Range<usize>> = Vec::new();
1396 for _ in 0..old_range_count {
1397 let last_end = old_ranges.last().map_or(0, |last_range| last_range.end + 1);
1398 if last_end > self.len() {
1399 break;
1400 }
1401 old_ranges.push(self.random_byte_range(last_end, rng));
1402 }
1403 let new_text_len = rng.gen_range(0..10);
1404 let new_text: String = crate::random_char_iter::RandomCharIter::new(&mut *rng)
1405 .take(new_text_len)
1406 .collect();
1407 log::info!(
1408 "mutating buffer {} at {:?}: {:?}",
1409 self.replica_id,
1410 old_ranges,
1411 new_text
1412 );
1413 let op = self.edit(old_ranges.iter().cloned(), new_text.as_str());
1414 (old_ranges, new_text, Operation::Edit(op))
1415 }
1416
1417 pub fn randomly_mutate<T>(&mut self, rng: &mut T) -> Vec<Operation>
1418 where
1419 T: rand::Rng,
1420 {
1421 use rand::prelude::*;
1422
1423 let mut ops = vec![self.randomly_edit(rng, 5).2];
1424
1425 // Randomly add, remove or mutate selection sets.
1426 let replica_selection_sets = &self
1427 .selection_sets()
1428 .map(|(set_id, _)| *set_id)
1429 .filter(|set_id| self.replica_id == set_id.replica_id)
1430 .collect::<Vec<_>>();
1431 let set_id = replica_selection_sets.choose(rng);
1432 if set_id.is_some() && rng.gen_bool(1.0 / 6.0) {
1433 ops.push(self.remove_selection_set(*set_id.unwrap()).unwrap());
1434 } else {
1435 let mut ranges = Vec::new();
1436 for _ in 0..5 {
1437 ranges.push(self.random_byte_range(0, rng));
1438 }
1439 let new_selections = self.selections_from_ranges(ranges).unwrap();
1440
1441 let op = if set_id.is_none() || rng.gen_bool(1.0 / 5.0) {
1442 self.add_selection_set(&new_selections)
1443 } else {
1444 self.update_selection_set(*set_id.unwrap(), &new_selections)
1445 .unwrap()
1446 };
1447 ops.push(op);
1448 }
1449
1450 ops
1451 }
1452
1453 pub fn randomly_undo_redo(&mut self, rng: &mut impl rand::Rng) -> Vec<Operation> {
1454 use rand::prelude::*;
1455
1456 let mut ops = Vec::new();
1457 for _ in 0..rng.gen_range(1..=5) {
1458 if let Some(transaction) = self.history.undo_stack.choose(rng).cloned() {
1459 log::info!(
1460 "undoing buffer {} transaction {:?}",
1461 self.replica_id,
1462 transaction
1463 );
1464 ops.push(self.undo_or_redo(transaction).unwrap());
1465 }
1466 }
1467 ops
1468 }
1469
1470 fn selections_from_ranges<I>(&self, ranges: I) -> Result<Vec<Selection<usize>>>
1471 where
1472 I: IntoIterator<Item = Range<usize>>,
1473 {
1474 use std::sync::atomic::{self, AtomicUsize};
1475
1476 static NEXT_SELECTION_ID: AtomicUsize = AtomicUsize::new(0);
1477
1478 let mut ranges = ranges.into_iter().collect::<Vec<_>>();
1479 ranges.sort_unstable_by_key(|range| range.start);
1480
1481 let mut selections = Vec::<Selection<usize>>::with_capacity(ranges.len());
1482 for mut range in ranges {
1483 let mut reversed = false;
1484 if range.start > range.end {
1485 reversed = true;
1486 std::mem::swap(&mut range.start, &mut range.end);
1487 }
1488
1489 if let Some(selection) = selections.last_mut() {
1490 if selection.end >= range.start {
1491 selection.end = range.end;
1492 continue;
1493 }
1494 }
1495
1496 selections.push(Selection {
1497 id: NEXT_SELECTION_ID.fetch_add(1, atomic::Ordering::SeqCst),
1498 start: range.start,
1499 end: range.end,
1500 reversed,
1501 goal: SelectionGoal::None,
1502 });
1503 }
1504 Ok(selections)
1505 }
1506
1507 pub fn selection_ranges<'a>(&'a self, set_id: SelectionSetId) -> Result<Vec<Range<usize>>> {
1508 Ok(self
1509 .selection_set(set_id)?
1510 .offset_selections(self)
1511 .map(move |selection| {
1512 if selection.reversed {
1513 selection.end..selection.start
1514 } else {
1515 selection.start..selection.end
1516 }
1517 })
1518 .collect())
1519 }
1520
1521 pub fn all_selection_ranges<'a>(
1522 &'a self,
1523 ) -> impl 'a + Iterator<Item = (SelectionSetId, Vec<Range<usize>>)> {
1524 self.selections
1525 .keys()
1526 .map(move |set_id| (*set_id, self.selection_ranges(*set_id).unwrap()))
1527 }
1528}
1529
1530#[derive(Clone)]
1531pub struct Snapshot {
1532 visible_text: Rope,
1533 deleted_text: Rope,
1534 undo_map: UndoMap,
1535 fragments: SumTree<Fragment>,
1536 version: clock::Global,
1537}
1538
1539impl Snapshot {
1540 pub fn as_rope(&self) -> &Rope {
1541 &self.visible_text
1542 }
1543
1544 pub fn len(&self) -> usize {
1545 self.visible_text.len()
1546 }
1547
1548 pub fn line_len(&self, row: u32) -> u32 {
1549 self.content().line_len(row)
1550 }
1551
1552 pub fn indent_column_for_line(&self, row: u32) -> u32 {
1553 self.content().indent_column_for_line(row)
1554 }
1555
1556 pub fn text(&self) -> Rope {
1557 self.visible_text.clone()
1558 }
1559
1560 pub fn text_summary(&self) -> TextSummary {
1561 self.visible_text.summary()
1562 }
1563
1564 pub fn max_point(&self) -> Point {
1565 self.visible_text.max_point()
1566 }
1567
1568 pub fn text_for_range<T: ToOffset>(&self, range: Range<T>) -> Chunks {
1569 let range = range.start.to_offset(self)..range.end.to_offset(self);
1570 self.visible_text.chunks_in_range(range)
1571 }
1572
1573 pub fn text_summary_for_range<T>(&self, range: Range<T>) -> TextSummary
1574 where
1575 T: ToOffset,
1576 {
1577 let range = range.start.to_offset(self.content())..range.end.to_offset(self.content());
1578 self.content().text_summary_for_range(range)
1579 }
1580
1581 pub fn point_for_offset(&self, offset: usize) -> Result<Point> {
1582 self.content().point_for_offset(offset)
1583 }
1584
1585 pub fn clip_offset(&self, offset: usize, bias: Bias) -> usize {
1586 self.visible_text.clip_offset(offset, bias)
1587 }
1588
1589 pub fn clip_point(&self, point: Point, bias: Bias) -> Point {
1590 self.visible_text.clip_point(point, bias)
1591 }
1592
1593 pub fn to_offset(&self, point: Point) -> usize {
1594 self.visible_text.point_to_offset(point)
1595 }
1596
1597 pub fn to_point(&self, offset: usize) -> Point {
1598 self.visible_text.offset_to_point(offset)
1599 }
1600
1601 pub fn anchor_before<T: ToOffset>(&self, position: T) -> Anchor {
1602 self.content().anchor_at(position, Bias::Left)
1603 }
1604
1605 pub fn anchor_after<T: ToOffset>(&self, position: T) -> Anchor {
1606 self.content().anchor_at(position, Bias::Right)
1607 }
1608
1609 pub fn edits_since<'a, D>(
1610 &'a self,
1611 since: &'a clock::Global,
1612 ) -> impl 'a + Iterator<Item = Edit<D>>
1613 where
1614 D: 'a + TextDimension<'a> + Ord,
1615 {
1616 self.content().edits_since(since)
1617 }
1618
1619 pub fn version(&self) -> &clock::Global {
1620 &self.version
1621 }
1622
1623 pub fn content(&self) -> Content {
1624 self.into()
1625 }
1626}
1627
1628#[derive(Clone)]
1629pub struct Content<'a> {
1630 visible_text: &'a Rope,
1631 deleted_text: &'a Rope,
1632 undo_map: &'a UndoMap,
1633 fragments: &'a SumTree<Fragment>,
1634 version: &'a clock::Global,
1635}
1636
1637impl<'a> From<&'a Snapshot> for Content<'a> {
1638 fn from(snapshot: &'a Snapshot) -> Self {
1639 Self {
1640 visible_text: &snapshot.visible_text,
1641 deleted_text: &snapshot.deleted_text,
1642 undo_map: &snapshot.undo_map,
1643 fragments: &snapshot.fragments,
1644 version: &snapshot.version,
1645 }
1646 }
1647}
1648
1649impl<'a> From<&'a Buffer> for Content<'a> {
1650 fn from(buffer: &'a Buffer) -> Self {
1651 Self {
1652 visible_text: &buffer.visible_text,
1653 deleted_text: &buffer.deleted_text,
1654 undo_map: &buffer.undo_map,
1655 fragments: &buffer.fragments,
1656 version: &buffer.version,
1657 }
1658 }
1659}
1660
1661impl<'a> From<&'a mut Buffer> for Content<'a> {
1662 fn from(buffer: &'a mut Buffer) -> Self {
1663 Self {
1664 visible_text: &buffer.visible_text,
1665 deleted_text: &buffer.deleted_text,
1666 undo_map: &buffer.undo_map,
1667 fragments: &buffer.fragments,
1668 version: &buffer.version,
1669 }
1670 }
1671}
1672
1673impl<'a> From<&'a Content<'a>> for Content<'a> {
1674 fn from(content: &'a Content) -> Self {
1675 Self {
1676 visible_text: &content.visible_text,
1677 deleted_text: &content.deleted_text,
1678 undo_map: &content.undo_map,
1679 fragments: &content.fragments,
1680 version: &content.version,
1681 }
1682 }
1683}
1684
1685impl<'a> Content<'a> {
1686 fn max_point(&self) -> Point {
1687 self.visible_text.max_point()
1688 }
1689
1690 fn len(&self) -> usize {
1691 self.fragments.extent::<usize>(&None)
1692 }
1693
1694 pub fn chars_at<T: ToOffset>(&self, position: T) -> impl Iterator<Item = char> + 'a {
1695 let offset = position.to_offset(self);
1696 self.visible_text.chars_at(offset)
1697 }
1698
1699 pub fn reversed_chars_at<T: ToOffset>(&self, position: T) -> impl Iterator<Item = char> + 'a {
1700 let offset = position.to_offset(self);
1701 self.visible_text.reversed_chars_at(offset)
1702 }
1703
1704 pub fn text_for_range<T: ToOffset>(&self, range: Range<T>) -> Chunks<'a> {
1705 let start = range.start.to_offset(self);
1706 let end = range.end.to_offset(self);
1707 self.visible_text.chunks_in_range(start..end)
1708 }
1709
1710 fn line_len(&self, row: u32) -> u32 {
1711 let row_start_offset = Point::new(row, 0).to_offset(self);
1712 let row_end_offset = if row >= self.max_point().row {
1713 self.len()
1714 } else {
1715 Point::new(row + 1, 0).to_offset(self) - 1
1716 };
1717 (row_end_offset - row_start_offset) as u32
1718 }
1719
1720 pub fn indent_column_for_line(&self, row: u32) -> u32 {
1721 let mut result = 0;
1722 for c in self.chars_at(Point::new(row, 0)) {
1723 if c == ' ' {
1724 result += 1;
1725 } else {
1726 break;
1727 }
1728 }
1729 result
1730 }
1731
1732 fn summary_for_anchor(&self, anchor: &Anchor) -> TextSummary {
1733 let cx = Some(anchor.version.clone());
1734 let mut cursor = self.fragments.cursor::<(VersionedFullOffset, usize)>();
1735 cursor.seek(
1736 &VersionedFullOffset::Offset(anchor.full_offset),
1737 anchor.bias,
1738 &cx,
1739 );
1740 let overshoot = if cursor.item().map_or(false, |fragment| fragment.visible) {
1741 anchor.full_offset - cursor.start().0.full_offset()
1742 } else {
1743 0
1744 };
1745 self.text_summary_for_range(0..cursor.start().1 + overshoot)
1746 }
1747
1748 fn text_summary_for_range(&self, range: Range<usize>) -> TextSummary {
1749 self.visible_text.cursor(range.start).summary(range.end)
1750 }
1751
1752 fn summaries_for_anchors<T>(
1753 &self,
1754 map: &'a AnchorMap<T>,
1755 ) -> impl Iterator<Item = (TextSummary, &'a T)> {
1756 let cx = Some(map.version.clone());
1757 let mut summary = TextSummary::default();
1758 let mut rope_cursor = self.visible_text.cursor(0);
1759 let mut cursor = self.fragments.cursor::<(VersionedFullOffset, usize)>();
1760 map.entries.iter().map(move |((offset, bias), value)| {
1761 cursor.seek_forward(&VersionedFullOffset::Offset(*offset), *bias, &cx);
1762 let overshoot = if cursor.item().map_or(false, |fragment| fragment.visible) {
1763 *offset - cursor.start().0.full_offset()
1764 } else {
1765 0
1766 };
1767 summary += rope_cursor.summary::<TextSummary>(cursor.start().1 + overshoot);
1768 (summary.clone(), value)
1769 })
1770 }
1771
1772 fn summaries_for_anchor_ranges<T>(
1773 &self,
1774 map: &'a AnchorRangeMap<T>,
1775 ) -> impl Iterator<Item = (Range<TextSummary>, &'a T)> {
1776 let cx = Some(map.version.clone());
1777 let mut summary = TextSummary::default();
1778 let mut rope_cursor = self.visible_text.cursor(0);
1779 let mut cursor = self.fragments.cursor::<(VersionedFullOffset, usize)>();
1780 map.entries.iter().map(move |(range, value)| {
1781 let Range {
1782 start: (start_offset, start_bias),
1783 end: (end_offset, end_bias),
1784 } = range;
1785
1786 cursor.seek_forward(
1787 &VersionedFullOffset::Offset(*start_offset),
1788 *start_bias,
1789 &cx,
1790 );
1791 let overshoot = if cursor.item().map_or(false, |fragment| fragment.visible) {
1792 *start_offset - cursor.start().0.full_offset()
1793 } else {
1794 0
1795 };
1796 summary += rope_cursor.summary::<TextSummary>(cursor.start().1 + overshoot);
1797 let start_summary = summary.clone();
1798
1799 cursor.seek_forward(&VersionedFullOffset::Offset(*end_offset), *end_bias, &cx);
1800 let overshoot = if cursor.item().map_or(false, |fragment| fragment.visible) {
1801 *end_offset - cursor.start().0.full_offset()
1802 } else {
1803 0
1804 };
1805 summary += rope_cursor.summary::<TextSummary>(cursor.start().1 + overshoot);
1806 let end_summary = summary.clone();
1807
1808 (start_summary..end_summary, value)
1809 })
1810 }
1811
1812 fn anchor_at<T: ToOffset>(&self, position: T, bias: Bias) -> Anchor {
1813 Anchor {
1814 full_offset: position.to_full_offset(self, bias),
1815 bias,
1816 version: self.version.clone(),
1817 }
1818 }
1819
1820 pub fn anchor_map<T, E>(&self, entries: E) -> AnchorMap<T>
1821 where
1822 E: IntoIterator<Item = ((usize, Bias), T)>,
1823 {
1824 let version = self.version.clone();
1825 let mut cursor = self.fragments.cursor::<FragmentTextSummary>();
1826 let entries = entries
1827 .into_iter()
1828 .map(|((offset, bias), value)| {
1829 cursor.seek_forward(&offset, bias, &None);
1830 let full_offset = FullOffset(cursor.start().deleted + offset);
1831 ((full_offset, bias), value)
1832 })
1833 .collect();
1834
1835 AnchorMap { version, entries }
1836 }
1837
1838 pub fn anchor_range_map<T, E>(&self, entries: E) -> AnchorRangeMap<T>
1839 where
1840 E: IntoIterator<Item = (Range<(usize, Bias)>, T)>,
1841 {
1842 let version = self.version.clone();
1843 let mut cursor = self.fragments.cursor::<FragmentTextSummary>();
1844 let entries = entries
1845 .into_iter()
1846 .map(|(range, value)| {
1847 let Range {
1848 start: (start_offset, start_bias),
1849 end: (end_offset, end_bias),
1850 } = range;
1851 cursor.seek_forward(&start_offset, start_bias, &None);
1852 let full_start_offset = FullOffset(cursor.start().deleted + start_offset);
1853 cursor.seek_forward(&end_offset, end_bias, &None);
1854 let full_end_offset = FullOffset(cursor.start().deleted + end_offset);
1855 (
1856 (full_start_offset, start_bias)..(full_end_offset, end_bias),
1857 value,
1858 )
1859 })
1860 .collect();
1861
1862 AnchorRangeMap { version, entries }
1863 }
1864
1865 pub fn anchor_set<E>(&self, entries: E) -> AnchorSet
1866 where
1867 E: IntoIterator<Item = (usize, Bias)>,
1868 {
1869 AnchorSet(self.anchor_map(entries.into_iter().map(|range| (range, ()))))
1870 }
1871
1872 pub fn anchor_range_set<E>(&self, entries: E) -> AnchorRangeSet
1873 where
1874 E: IntoIterator<Item = Range<(usize, Bias)>>,
1875 {
1876 AnchorRangeSet(self.anchor_range_map(entries.into_iter().map(|range| (range, ()))))
1877 }
1878
1879 pub fn anchor_range_multimap<T, E, O>(
1880 &self,
1881 start_bias: Bias,
1882 end_bias: Bias,
1883 entries: E,
1884 ) -> AnchorRangeMultimap<T>
1885 where
1886 T: Clone,
1887 E: IntoIterator<Item = (Range<O>, T)>,
1888 O: ToOffset,
1889 {
1890 let mut entries = entries
1891 .into_iter()
1892 .map(|(range, value)| AnchorRangeMultimapEntry {
1893 range: FullOffsetRange {
1894 start: range.start.to_full_offset(self, start_bias),
1895 end: range.end.to_full_offset(self, end_bias),
1896 },
1897 value,
1898 })
1899 .collect::<Vec<_>>();
1900 entries.sort_unstable_by_key(|i| (i.range.start, Reverse(i.range.end)));
1901 AnchorRangeMultimap {
1902 entries: SumTree::from_iter(entries, &()),
1903 version: self.version.clone(),
1904 start_bias,
1905 end_bias,
1906 }
1907 }
1908
1909 fn full_offset_for_anchor(&self, anchor: &Anchor) -> FullOffset {
1910 let cx = Some(anchor.version.clone());
1911 let mut cursor = self
1912 .fragments
1913 .cursor::<(VersionedFullOffset, FragmentTextSummary)>();
1914 cursor.seek(
1915 &VersionedFullOffset::Offset(anchor.full_offset),
1916 anchor.bias,
1917 &cx,
1918 );
1919 let overshoot = if cursor.item().is_some() {
1920 anchor.full_offset - cursor.start().0.full_offset()
1921 } else {
1922 0
1923 };
1924 let summary = cursor.start().1;
1925 FullOffset(summary.visible + summary.deleted + overshoot)
1926 }
1927
1928 pub fn clip_point(&self, point: Point, bias: Bias) -> Point {
1929 self.visible_text.clip_point(point, bias)
1930 }
1931
1932 pub fn clip_point_utf16(&self, point: PointUtf16, bias: Bias) -> PointUtf16 {
1933 self.visible_text.clip_point_utf16(point, bias)
1934 }
1935
1936 fn point_for_offset(&self, offset: usize) -> Result<Point> {
1937 if offset <= self.len() {
1938 Ok(self.text_summary_for_range(0..offset).lines)
1939 } else {
1940 Err(anyhow!("offset out of bounds"))
1941 }
1942 }
1943
1944 pub fn edits_since<D>(&self, since: &'a clock::Global) -> impl 'a + Iterator<Item = Edit<D>>
1945 where
1946 D: 'a + TextDimension<'a> + Ord,
1947 {
1948 let fragments_cursor = if since == self.version {
1949 None
1950 } else {
1951 Some(self.fragments.filter(
1952 move |summary| summary.max_version.changed_since(since),
1953 &None,
1954 ))
1955 };
1956
1957 Edits {
1958 visible_cursor: self.visible_text.cursor(0),
1959 deleted_cursor: self.deleted_text.cursor(0),
1960 fragments_cursor,
1961 undos: &self.undo_map,
1962 since,
1963 old_end: Default::default(),
1964 new_end: Default::default(),
1965 }
1966 }
1967}
1968
1969struct RopeBuilder<'a> {
1970 old_visible_cursor: rope::Cursor<'a>,
1971 old_deleted_cursor: rope::Cursor<'a>,
1972 new_visible: Rope,
1973 new_deleted: Rope,
1974}
1975
1976impl<'a> RopeBuilder<'a> {
1977 fn new(old_visible_cursor: rope::Cursor<'a>, old_deleted_cursor: rope::Cursor<'a>) -> Self {
1978 Self {
1979 old_visible_cursor,
1980 old_deleted_cursor,
1981 new_visible: Rope::new(),
1982 new_deleted: Rope::new(),
1983 }
1984 }
1985
1986 fn push_tree(&mut self, len: FragmentTextSummary) {
1987 self.push(len.visible, true, true);
1988 self.push(len.deleted, false, false);
1989 }
1990
1991 fn push_fragment(&mut self, fragment: &Fragment, was_visible: bool) {
1992 debug_assert!(fragment.len > 0);
1993 self.push(fragment.len, was_visible, fragment.visible)
1994 }
1995
1996 fn push(&mut self, len: usize, was_visible: bool, is_visible: bool) {
1997 let text = if was_visible {
1998 self.old_visible_cursor
1999 .slice(self.old_visible_cursor.offset() + len)
2000 } else {
2001 self.old_deleted_cursor
2002 .slice(self.old_deleted_cursor.offset() + len)
2003 };
2004 if is_visible {
2005 self.new_visible.append(text);
2006 } else {
2007 self.new_deleted.append(text);
2008 }
2009 }
2010
2011 fn push_str(&mut self, text: &str) {
2012 self.new_visible.push(text);
2013 }
2014
2015 fn finish(mut self) -> (Rope, Rope) {
2016 self.new_visible.append(self.old_visible_cursor.suffix());
2017 self.new_deleted.append(self.old_deleted_cursor.suffix());
2018 (self.new_visible, self.new_deleted)
2019 }
2020}
2021
2022impl<'a, D: TextDimension<'a> + Ord, F: FnMut(&FragmentSummary) -> bool> Iterator
2023 for Edits<'a, D, F>
2024{
2025 type Item = Edit<D>;
2026
2027 fn next(&mut self) -> Option<Self::Item> {
2028 let mut pending_edit: Option<Edit<D>> = None;
2029 let cursor = self.fragments_cursor.as_mut()?;
2030
2031 while let Some(fragment) = cursor.item() {
2032 let summary = self.visible_cursor.summary(cursor.start().visible);
2033 self.old_end.add_assign(&summary);
2034 self.new_end.add_assign(&summary);
2035 if pending_edit
2036 .as_ref()
2037 .map_or(false, |change| change.new.end < self.new_end)
2038 {
2039 break;
2040 }
2041
2042 if !fragment.was_visible(&self.since, &self.undos) && fragment.visible {
2043 let fragment_summary = self.visible_cursor.summary(cursor.end(&None).visible);
2044 let mut new_end = self.new_end.clone();
2045 new_end.add_assign(&fragment_summary);
2046 if let Some(pending_edit) = pending_edit.as_mut() {
2047 pending_edit.new.end = new_end.clone();
2048 } else {
2049 pending_edit = Some(Edit {
2050 old: self.old_end.clone()..self.old_end.clone(),
2051 new: self.new_end.clone()..new_end.clone(),
2052 });
2053 }
2054
2055 self.new_end = new_end;
2056 } else if fragment.was_visible(&self.since, &self.undos) && !fragment.visible {
2057 self.deleted_cursor.seek_forward(cursor.start().deleted);
2058 let fragment_summary = self.deleted_cursor.summary(cursor.end(&None).deleted);
2059 let mut old_end = self.old_end.clone();
2060 old_end.add_assign(&fragment_summary);
2061 if let Some(pending_edit) = pending_edit.as_mut() {
2062 pending_edit.old.end = old_end.clone();
2063 } else {
2064 pending_edit = Some(Edit {
2065 old: self.old_end.clone()..old_end.clone(),
2066 new: self.new_end.clone()..self.new_end.clone(),
2067 });
2068 }
2069
2070 self.old_end = old_end;
2071 }
2072
2073 cursor.next(&None);
2074 }
2075
2076 pending_edit
2077 }
2078}
2079
2080impl Fragment {
2081 fn is_visible(&self, undos: &UndoMap) -> bool {
2082 !undos.is_undone(self.timestamp.local())
2083 && self.deletions.iter().all(|d| undos.is_undone(*d))
2084 }
2085
2086 fn was_visible(&self, version: &clock::Global, undos: &UndoMap) -> bool {
2087 (version.observed(self.timestamp.local())
2088 && !undos.was_undone(self.timestamp.local(), version))
2089 && self
2090 .deletions
2091 .iter()
2092 .all(|d| !version.observed(*d) || undos.was_undone(*d, version))
2093 }
2094}
2095
2096impl sum_tree::Item for Fragment {
2097 type Summary = FragmentSummary;
2098
2099 fn summary(&self) -> Self::Summary {
2100 let mut max_version = clock::Global::new();
2101 max_version.observe(self.timestamp.local());
2102 for deletion in &self.deletions {
2103 max_version.observe(*deletion);
2104 }
2105 max_version.join(&self.max_undos);
2106
2107 let mut min_insertion_version = clock::Global::new();
2108 min_insertion_version.observe(self.timestamp.local());
2109 let max_insertion_version = min_insertion_version.clone();
2110 if self.visible {
2111 FragmentSummary {
2112 text: FragmentTextSummary {
2113 visible: self.len,
2114 deleted: 0,
2115 },
2116 max_version,
2117 min_insertion_version,
2118 max_insertion_version,
2119 }
2120 } else {
2121 FragmentSummary {
2122 text: FragmentTextSummary {
2123 visible: 0,
2124 deleted: self.len,
2125 },
2126 max_version,
2127 min_insertion_version,
2128 max_insertion_version,
2129 }
2130 }
2131 }
2132}
2133
2134impl sum_tree::Summary for FragmentSummary {
2135 type Context = Option<clock::Global>;
2136
2137 fn add_summary(&mut self, other: &Self, _: &Self::Context) {
2138 self.text.visible += &other.text.visible;
2139 self.text.deleted += &other.text.deleted;
2140 self.max_version.join(&other.max_version);
2141 self.min_insertion_version
2142 .meet(&other.min_insertion_version);
2143 self.max_insertion_version
2144 .join(&other.max_insertion_version);
2145 }
2146}
2147
2148impl Default for FragmentSummary {
2149 fn default() -> Self {
2150 FragmentSummary {
2151 text: FragmentTextSummary::default(),
2152 max_version: clock::Global::new(),
2153 min_insertion_version: clock::Global::new(),
2154 max_insertion_version: clock::Global::new(),
2155 }
2156 }
2157}
2158
2159#[derive(Copy, Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
2160pub struct FullOffset(usize);
2161
2162impl FullOffset {
2163 const MAX: Self = FullOffset(usize::MAX);
2164
2165 fn to_proto(self) -> u64 {
2166 self.0 as u64
2167 }
2168
2169 fn from_proto(value: u64) -> Self {
2170 Self(value as usize)
2171 }
2172}
2173
2174impl ops::AddAssign<usize> for FullOffset {
2175 fn add_assign(&mut self, rhs: usize) {
2176 self.0 += rhs;
2177 }
2178}
2179
2180impl ops::Add<usize> for FullOffset {
2181 type Output = Self;
2182
2183 fn add(mut self, rhs: usize) -> Self::Output {
2184 self += rhs;
2185 self
2186 }
2187}
2188
2189impl ops::Sub for FullOffset {
2190 type Output = usize;
2191
2192 fn sub(self, rhs: Self) -> Self::Output {
2193 self.0 - rhs.0
2194 }
2195}
2196
2197impl<'a> sum_tree::Dimension<'a, FragmentSummary> for usize {
2198 fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
2199 *self += summary.text.visible;
2200 }
2201}
2202
2203impl<'a> sum_tree::Dimension<'a, FragmentSummary> for FullOffset {
2204 fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
2205 self.0 += summary.text.visible + summary.text.deleted;
2206 }
2207}
2208
2209impl<'a> sum_tree::SeekTarget<'a, FragmentSummary, FragmentTextSummary> for usize {
2210 fn cmp(
2211 &self,
2212 cursor_location: &FragmentTextSummary,
2213 _: &Option<clock::Global>,
2214 ) -> cmp::Ordering {
2215 Ord::cmp(self, &cursor_location.visible)
2216 }
2217}
2218
2219#[derive(Copy, Clone, Debug, Eq, PartialEq)]
2220enum VersionedFullOffset {
2221 Offset(FullOffset),
2222 Invalid,
2223}
2224
2225impl VersionedFullOffset {
2226 fn full_offset(&self) -> FullOffset {
2227 if let Self::Offset(position) = self {
2228 *position
2229 } else {
2230 panic!("invalid version")
2231 }
2232 }
2233}
2234
2235impl Default for VersionedFullOffset {
2236 fn default() -> Self {
2237 Self::Offset(Default::default())
2238 }
2239}
2240
2241impl<'a> sum_tree::Dimension<'a, FragmentSummary> for VersionedFullOffset {
2242 fn add_summary(&mut self, summary: &'a FragmentSummary, cx: &Option<clock::Global>) {
2243 if let Self::Offset(offset) = self {
2244 let version = cx.as_ref().unwrap();
2245 if *version >= summary.max_insertion_version {
2246 *offset += summary.text.visible + summary.text.deleted;
2247 } else if !summary
2248 .min_insertion_version
2249 .iter()
2250 .all(|t| !version.observed(*t))
2251 {
2252 *self = Self::Invalid;
2253 }
2254 }
2255 }
2256}
2257
2258impl<'a> sum_tree::SeekTarget<'a, FragmentSummary, Self> for VersionedFullOffset {
2259 fn cmp(&self, cursor_position: &Self, _: &Option<clock::Global>) -> cmp::Ordering {
2260 match (self, cursor_position) {
2261 (Self::Offset(a), Self::Offset(b)) => Ord::cmp(a, b),
2262 (Self::Offset(_), Self::Invalid) => cmp::Ordering::Less,
2263 (Self::Invalid, _) => unreachable!(),
2264 }
2265 }
2266}
2267
2268impl Operation {
2269 fn replica_id(&self) -> ReplicaId {
2270 self.lamport_timestamp().replica_id
2271 }
2272
2273 fn lamport_timestamp(&self) -> clock::Lamport {
2274 match self {
2275 Operation::Edit(edit) => edit.timestamp.lamport(),
2276 Operation::Undo {
2277 lamport_timestamp, ..
2278 } => *lamport_timestamp,
2279 Operation::UpdateSelections {
2280 lamport_timestamp, ..
2281 } => *lamport_timestamp,
2282 Operation::RemoveSelections {
2283 lamport_timestamp, ..
2284 } => *lamport_timestamp,
2285 Operation::SetActiveSelections {
2286 lamport_timestamp, ..
2287 } => *lamport_timestamp,
2288 #[cfg(test)]
2289 Operation::Test(lamport_timestamp) => *lamport_timestamp,
2290 }
2291 }
2292
2293 pub fn is_edit(&self) -> bool {
2294 match self {
2295 Operation::Edit { .. } => true,
2296 _ => false,
2297 }
2298 }
2299}
2300
2301impl<'a> Into<proto::Operation> for &'a Operation {
2302 fn into(self) -> proto::Operation {
2303 proto::Operation {
2304 variant: Some(match self {
2305 Operation::Edit(edit) => proto::operation::Variant::Edit(edit.into()),
2306 Operation::Undo {
2307 undo,
2308 lamport_timestamp,
2309 } => proto::operation::Variant::Undo(proto::operation::Undo {
2310 replica_id: undo.id.replica_id as u32,
2311 local_timestamp: undo.id.value,
2312 lamport_timestamp: lamport_timestamp.value,
2313 ranges: undo
2314 .ranges
2315 .iter()
2316 .map(|r| proto::Range {
2317 start: r.start.to_proto(),
2318 end: r.end.to_proto(),
2319 })
2320 .collect(),
2321 counts: undo
2322 .counts
2323 .iter()
2324 .map(|(edit_id, count)| proto::operation::UndoCount {
2325 replica_id: edit_id.replica_id as u32,
2326 local_timestamp: edit_id.value,
2327 count: *count,
2328 })
2329 .collect(),
2330 version: From::from(&undo.version),
2331 }),
2332 Operation::UpdateSelections {
2333 set_id,
2334 selections,
2335 lamport_timestamp,
2336 } => proto::operation::Variant::UpdateSelections(
2337 proto::operation::UpdateSelections {
2338 replica_id: set_id.replica_id as u32,
2339 local_timestamp: set_id.value,
2340 lamport_timestamp: lamport_timestamp.value,
2341 version: selections.version().into(),
2342 selections: selections
2343 .raw_entries()
2344 .iter()
2345 .map(|(range, state)| proto::Selection {
2346 id: state.id as u64,
2347 start: range.start.0.to_proto(),
2348 end: range.end.0.to_proto(),
2349 reversed: state.reversed,
2350 })
2351 .collect(),
2352 },
2353 ),
2354 Operation::RemoveSelections {
2355 set_id,
2356 lamport_timestamp,
2357 } => proto::operation::Variant::RemoveSelections(
2358 proto::operation::RemoveSelections {
2359 replica_id: set_id.replica_id as u32,
2360 local_timestamp: set_id.value,
2361 lamport_timestamp: lamport_timestamp.value,
2362 },
2363 ),
2364 Operation::SetActiveSelections {
2365 set_id,
2366 lamport_timestamp,
2367 } => proto::operation::Variant::SetActiveSelections(
2368 proto::operation::SetActiveSelections {
2369 replica_id: lamport_timestamp.replica_id as u32,
2370 local_timestamp: set_id.map(|set_id| set_id.value),
2371 lamport_timestamp: lamport_timestamp.value,
2372 },
2373 ),
2374 #[cfg(test)]
2375 Operation::Test(_) => unimplemented!(),
2376 }),
2377 }
2378 }
2379}
2380
2381impl<'a> Into<proto::operation::Edit> for &'a EditOperation {
2382 fn into(self) -> proto::operation::Edit {
2383 let ranges = self
2384 .ranges
2385 .iter()
2386 .map(|range| proto::Range {
2387 start: range.start.to_proto(),
2388 end: range.end.to_proto(),
2389 })
2390 .collect();
2391 proto::operation::Edit {
2392 replica_id: self.timestamp.replica_id as u32,
2393 local_timestamp: self.timestamp.local,
2394 lamport_timestamp: self.timestamp.lamport,
2395 version: From::from(&self.version),
2396 ranges,
2397 new_text: self.new_text.clone(),
2398 }
2399 }
2400}
2401
2402impl TryFrom<proto::Operation> for Operation {
2403 type Error = anyhow::Error;
2404
2405 fn try_from(message: proto::Operation) -> Result<Self, Self::Error> {
2406 Ok(
2407 match message
2408 .variant
2409 .ok_or_else(|| anyhow!("missing operation variant"))?
2410 {
2411 proto::operation::Variant::Edit(edit) => Operation::Edit(edit.into()),
2412 proto::operation::Variant::Undo(undo) => Operation::Undo {
2413 lamport_timestamp: clock::Lamport {
2414 replica_id: undo.replica_id as ReplicaId,
2415 value: undo.lamport_timestamp,
2416 },
2417 undo: UndoOperation {
2418 id: clock::Local {
2419 replica_id: undo.replica_id as ReplicaId,
2420 value: undo.local_timestamp,
2421 },
2422 counts: undo
2423 .counts
2424 .into_iter()
2425 .map(|c| {
2426 (
2427 clock::Local {
2428 replica_id: c.replica_id as ReplicaId,
2429 value: c.local_timestamp,
2430 },
2431 c.count,
2432 )
2433 })
2434 .collect(),
2435 ranges: undo
2436 .ranges
2437 .into_iter()
2438 .map(|r| FullOffset::from_proto(r.start)..FullOffset::from_proto(r.end))
2439 .collect(),
2440 version: undo.version.into(),
2441 },
2442 },
2443 proto::operation::Variant::UpdateSelections(message) => {
2444 let version = message.version.into();
2445 let entries = message
2446 .selections
2447 .iter()
2448 .map(|selection| {
2449 let range = (FullOffset::from_proto(selection.start), Bias::Left)
2450 ..(FullOffset::from_proto(selection.end), Bias::Right);
2451 let state = SelectionState {
2452 id: selection.id as usize,
2453 reversed: selection.reversed,
2454 goal: SelectionGoal::None,
2455 };
2456 (range, state)
2457 })
2458 .collect();
2459 let selections = AnchorRangeMap::from_raw(version, entries);
2460
2461 Operation::UpdateSelections {
2462 set_id: clock::Lamport {
2463 replica_id: message.replica_id as ReplicaId,
2464 value: message.local_timestamp,
2465 },
2466 lamport_timestamp: clock::Lamport {
2467 replica_id: message.replica_id as ReplicaId,
2468 value: message.lamport_timestamp,
2469 },
2470 selections: Arc::from(selections),
2471 }
2472 }
2473 proto::operation::Variant::RemoveSelections(message) => {
2474 Operation::RemoveSelections {
2475 set_id: clock::Lamport {
2476 replica_id: message.replica_id as ReplicaId,
2477 value: message.local_timestamp,
2478 },
2479 lamport_timestamp: clock::Lamport {
2480 replica_id: message.replica_id as ReplicaId,
2481 value: message.lamport_timestamp,
2482 },
2483 }
2484 }
2485 proto::operation::Variant::SetActiveSelections(message) => {
2486 Operation::SetActiveSelections {
2487 set_id: message.local_timestamp.map(|value| clock::Lamport {
2488 replica_id: message.replica_id as ReplicaId,
2489 value,
2490 }),
2491 lamport_timestamp: clock::Lamport {
2492 replica_id: message.replica_id as ReplicaId,
2493 value: message.lamport_timestamp,
2494 },
2495 }
2496 }
2497 },
2498 )
2499 }
2500}
2501
2502impl From<proto::operation::Edit> for EditOperation {
2503 fn from(edit: proto::operation::Edit) -> Self {
2504 let ranges = edit
2505 .ranges
2506 .into_iter()
2507 .map(|range| FullOffset::from_proto(range.start)..FullOffset::from_proto(range.end))
2508 .collect();
2509 EditOperation {
2510 timestamp: InsertionTimestamp {
2511 replica_id: edit.replica_id as ReplicaId,
2512 local: edit.local_timestamp,
2513 lamport: edit.lamport_timestamp,
2514 },
2515 version: edit.version.into(),
2516 ranges,
2517 new_text: edit.new_text,
2518 }
2519 }
2520}
2521
2522pub trait ToOffset {
2523 fn to_offset<'a>(&self, content: impl Into<Content<'a>>) -> usize;
2524
2525 fn to_full_offset<'a>(&self, content: impl Into<Content<'a>>, bias: Bias) -> FullOffset {
2526 let content = content.into();
2527 let offset = self.to_offset(&content);
2528 let mut cursor = content.fragments.cursor::<FragmentTextSummary>();
2529 cursor.seek(&offset, bias, &None);
2530 FullOffset(offset + cursor.start().deleted)
2531 }
2532}
2533
2534impl ToOffset for Point {
2535 fn to_offset<'a>(&self, content: impl Into<Content<'a>>) -> usize {
2536 content.into().visible_text.point_to_offset(*self)
2537 }
2538}
2539
2540impl ToOffset for PointUtf16 {
2541 fn to_offset<'a>(&self, content: impl Into<Content<'a>>) -> usize {
2542 content.into().visible_text.point_utf16_to_offset(*self)
2543 }
2544}
2545
2546impl ToOffset for usize {
2547 fn to_offset<'a>(&self, content: impl Into<Content<'a>>) -> usize {
2548 assert!(*self <= content.into().len(), "offset is out of range");
2549 *self
2550 }
2551}
2552
2553impl ToOffset for Anchor {
2554 fn to_offset<'a>(&self, content: impl Into<Content<'a>>) -> usize {
2555 content.into().summary_for_anchor(self).bytes
2556 }
2557}
2558
2559impl<'a> ToOffset for &'a Anchor {
2560 fn to_offset<'b>(&self, content: impl Into<Content<'b>>) -> usize {
2561 content.into().summary_for_anchor(self).bytes
2562 }
2563}
2564
2565pub trait ToPoint {
2566 fn to_point<'a>(&self, content: impl Into<Content<'a>>) -> Point;
2567}
2568
2569impl ToPoint for Anchor {
2570 fn to_point<'a>(&self, content: impl Into<Content<'a>>) -> Point {
2571 content.into().summary_for_anchor(self).lines
2572 }
2573}
2574
2575impl ToPoint for usize {
2576 fn to_point<'a>(&self, content: impl Into<Content<'a>>) -> Point {
2577 content.into().visible_text.offset_to_point(*self)
2578 }
2579}
2580
2581impl ToPoint for Point {
2582 fn to_point<'a>(&self, _: impl Into<Content<'a>>) -> Point {
2583 *self
2584 }
2585}
2586
2587pub trait FromAnchor {
2588 fn from_anchor<'a>(anchor: &Anchor, content: &Content<'a>) -> Self;
2589}
2590
2591impl FromAnchor for Point {
2592 fn from_anchor<'a>(anchor: &Anchor, content: &Content<'a>) -> Self {
2593 anchor.to_point(content)
2594 }
2595}
2596
2597impl FromAnchor for usize {
2598 fn from_anchor<'a>(anchor: &Anchor, content: &Content<'a>) -> Self {
2599 anchor.to_offset(content)
2600 }
2601}