html5ever: each block start tag walks the stack of open elements, so nested divs parse in O(depth²)

From the repository

This page is repros/html5ever-p-in-button-scope-quadratic/README.md, included when the site is built. Edit it there.

What niso does

Nothing: niso parses through blitz-html’s sink on html5ever 0.40.1. Nested <span>s parse in linear time, and niso’s 200k-deep innerHTML test (crates/niso-quickjs/tests/deep_trees.rs) uses them. <div>s 100k deep take about 55 s. html5ever’s main already caps the stack (see Upstream main), so this goes away with the next release.

Expected vs actual

Every start tag for an address, div, p, ul and the other block elements runs “close a p element” if one is in button scope (close_p_element_in_button_scope, html5ever/src/tree_builder/mod.rs:1218 in 0.40.1), and in_scope walks the stack of open elements from the top until it finds a p or a scope boundary. Nested divs are neither, so each tag walks the whole stack and n of them cost O(n²).

<span> nested 5k deep 14 ms, 20k deep 18 ms; expected under 8x (linear is 4x), actual 1.3x
<div> nested 5k deep 50 ms, 20k deep 1158 ms; expected under 8x (linear is 4x), actual 23.0x

Run

CARGO_TARGET_DIR=~/.capy/work/repro-target cargo run --release

Upstream main

Fixed on main, not released. html5ever main was at a027c2835472d518893c906dc29c42200af3c960 when checked (2026-11-09). servo/html5ever#811 (merged 2026-11-03, after 0.40.1) caps the stack of open elements at 512 the way Gecko and Blink do, so in_scope walks at most 512 elements. It also means a parser-built tree is at most 512 deep, like in browsers. Once niso is on a release with it, the 200k-deep innerHTML test still holds: it counts elements, not depth.

Existing issue or PR

servo/html5ever#811, merged.

Issue text

None needed: #811 fixes it. Pick up the first html5ever release after 0.40.1.