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}