* Html: keep collapsed details with void tags from swallowing table closures
* Html: harden the parser, the walker and the widget against malformed input
Follows the void-tag fix in the `<details>` skip loop by auditing the rest of
the HTML code for the same class of defect. Robrix renders `formatted_body`
straight from Matrix events, so every parser crash here is reachable from a
message any stranger can send.
Crashes, all reachable from a chat message:
- Numeric character references were parsed as `i64` and cast to `u32`, then
handed to `char::from_u32(..).unwrap()`. `�`, `�`, `&#-1;`
and `�` aborted the process. They are validated now, and a
reference that names no scalar value stays literal text.
- An unterminated `&` stayed pending across a tag boundary or a closing
attribute quote, so a later `;` could fire `decoded.truncate()` and
retroactively invalidate byte ranges of nodes already emitted —
`<p>&am<b>p;</b></p>` produced out-of-bounds and mid-character ranges.
The pending entity is dropped at each of those boundaries.
- An unquoted attribute value beginning with a multi-byte character recorded
`decoded.len() - 1` as its start, splitting the character.
- `</summary>` with no `<summary>` popped an empty tracker stack, and stray
`</td>`, `</tr>`, `</li>` and friends reached `cx.end_turtle()` with nothing
to end. The widget now tracks what it opened and ignores unmatched closes.
- `('A' as u8 + count as u8 - 1)` overflowed on an attacker-controlled `start`
or `value`; alphabetic list markers now number a..z, aa, ab, ...
Content silently lost or mangled:
- `jump_to_close` counted every open tag toward depth, but a void element
written without a slash emits no close tag, so it overshot and swallowed the
rest of the document. `<a href=u>x<br>y</a>` hid everything after the link.
Only tags with the same id affect depth now, and an element with no close tag
leaves the walker where it is. `mod_html::find_close_tag` had it too.
- A `<` that cannot start a tag is literal text, the way a browser reads it.
`5<10 and 6<12` used to parse `<10` as an element and drop the rest.
- `?` mid-tag-name and `<!-->` / `<!--->` ran to end of input.
- `/` in an unquoted value ended it, truncating `href=http://host/path` at the
first slash; only a slash immediately before `>` closes the tag now.
- `<a href=>text</a>` took `>` as the value's first character, so the tag never
closed and its content leaked out as text.
- Unquoted values never decoded entities at all, unlike quoted ones.
- `<pre>`/`<code>` whitespace preservation was a single flag that any nested
tag cancelled, so a syntax-highlighted code block lost its indentation. It is
a depth counter now.
- HTML's whitespace set is five ASCII characters, not Unicode's;
`char::is_whitespace` collapsed ` ` runs and ate the full-width spaces
in CJK text.
- `find_text` returned the zero-length node the parser emits before every tag,
so `<a href=x><b>label</b></a>` rendered an empty link. `find_tag_text`
matched the case-sensitive id and missed any tag carrying an attribute.
- Duplicate `id` attributes bound two elements to one cached sub-widget, so a
second link could render its own text over the first link's href.
- `<li>a<li>b` and `<td>a<td>b` now implicitly close the previous item, and
anything a document leaves open is unwound before `TextFlow::end`.
Entity table, which had been generated by folding names case-insensitively:
- 146 names took their case-twin's code point. `é` rendered `É`,
`α` rendered `Α`, `→` rendered `⇒`, `𝕔` rendered `ℂ`.
- `Igrave`/`Icirc`/`Iuml` had been transcribed as `Lgrave`/`Lcirc`/`Luml`, and
`Iacute` was missing outright; the invented l-spellings are removed.
- `permil` mapped to the Windows-1252 byte 0x89 rather than U+2030, and an
empty-string key sat where it belonged, so `&;` decoded to `‰`.
- `tilde`, `lang` and `rang` were wrong.
The ALL-CAPS aliases the table also carries are left as they were.
Also: dropped the `unwrap` in `ElementSelfClose`, memoised table column counts
(quadratic in the number of `<table>` tags), and replaced the backward node
scan on every tag close with the depth counter.
Adds 18 tests covering each of the above. Verified by exhaustive enumeration of
all 12.2M inputs up to length 6 over a markup-heavy alphabet, and 6M randomized
structured cases, both checking that no input panics and that every node's byte
range is ordered, in bounds, on a character boundary, non-overlapping, and
agrees with its `all_ws` flag.
* Html: recover from malformed tags without leaking them into the text
A second pass over the same code, after the first round of fixes changed what
the edge cases look like.
- `</` followed by something that cannot name an element is literal text, the
rule `<` already follows. `i </3 u` used to emit a close tag named `3` and
drop the rest of the line.
- Junk inside a tag is discarded up to its `>` rather than resuming text in the
middle of it, which leaked the tag's own `>` into the output: `a</p x>b` and
`a<br/x>b` rendered `>b`.
- A custom widget with no close tag of its own is void, so it has no text.
Reading ahead picked up the *following* sibling's text, and now that
`jump_to_close` correctly stays put, the main loop drew that text a second
time: `<img src=x>caption` showed `caption` twice.
- `table_columns_cache` is keyed by node index, so it has to be cleared per
draw or a recycled widget lays a table out with a previous document's column
count.
- `<ol start="2147483647">` overflowed the item counter.
* Html: bound jump_to_close's scan and cut the measured hot spots
Benchmarked against the branch point (best-of-7, black_box'd, release).
- `jump_to_close` stops at the first close tag belonging to an enclosing
element instead of reading to the end of the node vector. It tracks the
elements opened inside this one so a descendant's close tag is still
matched correctly, and allocates nothing for the common case of an element
whose content is plain text.
- Numeric character references were compared against all ~1500 named-entity
arms before reaching the catch-all. Dispatching on the leading `#` first
makes them 2.9x faster (991us -> 342us for 3000 references).
- `process_entity` is `#[inline]`; it is called once per character.
- `decoded` is reserved up front, worth ~4% on text-heavy input. `nodes`
deliberately is not: its length tracks tag count rather than byte count, and
sizing it from `body.len()` cost a tag-sparse document a large pointless
allocation — that made the numeric-entity case 3x *slower* before it was
measured and removed.
- The widget rejects an unmatched close tag from a tally instead of scanning
the whole open-element stack, which was quadratic on a message combining
deep nesting with stray close tags.
- `align_keyword_to_x` compares in place rather than lowercasing into a fresh
String for every aligned cell on every draw.
Tag-heavy parsing is ~2-3% slower than the branch point, which is the standing
cost of the `<pre>` depth tracking, the literal-`<` guard and the entity state
carried across characters. Plain text is ~4% faster.
* Html: follow the tokenizer's recovery rules and resolve element ends at parse time
The parser's states now mirror the WHATWG tokenizer's, so malformed input
produces the tokens a browser would build from it rather than a guess:
- `</` followed by anything but a letter opens a bogus comment that runs to
the next `>`, `</>` is dropped, and `<?...>` is a bogus comment too. `<`
or `</` at the very end of input is text.
- `<a/b>` reads as `<a b>`: the slash was not a self-closing marker, so no
close tag is synthesized. `<x/>` still emits one — the SVG parser is built
on this walker and XML needs it — which is the one deliberate departure.
- In an unquoted attribute value a `/` is just another character, so
`href=http://host/path` keeps its path and `<img src=x/>` is `src="x/"`.
- `<!--x--!>` closes a comment, `<!-x>` is a bogus comment, and a tag cut
off by the end of input is dropped whole.
- Numeric character references follow the tokenizer's end state: zero, a
surrogate, or anything past U+10FFFF becomes U+FFFD, and the C1 range is
read as Windows-1252, so `—` is an em dash as legacy content intends.
Digits are accumulated with saturation so a forty-digit reference lands on
U+FFFD rather than an error. A decoded space collapses like a literal one.
- `<pre>`/`<code>` are tracked as a stack: a stray `</code>` cannot cancel an
enclosing `<pre>`, and `</pre>` closes a `<code>` left open inside it.
Every element's end is now resolved once at parse time (`HtmlDoc::closes`),
with the recovery a browser applies: a close tag ends the innermost open
element of its name and everything still open inside it, and a close tag
that matches nothing is ignored. `jump_to_close` and the new
`HtmlWalker::close_index` are lookups, which removes the last quadratic
case — a paragraph of thousands of `<img>` tags cost 3.4ms a frame — and a
stray `</span>` no longer stops a link's `</a>` from being found. The tally
that rejects stray close tags hashes `LiveId` through an identity hasher,
since it is already a 64-bit hash; with SipHash the pass cost 20%.
Widget:
- A `<summary>` left open is closed by `</details>` or the end of the
document, so its bold run and glyph tracker no longer leak into everything
drawn after it.
- Implicit closes follow the tree builder's scope rules — `<li>` closes an
open item up to its list, a cell up to its row, a row with its cells, a
heading directly following a heading, and any block element an open `<p>`
— rather than only the innermost element.
- A custom widget's label is all the text inside it, so
`<a href=x><b>Click</b> me</a>` reads "Click me", and a void one has none.
- Sub-widgets are keyed only by node index. Keying by the `id` attribute let
a document choose cache keys, and a repeated id bound two links to one
widget.
- `TrimWhitespaceInText`, `combine_spaces` and `ignore_newlines` are gone:
all three were written at every site and read at none.
- List markers are borrowed rather than allocated per item per draw, table
cell alignment compares in place, and link hit-testing no longer clones
its area list on every event.
Script module: `.html` printed raw hex for every tag and attribute name,
because the document was parsed without interning; it is interned now and
text and attribute values are escaped on the way out, so the output parses
back to the same document. `find_elements` counted every open tag toward
depth, the void-element bug again; it steps by resolved close index.
23 parser tests, exhaustive enumeration of all inputs up to length 6 over a
markup-heavy alphabet, and 6M randomized structured cases, checking that no
input panics and that every node range and close index is consistent.
* Html: resolve every element's end in the tokenizer, and close the review's findings
An adversarial review of the previous commit against the WHATWG tokenizer,
the branch point and a reference parser found the gaps below. All fixed.
The parser now keeps the open-element stack as tags stream past, so each
element's end is resolved in the same pass that tokenizes it — the recovery a
browser's tree builder applies: a close tag ends the innermost open element
of its name and everything still open inside it; a close tag that matches
nothing is ignored; the spec's void elements are whole at their open tag;
what is still open at end of input ends there. `HtmlDoc` records both the
element's own close tag (`close_index`) and where it ends (`end_index`).
That distinction was missing: an element ended by an ancestor looked the
same as a void one, so the script module gave `<li>a<li>b` items empty
ranges — no `.text`, no `.html`, children promoted to siblings — and the
widget dropped the label of a link ended by `</td>`. Both read correctly now.
Because the whitespace-preserving stack is the same stack, a `<pre>` ended
by an enclosing element's close tag stops preserving at that tag, which it
did not before.
Tokenizer fixes, each per the spec's state machine:
- `<!>` and `<!->` are complete bogus comments; they used to swallow text up
to the next `>`.
- A numeric character reference ends at the first non-digit whether or not
`;` follows (`& b` reads `& b`), and has no length limit: forty digits
saturate to U+FFFD as the previous commit claimed but did not do.
- An end tag followed by junk and then end of input is dropped like any
other tag cut off there; it used to emit its close tag anyway.
- `\r\n` and lone `\r` become `\n`, as the input stream preprocessing says.
- A repeated attribute name on one tag is dropped, so a consumer iterating
attributes sees the first `data-mx-color` rather than the last.
- A comment is not content, so `a <!-- c --> b` collapses to one space.
- `find_tag_text` answers for the first matching element and does not fall
through to a later one.
The maps that reject stray close tags and duplicate attributes are keyed
with a per-parse random seed and a multiply-fold hash: the previous identity
hasher let crafted tag names collide and made the pass quadratic, and the
standard SipHash cost a quarter of the parse time.
Widget:
- A `<summary>` is tied to the `<details>` that owns it. A `<details>` opened
inside a summary was taken for the owner, and `</details>` then popped an
empty tracker stack — a panic reachable from a chat message.
- `</summary>` and `</details>` end whatever was opened inside them, so an
`<li>` or a table cell opened in a summary no longer swallows the content
that follows.
- A collapsed body is skipped to the element's resolved end, so a
`<details>` ended by an ancestor no longer hides everything after it.
- `count_table_columns` ends the first row at the next `<tr>` as well as
`</tr>`; a table written without `</tr>` had every column halved.
- The `<p>` rule runs before the heading rule, as the tree builder orders
them, so `<h1><p>a<h2>` no longer nests the second heading in the first.
Script module: ranges are `(open, end)` with an exclusive end; `parse_query`
no longer panics on `a]b[`.
30 parser tests, exhaustive enumeration of all inputs up to length 6 over a
markup-heavy alphabet, and 6M randomized structured cases, checking every
node range, every `close_index`/`end_index`, nesting consistency, and
determinism.
* Html: build the tree builder's implicit closes into the parser, and end every element where it says
Two verification rounds against the previous commit — a spec-conformance
review, a stack-based reference for element ends, a simulation of the widget's
draw loop over exhaustive and random tag soups, and a round-trip check of the
script module — found the gaps below. All fixed.
The parser now applies the tree builder's implicit closes as it builds the
element stack: a block start tag closes an open `<p>`; a heading closes a
heading that is the current node; `<li>` closes an open item up to its list,
`<dd>`/`<dt>` likewise; a cell closes an open cell up to its row; `<tr>` closes
a row and its cells; a table section closes section, row and cells; a second
`<a>` closes the first. Every consumer therefore sees the tree a browser
builds: `<li>a<li>b` is two items, `<a href=1>x<a href=2>y</a>` two links,
and `<li><a href=u>one<li>two` gives the first link the label "one" rather
than "onetwo". The widget's own copy of these rules is gone; it closes each
element at the index the parser resolved, before that node is handled, and
`<details>`/`<summary>` without a close tag of their own are ended the same
way. Two bugs that fell out of them being special:
- a `<details>` ended by an enclosing close tag stayed on the stack, a later
`<summary>` bound to it, and the collapse-skip resumed *behind* the walker.
One stale level drew the text twice; N of them re-walked the document 2^N
times — a 380-byte message hung the UI. A resume is now never behind the
walker, and no level is left behind to be claimed.
- a `<summary>` ended by an enclosing close tag never popped its bold run and
glyph tracker, which leaked into everything drawn after it.
Per-name depth stacks replace the per-name counts, so finding the innermost
open element of a name, or the outermost one above a scope boundary, is a
lookup; scanning the stack made a document of nested `<div>`s quadratic.
A tag with thousands of attributes no longer makes every later tag pay to
clear the attribute-name set. Every nesting shape measured is linear.
Tokenizer and tree builder, per the spec: `</br>` is read as `<br>`, so
`x</br>y` breaks the line; the newline immediately after `<pre>` is not
content; NUL is dropped from text and replaced in attribute values.
Widget: a table whose first row is empty is sized by the first row that has
cells rather than falling back to 100px columns.
Script module: `.html` always writes `=""` and doubles a newline that starts
a `<pre>`, so its output parses back to the same document; `.text` is the
decoded text verbatim, no longer inventing a space inside a word split by a
comment or an inline tag; a query on a selection searches inside it, as
`querySelectorAll` does; descendant steps skip ranges already scanned, which
made `b b` on deeply nested `<b>` quadratic; `parse_query`'s grammar is
documented as implemented.
Deliberately unchanged: the entity table's omissions (`€`, ...), named
references without `;`, and an unquoted attribute value ending in `/` before
`>` (per the tokenizer the slash is part of the value; XML requires quotes).
33 parser tests; exhaustive enumeration of all inputs up to length 6 over a
markup-heavy alphabet and 6M randomized structured cases, checking every node
range, every `close_index`/`end_index`, nesting consistency, attribute
dedupe and determinism.
a843d772b5