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