mod anchor;pub mod locator;#[cfg(any(test, feature = "test-support"))]pub mod network;pub mod operation_queue;mod patch;mod selection;pub mod subscription;#[cfg(test)]mod tests;mod undo_map; pub use anchor::*;use anyhow::{Context as _, Result};use clock::Lamport;pub use clock::ReplicaId;use collections::{HashMap, HashSet};use locator::Locator;use operation_queue::OperationQueue;pub use patch::Patch;use postage::{oneshot, prelude::*}; use regex::Regex;pub use rope::*;pub use selection::*;use smallvec::SmallVec;use std::{    borrow::Cow,    cmp::{self, Ordering, Reverse},    fmt::Display,    future::Future,    iter::Iterator,    num::NonZeroU64,    ops::{self, Deref, Range, Sub},    str,    sync::{Arc, LazyLock},    time::{Duration, Instant},};pub use subscription::*;pub use sum_tree::Bias;use sum_tree::{Dimensions, FilterCursor, SumTree, TreeMap, TreeSet};use undo_map::UndoMap;use util::debug_panic; #[cfg(any(test, feature = "test-support"))]use util::RandomCharIter; static LINE_SEPARATORS_REGEX: LazyLock<Regex> =    LazyLock::new(|| Regex::new(r"\r\n|\r").expect("Failed to create LINE_SEPARATORS_REGEX")); /// The maximum length of a single insertion operation./// Fragments larger than this will be split into multiple smaller/// fragments. This allows us to use relative `u32` offsets instead of `usize`,/// reducing memory usage.const MAX_INSERTION_LEN: usize = if cfg!(test) { 16 } else { u32::MAX as usize }; pub type TransactionId = clock::Lamport; pub struct Buffer {    snapshot: BufferSnapshot,    history: History,    deferred_ops: OperationQueue<Operation>,    deferred_replicas: HashSet<ReplicaId>,    pub lamport_clock: clock::Lamport,    subscriptions: Topic<usize>,    edit_id_resolvers: HashMap<clock::Lamport, Vec<oneshot::Sender<()>>>,    wait_for_version_txs: Vec<(clock::Global, oneshot::Sender<()>)>,} #[repr(transparent)]#[derive(Clone, Copy, Debug, Hash, PartialEq, PartialOrd, Ord, Eq)]pub struct BufferId(NonZeroU64); impl Display for BufferId {    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {        write!(f, "{}", self.0)    }} impl From<NonZeroU64> for BufferId {    fn from(id: NonZeroU64) -> Self {        BufferId(id)    }} impl BufferId {    /// Returns Err if `id` is outside of BufferId domain.    pub fn new(id: u64) -> anyhow::Result<Self> {        let id = NonZeroU64::new(id).context("Buffer id cannot be 0.")?;        Ok(Self(id))    }     /// Increments this buffer id, returning the old value.    /// So that's a post-increment operator in disguise.    pub fn next(&mut self) -> Self {        let old = *self;        self.0 = self.0.saturating_add(1);        old    }     pub fn to_proto(self) -> u64 {        self.into()    }} impl From<BufferId> for u64 {    fn from(id: BufferId) -> Self {        id.0.get()    }} #[derive(Clone)]pub struct BufferSnapshot {    visible_text: Rope,    deleted_text: Rope,    fragments: SumTree<Fragment>,    insertions: SumTree<InsertionFragment>,    insertion_slices: TreeSet<InsertionSlice>,    undo_map: UndoMap,    pub version: clock::Global,    remote_id: BufferId,    replica_id: ReplicaId,    line_ending: LineEnding,} #[derive(Clone, Debug)]pub struct HistoryEntry {    transaction: Transaction,    first_edit_at: Instant,    last_edit_at: Instant,    suppress_grouping: bool,} #[derive(Clone, Debug)]pub struct Transaction {    pub id: TransactionId,    pub edit_ids: Vec<clock::Lamport>,    pub start: clock::Global,} impl Transaction {    pub fn merge_in(&mut self, other: Transaction) {        self.edit_ids.extend(other.edit_ids);    }} impl HistoryEntry {    pub fn transaction_id(&self) -> TransactionId {        self.transaction.id    }} struct History {    base_text: Rope,    operations: TreeMap<clock::Lamport, Operation>,    undo_stack: Vec<HistoryEntry>,    redo_stack: Vec<HistoryEntry>,    transaction_depth: usize,    group_interval: Duration,} #[derive(Clone, Debug, Eq, PartialEq)]struct InsertionSlice {    // Inline the lamports to allow the replica ids to share the same alignment    // saving 4 bytes space edit_id: clock::Lamport,    edit_id_value: clock::Seq,    edit_id_replica_id: ReplicaId,    // insertion_id: clock::Lamport,    insertion_id_value: clock::Seq,    insertion_id_replica_id: ReplicaId,    range: Range<u32>,} impl Ord for InsertionSlice {    fn cmp(&self, other: &Self) -> Ordering {        Lamport {            value: self.edit_id_value,            replica_id: self.edit_id_replica_id,        }        .cmp(&Lamport {            value: other.edit_id_value,            replica_id: other.edit_id_replica_id,        })        .then_with(|| {            Lamport {                value: self.insertion_id_value,                replica_id: self.insertion_id_replica_id,            }            .cmp(&Lamport {                value: other.insertion_id_value,                replica_id: other.insertion_id_replica_id,            })        })        .then_with(|| self.range.start.cmp(&other.range.start))        .then_with(|| self.range.end.cmp(&other.range.end))    }} impl PartialOrd for InsertionSlice {    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {        Some(self.cmp(other))    }} impl InsertionSlice {    fn from_fragment(edit_id: clock::Lamport, fragment: &Fragment) -> Self {        Self {            edit_id_value: edit_id.value,            edit_id_replica_id: edit_id.replica_id,            insertion_id_value: fragment.timestamp.value,            insertion_id_replica_id: fragment.timestamp.replica_id,            range: fragment.insertion_offset..fragment.insertion_offset + fragment.len,        }    }} impl History {    pub fn new(base_text: Rope) -> Self {        Self {            base_text,            operations: Default::default(),            undo_stack: Vec::new(),            redo_stack: Vec::new(),            transaction_depth: 0,            // Don't group transactions in tests unless we opt in, because it's a footgun.            group_interval: if cfg!(any(test, feature = "test-support")) {                Duration::ZERO            } else {                Duration::from_millis(300)            },        }    }     fn push(&mut self, op: Operation) {        self.operations.insert(op.timestamp(), op);    }     fn start_transaction(        &mut self,        start: clock::Global,        now: Instant,        clock: &mut clock::Lamport,    ) -> Option<TransactionId> {        self.transaction_depth += 1;        if self.transaction_depth == 1 {            let id = clock.tick();            self.undo_stack.push(HistoryEntry {                transaction: Transaction {                    id,                    start,                    edit_ids: Default::default(),                },                first_edit_at: now,                last_edit_at: now,                suppress_grouping: false,            });            Some(id)        } else {            None        }    }     fn end_transaction(&mut self, now: Instant) -> Option<&HistoryEntry> {        assert_ne!(self.transaction_depth, 0);        self.transaction_depth -= 1;        if self.transaction_depth == 0 {            if self                .undo_stack                .last()                .unwrap()                .transaction                .edit_ids                .is_empty()            {                self.undo_stack.pop();                None            } else {                self.redo_stack.clear();                let entry = self.undo_stack.last_mut().unwrap();                entry.last_edit_at = now;                Some(entry)            }        } else {            None        }    }     fn group(&mut self) -> Option<TransactionId> {        let mut count = 0;        let mut entries = self.undo_stack.iter();        if let Some(mut entry) = entries.next_back() {            while let Some(prev_entry) = entries.next_back() {                if !prev_entry.suppress_grouping                    && entry.first_edit_at - prev_entry.last_edit_at < self.group_interval                {                    entry = prev_entry;                    count += 1;                } else {                    break;                }            }        }        self.group_trailing(count)    }     fn group_until(&mut self, transaction_id: TransactionId) {        let mut count = 0;        for entry in self.undo_stack.iter().rev() {            if entry.transaction_id() == transaction_id {                self.group_trailing(count);                break;            } else if entry.suppress_grouping {                break;            } else {                count += 1;            }        }    }     fn group_trailing(&mut self, n: usize) -> Option<TransactionId> {        let new_len = self.undo_stack.len() - n;        let (entries_to_keep, entries_to_merge) = self.undo_stack.split_at_mut(new_len);        if let Some(last_entry) = entries_to_keep.last_mut() {            for entry in &*entries_to_merge {                for edit_id in &entry.transaction.edit_ids {                    last_entry.transaction.edit_ids.push(*edit_id);                }            }             if let Some(entry) = entries_to_merge.last_mut() {                last_entry.last_edit_at = entry.last_edit_at;            }        }         self.undo_stack.truncate(new_len);        self.undo_stack.last().map(|e| e.transaction.id)    }     fn finalize_last_transaction(&mut self) -> Option<&Transaction> {        self.undo_stack.last_mut().map(|entry| {            entry.transaction.edit_ids.shrink_to_fit();            entry.suppress_grouping = true;            &entry.transaction        })    }     fn push_transaction(&mut self, transaction: Transaction, now: Instant) {        assert_eq!(self.transaction_depth, 0);        self.undo_stack.push(HistoryEntry {            transaction,            first_edit_at: now,            last_edit_at: now,            suppress_grouping: false,        });    }     /// Differs from `push_transaction` in that it does not clear the redo    /// stack. Intended to be used to create a parent transaction to merge    /// potential child transactions into.    ///    /// The caller is responsible for removing it from the undo history using    /// `forget_transaction` if no edits are merged into it. Otherwise, if edits    /// are merged into this transaction, the caller is responsible for ensuring    /// the redo stack is cleared. The easiest way to ensure the redo stack is    /// cleared is to create transactions with the usual `start_transaction` and    /// `end_transaction` methods and merging the resulting transactions into    /// the transaction created by this method    fn push_empty_transaction(        &mut self,        start: clock::Global,        now: Instant,        clock: &mut clock::Lamport,    ) -> TransactionId {        assert_eq!(self.transaction_depth, 0);        let id = clock.tick();        let transaction = Transaction {            id,            start,            edit_ids: Vec::new(),        };        self.undo_stack.push(HistoryEntry {            transaction,            first_edit_at: now,            last_edit_at: now,            suppress_grouping: false,        });        id    }     fn push_undo(&mut self, op_id: clock::Lamport) {        assert_ne!(self.transaction_depth, 0);        if let Some(Operation::Edit(_)) = self.operations.get(&op_id) {            let last_transaction = self.undo_stack.last_mut().unwrap();            last_transaction.transaction.edit_ids.push(op_id);        }    }     fn pop_undo(&mut self) -> Option<&HistoryEntry> {        assert_eq!(self.transaction_depth, 0);        if let Some(entry) = self.undo_stack.pop() {            self.redo_stack.push(entry);            self.redo_stack.last()        } else {            None        }    }     fn remove_from_undo(&mut self, transaction_id: TransactionId) -> Option<&HistoryEntry> {        assert_eq!(self.transaction_depth, 0);         let entry_ix = self            .undo_stack            .iter()            .rposition(|entry| entry.transaction.id == transaction_id)?;        let entry = self.undo_stack.remove(entry_ix);        self.redo_stack.push(entry);        self.redo_stack.last()    }     fn remove_from_undo_until(&mut self, transaction_id: TransactionId) -> &[HistoryEntry] {        assert_eq!(self.transaction_depth, 0);         let redo_stack_start_len = self.redo_stack.len();        if let Some(entry_ix) = self            .undo_stack            .iter()            .rposition(|entry| entry.transaction.id == transaction_id)        {            self.redo_stack                .extend(self.undo_stack.drain(entry_ix..).rev());        }        &self.redo_stack[redo_stack_start_len..]    }     fn forget(&mut self, transaction_id: TransactionId) -> Option<Transaction> {        assert_eq!(self.transaction_depth, 0);        if let Some(entry_ix) = self            .undo_stack            .iter()            .rposition(|entry| entry.transaction.id == transaction_id)        {            Some(self.undo_stack.remove(entry_ix).transaction)        } else if let Some(entry_ix) = self            .redo_stack            .iter()            .rposition(|entry| entry.transaction.id == transaction_id)        {            Some(self.redo_stack.remove(entry_ix).transaction)        } else {            None        }    }     fn transaction(&self, transaction_id: TransactionId) -> Option<&Transaction> {        let entry = self            .undo_stack            .iter()            .rfind(|entry| entry.transaction.id == transaction_id)            .or_else(|| {                self.redo_stack                    .iter()                    .rfind(|entry| entry.transaction.id == transaction_id)            })?;        Some(&entry.transaction)    }     fn transaction_mut(&mut self, transaction_id: TransactionId) -> Option<&mut Transaction> {        let entry = self            .undo_stack            .iter_mut()            .rfind(|entry| entry.transaction.id == transaction_id)            .or_else(|| {                self.redo_stack                    .iter_mut()                    .rfind(|entry| entry.transaction.id == transaction_id)            })?;        Some(&mut entry.transaction)    }     fn merge_transactions(&mut self, transaction: TransactionId, destination: TransactionId) {        if let Some(transaction) = self.forget(transaction)            && let Some(destination) = self.transaction_mut(destination)        {            destination.edit_ids.extend(transaction.edit_ids);        }    }     fn pop_redo(&mut self) -> Option<&HistoryEntry> {        assert_eq!(self.transaction_depth, 0);        if let Some(entry) = self.redo_stack.pop() {            self.undo_stack.push(entry);            self.undo_stack.last()        } else {            None        }    }     fn remove_from_redo(&mut self, transaction_id: TransactionId) -> &[HistoryEntry] {        assert_eq!(self.transaction_depth, 0); 

Lines 1–500 of 3709. Load more