inikulin / parse5
96%
master: 96%

LAST BUILD BRANCH: chore/v8.1.1
DEFAULT BRANCH: master
Repo Added
Files 41
Badge
Embed ▾
README BADGES
x

If you need to use a raster PNG badge, change the '.svg' to '.png' in the link

Markdown

Textile

RDoc

HTML

Rst

LAST BUILD ON BRANCH release/parse5-security
branch: release/parse5-security
CHANGE BRANCH
x

coverage: 96.074% (+0.4%) from 95.638%
42385807362

Pull #1921

github

fb55 
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>
Pull Request #1921: Security fixes for the tokenizer, serializer, SAX parser and tree construction

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

Relevant lines Covered
4406 RELEVANT LINES 4233 COVERED LINES
154633.79 HITS PER LINE
Source Files on release/parse5-security

Recent builds

Builds Branch Commit Type Ran Committer Via Coverage
42385807362 release/parse5-security 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 r... Pull #1921 fb55 github
96.07
42371006084 release/parse5-security 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 r... Pull #1921 fb55 github
96.07
42327127589 release/parse5-security 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 st... Pull #1921 fb55 github
95.86
42254802986 release/parse5-security 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 st... Pull #1921 fb55 github
95.82
42254813239 release/parse5-security Merge e168c3163 into 1f6130866 Pull #1921 web-flow github
95.82
See All Builds (1714)