23 Aug 2014
Welcome back to my series on building your own toy browser engine. If you're just tuning in, you can find the previous episodes here:
This article will cover what the CSS standard calls assigning property values, or what I call the style module. This module takes DOM nodes and CSS rules as input, and matches them up to determine the value of each CSS property for any given node.
This part doesn't contain a lot of code, since I didn't implement the really complicated parts. However, I think what's left is still quite interesting, and I'll also explain how some of the missing pieces can be implemented.
The output of robinson's style module is something I call the style tree. Each node in this tree includes a pointer to a DOM node, plus its CSS property values:
What's with all the
'astuff? Those are lifetimes, part of how Rust guarantees that pointers are memory-safe without requiring garbage collection. If you're not working in Rust you can ignore them; they aren't critical to the code's meaning.
We could add new fields to the
dom::Node struct instead of creating a new
tree, but I wanted to keep style code out of the earlier "lessons." This also
gives me an opportunity to talk about the parallel trees that inhabit most
A browser engine module often takes one tree as input, and produces a different but related tree as output. For example, Gecko's layout code takes a DOM tree and produces a frame tree, which is then used to build a view tree. Blink and WebKit transform the DOM tree into a render tree. Later stages in all these engines produce still more trees, including layer trees and widget trees.
The pipeline for our toy browser engine will look something like this, after we complete a few more stages:
In my implementation, each node in the DOM tree has exactly one node in the
style tree. But in a more complicated pipeline stage, several input nodes
could collapse into a single output node. Or an input node might expand into
several output nodes, or be skipped completely. For example, the style tree
could exclude elements whose
display property is set to
'none'. (Instead I'll remove these in the layout stage, because my code
turned out a bit simpler that way.)
The first step in building the style tree is selector matching. This will be very easy, since my CSS parser supports only simple selectors. You can tell whether a simple selector matches an element just by looking at the element itself. Matching compound selectors would require traversing the DOM tree to look at the element's siblings, parents, etc.
To help, we'll add some convenient ID and class accessors to our DOM element
class attribute can contain multiple class names
separated by spaces, which we return in a hash table.
To test whether a simple selector matches an element, just look at each
selector component, and return
false if the element doesn't have a matching
class, ID, or tag name.
Rust note: This function uses the
anymethod, which returns
trueif an iterator contains an element that passes the provided test. This is the same as the
anyfunction in Python (or Haskell), or the
Next we need to traverse the DOM tree. For each element in the tree, we will search the stylesheet for matching rules.
When comparing two rules that match the same element, we need to use the highest-specificity selector from each match. Because our CSS parser stores the selectors from most- to least-specific, we can stop as soon as we find a matching one, and return its specificity along with a pointer to the rule.
To find all the rules that match an element we call
does a linear scan through the style sheet, checking every rule and throwing
out ones that don't match. A real browser engine would speed this up by
storing the rules in multiple hash tables based on tag name, id, class, etc.
Once we have the matching rules, we can find the specified values for the element. We insert each rule's property values into a HashMap. We sort the matches by specificity, so the more-specific rules are processed after the less-specific ones, and can overwrite their values in the HashMap.
Now we have everything we need to walk through the DOM tree and build the style tree. Note that selector matching works only on elements, so the specified values for a text node are just an empty map.
That's all of robinson's code for building the style tree. Next I'll talk about some glaring omissions.
Style sheets provided by the author of a web page are called author style sheets. In addition to these, browsers also provide default styles via user agent style sheets. And they may allow users to add custom styles through user style sheets (like Gecko's userContent.css).
The cascade defines which of these three "origins" takes
precedence over another. There are six levels to the cascade: one for each
origin's "normal" declarations, plus one for each origin's
Robinson's style code does not implement the cascade; it takes only a single
style sheet. The lack of a default style sheet means that HTML elements will
not have any of the default styles you might expect. For example, the
<head> element's contents will not be hidden unless you explicitly add this
rule to your style sheet:
Implementing the cascade should by fairly easy: Just track the origin of each rule, and sort declarations by origin and importance in addition to specificity. A simplified, two-level cascade should be enough to support the most common cases: normal user agent styles and normal author styles.
In addition to the "specified values" mentioned above, CSS defines initial, computed, used, and actual values.
Initial values are defaults for properties that aren't specified in the cascade. Computed values are based on specified values, but may have some property-specific normalization rules applied.
Implementing these correctly requires separate code for each property, based on its definition in the CSS specs. This work is necessary for a real-world browser engine, but I'm hoping to avoid it in this toy project. In later stages, code that uses these values will (sort of) simulate initial values by using a default when the specified value is missing.
Used values and actual values are calculated during and after layout, which I'll cover in future articles.
If text nodes can't match selectors, how do they get colors and fonts and other styles? The answer is inheritance.
When a property is inherited, any node without a cascaded value will receive
its parent's value for that property. Some properties, like
inherited by default; others only if the cascade specifies the special
My code does not support inheritance. To implement it, you could pass the
parent's style data into the
specified_values function, and use a hard-coded
lookup table to decide which properties should be inherited.
Any HTML element can include a
style attribute containing a list of CSS
declarations. There are no selectors, because these declarations
automatically apply only to the element itself.
If you want to support the
style attribute, make the
check for the attribute. If the attribute is present, pass it to
parse_declarations from the CSS parser. Apply the resulting
declarations after the normal author declarations, since the attribute is
more specific than any CSS selector.
In addition to writing your own selector matching and value assignment code, for further exercise you can implement one or more of the missing pieces discussed above, in your own project or a fork of robinson:
Also, if you extended the CSS parser from Part 3 to include compound selectors, you can now implement matching for those compound selectors.
Part 5 will introduce the layout module. I haven't finished the code for this yet, so there will be another delay before I can start writing the article. I plan to split layout into at least two articles (one for block layout and one for inline layout, probably).
In the meantime, I'd love to see anything you've created based on these articles or exercises. If your code is online somewhere, feel free to add a link to the comments below! So far I have seen Martin Tomasi's Java implementation and Pohl Longsine's Swift version.