1mod anchor;
2pub mod locator;
3#[cfg(any(test, feature = "test-support"))]
4pub mod network;
5pub mod operation_queue;
6mod patch;
7mod selection;
8pub mod subscription;
9#[cfg(test)]
10mod tests;
11mod undo_map;
12
13pub use anchor::*;
14use anyhow::{Context as _, Result};
15use clock::Lamport;
16pub use clock::ReplicaId;
17use collections::{HashMap, HashSet};
18use locator::Locator;
19use operation_queue::OperationQueue;
20pub use patch::Patch;
21use postage::{oneshot, prelude::*};
22
23use regex::Regex;
24pub use rope::*;
25pub use selection::*;
26use std::{
27 borrow::Cow,
28 cmp::{self, Ordering, Reverse},
29 fmt::Display,
30 future::Future,
31 iter::Iterator,
32 num::NonZeroU64,
33 ops::{self, Deref, Range, Sub},
34 str,
35 sync::{Arc, LazyLock},
36 time::{Duration, Instant},
37};
38pub use subscription::*;
39pub use sum_tree::Bias;
40use sum_tree::{Dimensions, FilterCursor, SumTree, TreeMap, TreeSet};
41use undo_map::UndoMap;
42
43#[cfg(any(test, feature = "test-support"))]
44use util::RandomCharIter;
45
46static LINE_SEPARATORS_REGEX: LazyLock<Regex> =
47 LazyLock::new(|| Regex::new(r"\r\n|\r").expect("Failed to create LINE_SEPARATORS_REGEX"));
48
49pub type TransactionId = clock::Lamport;
50
51pub struct Buffer {
52 snapshot: BufferSnapshot,
53 history: History,
54 deferred_ops: OperationQueue<Operation>,
55 deferred_replicas: HashSet<ReplicaId>,
56 pub lamport_clock: clock::Lamport,
57 subscriptions: Topic<usize>,
58 edit_id_resolvers: HashMap<clock::Lamport, Vec<oneshot::Sender<()>>>,
59 wait_for_version_txs: Vec<(clock::Global, oneshot::Sender<()>)>,
60}
61
62#[repr(transparent)]
63#[derive(Clone, Copy, Debug, Hash, PartialEq, PartialOrd, Ord, Eq)]
64pub struct BufferId(NonZeroU64);
65
66impl Display for BufferId {
67 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
68 write!(f, "{}", self.0)
69 }
70}
71
72impl From<NonZeroU64> for BufferId {
73 fn from(id: NonZeroU64) -> Self {
74 BufferId(id)
75 }
76}
77
78impl BufferId {
79 /// Returns Err if `id` is outside of BufferId domain.
80 pub fn new(id: u64) -> anyhow::Result<Self> {
81 let id = NonZeroU64::new(id).context("Buffer id cannot be 0.")?;
82 Ok(Self(id))
83 }
84
85 /// Increments this buffer id, returning the old value.
86 /// So that's a post-increment operator in disguise.
87 pub fn next(&mut self) -> Self {
88 let old = *self;
89 self.0 = self.0.saturating_add(1);
90 old
91 }
92
93 pub fn to_proto(self) -> u64 {
94 self.into()
95 }
96}
97
98impl From<BufferId> for u64 {
99 fn from(id: BufferId) -> Self {
100 id.0.get()
101 }
102}
103
104#[derive(Clone)]
105pub struct BufferSnapshot {
106 replica_id: ReplicaId,
107 remote_id: BufferId,
108 visible_text: Rope,
109 deleted_text: Rope,
110 line_ending: LineEnding,
111 undo_map: UndoMap,
112 fragments: SumTree<Fragment>,
113 insertions: SumTree<InsertionFragment>,
114 insertion_slices: TreeSet<InsertionSlice>,
115 pub version: clock::Global,
116}
117
118#[derive(Clone, Debug)]
119pub struct HistoryEntry {
120 transaction: Transaction,
121 first_edit_at: Instant,
122 last_edit_at: Instant,
123 suppress_grouping: bool,
124}
125
126#[derive(Clone, Debug)]
127pub struct Transaction {
128 pub id: TransactionId,
129 pub edit_ids: Vec<clock::Lamport>,
130 pub start: clock::Global,
131}
132
133impl Transaction {
134 pub fn merge_in(&mut self, other: Transaction) {
135 self.edit_ids.extend(other.edit_ids);
136 }
137}
138
139impl HistoryEntry {
140 pub fn transaction_id(&self) -> TransactionId {
141 self.transaction.id
142 }
143}
144
145struct History {
146 base_text: Rope,
147 operations: TreeMap<clock::Lamport, Operation>,
148 undo_stack: Vec<HistoryEntry>,
149 redo_stack: Vec<HistoryEntry>,
150 transaction_depth: usize,
151 group_interval: Duration,
152}
153
154#[derive(Clone, Debug, Eq, PartialEq)]
155struct InsertionSlice {
156 edit_id: clock::Lamport,
157 insertion_id: clock::Lamport,
158 range: Range<usize>,
159}
160
161impl Ord for InsertionSlice {
162 fn cmp(&self, other: &Self) -> Ordering {
163 self.edit_id
164 .cmp(&other.edit_id)
165 .then_with(|| self.insertion_id.cmp(&other.insertion_id))
166 .then_with(|| self.range.start.cmp(&other.range.start))
167 .then_with(|| self.range.end.cmp(&other.range.end))
168 }
169}
170
171impl PartialOrd for InsertionSlice {
172 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
173 Some(self.cmp(other))
174 }
175}
176
177impl InsertionSlice {
178 fn from_fragment(edit_id: clock::Lamport, fragment: &Fragment) -> Self {
179 Self {
180 edit_id,
181 insertion_id: fragment.timestamp,
182 range: fragment.insertion_offset..fragment.insertion_offset + fragment.len,
183 }
184 }
185}
186
187impl History {
188 pub fn new(base_text: Rope) -> Self {
189 Self {
190 base_text,
191 operations: Default::default(),
192 undo_stack: Vec::new(),
193 redo_stack: Vec::new(),
194 transaction_depth: 0,
195 // Don't group transactions in tests unless we opt in, because it's a footgun.
196 #[cfg(any(test, feature = "test-support"))]
197 group_interval: Duration::ZERO,
198 #[cfg(not(any(test, feature = "test-support")))]
199 group_interval: Duration::from_millis(300),
200 }
201 }
202
203 fn push(&mut self, op: Operation) {
204 self.operations.insert(op.timestamp(), op);
205 }
206
207 fn start_transaction(
208 &mut self,
209 start: clock::Global,
210 now: Instant,
211 clock: &mut clock::Lamport,
212 ) -> Option<TransactionId> {
213 self.transaction_depth += 1;
214 if self.transaction_depth == 1 {
215 let id = clock.tick();
216 self.undo_stack.push(HistoryEntry {
217 transaction: Transaction {
218 id,
219 start,
220 edit_ids: Default::default(),
221 },
222 first_edit_at: now,
223 last_edit_at: now,
224 suppress_grouping: false,
225 });
226 Some(id)
227 } else {
228 None
229 }
230 }
231
232 fn end_transaction(&mut self, now: Instant) -> Option<&HistoryEntry> {
233 assert_ne!(self.transaction_depth, 0);
234 self.transaction_depth -= 1;
235 if self.transaction_depth == 0 {
236 if self
237 .undo_stack
238 .last()
239 .unwrap()
240 .transaction
241 .edit_ids
242 .is_empty()
243 {
244 self.undo_stack.pop();
245 None
246 } else {
247 self.redo_stack.clear();
248 let entry = self.undo_stack.last_mut().unwrap();
249 entry.last_edit_at = now;
250 Some(entry)
251 }
252 } else {
253 None
254 }
255 }
256
257 fn group(&mut self) -> Option<TransactionId> {
258 let mut count = 0;
259 let mut entries = self.undo_stack.iter();
260 if let Some(mut entry) = entries.next_back() {
261 while let Some(prev_entry) = entries.next_back() {
262 if !prev_entry.suppress_grouping
263 && entry.first_edit_at - prev_entry.last_edit_at < self.group_interval
264 {
265 entry = prev_entry;
266 count += 1;
267 } else {
268 break;
269 }
270 }
271 }
272 self.group_trailing(count)
273 }
274
275 fn group_until(&mut self, transaction_id: TransactionId) {
276 let mut count = 0;
277 for entry in self.undo_stack.iter().rev() {
278 if entry.transaction_id() == transaction_id {
279 self.group_trailing(count);
280 break;
281 } else if entry.suppress_grouping {
282 break;
283 } else {
284 count += 1;
285 }
286 }
287 }
288
289 fn group_trailing(&mut self, n: usize) -> Option<TransactionId> {
290 let new_len = self.undo_stack.len() - n;
291 let (entries_to_keep, entries_to_merge) = self.undo_stack.split_at_mut(new_len);
292 if let Some(last_entry) = entries_to_keep.last_mut() {
293 for entry in &*entries_to_merge {
294 for edit_id in &entry.transaction.edit_ids {
295 last_entry.transaction.edit_ids.push(*edit_id);
296 }
297 }
298
299 if let Some(entry) = entries_to_merge.last_mut() {
300 last_entry.last_edit_at = entry.last_edit_at;
301 }
302 }
303
304 self.undo_stack.truncate(new_len);
305 self.undo_stack.last().map(|e| e.transaction.id)
306 }
307
308 fn finalize_last_transaction(&mut self) -> Option<&Transaction> {
309 self.undo_stack.last_mut().map(|entry| {
310 entry.suppress_grouping = true;
311 &entry.transaction
312 })
313 }
314
315 fn push_transaction(&mut self, transaction: Transaction, now: Instant) {
316 assert_eq!(self.transaction_depth, 0);
317 self.undo_stack.push(HistoryEntry {
318 transaction,
319 first_edit_at: now,
320 last_edit_at: now,
321 suppress_grouping: false,
322 });
323 }
324
325 /// Differs from `push_transaction` in that it does not clear the redo
326 /// stack. Intended to be used to create a parent transaction to merge
327 /// potential child transactions into.
328 ///
329 /// The caller is responsible for removing it from the undo history using
330 /// `forget_transaction` if no edits are merged into it. Otherwise, if edits
331 /// are merged into this transaction, the caller is responsible for ensuring
332 /// the redo stack is cleared. The easiest way to ensure the redo stack is
333 /// cleared is to create transactions with the usual `start_transaction` and
334 /// `end_transaction` methods and merging the resulting transactions into
335 /// the transaction created by this method
336 fn push_empty_transaction(
337 &mut self,
338 start: clock::Global,
339 now: Instant,
340 clock: &mut clock::Lamport,
341 ) -> TransactionId {
342 assert_eq!(self.transaction_depth, 0);
343 let id = clock.tick();
344 let transaction = Transaction {
345 id,
346 start,
347 edit_ids: Vec::new(),
348 };
349 self.undo_stack.push(HistoryEntry {
350 transaction,
351 first_edit_at: now,
352 last_edit_at: now,
353 suppress_grouping: false,
354 });
355 id
356 }
357
358 fn push_undo(&mut self, op_id: clock::Lamport) {
359 assert_ne!(self.transaction_depth, 0);
360 if let Some(Operation::Edit(_)) = self.operations.get(&op_id) {
361 let last_transaction = self.undo_stack.last_mut().unwrap();
362 last_transaction.transaction.edit_ids.push(op_id);
363 }
364 }
365
366 fn pop_undo(&mut self) -> Option<&HistoryEntry> {
367 assert_eq!(self.transaction_depth, 0);
368 if let Some(entry) = self.undo_stack.pop() {
369 self.redo_stack.push(entry);
370 self.redo_stack.last()
371 } else {
372 None
373 }
374 }
375
376 fn remove_from_undo(&mut self, transaction_id: TransactionId) -> Option<&HistoryEntry> {
377 assert_eq!(self.transaction_depth, 0);
378
379 let entry_ix = self
380 .undo_stack
381 .iter()
382 .rposition(|entry| entry.transaction.id == transaction_id)?;
383 let entry = self.undo_stack.remove(entry_ix);
384 self.redo_stack.push(entry);
385 self.redo_stack.last()
386 }
387
388 fn remove_from_undo_until(&mut self, transaction_id: TransactionId) -> &[HistoryEntry] {
389 assert_eq!(self.transaction_depth, 0);
390
391 let redo_stack_start_len = self.redo_stack.len();
392 if let Some(entry_ix) = self
393 .undo_stack
394 .iter()
395 .rposition(|entry| entry.transaction.id == transaction_id)
396 {
397 self.redo_stack
398 .extend(self.undo_stack.drain(entry_ix..).rev());
399 }
400 &self.redo_stack[redo_stack_start_len..]
401 }
402
403 fn forget(&mut self, transaction_id: TransactionId) -> Option<Transaction> {
404 assert_eq!(self.transaction_depth, 0);
405 if let Some(entry_ix) = self
406 .undo_stack
407 .iter()
408 .rposition(|entry| entry.transaction.id == transaction_id)
409 {
410 Some(self.undo_stack.remove(entry_ix).transaction)
411 } else if let Some(entry_ix) = self
412 .redo_stack
413 .iter()
414 .rposition(|entry| entry.transaction.id == transaction_id)
415 {
416 Some(self.redo_stack.remove(entry_ix).transaction)
417 } else {
418 None
419 }
420 }
421
422 fn transaction(&self, transaction_id: TransactionId) -> Option<&Transaction> {
423 let entry = self
424 .undo_stack
425 .iter()
426 .rfind(|entry| entry.transaction.id == transaction_id)
427 .or_else(|| {
428 self.redo_stack
429 .iter()
430 .rfind(|entry| entry.transaction.id == transaction_id)
431 })?;
432 Some(&entry.transaction)
433 }
434
435 fn transaction_mut(&mut self, transaction_id: TransactionId) -> Option<&mut Transaction> {
436 let entry = self
437 .undo_stack
438 .iter_mut()
439 .rfind(|entry| entry.transaction.id == transaction_id)
440 .or_else(|| {
441 self.redo_stack
442 .iter_mut()
443 .rfind(|entry| entry.transaction.id == transaction_id)
444 })?;
445 Some(&mut entry.transaction)
446 }
447
448 fn merge_transactions(&mut self, transaction: TransactionId, destination: TransactionId) {
449 if let Some(transaction) = self.forget(transaction)
450 && let Some(destination) = self.transaction_mut(destination)
451 {
452 destination.edit_ids.extend(transaction.edit_ids);
453 }
454 }
455
456 fn pop_redo(&mut self) -> Option<&HistoryEntry> {
457 assert_eq!(self.transaction_depth, 0);
458 if let Some(entry) = self.redo_stack.pop() {
459 self.undo_stack.push(entry);
460 self.undo_stack.last()
461 } else {
462 None
463 }
464 }
465
466 fn remove_from_redo(&mut self, transaction_id: TransactionId) -> &[HistoryEntry] {
467 assert_eq!(self.transaction_depth, 0);
468
469 let undo_stack_start_len = self.undo_stack.len();
470 if let Some(entry_ix) = self
471 .redo_stack
472 .iter()
473 .rposition(|entry| entry.transaction.id == transaction_id)
474 {
475 self.undo_stack
476 .extend(self.redo_stack.drain(entry_ix..).rev());
477 }
478 &self.undo_stack[undo_stack_start_len..]
479 }
480}
481
482struct Edits<'a, D: TextDimension, F: FnMut(&FragmentSummary) -> bool> {
483 visible_cursor: rope::Cursor<'a>,
484 deleted_cursor: rope::Cursor<'a>,
485 fragments_cursor: Option<FilterCursor<'a, 'static, F, Fragment, FragmentTextSummary>>,
486 undos: &'a UndoMap,
487 since: &'a clock::Global,
488 old_end: D,
489 new_end: D,
490 range: Range<(&'a Locator, usize)>,
491 buffer_id: BufferId,
492}
493
494#[derive(Clone, Debug, Default, Eq, PartialEq)]
495pub struct Edit<D> {
496 pub old: Range<D>,
497 pub new: Range<D>,
498}
499impl<D> Edit<D>
500where
501 D: PartialEq,
502{
503 pub fn is_empty(&self) -> bool {
504 self.old.start == self.old.end && self.new.start == self.new.end
505 }
506}
507
508impl<D, DDelta> Edit<D>
509where
510 D: Sub<D, Output = DDelta> + Copy,
511{
512 pub fn old_len(&self) -> DDelta {
513 self.old.end - self.old.start
514 }
515
516 pub fn new_len(&self) -> DDelta {
517 self.new.end - self.new.start
518 }
519}
520
521impl<D1, D2> Edit<(D1, D2)> {
522 pub fn flatten(self) -> (Edit<D1>, Edit<D2>) {
523 (
524 Edit {
525 old: self.old.start.0..self.old.end.0,
526 new: self.new.start.0..self.new.end.0,
527 },
528 Edit {
529 old: self.old.start.1..self.old.end.1,
530 new: self.new.start.1..self.new.end.1,
531 },
532 )
533 }
534}
535
536#[derive(Eq, PartialEq, Clone, Debug)]
537pub struct Fragment {
538 pub id: Locator,
539 pub timestamp: clock::Lamport,
540 pub insertion_offset: usize,
541 pub len: usize,
542 pub visible: bool,
543 pub deletions: HashSet<clock::Lamport>,
544 pub max_undos: clock::Global,
545}
546
547#[derive(Eq, PartialEq, Clone, Debug)]
548pub struct FragmentSummary {
549 text: FragmentTextSummary,
550 max_id: Locator,
551 max_version: clock::Global,
552 min_insertion_version: clock::Global,
553 max_insertion_version: clock::Global,
554}
555
556#[derive(Copy, Default, Clone, Debug, PartialEq, Eq)]
557struct FragmentTextSummary {
558 visible: usize,
559 deleted: usize,
560}
561
562impl<'a> sum_tree::Dimension<'a, FragmentSummary> for FragmentTextSummary {
563 fn zero(_: &Option<clock::Global>) -> Self {
564 Default::default()
565 }
566
567 fn add_summary(&mut self, summary: &'a FragmentSummary, _: &Option<clock::Global>) {
568 self.visible += summary.text.visible;
569 self.deleted += summary.text.deleted;
570 }
571}
572
573#[derive(Eq, PartialEq, Clone, Debug)]
574struct InsertionFragment {
575 timestamp: clock::Lamport,
576 split_offset: usize,
577 fragment_id: Locator,
578}
579
580#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
581struct InsertionFragmentKey {
582 timestamp: clock::Lamport,
583 split_offset: usize,
584}
585
586#[derive(Clone, Debug, Eq, PartialEq)]
587pub enum Operation {
588 Edit(EditOperation),
589 Undo(UndoOperation),
590}
591
592#[derive(Clone, Debug, Eq, PartialEq)]
593pub struct EditOperation {
594 pub timestamp: clock::Lamport,
595 pub version: clock::Global,
596 pub ranges: Vec<Range<FullOffset>>,
597 pub new_text: Vec<Arc<str>>,
598}
599
600#[derive(Clone, Debug, Eq, PartialEq)]
601pub struct UndoOperation {
602 pub timestamp: clock::Lamport,
603 pub version: clock::Global,
604 pub counts: HashMap<clock::Lamport, u32>,
605}
606
607/// Stores information about the indentation of a line (tabs and spaces).
608#[derive(Clone, Copy, Debug, Eq, PartialEq)]
609pub struct LineIndent {
610 pub tabs: u32,
611 pub spaces: u32,
612 pub line_blank: bool,
613}
614
615impl LineIndent {
616 pub fn from_chunks(chunks: &mut Chunks) -> Self {
617 let mut tabs = 0;
618 let mut spaces = 0;
619 let mut line_blank = true;
620
621 'outer: while let Some(chunk) = chunks.peek() {
622 for ch in chunk.chars() {
623 if ch == '\t' {
624 tabs += 1;
625 } else if ch == ' ' {
626 spaces += 1;
627 } else {
628 if ch != '\n' {
629 line_blank = false;
630 }
631 break 'outer;
632 }
633 }
634
635 chunks.next();
636 }
637
638 Self {
639 tabs,
640 spaces,
641 line_blank,
642 }
643 }
644
645 /// Constructs a new `LineIndent` which only contains spaces.
646 pub fn spaces(spaces: u32) -> Self {
647 Self {
648 tabs: 0,
649 spaces,
650 line_blank: true,
651 }
652 }
653
654 /// Constructs a new `LineIndent` which only contains tabs.
655 pub fn tabs(tabs: u32) -> Self {
656 Self {
657 tabs,
658 spaces: 0,
659 line_blank: true,
660 }
661 }
662
663 /// Indicates whether the line is empty.
664 pub fn is_line_empty(&self) -> bool {
665 self.tabs == 0 && self.spaces == 0 && self.line_blank
666 }
667
668 /// Indicates whether the line is blank (contains only whitespace).
669 pub fn is_line_blank(&self) -> bool {
670 self.line_blank
671 }
672
673 /// Returns the number of indentation characters (tabs or spaces).
674 pub fn raw_len(&self) -> u32 {
675 self.tabs + self.spaces
676 }
677
678 /// Returns the number of indentation characters (tabs or spaces), taking tab size into account.
679 pub fn len(&self, tab_size: u32) -> u32 {
680 self.tabs * tab_size + self.spaces
681 }
682}
683
684impl From<&str> for LineIndent {
685 fn from(value: &str) -> Self {
686 Self::from_iter(value.chars())
687 }
688}
689
690impl FromIterator<char> for LineIndent {
691 fn from_iter<T: IntoIterator<Item = char>>(chars: T) -> Self {
692 let mut tabs = 0;
693 let mut spaces = 0;
694 let mut line_blank = true;
695 for c in chars {
696 if c == '\t' {
697 tabs += 1;
698 } else if c == ' ' {
699 spaces += 1;
700 } else {
701 if c != '\n' {
702 line_blank = false;
703 }
704 break;
705 }
706 }
707 Self {
708 tabs,
709 spaces,
710 line_blank,
711 }
712 }
713}
714
715impl Buffer {
716 pub fn new(replica_id: ReplicaId, remote_id: BufferId, base_text: impl Into<String>) -> Buffer {
717 let mut base_text = base_text.into();
718 let line_ending = LineEnding::detect(&base_text);
719 LineEnding::normalize(&mut base_text);
720 Self::new_normalized(replica_id, remote_id, line_ending, Rope::from(&*base_text))
721 }
722
723 pub fn new_normalized(
724 replica_id: ReplicaId,
725 remote_id: BufferId,
726 line_ending: LineEnding,
727 normalized: Rope,
728 ) -> Buffer {
729 let history = History::new(normalized);
730 let mut fragments = SumTree::new(&None);
731 let mut insertions = SumTree::default();
732
733 let mut lamport_clock = clock::Lamport::new(replica_id);
734 let mut version = clock::Global::new();
735
736 let visible_text = history.base_text.clone();
737 if !visible_text.is_empty() {
738 let insertion_timestamp = clock::Lamport::new(ReplicaId::LOCAL);
739 lamport_clock.observe(insertion_timestamp);
740 version.observe(insertion_timestamp);
741 let fragment_id = Locator::between(&Locator::min(), &Locator::max());
742 let fragment = Fragment {
743 id: fragment_id,
744 timestamp: insertion_timestamp,
745 insertion_offset: 0,
746 len: visible_text.len(),
747 visible: true,
748 deletions: Default::default(),
749 max_undos: Default::default(),
750 };
751 insertions.push(InsertionFragment::new(&fragment), ());
752 fragments.push(fragment, &None);
753 }
754
755 Buffer {
756 snapshot: BufferSnapshot {
757 replica_id,
758 remote_id,
759 visible_text,
760 deleted_text: Rope::new(),
761 line_ending,
762 fragments,
763 insertions,
764 version,
765 undo_map: Default::default(),
766 insertion_slices: Default::default(),
767 },
768 history,
769 deferred_ops: OperationQueue::new(),
770 deferred_replicas: HashSet::default(),
771 lamport_clock,
772 subscriptions: Default::default(),
773 edit_id_resolvers: Default::default(),
774 wait_for_version_txs: Default::default(),
775 }
776 }
777
778 pub fn version(&self) -> clock::Global {
779 self.version.clone()
780 }
781
782 pub fn snapshot(&self) -> BufferSnapshot {
783 self.snapshot.clone()
784 }
785
786 pub fn branch(&self) -> Self {
787 Self {
788 snapshot: self.snapshot.clone(),
789 history: History::new(self.base_text().clone()),
790 deferred_ops: OperationQueue::new(),
791 deferred_replicas: HashSet::default(),
792 lamport_clock: clock::Lamport::new(ReplicaId::LOCAL_BRANCH),
793 subscriptions: Default::default(),
794 edit_id_resolvers: Default::default(),
795 wait_for_version_txs: Default::default(),
796 }
797 }
798
799 pub fn replica_id(&self) -> ReplicaId {
800 self.lamport_clock.replica_id
801 }
802
803 pub fn remote_id(&self) -> BufferId {
804 self.remote_id
805 }
806
807 pub fn deferred_ops_len(&self) -> usize {
808 self.deferred_ops.len()
809 }
810
811 pub fn transaction_group_interval(&self) -> Duration {
812 self.history.group_interval
813 }
814
815 pub fn edit<R, I, S, T>(&mut self, edits: R) -> Operation
816 where
817 R: IntoIterator<IntoIter = I>,
818 I: ExactSizeIterator<Item = (Range<S>, T)>,
819 S: ToOffset,
820 T: Into<Arc<str>>,
821 {
822 let edits = edits
823 .into_iter()
824 .map(|(range, new_text)| (range, new_text.into()));
825
826 self.start_transaction();
827 let timestamp = self.lamport_clock.tick();
828 let operation = Operation::Edit(self.apply_local_edit(edits, timestamp));
829
830 self.history.push(operation.clone());
831 self.history.push_undo(operation.timestamp());
832 self.snapshot.version.observe(operation.timestamp());
833 self.end_transaction();
834 operation
835 }
836
837 fn apply_local_edit<S: ToOffset, T: Into<Arc<str>>>(
838 &mut self,
839 edits: impl ExactSizeIterator<Item = (Range<S>, T)>,
840 timestamp: clock::Lamport,
841 ) -> EditOperation {
842 let mut edits_patch = Patch::default();
843 let mut edit_op = EditOperation {
844 timestamp,
845 version: self.version(),
846 ranges: Vec::with_capacity(edits.len()),
847 new_text: Vec::with_capacity(edits.len()),
848 };
849 let mut new_insertions = Vec::new();
850 let mut insertion_offset = 0;
851 let mut insertion_slices = Vec::new();
852
853 let mut edits = edits
854 .map(|(range, new_text)| (range.to_offset(&*self), new_text))
855 .peekable();
856
857 let mut new_ropes =
858 RopeBuilder::new(self.visible_text.cursor(0), self.deleted_text.cursor(0));
859 let mut old_fragments = self.fragments.cursor::<FragmentTextSummary>(&None);
860 let mut new_fragments = old_fragments.slice(&edits.peek().unwrap().0.start, Bias::Right);
861 new_ropes.append(new_fragments.summary().text);
862
863 let mut fragment_start = old_fragments.start().visible;
864 for (range, new_text) in edits {
865 let new_text = LineEnding::normalize_arc(new_text.into());
866 let fragment_end = old_fragments.end().visible;
867
868 // If the current fragment ends before this range, then jump ahead to the first fragment
869 // that extends past the start of this range, reusing any intervening fragments.
870 if fragment_end < range.start {
871 // If the current fragment has been partially consumed, then consume the rest of it
872 // and advance to the next fragment before slicing.
873 if fragment_start > old_fragments.start().visible {
874 if fragment_end > fragment_start {
875 let mut suffix = old_fragments.item().unwrap().clone();
876 suffix.len = fragment_end - fragment_start;
877 suffix.insertion_offset += fragment_start - old_fragments.start().visible;
878 new_insertions.push(InsertionFragment::insert_new(&suffix));
879 new_ropes.push_fragment(&suffix, suffix.visible);
880 new_fragments.push(suffix, &None);
881 }
882 old_fragments.next();
883 }
884
885 let slice = old_fragments.slice(&range.start, Bias::Right);
886 new_ropes.append(slice.summary().text);
887 new_fragments.append(slice, &None);
888 fragment_start = old_fragments.start().visible;
889 }
890
891 let full_range_start = FullOffset(range.start + old_fragments.start().deleted);
892
893 // Preserve any portion of the current fragment that precedes this range.
894 if fragment_start < range.start {
895 let mut prefix = old_fragments.item().unwrap().clone();
896 prefix.len = range.start - fragment_start;
897 prefix.insertion_offset += fragment_start - old_fragments.start().visible;
898 prefix.id = Locator::between(&new_fragments.summary().max_id, &prefix.id);
899 new_insertions.push(InsertionFragment::insert_new(&prefix));
900 new_ropes.push_fragment(&prefix, prefix.visible);
901 new_fragments.push(prefix, &None);
902 fragment_start = range.start;
903 }
904
905 // Insert the new text before any existing fragments within the range.
906 if !new_text.is_empty() {
907 let new_start = new_fragments.summary().text.visible;
908
909 let fragment = Fragment {
910 id: Locator::between(
911 &new_fragments.summary().max_id,
912 old_fragments
913 .item()
914 .map_or(&Locator::max(), |old_fragment| &old_fragment.id),
915 ),
916 timestamp,
917 insertion_offset,
918 len: new_text.len(),
919 deletions: Default::default(),
920 max_undos: Default::default(),
921 visible: true,
922 };
923 edits_patch.push(Edit {
924 old: fragment_start..fragment_start,
925 new: new_start..new_start + new_text.len(),
926 });
927 insertion_slices.push(InsertionSlice::from_fragment(timestamp, &fragment));
928 new_insertions.push(InsertionFragment::insert_new(&fragment));
929 new_ropes.push_str(new_text.as_ref());
930 new_fragments.push(fragment, &None);
931 insertion_offset += new_text.len();
932 }
933
934 // Advance through every fragment that intersects this range, marking the intersecting
935 // portions as deleted.
936 while fragment_start < range.end {
937 let fragment = old_fragments.item().unwrap();
938 let fragment_end = old_fragments.end().visible;
939 let mut intersection = fragment.clone();
940 let intersection_end = cmp::min(range.end, fragment_end);
941 if fragment.visible {
942 intersection.len = intersection_end - fragment_start;
943 intersection.insertion_offset += fragment_start - old_fragments.start().visible;
944 intersection.id =
945 Locator::between(&new_fragments.summary().max_id, &intersection.id);
946 intersection.deletions.insert(timestamp);
947 intersection.visible = false;
948 }
949 if intersection.len > 0 {
950 if fragment.visible && !intersection.visible {
951 let new_start = new_fragments.summary().text.visible;
952 edits_patch.push(Edit {
953 old: fragment_start..intersection_end,
954 new: new_start..new_start,
955 });
956 insertion_slices
957 .push(InsertionSlice::from_fragment(timestamp, &intersection));
958 }
959 new_insertions.push(InsertionFragment::insert_new(&intersection));
960 new_ropes.push_fragment(&intersection, fragment.visible);
961 new_fragments.push(intersection, &None);
962 fragment_start = intersection_end;
963 }
964 if fragment_end <= range.end {
965 old_fragments.next();
966 }
967 }
968
969 let full_range_end = FullOffset(range.end + old_fragments.start().deleted);
970 edit_op.ranges.push(full_range_start..full_range_end);
971 edit_op.new_text.push(new_text);
972 }
973
974 // If the current fragment has been partially consumed, then consume the rest of it
975 // and advance to the next fragment before slicing.
976 if fragment_start > old_fragments.start().visible {
977 let fragment_end = old_fragments.end().visible;
978 if fragment_end > fragment_start {
979 let mut suffix = old_fragments.item().unwrap().clone();
980 suffix.len = fragment_end - fragment_start;
981 suffix.insertion_offset += fragment_start - old_fragments.start().visible;
982 new_insertions.push(InsertionFragment::insert_new(&suffix));
983 new_ropes.push_fragment(&suffix, suffix.visible);
984 new_fragments.push(suffix, &None);
985 }
986 old_fragments.next();
987 }
988
989 let suffix = old_fragments.suffix();
990 new_ropes.append(suffix.summary().text);
991 new_fragments.append(suffix, &None);
992 let (visible_text, deleted_text) = new_ropes.finish();
993 drop(old_fragments);
994
995 self.snapshot.fragments = new_fragments;
996 self.snapshot.insertions.edit(new_insertions, ());
997 self.snapshot.visible_text = visible_text;
998 self.snapshot.deleted_text = deleted_text;
999 self.subscriptions.publish_mut(&edits_patch);
1000 self.snapshot.insertion_slices.extend(insertion_slices);
1001 edit_op
1002 }
1003
1004 pub fn set_line_ending(&mut self, line_ending: LineEnding) {
1005 self.snapshot.line_ending = line_ending;
1006 }
1007
1008 pub fn apply_ops<I: IntoIterator<Item = Operation>>(&mut self, ops: I) {
1009 let mut deferred_ops = Vec::new();
1010 for op in ops {
1011 self.history.push(op.clone());
1012 if self.can_apply_op(&op) {
1013 self.apply_op(op);
1014 } else {
1015 self.deferred_replicas.insert(op.replica_id());
1016 deferred_ops.push(op);
1017 }
1018 }
1019 self.deferred_ops.insert(deferred_ops);
1020 self.flush_deferred_ops();
1021 }
1022
1023 fn apply_op(&mut self, op: Operation) {
1024 match op {
1025 Operation::Edit(edit) => {
1026 if !self.version.observed(edit.timestamp) {
1027 self.apply_remote_edit(
1028 &edit.version,
1029 &edit.ranges,
1030 &edit.new_text,
1031 edit.timestamp,
1032 );
1033 self.snapshot.version.observe(edit.timestamp);
1034 self.lamport_clock.observe(edit.timestamp);
1035 self.resolve_edit(edit.timestamp);
1036 }
1037 }
1038 Operation::Undo(undo) => {
1039 if !self.version.observed(undo.timestamp) {
1040 self.apply_undo(&undo);
1041 self.snapshot.version.observe(undo.timestamp);
1042 self.lamport_clock.observe(undo.timestamp);
1043 }
1044 }
1045 }
1046 self.wait_for_version_txs.retain_mut(|(version, tx)| {
1047 if self.snapshot.version().observed_all(version) {
1048 tx.try_send(()).ok();
1049 false
1050 } else {
1051 true
1052 }
1053 });
1054 }
1055
1056 fn apply_remote_edit(
1057 &mut self,
1058 version: &clock::Global,
1059 ranges: &[Range<FullOffset>],
1060 new_text: &[Arc<str>],
1061 timestamp: clock::Lamport,
1062 ) {
1063 if ranges.is_empty() {
1064 return;
1065 }
1066
1067 let edits = ranges.iter().zip(new_text.iter());
1068 let mut edits_patch = Patch::default();
1069 let mut insertion_slices = Vec::new();
1070 let cx = Some(version.clone());
1071 let mut new_insertions = Vec::new();
1072 let mut insertion_offset = 0;
1073 let mut new_ropes =
1074 RopeBuilder::new(self.visible_text.cursor(0), self.deleted_text.cursor(0));
1075 let mut old_fragments = self
1076 .fragments
1077 .cursor::<Dimensions<VersionedFullOffset, usize>>(&cx);
1078 let mut new_fragments =
1079 old_fragments.slice(&VersionedFullOffset::Offset(ranges[0].start), Bias::Left);
1080 new_ropes.append(new_fragments.summary().text);
1081
1082 let mut fragment_start = old_fragments.start().0.full_offset();
1083 for (range, new_text) in edits {
1084 let fragment_end = old_fragments.end().0.full_offset();
1085
1086 // If the current fragment ends before this range, then jump ahead to the first fragment
1087 // that extends past the start of this range, reusing any intervening fragments.
1088 if fragment_end < range.start {
1089 // If the current fragment has been partially consumed, then consume the rest of it
1090 // and advance to the next fragment before slicing.
1091 if fragment_start > old_fragments.start().0.full_offset() {
1092 if fragment_end > fragment_start {
1093 let mut suffix = old_fragments.item().unwrap().clone();
1094 suffix.len = fragment_end.0 - fragment_start.0;
1095 suffix.insertion_offset +=
1096 fragment_start - old_fragments.start().0.full_offset();
1097 new_insertions.push(InsertionFragment::insert_new(&suffix));
1098 new_ropes.push_fragment(&suffix, suffix.visible);
1099 new_fragments.push(suffix, &None);
1100 }
1101 old_fragments.next();
1102 }
1103
1104 let slice =
1105 old_fragments.slice(&VersionedFullOffset::Offset(range.start), Bias::Left);
1106 new_ropes.append(slice.summary().text);
1107 new_fragments.append(slice, &None);
1108 fragment_start = old_fragments.start().0.full_offset();
1109 }
1110
1111 // If we are at the end of a non-concurrent fragment, advance to the next one.
1112 let fragment_end = old_fragments.end().0.full_offset();
1113 if fragment_end == range.start && fragment_end > fragment_start {
1114 let mut fragment = old_fragments.item().unwrap().clone();
1115 fragment.len = fragment_end.0 - fragment_start.0;
1116 fragment.insertion_offset += fragment_start - old_fragments.start().0.full_offset();
1117 new_insertions.push(InsertionFragment::insert_new(&fragment));
1118 new_ropes.push_fragment(&fragment, fragment.visible);
1119 new_fragments.push(fragment, &None);
1120 old_fragments.next();
1121 fragment_start = old_fragments.start().0.full_offset();
1122 }
1123
1124 // Skip over insertions that are concurrent to this edit, but have a lower lamport
1125 // timestamp.
1126 while let Some(fragment) = old_fragments.item() {
1127 if fragment_start == range.start && fragment.timestamp > timestamp {
1128 new_ropes.push_fragment(fragment, fragment.visible);
1129 new_fragments.push(fragment.clone(), &None);
1130 old_fragments.next();
1131 debug_assert_eq!(fragment_start, range.start);
1132 } else {
1133 break;
1134 }
1135 }
1136 debug_assert!(fragment_start <= range.start);
1137
1138 // Preserve any portion of the current fragment that precedes this range.
1139 if fragment_start < range.start {
1140 let mut prefix = old_fragments.item().unwrap().clone();
1141 prefix.len = range.start.0 - fragment_start.0;
1142 prefix.insertion_offset += fragment_start - old_fragments.start().0.full_offset();
1143 prefix.id = Locator::between(&new_fragments.summary().max_id, &prefix.id);
1144 new_insertions.push(InsertionFragment::insert_new(&prefix));
1145 fragment_start = range.start;
1146 new_ropes.push_fragment(&prefix, prefix.visible);
1147 new_fragments.push(prefix, &None);
1148 }
1149
1150 // Insert the new text before any existing fragments within the range.
1151 if !new_text.is_empty() {
1152 let mut old_start = old_fragments.start().1;
1153 if old_fragments.item().is_some_and(|f| f.visible) {
1154 old_start += fragment_start.0 - old_fragments.start().0.full_offset().0;
1155 }
1156 let new_start = new_fragments.summary().text.visible;
1157 let fragment = Fragment {
1158 id: Locator::between(
1159 &new_fragments.summary().max_id,
1160 old_fragments
1161 .item()
1162 .map_or(&Locator::max(), |old_fragment| &old_fragment.id),
1163 ),
1164 timestamp,
1165 insertion_offset,
1166 len: new_text.len(),
1167 deletions: Default::default(),
1168 max_undos: Default::default(),
1169 visible: true,
1170 };
1171 edits_patch.push(Edit {
1172 old: old_start..old_start,
1173 new: new_start..new_start + new_text.len(),
1174 });
1175 insertion_slices.push(InsertionSlice::from_fragment(timestamp, &fragment));
1176 new_insertions.push(InsertionFragment::insert_new(&fragment));
1177 new_ropes.push_str(new_text);
1178 new_fragments.push(fragment, &None);
1179 insertion_offset += new_text.len();
1180 }
1181
1182 // Advance through every fragment that intersects this range, marking the intersecting
1183 // portions as deleted.
1184 while fragment_start < range.end {
1185 let fragment = old_fragments.item().unwrap();
1186 let fragment_end = old_fragments.end().0.full_offset();
1187 let mut intersection = fragment.clone();
1188 let intersection_end = cmp::min(range.end, fragment_end);
1189 if fragment.was_visible(version, &self.undo_map) {
1190 intersection.len = intersection_end.0 - fragment_start.0;
1191 intersection.insertion_offset +=
1192 fragment_start - old_fragments.start().0.full_offset();
1193 intersection.id =
1194 Locator::between(&new_fragments.summary().max_id, &intersection.id);
1195 intersection.deletions.insert(timestamp);
1196 intersection.visible = false;
1197 insertion_slices.push(InsertionSlice::from_fragment(timestamp, &intersection));
1198 }
1199 if intersection.len > 0 {
1200 if fragment.visible && !intersection.visible {
1201 let old_start = old_fragments.start().1
1202 + (fragment_start.0 - old_fragments.start().0.full_offset().0);
1203 let new_start = new_fragments.summary().text.visible;
1204 edits_patch.push(Edit {
1205 old: old_start..old_start + intersection.len,
1206 new: new_start..new_start,
1207 });
1208 }
1209 new_insertions.push(InsertionFragment::insert_new(&intersection));
1210 new_ropes.push_fragment(&intersection, fragment.visible);
1211 new_fragments.push(intersection, &None);
1212 fragment_start = intersection_end;
1213 }
1214 if fragment_end <= range.end {
1215 old_fragments.next();
1216 }
1217 }
1218 }
1219
1220 // If the current fragment has been partially consumed, then consume the rest of it
1221 // and advance to the next fragment before slicing.
1222 if fragment_start > old_fragments.start().0.full_offset() {
1223 let fragment_end = old_fragments.end().0.full_offset();
1224 if fragment_end > fragment_start {
1225 let mut suffix = old_fragments.item().unwrap().clone();
1226 suffix.len = fragment_end.0 - fragment_start.0;
1227 suffix.insertion_offset += fragment_start - old_fragments.start().0.full_offset();
1228 new_insertions.push(InsertionFragment::insert_new(&suffix));
1229 new_ropes.push_fragment(&suffix, suffix.visible);
1230 new_fragments.push(suffix, &None);
1231 }
1232 old_fragments.next();
1233 }
1234
1235 let suffix = old_fragments.suffix();
1236 new_ropes.append(suffix.summary().text);
1237 new_fragments.append(suffix, &None);
1238 let (visible_text, deleted_text) = new_ropes.finish();
1239 drop(old_fragments);
1240
1241 self.snapshot.fragments = new_fragments;
1242 self.snapshot.visible_text = visible_text;
1243 self.snapshot.deleted_text = deleted_text;
1244 self.snapshot.insertions.edit(new_insertions, ());
1245 self.snapshot.insertion_slices.extend(insertion_slices);
1246 self.subscriptions.publish_mut(&edits_patch)
1247 }
1248
1249 fn fragment_ids_for_edits<'a>(
1250 &'a self,
1251 edit_ids: impl Iterator<Item = &'a clock::Lamport>,
1252 ) -> Vec<&'a Locator> {
1253 // Get all of the insertion slices changed by the given edits.
1254 let mut insertion_slices = Vec::new();
1255 for edit_id in edit_ids {
1256 let insertion_slice = InsertionSlice {
1257 edit_id: *edit_id,
1258 insertion_id: clock::Lamport::MIN,
1259 range: 0..0,
1260 };
1261 let slices = self
1262 .snapshot
1263 .insertion_slices
1264 .iter_from(&insertion_slice)
1265 .take_while(|slice| slice.edit_id == *edit_id);
1266 insertion_slices.extend(slices)
1267 }
1268 insertion_slices
1269 .sort_unstable_by_key(|s| (s.insertion_id, s.range.start, Reverse(s.range.end)));
1270
1271 // Get all of the fragments corresponding to these insertion slices.
1272 let mut fragment_ids = Vec::new();
1273 let mut insertions_cursor = self.insertions.cursor::<InsertionFragmentKey>(());
1274 for insertion_slice in &insertion_slices {
1275 if insertion_slice.insertion_id != insertions_cursor.start().timestamp
1276 || insertion_slice.range.start > insertions_cursor.start().split_offset
1277 {
1278 insertions_cursor.seek_forward(
1279 &InsertionFragmentKey {
1280 timestamp: insertion_slice.insertion_id,
1281 split_offset: insertion_slice.range.start,
1282 },
1283 Bias::Left,
1284 );
1285 }
1286 while let Some(item) = insertions_cursor.item() {
1287 if item.timestamp != insertion_slice.insertion_id
1288 || item.split_offset >= insertion_slice.range.end
1289 {
1290 break;
1291 }
1292 fragment_ids.push(&item.fragment_id);
1293 insertions_cursor.next();
1294 }
1295 }
1296 fragment_ids.sort_unstable();
1297 fragment_ids
1298 }
1299
1300 fn apply_undo(&mut self, undo: &UndoOperation) {
1301 self.snapshot.undo_map.insert(undo);
1302
1303 let mut edits = Patch::default();
1304 let mut old_fragments = self
1305 .fragments
1306 .cursor::<Dimensions<Option<&Locator>, usize>>(&None);
1307 let mut new_fragments = SumTree::new(&None);
1308 let mut new_ropes =
1309 RopeBuilder::new(self.visible_text.cursor(0), self.deleted_text.cursor(0));
1310
1311 for fragment_id in self.fragment_ids_for_edits(undo.counts.keys()) {
1312 let preceding_fragments = old_fragments.slice(&Some(fragment_id), Bias::Left);
1313 new_ropes.append(preceding_fragments.summary().text);
1314 new_fragments.append(preceding_fragments, &None);
1315
1316 if let Some(fragment) = old_fragments.item() {
1317 let mut fragment = fragment.clone();
1318 let fragment_was_visible = fragment.visible;
1319
1320 fragment.visible = fragment.is_visible(&self.undo_map);
1321 fragment.max_undos.observe(undo.timestamp);
1322
1323 let old_start = old_fragments.start().1;
1324 let new_start = new_fragments.summary().text.visible;
1325 if fragment_was_visible && !fragment.visible {
1326 edits.push(Edit {
1327 old: old_start..old_start + fragment.len,
1328 new: new_start..new_start,
1329 });
1330 } else if !fragment_was_visible && fragment.visible {
1331 edits.push(Edit {
1332 old: old_start..old_start,
1333 new: new_start..new_start + fragment.len,
1334 });
1335 }
1336 new_ropes.push_fragment(&fragment, fragment_was_visible);
1337 new_fragments.push(fragment, &None);
1338
1339 old_fragments.next();
1340 }
1341 }
1342
1343 let suffix = old_fragments.suffix();
1344 new_ropes.append(suffix.summary().text);
1345 new_fragments.append(suffix, &None);
1346
1347 drop(old_fragments);
1348 let (visible_text, deleted_text) = new_ropes.finish();
1349 self.snapshot.fragments = new_fragments;
1350 self.snapshot.visible_text = visible_text;
1351 self.snapshot.deleted_text = deleted_text;
1352 self.subscriptions.publish_mut(&edits);
1353 }
1354
1355 fn flush_deferred_ops(&mut self) {
1356 self.deferred_replicas.clear();
1357 let mut deferred_ops = Vec::new();
1358 for op in self.deferred_ops.drain().iter().cloned() {
1359 if self.can_apply_op(&op) {
1360 self.apply_op(op);
1361 } else {
1362 self.deferred_replicas.insert(op.replica_id());
1363 deferred_ops.push(op);
1364 }
1365 }
1366 self.deferred_ops.insert(deferred_ops);
1367 }
1368
1369 fn can_apply_op(&self, op: &Operation) -> bool {
1370 if self.deferred_replicas.contains(&op.replica_id()) {
1371 false
1372 } else {
1373 self.version.observed_all(match op {
1374 Operation::Edit(edit) => &edit.version,
1375 Operation::Undo(undo) => &undo.version,
1376 })
1377 }
1378 }
1379
1380 pub fn has_deferred_ops(&self) -> bool {
1381 !self.deferred_ops.is_empty()
1382 }
1383
1384 pub fn peek_undo_stack(&self) -> Option<&HistoryEntry> {
1385 self.history.undo_stack.last()
1386 }
1387
1388 pub fn peek_redo_stack(&self) -> Option<&HistoryEntry> {
1389 self.history.redo_stack.last()
1390 }
1391
1392 pub fn start_transaction(&mut self) -> Option<TransactionId> {
1393 self.start_transaction_at(Instant::now())
1394 }
1395
1396 pub fn start_transaction_at(&mut self, now: Instant) -> Option<TransactionId> {
1397 self.history
1398 .start_transaction(self.version.clone(), now, &mut self.lamport_clock)
1399 }
1400
1401 pub fn end_transaction(&mut self) -> Option<(TransactionId, clock::Global)> {
1402 self.end_transaction_at(Instant::now())
1403 }
1404
1405 pub fn end_transaction_at(&mut self, now: Instant) -> Option<(TransactionId, clock::Global)> {
1406 if let Some(entry) = self.history.end_transaction(now) {
1407 let since = entry.transaction.start.clone();
1408 let id = self.history.group().unwrap();
1409 Some((id, since))
1410 } else {
1411 None
1412 }
1413 }
1414
1415 pub fn finalize_last_transaction(&mut self) -> Option<&Transaction> {
1416 self.history.finalize_last_transaction()
1417 }
1418
1419 pub fn group_until_transaction(&mut self, transaction_id: TransactionId) {
1420 self.history.group_until(transaction_id);
1421 }
1422
1423 pub fn base_text(&self) -> &Rope {
1424 &self.history.base_text
1425 }
1426
1427 pub fn operations(&self) -> &TreeMap<clock::Lamport, Operation> {
1428 &self.history.operations
1429 }
1430
1431 pub fn undo(&mut self) -> Option<(TransactionId, Operation)> {
1432 if let Some(entry) = self.history.pop_undo() {
1433 let transaction = entry.transaction.clone();
1434 let transaction_id = transaction.id;
1435 let op = self.undo_or_redo(transaction);
1436 Some((transaction_id, op))
1437 } else {
1438 None
1439 }
1440 }
1441
1442 pub fn undo_transaction(&mut self, transaction_id: TransactionId) -> Option<Operation> {
1443 let transaction = self
1444 .history
1445 .remove_from_undo(transaction_id)?
1446 .transaction
1447 .clone();
1448 Some(self.undo_or_redo(transaction))
1449 }
1450
1451 pub fn undo_to_transaction(&mut self, transaction_id: TransactionId) -> Vec<Operation> {
1452 let transactions = self
1453 .history
1454 .remove_from_undo_until(transaction_id)
1455 .iter()
1456 .map(|entry| entry.transaction.clone())
1457 .collect::<Vec<_>>();
1458
1459 transactions
1460 .into_iter()
1461 .map(|transaction| self.undo_or_redo(transaction))
1462 .collect()
1463 }
1464
1465 pub fn forget_transaction(&mut self, transaction_id: TransactionId) -> Option<Transaction> {
1466 self.history.forget(transaction_id)
1467 }
1468
1469 pub fn get_transaction(&self, transaction_id: TransactionId) -> Option<&Transaction> {
1470 self.history.transaction(transaction_id)
1471 }
1472
1473 pub fn merge_transactions(&mut self, transaction: TransactionId, destination: TransactionId) {
1474 self.history.merge_transactions(transaction, destination);
1475 }
1476
1477 pub fn redo(&mut self) -> Option<(TransactionId, Operation)> {
1478 if let Some(entry) = self.history.pop_redo() {
1479 let transaction = entry.transaction.clone();
1480 let transaction_id = transaction.id;
1481 let op = self.undo_or_redo(transaction);
1482 Some((transaction_id, op))
1483 } else {
1484 None
1485 }
1486 }
1487
1488 pub fn redo_to_transaction(&mut self, transaction_id: TransactionId) -> Vec<Operation> {
1489 let transactions = self
1490 .history
1491 .remove_from_redo(transaction_id)
1492 .iter()
1493 .map(|entry| entry.transaction.clone())
1494 .collect::<Vec<_>>();
1495
1496 transactions
1497 .into_iter()
1498 .map(|transaction| self.undo_or_redo(transaction))
1499 .collect()
1500 }
1501
1502 fn undo_or_redo(&mut self, transaction: Transaction) -> Operation {
1503 let mut counts = HashMap::default();
1504 for edit_id in transaction.edit_ids {
1505 counts.insert(edit_id, self.undo_map.undo_count(edit_id).saturating_add(1));
1506 }
1507
1508 let operation = self.undo_operations(counts);
1509 self.history.push(operation.clone());
1510 operation
1511 }
1512
1513 pub fn undo_operations(&mut self, counts: HashMap<clock::Lamport, u32>) -> Operation {
1514 let timestamp = self.lamport_clock.tick();
1515 let version = self.version();
1516 self.snapshot.version.observe(timestamp);
1517 let undo = UndoOperation {
1518 timestamp,
1519 version,
1520 counts,
1521 };
1522 self.apply_undo(&undo);
1523 Operation::Undo(undo)
1524 }
1525
1526 pub fn push_transaction(&mut self, transaction: Transaction, now: Instant) {
1527 self.history.push_transaction(transaction, now);
1528 }
1529
1530 /// Differs from `push_transaction` in that it does not clear the redo stack.
1531 /// The caller responsible for
1532 /// Differs from `push_transaction` in that it does not clear the redo
1533 /// stack. Intended to be used to create a parent transaction to merge
1534 /// potential child transactions into.
1535 ///
1536 /// The caller is responsible for removing it from the undo history using
1537 /// `forget_transaction` if no edits are merged into it. Otherwise, if edits
1538 /// are merged into this transaction, the caller is responsible for ensuring
1539 /// the redo stack is cleared. The easiest way to ensure the redo stack is
1540 /// cleared is to create transactions with the usual `start_transaction` and
1541 /// `end_transaction` methods and merging the resulting transactions into
1542 /// the transaction created by this method
1543 pub fn push_empty_transaction(&mut self, now: Instant) -> TransactionId {
1544 self.history
1545 .push_empty_transaction(self.version.clone(), now, &mut self.lamport_clock)
1546 }
1547
1548 pub fn edited_ranges_for_transaction_id<D>(
1549 &self,
1550 transaction_id: TransactionId,
1551 ) -> impl '_ + Iterator<Item = Range<D>>
1552 where
1553 D: TextDimension,
1554 {
1555 self.history
1556 .transaction(transaction_id)
1557 .into_iter()
1558 .flat_map(|transaction| self.edited_ranges_for_transaction(transaction))
1559 }
1560
1561 pub fn edited_ranges_for_edit_ids<'a, D>(
1562 &'a self,
1563 edit_ids: impl IntoIterator<Item = &'a clock::Lamport>,
1564 ) -> impl 'a + Iterator<Item = Range<D>>
1565 where
1566 D: TextDimension,
1567 {
1568 // get fragment ranges
1569 let mut cursor = self
1570 .fragments
1571 .cursor::<Dimensions<Option<&Locator>, usize>>(&None);
1572 let offset_ranges = self
1573 .fragment_ids_for_edits(edit_ids.into_iter())
1574 .into_iter()
1575 .filter_map(move |fragment_id| {
1576 cursor.seek_forward(&Some(fragment_id), Bias::Left);
1577 let fragment = cursor.item()?;
1578 let start_offset = cursor.start().1;
1579 let end_offset = start_offset + if fragment.visible { fragment.len } else { 0 };
1580 Some(start_offset..end_offset)
1581 });
1582
1583 // combine adjacent ranges
1584 let mut prev_range: Option<Range<usize>> = None;
1585 let disjoint_ranges = offset_ranges
1586 .map(Some)
1587 .chain([None])
1588 .filter_map(move |range| {
1589 if let Some((range, prev_range)) = range.as_ref().zip(prev_range.as_mut())
1590 && prev_range.end == range.start
1591 {
1592 prev_range.end = range.end;
1593 return None;
1594 }
1595 let result = prev_range.clone();
1596 prev_range = range;
1597 result
1598 });
1599
1600 // convert to the desired text dimension.
1601 let mut position = D::zero(());
1602 let mut rope_cursor = self.visible_text.cursor(0);
1603 disjoint_ranges.map(move |range| {
1604 position.add_assign(&rope_cursor.summary(range.start));
1605 let start = position;
1606 position.add_assign(&rope_cursor.summary(range.end));
1607 let end = position;
1608 start..end
1609 })
1610 }
1611
1612 pub fn edited_ranges_for_transaction<'a, D>(
1613 &'a self,
1614 transaction: &'a Transaction,
1615 ) -> impl 'a + Iterator<Item = Range<D>>
1616 where
1617 D: TextDimension,
1618 {
1619 self.edited_ranges_for_edit_ids(&transaction.edit_ids)
1620 }
1621
1622 pub fn subscribe(&mut self) -> Subscription<usize> {
1623 self.subscriptions.subscribe()
1624 }
1625
1626 pub fn wait_for_edits<It: IntoIterator<Item = clock::Lamport>>(
1627 &mut self,
1628 edit_ids: It,
1629 ) -> impl 'static + Future<Output = Result<()>> + use<It> {
1630 let mut futures = Vec::new();
1631 for edit_id in edit_ids {
1632 if !self.version.observed(edit_id) {
1633 let (tx, rx) = oneshot::channel();
1634 self.edit_id_resolvers.entry(edit_id).or_default().push(tx);
1635 futures.push(rx);
1636 }
1637 }
1638
1639 async move {
1640 for mut future in futures {
1641 if future.recv().await.is_none() {
1642 anyhow::bail!("gave up waiting for edits");
1643 }
1644 }
1645 Ok(())
1646 }
1647 }
1648
1649 pub fn wait_for_anchors<It: IntoIterator<Item = Anchor>>(
1650 &mut self,
1651 anchors: It,
1652 ) -> impl 'static + Future<Output = Result<()>> + use<It> {
1653 let mut futures = Vec::new();
1654 for anchor in anchors {
1655 if !self.version.observed(anchor.timestamp) && !anchor.is_max() && !anchor.is_min() {
1656 let (tx, rx) = oneshot::channel();
1657 self.edit_id_resolvers
1658 .entry(anchor.timestamp)
1659 .or_default()
1660 .push(tx);
1661 futures.push(rx);
1662 }
1663 }
1664
1665 async move {
1666 for mut future in futures {
1667 if future.recv().await.is_none() {
1668 anyhow::bail!("gave up waiting for anchors");
1669 }
1670 }
1671 Ok(())
1672 }
1673 }
1674
1675 pub fn wait_for_version(
1676 &mut self,
1677 version: clock::Global,
1678 ) -> impl Future<Output = Result<()>> + use<> {
1679 let mut rx = None;
1680 if !self.snapshot.version.observed_all(&version) {
1681 let channel = oneshot::channel();
1682 self.wait_for_version_txs.push((version, channel.0));
1683 rx = Some(channel.1);
1684 }
1685 async move {
1686 if let Some(mut rx) = rx
1687 && rx.recv().await.is_none()
1688 {
1689 anyhow::bail!("gave up waiting for version");
1690 }
1691 Ok(())
1692 }
1693 }
1694
1695 pub fn give_up_waiting(&mut self) {
1696 self.edit_id_resolvers.clear();
1697 self.wait_for_version_txs.clear();
1698 }
1699
1700 fn resolve_edit(&mut self, edit_id: clock::Lamport) {
1701 for mut tx in self
1702 .edit_id_resolvers
1703 .remove(&edit_id)
1704 .into_iter()
1705 .flatten()
1706 {
1707 tx.try_send(()).ok();
1708 }
1709 }
1710}
1711
1712#[cfg(any(test, feature = "test-support"))]
1713impl Buffer {
1714 #[track_caller]
1715 pub fn edit_via_marked_text(&mut self, marked_string: &str) {
1716 let edits = self.edits_for_marked_text(marked_string);
1717 self.edit(edits);
1718 }
1719
1720 #[track_caller]
1721 pub fn edits_for_marked_text(&self, marked_string: &str) -> Vec<(Range<usize>, String)> {
1722 let old_text = self.text();
1723 let (new_text, mut ranges) = util::test::marked_text_ranges(marked_string, false);
1724 if ranges.is_empty() {
1725 ranges.push(0..new_text.len());
1726 }
1727
1728 assert_eq!(
1729 old_text[..ranges[0].start],
1730 new_text[..ranges[0].start],
1731 "invalid edit"
1732 );
1733
1734 let mut delta = 0;
1735 let mut edits = Vec::new();
1736 let mut ranges = ranges.into_iter().peekable();
1737
1738 while let Some(inserted_range) = ranges.next() {
1739 let new_start = inserted_range.start;
1740 let old_start = (new_start as isize - delta) as usize;
1741
1742 let following_text = if let Some(next_range) = ranges.peek() {
1743 &new_text[inserted_range.end..next_range.start]
1744 } else {
1745 &new_text[inserted_range.end..]
1746 };
1747
1748 let inserted_len = inserted_range.len();
1749 let deleted_len = old_text[old_start..]
1750 .find(following_text)
1751 .expect("invalid edit");
1752
1753 let old_range = old_start..old_start + deleted_len;
1754 edits.push((old_range, new_text[inserted_range].to_string()));
1755 delta += inserted_len as isize - deleted_len as isize;
1756 }
1757
1758 assert_eq!(
1759 old_text.len() as isize + delta,
1760 new_text.len() as isize,
1761 "invalid edit"
1762 );
1763
1764 edits
1765 }
1766
1767 pub fn check_invariants(&self) {
1768 // Ensure every fragment is ordered by locator in the fragment tree and corresponds
1769 // to an insertion fragment in the insertions tree.
1770 let mut prev_fragment_id = Locator::min();
1771 for fragment in self.snapshot.fragments.items(&None) {
1772 assert!(fragment.id > prev_fragment_id);
1773 prev_fragment_id = fragment.id.clone();
1774
1775 let insertion_fragment = self
1776 .snapshot
1777 .insertions
1778 .get(
1779 &InsertionFragmentKey {
1780 timestamp: fragment.timestamp,
1781 split_offset: fragment.insertion_offset,
1782 },
1783 (),
1784 )
1785 .unwrap();
1786 assert_eq!(
1787 insertion_fragment.fragment_id, fragment.id,
1788 "fragment: {:?}\ninsertion: {:?}",
1789 fragment, insertion_fragment
1790 );
1791 }
1792
1793 let mut cursor = self.snapshot.fragments.cursor::<Option<&Locator>>(&None);
1794 for insertion_fragment in self.snapshot.insertions.cursor::<()>(()) {
1795 cursor.seek(&Some(&insertion_fragment.fragment_id), Bias::Left);
1796 let fragment = cursor.item().unwrap();
1797 assert_eq!(insertion_fragment.fragment_id, fragment.id);
1798 assert_eq!(insertion_fragment.split_offset, fragment.insertion_offset);
1799 }
1800
1801 let fragment_summary = self.snapshot.fragments.summary();
1802 assert_eq!(
1803 fragment_summary.text.visible,
1804 self.snapshot.visible_text.len()
1805 );
1806 assert_eq!(
1807 fragment_summary.text.deleted,
1808 self.snapshot.deleted_text.len()
1809 );
1810
1811 assert!(!self.text().contains("\r\n"));
1812 }
1813
1814 pub fn set_group_interval(&mut self, group_interval: Duration) {
1815 self.history.group_interval = group_interval;
1816 }
1817
1818 pub fn random_byte_range(&self, start_offset: usize, rng: &mut impl rand::Rng) -> Range<usize> {
1819 let end = self.clip_offset(rng.random_range(start_offset..=self.len()), Bias::Right);
1820 let start = self.clip_offset(rng.random_range(start_offset..=end), Bias::Right);
1821 start..end
1822 }
1823
1824 pub fn get_random_edits<T>(
1825 &self,
1826 rng: &mut T,
1827 edit_count: usize,
1828 ) -> Vec<(Range<usize>, Arc<str>)>
1829 where
1830 T: rand::Rng,
1831 {
1832 let mut edits: Vec<(Range<usize>, Arc<str>)> = Vec::new();
1833 let mut last_end = None;
1834 for _ in 0..edit_count {
1835 if last_end.is_some_and(|last_end| last_end >= self.len()) {
1836 break;
1837 }
1838 let new_start = last_end.map_or(0, |last_end| last_end + 1);
1839 let range = self.random_byte_range(new_start, rng);
1840 last_end = Some(range.end);
1841
1842 let new_text_len = rng.random_range(0..10);
1843 let new_text: String = RandomCharIter::new(&mut *rng).take(new_text_len).collect();
1844
1845 edits.push((range, new_text.into()));
1846 }
1847 edits
1848 }
1849
1850 pub fn randomly_edit<T>(
1851 &mut self,
1852 rng: &mut T,
1853 edit_count: usize,
1854 ) -> (Vec<(Range<usize>, Arc<str>)>, Operation)
1855 where
1856 T: rand::Rng,
1857 {
1858 let mut edits = self.get_random_edits(rng, edit_count);
1859 log::info!("mutating buffer {:?} with {:?}", self.replica_id, edits);
1860
1861 let op = self.edit(edits.iter().cloned());
1862 if let Operation::Edit(edit) = &op {
1863 assert_eq!(edits.len(), edit.new_text.len());
1864 for (edit, new_text) in edits.iter_mut().zip(&edit.new_text) {
1865 edit.1 = new_text.clone();
1866 }
1867 } else {
1868 unreachable!()
1869 }
1870
1871 (edits, op)
1872 }
1873
1874 pub fn randomly_undo_redo(&mut self, rng: &mut impl rand::Rng) -> Vec<Operation> {
1875 use rand::prelude::*;
1876
1877 let mut ops = Vec::new();
1878 for _ in 0..rng.random_range(1..=5) {
1879 if let Some(entry) = self.history.undo_stack.choose(rng) {
1880 let transaction = entry.transaction.clone();
1881 log::info!(
1882 "undoing buffer {:?} transaction {:?}",
1883 self.replica_id,
1884 transaction
1885 );
1886 ops.push(self.undo_or_redo(transaction));
1887 }
1888 }
1889 ops
1890 }
1891}
1892
1893impl Deref for Buffer {
1894 type Target = BufferSnapshot;
1895
1896 fn deref(&self) -> &Self::Target {
1897 &self.snapshot
1898 }
1899}
1900
1901impl BufferSnapshot {
1902 pub fn as_rope(&self) -> &Rope {
1903 &self.visible_text
1904 }
1905
1906 pub fn rope_for_version(&self, version: &clock::Global) -> Rope {
1907 let mut rope = Rope::new();
1908
1909 let mut cursor = self
1910 .fragments
1911 .filter::<_, FragmentTextSummary>(&None, move |summary| {
1912 !version.observed_all(&summary.max_version)
1913 });
1914 cursor.next();
1915
1916 let mut visible_cursor = self.visible_text.cursor(0);
1917 let mut deleted_cursor = self.deleted_text.cursor(0);
1918
1919 while let Some(fragment) = cursor.item() {
1920 if cursor.start().visible > visible_cursor.offset() {
1921 let text = visible_cursor.slice(cursor.start().visible);
1922 rope.append(text);
1923 }
1924
1925 if fragment.was_visible(version, &self.undo_map) {
1926 if fragment.visible {
1927 let text = visible_cursor.slice(cursor.end().visible);
1928 rope.append(text);
1929 } else {
1930 deleted_cursor.seek_forward(cursor.start().deleted);
1931 let text = deleted_cursor.slice(cursor.end().deleted);
1932 rope.append(text);
1933 }
1934 } else if fragment.visible {
1935 visible_cursor.seek_forward(cursor.end().visible);
1936 }
1937
1938 cursor.next();
1939 }
1940
1941 if cursor.start().visible > visible_cursor.offset() {
1942 let text = visible_cursor.slice(cursor.start().visible);
1943 rope.append(text);
1944 }
1945
1946 rope
1947 }
1948
1949 pub fn remote_id(&self) -> BufferId {
1950 self.remote_id
1951 }
1952
1953 pub fn replica_id(&self) -> ReplicaId {
1954 self.replica_id
1955 }
1956
1957 pub fn row_count(&self) -> u32 {
1958 self.max_point().row + 1
1959 }
1960
1961 pub fn len(&self) -> usize {
1962 self.visible_text.len()
1963 }
1964
1965 pub fn is_empty(&self) -> bool {
1966 self.len() == 0
1967 }
1968
1969 pub fn chars(&self) -> impl Iterator<Item = char> + '_ {
1970 self.chars_at(0)
1971 }
1972
1973 pub fn chars_for_range<T: ToOffset>(&self, range: Range<T>) -> impl Iterator<Item = char> + '_ {
1974 self.text_for_range(range).flat_map(str::chars)
1975 }
1976
1977 pub fn reversed_chars_for_range<T: ToOffset>(
1978 &self,
1979 range: Range<T>,
1980 ) -> impl Iterator<Item = char> + '_ {
1981 self.reversed_chunks_in_range(range)
1982 .flat_map(|chunk| chunk.chars().rev())
1983 }
1984
1985 pub fn contains_str_at<T>(&self, position: T, needle: &str) -> bool
1986 where
1987 T: ToOffset,
1988 {
1989 let position = position.to_offset(self);
1990 position == self.clip_offset(position, Bias::Left)
1991 && self
1992 .bytes_in_range(position..self.len())
1993 .flatten()
1994 .copied()
1995 .take(needle.len())
1996 .eq(needle.bytes())
1997 }
1998
1999 pub fn common_prefix_at<T>(&self, position: T, needle: &str) -> Range<T>
2000 where
2001 T: ToOffset + TextDimension,
2002 {
2003 let offset = position.to_offset(self);
2004 let common_prefix_len = needle
2005 .char_indices()
2006 .map(|(index, _)| index)
2007 .chain([needle.len()])
2008 .take_while(|&len| len <= offset)
2009 .filter(|&len| {
2010 let left = self
2011 .chars_for_range(offset - len..offset)
2012 .flat_map(char::to_lowercase);
2013 let right = needle[..len].chars().flat_map(char::to_lowercase);
2014 left.eq(right)
2015 })
2016 .last()
2017 .unwrap_or(0);
2018 let start_offset = offset - common_prefix_len;
2019 let start = self.text_summary_for_range(0..start_offset);
2020 start..position
2021 }
2022
2023 pub fn text(&self) -> String {
2024 self.visible_text.to_string()
2025 }
2026
2027 pub fn line_ending(&self) -> LineEnding {
2028 self.line_ending
2029 }
2030
2031 pub fn deleted_text(&self) -> String {
2032 self.deleted_text.to_string()
2033 }
2034
2035 pub fn fragments(&self) -> impl Iterator<Item = &Fragment> {
2036 self.fragments.iter()
2037 }
2038
2039 pub fn text_summary(&self) -> TextSummary {
2040 self.visible_text.summary()
2041 }
2042
2043 pub fn max_point(&self) -> Point {
2044 self.visible_text.max_point()
2045 }
2046
2047 pub fn max_point_utf16(&self) -> PointUtf16 {
2048 self.visible_text.max_point_utf16()
2049 }
2050
2051 pub fn point_to_offset(&self, point: Point) -> usize {
2052 self.visible_text.point_to_offset(point)
2053 }
2054
2055 pub fn point_to_offset_utf16(&self, point: Point) -> OffsetUtf16 {
2056 self.visible_text.point_to_offset_utf16(point)
2057 }
2058
2059 pub fn point_utf16_to_offset_utf16(&self, point: PointUtf16) -> OffsetUtf16 {
2060 self.visible_text.point_utf16_to_offset_utf16(point)
2061 }
2062
2063 pub fn point_utf16_to_offset(&self, point: PointUtf16) -> usize {
2064 self.visible_text.point_utf16_to_offset(point)
2065 }
2066
2067 pub fn unclipped_point_utf16_to_offset(&self, point: Unclipped<PointUtf16>) -> usize {
2068 self.visible_text.unclipped_point_utf16_to_offset(point)
2069 }
2070
2071 pub fn unclipped_point_utf16_to_point(&self, point: Unclipped<PointUtf16>) -> Point {
2072 self.visible_text.unclipped_point_utf16_to_point(point)
2073 }
2074
2075 pub fn offset_utf16_to_offset(&self, offset: OffsetUtf16) -> usize {
2076 self.visible_text.offset_utf16_to_offset(offset)
2077 }
2078
2079 pub fn offset_to_offset_utf16(&self, offset: usize) -> OffsetUtf16 {
2080 self.visible_text.offset_to_offset_utf16(offset)
2081 }
2082
2083 pub fn offset_to_point(&self, offset: usize) -> Point {
2084 self.visible_text.offset_to_point(offset)
2085 }
2086
2087 pub fn offset_to_point_utf16(&self, offset: usize) -> PointUtf16 {
2088 self.visible_text.offset_to_point_utf16(offset)
2089 }
2090
2091 pub fn point_to_point_utf16(&self, point: Point) -> PointUtf16 {
2092 self.visible_text.point_to_point_utf16(point)
2093 }
2094
2095 pub fn point_utf16_to_point(&self, point: PointUtf16) -> Point {
2096 self.visible_text.point_utf16_to_point(point)
2097 }
2098
2099 pub fn version(&self) -> &clock::Global {
2100 &self.version
2101 }
2102
2103 pub fn chars_at<T: ToOffset>(&self, position: T) -> impl Iterator<Item = char> + '_ {
2104 let offset = position.to_offset(self);
2105 self.visible_text.chars_at(offset)
2106 }
2107
2108 pub fn reversed_chars_at<T: ToOffset>(&self, position: T) -> impl Iterator<Item = char> + '_ {
2109 let offset = position.to_offset(self);
2110 self.visible_text.reversed_chars_at(offset)
2111 }
2112
2113 pub fn reversed_chunks_in_range<T: ToOffset>(&self, range: Range<T>) -> rope::Chunks<'_> {
2114 let range = range.start.to_offset(self)..range.end.to_offset(self);
2115 self.visible_text.reversed_chunks_in_range(range)
2116 }
2117
2118 pub fn bytes_in_range<T: ToOffset>(&self, range: Range<T>) -> rope::Bytes<'_> {
2119 let start = range.start.to_offset(self);
2120 let end = range.end.to_offset(self);
2121 self.visible_text.bytes_in_range(start..end)
2122 }
2123
2124 pub fn reversed_bytes_in_range<T: ToOffset>(&self, range: Range<T>) -> rope::Bytes<'_> {
2125 let start = range.start.to_offset(self);
2126 let end = range.end.to_offset(self);
2127 self.visible_text.reversed_bytes_in_range(start..end)
2128 }
2129
2130 pub fn text_for_range<T: ToOffset>(&self, range: Range<T>) -> Chunks<'_> {
2131 let start = range.start.to_offset(self);
2132 let end = range.end.to_offset(self);
2133 self.visible_text.chunks_in_range(start..end)
2134 }
2135
2136 pub fn line_len(&self, row: u32) -> u32 {
2137 let row_start_offset = Point::new(row, 0).to_offset(self);
2138 let row_end_offset = if row >= self.max_point().row {
2139 self.len()
2140 } else {
2141 Point::new(row + 1, 0).to_previous_offset(self)
2142 };
2143 (row_end_offset - row_start_offset) as u32
2144 }
2145
2146 pub fn line_indents_in_row_range(
2147 &self,
2148 row_range: Range<u32>,
2149 ) -> impl Iterator<Item = (u32, LineIndent)> + '_ {
2150 let start = Point::new(row_range.start, 0).to_offset(self);
2151 let end = Point::new(row_range.end, self.line_len(row_range.end)).to_offset(self);
2152
2153 let mut chunks = self.as_rope().chunks_in_range(start..end);
2154 let mut row = row_range.start;
2155 let mut done = false;
2156 std::iter::from_fn(move || {
2157 if done {
2158 None
2159 } else {
2160 let indent = (row, LineIndent::from_chunks(&mut chunks));
2161 done = !chunks.next_line();
2162 row += 1;
2163 Some(indent)
2164 }
2165 })
2166 }
2167
2168 /// Returns the line indents in the given row range, exclusive of end row, in reversed order.
2169 pub fn reversed_line_indents_in_row_range(
2170 &self,
2171 row_range: Range<u32>,
2172 ) -> impl Iterator<Item = (u32, LineIndent)> + '_ {
2173 let start = Point::new(row_range.start, 0).to_offset(self);
2174
2175 let end_point;
2176 let end;
2177 if row_range.end > row_range.start {
2178 end_point = Point::new(row_range.end - 1, self.line_len(row_range.end - 1));
2179 end = end_point.to_offset(self);
2180 } else {
2181 end_point = Point::new(row_range.start, 0);
2182 end = start;
2183 };
2184
2185 let mut chunks = self.as_rope().chunks_in_range(start..end);
2186 // Move the cursor to the start of the last line if it's not empty.
2187 chunks.seek(end);
2188 if end_point.column > 0 {
2189 chunks.prev_line();
2190 }
2191
2192 let mut row = end_point.row;
2193 let mut done = false;
2194 std::iter::from_fn(move || {
2195 if done {
2196 None
2197 } else {
2198 let initial_offset = chunks.offset();
2199 let indent = (row, LineIndent::from_chunks(&mut chunks));
2200 if chunks.offset() > initial_offset {
2201 chunks.prev_line();
2202 }
2203 done = !chunks.prev_line();
2204 if !done {
2205 row -= 1;
2206 }
2207
2208 Some(indent)
2209 }
2210 })
2211 }
2212
2213 pub fn line_indent_for_row(&self, row: u32) -> LineIndent {
2214 LineIndent::from_iter(self.chars_at(Point::new(row, 0)))
2215 }
2216
2217 pub fn is_line_blank(&self, row: u32) -> bool {
2218 self.text_for_range(Point::new(row, 0)..Point::new(row, self.line_len(row)))
2219 .all(|chunk| chunk.matches(|c: char| !c.is_whitespace()).next().is_none())
2220 }
2221
2222 pub fn text_summary_for_range<D, O: ToOffset>(&self, range: Range<O>) -> D
2223 where
2224 D: TextDimension,
2225 {
2226 self.visible_text
2227 .cursor(range.start.to_offset(self))
2228 .summary(range.end.to_offset(self))
2229 }
2230
2231 pub fn summaries_for_anchors<'a, D, A>(&'a self, anchors: A) -> impl 'a + Iterator<Item = D>
2232 where
2233 D: 'a + TextDimension,
2234 A: 'a + IntoIterator<Item = &'a Anchor>,
2235 {
2236 let anchors = anchors.into_iter();
2237 self.summaries_for_anchors_with_payload::<D, _, ()>(anchors.map(|a| (a, ())))
2238 .map(|d| d.0)
2239 }
2240
2241 pub fn summaries_for_anchors_with_payload<'a, D, A, T>(
2242 &'a self,
2243 anchors: A,
2244 ) -> impl 'a + Iterator<Item = (D, T)>
2245 where
2246 D: 'a + TextDimension,
2247 A: 'a + IntoIterator<Item = (&'a Anchor, T)>,
2248 {
2249 let anchors = anchors.into_iter();
2250 let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>(());
2251 let mut fragment_cursor = self
2252 .fragments
2253 .cursor::<Dimensions<Option<&Locator>, usize>>(&None);
2254 let mut text_cursor = self.visible_text.cursor(0);
2255 let mut position = D::zero(());
2256
2257 anchors.map(move |(anchor, payload)| {
2258 if anchor.is_min() {
2259 return (D::zero(()), payload);
2260 } else if anchor.is_max() {
2261 return (D::from_text_summary(&self.visible_text.summary()), payload);
2262 }
2263
2264 let anchor_key = InsertionFragmentKey {
2265 timestamp: anchor.timestamp,
2266 split_offset: anchor.offset,
2267 };
2268 insertion_cursor.seek(&anchor_key, anchor.bias);
2269 if let Some(insertion) = insertion_cursor.item() {
2270 let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
2271 if comparison == Ordering::Greater
2272 || (anchor.bias == Bias::Left
2273 && comparison == Ordering::Equal
2274 && anchor.offset > 0)
2275 {
2276 insertion_cursor.prev();
2277 }
2278 } else {
2279 insertion_cursor.prev();
2280 }
2281 let Some(insertion) = insertion_cursor.item() else {
2282 panic!(
2283 "invalid insertion for buffer {}@{:?} with anchor {:?}",
2284 self.remote_id(),
2285 self.version,
2286 anchor
2287 );
2288 };
2289 assert_eq!(
2290 insertion.timestamp,
2291 anchor.timestamp,
2292 "invalid insertion for buffer {}@{:?} and anchor {:?}",
2293 self.remote_id(),
2294 self.version,
2295 anchor
2296 );
2297
2298 fragment_cursor.seek_forward(&Some(&insertion.fragment_id), Bias::Left);
2299 let fragment = fragment_cursor.item().unwrap();
2300 let mut fragment_offset = fragment_cursor.start().1;
2301 if fragment.visible {
2302 fragment_offset += anchor.offset - insertion.split_offset;
2303 }
2304
2305 position.add_assign(&text_cursor.summary(fragment_offset));
2306 (position, payload)
2307 })
2308 }
2309
2310 pub fn summary_for_anchor<D>(&self, anchor: &Anchor) -> D
2311 where
2312 D: TextDimension,
2313 {
2314 self.text_summary_for_range(0..self.offset_for_anchor(anchor))
2315 }
2316
2317 pub fn offset_for_anchor(&self, anchor: &Anchor) -> usize {
2318 if anchor.is_min() {
2319 0
2320 } else if anchor.is_max() {
2321 self.visible_text.len()
2322 } else {
2323 debug_assert!(anchor.buffer_id == Some(self.remote_id));
2324 debug_assert!(self.version.observed(anchor.timestamp));
2325 let anchor_key = InsertionFragmentKey {
2326 timestamp: anchor.timestamp,
2327 split_offset: anchor.offset,
2328 };
2329 let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>(());
2330 insertion_cursor.seek(&anchor_key, anchor.bias);
2331 if let Some(insertion) = insertion_cursor.item() {
2332 let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
2333 if comparison == Ordering::Greater
2334 || (anchor.bias == Bias::Left
2335 && comparison == Ordering::Equal
2336 && anchor.offset > 0)
2337 {
2338 insertion_cursor.prev();
2339 }
2340 } else {
2341 insertion_cursor.prev();
2342 }
2343
2344 let Some(insertion) = insertion_cursor
2345 .item()
2346 .filter(|insertion| insertion.timestamp == anchor.timestamp)
2347 else {
2348 self.panic_bad_anchor(anchor);
2349 };
2350
2351 let (start, _, item) = self
2352 .fragments
2353 .find::<Dimensions<Option<&Locator>, usize>, _>(
2354 &None,
2355 &Some(&insertion.fragment_id),
2356 Bias::Left,
2357 );
2358 let fragment = item.unwrap();
2359 let mut fragment_offset = start.1;
2360 if fragment.visible {
2361 fragment_offset += anchor.offset - insertion.split_offset;
2362 }
2363 fragment_offset
2364 }
2365 }
2366
2367 #[cold]
2368 fn panic_bad_anchor(&self, anchor: &Anchor) -> ! {
2369 if anchor.buffer_id.is_some_and(|id| id != self.remote_id) {
2370 panic!(
2371 "invalid anchor - buffer id does not match: anchor {anchor:?}; buffer id: {}, version: {:?}",
2372 self.remote_id, self.version
2373 );
2374 } else if !self.version.observed(anchor.timestamp) {
2375 panic!(
2376 "invalid anchor - snapshot has not observed lamport: {:?}; version: {:?}",
2377 anchor, self.version
2378 );
2379 } else {
2380 panic!(
2381 "invalid anchor {:?}. buffer id: {}, version: {:?}",
2382 anchor, self.remote_id, self.version
2383 );
2384 }
2385 }
2386
2387 fn fragment_id_for_anchor(&self, anchor: &Anchor) -> &Locator {
2388 self.try_fragment_id_for_anchor(anchor)
2389 .unwrap_or_else(|| self.panic_bad_anchor(anchor))
2390 }
2391
2392 fn try_fragment_id_for_anchor(&self, anchor: &Anchor) -> Option<&Locator> {
2393 if anchor.is_min() {
2394 Some(Locator::min_ref())
2395 } else if anchor.is_max() {
2396 Some(Locator::max_ref())
2397 } else {
2398 let anchor_key = InsertionFragmentKey {
2399 timestamp: anchor.timestamp,
2400 split_offset: anchor.offset,
2401 };
2402 let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>(());
2403 insertion_cursor.seek(&anchor_key, anchor.bias);
2404 if let Some(insertion) = insertion_cursor.item() {
2405 let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
2406 if comparison == Ordering::Greater
2407 || (anchor.bias == Bias::Left
2408 && comparison == Ordering::Equal
2409 && anchor.offset > 0)
2410 {
2411 insertion_cursor.prev();
2412 }
2413 } else {
2414 insertion_cursor.prev();
2415 }
2416
2417 insertion_cursor
2418 .item()
2419 .filter(|insertion| {
2420 !cfg!(debug_assertions) || insertion.timestamp == anchor.timestamp
2421 })
2422 .map(|insertion| &insertion.fragment_id)
2423 }
2424 }
2425
2426 pub fn anchor_before<T: ToOffset>(&self, position: T) -> Anchor {
2427 self.anchor_at(position, Bias::Left)
2428 }
2429
2430 pub fn anchor_after<T: ToOffset>(&self, position: T) -> Anchor {
2431 self.anchor_at(position, Bias::Right)
2432 }
2433
2434 pub fn anchor_at<T: ToOffset>(&self, position: T, bias: Bias) -> Anchor {
2435 self.anchor_at_offset(position.to_offset(self), bias)
2436 }
2437
2438 fn anchor_at_offset(&self, offset: usize, bias: Bias) -> Anchor {
2439 if bias == Bias::Left && offset == 0 {
2440 Anchor::min_for_buffer(self.remote_id)
2441 } else if bias == Bias::Right && offset == self.len() {
2442 Anchor::max_for_buffer(self.remote_id)
2443 } else {
2444 if cfg!(debug_assertions) {
2445 self.visible_text.assert_char_boundary(offset);
2446 } else if offset > self.visible_text.len() {
2447 panic!("offset {} is out of bounds", offset)
2448 }
2449 let (start, _, item) = self.fragments.find::<usize, _>(&None, &offset, bias);
2450 let fragment = item.unwrap();
2451 let overshoot = offset - start;
2452 Anchor {
2453 timestamp: fragment.timestamp,
2454 offset: fragment.insertion_offset + overshoot,
2455 bias,
2456 buffer_id: Some(self.remote_id),
2457 }
2458 }
2459 }
2460
2461 pub fn can_resolve(&self, anchor: &Anchor) -> bool {
2462 anchor.is_min()
2463 || anchor.is_max()
2464 || (Some(self.remote_id) == anchor.buffer_id && self.version.observed(anchor.timestamp))
2465 }
2466
2467 pub fn clip_offset(&self, offset: usize, bias: Bias) -> usize {
2468 self.visible_text.clip_offset(offset, bias)
2469 }
2470
2471 pub fn clip_point(&self, point: Point, bias: Bias) -> Point {
2472 self.visible_text.clip_point(point, bias)
2473 }
2474
2475 pub fn clip_offset_utf16(&self, offset: OffsetUtf16, bias: Bias) -> OffsetUtf16 {
2476 self.visible_text.clip_offset_utf16(offset, bias)
2477 }
2478
2479 pub fn clip_point_utf16(&self, point: Unclipped<PointUtf16>, bias: Bias) -> PointUtf16 {
2480 self.visible_text.clip_point_utf16(point, bias)
2481 }
2482
2483 pub fn edits_since<'a, D>(
2484 &'a self,
2485 since: &'a clock::Global,
2486 ) -> impl 'a + Iterator<Item = Edit<D>>
2487 where
2488 D: TextDimension + Ord,
2489 {
2490 self.edits_since_in_range(since, Anchor::MIN..Anchor::MAX)
2491 }
2492
2493 pub fn anchored_edits_since<'a, D>(
2494 &'a self,
2495 since: &'a clock::Global,
2496 ) -> impl 'a + Iterator<Item = (Edit<D>, Range<Anchor>)>
2497 where
2498 D: TextDimension + Ord,
2499 {
2500 self.anchored_edits_since_in_range(since, Anchor::MIN..Anchor::MAX)
2501 }
2502
2503 pub fn edits_since_in_range<'a, D>(
2504 &'a self,
2505 since: &'a clock::Global,
2506 range: Range<Anchor>,
2507 ) -> impl 'a + Iterator<Item = Edit<D>>
2508 where
2509 D: TextDimension + Ord,
2510 {
2511 self.anchored_edits_since_in_range(since, range)
2512 .map(|item| item.0)
2513 }
2514
2515 pub fn anchored_edits_since_in_range<'a, D>(
2516 &'a self,
2517 since: &'a clock::Global,
2518 range: Range<Anchor>,
2519 ) -> impl 'a + Iterator<Item = (Edit<D>, Range<Anchor>)>
2520 where
2521 D: TextDimension + Ord,
2522 {
2523 let fragments_cursor = if *since == self.version {
2524 None
2525 } else {
2526 let mut cursor = self.fragments.filter(&None, move |summary| {
2527 !since.observed_all(&summary.max_version)
2528 });
2529 cursor.next();
2530 Some(cursor)
2531 };
2532 let start_fragment_id = self.fragment_id_for_anchor(&range.start);
2533 let (start, _, item) = self
2534 .fragments
2535 .find::<Dimensions<Option<&Locator>, FragmentTextSummary>, _>(
2536 &None,
2537 &Some(start_fragment_id),
2538 Bias::Left,
2539 );
2540 let mut visible_start = start.1.visible;
2541 let mut deleted_start = start.1.deleted;
2542 if let Some(fragment) = item {
2543 let overshoot = range.start.offset - fragment.insertion_offset;
2544 if fragment.visible {
2545 visible_start += overshoot;
2546 } else {
2547 deleted_start += overshoot;
2548 }
2549 }
2550 let end_fragment_id = self.fragment_id_for_anchor(&range.end);
2551
2552 Edits {
2553 visible_cursor: self.visible_text.cursor(visible_start),
2554 deleted_cursor: self.deleted_text.cursor(deleted_start),
2555 fragments_cursor,
2556 undos: &self.undo_map,
2557 since,
2558 old_end: D::zero(()),
2559 new_end: D::zero(()),
2560 range: (start_fragment_id, range.start.offset)..(end_fragment_id, range.end.offset),
2561 buffer_id: self.remote_id,
2562 }
2563 }
2564
2565 pub fn has_edits_since_in_range(&self, since: &clock::Global, range: Range<Anchor>) -> bool {
2566 if *since != self.version {
2567 let start_fragment_id = self.fragment_id_for_anchor(&range.start);
2568 let end_fragment_id = self.fragment_id_for_anchor(&range.end);
2569 let mut cursor = self.fragments.filter::<_, usize>(&None, move |summary| {
2570 !since.observed_all(&summary.max_version)
2571 });
2572 cursor.next();
2573 while let Some(fragment) = cursor.item() {
2574 if fragment.id > *end_fragment_id {
2575 break;
2576 }
2577 if fragment.id > *start_fragment_id {
2578 let was_visible = fragment.was_visible(since, &self.undo_map);
2579 let is_visible = fragment.visible;
2580 if was_visible != is_visible {
2581 return true;
2582 }
2583 }
2584 cursor.next();
2585 }
2586 }
2587 false
2588 }
2589
2590 pub fn has_edits_since(&self, since: &clock::Global) -> bool {
2591 if *since != self.version {
2592 let mut cursor = self.fragments.filter::<_, usize>(&None, move |summary| {
2593 !since.observed_all(&summary.max_version)
2594 });
2595 cursor.next();
2596 while let Some(fragment) = cursor.item() {
2597 let was_visible = fragment.was_visible(since, &self.undo_map);
2598 let is_visible = fragment.visible;
2599 if was_visible != is_visible {
2600 return true;
2601 }
2602 cursor.next();
2603 }
2604 }
2605 false
2606 }
2607
2608 pub fn range_to_version(&self, range: Range<usize>, version: &clock::Global) -> Range<usize> {
2609 let mut offsets = self.offsets_to_version([range.start, range.end], version);
2610 offsets.next().unwrap()..offsets.next().unwrap()
2611 }
2612
2613 /// Converts the given sequence of offsets into their corresponding offsets
2614 /// at a prior version of this buffer.
2615 pub fn offsets_to_version<'a>(
2616 &'a self,
2617 offsets: impl 'a + IntoIterator<Item = usize>,
2618 version: &'a clock::Global,
2619 ) -> impl 'a + Iterator<Item = usize> {
2620 let mut edits = self.edits_since(version).peekable();
2621 let mut last_old_end = 0;
2622 let mut last_new_end = 0;
2623 offsets.into_iter().map(move |new_offset| {
2624 while let Some(edit) = edits.peek() {
2625 if edit.new.start > new_offset {
2626 break;
2627 }
2628
2629 if edit.new.end <= new_offset {
2630 last_new_end = edit.new.end;
2631 last_old_end = edit.old.end;
2632 edits.next();
2633 continue;
2634 }
2635
2636 let overshoot = new_offset - edit.new.start;
2637 return (edit.old.start + overshoot).min(edit.old.end);
2638 }
2639
2640 last_old_end + new_offset.saturating_sub(last_new_end)
2641 })
2642 }
2643
2644 /// Visually annotates a position or range with the `Debug` representation of a value. The
2645 /// callsite of this function is used as a key - previous annotations will be removed.
2646 #[cfg(debug_assertions)]
2647 #[track_caller]
2648 pub fn debug<R, V>(&self, ranges: &R, value: V)
2649 where
2650 R: debug::ToDebugRanges,
2651 V: std::fmt::Debug,
2652 {
2653 self.debug_with_key(std::panic::Location::caller(), ranges, value);
2654 }
2655
2656 /// Visually annotates a position or range with the `Debug` representation of a value. Previous
2657 /// debug annotations with the same key will be removed. The key is also used to determine the
2658 /// annotation's color.
2659 #[cfg(debug_assertions)]
2660 pub fn debug_with_key<K, R, V>(&self, key: &K, ranges: &R, value: V)
2661 where
2662 K: std::hash::Hash + 'static,
2663 R: debug::ToDebugRanges,
2664 V: std::fmt::Debug,
2665 {
2666 let ranges = ranges
2667 .to_debug_ranges(self)
2668 .into_iter()
2669 .map(|range| self.anchor_after(range.start)..self.anchor_before(range.end))
2670 .collect();
2671 debug::GlobalDebugRanges::with_locked(|debug_ranges| {
2672 debug_ranges.insert(key, ranges, format!("{value:?}").into());
2673 });
2674 }
2675}
2676
2677struct RopeBuilder<'a> {
2678 old_visible_cursor: rope::Cursor<'a>,
2679 old_deleted_cursor: rope::Cursor<'a>,
2680 new_visible: Rope,
2681 new_deleted: Rope,
2682}
2683
2684impl<'a> RopeBuilder<'a> {
2685 fn new(old_visible_cursor: rope::Cursor<'a>, old_deleted_cursor: rope::Cursor<'a>) -> Self {
2686 Self {
2687 old_visible_cursor,
2688 old_deleted_cursor,
2689 new_visible: Rope::new(),
2690 new_deleted: Rope::new(),
2691 }
2692 }
2693
2694 fn append(&mut self, len: FragmentTextSummary) {
2695 self.push(len.visible, true, true);
2696 self.push(len.deleted, false, false);
2697 }
2698
2699 fn push_fragment(&mut self, fragment: &Fragment, was_visible: bool) {
2700 debug_assert!(fragment.len > 0);
2701 self.push(fragment.len, was_visible, fragment.visible)
2702 }
2703
2704 fn push(&mut self, len: usize, was_visible: bool, is_visible: bool) {
2705 let text = if was_visible {
2706 self.old_visible_cursor
2707 .slice(self.old_visible_cursor.offset() + len)
2708 } else {
2709 self.old_deleted_cursor
2710 .slice(self.old_deleted_cursor.offset() + len)
2711 };
2712 if is_visible {
2713 self.new_visible.append(text);
2714 } else {
2715 self.new_deleted.append(text);
2716 }
2717 }
2718
2719 fn push_str(&mut self, text: &str) {
2720 self.new_visible.push(text);
2721 }
2722
2723 fn finish(mut self) -> (Rope, Rope) {
2724 self.new_visible.append(self.old_visible_cursor.suffix());
2725 self.new_deleted.append(self.old_deleted_cursor.suffix());
2726 (self.new_visible, self.new_deleted)
2727 }
2728}
2729
2730impl<D: TextDimension + Ord, F: FnMut(&FragmentSummary) -> bool> Iterator for Edits<'_, D, F> {
2731 type Item = (Edit<D>, Range<Anchor>);
2732
2733 fn next(&mut self) -> Option<Self::Item> {
2734 let mut pending_edit: Option<Self::Item> = None;
2735 let cursor = self.fragments_cursor.as_mut()?;
2736
2737 while let Some(fragment) = cursor.item() {
2738 if fragment.id < *self.range.start.0 {
2739 cursor.next();
2740 continue;
2741 } else if fragment.id > *self.range.end.0 {
2742 break;
2743 }
2744
2745 if cursor.start().visible > self.visible_cursor.offset() {
2746 let summary = self.visible_cursor.summary(cursor.start().visible);
2747 self.old_end.add_assign(&summary);
2748 self.new_end.add_assign(&summary);
2749 }
2750
2751 if pending_edit
2752 .as_ref()
2753 .is_some_and(|(change, _)| change.new.end < self.new_end)
2754 {
2755 break;
2756 }
2757
2758 let start_anchor = Anchor {
2759 timestamp: fragment.timestamp,
2760 offset: fragment.insertion_offset,
2761 bias: Bias::Right,
2762 buffer_id: Some(self.buffer_id),
2763 };
2764 let end_anchor = Anchor {
2765 timestamp: fragment.timestamp,
2766 offset: fragment.insertion_offset + fragment.len,
2767 bias: Bias::Left,
2768 buffer_id: Some(self.buffer_id),
2769 };
2770
2771 if !fragment.was_visible(self.since, self.undos) && fragment.visible {
2772 let mut visible_end = cursor.end().visible;
2773 if fragment.id == *self.range.end.0 {
2774 visible_end = cmp::min(
2775 visible_end,
2776 cursor.start().visible + (self.range.end.1 - fragment.insertion_offset),
2777 );
2778 }
2779
2780 let fragment_summary = self.visible_cursor.summary(visible_end);
2781 let mut new_end = self.new_end;
2782 new_end.add_assign(&fragment_summary);
2783 if let Some((edit, range)) = pending_edit.as_mut() {
2784 edit.new.end = new_end;
2785 range.end = end_anchor;
2786 } else {
2787 pending_edit = Some((
2788 Edit {
2789 old: self.old_end..self.old_end,
2790 new: self.new_end..new_end,
2791 },
2792 start_anchor..end_anchor,
2793 ));
2794 }
2795
2796 self.new_end = new_end;
2797 } else if fragment.was_visible(self.since, self.undos) && !fragment.visible {
2798 let mut deleted_end = cursor.end().deleted;
2799 if fragment.id == *self.range.end.0 {
2800 deleted_end = cmp::min(
2801 deleted_end,
2802 cursor.start().deleted + (self.range.end.1 - fragment.insertion_offset),
2803 );
2804 }
2805
2806 if cursor.start().deleted > self.deleted_cursor.offset() {
2807 self.deleted_cursor.seek_forward(cursor.start().deleted);
2808 }
2809 let fragment_summary = self.deleted_cursor.summary(deleted_end);
2810 let mut old_end = self.old_end;
2811 old_end.add_assign(&fragment_summary);
2812 if let Some((edit, range)) = pending_edit.as_mut() {
2813 edit.old.end = old_end;
2814 range.end = end_anchor;
2815 } else {
2816 pending_edit = Some((
2817 Edit {
2818 old: self.old_end..old_end,
2819 new: self.new_end..self.new_end,
2820 },
2821 start_anchor..end_anchor,
2822 ));
2823 }
2824
2825 self.old_end = old_end;
2826 }
2827
2828 cursor.next();
2829 }
2830
2831 pending_edit
2832 }
2833}
2834
2835impl Fragment {
2836 fn is_visible(&self, undos: &UndoMap) -> bool {
2837 !undos.is_undone(self.timestamp) && self.deletions.iter().all(|d| undos.is_undone(*d))
2838 }
2839
2840 fn was_visible(&self, version: &clock::Global, undos: &UndoMap) -> bool {
2841 (version.observed(self.timestamp) && !undos.was_undone(self.timestamp, version))
2842 && self
2843 .deletions
2844 .iter()
2845 .all(|d| !version.observed(*d) || undos.was_undone(*d, version))
2846 }
2847}
2848
2849impl sum_tree::Item for Fragment {
2850 type Summary = FragmentSummary;
2851
2852 fn summary(&self, _cx: &Option<clock::Global>) -> Self::Summary {
2853 let mut max_version = clock::Global::new();
2854 max_version.observe(self.timestamp);
2855 for deletion in &self.deletions {
2856 max_version.observe(*deletion);
2857 }
2858 max_version.join(&self.max_undos);
2859
2860 let mut min_insertion_version = clock::Global::new();
2861 min_insertion_version.observe(self.timestamp);
2862 let max_insertion_version = min_insertion_version.clone();
2863 if self.visible {
2864 FragmentSummary {
2865 max_id: self.id.clone(),
2866 text: FragmentTextSummary {
2867 visible: self.len,
2868 deleted: 0,
2869 },
2870 max_version,
2871 min_insertion_version,
2872 max_insertion_version,
2873 }
2874 } else {
2875 FragmentSummary {
2876 max_id: self.id.clone(),
2877 text: FragmentTextSummary {
2878 visible: 0,
2879 deleted: self.len,
2880 },
2881 max_version,
2882 min_insertion_version,
2883 max_insertion_version,
2884 }
2885 }
2886 }
2887}
2888
2889impl sum_tree::Summary for FragmentSummary {
2890 type Context<'a> = &'a Option<clock::Global>;
2891
2892 fn zero(_cx: Self::Context<'_>) -> Self {
2893 Default::default()
2894 }
2895
2896 fn add_summary(&mut self, other: &Self, _: Self::Context<'_>) {
2897 self.max_id.assign(&other.max_id);
2898 self.text.visible += &other.text.visible;
2899 self.text.deleted += &other.text.deleted;
2900 self.max_version.join(&other.max_version);
2901 self.min_insertion_version
2902 .meet(&other.min_insertion_version);
2903 self.max_insertion_version
2904 .join(&other.max_insertion_version);
2905 }
2906}
2907
2908impl Default for FragmentSummary {
2909 fn default() -> Self {
2910 FragmentSummary {
2911 max_id: Locator::min(),
2912 text: FragmentTextSummary::default(),
2913 max_version: clock::Global::new(),
2914 min_insertion_version: clock::Global::new(),
2915 max_insertion_version: clock::Global::new(),
2916 }
2917 }
2918}
2919
2920impl sum_tree::Item for InsertionFragment {
2921 type Summary = InsertionFragmentKey;
2922
2923 fn summary(&self, _cx: ()) -> Self::Summary {
2924 InsertionFragmentKey {
2925 timestamp: self.timestamp,
2926 split_offset: self.split_offset,
2927 }
2928 }
2929}
2930
2931impl sum_tree::KeyedItem for InsertionFragment {
2932 type Key = InsertionFragmentKey;
2933
2934 fn key(&self) -> Self::Key {
2935 sum_tree::Item::summary(self, ())
2936 }
2937}
2938
2939impl InsertionFragment {
2940 fn new(fragment: &Fragment) -> Self {
2941 Self {
2942 timestamp: fragment.timestamp,
2943 split_offset: fragment.insertion_offset,
2944 fragment_id: fragment.id.clone(),
2945 }
2946 }
2947
2948 fn insert_new(fragment: &Fragment) -> sum_tree::Edit<Self> {
2949 sum_tree::Edit::Insert(Self::new(fragment))
2950 }
2951}
2952
2953impl sum_tree::ContextLessSummary for InsertionFragmentKey {
2954 fn zero() -> Self {
2955 InsertionFragmentKey {
2956 timestamp: Lamport::MIN,
2957 split_offset: 0,
2958 }
2959 }
2960
2961 fn add_summary(&mut self, summary: &Self) {
2962 *self = *summary;
2963 }
2964}
2965
2966#[derive(Copy, Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
2967pub struct FullOffset(pub usize);
2968
2969impl ops::AddAssign<usize> for FullOffset {
2970 fn add_assign(&mut self, rhs: usize) {
2971 self.0 += rhs;
2972 }
2973}
2974
2975impl ops::Add<usize> for FullOffset {
2976 type Output = Self;
2977
2978 fn add(mut self, rhs: usize) -> Self::Output {
2979 self += rhs;
2980 self
2981 }
2982}
2983
2984impl ops::Sub for FullOffset {
2985 type Output = usize;
2986
2987 fn sub(self, rhs: Self) -> Self::Output {
2988 self.0 - rhs.0
2989 }
2990}
2991
2992impl sum_tree::Dimension<'_, FragmentSummary> for usize {
2993 fn zero(_: &Option<clock::Global>) -> Self {
2994 Default::default()
2995 }
2996
2997 fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
2998 *self += summary.text.visible;
2999 }
3000}
3001
3002impl sum_tree::Dimension<'_, FragmentSummary> for FullOffset {
3003 fn zero(_: &Option<clock::Global>) -> Self {
3004 Default::default()
3005 }
3006
3007 fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
3008 self.0 += summary.text.visible + summary.text.deleted;
3009 }
3010}
3011
3012impl<'a> sum_tree::Dimension<'a, FragmentSummary> for Option<&'a Locator> {
3013 fn zero(_: &Option<clock::Global>) -> Self {
3014 Default::default()
3015 }
3016
3017 fn add_summary(&mut self, summary: &'a FragmentSummary, _: &Option<clock::Global>) {
3018 *self = Some(&summary.max_id);
3019 }
3020}
3021
3022impl sum_tree::SeekTarget<'_, FragmentSummary, FragmentTextSummary> for usize {
3023 fn cmp(
3024 &self,
3025 cursor_location: &FragmentTextSummary,
3026 _: &Option<clock::Global>,
3027 ) -> cmp::Ordering {
3028 Ord::cmp(self, &cursor_location.visible)
3029 }
3030}
3031
3032#[derive(Copy, Clone, Debug, Eq, PartialEq)]
3033enum VersionedFullOffset {
3034 Offset(FullOffset),
3035 Invalid,
3036}
3037
3038impl VersionedFullOffset {
3039 fn full_offset(&self) -> FullOffset {
3040 if let Self::Offset(position) = self {
3041 *position
3042 } else {
3043 panic!("invalid version")
3044 }
3045 }
3046}
3047
3048impl Default for VersionedFullOffset {
3049 fn default() -> Self {
3050 Self::Offset(Default::default())
3051 }
3052}
3053
3054impl<'a> sum_tree::Dimension<'a, FragmentSummary> for VersionedFullOffset {
3055 fn zero(_cx: &Option<clock::Global>) -> Self {
3056 Default::default()
3057 }
3058
3059 fn add_summary(&mut self, summary: &'a FragmentSummary, cx: &Option<clock::Global>) {
3060 if let Self::Offset(offset) = self {
3061 let version = cx.as_ref().unwrap();
3062 if version.observed_all(&summary.max_insertion_version) {
3063 *offset += summary.text.visible + summary.text.deleted;
3064 } else if version.observed_any(&summary.min_insertion_version) {
3065 *self = Self::Invalid;
3066 }
3067 }
3068 }
3069}
3070
3071impl sum_tree::SeekTarget<'_, FragmentSummary, Self> for VersionedFullOffset {
3072 fn cmp(&self, cursor_position: &Self, _: &Option<clock::Global>) -> cmp::Ordering {
3073 match (self, cursor_position) {
3074 (Self::Offset(a), Self::Offset(b)) => Ord::cmp(a, b),
3075 (Self::Offset(_), Self::Invalid) => cmp::Ordering::Less,
3076 (Self::Invalid, _) => unreachable!(),
3077 }
3078 }
3079}
3080
3081impl Operation {
3082 fn replica_id(&self) -> ReplicaId {
3083 operation_queue::Operation::lamport_timestamp(self).replica_id
3084 }
3085
3086 pub fn timestamp(&self) -> clock::Lamport {
3087 match self {
3088 Operation::Edit(edit) => edit.timestamp,
3089 Operation::Undo(undo) => undo.timestamp,
3090 }
3091 }
3092
3093 pub fn as_edit(&self) -> Option<&EditOperation> {
3094 match self {
3095 Operation::Edit(edit) => Some(edit),
3096 _ => None,
3097 }
3098 }
3099
3100 pub fn is_edit(&self) -> bool {
3101 matches!(self, Operation::Edit { .. })
3102 }
3103}
3104
3105impl operation_queue::Operation for Operation {
3106 fn lamport_timestamp(&self) -> clock::Lamport {
3107 match self {
3108 Operation::Edit(edit) => edit.timestamp,
3109 Operation::Undo(undo) => undo.timestamp,
3110 }
3111 }
3112}
3113
3114pub trait ToOffset {
3115 fn to_offset(&self, snapshot: &BufferSnapshot) -> usize;
3116 /// Turns this point into the next offset in the buffer that comes after this, respecting utf8 boundaries.
3117 fn to_next_offset(&self, snapshot: &BufferSnapshot) -> usize {
3118 snapshot
3119 .visible_text
3120 .ceil_char_boundary(self.to_offset(snapshot) + 1)
3121 }
3122 /// Turns this point into the previous offset in the buffer that comes before this, respecting utf8 boundaries.
3123 fn to_previous_offset(&self, snapshot: &BufferSnapshot) -> usize {
3124 snapshot
3125 .visible_text
3126 .floor_char_boundary(self.to_offset(snapshot).saturating_sub(1))
3127 }
3128}
3129
3130impl ToOffset for Point {
3131 #[inline]
3132 fn to_offset(&self, snapshot: &BufferSnapshot) -> usize {
3133 snapshot.point_to_offset(*self)
3134 }
3135}
3136
3137impl ToOffset for usize {
3138 fn to_offset(&self, snapshot: &BufferSnapshot) -> usize {
3139 if cfg!(debug_assertions) {
3140 snapshot.as_rope().assert_char_boundary(*self);
3141 }
3142 *self
3143 }
3144}
3145
3146impl ToOffset for Anchor {
3147 #[inline]
3148 fn to_offset(&self, snapshot: &BufferSnapshot) -> usize {
3149 snapshot.summary_for_anchor(self)
3150 }
3151}
3152
3153impl<T: ToOffset> ToOffset for &T {
3154 #[inline]
3155 fn to_offset(&self, content: &BufferSnapshot) -> usize {
3156 (*self).to_offset(content)
3157 }
3158}
3159
3160impl ToOffset for PointUtf16 {
3161 #[inline]
3162 fn to_offset(&self, snapshot: &BufferSnapshot) -> usize {
3163 snapshot.point_utf16_to_offset(*self)
3164 }
3165}
3166
3167impl ToOffset for Unclipped<PointUtf16> {
3168 #[inline]
3169 fn to_offset(&self, snapshot: &BufferSnapshot) -> usize {
3170 snapshot.unclipped_point_utf16_to_offset(*self)
3171 }
3172}
3173
3174pub trait ToPoint {
3175 fn to_point(&self, snapshot: &BufferSnapshot) -> Point;
3176}
3177
3178impl ToPoint for Anchor {
3179 #[inline]
3180 fn to_point(&self, snapshot: &BufferSnapshot) -> Point {
3181 snapshot.summary_for_anchor(self)
3182 }
3183}
3184
3185impl ToPoint for usize {
3186 #[inline]
3187 fn to_point(&self, snapshot: &BufferSnapshot) -> Point {
3188 snapshot.offset_to_point(*self)
3189 }
3190}
3191
3192impl ToPoint for Point {
3193 #[inline]
3194 fn to_point(&self, _: &BufferSnapshot) -> Point {
3195 *self
3196 }
3197}
3198
3199impl ToPoint for Unclipped<PointUtf16> {
3200 #[inline]
3201 fn to_point(&self, snapshot: &BufferSnapshot) -> Point {
3202 snapshot.unclipped_point_utf16_to_point(*self)
3203 }
3204}
3205
3206pub trait ToPointUtf16 {
3207 fn to_point_utf16(&self, snapshot: &BufferSnapshot) -> PointUtf16;
3208}
3209
3210impl ToPointUtf16 for Anchor {
3211 #[inline]
3212 fn to_point_utf16(&self, snapshot: &BufferSnapshot) -> PointUtf16 {
3213 snapshot.summary_for_anchor(self)
3214 }
3215}
3216
3217impl ToPointUtf16 for usize {
3218 #[inline]
3219 fn to_point_utf16(&self, snapshot: &BufferSnapshot) -> PointUtf16 {
3220 snapshot.offset_to_point_utf16(*self)
3221 }
3222}
3223
3224impl ToPointUtf16 for PointUtf16 {
3225 #[inline]
3226 fn to_point_utf16(&self, _: &BufferSnapshot) -> PointUtf16 {
3227 *self
3228 }
3229}
3230
3231impl ToPointUtf16 for Point {
3232 #[inline]
3233 fn to_point_utf16(&self, snapshot: &BufferSnapshot) -> PointUtf16 {
3234 snapshot.point_to_point_utf16(*self)
3235 }
3236}
3237
3238pub trait ToOffsetUtf16 {
3239 fn to_offset_utf16(&self, snapshot: &BufferSnapshot) -> OffsetUtf16;
3240}
3241
3242impl ToOffsetUtf16 for Anchor {
3243 #[inline]
3244 fn to_offset_utf16(&self, snapshot: &BufferSnapshot) -> OffsetUtf16 {
3245 snapshot.summary_for_anchor(self)
3246 }
3247}
3248
3249impl ToOffsetUtf16 for usize {
3250 #[inline]
3251 fn to_offset_utf16(&self, snapshot: &BufferSnapshot) -> OffsetUtf16 {
3252 snapshot.offset_to_offset_utf16(*self)
3253 }
3254}
3255
3256impl ToOffsetUtf16 for OffsetUtf16 {
3257 #[inline]
3258 fn to_offset_utf16(&self, _snapshot: &BufferSnapshot) -> OffsetUtf16 {
3259 *self
3260 }
3261}
3262
3263pub trait FromAnchor {
3264 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self;
3265}
3266
3267impl FromAnchor for Anchor {
3268 #[inline]
3269 fn from_anchor(anchor: &Anchor, _snapshot: &BufferSnapshot) -> Self {
3270 *anchor
3271 }
3272}
3273
3274impl FromAnchor for Point {
3275 #[inline]
3276 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
3277 snapshot.summary_for_anchor(anchor)
3278 }
3279}
3280
3281impl FromAnchor for PointUtf16 {
3282 #[inline]
3283 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
3284 snapshot.summary_for_anchor(anchor)
3285 }
3286}
3287
3288impl FromAnchor for usize {
3289 #[inline]
3290 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
3291 snapshot.summary_for_anchor(anchor)
3292 }
3293}
3294
3295#[derive(Clone, Copy, Debug, PartialEq)]
3296pub enum LineEnding {
3297 Unix,
3298 Windows,
3299}
3300
3301impl Default for LineEnding {
3302 fn default() -> Self {
3303 #[cfg(unix)]
3304 return Self::Unix;
3305
3306 #[cfg(not(unix))]
3307 return Self::Windows;
3308 }
3309}
3310
3311impl LineEnding {
3312 pub fn as_str(&self) -> &'static str {
3313 match self {
3314 LineEnding::Unix => "\n",
3315 LineEnding::Windows => "\r\n",
3316 }
3317 }
3318
3319 pub fn label(&self) -> &'static str {
3320 match self {
3321 LineEnding::Unix => "LF",
3322 LineEnding::Windows => "CRLF",
3323 }
3324 }
3325
3326 pub fn detect(text: &str) -> Self {
3327 let mut max_ix = cmp::min(text.len(), 1000);
3328 while !text.is_char_boundary(max_ix) {
3329 max_ix -= 1;
3330 }
3331
3332 if let Some(ix) = text[..max_ix].find(['\n']) {
3333 if ix > 0 && text.as_bytes()[ix - 1] == b'\r' {
3334 Self::Windows
3335 } else {
3336 Self::Unix
3337 }
3338 } else {
3339 Self::default()
3340 }
3341 }
3342
3343 pub fn normalize(text: &mut String) {
3344 if let Cow::Owned(replaced) = LINE_SEPARATORS_REGEX.replace_all(text, "\n") {
3345 *text = replaced;
3346 }
3347 }
3348
3349 pub fn normalize_arc(text: Arc<str>) -> Arc<str> {
3350 if let Cow::Owned(replaced) = LINE_SEPARATORS_REGEX.replace_all(&text, "\n") {
3351 replaced.into()
3352 } else {
3353 text
3354 }
3355 }
3356
3357 pub fn normalize_cow(text: Cow<str>) -> Cow<str> {
3358 if let Cow::Owned(replaced) = LINE_SEPARATORS_REGEX.replace_all(&text, "\n") {
3359 replaced.into()
3360 } else {
3361 text
3362 }
3363 }
3364}
3365
3366#[cfg(debug_assertions)]
3367pub mod debug {
3368 use super::*;
3369 use parking_lot::Mutex;
3370 use std::any::TypeId;
3371 use std::hash::{Hash, Hasher};
3372
3373 static GLOBAL_DEBUG_RANGES: Mutex<Option<GlobalDebugRanges>> = Mutex::new(None);
3374
3375 pub struct GlobalDebugRanges {
3376 pub ranges: Vec<DebugRange>,
3377 key_to_occurrence_index: HashMap<Key, usize>,
3378 next_occurrence_index: usize,
3379 }
3380
3381 pub struct DebugRange {
3382 key: Key,
3383 pub ranges: Vec<Range<Anchor>>,
3384 pub value: Arc<str>,
3385 pub occurrence_index: usize,
3386 }
3387
3388 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
3389 struct Key {
3390 type_id: TypeId,
3391 hash: u64,
3392 }
3393
3394 impl GlobalDebugRanges {
3395 pub fn with_locked<R>(f: impl FnOnce(&mut Self) -> R) -> R {
3396 let mut state = GLOBAL_DEBUG_RANGES.lock();
3397 if state.is_none() {
3398 *state = Some(GlobalDebugRanges {
3399 ranges: Vec::new(),
3400 key_to_occurrence_index: HashMap::default(),
3401 next_occurrence_index: 0,
3402 });
3403 }
3404 if let Some(global_debug_ranges) = state.as_mut() {
3405 f(global_debug_ranges)
3406 } else {
3407 unreachable!()
3408 }
3409 }
3410
3411 pub fn insert<K: Hash + 'static>(
3412 &mut self,
3413 key: &K,
3414 ranges: Vec<Range<Anchor>>,
3415 value: Arc<str>,
3416 ) {
3417 let occurrence_index = *self
3418 .key_to_occurrence_index
3419 .entry(Key::new(key))
3420 .or_insert_with(|| {
3421 let occurrence_index = self.next_occurrence_index;
3422 self.next_occurrence_index += 1;
3423 occurrence_index
3424 });
3425 let key = Key::new(key);
3426 let existing = self
3427 .ranges
3428 .iter()
3429 .enumerate()
3430 .rfind(|(_, existing)| existing.key == key);
3431 if let Some((existing_ix, _)) = existing {
3432 self.ranges.remove(existing_ix);
3433 }
3434 self.ranges.push(DebugRange {
3435 ranges,
3436 key,
3437 value,
3438 occurrence_index,
3439 });
3440 }
3441
3442 pub fn remove<K: Hash + 'static>(&mut self, key: &K) {
3443 self.remove_impl(&Key::new(key));
3444 }
3445
3446 fn remove_impl(&mut self, key: &Key) {
3447 let existing = self
3448 .ranges
3449 .iter()
3450 .enumerate()
3451 .rfind(|(_, existing)| &existing.key == key);
3452 if let Some((existing_ix, _)) = existing {
3453 self.ranges.remove(existing_ix);
3454 }
3455 }
3456
3457 pub fn remove_all_with_key_type<K: 'static>(&mut self) {
3458 self.ranges
3459 .retain(|item| item.key.type_id != TypeId::of::<K>());
3460 }
3461 }
3462
3463 impl Key {
3464 fn new<K: Hash + 'static>(key: &K) -> Self {
3465 let type_id = TypeId::of::<K>();
3466 let mut hasher = collections::FxHasher::default();
3467 key.hash(&mut hasher);
3468 Key {
3469 type_id,
3470 hash: hasher.finish(),
3471 }
3472 }
3473 }
3474
3475 pub trait ToDebugRanges {
3476 fn to_debug_ranges(&self, snapshot: &BufferSnapshot) -> Vec<Range<usize>>;
3477 }
3478
3479 impl<T: ToOffset> ToDebugRanges for T {
3480 fn to_debug_ranges(&self, snapshot: &BufferSnapshot) -> Vec<Range<usize>> {
3481 [self.to_offset(snapshot)].to_debug_ranges(snapshot)
3482 }
3483 }
3484
3485 impl<T: ToOffset + Clone> ToDebugRanges for Range<T> {
3486 fn to_debug_ranges(&self, snapshot: &BufferSnapshot) -> Vec<Range<usize>> {
3487 [self.clone()].to_debug_ranges(snapshot)
3488 }
3489 }
3490
3491 impl<T: ToOffset> ToDebugRanges for Vec<T> {
3492 fn to_debug_ranges(&self, snapshot: &BufferSnapshot) -> Vec<Range<usize>> {
3493 self.as_slice().to_debug_ranges(snapshot)
3494 }
3495 }
3496
3497 impl<T: ToOffset> ToDebugRanges for Vec<Range<T>> {
3498 fn to_debug_ranges(&self, snapshot: &BufferSnapshot) -> Vec<Range<usize>> {
3499 self.as_slice().to_debug_ranges(snapshot)
3500 }
3501 }
3502
3503 impl<T: ToOffset> ToDebugRanges for [T] {
3504 fn to_debug_ranges(&self, snapshot: &BufferSnapshot) -> Vec<Range<usize>> {
3505 self.iter()
3506 .map(|item| {
3507 let offset = item.to_offset(snapshot);
3508 offset..offset
3509 })
3510 .collect()
3511 }
3512 }
3513
3514 impl<T: ToOffset> ToDebugRanges for [Range<T>] {
3515 fn to_debug_ranges(&self, snapshot: &BufferSnapshot) -> Vec<Range<usize>> {
3516 self.iter()
3517 .map(|range| range.start.to_offset(snapshot)..range.end.to_offset(snapshot))
3518 .collect()
3519 }
3520 }
3521}