Skip to main content

common/database/
block_offset_index.rs

1//! Sorted index of marker (block or table-anchor) → rope byte range.
2//!
3//! Tracks the byte offset at which each marker starts in the global
4//! rope, plus the rope's total byte length. A marker is either a
5//! real `Block` or a `TableAnchor` — the U+FFFC sentinel that
6//! occupies a line on its own in a parent frame's range to represent
7//! an embedded table (plan §1.6). Each marker extends from its
8//! `byte_start` to the next marker's `byte_start` (or to
9//! `total_bytes` for the last entry).
10//!
11//! Invariants:
12//! - `entries` is sorted by `byte_start` ascending.
13//! - No two entries share the same `byte_start`.
14//! - The last entry's `byte_start ≤ total_bytes`.
15//! - Empty `entries` ⟺ no markers in the document.
16
17use crate::types::EntityId;
18use im::HashMap as ImHashMap;
19use std::sync::Arc;
20
21/// Discriminates real blocks from table-anchor sentinels in the
22/// offset index. The wrapped `EntityId` is the corresponding entity's
23/// id (a Block id or a Table id).
24#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
25pub enum OffsetMarker {
26    Block(EntityId),
27    TableAnchor(EntityId),
28}
29
30impl OffsetMarker {
31    pub fn as_block(self) -> Option<EntityId> {
32        match self {
33            OffsetMarker::Block(id) => Some(id),
34            _ => None,
35        }
36    }
37
38    pub fn as_table_anchor(self) -> Option<EntityId> {
39        match self {
40            OffsetMarker::TableAnchor(id) => Some(id),
41            _ => None,
42        }
43    }
44
45    pub fn is_block(self) -> bool {
46        matches!(self, OffsetMarker::Block(_))
47    }
48}
49
50#[derive(Debug, Clone, Default, PartialEq, Eq)]
51pub struct BlockOffsetIndex {
52    /// `(marker, byte_start)` pairs sorted by `byte_start` ascending.
53    ///
54    /// Wrapped in `Arc` so the per-edit snapshot path (which clones
55    /// `BlockOffsetIndex` as part of `Store::snapshot`) does an O(1)
56    /// pointer bump instead of an O(N) memcpy of the underlying Vec.
57    /// Mutators in this `impl` block go through `Arc::make_mut`, which
58    /// deep-clones the Vec only on the first write after the Arc has
59    /// been shared (i.e., after a snapshot was taken). External
60    /// callers see `Arc<Vec<...>>` which derefs transparently to
61    /// `&[...]` for reads.
62    pub entries: Arc<Vec<(OffsetMarker, u32)>>,
63
64    /// Total byte length of the rope this index describes. The last
65    /// entry extends from its `byte_start` to this value.
66    pub total_bytes: u32,
67
68    /// O(1)-average lookup from marker to its position in `entries`.
69    /// Maintained eagerly by the `push` / `push_block` / `insert_at` /
70    /// `remove_at` / `clear` methods on this type — direct mutation of
71    /// `entries` from outside leaves this cache stale, so callers must
72    /// go through those methods (or call `rebuild_marker_index` after
73    /// mutating in bulk).
74    ///
75    /// Stored as `im::HashMap` so the snapshot-clone path stays O(1).
76    /// `shift_after` does not move positions, only byte_starts — so
77    /// this map is unaffected by shifts.
78    marker_index: ImHashMap<OffsetMarker, usize>,
79
80    /// Cached count of `OffsetMarker::TableAnchor` entries. Maintained
81    /// by the same mutator methods that maintain `marker_index`. Used
82    /// by `rope_helpers::rope_positions_match_flow` to gate the
83    /// per-edit position-refresh loop in O(1) instead of an O(N) walk
84    /// over `entries`.
85    table_anchor_count: usize,
86}
87
88impl BlockOffsetIndex {
89    pub fn new() -> Self {
90        Self::default()
91    }
92
93    pub fn len(&self) -> usize {
94        self.entries.len()
95    }
96
97    pub fn is_empty(&self) -> bool {
98        self.entries.is_empty()
99    }
100
101    pub fn total_bytes(&self) -> u32 {
102        self.total_bytes
103    }
104
105    pub fn set_total_bytes(&mut self, total: u32) {
106        self.total_bytes = total;
107    }
108
109    /// Number of `OffsetMarker::TableAnchor` entries currently indexed.
110    /// O(1) via a maintained counter. `rope_positions_match_flow` subtracts
111    /// it from `len()` to count the blocks the rope mirrors without walking
112    /// the entries.
113    pub fn table_anchor_count(&self) -> usize {
114        self.table_anchor_count
115    }
116
117    /// Insert a marker at a given byte position. The caller is
118    /// responsible for keeping the `byte_start` ordered relative to
119    /// neighbours — this method does NOT re-sort.
120    pub fn insert_at(&mut self, position: usize, marker: OffsetMarker, byte_start: u32) {
121        Arc::make_mut(&mut self.entries).insert(position, (marker, byte_start));
122        // All markers at positions ≥ `position` shifted up by 1.
123        for (m, p) in self.marker_index.iter_mut() {
124            if *p >= position && *m != marker {
125                *p += 1;
126            }
127        }
128        self.marker_index.insert(marker, position);
129        if matches!(marker, OffsetMarker::TableAnchor(_)) {
130            self.table_anchor_count += 1;
131        }
132    }
133
134    /// Insert consecutive markers starting at `position`, in order. The
135    /// result is exactly what calling [`insert_at`](Self::insert_at) once
136    /// per marker at `position`, `position + 1`, … would leave, but the
137    /// marker index is walked once for the whole run instead of once per
138    /// marker: inserting a run of N markers one at a time costs N walks of
139    /// every marker in the document. The caller keeps the `byte_start`s
140    /// ordered, as for `insert_at`.
141    pub fn insert_run_at(&mut self, position: usize, run: &[(OffsetMarker, u32)]) {
142        if run.is_empty() {
143            return;
144        }
145        Arc::make_mut(&mut self.entries).splice(position..position, run.iter().copied());
146        // Every marker already at or past `position` moves up by the run's length.
147        for (_, p) in self.marker_index.iter_mut() {
148            if *p >= position {
149                *p += run.len();
150            }
151        }
152        for (offset, (marker, _)) in run.iter().enumerate() {
153            self.marker_index.insert(*marker, position + offset);
154            if matches!(marker, OffsetMarker::TableAnchor(_)) {
155                self.table_anchor_count += 1;
156            }
157        }
158    }
159
160    /// Replace the entries from `position` on with `run`, one for one: the markers the run
161    /// holds are the markers those entries held, in another order and at other byte starts.
162    /// The caller keeps the `byte_start`s ordered, as for [`insert_at`](Self::insert_at).
163    /// Nothing outside the run moves, so only the run's own markers are re-indexed.
164    pub fn reorder_run(&mut self, position: usize, run: &[(OffsetMarker, u32)]) {
165        let entries = Arc::make_mut(&mut self.entries);
166        let Some(slots) = entries.get_mut(position..position + run.len()) else {
167            return;
168        };
169        slots.copy_from_slice(run);
170        for (offset, (marker, _)) in run.iter().enumerate() {
171            self.marker_index.insert(*marker, position + offset);
172        }
173    }
174
175    /// Take bytes out after several entries at once: for each
176    /// `(position, bytes)`, every entry past `position` moves back by
177    /// `bytes`, and so does `total_bytes`. The result is exactly what calling
178    /// [`shift_after`](Self::shift_after)`(entries[position].1 + 1, -bytes)`
179    /// once per pair leaves, provided each entry at `position` starts before
180    /// the entry after it, as an entry with content or a boundary after it
181    /// does. The entries are walked once for the whole list instead of once
182    /// per pair. `cuts` is in increasing `position` order.
183    pub fn remove_bytes_after(&mut self, cuts: &[(usize, u32)]) {
184        if cuts.is_empty() {
185            return;
186        }
187        entries_rewritten(self.entries.len());
188        let mut removed: u32 = 0;
189        let mut pending = cuts.iter().peekable();
190        for (position, (_, byte_start)) in Arc::make_mut(&mut self.entries).iter_mut().enumerate() {
191            debug_assert!(*byte_start >= removed, "a cut past an entry's start");
192            *byte_start = byte_start.saturating_sub(removed);
193            while let Some(&&(cut_position, bytes)) = pending.peek() {
194                if cut_position != position {
195                    break;
196                }
197                removed = removed.saturating_add(bytes);
198                pending.next();
199            }
200        }
201        self.total_bytes = self.total_bytes.saturating_sub(removed);
202    }
203
204    /// Shift the entries past several thresholds at once: for each
205    /// `(threshold, delta)`, every entry starting at or past `threshold` moves
206    /// by `delta`, and so does `total_bytes`. The result is exactly what calling
207    /// [`shift_after`](Self::shift_after) once per pair leaves, every threshold
208    /// read in the offsets as they stand before any of them moves, as the edits
209    /// of one text applied from its end back do. The entries are walked once
210    /// for the whole list instead of once per pair. `shifts` is in increasing
211    /// `threshold` order.
212    pub fn shift_after_each(&mut self, shifts: &[(u32, i32)]) {
213        if shifts.is_empty() {
214            return;
215        }
216        let first = self.entries.partition_point(|(_, bs)| *bs < shifts[0].0);
217        entries_rewritten(self.entries.len() - first);
218        let mut delta: i32 = 0;
219        let mut pending = shifts.iter().peekable();
220        for (_, byte_start) in Arc::make_mut(&mut self.entries)[first..].iter_mut() {
221            while let Some(&&(threshold, shift)) = pending.peek() {
222                if threshold > *byte_start {
223                    break;
224                }
225                delta += shift;
226                pending.next();
227            }
228            *byte_start = apply_delta(*byte_start, delta);
229        }
230        let total: i32 = shifts.iter().map(|(_, shift)| shift).sum();
231        self.total_bytes = apply_delta(self.total_bytes, total);
232    }
233
234    /// Drop the entries `dropped` flags (one flag per entry, by position) and
235    /// take the byte ranges `cuts` out of the text they index: every kept
236    /// entry moves back by the bytes cut in front of it, and `total_bytes`
237    /// by all of them. `cuts` is disjoint and in increasing order, and no cut
238    /// straddles a kept entry's first byte: each ends at or before it, or
239    /// starts at or after it. A cut starting exactly there is cut after the
240    /// entry, which keeps its offset: that is how the trailing entries of the
241    /// rope go when the entry before them is empty. One walk of the entries,
242    /// however many are dropped: removing them one at a time walked the index
243    /// once each.
244    pub fn remove_entries(&mut self, dropped: &[bool], cuts: &[(u32, u32)]) {
245        debug_assert_eq!(dropped.len(), self.entries.len());
246        entries_rewritten(self.entries.len());
247        let mut kept: Vec<(OffsetMarker, u32)> = Vec::with_capacity(self.entries.len());
248        let mut pending = cuts.iter().peekable();
249        let mut removed: u32 = 0;
250        for (position, &(marker, byte_start)) in self.entries.iter().enumerate() {
251            while let Some(&&(cut_start, cut_end)) = pending.peek() {
252                if cut_end > byte_start {
253                    break;
254                }
255                debug_assert!(cut_start <= cut_end, "a cut ends before it starts");
256                removed += cut_end - cut_start;
257                pending.next();
258            }
259            if !dropped.get(position).copied().unwrap_or(false) {
260                kept.push((marker, byte_start - removed));
261            }
262        }
263        let cut_total: u32 = cuts.iter().map(|(start, end)| end - start).sum();
264        self.entries = Arc::new(kept);
265        self.total_bytes = self.total_bytes.saturating_sub(cut_total);
266        self.rebuild_marker_index();
267    }
268
269    /// Append a marker at the end (its `byte_start` must be ≥ the last
270    /// entry's `byte_start`).
271    pub fn push(&mut self, marker: OffsetMarker, byte_start: u32) {
272        debug_assert!(
273            self.entries
274                .last()
275                .map(|(_, bs)| byte_start >= *bs)
276                .unwrap_or(true),
277            "push must preserve ordering"
278        );
279        let position = self.entries.len();
280        Arc::make_mut(&mut self.entries).push((marker, byte_start));
281        self.marker_index.insert(marker, position);
282        if matches!(marker, OffsetMarker::TableAnchor(_)) {
283            self.table_anchor_count += 1;
284        }
285    }
286
287    /// Convenience: register a block by id. Equivalent to
288    /// `push(OffsetMarker::Block(id), byte_start)`.
289    pub fn push_block(&mut self, block_id: EntityId, byte_start: u32) {
290        self.push(OffsetMarker::Block(block_id), byte_start);
291    }
292
293    /// Remove the entry at the given position. Panics if out of bounds.
294    pub fn remove_at(&mut self, position: usize) -> (OffsetMarker, u32) {
295        let removed = Arc::make_mut(&mut self.entries).remove(position);
296        self.marker_index.remove(&removed.0);
297        // All markers at positions > `position` shifted down by 1.
298        for (_, p) in self.marker_index.iter_mut() {
299            if *p > position {
300                *p -= 1;
301            }
302        }
303        if matches!(removed.0, OffsetMarker::TableAnchor(_)) {
304            self.table_anchor_count = self.table_anchor_count.saturating_sub(1);
305        }
306        removed
307    }
308
309    /// Remove a contiguous range of entries, equivalent to
310    /// `entries.drain(start..=end_inclusive)` plus the matching
311    /// marker_index maintenance. Returns the removed entries.
312    pub fn drain_inclusive(
313        &mut self,
314        start: usize,
315        end_inclusive: usize,
316    ) -> Vec<(OffsetMarker, u32)> {
317        let removed: Vec<_> = Arc::make_mut(&mut self.entries)
318            .drain(start..=end_inclusive)
319            .collect();
320        let removed_anchors = removed
321            .iter()
322            .filter(|(m, _)| matches!(m, OffsetMarker::TableAnchor(_)))
323            .count();
324        self.table_anchor_count = self.table_anchor_count.saturating_sub(removed_anchors);
325        for (m, _) in &removed {
326            self.marker_index.remove(m);
327        }
328        let shift = removed.len();
329        // All markers at positions > end_inclusive shift down by `shift`.
330        for (_, p) in self.marker_index.iter_mut() {
331            if *p > end_inclusive {
332                *p -= shift;
333            }
334        }
335        removed
336    }
337
338    /// Drop every entry and reset `total_bytes` to zero. Equivalent to
339    /// `*self = Self::default()` but expressed as a method so callers
340    /// don't need to depend on `Default`.
341    pub fn clear(&mut self) {
342        Arc::make_mut(&mut self.entries).clear();
343        self.marker_index = ImHashMap::new();
344        self.total_bytes = 0;
345        self.table_anchor_count = 0;
346    }
347
348    /// Rebuild `marker_index` and `table_anchor_count` from `entries`.
349    /// Use after bulk mutations that bypassed the maintenance methods
350    /// (e.g. raw `entries.push` in test setup).
351    pub fn rebuild_marker_index(&mut self) {
352        let mut idx = ImHashMap::new();
353        let mut anchors = 0usize;
354        for (i, (m, _)) in self.entries.iter().enumerate() {
355            idx.insert(*m, i);
356            if matches!(m, OffsetMarker::TableAnchor(_)) {
357                anchors += 1;
358            }
359        }
360        self.marker_index = idx;
361        self.table_anchor_count = anchors;
362    }
363
364    /// Byte range `(start, end)` of a marker. `end` is the next
365    /// marker's `byte_start` (or `total_bytes` for the last entry).
366    /// Returns `None` if the marker is not indexed.
367    ///
368    /// O(1) average via the `marker_index` map.
369    pub fn range_of(&self, marker: OffsetMarker) -> Option<(u32, u32)> {
370        let idx = *self.marker_index.get(&marker)?;
371        let start = self.entries[idx].1;
372        let end = self
373            .entries
374            .get(idx + 1)
375            .map(|(_, bs)| *bs)
376            .unwrap_or(self.total_bytes);
377        Some((start, end))
378    }
379
380    /// Byte range for a block-id specifically. Convenience for the
381    /// common case.
382    pub fn range_of_block(&self, block_id: EntityId) -> Option<(u32, u32)> {
383        self.range_of(OffsetMarker::Block(block_id))
384    }
385
386    /// Like `range_of`, but also reports whether the marker has a
387    /// successor entry. Callers that need to strip the trailing
388    /// inter-block `\n` boundary (e.g. `block_content_via_store`,
389    /// `block_char_length`) use this to distinguish "end == next
390    /// marker's byte_start, with a real `\n` between us" from "end
391    /// == total_bytes, no separator after".
392    ///
393    /// O(1) average via `marker_index`.
394    pub fn range_with_successor(&self, marker: OffsetMarker) -> Option<(u32, u32, bool)> {
395        let idx = *self.marker_index.get(&marker)?;
396        let start = self.entries[idx].1;
397        let has_successor = idx + 1 < self.entries.len();
398        let end = if has_successor {
399            self.entries[idx + 1].1
400        } else {
401            self.total_bytes
402        };
403        Some((start, end, has_successor))
404    }
405
406    /// Position of `marker` in `entries`. O(1) average via the
407    /// `marker_index` cache. Returns `None` if the marker is not
408    /// indexed.
409    pub fn position_of(&self, marker: OffsetMarker) -> Option<usize> {
410        self.marker_index.get(&marker).copied()
411    }
412
413    /// Marker whose byte range covers `byte`. Returns `None` if the
414    /// index is empty or `byte` falls past `total_bytes`.
415    ///
416    /// `byte == total_bytes` is treated as belonging to the last entry
417    /// (this is the cursor-at-end-of-document case).
418    pub fn marker_at_byte(&self, byte: u32) -> Option<OffsetMarker> {
419        if self.entries.is_empty() {
420            return None;
421        }
422        if byte > self.total_bytes {
423            return None;
424        }
425        let idx = match self.entries.binary_search_by_key(&byte, |(_, bs)| *bs) {
426            Ok(i) => i,
427            Err(0) => return None,
428            Err(i) => i - 1,
429        };
430        Some(self.entries[idx].0)
431    }
432
433    /// Block id whose byte range covers `byte`, ignoring table-anchor
434    /// markers. Returns `None` if no block covers the byte.
435    pub fn block_at_byte(&self, byte: u32) -> Option<EntityId> {
436        self.marker_at_byte(byte).and_then(|m| m.as_block())
437    }
438
439    /// Convert an absolute rope byte offset into
440    /// `(marker, byte_in_marker)`. Returns `None` for offsets past the
441    /// end or for an empty index.
442    pub fn byte_to_marker_byte(&self, byte: u32) -> Option<(OffsetMarker, u32)> {
443        let marker = self.marker_at_byte(byte)?;
444        let (start, _) = self.range_of(marker)?;
445        Some((marker, byte - start))
446    }
447
448    /// Block-only variant of `byte_to_marker_byte`.
449    pub fn byte_to_block_byte(&self, byte: u32) -> Option<(EntityId, u32)> {
450        let block_id = self.block_at_byte(byte)?;
451        let (start, _) = self.range_of_block(block_id)?;
452        Some((block_id, byte - start))
453    }
454
455    /// Shift every entry whose `byte_start ≥ threshold` by `delta`
456    /// bytes, and adjust `total_bytes` by `delta`. Used after a rope
457    /// insert (positive delta) or delete (negative delta) to keep the
458    /// index in sync without a full rebuild.
459    ///
460    /// `entries` is sorted by `byte_start`, so the affected suffix is
461    /// located via `partition_point` (O(log n)) and only that suffix
462    /// is walked.
463    pub fn shift_after(&mut self, threshold: u32, delta: i32) {
464        let start = self.entries.partition_point(|(_, bs)| *bs < threshold);
465        if start < self.entries.len() {
466            entries_rewritten(self.entries.len() - start);
467            for (_, bs) in Arc::make_mut(&mut self.entries)[start..].iter_mut() {
468                *bs = apply_delta(*bs, delta);
469            }
470        }
471        self.total_bytes = apply_delta(self.total_bytes, delta);
472    }
473}
474
475/// Record `count` entries an offset shift rewrote. Unit tests count them, which is
476/// how `rope_helpers`' `tests::clearing_blocks_together_walks_the_index_once`
477/// guards `rope_clear_blocks`' cost in the debug builds CI tests with, where
478/// timing it cannot.
479fn entries_rewritten(count: usize) {
480    #[cfg(test)]
481    tests::ENTRIES_REWRITTEN.with(|rewritten| rewritten.set(rewritten.get() + count));
482    #[cfg(not(test))]
483    let _ = count;
484}
485
486fn apply_delta(value: u32, delta: i32) -> u32 {
487    if delta >= 0 {
488        value
489            .checked_add(delta as u32)
490            .expect("byte offset overflow")
491    } else {
492        let abs = (-delta) as u32;
493        value
494            .checked_sub(abs)
495            .expect("byte offset would go negative")
496    }
497}
498
499#[cfg(test)]
500pub(crate) mod tests {
501    use std::cell::Cell;
502
503    thread_local! {
504        /// Entries the offset shifts rewrote on this thread (see [`super::entries_rewritten`]).
505        pub(crate) static ENTRIES_REWRITTEN: Cell<usize> = const { Cell::new(0) };
506    }
507}