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