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