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)]
387struct Fragment {
388 id: Locator,
389 insertion_timestamp: InsertionTimestamp,
390 insertion_offset: usize,
391 len: usize,
392 visible: bool,
393 deletions: HashSet<clock::Local>,
394 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 version(&self) -> clock::Global {
512 self.version.clone()
513 }
514
515 pub fn snapshot(&self) -> BufferSnapshot {
516 self.snapshot.clone()
517 }
518
519 pub fn replica_id(&self) -> ReplicaId {
520 self.local_clock.replica_id
521 }
522
523 pub fn remote_id(&self) -> u64 {
524 self.remote_id
525 }
526
527 pub fn deferred_ops_len(&self) -> usize {
528 self.deferred_ops.len()
529 }
530
531 pub fn transaction_group_interval(&self) -> Duration {
532 self.history.group_interval
533 }
534
535 pub fn edit<R, I, S, T>(&mut self, ranges: R, new_text: T) -> EditOperation
536 where
537 R: IntoIterator<IntoIter = I>,
538 I: ExactSizeIterator<Item = Range<S>>,
539 S: ToOffset,
540 T: Into<String>,
541 {
542 let new_text = new_text.into();
543 let new_text_len = new_text.len();
544 let new_text = if new_text_len > 0 {
545 Some(new_text)
546 } else {
547 None
548 };
549
550 self.start_transaction();
551 let timestamp = InsertionTimestamp {
552 replica_id: self.replica_id,
553 local: self.local_clock.tick().value,
554 lamport: self.lamport_clock.tick().value,
555 };
556 let edit = self.apply_local_edit(ranges.into_iter(), new_text, timestamp);
557
558 self.history.push(edit.clone());
559 self.history.push_undo(edit.timestamp.local());
560 self.last_edit = edit.timestamp.local();
561 self.snapshot.version.observe(edit.timestamp.local());
562 self.end_transaction();
563 edit
564 }
565
566 fn apply_local_edit<S: ToOffset>(
567 &mut self,
568 ranges: impl ExactSizeIterator<Item = Range<S>>,
569 new_text: Option<String>,
570 timestamp: InsertionTimestamp,
571 ) -> EditOperation {
572 let mut edits = Patch::default();
573 let mut edit_op = EditOperation {
574 timestamp,
575 version: self.version(),
576 ranges: Vec::with_capacity(ranges.len()),
577 new_text: None,
578 };
579 let mut new_insertions = Vec::new();
580 let mut insertion_offset = 0;
581
582 let mut ranges = ranges
583 .map(|range| range.start.to_offset(&*self)..range.end.to_offset(&*self))
584 .peekable();
585
586 let mut new_ropes =
587 RopeBuilder::new(self.visible_text.cursor(0), self.deleted_text.cursor(0));
588 let mut old_fragments = self.fragments.cursor::<FragmentTextSummary>();
589 let mut new_fragments =
590 old_fragments.slice(&ranges.peek().unwrap().start, Bias::Right, &None);
591 new_ropes.push_tree(new_fragments.summary().text);
592
593 let mut fragment_start = old_fragments.start().visible;
594 for range in ranges {
595 let fragment_end = old_fragments.end(&None).visible;
596
597 // If the current fragment ends before this range, then jump ahead to the first fragment
598 // that extends past the start of this range, reusing any intervening fragments.
599 if fragment_end < range.start {
600 // If the current fragment has been partially consumed, then consume the rest of it
601 // and advance to the next fragment before slicing.
602 if fragment_start > old_fragments.start().visible {
603 if fragment_end > fragment_start {
604 let mut suffix = old_fragments.item().unwrap().clone();
605 suffix.len = fragment_end - fragment_start;
606 suffix.insertion_offset += fragment_start - old_fragments.start().visible;
607 new_insertions.push(InsertionFragment::insert_new(&suffix));
608 new_ropes.push_fragment(&suffix, suffix.visible);
609 new_fragments.push(suffix, &None);
610 }
611 old_fragments.next(&None);
612 }
613
614 let slice = old_fragments.slice(&range.start, Bias::Right, &None);
615 new_ropes.push_tree(slice.summary().text);
616 new_fragments.push_tree(slice, &None);
617 fragment_start = old_fragments.start().visible;
618 }
619
620 let full_range_start = FullOffset(range.start + old_fragments.start().deleted);
621
622 // Preserve any portion of the current fragment that precedes this range.
623 if fragment_start < range.start {
624 let mut prefix = old_fragments.item().unwrap().clone();
625 prefix.len = range.start - fragment_start;
626 prefix.insertion_offset += fragment_start - old_fragments.start().visible;
627 prefix.id = Locator::between(&new_fragments.summary().max_id, &prefix.id);
628 new_insertions.push(InsertionFragment::insert_new(&prefix));
629 new_ropes.push_fragment(&prefix, prefix.visible);
630 new_fragments.push(prefix, &None);
631 fragment_start = range.start;
632 }
633
634 // Insert the new text before any existing fragments within the range.
635 if let Some(new_text) = new_text.as_deref() {
636 let new_start = new_fragments.summary().text.visible;
637 edits.push(Edit {
638 old: fragment_start..fragment_start,
639 new: new_start..new_start + new_text.len(),
640 });
641 let fragment = Fragment {
642 id: Locator::between(
643 &new_fragments.summary().max_id,
644 old_fragments
645 .item()
646 .map_or(&Locator::max(), |old_fragment| &old_fragment.id),
647 ),
648 insertion_timestamp: timestamp,
649 insertion_offset,
650 len: new_text.len(),
651 deletions: Default::default(),
652 max_undos: Default::default(),
653 visible: true,
654 };
655 new_insertions.push(InsertionFragment::insert_new(&fragment));
656 new_ropes.push_str(new_text);
657 new_fragments.push(fragment, &None);
658 insertion_offset += new_text.len();
659 }
660
661 // Advance through every fragment that intersects this range, marking the intersecting
662 // portions as deleted.
663 while fragment_start < range.end {
664 let fragment = old_fragments.item().unwrap();
665 let fragment_end = old_fragments.end(&None).visible;
666 let mut intersection = fragment.clone();
667 let intersection_end = cmp::min(range.end, fragment_end);
668 if fragment.visible {
669 intersection.len = intersection_end - fragment_start;
670 intersection.insertion_offset += fragment_start - old_fragments.start().visible;
671 intersection.id =
672 Locator::between(&new_fragments.summary().max_id, &intersection.id);
673 intersection.deletions.insert(timestamp.local());
674 intersection.visible = false;
675 }
676 if intersection.len > 0 {
677 if fragment.visible && !intersection.visible {
678 let new_start = new_fragments.summary().text.visible;
679 edits.push(Edit {
680 old: fragment_start..intersection_end,
681 new: new_start..new_start,
682 });
683 }
684 new_insertions.push(InsertionFragment::insert_new(&intersection));
685 new_ropes.push_fragment(&intersection, fragment.visible);
686 new_fragments.push(intersection, &None);
687 fragment_start = intersection_end;
688 }
689 if fragment_end <= range.end {
690 old_fragments.next(&None);
691 }
692 }
693
694 let full_range_end = FullOffset(range.end + old_fragments.start().deleted);
695 edit_op.ranges.push(full_range_start..full_range_end);
696 }
697
698 // If the current fragment has been partially consumed, then consume the rest of it
699 // and advance to the next fragment before slicing.
700 if fragment_start > old_fragments.start().visible {
701 let fragment_end = old_fragments.end(&None).visible;
702 if fragment_end > fragment_start {
703 let mut suffix = old_fragments.item().unwrap().clone();
704 suffix.len = fragment_end - fragment_start;
705 suffix.insertion_offset += fragment_start - old_fragments.start().visible;
706 new_insertions.push(InsertionFragment::insert_new(&suffix));
707 new_ropes.push_fragment(&suffix, suffix.visible);
708 new_fragments.push(suffix, &None);
709 }
710 old_fragments.next(&None);
711 }
712
713 let suffix = old_fragments.suffix(&None);
714 new_ropes.push_tree(suffix.summary().text);
715 new_fragments.push_tree(suffix, &None);
716 let (visible_text, deleted_text) = new_ropes.finish();
717 drop(old_fragments);
718
719 self.snapshot.fragments = new_fragments;
720 self.snapshot.insertions.edit(new_insertions, &());
721 self.snapshot.visible_text = visible_text;
722 self.snapshot.deleted_text = deleted_text;
723 self.subscriptions.publish_mut(&edits);
724 edit_op.new_text = new_text;
725 edit_op
726 }
727
728 pub fn apply_ops<I: IntoIterator<Item = Operation>>(&mut self, ops: I) -> Result<()> {
729 let mut deferred_ops = Vec::new();
730 for op in ops {
731 if self.can_apply_op(&op) {
732 self.apply_op(op)?;
733 } else {
734 self.deferred_replicas.insert(op.replica_id());
735 deferred_ops.push(op);
736 }
737 }
738 self.deferred_ops.insert(deferred_ops);
739 self.flush_deferred_ops()?;
740 Ok(())
741 }
742
743 fn apply_op(&mut self, op: Operation) -> Result<()> {
744 match op {
745 Operation::Edit(edit) => {
746 if !self.version.observed(edit.timestamp.local()) {
747 self.apply_remote_edit(
748 &edit.version,
749 &edit.ranges,
750 edit.new_text.as_deref(),
751 edit.timestamp,
752 );
753 self.snapshot.version.observe(edit.timestamp.local());
754 self.history.push(edit);
755 }
756 }
757 Operation::Undo {
758 undo,
759 lamport_timestamp,
760 } => {
761 if !self.version.observed(undo.id) {
762 self.apply_undo(&undo)?;
763 self.snapshot.version.observe(undo.id);
764 self.lamport_clock.observe(lamport_timestamp);
765 }
766 }
767 }
768 Ok(())
769 }
770
771 fn apply_remote_edit(
772 &mut self,
773 version: &clock::Global,
774 ranges: &[Range<FullOffset>],
775 new_text: Option<&str>,
776 timestamp: InsertionTimestamp,
777 ) {
778 if ranges.is_empty() {
779 return;
780 }
781
782 let mut edits = Patch::default();
783 let cx = Some(version.clone());
784 let mut new_insertions = Vec::new();
785 let mut insertion_offset = 0;
786 let mut new_ropes =
787 RopeBuilder::new(self.visible_text.cursor(0), self.deleted_text.cursor(0));
788 let mut old_fragments = self.fragments.cursor::<(VersionedFullOffset, usize)>();
789 let mut new_fragments = old_fragments.slice(
790 &VersionedFullOffset::Offset(ranges[0].start),
791 Bias::Left,
792 &cx,
793 );
794 new_ropes.push_tree(new_fragments.summary().text);
795
796 let mut fragment_start = old_fragments.start().0.full_offset();
797 for range in ranges {
798 let fragment_end = old_fragments.end(&cx).0.full_offset();
799
800 // If the current fragment ends before this range, then jump ahead to the first fragment
801 // that extends past the start of this range, reusing any intervening fragments.
802 if fragment_end < range.start {
803 // If the current fragment has been partially consumed, then consume the rest of it
804 // and advance to the next fragment before slicing.
805 if fragment_start > old_fragments.start().0.full_offset() {
806 if fragment_end > fragment_start {
807 let mut suffix = old_fragments.item().unwrap().clone();
808 suffix.len = fragment_end.0 - fragment_start.0;
809 suffix.insertion_offset +=
810 fragment_start - old_fragments.start().0.full_offset();
811 new_insertions.push(InsertionFragment::insert_new(&suffix));
812 new_ropes.push_fragment(&suffix, suffix.visible);
813 new_fragments.push(suffix, &None);
814 }
815 old_fragments.next(&cx);
816 }
817
818 let slice =
819 old_fragments.slice(&VersionedFullOffset::Offset(range.start), Bias::Left, &cx);
820 new_ropes.push_tree(slice.summary().text);
821 new_fragments.push_tree(slice, &None);
822 fragment_start = old_fragments.start().0.full_offset();
823 }
824
825 // If we are at the end of a non-concurrent fragment, advance to the next one.
826 let fragment_end = old_fragments.end(&cx).0.full_offset();
827 if fragment_end == range.start && fragment_end > fragment_start {
828 let mut fragment = old_fragments.item().unwrap().clone();
829 fragment.len = fragment_end.0 - fragment_start.0;
830 fragment.insertion_offset += fragment_start - old_fragments.start().0.full_offset();
831 new_insertions.push(InsertionFragment::insert_new(&fragment));
832 new_ropes.push_fragment(&fragment, fragment.visible);
833 new_fragments.push(fragment, &None);
834 old_fragments.next(&cx);
835 fragment_start = old_fragments.start().0.full_offset();
836 }
837
838 // Skip over insertions that are concurrent to this edit, but have a lower lamport
839 // timestamp.
840 while let Some(fragment) = old_fragments.item() {
841 if fragment_start == range.start
842 && fragment.insertion_timestamp.lamport() > timestamp.lamport()
843 {
844 new_ropes.push_fragment(fragment, fragment.visible);
845 new_fragments.push(fragment.clone(), &None);
846 old_fragments.next(&cx);
847 debug_assert_eq!(fragment_start, range.start);
848 } else {
849 break;
850 }
851 }
852 debug_assert!(fragment_start <= range.start);
853
854 // Preserve any portion of the current fragment that precedes this range.
855 if fragment_start < range.start {
856 let mut prefix = old_fragments.item().unwrap().clone();
857 prefix.len = range.start.0 - fragment_start.0;
858 prefix.insertion_offset += fragment_start - old_fragments.start().0.full_offset();
859 prefix.id = Locator::between(&new_fragments.summary().max_id, &prefix.id);
860 new_insertions.push(InsertionFragment::insert_new(&prefix));
861 fragment_start = range.start;
862 new_ropes.push_fragment(&prefix, prefix.visible);
863 new_fragments.push(prefix, &None);
864 }
865
866 // Insert the new text before any existing fragments within the range.
867 if let Some(new_text) = new_text {
868 let mut old_start = old_fragments.start().1;
869 if old_fragments.item().map_or(false, |f| f.visible) {
870 old_start += fragment_start.0 - old_fragments.start().0.full_offset().0;
871 }
872 let new_start = new_fragments.summary().text.visible;
873 edits.push(Edit {
874 old: old_start..old_start,
875 new: new_start..new_start + new_text.len(),
876 });
877 let fragment = Fragment {
878 id: Locator::between(
879 &new_fragments.summary().max_id,
880 old_fragments
881 .item()
882 .map_or(&Locator::max(), |old_fragment| &old_fragment.id),
883 ),
884 insertion_timestamp: timestamp,
885 insertion_offset,
886 len: new_text.len(),
887 deletions: Default::default(),
888 max_undos: Default::default(),
889 visible: true,
890 };
891 new_insertions.push(InsertionFragment::insert_new(&fragment));
892 new_ropes.push_str(new_text);
893 new_fragments.push(fragment, &None);
894 insertion_offset += new_text.len();
895 }
896
897 // Advance through every fragment that intersects this range, marking the intersecting
898 // portions as deleted.
899 while fragment_start < range.end {
900 let fragment = old_fragments.item().unwrap();
901 let fragment_end = old_fragments.end(&cx).0.full_offset();
902 let mut intersection = fragment.clone();
903 let intersection_end = cmp::min(range.end, fragment_end);
904 if fragment.was_visible(version, &self.undo_map) {
905 intersection.len = intersection_end.0 - fragment_start.0;
906 intersection.insertion_offset +=
907 fragment_start - old_fragments.start().0.full_offset();
908 intersection.id =
909 Locator::between(&new_fragments.summary().max_id, &intersection.id);
910 intersection.deletions.insert(timestamp.local());
911 intersection.visible = false;
912 }
913 if intersection.len > 0 {
914 if fragment.visible && !intersection.visible {
915 let old_start = old_fragments.start().1
916 + (fragment_start.0 - old_fragments.start().0.full_offset().0);
917 let new_start = new_fragments.summary().text.visible;
918 edits.push(Edit {
919 old: old_start..old_start + intersection.len,
920 new: new_start..new_start,
921 });
922 }
923 new_insertions.push(InsertionFragment::insert_new(&intersection));
924 new_ropes.push_fragment(&intersection, fragment.visible);
925 new_fragments.push(intersection, &None);
926 fragment_start = intersection_end;
927 }
928 if fragment_end <= range.end {
929 old_fragments.next(&cx);
930 }
931 }
932 }
933
934 // If the current fragment has been partially consumed, then consume the rest of it
935 // and advance to the next fragment before slicing.
936 if fragment_start > old_fragments.start().0.full_offset() {
937 let fragment_end = old_fragments.end(&cx).0.full_offset();
938 if fragment_end > fragment_start {
939 let mut suffix = old_fragments.item().unwrap().clone();
940 suffix.len = fragment_end.0 - fragment_start.0;
941 suffix.insertion_offset += fragment_start - old_fragments.start().0.full_offset();
942 new_insertions.push(InsertionFragment::insert_new(&suffix));
943 new_ropes.push_fragment(&suffix, suffix.visible);
944 new_fragments.push(suffix, &None);
945 }
946 old_fragments.next(&cx);
947 }
948
949 let suffix = old_fragments.suffix(&cx);
950 new_ropes.push_tree(suffix.summary().text);
951 new_fragments.push_tree(suffix, &None);
952 let (visible_text, deleted_text) = new_ropes.finish();
953 drop(old_fragments);
954
955 self.snapshot.fragments = new_fragments;
956 self.snapshot.visible_text = visible_text;
957 self.snapshot.deleted_text = deleted_text;
958 self.snapshot.insertions.edit(new_insertions, &());
959 self.local_clock.observe(timestamp.local());
960 self.lamport_clock.observe(timestamp.lamport());
961 self.subscriptions.publish_mut(&edits);
962 }
963
964 fn apply_undo(&mut self, undo: &UndoOperation) -> Result<()> {
965 let mut edits = Patch::default();
966 self.snapshot.undo_map.insert(undo);
967
968 let mut cx = undo.version.clone();
969 for edit_id in undo.counts.keys().copied() {
970 cx.observe(edit_id);
971 }
972 let cx = Some(cx);
973
974 let mut old_fragments = self.fragments.cursor::<(VersionedFullOffset, usize)>();
975 let mut new_fragments = old_fragments.slice(
976 &VersionedFullOffset::Offset(undo.ranges[0].start),
977 Bias::Right,
978 &cx,
979 );
980 let mut new_ropes =
981 RopeBuilder::new(self.visible_text.cursor(0), self.deleted_text.cursor(0));
982 new_ropes.push_tree(new_fragments.summary().text);
983
984 for range in &undo.ranges {
985 let mut end_offset = old_fragments.end(&cx).0.full_offset();
986
987 if end_offset < range.start {
988 let preceding_fragments = old_fragments.slice(
989 &VersionedFullOffset::Offset(range.start),
990 Bias::Right,
991 &cx,
992 );
993 new_ropes.push_tree(preceding_fragments.summary().text);
994 new_fragments.push_tree(preceding_fragments, &None);
995 }
996
997 while end_offset <= range.end {
998 if let Some(fragment) = old_fragments.item() {
999 let mut fragment = fragment.clone();
1000 let fragment_was_visible = fragment.visible;
1001
1002 if fragment.was_visible(&undo.version, &self.undo_map)
1003 || undo
1004 .counts
1005 .contains_key(&fragment.insertion_timestamp.local())
1006 {
1007 fragment.visible = fragment.is_visible(&self.undo_map);
1008 fragment.max_undos.observe(undo.id);
1009 }
1010
1011 let old_start = old_fragments.start().1;
1012 let new_start = new_fragments.summary().text.visible;
1013 if fragment_was_visible && !fragment.visible {
1014 edits.push(Edit {
1015 old: old_start..old_start + fragment.len,
1016 new: new_start..new_start,
1017 });
1018 } else if !fragment_was_visible && fragment.visible {
1019 edits.push(Edit {
1020 old: old_start..old_start,
1021 new: new_start..new_start + fragment.len,
1022 });
1023 }
1024 new_ropes.push_fragment(&fragment, fragment_was_visible);
1025 new_fragments.push(fragment, &None);
1026
1027 old_fragments.next(&cx);
1028 if end_offset == old_fragments.end(&cx).0.full_offset() {
1029 let unseen_fragments = old_fragments.slice(
1030 &VersionedFullOffset::Offset(end_offset),
1031 Bias::Right,
1032 &cx,
1033 );
1034 new_ropes.push_tree(unseen_fragments.summary().text);
1035 new_fragments.push_tree(unseen_fragments, &None);
1036 }
1037 end_offset = old_fragments.end(&cx).0.full_offset();
1038 } else {
1039 break;
1040 }
1041 }
1042 }
1043
1044 let suffix = old_fragments.suffix(&cx);
1045 new_ropes.push_tree(suffix.summary().text);
1046 new_fragments.push_tree(suffix, &None);
1047
1048 drop(old_fragments);
1049 let (visible_text, deleted_text) = new_ropes.finish();
1050 self.snapshot.fragments = new_fragments;
1051 self.snapshot.visible_text = visible_text;
1052 self.snapshot.deleted_text = deleted_text;
1053 self.subscriptions.publish_mut(&edits);
1054 Ok(())
1055 }
1056
1057 fn flush_deferred_ops(&mut self) -> Result<()> {
1058 self.deferred_replicas.clear();
1059 let mut deferred_ops = Vec::new();
1060 for op in self.deferred_ops.drain().iter().cloned() {
1061 if self.can_apply_op(&op) {
1062 self.apply_op(op)?;
1063 } else {
1064 self.deferred_replicas.insert(op.replica_id());
1065 deferred_ops.push(op);
1066 }
1067 }
1068 self.deferred_ops.insert(deferred_ops);
1069 Ok(())
1070 }
1071
1072 fn can_apply_op(&self, op: &Operation) -> bool {
1073 if self.deferred_replicas.contains(&op.replica_id()) {
1074 false
1075 } else {
1076 match op {
1077 Operation::Edit(edit) => self.version.ge(&edit.version),
1078 Operation::Undo { undo, .. } => self.version.ge(&undo.version),
1079 }
1080 }
1081 }
1082
1083 pub fn can_resolve(&self, anchor: &Anchor) -> bool {
1084 *anchor == Anchor::min()
1085 || *anchor == Anchor::max()
1086 || self.version.observed(anchor.timestamp)
1087 }
1088
1089 pub fn peek_undo_stack(&self) -> Option<&Transaction> {
1090 self.history.undo_stack.last()
1091 }
1092
1093 pub fn start_transaction(&mut self) -> Option<TransactionId> {
1094 self.start_transaction_at(Instant::now())
1095 }
1096
1097 pub fn start_transaction_at(&mut self, now: Instant) -> Option<TransactionId> {
1098 self.history.start_transaction(self.version.clone(), now)
1099 }
1100
1101 pub fn end_transaction(&mut self) -> Option<(TransactionId, clock::Global)> {
1102 self.end_transaction_at(Instant::now())
1103 }
1104
1105 pub fn end_transaction_at(&mut self, now: Instant) -> Option<(TransactionId, clock::Global)> {
1106 if let Some(transaction) = self.history.end_transaction(now) {
1107 let since = transaction.start.clone();
1108 let id = self.history.group().unwrap();
1109 Some((id, since))
1110 } else {
1111 None
1112 }
1113 }
1114
1115 pub fn base_text(&self) -> &Arc<str> {
1116 &self.history.base_text
1117 }
1118
1119 pub fn history(&self) -> impl Iterator<Item = &EditOperation> {
1120 self.history.ops.values()
1121 }
1122
1123 pub fn undo(&mut self) -> Option<(TransactionId, Operation)> {
1124 if let Some(transaction) = self.history.pop_undo().cloned() {
1125 let transaction_id = transaction.id;
1126 let op = self.undo_or_redo(transaction).unwrap();
1127 Some((transaction_id, op))
1128 } else {
1129 None
1130 }
1131 }
1132
1133 pub fn undo_transaction(&mut self, transaction_id: TransactionId) -> Option<Operation> {
1134 if let Some(transaction) = self.history.remove_from_undo(transaction_id).cloned() {
1135 let op = self.undo_or_redo(transaction).unwrap();
1136 Some(op)
1137 } else {
1138 None
1139 }
1140 }
1141
1142 pub fn redo(&mut self) -> Option<(TransactionId, Operation)> {
1143 if let Some(transaction) = self.history.pop_redo().cloned() {
1144 let transaction_id = transaction.id;
1145 let op = self.undo_or_redo(transaction).unwrap();
1146 Some((transaction_id, op))
1147 } else {
1148 None
1149 }
1150 }
1151
1152 pub fn redo_transaction(&mut self, transaction_id: TransactionId) -> Option<Operation> {
1153 if let Some(transaction) = self.history.remove_from_redo(transaction_id).cloned() {
1154 let op = self.undo_or_redo(transaction).unwrap();
1155 Some(op)
1156 } else {
1157 None
1158 }
1159 }
1160
1161 fn undo_or_redo(&mut self, transaction: Transaction) -> Result<Operation> {
1162 let mut counts = HashMap::default();
1163 for edit_id in transaction.edits {
1164 counts.insert(edit_id, self.undo_map.undo_count(edit_id) + 1);
1165 }
1166
1167 let undo = UndoOperation {
1168 id: self.local_clock.tick(),
1169 counts,
1170 ranges: transaction.ranges,
1171 version: transaction.start.clone(),
1172 };
1173 self.apply_undo(&undo)?;
1174 self.snapshot.version.observe(undo.id);
1175
1176 Ok(Operation::Undo {
1177 undo,
1178 lamport_timestamp: self.lamport_clock.tick(),
1179 })
1180 }
1181
1182 pub fn subscribe(&mut self) -> Subscription {
1183 self.subscriptions.subscribe()
1184 }
1185}
1186
1187#[cfg(any(test, feature = "test-support"))]
1188impl Buffer {
1189 fn random_byte_range(&mut self, start_offset: usize, rng: &mut impl rand::Rng) -> Range<usize> {
1190 let end = self.clip_offset(rng.gen_range(start_offset..=self.len()), Bias::Right);
1191 let start = self.clip_offset(rng.gen_range(start_offset..=end), Bias::Right);
1192 start..end
1193 }
1194
1195 pub fn randomly_edit<T>(
1196 &mut self,
1197 rng: &mut T,
1198 old_range_count: usize,
1199 ) -> (Vec<Range<usize>>, String, Operation)
1200 where
1201 T: rand::Rng,
1202 {
1203 let mut old_ranges: Vec<Range<usize>> = Vec::new();
1204 for _ in 0..old_range_count {
1205 let last_end = old_ranges.last().map_or(0, |last_range| last_range.end + 1);
1206 if last_end > self.len() {
1207 break;
1208 }
1209 old_ranges.push(self.random_byte_range(last_end, rng));
1210 }
1211 let new_text_len = rng.gen_range(0..10);
1212 let new_text: String = crate::random_char_iter::RandomCharIter::new(&mut *rng)
1213 .take(new_text_len)
1214 .collect();
1215 log::info!(
1216 "mutating buffer {} at {:?}: {:?}",
1217 self.replica_id,
1218 old_ranges,
1219 new_text
1220 );
1221 let op = self.edit(old_ranges.iter().cloned(), new_text.as_str());
1222 (old_ranges, new_text, Operation::Edit(op))
1223 }
1224
1225 pub fn randomly_undo_redo(&mut self, rng: &mut impl rand::Rng) -> Vec<Operation> {
1226 use rand::prelude::*;
1227
1228 let mut ops = Vec::new();
1229 for _ in 0..rng.gen_range(1..=5) {
1230 if let Some(transaction) = self.history.undo_stack.choose(rng).cloned() {
1231 log::info!(
1232 "undoing buffer {} transaction {:?}",
1233 self.replica_id,
1234 transaction
1235 );
1236 ops.push(self.undo_or_redo(transaction).unwrap());
1237 }
1238 }
1239 ops
1240 }
1241}
1242
1243impl Deref for Buffer {
1244 type Target = BufferSnapshot;
1245
1246 fn deref(&self) -> &Self::Target {
1247 &self.snapshot
1248 }
1249}
1250
1251impl BufferSnapshot {
1252 pub fn as_rope(&self) -> &Rope {
1253 &self.visible_text
1254 }
1255
1256 pub fn replica_id(&self) -> ReplicaId {
1257 self.replica_id
1258 }
1259
1260 pub fn row_count(&self) -> u32 {
1261 self.max_point().row + 1
1262 }
1263
1264 pub fn len(&self) -> usize {
1265 self.visible_text.len()
1266 }
1267
1268 pub fn chars(&self) -> impl Iterator<Item = char> + '_ {
1269 self.chars_at(0)
1270 }
1271
1272 pub fn chars_for_range<T: ToOffset>(&self, range: Range<T>) -> impl Iterator<Item = char> + '_ {
1273 self.text_for_range(range).flat_map(str::chars)
1274 }
1275
1276 pub fn contains_str_at<T>(&self, position: T, needle: &str) -> bool
1277 where
1278 T: ToOffset,
1279 {
1280 let position = position.to_offset(self);
1281 position == self.clip_offset(position, Bias::Left)
1282 && self
1283 .bytes_in_range(position..self.len())
1284 .flatten()
1285 .copied()
1286 .take(needle.len())
1287 .eq(needle.bytes())
1288 }
1289
1290 pub fn text(&self) -> String {
1291 self.text_for_range(0..self.len()).collect()
1292 }
1293
1294 pub fn text_summary(&self) -> TextSummary {
1295 self.visible_text.summary()
1296 }
1297
1298 pub fn max_point(&self) -> Point {
1299 self.visible_text.max_point()
1300 }
1301
1302 pub fn point_to_offset(&self, point: Point) -> usize {
1303 self.visible_text.point_to_offset(point)
1304 }
1305
1306 pub fn point_utf16_to_offset(&self, point: PointUtf16) -> usize {
1307 self.visible_text.point_utf16_to_offset(point)
1308 }
1309
1310 pub fn point_utf16_to_point(&self, point: PointUtf16) -> Point {
1311 self.visible_text.point_utf16_to_point(point)
1312 }
1313
1314 pub fn offset_to_point(&self, offset: usize) -> Point {
1315 self.visible_text.offset_to_point(offset)
1316 }
1317
1318 pub fn offset_to_point_utf16(&self, offset: usize) -> PointUtf16 {
1319 self.visible_text.offset_to_point_utf16(offset)
1320 }
1321
1322 pub fn version(&self) -> &clock::Global {
1323 &self.version
1324 }
1325
1326 pub fn chars_at<'a, T: ToOffset>(&'a self, position: T) -> impl Iterator<Item = char> + 'a {
1327 let offset = position.to_offset(self);
1328 self.visible_text.chars_at(offset)
1329 }
1330
1331 pub fn reversed_chars_at<'a, T: ToOffset>(
1332 &'a self,
1333 position: T,
1334 ) -> impl Iterator<Item = char> + 'a {
1335 let offset = position.to_offset(self);
1336 self.visible_text.reversed_chars_at(offset)
1337 }
1338
1339 pub fn reversed_chunks_in_range<T: ToOffset>(&self, range: Range<T>) -> rope::Chunks {
1340 let range = range.start.to_offset(self)..range.end.to_offset(self);
1341 self.visible_text.reversed_chunks_in_range(range)
1342 }
1343
1344 pub fn bytes_in_range<'a, T: ToOffset>(&'a self, range: Range<T>) -> rope::Bytes<'a> {
1345 let start = range.start.to_offset(self);
1346 let end = range.end.to_offset(self);
1347 self.visible_text.bytes_in_range(start..end)
1348 }
1349
1350 pub fn text_for_range<'a, T: ToOffset>(&'a self, range: Range<T>) -> Chunks<'a> {
1351 let start = range.start.to_offset(self);
1352 let end = range.end.to_offset(self);
1353 self.visible_text.chunks_in_range(start..end)
1354 }
1355
1356 pub fn line_len(&self, row: u32) -> u32 {
1357 let row_start_offset = Point::new(row, 0).to_offset(self);
1358 let row_end_offset = if row >= self.max_point().row {
1359 self.len()
1360 } else {
1361 Point::new(row + 1, 0).to_offset(self) - 1
1362 };
1363 (row_end_offset - row_start_offset) as u32
1364 }
1365
1366 pub fn is_line_blank(&self, row: u32) -> bool {
1367 self.text_for_range(Point::new(row, 0)..Point::new(row, self.line_len(row)))
1368 .all(|chunk| chunk.matches(|c: char| !c.is_whitespace()).next().is_none())
1369 }
1370
1371 pub fn indent_column_for_line(&self, row: u32) -> u32 {
1372 let mut result = 0;
1373 for c in self.chars_at(Point::new(row, 0)) {
1374 if c == ' ' {
1375 result += 1;
1376 } else {
1377 break;
1378 }
1379 }
1380 result
1381 }
1382
1383 pub fn text_summary_for_range<'a, D, O: ToOffset>(&'a self, range: Range<O>) -> D
1384 where
1385 D: TextDimension,
1386 {
1387 self.visible_text
1388 .cursor(range.start.to_offset(self))
1389 .summary(range.end.to_offset(self))
1390 }
1391
1392 pub fn summaries_for_anchors<'a, D, A>(&'a self, anchors: A) -> impl 'a + Iterator<Item = D>
1393 where
1394 D: 'a + TextDimension,
1395 A: 'a + IntoIterator<Item = &'a Anchor>,
1396 {
1397 let anchors = anchors.into_iter();
1398 let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>();
1399 let mut fragment_cursor = self.fragments.cursor::<(Option<&Locator>, usize)>();
1400 let mut text_cursor = self.visible_text.cursor(0);
1401 let mut position = D::default();
1402
1403 anchors.map(move |anchor| {
1404 if *anchor == Anchor::min() {
1405 return D::default();
1406 } else if *anchor == Anchor::max() {
1407 return D::from_text_summary(&self.visible_text.summary());
1408 }
1409
1410 let anchor_key = InsertionFragmentKey {
1411 timestamp: anchor.timestamp,
1412 split_offset: anchor.offset,
1413 };
1414 insertion_cursor.seek(&anchor_key, anchor.bias, &());
1415 if let Some(insertion) = insertion_cursor.item() {
1416 let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
1417 if comparison == Ordering::Greater
1418 || (anchor.bias == Bias::Left
1419 && comparison == Ordering::Equal
1420 && anchor.offset > 0)
1421 {
1422 insertion_cursor.prev(&());
1423 }
1424 } else {
1425 insertion_cursor.prev(&());
1426 }
1427 let insertion = insertion_cursor.item().expect("invalid insertion");
1428 debug_assert_eq!(insertion.timestamp, anchor.timestamp, "invalid insertion");
1429
1430 fragment_cursor.seek_forward(&Some(&insertion.fragment_id), Bias::Left, &None);
1431 let fragment = fragment_cursor.item().unwrap();
1432 let mut fragment_offset = fragment_cursor.start().1;
1433 if fragment.visible {
1434 fragment_offset += anchor.offset - insertion.split_offset;
1435 }
1436
1437 position.add_assign(&text_cursor.summary(fragment_offset));
1438 position.clone()
1439 })
1440 }
1441
1442 fn summary_for_anchor<'a, D>(&'a self, anchor: &Anchor) -> D
1443 where
1444 D: TextDimension,
1445 {
1446 if *anchor == Anchor::min() {
1447 D::default()
1448 } else if *anchor == Anchor::max() {
1449 D::from_text_summary(&self.visible_text.summary())
1450 } else {
1451 let anchor_key = InsertionFragmentKey {
1452 timestamp: anchor.timestamp,
1453 split_offset: anchor.offset,
1454 };
1455 let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>();
1456 insertion_cursor.seek(&anchor_key, anchor.bias, &());
1457 if let Some(insertion) = insertion_cursor.item() {
1458 let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
1459 if comparison == Ordering::Greater
1460 || (anchor.bias == Bias::Left
1461 && comparison == Ordering::Equal
1462 && anchor.offset > 0)
1463 {
1464 insertion_cursor.prev(&());
1465 }
1466 } else {
1467 insertion_cursor.prev(&());
1468 }
1469 let insertion = insertion_cursor.item().expect("invalid insertion");
1470 debug_assert_eq!(insertion.timestamp, anchor.timestamp, "invalid insertion");
1471
1472 let mut fragment_cursor = self.fragments.cursor::<(Option<&Locator>, usize)>();
1473 fragment_cursor.seek(&Some(&insertion.fragment_id), Bias::Left, &None);
1474 let fragment = fragment_cursor.item().unwrap();
1475 let mut fragment_offset = fragment_cursor.start().1;
1476 if fragment.visible {
1477 fragment_offset += anchor.offset - insertion.split_offset;
1478 }
1479 self.text_summary_for_range(0..fragment_offset)
1480 }
1481 }
1482
1483 fn fragment_id_for_anchor(&self, anchor: &Anchor) -> &Locator {
1484 if *anchor == Anchor::min() {
1485 &locator::MIN
1486 } else if *anchor == Anchor::max() {
1487 &locator::MAX
1488 } else {
1489 let anchor_key = InsertionFragmentKey {
1490 timestamp: anchor.timestamp,
1491 split_offset: anchor.offset,
1492 };
1493 let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>();
1494 insertion_cursor.seek(&anchor_key, anchor.bias, &());
1495 if let Some(insertion) = insertion_cursor.item() {
1496 let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
1497 if comparison == Ordering::Greater
1498 || (anchor.bias == Bias::Left
1499 && comparison == Ordering::Equal
1500 && anchor.offset > 0)
1501 {
1502 insertion_cursor.prev(&());
1503 }
1504 } else {
1505 insertion_cursor.prev(&());
1506 }
1507 let insertion = insertion_cursor.item().expect("invalid insertion");
1508 debug_assert_eq!(insertion.timestamp, anchor.timestamp, "invalid insertion");
1509 &insertion.fragment_id
1510 }
1511 }
1512
1513 pub fn anchor_before<T: ToOffset>(&self, position: T) -> Anchor {
1514 self.anchor_at(position, Bias::Left)
1515 }
1516
1517 pub fn anchor_after<T: ToOffset>(&self, position: T) -> Anchor {
1518 self.anchor_at(position, Bias::Right)
1519 }
1520
1521 pub fn anchor_at<T: ToOffset>(&self, position: T, bias: Bias) -> Anchor {
1522 let offset = position.to_offset(self);
1523 if bias == Bias::Left && offset == 0 {
1524 Anchor::min()
1525 } else if bias == Bias::Right && offset == self.len() {
1526 Anchor::max()
1527 } else {
1528 let mut fragment_cursor = self.fragments.cursor::<usize>();
1529 fragment_cursor.seek(&offset, bias, &None);
1530 let fragment = fragment_cursor.item().unwrap();
1531 let overshoot = offset - *fragment_cursor.start();
1532 Anchor {
1533 timestamp: fragment.insertion_timestamp.local(),
1534 offset: fragment.insertion_offset + overshoot,
1535 bias,
1536 }
1537 }
1538 }
1539
1540 pub fn clip_offset(&self, offset: usize, bias: Bias) -> usize {
1541 self.visible_text.clip_offset(offset, bias)
1542 }
1543
1544 pub fn clip_point(&self, point: Point, bias: Bias) -> Point {
1545 self.visible_text.clip_point(point, bias)
1546 }
1547
1548 pub fn clip_point_utf16(&self, point: PointUtf16, bias: Bias) -> PointUtf16 {
1549 self.visible_text.clip_point_utf16(point, bias)
1550 }
1551
1552 // pub fn point_for_offset(&self, offset: usize) -> Result<Point> {
1553 // if offset <= self.len() {
1554 // Ok(self.text_summary_for_range(0..offset))
1555 // } else {
1556 // Err(anyhow!("offset out of bounds"))
1557 // }
1558 // }
1559
1560 pub fn edits_since<'a, D>(
1561 &'a self,
1562 since: &'a clock::Global,
1563 ) -> impl 'a + Iterator<Item = Edit<D>>
1564 where
1565 D: TextDimension + Ord,
1566 {
1567 self.edits_since_in_range(since, Anchor::min()..Anchor::max())
1568 }
1569
1570 pub fn edits_since_in_range<'a, D>(
1571 &'a self,
1572 since: &'a clock::Global,
1573 range: Range<Anchor>,
1574 ) -> impl 'a + Iterator<Item = Edit<D>>
1575 where
1576 D: TextDimension + Ord,
1577 {
1578 let fragments_cursor = if *since == self.version {
1579 None
1580 } else {
1581 Some(
1582 self.fragments
1583 .filter(move |summary| !since.ge(&summary.max_version), &None),
1584 )
1585 };
1586 let mut cursor = self
1587 .fragments
1588 .cursor::<(Option<&Locator>, FragmentTextSummary)>();
1589
1590 let start_fragment_id = self.fragment_id_for_anchor(&range.start);
1591 cursor.seek(&Some(start_fragment_id), Bias::Left, &None);
1592 let mut visible_start = cursor.start().1.visible;
1593 let mut deleted_start = cursor.start().1.deleted;
1594 if let Some(fragment) = cursor.item() {
1595 let overshoot = range.start.offset - fragment.insertion_offset;
1596 if fragment.visible {
1597 visible_start += overshoot;
1598 } else {
1599 deleted_start += overshoot;
1600 }
1601 }
1602 let end_fragment_id = self.fragment_id_for_anchor(&range.end);
1603
1604 Edits {
1605 visible_cursor: self.visible_text.cursor(visible_start),
1606 deleted_cursor: self.deleted_text.cursor(deleted_start),
1607 fragments_cursor,
1608 undos: &self.undo_map,
1609 since,
1610 old_end: Default::default(),
1611 new_end: Default::default(),
1612 range: (start_fragment_id, range.start.offset)..(end_fragment_id, range.end.offset),
1613 }
1614 }
1615}
1616
1617struct RopeBuilder<'a> {
1618 old_visible_cursor: rope::Cursor<'a>,
1619 old_deleted_cursor: rope::Cursor<'a>,
1620 new_visible: Rope,
1621 new_deleted: Rope,
1622}
1623
1624impl<'a> RopeBuilder<'a> {
1625 fn new(old_visible_cursor: rope::Cursor<'a>, old_deleted_cursor: rope::Cursor<'a>) -> Self {
1626 Self {
1627 old_visible_cursor,
1628 old_deleted_cursor,
1629 new_visible: Rope::new(),
1630 new_deleted: Rope::new(),
1631 }
1632 }
1633
1634 fn push_tree(&mut self, len: FragmentTextSummary) {
1635 self.push(len.visible, true, true);
1636 self.push(len.deleted, false, false);
1637 }
1638
1639 fn push_fragment(&mut self, fragment: &Fragment, was_visible: bool) {
1640 debug_assert!(fragment.len > 0);
1641 self.push(fragment.len, was_visible, fragment.visible)
1642 }
1643
1644 fn push(&mut self, len: usize, was_visible: bool, is_visible: bool) {
1645 let text = if was_visible {
1646 self.old_visible_cursor
1647 .slice(self.old_visible_cursor.offset() + len)
1648 } else {
1649 self.old_deleted_cursor
1650 .slice(self.old_deleted_cursor.offset() + len)
1651 };
1652 if is_visible {
1653 self.new_visible.append(text);
1654 } else {
1655 self.new_deleted.append(text);
1656 }
1657 }
1658
1659 fn push_str(&mut self, text: &str) {
1660 self.new_visible.push(text);
1661 }
1662
1663 fn finish(mut self) -> (Rope, Rope) {
1664 self.new_visible.append(self.old_visible_cursor.suffix());
1665 self.new_deleted.append(self.old_deleted_cursor.suffix());
1666 (self.new_visible, self.new_deleted)
1667 }
1668}
1669
1670impl<'a, D: TextDimension + Ord, F: FnMut(&FragmentSummary) -> bool> Iterator for Edits<'a, D, F> {
1671 type Item = Edit<D>;
1672
1673 fn next(&mut self) -> Option<Self::Item> {
1674 let mut pending_edit: Option<Edit<D>> = None;
1675 let cursor = self.fragments_cursor.as_mut()?;
1676
1677 while let Some(fragment) = cursor.item() {
1678 if fragment.id < *self.range.start.0 {
1679 cursor.next(&None);
1680 continue;
1681 } else if fragment.id > *self.range.end.0 {
1682 break;
1683 }
1684
1685 if cursor.start().visible > self.visible_cursor.offset() {
1686 let summary = self.visible_cursor.summary(cursor.start().visible);
1687 self.old_end.add_assign(&summary);
1688 self.new_end.add_assign(&summary);
1689 }
1690
1691 if pending_edit
1692 .as_ref()
1693 .map_or(false, |change| change.new.end < self.new_end)
1694 {
1695 break;
1696 }
1697
1698 if !fragment.was_visible(&self.since, &self.undos) && fragment.visible {
1699 let mut visible_end = cursor.end(&None).visible;
1700 if fragment.id == *self.range.end.0 {
1701 visible_end = cmp::min(
1702 visible_end,
1703 cursor.start().visible + (self.range.end.1 - fragment.insertion_offset),
1704 );
1705 }
1706
1707 let fragment_summary = self.visible_cursor.summary(visible_end);
1708 let mut new_end = self.new_end.clone();
1709 new_end.add_assign(&fragment_summary);
1710 if let Some(pending_edit) = pending_edit.as_mut() {
1711 pending_edit.new.end = new_end.clone();
1712 } else {
1713 pending_edit = Some(Edit {
1714 old: self.old_end.clone()..self.old_end.clone(),
1715 new: self.new_end.clone()..new_end.clone(),
1716 });
1717 }
1718
1719 self.new_end = new_end;
1720 } else if fragment.was_visible(&self.since, &self.undos) && !fragment.visible {
1721 let mut deleted_end = cursor.end(&None).deleted;
1722 if fragment.id == *self.range.end.0 {
1723 deleted_end = cmp::min(
1724 deleted_end,
1725 cursor.start().deleted + (self.range.end.1 - fragment.insertion_offset),
1726 );
1727 }
1728
1729 if cursor.start().deleted > self.deleted_cursor.offset() {
1730 self.deleted_cursor.seek_forward(cursor.start().deleted);
1731 }
1732 let fragment_summary = self.deleted_cursor.summary(deleted_end);
1733 let mut old_end = self.old_end.clone();
1734 old_end.add_assign(&fragment_summary);
1735 if let Some(pending_edit) = pending_edit.as_mut() {
1736 pending_edit.old.end = old_end.clone();
1737 } else {
1738 pending_edit = Some(Edit {
1739 old: self.old_end.clone()..old_end.clone(),
1740 new: self.new_end.clone()..self.new_end.clone(),
1741 });
1742 }
1743
1744 self.old_end = old_end;
1745 }
1746
1747 cursor.next(&None);
1748 }
1749
1750 pending_edit
1751 }
1752}
1753
1754impl Fragment {
1755 fn is_visible(&self, undos: &UndoMap) -> bool {
1756 !undos.is_undone(self.insertion_timestamp.local())
1757 && self.deletions.iter().all(|d| undos.is_undone(*d))
1758 }
1759
1760 fn was_visible(&self, version: &clock::Global, undos: &UndoMap) -> bool {
1761 (version.observed(self.insertion_timestamp.local())
1762 && !undos.was_undone(self.insertion_timestamp.local(), version))
1763 && self
1764 .deletions
1765 .iter()
1766 .all(|d| !version.observed(*d) || undos.was_undone(*d, version))
1767 }
1768}
1769
1770impl sum_tree::Item for Fragment {
1771 type Summary = FragmentSummary;
1772
1773 fn summary(&self) -> Self::Summary {
1774 let mut max_version = clock::Global::new();
1775 max_version.observe(self.insertion_timestamp.local());
1776 for deletion in &self.deletions {
1777 max_version.observe(*deletion);
1778 }
1779 max_version.join(&self.max_undos);
1780
1781 let mut min_insertion_version = clock::Global::new();
1782 min_insertion_version.observe(self.insertion_timestamp.local());
1783 let max_insertion_version = min_insertion_version.clone();
1784 if self.visible {
1785 FragmentSummary {
1786 max_id: self.id.clone(),
1787 text: FragmentTextSummary {
1788 visible: self.len,
1789 deleted: 0,
1790 },
1791 max_version,
1792 min_insertion_version,
1793 max_insertion_version,
1794 }
1795 } else {
1796 FragmentSummary {
1797 max_id: self.id.clone(),
1798 text: FragmentTextSummary {
1799 visible: 0,
1800 deleted: self.len,
1801 },
1802 max_version,
1803 min_insertion_version,
1804 max_insertion_version,
1805 }
1806 }
1807 }
1808}
1809
1810impl sum_tree::Summary for FragmentSummary {
1811 type Context = Option<clock::Global>;
1812
1813 fn add_summary(&mut self, other: &Self, _: &Self::Context) {
1814 self.max_id.assign(&other.max_id);
1815 self.text.visible += &other.text.visible;
1816 self.text.deleted += &other.text.deleted;
1817 self.max_version.join(&other.max_version);
1818 self.min_insertion_version
1819 .meet(&other.min_insertion_version);
1820 self.max_insertion_version
1821 .join(&other.max_insertion_version);
1822 }
1823}
1824
1825impl Default for FragmentSummary {
1826 fn default() -> Self {
1827 FragmentSummary {
1828 max_id: Locator::min(),
1829 text: FragmentTextSummary::default(),
1830 max_version: clock::Global::new(),
1831 min_insertion_version: clock::Global::new(),
1832 max_insertion_version: clock::Global::new(),
1833 }
1834 }
1835}
1836
1837impl sum_tree::Item for InsertionFragment {
1838 type Summary = InsertionFragmentKey;
1839
1840 fn summary(&self) -> Self::Summary {
1841 InsertionFragmentKey {
1842 timestamp: self.timestamp,
1843 split_offset: self.split_offset,
1844 }
1845 }
1846}
1847
1848impl sum_tree::KeyedItem for InsertionFragment {
1849 type Key = InsertionFragmentKey;
1850
1851 fn key(&self) -> Self::Key {
1852 sum_tree::Item::summary(self)
1853 }
1854}
1855
1856impl InsertionFragment {
1857 fn new(fragment: &Fragment) -> Self {
1858 Self {
1859 timestamp: fragment.insertion_timestamp.local(),
1860 split_offset: fragment.insertion_offset,
1861 fragment_id: fragment.id.clone(),
1862 }
1863 }
1864
1865 fn insert_new(fragment: &Fragment) -> sum_tree::Edit<Self> {
1866 sum_tree::Edit::Insert(Self::new(fragment))
1867 }
1868}
1869
1870impl sum_tree::Summary for InsertionFragmentKey {
1871 type Context = ();
1872
1873 fn add_summary(&mut self, summary: &Self, _: &()) {
1874 *self = *summary;
1875 }
1876}
1877
1878#[derive(Copy, Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
1879pub struct FullOffset(pub usize);
1880
1881impl ops::AddAssign<usize> for FullOffset {
1882 fn add_assign(&mut self, rhs: usize) {
1883 self.0 += rhs;
1884 }
1885}
1886
1887impl ops::Add<usize> for FullOffset {
1888 type Output = Self;
1889
1890 fn add(mut self, rhs: usize) -> Self::Output {
1891 self += rhs;
1892 self
1893 }
1894}
1895
1896impl ops::Sub for FullOffset {
1897 type Output = usize;
1898
1899 fn sub(self, rhs: Self) -> Self::Output {
1900 self.0 - rhs.0
1901 }
1902}
1903
1904impl<'a> sum_tree::Dimension<'a, FragmentSummary> for usize {
1905 fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
1906 *self += summary.text.visible;
1907 }
1908}
1909
1910impl<'a> sum_tree::Dimension<'a, FragmentSummary> for FullOffset {
1911 fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
1912 self.0 += summary.text.visible + summary.text.deleted;
1913 }
1914}
1915
1916impl<'a> sum_tree::Dimension<'a, FragmentSummary> for Option<&'a Locator> {
1917 fn add_summary(&mut self, summary: &'a FragmentSummary, _: &Option<clock::Global>) {
1918 *self = Some(&summary.max_id);
1919 }
1920}
1921
1922impl<'a> sum_tree::SeekTarget<'a, FragmentSummary, FragmentTextSummary> for usize {
1923 fn cmp(
1924 &self,
1925 cursor_location: &FragmentTextSummary,
1926 _: &Option<clock::Global>,
1927 ) -> cmp::Ordering {
1928 Ord::cmp(self, &cursor_location.visible)
1929 }
1930}
1931
1932#[derive(Copy, Clone, Debug, Eq, PartialEq)]
1933enum VersionedFullOffset {
1934 Offset(FullOffset),
1935 Invalid,
1936}
1937
1938impl VersionedFullOffset {
1939 fn full_offset(&self) -> FullOffset {
1940 if let Self::Offset(position) = self {
1941 *position
1942 } else {
1943 panic!("invalid version")
1944 }
1945 }
1946}
1947
1948impl Default for VersionedFullOffset {
1949 fn default() -> Self {
1950 Self::Offset(Default::default())
1951 }
1952}
1953
1954impl<'a> sum_tree::Dimension<'a, FragmentSummary> for VersionedFullOffset {
1955 fn add_summary(&mut self, summary: &'a FragmentSummary, cx: &Option<clock::Global>) {
1956 if let Self::Offset(offset) = self {
1957 let version = cx.as_ref().unwrap();
1958 if version.ge(&summary.max_insertion_version) {
1959 *offset += summary.text.visible + summary.text.deleted;
1960 } else if version.observed_any(&summary.min_insertion_version) {
1961 *self = Self::Invalid;
1962 }
1963 }
1964 }
1965}
1966
1967impl<'a> sum_tree::SeekTarget<'a, FragmentSummary, Self> for VersionedFullOffset {
1968 fn cmp(&self, cursor_position: &Self, _: &Option<clock::Global>) -> cmp::Ordering {
1969 match (self, cursor_position) {
1970 (Self::Offset(a), Self::Offset(b)) => Ord::cmp(a, b),
1971 (Self::Offset(_), Self::Invalid) => cmp::Ordering::Less,
1972 (Self::Invalid, _) => unreachable!(),
1973 }
1974 }
1975}
1976
1977impl Operation {
1978 fn replica_id(&self) -> ReplicaId {
1979 operation_queue::Operation::lamport_timestamp(self).replica_id
1980 }
1981
1982 pub fn is_edit(&self) -> bool {
1983 match self {
1984 Operation::Edit { .. } => true,
1985 _ => false,
1986 }
1987 }
1988}
1989
1990impl operation_queue::Operation for Operation {
1991 fn lamport_timestamp(&self) -> clock::Lamport {
1992 match self {
1993 Operation::Edit(edit) => edit.timestamp.lamport(),
1994 Operation::Undo {
1995 lamport_timestamp, ..
1996 } => *lamport_timestamp,
1997 }
1998 }
1999}
2000
2001pub trait ToOffset {
2002 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize;
2003}
2004
2005impl ToOffset for Point {
2006 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2007 snapshot.point_to_offset(*self)
2008 }
2009}
2010
2011impl ToOffset for PointUtf16 {
2012 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2013 snapshot.point_utf16_to_offset(*self)
2014 }
2015}
2016
2017impl ToOffset for usize {
2018 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2019 assert!(*self <= snapshot.len(), "offset is out of range");
2020 *self
2021 }
2022}
2023
2024impl ToOffset for Anchor {
2025 fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2026 snapshot.summary_for_anchor(self)
2027 }
2028}
2029
2030impl<'a, T: ToOffset> ToOffset for &'a T {
2031 fn to_offset(&self, content: &BufferSnapshot) -> usize {
2032 (*self).to_offset(content)
2033 }
2034}
2035
2036pub trait ToPoint {
2037 fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point;
2038}
2039
2040impl ToPoint for Anchor {
2041 fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point {
2042 snapshot.summary_for_anchor(self)
2043 }
2044}
2045
2046impl ToPoint for usize {
2047 fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point {
2048 snapshot.offset_to_point(*self)
2049 }
2050}
2051
2052impl ToPoint for PointUtf16 {
2053 fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point {
2054 snapshot.point_utf16_to_point(*self)
2055 }
2056}
2057
2058impl ToPoint for Point {
2059 fn to_point<'a>(&self, _: &BufferSnapshot) -> Point {
2060 *self
2061 }
2062}
2063
2064pub trait Clip {
2065 fn clip(&self, bias: Bias, snapshot: &BufferSnapshot) -> Self;
2066}
2067
2068impl Clip for usize {
2069 fn clip(&self, bias: Bias, snapshot: &BufferSnapshot) -> Self {
2070 snapshot.clip_offset(*self, bias)
2071 }
2072}
2073
2074impl Clip for Point {
2075 fn clip(&self, bias: Bias, snapshot: &BufferSnapshot) -> Self {
2076 snapshot.clip_point(*self, bias)
2077 }
2078}
2079
2080impl Clip for PointUtf16 {
2081 fn clip(&self, bias: Bias, snapshot: &BufferSnapshot) -> Self {
2082 snapshot.clip_point_utf16(*self, bias)
2083 }
2084}
2085
2086pub trait FromAnchor {
2087 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self;
2088}
2089
2090impl FromAnchor for Point {
2091 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
2092 snapshot.summary_for_anchor(anchor)
2093 }
2094}
2095
2096impl FromAnchor for PointUtf16 {
2097 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
2098 snapshot.summary_for_anchor(anchor)
2099 }
2100}
2101
2102impl FromAnchor for usize {
2103 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
2104 snapshot.summary_for_anchor(anchor)
2105 }
2106}