Commit graph

98 commits

Author SHA1 Message Date
Ryan Liptak
6da1dfa8f2 LibWeb/HTML: Improve data structure of named character reference data
Introduces a few ad-hoc modifications to the DAFSA aimed to increase
performance while keeping the data size small.

- The 'first layer' of nodes is extracted out and replaced with a lookup
  table. This turns the search for the first character from O(n) to O
  (1), and doesn't increase the data size because all first characters
  in the set of named character references have the
  values 'a'-'z'/'A'-'Z', so a lookup array of exactly 52 elements can
  be used. The lookup table stores the cumulative "number" fields that
  would be calculated by a linear scan that matches a given node, thus
  allowing the unique index to be built-up as normal with a O(1) search
  instead of a linear scan.
- The 'second layer' of nodes is also extracted out and searches of the
  second layer are done using a bit field of 52 bits (the set bits of
  the bit field depend on the first character's value), where each set
  bit corresponds to one of 'a'-'z'/'A'-'Z' (similar to the first
  layer, the second layer can only contain ASCII alphabetic
  characters). The bit field is then re-used (along with an offset) to
  get the index into the array of second layer nodes. This technique
  ultimately allows for storing the minimum number of nodes in the
  second layer, and therefore only increasing the size of the data by
  the size of the 'first to second layer link' info which is 52 * 8 =
  416 bytes.
- After the second layer, the rest of the data is stored using a
  mostly-normal DAFSA, but there are still a few differences:
   - The "number" field is cumulative, in the same way that the
     first/second layer store a cumulative "number" field. This cuts
     down slightly on the amount of work done during the search of a
     list of children, and we can get away with it because the
     cumulative "number" fields of the remaining nodes in the DAFSA
     (after the first and second layer nodes were extracted out) happens
     to require few enough bits that we can store the cumulative version
     while staying under our 32-bit budget.
   - Instead of storing a 'last sibling' flag to denote the end of a
     list of children, the length of each node's list of children is
     stored. Again, this is mostly done just because there are enough
     bits available to do so while keeping the DAFSA node within 32
     bits.
   - Note: Together, these modifications open up the possibility of
     using a binary search instead of a linear search over the
     children, but due to the consistently small lengths of the lists
     of children in the remaining DAFSA, a linear search actually seems
     to be the better option.

The new data size is 24,724 bytes, up from 24,412 bytes (+312, -104 from
the 52 first layer nodes going from 4-bytes to 2-bytes, and +416 from
the addition of the 'first to second layer link' data).

In terms of raw matching speed (outside the context of the tokenizer),
this provides about a 1.72x speedup.

In very named-character-reference-heavy tokenizer benchmarks, this
provides about a 1.05x speedup (the effect of named character reference
matching speed is diluted when benchmarking the tokenizer).

Additionally, fixes the size of the named character reference data when
targeting Windows.
2025-07-14 09:43:08 +02:00
Andrew Kaster
3040ca4311 LibWeb: Remove noisy debug messages from HTMLParser 2025-07-09 16:26:49 -06:00
Luke Wilde
2368641de5 LibWeb: Track if element was created from token with dupe attributes
This is required for CSP to ignore the nonce attribute to prevent
duplicate attributes hijacking the attribute.

See https://w3c.github.io/webappsec-csp/#security-nonce-hijacking
2025-07-09 15:52:54 -06:00
Ryan Liptak
7096a2892e LibWeb/HTML: Use lookahead when possible for named character references
When there is an active insertion point, it's necessary to tokenize
code-point-by-code-point to handle the case of document.write being
used to insert a named character reference one code point at a time.

However, when there is no insertion point defined, looking ahead at the
input and doing the matching all-at-once is more efficient since it
allows:

- Avoiding the work done in next_code_point between each code point
  being matched (leading to better CPU cache usage in theory)
- Skipping ahead to the end of the match all at once, which does less
  work overall than the equivalent number of next_code_point calls
  (that is, skip(N) does less work than next_code_point called N times)

In my benchmarking, this provides a small performance boost (fewer
instructions, fewer cpu cycles, fewer branch misses) essentially for
free.
2025-07-04 11:11:19 +02:00
Tim Ledbetter
8828e0d791 LibWeb: Avoid updating muted state on muted content attribute changes
The `muted` content attribute should only affect the state of the
`muted` IDL property when the media element is first created. The
attribute should have no dynamic effect.
2025-06-27 09:14:54 +12:00
mikiubo
ff78746be1 LibWeb: Set readyState to complete for DOMParser documents
Documents created via DOMParser.parseFromString()
are parsed synchronously and do not participate in the
browsing context's loading pipeline.

This patch ensures that if the document has no browsing context
(i.e. was parsed via DOMParser),
its readiness is set to "complete" synchronously.

Fixes WPT:
domparsing/xmldomparser.html
2025-06-25 20:49:03 +12:00
Sam Atkins
423cdd447d LibWeb+LibGfx: Apply editorial punctuation/whitespace/markup fixes
Corresponds to d426109ea1
and fd08f81d06
2025-06-25 03:12:19 +12:00
Sam Atkins
a35d14eab3 LibWeb/HTML: Add or update spec steps in HTML parser
Partly corresponds to this which adds numbering to some substeps:
d426109ea1

This is not a complete review of all the spec steps to check that
they're up to date - I just updated the parts affected by that above
commit, and then added some `->` marks to places I noticed it was
missing. There may be actual spec differences still.

An actual change that needs tackling later is that `handle_in_head()`'s
branch for `<template>` has some new steps related to custom element
registries.
2025-06-25 03:12:19 +12:00
Shannon Booth
1fed3d27c1 LibWeb/HTML: Don't set opaque origin on innerHTML document
This appears to no longer be necessary now that we are properly
handling the loading of image data for the <img> element.
2025-06-24 09:56:14 +02:00
Shannon Booth
e0d7278820 LibURL+LibWeb: Make URL::Origin default constructor private
Instead, porting over all users to use the newly created
Origin::create_opaque factory function. This also requires porting
over some users of Origin to avoid default construction.
2025-06-17 20:54:03 +02:00
Shannon Booth
5deb8ba2f8 LibWeb: Explicitly set Document's origin
As part of the effort of removing the default constructor of
Origin, since document has the origin set after construction,
port Document's origin over to an Optional<Origin>.

This exposes that we were never setting the origin of the document
during fragment parsing. For now, to maintain previous behaviour,
let's explicitly set it to an opaque origin.
2025-06-17 20:54:03 +02:00
Gingeh
f1eaecc630 LibWeb: Escape "<" and ">" when serializing attribute values
See https://github.com/whatwg/html/pull/6362
2025-05-22 07:55:34 +01:00
Shannon Booth
579730d861 LibWeb: Prefer using equals_ignoring_ascii_case
Which has an optmization if both size of the string being passed
through are FlyStrings, which actually ends up being the case
in some places during selector matching comparing attribute names.
Instead of maintaining more overloads of
Infra::is_ascii_case_insensitive_match, switch
everything over to equals_ignoring_ascii_case instead.
2025-05-21 13:45:02 +01:00
Timothy Flynn
7280ed6312 Meta: Enforce newlines around namespaces
This has come up several times during code review, so let's just enforce
it using a new clang-format 20 option.
2025-05-14 02:01:59 -06:00
Mikkel Krautz
c48a78e37f LibWeb: Fix copyright headers with inconsistent > characters 2025-05-12 11:21:04 -06:00
Andreas Kling
263b125782 LibWeb: Let HTMLTokenizer walk over code points instead of UTF-8
Instead of using UTF-8 iterators to traverse the HTMLTokenizer input
stream one code point at a time, we now do a one-shot conversion up
front from the input encoding to a Vector<u32> of Unicode code points.

This simplifies the tokenizer logic somewhat, and ends up being faster
as well, so win-win.

1.02x speedup on Speedometer 2.1
2025-05-11 01:13:20 +02:00
Shannon Booth
084cceab5c LibWeb: Split out SimilarOriginWindowAgent from HTML::Agent
To allow for adding the concept of a WorkerAgent to be reused
between shared and dedicated workers. An event loop is the
commonality between the different agent types, though, there
are some differences between those event loops which we customize
on the construction of the HTML::EventLoop.
2025-04-25 14:07:51 +02:00
Andreas Kling
27efb3b140 LibWeb: When declarative shadow attachment fails, continue in right spot
If attachment fails for whatever reason (e.g the host element is not
allowed to be a host), the HTML spec tells us to insert the template
element anyway and proceed.

Before this change, we were recomputing the insertion location at this
point, which caused it to be *inside* the template element. Inserting
the template element into itself didn't work, and so the DOM would end
up incorrect.

The fix here is to simply use the insertion point we determined earlier
in the same function, before putting a template element on the stack of
open elements. We already do this elsewhere.

Fixes at least 228 subtests on WPT. :^)
2025-04-25 11:01:17 +02:00
Andreas Kling
e5d62e9915 LibWeb: Track whether HTMLLinkElement was enabled when created by parser
This information is needed by the script-blocking style sheet logic, and
its absence was causing a WPT test to crash.
2025-04-24 18:26:54 +02:00
Andreas Kling
5085b0dd66 LibWeb: Remove unused HTMLToken::Position::byte_offset 2025-04-20 18:43:11 +02:00
Andrew Kaster
6d11414957 LibWeb: Make storage of CSS::StyleValues const-correct
Now we consistently use `RefPtr<StyleValue const>` for all StyleValues.
2025-04-16 10:41:44 -06:00
Andrew Kaster
8cfac6ed71 LibWeb: Store a SpeculativeHTMLParser on the HTML Parser
The parser was previously added, but unused. Actually attaching one to
the HTML Parser will let us test the limits of Swift interop.
2025-04-16 09:02:27 -06:00
Sam Atkins
9dbeecb73d LibWeb: Correct some spec typos
Some checks are pending
CI / Lagom (arm64, Sanitizer_CI, false, macos-15, macOS, Clang) (push) Waiting to run
CI / Lagom (x86_64, Fuzzers_CI, false, ubuntu-24.04, Linux, Clang) (push) Waiting to run
CI / Lagom (x86_64, Sanitizer_CI, false, ubuntu-24.04, Linux, GNU) (push) Waiting to run
CI / Lagom (x86_64, Sanitizer_CI, true, ubuntu-24.04, Linux, Clang) (push) Waiting to run
Package the js repl as a binary artifact / build-and-package (arm64, macos-15, macOS, macOS-universal2) (push) Waiting to run
Package the js repl as a binary artifact / build-and-package (x86_64, ubuntu-24.04, Linux, Linux-x86_64) (push) Waiting to run
Run test262 and test-wasm / run_and_update_results (push) Waiting to run
Lint Code / lint (push) Waiting to run
Label PRs with merge conflicts / auto-labeler (push) Waiting to run
Push notes / build (push) Waiting to run
Corresponds to 285a58bf30
2025-04-10 04:01:37 +02:00
Andrew Kaster
9ee2473aa4 LibWeb+LibGC: Import GC swift module into LibWeb and an initial user
Start work on a speculative HTML Parser in Swift. This component will
walk ahead of the normal HTML parser looking for fetch() requests to
make while the normal parser is blocked. This work exposed many holes in
the Swift C++ interop component, which have been reported upstream.
2025-04-03 16:47:48 -06:00
Sam Atkins
7367150536 LibWeb/HTML: Update FIXME to not reset form-associated custom elements
Corresponds to e6bdd0557a
2025-04-02 17:28:06 +01:00
Andreas Kling
f1914893e9 LibJS+LibWeb: Remove more uses of DeprecatedFlyString 2025-03-24 22:27:17 +00:00
Ryan Liptak
0b0f47e320 LibWeb: Make named character references more spec-compliant & efficient
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 `&notin;` 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. `&notindo` which could lead to `&notindot;`),
some backtracking is performed after-the-fact in order to only consume
the code points within the longest match found (e.g. `&notindo` would
backtrack back to `&not`).

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.
2025-03-22 16:03:44 +01:00
Sam Atkins
415dd1be06 LibWeb/HTML: Remove "flag" word from usage of "page showing"
Corresponds to 30935f3474
2025-03-14 20:33:25 +00:00
InvalidUsernameException
0e1eb4d4a7 LibWeb: Respect scroll position set by script during page load
When setting scroll position during page load we need to consider
whether we actually have a fragment to scroll to. A script may already
have run at that point and may already have set a scroll position.

If there is an actual fragment to scroll to, it is fine to scroll to
that fragment, since it should take precedence. If we don't have a
fragment however, we should not unnecessarily overwrite the scroll
position set by the script back to (0, 0).

Since this problem is caused by a spec bug, I have tested the behavior
in the three major browsers engines. Unfortunately they do not agree
fully with each other. If there is no fragment at all (e.g. `foo.html`),
all browsers will respect the scroll position set by the script. If
there is a fragment (e.g. `foo.html#bar`), all browsers will set the
scroll position to the fragment element and ignore the one set by
script. However, when the fragment is empty (e.g. `foo.html#`), then
Blink and WebKit will set scroll position to the fragment, while Gecko
will set scroll position from script. Since all of this is ad-hoc
behavior anyway, I simply implemented the Blink/WebKit behavior because
of the majority vote for now.

This fixes a regression introduced in 51102254b5.
2025-03-10 17:14:13 +01:00
Andreas Kling
043e96946f LibWeb: Block rendering until linked stylesheets are loaded
This commit implements the main "render blocking" behavior for link
elements, drastically reducing the amount of FOUC (flash of unstyled
content) we subject our users to.

The document will now block rendering until linked style sheets
referenced by parser-created link elements have loaded (or failed).

Note that we don't yet extend the blocking period until "critical
subresources" such as imported style sheets have been downloaded
as well.
2025-02-27 21:36:40 +01:00
Tim Ledbetter
a187d5f28f LibWeb/SVG: Process script element when its text content changes 2025-02-26 16:08:35 +01:00
Jaycadox
f672c57ca7 LibWeb: Check charset UTF-16LE/BE separately for UTF-8 conversion
Previously, the charset of name "UTF-16BE/LE" would be checked against
when following standards to convert the charset to UTF-8, but in
reality, the charsets "UTF-16BE" and "UTF-16LE" should be checked
separately.

Co-authored-by: Jelle Raaijmakers <jelle@ladybird.org>
2025-02-24 14:51:41 +01:00
Sam Atkins
334c55c999 LibWeb/HTML: Add missing spec text/link for insert_html_element() 2025-02-20 21:55:34 +00:00
Sam Atkins
91fe0e1a1a LibWeb/HTML: Spec-ify reset_the_insertion_mode_appropriately()
It was already to-spec, with a couple of non-behavior-affecting changes,
but now it's clearer that this is the case. :^)
2025-02-20 21:55:34 +00:00
Sam Atkins
d7b4e1f2e3 LibWeb: Add missing text to find_appropriate_place_for_inserting_node() 2025-02-20 21:55:34 +00:00
Andreas Kling
550613e526 LibWeb: Remember when HTML parser should ignore next line feed character
There's a quirk in HTML where the parser should ignore any line feed
character immediately following a `pre` or `textarea` start tag.

This was working fine when we could peek ahead in the input stream and
see the next token, but didn't work in character-at-a-time parsing with
document.write().

This commit adds the "can ignore next line feed character" as a parser
flag that is maintained across invocations, making it work in this
parsing mode as well.

20 new passes in WPT/html/syntax/parsing/ :^)
2025-02-20 14:32:13 +01:00
Andreas Kling
611833429a LibWeb: Lazily merge text nodes when invoking HTML parser incrementally
Instead of always inserting a new text node, we now continue appending
to an extisting text node if the parser's character insertion point is
a suitable text node.

This fixes an issue where multiple invocations of document.write() would
create unnecessary sequences of text nodes. Such sequences are now
merged automatically.

19 new passes in WPT/html/syntax/parsing/ :^)
2025-02-20 14:32:13 +01:00
Andreas Kling
0c0fe09e70 LibWeb: Preserve attributes in "reconstruct active formatting elements"
25 new passes in WPT/html/syntax/parsing/ :^)
2025-02-20 14:32:13 +01:00
Andreas Kling
7549f6842f LibWeb: Ensure "frameset ok" flag is disabled after parsing pre tag
2 new passes in WPT/html/syntax/parsing/ :^)
2025-02-20 14:32:13 +01:00
Andreas Kling
2e59dbd10f LibWeb: Don't process frameset token twice in "in body" insertion mode
We were neglecting to return after handling the `frameset` start tag,
which caused us to process it twice, once properly and once generically.

54 new passes in WPT/html/syntax/parsing/ :^)
2025-02-20 14:32:13 +01:00
Andreas Kling
6f7b865cd1 LibWeb: Let HTML parser handle EOF inserted by document.close()
Before this change, the explicit EOF inserted by document.close() would
instantly abort the parser. This meant that parsing algorithms that ran
as part of the parser unwinding on EOF would never actually run.

591 new passes in WPT/html/syntax/parsing/ :^)

This exposed a problem where the parser would try to insert a root
<html> element on EOF in a document where someone already inserted such
an element via direct DOM manipulation. The parser now gracefully
handles this scenario. It's covered by existing tests (which would
crash without this change.)
2025-02-20 14:32:13 +01:00
Shannon Booth
7441aa34e4 LibWeb/HTML: Bail from HTML parsing when EOF hit on document.close
This fixes a crash in the included test that regressed in 0adf261,
and is hit by the following HTML:

```html
<body></body>
<script>
  const frame = document.body.appendChild(document.createElement("iframe"));
  frame.contentDocument.open();
  const child = frame.contentDocument.createElement("html")
  const html = frame.contentDocument.appendChild(child);
  frame.contentDocument.close();
</script>
```

I am not 100% sure this is fully the correct fix and there are other
cases which would not work properly. But it's definitely an improvement
to make the confuisingly named 'insert_an_eof' function of the tokenizer
actually do something.
2025-02-09 19:20:09 +00:00
Andreas Kling
4f855286d7 LibWeb: Clamp layout content sizes to a max value instead of crashing
We've historically asserted that no "saturated" size values end up as
final metrics for boxes in layout. This always had a chance of producing
false positives, since you can trivially create extremely large boxes
with CSS.

The reason we had those assertions was to catch bugs in our own engine
code where we'd incorrectly end up with non-finite values in layout
algorithms. At this point, we've found and fixed all known bugs of that
nature, and what remains are a bunch of false positives on pages that
create very large scrollable areas, iframes etc.

So, let's change it! We now clamp content width and height of boxes to
17895700 pixels, apparently the same cap as Firefox uses.

There's also the issue of calc() being able to produce non-finite
values. Note that we don't clamp the result of calc() directly, but
instead just clamp values when assigning them to content sizes.

Fixes #645.
Fixes #1236.
Fixes #1249.
Fixes #1908.
Fixes #3057.
2025-02-05 18:28:55 +01:00
Tim Ledbetter
8dfd382e12 LibWeb: Use as_if instead of dynamic_cast in a few places 2025-01-31 14:29:48 +01:00
Sam Atkins
3775f3399c LibWeb: Fix various typos
Corresponds to:
- https://github.com/whatwg/html/pull/10934
- https://github.com/whatwg/html/pull/10950
2025-01-30 15:00:16 +00:00
Timothy Flynn
85b424464a AK+Everywhere: Rename verify_cast to as
Follow-up to fc20e61e72.
2025-01-21 11:34:06 -05:00
Shannon Booth
51102254b5 LibWeb/HTML: Scroll to the fragment before loading the document
Otherwise nowhere ends up scrolling to the fragment specified by the
fragment in document's URL. This fixes ladybird scrolling to the
correct location in the document when navigating to a link that
has a fragment, e.g:

https://html.spec.whatwg.org/multipage/browsing-the-web.html#try-to-scroll-to-the-fragment

As well as use of the :target selector.
2025-01-15 12:43:48 +00:00
Shannon Booth
64eeda6450 LibWeb: Return a representation of an 'Agent' in 'relevant agent'
This makes it more convenient to use the 'relvant agent' concept,
instead of the awkward dynamic casts we needed to do for every call
site.

mutation_observers is also changed to hold a GC::Root instead of raw
GC::Ptr. Somehow this was not causing problems before, but trips up CI
after these changes.
2025-01-11 10:39:48 -05:00
Tim Ledbetter
f8b8c9c4a4 LibWeb: Wait until ReadyState is complete before detaching HTML parser
Previously, the DOM complete time was never being set, as the HTML
parser was detached before `DocumentReadyState` was set to complete.
2025-01-11 11:11:52 +01:00
Tim Ledbetter
8b5e9c2a1d LibWeb: Emit comment token for unterminated bogus comments on EOF 2025-01-11 11:09:47 +01:00