0005. Incremental layout: identity caches, resume, convergence, page reuse

• Status: Accepted
• Date: 2026-10-01 (recorded with the book-scale performance work, commit 85a3605)

Context

The benchmark is a generated book of 7,314 pages and 35,019 blocks. Laying out and redrawing everything on every keystroke cost 49 ms in the engine alone and 209 ms from keydown to a painted frame, with a 3.4 GB heap. The first non-negotiable is that an edit does work proportional to what it changed.

Decision

Layout is incremental at three levels, all keyed on object identity (nodes are immutable, see 0001):

1. Measurement: LayoutCache maps block node → Flow (per width, direction and page height). Unchanged blocks are never re-measured.
2. Pagination: given the previous layout, the unchanged prefix and suffix of top-level blocks are found by identity. Leading pages that can't see the edit are kept, pagination resumes at the first affected page, and it stops when it converges: pagination is memoryless given (start, carry, capacity), so once a new page starts where an old page started (shifted by the edit's height change) inside the unchanged suffix, the old tail is reused, shifted.
3. Pages: unchanged pages are returned as the same PageLayout objects (signature comparison, or known-identical content re-wrapped when only the page number changed), with lazy, non-enumerable fragments and chrome.

Correctness is pinned by a randomized test: 300 random edits, each incremental layout compared with a fresh full layout.

Consequences

• Keystroke engine time fell from 49 ms to 9.5 ms and keydown-to-frame from 209 ms to 28 ms; Enter (shifting every later block) from 731 ms to 50 ms; heap from 3.4 GB to ~460 MB.
• Renderers skip unchanged pages by identity; the position index caches per page object, so it survives edits too.
• Hosts must pass the same cache and the previous layout, and keep layout inputs (theme, renderer maps, header/footer config) stable by identity.
• Closures that pages keep must be created at module level: closures created in the build scope chained every previous layout generation in memory. Lazy getters must be non-enumerable so generic walkers don't materialize pages.
• O(blocks) bookkeeping remains per edit (prefix/suffix scan, offsets, ProseMirror's flat array); Word-like section nodes are the planned fix.