W3C home > Mailing lists > Public > www-style@w3.org > July 2008

Re: Parent Combinator / Parent pseudo-class

From: Francois Remy <fremycompany_pub@yahoo.fr>
Date: Thu, 24 Jul 2008 11:50:56 +0200
Message-ID: <59C172C245E9490CBE5A858BB5180EF5@FremyCompany1>
To: "Andrew Fedoniouk" <news@terrainformatica.com>
Cc: "Boris Zbarsky" <bzbarsky@MIT.EDU>, "www-style list" <www-style@w3.org>
> /* 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...

-----------------------------

No, it is'nt O(n*n).

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

after that, the complexity of with-child(a:hover b) is maximum O(n) [when the matching element is found, all the search is stopped]

The with-child rule need to be reevaluated each time :
-    (4) The first element matched by "div#base div.el1 a:hover b" change
-    (5) The first ancestror of the "b" that matches "a:hover" change

The main rule need to be reevaluated each time :
-    (4/5) The with-child statement change of value

The final complexity is so O(n) and not O(nē)

----------------------------------------------------

At loading time :

For each div1 matched by document.getElementsByTagName("div")
    (1) If any of these divs changes (dom 'id' attribute change, content change)
         ==> the rule must be evaluated since (2) for these div.
    (2) if div1 has "base" as "id", go to (3)
    the rule doesn't apply
    (3) 
    For each div2 matched by div1.getElementsByTagName("div")
        (4) If any of these divs change (dom 'class' attribute change, content change)
              ==> the rule must be evaluated since (5)
        (5) If div2 as "el1" as "class", go to (6)
        the rule doesn't apply
        (6) 
        For each a1 matched by div2.getElementsByTagName("a")
            (7) If any of these a's change (get/loose :hover, content change)
                  ==> the rule must be evaluated since (6)
            (8) If a1 has ":hover" as "modifier"
                (9)
                For each b1 matched by a1.getElementsByTagName("b")
                    (10) If any of these b's change (content change)
                          ==> the rule must be evaluated since (11)
                    (11) No condition are applied to b1, go to (12)
                    (12) go to (13)
                Next b1
        Next a1
        the rule doesn't apply
        (13)
        For each span matched by div2.getElementsByTagName("span")
            (14) If any of these span's change (get/loose :hover, content change)
                  ==> the rule must be evaluted since (15)
            (15) If span has ":hover" as "modifier", go to (16)
            the rule doesn't apply
            (16) the rule apply on span
        Next a2
    Next div2
Next div1

It's a O(n) complexity, you can trust me at this point.

Fremy
Received on Thursday, 24 July 2008 09:51:37 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Monday, 27 April 2009 13:55:10 GMT