Skip to main content

text_typeset/layout/
flow.rs

1use std::collections::HashMap;
2
3use crate::font::registry::FontRegistry;
4use crate::layout::block::{
5    BlockLayout, BlockLayoutParams, PaintSpan, apply_paint_spans, layout_block,
6};
7use crate::layout::frame::{FrameLayout, FrameLayoutParams, layout_frame};
8use crate::layout::table::{TableLayout, TableLayoutParams, layout_table};
9
10pub enum FlowItem {
11    Block {
12        block_id: usize,
13        y: f32,
14        height: f32,
15    },
16    Table {
17        table_id: usize,
18        y: f32,
19        height: f32,
20    },
21    Frame {
22        frame_id: usize,
23        y: f32,
24        height: f32,
25    },
26}
27
28// ── Nested-block resolution ────────────────────────────────────────
29//
30// `blocks` holds only the blocks laid out in the document's own column.
31// A block inside a table cell lives in `TableLayout::cell_layouts`, and one
32// inside a blockquote (or any other frame) lives in `FrameLayout::blocks`,
33// each with coordinates measured from its container rather than from the
34// document. Everything that reasons about a block by id — caret geometry,
35// per-character positions, the accessibility walk — needs to reach those
36// too, and needs to know what to add to get back into document space.
37
38/// A block's layout together with the document-space origin its own
39/// coordinates are measured from.
40///
41/// `block.y` is relative to [`origin_y`](Self::origin_y) and the block's line
42/// geometry is relative to the block, so the absolute top of the block is
43/// `origin_y + block.y`. For a block in the document's own column both
44/// origins are zero and `block.y` is already absolute — which is what keeps
45/// this a widening of the old lookup rather than a change to it.
46#[non_exhaustive]
47pub struct ResolvedBlock<'a> {
48    pub block: &'a BlockLayout,
49    /// Document-space x of the left edge of the block's content column.
50    pub origin_x: f32,
51    /// Document-space y that `block.y` is measured from.
52    pub origin_y: f32,
53}
54
55/// The document-space origin of a table's own coordinate system.
56///
57/// `TableLayout::column_xs` and `row_ys` are measured from here, so cell
58/// `(r, c)` sits at `(origin_x + column_xs[c], origin_y + row_ys[r])`.
59#[non_exhaustive]
60pub struct ResolvedTable<'a> {
61    pub table: &'a TableLayout,
62    pub origin_x: f32,
63    pub origin_y: f32,
64}
65
66fn resolve_block_in_table<'a>(
67    table: &'a TableLayout,
68    block_id: usize,
69    base_x: f32,
70    base_y: f32,
71) -> Option<ResolvedBlock<'a>> {
72    for cell in &table.cell_layouts {
73        if cell.row >= table.row_ys.len() || cell.column >= table.column_xs.len() {
74            continue;
75        }
76        let origin_x = base_x + table.column_xs[cell.column];
77        let origin_y = base_y + table.y + table.row_ys[cell.row];
78        for block in &cell.blocks {
79            if block.block_id == block_id {
80                return Some(ResolvedBlock {
81                    block,
82                    origin_x,
83                    origin_y,
84                });
85            }
86        }
87    }
88    None
89}
90
91fn resolve_block_in_frame<'a>(
92    frame: &'a FrameLayout,
93    block_id: usize,
94    base_x: f32,
95    base_y: f32,
96) -> Option<ResolvedBlock<'a>> {
97    let content_x = base_x + frame.x + frame.content_x;
98    let content_y = base_y + frame.y + frame.content_y;
99    for block in &frame.blocks {
100        if block.block_id == block_id {
101            return Some(ResolvedBlock {
102                block,
103                origin_x: content_x,
104                origin_y: content_y,
105            });
106        }
107    }
108    for table in &frame.tables {
109        if let Some(found) = resolve_block_in_table(table, block_id, content_x, content_y) {
110            return Some(found);
111        }
112    }
113    for nested in &frame.frames {
114        if let Some(found) = resolve_block_in_frame(nested, block_id, content_x, content_y) {
115            return Some(found);
116        }
117    }
118    None
119}
120
121fn resolve_table_in_frame<'a>(
122    frame: &'a FrameLayout,
123    table_id: usize,
124    base_x: f32,
125    base_y: f32,
126) -> Option<ResolvedTable<'a>> {
127    let content_x = base_x + frame.x + frame.content_x;
128    let content_y = base_y + frame.y + frame.content_y;
129    for table in &frame.tables {
130        if table.table_id == table_id {
131            return Some(ResolvedTable {
132                table,
133                origin_x: content_x,
134                origin_y: content_y + table.y,
135            });
136        }
137    }
138    for nested in &frame.frames {
139        if let Some(found) = resolve_table_in_frame(nested, table_id, content_x, content_y) {
140            return Some(found);
141        }
142    }
143    None
144}
145
146pub struct FlowLayout {
147    pub blocks: HashMap<usize, BlockLayout>,
148    pub tables: HashMap<usize, TableLayout>,
149    pub frames: HashMap<usize, FrameLayout>,
150    pub flow_order: Vec<FlowItem>,
151    pub content_height: f32,
152    pub viewport_width: f32,
153    pub viewport_height: f32,
154    pub cached_max_content_width: f32,
155    /// Device pixel ratio passed to shapers and rasterizers.
156    /// Layout is always stored in logical pixels; this only affects
157    /// precision (physical ppem) and glyph bitmap resolution.
158    pub scale_factor: f32,
159    /// Per-document logical text-magnification factor (`1.0` = none). Set from
160    /// `DocumentFlow::font_scale` at layout time and threaded into block layout
161    /// alongside `scale_factor`; multiplies the resolved font size so all text
162    /// grows logically (advances, line heights, content height) and reflows.
163    pub font_scale: f32,
164    /// Un-overlaid (shaped) copy of each block that currently carries a paint
165    /// overlay, keyed by block_id. The paint-overlay fast path re-derives the
166    /// live block from this so repeated highlight changes never compound run
167    /// splits.
168    ///
169    /// **Captured on write, not at layout.** Straight out of a full layout the
170    /// live blocks already ARE their own base, so a block enters this map only
171    /// when an overlay is first applied to it, and leaves when its overlay is
172    /// cleared. A document nothing highlights therefore keeps this map empty.
173    /// Capturing every block up front instead cost a second deep copy of the
174    /// whole shaped layout: on a book-length manuscript, 17 MB that only a
175    /// handful of blocks would ever have used.
176    ///
177    /// Absent means "identical to the live block", never "missing".
178    base_blocks: HashMap<usize, BlockLayout>,
179    /// Current paint-only highlight overlay per block_id. Empty for a block
180    /// means "no overlay" (base colors). Kept so an incrementally relaid block
181    /// re-applies its overlay.
182    pending_paint_spans: HashMap<usize, Vec<PaintSpan>>,
183}
184
185impl Default for FlowLayout {
186    fn default() -> Self {
187        Self::new()
188    }
189}
190
191impl FlowLayout {
192    pub fn new() -> Self {
193        Self {
194            blocks: HashMap::new(),
195            tables: HashMap::new(),
196            frames: HashMap::new(),
197            flow_order: Vec::new(),
198            content_height: 0.0,
199            viewport_width: 0.0,
200            viewport_height: 0.0,
201            cached_max_content_width: 0.0,
202            scale_factor: 1.0,
203            font_scale: 1.0,
204            base_blocks: HashMap::new(),
205            pending_paint_spans: HashMap::new(),
206        }
207    }
208
209    /// Add a table to the flow at the current y position.
210    pub fn add_table(
211        &mut self,
212        registry: &FontRegistry,
213        params: &TableLayoutParams,
214        available_width: f32,
215    ) {
216        let mut table = layout_table(
217            registry,
218            params,
219            available_width,
220            self.scale_factor,
221            self.font_scale,
222        );
223
224        let mut y = self.content_height;
225        table.y = y;
226        y += table.total_height;
227
228        self.flow_order.push(FlowItem::Table {
229            table_id: table.table_id,
230            y: table.y,
231            height: table.total_height,
232        });
233        if table.total_width > self.cached_max_content_width {
234            self.cached_max_content_width = table.total_width;
235        }
236        self.tables.insert(table.table_id, table);
237        self.content_height = y;
238    }
239
240    /// Add a frame to the flow.
241    ///
242    /// - **Inline**: placed in normal flow, advances content_height.
243    /// - **FloatLeft**: placed at current y, x=0. Does not advance content_height
244    ///   (surrounding content wraps around it).
245    /// - **FloatRight**: placed at current y, x=available_width - frame_width.
246    /// - **Absolute**: placed at (margin_left, margin_top) from document origin.
247    ///   Does not affect flow at all.
248    pub fn add_frame(
249        &mut self,
250        registry: &FontRegistry,
251        params: &FrameLayoutParams,
252        available_width: f32,
253    ) {
254        use crate::layout::frame::FramePosition;
255
256        let mut frame = layout_frame(
257            registry,
258            params,
259            available_width,
260            self.scale_factor,
261            self.font_scale,
262        );
263
264        match params.position {
265            FramePosition::Inline => {
266                frame.y = self.content_height;
267                frame.x = 0.0;
268                self.content_height += frame.total_height;
269            }
270            FramePosition::FloatLeft => {
271                frame.y = self.content_height;
272                frame.x = 0.0;
273                // Float doesn't advance content_height -content wraps beside it.
274                // For simplicity, we still advance so subsequent blocks appear below.
275                // True float wrapping would require a "float exclusion zone" tracked
276                // during paragraph layout, which is significantly more complex.
277                self.content_height += frame.total_height;
278            }
279            FramePosition::FloatRight => {
280                frame.y = self.content_height;
281                frame.x = (available_width - frame.total_width).max(0.0);
282                self.content_height += frame.total_height;
283            }
284            FramePosition::Absolute => {
285                // Absolute frames are positioned relative to the document origin
286                // using their margin values as coordinates. They don't affect flow.
287                frame.y = params.margin_top;
288                frame.x = params.margin_left;
289                // Don't advance content_height
290            }
291        }
292
293        self.flow_order.push(FlowItem::Frame {
294            frame_id: frame.frame_id,
295            y: frame.y,
296            height: frame.total_height,
297        });
298        if frame.total_width > self.cached_max_content_width {
299            self.cached_max_content_width = frame.total_width;
300        }
301        self.frames.insert(frame.frame_id, frame);
302    }
303
304    /// Clear all layout state. Call before rebuilding from a new FlowSnapshot.
305    pub fn clear(&mut self) {
306        self.blocks.clear();
307        self.tables.clear();
308        self.frames.clear();
309        self.flow_order.clear();
310        self.content_height = 0.0;
311        self.cached_max_content_width = 0.0;
312        self.base_blocks.clear();
313        self.pending_paint_spans.clear();
314    }
315
316    /// Drop every captured paint base. Called after a full layout, where the
317    /// freshly-shaped blocks are their own base and any prior overlay is gone.
318    ///
319    /// This used to deep-copy every laid-out block into `base_blocks` here. The
320    /// copy was correct and almost entirely unused: only a block that actually
321    /// receives an overlay is ever re-derived from its base, and
322    /// [`ensure_base`](Self::ensure_base) takes that copy at the moment it is
323    /// needed instead.
324    pub(crate) fn reset_paint_base(&mut self) {
325        self.base_blocks.clear();
326    }
327
328    /// How many blocks currently hold a captured paint base.
329    ///
330    /// The memory characteristic this layout makes a promise about: a block
331    /// enters the set when an overlay is applied to it and leaves when that
332    /// overlay is cleared, so a document nothing highlights answers `0`. Read by
333    /// the paint-overlay tests, and useful in a debugger when a highlight looks
334    /// stuck.
335    pub fn captured_paint_bases(&self) -> usize {
336        self.base_blocks.len()
337    }
338
339    /// Capture `block_id`'s live (base-coloured) shaped output, if it has not
340    /// been captured already. Returns whether the block exists at all.
341    ///
342    /// Called immediately before an overlay is applied, which is the only moment
343    /// a base is needed and the only moment the live block is still guaranteed
344    /// to be un-overlaid.
345    fn ensure_base(&mut self, block_id: usize) -> bool {
346        if self.base_blocks.contains_key(&block_id) {
347            return true;
348        }
349        let Some(fresh) = find_block_ref(self, block_id).cloned() else {
350            return false;
351        };
352        self.base_blocks.insert(block_id, fresh);
353        true
354    }
355
356    /// Forget the captured base of every block that no longer carries an
357    /// overlay, so toggling a highlight on and off does not accumulate copies.
358    ///
359    /// Safe only after the overlay walk has restored those blocks from their
360    /// bases: dropping a base a block still needs would freeze its colours.
361    fn drop_unused_bases(&mut self) {
362        if self.pending_paint_spans.is_empty() {
363            self.base_blocks.clear();
364            return;
365        }
366        self.base_blocks
367            .retain(|id, _| self.pending_paint_spans.contains_key(id));
368    }
369
370    /// Replace the paint-only color overlay for the whole flow.
371    ///
372    /// `spans_by_block` maps block_id → its disjoint paint spans (from
373    /// `text_document`'s `extract_paint_spans`). Every block is re-derived from
374    /// its captured base, so colors/decorations change but glyph positions,
375    /// advances, line breaks, and heights do NOT — no reshape, no reflow.
376    /// Blocks absent from the map reset to base colors.
377    pub fn apply_paint_spans_for(&mut self, spans_by_block: HashMap<usize, Vec<PaintSpan>>) {
378        // An empty span list means "no overlay", exactly as it does in
379        // `apply_block_paint_spans`. Keeping such an entry would pin a base copy
380        // for a block that carries nothing, which is the cost this capture-on-
381        // write layout exists to avoid.
382        let mut spans_by_block = spans_by_block;
383        spans_by_block.retain(|_, spans| !spans.is_empty());
384        // Capture a base for every block about to be overlaid. A block that is
385        // only being cleared keeps the base it was given when it was overlaid,
386        // which is what the walk below restores it from.
387        for &block_id in spans_by_block.keys() {
388            self.ensure_base(block_id);
389        }
390        self.pending_paint_spans = spans_by_block;
391        let base = &self.base_blocks;
392        let pending = &self.pending_paint_spans;
393        for b in self.blocks.values_mut() {
394            overlay_block_in_place(b, base, pending);
395        }
396        for t in self.tables.values_mut() {
397            for c in &mut t.cell_layouts {
398                for b in &mut c.blocks {
399                    overlay_block_in_place(b, base, pending);
400                }
401            }
402        }
403        for f in self.frames.values_mut() {
404            overlay_frame_in_place(f, base, pending);
405        }
406        self.drop_unused_bases();
407    }
408
409    /// Apply (or clear, when `spans` is empty) the paint overlay for a single
410    /// block, re-derived from its base.
411    ///
412    /// Returns `false` when there is nothing to do: either the block is not in
413    /// this layout at all, or it is being cleared while it never carried an
414    /// overlay, in which case it already shows its base colours. Callers read
415    /// the answer as "did anything change here", and repaint on `true`.
416    pub fn apply_block_paint_spans(&mut self, block_id: usize, spans: &[PaintSpan]) -> bool {
417        if spans.is_empty() {
418            if !self.base_blocks.contains_key(&block_id) {
419                return false;
420            }
421            self.pending_paint_spans.remove(&block_id);
422        } else {
423            if !self.ensure_base(block_id) {
424                return false;
425            }
426            self.pending_paint_spans.insert(block_id, spans.to_vec());
427        }
428        let base = &self.base_blocks;
429        let pending = &self.pending_paint_spans;
430        if let Some(b) = self.blocks.get_mut(&block_id) {
431            overlay_block_in_place(b, base, pending);
432            self.drop_unused_bases();
433            return true;
434        }
435        let mut overlaid = false;
436        for t in self.tables.values_mut() {
437            for c in &mut t.cell_layouts {
438                for b in &mut c.blocks {
439                    if b.block_id == block_id {
440                        overlay_block_in_place(b, base, pending);
441                        overlaid = true;
442                    }
443                }
444            }
445        }
446        if overlaid {
447            self.drop_unused_bases();
448            return true;
449        }
450        for f in self.frames.values_mut() {
451            if overlay_one_in_frame(f, block_id, base, pending) {
452                self.drop_unused_bases();
453                return true;
454            }
455        }
456        // The block is in none of the three places a block can live, so nothing
457        // was recoloured and the caller has nothing to repaint.
458        self.drop_unused_bases();
459        false
460    }
461
462    /// After an incremental relayout of `block_id`, make its freshly-shaped
463    /// output the new base and re-apply its pending overlay in place.
464    ///
465    /// The stale capture is **dropped** rather than refreshed. The fresh shaped
466    /// output IS the new base, so a later `apply_block_paint_spans` (the engine
467    /// re-applying syntax, search or spell highlights after an edit) captures it
468    /// on demand. Keeping the pre-edit copy instead would have that overlay
469    /// re-derive the block from text the writer has already changed, silently
470    /// clobbering the just-typed characters (visible only in highlights-on
471    /// views; a full re-layout from a resize would restore it).
472    fn refresh_base_and_overlay_block(&mut self, block_id: usize) {
473        self.base_blocks.remove(&block_id);
474        // Nothing to overlay unless this block itself carries pending spans: the
475        // freshly-reshaped block already holds the correct base-colored output,
476        // and every other block keeps whatever base it was captured with.
477        if !self.pending_paint_spans.contains_key(&block_id) {
478            return;
479        }
480        self.ensure_base(block_id);
481        let base = &self.base_blocks;
482        let pending = &self.pending_paint_spans;
483        if let Some(b) = self.blocks.get_mut(&block_id) {
484            overlay_block_in_place(b, base, pending);
485            return;
486        }
487        for t in self.tables.values_mut() {
488            for c in &mut t.cell_layouts {
489                for b in &mut c.blocks {
490                    if b.block_id == block_id {
491                        overlay_block_in_place(b, base, pending);
492                        return;
493                    }
494                }
495            }
496        }
497        for f in self.frames.values_mut() {
498            if overlay_one_in_frame(f, block_id, base, pending) {
499                return;
500            }
501        }
502    }
503
504    /// Add a single block to the flow at the current y position.
505    ///
506    /// **Bulk-path primitive.** This touches no paint-overlay bookkeeping at
507    /// all, which is what a full layout wants: it runs after `clear`, so no
508    /// stale base or pending overlay can be left over, and a base is captured
509    /// on demand when an overlay is first applied.
510    ///
511    /// Appending to an *existing* layout is different, because that layout may
512    /// already hold a base or a pending overlay under the same block_id — from
513    /// a previous block that carried it. Use
514    /// [`append_block`](Self::append_block) there. Reaching for this one is
515    /// silent when wrong: the block lays out and renders fine, but a stale base
516    /// re-derives it from the *previous* block's shaped output the next time
517    /// anything recolours it.
518    pub fn add_block(
519        &mut self,
520        registry: &FontRegistry,
521        params: &BlockLayoutParams,
522        available_width: f32,
523    ) {
524        let mut block = layout_block(
525            registry,
526            params,
527            available_width,
528            self.scale_factor,
529            self.font_scale,
530        );
531
532        // Margin collapsing with previous block
533        let mut y = self.content_height;
534        if let Some(FlowItem::Block {
535            block_id: prev_id, ..
536        }) = self.flow_order.last()
537        {
538            if let Some(prev_block) = self.blocks.get(prev_id) {
539                let collapsed = prev_block.bottom_margin.max(block.top_margin);
540                y -= prev_block.bottom_margin;
541                y += collapsed;
542            } else {
543                y += block.top_margin;
544            }
545        } else {
546            y += block.top_margin;
547        }
548
549        block.y = y;
550        let block_content = block.height - block.top_margin - block.bottom_margin;
551        y += block_content + block.bottom_margin;
552
553        self.flow_order.push(FlowItem::Block {
554            block_id: block.block_id,
555            y: block.y,
556            height: block.height,
557        });
558        self.update_max_width_for_block(&block);
559        self.blocks.insert(block.block_id, block);
560        self.content_height = y;
561    }
562
563    /// Append one block to the tail of an *existing* layout, in O(1).
564    ///
565    /// This is [`add_block`](Self::add_block) plus the paint-overlay
566    /// bookkeeping that only a tail append needs. A full layout runs after
567    /// `clear`, so nothing can be stale there; appending into a live layout can
568    /// land on a block_id that still carries the base and pending overlay of the
569    /// block that held it before, and re-deriving the new block from that base
570    /// would paint the *old* block's shaped output.
571    ///
572    /// So it drops any stale base for the appended id and re-applies whatever
573    /// overlay is still pending for it, in O(1)
574    /// (`refresh_base_and_overlay_block`, the same call
575    /// [`relayout_block`](Self::relayout_block) already relies on).
576    pub fn append_block(
577        &mut self,
578        registry: &FontRegistry,
579        params: &BlockLayoutParams,
580        available_width: f32,
581    ) {
582        self.add_block(registry, params, available_width);
583        self.refresh_base_and_overlay_block(params.block_id);
584    }
585
586    /// Drop the first `n` top-level blocks, returning how many were removed.
587    ///
588    /// The eviction half of a bounded streaming buffer (a log viewer's
589    /// scrollback cap). Usually O(n) map removals plus one `Vec` memmove of the
590    /// surviving `flow_order` entries — no reshaping. The return value is the
591    /// count actually evicted, which is less than `n` when the run of leading
592    /// blocks is shorter than `n` or a table/frame stops the walk.
593    ///
594    /// Surviving blocks deliberately **keep their absolute `y`**. The vacated
595    /// band at the top simply becomes empty, and `content_height` is unchanged,
596    /// so nothing below moves and no scroll position shifts under the user.
597    /// Rewriting every survivor's `y` would make eviction O(remaining) and
598    /// would yank the viewport; leaving them is both cheaper and correct.
599    /// `flow_order`'s ascending-`y` ordering — which `hit_test`'s binary search
600    /// relies on — is preserved, since removing a prefix of a sorted run leaves
601    /// it sorted.
602    ///
603    /// Only top-level blocks are considered; a leading table or frame stops the
604    /// eviction (a streaming buffer is a flat run of blocks by construction).
605    ///
606    /// If the widest block in the flow is among those evicted,
607    /// `max_content_width` is recomputed from the survivors — O(remaining) for
608    /// that call only. Evicting narrower blocks (the overwhelmingly common
609    /// case) cannot lower the maximum and skips the recompute.
610    pub fn remove_leading(&mut self, n: usize) -> usize {
611        let mut removed = 0;
612        let mut evicted_widest = false;
613
614        for item in self.flow_order.iter().take(n) {
615            let FlowItem::Block { block_id, .. } = item else {
616                break;
617            };
618            if let Some(block) = self.blocks.remove(block_id) {
619                // `cached_max_content_width` only ever grows, so it goes stale
620                // exactly when the block that set it leaves. Comparing against
621                // it here keeps the common case O(n).
622                if block_max_width(&block) >= self.cached_max_content_width {
623                    evicted_widest = true;
624                }
625            }
626            self.base_blocks.remove(block_id);
627            self.pending_paint_spans.remove(block_id);
628            removed += 1;
629        }
630
631        self.flow_order.drain(..removed);
632        if evicted_widest {
633            self.recompute_max_content_width();
634        }
635        removed
636    }
637
638    /// Re-derive `cached_max_content_width` from everything currently laid out.
639    ///
640    /// The cache is a running maximum that only grows, which is fine while a
641    /// flow only ever gains content. Anything that *removes* content has to
642    /// re-derive it, or the horizontal scroll range keeps describing content
643    /// that is no longer there.
644    pub(crate) fn recompute_max_content_width(&mut self) {
645        let mut max: f32 = 0.0;
646        for block in self.blocks.values() {
647            max = max.max(block_max_width(block));
648        }
649        for table in self.tables.values() {
650            max = max.max(table.total_width);
651        }
652        for frame in self.frames.values() {
653            max = max.max(frame.total_width);
654        }
655        self.cached_max_content_width = max;
656    }
657
658    /// Declare the total extent of a uniform-row-height document without
659    /// shaping anything.
660    ///
661    /// In windowed mode `content_height` describes the whole document, not the
662    /// shaped window, so it cannot come from the usual accumulator. Use this to
663    /// keep the scrollbar honest when the row count changes outside the shaped
664    /// window (a line appended while the user is scrolled away from the tail).
665    ///
666    /// Leaves the shaped window untouched.
667    pub fn set_uniform_extent(&mut self, total_rows: usize, row_height: f32) {
668        self.content_height = total_rows as f32 * row_height;
669    }
670
671    /// Shape only `window` — a slice of a much larger uniform-row-height
672    /// document — placing each row at an arithmetic `y = index * row_height`.
673    ///
674    /// Shaping every line is what makes a large document expensive: a resident
675    /// shaped line costs ~6.5 KB, so a 100 000-line buffer costs ~623 MB fully
676    /// laid out, against ~1 MB for a viewport-sized window
677    /// (`docs/streaming-baseline.md`). Rendering already culls to the viewport,
678    /// so shaping the off-screen remainder buys nothing.
679    ///
680    /// `y` is arithmetic rather than accumulated precisely so that a row can be
681    /// placed without having laid out — or even having in memory — any of the
682    /// rows above it, which is what lets the window start at an arbitrary
683    /// scroll position. `content_height` is likewise derived from
684    /// `total_rows`, so the scrollbar reflects the whole document rather than
685    /// the shaped window.
686    ///
687    /// # Invariants
688    ///
689    /// The arithmetic placement is only correct for a document whose rows are
690    /// genuinely uniform: **one row = one visual line of exactly `row_height`**
691    /// — no wrapping (`non_breakable_lines`), no embedded newlines, no
692    /// per-row margins, one font size throughout. That suits log/console
693    /// output and monospaced code; it does not suit prose. Callers with
694    /// variable-height content must use [`layout_blocks`](Self::layout_blocks).
695    /// `window` must be sorted ascending by index, which keeps `flow_order`
696    /// ascending by `y` as `hit_test`'s binary search requires. Both are
697    /// checked in debug builds.
698    ///
699    /// After this call, appending at the tail with
700    /// [`append_block`](Self::append_block) stays correct: `content_height` is
701    /// exactly `total_rows * row_height`, which is where row `total_rows`
702    /// belongs. Trim the window's front with
703    /// [`remove_leading`](Self::remove_leading).
704    ///
705    /// # Behaviour worth knowing
706    ///
707    /// Like [`layout_blocks`](Self::layout_blocks), this drops any paint
708    /// overlay: re-apply spans after re-windowing, or the new rows render in
709    /// base colours. Because this runs on every visible-range change, that
710    /// re-apply is part of the scroll path, not a one-off.
711    ///
712    /// `max_content_width` accumulates across windows rather than being
713    /// re-derived per window: it reports the widest row *seen so far*, not the
714    /// widest row in the document (unknowable without shaping all of it) and
715    /// not the widest row on screen (which would make the horizontal scrollbar
716    /// jump on every vertical scroll). It therefore only grows during a
717    /// windowed session.
718    ///
719    /// `y` is `index * row_height` in `f32`, which represents consecutive
720    /// integers exactly only to 2^24: past ~840 000 rows at a 20 px row height,
721    /// row positions begin quantizing and neighbouring rows drift out of
722    /// alignment. Well beyond the sizes this targets, but not infinite.
723    pub fn layout_window(
724        &mut self,
725        registry: &FontRegistry,
726        window: &[(usize, BlockLayoutParams)],
727        total_rows: usize,
728        row_height: f32,
729        available_width: f32,
730    ) {
731        debug_assert!(
732            window.windows(2).all(|w| w[0].0 < w[1].0),
733            "layout_window: window must be sorted ascending by row index, else \
734             flow_order stops being ascending by y and hit_test's binary search \
735             silently misreports rows"
736        );
737        debug_assert!(
738            window.last().is_none_or(|(last, _)| *last < total_rows),
739            "layout_window: window reaches row {:?} but the document declares \
740             only {total_rows} rows — those rows would sit below content_height \
741             and be unreachable by scrolling",
742            window.last().map(|(i, _)| *i)
743        );
744
745        // The widest row seen so far must survive the rebuild: re-deriving it
746        // from the window alone would make the horizontal scroll range track
747        // whatever happens to be on screen, so it would jump on every vertical
748        // scroll.
749        let max_width_seen = self.cached_max_content_width;
750        self.clear();
751        self.cached_max_content_width = max_width_seen;
752
753        for (index, params) in window {
754            let mut block = layout_block(
755                registry,
756                params,
757                available_width,
758                self.scale_factor,
759                self.font_scale,
760            );
761            debug_assert!(
762                (block.height - row_height).abs() < 0.5,
763                "layout_window: row {index} laid out {:.2}px tall against a \
764                 declared row_height of {row_height:.2}px — the row is not a \
765                 single unwrapped line, so arithmetic y placement would drift",
766                block.height
767            );
768
769            let y = *index as f32 * row_height;
770            block.y = y;
771            self.flow_order.push(FlowItem::Block {
772                block_id: block.block_id,
773                y,
774                height: block.height,
775            });
776            self.update_max_width_for_block(&block);
777            self.blocks.insert(block.block_id, block);
778        }
779
780        // Describes the whole document, not the shaped window — so the
781        // scrollbar spans everything even though almost none of it is shaped.
782        self.set_uniform_extent(total_rows, row_height);
783        // O(1): a full layout leaves the live blocks as their own base.
784        self.reset_paint_base();
785    }
786
787    /// Lay out a sequence of blocks vertically.
788    pub fn layout_blocks(
789        &mut self,
790        registry: &FontRegistry,
791        block_params: Vec<BlockLayoutParams>,
792        available_width: f32,
793    ) {
794        self.clear();
795        // Note: viewport_width is NOT set here. It's a display property
796        // set by Typesetter::set_viewport(), not a layout property.
797        // available_width is the layout width which may differ from viewport
798        // when using ContentWidthMode::Fixed.
799        for params in &block_params {
800            self.add_block(registry, params, available_width);
801        }
802        // A full layout clears any prior overlay (see `clear`), so the live
803        // blocks ARE the base at this point. The engine applies paint spans
804        // afterward via `apply_paint_spans_for`, which captures what it needs.
805        self.reset_paint_base();
806    }
807
808    /// Update a single block's layout and shift subsequent items if height changed.
809    ///
810    /// Finds the block in top-level blocks, table cells, or frames, re-layouts
811    /// it, and propagates any height delta to subsequent flow items.
812    /// Relayout the one block `params` names, wherever it lives, and shift the
813    /// document-character positions of everything after it.
814    ///
815    /// Returns `false` when the block is in none of the three places a block can
816    /// be — top level, a table cell, a frame. The caller must treat that as a
817    /// failed relayout and fall back to a full one: the shift is half of this
818    /// method's job, so skipping it silently leaves every later block's
819    /// `position` describing the document as it was before the edit.
820    #[must_use]
821    pub fn relayout_block(
822        &mut self,
823        registry: &FontRegistry,
824        params: &BlockLayoutParams,
825        available_width: f32,
826    ) -> bool {
827        let block_id = params.block_id;
828
829        // Top-level block
830        if self.blocks.contains_key(&block_id) {
831            self.relayout_top_level_block(registry, params, available_width);
832            self.refresh_base_and_overlay_block(block_id);
833            return true;
834        }
835
836        // Table cell block: scan tables for the block_id
837        let table_match = self.tables.iter().find_map(|(&tid, table)| {
838            for cell in &table.cell_layouts {
839                if cell.blocks.iter().any(|b| b.block_id == block_id) {
840                    return Some((tid, cell.row, cell.column));
841                }
842            }
843            None
844        });
845        if let Some((table_id, row, col)) = table_match {
846            let old_char_len = block_char_len(find_block_ref(self, block_id));
847            self.relayout_table_block(registry, params, table_id, row, col);
848            let new_char_len = block_char_len(find_block_ref(self, block_id));
849            let char_delta = new_char_len as isize - old_char_len as isize;
850            self.shift_block_positions_after_table_block(table_id, block_id, char_delta);
851            self.refresh_base_and_overlay_block(block_id);
852            return true;
853        }
854
855        // Frame block: scan frames (including nested frames) for the block_id
856        let frame_match = self.frames.iter().find_map(|(&fid, frame)| {
857            if frame_contains_block(frame, block_id) {
858                return Some(fid);
859            }
860            None
861        });
862        if let Some(frame_id) = frame_match {
863            let old_char_len = block_char_len(find_block_ref(self, block_id));
864            self.relayout_frame_block(registry, params, frame_id);
865            let new_char_len = block_char_len(find_block_ref(self, block_id));
866            let char_delta = new_char_len as isize - old_char_len as isize;
867            self.shift_block_positions_after_frame_block(frame_id, block_id, char_delta);
868            self.refresh_base_and_overlay_block(block_id);
869            return true;
870        }
871
872        false
873    }
874
875    /// Relayout a top-level block (existing logic).
876    fn relayout_top_level_block(
877        &mut self,
878        registry: &FontRegistry,
879        params: &BlockLayoutParams,
880        available_width: f32,
881    ) {
882        let block_id = params.block_id;
883        let old_y = self.blocks.get(&block_id).map(|b| b.y).unwrap_or(0.0);
884        let old_height = self.blocks.get(&block_id).map(|b| b.height).unwrap_or(0.0);
885        let old_top_margin = self
886            .blocks
887            .get(&block_id)
888            .map(|b| b.top_margin)
889            .unwrap_or(0.0);
890        let old_bottom_margin = self
891            .blocks
892            .get(&block_id)
893            .map(|b| b.bottom_margin)
894            .unwrap_or(0.0);
895        let old_content = old_height - old_top_margin - old_bottom_margin;
896        let old_end = old_y + old_content + old_bottom_margin;
897        let old_char_len = block_char_len(self.blocks.get(&block_id));
898
899        let mut block = layout_block(
900            registry,
901            params,
902            available_width,
903            self.scale_factor,
904            self.font_scale,
905        );
906        block.y = old_y;
907
908        if (block.top_margin - old_top_margin).abs() > 0.001 {
909            let prev_bm = self.prev_block_bottom_margin(block_id).unwrap_or(0.0);
910            let old_collapsed = prev_bm.max(old_top_margin);
911            let new_collapsed = prev_bm.max(block.top_margin);
912            block.y = old_y + (new_collapsed - old_collapsed);
913        }
914
915        let new_content = block.height - block.top_margin - block.bottom_margin;
916        let new_end = block.y + new_content + block.bottom_margin;
917        let delta = new_end - old_end;
918        let new_char_len = block_char_len(Some(&block));
919        let char_delta = new_char_len as isize - old_char_len as isize;
920
921        let new_y = block.y;
922        let new_height = block.height;
923        self.update_max_width_for_block(&block);
924        self.blocks.insert(block_id, block);
925
926        // Update flow_order entry
927        for item in &mut self.flow_order {
928            if let FlowItem::Block {
929                block_id: id,
930                y,
931                height,
932            } = item
933                && *id == block_id
934            {
935                *y = new_y;
936                *height = new_height;
937                break;
938            }
939        }
940
941        self.shift_items_after_block(block_id, delta);
942        self.shift_block_positions_after_block(block_id, char_delta);
943    }
944
945    /// Relayout a block inside a table cell. Recomputes the row height
946    /// and propagates any table height delta to subsequent flow items.
947    fn relayout_table_block(
948        &mut self,
949        registry: &FontRegistry,
950        params: &BlockLayoutParams,
951        table_id: usize,
952        row: usize,
953        col: usize,
954    ) {
955        let table = match self.tables.get_mut(&table_id) {
956            Some(t) => t,
957            None => return,
958        };
959
960        let old_table_height = table.total_height;
961        recompute_table_cell(
962            table,
963            registry,
964            params,
965            row,
966            col,
967            self.scale_factor,
968            self.font_scale,
969        );
970        let delta = table.total_height - old_table_height;
971
972        // Update flow_order entry for this table
973        for item in &mut self.flow_order {
974            if let FlowItem::Table {
975                table_id: id,
976                height,
977                ..
978            } = item
979                && *id == table_id
980            {
981                *height = table.total_height;
982                break;
983            }
984        }
985
986        self.shift_items_after_table(table_id, delta);
987    }
988
989    /// Relayout a block inside a frame. Handles direct blocks, blocks in
990    /// cells of frame-nested tables, and blocks in nested frames (any
991    /// depth). Recomputes frame content height and propagates any height
992    /// delta to subsequent flow items.
993    fn relayout_frame_block(
994        &mut self,
995        registry: &FontRegistry,
996        params: &BlockLayoutParams,
997        frame_id: usize,
998    ) {
999        let old_total_height = match self.frames.get(&frame_id) {
1000            Some(f) => f.total_height,
1001            None => return,
1002        };
1003
1004        {
1005            let frame = self.frames.get_mut(&frame_id).unwrap();
1006            relayout_block_deep_in_frame(
1007                frame,
1008                registry,
1009                params,
1010                self.scale_factor,
1011                self.font_scale,
1012            );
1013        }
1014
1015        let new_total_height = self.frames[&frame_id].total_height;
1016        let delta = new_total_height - old_total_height;
1017
1018        for item in &mut self.flow_order {
1019            if let FlowItem::Frame {
1020                frame_id: id,
1021                height,
1022                ..
1023            } = item
1024                && *id == frame_id
1025            {
1026                *height = new_total_height;
1027                break;
1028            }
1029        }
1030
1031        self.shift_items_after_frame(frame_id, delta);
1032    }
1033
1034    /// Shift the document-character `position` of every block that appears
1035    /// after the given target block in flow order by `char_delta` characters.
1036    ///
1037    /// `shift_items_after_block` only propagates the vertical pixel delta.
1038    /// This method propagates the character delta so hit_test and caret_rect
1039    /// keep returning correct document positions after an incremental
1040    /// relayout that changed the target block's char length (e.g. a cut or
1041    /// paste inside a non-last paragraph).
1042    fn shift_block_positions_after_block(&mut self, block_id: usize, char_delta: isize) {
1043        self.shift_block_positions_after_flow_item(FlowItemRef::Block(block_id), char_delta);
1044    }
1045
1046    /// Shift the document-character `position` of every block belonging to
1047    /// a flow item that appears after `target` in flow order.
1048    fn shift_block_positions_after_flow_item(&mut self, target: FlowItemRef, char_delta: isize) {
1049        if char_delta == 0 {
1050            return;
1051        }
1052        // Snapshot the order of items so we can mutate the containing
1053        // HashMaps inside the loop.
1054        let refs: Vec<FlowItemRef> = self
1055            .flow_order
1056            .iter()
1057            .map(|item| match item {
1058                FlowItem::Block { block_id, .. } => FlowItemRef::Block(*block_id),
1059                FlowItem::Table { table_id, .. } => FlowItemRef::Table(*table_id),
1060                FlowItem::Frame { frame_id, .. } => FlowItemRef::Frame(*frame_id),
1061            })
1062            .collect();
1063        let mut found = false;
1064        for r in refs {
1065            if found {
1066                match r {
1067                    FlowItemRef::Block(id) => {
1068                        if let Some(b) = self.blocks.get_mut(&id) {
1069                            b.position = apply_char_delta(b.position, char_delta);
1070                        }
1071                    }
1072                    FlowItemRef::Table(id) => {
1073                        if let Some(t) = self.tables.get_mut(&id) {
1074                            shift_block_positions_in_table(t, char_delta);
1075                        }
1076                    }
1077                    FlowItemRef::Frame(id) => {
1078                        if let Some(f) = self.frames.get_mut(&id) {
1079                            shift_block_positions_in_frame(f, char_delta);
1080                        }
1081                    }
1082                }
1083            } else if r == target {
1084                found = true;
1085            }
1086        }
1087    }
1088
1089    /// Shift document positions after an edit inside a top-level table's
1090    /// cell: cell blocks after the edited block within the table, then
1091    /// every flow item after the table.
1092    fn shift_block_positions_after_table_block(
1093        &mut self,
1094        table_id: usize,
1095        block_id: usize,
1096        char_delta: isize,
1097    ) {
1098        if char_delta == 0 {
1099            return;
1100        }
1101        if let Some(table) = self.tables.get_mut(&table_id) {
1102            shift_table_positions_after_block(table, block_id, char_delta);
1103        }
1104        self.shift_block_positions_after_flow_item(FlowItemRef::Table(table_id), char_delta);
1105    }
1106
1107    /// Shift document positions after an edit inside a frame (any depth):
1108    /// frame content after the edited block, then every flow item after
1109    /// the frame.
1110    fn shift_block_positions_after_frame_block(
1111        &mut self,
1112        frame_id: usize,
1113        block_id: usize,
1114        char_delta: isize,
1115    ) {
1116        if char_delta == 0 {
1117            return;
1118        }
1119        if let Some(frame) = self.frames.get_mut(&frame_id) {
1120            shift_frame_positions_after_block(frame, block_id, char_delta);
1121        }
1122        self.shift_block_positions_after_flow_item(FlowItemRef::Frame(frame_id), char_delta);
1123    }
1124
1125    /// Shift all flow items after the given block by `delta` pixels.
1126    fn shift_items_after_block(&mut self, block_id: usize, delta: f32) {
1127        if delta.abs() <= 0.001 {
1128            return;
1129        }
1130        let mut found = false;
1131        for item in &mut self.flow_order {
1132            match item {
1133                FlowItem::Block {
1134                    block_id: id, y, ..
1135                } => {
1136                    if found {
1137                        *y += delta;
1138                        if let Some(b) = self.blocks.get_mut(id) {
1139                            b.y += delta;
1140                        }
1141                    }
1142                    if *id == block_id {
1143                        found = true;
1144                    }
1145                }
1146                FlowItem::Table {
1147                    table_id: id, y, ..
1148                } => {
1149                    if found {
1150                        *y += delta;
1151                        if let Some(t) = self.tables.get_mut(id) {
1152                            t.y += delta;
1153                        }
1154                    }
1155                }
1156                FlowItem::Frame {
1157                    frame_id: id, y, ..
1158                } => {
1159                    if found {
1160                        *y += delta;
1161                        if let Some(f) = self.frames.get_mut(id) {
1162                            f.y += delta;
1163                        }
1164                    }
1165                }
1166            }
1167        }
1168        self.content_height += delta;
1169    }
1170
1171    /// Shift all flow items after the given table by `delta` pixels.
1172    fn shift_items_after_table(&mut self, table_id: usize, delta: f32) {
1173        if delta.abs() <= 0.001 {
1174            return;
1175        }
1176        let mut found = false;
1177        for item in &mut self.flow_order {
1178            match item {
1179                FlowItem::Table {
1180                    table_id: id, y, ..
1181                } => {
1182                    if *id == table_id {
1183                        found = true;
1184                        continue;
1185                    }
1186                    if found {
1187                        *y += delta;
1188                        if let Some(t) = self.tables.get_mut(id) {
1189                            t.y += delta;
1190                        }
1191                    }
1192                }
1193                FlowItem::Block {
1194                    block_id: id, y, ..
1195                } => {
1196                    if found {
1197                        *y += delta;
1198                        if let Some(b) = self.blocks.get_mut(id) {
1199                            b.y += delta;
1200                        }
1201                    }
1202                }
1203                FlowItem::Frame {
1204                    frame_id: id, y, ..
1205                } => {
1206                    if found {
1207                        *y += delta;
1208                        if let Some(f) = self.frames.get_mut(id) {
1209                            f.y += delta;
1210                        }
1211                    }
1212                }
1213            }
1214        }
1215        self.content_height += delta;
1216    }
1217
1218    /// Shift all flow items after the given frame by `delta` pixels.
1219    fn shift_items_after_frame(&mut self, frame_id: usize, delta: f32) {
1220        if delta.abs() <= 0.001 {
1221            return;
1222        }
1223        let mut found = false;
1224        for item in &mut self.flow_order {
1225            match item {
1226                FlowItem::Frame {
1227                    frame_id: id, y, ..
1228                } => {
1229                    if *id == frame_id {
1230                        found = true;
1231                        continue;
1232                    }
1233                    if found {
1234                        *y += delta;
1235                        if let Some(f) = self.frames.get_mut(id) {
1236                            f.y += delta;
1237                        }
1238                    }
1239                }
1240                FlowItem::Block {
1241                    block_id: id, y, ..
1242                } => {
1243                    if found {
1244                        *y += delta;
1245                        if let Some(b) = self.blocks.get_mut(id) {
1246                            b.y += delta;
1247                        }
1248                    }
1249                }
1250                FlowItem::Table {
1251                    table_id: id, y, ..
1252                } => {
1253                    if found {
1254                        *y += delta;
1255                        if let Some(t) = self.tables.get_mut(id) {
1256                            t.y += delta;
1257                        }
1258                    }
1259                }
1260            }
1261        }
1262        self.content_height += delta;
1263    }
1264
1265    /// Update the cached max content width considering a single block's lines.
1266    fn update_max_width_for_block(&mut self, block: &BlockLayout) {
1267        let w = block_max_width(block);
1268        if w > self.cached_max_content_width {
1269            self.cached_max_content_width = w;
1270        }
1271    }
1272
1273    /// Find the bottom margin of the block immediately before `block_id` in flow order.
1274    fn prev_block_bottom_margin(&self, block_id: usize) -> Option<f32> {
1275        let mut prev_bm = None;
1276        for item in &self.flow_order {
1277            match item {
1278                FlowItem::Block { block_id: id, .. } => {
1279                    if *id == block_id {
1280                        return prev_bm;
1281                    }
1282                    if let Some(b) = self.blocks.get(id) {
1283                        prev_bm = Some(b.bottom_margin);
1284                    }
1285                }
1286                _ => {
1287                    // Non-block items reset margin collapsing
1288                    prev_bm = None;
1289                }
1290            }
1291        }
1292        None
1293    }
1294}
1295
1296#[derive(Clone, Copy, PartialEq, Eq)]
1297enum FlowItemRef {
1298    Block(usize),
1299    Table(usize),
1300    Frame(usize),
1301}
1302
1303fn block_char_len(block: Option<&BlockLayout>) -> usize {
1304    block
1305        .and_then(|b| b.lines.last().map(|l| l.char_range.end))
1306        .unwrap_or(0)
1307}
1308
1309fn apply_char_delta(position: usize, delta: isize) -> usize {
1310    if delta >= 0 {
1311        position + delta as usize
1312    } else {
1313        position.saturating_sub((-delta) as usize)
1314    }
1315}
1316
1317fn shift_block_positions_in_slice(blocks: &mut [BlockLayout], delta: isize) {
1318    for block in blocks {
1319        block.position = apply_char_delta(block.position, delta);
1320    }
1321}
1322
1323fn shift_block_positions_in_table(table: &mut TableLayout, delta: isize) {
1324    for cell in &mut table.cell_layouts {
1325        shift_block_positions_in_slice(&mut cell.blocks, delta);
1326    }
1327}
1328
1329fn shift_block_positions_in_frame(frame: &mut FrameLayout, delta: isize) {
1330    shift_block_positions_in_slice(&mut frame.blocks, delta);
1331    for table in &mut frame.tables {
1332        shift_block_positions_in_table(table, delta);
1333    }
1334    for nested in &mut frame.frames {
1335        shift_block_positions_in_frame(nested, delta);
1336    }
1337}
1338
1339/// Shift the `position` of every cell block that comes after `block_id`
1340/// within `table` (cells iterate in document/row-major order). Returns
1341/// `true` when the edited block was found in this table.
1342fn shift_table_positions_after_block(
1343    table: &mut TableLayout,
1344    block_id: usize,
1345    delta: isize,
1346) -> bool {
1347    let mut found = false;
1348    for cell in &mut table.cell_layouts {
1349        for b in &mut cell.blocks {
1350            if found {
1351                b.position = apply_char_delta(b.position, delta);
1352            } else if b.block_id == block_id {
1353                found = true;
1354            }
1355        }
1356    }
1357    found
1358}
1359
1360/// Shift the `position` of every block that comes after `block_id` in
1361/// `frame`'s document order — walking `flow_order` so interleaved blocks,
1362/// tables, and nested frames shift correctly. Returns `true` when the
1363/// edited block was found in this frame tree.
1364fn shift_frame_positions_after_block(
1365    frame: &mut FrameLayout,
1366    block_id: usize,
1367    delta: isize,
1368) -> bool {
1369    let order = frame.flow_order.clone();
1370    let mut found = false;
1371    for child in &order {
1372        match child {
1373            crate::layout::frame::FrameChildRef::Block(bid) => {
1374                if found {
1375                    if let Some(b) = frame.blocks.iter_mut().find(|b| b.block_id == *bid) {
1376                        b.position = apply_char_delta(b.position, delta);
1377                    }
1378                } else if *bid == block_id {
1379                    found = true;
1380                }
1381            }
1382            crate::layout::frame::FrameChildRef::Table(tid) => {
1383                if let Some(t) = frame.tables.iter_mut().find(|t| t.table_id == *tid) {
1384                    if found {
1385                        shift_block_positions_in_table(t, delta);
1386                    } else {
1387                        found = shift_table_positions_after_block(t, block_id, delta);
1388                    }
1389                }
1390            }
1391            crate::layout::frame::FrameChildRef::Frame(fid) => {
1392                if let Some(nested) = frame.frames.iter_mut().find(|f| f.frame_id == *fid) {
1393                    if found {
1394                        shift_block_positions_in_frame(nested, delta);
1395                    } else {
1396                        found = shift_frame_positions_after_block(nested, block_id, delta);
1397                    }
1398                }
1399            }
1400        }
1401    }
1402    found
1403}
1404
1405// ── Paint-overlay helpers (recolor without reshape/reflow) ──────────────────
1406
1407/// Re-derive `b` in place from its base + pending overlay. No-op if no base
1408/// was captured for it.
1409///
1410/// The base supplies the *shaped* output — runs, glyphs, line breaks — which is
1411/// what a recolor re-derives. It does **not** supply where the block sits.
1412///
1413/// Those are two different lifetimes. A base is captured when its own block is
1414/// laid out, but a block's placement changes without it being laid out at all:
1415/// an edit anywhere above shifts every later block's document-character
1416/// `position` and its `y`, live, through `shift_block_positions_after_block` and
1417/// `shift_items_after_block` — neither of which re-captures the bases they
1418/// invalidate. `apply_paint_spans` opens with `base.clone()`, so overlaying
1419/// without care puts a block back where it was before an edit it was never part
1420/// of. `hit_test` and `caret_rect` read `position` straight, so from then on a
1421/// click near that block landed N characters early and its selection highlights
1422/// painted N characters off — N being however many characters had been typed
1423/// above it. Only a full relayout recovered.
1424///
1425/// Carrying the live placement across is the whole fix: it is exactly the two
1426/// fields the shift functions own, and the live block is never the staler of the
1427/// two — a relayout of this block refreshes its base from it.
1428fn overlay_block_in_place(
1429    b: &mut BlockLayout,
1430    base: &HashMap<usize, BlockLayout>,
1431    pending: &HashMap<usize, Vec<PaintSpan>>,
1432) {
1433    if let Some(base_b) = base.get(&b.block_id) {
1434        let empty: Vec<PaintSpan> = Vec::new();
1435        let spans = pending.get(&b.block_id).unwrap_or(&empty);
1436        let (position, y) = (b.position, b.y);
1437        *b = apply_paint_spans(base_b, spans);
1438        b.position = position;
1439        b.y = y;
1440    }
1441}
1442
1443/// Re-derive every block in a frame (recursively) from base + pending.
1444fn overlay_frame_in_place(
1445    frame: &mut FrameLayout,
1446    base: &HashMap<usize, BlockLayout>,
1447    pending: &HashMap<usize, Vec<PaintSpan>>,
1448) {
1449    for b in &mut frame.blocks {
1450        overlay_block_in_place(b, base, pending);
1451    }
1452    for t in &mut frame.tables {
1453        for c in &mut t.cell_layouts {
1454            for b in &mut c.blocks {
1455                overlay_block_in_place(b, base, pending);
1456            }
1457        }
1458    }
1459    for nested in &mut frame.frames {
1460        overlay_frame_in_place(nested, base, pending);
1461    }
1462}
1463
1464/// Re-derive a single block (by id) inside a frame (recursively). Returns true
1465/// if found.
1466fn overlay_one_in_frame(
1467    frame: &mut FrameLayout,
1468    block_id: usize,
1469    base: &HashMap<usize, BlockLayout>,
1470    pending: &HashMap<usize, Vec<PaintSpan>>,
1471) -> bool {
1472    for b in &mut frame.blocks {
1473        if b.block_id == block_id {
1474            overlay_block_in_place(b, base, pending);
1475            return true;
1476        }
1477    }
1478    for t in &mut frame.tables {
1479        for c in &mut t.cell_layouts {
1480            for b in &mut c.blocks {
1481                if b.block_id == block_id {
1482                    overlay_block_in_place(b, base, pending);
1483                    return true;
1484                }
1485            }
1486        }
1487    }
1488    for nested in &mut frame.frames {
1489        if overlay_one_in_frame(nested, block_id, base, pending) {
1490            return true;
1491        }
1492    }
1493    false
1494}
1495
1496/// Find a block by id across top-level / table cells / frames.
1497/// Widest laid-out line of `block`, margins included.
1498///
1499/// The single definition of "how wide is this block", shared by the running
1500/// maximum (`update_max_width_for_block`) and the re-derivation eviction needs
1501/// (`recompute_max_content_width`), so the two cannot drift apart and disagree
1502/// about the horizontal scroll range.
1503fn block_max_width(block: &BlockLayout) -> f32 {
1504    block
1505        .lines
1506        .iter()
1507        .map(|line| line.width + block.left_margin + block.right_margin)
1508        .fold(0.0_f32, f32::max)
1509}
1510
1511pub(crate) fn find_block_ref(flow: &FlowLayout, block_id: usize) -> Option<&BlockLayout> {
1512    if let Some(b) = flow.blocks.get(&block_id) {
1513        return Some(b);
1514    }
1515    for t in flow.tables.values() {
1516        for c in &t.cell_layouts {
1517            for b in &c.blocks {
1518                if b.block_id == block_id {
1519                    return Some(b);
1520                }
1521            }
1522        }
1523    }
1524    for f in flow.frames.values() {
1525        if let Some(b) = find_block_in_frame(f, block_id) {
1526            return Some(b);
1527        }
1528    }
1529    None
1530}
1531
1532fn find_block_in_frame(frame: &FrameLayout, block_id: usize) -> Option<&BlockLayout> {
1533    for b in &frame.blocks {
1534        if b.block_id == block_id {
1535            return Some(b);
1536        }
1537    }
1538    for t in &frame.tables {
1539        for c in &t.cell_layouts {
1540            for b in &c.blocks {
1541                if b.block_id == block_id {
1542                    return Some(b);
1543                }
1544            }
1545        }
1546    }
1547    for nested in &frame.frames {
1548        if let Some(b) = find_block_in_frame(nested, block_id) {
1549            return Some(b);
1550        }
1551    }
1552    None
1553}
1554
1555/// Check whether a frame (or any of its nested frames) contains a block
1556/// with the given id — including blocks inside cells of tables that are
1557/// direct children of the frame.
1558pub(crate) fn frame_contains_block(frame: &FrameLayout, block_id: usize) -> bool {
1559    if frame.blocks.iter().any(|b| b.block_id == block_id) {
1560        return true;
1561    }
1562    for table in &frame.tables {
1563        for cell in &table.cell_layouts {
1564            if cell.blocks.iter().any(|b| b.block_id == block_id) {
1565                return true;
1566            }
1567        }
1568    }
1569    frame
1570        .frames
1571        .iter()
1572        .any(|nested| frame_contains_block(nested, block_id))
1573}
1574
1575/// Where inside a frame a given block lives (one level deep — nested
1576/// frames are reported as `NestedFrame` and must be descended into).
1577pub(crate) enum FrameBlockLocation {
1578    /// A direct child block of the frame.
1579    DirectBlock,
1580    /// A block inside a cell of a table that is a direct child of the
1581    /// frame. Carries `(table_id, row, column)`.
1582    TableCell(usize, usize, usize),
1583    /// A block somewhere inside a nested frame (carries the nested
1584    /// frame's id).
1585    NestedFrame(usize),
1586}
1587
1588/// Locate `block_id` among the direct children of `frame`.
1589pub(crate) fn find_block_location_in_frame(
1590    frame: &FrameLayout,
1591    block_id: usize,
1592) -> Option<FrameBlockLocation> {
1593    if frame.blocks.iter().any(|b| b.block_id == block_id) {
1594        return Some(FrameBlockLocation::DirectBlock);
1595    }
1596    for table in &frame.tables {
1597        for cell in &table.cell_layouts {
1598            if cell.blocks.iter().any(|b| b.block_id == block_id) {
1599                return Some(FrameBlockLocation::TableCell(
1600                    table.table_id,
1601                    cell.row,
1602                    cell.column,
1603                ));
1604            }
1605        }
1606    }
1607    for nested in &frame.frames {
1608        if frame_contains_block(nested, block_id) {
1609            return Some(FrameBlockLocation::NestedFrame(nested.frame_id));
1610        }
1611    }
1612    None
1613}
1614
1615/// Replace a direct child block of `frame` and re-stack the frame's
1616/// children. The caller is responsible for routing blocks that live in
1617/// nested frames or table cells (see `relayout_block_deep_in_frame`) —
1618/// the block must have been laid out at this frame's `content_width`.
1619fn relayout_block_in_frame(frame: &mut FrameLayout, block_id: usize, new_block: BlockLayout) {
1620    if let Some(old) = frame.blocks.iter_mut().find(|b| b.block_id == block_id) {
1621        *old = new_block;
1622    }
1623    reposition_frame_children(frame);
1624}
1625
1626/// Relayout the block identified by `params.block_id` wherever it lives
1627/// inside `frame`: as a direct block, inside a cell of a frame-nested
1628/// table, or anywhere within a nested frame (recursing to any depth).
1629/// Each level re-stacks its children in flow order on the way back up,
1630/// so height changes propagate to the outermost frame's `total_height`.
1631fn relayout_block_deep_in_frame(
1632    frame: &mut FrameLayout,
1633    registry: &FontRegistry,
1634    params: &BlockLayoutParams,
1635    scale_factor: f32,
1636    font_scale: f32,
1637) {
1638    match find_block_location_in_frame(frame, params.block_id) {
1639        None => {}
1640        Some(FrameBlockLocation::DirectBlock) => {
1641            let new_block = layout_block(
1642                registry,
1643                params,
1644                frame.content_width,
1645                scale_factor,
1646                font_scale,
1647            );
1648            relayout_block_in_frame(frame, params.block_id, new_block);
1649        }
1650        Some(FrameBlockLocation::TableCell(table_id, row, col)) => {
1651            if let Some(table) = frame.tables.iter_mut().find(|t| t.table_id == table_id) {
1652                recompute_table_cell(table, registry, params, row, col, scale_factor, font_scale);
1653            }
1654            reposition_frame_children(frame);
1655        }
1656        Some(FrameBlockLocation::NestedFrame(nested_frame_id)) => {
1657            if let Some(nested) = frame
1658                .frames
1659                .iter_mut()
1660                .find(|f| f.frame_id == nested_frame_id)
1661            {
1662                relayout_block_deep_in_frame(nested, registry, params, scale_factor, font_scale);
1663            }
1664            reposition_frame_children(frame);
1665        }
1666    }
1667}
1668
1669/// Re-layout the block identified by `params.block_id` inside the cell at
1670/// `(row, col)`, then recompute the row height, row y positions, and the
1671/// table's `total_height`. Shared by the top-level table relayout path and
1672/// the frame-nested one; the caller propagates the height delta into its
1673/// own container.
1674fn recompute_table_cell(
1675    table: &mut crate::layout::table::TableLayout,
1676    registry: &FontRegistry,
1677    params: &BlockLayoutParams,
1678    row: usize,
1679    col: usize,
1680    scale_factor: f32,
1681    font_scale: f32,
1682) {
1683    let cell_width = table
1684        .column_content_widths
1685        .get(col)
1686        .copied()
1687        .unwrap_or(200.0);
1688
1689    // Find the cell and replace the block
1690    let cell = match table
1691        .cell_layouts
1692        .iter_mut()
1693        .find(|c| c.row == row && c.column == col)
1694    {
1695        Some(c) => c,
1696        None => return,
1697    };
1698
1699    let new_block = layout_block(registry, params, cell_width, scale_factor, font_scale);
1700    if let Some(old) = cell
1701        .blocks
1702        .iter_mut()
1703        .find(|b| b.block_id == params.block_id)
1704    {
1705        *old = new_block;
1706    }
1707
1708    // Reposition blocks within the cell and recompute cell height
1709    let mut block_y = 0.0f32;
1710    for block in &mut cell.blocks {
1711        block.y = block_y;
1712        block_y += block.height;
1713    }
1714    let cell_height = block_y;
1715
1716    // Recompute row height by scanning all cells in this row
1717    if row < table.row_heights.len() {
1718        let mut max_h = 0.0f32;
1719        for c in &table.cell_layouts {
1720            if c.row == row {
1721                let h: f32 = c.blocks.iter().map(|b| b.height).sum();
1722                max_h = max_h.max(h);
1723            }
1724        }
1725        // Also consider the cell we just updated
1726        max_h = max_h.max(cell_height);
1727        table.row_heights[row] = max_h;
1728    }
1729
1730    // Recompute row y positions and total height
1731    let border = table.border_width;
1732    let padding = table.cell_padding;
1733    let spacing = if table.row_ys.len() > 1 {
1734        // Infer spacing from existing layout
1735        if table.row_ys.len() >= 2 && !table.row_heights.is_empty() {
1736            let expected = table.row_ys[0] + padding + table.row_heights[0] + padding;
1737            (table.row_ys.get(1).copied().unwrap_or(expected) - expected).max(0.0)
1738        } else {
1739            0.0
1740        }
1741    } else {
1742        0.0
1743    };
1744    let mut y = border;
1745    for (r, &row_h) in table.row_heights.iter().enumerate() {
1746        if r < table.row_ys.len() {
1747            table.row_ys[r] = y + padding;
1748        }
1749        y += padding * 2.0 + row_h;
1750        if r < table.row_heights.len() - 1 {
1751            y += spacing;
1752        }
1753    }
1754    table.total_height = y + border;
1755}
1756
1757/// Recompute the y position of every direct child of `frame` in document
1758/// (flow) order, then update `content_height` / `total_height`.
1759///
1760/// Walks `frame.flow_order` so interleaved children keep their document
1761/// order — stacking the per-kind vecs one after another would visually
1762/// reorder a frame containing e.g. [block, table, block]. Placement
1763/// mirrors `layout_frame` exactly: blocks at `content_y + top_margin`
1764/// (no collapsing between frame children), tables and nested frames at
1765/// `content_y` advancing by `total_height`.
1766pub(crate) fn reposition_frame_children(frame: &mut FrameLayout) {
1767    let old_content_height = frame.content_height;
1768    let order = frame.flow_order.clone();
1769    let mut content_y = 0.0f32;
1770
1771    for child in &order {
1772        match child {
1773            crate::layout::frame::FrameChildRef::Block(bid) => {
1774                if let Some(block) = frame.blocks.iter_mut().find(|b| b.block_id == *bid) {
1775                    block.y = content_y + block.top_margin;
1776                    let block_content = block.height - block.top_margin - block.bottom_margin;
1777                    content_y = block.y + block_content + block.bottom_margin;
1778                }
1779            }
1780            crate::layout::frame::FrameChildRef::Table(tid) => {
1781                if let Some(table) = frame.tables.iter_mut().find(|t| t.table_id == *tid) {
1782                    table.y = content_y;
1783                    content_y += table.total_height;
1784                }
1785            }
1786            crate::layout::frame::FrameChildRef::Frame(fid) => {
1787                if let Some(nested) = frame.frames.iter_mut().find(|f| f.frame_id == *fid) {
1788                    nested.y = content_y;
1789                    content_y += nested.total_height;
1790                }
1791            }
1792        }
1793    }
1794
1795    frame.content_height = content_y;
1796    frame.total_height += content_y - old_content_height;
1797}
1798
1799impl FlowLayout {
1800    /// Find a block's layout by id wherever it lives — the document's own
1801    /// column, a table cell, or a frame at any depth — with the origin its
1802    /// coordinates are measured from.
1803    ///
1804    /// The flat `blocks` map is tried first, so the common case stays a
1805    /// single hash lookup and only a nested block pays for the walk.
1806    pub fn resolve_block(&self, block_id: usize) -> Option<ResolvedBlock<'_>> {
1807        if let Some(block) = self.blocks.get(&block_id) {
1808            return Some(ResolvedBlock {
1809                block,
1810                origin_x: 0.0,
1811                origin_y: 0.0,
1812            });
1813        }
1814        for table in self.tables.values() {
1815            if let Some(found) = resolve_block_in_table(table, block_id, 0.0, 0.0) {
1816                return Some(found);
1817            }
1818        }
1819        for frame in self.frames.values() {
1820            if let Some(found) = resolve_block_in_frame(frame, block_id, 0.0, 0.0) {
1821                return Some(found);
1822            }
1823        }
1824        None
1825    }
1826
1827    /// Find a table's layout by id — at the top level or inside a frame at
1828    /// any depth — with the document-space origin `column_xs` / `row_ys` are
1829    /// measured from.
1830    pub fn resolve_table(&self, table_id: usize) -> Option<ResolvedTable<'_>> {
1831        if let Some(table) = self.tables.get(&table_id) {
1832            return Some(ResolvedTable {
1833                table,
1834                origin_x: 0.0,
1835                origin_y: table.y,
1836            });
1837        }
1838        for frame in self.frames.values() {
1839            if let Some(found) = resolve_table_in_frame(frame, table_id, 0.0, 0.0) {
1840                return Some(found);
1841            }
1842        }
1843        None
1844    }
1845}