commit 1b3a56de114a90840edbb2a5f42b41408c563e37
author Byungwoo Lee <blee@igalia.com> Thu Jun 03 10:02:37 2021
committer Chromium LUCI CQ <chromium-scoped@luci-project-accounts.iam.gserviceaccount.com> Thu Jun 03 10:02:37 2021
tree 1e9c2201e867e3ee0b68c7050c75848a21e97d18
parent 46c1cf7c7d2906cb72aacc4485b861df766cf2c2

Supports :has() pseudo class matching

Add :has() pseudo class syntax support and matching logic behind a
runtime test feature (CSSPseudoHas)

<Syntax support>
Add syntax support for :has() pseudo class specified in Selectors 4.
 - https://www.w3.org/TR/selectors-4/#relational

:has() pseudo class takes a relatvie selector list as an argument.
 - :has(<relative-selector-list>)
 - <relative-selector-list> = <relative-selector>#
 - <relative-selector> = <combinator>? <complex-selector>

<relative-selector> is also specified in Selector 4, but it is not
supported yet.
 - https://www.w3.org/TR/selectors-4/#relative

So this CL only supports :has argument selectors starting with
descendant combinator. Argument selectors starting with other
combinators are not supported yet.
 - .a:has(.b)    : Supported
 - .a:has(> .b)  : Not supported yet
 - .a:has(~ .b)  : Not supported yet
 - .a:has(+ .b)  : Not supported yet

<Selector matching>
Add :has() pseudo class selector matching logic.

This CL suggests a stack-allocated :has() matching status cache
to prevent repetitive tree traversal and argument selector matching
operation.

The cache stores each element status as below.
 - Matched : Checked :has() and matched
 - Checked : Checked :has() but not matched
 - NotChecked : Not checked :has() (default)

This is the pseudo code of the matching operation for the :has
pseudo class with descendant relative argument selectors.
(e.g. ':has(.a)' or ':has(:scope .a)')

 ┬ Allocate cache on stack memory
 ├ Enter the style recalculation(or node selector API) sequence
 │  ├ ...
 │  ├ Enter the selector matching sequence
 │  │  ├ If matching :has pseudo class on an element
 │  │  │  └ Enter :has selector matching sequence
 │  │  │     ├ Get argument selector
 │  │  │     ├ Get element status from cache
 │  │  │     ├ If the element status is checked
 │  │  │     │  └ If the element status is matched
 │  │  │     │    └ Finish has pseudo class matching as matched
 │  │  │     ├ Else
 │  │  │     │  ├ Set the element status as checked
 │  │  │     │  └ Traverse all descendants of the element
 │  │  │     │    ├ Get the descendant status from cache
 │  │  │     │    ├ If the descendant status is checked
 │  │  │     │    │  └ If the descendant status is matched
 │  │  │     │    │    ├ Set the element status as matched
 │  │  │     │    │    └ Finish has pseudo class matching as matched
 │  │  │     │    └ Else
 │  │  │     │      ├ Set the descendant status as checked
 │  │  │     │      └ If the descendant matches the argument selector
 │  │  │     │        ├ Get start element of the shortest match
 │  │  │     │        ├ Traverse it's ancestors until met the element
 │  │  │     │        │  └ Set the ancestor status as matched
 │  │  │     │        ├ Set the element status as matched
 │  │  │     │        └ Finish has pseudo class matching as matched
 │  │  │     └ Finish has pseudo class matching as not matched
 │  │  └ Otherwise
 │  │     └ Do other selector matching sequence
 │  └ ...
 └ Release cache from stack memory

Other cases will be handled later in the separated CLs.
 - :has(> .a) or :has(:scope > .a)
 - :has(~ .a) or :has(:scope ~ .a)
 - :has(+ .a) or :has(:scope + .a)

This CL supports :has with the following javascript APIs.
 - querySelector
 - querySelectorAll
 - matches
 - closest

Changes in this CL were originally in the below 2 CLs. Those are
merged to prevent a web_test failure. (jquery/traversing.html)
 - https://chromium-review.googlesource.com/c/chromium/src/+/2648150
 - https://chromium-review.googlesource.com/c/chromium/src/+/2695192

Change-Id: I1992b70d86f47fc5f98437e1e6abea2da021ef6b
Bug: 669058
Reviewed-on: https://chromium-review.googlesource.com/c/chromium/src/+/2914717
Reviewed-by: Rune Lillesveen <futhark@chromium.org>
Commit-Queue: Byungwoo Lee <blee@igalia.com>
Cr-Commit-Position: refs/heads/master@{#888799}