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