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