There are two changes happening here: a correctness fix, and an
optimization. In theory they are unrelated, but the optimization
actually paves the way for the correctness fix.
Before this commit, the HTML tokenizer would attempt to look for named
character references by checking from after the `&` until the end of
m_decoded_input, which meant that it was unable to recognize things like
named character references that are inserted via `document.write` one
byte at a time. For example, if `∉` was written one-byte-at-a-time
with `document.write`, then the tokenizer would only check against `n`
since that's all that would exist at the time of the check and therefore
erroneously conclude that it was an invalid named character reference.
This commit modifies the approach taken for named character reference
matching by using a trie-like structure (specifically, a deterministic
acyclic finite state automaton or DAFSA), which allows for efficiently
matching one-character-at-a-time and therefore it is able to pick up
matching where it left off after each code point is consumed.
Note: Because it's possible for a partial match to not actually develop
into a full match (e.g. `¬indo` which could lead to `⋵̸`),
some backtracking is performed after-the-fact in order to only consume
the code points within the longest match found (e.g. `¬indo` would
backtrack back to `¬`).
With this new approach, `document.write` being called one-byte-at-a-time
is handled correctly, which allows for passing more WPT tests, with the
most directly relevant tests being
`/html/syntax/parsing/html5lib_entities01.html`
and
`/html/syntax/parsing/html5lib_entities02.html`
when run with `?run_type=write_single`. Additionally, the implementation
now better conforms to the language of the spec (and resolves a FIXME)
because exactly the matched characters are consumed and nothing more, so
SWITCH_TO is able to be used as the spec says instead of RECONSUME_IN.
The new approach is also an optimization:
- Instead of a linear search using `starts_with`, the usage of a DAFSA
means that it is always aware of which characters can lead to a match
at any given point, and will bail out whenever a match is no longer
possible.
- The DAFSA is able to take advantage of the note in the section
`13.5 Named character references` that says "This list is static and
will not be expanded or changed in the future." and tailor its Node
struct accordingly to tightly pack each node's data into 32-bits.
Together with the inherent DAFSA property of redundant node
deduplication, the amount of data stored for named character reference
matching is minimized.
In my testing:
- A benchmark tokenizing an arbitrary set of HTML test files was about
1.23x faster (2070ms to 1682ms).
- A benchmark tokenizing a file with tens of thousands of named
character references mixed in with truncated named character
references and arbitrary ASCII characters/ampersands runs about 8x
faster (758ms to 93ms).
- The size of `liblagom-web.so` was reduced by 94.96KiB.
Some technical details:
A DAFSA (deterministic acyclic finite state automaton) is essentially a
trie flattened into an array, but it also uses techniques to minimize
redundant nodes. This provides fast lookups while minimizing the
required data size, but normally does not allow for associating data
related to each word. However, by adding a count of the number of
possible words from each node, it becomes possible to also use it to
achieve minimal perfect hashing for the set of words (which allows going
from word -> unique index as well as unique index -> word). This allows
us to store a second array of data so that the DAFSA can be used as a
lookup for e.g. the associated code points.
For the Swift implementation, the new NamedCharacterReferenceMatcher
was used to satisfy the previous API and the tokenizer was left alone
otherwise. In the future, the Swift implementation should be updated to
use the same implementation for its NamedCharacterReference state as
the updated C++ implementation.
We previously had PropertyOwningCSSStyleDeclaration and
ResolvedCSSStyleDeclaration, representing the current style properties
and resolved style respectively. Both of these were the
CSSStyleDeclaration type in the CSSOM. (We also had
ElementInlineCSSStyleDeclaration but I removed that in a previous
commit.)
In the meantime, the spec has changed so that these should now be a new
CSSStyleProperties type in the CSSOM. Also, we need to subclass
CSSStyleDeclaration for things like CSSFontFaceRule's list of
descriptors, which means it wouldn't hold style properties.
So, this commit does the fairly messy work of combining these two types
into a new CSSStyleProperties class. A lot of what previously was done
as separate methods in the two classes, now follows the spec steps of
"if the readonly flag is set, do X" instead, which is hopefully easier
to follow too.
There is still some functionality in CSSStyleDeclaration that belongs in
CSSStyleProperties, but I'll do that next. To avoid a huge diff for
"CSSStyleDeclaration-all-supported-properties-and-default-values.txt"
both here and in the following commit, we don't apply the (currently
empty) CSSStyleProperties prototype yet.
The DOMParsing spec is in the process of being merged into the HTML one,
gradually. The linked spec change moves XMLSerializer, but many of the
algorithms are still in the DOMParsing spec so I've left the links to
those alone.
I've done my best to update the GN build but since I'm not actually
using it, I might have done that wrong.
Corresponds to 2edb8cc7ee
This is not really a context, but more of a set of parameters for
creating a Parser. So, treat it as such: Rename it to ParsingParams,
and store its values and methods directly in the Parser instead of
keeping the ParsingContext around.
This has a nice side-effect of not including DOM/Document.h everywhere
that needs a Parser.
This file has been a pain to edit for a while, even with the previous
splits. So, I've divided it up into 3 parts:
- Parser.cpp has the "base" code. It's the algorithms and entry-points
defined in the Syntax spec.
- ValueParsing.cpp contains code for parsing single values, such as a
length, or a color, or a calculation.
- PropertyParsing.cpp contains code for parsing an entire property's
value. A few of these sit in a grey area between being a property's
value and a value in their own right, but the rule I've used is "is
this useful outside of a single property and its shorthands?"
This only moves code, with as few modifications as possible to make that
work. I did add explicit instantiations for the template implementations
as part of this, which revealed a few that are actually only compatible
with a single type, so I'll clear those up in a subsequent commit.
Same again, although rotation is more complicated: `rotate`
is "equivalent to" multiple different transform function depending on
its arguments. So we can parse as one of those instead of the full
`rotate3d()`, but then need to handle this when serializing.
This adds a thin wrapper to LibCrypto for generating cryptographically
secure random values and replaces current usages of PRNG within
LibCrypto as well.
This reverts commit 76daba3069.
We're going to need separate types for the JS-exposed style values, so
it doesn't make sense for us to match their names with our internal
types.
This is an attempt to bring the size of Parser.cpp down. No code
changes, just moves and some explicit template instantiations now that
we're using them from a different file.
This is a mixin in the IDL, so let's treat it as a mixin in our code and
let both SVGElement and MathMLElement reuse the implementations that we
wrote for HTMLElement.
This input event handling change is intended to address the following
design issues:
- Having `DOM::Position` is unnecessary complexity when `Selection`
exists because caret position could be described by the selection
object with a collapsed state. Before this change, we had to
synchronize those whenever one of them was modified, and there were
already bugs caused by that, i.e., caret position was not changed when
selection offset was modified from the JS side.
- Selection API exposes selection offset within `<textarea>` and
`<input>`, which is not supposed to happen. These objects should
manage their selection state by themselves and have selection offset
even when they are not displayed.
- `EventHandler` looks only at `DOM::Text` owned by `DOM::Position`
while doing text manipulations. It works fine for `<input>` and
`<textarea>`, but `contenteditable` needs to consider all text
descendant text nodes; i.e., if the cursor is moved outside of
`DOM::Text`, we need to look for an adjacent text node to move the
cursor there.
With this change, `EventHandler` no longer does direct manipulations on
caret position or text content, but instead delegates them to the active
`InputEventsTarget`, which could be either
`FormAssociatedTextControlElement` (for `<input>` and `<textarea>`) or
`EditingHostManager` (for `contenteditable`). The `Selection` object is
used to manage both selection and caret position for `contenteditable`,
and text control elements manage their own selection state that is not
exposed by Selection API.
This change improves text editing on Discord, as now we don't have to
refocus the `contenteditable` element after character input. The problem
was that selection manipulations from the JS side were not propagated
to `DOM::Position`.
I expect this change to make future correctness improvements for
`contenteditable` (and `designMode`) easier, as now it's decoupled from
`<input>` and `<textarea>` and separated from `EventHandler`, which is
quite a busy file.
This is really bare bone as we only support the `xyz-d50` color space
for the moment.
It makes us pass the following WPT tests:
- css/css-color/predefined-016.html
- css/css-color/xyz-d50-001.html
- css/css-color/xyz-d50-002.html
