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