script: Rewrite NodeList::ChildrenList with a cached Vec of nodes by SimonSapin · Pull Request #44435 · servo/servo

SimonSapin · 2026-04-22T13:02:54Z

In DOM APIs, Node.childNodes is a NodeList that has an .item(index) method that allows random access, but DOM nodes only store pointers to their first/last child and next/previous sibling. The previous implementation involved keeping a "last accessed" pointer, and a significant amount of logic to find the requested index by walking next/previous sibling pointers from whichever of last accessed, first child, or last child is nearest. This logic sometimes incorrectly assumed the (nullable) last accessed pointer to be present, causing a panic in Option::unwrap.

Rather than try to fix that logic, this replaces entirely with the approach suggested in #25206 and used by Firefox: keep a cached Vec of pointers to all child nodes, created lazily when needed, and invalidated whenever any part of it changes.

Testing: the first commit adds a failing WPT crashtest, the second commit fixes it
Fixes: #25206
Fixes: #36764

github-actions · 2026-04-22T13:07:29Z

🔨 Triggering try run (#24779803919) for Linux (WPT)

TimvdLippe

Nice fix!

github-actions · 2026-04-22T13:44:39Z

Test results for linux-wpt from try job (#24779803919):

Flaky unexpected result (29)

OK /IndexedDB/transaction-create_in_versionchange.any.html (#44200)

FAIL [expected PASS] subtest: Attempt to create new transactions inside a versionchange transaction

assert_array_equals: events expected property 4 to be "open_rq.success: [object IDBDatabase]" but got "complete_count.success: 2" (expected array ["versionchange_add.success: 1", "versionchange_count.success: 0", "versionchange_add2.success: 2", "versionchange_txn.complete", "open_rq.success: [object IDBDatabase]", "complete_count.success: 2", "complete2_get.success: 1"] got ["versionchange_add.success: 1", "versionchange_count.success: 0", "versionchange_add2.success: 2", "versionchange_txn.complete", "complete_count.success: 2", "open_rq.success: [object IDBDatabase]", "complete2_get.success: 1"])

OK /beacon/beacon-basic.https.window.html (#41723)
- FAIL [expected PASS] subtest: Payload size restriction should be accumulated: type = string
```
assert_false: expected false got true
```
FAIL [expected PASS] /css/css-backgrounds/border-image-repeat-space-9.html
OK /css/css-cascade/layer-font-face-override.html (#35935)
- PASS [expected FAIL] subtest: @font-face override update with appended sheet 1
- PASS [expected FAIL] subtest: @font-face override update with appended sheet 2
OK /css/css-fonts/generic-family-keywords-002.html (#40929)
- FAIL [expected PASS] subtest: font-family: -webkit-serif treated as <font-family>, not <generic-name>
```
assert_equals: expected 30 but got 50
```
- FAIL [expected PASS] subtest: font-family: -webkit-sans-serif treated as <font-family>, not <generic-name>
```
assert_equals: expected 30 but got 50
```
- FAIL [expected PASS] subtest: font-family: -webkit-cursive treated as <font-family>, not <generic-name>
```
assert_equals: expected 30 but got 50
```
- FAIL [expected PASS] subtest: font-family: -webkit-fantasy treated as <font-family>, not <generic-name>
```
assert_equals: expected 30 but got 50
```
- FAIL [expected PASS] subtest: font-family: -webkit-monospace treated as <font-family>, not <generic-name>
```
assert_equals: expected 30 but got 50
```
- FAIL [expected PASS] subtest: font-family: -webkit-system-ui treated as <font-family>, not <generic-name>
```
assert_equals: expected 30 but got 50
```
- FAIL [expected PASS] subtest: font-family: -webkit-math treated as <font-family>, not <generic-name>
```
assert_equals: expected 30 but got 50
```
- PASS [expected FAIL] subtest: font-family: -webkit-generic(fangsong) treated as <font-family>, not <generic-name>
- PASS [expected FAIL] subtest: font-family: -webkit-generic(kai) treated as <font-family>, not <generic-name>
- PASS [expected FAIL] subtest: font-family: -webkit-generic(khmer-mul) treated as <font-family>, not <generic-name>
- And 12 more unexpected results...
FAIL [expected PASS] /css/css-ui/webkit-appearance-menulist-button-001.html
CRASH [expected OK] /fetch/api/headers/headers-no-cors.any.worker.html
CRASH [expected OK] /fetch/api/request/request-init-001.sub.html
OK [expected ERROR] /fetch/fetch-later/quota/cross-origin-iframe/sandboxed-iframe.https.window.html
ERROR [expected OK] /fetch/fetch-later/quota/same-origin-iframe/multiple-iframes.https.window.html (#35176)
OK [expected ERROR] /focus/focus-event-after-switching-iframes.sub.html (#40368)
OK /html/browsers/browsing-the-web/navigating-across-documents/005.html (#27062)
- PASS [expected FAIL] subtest: Link with onclick navigation and href navigation
OK /html/browsers/browsing-the-web/navigating-across-documents/navigation-unload-cross-origin.sub.window.html (#29056)
- PASS [expected FAIL] subtest: Cross-origin navigation started from unload handler must be ignored
OK /html/browsers/history/the-history-interface/traverse_the_history_2.html (#21383)
- PASS [expected FAIL] subtest: Multiple history traversals, last would be aborted
OK /html/browsers/history/the-history-interface/traverse_the_history_4.html (#21383)
- FAIL [expected PASS] subtest: Multiple history traversals, last would be aborted
```
assert_array_equals: Pages opened during history navigation expected property 1 to be 5 but got 3 (expected array [6, 5] got [6, 3])
```
TIMEOUT [expected OK] /html/interaction/focus/the-autofocus-attribute/document-with-fragment-nonexistent.html (#28259)
- TIMEOUT [expected FAIL] subtest: Autofocus elements in top-level browsing context's documents with non-existent fragments should work.
```
Test timed out
```
OK /html/semantics/document-metadata/the-meta-element/pragma-directives/attr-meta-http-equiv-refresh/allow-scripts-flag-changing-2.html (#39703)
- FAIL [expected PASS] subtest: Meta refresh of the original iframe is not blocked if moved into a sandboxed iframe
```
uncaught exception: Error: assert_unreached: The iframe into which the meta was moved must not refresh Reached unreachable code
```
TIMEOUT [expected OK] /html/semantics/embedded-content/the-iframe-element/iframe_sandbox_navigate_other_frame_popup.sub.html (#39702)
- TIMEOUT [expected FAIL] subtest: Sandboxed iframe can not navigate other frame's popup
```
Test timed out
```
CRASH [expected ERROR] /html/semantics/forms/the-select-element/customizable-select/select-appearance-button-after-span.html
OK /html/semantics/scripting-1/the-script-element/module/dynamic-import/blob-url.any.html (#33948)
- FAIL [expected PASS] subtest: Revoking a blob URL immediately after calling import will not fail
```
promise_test: Unhandled rejection with value: object "TypeError: Module fetching failed"
```
TIMEOUT [expected OK] /html/user-activation/navigation-state-reset-sameorigin.html
- TIMEOUT [expected PASS] subtest: Post-navigation state reset.
```
Test timed out
```
OK /infrastructure/testdriver/click_iframe.html
- FAIL [expected PASS] subtest: TestDriver click on a document in an iframe
```
Unhandled rejection: assert_unreached: click failed Reached unreachable code
```
TIMEOUT [expected OK] /pointerevents/compat/pointerevent_touch-action_two-finger_interaction.html
- NOTRUN [expected PASS] subtest: touch two-finger pan on 'touch-action: pan-x pan-y'
- NOTRUN [expected FAIL] subtest: touch two-finger pan on 'touch-action: pinch-zoom'
OK /preload/prefetch-document.html (#37210)
- FAIL [expected PASS] subtest: different-site document prefetch with 'as=document' should not be consumed
```
assert_equals: expected 2 but got 1
```
OK /resource-timing/test_resource_timing.html (#25720)
- PASS [expected FAIL] subtest: PerformanceEntry has correct name, initiatorType, startTime, and duration (xmlhttprequest)
OK /visual-viewport/resize-event-order.html (#41981)
- PASS [expected FAIL] subtest: Popup: DOMWindow resize fired before VisualViewport.
CRASH [expected OK] /webaudio/the-audio-api/the-mediastreamaudiodestinationnode-interface/closed-audiocontext-construction.html
OK [expected TIMEOUT] /webstorage/localstorage-about-blank-3P-iframe-opens-3P-window.partitioned.html (#29053)
- FAIL [expected TIMEOUT] subtest: StorageKey: test 3P about:blank window opened from a 3P iframe
```
assert_true: about:blank window opened by 3P iframe does not inherit 3P iframe's StorageKey expected true got false
```
ERROR [expected OK] /workers/baseurl/alpha/sharedworker-in-worker.html (#21315)

Stable unexpected results that are known to be intermittent (21)

OK /IndexedDB/idbdatabase_deleteObjectStore.any.html (#43823)
- PASS [expected FAIL] subtest: Deleted object store's name should be removed from database's list. Attempting to use a deleted IDBObjectStore should throw an InvalidStateError
TIMEOUT [expected OK] /_mozilla/mozilla/window-resize-event.html (#36741)
- TIMEOUT [expected PASS] subtest: Popup onresize event fires after resizeTo
```
Test timed out
```

OK /_webgl/conformance/textures/misc/texture-upload-size.html (#21770)

FAIL [expected PASS] subtest: WebGL test #45

assert_true: Texture was smaller than the expected size 2x2 expected true got false

FAIL [expected PASS] subtest: WebGL test #47

assert_true: getError expected: INVALID_VALUE. Was NO_ERROR : when calling texSubImage2D with the same texture upload with offset 1, 1 expected true got false

FAIL [expected PASS] subtest: WebGL test #49

assert_true: Texture was smaller than the expected size 2x2 expected true got false

FAIL [expected PASS] subtest: WebGL test #51

assert_true: getError expected: INVALID_VALUE. Was NO_ERROR : when calling texSubImage2D with the same texture upload with offset 1, 1 expected true got false

PASS [expected FAIL] subtest: WebGL test #53
PASS [expected FAIL] subtest: WebGL test #55
PASS [expected FAIL] subtest: WebGL test #57
PASS [expected FAIL] subtest: WebGL test #59

FAIL [expected PASS] subtest: WebGL test #61

assert_true: Texture was smaller than the expected size 2x2 expected true got false

FAIL [expected PASS] subtest: WebGL test #63

assert_true: getError expected: INVALID_VALUE. Was NO_ERROR : when calling texSubImage2D with the same texture upload with offset 1, 1 expected true got false

And 10 more unexpected results...

ERROR /_webgl/conformance2/textures/misc/tex-3d-size-limit.html (#44383)

FAIL [expected PASS] subtest: WebGL test #77

assert_true: successfullyParsed should be true (of type boolean). Was undefined (of type undefined). expected true got false

OK [expected CRASH] /content-security-policy/meta/sandbox-iframe.html (#43478)
OK /css/css-fonts/generic-family-keywords-001.html (#37467)
- FAIL [expected PASS] subtest: @font-face matching for quoted and unquoted generic(fangsong)
```
assert_equals: quoted generic(fangsong) matches  @font-face rule expected 50 but got 30
```
- FAIL [expected PASS] subtest: @font-face matching for quoted and unquoted generic(nastaliq)
```
assert_equals: quoted generic(nastaliq) matches  @font-face rule expected 50 but got 30
```
OK /css/css-fonts/generic-family-keywords-003.html (#38994)
- PASS [expected FAIL] subtest: @font-face matching for quoted and unquoted cursive (drawing text in a canvas)
- FAIL [expected PASS] subtest: @font-face matching for quoted and unquoted fantasy (drawing text in a canvas)
```
assert_equals: quoted fantasy matches  @font-face rule expected 125 but got 40
```
- FAIL [expected PASS] subtest: @font-face matching for quoted and unquoted monospace (drawing text in a canvas)
```
assert_equals: quoted monospace matches  @font-face rule expected 125 but got 40
```
- PASS [expected FAIL] subtest: @font-face matching for quoted and unquoted generic(kai) (drawing text in a canvas)
- FAIL [expected PASS] subtest: @font-face matching for quoted and unquoted generic(khmer-mul) (drawing text in a canvas)
```
assert_equals: quoted generic(khmer-mul) matches  @font-face rule expected 125 but got 40
```
- FAIL [expected PASS] subtest: @font-face matching for quoted and unquoted ui-serif (drawing text in a canvas)
```
assert_equals: quoted ui-serif matches  @font-face rule expected 125 but got 40
```
- FAIL [expected PASS] subtest: @font-face matching for quoted and unquoted ui-sans-serif (drawing text in a canvas)
```
assert_equals: unquoted ui-sans-serif does not match @font-face rule expected 40 but got 125
```
ERROR [expected OK] /fetch/fetch-later/quota/same-origin-iframe/sandboxed-iframe.https.window.html (#41704)
OK /fetch/metadata/generated/css-font-face.https.sub.tentative.html (#32732)
- PASS [expected FAIL] subtest: sec-fetch-mode
- FAIL [expected PASS] subtest: sec-fetch-storage-access - Cross-site
```
promise_test: Unhandled rejection with value: object "Error: Failed to query for recorded headers."
```
TIMEOUT /fetch/metadata/generated/css-images.https.sub.tentative.html (#42229)
- FAIL [expected PASS] subtest: content sec-fetch-site - Cross-Site -> Same-Site
```
assert_unreached: Reached unreachable code
```
- FAIL [expected PASS] subtest: content sec-fetch-site - Same-Origin -> Same Origin
```
assert_unreached: Reached unreachable code
```
OK /html/browsers/browsing-the-web/navigating-across-documents/navigation-unload-same-origin-fragment.html (#20768)
- FAIL [expected PASS] subtest: Tests that a fragment navigation in the unload handler will not block the initial navigation
```
assert_equals: expected "" but got "#fragment"
```
TIMEOUT [expected OK] /html/browsers/browsing-the-web/navigating-across-documents/replace-before-load/form-submit-button-click.html (#44099)
- TIMEOUT [expected FAIL] subtest: Replace before load, triggered by submitButton.click()
```
Test timed out
```
CRASH [expected TIMEOUT] /html/browsers/history/the-location-interface/location_replace_session_history.html (#41896)

OK [expected TIMEOUT] /html/interaction/focus/the-autofocus-attribute/supported-elements.html (#24145)

FAIL [expected NOTRUN] subtest: Host element with delegatesFocus including no focusable descendants should be skipped

assert_equals: expected Element node &lt;input autofocus=""&gt;&lt;/input&gt; but got Element node &lt;body&gt;&lt;div autofocus=""&gt;&lt;/div&gt;&lt;input autofocus=""&gt;&lt;/body&gt;

FAIL [expected NOTRUN] subtest: Area element should support autofocus

promise_test: Unhandled rejection with value: object "TypeError: can't access property "appendChild", w.document.querySelector(...) is null"

OK /html/semantics/document-metadata/the-meta-element/pragma-directives/attr-meta-http-equiv-refresh/allow-scripts-flag-changing-1.html (#39694)
- FAIL [expected PASS] subtest: Meta refresh is blocked by the allow-scripts sandbox flag at its creation time, not when refresh comes due
```
uncaught exception: Error: assert_unreached: The iframe from which the meta came from must not refresh Reached unreachable code
```
OK [expected TIMEOUT] /infrastructure/testdriver/click_nested.html (#43887)
- FAIL [expected NOTRUN] subtest: TestDriver click method with multiple windows and nested iframe
```
can't access property "document", child.frames[2] is undefined
```
OK /mixed-content/tentative/autoupgrades/mixed-content-cors.https.sub.html (#41123)
- PASS [expected FAIL] subtest: Cross-Origin video should get upgraded even if CORS is set
OK /navigation-timing/test-navigation-type-reload.html (#33334)
- PASS [expected FAIL] subtest: Reload domInteractive > Original domInteractive
- PASS [expected FAIL] subtest: Reload fetchStart > Original fetchStart
OK /resource-timing/buffer-full-add-then-clear.html (#40819)
- FAIL [expected PASS] subtest: Test that if the buffer is cleared after entries were added to the secondary buffer, those entries make it into the primary one
```
assert_equals: Number of entries does not match the expected value. expected 3 but got 0
```
OK /touch-events/single-tap-when-touchend-listener-use-sync-xhr.html (#41175)
- PASS [expected FAIL] subtest: Click event should be fired when touchend opens synchronous XHR
OK [expected ERROR] /webxr/render_state_update.https.html (#27535)

github-actions · 2026-04-22T13:44:48Z

✨ Try run (#24779803919) succeeded.

servo#36764 Signed-off-by: Simon Sapin <simon@igalia.com>

In DOM APIs, `Node.childNodes` is a `NodeList` that has an `.item(index)` method that allows random access, but DOM nodes only store pointers to their first/last child and next/previous sibling. The previous implementation involved keeping a "last access" pointer, and a significant amount of logic to find the requested index by walking next/previous sibling pointers from whichever of last access, first child, or last child is nearest. This logic sometimes incorrectly assumed the (nullable) last accessed pointer to be present, causing a panic in `Option::unwrap`. Rather than try to fix that logic, this replaces entirely with the approach suggested in servo#25206 and used by Firefox: keep a cached `Vec` of pointers to all child nodes, created lazily when needed, and invalidated whenever any part of it changes. Fixes servo#25206 Fixes servo#36764 Signed-off-by: Simon Sapin <simon@igalia.com>

servo-wpt-sync · 2026-04-22T14:59:27Z

🤖 Opened new upstream WPT pull request (web-platform-tests/wpt#59405) with upstreamable changes.

servo-wpt-sync · 2026-04-22T15:40:35Z

✍ Updated existing upstream WPT pull request (web-platform-tests/wpt#59405) title and body.

Pass `&JsContext` in a few more places in order to use `*_no_gc` APIs. This is a follow-up to servo#44435 Testing: expecting no change to existing test results --------- Signed-off-by: Simon Sapin <simon@igalia.com>

SimonSapin requested a review from gterzian as a code owner April 22, 2026 13:02

servo-highfive added the S-awaiting-review There is new code that needs to be reviewed. label Apr 22, 2026

SimonSapin added the T-linux-wpt Do a try run of the WPT label Apr 22, 2026

github-actions Bot removed the T-linux-wpt Do a try run of the WPT label Apr 22, 2026

TimvdLippe approved these changes Apr 22, 2026

View reviewed changes

Comment thread tests/wpt/tests/dom/nodes/crashtests/childNodes-last_visited-unwrap-crash.html

servo-highfive removed the S-awaiting-review There is new code that needs to be reviewed. label Apr 22, 2026

SimonSapin added 2 commits April 22, 2026 16:52

Add WPT crashtest for unwrap panic in NodeList::ChildrenList

95a7911

servo#36764 Signed-off-by: Simon Sapin <simon@igalia.com>

SimonSapin force-pushed the childlist-vec branch from 110f9e9 to d0e2bab Compare April 22, 2026 14:54

servo-highfive added the S-awaiting-review There is new code that needs to be reviewed. label Apr 22, 2026

TimvdLippe enabled auto-merge April 22, 2026 14:57

servo-wpt-sync mentioned this pull request Apr 22, 2026

script: Rewrite NodeList::ChildrenList with a cached Vec of nodes web-platform-tests/wpt#59405

Merged

TimvdLippe added this pull request to the merge queue Apr 22, 2026

servo-highfive added the S-awaiting-merge The PR is in the process of compiling and running tests on the automated CI. label Apr 22, 2026

github-merge-queue Bot removed this pull request from the merge queue due to failed status checks Apr 22, 2026

servo-highfive added S-tests-failed The changes caused existing tests to fail. and removed S-awaiting-merge The PR is in the process of compiling and running tests on the automated CI. labels Apr 22, 2026

mrobinson changed the title ~~Rewrite NodeList::ChildrenList with a cached Vec of nodes~~ script: Rewrite NodeList::ChildrenList with a cached Vec of nodes Apr 22, 2026

Gae24 added this pull request to the merge queue Apr 22, 2026

servo-highfive added S-awaiting-merge The PR is in the process of compiling and running tests on the automated CI. and removed S-tests-failed The changes caused existing tests to fail. labels Apr 22, 2026

Merged via the queue into servo:main with commit 4535a7d Apr 22, 2026
40 checks passed

servo-highfive removed the S-awaiting-merge The PR is in the process of compiling and running tests on the automated CI. label Apr 22, 2026

mrobinson mentioned this pull request Apr 23, 2026

Crash on DonanimHaber forum - Option::unwrap() on a None value #44442

Closed

SimonSapin deleted the childlist-vec branch April 23, 2026 09:10

This was referenced Jul 20, 2026

script: Reduce GC-rooting in NodeList #46664

Merged

Iterating getElementsByName() is O(n²) to the document size #46665

Open

Navigation Menu

Uh oh!

Uh oh!

script: Rewrite NodeList::ChildrenList with a cached Vec of nodes - #44435

script: Rewrite NodeList::ChildrenList with a cached Vec of nodes#44435
Gae24 merged 2 commits into
servo:mainfrom
SimonSapin:childlist-vec

SimonSapin commented Apr 22, 2026 •

edited

Loading

Uh oh!

github-actions Bot commented Apr 22, 2026

Uh oh!

TimvdLippe left a comment

Uh oh!

Uh oh!

github-actions Bot commented Apr 22, 2026

Uh oh!

github-actions Bot commented Apr 22, 2026

Uh oh!

servo-wpt-sync commented Apr 22, 2026

Uh oh!

Uh oh!

servo-wpt-sync commented Apr 22, 2026

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

Uh oh!

Uh oh!

Conversation

SimonSapin commented Apr 22, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

github-actions Bot commented Apr 22, 2026

Uh oh!

TimvdLippe left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

github-actions Bot commented Apr 22, 2026

Uh oh!

github-actions Bot commented Apr 22, 2026

Uh oh!

servo-wpt-sync commented Apr 22, 2026

Uh oh!

Uh oh!

servo-wpt-sync commented Apr 22, 2026

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

SimonSapin commented Apr 22, 2026 •

edited

Loading