Re: Suggestion for CSS3 selectors (fwd)

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.

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.

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

-- 
Andrei Polushin

Received on Thursday, 1 May 2008 23:16:45 UTC