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