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