inikulin / parse5 / 42385807362

96%

master: 96%

Pull #1921

github

perf(parser): find open elements without scanning a deep stack

Searches of the stack of open elements walked it from the top: the
scope checks, the search for a list item to close, generic end tags in
HTML and in foreign content, insertion-mode resets, foster parenting and
the adoption agency. On a deep stack every such token paid for the
depth, so `<p><button>` followed by N `<div>`s, or `<b>` followed by N
`<span><div>` pairs and N `</b>`, took quadratic time.

Once 64 elements are open, the stack indexes them: elements with the
same tag in the same namespace are chained, so the topmost is found
without a scan, and each slot counts the special elements, list item
boundaries and scope boundaries at or below it, so whether one lies
between two elements is a comparison. Open formatting elements are
found by element. Stacks that never reach 64 elements are scanned,
which costs less than keeping the index on every push and pop.

On an indexed stack, removing an element from the middle leaves its
slot free instead of moving every element above it down, and the
adoption agency moves only the furthest block and the formatting
elements it kept below it, so each of its steps costs the elements it
passes, not the depth of the stack. `replaceFormattingElement` replaces
`insertAfter`, which only the adoption agency used.

The stack tests count reads of the stack's arrays for each kind of
search behind a deep stack, with the target missing or behind a
boundary; each is constant per token, and the reset rows that counted
the entries a reset passed are among them. The stack's unit tests check
the searches after removals from the middle and the adoption agency's
step, on a scanned and on an indexed stack, and a parser test parses
inputs that use each search behind 64 open elements as behind none.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>

656 of 658 branches covered (99.7%)

602 of 605 new or added lines in 11 files covered. (99.5%)

4233 of 4406 relevant lines covered (96.07%)

154633.79 hits per line