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_transactions(&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_transactions(&mut self, transaction: TransactionId, destination: TransactionId) {
1229        self.history.merge_transactions(transaction, destination);
1230    }
1231
1232    pub fn redo(&mut self) -> Option<(TransactionId, Operation)> {
1233        if let Some(entry) = self.history.pop_redo() {
1234            let transaction = entry.transaction.clone();
1235            let transaction_id = transaction.id;
1236            let op = self.undo_or_redo(transaction).unwrap();
1237            Some((transaction_id, op))
1238        } else {
1239            None
1240        }
1241    }
1242
1243    #[allow(clippy::needless_collect)]
1244    pub fn redo_to_transaction(&mut self, transaction_id: TransactionId) -> Vec<Operation> {
1245        let transactions = self
1246            .history
1247            .remove_from_redo(transaction_id)
1248            .iter()
1249            .map(|entry| entry.transaction.clone())
1250            .collect::<Vec<_>>();
1251
1252        transactions
1253            .into_iter()
1254            .map(|transaction| self.undo_or_redo(transaction).unwrap())
1255            .collect()
1256    }
1257
1258    fn undo_or_redo(&mut self, transaction: Transaction) -> Result<Operation> {
1259        let mut counts = HashMap::default();
1260        for edit_id in transaction.edit_ids {
1261            counts.insert(edit_id, self.undo_map.undo_count(edit_id) + 1);
1262        }
1263
1264        let undo = UndoOperation {
1265            id: self.local_clock.tick(),
1266            version: self.version(),
1267            counts,
1268        };
1269        self.apply_undo(&undo)?;
1270        let operation = Operation::Undo {
1271            undo,
1272            lamport_timestamp: self.lamport_clock.tick(),
1273        };
1274        self.snapshot.version.observe(operation.local_timestamp());
1275        self.history.push(operation.clone());
1276        Ok(operation)
1277    }
1278
1279    pub fn push_transaction(&mut self, transaction: Transaction, now: Instant) {
1280        self.history.push_transaction(transaction, now);
1281        self.history.finalize_last_transaction();
1282    }
1283
1284    pub fn edited_ranges_for_transaction<'a, D>(
1285        &'a self,
1286        transaction: &'a Transaction,
1287    ) -> impl 'a + Iterator<Item = Range<D>>
1288    where
1289        D: TextDimension,
1290    {
1291        // get fragment ranges
1292        let mut cursor = self.fragments.cursor::<(Option<&Locator>, usize)>();
1293        let offset_ranges = self
1294            .fragment_ids_for_edits(transaction.edit_ids.iter())
1295            .into_iter()
1296            .filter_map(move |fragment_id| {
1297                cursor.seek_forward(&Some(fragment_id), Bias::Left, &None);
1298                let fragment = cursor.item()?;
1299                let start_offset = cursor.start().1;
1300                let end_offset = start_offset + if fragment.visible { fragment.len } else { 0 };
1301                Some(start_offset..end_offset)
1302            });
1303
1304        // combine adjacent ranges
1305        let mut prev_range: Option<Range<usize>> = None;
1306        let disjoint_ranges = offset_ranges
1307            .map(Some)
1308            .chain([None])
1309            .filter_map(move |range| {
1310                if let Some((range, prev_range)) = range.as_ref().zip(prev_range.as_mut()) {
1311                    if prev_range.end == range.start {
1312                        prev_range.end = range.end;
1313                        return None;
1314                    }
1315                }
1316                let result = prev_range.clone();
1317                prev_range = range;
1318                result
1319            });
1320
1321        // convert to the desired text dimension.
1322        let mut position = D::default();
1323        let mut rope_cursor = self.visible_text.cursor(0);
1324        disjoint_ranges.map(move |range| {
1325            position.add_assign(&rope_cursor.summary(range.start));
1326            let start = position.clone();
1327            position.add_assign(&rope_cursor.summary(range.end));
1328            let end = position.clone();
1329            start..end
1330        })
1331    }
1332
1333    pub fn subscribe(&mut self) -> Subscription {
1334        self.subscriptions.subscribe()
1335    }
1336
1337    pub fn wait_for_edits(
1338        &mut self,
1339        edit_ids: impl IntoIterator<Item = clock::Local>,
1340    ) -> impl 'static + Future<Output = Result<()>> {
1341        let mut futures = Vec::new();
1342        for edit_id in edit_ids {
1343            if !self.version.observed(edit_id) {
1344                let (tx, rx) = oneshot::channel();
1345                self.edit_id_resolvers.entry(edit_id).or_default().push(tx);
1346                futures.push(rx);
1347            }
1348        }
1349
1350        async move {
1351            for mut future in futures {
1352                if future.recv().await.is_none() {
1353                    Err(anyhow!("gave up waiting for edits"))?;
1354                }
1355            }
1356            Ok(())
1357        }
1358    }
1359
1360    pub fn wait_for_anchors(
1361        &mut self,
1362        anchors: impl IntoIterator<Item = Anchor>,
1363    ) -> impl 'static + Future<Output = Result<()>> {
1364        let mut futures = Vec::new();
1365        for anchor in anchors {
1366            if !self.version.observed(anchor.timestamp)
1367                && anchor != Anchor::MAX
1368                && anchor != Anchor::MIN
1369            {
1370                let (tx, rx) = oneshot::channel();
1371                self.edit_id_resolvers
1372                    .entry(anchor.timestamp)
1373                    .or_default()
1374                    .push(tx);
1375                futures.push(rx);
1376            }
1377        }
1378
1379        async move {
1380            for mut future in futures {
1381                if future.recv().await.is_none() {
1382                    Err(anyhow!("gave up waiting for anchors"))?;
1383                }
1384            }
1385            Ok(())
1386        }
1387    }
1388
1389    pub fn wait_for_version(&mut self, version: clock::Global) -> impl Future<Output = Result<()>> {
1390        let mut rx = None;
1391        if !self.snapshot.version.observed_all(&version) {
1392            let channel = oneshot::channel();
1393            self.wait_for_version_txs.push((version, channel.0));
1394            rx = Some(channel.1);
1395        }
1396        async move {
1397            if let Some(mut rx) = rx {
1398                if rx.recv().await.is_none() {
1399                    Err(anyhow!("gave up waiting for version"))?;
1400                }
1401            }
1402            Ok(())
1403        }
1404    }
1405
1406    pub fn give_up_waiting(&mut self) {
1407        self.edit_id_resolvers.clear();
1408        self.wait_for_version_txs.clear();
1409    }
1410
1411    fn resolve_edit(&mut self, edit_id: clock::Local) {
1412        for mut tx in self
1413            .edit_id_resolvers
1414            .remove(&edit_id)
1415            .into_iter()
1416            .flatten()
1417        {
1418            tx.try_send(()).ok();
1419        }
1420    }
1421}
1422
1423#[cfg(any(test, feature = "test-support"))]
1424impl Buffer {
1425    pub fn edit_via_marked_text(&mut self, marked_string: &str) {
1426        let edits = self.edits_for_marked_text(marked_string);
1427        self.edit(edits);
1428    }
1429
1430    pub fn edits_for_marked_text(&self, marked_string: &str) -> Vec<(Range<usize>, String)> {
1431        let old_text = self.text();
1432        let (new_text, mut ranges) = util::test::marked_text_ranges(marked_string, false);
1433        if ranges.is_empty() {
1434            ranges.push(0..new_text.len());
1435        }
1436
1437        assert_eq!(
1438            old_text[..ranges[0].start],
1439            new_text[..ranges[0].start],
1440            "invalid edit"
1441        );
1442
1443        let mut delta = 0;
1444        let mut edits = Vec::new();
1445        let mut ranges = ranges.into_iter().peekable();
1446
1447        while let Some(inserted_range) = ranges.next() {
1448            let new_start = inserted_range.start;
1449            let old_start = (new_start as isize - delta) as usize;
1450
1451            let following_text = if let Some(next_range) = ranges.peek() {
1452                &new_text[inserted_range.end..next_range.start]
1453            } else {
1454                &new_text[inserted_range.end..]
1455            };
1456
1457            let inserted_len = inserted_range.len();
1458            let deleted_len = old_text[old_start..]
1459                .find(following_text)
1460                .expect("invalid edit");
1461
1462            let old_range = old_start..old_start + deleted_len;
1463            edits.push((old_range, new_text[inserted_range].to_string()));
1464            delta += inserted_len as isize - deleted_len as isize;
1465        }
1466
1467        assert_eq!(
1468            old_text.len() as isize + delta,
1469            new_text.len() as isize,
1470            "invalid edit"
1471        );
1472
1473        edits
1474    }
1475
1476    pub fn check_invariants(&self) {
1477        // Ensure every fragment is ordered by locator in the fragment tree and corresponds
1478        // to an insertion fragment in the insertions tree.
1479        let mut prev_fragment_id = Locator::min();
1480        for fragment in self.snapshot.fragments.items(&None) {
1481            assert!(fragment.id > prev_fragment_id);
1482            prev_fragment_id = fragment.id.clone();
1483
1484            let insertion_fragment = self
1485                .snapshot
1486                .insertions
1487                .get(
1488                    &InsertionFragmentKey {
1489                        timestamp: fragment.insertion_timestamp.local(),
1490                        split_offset: fragment.insertion_offset,
1491                    },
1492                    &(),
1493                )
1494                .unwrap();
1495            assert_eq!(
1496                insertion_fragment.fragment_id, fragment.id,
1497                "fragment: {:?}\ninsertion: {:?}",
1498                fragment, insertion_fragment
1499            );
1500        }
1501
1502        let mut cursor = self.snapshot.fragments.cursor::<Option<&Locator>>();
1503        for insertion_fragment in self.snapshot.insertions.cursor::<()>() {
1504            cursor.seek(&Some(&insertion_fragment.fragment_id), Bias::Left, &None);
1505            let fragment = cursor.item().unwrap();
1506            assert_eq!(insertion_fragment.fragment_id, fragment.id);
1507            assert_eq!(insertion_fragment.split_offset, fragment.insertion_offset);
1508        }
1509
1510        let fragment_summary = self.snapshot.fragments.summary();
1511        assert_eq!(
1512            fragment_summary.text.visible,
1513            self.snapshot.visible_text.len()
1514        );
1515        assert_eq!(
1516            fragment_summary.text.deleted,
1517            self.snapshot.deleted_text.len()
1518        );
1519
1520        assert!(!self.text().contains("\r\n"));
1521    }
1522
1523    pub fn set_group_interval(&mut self, group_interval: Duration) {
1524        self.history.group_interval = group_interval;
1525    }
1526
1527    pub fn random_byte_range(&self, start_offset: usize, rng: &mut impl rand::Rng) -> Range<usize> {
1528        let end = self.clip_offset(rng.gen_range(start_offset..=self.len()), Bias::Right);
1529        let start = self.clip_offset(rng.gen_range(start_offset..=end), Bias::Right);
1530        start..end
1531    }
1532
1533    pub fn get_random_edits<T>(
1534        &self,
1535        rng: &mut T,
1536        edit_count: usize,
1537    ) -> Vec<(Range<usize>, Arc<str>)>
1538    where
1539        T: rand::Rng,
1540    {
1541        let mut edits: Vec<(Range<usize>, Arc<str>)> = Vec::new();
1542        let mut last_end = None;
1543        for _ in 0..edit_count {
1544            if last_end.map_or(false, |last_end| last_end >= self.len()) {
1545                break;
1546            }
1547            let new_start = last_end.map_or(0, |last_end| last_end + 1);
1548            let range = self.random_byte_range(new_start, rng);
1549            last_end = Some(range.end);
1550
1551            let new_text_len = rng.gen_range(0..10);
1552            let new_text: String = RandomCharIter::new(&mut *rng).take(new_text_len).collect();
1553
1554            edits.push((range, new_text.into()));
1555        }
1556        edits
1557    }
1558
1559    #[allow(clippy::type_complexity)]
1560    pub fn randomly_edit<T>(
1561        &mut self,
1562        rng: &mut T,
1563        edit_count: usize,
1564    ) -> (Vec<(Range<usize>, Arc<str>)>, Operation)
1565    where
1566        T: rand::Rng,
1567    {
1568        let mut edits = self.get_random_edits(rng, edit_count);
1569        log::info!("mutating buffer {} with {:?}", self.replica_id, edits);
1570
1571        let op = self.edit(edits.iter().cloned());
1572        if let Operation::Edit(edit) = &op {
1573            assert_eq!(edits.len(), edit.new_text.len());
1574            for (edit, new_text) in edits.iter_mut().zip(&edit.new_text) {
1575                edit.1 = new_text.clone();
1576            }
1577        } else {
1578            unreachable!()
1579        }
1580
1581        (edits, op)
1582    }
1583
1584    pub fn randomly_undo_redo(&mut self, rng: &mut impl rand::Rng) -> Vec<Operation> {
1585        use rand::prelude::*;
1586
1587        let mut ops = Vec::new();
1588        for _ in 0..rng.gen_range(1..=5) {
1589            if let Some(entry) = self.history.undo_stack.choose(rng) {
1590                let transaction = entry.transaction.clone();
1591                log::info!(
1592                    "undoing buffer {} transaction {:?}",
1593                    self.replica_id,
1594                    transaction
1595                );
1596                ops.push(self.undo_or_redo(transaction).unwrap());
1597            }
1598        }
1599        ops
1600    }
1601}
1602
1603impl Deref for Buffer {
1604    type Target = BufferSnapshot;
1605
1606    fn deref(&self) -> &Self::Target {
1607        &self.snapshot
1608    }
1609}
1610
1611impl BufferSnapshot {
1612    pub fn as_rope(&self) -> &Rope {
1613        &self.visible_text
1614    }
1615
1616    pub fn remote_id(&self) -> u64 {
1617        self.remote_id
1618    }
1619
1620    pub fn replica_id(&self) -> ReplicaId {
1621        self.replica_id
1622    }
1623
1624    pub fn row_count(&self) -> u32 {
1625        self.max_point().row + 1
1626    }
1627
1628    pub fn len(&self) -> usize {
1629        self.visible_text.len()
1630    }
1631
1632    pub fn is_empty(&self) -> bool {
1633        self.len() == 0
1634    }
1635
1636    pub fn chars(&self) -> impl Iterator<Item = char> + '_ {
1637        self.chars_at(0)
1638    }
1639
1640    pub fn chars_for_range<T: ToOffset>(&self, range: Range<T>) -> impl Iterator<Item = char> + '_ {
1641        self.text_for_range(range).flat_map(str::chars)
1642    }
1643
1644    pub fn reversed_chars_for_range<T: ToOffset>(
1645        &self,
1646        range: Range<T>,
1647    ) -> impl Iterator<Item = char> + '_ {
1648        self.reversed_chunks_in_range(range)
1649            .flat_map(|chunk| chunk.chars().rev())
1650    }
1651
1652    pub fn contains_str_at<T>(&self, position: T, needle: &str) -> bool
1653    where
1654        T: ToOffset,
1655    {
1656        let position = position.to_offset(self);
1657        position == self.clip_offset(position, Bias::Left)
1658            && self
1659                .bytes_in_range(position..self.len())
1660                .flatten()
1661                .copied()
1662                .take(needle.len())
1663                .eq(needle.bytes())
1664    }
1665
1666    pub fn common_prefix_at<T>(&self, position: T, needle: &str) -> Range<T>
1667    where
1668        T: ToOffset + TextDimension,
1669    {
1670        let offset = position.to_offset(self);
1671        let common_prefix_len = needle
1672            .char_indices()
1673            .map(|(index, _)| index)
1674            .chain([needle.len()])
1675            .take_while(|&len| len <= offset)
1676            .filter(|&len| {
1677                let left = self
1678                    .chars_for_range(offset - len..offset)
1679                    .flat_map(char::to_lowercase);
1680                let right = needle[..len].chars().flat_map(char::to_lowercase);
1681                left.eq(right)
1682            })
1683            .last()
1684            .unwrap_or(0);
1685        let start_offset = offset - common_prefix_len;
1686        let start = self.text_summary_for_range(0..start_offset);
1687        start..position
1688    }
1689
1690    pub fn text(&self) -> String {
1691        self.visible_text.to_string()
1692    }
1693
1694    pub fn line_ending(&self) -> LineEnding {
1695        self.line_ending
1696    }
1697
1698    pub fn deleted_text(&self) -> String {
1699        self.deleted_text.to_string()
1700    }
1701
1702    pub fn fragments(&self) -> impl Iterator<Item = &Fragment> {
1703        self.fragments.iter()
1704    }
1705
1706    pub fn text_summary(&self) -> TextSummary {
1707        self.visible_text.summary()
1708    }
1709
1710    pub fn max_point(&self) -> Point {
1711        self.visible_text.max_point()
1712    }
1713
1714    pub fn max_point_utf16(&self) -> PointUtf16 {
1715        self.visible_text.max_point_utf16()
1716    }
1717
1718    pub fn point_to_offset(&self, point: Point) -> usize {
1719        self.visible_text.point_to_offset(point)
1720    }
1721
1722    pub fn point_utf16_to_offset(&self, point: PointUtf16) -> usize {
1723        self.visible_text.point_utf16_to_offset(point)
1724    }
1725
1726    pub fn unclipped_point_utf16_to_offset(&self, point: Unclipped<PointUtf16>) -> usize {
1727        self.visible_text.unclipped_point_utf16_to_offset(point)
1728    }
1729
1730    pub fn unclipped_point_utf16_to_point(&self, point: Unclipped<PointUtf16>) -> Point {
1731        self.visible_text.unclipped_point_utf16_to_point(point)
1732    }
1733
1734    pub fn offset_utf16_to_offset(&self, offset: OffsetUtf16) -> usize {
1735        self.visible_text.offset_utf16_to_offset(offset)
1736    }
1737
1738    pub fn offset_to_offset_utf16(&self, offset: usize) -> OffsetUtf16 {
1739        self.visible_text.offset_to_offset_utf16(offset)
1740    }
1741
1742    pub fn offset_to_point(&self, offset: usize) -> Point {
1743        self.visible_text.offset_to_point(offset)
1744    }
1745
1746    pub fn offset_to_point_utf16(&self, offset: usize) -> PointUtf16 {
1747        self.visible_text.offset_to_point_utf16(offset)
1748    }
1749
1750    pub fn point_to_point_utf16(&self, point: Point) -> PointUtf16 {
1751        self.visible_text.point_to_point_utf16(point)
1752    }
1753
1754    pub fn version(&self) -> &clock::Global {
1755        &self.version
1756    }
1757
1758    pub fn chars_at<T: ToOffset>(&self, position: T) -> impl Iterator<Item = char> + '_ {
1759        let offset = position.to_offset(self);
1760        self.visible_text.chars_at(offset)
1761    }
1762
1763    pub fn reversed_chars_at<T: ToOffset>(&self, position: T) -> impl Iterator<Item = char> + '_ {
1764        let offset = position.to_offset(self);
1765        self.visible_text.reversed_chars_at(offset)
1766    }
1767
1768    pub fn reversed_chunks_in_range<T: ToOffset>(&self, range: Range<T>) -> rope::Chunks {
1769        let range = range.start.to_offset(self)..range.end.to_offset(self);
1770        self.visible_text.reversed_chunks_in_range(range)
1771    }
1772
1773    pub fn bytes_in_range<T: ToOffset>(&self, range: Range<T>) -> rope::Bytes<'_> {
1774        let start = range.start.to_offset(self);
1775        let end = range.end.to_offset(self);
1776        self.visible_text.bytes_in_range(start..end)
1777    }
1778
1779    pub fn reversed_bytes_in_range<T: ToOffset>(&self, range: Range<T>) -> rope::Bytes<'_> {
1780        let start = range.start.to_offset(self);
1781        let end = range.end.to_offset(self);
1782        self.visible_text.reversed_bytes_in_range(start..end)
1783    }
1784
1785    pub fn text_for_range<T: ToOffset>(&self, range: Range<T>) -> Chunks<'_> {
1786        let start = range.start.to_offset(self);
1787        let end = range.end.to_offset(self);
1788        self.visible_text.chunks_in_range(start..end)
1789    }
1790
1791    pub fn line_len(&self, row: u32) -> u32 {
1792        let row_start_offset = Point::new(row, 0).to_offset(self);
1793        let row_end_offset = if row >= self.max_point().row {
1794            self.len()
1795        } else {
1796            Point::new(row + 1, 0).to_offset(self) - 1
1797        };
1798        (row_end_offset - row_start_offset) as u32
1799    }
1800
1801    pub fn is_line_blank(&self, row: u32) -> bool {
1802        self.text_for_range(Point::new(row, 0)..Point::new(row, self.line_len(row)))
1803            .all(|chunk| chunk.matches(|c: char| !c.is_whitespace()).next().is_none())
1804    }
1805
1806    pub fn text_summary_for_range<D, O: ToOffset>(&self, range: Range<O>) -> D
1807    where
1808        D: TextDimension,
1809    {
1810        self.visible_text
1811            .cursor(range.start.to_offset(self))
1812            .summary(range.end.to_offset(self))
1813    }
1814
1815    pub fn summaries_for_anchors<'a, D, A>(&'a self, anchors: A) -> impl 'a + Iterator<Item = D>
1816    where
1817        D: 'a + TextDimension,
1818        A: 'a + IntoIterator<Item = &'a Anchor>,
1819    {
1820        let anchors = anchors.into_iter();
1821        self.summaries_for_anchors_with_payload::<D, _, ()>(anchors.map(|a| (a, ())))
1822            .map(|d| d.0)
1823    }
1824
1825    pub fn summaries_for_anchors_with_payload<'a, D, A, T>(
1826        &'a self,
1827        anchors: A,
1828    ) -> impl 'a + Iterator<Item = (D, T)>
1829    where
1830        D: 'a + TextDimension,
1831        A: 'a + IntoIterator<Item = (&'a Anchor, T)>,
1832    {
1833        let anchors = anchors.into_iter();
1834        let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>();
1835        let mut fragment_cursor = self.fragments.cursor::<(Option<&Locator>, usize)>();
1836        let mut text_cursor = self.visible_text.cursor(0);
1837        let mut position = D::default();
1838
1839        anchors.map(move |(anchor, payload)| {
1840            if *anchor == Anchor::MIN {
1841                return (D::default(), payload);
1842            } else if *anchor == Anchor::MAX {
1843                return (D::from_text_summary(&self.visible_text.summary()), payload);
1844            }
1845
1846            let anchor_key = InsertionFragmentKey {
1847                timestamp: anchor.timestamp,
1848                split_offset: anchor.offset,
1849            };
1850            insertion_cursor.seek(&anchor_key, anchor.bias, &());
1851            if let Some(insertion) = insertion_cursor.item() {
1852                let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
1853                if comparison == Ordering::Greater
1854                    || (anchor.bias == Bias::Left
1855                        && comparison == Ordering::Equal
1856                        && anchor.offset > 0)
1857                {
1858                    insertion_cursor.prev(&());
1859                }
1860            } else {
1861                insertion_cursor.prev(&());
1862            }
1863            let insertion = insertion_cursor.item().expect("invalid insertion");
1864            assert_eq!(insertion.timestamp, anchor.timestamp, "invalid insertion");
1865
1866            fragment_cursor.seek_forward(&Some(&insertion.fragment_id), Bias::Left, &None);
1867            let fragment = fragment_cursor.item().unwrap();
1868            let mut fragment_offset = fragment_cursor.start().1;
1869            if fragment.visible {
1870                fragment_offset += anchor.offset - insertion.split_offset;
1871            }
1872
1873            position.add_assign(&text_cursor.summary(fragment_offset));
1874            (position.clone(), payload)
1875        })
1876    }
1877
1878    fn summary_for_anchor<D>(&self, anchor: &Anchor) -> D
1879    where
1880        D: TextDimension,
1881    {
1882        if *anchor == Anchor::MIN {
1883            D::default()
1884        } else if *anchor == Anchor::MAX {
1885            D::from_text_summary(&self.visible_text.summary())
1886        } else {
1887            let anchor_key = InsertionFragmentKey {
1888                timestamp: anchor.timestamp,
1889                split_offset: anchor.offset,
1890            };
1891            let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>();
1892            insertion_cursor.seek(&anchor_key, anchor.bias, &());
1893            if let Some(insertion) = insertion_cursor.item() {
1894                let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
1895                if comparison == Ordering::Greater
1896                    || (anchor.bias == Bias::Left
1897                        && comparison == Ordering::Equal
1898                        && anchor.offset > 0)
1899                {
1900                    insertion_cursor.prev(&());
1901                }
1902            } else {
1903                insertion_cursor.prev(&());
1904            }
1905            let insertion = insertion_cursor.item().expect("invalid insertion");
1906            assert_eq!(insertion.timestamp, anchor.timestamp, "invalid insertion");
1907
1908            let mut fragment_cursor = self.fragments.cursor::<(Option<&Locator>, usize)>();
1909            fragment_cursor.seek(&Some(&insertion.fragment_id), Bias::Left, &None);
1910            let fragment = fragment_cursor.item().unwrap();
1911            let mut fragment_offset = fragment_cursor.start().1;
1912            if fragment.visible {
1913                fragment_offset += anchor.offset - insertion.split_offset;
1914            }
1915            self.text_summary_for_range(0..fragment_offset)
1916        }
1917    }
1918
1919    fn fragment_id_for_anchor(&self, anchor: &Anchor) -> &Locator {
1920        if *anchor == Anchor::MIN {
1921            Locator::min_ref()
1922        } else if *anchor == Anchor::MAX {
1923            Locator::max_ref()
1924        } else {
1925            let anchor_key = InsertionFragmentKey {
1926                timestamp: anchor.timestamp,
1927                split_offset: anchor.offset,
1928            };
1929            let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>();
1930            insertion_cursor.seek(&anchor_key, anchor.bias, &());
1931            if let Some(insertion) = insertion_cursor.item() {
1932                let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
1933                if comparison == Ordering::Greater
1934                    || (anchor.bias == Bias::Left
1935                        && comparison == Ordering::Equal
1936                        && anchor.offset > 0)
1937                {
1938                    insertion_cursor.prev(&());
1939                }
1940            } else {
1941                insertion_cursor.prev(&());
1942            }
1943            let insertion = insertion_cursor.item().expect("invalid insertion");
1944            debug_assert_eq!(insertion.timestamp, anchor.timestamp, "invalid insertion");
1945            &insertion.fragment_id
1946        }
1947    }
1948
1949    pub fn anchor_before<T: ToOffset>(&self, position: T) -> Anchor {
1950        self.anchor_at(position, Bias::Left)
1951    }
1952
1953    pub fn anchor_after<T: ToOffset>(&self, position: T) -> Anchor {
1954        self.anchor_at(position, Bias::Right)
1955    }
1956
1957    pub fn anchor_at<T: ToOffset>(&self, position: T, bias: Bias) -> Anchor {
1958        self.anchor_at_offset(position.to_offset(self), bias)
1959    }
1960
1961    fn anchor_at_offset(&self, offset: usize, bias: Bias) -> Anchor {
1962        if bias == Bias::Left && offset == 0 {
1963            Anchor::MIN
1964        } else if bias == Bias::Right && offset == self.len() {
1965            Anchor::MAX
1966        } else {
1967            let mut fragment_cursor = self.fragments.cursor::<usize>();
1968            fragment_cursor.seek(&offset, bias, &None);
1969            let fragment = fragment_cursor.item().unwrap();
1970            let overshoot = offset - *fragment_cursor.start();
1971            Anchor {
1972                timestamp: fragment.insertion_timestamp.local(),
1973                offset: fragment.insertion_offset + overshoot,
1974                bias,
1975                buffer_id: Some(self.remote_id),
1976            }
1977        }
1978    }
1979
1980    pub fn can_resolve(&self, anchor: &Anchor) -> bool {
1981        *anchor == Anchor::MIN
1982            || *anchor == Anchor::MAX
1983            || (Some(self.remote_id) == anchor.buffer_id && self.version.observed(anchor.timestamp))
1984    }
1985
1986    pub fn clip_offset(&self, offset: usize, bias: Bias) -> usize {
1987        self.visible_text.clip_offset(offset, bias)
1988    }
1989
1990    pub fn clip_point(&self, point: Point, bias: Bias) -> Point {
1991        self.visible_text.clip_point(point, bias)
1992    }
1993
1994    pub fn clip_offset_utf16(&self, offset: OffsetUtf16, bias: Bias) -> OffsetUtf16 {
1995        self.visible_text.clip_offset_utf16(offset, bias)
1996    }
1997
1998    pub fn clip_point_utf16(&self, point: Unclipped<PointUtf16>, bias: Bias) -> PointUtf16 {
1999        self.visible_text.clip_point_utf16(point, bias)
2000    }
2001
2002    pub fn edits_since<'a, D>(
2003        &'a self,
2004        since: &'a clock::Global,
2005    ) -> impl 'a + Iterator<Item = Edit<D>>
2006    where
2007        D: TextDimension + Ord,
2008    {
2009        self.edits_since_in_range(since, Anchor::MIN..Anchor::MAX)
2010    }
2011
2012    pub fn anchored_edits_since<'a, D>(
2013        &'a self,
2014        since: &'a clock::Global,
2015    ) -> impl 'a + Iterator<Item = (Edit<D>, Range<Anchor>)>
2016    where
2017        D: TextDimension + Ord,
2018    {
2019        self.anchored_edits_since_in_range(since, Anchor::MIN..Anchor::MAX)
2020    }
2021
2022    pub fn edits_since_in_range<'a, D>(
2023        &'a self,
2024        since: &'a clock::Global,
2025        range: Range<Anchor>,
2026    ) -> impl 'a + Iterator<Item = Edit<D>>
2027    where
2028        D: TextDimension + Ord,
2029    {
2030        self.anchored_edits_since_in_range(since, range)
2031            .map(|item| item.0)
2032    }
2033
2034    pub fn anchored_edits_since_in_range<'a, D>(
2035        &'a self,
2036        since: &'a clock::Global,
2037        range: Range<Anchor>,
2038    ) -> impl 'a + Iterator<Item = (Edit<D>, Range<Anchor>)>
2039    where
2040        D: TextDimension + Ord,
2041    {
2042        let fragments_cursor = if *since == self.version {
2043            None
2044        } else {
2045            let mut cursor = self
2046                .fragments
2047                .filter(move |summary| !since.observed_all(&summary.max_version));
2048            cursor.next(&None);
2049            Some(cursor)
2050        };
2051        let mut cursor = self
2052            .fragments
2053            .cursor::<(Option<&Locator>, FragmentTextSummary)>();
2054
2055        let start_fragment_id = self.fragment_id_for_anchor(&range.start);
2056        cursor.seek(&Some(start_fragment_id), Bias::Left, &None);
2057        let mut visible_start = cursor.start().1.visible;
2058        let mut deleted_start = cursor.start().1.deleted;
2059        if let Some(fragment) = cursor.item() {
2060            let overshoot = range.start.offset - fragment.insertion_offset;
2061            if fragment.visible {
2062                visible_start += overshoot;
2063            } else {
2064                deleted_start += overshoot;
2065            }
2066        }
2067        let end_fragment_id = self.fragment_id_for_anchor(&range.end);
2068
2069        Edits {
2070            visible_cursor: self.visible_text.cursor(visible_start),
2071            deleted_cursor: self.deleted_text.cursor(deleted_start),
2072            fragments_cursor,
2073            undos: &self.undo_map,
2074            since,
2075            old_end: Default::default(),
2076            new_end: Default::default(),
2077            range: (start_fragment_id, range.start.offset)..(end_fragment_id, range.end.offset),
2078            buffer_id: self.remote_id,
2079        }
2080    }
2081}
2082
2083struct RopeBuilder<'a> {
2084    old_visible_cursor: rope::Cursor<'a>,
2085    old_deleted_cursor: rope::Cursor<'a>,
2086    new_visible: Rope,
2087    new_deleted: Rope,
2088}
2089
2090impl<'a> RopeBuilder<'a> {
2091    fn new(old_visible_cursor: rope::Cursor<'a>, old_deleted_cursor: rope::Cursor<'a>) -> Self {
2092        Self {
2093            old_visible_cursor,
2094            old_deleted_cursor,
2095            new_visible: Rope::new(),
2096            new_deleted: Rope::new(),
2097        }
2098    }
2099
2100    fn append(&mut self, len: FragmentTextSummary) {
2101        self.push(len.visible, true, true);
2102        self.push(len.deleted, false, false);
2103    }
2104
2105    fn push_fragment(&mut self, fragment: &Fragment, was_visible: bool) {
2106        debug_assert!(fragment.len > 0);
2107        self.push(fragment.len, was_visible, fragment.visible)
2108    }
2109
2110    fn push(&mut self, len: usize, was_visible: bool, is_visible: bool) {
2111        let text = if was_visible {
2112            self.old_visible_cursor
2113                .slice(self.old_visible_cursor.offset() + len)
2114        } else {
2115            self.old_deleted_cursor
2116                .slice(self.old_deleted_cursor.offset() + len)
2117        };
2118        if is_visible {
2119            self.new_visible.append(text);
2120        } else {
2121            self.new_deleted.append(text);
2122        }
2123    }
2124
2125    fn push_str(&mut self, text: &str) {
2126        self.new_visible.push(text);
2127    }
2128
2129    fn finish(mut self) -> (Rope, Rope) {
2130        self.new_visible.append(self.old_visible_cursor.suffix());
2131        self.new_deleted.append(self.old_deleted_cursor.suffix());
2132        (self.new_visible, self.new_deleted)
2133    }
2134}
2135
2136impl<'a, D: TextDimension + Ord, F: FnMut(&FragmentSummary) -> bool> Iterator for Edits<'a, D, F> {
2137    type Item = (Edit<D>, Range<Anchor>);
2138
2139    fn next(&mut self) -> Option<Self::Item> {
2140        let mut pending_edit: Option<Self::Item> = None;
2141        let cursor = self.fragments_cursor.as_mut()?;
2142
2143        while let Some(fragment) = cursor.item() {
2144            if fragment.id < *self.range.start.0 {
2145                cursor.next(&None);
2146                continue;
2147            } else if fragment.id > *self.range.end.0 {
2148                break;
2149            }
2150
2151            if cursor.start().visible > self.visible_cursor.offset() {
2152                let summary = self.visible_cursor.summary(cursor.start().visible);
2153                self.old_end.add_assign(&summary);
2154                self.new_end.add_assign(&summary);
2155            }
2156
2157            if pending_edit
2158                .as_ref()
2159                .map_or(false, |(change, _)| change.new.end < self.new_end)
2160            {
2161                break;
2162            }
2163
2164            let timestamp = fragment.insertion_timestamp.local();
2165            let start_anchor = Anchor {
2166                timestamp,
2167                offset: fragment.insertion_offset,
2168                bias: Bias::Right,
2169                buffer_id: Some(self.buffer_id),
2170            };
2171            let end_anchor = Anchor {
2172                timestamp,
2173                offset: fragment.insertion_offset + fragment.len,
2174                bias: Bias::Left,
2175                buffer_id: Some(self.buffer_id),
2176            };
2177
2178            if !fragment.was_visible(self.since, self.undos) && fragment.visible {
2179                let mut visible_end = cursor.end(&None).visible;
2180                if fragment.id == *self.range.end.0 {
2181                    visible_end = cmp::min(
2182                        visible_end,
2183                        cursor.start().visible + (self.range.end.1 - fragment.insertion_offset),
2184                    );
2185                }
2186
2187                let fragment_summary = self.visible_cursor.summary(visible_end);
2188                let mut new_end = self.new_end.clone();
2189                new_end.add_assign(&fragment_summary);
2190                if let Some((edit, range)) = pending_edit.as_mut() {
2191                    edit.new.end = new_end.clone();
2192                    range.end = end_anchor;
2193                } else {
2194                    pending_edit = Some((
2195                        Edit {
2196                            old: self.old_end.clone()..self.old_end.clone(),
2197                            new: self.new_end.clone()..new_end.clone(),
2198                        },
2199                        start_anchor..end_anchor,
2200                    ));
2201                }
2202
2203                self.new_end = new_end;
2204            } else if fragment.was_visible(self.since, self.undos) && !fragment.visible {
2205                let mut deleted_end = cursor.end(&None).deleted;
2206                if fragment.id == *self.range.end.0 {
2207                    deleted_end = cmp::min(
2208                        deleted_end,
2209                        cursor.start().deleted + (self.range.end.1 - fragment.insertion_offset),
2210                    );
2211                }
2212
2213                if cursor.start().deleted > self.deleted_cursor.offset() {
2214                    self.deleted_cursor.seek_forward(cursor.start().deleted);
2215                }
2216                let fragment_summary = self.deleted_cursor.summary(deleted_end);
2217                let mut old_end = self.old_end.clone();
2218                old_end.add_assign(&fragment_summary);
2219                if let Some((edit, range)) = pending_edit.as_mut() {
2220                    edit.old.end = old_end.clone();
2221                    range.end = end_anchor;
2222                } else {
2223                    pending_edit = Some((
2224                        Edit {
2225                            old: self.old_end.clone()..old_end.clone(),
2226                            new: self.new_end.clone()..self.new_end.clone(),
2227                        },
2228                        start_anchor..end_anchor,
2229                    ));
2230                }
2231
2232                self.old_end = old_end;
2233            }
2234
2235            cursor.next(&None);
2236        }
2237
2238        pending_edit
2239    }
2240}
2241
2242impl Fragment {
2243    fn insertion_slice(&self) -> InsertionSlice {
2244        InsertionSlice {
2245            insertion_id: self.insertion_timestamp.local(),
2246            range: self.insertion_offset..self.insertion_offset + self.len,
2247        }
2248    }
2249
2250    fn is_visible(&self, undos: &UndoMap) -> bool {
2251        !undos.is_undone(self.insertion_timestamp.local())
2252            && self.deletions.iter().all(|d| undos.is_undone(*d))
2253    }
2254
2255    fn was_visible(&self, version: &clock::Global, undos: &UndoMap) -> bool {
2256        (version.observed(self.insertion_timestamp.local())
2257            && !undos.was_undone(self.insertion_timestamp.local(), version))
2258            && self
2259                .deletions
2260                .iter()
2261                .all(|d| !version.observed(*d) || undos.was_undone(*d, version))
2262    }
2263}
2264
2265impl sum_tree::Item for Fragment {
2266    type Summary = FragmentSummary;
2267
2268    fn summary(&self) -> Self::Summary {
2269        let mut max_version = clock::Global::new();
2270        max_version.observe(self.insertion_timestamp.local());
2271        for deletion in &self.deletions {
2272            max_version.observe(*deletion);
2273        }
2274        max_version.join(&self.max_undos);
2275
2276        let mut min_insertion_version = clock::Global::new();
2277        min_insertion_version.observe(self.insertion_timestamp.local());
2278        let max_insertion_version = min_insertion_version.clone();
2279        if self.visible {
2280            FragmentSummary {
2281                max_id: self.id.clone(),
2282                text: FragmentTextSummary {
2283                    visible: self.len,
2284                    deleted: 0,
2285                },
2286                max_version,
2287                min_insertion_version,
2288                max_insertion_version,
2289            }
2290        } else {
2291            FragmentSummary {
2292                max_id: self.id.clone(),
2293                text: FragmentTextSummary {
2294                    visible: 0,
2295                    deleted: self.len,
2296                },
2297                max_version,
2298                min_insertion_version,
2299                max_insertion_version,
2300            }
2301        }
2302    }
2303}
2304
2305impl sum_tree::Summary for FragmentSummary {
2306    type Context = Option<clock::Global>;
2307
2308    fn add_summary(&mut self, other: &Self, _: &Self::Context) {
2309        self.max_id.assign(&other.max_id);
2310        self.text.visible += &other.text.visible;
2311        self.text.deleted += &other.text.deleted;
2312        self.max_version.join(&other.max_version);
2313        self.min_insertion_version
2314            .meet(&other.min_insertion_version);
2315        self.max_insertion_version
2316            .join(&other.max_insertion_version);
2317    }
2318}
2319
2320impl Default for FragmentSummary {
2321    fn default() -> Self {
2322        FragmentSummary {
2323            max_id: Locator::min(),
2324            text: FragmentTextSummary::default(),
2325            max_version: clock::Global::new(),
2326            min_insertion_version: clock::Global::new(),
2327            max_insertion_version: clock::Global::new(),
2328        }
2329    }
2330}
2331
2332impl sum_tree::Item for InsertionFragment {
2333    type Summary = InsertionFragmentKey;
2334
2335    fn summary(&self) -> Self::Summary {
2336        InsertionFragmentKey {
2337            timestamp: self.timestamp,
2338            split_offset: self.split_offset,
2339        }
2340    }
2341}
2342
2343impl sum_tree::KeyedItem for InsertionFragment {
2344    type Key = InsertionFragmentKey;
2345
2346    fn key(&self) -> Self::Key {
2347        sum_tree::Item::summary(self)
2348    }
2349}
2350
2351impl InsertionFragment {
2352    fn new(fragment: &Fragment) -> Self {
2353        Self {
2354            timestamp: fragment.insertion_timestamp.local(),
2355            split_offset: fragment.insertion_offset,
2356            fragment_id: fragment.id.clone(),
2357        }
2358    }
2359
2360    fn insert_new(fragment: &Fragment) -> sum_tree::Edit<Self> {
2361        sum_tree::Edit::Insert(Self::new(fragment))
2362    }
2363}
2364
2365impl sum_tree::Summary for InsertionFragmentKey {
2366    type Context = ();
2367
2368    fn add_summary(&mut self, summary: &Self, _: &()) {
2369        *self = *summary;
2370    }
2371}
2372
2373#[derive(Copy, Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
2374pub struct FullOffset(pub usize);
2375
2376impl ops::AddAssign<usize> for FullOffset {
2377    fn add_assign(&mut self, rhs: usize) {
2378        self.0 += rhs;
2379    }
2380}
2381
2382impl ops::Add<usize> for FullOffset {
2383    type Output = Self;
2384
2385    fn add(mut self, rhs: usize) -> Self::Output {
2386        self += rhs;
2387        self
2388    }
2389}
2390
2391impl ops::Sub for FullOffset {
2392    type Output = usize;
2393
2394    fn sub(self, rhs: Self) -> Self::Output {
2395        self.0 - rhs.0
2396    }
2397}
2398
2399impl<'a> sum_tree::Dimension<'a, FragmentSummary> for usize {
2400    fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
2401        *self += summary.text.visible;
2402    }
2403}
2404
2405impl<'a> sum_tree::Dimension<'a, FragmentSummary> for FullOffset {
2406    fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
2407        self.0 += summary.text.visible + summary.text.deleted;
2408    }
2409}
2410
2411impl<'a> sum_tree::Dimension<'a, FragmentSummary> for Option<&'a Locator> {
2412    fn add_summary(&mut self, summary: &'a FragmentSummary, _: &Option<clock::Global>) {
2413        *self = Some(&summary.max_id);
2414    }
2415}
2416
2417impl<'a> sum_tree::SeekTarget<'a, FragmentSummary, FragmentTextSummary> for usize {
2418    fn cmp(
2419        &self,
2420        cursor_location: &FragmentTextSummary,
2421        _: &Option<clock::Global>,
2422    ) -> cmp::Ordering {
2423        Ord::cmp(self, &cursor_location.visible)
2424    }
2425}
2426
2427#[derive(Copy, Clone, Debug, Eq, PartialEq)]
2428enum VersionedFullOffset {
2429    Offset(FullOffset),
2430    Invalid,
2431}
2432
2433impl VersionedFullOffset {
2434    fn full_offset(&self) -> FullOffset {
2435        if let Self::Offset(position) = self {
2436            *position
2437        } else {
2438            panic!("invalid version")
2439        }
2440    }
2441}
2442
2443impl Default for VersionedFullOffset {
2444    fn default() -> Self {
2445        Self::Offset(Default::default())
2446    }
2447}
2448
2449impl<'a> sum_tree::Dimension<'a, FragmentSummary> for VersionedFullOffset {
2450    fn add_summary(&mut self, summary: &'a FragmentSummary, cx: &Option<clock::Global>) {
2451        if let Self::Offset(offset) = self {
2452            let version = cx.as_ref().unwrap();
2453            if version.observed_all(&summary.max_insertion_version) {
2454                *offset += summary.text.visible + summary.text.deleted;
2455            } else if version.observed_any(&summary.min_insertion_version) {
2456                *self = Self::Invalid;
2457            }
2458        }
2459    }
2460}
2461
2462impl<'a> sum_tree::SeekTarget<'a, FragmentSummary, Self> for VersionedFullOffset {
2463    fn cmp(&self, cursor_position: &Self, _: &Option<clock::Global>) -> cmp::Ordering {
2464        match (self, cursor_position) {
2465            (Self::Offset(a), Self::Offset(b)) => Ord::cmp(a, b),
2466            (Self::Offset(_), Self::Invalid) => cmp::Ordering::Less,
2467            (Self::Invalid, _) => unreachable!(),
2468        }
2469    }
2470}
2471
2472impl Operation {
2473    fn replica_id(&self) -> ReplicaId {
2474        operation_queue::Operation::lamport_timestamp(self).replica_id
2475    }
2476
2477    pub fn local_timestamp(&self) -> clock::Local {
2478        match self {
2479            Operation::Edit(edit) => edit.timestamp.local(),
2480            Operation::Undo { undo, .. } => undo.id,
2481        }
2482    }
2483
2484    pub fn as_edit(&self) -> Option<&EditOperation> {
2485        match self {
2486            Operation::Edit(edit) => Some(edit),
2487            _ => None,
2488        }
2489    }
2490
2491    pub fn is_edit(&self) -> bool {
2492        matches!(self, Operation::Edit { .. })
2493    }
2494}
2495
2496impl operation_queue::Operation for Operation {
2497    fn lamport_timestamp(&self) -> clock::Lamport {
2498        match self {
2499            Operation::Edit(edit) => edit.timestamp.lamport(),
2500            Operation::Undo {
2501                lamport_timestamp, ..
2502            } => *lamport_timestamp,
2503        }
2504    }
2505}
2506
2507pub trait ToOffset {
2508    fn to_offset(&self, snapshot: &BufferSnapshot) -> usize;
2509}
2510
2511impl ToOffset for Point {
2512    fn to_offset(&self, snapshot: &BufferSnapshot) -> usize {
2513        snapshot.point_to_offset(*self)
2514    }
2515}
2516
2517impl ToOffset for usize {
2518    fn to_offset(&self, snapshot: &BufferSnapshot) -> usize {
2519        assert!(
2520            *self <= snapshot.len(),
2521            "offset {} is out of range, max allowed is {}",
2522            self,
2523            snapshot.len()
2524        );
2525        *self
2526    }
2527}
2528
2529impl ToOffset for Anchor {
2530    fn to_offset(&self, snapshot: &BufferSnapshot) -> usize {
2531        snapshot.summary_for_anchor(self)
2532    }
2533}
2534
2535impl<'a, T: ToOffset> ToOffset for &'a T {
2536    fn to_offset(&self, content: &BufferSnapshot) -> usize {
2537        (*self).to_offset(content)
2538    }
2539}
2540
2541impl ToOffset for PointUtf16 {
2542    fn to_offset(&self, snapshot: &BufferSnapshot) -> usize {
2543        snapshot.point_utf16_to_offset(*self)
2544    }
2545}
2546
2547impl ToOffset for Unclipped<PointUtf16> {
2548    fn to_offset(&self, snapshot: &BufferSnapshot) -> usize {
2549        snapshot.unclipped_point_utf16_to_offset(*self)
2550    }
2551}
2552
2553pub trait ToPoint {
2554    fn to_point(&self, snapshot: &BufferSnapshot) -> Point;
2555}
2556
2557impl ToPoint for Anchor {
2558    fn to_point(&self, snapshot: &BufferSnapshot) -> Point {
2559        snapshot.summary_for_anchor(self)
2560    }
2561}
2562
2563impl ToPoint for usize {
2564    fn to_point(&self, snapshot: &BufferSnapshot) -> Point {
2565        snapshot.offset_to_point(*self)
2566    }
2567}
2568
2569impl ToPoint for Point {
2570    fn to_point(&self, _: &BufferSnapshot) -> Point {
2571        *self
2572    }
2573}
2574
2575impl ToPoint for Unclipped<PointUtf16> {
2576    fn to_point(&self, snapshot: &BufferSnapshot) -> Point {
2577        snapshot.unclipped_point_utf16_to_point(*self)
2578    }
2579}
2580
2581pub trait ToPointUtf16 {
2582    fn to_point_utf16(&self, snapshot: &BufferSnapshot) -> PointUtf16;
2583}
2584
2585impl ToPointUtf16 for Anchor {
2586    fn to_point_utf16(&self, snapshot: &BufferSnapshot) -> PointUtf16 {
2587        snapshot.summary_for_anchor(self)
2588    }
2589}
2590
2591impl ToPointUtf16 for usize {
2592    fn to_point_utf16(&self, snapshot: &BufferSnapshot) -> PointUtf16 {
2593        snapshot.offset_to_point_utf16(*self)
2594    }
2595}
2596
2597impl ToPointUtf16 for PointUtf16 {
2598    fn to_point_utf16(&self, _: &BufferSnapshot) -> PointUtf16 {
2599        *self
2600    }
2601}
2602
2603impl ToPointUtf16 for Point {
2604    fn to_point_utf16(&self, snapshot: &BufferSnapshot) -> PointUtf16 {
2605        snapshot.point_to_point_utf16(*self)
2606    }
2607}
2608
2609pub trait ToOffsetUtf16 {
2610    fn to_offset_utf16(&self, snapshot: &BufferSnapshot) -> OffsetUtf16;
2611}
2612
2613impl ToOffsetUtf16 for Anchor {
2614    fn to_offset_utf16(&self, snapshot: &BufferSnapshot) -> OffsetUtf16 {
2615        snapshot.summary_for_anchor(self)
2616    }
2617}
2618
2619impl ToOffsetUtf16 for usize {
2620    fn to_offset_utf16(&self, snapshot: &BufferSnapshot) -> OffsetUtf16 {
2621        snapshot.offset_to_offset_utf16(*self)
2622    }
2623}
2624
2625impl ToOffsetUtf16 for OffsetUtf16 {
2626    fn to_offset_utf16(&self, _snapshot: &BufferSnapshot) -> OffsetUtf16 {
2627        *self
2628    }
2629}
2630
2631pub trait FromAnchor {
2632    fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self;
2633}
2634
2635impl FromAnchor for Point {
2636    fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
2637        snapshot.summary_for_anchor(anchor)
2638    }
2639}
2640
2641impl FromAnchor for PointUtf16 {
2642    fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
2643        snapshot.summary_for_anchor(anchor)
2644    }
2645}
2646
2647impl FromAnchor for usize {
2648    fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
2649        snapshot.summary_for_anchor(anchor)
2650    }
2651}