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