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