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