Rust Browser 5: A Proper Tree Structure
Styling in a browser is conceptually very simple. We’ve parsed the DOM into a tree structure of elements. We’ve parsed the CSS into a tree structure of rules.
Each DOM node is transformed into a new StyledNode, which contains a reference to the DOM node and a list of specified values. These are the actual CSS values that will be used for that node. The values are produced by searching for CSS rules that match the DOM node, pulling out the matched values, then sorting them by specificity.
A Tree Structure for Styles
Conceptually this is simple. For each node we loop over the rules finding the ones that match, then copy the values into a list and sort by specificity. The specificity is defined strictly by the CSS specs, so it’s easy to calculate. Of course to do this whole thing we need a tree structure for the StyledNodes.
Originally I made the styled nodes similar to the DOM node. Each parent owns a vector of children, plus
struct StyledNode {
pub node:Node,
pub children: Vec<StyledNode>,
pub specified_values: PropertyMap,
}The problem is that we don't have a reference to the parent. Originally I solved the problem by building up a list of parents as I recurse into the tree. There’s a vector called ancestors. And this did work for the initial matching with ancestor selectors. However, certain properties actually require having the parent to resolve. In fact, any property where the value is inherit must be able to look it up in its parent or its parent’s parent, etc.
The problem is that the property resolution happens in the layout when the property is needed, not here when we are matching rules.
Computed vs Specified CSS Values
Okay, let me back up a sec. In the browser specs every element has properties on it based on the CSS. These are values like border-width: 2em or width: 80%. Some of these properties have concrete values that we can use right away, like 3px, but some require context to evaluate. 2em really means 2 times the height of the current font. width: 80% means 80% of the width of the parent element. These are called ‘computed’ css values, whereas the originals are called ‘original’ css values or ‘specified’ css values. During the styling phase we are working with the specified values. During the layout phase these must be turned into the computed values, which requires know things like the parent’s width or the inherited font size.
All of this means that some values can’t be resolved until the layout phase, but we were calculating the parents during the styling phase. The current system won’t work. Instead I need a tree structure that preserves access to the parent nodes at any time.
A Better Tree Structure
After some research and asking on Reddit and reading lots of docs, I built a new system using Rcs and RefCells. Here’s the definition now.
pub struct StyledTree {
pub root: RefCell<Rc<StyledNode>>,
}
pub struct StyledNode {
pub node: Node,
pub children: RefCell<Vec<Rc<StyledNode>>>,
parent: RefCell<Weak<StyledNode>>,
pub specified_values: PropertyMap,
}Now there is a single object called StyledTree which has access to the root node. Each node has access to the original DOM node, the styled children, the specified values (not the computed values), and the parent node. Access to children and parents is done with RefCells and Rcs. Rcs are reference counted, meaning more than one structure can have access to the object. RefCells are reference cells. They give you read only access to an object that can be temporarily upgraded to mutable access using borrow() and borrow_mut().
This system works but can introduce loops. In fact, I discovered that calling println! on the structure would lock up the app when it goes into an infinite loop trying to follow the links from parents to children to parents. To fix this the parent reference is done with a Weak pointer. That weakly holds onto the parent but won’t be followed in the Rc loops.
Accessing fields of these objects is a little trickier than normal, so I put util functions on StyledTree to handle it.
impl StyledTree {
pub fn new() -> Self {
StyledTree {
root: RefCell::new(Rc::new(StyledNode {
node: Node { node_type: NodeType::Comment(String::from(“comment”)), children: vec![] },
children: RefCell::new(vec![]),
parent: RefCell::new(Default::default()),
specified_values: Default::default()
}))
}
}
pub fn make(&self) -> Rc<StyledNode> {
Rc::new(StyledNode{
node: Node {
node_type: NodeType::Comment(String::from(“comment”)),
Children: vec![]
},
children: RefCell::new(vec![]),
parent: RefCell::new(Weak::new()),
specified_values: Default::default()
})
}
pub fn make_with(&self, node:Node, specified_values:PropertyMap,
children:RefCell<Vec<Rc<StyledNode>>>) -> Rc<StyledNode> {
let rc = Rc::new(StyledNode {
node,
children,
parent: RefCell::new(Default::default()),
specified_values,
});
for ch in rc.children.borrow().iter() {
*ch.parent.borrow_mut() = Rc::downgrade(&rc);
}
return rc;
}
pub fn set_root(&self, node:Rc<StyledNode>) {
*self.root.borrow_mut() = node;
}
pub fn append(&self, parent:&Rc<StyledNode>, child:&Rc<StyledNode>) {
parent.children.borrow_mut().push(Rc::clone(child));
*child.parent.borrow_mut() = Rc::downgrade(parent);
}
}
Now I can assemble a simple tree like this:
let tree = StyledTree::new();
let root = tree.make();
let child1 = tree.make();
let child2 = tree.make();
tree.set_root(&root);
tree.append(&root,&child1);
tree.append(&root,&child2);
All of the trick reference management is handled in one place.
The Actual Styling Algorithm
Okay, now that I’ve got a proper tree structure it’s time to move on to actually making the style tree.
The process kicks off by calling dom_tree_to_stylednodes() which takes a reference to the root DOM node and the stylesheet. (Really it should be ‘stylesheet’s but I haven’t implemented that part yet). This creates an empty ancestor vector (which could probably go away in a future iteration) then starts the recursive traversal of the Dom tree
pub fn dom_tree_to_stylednodes<'a>(root: &’a Node, stylesheet: &’a Stylesheet) -> StyledTree {
let tree = StyledTree::new();
let mut ansc:Vec<(&Node, &PropertyMap)> = vec![];
tree.set_root(real_style_tree(&tree, root, stylesheet, &mut ansc));
return tree;
}
For each time through real_style_tree it will check if the current Dom node is for an element or text or comment. If it is an element it will run specified_values to calculate the values for that node.
fn real_style_tree<'a>(tree:&StyledTree, root: &’a Node, stylesheet: &’a Stylesheet,
ancestors:&mut Vec::<(&Node,&PropertyMap)>) -> Rc<StyledNode> {
let specified = match root.node_type {
Element(ref elem) => specified_values(elem, stylesheet, ancestors),
Text(_) => HashMap::new(),
Meta(_) => HashMap::new(),
_ => HashMap::new(),
};
let mut a2:Vec<(&Node, &PropertyMap)> = vec![];
a2.push((root, &specified));
let ch2:Vec<Rc<StyledNode>> = root.children.iter()
.map(|child| {
real_style_tree(tree,child, stylesheet, &mut a2)
}).collect();
return tree.make_with((*root).clone(),specified,RefCell::new(ch2));
}
Once calculated it creates a new styled node with tree.make_with.
To calculate specified values first we need to know what rules match the element. First the matching_rules function looks at the stylesheet and its parent stylesheet, and calls match_rule on each rule. match_rule calls matches on each rule, the calculates the specificity. The matches rule does the actual matching. If the rule is a simple selector then checks if the tag name matches the actual element, or the classes, or if it’s the * selector which matches all elements. If the rule is a descendant selector, then it checks if the parent and child both match their part. If the rule ultimately matches then we move to the next part.
If the tule matches then we calculate the specificity. Essentially this means the priority of the rule. Rules using the id selector are a higher priority than class matches, which are higher than element matches, which is higher than *. This code does that calculation:
impl Selector {
pub fn specificity(&self) -> Specificity {
if let Selector::Simple(ref simple) = *self {
let a = simple.id.iter().count();
let b = simple.class.len();
let c = simple.tag_name.iter().count();
return (a, b, c)
}
if let Selector::Ancestor(ref anc) = *self {
return anc.ancestor.specificity();
}
panic!(“unknown selector type”);
}
}
Ultimately it returns a tuple of the id, class, and tag name counts. These tuples are collected into a vector for the target element. Once all of the rules are collected we sort them, then loop through the list copying them into the final specified values. This is the point that inherited values are replaced by their actual inherited values.
// get all values set by all rules
fn specified_values(elem: &ElementData, stylesheet: &Stylesheet,
ancestors:&mut Vec::<(&Node,&PropertyMap)>) -> PropertyMap {
// println!(“styling with ancestors {:#?}”, ancestors.len());
// for an in ancestors.iter() {
// println!(“ ancestor {:#?} {:#?}”, an.0.node_type, an.1);
// }
let mut values:HashMap<String,Value> = HashMap::new();
let mut rules = matching_rules(elem,stylesheet,ancestors);
//sort rules by specificity
rules.sort_by(|&(a,_),&(b,_)| a.cmp(&b));
for (_,rule) in rules {
for declaration in &rule.declarations {
// println!(“checking {} {:#?}”, declaration.name, declaration.value);
let vv = calculate_inherited_property_value(declaration, ancestors);
values.insert(declaration.name.clone(), vv);
}
}
values
}
Now we finally have a sorted HashMap of values that match the element. This all brings us back to realstyletree which is the master function that calls everything else.
fn real_style_tree<'a>(tree:&StyledTree, root: &’a Node, stylesheet: &’a Stylesheet,
ancestors:&mut Vec::<(&Node,&PropertyMap)>) -> Rc<StyledNode> {
let specified = match root.node_type {
Element(ref elem) => specified_values(elem, stylesheet, ancestors),
Text(_) => HashMap::new(),
Meta(_) => HashMap::new(),
_ => HashMap::new(),
};
let mut a2:Vec<(&Node, &PropertyMap)> = vec![];
a2.push((root, &specified));
let ch2:Vec<Rc<StyledNode>> = root.children.iter()
.map(|child| {
real_style_tree(tree,child, stylesheet, &mut a2)
}).collect();
return tree.make_with((*root).clone(),specified,RefCell::new(ch2));
}
As you can see in the code above it calls specified_values on all elements, but skips the text, comments, and meta data. Then it calls real_style_tree on every child of the node, collecting the results in a2. Then it creates the final StyledNode with tree.make_with.
Le Fin
Yay! We’re finally done. This whole process produces a tree of styled nodes. Next time we’ll move on to actually laying out the tree with real pixel values, and producing boxes that can actually be drawn on screen.
You can see the full code of everything I did above here in style/mod.rs in the repo.