tenant.openagents/omega

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