1mod anchor;
   2pub mod locator;
   3pub mod operation_queue;
   4mod patch;
   5mod point;
   6mod point_utf16;
   7#[cfg(any(test, feature = "test-support"))]
   8pub mod random_char_iter;
   9pub mod rope;
  10mod selection;
  11pub mod subscription;
  12#[cfg(test)]
  13mod tests;
  14
  15pub use anchor::*;
  16use anyhow::Result;
  17use clock::ReplicaId;
  18use collections::{HashMap, HashSet};
  19use locator::Locator;
  20use operation_queue::OperationQueue;
  21pub use patch::Patch;
  22pub use point::*;
  23pub use point_utf16::*;
  24#[cfg(any(test, feature = "test-support"))]
  25pub use random_char_iter::*;
  26use rope::TextDimension;
  27pub use rope::{Chunks, Rope, TextSummary};
  28pub use selection::*;
  29use std::{
  30    cmp::{self, Ordering},
  31    iter::Iterator,
  32    ops::{self, Deref, Range, Sub},
  33    str,
  34    sync::Arc,
  35    time::{Duration, Instant},
  36};
  37pub use subscription::*;
  38pub use sum_tree::Bias;
  39use sum_tree::{FilterCursor, SumTree};
  40
  41pub type TransactionId = usize;
  42
  43pub struct Buffer {
  44    snapshot: BufferSnapshot,
  45    last_edit: clock::Local,
  46    history: History,
  47    deferred_ops: OperationQueue<Operation>,
  48    deferred_replicas: HashSet<ReplicaId>,
  49    replica_id: ReplicaId,
  50    remote_id: u64,
  51    local_clock: clock::Local,
  52    pub lamport_clock: clock::Lamport,
  53    subscriptions: Topic,
  54}
  55
  56#[derive(Clone, Debug)]
  57pub struct BufferSnapshot {
  58    replica_id: ReplicaId,
  59    visible_text: Rope,
  60    deleted_text: Rope,
  61    undo_map: UndoMap,
  62    fragments: SumTree<Fragment>,
  63    insertions: SumTree<InsertionFragment>,
  64    pub version: clock::Global,
  65}
  66
  67#[derive(Clone, Debug)]
  68pub struct Transaction {
  69    id: TransactionId,
  70    start: clock::Global,
  71    end: clock::Global,
  72    edits: Vec<clock::Local>,
  73    ranges: Vec<Range<FullOffset>>,
  74    first_edit_at: Instant,
  75    last_edit_at: Instant,
  76}
  77
  78impl Transaction {
  79    fn push_edit(&mut self, edit: &EditOperation) {
  80        self.edits.push(edit.timestamp.local());
  81        self.end.observe(edit.timestamp.local());
  82
  83        let mut other_ranges = edit.ranges.iter().peekable();
  84        let mut new_ranges = Vec::new();
  85        let insertion_len = edit.new_text.as_ref().map_or(0, |t| t.len());
  86        let mut delta = 0;
  87
  88        for mut self_range in self.ranges.iter().cloned() {
  89            self_range.start += delta;
  90            self_range.end += delta;
  91
  92            while let Some(other_range) = other_ranges.peek() {
  93                let mut other_range = (*other_range).clone();
  94                other_range.start += delta;
  95                other_range.end += delta;
  96
  97                if other_range.start <= self_range.end {
  98                    other_ranges.next().unwrap();
  99                    delta += insertion_len;
 100
 101                    if other_range.end < self_range.start {
 102                        new_ranges.push(other_range.start..other_range.end + insertion_len);
 103                        self_range.start += insertion_len;
 104                        self_range.end += insertion_len;
 105                    } else {
 106                        self_range.start = cmp::min(self_range.start, other_range.start);
 107                        self_range.end = cmp::max(self_range.end, other_range.end) + insertion_len;
 108                    }
 109                } else {
 110                    break;
 111                }
 112            }
 113
 114            new_ranges.push(self_range);
 115        }
 116
 117        for other_range in other_ranges {
 118            new_ranges.push(other_range.start + delta..other_range.end + delta + insertion_len);
 119            delta += insertion_len;
 120        }
 121
 122        self.ranges = new_ranges;
 123    }
 124}
 125
 126#[derive(Clone)]
 127pub struct History {
 128    // TODO: Turn this into a String or Rope, maybe.
 129    pub base_text: Arc<str>,
 130    ops: HashMap<clock::Local, EditOperation>,
 131    undo_stack: Vec<Transaction>,
 132    redo_stack: Vec<Transaction>,
 133    transaction_depth: usize,
 134    group_interval: Duration,
 135    next_transaction_id: TransactionId,
 136}
 137
 138impl History {
 139    pub fn new(base_text: Arc<str>) -> Self {
 140        Self {
 141            base_text,
 142            ops: Default::default(),
 143            undo_stack: Vec::new(),
 144            redo_stack: Vec::new(),
 145            transaction_depth: 0,
 146            group_interval: Duration::from_millis(300),
 147            next_transaction_id: 0,
 148        }
 149    }
 150
 151    fn push(&mut self, op: EditOperation) {
 152        self.ops.insert(op.timestamp.local(), op);
 153    }
 154
 155    fn start_transaction(&mut self, start: clock::Global, now: Instant) -> Option<TransactionId> {
 156        self.transaction_depth += 1;
 157        if self.transaction_depth == 1 {
 158            let id = self.next_transaction_id;
 159            self.next_transaction_id += 1;
 160            self.undo_stack.push(Transaction {
 161                id,
 162                start: start.clone(),
 163                end: start,
 164                edits: Vec::new(),
 165                ranges: Vec::new(),
 166                first_edit_at: now,
 167                last_edit_at: now,
 168            });
 169            Some(id)
 170        } else {
 171            None
 172        }
 173    }
 174
 175    fn end_transaction(&mut self, now: Instant) -> Option<&Transaction> {
 176        assert_ne!(self.transaction_depth, 0);
 177        self.transaction_depth -= 1;
 178        if self.transaction_depth == 0 {
 179            if self.undo_stack.last().unwrap().ranges.is_empty() {
 180                self.undo_stack.pop();
 181                None
 182            } else {
 183                let transaction = self.undo_stack.last_mut().unwrap();
 184                transaction.last_edit_at = now;
 185                Some(transaction)
 186            }
 187        } else {
 188            None
 189        }
 190    }
 191
 192    fn group(&mut self) -> Option<TransactionId> {
 193        let mut new_len = self.undo_stack.len();
 194        let mut transactions = self.undo_stack.iter_mut();
 195
 196        if let Some(mut transaction) = transactions.next_back() {
 197            while let Some(prev_transaction) = transactions.next_back() {
 198                if transaction.first_edit_at - prev_transaction.last_edit_at <= self.group_interval
 199                    && transaction.start == prev_transaction.end
 200                {
 201                    transaction = prev_transaction;
 202                    new_len -= 1;
 203                } else {
 204                    break;
 205                }
 206            }
 207        }
 208
 209        let (transactions_to_keep, transactions_to_merge) = self.undo_stack.split_at_mut(new_len);
 210        if let Some(last_transaction) = transactions_to_keep.last_mut() {
 211            for transaction in &*transactions_to_merge {
 212                for edit_id in &transaction.edits {
 213                    last_transaction.push_edit(&self.ops[edit_id]);
 214                }
 215            }
 216
 217            if let Some(transaction) = transactions_to_merge.last_mut() {
 218                last_transaction.last_edit_at = transaction.last_edit_at;
 219                last_transaction.end = transaction.end.clone();
 220            }
 221        }
 222
 223        self.undo_stack.truncate(new_len);
 224        self.undo_stack.last().map(|t| t.id)
 225    }
 226
 227    fn push_undo(&mut self, edit_id: clock::Local) {
 228        assert_ne!(self.transaction_depth, 0);
 229        let last_transaction = self.undo_stack.last_mut().unwrap();
 230        last_transaction.push_edit(&self.ops[&edit_id]);
 231    }
 232
 233    fn pop_undo(&mut self) -> Option<&Transaction> {
 234        assert_eq!(self.transaction_depth, 0);
 235        if let Some(transaction) = self.undo_stack.pop() {
 236            self.redo_stack.push(transaction);
 237            self.redo_stack.last()
 238        } else {
 239            None
 240        }
 241    }
 242
 243    fn remove_from_undo(&mut self, transaction_id: TransactionId) -> Option<&Transaction> {
 244        assert_eq!(self.transaction_depth, 0);
 245        if let Some(transaction_ix) = self.undo_stack.iter().rposition(|t| t.id == transaction_id) {
 246            let transaction = self.undo_stack.remove(transaction_ix);
 247            self.redo_stack.push(transaction);
 248            self.redo_stack.last()
 249        } else {
 250            None
 251        }
 252    }
 253
 254    fn pop_redo(&mut self) -> Option<&Transaction> {
 255        assert_eq!(self.transaction_depth, 0);
 256        if let Some(transaction) = self.redo_stack.pop() {
 257            self.undo_stack.push(transaction);
 258            self.undo_stack.last()
 259        } else {
 260            None
 261        }
 262    }
 263
 264    fn remove_from_redo(&mut self, transaction_id: TransactionId) -> Option<&Transaction> {
 265        assert_eq!(self.transaction_depth, 0);
 266        if let Some(transaction_ix) = self.redo_stack.iter().rposition(|t| t.id == transaction_id) {
 267            let transaction = self.redo_stack.remove(transaction_ix);
 268            self.undo_stack.push(transaction);
 269            self.undo_stack.last()
 270        } else {
 271            None
 272        }
 273    }
 274}
 275
 276#[derive(Clone, Default, Debug)]
 277struct UndoMap(HashMap<clock::Local, Vec<(clock::Local, u32)>>);
 278
 279impl UndoMap {
 280    fn insert(&mut self, undo: &UndoOperation) {
 281        for (edit_id, count) in &undo.counts {
 282            self.0.entry(*edit_id).or_default().push((undo.id, *count));
 283        }
 284    }
 285
 286    fn is_undone(&self, edit_id: clock::Local) -> bool {
 287        self.undo_count(edit_id) % 2 == 1
 288    }
 289
 290    fn was_undone(&self, edit_id: clock::Local, version: &clock::Global) -> bool {
 291        let undo_count = self
 292            .0
 293            .get(&edit_id)
 294            .unwrap_or(&Vec::new())
 295            .iter()
 296            .filter(|(undo_id, _)| version.observed(*undo_id))
 297            .map(|(_, undo_count)| *undo_count)
 298            .max()
 299            .unwrap_or(0);
 300        undo_count % 2 == 1
 301    }
 302
 303    fn undo_count(&self, edit_id: clock::Local) -> u32 {
 304        self.0
 305            .get(&edit_id)
 306            .unwrap_or(&Vec::new())
 307            .iter()
 308            .map(|(_, undo_count)| *undo_count)
 309            .max()
 310            .unwrap_or(0)
 311    }
 312}
 313
 314struct Edits<'a, D: TextDimension, F: FnMut(&FragmentSummary) -> bool> {
 315    visible_cursor: rope::Cursor<'a>,
 316    deleted_cursor: rope::Cursor<'a>,
 317    fragments_cursor: Option<FilterCursor<'a, F, Fragment, FragmentTextSummary>>,
 318    undos: &'a UndoMap,
 319    since: &'a clock::Global,
 320    old_end: D,
 321    new_end: D,
 322    range: Range<(&'a Locator, usize)>,
 323}
 324
 325#[derive(Clone, Debug, Default, Eq, PartialEq)]
 326pub struct Edit<D> {
 327    pub old: Range<D>,
 328    pub new: Range<D>,
 329}
 330
 331impl<D> Edit<D>
 332where
 333    D: Sub<D, Output = D> + PartialEq + Copy,
 334{
 335    pub fn old_len(&self) -> D {
 336        self.old.end - self.old.start
 337    }
 338
 339    pub fn new_len(&self) -> D {
 340        self.new.end - self.new.start
 341    }
 342
 343    pub fn is_empty(&self) -> bool {
 344        self.old.start == self.old.end && self.new.start == self.new.end
 345    }
 346}
 347
 348impl<D1, D2> Edit<(D1, D2)> {
 349    pub fn flatten(self) -> (Edit<D1>, Edit<D2>) {
 350        (
 351            Edit {
 352                old: self.old.start.0..self.old.end.0,
 353                new: self.new.start.0..self.new.end.0,
 354            },
 355            Edit {
 356                old: self.old.start.1..self.old.end.1,
 357                new: self.new.start.1..self.new.end.1,
 358            },
 359        )
 360    }
 361}
 362
 363#[derive(Copy, Clone, Debug, Default, Eq, PartialEq, PartialOrd, Ord)]
 364pub struct InsertionTimestamp {
 365    pub replica_id: ReplicaId,
 366    pub local: clock::Seq,
 367    pub lamport: clock::Seq,
 368}
 369
 370impl InsertionTimestamp {
 371    fn local(&self) -> clock::Local {
 372        clock::Local {
 373            replica_id: self.replica_id,
 374            value: self.local,
 375        }
 376    }
 377
 378    fn lamport(&self) -> clock::Lamport {
 379        clock::Lamport {
 380            replica_id: self.replica_id,
 381            value: self.lamport,
 382        }
 383    }
 384}
 385
 386#[derive(Eq, PartialEq, Clone, Debug)]
 387struct Fragment {
 388    id: Locator,
 389    insertion_timestamp: InsertionTimestamp,
 390    insertion_offset: usize,
 391    len: usize,
 392    visible: bool,
 393    deletions: HashSet<clock::Local>,
 394    max_undos: clock::Global,
 395}
 396
 397#[derive(Eq, PartialEq, Clone, Debug)]
 398pub struct FragmentSummary {
 399    text: FragmentTextSummary,
 400    max_id: Locator,
 401    max_version: clock::Global,
 402    min_insertion_version: clock::Global,
 403    max_insertion_version: clock::Global,
 404}
 405
 406#[derive(Copy, Default, Clone, Debug, PartialEq, Eq)]
 407struct FragmentTextSummary {
 408    visible: usize,
 409    deleted: usize,
 410}
 411
 412impl<'a> sum_tree::Dimension<'a, FragmentSummary> for FragmentTextSummary {
 413    fn add_summary(&mut self, summary: &'a FragmentSummary, _: &Option<clock::Global>) {
 414        self.visible += summary.text.visible;
 415        self.deleted += summary.text.deleted;
 416    }
 417}
 418
 419#[derive(Eq, PartialEq, Clone, Debug)]
 420struct InsertionFragment {
 421    timestamp: clock::Local,
 422    split_offset: usize,
 423    fragment_id: Locator,
 424}
 425
 426#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord)]
 427struct InsertionFragmentKey {
 428    timestamp: clock::Local,
 429    split_offset: usize,
 430}
 431
 432#[derive(Clone, Debug, Eq, PartialEq)]
 433pub enum Operation {
 434    Edit(EditOperation),
 435    Undo {
 436        undo: UndoOperation,
 437        lamport_timestamp: clock::Lamport,
 438    },
 439}
 440
 441#[derive(Clone, Debug, Eq, PartialEq)]
 442pub struct EditOperation {
 443    pub timestamp: InsertionTimestamp,
 444    pub version: clock::Global,
 445    pub ranges: Vec<Range<FullOffset>>,
 446    pub new_text: Option<String>,
 447}
 448
 449#[derive(Clone, Debug, Eq, PartialEq)]
 450pub struct UndoOperation {
 451    pub id: clock::Local,
 452    pub counts: HashMap<clock::Local, u32>,
 453    pub ranges: Vec<Range<FullOffset>>,
 454    pub version: clock::Global,
 455}
 456
 457impl Buffer {
 458    pub fn new(replica_id: u16, remote_id: u64, history: History) -> Buffer {
 459        let mut fragments = SumTree::new();
 460        let mut insertions = SumTree::new();
 461
 462        let mut local_clock = clock::Local::new(replica_id);
 463        let mut lamport_clock = clock::Lamport::new(replica_id);
 464        let mut version = clock::Global::new();
 465        let visible_text = Rope::from(history.base_text.as_ref());
 466        if visible_text.len() > 0 {
 467            let insertion_timestamp = InsertionTimestamp {
 468                replica_id: 0,
 469                local: 1,
 470                lamport: 1,
 471            };
 472            local_clock.observe(insertion_timestamp.local());
 473            lamport_clock.observe(insertion_timestamp.lamport());
 474            version.observe(insertion_timestamp.local());
 475            let fragment_id = Locator::between(&Locator::min(), &Locator::max());
 476            let fragment = Fragment {
 477                id: fragment_id,
 478                insertion_timestamp,
 479                insertion_offset: 0,
 480                len: visible_text.len(),
 481                visible: true,
 482                deletions: Default::default(),
 483                max_undos: Default::default(),
 484            };
 485            insertions.push(InsertionFragment::new(&fragment), &());
 486            fragments.push(fragment, &None);
 487        }
 488
 489        Buffer {
 490            snapshot: BufferSnapshot {
 491                replica_id,
 492                visible_text,
 493                deleted_text: Rope::new(),
 494                fragments,
 495                insertions,
 496                version,
 497                undo_map: Default::default(),
 498            },
 499            last_edit: clock::Local::default(),
 500            history,
 501            deferred_ops: OperationQueue::new(),
 502            deferred_replicas: HashSet::default(),
 503            replica_id,
 504            remote_id,
 505            local_clock,
 506            lamport_clock,
 507            subscriptions: Default::default(),
 508        }
 509    }
 510
 511    pub fn version(&self) -> clock::Global {
 512        self.version.clone()
 513    }
 514
 515    pub fn snapshot(&self) -> BufferSnapshot {
 516        self.snapshot.clone()
 517    }
 518
 519    pub fn replica_id(&self) -> ReplicaId {
 520        self.local_clock.replica_id
 521    }
 522
 523    pub fn remote_id(&self) -> u64 {
 524        self.remote_id
 525    }
 526
 527    pub fn deferred_ops_len(&self) -> usize {
 528        self.deferred_ops.len()
 529    }
 530
 531    pub fn transaction_group_interval(&self) -> Duration {
 532        self.history.group_interval
 533    }
 534
 535    pub fn edit<R, I, S, T>(&mut self, ranges: R, new_text: T) -> EditOperation
 536    where
 537        R: IntoIterator<IntoIter = I>,
 538        I: ExactSizeIterator<Item = Range<S>>,
 539        S: ToOffset,
 540        T: Into<String>,
 541    {
 542        let new_text = new_text.into();
 543        let new_text_len = new_text.len();
 544        let new_text = if new_text_len > 0 {
 545            Some(new_text)
 546        } else {
 547            None
 548        };
 549
 550        self.start_transaction();
 551        let timestamp = InsertionTimestamp {
 552            replica_id: self.replica_id,
 553            local: self.local_clock.tick().value,
 554            lamport: self.lamport_clock.tick().value,
 555        };
 556        let edit = self.apply_local_edit(ranges.into_iter(), new_text, timestamp);
 557
 558        self.history.push(edit.clone());
 559        self.history.push_undo(edit.timestamp.local());
 560        self.last_edit = edit.timestamp.local();
 561        self.snapshot.version.observe(edit.timestamp.local());
 562        self.end_transaction();
 563        edit
 564    }
 565
 566    fn apply_local_edit<S: ToOffset>(
 567        &mut self,
 568        ranges: impl ExactSizeIterator<Item = Range<S>>,
 569        new_text: Option<String>,
 570        timestamp: InsertionTimestamp,
 571    ) -> EditOperation {
 572        let mut edits = Patch::default();
 573        let mut edit_op = EditOperation {
 574            timestamp,
 575            version: self.version(),
 576            ranges: Vec::with_capacity(ranges.len()),
 577            new_text: None,
 578        };
 579        let mut new_insertions = Vec::new();
 580        let mut insertion_offset = 0;
 581
 582        let mut ranges = ranges
 583            .map(|range| range.start.to_offset(&*self)..range.end.to_offset(&*self))
 584            .peekable();
 585
 586        let mut new_ropes =
 587            RopeBuilder::new(self.visible_text.cursor(0), self.deleted_text.cursor(0));
 588        let mut old_fragments = self.fragments.cursor::<FragmentTextSummary>();
 589        let mut new_fragments =
 590            old_fragments.slice(&ranges.peek().unwrap().start, Bias::Right, &None);
 591        new_ropes.push_tree(new_fragments.summary().text);
 592
 593        let mut fragment_start = old_fragments.start().visible;
 594        for range in ranges {
 595            let fragment_end = old_fragments.end(&None).visible;
 596
 597            // If the current fragment ends before this range, then jump ahead to the first fragment
 598            // that extends past the start of this range, reusing any intervening fragments.
 599            if fragment_end < range.start {
 600                // If the current fragment has been partially consumed, then consume the rest of it
 601                // and advance to the next fragment before slicing.
 602                if fragment_start > old_fragments.start().visible {
 603                    if fragment_end > fragment_start {
 604                        let mut suffix = old_fragments.item().unwrap().clone();
 605                        suffix.len = fragment_end - fragment_start;
 606                        suffix.insertion_offset += fragment_start - old_fragments.start().visible;
 607                        new_insertions.push(InsertionFragment::insert_new(&suffix));
 608                        new_ropes.push_fragment(&suffix, suffix.visible);
 609                        new_fragments.push(suffix, &None);
 610                    }
 611                    old_fragments.next(&None);
 612                }
 613
 614                let slice = old_fragments.slice(&range.start, Bias::Right, &None);
 615                new_ropes.push_tree(slice.summary().text);
 616                new_fragments.push_tree(slice, &None);
 617                fragment_start = old_fragments.start().visible;
 618            }
 619
 620            let full_range_start = FullOffset(range.start + old_fragments.start().deleted);
 621
 622            // Preserve any portion of the current fragment that precedes this range.
 623            if fragment_start < range.start {
 624                let mut prefix = old_fragments.item().unwrap().clone();
 625                prefix.len = range.start - fragment_start;
 626                prefix.insertion_offset += fragment_start - old_fragments.start().visible;
 627                prefix.id = Locator::between(&new_fragments.summary().max_id, &prefix.id);
 628                new_insertions.push(InsertionFragment::insert_new(&prefix));
 629                new_ropes.push_fragment(&prefix, prefix.visible);
 630                new_fragments.push(prefix, &None);
 631                fragment_start = range.start;
 632            }
 633
 634            // Insert the new text before any existing fragments within the range.
 635            if let Some(new_text) = new_text.as_deref() {
 636                let new_start = new_fragments.summary().text.visible;
 637                edits.push(Edit {
 638                    old: fragment_start..fragment_start,
 639                    new: new_start..new_start + new_text.len(),
 640                });
 641                let fragment = Fragment {
 642                    id: Locator::between(
 643                        &new_fragments.summary().max_id,
 644                        old_fragments
 645                            .item()
 646                            .map_or(&Locator::max(), |old_fragment| &old_fragment.id),
 647                    ),
 648                    insertion_timestamp: timestamp,
 649                    insertion_offset,
 650                    len: new_text.len(),
 651                    deletions: Default::default(),
 652                    max_undos: Default::default(),
 653                    visible: true,
 654                };
 655                new_insertions.push(InsertionFragment::insert_new(&fragment));
 656                new_ropes.push_str(new_text);
 657                new_fragments.push(fragment, &None);
 658                insertion_offset += new_text.len();
 659            }
 660
 661            // Advance through every fragment that intersects this range, marking the intersecting
 662            // portions as deleted.
 663            while fragment_start < range.end {
 664                let fragment = old_fragments.item().unwrap();
 665                let fragment_end = old_fragments.end(&None).visible;
 666                let mut intersection = fragment.clone();
 667                let intersection_end = cmp::min(range.end, fragment_end);
 668                if fragment.visible {
 669                    intersection.len = intersection_end - fragment_start;
 670                    intersection.insertion_offset += fragment_start - old_fragments.start().visible;
 671                    intersection.id =
 672                        Locator::between(&new_fragments.summary().max_id, &intersection.id);
 673                    intersection.deletions.insert(timestamp.local());
 674                    intersection.visible = false;
 675                }
 676                if intersection.len > 0 {
 677                    if fragment.visible && !intersection.visible {
 678                        let new_start = new_fragments.summary().text.visible;
 679                        edits.push(Edit {
 680                            old: fragment_start..intersection_end,
 681                            new: new_start..new_start,
 682                        });
 683                    }
 684                    new_insertions.push(InsertionFragment::insert_new(&intersection));
 685                    new_ropes.push_fragment(&intersection, fragment.visible);
 686                    new_fragments.push(intersection, &None);
 687                    fragment_start = intersection_end;
 688                }
 689                if fragment_end <= range.end {
 690                    old_fragments.next(&None);
 691                }
 692            }
 693
 694            let full_range_end = FullOffset(range.end + old_fragments.start().deleted);
 695            edit_op.ranges.push(full_range_start..full_range_end);
 696        }
 697
 698        // If the current fragment has been partially consumed, then consume the rest of it
 699        // and advance to the next fragment before slicing.
 700        if fragment_start > old_fragments.start().visible {
 701            let fragment_end = old_fragments.end(&None).visible;
 702            if fragment_end > fragment_start {
 703                let mut suffix = old_fragments.item().unwrap().clone();
 704                suffix.len = fragment_end - fragment_start;
 705                suffix.insertion_offset += fragment_start - old_fragments.start().visible;
 706                new_insertions.push(InsertionFragment::insert_new(&suffix));
 707                new_ropes.push_fragment(&suffix, suffix.visible);
 708                new_fragments.push(suffix, &None);
 709            }
 710            old_fragments.next(&None);
 711        }
 712
 713        let suffix = old_fragments.suffix(&None);
 714        new_ropes.push_tree(suffix.summary().text);
 715        new_fragments.push_tree(suffix, &None);
 716        let (visible_text, deleted_text) = new_ropes.finish();
 717        drop(old_fragments);
 718
 719        self.snapshot.fragments = new_fragments;
 720        self.snapshot.insertions.edit(new_insertions, &());
 721        self.snapshot.visible_text = visible_text;
 722        self.snapshot.deleted_text = deleted_text;
 723        self.subscriptions.publish_mut(&edits);
 724        edit_op.new_text = new_text;
 725        edit_op
 726    }
 727
 728    pub fn apply_ops<I: IntoIterator<Item = Operation>>(&mut self, ops: I) -> Result<()> {
 729        let mut deferred_ops = Vec::new();
 730        for op in ops {
 731            if self.can_apply_op(&op) {
 732                self.apply_op(op)?;
 733            } else {
 734                self.deferred_replicas.insert(op.replica_id());
 735                deferred_ops.push(op);
 736            }
 737        }
 738        self.deferred_ops.insert(deferred_ops);
 739        self.flush_deferred_ops()?;
 740        Ok(())
 741    }
 742
 743    fn apply_op(&mut self, op: Operation) -> Result<()> {
 744        match op {
 745            Operation::Edit(edit) => {
 746                if !self.version.observed(edit.timestamp.local()) {
 747                    self.apply_remote_edit(
 748                        &edit.version,
 749                        &edit.ranges,
 750                        edit.new_text.as_deref(),
 751                        edit.timestamp,
 752                    );
 753                    self.snapshot.version.observe(edit.timestamp.local());
 754                    self.history.push(edit);
 755                }
 756            }
 757            Operation::Undo {
 758                undo,
 759                lamport_timestamp,
 760            } => {
 761                if !self.version.observed(undo.id) {
 762                    self.apply_undo(&undo)?;
 763                    self.snapshot.version.observe(undo.id);
 764                    self.lamport_clock.observe(lamport_timestamp);
 765                }
 766            }
 767        }
 768        Ok(())
 769    }
 770
 771    fn apply_remote_edit(
 772        &mut self,
 773        version: &clock::Global,
 774        ranges: &[Range<FullOffset>],
 775        new_text: Option<&str>,
 776        timestamp: InsertionTimestamp,
 777    ) {
 778        if ranges.is_empty() {
 779            return;
 780        }
 781
 782        let mut edits = Patch::default();
 783        let cx = Some(version.clone());
 784        let mut new_insertions = Vec::new();
 785        let mut insertion_offset = 0;
 786        let mut new_ropes =
 787            RopeBuilder::new(self.visible_text.cursor(0), self.deleted_text.cursor(0));
 788        let mut old_fragments = self.fragments.cursor::<(VersionedFullOffset, usize)>();
 789        let mut new_fragments = old_fragments.slice(
 790            &VersionedFullOffset::Offset(ranges[0].start),
 791            Bias::Left,
 792            &cx,
 793        );
 794        new_ropes.push_tree(new_fragments.summary().text);
 795
 796        let mut fragment_start = old_fragments.start().0.full_offset();
 797        for range in ranges {
 798            let fragment_end = old_fragments.end(&cx).0.full_offset();
 799
 800            // If the current fragment ends before this range, then jump ahead to the first fragment
 801            // that extends past the start of this range, reusing any intervening fragments.
 802            if fragment_end < range.start {
 803                // If the current fragment has been partially consumed, then consume the rest of it
 804                // and advance to the next fragment before slicing.
 805                if fragment_start > old_fragments.start().0.full_offset() {
 806                    if fragment_end > fragment_start {
 807                        let mut suffix = old_fragments.item().unwrap().clone();
 808                        suffix.len = fragment_end.0 - fragment_start.0;
 809                        suffix.insertion_offset +=
 810                            fragment_start - old_fragments.start().0.full_offset();
 811                        new_insertions.push(InsertionFragment::insert_new(&suffix));
 812                        new_ropes.push_fragment(&suffix, suffix.visible);
 813                        new_fragments.push(suffix, &None);
 814                    }
 815                    old_fragments.next(&cx);
 816                }
 817
 818                let slice =
 819                    old_fragments.slice(&VersionedFullOffset::Offset(range.start), Bias::Left, &cx);
 820                new_ropes.push_tree(slice.summary().text);
 821                new_fragments.push_tree(slice, &None);
 822                fragment_start = old_fragments.start().0.full_offset();
 823            }
 824
 825            // If we are at the end of a non-concurrent fragment, advance to the next one.
 826            let fragment_end = old_fragments.end(&cx).0.full_offset();
 827            if fragment_end == range.start && fragment_end > fragment_start {
 828                let mut fragment = old_fragments.item().unwrap().clone();
 829                fragment.len = fragment_end.0 - fragment_start.0;
 830                fragment.insertion_offset += fragment_start - old_fragments.start().0.full_offset();
 831                new_insertions.push(InsertionFragment::insert_new(&fragment));
 832                new_ropes.push_fragment(&fragment, fragment.visible);
 833                new_fragments.push(fragment, &None);
 834                old_fragments.next(&cx);
 835                fragment_start = old_fragments.start().0.full_offset();
 836            }
 837
 838            // Skip over insertions that are concurrent to this edit, but have a lower lamport
 839            // timestamp.
 840            while let Some(fragment) = old_fragments.item() {
 841                if fragment_start == range.start
 842                    && fragment.insertion_timestamp.lamport() > timestamp.lamport()
 843                {
 844                    new_ropes.push_fragment(fragment, fragment.visible);
 845                    new_fragments.push(fragment.clone(), &None);
 846                    old_fragments.next(&cx);
 847                    debug_assert_eq!(fragment_start, range.start);
 848                } else {
 849                    break;
 850                }
 851            }
 852            debug_assert!(fragment_start <= range.start);
 853
 854            // Preserve any portion of the current fragment that precedes this range.
 855            if fragment_start < range.start {
 856                let mut prefix = old_fragments.item().unwrap().clone();
 857                prefix.len = range.start.0 - fragment_start.0;
 858                prefix.insertion_offset += fragment_start - old_fragments.start().0.full_offset();
 859                prefix.id = Locator::between(&new_fragments.summary().max_id, &prefix.id);
 860                new_insertions.push(InsertionFragment::insert_new(&prefix));
 861                fragment_start = range.start;
 862                new_ropes.push_fragment(&prefix, prefix.visible);
 863                new_fragments.push(prefix, &None);
 864            }
 865
 866            // Insert the new text before any existing fragments within the range.
 867            if let Some(new_text) = new_text {
 868                let mut old_start = old_fragments.start().1;
 869                if old_fragments.item().map_or(false, |f| f.visible) {
 870                    old_start += fragment_start.0 - old_fragments.start().0.full_offset().0;
 871                }
 872                let new_start = new_fragments.summary().text.visible;
 873                edits.push(Edit {
 874                    old: old_start..old_start,
 875                    new: new_start..new_start + new_text.len(),
 876                });
 877                let fragment = Fragment {
 878                    id: Locator::between(
 879                        &new_fragments.summary().max_id,
 880                        old_fragments
 881                            .item()
 882                            .map_or(&Locator::max(), |old_fragment| &old_fragment.id),
 883                    ),
 884                    insertion_timestamp: timestamp,
 885                    insertion_offset,
 886                    len: new_text.len(),
 887                    deletions: Default::default(),
 888                    max_undos: Default::default(),
 889                    visible: true,
 890                };
 891                new_insertions.push(InsertionFragment::insert_new(&fragment));
 892                new_ropes.push_str(new_text);
 893                new_fragments.push(fragment, &None);
 894                insertion_offset += new_text.len();
 895            }
 896
 897            // Advance through every fragment that intersects this range, marking the intersecting
 898            // portions as deleted.
 899            while fragment_start < range.end {
 900                let fragment = old_fragments.item().unwrap();
 901                let fragment_end = old_fragments.end(&cx).0.full_offset();
 902                let mut intersection = fragment.clone();
 903                let intersection_end = cmp::min(range.end, fragment_end);
 904                if fragment.was_visible(version, &self.undo_map) {
 905                    intersection.len = intersection_end.0 - fragment_start.0;
 906                    intersection.insertion_offset +=
 907                        fragment_start - old_fragments.start().0.full_offset();
 908                    intersection.id =
 909                        Locator::between(&new_fragments.summary().max_id, &intersection.id);
 910                    intersection.deletions.insert(timestamp.local());
 911                    intersection.visible = false;
 912                }
 913                if intersection.len > 0 {
 914                    if fragment.visible && !intersection.visible {
 915                        let old_start = old_fragments.start().1
 916                            + (fragment_start.0 - old_fragments.start().0.full_offset().0);
 917                        let new_start = new_fragments.summary().text.visible;
 918                        edits.push(Edit {
 919                            old: old_start..old_start + intersection.len,
 920                            new: new_start..new_start,
 921                        });
 922                    }
 923                    new_insertions.push(InsertionFragment::insert_new(&intersection));
 924                    new_ropes.push_fragment(&intersection, fragment.visible);
 925                    new_fragments.push(intersection, &None);
 926                    fragment_start = intersection_end;
 927                }
 928                if fragment_end <= range.end {
 929                    old_fragments.next(&cx);
 930                }
 931            }
 932        }
 933
 934        // If the current fragment has been partially consumed, then consume the rest of it
 935        // and advance to the next fragment before slicing.
 936        if fragment_start > old_fragments.start().0.full_offset() {
 937            let fragment_end = old_fragments.end(&cx).0.full_offset();
 938            if fragment_end > fragment_start {
 939                let mut suffix = old_fragments.item().unwrap().clone();
 940                suffix.len = fragment_end.0 - fragment_start.0;
 941                suffix.insertion_offset += fragment_start - old_fragments.start().0.full_offset();
 942                new_insertions.push(InsertionFragment::insert_new(&suffix));
 943                new_ropes.push_fragment(&suffix, suffix.visible);
 944                new_fragments.push(suffix, &None);
 945            }
 946            old_fragments.next(&cx);
 947        }
 948
 949        let suffix = old_fragments.suffix(&cx);
 950        new_ropes.push_tree(suffix.summary().text);
 951        new_fragments.push_tree(suffix, &None);
 952        let (visible_text, deleted_text) = new_ropes.finish();
 953        drop(old_fragments);
 954
 955        self.snapshot.fragments = new_fragments;
 956        self.snapshot.visible_text = visible_text;
 957        self.snapshot.deleted_text = deleted_text;
 958        self.snapshot.insertions.edit(new_insertions, &());
 959        self.local_clock.observe(timestamp.local());
 960        self.lamport_clock.observe(timestamp.lamport());
 961        self.subscriptions.publish_mut(&edits);
 962    }
 963
 964    fn apply_undo(&mut self, undo: &UndoOperation) -> Result<()> {
 965        let mut edits = Patch::default();
 966        self.snapshot.undo_map.insert(undo);
 967
 968        let mut cx = undo.version.clone();
 969        for edit_id in undo.counts.keys().copied() {
 970            cx.observe(edit_id);
 971        }
 972        let cx = Some(cx);
 973
 974        let mut old_fragments = self.fragments.cursor::<(VersionedFullOffset, usize)>();
 975        let mut new_fragments = old_fragments.slice(
 976            &VersionedFullOffset::Offset(undo.ranges[0].start),
 977            Bias::Right,
 978            &cx,
 979        );
 980        let mut new_ropes =
 981            RopeBuilder::new(self.visible_text.cursor(0), self.deleted_text.cursor(0));
 982        new_ropes.push_tree(new_fragments.summary().text);
 983
 984        for range in &undo.ranges {
 985            let mut end_offset = old_fragments.end(&cx).0.full_offset();
 986
 987            if end_offset < range.start {
 988                let preceding_fragments = old_fragments.slice(
 989                    &VersionedFullOffset::Offset(range.start),
 990                    Bias::Right,
 991                    &cx,
 992                );
 993                new_ropes.push_tree(preceding_fragments.summary().text);
 994                new_fragments.push_tree(preceding_fragments, &None);
 995            }
 996
 997            while end_offset <= range.end {
 998                if let Some(fragment) = old_fragments.item() {
 999                    let mut fragment = fragment.clone();
1000                    let fragment_was_visible = fragment.visible;
1001
1002                    if fragment.was_visible(&undo.version, &self.undo_map)
1003                        || undo
1004                            .counts
1005                            .contains_key(&fragment.insertion_timestamp.local())
1006                    {
1007                        fragment.visible = fragment.is_visible(&self.undo_map);
1008                        fragment.max_undos.observe(undo.id);
1009                    }
1010
1011                    let old_start = old_fragments.start().1;
1012                    let new_start = new_fragments.summary().text.visible;
1013                    if fragment_was_visible && !fragment.visible {
1014                        edits.push(Edit {
1015                            old: old_start..old_start + fragment.len,
1016                            new: new_start..new_start,
1017                        });
1018                    } else if !fragment_was_visible && fragment.visible {
1019                        edits.push(Edit {
1020                            old: old_start..old_start,
1021                            new: new_start..new_start + fragment.len,
1022                        });
1023                    }
1024                    new_ropes.push_fragment(&fragment, fragment_was_visible);
1025                    new_fragments.push(fragment, &None);
1026
1027                    old_fragments.next(&cx);
1028                    if end_offset == old_fragments.end(&cx).0.full_offset() {
1029                        let unseen_fragments = old_fragments.slice(
1030                            &VersionedFullOffset::Offset(end_offset),
1031                            Bias::Right,
1032                            &cx,
1033                        );
1034                        new_ropes.push_tree(unseen_fragments.summary().text);
1035                        new_fragments.push_tree(unseen_fragments, &None);
1036                    }
1037                    end_offset = old_fragments.end(&cx).0.full_offset();
1038                } else {
1039                    break;
1040                }
1041            }
1042        }
1043
1044        let suffix = old_fragments.suffix(&cx);
1045        new_ropes.push_tree(suffix.summary().text);
1046        new_fragments.push_tree(suffix, &None);
1047
1048        drop(old_fragments);
1049        let (visible_text, deleted_text) = new_ropes.finish();
1050        self.snapshot.fragments = new_fragments;
1051        self.snapshot.visible_text = visible_text;
1052        self.snapshot.deleted_text = deleted_text;
1053        self.subscriptions.publish_mut(&edits);
1054        Ok(())
1055    }
1056
1057    fn flush_deferred_ops(&mut self) -> Result<()> {
1058        self.deferred_replicas.clear();
1059        let mut deferred_ops = Vec::new();
1060        for op in self.deferred_ops.drain().iter().cloned() {
1061            if self.can_apply_op(&op) {
1062                self.apply_op(op)?;
1063            } else {
1064                self.deferred_replicas.insert(op.replica_id());
1065                deferred_ops.push(op);
1066            }
1067        }
1068        self.deferred_ops.insert(deferred_ops);
1069        Ok(())
1070    }
1071
1072    fn can_apply_op(&self, op: &Operation) -> bool {
1073        if self.deferred_replicas.contains(&op.replica_id()) {
1074            false
1075        } else {
1076            match op {
1077                Operation::Edit(edit) => self.version.ge(&edit.version),
1078                Operation::Undo { undo, .. } => self.version.ge(&undo.version),
1079            }
1080        }
1081    }
1082
1083    pub fn can_resolve(&self, anchor: &Anchor) -> bool {
1084        *anchor == Anchor::min()
1085            || *anchor == Anchor::max()
1086            || self.version.observed(anchor.timestamp)
1087    }
1088
1089    pub fn peek_undo_stack(&self) -> Option<&Transaction> {
1090        self.history.undo_stack.last()
1091    }
1092
1093    pub fn start_transaction(&mut self) -> Option<TransactionId> {
1094        self.start_transaction_at(Instant::now())
1095    }
1096
1097    pub fn start_transaction_at(&mut self, now: Instant) -> Option<TransactionId> {
1098        self.history.start_transaction(self.version.clone(), now)
1099    }
1100
1101    pub fn end_transaction(&mut self) -> Option<(TransactionId, clock::Global)> {
1102        self.end_transaction_at(Instant::now())
1103    }
1104
1105    pub fn end_transaction_at(&mut self, now: Instant) -> Option<(TransactionId, clock::Global)> {
1106        if let Some(transaction) = self.history.end_transaction(now) {
1107            let since = transaction.start.clone();
1108            let id = self.history.group().unwrap();
1109            Some((id, since))
1110        } else {
1111            None
1112        }
1113    }
1114
1115    pub fn base_text(&self) -> &Arc<str> {
1116        &self.history.base_text
1117    }
1118
1119    pub fn history(&self) -> impl Iterator<Item = &EditOperation> {
1120        self.history.ops.values()
1121    }
1122
1123    pub fn undo(&mut self) -> Option<(TransactionId, Operation)> {
1124        if let Some(transaction) = self.history.pop_undo().cloned() {
1125            let transaction_id = transaction.id;
1126            let op = self.undo_or_redo(transaction).unwrap();
1127            Some((transaction_id, op))
1128        } else {
1129            None
1130        }
1131    }
1132
1133    pub fn undo_transaction(&mut self, transaction_id: TransactionId) -> Option<Operation> {
1134        if let Some(transaction) = self.history.remove_from_undo(transaction_id).cloned() {
1135            let op = self.undo_or_redo(transaction).unwrap();
1136            Some(op)
1137        } else {
1138            None
1139        }
1140    }
1141
1142    pub fn redo(&mut self) -> Option<(TransactionId, Operation)> {
1143        if let Some(transaction) = self.history.pop_redo().cloned() {
1144            let transaction_id = transaction.id;
1145            let op = self.undo_or_redo(transaction).unwrap();
1146            Some((transaction_id, op))
1147        } else {
1148            None
1149        }
1150    }
1151
1152    pub fn redo_transaction(&mut self, transaction_id: TransactionId) -> Option<Operation> {
1153        if let Some(transaction) = self.history.remove_from_redo(transaction_id).cloned() {
1154            let op = self.undo_or_redo(transaction).unwrap();
1155            Some(op)
1156        } else {
1157            None
1158        }
1159    }
1160
1161    fn undo_or_redo(&mut self, transaction: Transaction) -> Result<Operation> {
1162        let mut counts = HashMap::default();
1163        for edit_id in transaction.edits {
1164            counts.insert(edit_id, self.undo_map.undo_count(edit_id) + 1);
1165        }
1166
1167        let undo = UndoOperation {
1168            id: self.local_clock.tick(),
1169            counts,
1170            ranges: transaction.ranges,
1171            version: transaction.start.clone(),
1172        };
1173        self.apply_undo(&undo)?;
1174        self.snapshot.version.observe(undo.id);
1175
1176        Ok(Operation::Undo {
1177            undo,
1178            lamport_timestamp: self.lamport_clock.tick(),
1179        })
1180    }
1181
1182    pub fn subscribe(&mut self) -> Subscription {
1183        self.subscriptions.subscribe()
1184    }
1185}
1186
1187#[cfg(any(test, feature = "test-support"))]
1188impl Buffer {
1189    fn random_byte_range(&mut self, start_offset: usize, rng: &mut impl rand::Rng) -> Range<usize> {
1190        let end = self.clip_offset(rng.gen_range(start_offset..=self.len()), Bias::Right);
1191        let start = self.clip_offset(rng.gen_range(start_offset..=end), Bias::Right);
1192        start..end
1193    }
1194
1195    pub fn randomly_edit<T>(
1196        &mut self,
1197        rng: &mut T,
1198        old_range_count: usize,
1199    ) -> (Vec<Range<usize>>, String, Operation)
1200    where
1201        T: rand::Rng,
1202    {
1203        let mut old_ranges: Vec<Range<usize>> = Vec::new();
1204        for _ in 0..old_range_count {
1205            let last_end = old_ranges.last().map_or(0, |last_range| last_range.end + 1);
1206            if last_end > self.len() {
1207                break;
1208            }
1209            old_ranges.push(self.random_byte_range(last_end, rng));
1210        }
1211        let new_text_len = rng.gen_range(0..10);
1212        let new_text: String = crate::random_char_iter::RandomCharIter::new(&mut *rng)
1213            .take(new_text_len)
1214            .collect();
1215        log::info!(
1216            "mutating buffer {} at {:?}: {:?}",
1217            self.replica_id,
1218            old_ranges,
1219            new_text
1220        );
1221        let op = self.edit(old_ranges.iter().cloned(), new_text.as_str());
1222        (old_ranges, new_text, Operation::Edit(op))
1223    }
1224
1225    pub fn randomly_undo_redo(&mut self, rng: &mut impl rand::Rng) -> Vec<Operation> {
1226        use rand::prelude::*;
1227
1228        let mut ops = Vec::new();
1229        for _ in 0..rng.gen_range(1..=5) {
1230            if let Some(transaction) = self.history.undo_stack.choose(rng).cloned() {
1231                log::info!(
1232                    "undoing buffer {} transaction {:?}",
1233                    self.replica_id,
1234                    transaction
1235                );
1236                ops.push(self.undo_or_redo(transaction).unwrap());
1237            }
1238        }
1239        ops
1240    }
1241}
1242
1243impl Deref for Buffer {
1244    type Target = BufferSnapshot;
1245
1246    fn deref(&self) -> &Self::Target {
1247        &self.snapshot
1248    }
1249}
1250
1251impl BufferSnapshot {
1252    pub fn as_rope(&self) -> &Rope {
1253        &self.visible_text
1254    }
1255
1256    pub fn replica_id(&self) -> ReplicaId {
1257        self.replica_id
1258    }
1259
1260    pub fn row_count(&self) -> u32 {
1261        self.max_point().row + 1
1262    }
1263
1264    pub fn len(&self) -> usize {
1265        self.visible_text.len()
1266    }
1267
1268    pub fn chars(&self) -> impl Iterator<Item = char> + '_ {
1269        self.chars_at(0)
1270    }
1271
1272    pub fn chars_for_range<T: ToOffset>(&self, range: Range<T>) -> impl Iterator<Item = char> + '_ {
1273        self.text_for_range(range).flat_map(str::chars)
1274    }
1275
1276    pub fn contains_str_at<T>(&self, position: T, needle: &str) -> bool
1277    where
1278        T: ToOffset,
1279    {
1280        let position = position.to_offset(self);
1281        position == self.clip_offset(position, Bias::Left)
1282            && self
1283                .bytes_in_range(position..self.len())
1284                .flatten()
1285                .copied()
1286                .take(needle.len())
1287                .eq(needle.bytes())
1288    }
1289
1290    pub fn text(&self) -> String {
1291        self.text_for_range(0..self.len()).collect()
1292    }
1293
1294    pub fn text_summary(&self) -> TextSummary {
1295        self.visible_text.summary()
1296    }
1297
1298    pub fn max_point(&self) -> Point {
1299        self.visible_text.max_point()
1300    }
1301
1302    pub fn point_to_offset(&self, point: Point) -> usize {
1303        self.visible_text.point_to_offset(point)
1304    }
1305
1306    pub fn point_utf16_to_offset(&self, point: PointUtf16) -> usize {
1307        self.visible_text.point_utf16_to_offset(point)
1308    }
1309
1310    pub fn offset_to_point(&self, offset: usize) -> Point {
1311        self.visible_text.offset_to_point(offset)
1312    }
1313
1314    pub fn offset_to_point_utf16(&self, offset: usize) -> PointUtf16 {
1315        self.visible_text.offset_to_point_utf16(offset)
1316    }
1317
1318    pub fn version(&self) -> &clock::Global {
1319        &self.version
1320    }
1321
1322    pub fn chars_at<'a, T: ToOffset>(&'a self, position: T) -> impl Iterator<Item = char> + 'a {
1323        let offset = position.to_offset(self);
1324        self.visible_text.chars_at(offset)
1325    }
1326
1327    pub fn reversed_chars_at<'a, T: ToOffset>(
1328        &'a self,
1329        position: T,
1330    ) -> impl Iterator<Item = char> + 'a {
1331        let offset = position.to_offset(self);
1332        self.visible_text.reversed_chars_at(offset)
1333    }
1334
1335    pub fn reversed_chunks_in_range<T: ToOffset>(&self, range: Range<T>) -> rope::Chunks {
1336        let range = range.start.to_offset(self)..range.end.to_offset(self);
1337        self.visible_text.reversed_chunks_in_range(range)
1338    }
1339
1340    pub fn bytes_in_range<'a, T: ToOffset>(&'a self, range: Range<T>) -> rope::Bytes<'a> {
1341        let start = range.start.to_offset(self);
1342        let end = range.end.to_offset(self);
1343        self.visible_text.bytes_in_range(start..end)
1344    }
1345
1346    pub fn text_for_range<'a, T: ToOffset>(&'a self, range: Range<T>) -> Chunks<'a> {
1347        let start = range.start.to_offset(self);
1348        let end = range.end.to_offset(self);
1349        self.visible_text.chunks_in_range(start..end)
1350    }
1351
1352    pub fn line_len(&self, row: u32) -> u32 {
1353        let row_start_offset = Point::new(row, 0).to_offset(self);
1354        let row_end_offset = if row >= self.max_point().row {
1355            self.len()
1356        } else {
1357            Point::new(row + 1, 0).to_offset(self) - 1
1358        };
1359        (row_end_offset - row_start_offset) as u32
1360    }
1361
1362    pub fn is_line_blank(&self, row: u32) -> bool {
1363        self.text_for_range(Point::new(row, 0)..Point::new(row, self.line_len(row)))
1364            .all(|chunk| chunk.matches(|c: char| !c.is_whitespace()).next().is_none())
1365    }
1366
1367    pub fn indent_column_for_line(&self, row: u32) -> u32 {
1368        let mut result = 0;
1369        for c in self.chars_at(Point::new(row, 0)) {
1370            if c == ' ' {
1371                result += 1;
1372            } else {
1373                break;
1374            }
1375        }
1376        result
1377    }
1378
1379    pub fn text_summary_for_range<'a, D, O: ToOffset>(&'a self, range: Range<O>) -> D
1380    where
1381        D: TextDimension,
1382    {
1383        self.visible_text
1384            .cursor(range.start.to_offset(self))
1385            .summary(range.end.to_offset(self))
1386    }
1387
1388    pub fn summaries_for_anchors<'a, D, A>(&'a self, anchors: A) -> impl 'a + Iterator<Item = D>
1389    where
1390        D: 'a + TextDimension,
1391        A: 'a + IntoIterator<Item = &'a Anchor>,
1392    {
1393        let anchors = anchors.into_iter();
1394        let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>();
1395        let mut fragment_cursor = self.fragments.cursor::<(Option<&Locator>, usize)>();
1396        let mut text_cursor = self.visible_text.cursor(0);
1397        let mut position = D::default();
1398
1399        anchors.map(move |anchor| {
1400            if *anchor == Anchor::min() {
1401                return D::default();
1402            } else if *anchor == Anchor::max() {
1403                return D::from_text_summary(&self.visible_text.summary());
1404            }
1405
1406            let anchor_key = InsertionFragmentKey {
1407                timestamp: anchor.timestamp,
1408                split_offset: anchor.offset,
1409            };
1410            insertion_cursor.seek(&anchor_key, anchor.bias, &());
1411            if let Some(insertion) = insertion_cursor.item() {
1412                let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
1413                if comparison == Ordering::Greater
1414                    || (anchor.bias == Bias::Left
1415                        && comparison == Ordering::Equal
1416                        && anchor.offset > 0)
1417                {
1418                    insertion_cursor.prev(&());
1419                }
1420            } else {
1421                insertion_cursor.prev(&());
1422            }
1423            let insertion = insertion_cursor.item().expect("invalid insertion");
1424            debug_assert_eq!(insertion.timestamp, anchor.timestamp, "invalid insertion");
1425
1426            fragment_cursor.seek_forward(&Some(&insertion.fragment_id), Bias::Left, &None);
1427            let fragment = fragment_cursor.item().unwrap();
1428            let mut fragment_offset = fragment_cursor.start().1;
1429            if fragment.visible {
1430                fragment_offset += anchor.offset - insertion.split_offset;
1431            }
1432
1433            position.add_assign(&text_cursor.summary(fragment_offset));
1434            position.clone()
1435        })
1436    }
1437
1438    fn summary_for_anchor<'a, D>(&'a self, anchor: &Anchor) -> D
1439    where
1440        D: TextDimension,
1441    {
1442        if *anchor == Anchor::min() {
1443            D::default()
1444        } else if *anchor == Anchor::max() {
1445            D::from_text_summary(&self.visible_text.summary())
1446        } else {
1447            let anchor_key = InsertionFragmentKey {
1448                timestamp: anchor.timestamp,
1449                split_offset: anchor.offset,
1450            };
1451            let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>();
1452            insertion_cursor.seek(&anchor_key, anchor.bias, &());
1453            if let Some(insertion) = insertion_cursor.item() {
1454                let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
1455                if comparison == Ordering::Greater
1456                    || (anchor.bias == Bias::Left
1457                        && comparison == Ordering::Equal
1458                        && anchor.offset > 0)
1459                {
1460                    insertion_cursor.prev(&());
1461                }
1462            } else {
1463                insertion_cursor.prev(&());
1464            }
1465            let insertion = insertion_cursor.item().expect("invalid insertion");
1466            debug_assert_eq!(insertion.timestamp, anchor.timestamp, "invalid insertion");
1467
1468            let mut fragment_cursor = self.fragments.cursor::<(Option<&Locator>, usize)>();
1469            fragment_cursor.seek(&Some(&insertion.fragment_id), Bias::Left, &None);
1470            let fragment = fragment_cursor.item().unwrap();
1471            let mut fragment_offset = fragment_cursor.start().1;
1472            if fragment.visible {
1473                fragment_offset += anchor.offset - insertion.split_offset;
1474            }
1475            self.text_summary_for_range(0..fragment_offset)
1476        }
1477    }
1478
1479    fn fragment_id_for_anchor(&self, anchor: &Anchor) -> &Locator {
1480        if *anchor == Anchor::min() {
1481            &locator::MIN
1482        } else if *anchor == Anchor::max() {
1483            &locator::MAX
1484        } else {
1485            let anchor_key = InsertionFragmentKey {
1486                timestamp: anchor.timestamp,
1487                split_offset: anchor.offset,
1488            };
1489            let mut insertion_cursor = self.insertions.cursor::<InsertionFragmentKey>();
1490            insertion_cursor.seek(&anchor_key, anchor.bias, &());
1491            if let Some(insertion) = insertion_cursor.item() {
1492                let comparison = sum_tree::KeyedItem::key(insertion).cmp(&anchor_key);
1493                if comparison == Ordering::Greater
1494                    || (anchor.bias == Bias::Left
1495                        && comparison == Ordering::Equal
1496                        && anchor.offset > 0)
1497                {
1498                    insertion_cursor.prev(&());
1499                }
1500            } else {
1501                insertion_cursor.prev(&());
1502            }
1503            let insertion = insertion_cursor.item().expect("invalid insertion");
1504            debug_assert_eq!(insertion.timestamp, anchor.timestamp, "invalid insertion");
1505            &insertion.fragment_id
1506        }
1507    }
1508
1509    pub fn anchor_before<T: ToOffset>(&self, position: T) -> Anchor {
1510        self.anchor_at(position, Bias::Left)
1511    }
1512
1513    pub fn anchor_after<T: ToOffset>(&self, position: T) -> Anchor {
1514        self.anchor_at(position, Bias::Right)
1515    }
1516
1517    pub fn anchor_at<T: ToOffset>(&self, position: T, bias: Bias) -> Anchor {
1518        let offset = position.to_offset(self);
1519        if bias == Bias::Left && offset == 0 {
1520            Anchor::min()
1521        } else if bias == Bias::Right && offset == self.len() {
1522            Anchor::max()
1523        } else {
1524            let mut fragment_cursor = self.fragments.cursor::<usize>();
1525            fragment_cursor.seek(&offset, bias, &None);
1526            let fragment = fragment_cursor.item().unwrap();
1527            let overshoot = offset - *fragment_cursor.start();
1528            Anchor {
1529                timestamp: fragment.insertion_timestamp.local(),
1530                offset: fragment.insertion_offset + overshoot,
1531                bias,
1532            }
1533        }
1534    }
1535
1536    pub fn clip_offset(&self, offset: usize, bias: Bias) -> usize {
1537        self.visible_text.clip_offset(offset, bias)
1538    }
1539
1540    pub fn clip_point(&self, point: Point, bias: Bias) -> Point {
1541        self.visible_text.clip_point(point, bias)
1542    }
1543
1544    pub fn clip_point_utf16(&self, point: PointUtf16, bias: Bias) -> PointUtf16 {
1545        self.visible_text.clip_point_utf16(point, bias)
1546    }
1547
1548    // pub fn point_for_offset(&self, offset: usize) -> Result<Point> {
1549    //     if offset <= self.len() {
1550    //         Ok(self.text_summary_for_range(0..offset))
1551    //     } else {
1552    //         Err(anyhow!("offset out of bounds"))
1553    //     }
1554    // }
1555
1556    pub fn edits_since<'a, D>(
1557        &'a self,
1558        since: &'a clock::Global,
1559    ) -> impl 'a + Iterator<Item = Edit<D>>
1560    where
1561        D: TextDimension + Ord,
1562    {
1563        self.edits_since_in_range(since, Anchor::min()..Anchor::max())
1564    }
1565
1566    pub fn edits_since_in_range<'a, D>(
1567        &'a self,
1568        since: &'a clock::Global,
1569        range: Range<Anchor>,
1570    ) -> impl 'a + Iterator<Item = Edit<D>>
1571    where
1572        D: TextDimension + Ord,
1573    {
1574        let fragments_cursor = if *since == self.version {
1575            None
1576        } else {
1577            Some(
1578                self.fragments
1579                    .filter(move |summary| !since.ge(&summary.max_version), &None),
1580            )
1581        };
1582        let mut cursor = self
1583            .fragments
1584            .cursor::<(Option<&Locator>, FragmentTextSummary)>();
1585
1586        let start_fragment_id = self.fragment_id_for_anchor(&range.start);
1587        cursor.seek(&Some(start_fragment_id), Bias::Left, &None);
1588        let mut visible_start = cursor.start().1.visible;
1589        let mut deleted_start = cursor.start().1.deleted;
1590        if let Some(fragment) = cursor.item() {
1591            let overshoot = range.start.offset - fragment.insertion_offset;
1592            if fragment.visible {
1593                visible_start += overshoot;
1594            } else {
1595                deleted_start += overshoot;
1596            }
1597        }
1598        let end_fragment_id = self.fragment_id_for_anchor(&range.end);
1599
1600        Edits {
1601            visible_cursor: self.visible_text.cursor(visible_start),
1602            deleted_cursor: self.deleted_text.cursor(deleted_start),
1603            fragments_cursor,
1604            undos: &self.undo_map,
1605            since,
1606            old_end: Default::default(),
1607            new_end: Default::default(),
1608            range: (start_fragment_id, range.start.offset)..(end_fragment_id, range.end.offset),
1609        }
1610    }
1611}
1612
1613struct RopeBuilder<'a> {
1614    old_visible_cursor: rope::Cursor<'a>,
1615    old_deleted_cursor: rope::Cursor<'a>,
1616    new_visible: Rope,
1617    new_deleted: Rope,
1618}
1619
1620impl<'a> RopeBuilder<'a> {
1621    fn new(old_visible_cursor: rope::Cursor<'a>, old_deleted_cursor: rope::Cursor<'a>) -> Self {
1622        Self {
1623            old_visible_cursor,
1624            old_deleted_cursor,
1625            new_visible: Rope::new(),
1626            new_deleted: Rope::new(),
1627        }
1628    }
1629
1630    fn push_tree(&mut self, len: FragmentTextSummary) {
1631        self.push(len.visible, true, true);
1632        self.push(len.deleted, false, false);
1633    }
1634
1635    fn push_fragment(&mut self, fragment: &Fragment, was_visible: bool) {
1636        debug_assert!(fragment.len > 0);
1637        self.push(fragment.len, was_visible, fragment.visible)
1638    }
1639
1640    fn push(&mut self, len: usize, was_visible: bool, is_visible: bool) {
1641        let text = if was_visible {
1642            self.old_visible_cursor
1643                .slice(self.old_visible_cursor.offset() + len)
1644        } else {
1645            self.old_deleted_cursor
1646                .slice(self.old_deleted_cursor.offset() + len)
1647        };
1648        if is_visible {
1649            self.new_visible.append(text);
1650        } else {
1651            self.new_deleted.append(text);
1652        }
1653    }
1654
1655    fn push_str(&mut self, text: &str) {
1656        self.new_visible.push(text);
1657    }
1658
1659    fn finish(mut self) -> (Rope, Rope) {
1660        self.new_visible.append(self.old_visible_cursor.suffix());
1661        self.new_deleted.append(self.old_deleted_cursor.suffix());
1662        (self.new_visible, self.new_deleted)
1663    }
1664}
1665
1666impl<'a, D: TextDimension + Ord, F: FnMut(&FragmentSummary) -> bool> Iterator for Edits<'a, D, F> {
1667    type Item = Edit<D>;
1668
1669    fn next(&mut self) -> Option<Self::Item> {
1670        let mut pending_edit: Option<Edit<D>> = None;
1671        let cursor = self.fragments_cursor.as_mut()?;
1672
1673        while let Some(fragment) = cursor.item() {
1674            if fragment.id < *self.range.start.0 {
1675                cursor.next(&None);
1676                continue;
1677            } else if fragment.id > *self.range.end.0 {
1678                break;
1679            }
1680
1681            if cursor.start().visible > self.visible_cursor.offset() {
1682                let summary = self.visible_cursor.summary(cursor.start().visible);
1683                self.old_end.add_assign(&summary);
1684                self.new_end.add_assign(&summary);
1685            }
1686
1687            if pending_edit
1688                .as_ref()
1689                .map_or(false, |change| change.new.end < self.new_end)
1690            {
1691                break;
1692            }
1693
1694            if !fragment.was_visible(&self.since, &self.undos) && fragment.visible {
1695                let mut visible_end = cursor.end(&None).visible;
1696                if fragment.id == *self.range.end.0 {
1697                    visible_end = cmp::min(
1698                        visible_end,
1699                        cursor.start().visible + (self.range.end.1 - fragment.insertion_offset),
1700                    );
1701                }
1702
1703                let fragment_summary = self.visible_cursor.summary(visible_end);
1704                let mut new_end = self.new_end.clone();
1705                new_end.add_assign(&fragment_summary);
1706                if let Some(pending_edit) = pending_edit.as_mut() {
1707                    pending_edit.new.end = new_end.clone();
1708                } else {
1709                    pending_edit = Some(Edit {
1710                        old: self.old_end.clone()..self.old_end.clone(),
1711                        new: self.new_end.clone()..new_end.clone(),
1712                    });
1713                }
1714
1715                self.new_end = new_end;
1716            } else if fragment.was_visible(&self.since, &self.undos) && !fragment.visible {
1717                let mut deleted_end = cursor.end(&None).deleted;
1718                if fragment.id == *self.range.end.0 {
1719                    deleted_end = cmp::min(
1720                        deleted_end,
1721                        cursor.start().deleted + (self.range.end.1 - fragment.insertion_offset),
1722                    );
1723                }
1724
1725                if cursor.start().deleted > self.deleted_cursor.offset() {
1726                    self.deleted_cursor.seek_forward(cursor.start().deleted);
1727                }
1728                let fragment_summary = self.deleted_cursor.summary(deleted_end);
1729                let mut old_end = self.old_end.clone();
1730                old_end.add_assign(&fragment_summary);
1731                if let Some(pending_edit) = pending_edit.as_mut() {
1732                    pending_edit.old.end = old_end.clone();
1733                } else {
1734                    pending_edit = Some(Edit {
1735                        old: self.old_end.clone()..old_end.clone(),
1736                        new: self.new_end.clone()..self.new_end.clone(),
1737                    });
1738                }
1739
1740                self.old_end = old_end;
1741            }
1742
1743            cursor.next(&None);
1744        }
1745
1746        pending_edit
1747    }
1748}
1749
1750impl Fragment {
1751    fn is_visible(&self, undos: &UndoMap) -> bool {
1752        !undos.is_undone(self.insertion_timestamp.local())
1753            && self.deletions.iter().all(|d| undos.is_undone(*d))
1754    }
1755
1756    fn was_visible(&self, version: &clock::Global, undos: &UndoMap) -> bool {
1757        (version.observed(self.insertion_timestamp.local())
1758            && !undos.was_undone(self.insertion_timestamp.local(), version))
1759            && self
1760                .deletions
1761                .iter()
1762                .all(|d| !version.observed(*d) || undos.was_undone(*d, version))
1763    }
1764}
1765
1766impl sum_tree::Item for Fragment {
1767    type Summary = FragmentSummary;
1768
1769    fn summary(&self) -> Self::Summary {
1770        let mut max_version = clock::Global::new();
1771        max_version.observe(self.insertion_timestamp.local());
1772        for deletion in &self.deletions {
1773            max_version.observe(*deletion);
1774        }
1775        max_version.join(&self.max_undos);
1776
1777        let mut min_insertion_version = clock::Global::new();
1778        min_insertion_version.observe(self.insertion_timestamp.local());
1779        let max_insertion_version = min_insertion_version.clone();
1780        if self.visible {
1781            FragmentSummary {
1782                max_id: self.id.clone(),
1783                text: FragmentTextSummary {
1784                    visible: self.len,
1785                    deleted: 0,
1786                },
1787                max_version,
1788                min_insertion_version,
1789                max_insertion_version,
1790            }
1791        } else {
1792            FragmentSummary {
1793                max_id: self.id.clone(),
1794                text: FragmentTextSummary {
1795                    visible: 0,
1796                    deleted: self.len,
1797                },
1798                max_version,
1799                min_insertion_version,
1800                max_insertion_version,
1801            }
1802        }
1803    }
1804}
1805
1806impl sum_tree::Summary for FragmentSummary {
1807    type Context = Option<clock::Global>;
1808
1809    fn add_summary(&mut self, other: &Self, _: &Self::Context) {
1810        self.max_id.assign(&other.max_id);
1811        self.text.visible += &other.text.visible;
1812        self.text.deleted += &other.text.deleted;
1813        self.max_version.join(&other.max_version);
1814        self.min_insertion_version
1815            .meet(&other.min_insertion_version);
1816        self.max_insertion_version
1817            .join(&other.max_insertion_version);
1818    }
1819}
1820
1821impl Default for FragmentSummary {
1822    fn default() -> Self {
1823        FragmentSummary {
1824            max_id: Locator::min(),
1825            text: FragmentTextSummary::default(),
1826            max_version: clock::Global::new(),
1827            min_insertion_version: clock::Global::new(),
1828            max_insertion_version: clock::Global::new(),
1829        }
1830    }
1831}
1832
1833impl sum_tree::Item for InsertionFragment {
1834    type Summary = InsertionFragmentKey;
1835
1836    fn summary(&self) -> Self::Summary {
1837        InsertionFragmentKey {
1838            timestamp: self.timestamp,
1839            split_offset: self.split_offset,
1840        }
1841    }
1842}
1843
1844impl sum_tree::KeyedItem for InsertionFragment {
1845    type Key = InsertionFragmentKey;
1846
1847    fn key(&self) -> Self::Key {
1848        sum_tree::Item::summary(self)
1849    }
1850}
1851
1852impl InsertionFragment {
1853    fn new(fragment: &Fragment) -> Self {
1854        Self {
1855            timestamp: fragment.insertion_timestamp.local(),
1856            split_offset: fragment.insertion_offset,
1857            fragment_id: fragment.id.clone(),
1858        }
1859    }
1860
1861    fn insert_new(fragment: &Fragment) -> sum_tree::Edit<Self> {
1862        sum_tree::Edit::Insert(Self::new(fragment))
1863    }
1864}
1865
1866impl sum_tree::Summary for InsertionFragmentKey {
1867    type Context = ();
1868
1869    fn add_summary(&mut self, summary: &Self, _: &()) {
1870        *self = *summary;
1871    }
1872}
1873
1874#[derive(Copy, Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
1875pub struct FullOffset(pub usize);
1876
1877impl ops::AddAssign<usize> for FullOffset {
1878    fn add_assign(&mut self, rhs: usize) {
1879        self.0 += rhs;
1880    }
1881}
1882
1883impl ops::Add<usize> for FullOffset {
1884    type Output = Self;
1885
1886    fn add(mut self, rhs: usize) -> Self::Output {
1887        self += rhs;
1888        self
1889    }
1890}
1891
1892impl ops::Sub for FullOffset {
1893    type Output = usize;
1894
1895    fn sub(self, rhs: Self) -> Self::Output {
1896        self.0 - rhs.0
1897    }
1898}
1899
1900impl<'a> sum_tree::Dimension<'a, FragmentSummary> for usize {
1901    fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
1902        *self += summary.text.visible;
1903    }
1904}
1905
1906impl<'a> sum_tree::Dimension<'a, FragmentSummary> for FullOffset {
1907    fn add_summary(&mut self, summary: &FragmentSummary, _: &Option<clock::Global>) {
1908        self.0 += summary.text.visible + summary.text.deleted;
1909    }
1910}
1911
1912impl<'a> sum_tree::Dimension<'a, FragmentSummary> for Option<&'a Locator> {
1913    fn add_summary(&mut self, summary: &'a FragmentSummary, _: &Option<clock::Global>) {
1914        *self = Some(&summary.max_id);
1915    }
1916}
1917
1918impl<'a> sum_tree::SeekTarget<'a, FragmentSummary, FragmentTextSummary> for usize {
1919    fn cmp(
1920        &self,
1921        cursor_location: &FragmentTextSummary,
1922        _: &Option<clock::Global>,
1923    ) -> cmp::Ordering {
1924        Ord::cmp(self, &cursor_location.visible)
1925    }
1926}
1927
1928#[derive(Copy, Clone, Debug, Eq, PartialEq)]
1929enum VersionedFullOffset {
1930    Offset(FullOffset),
1931    Invalid,
1932}
1933
1934impl VersionedFullOffset {
1935    fn full_offset(&self) -> FullOffset {
1936        if let Self::Offset(position) = self {
1937            *position
1938        } else {
1939            panic!("invalid version")
1940        }
1941    }
1942}
1943
1944impl Default for VersionedFullOffset {
1945    fn default() -> Self {
1946        Self::Offset(Default::default())
1947    }
1948}
1949
1950impl<'a> sum_tree::Dimension<'a, FragmentSummary> for VersionedFullOffset {
1951    fn add_summary(&mut self, summary: &'a FragmentSummary, cx: &Option<clock::Global>) {
1952        if let Self::Offset(offset) = self {
1953            let version = cx.as_ref().unwrap();
1954            if version.ge(&summary.max_insertion_version) {
1955                *offset += summary.text.visible + summary.text.deleted;
1956            } else if version.observed_any(&summary.min_insertion_version) {
1957                *self = Self::Invalid;
1958            }
1959        }
1960    }
1961}
1962
1963impl<'a> sum_tree::SeekTarget<'a, FragmentSummary, Self> for VersionedFullOffset {
1964    fn cmp(&self, cursor_position: &Self, _: &Option<clock::Global>) -> cmp::Ordering {
1965        match (self, cursor_position) {
1966            (Self::Offset(a), Self::Offset(b)) => Ord::cmp(a, b),
1967            (Self::Offset(_), Self::Invalid) => cmp::Ordering::Less,
1968            (Self::Invalid, _) => unreachable!(),
1969        }
1970    }
1971}
1972
1973impl Operation {
1974    fn replica_id(&self) -> ReplicaId {
1975        operation_queue::Operation::lamport_timestamp(self).replica_id
1976    }
1977
1978    pub fn is_edit(&self) -> bool {
1979        match self {
1980            Operation::Edit { .. } => true,
1981            _ => false,
1982        }
1983    }
1984}
1985
1986impl operation_queue::Operation for Operation {
1987    fn lamport_timestamp(&self) -> clock::Lamport {
1988        match self {
1989            Operation::Edit(edit) => edit.timestamp.lamport(),
1990            Operation::Undo {
1991                lamport_timestamp, ..
1992            } => *lamport_timestamp,
1993        }
1994    }
1995}
1996
1997pub trait ToOffset {
1998    fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize;
1999}
2000
2001impl ToOffset for Point {
2002    fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2003        snapshot.point_to_offset(*self)
2004    }
2005}
2006
2007impl ToOffset for PointUtf16 {
2008    fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2009        snapshot.point_utf16_to_offset(*self)
2010    }
2011}
2012
2013impl ToOffset for usize {
2014    fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2015        assert!(*self <= snapshot.len(), "offset is out of range");
2016        *self
2017    }
2018}
2019
2020impl ToOffset for Anchor {
2021    fn to_offset<'a>(&self, snapshot: &BufferSnapshot) -> usize {
2022        snapshot.summary_for_anchor(self)
2023    }
2024}
2025
2026impl<'a, T: ToOffset> ToOffset for &'a T {
2027    fn to_offset(&self, content: &BufferSnapshot) -> usize {
2028        (*self).to_offset(content)
2029    }
2030}
2031
2032pub trait ToPoint {
2033    fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point;
2034}
2035
2036impl ToPoint for Anchor {
2037    fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point {
2038        snapshot.summary_for_anchor(self)
2039    }
2040}
2041
2042impl ToPoint for usize {
2043    fn to_point<'a>(&self, snapshot: &BufferSnapshot) -> Point {
2044        snapshot.offset_to_point(*self)
2045    }
2046}
2047
2048impl ToPoint for Point {
2049    fn to_point<'a>(&self, _: &BufferSnapshot) -> Point {
2050        *self
2051    }
2052}
2053
2054pub trait FromAnchor {
2055    fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self;
2056}
2057
2058impl FromAnchor for Point {
2059    fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
2060        anchor.to_point(snapshot)
2061    }
2062}
2063
2064impl FromAnchor for usize {
2065    fn from_anchor(anchor: &Anchor, snapshot: &BufferSnapshot) -> Self {
2066        anchor.to_offset(snapshot)
2067    }
2068}