Handling of style updates when the DOM changes

In what cases are style updates needed?

Throughout, we use the terms "selector" and "sequence of simple selectors" as defined in CSS3 Selectors. In addition, we use the term "subject sequence of simple selectors" to describe the sequence of simple selectors that must match elements that the full selector matches. In Selectors Level 3 this is the rightmost sequence of simple selectors, but there are proposals to allow this to be other parts of the selector.

DOM changes, broadly construed to include mutations of the structure of the DOM tree, changes to element attributes, and internal state changes on elements, can cause changes to styles in the following situations:

1. Whether an element matches the subject sequence of simple selectors of some selector changes due to attribute or state changes on the element. The set of rules applying to that element then needs to be recomputed, and inheritance might need to be redone for descendants.
2. Whether an element matches the subject sequence of simple selectors of some selector changes due to insertions or deletions of element subtrees in the DOM. This can be caused by + and ~ combinators, as well as by use of structural pseudo-classes like :nth-child, :empty, etc. The consequences are the same as for item 1. The hard part here is figuring out which elements are affected by a given insertion/deletion.
3. Whether an element matches a non-subject sequence of simple selectors changes due to attribute or state changes on the element. The set of elements which now match the subject sequence of simple selectors needs to be recomputed. What that set is depends on the exact combinators used in the selector.

Gecko's handling of style updates

Gecko has several mechanisms for handling changes as described above.

Attribute changes

Attribute changes in Gecko send an AttributeWillChange notification before the change and a AttributeChanged notification afterward. Both calls ask the rule processors for the document to check for sequences of simple selectors that depend on the attribute that's changing (whose name is known inside the above notifications). If such sequences are found and match the element whose attribute is changing (both the sequence of simple selectors and the part of its selector to the left of it needs to match) then Gecko assumes that either the element will stop matching the sequence of simple selectors (in AttributeWillChange) or will start matching it (in AttributeChanged). In either case, Gecko queues up "recompute the set of rules matching this element" events for some set of elements that depends on the combinator that comes after the sequence of simple selectors in question. If there is no combinator, this set is just the element itself. If the combinator is '>' or ' ', this set is the element and all its descendants. If the combinator is '~' or '+', this set is all following siblings of the element and all their descendants.

Benefits of this approach are that it's fairly exhaustive (so that Gecko does not miss changes for '~' and '+') and yet being able to optimize away changes that don't matter (e.g. a class attribute change from one value that matched no rules to another value that matched no rules will not cause any restyling).

Drawbacks are that all those before/after change notifications are expensive in Gecko, as is the process that walks over rule processors looking for relevant sequences of simple selectors. Even if there aren't any, Gecko ends up making dozens of virtual function calls to discover that, and possibly examining a nontrivial amount of data.

State changes

Boolean state changes are handled similarly to attribute changes, but instead of having before/after notifications there is a single notification that indicates the set of changed states. Selector matching then ignores that set of states when looking for state-dependent sequences of simple selectors that might have stopped or started matching the element. This does not allow catching cases when the switch is from a state that didn't match to another state that does not match, unfortunately, but does reduce the number of notifications needed.

There is one ad-hoc optimization here: if the state that changed is "hover", Gecko skips the entire process for elements that were never matched against a :hover simple selector before. See https://bugzilla.mozilla.org/show_bug.cgi?id=732667 for the background on this.

Handling of insertions and deletions

When during selector matching a '~' or '+' combinator or a structural pseudo-class is encountered, Gecko sets a flag on the parent of the things being matched that indicates that it had children affected by "slow selectors". There are actually 4 different flags here that handle different cases: :empty selectors, selectors like :nth-last-child which might require restyles on any append/removal/insertion, selectors like :only-child or :last-child or :first-child which only matter for the first/last kids of the element, and selectors like :nth-child which might require restyles on insertion and removal but NOT on append.

When an insertion or removal happens, if the parent of the node being inserted/removed has one of the slow selector flags, Gecko posts "recompute the set of matching rules" events on either the parent, or all its kids, or the kids that come after the insertion location, depending on which of the above flags are set.

This setup, again, makes sure that dynamic changes are not missed, while trying to optimize the common append case as much as possible. But it will often be more pessimistic than it needs to be, and in particular can end up flagging with slow selector flags elements whose descendants don't actually match the selector with the structural pseudo-class or sibling combinator anyway, because of a simple selector further to the left which fails to match ancestors of the flagged element.

WebKit's handling of style updates

Attribute changes

If the element does not already have a style recalc flagged, and if either the attribute is the id attribute or there are selectors that involve the attribute, the element is flagged for a style recalc. There is no attempt to double-check whether those selectors have anything to do with the element and no attempt to handle cases involving '~' and '+' at this stage. There is also a separate hook called when class attributes change that amongst other things unconditionally flags the element as needing a style recalc. Again, no attempt is made to handle '~' and '+'. In none of these cases is there an attempt to optimize away selector matching on descendants.

State changes

There is no unified setup for state changes in WebKit. For each pseudo-class that is handled via boolean states in Gecko, selector matching has a dedicated function the element that it can call to test whether that pseudo-class matches. Changes to that state inside an element are responsible for directly marking that element as needing style recalc. Again, no attempt to optimize away selector matching on descendants or to handle '+' or '~' is made. There are some optimizations here similar to the one Gecko makes for :hover that cover :hover, :active, and something about dragging.

Handling of insertions and deletions

The RenderStyle has flags that indicate whether its kids are affected by various structural pseudo-classes and '+' or '~' combinators. On DOM mutations, the first affected element after the change (in child list order) is marked as needing a style recalc, or the single first child of the parent if it might need a recalc. If more things before the change might need a recalc, then the parent is marked as needing a style recalc, which will recalc all its kids.

In all of these cases, when actually recomputing style on an element, a check is made to see whether its kids are affected by '+' or '~'. If so, then if any child is flagged as needing style recalc either the child after it or all children after it (depending on whether '+' or '~' was involved) are also flagged as needing style recalc. There are some bugs here around chains of multiple '+', I think.

The upshot is that in some cases WebKit ends up recomputing style on a lot more elements than Gecko does, as far as I can tell, but in others it ends up recomputing style on many fewer elements. For example, given a selector like ".foo ~ span" and a div that changes class from "foo" to "bar", Gecko will restyle all later siblings of the div, while WebKit will not do any work at all if there are no "span" kids, since it would never have marked the parent as being affected by the '+' in that case. I'm not sure to what extent this affects insertion behavior, where it seems like the two should be more similar. _Somehow_ WebKit seems to do better than Gecko on the HTML5 single-page spec scripts, and I can't figure out why at this point. Perhaps this is simply because its style recomputation seems to be much cheaper than Gecko's to actually run.

The other upshot is that the work involved in individual attribute and state changes is much less than in Gecko, at the cost of more style recomputation. The work involved in DOM insertion/deletion is about the same.

Options for Servo

One thing we want to decide up front is how we want to handle '+' and '~', and possibly other things the CSS working group will decide to do in terms of allowing flagging of arbitrary parts of a selector as the subject. Neither the WebKit nor Gecko approaches make me entirely happy.

One thing that Servo will have that neither WebKit nor Gecko does is the ability to consider both the pre-change and post-change states of the DOM, if we're willing to do such processing as part of the "discard the old read pointers" process. This can allow us to completely or partially defer processing of whether restyles are needed from when changes are actually made to the discarding process. Unfortunately, what that will require is running said deferred processing on the DOM thread, since that's the only place we can safely access both the old and new DOM states. We may want to restrict this to only particular things where the win from having access to both the old and new value is particularly meaningful (e.g. class attribute changes)?

It seems to me that we can mix and match the Gecko and WebKit approaches here as needed, depending on how fast we can make style recomputation.

The one thing I want to avoid that Gecko does right now is interrogating a whole bunch of objects to find out whether a change is style-relevant. We should propagate all that information back to a single object. This change could even be made in Gecko today....