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