Re: Proposal for limited :matches pseudoclass

Francois Remy wrote:
>>>  :root > * * * *:hover * * * * *:contains(e) * * { color: red; }
>>
>> I see nothing buggy in this selector, nor anything that would take 
>> significant processor time to deal with (apart from the :contains, 
>> which as I already mentioned is no longer in CSS3 Selectors).
> 
> I can assure you that this selector, even without the :contains, need a 
> long CPU-time.
> 
> In fact, :root > * * * * match (nearly) each elements of the document 4 
> times !

I think I see the problem here.  We're approaching this issue from 
completely different points of view.  The questions that worry me about 
selector performance are the following:

1) Given an element and a selector, how long does it take to determine
    whether the element matches the selector?
2) Given a DOM mutation, what elements does style need to be recomputed
    for?
3) Given some state change (e.g. mouse move), what elements does style
    need to be recomputed for?
4) How long does answering questions 2 and 3 take, and how much memory
    does it use?

For the selector in question, which is:

   :root > * * * *:hover * * * * * * * * { color: red; }

the answers are the following (for Gecko; for a different implementation 
they might be different):

1) The same amount of time as for ":root :hover *": O(k) where
    k is the depth of the tree.
2) None (other than the obvious need to resolve style on an inserted
    node and its descendants).
3) If the :hover state of a node changes, style needs to be reresolved
    on that node and its descendants.  (Note that this is not the optimal
    answer for this selector, but this is where question 4 comes in.)
4) Answering question 2 requires verifying that there are no '+' or '~'
    combinators or content pseudo-classes (:empty, :nth-child, etc) in
    the selectors applied to the page.  Answering question 3 involves
    verifying the same, plus that there is a :hover pseudo-class.  No
    significant extra memory is needed past that already used for
    selector storage and DOM storage.

So in fact, this is actually a rather nice selector to deal with from a 
performance point of view.

> The :root > * * * * selector can match
>    - "html > body a b c", "html > body a b d", "html > body a b e", ...
>    - "html > body b c d", "html > body b c e", ....
>    - "html > body c d e",  ...

Sure.

> So, we get 4 mousein/out handlers attached to all elements matched by 
> :root> * * * *:hover.

Or just one mousein/out handler on the root, which then flips the hover 
state on the event target and ancestors as needed.  That's basically how 
Gecko implements it.

> In addtion, they also receive handlers for DOM mutation events (* added 
> or removed into id).

Again, a single event handler on the root can handle this.

> Because we continue to add some * after, elements of the document, the 
> complexity is very high.

Not really, no.

-Boris

Received on Thursday, 31 July 2008 21:06:02 UTC