Servo/StyleUpdateOnDOMChange

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.

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. XXXbz At least the latter is the only way I can explain its behavior on the HTML5 spec. What I don't undertstand is why it ends up with that behavior, since it flags the "children affected by" flags just as eagerly as Gecko does... Anyone know offhand?

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.