Re: Select a parrent node with s CSS selector?

----- Original Message ----- 
From: "Allan Sandfeld Jensen" <>
To: <>
Sent: Tuesday, April 24, 2007 9:13 AM
Subject: Re: Select a parrent node with s CSS selector?

> On Tuesday 24 April 2007 04:42, Andrew Fedoniouk wrote:
>> This is not about complexity of implementation but about computational
>> complexity of algorithm needed to calculate such a selector:
>> See:
>> For example proposed selector
>> * < *:link  /* element that has at least one link inside */
>> requires deep scan of all children of any given element to verify the
>> selector.
>> Formula O( n * n ) means that document having twice more
>> elements will require four times more time to match selectors.
>> (In practice this can be lot less - this is just a worst case - but 
>> still)
>> Again it is possible to compute this but selectors that have exponential
>> nature are *highly* non-desirable.
> O(n*n) is quadratic not exponential,

Thanks, Allan, quadratic indeed.

> ... and many CSS implementations are worst
> case quadratic anyway.

CSS implementations or the nature of CSS selectors?

So far no one of proposed CSS selectors has purely quadratic nature.

The are bad ones like bunch of  :only-of-type, :first-of-type, etc. pseudos 
the Indirect adjacent combinator A ~ B.
Use of them may potentially kill the design without any warning to the 
But no quadratic algorithms even in worst case.

Side note, interesting thing:
"Evil" pseudo class "6.6.6 Content pseudo-class" in CSS3 has note:
  Editor's note : need to add here a strong warning about performance issues
  related to this pseudo.
But, say, A ~ B considered to be less evil for some reasons.

> And no, it can still be done in linear time O(n) using a standard NFA to 
> conversion (consider the CSS selectors a collection of NFA rules).

It would be extremely nice if it will be always possible to reduce O(n*n) to 

> The problem is that it can't be done conclusively for all cases until the 
> entire
> document has been parsed. This either makes the page keep changing style
> while loading and parsing, or delays the display until end of page-load. 
> has been designed to be applied incrementally (expect for a few odd CSS3
> selectors).


There are precisely 5 problematic pseudo-classes
:last-of-type, :not-last-of-type, :only-of-type, :not-only-of-type
and :last-child, :not-last-child that requre look ahead on the
DOM tree (so conflict with incremental rendering).
But these are only on the same siblings level.


> That said there have been suggestions on this list that could be applied
> better incrementally and achieve many of the same effects, and there is 
> also
> the idea to just allow the web authors shoot themselves in the foot if 
> they
> use the parent selector on BODY (worse case scenario).
> `Allan

Received on Wednesday, 25 April 2007 00:03:56 UTC