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