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