3 ms·

Microsoft has a long and infamous history with CSS selectors. That they start off by saying they parse selectors right to left is shocking, but not surprising

Microsoft has a long and infamous history with CSS selectors. That they start off by saying they parse selectors right to left is shocking, but not surprising.

dubcanada 4y ago
Considering they use Blink like Chrome and everyone parses right to left, not sure what you mean?
megous 4y ago
Shocking would be if they matched them left to right. Just try imagining the algorithm.
- comex 4y ago
  Not the parent, but I can imagine a pretty fast left-to-right algorithm. First assemble all the CSS rules into a tree, where each non-leaf node represents a selector and following a path down the tree corresponds to reading a selector from left to right. For example, if there are two rules, ".foo .bar" and ".foo .baz", the tree root would be ".foo", and it would have children ".bar" and ".baz". Then give each DOM element a pointer to a style tree node. When an element is inserted into the document, set its style tree node by looking for a matching selector among the children of the parent element's style tree node. For example, <div class="foo"> would be associated with the ".foo" style tree node; if <div class="bar"> is created underneath that, the browser looks up ".bar" among that node's children. If there is no match, then use the same style tree node from the parent. That way you can find the matching CSS rules for each element at the cost of a single lookup per element, regardless of how deeply the rules are nested. In reality it's more complicated than that, because an element might actually need multiple style tree positions. If you have ".foo .bar" and "div .bar", ".foo" and "div" would naively be two separate tree nodes (each with a ".bar" child node), but <div class="foo"> would have to be associated with both nodes. In other words, the style tree is an NFA. But just like with regular expression matching, it might be faster to convert it to a DFA in advance, i.e. duplicate nodes as necessary so that each element does only need one position in the tree. And the need to support efficient incremental updates (e.g. an element could change class name, or style rules themselves could be added/removed) makes everything even more complicated. Still, if you asked me before today to guess how browsers implemented CSS rule matching, that's the algorithm I would have thought of… I wonder why they don't do this. Maybe deeply nested CSS rules are not that common in practice.
matsemann 4y ago
Doesn't all browsers do that? I've heard that being the reason for it being some what fast, but also why it's hard to add certain things to css people want, because that would break some optimizations.

Microsoft has a long and infamous history with CSS selectors. That they start off by saying they parse selectors right to left is shocking, but not surprising.

dubcanada 4y ago

Considering they use Blink like Chrome and everyone parses right to left, not sure what you mean?

megous 4y ago

Shocking would be if they matched them left to right. Just try imagining the algorithm.

comex 4y ago
Not the parent, but I can imagine a pretty fast left-to-right algorithm. First assemble all the CSS rules into a tree, where each non-leaf node represents a selector and following a path down the tree corresponds to reading a selector from left to right. For example, if there are two rules, ".foo .bar" and ".foo .baz", the tree root would be ".foo", and it would have children ".bar" and ".baz". Then give each DOM element a pointer to a style tree node. When an element is inserted into the document, set its style tree node by looking for a matching selector among the children of the parent element's style tree node. For example, <div class="foo"> would be associated with the ".foo" style tree node; if <div class="bar"> is created underneath that, the browser looks up ".bar" among that node's children. If there is no match, then use the same style tree node from the parent. That way you can find the matching CSS rules for each element at the cost of a single lookup per element, regardless of how deeply the rules are nested. In reality it's more complicated than that, because an element might actually need multiple style tree positions. If you have ".foo .bar" and "div .bar", ".foo" and "div" would naively be two separate tree nodes (each with a ".bar" child node), but <div class="foo"> would have to be associated with both nodes. In other words, the style tree is an NFA. But just like with regular expression matching, it might be faster to convert it to a DFA in advance, i.e. duplicate nodes as necessary so that each element does only need one position in the tree. And the need to support efficient incremental updates (e.g. an element could change class name, or style rules themselves could be added/removed) makes everything even more complicated. Still, if you asked me before today to guess how browsers implemented CSS rule matching, that's the algorithm I would have thought of… I wonder why they don't do this. Maybe deeply nested CSS rules are not that common in practice.

matsemann 4y ago

Doesn't all browsers do that? I've heard that being the reason for it being some what fast, but also why it's hard to add certain things to css people want, because that would break some optimizations.