Bug 220711

Summary:

Optimize :hover/:active style invalidation for deep trees and descendant selectors

Product:

WebKit

Reporter:

Antti Koivisto <koivisto>

Component:

CSS

Assignee:

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:

Keywords:

InRadar

Version:

WebKit Nightly Build

Hardware:

Unspecified

OS:

Unspecified

Attachments:

Description	Flags
patch	none
patch	none
patch	none

Antti Koivisto

Reported 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.

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 attachment proposed patch, testcase, etc.