Bug 220711 - Optimize :hover/:active style invalidation for deep trees and descendant selectors
Summary: Optimize :hover/:active style invalidation for deep trees and descendant sele...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: CSS (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Nobody
URL:
Keywords: InRadar
Depends on:
Blocks:
 
Reported: 2021-01-18 08:57 PST by Antti Koivisto
Modified: 2022-01-22 00:20 PST (History)
13 users (show)

See Also:

Attachments
patch (14.46 KB, patch)
2021-01-18 09:05 PST, Antti Koivisto 		no flags Details | Formatted Diff | Diff
patch (17.23 KB, patch)
2021-01-18 09:51 PST, Antti Koivisto 		no flags Details | Formatted Diff | Diff
patch (17.17 KB, patch)
2021-01-18 10:02 PST, Antti Koivisto 		no flags Details | Formatted Diff | Diff
Show Obsolete (2) View All Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
Description Antti Koivisto 2021-01-18 08:57:39 PST 
Hover and active states are flipped for the entire ancestor chain. We compute invalidation for each element separately. If the selectors are of form ':active .descendant' then each of these invalidations need to traverse the whole subtree leading to O(n^2) behavior.

We really only need to traverse the descendants once, starting from the element closest to the root that changes state.
Comment 1 Antti Koivisto 2021-01-18 09:05:56 PST 
Created attachment 417836 [details]
patch
Comment 2 Antti Koivisto 2021-01-18 09:51:27 PST 
Created attachment 417839 [details]
patch
Comment 3 Antti Koivisto 2021-01-18 10:02:14 PST 
Created attachment 417840 [details]
patch
Comment 4 Antti Koivisto 2021-01-18 12:12:25 PST 
rdar://72138961
Comment 5 EWS 2021-01-18 12:26:29 PST 
Committed r271584: <https://trac.webkit.org/changeset/271584>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 417840 [details].
Comment 6 Radar WebKit Bug Importer 2021-01-18 12:27:13 PST 
<rdar://problem/73328176>
Comment 7 Antoine Quint 2021-01-22 08:52:51 PST 
I suspect this caused bug 220862.