Bound the tail for long open lists/blockquotes (frozen/tail v2)

[jonathanKingston]

Type: performance · Area: src/streaming-frozen-tail.ts · Follow-up to #21 / #23

Summary

The frozen/tail split (#23) makes committed-prefix rendering O(tail) per commit — except when the trailing top-level group never settles. settledTailStart keeps an entire open list (or blockquote) in the tail because a later item can still change it, so streaming a single long top-level list re-renders/re-sanitizes/re-morphs the whole list on every item commit. That is the old O(n²) behaviour for arguably the most common long LLM output shape (a bulleted list). Correct output, but no speedup for list-dominated content.

Documented as a known bound in the streaming-frozen-tail.ts header today.

Why it's hard

The current frozen region is a whole number of top-level group nodes (a <ul> is one node). Bounding a list's tail means freezing individual <li> nodes inside a shared <ul>, which the top-level-boundary mechanism can't express — rendering the tail <li>s separately would emit a second <ul>.

Two correctness hazards:

1. Tight → loose flip. Loose/tight is a whole-list property (collectListGroup, render-blocks.ts). A frozen tight prefix becomes wrong the moment a blank-separated continuation makes the list loose (items gain <p> wrappers). So a tight list's items can never be frozen while the list is still open.
2. Same-list continuation across blanks (#306) — a blank run followed by a same-marker item continues the list, so "the list ended" is only knowable after a non-continuing block.

Sketch

• Introduce a sub-group freezing mode: the frozen region may end inside a trailing <ul>/<ol>, and the tail morph appends <li>s into that existing list element instead of creating a new one.
• Only engage it once the list is provably loose (a blank-separated continuation has been observed → loose is monotonic for that list), so a frozen item renders identically (loose) whether frozen or in-tail. Tight lists stay wholly in the tail.
• Add a list-looseness analogue of the tokenStraddles guard: if the observed looseness or marker type flips against a frozen assumption, fall back to full morph.
• Same parity-first method as perf(streaming): incremental committed-prefix rendering (fixes #21) #23: assert byte-identity across the baseline corpus and exhaustive convergence fuzz before wiring in, behind the full-morph fallback.

Acceptance

• Streaming a 1,000-item top-level list grows sub-quadratically (add a scaling case to bench-streaming.mts).
• Byte-identical to the at-rest render at every committed frame; exhaustive convergence fuzz passes.
• Tight-list, loose-flip, marker-change, and blank-run-continuation cases covered by targeted tests.

References

• src/streaming-frozen-tail.ts — settledTailStart, isMultiTokenGroupKind, FrozenTailRenderer.update
• src/render-blocks.ts — collectListGroup (loose/tight, #306), collectBlockquoteGroup

[jonathanKingston]

Design note: the blocker is the morph target, not the settle logic

Worked through the mechanics. The settle-logic side is tractable — list looseness is monotonic (once any two items are blank-separated or an item has multiple paragraphs, the list is loose forever), so the safe rule is: freeze item prefixes only once the list is provably loose, or freeze tight optimistically and take a one-time full-morph fallback on the loose-flip (each list flips at most once → amortized O(n)).

The real blocker is structural, in the DOM layer:

• Today the frozen region is a whole number of direct children of completedEl; morphInnerHtmlFrom(container, startIndex, html) reconciles completedEl's direct children from an offset. A <ul> is one such child.
• Bounding a list's tail means the trailing frozen node is a <ul> holding the frozen <li>s, and the tail render must append more <li>s into that same <ul> — not as a sibling of it. morphInnerHtmlFrom can't express "reconcile the children of the last frozen element from an offset."

So #29 needs a morph-model extension: when the trailing frozen node is a list, the tail reconciles inside that <ul>/<ol> (its <li> children from an offset) rather than against completedEl's children — plus frozenNodeCount becomes two-level (frozen top-level nodes + frozen <li>s inside the trailing list). That's the crux to design first; the looseness/settle rules are the easy part.

Prerequisite: this is cleaner on top of #32 item 2 (a shared top-level group-segmentation primitive), so settledTailStart and the new intra-list boundary share one source of truth.

---

Generated by Claude Code

[jonathanKingston]

Implementation plan (v1, tight-optimistic)

Worked this out to implementable depth. Supersedes the earlier design note; the morph-model observation there stands, this fills in the rest.

Why per-item freezing is unavoidable

Checked and rejected the cheaper alternatives:

• Two sibling lists (frozen <ul> + tail <ul>) — breaks byte-parity: renderMarkdown emits ONE <ul>.
• Checkpointing (re-render whole list every K items, keep whole list in tail between checkpoints) — between checkpoints the tail is still O(list), so it's O(n²/K) at best and still needs partial-list rendering to do better. Dead end.

So: frozen <li>s and tail <li>s must share one <ul>, and the per-commit render must produce an item slice, not a whole list.

The two primitives to build

1. render-blocks.ts: export an item-slice renderer — renderListItemsSlice(source, itemTokens, loose, linkRefs): { itemsHtml, anyTask }, reusing the existing renderListItemContent/renderListItem internals, plus the list-continuation predicate (continuesList: same ordered-ness, marker char, delimiter). This is the real Structural cleanup from #23 review (shared render opts, group segmentation, split return type) #32-item-2 sharing — exported where it's consumed, no dead code.
2. streaming-dom-morph.ts / frozen-tail: intra-list morph — morphChildren already takes an offset, so the mechanism exists. Per commit: build the template as the sanitized wrapped list <ul …>${itemsHtml}</ul> (sanitizing bare <li> fragments risks parser-context surprises; wrapping keeps DOMPurify's parse context correct), sync the real <ul>'s attributes from the template root (class can legitimately change — see task-list below), then morphChildren(realUl, templateUl, frozenLiCount).

State (extends FrozenTailRenderer)

frozenLiCount (frozen <li> children of the trailing shared list), frozenListLoose (looseness baked into frozen items), frozenListHasTask, frozenListOrdered/startAttr (open-tag identity, fixed by the first frozen item). frozenEnd generalizes cleanly: it lands on a list_item token boundary (items are separate tokens), so the existing tokenStraddles + frozenSource.startsWith + link-ref guards all keep working unchanged.

Freeze rule

Freeze items [groupStart, lastItem) — everything but the last item, which can still absorb lazy/indented continuations (an earlier item's token extending anyway trips tokenStraddles → fallback). Blanks between items live in the tail (they carry the loose evidence).

The three monotonic properties that make it safe

• Looseness is monotonic: evidence (blank-separated items, multi-paragraph item) only accumulates as source is append-only within the frozen region. Per-commit check is O(tail): frozenListLoose || tailSliceHasLooseEvidence (evidence can only appear in the not-yet-frozen slice + the boundary blank, which is in the tail).
• Tight→loose flip (the one hazard): frozen tight <li>x</li> vs required loose <li><p>x</p></li>. Detect via the check above → one-time full-morph fallback per list (loose never reverts) → amortized O(n).
• Task-list class is monotonic-additive: a new checkbox item flips the shared <ul> class — handled by the attribute sync (the <ul> element is not frozen; only its leading <li>s are).

Marker/delimiter change in a tail item = the list actually ends there (new group) → continuesList fails → full-morph fallback, then normal top-level settling takes over. Rare, correct.

Settle transition

When the list finally settles (blank + non-continuing block), the delta [frozenEnd → settledOffset) begins with remaining items of the shared list — so the delta path must also use the item-slice renderer for the leading list portion before falling back to renderBlocks for the rest. This is the fiddliest integration point; the parity oracle (byte-identity at every committed frame) is the test for it.

Order of work

1. Land refactor(streaming): compile-enforced settle classification + review dedups #36 (compile-enforced settle classes — the boundary this builds on).
2. renderListItemsSlice + continuesList export, with unit parity tests (slice render == whole-list render sliced, both loose and tight).
3. Intra-list state machine behind the existing full-morph fallback, parity-first: corpus byte-identity at every committed frame + exhaustive convergence fuzz + targeted tests (tight→loose flip, marker change, task-class flip, lazy continuation into last item, settle transition).
4. Bench: add a 500/1000-item single-list scaling case; acceptance is ~2×/doubling on it (it's ~4× today).

Scope call: tight-optimistic (freeze tight lists, one-time fallback on flip) rather than loose-only — tight lists are the common LLM shape, and the flip cost is amortized O(n) by monotonicity.

---

Generated by Claude Code