Bug 220711

Summary: Optimize :hover/:active style invalidation for deep trees and descendant selectors
Product: WebKit Reporter: Antti Koivisto <koivisto>
Component: CSSAssignee: Nobody <webkit-unassigned>
Status: RESOLVED FIXED    
Severity: Normal CC: 04-punch-pinyons, cdumez, changseok, cmarcelo, esprehn+autocc, ews-watchlist, graouts, gyuyoung.kim, kangil.han, mifenton, simon.fraser, webkit-bug-importer, zalan
Priority: P2 Keywords: InRadar
Version: WebKit Nightly Build   
Hardware: Unspecified   
OS: Unspecified   
Attachments:
Description Flags
patch
none
patch
none
patch none

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.