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