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