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