CSS Engine Style Invalidation Strategy

Based on the reading of https://wiki.mozilla.org/Servo/StyleUpdateOnDOMChange and my own experience, I would like to have feedback on the following style update strategy:


{please be kind and forward  this mail if you know someone who could answer those questions but isn’t subscribed to www-style}


Memory and description of the flags:

Each element has three sets of invalidating flags:
Self invalidation (when a change of value for the flag should trigger only a rematching procedure on the element, and a new inherit/cascade process on its children)
Descendant invalidation (when a change of value for the flag should trigger a rematching on all the descendants of the element, itself non-included)
Sibling invalidation (when a change of value for the flag should trigger a rematching on all the next sibling of the element, itself non-included)
Each set of invalidation flags contain four different flag sections:
64bits for IDs
64bits for Classes
64bits for Attributes
32bits for States (hover…)


Whenever the set of matching rules for an element is being computed:
Every {class/id/attribute-name} string is hashed such that it only maps to one bit out of 64, and every state itself has one out of 32bits hash (precomputed when reading the selector). 
All the flags for the self-invalidation set are reset to 0.
Let X represent any value from {ID, Class, Attribute, State}
When a X condition is being checked on an element to see if it matches a selector, the flags corresponding to Xs for self-invalidation is ORed with the hash of the X feature being tested
When a X condition is being tested on a previous sibling of the element or any of its ancestors to see if the element matches a selector, the flags corresponding to Xs for sibling-invalidation is ORed with the hash of the X feature being tested
When a X condition is being tested on an ancestor for the element, the flags corresponding to Xs for descendant-invalidation is ORed with the hash of the X feature being tested


Whenever the set of matching rules is being computed for an element and all its descendants:
Reset the self-invalidation and descendant-invalidation flags before proceeding


Whenever the set of matching rules is being computed on an ancestor of an element and all its descendants:
Reset all the invalidation flags before proceeding


When a DOM/State update happens:
See if the X feature has any CSS selector using it at all; if not abort these steps
Compute the hashes of the X feature being modified, and AND them with the flags on the element where the update did happen. If the result of any of the operation is not zero, mark for rematch any element that is included in the affected invalidation set.


Expected strengths:
Very efficient for things like “abc:hover def” when there’s no “def” inside an “abc” because the “abc” will never be asked for his “:hover” state from a child
Very efficient at finding whether we should update the element itself, its descendants or its whole sibling world
Very fast at deciding whether we should rematch or not, no need to use external data.


Expected weaknesses:
Is ineffective for documents with a lot of unused selectors, or with selectors with a lot of possible failures points (like “.a, .b, .c, .d, .e, .f” or “.a .b .c .d .e .f”) as the numbers of flags do not grow with the number of classes and resulting pollution may make filters inoperant - current strategies suffer from this as well but maybe to a lesser extent
Potentially triggers a lot of memory writes during selector matching (is that an issue?)


Do you think this would a good procedure:
From the memory point of view?
From the efficiency point of view?
From the setup requirements point of view?


Thanks a lot for reading me up to here, I hope you’ll take some time sharing your thoughts!

Francois


_____________________________________

DISCLAIMER: I’m not working on such optimized css engine right now but if I end up working on one at some point this may prove useful. Now the ideas are fresh in my head, who knows how they will be in 6months, 1year…