layout: Avoid potential n² comparisons when updating children of accessibility nodes - #46530
Merged
Merged
Conversation
|
Member
Contributor
Author
mrobinson
approved these changes
Jul 16, 2026
github-merge-queue
Bot
removed this pull request from the merge queue due to failed status checks
Jul 16, 2026
Signed-off-by: Alice Boxhall <alice@igalia.com>
Signed-off-by: Alice Boxhall <alice@igalia.com>
Rather than using `zip_longest()`, just iterate over the child IDs and DOM children in parallel manually. This doesn't move the DOM children iterator, meaning we can pick up the iterator where we left off later. Signed-off-by: Alice Boxhall <alice@igalia.com>
Signed-off-by: Alice Boxhall <alice@igalia.com>
…()` if the child list has changed. Signed-off-by: Alice Boxhall <alice@igalia.com>
alice
force-pushed
the
accessibility-set-children
branch
from
July 17, 2026 10:40
1ff4d0f to
2851106
Compare
Contributor
Author
|
@mrobinson The last commit fixes the WPT test failure which caused it to fail the merge queue. |
mrobinson
enabled auto-merge
July 17, 2026 10:51
pull Bot
pushed a commit
to Haofei/servo
that referenced
this pull request
Jul 19, 2026
…ervo#46589) Note: this is a bit of a grab-bag of changes. Happy to split it out if necessary. Improvements: - Order `counters` above `rooted_nodes` in `AccesibilityUpdate`, and add a doc comment. - Fix a bug in computing the number of changed nodes in an update: - A node may be both changed and removed in a single update, which causes it to be tracked in `changed_nodes`, but we filter out removed nodes from the update (in fact, including them would cause a panic). The counter needs to track the number of nodes actually sent in the update. - Future work could avoid updating removed nodes at all, but that's out of scope here. - Rename fields in `AccessibilityUpdateResult` to remove redundant `accessibility`, making tests easier to read New tests: - Add `accessibility-update-partial-subtree-move-and-delete.html` to match the existing `test_accessibility_partial_subtree_move_and_delete` in `accessibility.rs` - Add `test_accessibility_children_of_heading_change` and `test_accessibility_descendants_of_heading_change`, and matching servo-wpt tests `accessibility-update-children-of-heading-change.html` and `accessibility-update-descendants-of-heading-change.html` to test that changing the subtree of a heading automatically causes its label to be recomputed. - These were added as a result of an error in servo#46530 not being picked up by existing tests. Testing: Existing and new tests pass. Fixes: part of servo#46346 --------- Signed-off-by: Alice Boxhall <alice@igalia.com>
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
5 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Previously, we always built a pair of vecs for the new children based on the DOM children, representing the child nodes and their IDs respectively, and then compared the old and new children to set the appropriate
TreeChangeon each added/removed child node.This change instead iterates over the existing child IDs and the new DOM children in parallel for as long as the two iterators match up, then removes the remaining children of the accessibility node and reconstructs the remaining children from the DOM children (reusing any existing accessibility nodes).
This also allows us to update the
child_nodesvec in-place, although we can't update thechildrenproperty of the AccessKit node the same way so we still need to re-create that if there is any change.Profiles:
before: https://share.firefox.dev/4f33Hlp
after: https://share.firefox.dev/4fePVuK
Testing: No behaviour change, covered by existing tests.
Fixes: #46237