Skip to main content

common/database/
rope_helpers.rs

1//! Helpers for writing the global character rope from use cases.
2//!
3//! Each helper mutates `store.rope` and `store.block_offsets`
4//! together so callers can stay oblivious to the underlying layout.
5//! Read helpers (`block_content_via_store`) source content from the
6//! rope and return empty when a block is not yet registered in the
7//! offset index.
8
9use crate::database::Store;
10use crate::database::block_offset_index::OffsetMarker;
11use crate::entities::Block;
12use crate::format_runs::{
13    FootnoteRefAnchor, FormatRun, FormatRunError, ImageAnchor, ReplaceFormatPolicy,
14    check_well_formed, logical_offset_to_byte, shift_footnote_refs_for_delete,
15    shift_footnote_refs_for_insert, shift_images_for_delete, shift_images_for_insert,
16    shift_runs_for_replace,
17};
18use crate::types::EntityId;
19use std::collections::HashMap;
20
21/// Read a block's content from the global rope via `block_offsets`,
22/// stripping the trailing `\n` boundary that `range_of` includes for
23/// non-last entries. Returns an empty string if the block isn't
24/// registered in the offset index (e.g. a freshly-created block that
25/// hasn't been spliced into the rope yet — `setup_with_text` test
26/// docs use this path).
27pub fn block_content_via_store(block: &Block, store: &Store) -> String {
28    let offsets = store.block_offsets.read();
29    let marker = OffsetMarker::Block(block.id);
30    let Some((bs, be, has_successor)) = offsets.range_with_successor(marker) else {
31        return String::new();
32    };
33    // Drop the trailing inter-block boundary `\n` ONLY when this block
34    // has a successor entry — that one byte is the boundary `\n` between
35    // this block and the next. The last entry has no trailing boundary;
36    // any final `\n` is real content.
37    let content_end = if has_successor && be > bs { be - 1 } else { be };
38    drop(offsets);
39    let rope = store.rope.read();
40    rope.byte_slice(bs as usize..content_end as usize)
41        .to_string()
42}
43
44/// Logical character count of a block — what the old
45/// `Block.text_length` field used to cache. Image anchors are stored as
46/// `\u{FFFC}` (one char, three bytes) inside the rope content, so the
47/// char count already covers them. Returns 0 for blocks not registered
48/// in the offset index.
49///
50/// O(log n) via `ropey::Rope::byte_to_char` — does NOT materialize the
51/// block's text into a String. Replaces the prior O(L) implementation
52/// that counted chars by walking UTF-8 over a cloned slice.
53pub fn block_char_length(block: &Block, store: &Store) -> i64 {
54    let offsets = store.block_offsets.read();
55    let marker = OffsetMarker::Block(block.id);
56    let Some((bs, be, has_successor)) = offsets.range_with_successor(marker) else {
57        return 0;
58    };
59    let content_end_bytes = if has_successor && be > bs { be - 1 } else { be };
60    drop(offsets);
61    let rope = store.rope.read();
62    let char_start = rope.byte_to_char(bs as usize);
63    let char_end = rope.byte_to_char(content_end_bytes as usize);
64    (char_end - char_start) as i64
65}
66
67/// Return the absolute character position of a block's start in the
68/// document, derived from the rope via `BlockOffsetIndex`.
69///
70/// O(log n): one `range_of_block` lookup + one `byte_to_char` conversion.
71/// Falls back to `block.document_position` for blocks not registered in
72/// the index — blocks under non-top-level frames (`insert_frame_uc` only
73/// mirrors top-level frames). Table-cell blocks ARE registered: they are
74/// mirrored inline into the rope in document order. The stored field is
75/// set authoritatively by the non-flow paths and stays correct for them
76/// across main-flow edits.
77pub fn block_document_position(block: &Block, store: &Store) -> i64 {
78    let offsets = store.block_offsets.read();
79    let Some((byte_start, _)) = offsets.range_of_block(block.id) else {
80        return block.document_position;
81    };
82    drop(offsets);
83    let rope = store.rope.read();
84    rope.byte_to_char(byte_start as usize) as i64
85}
86
87/// Bring a batch of `document_position` slots in step with the rope.
88///
89/// `slots` pairs each block's id with the field to overwrite. A block the offset index
90/// holds gets its rope-derived start; one it does not hold keeps what it had. When the rope
91/// is not the document's position space (see [`rope_positions_match_flow`]) nothing is
92/// touched: there the stored field is maintained by the editing use cases and is the truth.
93///
94/// This is the reader's half of the bargain `insert_text_uc` and `delete_text_uc` struck
95/// when they stopped shifting every later block on every keystroke: the stored field drifts
96/// by exactly what was typed (or removed) since the last time something wrote it, so a use
97/// case comparing a caller's position with it compares two different spaces. That is how a
98/// cut at a paragraph's end came to carry the paragraph break and the head of the next
99/// paragraph away while the deletion, which walks the rope, took only the selection — and
100/// how bold, replace and "make a list" landed the same number of characters late.
101pub fn refresh_positions_from_rope<'a>(
102    store: &Store,
103    slots: impl IntoIterator<Item = (EntityId, &'a mut i64)>,
104) {
105    if !rope_positions_match_flow(store) {
106        return;
107    }
108    let offsets = store.block_offsets.read();
109    let rope = store.rope.read();
110    for (block_id, slot) in slots {
111        if let Some((byte_start, _)) = offsets.range_of_block(block_id) {
112            *slot = rope.byte_to_char(byte_start as usize) as i64;
113        }
114    }
115}
116
117/// [`refresh_positions_from_rope`] over block entities — what a use case holds after
118/// `get_block_multi`. Call it before sorting by `document_position` or comparing that field
119/// with a position the caller supplied.
120pub fn refresh_block_positions(blocks: &mut [Block], store: &Store) {
121    refresh_positions_from_rope(
122        store,
123        blocks.iter_mut().map(|b| (b.id, &mut b.document_position)),
124    );
125}
126
127/// Whether the rope's char-position space matches the user-visible
128/// flow positions that `Block.document_position` is computed against.
129///
130/// They match when every block is mirrored to the rope as a contiguous
131/// run. They DON'T match when:
132/// 1. The document contains tables — cell content sits at separate rope
133///    byte ranges (plan §1.6), so the rope is missing the cells'
134///    flow-position contribution.
135/// 2. The document contains sub-frames whose blocks aren't mirrored —
136///    `insert_frame_uc` only mirrors top-level frames.
137///
138/// When this returns `true`, readers can derive `document_position`
139/// directly from the rope (O(log n)) and the use-case-side
140/// position-refresh loops can be skipped. When it returns `false`,
141/// readers must consult the maintained `Block.document_position`
142/// stored field, and the loops are required to keep it correct.
143pub fn rope_positions_match_flow(store: &Store) -> bool {
144    let offsets = store.block_offsets.read();
145    // The rope is authoritative as long as EVERY block is mirrored into it.
146    // Tables no longer disqualify it: cell content is mirrored inline, in
147    // document order, and the table itself occupies a 1-char anchor sentinel
148    // — so the rope's char space matches the user-visible flow order. (The
149    // flow snapshot derives its block positions from this same rope space,
150    // so the two agree by construction.) Only count Block markers; the
151    // TableAnchor sentinel entries are not blocks.
152    // The index holds exactly two kinds of entry, so the blocks it mirrors are what is
153    // left once the anchors are taken away — an O(1) answer for a check that sits on the
154    // clamp of every caret move, insert and delete.
155    let indexed_block_count = offsets.len() - offsets.table_anchor_count();
156    drop(offsets);
157    let total_block_count = store.blocks.read().len();
158    indexed_block_count == total_block_count
159}
160
161/// Where the main text ends, as a position, when the rope holds anything after it, which
162/// is the footnote bodies: the end of the main frame's last entry. `None` when nothing
163/// follows the main text, or when the rope's positions are not the flow's.
164///
165/// No view shows a footnote's body, and the loads put every body after the main text: a
166/// caret moved on from the end of the text went into the first note, and typing there
167/// edited it unseen. The cursor's moves stop here.
168///
169/// Read down from the end of the main frame, so it costs the depth of the frames the text
170/// ends in (and the cells of a table it ends with), whatever the length of the text and
171/// however many notes follow it. Every forward move of a caret asks it; it gathered every
172/// block of every body first, milliseconds a keystroke in a document of many notes.
173pub fn main_text_end(store: &Store) -> Option<i64> {
174    if !rope_positions_match_flow(store) {
175        return None;
176    }
177    let main_frame = store
178        .documents
179        .read()
180        .values()
181        .next()
182        .and_then(|document| document.frames.first().copied())?;
183    let last = {
184        let tables = store.tables.read();
185        let cells = store.table_cells.read();
186        let frames = store.frames.read();
187        last_flow_entry(main_frame, &tables, &cells, &frames)?
188    };
189    let offsets = store.block_offsets.read();
190    let last_of_text = offsets.position_of(last)?;
191    looked_at(1);
192    // The text of that entry ends at the boundary before whatever follows it.
193    let next_start = offsets.entries.get(last_of_text + 1)?.1;
194    drop(offsets);
195    let end_byte = next_start.saturating_sub(1) as usize;
196    Some(store.rope.read().byte_to_char(end_byte) as i64)
197}
198
199/// The last entry of the flow of `frame_id`, in reading order: its last block, or the last
200/// entry of the quotation or the table it ends with. `None` when it holds nothing.
201fn last_flow_entry(
202    frame_id: EntityId,
203    tables: &im::HashMap<EntityId, crate::entities::Table>,
204    cells: &im::HashMap<EntityId, crate::entities::TableCell>,
205    frames: &im::HashMap<EntityId, crate::entities::Frame>,
206) -> Option<OffsetMarker> {
207    // Each frame on the way down, with how many of its entries are still to look at: an
208    // empty quotation at the end sends the walk back to the entry before it.
209    let mut stack: Vec<(EntityId, usize)> =
210        vec![(frame_id, frames.get(&frame_id)?.child_order.len())];
211    let mut seen: std::collections::HashSet<EntityId> = std::collections::HashSet::new();
212    seen.insert(frame_id);
213    while let Some((id, remaining)) = stack.pop() {
214        looked_at(1);
215        let Some(entry) = remaining
216            .checked_sub(1)
217            .and_then(|at| frames.get(&id)?.child_order.get(at).copied())
218        else {
219            continue;
220        };
221        stack.push((id, remaining - 1));
222        if entry > 0 {
223            return Some(OffsetMarker::Block(entry as EntityId));
224        }
225        let sub_id = entry.unsigned_abs() as EntityId;
226        let Some(sub) = frames.get(&sub_id) else {
227            continue;
228        };
229        if !seen.insert(sub_id) {
230            continue;
231        }
232        match sub.table {
233            Some(table_id) => {
234                let mut ordered: Vec<OffsetMarker> = Vec::new();
235                table_reading_order(table_id, tables, cells, frames, &mut ordered);
236                looked_at(ordered.len());
237                return ordered.last().copied();
238            }
239            None => stack.push((sub_id, sub.child_order.len())),
240        }
241    }
242    None
243}
244
245/// Record `count` frames or index entries [`main_text_end`] looked at. Unit tests count
246/// them: it runs on every forward move of a caret, and a debug build cannot time it.
247fn looked_at(count: usize) {
248    #[cfg(test)]
249    tests::LOOKED_AT.with(|looked| looked.set(looked.get() + count));
250    #[cfg(not(test))]
251    let _ = count;
252}
253
254/// Locate which block contains a given absolute char position in the
255/// document, returning `(block_id, char_offset_in_block, block_char_start)`
256/// in O(log n) using the rope + `BlockOffsetIndex` instead of an O(N)
257/// linear walk of all blocks.
258///
259/// Replaces the per-keystroke hot path in editing use cases
260/// (`find_block_at_position_sequential`) which fetched every block
261/// + called `block_char_length` per block. For an N-block document
262///   each editor keystroke now costs O(log n) lookups instead of O(N).
263///
264/// Returns `None` only when some block is unmirrored (a sub-frame
265/// inserted with a parent — `insert_frame_uc` mirrors only top-level
266/// frames), where the rope's char space diverges from flow order and
267/// callers must fall back to the slow per-block walk. Tables are fine:
268/// cell content is mirrored inline in document order and each table is a
269/// 1-char anchor sentinel, so byte→block lookup resolves correctly.
270///
271/// `position` past the document end clamps to the last block's
272/// end-of-content.
273pub fn find_block_at_char_position(store: &Store, position: i64) -> Option<(EntityId, i64, i64)> {
274    // Fast path is only valid when EVERY block in the document is
275    // mirrored to the rope. Disqualifying cases:
276    //
277    // 1. Documents containing tables — cell content sits at separate
278    //    rope byte ranges (plan §1.6) so byte→block lookup finds the
279    //    wrong block for cursor positions inside cells.
280    //
281    // 2. Documents containing sub-frames inserted with a parent —
282    //    `insert_frame_uc` currently only mirrors top-level frames to
283    //    the rope (parent=None case), leaving sub-frame blocks
284    //    unregistered in the offset index. Detect by comparing block
285    //    counts: if the rope index has fewer Block markers than the
286    //    store has Block entities, some are unmirrored.
287    let offsets = store.block_offsets.read();
288    // Valid as long as every block is mirrored to the rope. Tables are fine:
289    // cell content is mirrored inline in document order and the table is a
290    // 1-char anchor sentinel, so byte→block lookup resolves correctly for any
291    // non-sentinel position. A position that lands exactly on the sentinel
292    // resolves to a TableAnchor marker, where `as_block()` returns None and
293    // the caller falls back to the slow walk. Only count Block markers.
294    let indexed_block_count = offsets.entries.iter().filter(|(m, _)| m.is_block()).count();
295    let total_block_count = store.blocks.read().len();
296    if indexed_block_count != total_block_count {
297        return None;
298    }
299    drop(offsets);
300
301    let rope = store.rope.read();
302    let total_chars = rope.len_chars() as i64;
303    let pos_clamped = position.clamp(0, total_chars);
304    let abs_byte = rope.char_to_byte(pos_clamped as usize);
305    drop(rope);
306
307    let offsets = store.block_offsets.read();
308    let block_id = offsets.marker_at_byte(abs_byte as u32)?.as_block()?;
309    let (bs, be, has_successor) = offsets.range_with_successor(OffsetMarker::Block(block_id))?;
310    let content_end = if has_successor && be > bs { be - 1 } else { be };
311
312    drop(offsets);
313
314    let rope = store.rope.read();
315    let block_char_start = rope.byte_to_char(bs as usize) as i64;
316    // Clamp the cursor's byte to the block's content area (not into the
317    // trailing `\n` boundary if any).
318    let byte_for_char = std::cmp::min(abs_byte, content_end as usize);
319    let abs_char = rope.byte_to_char(byte_for_char) as i64;
320    let char_in_block = abs_char - block_char_start;
321
322    // NOTE: separator semantics differ across use cases. Callers like
323    // `get_block_at_position_uc` interpret "position at the end of a
324    // non-empty block with a successor" as "belongs to the next
325    // block"; callers like `insert_text_uc` want the previous block
326    // with offset == block_char_len. This helper returns the
327    // previous-block answer (the simpler semantic); use-case-specific
328    // advance logic lives at the call site.
329    let _ = has_successor;
330
331    Some((block_id, char_in_block, block_char_start))
332}
333
334/// Convert an in-block char offset to an in-block byte offset using the
335/// rope's index. Both inputs and outputs are relative to the start of
336/// the block's content (NOT absolute rope positions). The char offset
337/// is clamped to the block's logical length so callers don't need to
338/// pre-validate.
339///
340/// O(log n) via `ropey::Rope::char_to_byte` — replaces the O(L)
341/// "materialize block text + walk char_indices" pattern that
342/// `set_text_format_uc` / `merge_text_format_uc` used. Returns
343/// `(byte_offset_in_block, content_byte_len)` so callers can also
344/// pass the content length to `debug_assert_well_formed` without
345/// materializing the text.
346///
347/// Returns `(0, 0)` for blocks not registered in the offset index.
348pub fn block_char_to_byte_in_block(
349    store: &Store,
350    block_id: EntityId,
351    char_offset: usize,
352) -> (u32, usize) {
353    let offsets = store.block_offsets.read();
354    let marker = OffsetMarker::Block(block_id);
355    let Some((bs, be, has_successor)) = offsets.range_with_successor(marker) else {
356        return (0, 0);
357    };
358    let content_end_bytes = if has_successor && be > bs { be - 1 } else { be };
359    let content_byte_len = (content_end_bytes - bs) as usize;
360    drop(offsets);
361
362    let rope = store.rope.read();
363    let block_char_start = rope.byte_to_char(bs as usize);
364    let block_char_end = rope.byte_to_char(content_end_bytes as usize);
365    let block_char_len = block_char_end - block_char_start;
366
367    // Clamp char_offset to block's char length.
368    let clamped = std::cmp::min(char_offset, block_char_len);
369    let abs_byte = rope.char_to_byte(block_char_start + clamped);
370    let byte_in_block = (abs_byte - bs as usize) as u32;
371    (byte_in_block, content_byte_len)
372}
373
374/// Fast-path full-document plain text: returns `Some(rope.to_string())`
375/// iff the document is in the canonical flat layout — no table anchors
376/// in the offset index, single top-level frame. In that case the
377/// rope's byte order is the same as the document-flow order, so one
378/// `to_string()` allocation replaces the O(N) per-block walk +
379/// per-block `Cow<str>` materialization that `build_full_text` /
380/// `export_plain_text` would otherwise do.
381///
382/// Returns `None` for documents containing tables or nested frames —
383/// those require the per-frame, per-block traversal because table
384/// cell content lives in separate byte ranges later in the rope
385/// (plan §1.6), not interleaved with the parent frame's bytes.
386///
387/// `top_frame_count` is the caller-known number of top-level frames
388/// (typically obtained from `Document.frames.len()`). Callers
389/// already have this value and pass it in to avoid a redundant uow
390/// query.
391pub fn rope_flat_text_if_simple(store: &Store, top_frame_count: usize) -> Option<String> {
392    if top_frame_count != 1 {
393        return None;
394    }
395    let offsets = store.block_offsets.read();
396    let has_table = offsets
397        .entries
398        .iter()
399        .any(|(m, _)| matches!(m, OffsetMarker::TableAnchor(_)));
400    if has_table {
401        return None;
402    }
403    drop(offsets);
404    Some(store.rope.read().to_string())
405}
406
407/// Whole-document searchable text straight from the rope, valid whenever
408/// the rope's char-position space matches the user-visible flow order
409/// (`rope_positions_match_flow`).
410///
411/// Unlike `rope_flat_text_if_simple` this does NOT bail on tables or
412/// multiple top-level frames: table-cell content is mirrored inline into
413/// the rope in document order and each table occupies a 1-char anchor
414/// sentinel, so the rope already contains all searchable text — including
415/// cell text — at the same char offsets that match positions are reported
416/// in. Returns `None` only when some block is unmirrored (e.g. a sub-frame
417/// inserted with a parent), where the caller must fall back to the
418/// per-frame, per-block traversal.
419pub fn rope_full_text_if_flow_matches(store: &Store) -> Option<String> {
420    rope_positions_match_flow(store).then(|| store.rope.read().to_string())
421}
422
423/// Reset the rope to empty and clear `block_offsets`. Called by
424/// importers when they replace the entire document content.
425pub fn rope_reset(store: &Store) {
426    *store.rope.write() = ropey::Rope::new();
427    *store.block_offsets.write() = crate::database::block_offset_index::BlockOffsetIndex::new();
428}
429
430/// Append `text` to the end of the rope and register `block_id` at
431/// the byte position where the text starts. Returns that byte offset.
432///
433/// Callers are responsible for inserting an inter-block `\n`
434/// (`rope_insert_block_boundary`) before each block AFTER the first
435/// in a contiguous frame.
436pub fn rope_append_block(store: &Store, block_id: EntityId, text: &str) -> u32 {
437    let mut rope = store.rope.write();
438    let byte_start = rope.len_bytes() as u32;
439    let char_end = rope.len_chars();
440    rope.insert(char_end, text);
441    let new_total = rope.len_bytes() as u32;
442    drop(rope);
443
444    let mut offsets = store.block_offsets.write();
445    offsets.push_block(block_id, byte_start);
446    offsets.set_total_bytes(new_total);
447    byte_start
448}
449
450/// Insert `text` as a new block at `byte_pos` in the rope, prepending
451/// a `\n` boundary. Used by `insert_table_uc` to place cell blocks at
452/// the end of their containing top-level frame's range (plan §1.6),
453/// rather than always at rope end.
454///
455/// Total bytes inserted: `1 + text.len()`. The block's content
456/// occupies `[byte_pos + 1, byte_pos + 1 + text.len())`. The block
457/// entry is registered at `byte_pos + 1` in `block_offsets`.
458///
459/// Existing entries with `byte_start == byte_pos` (e.g. a previous
460/// empty block whose end coincides with this insertion point) are
461/// kept BEFORE the new entry in the Vec, since the inserted `\n`
462/// boundary belongs after them. Entries strictly past `byte_pos`
463/// shift forward by `(1 + text.len())` bytes.
464///
465/// When `byte_pos == total_bytes`, behaves like
466/// `rope_insert_block_boundary` followed by `rope_append_block`.
467pub fn rope_insert_block_at(store: &Store, byte_pos: u32, block_id: EntityId, text: &str) {
468    let delta = (1 + text.len()) as i32;
469    // Vec position: insert AFTER any entry at byte_pos itself
470    // (those represent earlier empty blocks whose `\n` boundary
471    // we are placing now). Only entries strictly past byte_pos
472    // come after our new entry in the Vec.
473    let new_entry_vec_pos = {
474        let offsets = store.block_offsets.read();
475        offsets
476            .entries
477            .iter()
478            .position(|(_, bs)| *bs > byte_pos)
479            .unwrap_or(offsets.entries.len())
480    };
481    {
482        let mut rope = store.rope.write();
483        let char_idx = rope.byte_to_char(byte_pos as usize);
484        let mut combined = String::with_capacity(1 + text.len());
485        combined.push('\n');
486        combined.push_str(text);
487        rope.insert(char_idx, &combined);
488    }
489    let mut offsets = store.block_offsets.write();
490    // Shift entries strictly past byte_pos. Entries AT byte_pos
491    // (the prior empty block) stay where they are — the new `\n`
492    // is conceptually "after" them.
493    offsets.shift_after(byte_pos + 1, delta);
494    offsets.insert_at(
495        new_entry_vec_pos,
496        OffsetMarker::Block(block_id),
497        byte_pos + 1,
498    );
499}
500
501/// Walks up `frame.parent_frame` to find the top-level ancestor of
502/// the given frame, then returns the end byte of that top-level
503/// frame's current rope range.
504///
505/// Not where a table's cells belong. They follow the table's anchor, in
506/// reading order (see [`rope_insert_run_after`] and
507/// [`rope_place_new_cell_blocks`]); the end of the enclosing frame is that
508/// place only when the table is the last thing in the frame, and cells put
509/// there after a table followed by text left the rope out of flow order.
510/// No editing use case calls this any more.
511///
512/// Reads `block_offsets`/`frames`/`tables`/`table_cells` directly, so
513/// the result is fresh even when `Frame.byte_range` has not yet been
514/// recomputed at commit time.
515pub fn top_level_frame_end_byte(store: &Store, frame_id: EntityId) -> u32 {
516    let top_id = {
517        let frames = store.frames.read();
518        let mut current = frame_id;
519        loop {
520            let Some(f) = frames.get(&current) else {
521                return 0;
522            };
523            match f.parent_frame {
524                None => break current,
525                Some(p) => current = p,
526            }
527        }
528    };
529    let (_min, max) = compute_frame_byte_range_recursive(store, top_id);
530    max
531}
532
533/// Append a new empty block to the end of the rope, separating it
534/// from any prior content with a `\n` boundary (only if the rope is
535/// already non-empty). Registers `block_id` at the resulting byte
536/// position. Returns that byte position. Used when `insert_frame_uc`
537/// creates a new top-level frame with a single empty block.
538pub fn rope_append_empty_block(store: &Store, block_id: EntityId) -> u32 {
539    let was_empty = store.rope.read().len_bytes() == 0;
540    if !was_empty {
541        rope_insert_block_boundary(store);
542    }
543    let pos = store.rope.read().len_bytes() as u32;
544    let mut offsets = store.block_offsets.write();
545    offsets.push_block(block_id, pos);
546    offsets.set_total_bytes(pos);
547    pos
548}
549
550/// Register `block_id` as a new empty block in front of every other entry:
551/// at byte 0, followed by a boundary `\n` when anything comes after it.
552/// Every other entry moves one byte on.
553pub fn rope_insert_empty_block_first(store: &Store, block_id: EntityId) {
554    let mut offsets = store.block_offsets.write();
555    if !offsets.is_empty() {
556        {
557            let mut rope = store.rope.write();
558            rope.insert(0, "\n");
559        }
560        offsets.shift_after(0, 1);
561    }
562    offsets.insert_at(0, OffsetMarker::Block(block_id), 0);
563}
564
565/// Append a single `\n` inter-block boundary character to the end of
566/// the rope. Does NOT register a block — this is the sentinel between
567/// two adjacent blocks within the same frame (plan §1.4).
568pub fn rope_insert_block_boundary(store: &Store) {
569    let mut rope = store.rope.write();
570    let char_end = rope.len_chars();
571    rope.insert(char_end, "\n");
572    let new_total = rope.len_bytes() as u32;
573    drop(rope);
574
575    store.block_offsets.write().set_total_bytes(new_total);
576}
577
578/// Insert `text` at `byte_offset_in_block` inside the block identified
579/// by `block_id`. Looks up the block's start in the rope via
580/// `block_offsets.range_of()`, splices into the rope, and shifts
581/// subsequent block offsets by the inserted byte length.
582///
583/// Silently no-ops if the block is not registered in the offset index
584/// (this can happen for blocks whose content lives outside the global
585/// rope, e.g. table cells until step 5.5).
586pub fn rope_insert_in_block(
587    store: &Store,
588    block_id: EntityId,
589    byte_offset_in_block: u32,
590    text: &str,
591) {
592    let inserted_bytes = text.len() as u32;
593    if inserted_bytes == 0 {
594        return;
595    }
596    let block_byte_start = {
597        let offsets = store.block_offsets.read();
598        let Some((start, _end)) = offsets.range_of_block(block_id) else {
599            return;
600        };
601        start
602    };
603    let rope_byte = block_byte_start + byte_offset_in_block;
604    {
605        let mut rope = store.rope.write();
606        let char_idx = rope.byte_to_char(rope_byte as usize);
607        rope.insert(char_idx, text);
608    }
609    // Shift entries past this block by inserted_bytes. Threshold
610    // is one byte past block_byte_start so the current block's own
611    // entry isn't moved.
612    store
613        .block_offsets
614        .write()
615        .shift_after(block_byte_start + 1, inserted_bytes as i32);
616}
617
618/// Split an existing block in the rope at `byte_offset_in_block`:
619/// - inserts a `\n` inter-block boundary at the absolute byte position
620///   `block_start + byte_offset_in_block` in the rope
621/// - shifts entries past that position by +1 byte
622/// - inserts a new entry for `new_block_id` at
623///   `block_start + byte_offset_in_block + 1` (right after the newline),
624///   placed immediately after the original block in the entries Vec
625///
626/// `byte_offset_in_block` may be 0 (split before first char of block,
627/// i.e. insert empty block before this one) or equal to the block's
628/// byte length (split after last char, i.e. insert empty block after).
629pub fn rope_split_block(
630    store: &Store,
631    current_block_id: EntityId,
632    byte_offset_in_block: u32,
633    new_block_id: EntityId,
634) {
635    let current_marker = OffsetMarker::Block(current_block_id);
636    let (block_start, current_idx) = {
637        let offsets = store.block_offsets.read();
638        let Some((start, _end)) = offsets.range_of(current_marker) else {
639            return;
640        };
641        let idx = offsets
642            .entries
643            .iter()
644            .position(|(m, _)| *m == current_marker)
645            .unwrap();
646        (start, idx)
647    };
648    let split_byte = block_start + byte_offset_in_block;
649
650    // 1. Insert the `\n` boundary at the split point.
651    {
652        let mut rope = store.rope.write();
653        let char_idx = rope.byte_to_char(split_byte as usize);
654        rope.insert(char_idx, "\n");
655    }
656
657    // 2. Shift entries past the split (and total_bytes) by +1.
658    //    Threshold > split_byte so the new entry we insert next
659    //    isn't double-shifted.
660    store.block_offsets.write().shift_after(split_byte + 1, 1);
661
662    // 3. Register the new block at `split_byte + 1`, immediately
663    //    after the original in the entries Vec.
664    store.block_offsets.write().insert_at(
665        current_idx + 1,
666        OffsetMarker::Block(new_block_id),
667        split_byte + 1,
668    );
669}
670
671/// [`rope_split_block`] on `current_block_id` at `byte_offset_in_block`,
672/// then again at the end of each new block in turn, each new block
673/// filled with its text by [`rope_insert_in_block`]: the rope and index
674/// that loop leaves, built with one rope insert and one index update.
675///
676/// `blocks` pairs each new block's id with its text, in document order.
677/// Whatever followed the split point in `current_block_id` ends up after
678/// the last new block, as it does through the loop. No-op if
679/// `current_block_id` is not in the index.
680///
681/// The loop walks every marker in the index once per new block, so
682/// pasting or restoring a document of N paragraphs through it cost N
683/// walks of N markers.
684pub fn rope_split_block_into(
685    store: &Store,
686    current_block_id: EntityId,
687    byte_offset_in_block: u32,
688    blocks: &[(EntityId, &str)],
689) {
690    let current_marker = OffsetMarker::Block(current_block_id);
691    let (block_start, current_idx) = {
692        let offsets = store.block_offsets.read();
693        let (Some((start, _end)), Some(idx)) = (
694            offsets.range_of(current_marker),
695            offsets.position_of(current_marker),
696        ) else {
697            return;
698        };
699        (start, idx)
700    };
701    rope_insert_marker_run(
702        store,
703        block_start + byte_offset_in_block,
704        current_idx + 1,
705        blocks
706            .iter()
707            .map(|(block_id, text)| (OffsetMarker::Block(*block_id), *text)),
708    );
709}
710
711/// [`rope_insert_block_at`] for each of `blocks` in turn, the first at
712/// `byte_pos` and each next one at the byte right after the block before
713/// it: the rope and index that loop leaves, built with one rope insert
714/// and one index update. Returns the byte right after the last block,
715/// where that loop would insert next.
716///
717/// `blocks` pairs each new block's id with its text, in document order.
718pub fn rope_insert_blocks_at(store: &Store, byte_pos: u32, blocks: &[(EntityId, &str)]) -> u32 {
719    // Same placement rule as `rope_insert_block_at`: after every entry at
720    // `byte_pos` itself, before every entry strictly past it.
721    let vec_pos = {
722        let offsets = store.block_offsets.read();
723        offsets
724            .entries
725            .iter()
726            .position(|(_, bs)| *bs > byte_pos)
727            .unwrap_or(offsets.entries.len())
728    };
729    rope_insert_marker_run(
730        store,
731        byte_pos,
732        vec_pos,
733        blocks
734            .iter()
735            .map(|(block_id, text)| (OffsetMarker::Block(*block_id), *text)),
736    )
737}
738
739/// Insert `run` into the rope right after the content of the entry
740/// `after`, in order: each marker a `\n` boundary followed by its text (a
741/// block's content, or `U+FFFC` for a table's anchor), registered in the
742/// offset index right after `after`. Whatever followed `after` follows the
743/// run. Returns `false`, leaving the rope alone, when `after` is not in the
744/// index.
745///
746/// This is how a paste lays out what it inserts after the block at the
747/// caret: its paragraphs, each table's anchor followed by the table's cells
748/// in reading order, and the tail, in the order the frames list them, with
749/// one rope insert and one index update for the whole paste.
750pub fn rope_insert_run_after(
751    store: &Store,
752    after: OffsetMarker,
753    run: &[(OffsetMarker, &str)],
754) -> bool {
755    let (content_end, position) = {
756        let offsets = store.block_offsets.read();
757        let (Some((start, end, has_successor)), Some(position)) = (
758            offsets.range_with_successor(after),
759            offsets.position_of(after),
760        ) else {
761            return false;
762        };
763        let content_end = if has_successor && end > start {
764            end - 1
765        } else {
766            end
767        };
768        (content_end, position)
769    };
770    rope_insert_marker_run(store, content_end, position + 1, run.iter().copied());
771    true
772}
773
774/// Insert a run of new markers at `byte_pos`, each a `\n` boundary
775/// followed by its text, and register them in the offset index at
776/// `vec_pos`, `vec_pos + 1`, …. Every entry strictly past `byte_pos`
777/// shifts by the whole run. Returns the byte right after the run.
778fn rope_insert_marker_run<'a>(
779    store: &Store,
780    byte_pos: u32,
781    vec_pos: usize,
782    markers: impl IntoIterator<Item = (OffsetMarker, &'a str)>,
783) -> u32 {
784    let mut inserted = String::new();
785    let mut run = Vec::new();
786    for (marker, text) in markers {
787        inserted.push('\n');
788        run.push((marker, byte_pos + inserted.len() as u32));
789        inserted.push_str(text);
790    }
791    if run.is_empty() {
792        return byte_pos;
793    }
794    {
795        let mut rope = store.rope.write();
796        let char_idx = rope.byte_to_char(byte_pos as usize);
797        rope.insert(char_idx, &inserted);
798    }
799    let mut offsets = store.block_offsets.write();
800    offsets.shift_after(byte_pos + 1, inserted.len() as i32);
801    offsets.insert_run_at(vec_pos, &run);
802    byte_pos + inserted.len() as u32
803}
804
805/// Mirror a table's new, empty cell blocks into the rope where reading order
806/// puts them: each after the block before it in the table's row-major order,
807/// the first cell's after the table's anchor. `new_blocks` are blocks the
808/// table's cells list but the index does not hold yet; the others stay
809/// where they are. Consecutive new blocks go in as one run.
810///
811/// The row, column and cell-split edits used to put their new cells at the
812/// end of the table's enclosing top-level frame, which is where they belong
813/// only when the table is the last thing in it: after any table followed by
814/// text, the new cells sat after that text in the rope, out of flow order,
815/// and every position past the table was wrong.
816pub fn rope_place_new_cell_blocks(store: &Store, table_id: EntityId, new_blocks: &[EntityId]) {
817    if new_blocks.is_empty() {
818        return;
819    }
820    let new: std::collections::HashSet<EntityId> = new_blocks.iter().copied().collect();
821    // Everything the table holds, in reading order: its anchor, then its
822    // cells by row and column, each cell's blocks and whatever is nested in
823    // it in its frame's order.
824    let mut ordered: Vec<OffsetMarker> = Vec::new();
825    {
826        let tables = store.tables.read();
827        let cells = store.table_cells.read();
828        let frames = store.frames.read();
829        table_reading_order(table_id, &tables, &cells, &frames, &mut ordered);
830    }
831    let mut after = OffsetMarker::TableAnchor(table_id);
832    let mut run: Vec<(OffsetMarker, &str)> = Vec::new();
833    for marker in ordered {
834        if matches!(marker, OffsetMarker::Block(id) if new.contains(&id)) {
835            run.push((marker, ""));
836            continue;
837        }
838        if !run.is_empty() {
839            rope_insert_run_after(store, after, &run);
840            run.clear();
841        }
842        after = marker;
843    }
844    if !run.is_empty() {
845        rope_insert_run_after(store, after, &run);
846    }
847}
848
849/// Put `table_id`'s anchor and the blocks of its cells back in reading order in
850/// the rope, when an edit of the table's rows left them in another.
851///
852/// Removing the first row of a cell that spans two rows keeps the cell at its
853/// row, one row shorter, and moves the row below up beside it: a moved-up cell
854/// of an earlier column now comes before the spanning cell in reading order,
855/// while the rope still held the spanning cell's text first. Every position in
856/// the table then addressed another cell than the one the frames put there, and
857/// the text a caret walked read the cells in another order than the save.
858///
859/// The table's entries are rewritten where they stand, as one span: same texts,
860/// same boundaries, same length, so nothing outside the table moves. Leaves the
861/// rope alone when its entries are already in reading order, or are not all in
862/// the index and next to each other.
863pub fn rope_restore_table_reading_order(store: &Store, table_id: EntityId) {
864    let mut ordered: Vec<OffsetMarker> = Vec::new();
865    {
866        let tables = store.tables.read();
867        let cells = store.table_cells.read();
868        let frames = store.frames.read();
869        table_reading_order(table_id, &tables, &cells, &frames, &mut ordered);
870    }
871    let mut offsets = store.block_offsets.write();
872    let positions: Option<Vec<usize>> = ordered
873        .iter()
874        .map(|marker| offsets.position_of(*marker))
875        .collect();
876    let Some(positions) = positions else {
877        return;
878    };
879    if positions.windows(2).all(|pair| pair[0] < pair[1]) {
880        return;
881    }
882    let Some(first) = positions.iter().min().copied() else {
883        return;
884    };
885    let last = first + positions.len() - 1;
886    let mut sorted = positions.clone();
887    sorted.sort_unstable();
888    if sorted
889        .iter()
890        .enumerate()
891        .any(|(i, position)| *position != first + i)
892    {
893        return;
894    }
895    let total = offsets.total_bytes();
896    let entries = offsets.entries.clone();
897    // Where each entry's text ends: at the boundary before the next entry, or at
898    // the end of the rope for the last one.
899    let text_end = |index: usize| -> u32 {
900        entries
901            .get(index + 1)
902            .map_or(total, |(_, next)| next.saturating_sub(1))
903    };
904    let span_start = entries[first].1;
905    let span_end = text_end(last);
906    let mut rope = store.rope.write();
907    let char_of = |byte: u32| rope.byte_to_char(byte as usize);
908    let text_of = |index: usize| -> String {
909        let (start, end) = (entries[index].1, text_end(index));
910        rope.slice(char_of(start)..char_of(end)).to_string()
911    };
912    let mut rebuilt = String::with_capacity((span_end - span_start) as usize);
913    let mut run: Vec<(OffsetMarker, u32)> = Vec::with_capacity(positions.len());
914    for (marker, position) in ordered.iter().zip(&positions) {
915        if !run.is_empty() {
916            rebuilt.push('\n');
917        }
918        run.push((*marker, span_start + rebuilt.len() as u32));
919        rebuilt.push_str(&text_of(*position));
920    }
921    if rebuilt.len() as u32 != span_end - span_start {
922        return;
923    }
924    let (char_start, char_end) = (char_of(span_start), char_of(span_end));
925    rope.remove(char_start..char_end);
926    rope.insert(char_start, &rebuilt);
927    offsets.reorder_run(first, &run);
928}
929
930/// Append `table_id`'s anchor and everything in its cells to `out`, in
931/// reading order.
932fn table_reading_order(
933    table_id: EntityId,
934    tables: &im::HashMap<EntityId, crate::entities::Table>,
935    cells: &im::HashMap<EntityId, crate::entities::TableCell>,
936    frames: &im::HashMap<EntityId, crate::entities::Frame>,
937    out: &mut Vec<OffsetMarker>,
938) {
939    out.push(OffsetMarker::TableAnchor(table_id));
940    let Some(table) = tables.get(&table_id) else {
941        return;
942    };
943    let mut table_cells: Vec<_> = table.cells.iter().filter_map(|id| cells.get(id)).collect();
944    table_cells.sort_by_key(|cell| (cell.row, cell.column));
945    for cell in table_cells {
946        if let Some(frame) = cell.cell_frame {
947            frame_reading_order(frame, tables, cells, frames, out);
948        }
949    }
950}
951
952/// Every block `table_id` holds, nested ones included, in reading order.
953pub fn table_block_ids(store: &Store, table_id: EntityId) -> Vec<EntityId> {
954    let mut ordered: Vec<OffsetMarker> = Vec::new();
955    {
956        let tables = store.tables.read();
957        let cells = store.table_cells.read();
958        let frames = store.frames.read();
959        table_reading_order(table_id, &tables, &cells, &frames, &mut ordered);
960    }
961    ordered
962        .into_iter()
963        .filter_map(OffsetMarker::as_block)
964        .collect()
965}
966
967/// Insert `run` into the rope right after everything `table_id` holds: its
968/// anchor, its cells and whatever is nested in them, in reading order. See
969/// [`rope_insert_run_after`]. Returns `false`, leaving the rope alone, when the
970/// table's last entry is not in the index.
971pub fn rope_insert_run_after_table(
972    store: &Store,
973    table_id: EntityId,
974    run: &[(OffsetMarker, &str)],
975) -> bool {
976    let mut ordered: Vec<OffsetMarker> = Vec::new();
977    {
978        let tables = store.tables.read();
979        let cells = store.table_cells.read();
980        let frames = store.frames.read();
981        table_reading_order(table_id, &tables, &cells, &frames, &mut ordered);
982    }
983    match ordered.last() {
984        Some(last) => rope_insert_run_after(store, *last, run),
985        None => false,
986    }
987}
988
989/// The outermost table whose cells hold the frame `frame_id`, at any depth:
990/// the table, its anchor frame, and the frame whose `child_order` lists that
991/// anchor frame. `None` when `frame_id` is in no table cell.
992///
993/// Read from the tables' cell lists and the frames' `child_order`, never from
994/// `Frame.parent_frame`: a table pasted into the document has cell frames with
995/// no parent, so a walk up the parents took a caret in such a cell for one
996/// outside any table.
997pub fn outermost_table_around(
998    store: &Store,
999    frame_id: EntityId,
1000) -> Option<(EntityId, EntityId, EntityId)> {
1001    let tables = store.tables.read();
1002    let cells = store.table_cells.read();
1003    let frames = store.frames.read();
1004    let table_of_cell_frame = |frame: EntityId| {
1005        let (cell_id, _) = cells
1006            .iter()
1007            .find(|(_, cell)| cell.cell_frame == Some(frame))?;
1008        tables
1009            .iter()
1010            .find(|(_, table)| table.cells.contains(cell_id))
1011            .map(|(table_id, _)| *table_id)
1012    };
1013    let frame_listing = |frame: EntityId| {
1014        let entry = -(frame as i64);
1015        frames
1016            .iter()
1017            .find(|(_, candidate)| candidate.child_order.contains(&entry))
1018            .map(|(id, _)| *id)
1019    };
1020    let mut found = None;
1021    let mut current = frame_id;
1022    // Each step moves one frame out; a well-formed tree ends at a root in at
1023    // most as many steps as there are frames.
1024    for _ in 0..=frames.len() {
1025        let next = match table_of_cell_frame(current) {
1026            Some(table_id) => {
1027                let Some((anchor_id, _)) = frames
1028                    .iter()
1029                    .find(|(_, frame)| frame.table == Some(table_id))
1030                else {
1031                    break;
1032                };
1033                let Some(parent) = frame_listing(*anchor_id) else {
1034                    break;
1035                };
1036                found = Some((table_id, *anchor_id, parent));
1037                parent
1038            }
1039            None => match frame_listing(current) {
1040                Some(parent) => parent,
1041                None => break,
1042            },
1043        };
1044        current = next;
1045    }
1046    found
1047}
1048
1049/// Append a frame's blocks and everything nested in it to `out`, in the
1050/// frame's `child_order`.
1051fn frame_reading_order(
1052    frame_id: EntityId,
1053    tables: &im::HashMap<EntityId, crate::entities::Table>,
1054    cells: &im::HashMap<EntityId, crate::entities::TableCell>,
1055    frames: &im::HashMap<EntityId, crate::entities::Frame>,
1056    out: &mut Vec<OffsetMarker>,
1057) {
1058    let Some(frame) = frames.get(&frame_id) else {
1059        return;
1060    };
1061    for entry in &frame.child_order {
1062        if *entry > 0 {
1063            out.push(OffsetMarker::Block(*entry as EntityId));
1064        } else if *entry < 0 {
1065            let sub_id = (-*entry) as EntityId;
1066            match frames.get(&sub_id).and_then(|sub| sub.table) {
1067                Some(nested) => table_reading_order(nested, tables, cells, frames, out),
1068                None => frame_reading_order(sub_id, tables, cells, frames, out),
1069            }
1070        }
1071    }
1072}
1073
1074/// Merge `start_block` and `end_block` by deleting the rope range
1075/// `[start_block.start + byte_so .. end_block.start + byte_eo)` — i.e.
1076/// the suffix of `start_block`, every block between (and their
1077/// boundary newlines), and the prefix of `end_block`. Removes the
1078/// index entries for every block strictly between `start_block` and
1079/// `end_block` (inclusive of `end_block` itself); the surviving
1080/// content lives in `start_block`. Shifts any blocks past `end_block`
1081/// by the negative delta.
1082///
1083/// No-op if `start_block` is not in the index. Skipped for any
1084/// intermediate block id whose range is missing from the index (e.g.
1085/// table cells until step 5.5e).
1086pub fn rope_merge_block_range(
1087    store: &Store,
1088    start_block_id: EntityId,
1089    byte_so_in_start: u32,
1090    end_block_id: EntityId,
1091    byte_eo_in_end: u32,
1092) {
1093    let start_marker = OffsetMarker::Block(start_block_id);
1094    let end_marker = OffsetMarker::Block(end_block_id);
1095    let (start_block_byte, end_block_byte, start_idx, end_idx) = {
1096        let offsets = store.block_offsets.read();
1097        let Some((sb, _)) = offsets.range_of(start_marker) else {
1098            return;
1099        };
1100        let Some((eb, _)) = offsets.range_of(end_marker) else {
1101            return;
1102        };
1103        let si = offsets
1104            .entries
1105            .iter()
1106            .position(|(m, _)| *m == start_marker)
1107            .unwrap();
1108        let ei = offsets
1109            .entries
1110            .iter()
1111            .position(|(m, _)| *m == end_marker)
1112            .unwrap();
1113        (sb, eb, si, ei)
1114    };
1115    if end_idx <= start_idx {
1116        return;
1117    }
1118
1119    let delete_start = start_block_byte + byte_so_in_start;
1120    let delete_end = end_block_byte + byte_eo_in_end;
1121    if delete_end <= delete_start {
1122        return;
1123    }
1124    let deleted_bytes = delete_end - delete_start;
1125
1126    // 1. Remove the rope range.
1127    {
1128        let mut rope = store.rope.write();
1129        let char_start = rope.byte_to_char(delete_start as usize);
1130        let char_end = rope.byte_to_char(delete_end as usize);
1131        rope.remove(char_start..char_end);
1132    }
1133
1134    // 2. Remove block_offsets entries for [start_idx+1 ..= end_idx].
1135    {
1136        let mut offsets = store.block_offsets.write();
1137        offsets.drain_inclusive(start_idx + 1, end_idx);
1138    }
1139
1140    // 3. Shift any remaining entries past the deletion by -deleted_bytes.
1141    //    Threshold > delete_start because start_block's own entry
1142    //    sits at delete_start - byte_so_in_start (≤ delete_start)
1143    //    and must not move.
1144    store
1145        .block_offsets
1146        .write()
1147        .shift_after(delete_start + 1, -(deleted_bytes as i32));
1148}
1149
1150/// Insert a U+FFFC OBJECT REPLACEMENT CHARACTER sentinel in the rope
1151/// at the table-anchor position, registering a `TableAnchor(table_id)`
1152/// marker in the offset index (plan §1.6).
1153///
1154/// `target_block_id` is the block in the parent frame that the table
1155/// is adjacent to. `after` controls whether the table goes BEFORE
1156/// (`after = false`) or AFTER the target block.
1157///
1158/// The 3-byte sentinel is paired with an inter-marker `\n`:
1159/// - `after = false`: inserts `\u{FFFC}\n` at `target.byte_start`
1160/// - `after = true`, target is NOT the last entry: inserts
1161///   `\u{FFFC}\n` at `target.byte_end` (between target's trailing
1162///   `\n` and the next entry)
1163/// - `after = true`, target IS the last entry: inserts `\n\u{FFFC}`
1164///   at `target.byte_end` (rope now ends with the sentinel)
1165///
1166/// NOTE: cell-internal content is not yet routed through the rope —
1167/// the rope reflects table *presence* (3-byte sentinel) only.
1168/// Routing cell content is deferred to plan §1.6's `Frame.byte_range`
1169/// model.
1170///
1171/// No-op if `target_block_id` is not in the index.
1172pub fn rope_insert_table_anchor(
1173    store: &Store,
1174    table_id: EntityId,
1175    target_block_id: EntityId,
1176    after: bool,
1177) {
1178    const SENTINEL: &str = "\u{FFFC}"; // 3 bytes
1179    const SENTINEL_BYTES: u32 = 3;
1180
1181    let (insert_pos, target_idx, target_is_last) = {
1182        let offsets = store.block_offsets.read();
1183        let target_marker = OffsetMarker::Block(target_block_id);
1184        let Some((start, end)) = offsets.range_of(target_marker) else {
1185            return;
1186        };
1187        let idx = offsets
1188            .entries
1189            .iter()
1190            .position(|(m, _)| *m == target_marker)
1191            .unwrap();
1192        let is_last = idx + 1 == offsets.entries.len();
1193        let pos = if after { end } else { start };
1194        (pos, idx, is_last)
1195    };
1196
1197    // Insertion strategy:
1198    let (rope_inserted, marker_byte_start, new_entry_pos, shift_threshold, shift_delta) = if !after
1199    {
1200        // Before target: "\u{FFFC}\n" at target.byte_start
1201        ("\u{FFFC}\n", insert_pos, target_idx, insert_pos, 4i32)
1202    } else if !target_is_last {
1203        // After target, with following entries: "\u{FFFC}\n"
1204        // at target.byte_end. The TableAnchor sits where the
1205        // next block USED to start; that following entry
1206        // shifts by 4.
1207        ("\u{FFFC}\n", insert_pos, target_idx + 1, insert_pos, 4i32)
1208    } else {
1209        // After target which is last: "\n\u{FFFC}" appended.
1210        // TableAnchor's byte_start sits 1 past the original
1211        // total (after the new `\n`).
1212        (
1213            "\n\u{FFFC}",
1214            insert_pos + 1,
1215            target_idx + 1,
1216            insert_pos,
1217            4i32,
1218        )
1219    };
1220
1221    // 1. Splice the literal bytes into the rope.
1222    {
1223        let mut rope = store.rope.write();
1224        let char_idx = rope.byte_to_char(insert_pos as usize);
1225        rope.insert(char_idx, rope_inserted);
1226    }
1227
1228    // 2. Shift entries past the insertion point. Use shift_after
1229    //    BEFORE inserting our new entry so we don't double-shift.
1230    store
1231        .block_offsets
1232        .write()
1233        .shift_after(shift_threshold, shift_delta);
1234
1235    // 3. Register the TableAnchor at the resolved byte position
1236    //    and the resolved Vec position.
1237    store.block_offsets.write().insert_at(
1238        new_entry_pos,
1239        OffsetMarker::TableAnchor(table_id),
1240        marker_byte_start,
1241    );
1242
1243    // Note: SENTINEL_BYTES is part of `shift_delta` (3 for the
1244    // sentinel + 1 for the `\n`).
1245    let _ = SENTINEL;
1246    let _ = SENTINEL_BYTES;
1247}
1248
1249/// Append a U+FFFC table-anchor sentinel at the end of the rope and
1250/// register a `TableAnchor(table_id)` marker.
1251///
1252/// Used by import paths (`import_djot_uc`, `import_html_uc`,
1253/// `import_markdown_uc`) that process the document linearly and append
1254/// entities as they encounter them, rather than inserting relative to
1255/// an existing target block.
1256///
1257/// # `needs_boundary`
1258///
1259/// True when something has already been emitted, so the sentinel needs a
1260/// `\n` in front of it rather than running into the previous entry.
1261///
1262/// It is the **caller's** flag, not `rope.len_bytes() == 0`, and the
1263/// difference is not academic. Those two answers diverge on exactly one
1264/// document: one whose first block is *empty* — an empty code fence, say.
1265/// The rope is then still zero bytes long even though a block has been
1266/// emitted, so an emptiness check skips the boundary that block is owed.
1267/// Its `block_offsets` entry and the anchor's then both point at byte 0:
1268/// two entities claiming one offset, in the offset index every edit
1269/// resolves through.
1270///
1271/// Every other element gets its boundary from the importer's own
1272/// positional flag (`rope_insert_block_boundary` after the first block).
1273/// Deriving the same fact a second way, from the rope's byte length, is
1274/// what let the two disagree.
1275pub fn rope_append_table_anchor(store: &Store, table_id: EntityId, needs_boundary: bool) {
1276    let (anchor_byte_start, new_total) = {
1277        let mut rope = store.rope.write();
1278        let char_end = rope.len_chars();
1279        let to_insert = if needs_boundary {
1280            "\n\u{FFFC}"
1281        } else {
1282            "\u{FFFC}"
1283        };
1284        rope.insert(char_end, to_insert);
1285        let new_total = rope.len_bytes() as u32;
1286        // Sentinel is 3 bytes; if a `\n` was prepended that's 1 byte
1287        // before the sentinel.
1288        let anchor_byte_start = new_total - 3;
1289        (anchor_byte_start, new_total)
1290    };
1291
1292    let mut offsets = store.block_offsets.write();
1293    offsets.push(OffsetMarker::TableAnchor(table_id), anchor_byte_start);
1294    offsets.set_total_bytes(new_total);
1295}
1296
1297/// Remove a TableAnchor sentinel from the rope, undoing the effect
1298/// of `rope_insert_table_anchor`. Looks up the anchor's byte range
1299/// (always 3 bytes for the U+FFFC plus 1 byte of inter-marker `\n`
1300/// either before or after, depending on what's adjacent), removes
1301/// those 4 bytes from the rope, drops the entry, shifts trailing
1302/// entries by -4.
1303///
1304/// No-op if no TableAnchor for `table_id` exists.
1305pub fn rope_remove_table_anchor(store: &Store, table_id: EntityId) {
1306    let anchor_marker = OffsetMarker::TableAnchor(table_id);
1307    let (anchor_byte_start, anchor_idx, anchor_is_last, has_predecessor) = {
1308        let offsets = store.block_offsets.read();
1309        let Some((start, _end)) = offsets.range_of(anchor_marker) else {
1310            return;
1311        };
1312        let idx = offsets
1313            .entries
1314            .iter()
1315            .position(|(m, _)| *m == anchor_marker)
1316            .unwrap();
1317        let is_last = idx + 1 == offsets.entries.len();
1318        let has_pred = idx > 0;
1319        (start, idx, is_last, has_pred)
1320    };
1321
1322    // Symmetric to insert_table_anchor. The bytes to remove are:
1323    // - if anchor is last: [byte_start - 1 .. byte_start + 3) — the
1324    //   preceding `\n` + the 3-byte sentinel
1325    // - if anchor is the only entry: [byte_start .. byte_start + 3),
1326    //   the sentinel alone, with no boundary on either side
1327    // - otherwise: [byte_start .. byte_start + 4) — the sentinel
1328    //   + the following `\n`
1329    let (remove_start, remove_end) = match (anchor_is_last, has_predecessor) {
1330        (true, true) => (anchor_byte_start - 1, anchor_byte_start + 3),
1331        (true, false) => (anchor_byte_start, anchor_byte_start + 3),
1332        (false, _) => (anchor_byte_start, anchor_byte_start + 4),
1333    };
1334
1335    {
1336        let mut rope = store.rope.write();
1337        let char_start = rope.byte_to_char(remove_start as usize);
1338        let char_end = rope.byte_to_char(remove_end as usize);
1339        rope.remove(char_start..char_end);
1340    }
1341    {
1342        let mut offsets = store.block_offsets.write();
1343        offsets.remove_at(anchor_idx);
1344    }
1345    // Shift the entries past the removed range only, as `rope_remove_block`
1346    // does. An empty entry right before a last anchor starts where the cut
1347    // starts, at the boundary it loses; shifting from there moved it back
1348    // into the entry before it, or below zero.
1349    store
1350        .block_offsets
1351        .write()
1352        .shift_after(remove_end, -((remove_end - remove_start) as i32));
1353}
1354
1355/// Remove every one of `markers` (blocks and table anchors alike) from the
1356/// rope, each with one boundary `\n`, and drop their entries from the index:
1357/// the rope and index that [`rope_remove_block`] and
1358/// [`rope_remove_table_anchor`] leave, called for each marker, with one walk
1359/// of the index for all of them. What is left is the kept entries' contents
1360/// joined by boundaries, in their order. Markers not in the index are
1361/// skipped.
1362///
1363/// A deletion that removes entities has to take their text out of the rope
1364/// too, or the rope keeps text no block owns: the offset index then names
1365/// blocks that are gone, every position after them is off by their length,
1366/// and search and the addressable text still find the deleted words.
1367pub fn rope_remove_markers(store: &Store, markers: &[OffsetMarker]) {
1368    let mut offsets = store.block_offsets.write();
1369    let count = offsets.len();
1370    let mut dropped = vec![false; count];
1371    let mut any = false;
1372    for marker in markers {
1373        if let Some(position) = offsets.position_of(*marker) {
1374            dropped[position] = true;
1375            any = true;
1376        }
1377    }
1378    if !any {
1379        return;
1380    }
1381    let total = offsets.total_bytes();
1382    // One cut per run of consecutive dropped entries: their contents and the
1383    // boundary after each when a kept entry follows the run, or else the
1384    // boundary before the run and everything to the end of the rope.
1385    let mut cuts: Vec<(u32, u32)> = Vec::new();
1386    let mut position = 0;
1387    while position < count {
1388        if !dropped[position] {
1389            position += 1;
1390            continue;
1391        }
1392        let run_start = position;
1393        while position < count && dropped[position] {
1394            position += 1;
1395        }
1396        let first_byte = offsets.entries[run_start].1;
1397        let cut = if position < count {
1398            (first_byte, offsets.entries[position].1)
1399        } else if run_start > 0 {
1400            (first_byte.saturating_sub(1), total)
1401        } else {
1402            (0, total)
1403        };
1404        if cut.1 > cut.0 {
1405            cuts.push(cut);
1406        }
1407    }
1408    {
1409        // Last cut first, so the byte offsets of the others still hold.
1410        let mut rope = store.rope.write();
1411        for &(start, end) in cuts.iter().rev() {
1412            let char_start = rope.byte_to_char(start as usize);
1413            let char_end = rope.byte_to_char(end as usize);
1414            rope.remove(char_start..char_end);
1415        }
1416    }
1417    offsets.remove_entries(&dropped, &cuts);
1418}
1419
1420/// What an edit changed between two states of the rope, as positions: the
1421/// span of `before` from the first returned position to the second was
1422/// replaced by the span of `after` from the first to the third.
1423///
1424/// `from` is where the edit was asked to go in, and the span starts there or
1425/// after it when the text in front of `from` is unchanged: the ends are
1426/// matched first, so text that repeats the text in front of it counts as
1427/// going in at the earliest place from `from` on, then the starts. An
1428/// insertion goes in where it is asked, with two exceptions this finds: a
1429/// table pasted into a paragraph goes in after the paragraph, so what of the
1430/// paragraph followed the caret stays in front of it; and a table pasted into
1431/// a table cell fills the cells from the caret's own, replacing what they held
1432/// from the start of the caret's cell, which can lie before `from`. Counting
1433/// either as text put in at the caret moved every cursor standing in the rest
1434/// of that paragraph, or in those cells, to the wrong place.
1435pub fn changed_span(
1436    before: &ropey::Rope,
1437    after: &ropey::Rope,
1438    from: usize,
1439) -> (usize, usize, usize) {
1440    let (old_len, new_len) = (before.len_chars(), after.len_chars());
1441    let shorter = old_len.min(new_len);
1442    let from = from.min(shorter);
1443    // The common start, as far as `from`.
1444    let mut prefix = 0;
1445    {
1446        let mut old_chars = before.chars();
1447        let mut new_chars = after.chars();
1448        while prefix < from {
1449            match (old_chars.next(), new_chars.next()) {
1450                (Some(old), Some(new)) if old == new => prefix += 1,
1451                _ => break,
1452            }
1453        }
1454    }
1455    // The common end, reaching back no further than the common start.
1456    let mut suffix = 0;
1457    {
1458        let reach = shorter - prefix;
1459        let mut old_chars = before.chars_at(old_len);
1460        let mut new_chars = after.chars_at(new_len);
1461        while suffix < reach {
1462            match (old_chars.prev(), new_chars.prev()) {
1463                (Some(old), Some(new)) if old == new => suffix += 1,
1464                _ => break,
1465            }
1466        }
1467    }
1468    let (old_end, new_end) = (old_len - suffix, new_len - suffix);
1469    // When nothing in front of `from` changed, the rest of the common start,
1470    // from `from` on, up to what the end left.
1471    if prefix == from {
1472        let mut old_chars = before.chars_at(from);
1473        let mut new_chars = after.chars_at(from);
1474        while prefix < old_end.min(new_end) {
1475            match (old_chars.next(), new_chars.next()) {
1476                (Some(old), Some(new)) if old == new => prefix += 1,
1477                _ => break,
1478            }
1479        }
1480    }
1481    (prefix, old_end, new_end)
1482}
1483
1484/// Where a position belongs when it falls on a table's anchor: the `U+FFFC`
1485/// a table occupies in the rope, or the boundary after it. Those two
1486/// characters stand for the table as a whole and belong to no block.
1487/// `forward`, the position moves to the start of the table's first cell:
1488/// where a caret on the table types, and where a range starting on it
1489/// starts. Otherwise it moves back to the end of the entry before the table,
1490/// where a range ending on it ends. Any other position, and every position of
1491/// a document whose rope is not its position space, is returned as is.
1492///
1493/// Resolved as a block position, the anchor matched no block: the edit fell
1494/// back to the document's last block, so text typed or pasted there landed at
1495/// the end of the document and a deletion ending there ran to it.
1496///
1497/// Tables can follow each other with nothing between them in the rope: a table
1498/// nested at the start of a cell's frame has its anchor right after the anchor
1499/// of the table holding that cell. The walk goes past every anchor of such a
1500/// chain, so the result is never an anchor position itself: forward, it is the
1501/// first block after the chain (the innermost table's first cell); backward, it
1502/// is the end of the entry before the chain, or the document's start when the
1503/// chain opens it.
1504pub fn snap_off_table_anchor(store: &Store, position: i64, forward: bool) -> i64 {
1505    if !rope_positions_match_flow(store) {
1506        return position;
1507    }
1508    let rope = store.rope.read();
1509    let clamped = position.clamp(0, rope.len_chars() as i64);
1510    let byte = rope.char_to_byte(clamped as usize) as u32;
1511    let offsets = store.block_offsets.read();
1512    let Some(marker @ OffsetMarker::TableAnchor(_)) = offsets.marker_at_byte(byte) else {
1513        return position;
1514    };
1515    let Some(index) = offsets.position_of(marker) else {
1516        return position;
1517    };
1518    let is_anchor = |i: usize| {
1519        offsets
1520            .entries
1521            .get(i)
1522            .is_some_and(|(entry, _)| !entry.is_block())
1523    };
1524    let target = if forward {
1525        let mut next = index + 1;
1526        while is_anchor(next) {
1527            next += 1;
1528        }
1529        offsets
1530            .entries
1531            .get(next)
1532            .map_or_else(|| offsets.total_bytes(), |(_, start)| *start)
1533    } else {
1534        let mut first = index;
1535        while first > 0 && is_anchor(first - 1) {
1536            first -= 1;
1537        }
1538        // The boundary in front of the chain's first anchor closes the entry
1539        // before it: a caret there stands at that entry's end.
1540        offsets
1541            .entries
1542            .get(first)
1543            .map_or(0, |(_, start)| start.saturating_sub(1))
1544    };
1545    rope.byte_to_char(target as usize) as i64
1546}
1547
1548/// Where `table_id`'s anchor stands in the rope's position space, when the
1549/// rope is the document's position space and holds the anchor.
1550pub fn table_anchor_position(store: &Store, table_id: EntityId) -> Option<i64> {
1551    if !rope_positions_match_flow(store) {
1552        return None;
1553    }
1554    let (byte, _) = store
1555        .block_offsets
1556        .read()
1557        .range_of(OffsetMarker::TableAnchor(table_id))?;
1558    Some(store.rope.read().byte_to_char(byte as usize) as i64)
1559}
1560
1561/// Whether a table's anchor lies in the positions `[start, end)`: whether a
1562/// range over them covers the start of a table. `false` for a document whose
1563/// rope is not its position space.
1564pub fn range_covers_table_anchor(store: &Store, start: i64, end: i64) -> bool {
1565    if start >= end || !rope_positions_match_flow(store) {
1566        return false;
1567    }
1568    let rope = store.rope.read();
1569    let total = rope.len_chars() as i64;
1570    let byte_of = |position: i64| rope.char_to_byte(position.clamp(0, total) as usize) as u32;
1571    let (from, to) = (byte_of(start), byte_of(end));
1572    let offsets = store.block_offsets.read();
1573    // The entries are in byte order: only those starting inside the range are
1574    // looked at, which for a Backspace or a Delete is one or two.
1575    let first = offsets.entries.partition_point(|(_, byte)| *byte < from);
1576    offsets.entries[first..]
1577        .iter()
1578        .take_while(|(_, byte)| *byte < to)
1579        .any(|(marker, _)| !marker.is_block())
1580}
1581
1582/// Whether the range from `requested_start` (on or before a table's anchor, which the
1583/// range's `start` was moved past, see [`snap_off_table_anchor`]) to `end` holds a whole
1584/// table: the anchor and every block of its cells.
1585pub fn holds_a_table_from_its_anchor(
1586    store: &Store,
1587    requested_start: i64,
1588    start: i64,
1589    end: i64,
1590) -> bool {
1591    if requested_start >= start {
1592        return false;
1593    }
1594    let table_ids: Vec<EntityId> = store.tables.read().keys().copied().collect();
1595    table_ids.into_iter().any(|table_id| {
1596        let Some(anchor) = table_anchor_position(store, table_id) else {
1597            return false;
1598        };
1599        if anchor < requested_start || anchor >= start {
1600            return false;
1601        }
1602        let table_end = {
1603            let offsets = store.block_offsets.read();
1604            let rope = store.rope.read();
1605            table_block_ids(store, table_id)
1606                .iter()
1607                .filter_map(|block_id| offsets.range_with_successor(OffsetMarker::Block(*block_id)))
1608                .map(|(block_start, block_end, has_successor)| {
1609                    let text_end = if has_successor && block_end > block_start {
1610                        block_end - 1
1611                    } else {
1612                        block_end
1613                    };
1614                    rope.byte_to_char(text_end as usize) as i64
1615                })
1616                .max()
1617        };
1618        table_end.is_some_and(|table_end| end >= table_end)
1619    })
1620}
1621
1622/// Whether a range over the positions `[start, end)` holds a whole table, as a deletion of
1623/// it takes one: with its ends moved off any table's anchor (see [`snap_off_table_anchor`]),
1624/// it covers a table's anchor, or it starts on a table's anchor and reaches the end of that
1625/// table's last cell.
1626///
1627/// A copy reads a range as the deletion does. It took a table whole whenever the range held
1628/// the table's anchor, where the deletion takes it only then: a selection from a table's
1629/// anchor into its first cell, which the Right arrow and Shift+Right from the paragraph
1630/// before the table make, copied the whole table and cut the characters selected, and the
1631/// paste of the cut put the table in a second time.
1632pub fn range_holds_a_whole_table(store: &Store, start: i64, end: i64) -> bool {
1633    let snapped_start = snap_off_table_anchor(store, start, true);
1634    let snapped_end = snap_off_table_anchor(store, end, false);
1635    range_covers_table_anchor(store, snapped_start, snapped_end)
1636        || holds_a_table_from_its_anchor(store, start, snapped_start, snapped_end)
1637}
1638
1639/// Remove a registered block from the rope: drops its content bytes
1640/// plus one boundary `\n` (the one after, if the block has a
1641/// successor; the one before, if it's the last entry), removes the
1642/// entry from the index, and shifts trailing entries by the negative
1643/// byte delta.
1644///
1645/// No-op if `block_id` is not in the index. No-op for the special
1646/// case of a single-block document being asked to remove its sole
1647/// block (we'd produce an empty rope but the block itself is being
1648/// cascaded by the caller).
1649pub fn rope_remove_block(store: &Store, block_id: EntityId) {
1650    let block_marker = OffsetMarker::Block(block_id);
1651    let (block_start, block_end, idx, is_last, has_pred) = {
1652        let offsets = store.block_offsets.read();
1653        let Some((start, end)) = offsets.range_of(block_marker) else {
1654            return;
1655        };
1656        let idx = offsets
1657            .entries
1658            .iter()
1659            .position(|(m, _)| *m == block_marker)
1660            .unwrap();
1661        let is_last = idx + 1 == offsets.entries.len();
1662        let has_pred = idx > 0;
1663        (start, end, idx, is_last, has_pred)
1664    };
1665
1666    // Determine the byte range to delete:
1667    // - if there's a successor: [block_start..block_end) — the
1668    //   block's content INCLUDING its trailing boundary `\n`
1669    //   (which is the byte at block_end - 1)
1670    // - if last and has predecessor: [block_start - 1..block_end)
1671    //   — also delete the LEADING boundary `\n` that the previous
1672    //   entry placed before us
1673    // - if last and no predecessor (sole entry): just delete
1674    //   [block_start..block_end) (no boundary `\n` exists)
1675    let (remove_start, remove_end) = if is_last && has_pred {
1676        (block_start.saturating_sub(1), block_end)
1677    } else {
1678        (block_start, block_end)
1679    };
1680    if remove_end <= remove_start {
1681        // Drop the entry only; nothing to remove from the rope.
1682        store.block_offsets.write().remove_at(idx);
1683        return;
1684    }
1685    let deleted_bytes = remove_end - remove_start;
1686
1687    {
1688        let mut rope = store.rope.write();
1689        let char_start = rope.byte_to_char(remove_start as usize);
1690        let char_end = rope.byte_to_char(remove_end as usize);
1691        rope.remove(char_start..char_end);
1692    }
1693    store.block_offsets.write().remove_at(idx);
1694    // Shift entries STRICTLY PAST the removed range. Using `remove_end` as
1695    // the threshold (rather than `remove_start`) keeps an empty predecessor
1696    // whose byte_start equals `remove_start` (the leading boundary `\n` we
1697    // just deleted) in place — its content position is unchanged, only its
1698    // trailing boundary is gone. `total_bytes` decreases by `deleted_bytes`
1699    // regardless of threshold.
1700    store
1701        .block_offsets
1702        .write()
1703        .shift_after(remove_end, -(deleted_bytes as i32));
1704}
1705
1706/// Replace the entire content of a registered block in the rope with
1707/// `new_text`. Preserves the block's `byte_start` and its trailing
1708/// boundary `\n` (if any); subsequent entries shift by the net
1709/// length delta.
1710///
1711/// Used by use cases that compute a block's final content as a string
1712/// and want to push that content to the rope in one shot — e.g. the
1713/// block-splitting branches of `insert_html_at_position_uc` and
1714/// `insert_markdown_at_position_uc`, where each affected block
1715/// (head, tail, mid-replacement) gets a single new value.
1716///
1717/// No-op if `block_id` is not in the index.
1718pub fn rope_replace_block_content(store: &Store, block_id: EntityId, new_text: &str) {
1719    let (block_byte_start, content_bytes) = {
1720        let offsets = store.block_offsets.read();
1721        let Some((start, end, has_successor)) =
1722            offsets.range_with_successor(OffsetMarker::Block(block_id))
1723        else {
1724            return;
1725        };
1726        // `range_of` extends to the next entry's `byte_start` (or to
1727        // `total_bytes`). If there's a following entry, the byte at
1728        // `end - 1` is the inter-block boundary `\n` that belongs to
1729        // the boundary between this block and the next, not to this
1730        // block's content.
1731        //
1732        // Whether there is one is the index's to say. Asking whether the
1733        // range stops short of the rope's end got it wrong before an empty
1734        // last block, which starts at the rope's end: the boundary before it
1735        // was taken for content and replaced, and the two blocks were left
1736        // at one offset.
1737        let content_bytes = if has_successor && end > start {
1738            end - start - 1
1739        } else {
1740            end - start
1741        };
1742        (start, content_bytes)
1743    };
1744
1745    let new_bytes = new_text.len() as u32;
1746    if content_bytes == 0 && new_bytes == 0 {
1747        return;
1748    }
1749    let delta = new_bytes as i32 - content_bytes as i32;
1750
1751    // Splice [block_byte_start..block_byte_start + content_bytes)
1752    // with `new_text`.
1753    {
1754        let mut rope = store.rope.write();
1755        let char_start = rope.byte_to_char(block_byte_start as usize);
1756        if content_bytes > 0 {
1757            let char_end = rope.byte_to_char((block_byte_start + content_bytes) as usize);
1758            rope.remove(char_start..char_end);
1759        }
1760        if new_bytes > 0 {
1761            rope.insert(char_start, new_text);
1762        }
1763    }
1764
1765    if delta != 0 {
1766        // Shift entries that sit strictly past this block's start
1767        // (i.e. the trailing boundary and everything after).
1768        store
1769            .block_offsets
1770            .write()
1771            .shift_after(block_byte_start + 1, delta);
1772    }
1773}
1774
1775/// [`rope_replace_block_content`] with an empty text for each of
1776/// `block_ids` in turn: the rope and index that loop leaves, with one walk
1777/// of the index instead of one per block.
1778///
1779/// Each one-block clear shifts every entry after the block, so emptying the
1780/// cells of many tables one block at a time walked the index once per cell.
1781/// When the blocks come in index order, as a deletion meets them, each
1782/// block's content is exactly what it holds before any of them is cleared:
1783/// clearing an earlier block moves this one and the entry after it back by
1784/// the same amount. Out of that order the blocks are cleared one at a time,
1785/// as that loop does.
1786pub fn rope_clear_blocks(store: &Store, block_ids: &[EntityId]) {
1787    // `(index position, byte start, content bytes)` of each block with content.
1788    let mut cuts: Vec<(usize, u32, u32)> = Vec::with_capacity(block_ids.len());
1789    {
1790        let offsets = store.block_offsets.read();
1791        let mut previous: Option<usize> = None;
1792        let mut in_index_order = true;
1793        for &block_id in block_ids {
1794            let marker = OffsetMarker::Block(block_id);
1795            let (Some((start, end, has_successor)), Some(position)) = (
1796                offsets.range_with_successor(marker),
1797                offsets.position_of(marker),
1798            ) else {
1799                // Not in the index: the one-block clear leaves it alone too.
1800                continue;
1801            };
1802            if previous.is_some_and(|before| position <= before) {
1803                in_index_order = false;
1804                break;
1805            }
1806            previous = Some(position);
1807            // What `rope_replace_block_content` counts as the block's content.
1808            let content = if has_successor && end > start {
1809                end - start - 1
1810            } else {
1811                end - start
1812            };
1813            if content > 0 {
1814                cuts.push((position, start, content));
1815            }
1816        }
1817        if !in_index_order {
1818            drop(offsets);
1819            for &block_id in block_ids {
1820                rope_replace_block_content(store, block_id, "");
1821            }
1822            return;
1823        }
1824    }
1825    if cuts.is_empty() {
1826        return;
1827    }
1828    {
1829        // Last cut first, so the byte offsets of the others still hold.
1830        let mut rope = store.rope.write();
1831        for &(_, start, content) in cuts.iter().rev() {
1832            let char_start = rope.byte_to_char(start as usize);
1833            let char_end = rope.byte_to_char((start + content) as usize);
1834            rope.remove(char_start..char_end);
1835        }
1836    }
1837    let shifts: Vec<(usize, u32)> = cuts
1838        .iter()
1839        .map(|&(position, _, content)| (position, content))
1840        .collect();
1841    store.block_offsets.write().remove_bytes_after(&shifts);
1842}
1843
1844/// Delete bytes `[byte_start_in_block..byte_end_in_block)` from inside
1845/// the block identified by `block_id`. Shifts subsequent block offsets
1846/// by the deleted byte length. No-op for blocks not in the index.
1847pub fn rope_delete_in_block(
1848    store: &Store,
1849    block_id: EntityId,
1850    byte_start_in_block: u32,
1851    byte_end_in_block: u32,
1852) {
1853    if byte_end_in_block <= byte_start_in_block {
1854        return;
1855    }
1856    let deleted_bytes = byte_end_in_block - byte_start_in_block;
1857    let block_byte_start = {
1858        let offsets = store.block_offsets.read();
1859        let Some((start, _end)) = offsets.range_of_block(block_id) else {
1860            return;
1861        };
1862        start
1863    };
1864    let rope_byte_start = block_byte_start + byte_start_in_block;
1865    let rope_byte_end = block_byte_start + byte_end_in_block;
1866    {
1867        let mut rope = store.rope.write();
1868        let char_start = rope.byte_to_char(rope_byte_start as usize);
1869        let char_end = rope.byte_to_char(rope_byte_end as usize);
1870        rope.remove(char_start..char_end);
1871    }
1872    store
1873        .block_offsets
1874        .write()
1875        .shift_after(block_byte_start + 1, -(deleted_bytes as i32));
1876}
1877
1878/// Recompute `Frame.byte_range` for every frame in `store.frames`
1879/// based on current `block_offsets` and the frame tree structure.
1880/// Plan §1.6 invariant: each frame's byte_range is the (min_start,
1881/// max_end) over all its descendant blocks, sub-frames, and table
1882/// anchors+cells.
1883///
1884/// Call this after any mutation that affects rope byte positions.
1885/// O(F + B) where F = frames, B = blocks in the document.
1886pub fn recompute_all_frame_byte_ranges(store: &Store) {
1887    let frame_ids: Vec<EntityId> = {
1888        let frames = store.frames.read();
1889        frames.keys().copied().collect()
1890    };
1891    for fid in frame_ids {
1892        let new_range = compute_frame_byte_range_recursive(store, fid);
1893        let mut frames = store.frames.write();
1894        if let Some(f) = frames.get(&fid).cloned()
1895            && f.byte_range != new_range
1896        {
1897            let mut updated = f;
1898            updated.byte_range = new_range;
1899            frames.insert(fid, updated);
1900        }
1901    }
1902}
1903
1904fn compute_frame_byte_range_recursive(store: &Store, frame_id: EntityId) -> (u32, u32) {
1905    let mut bounds: Option<(u32, u32)> = None;
1906    walk_frame_bounds(store, frame_id, &mut bounds);
1907    bounds.unwrap_or((0, 0))
1908}
1909
1910fn walk_frame_bounds(store: &Store, frame_id: EntityId, bounds: &mut Option<(u32, u32)>) {
1911    fn merge(bounds: &mut Option<(u32, u32)>, s: u32, e: u32) {
1912        *bounds = Some(match *bounds {
1913            None => (s, e),
1914            Some((min, max)) => (min.min(s), max.max(e)),
1915        });
1916    }
1917
1918    let (blocks, child_order, table_id) = {
1919        let frames = store.frames.read();
1920        let Some(f) = frames.get(&frame_id) else {
1921            return;
1922        };
1923        (f.blocks.clone(), f.child_order.clone(), f.table)
1924    };
1925
1926    {
1927        let offsets = store.block_offsets.read();
1928        for bid in &blocks {
1929            if let Some((s, e)) = offsets.range_of_block(*bid) {
1930                merge(bounds, s, e);
1931            }
1932        }
1933        if let Some(tid) = table_id
1934            && let Some((s, e)) = offsets.range_of(OffsetMarker::TableAnchor(tid))
1935        {
1936            merge(bounds, s, e);
1937        }
1938    }
1939
1940    for entry in &child_order {
1941        if *entry < 0 {
1942            walk_frame_bounds(store, (-*entry) as EntityId, bounds);
1943        }
1944    }
1945
1946    if let Some(tid) = table_id {
1947        let cell_ids: Vec<EntityId> = {
1948            let tables = store.tables.read();
1949            tables
1950                .get(&tid)
1951                .map(|t| t.cells.clone())
1952                .unwrap_or_default()
1953        };
1954        for cell_id in &cell_ids {
1955            let cell_frame_id = {
1956                let cells = store.table_cells.read();
1957                cells.get(cell_id).and_then(|c| c.cell_frame)
1958            };
1959            if let Some(cfid) = cell_frame_id {
1960                walk_frame_bounds(store, cfid, bounds);
1961            }
1962        }
1963    }
1964}
1965
1966/// Replace `[char_start..char_end)` inside `block` with `replacement`, choosing what the
1967/// replacement wears where it overwrites formatted text — see [`ReplaceFormatPolicy`].
1968/// Mutates the block's format runs, image anchors, footnote references and the global rope
1969/// consistently in one step, and returns the updated `Block` (with a bumped `updated_at`) for
1970/// the caller to persist via its own unit of work.
1971///
1972/// The single shared implementation of "replace a char range inside one block" — originally
1973/// written for the project-wide replace path (`document_search::replace_core::apply_in_block`)
1974/// and moved here so `document_editing`'s interactive selection-replace path can offer the
1975/// same format-policy choice instead of being permanently pinned to
1976/// [`ReplaceFormatPolicy::InheritPreceding`]. See `ReplaceFormatPolicy`'s own doc comment for
1977/// the failure mode a second, independently-drifting copy of this would risk: a replace used
1978/// to be an unannounced delete + insert, which silently dropped formatting. It is
1979/// [`replace_in_blocks`] with one replacement, so the two cannot drift either.
1980///
1981/// Deliberately takes no unit of work — everything here is store-level (the block's text
1982/// lives in the rope, its formatting in `format_runs`, its images in `block_images`), so the
1983/// caller's UoW only has to persist the returned `Block`.
1984///
1985/// Returns `Err` rather than corrupting the block if the replace would violate the format-run
1986/// invariants (see [`FormatRunError`]) — the caller should refuse the edit and propagate this
1987/// rather than swallow it.
1988pub fn replace_in_block(
1989    store: &Store,
1990    block: &Block,
1991    char_start: i64,
1992    char_end: i64,
1993    replacement: &str,
1994    policy: ReplaceFormatPolicy,
1995) -> Result<Block, FormatRunError> {
1996    replace_in_blocks(
1997        store,
1998        &[BlockReplacement {
1999            block,
2000            char_start,
2001            char_end,
2002            replacement,
2003        }],
2004        policy,
2005    )?;
2006    let mut updated = block.clone();
2007    updated.updated_at = chrono::Utc::now();
2008    Ok(updated)
2009}
2010
2011/// One replacement [`replace_in_blocks`] makes: `[char_start..char_end)` of `block`'s text, in
2012/// the block's own positions (an image or a footnote reference counts one), replaced by
2013/// `replacement`.
2014#[derive(Debug, Clone, Copy)]
2015pub struct BlockReplacement<'a> {
2016    pub block: &'a Block,
2017    pub char_start: i64,
2018    pub char_end: i64,
2019    pub replacement: &'a str,
2020}
2021
2022/// Make every replacement of `edits` in one pass over the document: each block's format runs,
2023/// image anchors and footnote references, the rope, and one walk of the offset index for all
2024/// of them. The replacements of one block must not overlap; they may come in any order.
2025///
2026/// Replace All used to make its replacements one at a time, and each moved every index entry
2027/// after it: one match per paragraph cost a walk of the index per match, so replacing a word
2028/// throughout a long text grew with the square of its length and froze the editor for
2029/// seconds. The rope takes each splice in logarithmic time, from the last back, so the
2030/// offsets of the others still hold; the index then moves each entry once, by what the
2031/// replacements before it added or took.
2032///
2033/// Nothing is written until every block's new state is known to be well formed: an `Err`
2034/// leaves the store as it was.
2035pub fn replace_in_blocks(
2036    store: &Store,
2037    edits: &[BlockReplacement<'_>],
2038    policy: ReplaceFormatPolicy,
2039) -> Result<(), FormatRunError> {
2040    // The replacements of each block, blocks in the order they first appear.
2041    let mut order: Vec<&Block> = Vec::new();
2042    let mut of_block: HashMap<EntityId, Vec<&BlockReplacement<'_>>> = HashMap::new();
2043    for edit in edits {
2044        let group = of_block.entry(edit.block.id).or_default();
2045        if group.is_empty() {
2046            order.push(edit.block);
2047        }
2048        group.push(edit);
2049    }
2050
2051    struct NewState<'a> {
2052        block_id: EntityId,
2053        runs: Vec<FormatRun>,
2054        images: Vec<ImageAnchor>,
2055        notes: Option<Vec<FootnoteRefAnchor>>,
2056        /// `(byte_start, byte_end, replacement)` in the block's text, ascending.
2057        splices: Vec<(u32, u32, &'a str)>,
2058    }
2059    let mut states: Vec<NewState<'_>> = Vec::with_capacity(order.len());
2060    for block in order {
2061        let group = of_block.remove(&block.id).unwrap_or_default();
2062        let images_before = store
2063            .block_images
2064            .read()
2065            .get(&block.id)
2066            .cloned()
2067            .unwrap_or_default();
2068        let block_text = block_content_via_store(block, store);
2069        let mut splices: Vec<(u32, u32, &str)> = Vec::with_capacity(group.len());
2070        for edit in group {
2071            let byte_start = logical_offset_to_byte(&block_text, &images_before, edit.char_start);
2072            let byte_end = logical_offset_to_byte(&block_text, &images_before, edit.char_end);
2073            if byte_end < byte_start {
2074                // A range whose end comes before its start names no text to replace;
2075                // measuring it overflowed.
2076                return Err(FormatRunError::ReversedRange {
2077                    start: byte_start,
2078                    end: byte_end,
2079                });
2080            }
2081            splices.push((byte_start, byte_end, edit.replacement));
2082        }
2083        splices.sort_by_key(|(start, end, _)| (*start, *end));
2084        if let Some(pair) = splices.windows(2).find(|pair| pair[0].1 > pair[1].0) {
2085            // Two replacements of the same text: the second would splice bytes the first
2086            // already changed.
2087            return Err(FormatRunError::ReversedRange {
2088                start: pair[0].1,
2089                end: pair[1].0,
2090            });
2091        }
2092
2093        let mut runs = store
2094            .format_runs
2095            .read()
2096            .get(&block.id)
2097            .cloned()
2098            .unwrap_or_default();
2099        let mut images = images_before;
2100        let mut notes = store.block_footnote_refs.read().get(&block.id).cloned();
2101        let mut new_len = block_text.len();
2102        // From the last back, so each splice's offsets are still the text's own.
2103        for &(byte_start, byte_end, replacement) in splices.iter().rev() {
2104            let inserted = replacement.len() as u32;
2105            // Format runs under an explicit policy, and then CHECK the result rather than
2106            // assert it: `debug_assert_well_formed` is compiled out of release, so a
2107            // malformed run list produced in a shipped build went entirely undetected, and
2108            // autosave wrote it to the writer's file seconds later. A replace that would
2109            // corrupt a block's formatting fails loudly.
2110            shift_runs_for_replace(&mut runs, byte_start, byte_end, inserted, policy)?;
2111            shift_images_for_delete(&mut images, byte_start, byte_end);
2112            shift_images_for_insert(&mut images, byte_start, inserted);
2113            if let Some(notes) = notes.as_mut() {
2114                shift_footnote_refs_for_delete(notes, byte_start, byte_end);
2115                shift_footnote_refs_for_insert(notes, byte_start, inserted);
2116            }
2117            new_len = new_len - (byte_end - byte_start) as usize + replacement.len();
2118        }
2119        check_well_formed(&runs, new_len)?;
2120        states.push(NewState {
2121            block_id: block.id,
2122            runs,
2123            images,
2124            notes,
2125            splices,
2126        });
2127    }
2128
2129    // Every block's new state is sound: write it.
2130    let mut rope_splices: Vec<(u32, u32, &str)> = Vec::new();
2131    let mut shifts: Vec<(u32, i32)> = Vec::new();
2132    {
2133        let offsets = store.block_offsets.read();
2134        let mut runs_map = store.format_runs.write();
2135        let mut images_map = store.block_images.write();
2136        let mut notes_map = store.block_footnote_refs.write();
2137        for state in states {
2138            runs_map.insert(state.block_id, state.runs);
2139            images_map.insert(state.block_id, state.images);
2140            if let Some(notes) = state.notes {
2141                notes_map.insert(state.block_id, notes);
2142            }
2143            // A block the index does not hold has no text in the rope to change.
2144            let Some((block_start, _)) = offsets.range_of_block(state.block_id) else {
2145                continue;
2146            };
2147            let mut delta: i64 = 0;
2148            for (byte_start, byte_end, replacement) in state.splices {
2149                rope_splices.push((
2150                    block_start + byte_start,
2151                    block_start + byte_end,
2152                    replacement,
2153                ));
2154                delta += replacement.len() as i64 - (byte_end - byte_start) as i64;
2155            }
2156            // One byte past the block's start, so the block's own entry stays where it is.
2157            if delta != 0 {
2158                shifts.push((block_start + 1, delta as i32));
2159            }
2160        }
2161    }
2162    rope_splices.sort_by_key(|(start, end, _)| (*start, *end));
2163    {
2164        let mut rope = store.rope.write();
2165        for &(byte_start, byte_end, replacement) in rope_splices.iter().rev() {
2166            let char_start = rope.byte_to_char(byte_start as usize);
2167            if byte_end > byte_start {
2168                let char_end = rope.byte_to_char(byte_end as usize);
2169                rope.remove(char_start..char_end);
2170            }
2171            if !replacement.is_empty() {
2172                rope.insert(char_start, replacement);
2173            }
2174        }
2175    }
2176    shifts.sort_by_key(|(threshold, _)| *threshold);
2177    store.block_offsets.write().shift_after_each(&shifts);
2178    Ok(())
2179}
2180
2181#[cfg(test)]
2182mod tests {
2183    use super::*;
2184    use crate::database::block_offset_index::tests::ENTRIES_REWRITTEN;
2185    use crate::entities::{Document, Frame};
2186    use std::cell::Cell;
2187
2188    thread_local! {
2189        /// What `main_text_end` looked at on this thread (see [`super::looked_at`]).
2190        pub(super) static LOOKED_AT: Cell<usize> = const { Cell::new(0) };
2191    }
2192
2193    /// A text of `paragraphs` paragraphs followed by `notes` footnote bodies of one
2194    /// paragraph each, laid out as the loads lay one out: the bodies after the main text.
2195    /// Returns the store and where the main text ends.
2196    fn text_with_notes(paragraphs: u64, notes: u64) -> (Store, i64) {
2197        let store = Store::new();
2198        let main: EntityId = 1;
2199        let mut frames = vec![Frame {
2200            id: main,
2201            ..Frame::default()
2202        }];
2203        let mut end = 0;
2204        let mut next_block: EntityId = 1;
2205        for i in 0..paragraphs {
2206            if next_block > 1 {
2207                rope_insert_block_boundary(&store);
2208            }
2209            let text = format!("Paragraph {i}.");
2210            end = store.rope.read().len_chars() as i64 + text.chars().count() as i64;
2211            rope_append_block(&store, next_block, &text);
2212            frames[0].blocks.push(next_block);
2213            frames[0].child_order.push(next_block as i64);
2214            next_block += 1;
2215        }
2216        for i in 0..notes {
2217            rope_insert_block_boundary(&store);
2218            rope_append_block(&store, next_block, &format!("Note {i}."));
2219            frames.push(Frame {
2220                id: main + 1 + i,
2221                blocks: vec![next_block],
2222                child_order: vec![next_block as i64],
2223                footnote_label: Some(format!("n{i}")),
2224                ..Frame::default()
2225            });
2226            next_block += 1;
2227        }
2228        {
2229            let mut blocks = store.blocks.write();
2230            for id in 1..next_block {
2231                blocks.insert(
2232                    id,
2233                    Block {
2234                        id,
2235                        ..Block::default()
2236                    },
2237                );
2238            }
2239        }
2240        store.documents.write().insert(
2241            1,
2242            Document {
2243                id: 1,
2244                frames: frames.iter().map(|frame| frame.id).collect(),
2245                ..Document::default()
2246            },
2247        );
2248        let mut stored = store.frames.write();
2249        for frame in frames {
2250            stored.insert(frame.id, frame);
2251        }
2252        drop(stored);
2253        (store, end)
2254    }
2255
2256    /// Every forward move of a caret asks where the main text ends. It gathered every block
2257    /// of every note's body and walked the rope index back over them: a document of
2258    /// thousands of notes spent milliseconds on each arrow key. What it looks at must not
2259    /// grow with the notes, nor with the text.
2260    #[test]
2261    fn the_end_of_the_main_text_costs_the_same_however_many_notes_follow() {
2262        let mut looked = Vec::new();
2263        for (paragraphs, notes) in [(50, 100), (50, 2_000), (1_000, 2_000)] {
2264            let (store, end) = text_with_notes(paragraphs, notes);
2265            LOOKED_AT.with(|looked| looked.set(0));
2266            assert_eq!(
2267                main_text_end(&store),
2268                Some(end),
2269                "{paragraphs} paragraphs, {notes} notes"
2270            );
2271            looked.push(LOOKED_AT.with(Cell::get));
2272        }
2273        assert!(
2274            looked.windows(2).all(|pair| pair[0] == pair[1]),
2275            "the end of the main text looked at {looked:?} frames and entries for 100 and \
2276             2,000 notes, then 1,000 paragraphs"
2277        );
2278
2279        // Nothing follows a text without notes, and its end needs no stop.
2280        let (store, _) = text_with_notes(20, 0);
2281        assert_eq!(main_text_end(&store), None);
2282    }
2283
2284    /// A store of `blocks` blocks of a few characters each, the way the importers lay a
2285    /// document out: separated by a `\n` boundary. Returns the ids of its blocks, in order.
2286    fn blocks(blocks: u64) -> (Store, Vec<EntityId>) {
2287        let store = Store::new();
2288        let ids: Vec<EntityId> = (1..=blocks).collect();
2289        for &id in &ids {
2290            if id > 1 {
2291                rope_insert_block_boundary(&store);
2292            }
2293            rope_append_block(&store, id, &format!("cell {id}"));
2294        }
2295        (store, ids)
2296    }
2297
2298    /// Emptying the cells of every table a deletion covers clears a block per cell, and a
2299    /// one-block clear rewrites every index entry after the block: clearing a quarter of
2300    /// the blocks one at a time rewrites about an eighth of the index squared. Clearing
2301    /// them together must rewrite each entry once.
2302    #[test]
2303    fn clearing_blocks_together_walks_the_index_once() {
2304        const BLOCKS: u64 = 1_000;
2305        let (one_by_one, ids) = blocks(BLOCKS);
2306        let (together, _) = blocks(BLOCKS);
2307        let cleared: Vec<EntityId> = ids.iter().copied().step_by(4).collect();
2308
2309        ENTRIES_REWRITTEN.with(|rewritten| rewritten.set(0));
2310        for &id in &cleared {
2311            rope_replace_block_content(&one_by_one, id, "");
2312        }
2313        let block_by_block = ENTRIES_REWRITTEN.with(Cell::get);
2314
2315        ENTRIES_REWRITTEN.with(|rewritten| rewritten.set(0));
2316        rope_clear_blocks(&together, &cleared);
2317        let in_one_walk = ENTRIES_REWRITTEN.with(Cell::get);
2318
2319        assert_eq!(
2320            *together.rope.read(),
2321            *one_by_one.rope.read(),
2322            "the same text is left"
2323        );
2324        assert_eq!(
2325            *together.block_offsets.read(),
2326            *one_by_one.block_offsets.read(),
2327            "the same index is left"
2328        );
2329        assert!(
2330            block_by_block > 100 * BLOCKS as usize,
2331            "clearing block by block rewrote {block_by_block} entries"
2332        );
2333        assert_eq!(
2334            in_one_walk,
2335            BLOCKS as usize,
2336            "clearing {} blocks together rewrote {in_one_walk} index entries, where one walk \
2337             of the {BLOCKS} entries is enough",
2338            cleared.len()
2339        );
2340    }
2341
2342    /// Replace All replaced one match at a time, and each replacement moved every index
2343    /// entry after it: with a match in every paragraph, the whole index once per match. All
2344    /// of them together must move each entry once, and leave what one at a time leaves.
2345    #[test]
2346    fn replacing_in_many_blocks_walks_the_index_once() {
2347        const BLOCKS: u64 = 1_000;
2348        let (one_by_one, ids) = blocks(BLOCKS);
2349        let (together, _) = blocks(BLOCKS);
2350        let entities: Vec<Block> = ids
2351            .iter()
2352            .map(|&id| Block {
2353                id,
2354                ..Block::default()
2355            })
2356            .collect();
2357        // In each block, "cell {id}": "ce" becomes "k", and "!?" goes in at the end: each
2358        // block grows by one byte, so every entry after it moves.
2359        let edits: Vec<BlockReplacement<'_>> = entities
2360            .iter()
2361            .flat_map(|block| {
2362                let end = format!("cell {}", block.id).chars().count() as i64;
2363                [
2364                    BlockReplacement {
2365                        block,
2366                        char_start: 0,
2367                        char_end: 2,
2368                        replacement: "k",
2369                    },
2370                    BlockReplacement {
2371                        block,
2372                        char_start: end,
2373                        char_end: end,
2374                        replacement: "!?",
2375                    },
2376                ]
2377            })
2378            .collect();
2379
2380        ENTRIES_REWRITTEN.with(|rewritten| rewritten.set(0));
2381        for edit in edits.iter().rev() {
2382            replace_in_block(
2383                &one_by_one,
2384                edit.block,
2385                edit.char_start,
2386                edit.char_end,
2387                edit.replacement,
2388                ReplaceFormatPolicy::default(),
2389            )
2390            .unwrap();
2391        }
2392        let edit_by_edit = ENTRIES_REWRITTEN.with(Cell::get);
2393
2394        ENTRIES_REWRITTEN.with(|rewritten| rewritten.set(0));
2395        replace_in_blocks(&together, &edits, ReplaceFormatPolicy::default()).unwrap();
2396        let in_one_walk = ENTRIES_REWRITTEN.with(Cell::get);
2397
2398        assert_eq!(
2399            *together.rope.read(),
2400            *one_by_one.rope.read(),
2401            "the same text is left"
2402        );
2403        assert_eq!(
2404            *together.block_offsets.read(),
2405            *one_by_one.block_offsets.read(),
2406            "the same index is left"
2407        );
2408        assert!(
2409            together
2410                .rope
2411                .read()
2412                .to_string()
2413                .starts_with("kll 1!?\nkll 2!?\n")
2414        );
2415        assert!(
2416            edit_by_edit > 100 * BLOCKS as usize,
2417            "replacing edit by edit rewrote {edit_by_edit} entries"
2418        );
2419        assert!(
2420            in_one_walk <= BLOCKS as usize,
2421            "{} replacements together rewrote {in_one_walk} index entries, where one walk of \
2422             the {BLOCKS} entries is enough",
2423            edits.len()
2424        );
2425    }
2426
2427    /// Two replacements of the same characters cannot both be made: the whole call is
2428    /// refused and nothing is written.
2429    #[test]
2430    fn overlapping_replacements_change_nothing() {
2431        let store = blocks_holding(&["alpha", "beta"]);
2432        let block = Block {
2433            id: 1,
2434            ..Block::default()
2435        };
2436        let edits = [
2437            BlockReplacement {
2438                block: &block,
2439                char_start: 0,
2440                char_end: 3,
2441                replacement: "x",
2442            },
2443            BlockReplacement {
2444                block: &block,
2445                char_start: 2,
2446                char_end: 4,
2447                replacement: "y",
2448            },
2449        ];
2450        assert!(replace_in_blocks(&store, &edits, ReplaceFormatPolicy::default()).is_err());
2451        assert_eq!(store.rope.read().to_string(), "alpha\nbeta");
2452    }
2453
2454    /// A store holding one block per text, in order, separated by `\n` boundaries.
2455    fn blocks_holding(texts: &[&str]) -> Store {
2456        let store = Store::new();
2457        for (i, text) in texts.iter().enumerate() {
2458            if i > 0 {
2459                rope_insert_block_boundary(&store);
2460            }
2461            rope_append_block(&store, i as EntityId + 1, text);
2462        }
2463        store
2464    }
2465
2466    /// A block followed by an empty last block has a boundary after it, though its range
2467    /// runs to the end of the rope: the empty block starts there. Taking a range that ends
2468    /// at the rope's end for the last one counted that boundary as the block's content, so
2469    /// replacing or clearing the block took the boundary out and left the two blocks at one
2470    /// offset, where every later read of either sliced the wrong bytes.
2471    #[test]
2472    fn emptying_the_block_before_an_empty_last_block_keeps_the_boundary() {
2473        for together in [false, true] {
2474            let store = blocks_holding(&["text", ""]);
2475            if together {
2476                rope_clear_blocks(&store, &[1]);
2477            } else {
2478                rope_replace_block_content(&store, 1, "");
2479            }
2480            assert_eq!(store.rope.read().to_string(), "\n", "together: {together}");
2481            let offsets = store.block_offsets.read();
2482            assert_eq!(
2483                *offsets.entries,
2484                vec![(OffsetMarker::Block(1), 0), (OffsetMarker::Block(2), 1)],
2485                "together: {together}"
2486            );
2487            assert_eq!(offsets.total_bytes(), 1);
2488        }
2489    }
2490
2491    /// A table nested at the start of a cell puts its anchor right after the anchor of the
2492    /// table holding the cell, and a position on either stands for the tables, not for a
2493    /// block. Moving one entry off the anchor landed on the other anchor: forward, a caret
2494    /// meant for the first cell stood on the inner table's anchor, and backward, a range end
2495    /// meant to stop before the tables stood on the outer anchor's boundary. Resolved as
2496    /// block positions, both fell back to the document's last block, where a deletion ran to
2497    /// and a paste landed.
2498    #[test]
2499    fn a_position_on_a_chain_of_anchors_snaps_past_the_whole_chain() {
2500        let with_anchors = |texts: &[&str], anchors: &[usize]| {
2501            let store = blocks_holding(texts);
2502            {
2503                let mut offsets = store.block_offsets.write();
2504                let mut entries = (*offsets.entries).clone();
2505                for (i, entry) in entries.iter_mut().enumerate() {
2506                    if anchors.contains(&i) {
2507                        entry.0 = OffsetMarker::TableAnchor(100 + i as EntityId);
2508                    }
2509                }
2510                offsets.entries = std::sync::Arc::new(entries);
2511                offsets.rebuild_marker_index();
2512            }
2513            {
2514                // The rope is the position space only when it mirrors every block.
2515                let mut blocks = store.blocks.write();
2516                for id in 1..=texts.len() as EntityId {
2517                    if !anchors.contains(&(id as usize - 1)) {
2518                        blocks.insert(
2519                            id,
2520                            Block {
2521                                id,
2522                                ..Block::default()
2523                            },
2524                        );
2525                    }
2526                }
2527            }
2528            store
2529        };
2530
2531        // "Before." 0..7, its boundary 7, the outer anchor 8 and its boundary 9, the inner
2532        // anchor 10 and its boundary 11, then the inner table's cell at 12.
2533        let store = with_anchors(
2534            &[
2535                "Before.", "\u{FFFC}", "\u{FFFC}", "inner", "outer", "After.",
2536            ],
2537            &[1, 2],
2538        );
2539        for on_chain in 8..=11 {
2540            assert_eq!(
2541                snap_off_table_anchor(&store, on_chain, true),
2542                12,
2543                "from {on_chain}"
2544            );
2545            assert_eq!(
2546                snap_off_table_anchor(&store, on_chain, false),
2547                7,
2548                "from {on_chain}"
2549            );
2550        }
2551        for off_chain in [0, 6, 7, 12, 17] {
2552            assert_eq!(snap_off_table_anchor(&store, off_chain, true), off_chain);
2553            assert_eq!(snap_off_table_anchor(&store, off_chain, false), off_chain);
2554        }
2555
2556        // A chain opening the document: back to its start, forward to the first cell.
2557        let store = with_anchors(&["\u{FFFC}", "\u{FFFC}", "cell"], &[0, 1]);
2558        for on_chain in 0..=3 {
2559            assert_eq!(
2560                snap_off_table_anchor(&store, on_chain, true),
2561                4,
2562                "from {on_chain}"
2563            );
2564            assert_eq!(
2565                snap_off_table_anchor(&store, on_chain, false),
2566                0,
2567                "from {on_chain}"
2568            );
2569        }
2570    }
2571
2572    /// Whether a range covers a table's anchor, for ranges around, onto and past one.
2573    #[test]
2574    fn a_range_covers_a_table_when_it_holds_its_anchor() {
2575        let store = blocks_holding(&["Before.", "\u{FFFC}", "cell", "After."]);
2576        {
2577            let mut offsets = store.block_offsets.write();
2578            let mut entries = (*offsets.entries).clone();
2579            entries[1].0 = OffsetMarker::TableAnchor(40);
2580            offsets.entries = std::sync::Arc::new(entries);
2581            offsets.rebuild_marker_index();
2582        }
2583        {
2584            let mut blocks = store.blocks.write();
2585            for id in [1, 3, 4] {
2586                blocks.insert(
2587                    id,
2588                    Block {
2589                        id,
2590                        ..Block::default()
2591                    },
2592                );
2593            }
2594        }
2595        // The anchor is at 8, the cell at 10..14, "After." from 15.
2596        for (start, end, covers) in [
2597            (0, 8, false),
2598            (0, 9, true),
2599            (7, 9, true),
2600            (8, 9, true),
2601            (9, 20, false),
2602            (7, 15, true),
2603            (14, 15, false),
2604            (9, 9, false),
2605        ] {
2606            assert_eq!(
2607                range_covers_table_anchor(&store, start, end),
2608                covers,
2609                "{start}..{end}"
2610            );
2611        }
2612    }
2613
2614    /// A rope laid out from `entries`, `None` standing for a table's anchor: the entries'
2615    /// contents joined by boundaries. Entry `i` is `Block(i + 1)`, or `TableAnchor(i + 1)`.
2616    fn layout_of(entries: &[Option<&str>]) -> (Store, Vec<OffsetMarker>) {
2617        let texts: Vec<&str> = entries
2618            .iter()
2619            .map(|entry| entry.unwrap_or("\u{FFFC}"))
2620            .collect();
2621        let store = blocks_holding(&texts);
2622        let markers: Vec<OffsetMarker> = entries
2623            .iter()
2624            .enumerate()
2625            .map(|(i, entry)| match entry {
2626                Some(_) => OffsetMarker::Block(i as EntityId + 1),
2627                None => OffsetMarker::TableAnchor(i as EntityId + 1),
2628            })
2629            .collect();
2630        {
2631            let mut offsets = store.block_offsets.write();
2632            let mut indexed = (*offsets.entries).clone();
2633            for (slot, marker) in indexed.iter_mut().zip(&markers) {
2634                slot.0 = *marker;
2635            }
2636            offsets.entries = std::sync::Arc::new(indexed);
2637            offsets.rebuild_marker_index();
2638        }
2639        (store, markers)
2640    }
2641
2642    /// Removing a set of entries leaves the kept entries' contents joined by boundaries, each
2643    /// entry indexed where it starts in that text, whether they are removed in one pass or
2644    /// one at a time, for every subset of each layout. The layouts hold empty blocks next to
2645    /// table anchors: an empty block right before a last anchor starts where the anchor's
2646    /// cut starts, which moved it back into the entry before it, or below zero; and a table
2647    /// alone had four bytes cut from a rope of three.
2648    #[test]
2649    fn removing_markers_together_matches_removing_them_one_at_a_time() {
2650        let layouts: [&[Option<&str>]; 7] = [
2651            &[
2652                Some("one"),
2653                Some(""),
2654                Some("three"),
2655                None,
2656                Some("five"),
2657                Some(""),
2658            ],
2659            &[Some("Hello"), Some(""), None],
2660            &[Some(""), None],
2661            &[None],
2662            &[None, Some("")],
2663            &[Some("x"), None, Some(""), None, Some("")],
2664            &[Some(""), None, Some("a"), Some("b"), None],
2665        ];
2666        for entries in layouts {
2667            for subset in 1u32..(1 << entries.len()) {
2668                let (_, markers) = layout_of(entries);
2669                let chosen: Vec<OffsetMarker> = markers
2670                    .iter()
2671                    .enumerate()
2672                    .filter(|(i, _)| subset & (1 << i) != 0)
2673                    .map(|(_, marker)| *marker)
2674                    .collect();
2675                // What is left: the kept contents joined by boundaries.
2676                let mut expected_text = String::new();
2677                let mut expected_entries: Vec<(OffsetMarker, u32)> = Vec::new();
2678                for (entry, marker) in entries.iter().zip(&markers) {
2679                    if chosen.contains(marker) {
2680                        continue;
2681                    }
2682                    if !expected_entries.is_empty() {
2683                        expected_text.push('\n');
2684                    }
2685                    expected_entries.push((*marker, expected_text.len() as u32));
2686                    expected_text.push_str(entry.unwrap_or("\u{FFFC}"));
2687                }
2688
2689                let (one_by_one, _) = layout_of(entries);
2690                for marker in &chosen {
2691                    match marker {
2692                        OffsetMarker::Block(id) => rope_remove_block(&one_by_one, *id),
2693                        OffsetMarker::TableAnchor(id) => rope_remove_table_anchor(&one_by_one, *id),
2694                    }
2695                }
2696                let (together, _) = layout_of(entries);
2697                rope_remove_markers(&together, &chosen);
2698                for (how, store) in [("one by one", &one_by_one), ("together", &together)] {
2699                    assert_eq!(
2700                        store.rope.read().to_string(),
2701                        expected_text,
2702                        "{how}, removing {chosen:?} from {entries:?}"
2703                    );
2704                    let offsets = store.block_offsets.read();
2705                    assert_eq!(
2706                        *offsets.entries, expected_entries,
2707                        "{how}, removing {chosen:?} from {entries:?}"
2708                    );
2709                    assert_eq!(
2710                        offsets.total_bytes() as usize,
2711                        expected_text.len(),
2712                        "{how}, removing {chosen:?} from {entries:?}"
2713                    );
2714                }
2715            }
2716        }
2717    }
2718
2719    /// The span an edit changed, from the two ropes around it and where it was asked to go
2720    /// in: at the caret, at the earliest place from the caret on when the new text repeats
2721    /// the text in front of it, after the rest of the paragraph when the edit put its text
2722    /// there, and from before the caret when the edit replaced text there.
2723    #[test]
2724    fn a_changed_span_is_found_where_the_edit_went() {
2725        let span = |before: &str, after: &str, from: usize| {
2726            changed_span(
2727                &ropey::Rope::from_str(before),
2728                &ropey::Rope::from_str(after),
2729                from,
2730            )
2731        };
2732        // Typed at the caret.
2733        assert_eq!(span("Hello world", "Hello big world", 6), (6, 6, 10));
2734        // The same word typed in front of itself: at the caret, not after the old word.
2735        assert_eq!(span("X inserted Y", "X insertedinserted Y", 2), (2, 2, 10));
2736        // A table pasted at 3 goes in after the paragraph: from its end, a boundary and the
2737        // table, in front of the paragraph's own boundary.
2738        assert_eq!(
2739            span("one two\nthree", "one two\n\u{FFFC}\nx\ny\nthree", 3),
2740            (7, 7, 13)
2741        );
2742        // Cells filled from the start of the caret's cell, which is before the caret.
2743        assert_eq!(span("a\nbcd\ne", "a\nx\ny\ne", 4), (2, 5, 5));
2744        // Nothing changed: an empty span at the caret.
2745        assert_eq!(span("same", "same", 2), (2, 2, 2));
2746    }
2747}