Re: Parent Combinator / Parent pseudo-class

From: "Andrew Fedoniouk" <news@terrainformatica.com>
>
> Francois Remy wrote:
>>  > /* I don't have better solution if we must generalize in JScript */
>>  >    setInterval(update, 500);
>>  >
>>  > (As far as I understand you think that there is a better
>>  > solution, right?)
>>  >
>>  > Your function update() {} has worst case complexity O(n*n).
>>  > You can *easily* hit the point when it will take more than 500ms
>>  > to execute. So UA will be busy crunching selectors most of the time.
>>  >
>>  > Cheers.
>>  >
>>  > --
>>  > Andrew Fedoniouk.
>>
>> Yes, there's another solution : you can watch change applied on the 
>> elements that can change the value of the rule.
>> But it's not possible to know when an element changes in JScript...
>
> Imagine that I you have some event that is fired when one of its
> attributes, states or its subtree is getting changed.
> (Lets put aside for the second when such an event needs to be fired)
>
> How it will help you?

You don't need to run the whole selector each time there's a DOM 
modification, only each one that are applying on elements that are concerned 
by the rule.
And yes, I missed a case : when a DIV is added to the document, we must 
check the rule for this new div.

>
>>  -----------------------------
>>  No, it is'nt O(n*n).
>
> It is not O(n*n), it is even worse, see below.
>
>>  imagine this case :
>>  <div id="base">
>>     <div class="el1">
>>         <a href="#"><b><span>First</span> link</b></a>
>>         <a href="#"><span>Second</span> link</a>
>>     </div>
>>     <div class="el2">
>>         <a href="#"><b><span>First</span> link</b></a>
>>         <a href="#"><span>Second</span> link</a>
>>     </div>
>> </div>
>>  and this rule :
>>  div#base div.el1:with-child(a:hover b) span:hover { color: green; }
>> -------------------------------
>>  The complexity of #base .el1 a:hover is O(n).
>
> Agreed at this point.

Ok, so it's O(n)

>
>> The rule need to be reevaluated each time :
>> -    (1) The elements matched by "div" change (any DIV can get or loose 
>> id="base")
>> -    (2) The elements matched by "div#base div" change (any DIV of 
>> div#base can get or loose class="el1")
>> -    (3) The elements matched by "div#base div.el1 span" change (any SPAN 
>> can get or loose :hover)
>
> Each of this operations is by itself O(n) operation.
> Complexity of this step is O(3*n).

So, you're saying that O(n) is equals to O(3*n) ?
Because here, it's only the cases when we need to reevaluate a part of the 
div#base div.el1 span.
And on the same rule, you agreed with me that it's a O(n) rule... You'ren't 
consistent here.

>
> So on *each DOM modification* you will run O(3*n) operation.
> For each element found you need to check for $(#base .el1 a:hover).

Not really. We only need to check if there's a "a:hover b" child in the 
matched div.
It's not a O(n), it's smaller. In fact, I think O(...) is not the good way 
to say if a rule is complicated or not because it's simply irrevelant.

" span[title='1'] > span[title='2'] > span[title='3'] > ... > span[title=n] 
" is really painfull for the UA but it's a O(n).
But "span" is a O(n) too, and he's very simple.

If fact, we don't need to think so.
We must see how much recursion are done to apply the rule.

For "span" it's 1.
For "span[...] > ...." it's n.
For "span:with-child(span)", it's 2.

For [[ before-selector:with-child(child-selector) after-selector ]], it's 
I(before-selector) + I(after-selector) + I(child-selector)

So for div#base div.el1:with-child(a:hover b) span:hover, you have a 
loop-complexity of 5.
You can see my code, there's only 2 loops for before-selector, 2 loops for 
child-selector and then 1 loop for after-selector.

"a b c d e" also have a loop-complexity of 5, and it's not a difficult rule 
to evaluate.
"a b:with-child(c d) e" is not really more complex than the first one.

> Therefore total (worst case) is O(m*n*n) where 'm' is a number of simple 
> selectors of the complex selector.
>
>>  It's a O(n) complexity, you can trust me at this point.
>
> I will.
>
> -- 
> Andrew Fedoniouk.
>
> http://terrainformatica.com

Received on Thursday, 24 July 2008 20:39:45 UTC