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