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_edit_ids<'a, D>(
1502 &'a self,
1503 edit_ids: impl IntoIterator<Item = &'a clock::Lamport>,
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(edit_ids.into_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 edited_ranges_for_transaction<'a, D>(
1551 &'a self,
1552 transaction: &'a Transaction,
1553 ) -> impl 'a + Iterator<Item = Range<D>>
1554 where
1555 D: TextDimension,
1556 {
1557 self.edited_ranges_for_edit_ids(&transaction.edit_ids)
1558 }
1559
1560 pub fn subscribe(&mut self) -> Subscription {
1561 self.subscriptions.subscribe()
1562 }
1563
1564 pub fn wait_for_edits(
1565 &mut self,
1566 edit_ids: impl IntoIterator<Item = clock::Lamport>,
1567 ) -> impl 'static + Future<Output = Result<()>> {
1568 let mut futures = Vec::new();
1569 for edit_id in edit_ids {
1570 if !self.version.observed(edit_id) {
1571 let (tx, rx) = oneshot::channel();
1572 self.edit_id_resolvers.entry(edit_id).or_default().push(tx);
1573 futures.push(rx);
1574 }
1575 }
1576
1577 async move {
1578 for mut future in futures {
1579 if future.recv().await.is_none() {
1580 Err(anyhow!("gave up waiting for edits"))?;
1581 }
1582 }
1583 Ok(())
1584 }
1585 }
1586
1587 pub fn wait_for_anchors(
1588 &mut self,
1589 anchors: impl IntoIterator<Item = Anchor>,
1590 ) -> impl 'static + Future<Output = Result<()>> {
1591 let mut futures = Vec::new();
1592 for anchor in anchors {
1593 if !self.version.observed(anchor.timestamp)
1594 && anchor != Anchor::MAX
1595 && anchor != Anchor::MIN
1596 {
1597 let (tx, rx) = oneshot::channel();
1598 self.edit_id_resolvers
1599 .entry(anchor.timestamp)
1600 .or_default()
1601 .push(tx);
1602 futures.push(rx);
1603 }
1604 }
1605
1606 async move {
1607 for mut future in futures {
1608 if future.recv().await.is_none() {
1609 Err(anyhow!("gave up waiting for anchors"))?;
1610 }
1611 }
1612 Ok(())
1613 }
1614 }
1615
1616 pub fn wait_for_version(&mut self, version: clock::Global) -> impl Future<Output = Result<()>> {
1617 let mut rx = None;
1618 if !self.snapshot.version.observed_all(&version) {
1619 let channel = oneshot::channel();
1620 self.wait_for_version_txs.push((version, channel.0));
1621 rx = Some(channel.1);
1622 }
1623 async move {
1624 if let Some(mut rx) = rx {
1625 if rx.recv().await.is_none() {
1626 Err(anyhow!("gave up waiting for version"))?;
1627 }
1628 }
1629 Ok(())
1630 }
1631 }
1632
1633 pub fn give_up_waiting(&mut self) {
1634 self.edit_id_resolvers.clear();
1635 self.wait_for_version_txs.clear();
1636 }
1637
1638 fn resolve_edit(&mut self, edit_id: clock::Lamport) {
1639 for mut tx in self
1640 .edit_id_resolvers
1641 .remove(&edit_id)
1642 .into_iter()
1643 .flatten()
1644 {
1645 tx.try_send(()).ok();
1646 }
1647 }
1648}
1649
1650#[cfg(any(test, feature = "test-support"))]
1651impl Buffer {
1652 pub fn edit_via_marked_text(&mut self, marked_string: &str) {
1653 let edits = self.edits_for_marked_text(marked_string);
1654 self.edit(edits);
1655 }
1656
1657 pub fn edits_for_marked_text(&self, marked_string: &str) -> Vec<(Range<usize>, String)> {
1658 let old_text = self.text();
1659 let (new_text, mut ranges) = util::test::marked_text_ranges(marked_string, false);
1660 if ranges.is_empty() {
1661 ranges.push(0..new_text.len());
1662 }
1663
1664 assert_eq!(
1665 old_text[..ranges[0].start],
1666 new_text[..ranges[0].start],
1667 "invalid edit"
1668 );
1669
1670 let mut delta = 0;
1671 let mut edits = Vec::new();
1672 let mut ranges = ranges.into_iter().peekable();
1673
1674 while let Some(inserted_range) = ranges.next() {
1675 let new_start = inserted_range.start;
1676 let old_start = (new_start as isize - delta) as usize;
1677
1678 let following_text = if let Some(next_range) = ranges.peek() {
1679 &new_text[inserted_range.end..next_range.start]
1680 } else {
1681 &new_text[inserted_range.end..]
1682 };
1683
1684 let inserted_len = inserted_range.len();
1685 let deleted_len = old_text[old_start..]
1686 .find(following_text)
1687 .expect("invalid edit");
1688
1689 let old_range = old_start..old_start + deleted_len;
1690 edits.push((old_range, new_text[inserted_range].to_string()));
1691 delta += inserted_len as isize - deleted_len as isize;
1692 }
1693
1694 assert_eq!(
1695 old_text.len() as isize + delta,
1696 new_text.len() as isize,
1697 "invalid edit"
1698 );
1699
1700 edits
1701 }
1702
1703 pub fn check_invariants(&self) {
1704 // Ensure every fragment is ordered by locator in the fragment tree and corresponds
1705 // to an insertion fragment in the insertions tree.
1706 let mut prev_fragment_id = Locator::min();
1707 for fragment in self.snapshot.fragments.items(&None) {
1708 assert!(fragment.id > prev_fragment_id);
1709 prev_fragment_id = fragment.id.clone();
1710
1711 let insertion_fragment = self
1712 .snapshot
1713 .insertions
1714 .get(
1715 &InsertionFragmentKey {
1716 timestamp: fragment.timestamp,
1717 split_offset: fragment.insertion_offset,
1718 },
1719 &(),
1720 )
1721 .unwrap();
1722 assert_eq!(
1723 insertion_fragment.fragment_id, fragment.id,
1724 "fragment: {:?}\ninsertion: {:?}",
1725 fragment, insertion_fragment
1726 );
1727 }
1728
1729 let mut cursor = self.snapshot.fragments.cursor::<Option<&Locator>>(&None);
1730 for insertion_fragment in self.snapshot.insertions.cursor::<()>(&()) {
1731 cursor.seek(&Some(&insertion_fragment.fragment_id), Bias::Left, &None);
1732 let fragment = cursor.item().unwrap();
1733 assert_eq!(insertion_fragment.fragment_id, fragment.id);
1734 assert_eq!(insertion_fragment.split_offset, fragment.insertion_offset);
1735 }
1736
1737 let fragment_summary = self.snapshot.fragments.summary();
1738 assert_eq!(
1739 fragment_summary.text.visible,
1740 self.snapshot.visible_text.len()
1741 );
1742 assert_eq!(
1743 fragment_summary.text.deleted,
1744 self.snapshot.deleted_text.len()
1745 );
1746
1747 assert!(!self.text().contains("\r\n"));
1748 }
1749
1750 pub fn set_group_interval(&mut self, group_interval: Duration) {
1751 self.history.group_interval = group_interval;
1752 }
1753
1754 pub fn random_byte_range(&self, start_offset: usize, rng: &mut impl rand::Rng) -> Range<usize> {
1755 let end = self.clip_offset(rng.gen_range(start_offset..=self.len()), Bias::Right);
1756 let start = self.clip_offset(rng.gen_range(start_offset..=end), Bias::Right);
1757 start..end
1758 }
1759
1760 pub fn get_random_edits<T>(
1761 &self,
1762 rng: &mut T,
1763 edit_count: usize,
1764 ) -> Vec<(Range<usize>, Arc<str>)>
1765 where
1766 T: rand::Rng,
1767 {
1768 let mut edits: Vec<(Range<usize>, Arc<str>)> = Vec::new();
1769 let mut last_end = None;
1770 for _ in 0..edit_count {
1771 if last_end.map_or(false, |last_end| last_end >= self.len()) {
1772 break;
1773 }
1774 let new_start = last_end.map_or(0, |last_end| last_end + 1);
1775 let range = self.random_byte_range(new_start, rng);
1776 last_end = Some(range.end);
1777
1778 let new_text_len = rng.gen_range(0..10);
1779 let new_text: String = RandomCharIter::new(&mut *rng).take(new_text_len).collect();
1780
1781 edits.push((range, new_text.into()));
1782 }
1783 edits
1784 }
1785
1786 pub fn randomly_edit<T>(
1787 &mut self,
1788 rng: &mut T,
1789 edit_count: usize,
1790 ) -> (Vec<(Range<usize>, Arc<str>)>, Operation)
1791 where
1792 T: rand::Rng,
1793 {
1794 let mut edits = self.get_random_edits(rng, edit_count);
1795 log::info!("mutating buffer {} with {:?}", self.replica_id, edits);
1796
1797 let op = self.edit(edits.iter().cloned());
1798 if let Operation::Edit(edit) = &op {
1799 assert_eq!(edits.len(), edit.new_text.len());
1800 for (edit, new_text) in edits.iter_mut().zip(&edit.new_text) {
1801 edit.1 = new_text.clone();
1802 }
1803 } else {
1804 unreachable!()
1805 }
1806
1807 (edits, op)
1808 }
1809
1810 pub fn randomly_undo_redo(&mut self, rng: &mut impl rand::Rng) -> Vec<Operation> {
1811 use rand::prelude::*;
1812
1813 let mut ops = Vec::new();
1814 for _ in 0..rng.gen_range(1..=5) {
1815 if let Some(entry) = self.history.undo_stack.choose(rng) {
1816 let transaction = entry.transaction.clone();
1817 log::info!(
1818 "undoing buffer {} transaction {:?}",
1819 self.replica_id,
1820 transaction
1821 );
1822 ops.push(self.undo_or_redo(transaction));
1823 }
1824 }
1825 ops
1826 }
1827}
1828
1829impl Deref for Buffer {
1830 type Target = BufferSnapshot;
1831
1832 fn deref(&self) -> &Self::Target {
1833 &self.snapshot
1834 }
1835}
1836
1837impl BufferSnapshot {
1838 pub fn as_rope(&self) -> &Rope {
1839 &self.visible_text
1840 }
1841
1842 pub fn rope_for_version(&self, version: &clock::Global) -> Rope {
1843 let mut rope = Rope::new();
1844
1845 let mut cursor = self
1846 .fragments
1847 .filter::<_, FragmentTextSummary>(&None, move |summary| {
1848 !version.observed_all(&summary.max_version)
1849 });
1850 cursor.next(&None);
1851
1852 let mut visible_cursor = self.visible_text.cursor(0);
1853 let mut deleted_cursor = self.deleted_text.cursor(0);
1854
1855 while let Some(fragment) = cursor.item() {
1856 if cursor.start().visible > visible_cursor.offset() {
1857 let text = visible_cursor.slice(cursor.start().visible);
1858 rope.append(text);
1859 }
1860
1861 if fragment.was_visible(version, &self.undo_map) {
1862 if fragment.visible {
1863 let text = visible_cursor.slice(cursor.end(&None).visible);
1864 rope.append(text);
1865 } else {
1866 deleted_cursor.seek_forward(cursor.start().deleted);
1867 let text = deleted_cursor.slice(cursor.end(&None).deleted);
1868 rope.append(text);
1869 }
1870 } else if fragment.visible {
1871 visible_cursor.seek_forward(cursor.end(&None).visible);
1872 }
1873
1874 cursor.next(&None);
1875 }
1876
1877 if cursor.start().visible > visible_cursor.offset() {
1878 let text = visible_cursor.slice(cursor.start().visible);
1879 rope.append(text);
1880 }
1881
1882 rope
1883 }
1884
1885 pub fn remote_id(&self) -> BufferId {
1886 self.remote_id
1887 }
1888
1889 pub fn replica_id(&self) -> ReplicaId {
1890 self.replica_id
1891 }
1892
1893 pub fn row_count(&self) -> u32 {
1894 self.max_point().row + 1
1895 }
1896
1897 pub fn len(&self) -> usize {
1898 self.visible_text.len()
1899 }
1900
1901 pub fn is_empty(&self) -> bool {
1902 self.len() == 0
1903 }
1904
1905 pub fn chars(&self) -> impl Iterator<Item = char> + '_ {
1906 self.chars_at(0)
1907 }
1908
1909 pub fn chars_for_range<T: ToOffset>(&self, range: Range<T>) -> impl Iterator<Item = char> + '_ {
1910 self.text_for_range(range).flat_map(str::chars)
1911 }
1912
1913 pub fn reversed_chars_for_range<T: ToOffset>(
1914 &self,
1915 range: Range<T>,
1916 ) -> impl Iterator<Item = char> + '_ {
1917 self.reversed_chunks_in_range(range)
1918 .flat_map(|chunk| chunk.chars().rev())
1919 }
1920
1921 pub fn contains_str_at<T>(&self, position: T, needle: &str) -> bool
1922 where
1923 T: ToOffset,
1924 {
1925 let position = position.to_offset(self);
1926 position == self.clip_offset(position, Bias::Left)
1927 && self
1928 .bytes_in_range(position..self.len())
1929 .flatten()
1930 .copied()
1931 .take(needle.len())
1932 .eq(needle.bytes())
1933 }
1934
1935 pub fn common_prefix_at<T>(&self, position: T, needle: &str) -> Range<T>
1936 where
1937 T: ToOffset + TextDimension,
1938 {
1939 let offset = position.to_offset(self);
1940 let common_prefix_len = needle
1941 .char_indices()
1942 .map(|(index, _)| index)
1943 .chain([needle.len()])
1944 .take_while(|&len| len <= offset)
1945 .filter(|&len| {
1946 let left = self
1947 .chars_for_range(offset - len..offset)
1948 .flat_map(char::to_lowercase);
1949 let right = needle[..len].chars().flat_map(char::to_lowercase);
1950 left.eq(right)
1951 })
1952 .last()
1953 .unwrap_or(0);
1954 let start_offset = offset - common_prefix_len;
1955 let start = self.text_summary_for_range(0..start_offset);
1956 start..position
1957 }
1958
1959 pub fn text(&self) -> String {
1960 self.visible_text.to_string()
1961 }
1962
1963 pub fn line_ending(&self) -> LineEnding {
1964 self.line_ending
1965 }
1966
1967 pub fn deleted_text(&self) -> String {
1968 self.deleted_text.to_string()
1969 }
1970
1971 pub fn fragments(&self) -> impl Iterator<Item = &Fragment> {
1972 self.fragments.iter()
1973 }
1974
1975 pub fn text_summary(&self) -> TextSummary {
1976 self.visible_text.summary()
1977 }
1978
1979 pub fn max_point(&self) -> Point {
1980 self.visible_text.max_point()
1981 }
1982
1983 pub fn max_point_utf16(&self) -> PointUtf16 {
1984 self.visible_text.max_point_utf16()
1985 }
1986
1987 pub fn point_to_offset(&self, point: Point) -> usize {
1988 self.visible_text.point_to_offset(point)
1989 }
1990
1991 pub fn point_utf16_to_offset(&self, point: PointUtf16) -> usize {
1992 self.visible_text.point_utf16_to_offset(point)
1993 }
1994
1995 pub fn unclipped_point_utf16_to_offset(&self, point: Unclipped<PointUtf16>) -> usize {
1996 self.visible_text.unclipped_point_utf16_to_offset(point)
1997 }
1998
1999 pub fn unclipped_point_utf16_to_point(&self, point: Unclipped<PointUtf16>) -> Point {
2000 self.visible_text.unclipped_point_utf16_to_point(point)
2001 }
2002
2003 pub fn offset_utf16_to_offset(&self, offset: OffsetUtf16) -> usize {
2004 self.visible_text.offset_utf16_to_offset(offset)
2005 }
2006
2007 pub fn offset_to_offset_utf16(&self, offset: usize) -> OffsetUtf16 {
2008 self.visible_text.offset_to_offset_utf16(offset)
2009 }
2010
2011 pub fn offset_to_point(&self, offset: usize) -> Point {
2012 self.visible_text.offset_to_point(offset)
2013 }
2014
2015 pub fn offset_to_point_utf16(&self, offset: usize) -> PointUtf16 {
2016 self.visible_text.offset_to_point_utf16(offset)
2017 }
2018
2019 pub fn point_to_point_utf16(&self, point: Point) -> PointUtf16 {
2020 self.visible_text.point_to_point_utf16(point)
2021 }
2022
2023 pub fn version(&self) -> &clock::Global {
2024 &self.version
2025 }
2026
2027 pub fn chars_at<T: ToOffset>(&self, position: T) -> impl Iterator<Item = char> + '_ {
2028 let offset = position.to_offset(self);
2029 self.visible_text.chars_at(offset)
2030 }
2031
2032 pub fn reversed_chars_at<T: ToOffset>(&self, position: T) -> impl Iterator<Item = char> + '_ {
2033 let offset = position.to_offset(self);
2034 self.visible_text.reversed_chars_at(offset)
2035 }
2036
2037 pub fn reversed_chunks_in_range<T: ToOffset>(&self, range: Range<T>) -> rope::Chunks {
2038 let range = range.start.to_offset(self)..range.end.to_offset(self);
2039 self.visible_text.reversed_chunks_in_range(range)
2040 }
2041
2042 pub fn bytes_in_range<T: ToOffset>(&self, range: Range<T>) -> rope::Bytes<'_> {
2043 let start = range.start.to_offset(self);
2044 let end = range.end.to_offset(self);
2045 self.visible_text.bytes_in_range(start..end)
2046 }
2047
2048 pub fn reversed_bytes_in_range<T: ToOffset>(&self, range: Range<T>) -> rope::Bytes<'_> {
2049 let start = range.start.to_offset(self);
2050 let end = range.end.to_offset(self);
2051 self.visible_text.reversed_bytes_in_range(start..end)
2052 }
2053
2054 pub fn text_for_range<T: ToOffset>(&self, range: Range<T>) -> Chunks<'_> {
2055 let start = range.start.to_offset(self);
2056 let end = range.end.to_offset(self);
2057 self.visible_text.chunks_in_range(start..end)
2058 }
2059
2060 pub fn line_len(&self, row: u32) -> u32 {
2061 let row_start_offset = Point::new(row, 0).to_offset(self);
2062 let row_end_offset = if row >= self.max_point().row {
2063 self.len()
2064 } else {
2065 Point::new(row + 1, 0).to_offset(self) - 1
2066 };
2067 (row_end_offset - row_start_offset) as u32
2068 }
2069
2070 pub fn line_indents_in_row_range(
2071 &self,
2072 row_range: Range<u32>,
2073 ) -> impl Iterator<Item = (u32, LineIndent)> + '_ {
2074 let start = Point::new(row_range.start, 0).to_offset(self);
2075 let end = Point::new(row_range.end, self.line_len(row_range.end)).to_offset(self);
2076
2077 let mut chunks = self.as_rope().chunks_in_range(start..end);
2078 let mut row = row_range.start;
2079 let mut done = false;
2080 std::iter::from_fn(move || {
2081 if done {
2082 None
2083 } else {
2084 let indent = (row, LineIndent::from_chunks(&mut chunks));
2085 done = !chunks.next_line();
2086 row += 1;
2087 Some(indent)
2088 }
2089 })
2090 }
2091
2092 /// Returns the line indents in the given row range, exclusive of end row, in reversed order.
2093 pub fn reversed_line_indents_in_row_range(
2094 &self,
2095 row_range: Range<u32>,
2096 ) -> impl Iterator<Item = (u32, LineIndent)> + '_ {
2097 let start = Point::new(row_range.start, 0).to_offset(self);
2098
2099 let end_point;
2100 let end;
2101 if row_range.end > row_range.start {
2102 end_point = Point::new(row_range.end - 1, self.line_len(row_range.end - 1));
2103 end = end_point.to_offset(self);
2104 } else {
2105 end_point = Point::new(row_range.start, 0);
2106 end = start;
2107 };
2108
2109 let mut chunks = self.as_rope().chunks_in_range(start..end);
2110 // Move the cursor to the start of the last line if it's not empty.
2111 chunks.seek(end);
2112 if end_point.column > 0 {
2113 chunks.prev_line();
2114 }
2115
2116 let mut row = end_point.row;
2117 let mut done = false;
2118 std::iter::from_fn(move || {
2119 if done {
2120 None
2121 } else {
2122 let initial_offset = chunks.offset();
2123 let indent = (row, LineIndent::from_chunks(&mut chunks));
2124 if chunks.offset() > initial_offset {
2125 chunks.prev_line();
2126 }
2127 done = !chunks.prev_line();
2128 if !done {
2129 row -= 1;
2130 }
2131
2132 Some(indent)
2133 }
2134 })
2135 }
2136
2137 pub fn line_indent_for_row(&self, row: u32) -> LineIndent {
2138 LineIndent::from_iter(self.chars_at(Point::new(row, 0)))
2139 }
2140
2141 pub fn is_line_blank(&self, row: u32) -> bool {
2142 self.text_for_range(Point::new(row, 0)..Point::new(row, self.line_len(row)))
2143 .all(|chunk| chunk.matches(|c: char| !c.is_whitespace()).next().is_none())
2144 }
2145
2146 pub fn text_summary_for_range<D, O: ToOffset>(&self, range: Range<O>) -> D
2147 where
2148 D: TextDimension,
2149 {
2150 self.visible_text
2151 .cursor(range.start.to_offset(self))
2152 .summary(range.end.to_offset(self))
2153 }
2154
2155 pub fn summaries_for_anchors<'a, D, A>(&'a self, anchors: A) -> impl 'a + Iterator<Item = D>
2156 where
2157 D: 'a + TextDimension,
2158 A: 'a + IntoIterator<Item = &'a Anchor>,
2159 {
2160 let anchors = anchors.into_iter();
2161 self.summaries_for_anchors_with_payload::<D, _, ()>(anchors.map(|a| (a, ())))
2162 .map(|d| d.0)
2163 }
2164
2165 pub fn summaries_for_anchors_with_payload<'a, D, A, T>(
2166 &'a self,
2167 anchors: A,
2168 ) -> impl 'a + Iterator<Item = (D, T)>
2169 where
2170 D: 'a + TextDimension,
2171 A: 'a + IntoIterator<Item = (&'a Anchor, T)>,
2172 {
2173 let anchors = anchors.into_iter();
2174 let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>(&());
2175 let mut fragment_cursor = self.fragments.cursor::<(Option<&Locator>, usize)>(&None);
2176 let mut text_cursor = self.visible_text.cursor(0);
2177 let mut position = D::zero(&());
2178
2179 anchors.map(move |(anchor, payload)| {
2180 if *anchor == Anchor::MIN {
2181 return (D::zero(&()), payload);
2182 } else if *anchor == Anchor::MAX {
2183 return (D::from_text_summary(&self.visible_text.summary()), payload);
2184 }
2185
2186 let anchor_key = InsertionFragmentKey {
2187 timestamp: anchor.timestamp,
2188 split_offset: anchor.offset,
2189 };
2190 insertion_cursor.seek(&anchor_key, anchor.bias, &());
2191 if let Some(insertion) = insertion_cursor.item() {
2192 let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
2193 if comparison == Ordering::Greater
2194 || (anchor.bias == Bias::Left
2195 && comparison == Ordering::Equal
2196 && anchor.offset > 0)
2197 {
2198 insertion_cursor.prev(&());
2199 }
2200 } else {
2201 insertion_cursor.prev(&());
2202 }
2203 let insertion = insertion_cursor.item().expect("invalid insertion");
2204 assert_eq!(insertion.timestamp, anchor.timestamp, "invalid insertion");
2205
2206 fragment_cursor.seek_forward(&Some(&insertion.fragment_id), Bias::Left, &None);
2207 let fragment = fragment_cursor.item().unwrap();
2208 let mut fragment_offset = fragment_cursor.start().1;
2209 if fragment.visible {
2210 fragment_offset += anchor.offset - insertion.split_offset;
2211 }
2212
2213 position.add_assign(&text_cursor.summary(fragment_offset));
2214 (position, payload)
2215 })
2216 }
2217
2218 pub fn summary_for_anchor<D>(&self, anchor: &Anchor) -> D
2219 where
2220 D: TextDimension,
2221 {
2222 self.text_summary_for_range(0..self.offset_for_anchor(anchor))
2223 }
2224
2225 pub fn offset_for_anchor(&self, anchor: &Anchor) -> usize {
2226 if *anchor == Anchor::MIN {
2227 0
2228 } else if *anchor == Anchor::MAX {
2229 self.visible_text.len()
2230 } else {
2231 let anchor_key = InsertionFragmentKey {
2232 timestamp: anchor.timestamp,
2233 split_offset: anchor.offset,
2234 };
2235 let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>(&());
2236 insertion_cursor.seek(&anchor_key, anchor.bias, &());
2237 if let Some(insertion) = insertion_cursor.item() {
2238 let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
2239 if comparison == Ordering::Greater
2240 || (anchor.bias == Bias::Left
2241 && comparison == Ordering::Equal
2242 && anchor.offset > 0)
2243 {
2244 insertion_cursor.prev(&());
2245 }
2246 } else {
2247 insertion_cursor.prev(&());
2248 }
2249
2250 let Some(insertion) = insertion_cursor
2251 .item()
2252 .filter(|insertion| insertion.timestamp == anchor.timestamp)
2253 else {
2254 panic!(
2255 "invalid anchor {:?}. buffer id: {}, version: {:?}",
2256 anchor, self.remote_id, self.version
2257 );
2258 };
2259
2260 let mut fragment_cursor = self.fragments.cursor::<(Option<&Locator>, usize)>(&None);
2261 fragment_cursor.seek(&Some(&insertion.fragment_id), Bias::Left, &None);
2262 let fragment = fragment_cursor.item().unwrap();
2263 let mut fragment_offset = fragment_cursor.start().1;
2264 if fragment.visible {
2265 fragment_offset += anchor.offset - insertion.split_offset;
2266 }
2267 fragment_offset
2268 }
2269 }
2270
2271 fn fragment_id_for_anchor(&self, anchor: &Anchor) -> &Locator {
2272 if *anchor == Anchor::MIN {
2273 Locator::min_ref()
2274 } else if *anchor == Anchor::MAX {
2275 Locator::max_ref()
2276 } else {
2277 let anchor_key = InsertionFragmentKey {
2278 timestamp: anchor.timestamp,
2279 split_offset: anchor.offset,
2280 };
2281 let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>(&());
2282 insertion_cursor.seek(&anchor_key, anchor.bias, &());
2283 if let Some(insertion) = insertion_cursor.item() {
2284 let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
2285 if comparison == Ordering::Greater
2286 || (anchor.bias == Bias::Left
2287 && comparison == Ordering::Equal
2288 && anchor.offset > 0)
2289 {
2290 insertion_cursor.prev(&());
2291 }
2292 } else {
2293 insertion_cursor.prev(&());
2294 }
2295
2296 let Some(insertion) = insertion_cursor.item().filter(|insertion| {
2297 if cfg!(debug_assertions) {
2298 insertion.timestamp == anchor.timestamp
2299 } else {
2300 true
2301 }
2302 }) else {
2303 panic!(
2304 "invalid anchor {:?}. buffer id: {}, version: {:?}",
2305 anchor, self.remote_id, self.version
2306 );
2307 };
2308
2309 &insertion.fragment_id
2310 }
2311 }
2312
2313 pub fn anchor_before<T: ToOffset>(&self, position: T) -> Anchor {
2314 self.anchor_at(position, Bias::Left)
2315 }
2316
2317 pub fn anchor_after<T: ToOffset>(&self, position: T) -> Anchor {
2318 self.anchor_at(position, Bias::Right)
2319 }
2320
2321 pub fn anchor_at<T: ToOffset>(&self, position: T, bias: Bias) -> Anchor {
2322 self.anchor_at_offset(position.to_offset(self), bias)
2323 }
2324
2325 fn anchor_at_offset(&self, offset: usize, bias: Bias) -> Anchor {
2326 if bias == Bias::Left && offset == 0 {
2327 Anchor::MIN
2328 } else if bias == Bias::Right && offset == self.len() {
2329 Anchor::MAX
2330 } else {
2331 let mut fragment_cursor = self.fragments.cursor::<usize>(&None);
2332 fragment_cursor.seek(&offset, bias, &None);
2333 let fragment = fragment_cursor.item().unwrap();
2334 let overshoot = offset - *fragment_cursor.start();
2335 Anchor {
2336 timestamp: fragment.timestamp,
2337 offset: fragment.insertion_offset + overshoot,
2338 bias,
2339 buffer_id: Some(self.remote_id),
2340 }
2341 }
2342 }
2343
2344 pub fn can_resolve(&self, anchor: &Anchor) -> bool {
2345 *anchor == Anchor::MIN
2346 || *anchor == Anchor::MAX
2347 || (Some(self.remote_id) == anchor.buffer_id && self.version.observed(anchor.timestamp))
2348 }
2349
2350 pub fn clip_offset(&self, offset: usize, bias: Bias) -> usize {
2351 self.visible_text.clip_offset(offset, bias)
2352 }
2353
2354 pub fn clip_point(&self, point: Point, bias: Bias) -> Point {
2355 self.visible_text.clip_point(point, bias)
2356 }
2357
2358 pub fn clip_offset_utf16(&self, offset: OffsetUtf16, bias: Bias) -> OffsetUtf16 {
2359 self.visible_text.clip_offset_utf16(offset, bias)
2360 }
2361
2362 pub fn clip_point_utf16(&self, point: Unclipped<PointUtf16>, bias: Bias) -> PointUtf16 {
2363 self.visible_text.clip_point_utf16(point, bias)
2364 }
2365
2366 pub fn edits_since<'a, D>(
2367 &'a self,
2368 since: &'a clock::Global,
2369 ) -> impl 'a + Iterator<Item = Edit<D>>
2370 where
2371 D: TextDimension + Ord,
2372 {
2373 self.edits_since_in_range(since, Anchor::MIN..Anchor::MAX)
2374 }
2375
2376 pub fn anchored_edits_since<'a, D>(
2377 &'a self,
2378 since: &'a clock::Global,
2379 ) -> impl 'a + Iterator<Item = (Edit<D>, Range<Anchor>)>
2380 where
2381 D: TextDimension + Ord,
2382 {
2383 self.anchored_edits_since_in_range(since, Anchor::MIN..Anchor::MAX)
2384 }
2385
2386 pub fn edits_since_in_range<'a, D>(
2387 &'a self,
2388 since: &'a clock::Global,
2389 range: Range<Anchor>,
2390 ) -> impl 'a + Iterator<Item = Edit<D>>
2391 where
2392 D: TextDimension + Ord,
2393 {
2394 self.anchored_edits_since_in_range(since, range)
2395 .map(|item| item.0)
2396 }
2397
2398 pub fn anchored_edits_since_in_range<'a, D>(
2399 &'a self,
2400 since: &'a clock::Global,
2401 range: Range<Anchor>,
2402 ) -> impl 'a + Iterator<Item = (Edit<D>, Range<Anchor>)>
2403 where
2404 D: TextDimension + Ord,
2405 {
2406 let fragments_cursor = if *since == self.version {
2407 None
2408 } else {
2409 let mut cursor = self.fragments.filter(&None, move |summary| {
2410 !since.observed_all(&summary.max_version)
2411 });
2412 cursor.next(&None);
2413 Some(cursor)
2414 };
2415 let mut cursor = self
2416 .fragments
2417 .cursor::<(Option<&Locator>, FragmentTextSummary)>(&None);
2418
2419 let start_fragment_id = self.fragment_id_for_anchor(&range.start);
2420 cursor.seek(&Some(start_fragment_id), Bias::Left, &None);
2421 let mut visible_start = cursor.start().1.visible;
2422 let mut deleted_start = cursor.start().1.deleted;
2423 if let Some(fragment) = cursor.item() {
2424 let overshoot = range.start.offset - fragment.insertion_offset;
2425 if fragment.visible {
2426 visible_start += overshoot;
2427 } else {
2428 deleted_start += overshoot;
2429 }
2430 }
2431 let end_fragment_id = self.fragment_id_for_anchor(&range.end);
2432
2433 Edits {
2434 visible_cursor: self.visible_text.cursor(visible_start),
2435 deleted_cursor: self.deleted_text.cursor(deleted_start),
2436 fragments_cursor,
2437 undos: &self.undo_map,
2438 since,
2439 old_end: D::zero(&()),
2440 new_end: D::zero(&()),
2441 range: (start_fragment_id, range.start.offset)..(end_fragment_id, range.end.offset),
2442 buffer_id: self.remote_id,
2443 }
2444 }
2445
2446 pub fn has_edits_since_in_range(&self, since: &clock::Global, range: Range<Anchor>) -> bool {
2447 if *since != self.version {
2448 let start_fragment_id = self.fragment_id_for_anchor(&range.start);
2449 let end_fragment_id = self.fragment_id_for_anchor(&range.end);
2450 let mut cursor = self.fragments.filter::<_, usize>(&None, move |summary| {
2451 !since.observed_all(&summary.max_version)
2452 });
2453 cursor.next(&None);
2454 while let Some(fragment) = cursor.item() {
2455 if fragment.id > *end_fragment_id {
2456 break;
2457 }
2458 if fragment.id > *start_fragment_id {
2459 let was_visible = fragment.was_visible(since, &self.undo_map);
2460 let is_visible = fragment.visible;
2461 if was_visible != is_visible {
2462 return true;
2463 }
2464 }
2465 cursor.next(&None);
2466 }
2467 }
2468 false
2469 }
2470
2471 pub fn has_edits_since(&self, since: &clock::Global) -> bool {
2472 if *since != self.version {
2473 let mut cursor = self.fragments.filter::<_, usize>(&None, move |summary| {
2474 !since.observed_all(&summary.max_version)
2475 });
2476 cursor.next(&None);
2477 while let Some(fragment) = cursor.item() {
2478 let was_visible = fragment.was_visible(since, &self.undo_map);
2479 let is_visible = fragment.visible;
2480 if was_visible != is_visible {
2481 return true;
2482 }
2483 cursor.next(&None);
2484 }
2485 }
2486 false
2487 }
2488
2489 pub fn range_to_version(&self, range: Range<usize>, version: &clock::Global) -> Range<usize> {
2490 let mut offsets = self.offsets_to_version([range.start, range.end], version);
2491 offsets.next().unwrap()..offsets.next().unwrap()
2492 }
2493
2494 /// Converts the given sequence of offsets into their corresponding offsets
2495 /// at a prior version of this buffer.
2496 pub fn offsets_to_version<'a>(
2497 &'a self,
2498 offsets: impl 'a + IntoIterator<Item = usize>,
2499 version: &'a clock::Global,
2500 ) -> impl 'a + Iterator<Item = usize> {
2501 let mut edits = self.edits_since(version).peekable();
2502 let mut last_old_end = 0;
2503 let mut last_new_end = 0;
2504 offsets.into_iter().map(move |new_offset| {
2505 while let Some(edit) = edits.peek() {
2506 if edit.new.start > new_offset {
2507 break;
2508 }
2509
2510 if edit.new.end <= new_offset {
2511 last_new_end = edit.new.end;
2512 last_old_end = edit.old.end;
2513 edits.next();
2514 continue;
2515 }
2516
2517 let overshoot = new_offset - edit.new.start;
2518 return (edit.old.start + overshoot).min(edit.old.end);
2519 }
2520
2521 last_old_end + new_offset.saturating_sub(last_new_end)
2522 })
2523 }
2524}
2525
2526struct RopeBuilder<'a> {
2527 old_visible_cursor: rope::Cursor<'a>,
2528 old_deleted_cursor: rope::Cursor<'a>,
2529 new_visible: Rope,
2530 new_deleted: Rope,
2531}
2532
2533impl<'a> RopeBuilder<'a> {
2534 fn new(old_visible_cursor: rope::Cursor<'a>, old_deleted_cursor: rope::Cursor<'a>) -> Self {
2535 Self {
2536 old_visible_cursor,
2537 old_deleted_cursor,
2538 new_visible: Rope::new(),
2539 new_deleted: Rope::new(),
2540 }
2541 }
2542
2543 fn append(&mut self, len: FragmentTextSummary) {
2544 self.push(len.visible, true, true);
2545 self.push(len.deleted, false, false);
2546 }
2547
2548 fn push_fragment(&mut self, fragment: &Fragment, was_visible: bool) {
2549 debug_assert!(fragment.len > 0);
2550 self.push(fragment.len, was_visible, fragment.visible)
2551 }
2552
2553 fn push(&mut self, len: usize, was_visible: bool, is_visible: bool) {
2554 let text = if was_visible {
2555 self.old_visible_cursor
2556 .slice(self.old_visible_cursor.offset() + len)
2557 } else {
2558 self.old_deleted_cursor
2559 .slice(self.old_deleted_cursor.offset() + len)
2560 };
2561 if is_visible {
2562 self.new_visible.append(text);
2563 } else {
2564 self.new_deleted.append(text);
2565 }
2566 }
2567
2568 fn push_str(&mut self, text: &str) {
2569 self.new_visible.push(text);
2570 }
2571
2572 fn finish(mut self) -> (Rope, Rope) {
2573 self.new_visible.append(self.old_visible_cursor.suffix());
2574 self.new_deleted.append(self.old_deleted_cursor.suffix());
2575 (self.new_visible, self.new_deleted)
2576 }
2577}
2578
2579impl<D: TextDimension + Ord, F: FnMut(&FragmentSummary) -> bool> Iterator for Edits<'_, D, F> {
2580 type Item = (Edit<D>, Range<Anchor>);
2581
2582 fn next(&mut self) -> Option<Self::Item> {
2583 let mut pending_edit: Option<Self::Item> = None;
2584 let cursor = self.fragments_cursor.as_mut()?;
2585
2586 while let Some(fragment) = cursor.item() {
2587 if fragment.id < *self.range.start.0 {
2588 cursor.next(&None);
2589 continue;
2590 } else if fragment.id > *self.range.end.0 {
2591 break;
2592 }
2593
2594 if cursor.start().visible > self.visible_cursor.offset() {
2595 let summary = self.visible_cursor.summary(cursor.start().visible);
2596 self.old_end.add_assign(&summary);
2597 self.new_end.add_assign(&summary);
2598 }
2599
2600 if pending_edit
2601 .as_ref()
2602 .map_or(false, |(change, _)| change.new.end < self.new_end)
2603 {
2604 break;
2605 }
2606
2607 let start_anchor = Anchor {
2608 timestamp: fragment.timestamp,
2609 offset: fragment.insertion_offset,
2610 bias: Bias::Right,
2611 buffer_id: Some(self.buffer_id),
2612 };
2613 let end_anchor = Anchor {
2614 timestamp: fragment.timestamp,
2615 offset: fragment.insertion_offset + fragment.len,
2616 bias: Bias::Left,
2617 buffer_id: Some(self.buffer_id),
2618 };
2619
2620 if !fragment.was_visible(self.since, self.undos) && fragment.visible {
2621 let mut visible_end = cursor.end(&None).visible;
2622 if fragment.id == *self.range.end.0 {
2623 visible_end = cmp::min(
2624 visible_end,
2625 cursor.start().visible + (self.range.end.1 - fragment.insertion_offset),
2626 );
2627 }
2628
2629 let fragment_summary = self.visible_cursor.summary(visible_end);
2630 let mut new_end = self.new_end;
2631 new_end.add_assign(&fragment_summary);
2632 if let Some((edit, range)) = pending_edit.as_mut() {
2633 edit.new.end = new_end;
2634 range.end = end_anchor;
2635 } else {
2636 pending_edit = Some((
2637 Edit {
2638 old: self.old_end..self.old_end,
2639 new: self.new_end..new_end,
2640 },
2641 start_anchor..end_anchor,
2642 ));
2643 }
2644
2645 self.new_end = new_end;
2646 } else if fragment.was_visible(self.since, self.undos) && !fragment.visible {
2647 let mut deleted_end = cursor.end(&None).deleted;
2648 if fragment.id == *self.range.end.0 {
2649 deleted_end = cmp::min(
2650 deleted_end,
2651 cursor.start().deleted + (self.range.end.1 - fragment.insertion_offset),
2652 );
2653 }
2654
2655 if cursor.start().deleted > self.deleted_cursor.offset() {
2656 self.deleted_cursor.seek_forward(cursor.start().deleted);
2657 }
2658 let fragment_summary = self.deleted_cursor.summary(deleted_end);
2659 let mut old_end = self.old_end;
2660 old_end.add_assign(&fragment_summary);
2661 if let Some((edit, range)) = pending_edit.as_mut() {
2662 edit.old.end = old_end;
2663 range.end = end_anchor;
2664 } else {
2665 pending_edit = Some((
2666 Edit {
2667 old: self.old_end..old_end,
2668 new: self.new_end..self.new_end,
2669 },
2670 start_anchor..end_anchor,
2671 ));
2672 }
2673
2674 self.old_end = old_end;
2675 }
2676
2677 cursor.next(&None);
2678 }
2679
2680 pending_edit
2681 }
2682}
2683
2684impl Fragment {
2685 fn is_visible(&self, undos: &UndoMap) -> bool {
2686 !undos.is_undone(self.timestamp) && self.deletions.iter().all(|d| undos.is_undone(*d))
2687 }
2688
2689 fn was_visible(&self, version: &clock::Global, undos: &UndoMap) -> bool {
2690 (version.observed(self.timestamp) && !undos.was_undone(self.timestamp, version))
2691 && self
2692 .deletions
2693 .iter()
2694 .all(|d| !version.observed(*d) || undos.was_undone(*d, version))
2695 }
2696}
2697
2698impl sum_tree::Item for Fragment {
2699 type Summary = FragmentSummary;
2700
2701 fn summary(&self, _cx: &Option<clock::Global>) -> Self::Summary {
2702 let mut max_version = clock::Global::new();
2703 max_version.observe(self.timestamp);
2704 for deletion in &self.deletions {
2705 max_version.observe(*deletion);
2706 }
2707 max_version.join(&self.max_undos);
2708
2709 let mut min_insertion_version = clock::Global::new();
2710 min_insertion_version.observe(self.timestamp);
2711 let max_insertion_version = min_insertion_version.clone();
2712 if self.visible {
2713 FragmentSummary {
2714 max_id: self.id.clone(),
2715 text: FragmentTextSummary {
2716 visible: self.len,
2717 deleted: 0,
2718 },
2719 max_version,
2720 min_insertion_version,
2721 max_insertion_version,
2722 }
2723 } else {
2724 FragmentSummary {
2725 max_id: self.id.clone(),
2726 text: FragmentTextSummary {
2727 visible: 0,
2728 deleted: self.len,
2729 },
2730 max_version,
2731 min_insertion_version,
2732 max_insertion_version,
2733 }
2734 }
2735 }
2736}
2737
2738impl sum_tree::Summary for FragmentSummary {
2739 type Context = Option<clock::Global>;
2740
2741 fn zero(_cx: &Self::Context) -> Self {
2742 Default::default()
2743 }
2744
2745 fn add_summary(&mut self, other: &Self, _: &Self::Context) {
2746 self.max_id.assign(&other.max_id);
2747 self.text.visible += &other.text.visible;
2748 self.text.deleted += &other.text.deleted;
2749 self.max_version.join(&other.max_version);
2750 self.min_insertion_version
2751 .meet(&other.min_insertion_version);
2752 self.max_insertion_version
2753 .join(&other.max_insertion_version);
2754 }
2755}
2756
2757impl Default for FragmentSummary {
2758 fn default() -> Self {
2759 FragmentSummary {
2760 max_id: Locator::min(),
2761 text: FragmentTextSummary::default(),
2762 max_version: clock::Global::new(),
2763 min_insertion_version: clock::Global::new(),
2764 max_insertion_version: clock::Global::new(),
2765 }
2766 }
2767}
2768
2769impl sum_tree::Item for InsertionFragment {
2770 type Summary = InsertionFragmentKey;
2771
2772 fn summary(&self, _cx: &()) -> Self::Summary {
2773 InsertionFragmentKey {
2774 timestamp: self.timestamp,
2775 split_offset: self.split_offset,
2776 }
2777 }
2778}
2779
2780impl sum_tree::KeyedItem for InsertionFragment {
2781 type Key = InsertionFragmentKey;
2782
2783 fn key(&self) -> Self::Key {
2784 sum_tree::Item::summary(self, &())
2785 }
2786}
2787
2788impl InsertionFragment {
2789 fn new(fragment: &Fragment) -> Self {
2790 Self {
2791 timestamp: fragment.timestamp,
2792 split_offset: fragment.insertion_offset,
2793 fragment_id: fragment.id.clone(),
2794 }
2795 }
2796
2797 fn insert_new(fragment: &Fragment) -> sum_tree::Edit<Self> {
2798 sum_tree::Edit::Insert(Self::new(fragment))
2799 }
2800}
2801
2802impl sum_tree::Summary for InsertionFragmentKey {
2803 type Context = ();
2804
2805 fn zero(_cx: &()) -> Self {
2806 Default::default()
2807 }
2808
2809 fn add_summary(&mut self, summary: &Self, _: &()) {
2810 *self = *summary;
2811 }
2812}
2813
2814#[derive(Copy, Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
2815pub struct FullOffset(pub usize);
2816
2817impl ops::AddAssign<usize> for FullOffset {
2818 fn add_assign(&mut self, rhs: usize) {
2819 self.0 += rhs;
2820 }
2821}
2822
2823impl ops::Add<usize> for FullOffset {
2824 type Output = Self;
2825
2826 fn add(mut self, rhs: usize) -> Self::Output {
2827 self += rhs;
2828 self
2829 }
2830}
2831
2832impl ops::Sub for FullOffset {
2833 type Output = usize;
2834
2835 fn sub(self, rhs: Self) -> Self::Output {
2836 self.0 - rhs.0
2837 }
2838}
2839
2840impl sum_tree::Dimension<'_, FragmentSummary> for usize {
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 += summary.text.visible;
2847 }
2848}
2849
2850impl sum_tree::Dimension<'_, FragmentSummary> for FullOffset {
2851 fn zero(_: &Option<clock::Global>) -> Self {
2852 Default::default()
2853 }
2854
2855 fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
2856 self.0 += summary.text.visible + summary.text.deleted;
2857 }
2858}
2859
2860impl<'a> sum_tree::Dimension<'a, FragmentSummary> for Option<&'a Locator> {
2861 fn zero(_: &Option<clock::Global>) -> Self {
2862 Default::default()
2863 }
2864
2865 fn add_summary(&mut self, summary: &'a FragmentSummary, _: &Option<clock::Global>) {
2866 *self = Some(&summary.max_id);
2867 }
2868}
2869
2870impl sum_tree::SeekTarget<'_, FragmentSummary, FragmentTextSummary> for usize {
2871 fn cmp(
2872 &self,
2873 cursor_location: &FragmentTextSummary,
2874 _: &Option<clock::Global>,
2875 ) -> cmp::Ordering {
2876 Ord::cmp(self, &cursor_location.visible)
2877 }
2878}
2879
2880#[derive(Copy, Clone, Debug, Eq, PartialEq)]
2881enum VersionedFullOffset {
2882 Offset(FullOffset),
2883 Invalid,
2884}
2885
2886impl VersionedFullOffset {
2887 fn full_offset(&self) -> FullOffset {
2888 if let Self::Offset(position) = self {
2889 *position
2890 } else {
2891 panic!("invalid version")
2892 }
2893 }
2894}
2895
2896impl Default for VersionedFullOffset {
2897 fn default() -> Self {
2898 Self::Offset(Default::default())
2899 }
2900}
2901
2902impl<'a> sum_tree::Dimension<'a, FragmentSummary> for VersionedFullOffset {
2903 fn zero(_cx: &Option<clock::Global>) -> Self {
2904 Default::default()
2905 }
2906
2907 fn add_summary(&mut self, summary: &'a FragmentSummary, cx: &Option<clock::Global>) {
2908 if let Self::Offset(offset) = self {
2909 let version = cx.as_ref().unwrap();
2910 if version.observed_all(&summary.max_insertion_version) {
2911 *offset += summary.text.visible + summary.text.deleted;
2912 } else if version.observed_any(&summary.min_insertion_version) {
2913 *self = Self::Invalid;
2914 }
2915 }
2916 }
2917}
2918
2919impl sum_tree::SeekTarget<'_, FragmentSummary, Self> for VersionedFullOffset {
2920 fn cmp(&self, cursor_position: &Self, _: &Option<clock::Global>) -> cmp::Ordering {
2921 match (self, cursor_position) {
2922 (Self::Offset(a), Self::Offset(b)) => Ord::cmp(a, b),
2923 (Self::Offset(_), Self::Invalid) => cmp::Ordering::Less,
2924 (Self::Invalid, _) => unreachable!(),
2925 }
2926 }
2927}
2928
2929impl Operation {
2930 fn replica_id(&self) -> ReplicaId {
2931 operation_queue::Operation::lamport_timestamp(self).replica_id
2932 }
2933
2934 pub fn timestamp(&self) -> clock::Lamport {
2935 match self {
2936 Operation::Edit(edit) => edit.timestamp,
2937 Operation::Undo(undo) => undo.timestamp,
2938 }
2939 }
2940
2941 pub fn as_edit(&self) -> Option<&EditOperation> {
2942 match self {
2943 Operation::Edit(edit) => Some(edit),
2944 _ => None,
2945 }
2946 }
2947
2948 pub fn is_edit(&self) -> bool {
2949 matches!(self, Operation::Edit { .. })
2950 }
2951}
2952
2953impl operation_queue::Operation for Operation {
2954 fn lamport_timestamp(&self) -> clock::Lamport {
2955 match self {
2956 Operation::Edit(edit) => edit.timestamp,
2957 Operation::Undo(undo) => undo.timestamp,
2958 }
2959 }
2960}
2961
2962pub trait ToOffset {
2963 fn to_offset(&self, snapshot: &BufferSnapshot) -> usize;
2964}
2965
2966impl ToOffset for Point {
2967 fn to_offset(&self, snapshot: &BufferSnapshot) -> usize {
2968 snapshot.point_to_offset(*self)
2969 }
2970}
2971
2972impl ToOffset for usize {
2973 #[track_caller]
2974 fn to_offset(&self, snapshot: &BufferSnapshot) -> usize {
2975 assert!(
2976 *self <= snapshot.len(),
2977 "offset {} is out of range, max allowed is {}",
2978 self,
2979 snapshot.len()
2980 );
2981 *self
2982 }
2983}
2984
2985impl ToOffset for Anchor {
2986 fn to_offset(&self, snapshot: &BufferSnapshot) -> usize {
2987 snapshot.summary_for_anchor(self)
2988 }
2989}
2990
2991impl<T: ToOffset> ToOffset for &T {
2992 fn to_offset(&self, content: &BufferSnapshot) -> usize {
2993 (*self).to_offset(content)
2994 }
2995}
2996
2997impl ToOffset for PointUtf16 {
2998 fn to_offset(&self, snapshot: &BufferSnapshot) -> usize {
2999 snapshot.point_utf16_to_offset(*self)
3000 }
3001}
3002
3003impl ToOffset for Unclipped<PointUtf16> {
3004 fn to_offset(&self, snapshot: &BufferSnapshot) -> usize {
3005 snapshot.unclipped_point_utf16_to_offset(*self)
3006 }
3007}
3008
3009pub trait ToPoint {
3010 fn to_point(&self, snapshot: &BufferSnapshot) -> Point;
3011}
3012
3013impl ToPoint for Anchor {
3014 fn to_point(&self, snapshot: &BufferSnapshot) -> Point {
3015 snapshot.summary_for_anchor(self)
3016 }
3017}
3018
3019impl ToPoint for usize {
3020 fn to_point(&self, snapshot: &BufferSnapshot) -> Point {
3021 snapshot.offset_to_point(*self)
3022 }
3023}
3024
3025impl ToPoint for Point {
3026 fn to_point(&self, _: &BufferSnapshot) -> Point {
3027 *self
3028 }
3029}
3030
3031impl ToPoint for Unclipped<PointUtf16> {
3032 fn to_point(&self, snapshot: &BufferSnapshot) -> Point {
3033 snapshot.unclipped_point_utf16_to_point(*self)
3034 }
3035}
3036
3037pub trait ToPointUtf16 {
3038 fn to_point_utf16(&self, snapshot: &BufferSnapshot) -> PointUtf16;
3039}
3040
3041impl ToPointUtf16 for Anchor {
3042 fn to_point_utf16(&self, snapshot: &BufferSnapshot) -> PointUtf16 {
3043 snapshot.summary_for_anchor(self)
3044 }
3045}
3046
3047impl ToPointUtf16 for usize {
3048 fn to_point_utf16(&self, snapshot: &BufferSnapshot) -> PointUtf16 {
3049 snapshot.offset_to_point_utf16(*self)
3050 }
3051}
3052
3053impl ToPointUtf16 for PointUtf16 {
3054 fn to_point_utf16(&self, _: &BufferSnapshot) -> PointUtf16 {
3055 *self
3056 }
3057}
3058
3059impl ToPointUtf16 for Point {
3060 fn to_point_utf16(&self, snapshot: &BufferSnapshot) -> PointUtf16 {
3061 snapshot.point_to_point_utf16(*self)
3062 }
3063}
3064
3065pub trait ToOffsetUtf16 {
3066 fn to_offset_utf16(&self, snapshot: &BufferSnapshot) -> OffsetUtf16;
3067}
3068
3069impl ToOffsetUtf16 for Anchor {
3070 fn to_offset_utf16(&self, snapshot: &BufferSnapshot) -> OffsetUtf16 {
3071 snapshot.summary_for_anchor(self)
3072 }
3073}
3074
3075impl ToOffsetUtf16 for usize {
3076 fn to_offset_utf16(&self, snapshot: &BufferSnapshot) -> OffsetUtf16 {
3077 snapshot.offset_to_offset_utf16(*self)
3078 }
3079}
3080
3081impl ToOffsetUtf16 for OffsetUtf16 {
3082 fn to_offset_utf16(&self, _snapshot: &BufferSnapshot) -> OffsetUtf16 {
3083 *self
3084 }
3085}
3086
3087pub trait FromAnchor {
3088 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self;
3089}
3090
3091impl FromAnchor for Anchor {
3092 fn from_anchor(anchor: &Anchor, _snapshot: &BufferSnapshot) -> Self {
3093 *anchor
3094 }
3095}
3096
3097impl FromAnchor for Point {
3098 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
3099 snapshot.summary_for_anchor(anchor)
3100 }
3101}
3102
3103impl FromAnchor for PointUtf16 {
3104 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
3105 snapshot.summary_for_anchor(anchor)
3106 }
3107}
3108
3109impl FromAnchor for usize {
3110 fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
3111 snapshot.summary_for_anchor(anchor)
3112 }
3113}
3114
3115#[derive(Clone, Copy, Debug, PartialEq)]
3116pub enum LineEnding {
3117 Unix,
3118 Windows,
3119}
3120
3121impl Default for LineEnding {
3122 fn default() -> Self {
3123 #[cfg(unix)]
3124 return Self::Unix;
3125
3126 #[cfg(not(unix))]
3127 return Self::Windows;
3128 }
3129}
3130
3131impl LineEnding {
3132 pub fn as_str(&self) -> &'static str {
3133 match self {
3134 LineEnding::Unix => "\n",
3135 LineEnding::Windows => "\r\n",
3136 }
3137 }
3138
3139 pub fn detect(text: &str) -> Self {
3140 let mut max_ix = cmp::min(text.len(), 1000);
3141 while !text.is_char_boundary(max_ix) {
3142 max_ix -= 1;
3143 }
3144
3145 if let Some(ix) = text[..max_ix].find(['\n']) {
3146 if ix > 0 && text.as_bytes()[ix - 1] == b'\r' {
3147 Self::Windows
3148 } else {
3149 Self::Unix
3150 }
3151 } else {
3152 Self::default()
3153 }
3154 }
3155
3156 pub fn normalize(text: &mut String) {
3157 if let Cow::Owned(replaced) = LINE_SEPARATORS_REGEX.replace_all(text, "\n") {
3158 *text = replaced;
3159 }
3160 }
3161
3162 pub fn normalize_arc(text: Arc<str>) -> Arc<str> {
3163 if let Cow::Owned(replaced) = LINE_SEPARATORS_REGEX.replace_all(&text, "\n") {
3164 replaced.into()
3165 } else {
3166 text
3167 }
3168 }
3169
3170 pub fn normalize_cow(text: Cow<str>) -> Cow<str> {
3171 if let Cow::Owned(replaced) = LINE_SEPARATORS_REGEX.replace_all(&text, "\n") {
3172 replaced.into()
3173 } else {
3174 text
3175 }
3176 }
3177}