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