Re: Selector for parent/predecessor?

On Monday 21 August 2006 17:51, Boris Zbarsky wrote:
> > Even worse, I don't understand /who/ is objecting
>
> Last I checked, people involved in Gecko (myself, say) and Webkit [Safari]
> (David Hyatt, say) were having concerns about being able to implement this
> in a performant way.
I would for the record also object to something too generic. I am only saying 
it would be easy to implement. The hard part is coming up with reasonable 
restrictions that makes it hard or impossible to trigger worst-cases. 

>
> I'd love to see Allan's implementation; it may give me some ideas on how to
> do this in Gecko.  I'd also like to do some performance testing on it as
> compared to Gecko, of course.  ;)
>
Your wish is my command ;)

The model implemented in KHTML is loosly based on 1-1 dependency tracking. 
There are a bunch of optimizations and restrictions to avoid it reaching it's 
worst-case n*log(n) memory consumption. The 1-1 dependencies are why it can 
easily handle cousin relationships, but also why the memory used could 
explode.

The most important relationships tracked are structural and 
backward-structural. A structural dependency means that the style is affected 
by inserts on the element, but not append. A backward-structural dependency 
means the style is affected by both inserts and append (but in theory not 
prepend).
The other dependencies are the various attributes, hover/active, focus and 
otherstates. The later being a catch all for form states.

A ~ or + combinators as well as :first-child and friends always generate 
structural dependencies. 

The :empty, :last-*, :last-nth-* selectors all generate backward-structural 
dependencies. To avoid restyling all the time during parsing, 
backward-structural updates are inhibited during parsing, and are only fired 
when the element's closing element has been parsed. (Note, if you implement 
the prepend optimization :empty has both types of dependencies).

When an elements state change, it looks up the type of change against the 
dependency tracker. The result can be either a specific set of elements to 
restyle, or one of three generic rules: Self, Children or Siblings. If Self, 
restyle self, if Child restyle all children and their descendants. If sibling 
simulate a structural change on the parent. Both structural dependencies 
always return a set of elements instead of a rule.


Regards
`Allan

Received on Tuesday, 22 August 2006 13:40:29 UTC