inikulin / parse5 / 42254802986

96%

master: 96%

Pull #1921

github

perf(parser): keep at most 512 elements open, as WebKit does

Every search of the stack of open elements costs up to its depth per
token: the scope checks before closing a paragraph or list item, the
check whether the last formatting element is still open before text,
and the adoption agency's up to eight passes per end tag. A document of
`<b>` followed by many `<span><div>` pairs and as many `</b>` made the
agency's scans grow with the depth, which was unbounded.

WebKit and Blink stop the DOM tree at 512 nested elements
(`defaultMaximumHTMLParserDOMTreeDepth`, `kMaximumHTMLParserDOMTreeDepth`).
WebKit also closes the current element first, so its stack of open
elements never grows past that depth. The parser now does the same:
when 512 elements are open and a node is attached (an element, a void
element or a comment), the current element is closed first and the node
goes where the next one would. Template contents are not exempt, unlike
in WebKit, so the bound holds for nested templates too. The element is
closed as its end tag would close it: a formatting marker it inserted is
cleared, a template takes its insertion mode entry with it, and an
element that selects an insertion mode resets the mode (WebKit does this
for cells), unless the limit makes room for an HTML element that selects
its own mode once inserted, as all of them but `select` do: the reset
walks up to 512 elements, and every table, row and cell inserted at the
limit would pay that for a mode its handler sets right after. A
table-body end tag that reaches a row the limit has closed takes its
mode from the stack instead of popping past the row. Comments set the
current token, so the element a comment closes ends at the comment. With
the stack bounded, every search of it is bounded per token.

Formatting elements closed by the limit stay in the list of active
formatting elements and are reconstructed by the next text, as in
WebKit: `<b a=i>` × N followed by `x</b>` × N creates N² elemen... (continued)

604 of 607 branches covered (99.51%)

267 of 275 new or added lines in 11 files covered. (97.09%)

4060 of 4237 relevant lines covered (95.82%)

168372.41 hits per line