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