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