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 `run` into the rope right in front of the entry `before`, in order: whatever
775/// preceded `before` precedes the run, and `before` follows it. Returns `false`, leaving the
776/// rope alone, when `before` is not in the index.
777///
778/// This is how a paste opening with a table at the start of a paragraph lays the table out
779/// in front of that paragraph rather than after it (see `insert_fragment_uc`).
780pub fn rope_insert_run_before(
781    store: &Store,
782    before: OffsetMarker,
783    run: &[(OffsetMarker, &str)],
784) -> bool {
785    let previous = {
786        let offsets = store.block_offsets.read();
787        let Some(position) = offsets.position_of(before) else {
788            return false;
789        };
790        position
791            .checked_sub(1)
792            .and_then(|at| offsets.entries.get(at))
793            .map(|(marker, _)| *marker)
794    };
795    if let Some(previous) = previous {
796        return rope_insert_run_after(store, previous, run);
797    }
798    if run.is_empty() {
799        return true;
800    }
801    // `before` opens the rope: each marker of the run is its text followed by a boundary,
802    // and everything already there moves up by the whole run.
803    let mut inserted = String::new();
804    let mut entries = Vec::with_capacity(run.len());
805    for (marker, text) in run {
806        entries.push((*marker, inserted.len() as u32));
807        inserted.push_str(text);
808        inserted.push('\n');
809    }
810    store.rope.write().insert(0, &inserted);
811    let mut offsets = store.block_offsets.write();
812    offsets.shift_after(0, inserted.len() as i32);
813    offsets.insert_run_at(0, &entries);
814    true
815}
816
817/// Insert a run of new markers at `byte_pos`, each a `\n` boundary
818/// followed by its text, and register them in the offset index at
819/// `vec_pos`, `vec_pos + 1`, …. Every entry strictly past `byte_pos`
820/// shifts by the whole run. Returns the byte right after the run.
821fn rope_insert_marker_run<'a>(
822    store: &Store,
823    byte_pos: u32,
824    vec_pos: usize,
825    markers: impl IntoIterator<Item = (OffsetMarker, &'a str)>,
826) -> u32 {
827    let mut inserted = String::new();
828    let mut run = Vec::new();
829    for (marker, text) in markers {
830        inserted.push('\n');
831        run.push((marker, byte_pos + inserted.len() as u32));
832        inserted.push_str(text);
833    }
834    if run.is_empty() {
835        return byte_pos;
836    }
837    {
838        let mut rope = store.rope.write();
839        let char_idx = rope.byte_to_char(byte_pos as usize);
840        rope.insert(char_idx, &inserted);
841    }
842    let mut offsets = store.block_offsets.write();
843    offsets.shift_after(byte_pos + 1, inserted.len() as i32);
844    offsets.insert_run_at(vec_pos, &run);
845    byte_pos + inserted.len() as u32
846}
847
848/// Mirror a table's new, empty cell blocks into the rope where reading order
849/// puts them: each after the block before it in the table's row-major order,
850/// the first cell's after the table's anchor. `new_blocks` are blocks the
851/// table's cells list but the index does not hold yet; the others stay
852/// where they are. Consecutive new blocks go in as one run.
853///
854/// The row, column and cell-split edits used to put their new cells at the
855/// end of the table's enclosing top-level frame, which is where they belong
856/// only when the table is the last thing in it: after any table followed by
857/// text, the new cells sat after that text in the rope, out of flow order,
858/// and every position past the table was wrong.
859pub fn rope_place_new_cell_blocks(store: &Store, table_id: EntityId, new_blocks: &[EntityId]) {
860    if new_blocks.is_empty() {
861        return;
862    }
863    let new: std::collections::HashSet<EntityId> = new_blocks.iter().copied().collect();
864    // Everything the table holds, in reading order: its anchor, then its
865    // cells by row and column, each cell's blocks and whatever is nested in
866    // it in its frame's order.
867    let mut ordered: Vec<OffsetMarker> = Vec::new();
868    {
869        let tables = store.tables.read();
870        let cells = store.table_cells.read();
871        let frames = store.frames.read();
872        table_reading_order(table_id, &tables, &cells, &frames, &mut ordered);
873    }
874    let mut after = OffsetMarker::TableAnchor(table_id);
875    let mut run: Vec<(OffsetMarker, &str)> = Vec::new();
876    for marker in ordered {
877        if matches!(marker, OffsetMarker::Block(id) if new.contains(&id)) {
878            run.push((marker, ""));
879            continue;
880        }
881        if !run.is_empty() {
882            rope_insert_run_after(store, after, &run);
883            run.clear();
884        }
885        after = marker;
886    }
887    if !run.is_empty() {
888        rope_insert_run_after(store, after, &run);
889    }
890}
891
892/// Put `table_id`'s anchor and the blocks of its cells back in reading order in
893/// the rope, when an edit of the table's rows left them in another.
894///
895/// Removing the first row of a cell that spans two rows keeps the cell at its
896/// row, one row shorter, and moves the row below up beside it: a moved-up cell
897/// of an earlier column now comes before the spanning cell in reading order,
898/// while the rope still held the spanning cell's text first. Every position in
899/// the table then addressed another cell than the one the frames put there, and
900/// the text a caret walked read the cells in another order than the save.
901///
902/// The table's entries are rewritten where they stand, as one span: same texts,
903/// same boundaries, same length, so nothing outside the table moves. Leaves the
904/// rope alone when its entries are already in reading order, or are not all in
905/// the index and next to each other.
906pub fn rope_restore_table_reading_order(store: &Store, table_id: EntityId) {
907    let mut ordered: Vec<OffsetMarker> = Vec::new();
908    {
909        let tables = store.tables.read();
910        let cells = store.table_cells.read();
911        let frames = store.frames.read();
912        table_reading_order(table_id, &tables, &cells, &frames, &mut ordered);
913    }
914    let mut offsets = store.block_offsets.write();
915    let positions: Option<Vec<usize>> = ordered
916        .iter()
917        .map(|marker| offsets.position_of(*marker))
918        .collect();
919    let Some(positions) = positions else {
920        return;
921    };
922    if positions.windows(2).all(|pair| pair[0] < pair[1]) {
923        return;
924    }
925    let Some(first) = positions.iter().min().copied() else {
926        return;
927    };
928    let last = first + positions.len() - 1;
929    let mut sorted = positions.clone();
930    sorted.sort_unstable();
931    if sorted
932        .iter()
933        .enumerate()
934        .any(|(i, position)| *position != first + i)
935    {
936        return;
937    }
938    let total = offsets.total_bytes();
939    let entries = offsets.entries.clone();
940    // Where each entry's text ends: at the boundary before the next entry, or at
941    // the end of the rope for the last one.
942    let text_end = |index: usize| -> u32 {
943        entries
944            .get(index + 1)
945            .map_or(total, |(_, next)| next.saturating_sub(1))
946    };
947    let span_start = entries[first].1;
948    let span_end = text_end(last);
949    let mut rope = store.rope.write();
950    let char_of = |byte: u32| rope.byte_to_char(byte as usize);
951    let text_of = |index: usize| -> String {
952        let (start, end) = (entries[index].1, text_end(index));
953        rope.slice(char_of(start)..char_of(end)).to_string()
954    };
955    let mut rebuilt = String::with_capacity((span_end - span_start) as usize);
956    let mut run: Vec<(OffsetMarker, u32)> = Vec::with_capacity(positions.len());
957    for (marker, position) in ordered.iter().zip(&positions) {
958        if !run.is_empty() {
959            rebuilt.push('\n');
960        }
961        run.push((*marker, span_start + rebuilt.len() as u32));
962        rebuilt.push_str(&text_of(*position));
963    }
964    if rebuilt.len() as u32 != span_end - span_start {
965        return;
966    }
967    let (char_start, char_end) = (char_of(span_start), char_of(span_end));
968    rope.remove(char_start..char_end);
969    rope.insert(char_start, &rebuilt);
970    offsets.reorder_run(first, &run);
971}
972
973/// Append `table_id`'s anchor and everything in its cells to `out`, in
974/// reading order.
975fn table_reading_order(
976    table_id: EntityId,
977    tables: &im::HashMap<EntityId, crate::entities::Table>,
978    cells: &im::HashMap<EntityId, crate::entities::TableCell>,
979    frames: &im::HashMap<EntityId, crate::entities::Frame>,
980    out: &mut Vec<OffsetMarker>,
981) {
982    out.push(OffsetMarker::TableAnchor(table_id));
983    let Some(table) = tables.get(&table_id) else {
984        return;
985    };
986    let mut table_cells: Vec<_> = table.cells.iter().filter_map(|id| cells.get(id)).collect();
987    table_cells.sort_by_key(|cell| (cell.row, cell.column));
988    for cell in table_cells {
989        if let Some(frame) = cell.cell_frame {
990            frame_reading_order(frame, tables, cells, frames, out);
991        }
992    }
993}
994
995/// Every block `table_id` holds, nested ones included, in reading order.
996pub fn table_block_ids(store: &Store, table_id: EntityId) -> Vec<EntityId> {
997    let mut ordered: Vec<OffsetMarker> = Vec::new();
998    {
999        let tables = store.tables.read();
1000        let cells = store.table_cells.read();
1001        let frames = store.frames.read();
1002        table_reading_order(table_id, &tables, &cells, &frames, &mut ordered);
1003    }
1004    ordered
1005        .into_iter()
1006        .filter_map(OffsetMarker::as_block)
1007        .collect()
1008}
1009
1010/// Insert `run` into the rope right after everything `table_id` holds: its
1011/// anchor, its cells and whatever is nested in them, in reading order. See
1012/// [`rope_insert_run_after`]. Returns `false`, leaving the rope alone, when the
1013/// table's last entry is not in the index.
1014pub fn rope_insert_run_after_table(
1015    store: &Store,
1016    table_id: EntityId,
1017    run: &[(OffsetMarker, &str)],
1018) -> bool {
1019    let mut ordered: Vec<OffsetMarker> = Vec::new();
1020    {
1021        let tables = store.tables.read();
1022        let cells = store.table_cells.read();
1023        let frames = store.frames.read();
1024        table_reading_order(table_id, &tables, &cells, &frames, &mut ordered);
1025    }
1026    match ordered.last() {
1027        Some(last) => rope_insert_run_after(store, *last, run),
1028        None => false,
1029    }
1030}
1031
1032/// The outermost table whose cells hold the frame `frame_id`, at any depth:
1033/// the table, its anchor frame, and the frame whose `child_order` lists that
1034/// anchor frame. `None` when `frame_id` is in no table cell.
1035///
1036/// Read from the tables' cell lists and the frames' `child_order`, never from
1037/// `Frame.parent_frame`: a table pasted into the document has cell frames with
1038/// no parent, so a walk up the parents took a caret in such a cell for one
1039/// outside any table.
1040pub fn outermost_table_around(
1041    store: &Store,
1042    frame_id: EntityId,
1043) -> Option<(EntityId, EntityId, EntityId)> {
1044    let tables = store.tables.read();
1045    let cells = store.table_cells.read();
1046    let frames = store.frames.read();
1047    let table_of_cell_frame = |frame: EntityId| {
1048        let (cell_id, _) = cells
1049            .iter()
1050            .find(|(_, cell)| cell.cell_frame == Some(frame))?;
1051        tables
1052            .iter()
1053            .find(|(_, table)| table.cells.contains(cell_id))
1054            .map(|(table_id, _)| *table_id)
1055    };
1056    let frame_listing = |frame: EntityId| {
1057        let entry = -(frame as i64);
1058        frames
1059            .iter()
1060            .find(|(_, candidate)| candidate.child_order.contains(&entry))
1061            .map(|(id, _)| *id)
1062    };
1063    let mut found = None;
1064    let mut current = frame_id;
1065    // Each step moves one frame out; a well-formed tree ends at a root in at
1066    // most as many steps as there are frames.
1067    for _ in 0..=frames.len() {
1068        let next = match table_of_cell_frame(current) {
1069            Some(table_id) => {
1070                let Some((anchor_id, _)) = frames
1071                    .iter()
1072                    .find(|(_, frame)| frame.table == Some(table_id))
1073                else {
1074                    break;
1075                };
1076                let Some(parent) = frame_listing(*anchor_id) else {
1077                    break;
1078                };
1079                found = Some((table_id, *anchor_id, parent));
1080                parent
1081            }
1082            None => match frame_listing(current) {
1083                Some(parent) => parent,
1084                None => break,
1085            },
1086        };
1087        current = next;
1088    }
1089    found
1090}
1091
1092/// Append a frame's blocks and everything nested in it to `out`, in the
1093/// frame's `child_order`.
1094fn frame_reading_order(
1095    frame_id: EntityId,
1096    tables: &im::HashMap<EntityId, crate::entities::Table>,
1097    cells: &im::HashMap<EntityId, crate::entities::TableCell>,
1098    frames: &im::HashMap<EntityId, crate::entities::Frame>,
1099    out: &mut Vec<OffsetMarker>,
1100) {
1101    let Some(frame) = frames.get(&frame_id) else {
1102        return;
1103    };
1104    for entry in &frame.child_order {
1105        if *entry > 0 {
1106            out.push(OffsetMarker::Block(*entry as EntityId));
1107        } else if *entry < 0 {
1108            let sub_id = (-*entry) as EntityId;
1109            match frames.get(&sub_id).and_then(|sub| sub.table) {
1110                Some(nested) => table_reading_order(nested, tables, cells, frames, out),
1111                None => frame_reading_order(sub_id, tables, cells, frames, out),
1112            }
1113        }
1114    }
1115}
1116
1117/// Merge `start_block` and `end_block` by deleting the rope range
1118/// `[start_block.start + byte_so .. end_block.start + byte_eo)` — i.e.
1119/// the suffix of `start_block`, every block between (and their
1120/// boundary newlines), and the prefix of `end_block`. Removes the
1121/// index entries for every block strictly between `start_block` and
1122/// `end_block` (inclusive of `end_block` itself); the surviving
1123/// content lives in `start_block`. Shifts any blocks past `end_block`
1124/// by the negative delta.
1125///
1126/// No-op if `start_block` is not in the index. Skipped for any
1127/// intermediate block id whose range is missing from the index (e.g.
1128/// table cells until step 5.5e).
1129pub fn rope_merge_block_range(
1130    store: &Store,
1131    start_block_id: EntityId,
1132    byte_so_in_start: u32,
1133    end_block_id: EntityId,
1134    byte_eo_in_end: u32,
1135) {
1136    let start_marker = OffsetMarker::Block(start_block_id);
1137    let end_marker = OffsetMarker::Block(end_block_id);
1138    let (start_block_byte, end_block_byte, start_idx, end_idx) = {
1139        let offsets = store.block_offsets.read();
1140        let Some((sb, _)) = offsets.range_of(start_marker) else {
1141            return;
1142        };
1143        let Some((eb, _)) = offsets.range_of(end_marker) else {
1144            return;
1145        };
1146        let si = offsets
1147            .entries
1148            .iter()
1149            .position(|(m, _)| *m == start_marker)
1150            .unwrap();
1151        let ei = offsets
1152            .entries
1153            .iter()
1154            .position(|(m, _)| *m == end_marker)
1155            .unwrap();
1156        (sb, eb, si, ei)
1157    };
1158    if end_idx <= start_idx {
1159        return;
1160    }
1161
1162    let delete_start = start_block_byte + byte_so_in_start;
1163    let delete_end = end_block_byte + byte_eo_in_end;
1164    if delete_end <= delete_start {
1165        return;
1166    }
1167    let deleted_bytes = delete_end - delete_start;
1168
1169    // 1. Remove the rope range.
1170    {
1171        let mut rope = store.rope.write();
1172        let char_start = rope.byte_to_char(delete_start as usize);
1173        let char_end = rope.byte_to_char(delete_end as usize);
1174        rope.remove(char_start..char_end);
1175    }
1176
1177    // 2. Remove block_offsets entries for [start_idx+1 ..= end_idx].
1178    {
1179        let mut offsets = store.block_offsets.write();
1180        offsets.drain_inclusive(start_idx + 1, end_idx);
1181    }
1182
1183    // 3. Shift any remaining entries past the deletion by -deleted_bytes.
1184    //    Threshold > delete_start because start_block's own entry
1185    //    sits at delete_start - byte_so_in_start (≤ delete_start)
1186    //    and must not move.
1187    store
1188        .block_offsets
1189        .write()
1190        .shift_after(delete_start + 1, -(deleted_bytes as i32));
1191}
1192
1193/// Insert a U+FFFC OBJECT REPLACEMENT CHARACTER sentinel in the rope
1194/// at the table-anchor position, registering a `TableAnchor(table_id)`
1195/// marker in the offset index (plan §1.6).
1196///
1197/// `target_block_id` is the block in the parent frame that the table
1198/// is adjacent to. `after` controls whether the table goes BEFORE
1199/// (`after = false`) or AFTER the target block.
1200///
1201/// The 3-byte sentinel is paired with an inter-marker `\n`:
1202/// - `after = false`: inserts `\u{FFFC}\n` at `target.byte_start`
1203/// - `after = true`, target is NOT the last entry: inserts
1204///   `\u{FFFC}\n` at `target.byte_end` (between target's trailing
1205///   `\n` and the next entry)
1206/// - `after = true`, target IS the last entry: inserts `\n\u{FFFC}`
1207///   at `target.byte_end` (rope now ends with the sentinel)
1208///
1209/// NOTE: cell-internal content is not yet routed through the rope —
1210/// the rope reflects table *presence* (3-byte sentinel) only.
1211/// Routing cell content is deferred to plan §1.6's `Frame.byte_range`
1212/// model.
1213///
1214/// No-op if `target_block_id` is not in the index.
1215pub fn rope_insert_table_anchor(
1216    store: &Store,
1217    table_id: EntityId,
1218    target_block_id: EntityId,
1219    after: bool,
1220) {
1221    const SENTINEL: &str = "\u{FFFC}"; // 3 bytes
1222    const SENTINEL_BYTES: u32 = 3;
1223
1224    let (insert_pos, target_idx, target_is_last) = {
1225        let offsets = store.block_offsets.read();
1226        let target_marker = OffsetMarker::Block(target_block_id);
1227        let Some((start, end)) = offsets.range_of(target_marker) else {
1228            return;
1229        };
1230        let idx = offsets
1231            .entries
1232            .iter()
1233            .position(|(m, _)| *m == target_marker)
1234            .unwrap();
1235        let is_last = idx + 1 == offsets.entries.len();
1236        let pos = if after { end } else { start };
1237        (pos, idx, is_last)
1238    };
1239
1240    // Insertion strategy:
1241    let (rope_inserted, marker_byte_start, new_entry_pos, shift_threshold, shift_delta) = if !after
1242    {
1243        // Before target: "\u{FFFC}\n" at target.byte_start
1244        ("\u{FFFC}\n", insert_pos, target_idx, insert_pos, 4i32)
1245    } else if !target_is_last {
1246        // After target, with following entries: "\u{FFFC}\n"
1247        // at target.byte_end. The TableAnchor sits where the
1248        // next block USED to start; that following entry
1249        // shifts by 4.
1250        ("\u{FFFC}\n", insert_pos, target_idx + 1, insert_pos, 4i32)
1251    } else {
1252        // After target which is last: "\n\u{FFFC}" appended.
1253        // TableAnchor's byte_start sits 1 past the original
1254        // total (after the new `\n`).
1255        (
1256            "\n\u{FFFC}",
1257            insert_pos + 1,
1258            target_idx + 1,
1259            insert_pos,
1260            4i32,
1261        )
1262    };
1263
1264    // 1. Splice the literal bytes into the rope.
1265    {
1266        let mut rope = store.rope.write();
1267        let char_idx = rope.byte_to_char(insert_pos as usize);
1268        rope.insert(char_idx, rope_inserted);
1269    }
1270
1271    // 2. Shift entries past the insertion point. Use shift_after
1272    //    BEFORE inserting our new entry so we don't double-shift.
1273    store
1274        .block_offsets
1275        .write()
1276        .shift_after(shift_threshold, shift_delta);
1277
1278    // 3. Register the TableAnchor at the resolved byte position
1279    //    and the resolved Vec position.
1280    store.block_offsets.write().insert_at(
1281        new_entry_pos,
1282        OffsetMarker::TableAnchor(table_id),
1283        marker_byte_start,
1284    );
1285
1286    // Note: SENTINEL_BYTES is part of `shift_delta` (3 for the
1287    // sentinel + 1 for the `\n`).
1288    let _ = SENTINEL;
1289    let _ = SENTINEL_BYTES;
1290}
1291
1292/// Append a U+FFFC table-anchor sentinel at the end of the rope and
1293/// register a `TableAnchor(table_id)` marker.
1294///
1295/// Used by import paths (`import_djot_uc`, `import_html_uc`,
1296/// `import_markdown_uc`) that process the document linearly and append
1297/// entities as they encounter them, rather than inserting relative to
1298/// an existing target block.
1299///
1300/// # `needs_boundary`
1301///
1302/// True when something has already been emitted, so the sentinel needs a
1303/// `\n` in front of it rather than running into the previous entry.
1304///
1305/// It is the **caller's** flag, not `rope.len_bytes() == 0`, and the
1306/// difference is not academic. Those two answers diverge on exactly one
1307/// document: one whose first block is *empty* — an empty code fence, say.
1308/// The rope is then still zero bytes long even though a block has been
1309/// emitted, so an emptiness check skips the boundary that block is owed.
1310/// Its `block_offsets` entry and the anchor's then both point at byte 0:
1311/// two entities claiming one offset, in the offset index every edit
1312/// resolves through.
1313///
1314/// Every other element gets its boundary from the importer's own
1315/// positional flag (`rope_insert_block_boundary` after the first block).
1316/// Deriving the same fact a second way, from the rope's byte length, is
1317/// what let the two disagree.
1318pub fn rope_append_table_anchor(store: &Store, table_id: EntityId, needs_boundary: bool) {
1319    let (anchor_byte_start, new_total) = {
1320        let mut rope = store.rope.write();
1321        let char_end = rope.len_chars();
1322        let to_insert = if needs_boundary {
1323            "\n\u{FFFC}"
1324        } else {
1325            "\u{FFFC}"
1326        };
1327        rope.insert(char_end, to_insert);
1328        let new_total = rope.len_bytes() as u32;
1329        // Sentinel is 3 bytes; if a `\n` was prepended that's 1 byte
1330        // before the sentinel.
1331        let anchor_byte_start = new_total - 3;
1332        (anchor_byte_start, new_total)
1333    };
1334
1335    let mut offsets = store.block_offsets.write();
1336    offsets.push(OffsetMarker::TableAnchor(table_id), anchor_byte_start);
1337    offsets.set_total_bytes(new_total);
1338}
1339
1340/// Remove a TableAnchor sentinel from the rope, undoing the effect
1341/// of `rope_insert_table_anchor`. Looks up the anchor's byte range
1342/// (always 3 bytes for the U+FFFC plus 1 byte of inter-marker `\n`
1343/// either before or after, depending on what's adjacent), removes
1344/// those 4 bytes from the rope, drops the entry, shifts trailing
1345/// entries by -4.
1346///
1347/// No-op if no TableAnchor for `table_id` exists.
1348pub fn rope_remove_table_anchor(store: &Store, table_id: EntityId) {
1349    let anchor_marker = OffsetMarker::TableAnchor(table_id);
1350    let (anchor_byte_start, anchor_idx, anchor_is_last, has_predecessor) = {
1351        let offsets = store.block_offsets.read();
1352        let Some((start, _end)) = offsets.range_of(anchor_marker) else {
1353            return;
1354        };
1355        let idx = offsets
1356            .entries
1357            .iter()
1358            .position(|(m, _)| *m == anchor_marker)
1359            .unwrap();
1360        let is_last = idx + 1 == offsets.entries.len();
1361        let has_pred = idx > 0;
1362        (start, idx, is_last, has_pred)
1363    };
1364
1365    // Symmetric to insert_table_anchor. The bytes to remove are:
1366    // - if anchor is last: [byte_start - 1 .. byte_start + 3) — the
1367    //   preceding `\n` + the 3-byte sentinel
1368    // - if anchor is the only entry: [byte_start .. byte_start + 3),
1369    //   the sentinel alone, with no boundary on either side
1370    // - otherwise: [byte_start .. byte_start + 4) — the sentinel
1371    //   + the following `\n`
1372    let (remove_start, remove_end) = match (anchor_is_last, has_predecessor) {
1373        (true, true) => (anchor_byte_start - 1, anchor_byte_start + 3),
1374        (true, false) => (anchor_byte_start, anchor_byte_start + 3),
1375        (false, _) => (anchor_byte_start, anchor_byte_start + 4),
1376    };
1377
1378    {
1379        let mut rope = store.rope.write();
1380        let char_start = rope.byte_to_char(remove_start as usize);
1381        let char_end = rope.byte_to_char(remove_end as usize);
1382        rope.remove(char_start..char_end);
1383    }
1384    {
1385        let mut offsets = store.block_offsets.write();
1386        offsets.remove_at(anchor_idx);
1387    }
1388    // Shift the entries past the removed range only, as `rope_remove_block`
1389    // does. An empty entry right before a last anchor starts where the cut
1390    // starts, at the boundary it loses; shifting from there moved it back
1391    // into the entry before it, or below zero.
1392    store
1393        .block_offsets
1394        .write()
1395        .shift_after(remove_end, -((remove_end - remove_start) as i32));
1396}
1397
1398/// Remove every one of `markers` (blocks and table anchors alike) from the
1399/// rope, each with one boundary `\n`, and drop their entries from the index:
1400/// the rope and index that [`rope_remove_block`] and
1401/// [`rope_remove_table_anchor`] leave, called for each marker, with one walk
1402/// of the index for all of them. What is left is the kept entries' contents
1403/// joined by boundaries, in their order. Markers not in the index are
1404/// skipped.
1405///
1406/// A deletion that removes entities has to take their text out of the rope
1407/// too, or the rope keeps text no block owns: the offset index then names
1408/// blocks that are gone, every position after them is off by their length,
1409/// and search and the addressable text still find the deleted words.
1410pub fn rope_remove_markers(store: &Store, markers: &[OffsetMarker]) {
1411    let mut offsets = store.block_offsets.write();
1412    let count = offsets.len();
1413    let mut dropped = vec![false; count];
1414    let mut any = false;
1415    for marker in markers {
1416        if let Some(position) = offsets.position_of(*marker) {
1417            dropped[position] = true;
1418            any = true;
1419        }
1420    }
1421    if !any {
1422        return;
1423    }
1424    let total = offsets.total_bytes();
1425    // One cut per run of consecutive dropped entries: their contents and the
1426    // boundary after each when a kept entry follows the run, or else the
1427    // boundary before the run and everything to the end of the rope.
1428    let mut cuts: Vec<(u32, u32)> = Vec::new();
1429    let mut position = 0;
1430    while position < count {
1431        if !dropped[position] {
1432            position += 1;
1433            continue;
1434        }
1435        let run_start = position;
1436        while position < count && dropped[position] {
1437            position += 1;
1438        }
1439        let first_byte = offsets.entries[run_start].1;
1440        let cut = if position < count {
1441            (first_byte, offsets.entries[position].1)
1442        } else if run_start > 0 {
1443            (first_byte.saturating_sub(1), total)
1444        } else {
1445            (0, total)
1446        };
1447        if cut.1 > cut.0 {
1448            cuts.push(cut);
1449        }
1450    }
1451    {
1452        // Last cut first, so the byte offsets of the others still hold.
1453        let mut rope = store.rope.write();
1454        for &(start, end) in cuts.iter().rev() {
1455            let char_start = rope.byte_to_char(start as usize);
1456            let char_end = rope.byte_to_char(end as usize);
1457            rope.remove(char_start..char_end);
1458        }
1459    }
1460    offsets.remove_entries(&dropped, &cuts);
1461}
1462
1463/// What an edit changed between two states of the rope, as positions: the
1464/// span of `before` from the first returned position to the second was
1465/// replaced by the span of `after` from the first to the third.
1466///
1467/// `from` is where the edit was asked to go in, and the span starts there or
1468/// after it when the text in front of `from` is unchanged: the ends are
1469/// matched first, so text that repeats the text in front of it counts as
1470/// going in at the earliest place from `from` on, then the starts. An
1471/// insertion goes in where it is asked, with two exceptions this finds: a
1472/// table pasted into a paragraph goes in after the paragraph, so what of the
1473/// paragraph followed the caret stays in front of it; and a table pasted into
1474/// a table cell fills the cells from the caret's own, replacing what they held
1475/// from the start of the caret's cell, which can lie before `from`. Counting
1476/// either as text put in at the caret moved every cursor standing in the rest
1477/// of that paragraph, or in those cells, to the wrong place.
1478pub fn changed_span(
1479    before: &ropey::Rope,
1480    after: &ropey::Rope,
1481    from: usize,
1482) -> (usize, usize, usize) {
1483    let (old_len, new_len) = (before.len_chars(), after.len_chars());
1484    let shorter = old_len.min(new_len);
1485    let from = from.min(shorter);
1486    // The common start, as far as `from`.
1487    let mut prefix = 0;
1488    {
1489        let mut old_chars = before.chars();
1490        let mut new_chars = after.chars();
1491        while prefix < from {
1492            match (old_chars.next(), new_chars.next()) {
1493                (Some(old), Some(new)) if old == new => prefix += 1,
1494                _ => break,
1495            }
1496        }
1497    }
1498    // The common end, reaching back no further than the common start.
1499    let mut suffix = 0;
1500    {
1501        let reach = shorter - prefix;
1502        let mut old_chars = before.chars_at(old_len);
1503        let mut new_chars = after.chars_at(new_len);
1504        while suffix < reach {
1505            match (old_chars.prev(), new_chars.prev()) {
1506                (Some(old), Some(new)) if old == new => suffix += 1,
1507                _ => break,
1508            }
1509        }
1510    }
1511    let (old_end, new_end) = (old_len - suffix, new_len - suffix);
1512    // When nothing in front of `from` changed, the rest of the common start,
1513    // from `from` on, up to what the end left.
1514    if prefix == from {
1515        let mut old_chars = before.chars_at(from);
1516        let mut new_chars = after.chars_at(from);
1517        while prefix < old_end.min(new_end) {
1518            match (old_chars.next(), new_chars.next()) {
1519                (Some(old), Some(new)) if old == new => prefix += 1,
1520                _ => break,
1521            }
1522        }
1523    }
1524    (prefix, old_end, new_end)
1525}
1526
1527/// Where a position belongs when it falls on a table's anchor: the `U+FFFC`
1528/// a table occupies in the rope, or the boundary after it. Those two
1529/// characters stand for the table as a whole and belong to no block.
1530/// `forward`, the position moves to the start of the table's first cell:
1531/// where a caret on the table types, and where a range starting on it
1532/// starts. Otherwise it moves back to the end of the entry before the table,
1533/// where a range ending on it ends. Any other position, and every position of
1534/// a document whose rope is not its position space, is returned as is.
1535///
1536/// Resolved as a block position, the anchor matched no block: the edit fell
1537/// back to the document's last block, so text typed or pasted there landed at
1538/// the end of the document and a deletion ending there ran to it.
1539///
1540/// Tables can follow each other with nothing between them in the rope: a table
1541/// nested at the start of a cell's frame has its anchor right after the anchor
1542/// of the table holding that cell. The walk goes past every anchor of such a
1543/// chain, so the result is never an anchor position itself: forward, it is the
1544/// first block after the chain (the innermost table's first cell); backward, it
1545/// is the end of the entry before the chain, or the document's start when the
1546/// chain opens it.
1547pub fn snap_off_table_anchor(store: &Store, position: i64, forward: bool) -> i64 {
1548    if !rope_positions_match_flow(store) {
1549        return position;
1550    }
1551    let rope = store.rope.read();
1552    let clamped = position.clamp(0, rope.len_chars() as i64);
1553    let byte = rope.char_to_byte(clamped as usize) as u32;
1554    let offsets = store.block_offsets.read();
1555    let Some(marker @ OffsetMarker::TableAnchor(_)) = offsets.marker_at_byte(byte) else {
1556        return position;
1557    };
1558    let Some(index) = offsets.position_of(marker) else {
1559        return position;
1560    };
1561    let is_anchor = |i: usize| {
1562        offsets
1563            .entries
1564            .get(i)
1565            .is_some_and(|(entry, _)| !entry.is_block())
1566    };
1567    let target = if forward {
1568        let mut next = index + 1;
1569        while is_anchor(next) {
1570            next += 1;
1571        }
1572        offsets
1573            .entries
1574            .get(next)
1575            .map_or_else(|| offsets.total_bytes(), |(_, start)| *start)
1576    } else {
1577        let mut first = index;
1578        while first > 0 && is_anchor(first - 1) {
1579            first -= 1;
1580        }
1581        // The boundary in front of the chain's first anchor closes the entry
1582        // before it: a caret there stands at that entry's end.
1583        offsets
1584            .entries
1585            .get(first)
1586            .map_or(0, |(_, start)| start.saturating_sub(1))
1587    };
1588    rope.byte_to_char(target as usize) as i64
1589}
1590
1591/// Where `table_id`'s anchor stands in the rope's position space, when the
1592/// rope is the document's position space and holds the anchor.
1593pub fn table_anchor_position(store: &Store, table_id: EntityId) -> Option<i64> {
1594    if !rope_positions_match_flow(store) {
1595        return None;
1596    }
1597    let (byte, _) = store
1598        .block_offsets
1599        .read()
1600        .range_of(OffsetMarker::TableAnchor(table_id))?;
1601    Some(store.rope.read().byte_to_char(byte as usize) as i64)
1602}
1603
1604/// Whether a table's anchor lies in the positions `[start, end)`: whether a
1605/// range over them covers the start of a table. `false` for a document whose
1606/// rope is not its position space.
1607pub fn range_covers_table_anchor(store: &Store, start: i64, end: i64) -> bool {
1608    if start >= end || !rope_positions_match_flow(store) {
1609        return false;
1610    }
1611    let rope = store.rope.read();
1612    let total = rope.len_chars() as i64;
1613    let byte_of = |position: i64| rope.char_to_byte(position.clamp(0, total) as usize) as u32;
1614    let (from, to) = (byte_of(start), byte_of(end));
1615    let offsets = store.block_offsets.read();
1616    // The entries are in byte order: only those starting inside the range are
1617    // looked at, which for a Backspace or a Delete is one or two.
1618    let first = offsets.entries.partition_point(|(_, byte)| *byte < from);
1619    offsets.entries[first..]
1620        .iter()
1621        .take_while(|(_, byte)| *byte < to)
1622        .any(|(marker, _)| !marker.is_block())
1623}
1624
1625/// Whether the range from `requested_start` (on or before a table's anchor, which the
1626/// range's `start` was moved past, see [`snap_off_table_anchor`]) to `end` holds a whole
1627/// table: the anchor and every block of its cells.
1628pub fn holds_a_table_from_its_anchor(
1629    store: &Store,
1630    requested_start: i64,
1631    start: i64,
1632    end: i64,
1633) -> bool {
1634    if requested_start >= start {
1635        return false;
1636    }
1637    let table_ids: Vec<EntityId> = store.tables.read().keys().copied().collect();
1638    table_ids.into_iter().any(|table_id| {
1639        let Some(anchor) = table_anchor_position(store, table_id) else {
1640            return false;
1641        };
1642        if anchor < requested_start || anchor >= start {
1643            return false;
1644        }
1645        let table_end = {
1646            let offsets = store.block_offsets.read();
1647            let rope = store.rope.read();
1648            table_block_ids(store, table_id)
1649                .iter()
1650                .filter_map(|block_id| offsets.range_with_successor(OffsetMarker::Block(*block_id)))
1651                .map(|(block_start, block_end, has_successor)| {
1652                    let text_end = if has_successor && block_end > block_start {
1653                        block_end - 1
1654                    } else {
1655                        block_end
1656                    };
1657                    rope.byte_to_char(text_end as usize) as i64
1658                })
1659                .max()
1660        };
1661        table_end.is_some_and(|table_end| end >= table_end)
1662    })
1663}
1664
1665/// Whether a range over the positions `[start, end)` holds a whole table, as a deletion of
1666/// it takes one: with its ends moved off any table's anchor (see [`snap_off_table_anchor`]),
1667/// it covers a table's anchor, or it starts on a table's anchor and reaches the end of that
1668/// table's last cell.
1669///
1670/// A copy reads a range as the deletion does. It took a table whole whenever the range held
1671/// the table's anchor, where the deletion takes it only then: a selection from a table's
1672/// anchor into its first cell, which the Right arrow and Shift+Right from the paragraph
1673/// before the table make, copied the whole table and cut the characters selected, and the
1674/// paste of the cut put the table in a second time.
1675pub fn range_holds_a_whole_table(store: &Store, start: i64, end: i64) -> bool {
1676    let snapped_start = snap_off_table_anchor(store, start, true);
1677    let snapped_end = snap_off_table_anchor(store, end, false);
1678    range_covers_table_anchor(store, snapped_start, snapped_end)
1679        || holds_a_table_from_its_anchor(store, start, snapped_start, snapped_end)
1680}
1681
1682/// Where a table lies in the rope's position space: the position of its anchor, and where
1683/// the text of the last entry it holds ends (its last cell's last paragraph, or a table
1684/// nested there).
1685#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1686pub struct TableExtent {
1687    pub table_id: EntityId,
1688    pub anchor: i64,
1689    pub end: i64,
1690}
1691
1692impl TableExtent {
1693    /// Whether a range starting at `start` starts in the table: in one of its cells, or on
1694    /// the boundary right after its anchor, which stands for its first cell. A start on the
1695    /// anchor itself is the table's start (see [`holds_a_table_from_its_anchor`]).
1696    fn holds_start(&self, start: i64) -> bool {
1697        self.anchor < start && start <= self.end
1698    }
1699
1700    /// Whether a range ending at `end` ends in the table: in one of its cells. An end on the
1701    /// anchor, or on the boundary after it, ends before the table (see
1702    /// [`snap_off_table_anchor`]).
1703    fn holds_end(&self, store: &Store, end: i64) -> bool {
1704        let end = snap_off_table_anchor(store, end, false);
1705        self.anchor < end && end <= self.end
1706    }
1707}
1708
1709/// Every table's [`TableExtent`], in reading order, when the rope is the document's position
1710/// space. Empty otherwise, and for a document holding no table.
1711pub fn table_extents(store: &Store) -> Vec<TableExtent> {
1712    if !rope_positions_match_flow(store) {
1713        return Vec::new();
1714    }
1715    let table_ids: Vec<EntityId> = store.tables.read().keys().copied().collect();
1716    let mut extents: Vec<TableExtent> = table_ids
1717        .into_iter()
1718        .filter_map(|table_id| extent_of(store, table_id))
1719        .collect();
1720    // In reading order, whatever order the store keeps the tables in.
1721    extents.sort_unstable_by_key(|extent| extent.anchor);
1722    extents
1723}
1724
1725/// The [`TableExtent`] of `table_id`, when the rope is the document's position space and
1726/// holds its anchor.
1727pub fn table_extent(store: &Store, table_id: EntityId) -> Option<TableExtent> {
1728    if !rope_positions_match_flow(store) {
1729        return None;
1730    }
1731    extent_of(store, table_id)
1732}
1733
1734fn extent_of(store: &Store, table_id: EntityId) -> Option<TableExtent> {
1735    let blocks = table_block_ids(store, table_id);
1736    let offsets = store.block_offsets.read();
1737    let anchor_index = offsets.position_of(OffsetMarker::TableAnchor(table_id))?;
1738    let last_index = blocks
1739        .iter()
1740        .filter_map(|block_id| offsets.position_of(OffsetMarker::Block(*block_id)))
1741        .max()
1742        .unwrap_or(anchor_index)
1743        .max(anchor_index);
1744    let rope = store.rope.read();
1745    let char_of = |byte: u32| rope.byte_to_char(byte as usize) as i64;
1746    let (_, anchor_byte) = offsets.entries.get(anchor_index)?;
1747    // The text of the last entry ends at the boundary before whatever follows it, or at the
1748    // end of the rope.
1749    let end = offsets
1750        .entries
1751        .get(last_index + 1)
1752        .map_or(rope.len_chars() as i64, |(_, next)| {
1753            char_of(next.saturating_sub(1))
1754        });
1755    Some(TableExtent {
1756        table_id,
1757        anchor: char_of(*anchor_byte),
1758        end,
1759    })
1760}
1761
1762/// The range `[start, end)` widened to hold whole every table it has one end in and the
1763/// other end outside of: a start in a table's cells with an end past the table moves back to
1764/// the table's anchor, and an end in a table's cells with a start before the table moves on
1765/// to the end of the table's last cell. The same is done for the tables around those, so a
1766/// range from a table nested in a cell to past the outer table holds the outer one whole.
1767///
1768/// This is the one rule a copy and a removal share for a range crossing a table's edge, as
1769/// a range holding a table's anchor already is (see [`range_holds_a_whole_table`]): the
1770/// whole table goes with the text beside it, as Word and LibreOffice take a table a
1771/// selection runs out of. A copy of such a range held the whole table while the removal
1772/// emptied the cells it met and kept the grid, so a cut pasted back put the table in twice;
1773/// and a removal from a table's last cell to the end of the text kept the paragraph after
1774/// the table. A range with both ends in one table, or both outside every table, is left as
1775/// it is.
1776pub fn take_whole_tables(store: &Store, start: i64, end: i64) -> (i64, i64) {
1777    if start >= end || store.tables.read().is_empty() {
1778        return (start, end);
1779    }
1780    let extents = table_extents(store);
1781    let (mut start, mut end) = (start, end);
1782    // Each widening moves an end out to a table's edge, never back: at most one pass per
1783    // table, and one more to see nothing moves.
1784    for _ in 0..=extents.len() {
1785        let mut moved = false;
1786        for extent in &extents {
1787            if extent.holds_start(start) && end > extent.end {
1788                start = extent.anchor;
1789                moved = true;
1790            }
1791            if start < extent.anchor && extent.holds_end(store, end) && end < extent.end {
1792                end = extent.end;
1793                moved = true;
1794            }
1795        }
1796        if !moved {
1797            break;
1798        }
1799    }
1800    (start, end)
1801}
1802
1803/// Remove a registered block from the rope: drops its content bytes
1804/// plus one boundary `\n` (the one after, if the block has a
1805/// successor; the one before, if it's the last entry), removes the
1806/// entry from the index, and shifts trailing entries by the negative
1807/// byte delta.
1808///
1809/// No-op if `block_id` is not in the index. No-op for the special
1810/// case of a single-block document being asked to remove its sole
1811/// block (we'd produce an empty rope but the block itself is being
1812/// cascaded by the caller).
1813pub fn rope_remove_block(store: &Store, block_id: EntityId) {
1814    let block_marker = OffsetMarker::Block(block_id);
1815    let (block_start, block_end, idx, is_last, has_pred) = {
1816        let offsets = store.block_offsets.read();
1817        let Some((start, end)) = offsets.range_of(block_marker) else {
1818            return;
1819        };
1820        let Some(idx) = offsets.position_of(block_marker) else {
1821            return;
1822        };
1823        let is_last = idx + 1 == offsets.entries.len();
1824        let has_pred = idx > 0;
1825        (start, end, idx, is_last, has_pred)
1826    };
1827
1828    // Determine the byte range to delete:
1829    // - if there's a successor: [block_start..block_end) — the
1830    //   block's content INCLUDING its trailing boundary `\n`
1831    //   (which is the byte at block_end - 1)
1832    // - if last and has predecessor: [block_start - 1..block_end)
1833    //   — also delete the LEADING boundary `\n` that the previous
1834    //   entry placed before us
1835    // - if last and no predecessor (sole entry): just delete
1836    //   [block_start..block_end) (no boundary `\n` exists)
1837    let (remove_start, remove_end) = if is_last && has_pred {
1838        (block_start.saturating_sub(1), block_end)
1839    } else {
1840        (block_start, block_end)
1841    };
1842    if remove_end <= remove_start {
1843        // Drop the entry only; nothing to remove from the rope.
1844        store.block_offsets.write().remove_at(idx);
1845        return;
1846    }
1847    let deleted_bytes = remove_end - remove_start;
1848
1849    {
1850        let mut rope = store.rope.write();
1851        let char_start = rope.byte_to_char(remove_start as usize);
1852        let char_end = rope.byte_to_char(remove_end as usize);
1853        rope.remove(char_start..char_end);
1854    }
1855    store.block_offsets.write().remove_at(idx);
1856    // Shift entries STRICTLY PAST the removed range. Using `remove_end` as
1857    // the threshold (rather than `remove_start`) keeps an empty predecessor
1858    // whose byte_start equals `remove_start` (the leading boundary `\n` we
1859    // just deleted) in place — its content position is unchanged, only its
1860    // trailing boundary is gone. `total_bytes` decreases by `deleted_bytes`
1861    // regardless of threshold.
1862    store
1863        .block_offsets
1864        .write()
1865        .shift_after(remove_end, -(deleted_bytes as i32));
1866}
1867
1868/// Replace the entire content of a registered block in the rope with
1869/// `new_text`. Preserves the block's `byte_start` and its trailing
1870/// boundary `\n` (if any); subsequent entries shift by the net
1871/// length delta.
1872///
1873/// Used by use cases that compute a block's final content as a string
1874/// and want to push that content to the rope in one shot — e.g. the
1875/// block-splitting branches of `insert_html_at_position_uc` and
1876/// `insert_markdown_at_position_uc`, where each affected block
1877/// (head, tail, mid-replacement) gets a single new value.
1878///
1879/// No-op if `block_id` is not in the index.
1880pub fn rope_replace_block_content(store: &Store, block_id: EntityId, new_text: &str) {
1881    let (block_byte_start, content_bytes) = {
1882        let offsets = store.block_offsets.read();
1883        let Some((start, end, has_successor)) =
1884            offsets.range_with_successor(OffsetMarker::Block(block_id))
1885        else {
1886            return;
1887        };
1888        // `range_of` extends to the next entry's `byte_start` (or to
1889        // `total_bytes`). If there's a following entry, the byte at
1890        // `end - 1` is the inter-block boundary `\n` that belongs to
1891        // the boundary between this block and the next, not to this
1892        // block's content.
1893        //
1894        // Whether there is one is the index's to say. Asking whether the
1895        // range stops short of the rope's end got it wrong before an empty
1896        // last block, which starts at the rope's end: the boundary before it
1897        // was taken for content and replaced, and the two blocks were left
1898        // at one offset.
1899        let content_bytes = if has_successor && end > start {
1900            end - start - 1
1901        } else {
1902            end - start
1903        };
1904        (start, content_bytes)
1905    };
1906
1907    let new_bytes = new_text.len() as u32;
1908    if content_bytes == 0 && new_bytes == 0 {
1909        return;
1910    }
1911    let delta = new_bytes as i32 - content_bytes as i32;
1912
1913    // Splice [block_byte_start..block_byte_start + content_bytes)
1914    // with `new_text`.
1915    {
1916        let mut rope = store.rope.write();
1917        let char_start = rope.byte_to_char(block_byte_start as usize);
1918        if content_bytes > 0 {
1919            let char_end = rope.byte_to_char((block_byte_start + content_bytes) as usize);
1920            rope.remove(char_start..char_end);
1921        }
1922        if new_bytes > 0 {
1923            rope.insert(char_start, new_text);
1924        }
1925    }
1926
1927    if delta != 0 {
1928        // Shift entries that sit strictly past this block's start
1929        // (i.e. the trailing boundary and everything after).
1930        store
1931            .block_offsets
1932            .write()
1933            .shift_after(block_byte_start + 1, delta);
1934    }
1935}
1936
1937/// [`rope_replace_block_content`] with an empty text for each of
1938/// `block_ids` in turn: the rope and index that loop leaves, with one walk
1939/// of the index instead of one per block.
1940///
1941/// Each one-block clear shifts every entry after the block, so emptying the
1942/// cells of many tables one block at a time walked the index once per cell.
1943/// When the blocks come in index order, as a deletion meets them, each
1944/// block's content is exactly what it holds before any of them is cleared:
1945/// clearing an earlier block moves this one and the entry after it back by
1946/// the same amount. Out of that order the blocks are cleared one at a time,
1947/// as that loop does.
1948pub fn rope_clear_blocks(store: &Store, block_ids: &[EntityId]) {
1949    // `(index position, byte start, content bytes)` of each block with content.
1950    let mut cuts: Vec<(usize, u32, u32)> = Vec::with_capacity(block_ids.len());
1951    {
1952        let offsets = store.block_offsets.read();
1953        let mut previous: Option<usize> = None;
1954        let mut in_index_order = true;
1955        for &block_id in block_ids {
1956            let marker = OffsetMarker::Block(block_id);
1957            let (Some((start, end, has_successor)), Some(position)) = (
1958                offsets.range_with_successor(marker),
1959                offsets.position_of(marker),
1960            ) else {
1961                // Not in the index: the one-block clear leaves it alone too.
1962                continue;
1963            };
1964            if previous.is_some_and(|before| position <= before) {
1965                in_index_order = false;
1966                break;
1967            }
1968            previous = Some(position);
1969            // What `rope_replace_block_content` counts as the block's content.
1970            let content = if has_successor && end > start {
1971                end - start - 1
1972            } else {
1973                end - start
1974            };
1975            if content > 0 {
1976                cuts.push((position, start, content));
1977            }
1978        }
1979        if !in_index_order {
1980            drop(offsets);
1981            for &block_id in block_ids {
1982                rope_replace_block_content(store, block_id, "");
1983            }
1984            return;
1985        }
1986    }
1987    if cuts.is_empty() {
1988        return;
1989    }
1990    {
1991        // Last cut first, so the byte offsets of the others still hold.
1992        let mut rope = store.rope.write();
1993        for &(_, start, content) in cuts.iter().rev() {
1994            let char_start = rope.byte_to_char(start as usize);
1995            let char_end = rope.byte_to_char((start + content) as usize);
1996            rope.remove(char_start..char_end);
1997        }
1998    }
1999    let shifts: Vec<(usize, u32)> = cuts
2000        .iter()
2001        .map(|&(position, _, content)| (position, content))
2002        .collect();
2003    store.block_offsets.write().remove_bytes_after(&shifts);
2004}
2005
2006/// Delete bytes `[byte_start_in_block..byte_end_in_block)` from inside
2007/// the block identified by `block_id`. Shifts subsequent block offsets
2008/// by the deleted byte length. No-op for blocks not in the index.
2009pub fn rope_delete_in_block(
2010    store: &Store,
2011    block_id: EntityId,
2012    byte_start_in_block: u32,
2013    byte_end_in_block: u32,
2014) {
2015    if byte_end_in_block <= byte_start_in_block {
2016        return;
2017    }
2018    let deleted_bytes = byte_end_in_block - byte_start_in_block;
2019    let block_byte_start = {
2020        let offsets = store.block_offsets.read();
2021        let Some((start, _end)) = offsets.range_of_block(block_id) else {
2022            return;
2023        };
2024        start
2025    };
2026    let rope_byte_start = block_byte_start + byte_start_in_block;
2027    let rope_byte_end = block_byte_start + byte_end_in_block;
2028    {
2029        let mut rope = store.rope.write();
2030        let char_start = rope.byte_to_char(rope_byte_start as usize);
2031        let char_end = rope.byte_to_char(rope_byte_end as usize);
2032        rope.remove(char_start..char_end);
2033    }
2034    store
2035        .block_offsets
2036        .write()
2037        .shift_after(block_byte_start + 1, -(deleted_bytes as i32));
2038}
2039
2040/// Recompute `Frame.byte_range` for every frame in `store.frames`
2041/// based on current `block_offsets` and the frame tree structure.
2042/// Plan §1.6 invariant: each frame's byte_range is the (min_start,
2043/// max_end) over all its descendant blocks, sub-frames, and table
2044/// anchors+cells.
2045///
2046/// Call this after any mutation that affects rope byte positions.
2047/// O(F + B) where F = frames, B = blocks in the document.
2048pub fn recompute_all_frame_byte_ranges(store: &Store) {
2049    let frame_ids: Vec<EntityId> = {
2050        let frames = store.frames.read();
2051        frames.keys().copied().collect()
2052    };
2053    for fid in frame_ids {
2054        let new_range = compute_frame_byte_range_recursive(store, fid);
2055        let mut frames = store.frames.write();
2056        if let Some(f) = frames.get(&fid).cloned()
2057            && f.byte_range != new_range
2058        {
2059            let mut updated = f;
2060            updated.byte_range = new_range;
2061            frames.insert(fid, updated);
2062        }
2063    }
2064}
2065
2066fn compute_frame_byte_range_recursive(store: &Store, frame_id: EntityId) -> (u32, u32) {
2067    let mut bounds: Option<(u32, u32)> = None;
2068    walk_frame_bounds(store, frame_id, &mut bounds);
2069    bounds.unwrap_or((0, 0))
2070}
2071
2072fn walk_frame_bounds(store: &Store, frame_id: EntityId, bounds: &mut Option<(u32, u32)>) {
2073    fn merge(bounds: &mut Option<(u32, u32)>, s: u32, e: u32) {
2074        *bounds = Some(match *bounds {
2075            None => (s, e),
2076            Some((min, max)) => (min.min(s), max.max(e)),
2077        });
2078    }
2079
2080    let (blocks, child_order, table_id) = {
2081        let frames = store.frames.read();
2082        let Some(f) = frames.get(&frame_id) else {
2083            return;
2084        };
2085        (f.blocks.clone(), f.child_order.clone(), f.table)
2086    };
2087
2088    {
2089        let offsets = store.block_offsets.read();
2090        for bid in &blocks {
2091            if let Some((s, e)) = offsets.range_of_block(*bid) {
2092                merge(bounds, s, e);
2093            }
2094        }
2095        if let Some(tid) = table_id
2096            && let Some((s, e)) = offsets.range_of(OffsetMarker::TableAnchor(tid))
2097        {
2098            merge(bounds, s, e);
2099        }
2100    }
2101
2102    for entry in &child_order {
2103        if *entry < 0 {
2104            walk_frame_bounds(store, (-*entry) as EntityId, bounds);
2105        }
2106    }
2107
2108    if let Some(tid) = table_id {
2109        let cell_ids: Vec<EntityId> = {
2110            let tables = store.tables.read();
2111            tables
2112                .get(&tid)
2113                .map(|t| t.cells.clone())
2114                .unwrap_or_default()
2115        };
2116        for cell_id in &cell_ids {
2117            let cell_frame_id = {
2118                let cells = store.table_cells.read();
2119                cells.get(cell_id).and_then(|c| c.cell_frame)
2120            };
2121            if let Some(cfid) = cell_frame_id {
2122                walk_frame_bounds(store, cfid, bounds);
2123            }
2124        }
2125    }
2126}
2127
2128/// Replace `[char_start..char_end)` inside `block` with `replacement`, choosing what the
2129/// replacement wears where it overwrites formatted text — see [`ReplaceFormatPolicy`].
2130/// Mutates the block's format runs, image anchors, footnote references and the global rope
2131/// consistently in one step, and returns the updated `Block` (with a bumped `updated_at`) for
2132/// the caller to persist via its own unit of work.
2133///
2134/// The single shared implementation of "replace a char range inside one block" — originally
2135/// written for the project-wide replace path (`document_search::replace_core::apply_in_block`)
2136/// and moved here so `document_editing`'s interactive selection-replace path can offer the
2137/// same format-policy choice instead of being permanently pinned to
2138/// [`ReplaceFormatPolicy::InheritPreceding`]. See `ReplaceFormatPolicy`'s own doc comment for
2139/// the failure mode a second, independently-drifting copy of this would risk: a replace used
2140/// to be an unannounced delete + insert, which silently dropped formatting. It is
2141/// [`replace_in_blocks`] with one replacement, so the two cannot drift either.
2142///
2143/// Deliberately takes no unit of work — everything here is store-level (the block's text
2144/// lives in the rope, its formatting in `format_runs`, its images in `block_images`), so the
2145/// caller's UoW only has to persist the returned `Block`.
2146///
2147/// Returns `Err` rather than corrupting the block if the replace would violate the format-run
2148/// invariants (see [`FormatRunError`]) — the caller should refuse the edit and propagate this
2149/// rather than swallow it.
2150pub fn replace_in_block(
2151    store: &Store,
2152    block: &Block,
2153    char_start: i64,
2154    char_end: i64,
2155    replacement: &str,
2156    policy: ReplaceFormatPolicy,
2157) -> Result<Block, FormatRunError> {
2158    replace_in_blocks(
2159        store,
2160        &[BlockReplacement {
2161            block,
2162            char_start,
2163            char_end,
2164            replacement,
2165        }],
2166        policy,
2167    )?;
2168    let mut updated = block.clone();
2169    updated.updated_at = chrono::Utc::now();
2170    Ok(updated)
2171}
2172
2173/// One replacement [`replace_in_blocks`] makes: `[char_start..char_end)` of `block`'s text, in
2174/// the block's own positions (an image or a footnote reference counts one), replaced by
2175/// `replacement`.
2176#[derive(Debug, Clone, Copy)]
2177pub struct BlockReplacement<'a> {
2178    pub block: &'a Block,
2179    pub char_start: i64,
2180    pub char_end: i64,
2181    pub replacement: &'a str,
2182}
2183
2184/// Make every replacement of `edits` in one pass over the document: each block's format runs,
2185/// image anchors and footnote references, the rope, and one walk of the offset index for all
2186/// of them. The replacements of one block must not overlap; they may come in any order.
2187///
2188/// Replace All used to make its replacements one at a time, and each moved every index entry
2189/// after it: one match per paragraph cost a walk of the index per match, so replacing a word
2190/// throughout a long text grew with the square of its length and froze the editor for
2191/// seconds. The rope takes each splice in logarithmic time, from the last back, so the
2192/// offsets of the others still hold; the index then moves each entry once, by what the
2193/// replacements before it added or took.
2194///
2195/// Nothing is written until every block's new state is known to be well formed: an `Err`
2196/// leaves the store as it was.
2197pub fn replace_in_blocks(
2198    store: &Store,
2199    edits: &[BlockReplacement<'_>],
2200    policy: ReplaceFormatPolicy,
2201) -> Result<(), FormatRunError> {
2202    // The replacements of each block, blocks in the order they first appear.
2203    let mut order: Vec<&Block> = Vec::new();
2204    let mut of_block: HashMap<EntityId, Vec<&BlockReplacement<'_>>> = HashMap::new();
2205    for edit in edits {
2206        let group = of_block.entry(edit.block.id).or_default();
2207        if group.is_empty() {
2208            order.push(edit.block);
2209        }
2210        group.push(edit);
2211    }
2212
2213    struct NewState<'a> {
2214        block_id: EntityId,
2215        runs: Vec<FormatRun>,
2216        images: Vec<ImageAnchor>,
2217        notes: Option<Vec<FootnoteRefAnchor>>,
2218        /// `(byte_start, byte_end, replacement)` in the block's text, ascending.
2219        splices: Vec<(u32, u32, &'a str)>,
2220    }
2221    let mut states: Vec<NewState<'_>> = Vec::with_capacity(order.len());
2222    for block in order {
2223        let group = of_block.remove(&block.id).unwrap_or_default();
2224        let images_before = store
2225            .block_images
2226            .read()
2227            .get(&block.id)
2228            .cloned()
2229            .unwrap_or_default();
2230        let block_text = block_content_via_store(block, store);
2231        let mut splices: Vec<(u32, u32, &str)> = Vec::with_capacity(group.len());
2232        for edit in group {
2233            let byte_start = logical_offset_to_byte(&block_text, &images_before, edit.char_start);
2234            let byte_end = logical_offset_to_byte(&block_text, &images_before, edit.char_end);
2235            if byte_end < byte_start {
2236                // A range whose end comes before its start names no text to replace;
2237                // measuring it overflowed.
2238                return Err(FormatRunError::ReversedRange {
2239                    start: byte_start,
2240                    end: byte_end,
2241                });
2242            }
2243            splices.push((byte_start, byte_end, edit.replacement));
2244        }
2245        splices.sort_by_key(|(start, end, _)| (*start, *end));
2246        if let Some(pair) = splices.windows(2).find(|pair| pair[0].1 > pair[1].0) {
2247            // Two replacements of the same text: the second would splice bytes the first
2248            // already changed.
2249            return Err(FormatRunError::ReversedRange {
2250                start: pair[0].1,
2251                end: pair[1].0,
2252            });
2253        }
2254
2255        let mut runs = store
2256            .format_runs
2257            .read()
2258            .get(&block.id)
2259            .cloned()
2260            .unwrap_or_default();
2261        let mut images = images_before;
2262        let mut notes = store.block_footnote_refs.read().get(&block.id).cloned();
2263        let mut new_len = block_text.len();
2264        // From the last back, so each splice's offsets are still the text's own.
2265        for &(byte_start, byte_end, replacement) in splices.iter().rev() {
2266            let inserted = replacement.len() as u32;
2267            // Format runs under an explicit policy, and then CHECK the result rather than
2268            // assert it: `debug_assert_well_formed` is compiled out of release, so a
2269            // malformed run list produced in a shipped build went entirely undetected, and
2270            // autosave wrote it to the writer's file seconds later. A replace that would
2271            // corrupt a block's formatting fails loudly.
2272            shift_runs_for_replace(&mut runs, byte_start, byte_end, inserted, policy)?;
2273            shift_images_for_delete(&mut images, byte_start, byte_end);
2274            shift_images_for_insert(&mut images, byte_start, inserted);
2275            if let Some(notes) = notes.as_mut() {
2276                shift_footnote_refs_for_delete(notes, byte_start, byte_end);
2277                shift_footnote_refs_for_insert(notes, byte_start, inserted);
2278            }
2279            new_len = new_len - (byte_end - byte_start) as usize + replacement.len();
2280        }
2281        check_well_formed(&runs, new_len)?;
2282        states.push(NewState {
2283            block_id: block.id,
2284            runs,
2285            images,
2286            notes,
2287            splices,
2288        });
2289    }
2290
2291    // Every block's new state is sound: write it.
2292    let mut rope_splices: Vec<(u32, u32, &str)> = Vec::new();
2293    let mut shifts: Vec<(u32, i32)> = Vec::new();
2294    {
2295        let offsets = store.block_offsets.read();
2296        let mut runs_map = store.format_runs.write();
2297        let mut images_map = store.block_images.write();
2298        let mut notes_map = store.block_footnote_refs.write();
2299        for state in states {
2300            runs_map.insert(state.block_id, state.runs);
2301            images_map.insert(state.block_id, state.images);
2302            if let Some(notes) = state.notes {
2303                notes_map.insert(state.block_id, notes);
2304            }
2305            // A block the index does not hold has no text in the rope to change.
2306            let Some((block_start, _)) = offsets.range_of_block(state.block_id) else {
2307                continue;
2308            };
2309            let mut delta: i64 = 0;
2310            for (byte_start, byte_end, replacement) in state.splices {
2311                rope_splices.push((
2312                    block_start + byte_start,
2313                    block_start + byte_end,
2314                    replacement,
2315                ));
2316                delta += replacement.len() as i64 - (byte_end - byte_start) as i64;
2317            }
2318            // One byte past the block's start, so the block's own entry stays where it is.
2319            if delta != 0 {
2320                shifts.push((block_start + 1, delta as i32));
2321            }
2322        }
2323    }
2324    rope_splices.sort_by_key(|(start, end, _)| (*start, *end));
2325    {
2326        let mut rope = store.rope.write();
2327        for &(byte_start, byte_end, replacement) in rope_splices.iter().rev() {
2328            let char_start = rope.byte_to_char(byte_start as usize);
2329            if byte_end > byte_start {
2330                let char_end = rope.byte_to_char(byte_end as usize);
2331                rope.remove(char_start..char_end);
2332            }
2333            if !replacement.is_empty() {
2334                rope.insert(char_start, replacement);
2335            }
2336        }
2337    }
2338    shifts.sort_by_key(|(threshold, _)| *threshold);
2339    store.block_offsets.write().shift_after_each(&shifts);
2340    Ok(())
2341}
2342
2343#[cfg(test)]
2344mod tests {
2345    use super::*;
2346    use crate::database::block_offset_index::tests::ENTRIES_REWRITTEN;
2347    use crate::entities::{Document, Frame};
2348    use std::cell::Cell;
2349
2350    thread_local! {
2351        /// What `main_text_end` looked at on this thread (see [`super::looked_at`]).
2352        pub(super) static LOOKED_AT: Cell<usize> = const { Cell::new(0) };
2353    }
2354
2355    /// A text of `paragraphs` paragraphs followed by `notes` footnote bodies of one
2356    /// paragraph each, laid out as the loads lay one out: the bodies after the main text.
2357    /// Returns the store and where the main text ends.
2358    fn text_with_notes(paragraphs: u64, notes: u64) -> (Store, i64) {
2359        let store = Store::new();
2360        let main: EntityId = 1;
2361        let mut frames = vec![Frame {
2362            id: main,
2363            ..Frame::default()
2364        }];
2365        let mut end = 0;
2366        let mut next_block: EntityId = 1;
2367        for i in 0..paragraphs {
2368            if next_block > 1 {
2369                rope_insert_block_boundary(&store);
2370            }
2371            let text = format!("Paragraph {i}.");
2372            end = store.rope.read().len_chars() as i64 + text.chars().count() as i64;
2373            rope_append_block(&store, next_block, &text);
2374            frames[0].blocks.push(next_block);
2375            frames[0].child_order.push(next_block as i64);
2376            next_block += 1;
2377        }
2378        for i in 0..notes {
2379            rope_insert_block_boundary(&store);
2380            rope_append_block(&store, next_block, &format!("Note {i}."));
2381            frames.push(Frame {
2382                id: main + 1 + i,
2383                blocks: vec![next_block],
2384                child_order: vec![next_block as i64],
2385                footnote_label: Some(format!("n{i}")),
2386                ..Frame::default()
2387            });
2388            next_block += 1;
2389        }
2390        {
2391            let mut blocks = store.blocks.write();
2392            for id in 1..next_block {
2393                blocks.insert(
2394                    id,
2395                    Block {
2396                        id,
2397                        ..Block::default()
2398                    },
2399                );
2400            }
2401        }
2402        store.documents.write().insert(
2403            1,
2404            Document {
2405                id: 1,
2406                frames: frames.iter().map(|frame| frame.id).collect(),
2407                ..Document::default()
2408            },
2409        );
2410        let mut stored = store.frames.write();
2411        for frame in frames {
2412            stored.insert(frame.id, frame);
2413        }
2414        drop(stored);
2415        (store, end)
2416    }
2417
2418    /// Every forward move of a caret asks where the main text ends. It gathered every block
2419    /// of every note's body and walked the rope index back over them: a document of
2420    /// thousands of notes spent milliseconds on each arrow key. What it looks at must not
2421    /// grow with the notes, nor with the text.
2422    #[test]
2423    fn the_end_of_the_main_text_costs_the_same_however_many_notes_follow() {
2424        let mut looked = Vec::new();
2425        for (paragraphs, notes) in [(50, 100), (50, 2_000), (1_000, 2_000)] {
2426            let (store, end) = text_with_notes(paragraphs, notes);
2427            LOOKED_AT.with(|looked| looked.set(0));
2428            assert_eq!(
2429                main_text_end(&store),
2430                Some(end),
2431                "{paragraphs} paragraphs, {notes} notes"
2432            );
2433            looked.push(LOOKED_AT.with(Cell::get));
2434        }
2435        assert!(
2436            looked.windows(2).all(|pair| pair[0] == pair[1]),
2437            "the end of the main text looked at {looked:?} frames and entries for 100 and \
2438             2,000 notes, then 1,000 paragraphs"
2439        );
2440
2441        // Nothing follows a text without notes, and its end needs no stop.
2442        let (store, _) = text_with_notes(20, 0);
2443        assert_eq!(main_text_end(&store), None);
2444    }
2445
2446    /// A store of `blocks` blocks of a few characters each, the way the importers lay a
2447    /// document out: separated by a `\n` boundary. Returns the ids of its blocks, in order.
2448    fn blocks(blocks: u64) -> (Store, Vec<EntityId>) {
2449        let store = Store::new();
2450        let ids: Vec<EntityId> = (1..=blocks).collect();
2451        for &id in &ids {
2452            if id > 1 {
2453                rope_insert_block_boundary(&store);
2454            }
2455            rope_append_block(&store, id, &format!("cell {id}"));
2456        }
2457        (store, ids)
2458    }
2459
2460    /// Emptying the cells of every table a deletion covers clears a block per cell, and a
2461    /// one-block clear rewrites every index entry after the block: clearing a quarter of
2462    /// the blocks one at a time rewrites about an eighth of the index squared. Clearing
2463    /// them together must rewrite each entry once.
2464    #[test]
2465    fn clearing_blocks_together_walks_the_index_once() {
2466        const BLOCKS: u64 = 1_000;
2467        let (one_by_one, ids) = blocks(BLOCKS);
2468        let (together, _) = blocks(BLOCKS);
2469        let cleared: Vec<EntityId> = ids.iter().copied().step_by(4).collect();
2470
2471        ENTRIES_REWRITTEN.with(|rewritten| rewritten.set(0));
2472        for &id in &cleared {
2473            rope_replace_block_content(&one_by_one, id, "");
2474        }
2475        let block_by_block = ENTRIES_REWRITTEN.with(Cell::get);
2476
2477        ENTRIES_REWRITTEN.with(|rewritten| rewritten.set(0));
2478        rope_clear_blocks(&together, &cleared);
2479        let in_one_walk = ENTRIES_REWRITTEN.with(Cell::get);
2480
2481        assert_eq!(
2482            *together.rope.read(),
2483            *one_by_one.rope.read(),
2484            "the same text is left"
2485        );
2486        assert_eq!(
2487            *together.block_offsets.read(),
2488            *one_by_one.block_offsets.read(),
2489            "the same index is left"
2490        );
2491        assert!(
2492            block_by_block > 100 * BLOCKS as usize,
2493            "clearing block by block rewrote {block_by_block} entries"
2494        );
2495        assert_eq!(
2496            in_one_walk,
2497            BLOCKS as usize,
2498            "clearing {} blocks together rewrote {in_one_walk} index entries, where one walk \
2499             of the {BLOCKS} entries is enough",
2500            cleared.len()
2501        );
2502    }
2503
2504    /// Replace All replaced one match at a time, and each replacement moved every index
2505    /// entry after it: with a match in every paragraph, the whole index once per match. All
2506    /// of them together must move each entry once, and leave what one at a time leaves.
2507    #[test]
2508    fn replacing_in_many_blocks_walks_the_index_once() {
2509        const BLOCKS: u64 = 1_000;
2510        let (one_by_one, ids) = blocks(BLOCKS);
2511        let (together, _) = blocks(BLOCKS);
2512        let entities: Vec<Block> = ids
2513            .iter()
2514            .map(|&id| Block {
2515                id,
2516                ..Block::default()
2517            })
2518            .collect();
2519        // In each block, "cell {id}": "ce" becomes "k", and "!?" goes in at the end: each
2520        // block grows by one byte, so every entry after it moves.
2521        let edits: Vec<BlockReplacement<'_>> = entities
2522            .iter()
2523            .flat_map(|block| {
2524                let end = format!("cell {}", block.id).chars().count() as i64;
2525                [
2526                    BlockReplacement {
2527                        block,
2528                        char_start: 0,
2529                        char_end: 2,
2530                        replacement: "k",
2531                    },
2532                    BlockReplacement {
2533                        block,
2534                        char_start: end,
2535                        char_end: end,
2536                        replacement: "!?",
2537                    },
2538                ]
2539            })
2540            .collect();
2541
2542        ENTRIES_REWRITTEN.with(|rewritten| rewritten.set(0));
2543        for edit in edits.iter().rev() {
2544            replace_in_block(
2545                &one_by_one,
2546                edit.block,
2547                edit.char_start,
2548                edit.char_end,
2549                edit.replacement,
2550                ReplaceFormatPolicy::default(),
2551            )
2552            .unwrap();
2553        }
2554        let edit_by_edit = ENTRIES_REWRITTEN.with(Cell::get);
2555
2556        ENTRIES_REWRITTEN.with(|rewritten| rewritten.set(0));
2557        replace_in_blocks(&together, &edits, ReplaceFormatPolicy::default()).unwrap();
2558        let in_one_walk = ENTRIES_REWRITTEN.with(Cell::get);
2559
2560        assert_eq!(
2561            *together.rope.read(),
2562            *one_by_one.rope.read(),
2563            "the same text is left"
2564        );
2565        assert_eq!(
2566            *together.block_offsets.read(),
2567            *one_by_one.block_offsets.read(),
2568            "the same index is left"
2569        );
2570        assert!(
2571            together
2572                .rope
2573                .read()
2574                .to_string()
2575                .starts_with("kll 1!?\nkll 2!?\n")
2576        );
2577        assert!(
2578            edit_by_edit > 100 * BLOCKS as usize,
2579            "replacing edit by edit rewrote {edit_by_edit} entries"
2580        );
2581        assert!(
2582            in_one_walk <= BLOCKS as usize,
2583            "{} replacements together rewrote {in_one_walk} index entries, where one walk of \
2584             the {BLOCKS} entries is enough",
2585            edits.len()
2586        );
2587    }
2588
2589    /// Two replacements of the same characters cannot both be made: the whole call is
2590    /// refused and nothing is written.
2591    #[test]
2592    fn overlapping_replacements_change_nothing() {
2593        let store = blocks_holding(&["alpha", "beta"]);
2594        let block = Block {
2595            id: 1,
2596            ..Block::default()
2597        };
2598        let edits = [
2599            BlockReplacement {
2600                block: &block,
2601                char_start: 0,
2602                char_end: 3,
2603                replacement: "x",
2604            },
2605            BlockReplacement {
2606                block: &block,
2607                char_start: 2,
2608                char_end: 4,
2609                replacement: "y",
2610            },
2611        ];
2612        assert!(replace_in_blocks(&store, &edits, ReplaceFormatPolicy::default()).is_err());
2613        assert_eq!(store.rope.read().to_string(), "alpha\nbeta");
2614    }
2615
2616    /// A store holding one block per text, in order, separated by `\n` boundaries.
2617    fn blocks_holding(texts: &[&str]) -> Store {
2618        let store = Store::new();
2619        for (i, text) in texts.iter().enumerate() {
2620            if i > 0 {
2621                rope_insert_block_boundary(&store);
2622            }
2623            rope_append_block(&store, i as EntityId + 1, text);
2624        }
2625        store
2626    }
2627
2628    /// A block followed by an empty last block has a boundary after it, though its range
2629    /// runs to the end of the rope: the empty block starts there. Taking a range that ends
2630    /// at the rope's end for the last one counted that boundary as the block's content, so
2631    /// replacing or clearing the block took the boundary out and left the two blocks at one
2632    /// offset, where every later read of either sliced the wrong bytes.
2633    #[test]
2634    fn emptying_the_block_before_an_empty_last_block_keeps_the_boundary() {
2635        for together in [false, true] {
2636            let store = blocks_holding(&["text", ""]);
2637            if together {
2638                rope_clear_blocks(&store, &[1]);
2639            } else {
2640                rope_replace_block_content(&store, 1, "");
2641            }
2642            assert_eq!(store.rope.read().to_string(), "\n", "together: {together}");
2643            let offsets = store.block_offsets.read();
2644            assert_eq!(
2645                *offsets.entries,
2646                vec![(OffsetMarker::Block(1), 0), (OffsetMarker::Block(2), 1)],
2647                "together: {together}"
2648            );
2649            assert_eq!(offsets.total_bytes(), 1);
2650        }
2651    }
2652
2653    /// A table nested at the start of a cell puts its anchor right after the anchor of the
2654    /// table holding the cell, and a position on either stands for the tables, not for a
2655    /// block. Moving one entry off the anchor landed on the other anchor: forward, a caret
2656    /// meant for the first cell stood on the inner table's anchor, and backward, a range end
2657    /// meant to stop before the tables stood on the outer anchor's boundary. Resolved as
2658    /// block positions, both fell back to the document's last block, where a deletion ran to
2659    /// and a paste landed.
2660    #[test]
2661    fn a_position_on_a_chain_of_anchors_snaps_past_the_whole_chain() {
2662        let with_anchors = |texts: &[&str], anchors: &[usize]| {
2663            let store = blocks_holding(texts);
2664            {
2665                let mut offsets = store.block_offsets.write();
2666                let mut entries = (*offsets.entries).clone();
2667                for (i, entry) in entries.iter_mut().enumerate() {
2668                    if anchors.contains(&i) {
2669                        entry.0 = OffsetMarker::TableAnchor(100 + i as EntityId);
2670                    }
2671                }
2672                offsets.entries = std::sync::Arc::new(entries);
2673                offsets.rebuild_marker_index();
2674            }
2675            {
2676                // The rope is the position space only when it mirrors every block.
2677                let mut blocks = store.blocks.write();
2678                for id in 1..=texts.len() as EntityId {
2679                    if !anchors.contains(&(id as usize - 1)) {
2680                        blocks.insert(
2681                            id,
2682                            Block {
2683                                id,
2684                                ..Block::default()
2685                            },
2686                        );
2687                    }
2688                }
2689            }
2690            store
2691        };
2692
2693        // "Before." 0..7, its boundary 7, the outer anchor 8 and its boundary 9, the inner
2694        // anchor 10 and its boundary 11, then the inner table's cell at 12.
2695        let store = with_anchors(
2696            &[
2697                "Before.", "\u{FFFC}", "\u{FFFC}", "inner", "outer", "After.",
2698            ],
2699            &[1, 2],
2700        );
2701        for on_chain in 8..=11 {
2702            assert_eq!(
2703                snap_off_table_anchor(&store, on_chain, true),
2704                12,
2705                "from {on_chain}"
2706            );
2707            assert_eq!(
2708                snap_off_table_anchor(&store, on_chain, false),
2709                7,
2710                "from {on_chain}"
2711            );
2712        }
2713        for off_chain in [0, 6, 7, 12, 17] {
2714            assert_eq!(snap_off_table_anchor(&store, off_chain, true), off_chain);
2715            assert_eq!(snap_off_table_anchor(&store, off_chain, false), off_chain);
2716        }
2717
2718        // A chain opening the document: back to its start, forward to the first cell.
2719        let store = with_anchors(&["\u{FFFC}", "\u{FFFC}", "cell"], &[0, 1]);
2720        for on_chain in 0..=3 {
2721            assert_eq!(
2722                snap_off_table_anchor(&store, on_chain, true),
2723                4,
2724                "from {on_chain}"
2725            );
2726            assert_eq!(
2727                snap_off_table_anchor(&store, on_chain, false),
2728                0,
2729                "from {on_chain}"
2730            );
2731        }
2732    }
2733
2734    /// Whether a range covers a table's anchor, for ranges around, onto and past one.
2735    #[test]
2736    fn a_range_covers_a_table_when_it_holds_its_anchor() {
2737        let store = blocks_holding(&["Before.", "\u{FFFC}", "cell", "After."]);
2738        {
2739            let mut offsets = store.block_offsets.write();
2740            let mut entries = (*offsets.entries).clone();
2741            entries[1].0 = OffsetMarker::TableAnchor(40);
2742            offsets.entries = std::sync::Arc::new(entries);
2743            offsets.rebuild_marker_index();
2744        }
2745        {
2746            let mut blocks = store.blocks.write();
2747            for id in [1, 3, 4] {
2748                blocks.insert(
2749                    id,
2750                    Block {
2751                        id,
2752                        ..Block::default()
2753                    },
2754                );
2755            }
2756        }
2757        // The anchor is at 8, the cell at 10..14, "After." from 15.
2758        for (start, end, covers) in [
2759            (0, 8, false),
2760            (0, 9, true),
2761            (7, 9, true),
2762            (8, 9, true),
2763            (9, 20, false),
2764            (7, 15, true),
2765            (14, 15, false),
2766            (9, 9, false),
2767        ] {
2768            assert_eq!(
2769                range_covers_table_anchor(&store, start, end),
2770                covers,
2771                "{start}..{end}"
2772            );
2773        }
2774    }
2775
2776    /// A rope laid out from `entries`, `None` standing for a table's anchor: the entries'
2777    /// contents joined by boundaries. Entry `i` is `Block(i + 1)`, or `TableAnchor(i + 1)`.
2778    fn layout_of(entries: &[Option<&str>]) -> (Store, Vec<OffsetMarker>) {
2779        let texts: Vec<&str> = entries
2780            .iter()
2781            .map(|entry| entry.unwrap_or("\u{FFFC}"))
2782            .collect();
2783        let store = blocks_holding(&texts);
2784        let markers: Vec<OffsetMarker> = entries
2785            .iter()
2786            .enumerate()
2787            .map(|(i, entry)| match entry {
2788                Some(_) => OffsetMarker::Block(i as EntityId + 1),
2789                None => OffsetMarker::TableAnchor(i as EntityId + 1),
2790            })
2791            .collect();
2792        {
2793            let mut offsets = store.block_offsets.write();
2794            let mut indexed = (*offsets.entries).clone();
2795            for (slot, marker) in indexed.iter_mut().zip(&markers) {
2796                slot.0 = *marker;
2797            }
2798            offsets.entries = std::sync::Arc::new(indexed);
2799            offsets.rebuild_marker_index();
2800        }
2801        (store, markers)
2802    }
2803
2804    /// Removing a set of entries leaves the kept entries' contents joined by boundaries, each
2805    /// entry indexed where it starts in that text, whether they are removed in one pass or
2806    /// one at a time, for every subset of each layout. The layouts hold empty blocks next to
2807    /// table anchors: an empty block right before a last anchor starts where the anchor's
2808    /// cut starts, which moved it back into the entry before it, or below zero; and a table
2809    /// alone had four bytes cut from a rope of three.
2810    #[test]
2811    fn removing_markers_together_matches_removing_them_one_at_a_time() {
2812        let layouts: [&[Option<&str>]; 7] = [
2813            &[
2814                Some("one"),
2815                Some(""),
2816                Some("three"),
2817                None,
2818                Some("five"),
2819                Some(""),
2820            ],
2821            &[Some("Hello"), Some(""), None],
2822            &[Some(""), None],
2823            &[None],
2824            &[None, Some("")],
2825            &[Some("x"), None, Some(""), None, Some("")],
2826            &[Some(""), None, Some("a"), Some("b"), None],
2827        ];
2828        for entries in layouts {
2829            for subset in 1u32..(1 << entries.len()) {
2830                let (_, markers) = layout_of(entries);
2831                let chosen: Vec<OffsetMarker> = markers
2832                    .iter()
2833                    .enumerate()
2834                    .filter(|(i, _)| subset & (1 << i) != 0)
2835                    .map(|(_, marker)| *marker)
2836                    .collect();
2837                // What is left: the kept contents joined by boundaries.
2838                let mut expected_text = String::new();
2839                let mut expected_entries: Vec<(OffsetMarker, u32)> = Vec::new();
2840                for (entry, marker) in entries.iter().zip(&markers) {
2841                    if chosen.contains(marker) {
2842                        continue;
2843                    }
2844                    if !expected_entries.is_empty() {
2845                        expected_text.push('\n');
2846                    }
2847                    expected_entries.push((*marker, expected_text.len() as u32));
2848                    expected_text.push_str(entry.unwrap_or("\u{FFFC}"));
2849                }
2850
2851                let (one_by_one, _) = layout_of(entries);
2852                for marker in &chosen {
2853                    match marker {
2854                        OffsetMarker::Block(id) => rope_remove_block(&one_by_one, *id),
2855                        OffsetMarker::TableAnchor(id) => rope_remove_table_anchor(&one_by_one, *id),
2856                    }
2857                }
2858                let (together, _) = layout_of(entries);
2859                rope_remove_markers(&together, &chosen);
2860                for (how, store) in [("one by one", &one_by_one), ("together", &together)] {
2861                    assert_eq!(
2862                        store.rope.read().to_string(),
2863                        expected_text,
2864                        "{how}, removing {chosen:?} from {entries:?}"
2865                    );
2866                    let offsets = store.block_offsets.read();
2867                    assert_eq!(
2868                        *offsets.entries, expected_entries,
2869                        "{how}, removing {chosen:?} from {entries:?}"
2870                    );
2871                    assert_eq!(
2872                        offsets.total_bytes() as usize,
2873                        expected_text.len(),
2874                        "{how}, removing {chosen:?} from {entries:?}"
2875                    );
2876                }
2877            }
2878        }
2879    }
2880
2881    /// The span an edit changed, from the two ropes around it and where it was asked to go
2882    /// in: at the caret, at the earliest place from the caret on when the new text repeats
2883    /// the text in front of it, after the rest of the paragraph when the edit put its text
2884    /// there, and from before the caret when the edit replaced text there.
2885    #[test]
2886    fn a_changed_span_is_found_where_the_edit_went() {
2887        let span = |before: &str, after: &str, from: usize| {
2888            changed_span(
2889                &ropey::Rope::from_str(before),
2890                &ropey::Rope::from_str(after),
2891                from,
2892            )
2893        };
2894        // Typed at the caret.
2895        assert_eq!(span("Hello world", "Hello big world", 6), (6, 6, 10));
2896        // The same word typed in front of itself: at the caret, not after the old word.
2897        assert_eq!(span("X inserted Y", "X insertedinserted Y", 2), (2, 2, 10));
2898        // A table pasted at 3 goes in after the paragraph: from its end, a boundary and the
2899        // table, in front of the paragraph's own boundary.
2900        assert_eq!(
2901            span("one two\nthree", "one two\n\u{FFFC}\nx\ny\nthree", 3),
2902            (7, 7, 13)
2903        );
2904        // Cells filled from the start of the caret's cell, which is before the caret.
2905        assert_eq!(span("a\nbcd\ne", "a\nx\ny\ne", 4), (2, 5, 5));
2906        // Nothing changed: an empty span at the caret.
2907        assert_eq!(span("same", "same", 2), (2, 2, 2));
2908    }
2909}