Skip to content

Commit 78d0d4c

Browse files
perf(html): stream the SourceProcessor walk and recycle completed subtrees (#21595)
* perf(html): stream the SourceProcessor walk and recycle completed subtrees Visit and release each completed subtree during tree construction instead of materializing the whole document first, so peak node storage tracks the open subtree rather than the document. Flushing is gated on an empty active formatting elements list, which also covers table markers, so neither the adoption agency nor foster parenting can reach an already-flushed node; unsafe stretches buffer and the next catch-up sees the final tree. Skip the input-length column pre-sizing when streaming — it allocated orders of magnitude more than a streamed parse ever uses. Only walk-only passes stream; printing holds every node's text until its parent prints, so `minimize` still builds the tree and walks it. `parseHtml` itself is unchanged. On the 2.33 MiB benchmark document with `skip.text`: peak live AST 10.19 -> 1.26 MiB, parse+walk 125.1 -> 104.6 ms. INCOMPLETE — do not merge. A pre-order `enter` cannot observe post-order facts, so an element still on the open stack reports a provisional `end`, `firstChild` and `nextSibling`. HtmlGenerator and HtmlParser read `end` on Element enter for the head/body injection anchors and must move to `exit`, and HtmlSyntax.unittest.js currently has 1 failing case (`firstChild`). * perf(html): cut the per-token cost of the streamed walk Bail out of the sync before the safety check on the common token shape (open stack untouched, nothing completed under the current element), and replace the O(depth) reconcile scan with a suffix scan, falling back to the full scan only when a mid-stack open.splice marks the stack dirty. Corrects the measurement in the previous commit. That 125.1 -> 104.6 ms compared two separate process runs and does not survive a controlled A/B; in child-process runs (median of 7) the streamed walk is still slower than the buffered one, by ~8-25% depending on document shape, after these two fixes cut it from ~25-35%. Memory is a large win: peak column bytes drop 54-85%. Still INCOMPLETE - the provisional-end breakage is unfixed. * fix(html): read post-order node facts on exit in the streamed walk An element is entered while it is still open, so its end offset and child links are not final there. Move HtmlGenerator's head/body injection anchors and its script/link/style/meta collection to exit, where end is final; script/link/style/meta never nest in each other, so source order is kept. Cover the streamed contract in the path-accessor test: a completed child subtree is visited and unlinked while its parent is still open, so child links read empty from either half of an element's visit - structure is read from parseHtml's materialized tree instead. HtmlParser's headLastEnd still reads end on enter. Moving it to exit regressed 25 CSS-link injection cases, so it needs its own investigation. * perf(html): batch streamed flushes behind a clamped allocator rewind A flush only earns its walk setup once enough has piled up under the current element, so the per-token cost drops from a flush attempt to a subtraction. Batching alone corrupted the tree: deferring flushes let the allocator rewind below an element that was still open, so the next mkEl aliased a live node and produced self-referential links (parent === firstChild === itself), which spun the walk forever. Route every rewind through _streamRewind, which never reclaims an id at or below the deepest open element, and only relocate a held-back trailing text node when it is the sole survivor above its parent so the id space keeps no gaps. Found with a temporary link validator (cycle / bad-parent / open-above-count) run over the html5lib tokenizer corpus plus 6000 seeded fuzz documents: 25612 parses, 0 violations. The differential against the buffered walk is unchanged at 590 mismatches, now all the inherent end-at-enter class. * perf(html): enter lazily and flush whole sibling runs in one walk Key the per-token gate on the deepest *entered* element rather than the deepest open one. The open stack changes on every start and end tag, so the old gate never engaged on shallow markup; keyed this way, an element that opens and closes inside the batch window is never entered at all and is later walked as one completed subtree. That is both cheaper and gives its visitors a final end offset - the differential against the buffered walk drops from 590 mismatches to 14. Flush a run of children with a single walk instead of a call per child, pick the run's stop node in O(1) from lastChild, and inline the gate into dispatch so an idle token costs three loads and a compare. Batch 4096 balances the two: on the nested benchmark document 6-15% faster than the buffered walk with ~85% less peak column memory; deep nesting is neutral. Pathologically flat markup (60k siblings under body) is still 5-13% slower - what is left there is the per-token gate itself, which stays even when the batch is raised until the memory win is gone. * perf(html): pre-size streamed columns up to one batch A streamed parse recycles each flushed subtree, so it was left to grow from the default capacity by doubling. A document that keeps everything open (deep nesting) still reaches the document's size, and doubling into it overshoots where one exact allocation would not - 5000 nested divs peaked at 0.74 MiB of columns against the buffered walk's 0.43 MiB. Apply the same input-length estimate, capped at what one batch can hold, so deep nesting matches the buffered peak exactly and wide documents keep the small streamed footprint. * refactor(html): drop the duplicate subtree walker and the held-node relocate _walkSubtree was _walkRun restricted to a single subtree - the printing path now calls _walkRun directly with the node's own parent and next sibling as the run bounds, so one walker covers both. The relocate existed to close the id-space gap a held-back trailing text node left behind. Since every rewind is clamped by _streamRewind that gap can no longer be reused by a live node, and dropping it changes nothing measurable: same 14 differential mismatches, same 2.35 MiB peak, same timings. * perf(html): drive the streamed walk from the open-stack pops Route every open-stack pop through popOpen, which marks the walk dirty, and have dispatch do one boolean test per token instead of re-deriving the whole gate. Only a stack change can complete a subtree, so the four-term gate was being recomputed on every token to answer a question that popOpen already knows - the CSS grammar gets the same effect from its onRule sink. The mark cannot do the work itself: an element's end offset is assigned after it is popped, so syncing inside popOpen visits it with a provisional end (it regressed the differential to a new mismatch class). The flag defers to the end of the token, where the end is final. This closes the flat-markup regression - 60k siblings under body go from ~13-20% slower than the buffered walk to ~6% faster, with peak columns still roughly halved. * test(html): cover final end offsets in the streamed walk HtmlParser folds a head element's end into its injection anchor at enter and consumes that anchor in the same visit, so a provisional end there would misplace injected tags. The streamed walk only starts once the parse reaches in-body, which is what keeps every head element a completed subtree with a final end - assert it directly so a change to that guard cannot silently break head injection. Restore the path-accessor test to its original enter-only form: entering lazily and driving the walk from the pops means an element is walked as a completed subtree, so its child links are live again at enter. * refactor(html): state the streamed walk's model and drop redundant flags Collapse _streaming / _streamRequested into one flag whose lifetime grammar owns through try/finally, so a thrown parse can no longer leak streaming into a later direct parseHtml call and the consume-once dance disappears. _openSpliced already implies a stack change, so the five sites that set both now set one and dispatch ORs them. Split _streamSync into named steps (prefix, close, open, flush) behind a comment that states the model up front: the walk follows the open element stack, an element is entered only when something beneath it must be flushed, and nothing is visited unless _canFlush() holds. Rename _streamSafe to _canFlush and _streamDirty to _openStackChanged so the vocabulary matches. No behaviour change: differential unchanged at 14, 452 unit tests pass, timings within noise. * fix(html): pair enter and exit under skipChildren in the streamed walk A descendant of a skipChildren() element is tracked on _entered without being entered, but the close path called _exitNode on it anyway, so exit fired with no matching enter once nesting was deep enough to stream mid-parse. The buffered walk fires exit for the skipped element itself and nothing below it; match that in both the sync and the EOF paths. Reported by Cursor Bugbot. Reattach the _streamFlush and _streamRewind JSDoc blocks, which an earlier edit left stacked above _walkRun - tsc reported five implicit-any parameters and failed lint. Add streamed-walk tests sized past the flush batch so the enter, flush, detach and recycle paths are exercised by the unit suite rather than only by integration: element visits stay balanced across batches, skipChildren pairs correctly (this case fails with 3635 unmatched exits without the fix above), adjacent text stays merged, and forms and tables stream. * fix(html): stop streaming when a splice removes an entered element A mid-stack open.splice takes an element off the stack without ending its subtree - </form> with a div still open inside it leaves the div live, nested in the form. Reconciling the entered stack against the open stack there treats the div as finished: it exits and detaches a live element, then enters it again, so visitors see a false close/reopen and later inserts hang off a detached subtree. Reported by Cursor Bugbot. Those splices are rare, so stop streaming for the rest of the parse instead of teaching the reconcile to model an insertion point that outlives its stack entry: what is already visited stays visited, and the remainder is walked at EOF. The same handling covers the adoption agency's splices, which drops the differential against the buffered walk from 14 mismatches to 0 - the streamed walk now matches it exactly across 25612 parses. The regression test asserts visit counts, not enter/exit pairing: the faulty sequence (+div -div -form +div) is balanced, so pairing alone cannot see it. * fix(html): only halt streaming for entered mid-stack removals The halt was set at every open.splice, which was far broader than the problem it guards. Two common shapes lost subtree recycling for the whole parse: </form> (any form, even when it is the stack top after implied end tags) and the afterHead reopen for a late link/meta/script/style. Both reported by Cursor Bugbot; the form case also showed up in a form-vs-form-free benchmark, where peak columns went 0.76 -> 4.58 MiB, cancelling the entire win. Route every stack removal through removeOpenAt, which halts only when the removed element was actually entered and still has open descendants above it. Removing the stack top is just a pop, and an element the walk never entered (anything opened while the active formatting elements list was non-empty, and everything in the head) costs it nothing. Forms and late head tags now stream again - both back to 0.76 MiB - and the re-visit regression test still passes, so the false close/reopen stays fixed. The differential goes back from 0 to 14 mismatches: the broad halt had masked them by not streaming at all. They are the inherent enter-time end offset on misnested li, and event counts match everywhere (0 cases differ), so no element is visited a different number of times. * perf(html): only stream the walk once a document is big enough Streaming every walk cost more than it saved on ordinary pages: a 72 KiB page is ~4.5k nodes, so the per-token sync and the flushes ran with nothing to reclaim. Measured against main on a realistic page shape, that was +6.6% at 142 KiB and +7.1% at 568 KiB, while the memory win only appeared past ~1 MiB per page. Start the walk unstreamed and switch it on once the document passes `_STREAM_MIN_NODES`; the first sync enters the open stack and flushes what already finished. Below the threshold a page is walked once at EOF, which is what it wanted anyway. Also stop capping the attribute estimate for a streamed parse. Attribute ids are never recycled (`_attrCount` only resets between parses), so the cap just forced the columns through the doubling cascade. The node cap stays under `_COLUMN_SHRINK_CAPACITY` so a streamed parse's columns are still reusable by the next parse. Peak parser columns over six 2.4 MiB pages: 19.2 MiB -> 5.8 MiB. Ordinary pages are byte-identical to main in both time and memory. * fix(html): release strings and walk state a streamed parse left behind Two retention regressions from hoisting the walk to module scope. `_releaseAstColumns` cleared `_nodeStrings` only up to `_nodeCount`, but streaming rewinds that counter as it recycles ids, so every string written above the final count stayed reachable. The streamed capacity is kept under `_COLUMN_SHRINK_CAPACITY` so the drop-the-array path never ran either. Measured on a 60k-paragraph document: 49,148 strings / 270,314 characters pinned after the parse returned, against zero on main. Track the id high-water mark and clear up to that instead. `grammar` also left the caller's compiled visitor map and print context in the module-scope `_visitors` / `_writer` after returning, keeping those closures alive until the next parse; they used to fall away with the call. Clear both in the `finally`. * fix(html): honour skipChildren() on the document root The walk-only path called `_enterNode(doc)` for its side effect and threw the return value away, then finished with `_streamFinish`, which flushes the root's children with visiting forced on. A `skipChildren()` in the document's `enter` was therefore ignored and the whole tree was visited — on every document, not just streamed ones. Against main, a four-element page went from 2 visits to 12, and a 120k-node one from 2 to 160,008. Stop the walk when the root's `enter` declines its children, leaving only the document's own `exit` to fire, which is what the pre-stream walk did. * fix(html): halt streaming on any mid-stack open-stack removal `removeOpenAt` only halted when the removed element was already entered. An element the walk had not entered yet is just as unsafe: it leaves the stack while descendants stay open, and the next sync enters those descendants against an open stack that no longer describes their parent. A document that crosses the streaming threshold before reaching `<form><div></form><p>y</p></div>` lost the div and its paragraph entirely — main visits eight nodes there, the streamed walk visited four. Key the halt on the mid-stack test alone. Removing the top of the stack, which is the common `</form>` after implied end tags, still streams: 40k forms retain 2.80 MiB against main's 9.50 MiB. * perf(html): print the document in pieces instead of composing it whole The printer built each node's text from its children's, so the print store held every node's string until the root was taken — several times the output for a document of any size, and the reason this branch's walk streaming is limited to walk-only passes. A node whose text is exactly `open + children + close` now emits its opener as it opens and its closer as it exits, and each child goes straight out as it finishes; the store only ever holds the subtrees that are not of that shape (a `<pre>` leading newline to round-trip, a `<template>`'s content fragment, a `/>` whose end tag depends on what printed inside it). An omitted `<html>` / `<body>` waits in the writer's pending stack, since it materializes only when the first thing inside it is whitespace. The walk is unchanged apart from carrying the open path's depth, which is what lets a node reach the frame its opener was emitted from. Output is unchanged: byte-identical over the 225 fixture documents and 50,000 random ones, plus the same source map. Retained heap at the walk's end, and CPU per print (20k-node documents): table 12.51 -> 1.47 MiB 105 -> 77 ms flat 5.33 -> 0.03 MiB 33 -> 27 ms lists 5.23 -> 0.69 MiB 62 -> 51 ms deep 1.54 -> 0.62 MiB 5.5 -> 4.7 ms * test(html): benchmark the printer, not just the parser `html-parser-document-unit` stops at the parse, so nothing measured serialization — the half this branch changes. This covers both paths a node can take (emitted in pieces as the walk reaches them, or composed from its children and read back) and the tree shapes they cost differently on: fan-out and depth are separate axes for a walk that carries one frame per open element. Against this branch's merge base every case separates well clear of its spread, so a regression in either path shows up rather than hiding in the document total: document 278.7 -> 68.8 ms fragment (tr) 50.6 -> 27.6 ms wide table 79.7 -> 35.9 ms flat siblings 21.9 -> 13.7 ms nested lists 30.3 -> 24.1 ms deep nesting 34.1 -> 25.1 ms composed subtrees 21.8 -> 18.2 ms implied start tags 13.2 -> 10.9 ms * test(html): benchmark each printer fixture unminimized too A build that is not minimizing still parses and walks, and that pass is the floor the printer sits on. Running every fixture both ways makes the pair the measurement: the difference is what printing costs on that shape, which neither number shows alone. fixture walk minify document 25.6 -> 61.2 ms fragment (tr) 13.4 -> 27.9 ms wide table 15.4 -> 32.8 ms flat siblings 6.7 -> 13.6 ms nested lists 10.8 -> 23.5 ms deep nesting 12.7 -> 26.9 ms composed subtrees 7.2 -> 15.8 ms implied start tags 3.9 -> 9.9 ms The fixtures move to a table so the two modes cannot drift apart; the `minify (...)` names are unchanged, so their history carries over. * feat(html): make the printer's mode reachable and support beautifying `PrintOptions.mode` has always been typed `"minify" | "beautify"` and both printers branch on it, but `process()` hardcoded `"minify"`, so half of it was unreachable. `process(src, { mode })` now selects it; `minimize: true` keeps working as the shorthand for `mode: "minify"` it reads as. Beautifying re-serializes rather than rewrites: the source's own attribute quoting, its comments and its end tags all come back, and nothing is dropped for re-parsing the same. It is deliberately still ugly — nothing is re-indented — but it must not be lossy, and on the CSS side two things were: kept license comments were only collected when minifying, and a custom property's value claimed them from the writer only on the minifying path, so each was emitted twice. Both are fixed here. Minify output is unchanged, byte-for-byte, over the 843-file css/html fixture corpus and 24,000 random inputs. On the same inputs `minify(beautify(x)) === minify(x)` holds everywhere minify is itself idempotent. Each printer benchmark fixture now runs in all three modes, so `minify - beautify` shows what the rewrites cost on top of serializing: fixture walk beautify minify document 26.4 -> 48.2 -> 57.8 ms fragment (tr) 12.3 -> 22.1 -> 25.1 ms wide table 14.1 -> 25.4 -> 34.3 ms flat siblings 6.4 -> 12.9 -> 14.8 ms nested lists 10.8 -> 17.5 -> 23.9 ms deep nesting 12.3 -> 17.5 -> 23.9 ms composed subtrees 7.1 -> 13.9 -> 16.3 ms implied start tags 3.9 -> 7.5 -> 9.6 ms * fix(html): refuse a nested parse, and pin the streamed walk's offsets Three review findings on the walk streaming: - The JSDoc describing `popOpen` sat above `removeOpenAt`, so one helper was documented by a block declaring a return value it does not have and the other had none. Moved onto the function it describes. - Hoisting the walk's state (`_visitors`, `_writer`, the open path, the AST columns) to module scope for monomorphic call sites made the grammar non-reentrant: a visitor that started another HTML parse would take this one's state over and release its columns on the way out, silently. It used to work, because the state was per-call. Refuse it with a clear error instead. Nesting the other language is untouched — a `<style>`'s CSS has its own module state — and an `<iframe srcdoc>` is a separate module webpack parses on its own, which is why every `configCases/html` case still passes. - The offsets test was a few dozen nodes against a 49152-node threshold, so it never reached the streamed walk it described, and its comment credited the wrong mechanism: head elements do not keep final offsets because streaming starts in body, but because a flush only ever visits children that are already complete, and `HtmlParser` reads `tagEnd()` — assigned at insertion — for the still-open `<html>` / `<head>`. Replaced with the contrast that does pin the streamed path: the same markup below and above the threshold, asserting an entered element reports a provisional `end` at `enter` and a final one at `exit`. Verified it bites — pushing the threshold out of reach fails it, where the old test passed. Output is unchanged: the fuzz corpus hashes identically with and without these commits.
1 parent 57f8dcf commit 78d0d4c

6 files changed

Lines changed: 1403 additions & 186 deletions

File tree

‎lib/html/HtmlGenerator.js‎

Lines changed: 14 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -704,11 +704,23 @@ class HtmlGenerator extends Generator {
704704
if (name === "head") {
705705
if (headOpen < 0) headOpen = headEnd = path.tagEnd();
706706
headDepth++;
707+
} else if (name === "body") {
708+
if (bodyOpen < 0) bodyOpen = bodyEnd = path.tagEnd();
709+
bodyDepth++;
710+
}
711+
},
712+
// Collected on exit: an element's `end` is only final once it
713+
// closes, and the streamed walk enters it while it is still open.
714+
// `script` / `style` / `link` / `meta` never nest in each other, so
715+
// exiting keeps them in source order.
716+
exit: (path) => {
717+
const name = path.tagName();
718+
if (name === "head") {
719+
if (headDepth > 0) headDepth--;
707720
return;
708721
}
709722
if (name === "body") {
710-
if (bodyOpen < 0) bodyOpen = bodyEnd = path.tagEnd();
711-
bodyDepth++;
723+
if (bodyDepth > 0) bodyDepth--;
712724
return;
713725
}
714726
const end = path.end();
@@ -749,14 +761,6 @@ class HtmlGenerator extends Generator {
749761
});
750762
originals.push(snapshotAttrs(attrs));
751763
descriptors.push(null);
752-
},
753-
exit: (path) => {
754-
const name = path.tagName();
755-
if (name === "head") {
756-
if (headDepth > 0) headDepth--;
757-
} else if (name === "body" && bodyDepth > 0) {
758-
bodyDepth--;
759-
}
760764
}
761765
}
762766
})

0 commit comments

Comments
 (0)