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