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: http://en.wikipedia.org/wiki/Computational_complexity_theory
>
> 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, and many CSS implementations are worst 
case quadratic anyway.

And no, it can still be done in linear time O(n) using a standard NFA to DFA 
conversion (consider the CSS selectors a collection of NFA rules). 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. CSS 
has been designed to be applied incrementally (expect for a few odd CSS3 
selectors).

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 Tuesday, 24 April 2007 16:13:53 UTC