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