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

Re: Suggestion for CSS3 selectors (fwd)

From: Andrew Fedoniouk <news@terrainformatica.com>
Date: Thu, 01 May 2008 17:49:44 -0700
Message-ID: <481A6528.40408@terrainformatica.com>
To: Andrei Polushin <polushin@gmail.com>
CC: fantasai <fantasai.lists@inkedblade.net>, "Brian J. Fink" <desertowl23@gmail.com>, dbaron@dbaron.org, www-style@w3.org

Andrei Polushin wrote:
> Andrew Fedoniouk wrote:
>> To resolve final style of the element (child) you need (resolved) 
>> parent style and list of rules matching the child. To find parent 
>> style you need to scan all children first. That is still O(n).
>
> The simplest algorithm I can imagine for now is a two-phase style
> resolution, we scan the whole DOM tree in two phases:
>
> 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).

>
> 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.
>
> The complexity of two-phase scan is O(2n).
>
> In practice, the algorithm could be more optimistic: it could perform the
> style resolution in the first phase, in assumption that the node does not
> contain any child that matches a retroactive selector. In case when such
> match actually occurs, the style of the corresponding parent (with all 
> children) should be invalidated, and the matched child should become 
> "noticed" by the parent, thus effectively switching the algorithm into
> two-phase scanning mode.
>
>
>> ---
>> Gentlemen, do we have real life samples of where this feature is 
>> required?
>
> Not sure whether it'll count for "real life sample", but the most recent
> request from the web author was [1], and in its follow-up [2] he says 
> that
> he uses JavaScript instead. That claim may also prove that the practical
> implementation is possible.
>
> [1]: http://lists.w3.org/Archives/Public/www-style/2007Apr/0105.html
> [2]: http://lists.w3.org/Archives/Public/www-style/2007Apr/0206.html
>
As far as I understand that is primarily for dynamic updates. So what 
about this
(css-action-script):

p.description a:link
{
  on-hover-enter: nearest-parent( p.description )[highlight] = "";
  on-hover-leave: nearest-parent( p.description )[highlight] = undefined;
}
p.description[highlight] { background: yellow; }

This will solve other problems like:
when hover on link a.one highlight element div.second when
div.second and a.one not in parent/child relationship.

At least this approach will not make things worse than they are now.

--
Andrew Fedoniouk.
http://terrainformatica.com
Received on Friday, 2 May 2008 00:50:33 GMT

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