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