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