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

Re: Suggestion for CSS3 selectors (fwd)

From: Andrei Polushin <polushin@gmail.com>
Date: Fri, 02 May 2008 09:24:42 +0700
Message-ID: <481A7B6A.7080704@gmail.com>
To: Andrew Fedoniouk <news@terrainformatica.com>
CC: Andrei Polushin <polushin@gmail.com>, fantasai <fantasai.lists@inkedblade.net>, "Brian J. Fink" <desertowl23@gmail.com>, dbaron@dbaron.org, www-style@w3.org

Andrew Fedoniouk wrote:
> Andrei Polushin wrote:
>> 1. In the first phase, we are noticing the child nodes that match those
>> "retroactive" selectors. A reference to such child become recorded by
>> its corresponding parent for the later use.
> Let's consider selector:
>   p.description < a:link
> At this first stage we will build a list ( find all a:link and their 
> p.description parents ) 
> is a task of complexity O(n*d) where n - number of elements in the DOM, 
> d - depth of the DOM tree.
> Elements p.description will have a list of CSS rules references 
> (selectors and style-defs).

Not necessary. Elements p.description will have a list of references to 
descendant a:link elements. The CSS rules will be found later, at the second 

>> 2. In the second phase, we resolve the style of each node, matching 
>> both the 
>> conventional selectors (as we did it in CSS2), and using the 
>> previously matched (in phase 1) retroactive selectors.
> Complexity of this stage is also close to O(n*d) so, indeed, we will 
> have a better picture:
>  O(2*n*d) with the price of rules list maintainance for each DOM element.
> That is caching commonly used for O(n*n) problems solving.
> That appears as better but still not that good. For dynamic updates 
> (e.g. a:hover) you will need 
> to recalculate styles not only of descendants/sibling but also for all 
> elements in parent containers - potentially the whole 
> tree.

You're estimating the problem for the worst case. But this case doesn't 
appear to be bad enough in practice. On average, the worst case is rare and 
shouldn't appear. Even if it appears, it could be noticeable (or should be 
made noticeable, if it's not) for the web author that the computation 
problem occurs as the result of his/her particular authoring style. Author 
could then avoid the computational problem by changing the authoring style.

Thus I agree that the computational problem could remain. It would be better 
if we will have a formal research and conclusion on this, from the several 
competent scientists.

Andrei Polushin
Received on Friday, 2 May 2008 02:25:18 UTC

This archive was generated by hypermail 2.3.1 : Monday, 2 May 2016 14:27:36 UTC