CSS selector matching is pretty straightforward, starting with the subject and moving upwards in the document tree matching each of the simple selectors until you have a match, or a failing one. There are a couple of performance challenges being solved and described in this document. One is the problem of reloading CSS properties for as few elements as necessary when the dynamic pseudo state for elements change. The other is an inherent O(n!) complexity for descendant selectors (and indirect adjacent sibling selectors in CSS3).
In order to reload properties for as few elements as possible, we would have had to store for a given element which other elements would possibly affect a selector match for that element. That would have required too much memory.
As a simple approximation, we mark elements which are affected by dynamic pseudo classes with a bit per dynamic pseudo class. The elements are marked during selector matching. Below is a formal description of how document elements are marked.
Let document D be a set of elements in a given document, and G the set of selectors from the stylesheets which apply to the document.
Let S be a selector in G consisting of n simple selectors (simple selectors as in CSS2.1) s1 to sn with arbitrary combinators, and sn be the simple selector that matches the subject.
Let S' denote the selector that consists of simple selectors s'1 to s'n where each simple selector s'i is the simple selector si from S with all dynamic pseudo classes removed.
Let E, consisting of elements e1 to en, denote a match for selector S' where each element ei ∈ D matches the simple selector s'i of S'.
Then, for every S ∈ G
LayoutWorkplace::ApplyPropertyChanges is called for applying the dynamic pseudo style. It marks properties dirty for the elements which needs to reload the CSS properties based on the marked bits.
selector: div:hover input:focus document source: <div> <input type="text"> </div>The div element will be marked with hover because hovering the div will affect the selector match, and the input will be marked with both hover and focus because hovering another element in the tree (in this case the div), or focusing the input will require a reload of the CSS properties for the input.
selector: .myclass div:hover document source: <div class="yourclass"> <div> </div> </div>No element will be marked because the class selector doesn't match. If the class attribute is changed to "myclass" via DOM, the div with the class attribute will have the CSS properties reloaded and CSS properties reloaded. The reload will ensure the pseudo bits are set correctly.
Updating dynamic pseudo style for :hover is a bit different because when you hover an element, all its ancestors are automatically also in their a hovered state. So when you hover an element deep down in the tree, the body element is also hovered which can cause the whole document tree to have the CSS properties reloaded.
Consider this example:
selector:
body:hover div#not_hovered
document source:
<body>
<div>
...
<div id="not_hovered" />
...
</div>
<div>
...
<div id="hovered" />
...
</div>
</body>
When you hover the element with id="hovered", the body element will
also be hovered. That means that all child elements of body
potentially will have to have their CSS properties reloaded because of
the rules with the type of selectors as in the example above. So, the
properties have to be reloaded for not_hovered, even though it's not
an ancestor or descendant of the hovered element.
We have been re-applying hover quite inefficiently by doing:
Say that we have a document tree like the one in Figure 3.1 and that we have a stylesheet applied which causes the element nodes to be marked with dynamic pseudo bits as indicated with the red squares. If we hover between the two leaf nodes marked with the number 1. The closest common parent (also marked 1) will have the save hover style when both leaf nodes are hovered. That means we can get away with recursively reloading the properties for the children of the closest common parent.
In the case where we don't have a common parent with the dynamic pseudo bit set, we have to reload the sub tree for both the old and new hovered element starting from the top-most parent of the respective elements with the dynamic pseudo bit set. This is the case when hovering between the two nodes marked with 2 in Figure 3.1.
Descendant selectors can have any number of elements between the matching elements of the simple selectors. This means a brute force can be ugly performance-wise. Consider the case where we have a selector of n div elements with descendant combinators:
div div div ... divand a document subtree consisting of n-1 div elements, assuming there are no div elements in the dom tree which is a parent of the subtree root.
div
\
div
\
...
\
div
The selector will not match any of the n-1 div elements in the
subtree. But, consider how we would match the selector from the
subject and upwards in the dom tree. We start by matching the subject
which is the nth div in the selector and the (n-1)th div in the
subtree. Then, we start looking for candidates for the ascendant div,
and start with the parent. The parent ((n-2)th div in the
subtree) is a match for the (n-1)th div in the selector and this way,
we continue matching the divs in the subtree and the selector up to
the root div of the tree where we're left with an unmatched div
ascendant div in the selector.
Since this combination of divs doesn't match, we trace back to find the next candidate for the subject ascendant, which is the (n-3)th div in the subtree and continue matching from there.
So, for the nth descendant selector you have n-1 candidates for a match. For the whole selector selector, that is
(n-1)(n-2)...(1) = (n-1)!possible matches. This is just one example of the combinatory nature of descendant selectors that can cause performance problems. We have an optimization in our matching implementation, described in the next section, which has worked well so far.
To remedy the O(n!) problem described above, we have a depth first optimization starting with a tightest possible match for descendant selectors that stops the search for descendant selector candidates if we know that the selector cannot possibly match.
Let Ei,j, consisting of elements ei to ej be a partial match of S with 1 < i ≤ j ≤ n.
Then Ei,j is called a tight partial match iff for every descendant combinator separated sk and sk+1, i ≤ k < j, ek is the parent element of ek+1.
Let Ei,j be a partial match of S with 1 < i ≤ j ≤ n. And, let cn be the combinator between sn and sn+1.
Then Ei,j is called a failed top match iff one of these conditions hold:
Let S be a selector with n simple selectors, Ej,n be a partial match for sj to sn, 1 < j < n, for a subject e = en.
If there is a partial match Ei,j, 1 < i ≤ j, sharing ej with Ej,n, which is both a tight partial match, and a failed top match, there exists no partial match E1,j of S1,j and hence no match E containing the partial match Ej,n of S for the subject e.
I don't have a formal proof for this.
This means that we can stop searching for descendant selector candidates if we reach the top of the document without a failure for the tightest possible match of a selector containing descendant combinators.
For the example with the n-1 divs above, we will get a tight partial match, with a failed match to top for the first candidate for every div we try to match. This saves us from trying out combinations of div descendants that we know will fail.
Indirect adjacent selectors have the same O(n!) performance problem as descendant selectors. A match-to-left optimization, orthogonal to the match-to-top optimization, is implemented.
Here is an outline of the actual matching algorithm
Match() ....To be continued... (Don't know if it's really necessary. It's quite simple apart from the two optimization techniques described above.)
During the matching we do not mark the HTML_Element objects with the pseudo bits before we see that the whole selector can possibly match. Instead we push the pseudo bits and the HTML_Element pointer onto a pseudo stack and commit the stack when we see that the matching elements on the stack is part of an S' match.
Example:
.nevermatch div:hover div:hover div:hoverFor the selector above, we push the matched div elements with a hover bit onto the pseudo stack, but throw them away when we find out that no ascendending element of the three divs have a class attribute that contains "nevermatch".