inikulin / parse5 / 42371006084

96%

master: 96%

Build Type

Pull #1921

github

Committed by fb55

Commit Message

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. Shallower stacks are still 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>

Pull Request Pull Request #1921: Security fixes for the tokenizer, serializer, SAX parser and tree construction

Coverage Stats

656 of 658 branches covered (99.7%)

603 of 606 new or added lines in 11 files covered. (99.5%)

1 existing line in 1 file now uncovered.

4234 of 4407 relevant lines covered (96.07%)

154580.23 hits per line