Rust Browser 6: Layout
Now we get to the big dramatic part of building a browser. Layout. Until now we’ve just had a tree of data. This is the part where we position actual rectangles and colors and text blocks. The part where we do line wrapping and worry about font sizes. This is the real deal! Let’s dive in.
As you might expect, the layout process is implemented in layout.rs. It’s done in two phases. First, every StyledNode in the style tree is turned into some type of LayoutBox. Then we go through the layout box tree doing the actual layout positioning.
Data Structures
Let’s start with the structures we will need. In the web layout model there are a few key kinds of layout objects: blocks and inlines. A block is a box that takes up all available width and is as short as possible. Blocks stack vertically. Inline boxes are arranged left to right (if in a left to right language) and wrap when they reach the max width. Inlines can even be broken in half (or more) to wrap at the edge of the box. There are a few other box types for things like Tables and Lists, but for now let’s just consider Block and Inline.
Both blocks and inline boxes have sizes as well as borders, padding, and margins. I wrapped this all up into an object called Dimensions, composed of a Rect for the content, and EdgeSizes (left,right,top,bottom) for the borders, padding, and margins. These objects look like this:
#[derive(Clone, Copy, Debug, Default)]
pub struct Dimensions {
pub content: Rect,
pub padding: EdgeSizes,
pub border: EdgeSizes,
pub margin: EdgeSizes,
}
#[derive(Clone, Copy, Debug, Default)]
pub struct Rect {
pub x: f32,
pub y: f32,
pub width: f32,
pub height: f32,
}
#[derive(Clone, Copy, Debug, Default)]
pub struct EdgeSizes {
pub left: f32,
pub right: f32,
pub top: f32,
pub bottom: f32,
}
The final size of the content is calculated by adding the inner rectangles, so lets add some utility methods for those:
impl Dimensions {
fn padding_box(self) -> Rect {
self.content.expanded_by(self.padding)
}
fn border_box(self) -> Rect {
self.padding_box().expanded_by(self.border)
}
fn margin_box(self) -> Rect {
self.border_box().expanded_by(self.margin)
}
}
A rectangle can be expanded by a fixed amount or another edge. We could also ask if a given point is inside a rectangle. So let’s add methods for those:
impl Rect {
pub fn with_inset(self, val:f32) -> Rect {
Rect {
x: (self.x + val).floor() + 0.5,
y: (self.y + val).floor() + 0.5,
width: (self.width - val - val).floor(),
height: (self.height - val -val).floor(),
}
}
fn expanded_by(self, edge: EdgeSizes) -> Rect {
Rect {
x: self.x - edge.left,
y: self.y - edge.top,
width: self.width + edge.left + edge.right,
height: self.height + edge.top + edge.bottom,
}
}
pub fn contains(self, x:f32, y:f32) -> bool {
self.x <= x && self.x + self.width >= x && self.y <= y && self.y + self.height > y
}
}
Now we can define what a LayoutBox is. It’s a box composed of it’s size (the Dimensions), what type of box it is (the BoxType enum), and a vector of children.
#[derive(Debug)]
pub struct LayoutBox {
pub dimensions: Dimensions,
pub box_type: BoxType,
pub children: Vec<LayoutBox>,
}
#[derive(Debug)]
pub enum BoxType {
BlockNode(Rc<StyledNode>),
InlineNode(Rc<StyledNode>),
InlineBlockNode(Rc<StyledNode>),
AnonymousBlock(Rc<StyledNode>),
TableNode(Rc<StyledNode>),
TableRowGroupNode(Rc<StyledNode>),
TableRowNode(Rc<StyledNode>),
TableCellNode(Rc<StyledNode>),
ListItemNode(Rc<StyledNode>),
}
You can see the box type definition above. As previously stated, we mainly care about a BlockNode and InlineNode. An InlineBlockNode is when something behaves like a block internally, but is still formatted in an inline context. This is mainly for images. We can ignore the table and list item types for now. That just leaves AnonymousBlock. It’s special.
Layout Flows
When we layout stuff in the DOM we have two types of flows. The block flow and the inline flow. Blocks stack vertically. Inlines go left to right and wrap. The tricky part is that a block flow can only contain blocks. And an inline flow can only contain inlines. So what do we do when a block flow actually contains a mixture inlines and blocks? Let’s look at some examples.
<div>
Some text.
<b>bold!</b>
and more text.
</div>
The example above shows a div with some text inside it. The div is itself a block, but it contains only inline children: the b element and the raw text. So it would have an inline flow.
This next example has only block children.
<div>
<p>some text</p>
<p>some <b>more</b> text</p>
</div>
This div has only p children. (Yes, the b is inside of the div, but is not a direct descendant of the div. It’s actually a child of p first). Since p is a block type, the div only has block children, and will use a block formatting flow; meaning the p elements will all stack vertically.
Now let’s look at this example:
<div>
<b>Some text before</b>
<p>a paragraph</p>
some text after
</div>
The div has a b child (inline), a p child (block), and some raw text (inline). It has mixed children, but it can only be block or inline flow. Not both. What do we do?
The DOM formatting model tells us. In this case anonymous block parents are formed around the inline content, so that the div only has block children again. It would as if this is the original markup, even though it’s not.
<div>
<anonymous><b>Some text before</b></anonymous>
<p>a paragraph</p>
<anonymous>some text after</anonymous>
</div>
All of the above is just a long way of saying that if a block element has both block and inline children then we need to generate some anonymous blocks to wrap them up nicely.
Layout Phase 1
Now let’s get back to some code. First we’ll look at the recursive build_layout_tree function which turns StyledNodes into LayoutBoxs.
pub fn build_layout_tree<‘a>(style_node: &Rc<StyledNode>, doc:&Document) -> LayoutBox {
let mut root = LayoutBox::new(match style_node.display() {
Display::Block => BlockNode(Rc::clone(style_node)),
Display::Inline => InlineNode(Rc::clone(style_node)),
Display::InlineBlock => InlineBlockNode(Rc::clone(style_node)),
Display::ListItem => BoxType::ListItemNode(Rc::clone(style_node)),
Display::Table => TableNode(Rc::clone(style_node)),
Display::TableRowGroup => TableRowGroupNode(Rc::clone(style_node)),
Display::TableRow => TableRowNode(Rc::clone(style_node)),
Display::TableCell => TableCellNode(Rc::clone(style_node)),
Display::None => panic!(“Root node has display none.”)
});
This part is pretty simple. It matches on the style_node.display() property. If it’s a Block then it makes a BlockNode(). If it’s an Inline it makes an InlineBlock(). etc.
Now let’s look at the children of the StyledNode.
for child in style_node.children.borrow().iter() {
match child.display() {
Display::Block => root.children.push(build_layout_tree(child, doc)),
Display::ListItem => root.children.push(build_layout_tree(child, doc)),
Display::Inline => root.get_inline_container().children.push(build_layout_tree(&child, doc)),
Display::InlineBlock => root.get_inline_container().children.push(build_layout_tree(&child, doc)),
Display::Table => root.children.push(build_layout_tree(&child,doc)),
Display::TableRowGroup => root.children.push(build_layout_tree(&child, doc)),
Display::TableRow => root.children.push(build_layout_tree(&child,doc)),
Display::TableCell => root.children.push(build_layout_tree(&child,doc)),
Display::None => { },
}
}
root
}
It loops over the children of the node. If the child is also a block, then it just recursively calls build_layout_tree again on the child. It does the same for all of the other block like types: (ListItem, Table, TableRow, TableCell, etc.). In every case it calls build_layout_tree to produce a new layoutbox for the child, then adds that child to the new root layout boxes children.
If the child is an inline or inline block, however, it still calls build_layout_tree but it adds the child to the root’s inline container. This is the magic part that handles anonymous boxes. Let’s take a look at get_inline_container.
fn get_inline_container(&mut self) -> &mut LayoutBox {
match &self.box_type {
InlineNode(_) | InlineBlockNode(_) | AnonymousBlock(_) => self,
BlockNode(node)
| ListItemNode(node)
| TableNode(node)
| TableCellNode(node)
| TableRowGroupNode(node)
| TableRowNode(node) => {
// if last child is anonymous block, keep using it
let last = self.children.last();
let is_anon = match last {
Some(ch) => {
match ch.box_type {
AnonymousBlock(_) => true,
_ => {false}
}
},
_ => {
false
}
};
if !is_anon {
// make new anon block
self.children.push(LayoutBox::new(AnonymousBlock(Rc::clone(node))))
}
self.children.last_mut().unwrap()
}
}
}
If the root is an inline, inline block, or anonymous block, then it already is an inline container, so it just returns itself. If the root is a block type, then it creates a new AnonymousBlock as the child. However, first it checks if it already has an anonymous block child. If it does then it reuses that child, if not it creates a new anonymous child. Either way it returns something that can accept new inline children.
So that’s it for phase 1.
Layout Phase 2
Once we’ve turned the tree of StyledNodes into a tree of LayoutBoxes it’s time to start positioning things. That’s what the layout function does.
To actually do layout we need some information in place first. First we need to know how big the page is. In DOM terms this is called the viewport. As the layout progresses the available area for layout might shrink (say the inside of a table column, or because a parent used up some space with padding). As we go through this is called the containing block. It’s represented by Dimensions.
Next we need to have real fonts that we can measure. We need to know how high and wide some bit of text will be in a given font size, weight, family, etc. And of course we don’t want to load a whole font everything we need to measure something, so all of the font data is stored inside of an object called the FontCache. It caches the actual font data and can return glyphs for measuring.
Finally we need a reference to the original Document. All of the style information is already available in the StyledNodes, but we still need the base URL of the document so we can load images and other resources from relative URLs.
All of the above dependencies are encoded in the signature of layout. Now we can call it:
pub fn layout(&mut self, containing: &mut Dimensions, font:&mut FontCache, doc:&Document) -> RenderBox {
match &self.box_type {
BlockNode(_node) => RenderBox::Block(self.layout_block(containing, font, doc)),
TableNode(_node) => RenderBox::Block(self.layout_block(containing, font, doc)),
TableRowGroupNode(_node) => RenderBox::Block(self.layout_block(containing, font, doc)),
TableRowNode(_node) => RenderBox::Block(self.layout_table_row(containing, font, doc)),
TableCellNode(_node) => RenderBox::Block(self.layout_block(containing, font, doc)),
InlineNode(_node) => RenderBox::Inline(),
InlineBlockNode(_node) => RenderBox::InlineBlock(),
AnonymousBlock(_node) => RenderBox::Anonymous(self.layout_anonymous_2(containing, font, doc)),
ListItemNode(_node) => RenderBox::Block(self.layout_block(containing, font, doc)),
}
}
The layout just matches on the type of box, then delegates to a specific layout algorithm. Blocks and other block like things go to layout_block. Table rows are special so they go to layout_table_row. Anonymous blocks go to layout_anonymous_2. (There’s an older implementation of this called layoutanonymous1 that I still need to delete). Each of these returns a RenderBox, which is the object that the rendering system can actually draw on screen. We’ll cover that part in the next blog of this series.
Laying Out Blocks
Let’s take a look at how layout_block works. I know it looks big but it’s actually pretty simple. First it calculates the width of the block, then vertical position, then recursively lays out it’s children. Finally, once the children are done, it can determine it’s own final height. Then it produces the RenderBox that will be used for drawing. RenderBlockBox has a ton of fields, but they are mostly straightforward data fields for things like the size, color, and padding of the box.
fn layout_block(&mut self, containing_block: &mut Dimensions,
font_cache:&mut FontCache, doc:&Document) -> RenderBlockBox {
self.calculate_block_width(containing_block);
self.calculate_block_position(containing_block);
let children:Vec<RenderBox> = self.layout_block_children(font_cache, doc);
self.calculate_block_height();
let zero = Length(0.0, Px);
let style = self.get_style_node();
RenderBlockBox{
rect:self.dimensions.content,
margin: self.dimensions.margin,
padding: self.dimensions.padding,
children,
title: self.debug_calculate_element_name(),
background_color: style.color(“background-color”),
border_width: EdgeSizes {
top: style.lookup_length_as_px(“border-width-top”, 0.0),
bottom: style.lookup_length_as_px(“border-width-bottom”,0.0),
left: style.lookup_length_as_px(“border-width-top”,0.0),
right: style.lookup_length_as_px(“border-width-bottom”,0.0),
},
border_color: style.color(“border-color”),
valign: String::from(“baseline”),
marker: if style.lookup_string(“display”,”block”) == “list-item” {
match &*style.lookup_string(“list-style-type”, “none”) {
“disc” => ListMarker::Disc,
_ => ListMarker::None,
}
} else {
ListMarker::None
},
color: Some(style.lookup_color("color", &BLACK)),
font_family: style.lookup_font_family(font_cache),
font_weight : style.lookup_font_weight(400),
font_style : style.lookup_string("font-style", "normal"),
font_size: style.lookup_font_size(),
}
}
I’m not going to go into how calculate_block_width and calculateblockposition work because they are long and have a lot of edge cases. They are direct translation of the CSS specs, so they would be pretty easy to follow. Essentially calculateblockposition looks up style values to calculate the padding, margin, and borders, then figure out the final height through addition. calculate_block_width works the same way except that it has to handle special cases like a margin being set to auto. In any case, the end result of these is that the values for self.dimension.content.*, self.dimension.padding.*, etc are filled in.
In some cases the style values are relative units like ems. To handle these all style values are put through a lengthtopx function that calculates the final computed value as pixels.
For example, suppose we want to know the height of the top border of a box. We’d calculate it like this:
let border = EdgeSizes {
top: style.lookup_length_as_px(“border-width-top”,0.0),
bottom: style.lookup_length_as_px(“border-width-bottom”,0.0),
..(self.dimensions.border)
};
Where lookuplengthas_px is
pub fn lookup_length_as_px(&self, name:&str, default:f32) -> f32{
if let Some(value) = self.value(name) {
match value {
Length(v, Unit::Px) => v,
Length(v, Unit::Em) => v*self.lookup_font_size(),
Length(v, Unit::Rem) => v*self.lookup_font_size(),
// TODO: use real document font size
Length(_v, Unit::Per) => {
default
}
_ => default,
}
} else {
default
}
}
Once the render box size and vertical position are calculated the code calls layout_block_children to recursively layout the children.
fn layout_block_children(&mut self, font_cache:&mut FontCache, doc:&Document) -> Vec<RenderBox>{
let d = &mut self.dimensions;
let mut children:Vec<RenderBox> = vec![];
for child in self.children.iter_mut() {
let bx = child.layout(d, font_cache, doc);
d.content.height += child.dimensions.margin_box().height;
children.push(bx)
};
children
}
Note how dimensions.content.height is incremented for each child by however high that child is. Once all of the children are laid out it will have the final height of the parent. Of course the parent could have have an explicit height which overrides the calculated height, so calculate_block_height takes care of that.
fn calculate_block_height(&mut self) {
if let Some(val) = self.get_style_node().value(“height”) {
self.dimensions.content.height = self.length_to_px(&val);
}
}
So that’s it for block layout. At the end of the day it’s just stacking up boxes and shrinking the available width using padding, borders, and margins. Inline layout is a lot trickier.
Inline Layout
Let’s take a look at layout_anonymous, which handles the inline layout. I’ve gone through several iterations of this code and I’m still not 100% happy with it. It’s simply a complex problem. You have to measure the text and break it into line boxes. But you also have to handle inline blocks that can’t be broken (like images). And you also have to handle nested inline elements the can be broken, like span and b.
This complex recursive loop is even more complicated because there’s a lot of state that has to be passed around like the current line box, how far to the left or right we are, the style of the current node, etc. To address this I created a context object called Looper that stores all of the current values. It is passed down through the recursive loop so that we can keep everything straight. Let’s dive in and I’ll try to explain a little of how it works (but keep in mind this is definitely the most complicated part of the browser).
fn layout_anonymous_2(&mut self, dim:&mut Dimensions,
font_cache:&mut FontCache, doc:&Document) -> RenderAnonymousBox {
let mut looper = Looper {
Lines: vec![],
current: RenderLineBox {
rect: Rect{
x: dim.content.x,
y: dim.content.y + dim.content.height,
width: dim.content.width,
height: 0.0,
},
baseline:0.0,
Children: vec![]
},
extents: Rect {
x: dim.content.x,
y: dim.content.y + dim.content.height,
width: dim.content.width,
height: 0.0,
},
current_start: dim.content.x,
current_end: dim.content.x,
current_bottom: dim.content.y + dim.content.height,
font_cache:font_cache,
doc,
style_node:Rc::clone(self.get_style_node()),
};
for child in self.children.iter_mut() {
match &child.box_type {
InlineBlockNode(_styled) => child.do_inline_block(&mut looper),
InlineNode(_styled) => child.do_inline(&mut looper),
_ => println!(“can’t do this child of an anonymous box”),
}
}
looper.adjust_current_line_vertical();
looper.adjust_current_line_horizontal();
let old = looper.current;
looper.current_bottom += old.rect.height;
looper.extents.height += old.rect.height;
looper.lines.push(old);
self.dimensions.content.y = looper.extents.y;
self.dimensions.content.width = looper.extents.width;
self.dimensions.content.height = looper.current_bottom - looper.extents.y ;
RenderAnonymousBox {
rect: looper.extents,
children: looper.lines,
}
}
To start it creates a Looper instance. This tracks the current line box, the available space (extents), the current x and y positions, and carries along the current doc, font cache, and style node. It collects all of the line boxes into a lines property.
Once the looper is created the code loops over every child. If it’s an inline block it calls do_inline_block on the child. Otherwise it calls do_inline. Once the children are handled it finalizes each line box’s horizontal and vertical alignment with looper.adjust_current_line_vertical() and looper.adjust_current_line_horizontal(). Finally it calculates the bottom edge of the anonymous box and returns the new RenderBox.
Let’s take a look at do_inline, which implements the standard inline layout algorithm of chopping text up into lines by measuring them.
fn do_inline(&self, looper:&mut Looper) {
// println!(“doing inline {:#?}”, &self.debug_calculate_element_name());
let link:Option<String> = match &looper.style_node.node.node_type {
Text(_) => None,
NodeType::Comment(_) => None,
NodeType::Cdata(_) => None,
Element(ed) => {
if ed.tag_name == “a” {
ed.attributes.get("href").map(String::from)
} else {
None
}
},
NodeType::Meta(_) => None,
};
if let BoxType::InlineNode(snode) = &self.box_type {
match &snode.node.node_type {
NodeType::Text(txt) => {
let whitespace = looper.style_node.lookup_keyword(“white-space”,
&Keyword(String::from(“normal”)));
match whitespace {
Keyword(str) => {
match &*str {
“pre” => return self.do_pre_layout(looper,txt,&link),
_ => return self.do_normal_inline_layout(looper,txt,&link),
}
},
_ => {
println!(“invalid whitespace type”);
}
}
}
// if child is element
NodeType::Element(_ed) => {
// println!(“recursing”);
let old = Rc::clone(&looper.style_node);
looper.style_node = Rc::clone(snode);
for ch in self.children.iter() {
ch.do_inline(looper);
}
looper.style_node = old;
}
_ => {}
}
}
}
First it checks if the current node is a link. If it does then it extracts the href. Next I checks if the node is text. If it is it looks up the whitespace setting of the text. If it’s pre, then it delegates to the do_pre_layout function, otherwise it does the do_normal_inline_layout. If the node is actually an element, it swaps in the child elements style node and recurses on do_inline.
Finally we get to do_normal_inline_layout. This looks up the style of the current text, splits it into words, then actually measures the text using the font.
fn do_normal_inline_layout(&self, looper:&mut Looper, txt:&str, link:&Option<String>) {
// println!(“processing text ‘{}’”, txt);
let font_family = looper.style_node.lookup_font_family(looper.font_cache);
// println!(“using font family {}”, font_family);
let font_weight = looper.style_node.lookup_font_weight(400);
let font_size = looper.style_node.lookup_font_size();
let font_style = looper.style_node.lookup_string("font-style”, “normal”);
let vertical_align = looper.style_node.lookup_string(“vertical-align”,”baseline”);
let line_height = font_size;
// let line_height = looper.style_node.lookup_length_px(“line-height”, line_height);
let color = looper.style_node.lookup_color(“color”, &BLACK);
// println!(“styles={:#?}”,looper.style_node);
// println!(“parent={:#?}”, parent.get_style_node());
// println!(“looper is {} {} {}”,looper.current_start, looper.current_end, looper.current_start);
let mut curr_text = String::new();
for word in txt.split_whitespace() {
let mut word2 = String::from(“ “);
word2.push_str(word);
let w: f32 = calculate_word_length(word2.as_str(), looper.font_cache, font_size,
&font_family, font_weight, &font_style);
//if it’s too long then we need to wrap
if looper.current_end + w > looper.extents.x + looper.extents.width {
//add current text to the current line
// println!(“wrapping: {} cb = {}”, curr_text, looper.current_bottom);
let bx = RenderInlineBoxType::Text(RenderTextBox{
rect: Rect{
x: looper.current_start,
y: looper.current_bottom,
width: looper.current_end - looper.current_start,
height: line_height
},
text: curr_text,
color: Some(color.clone()),
background_color: looper.style_node.color(“background-color”),
font_size,
font_family: font_family.clone(),
font_style: font_style.clone(),
link: link.clone(),
font_weight,
valign: vertical_align.clone(),
text_decoration_line: looper.style_node.lookup_text_decoration_line(),
});
looper.add_box_to_current_line(bx);
//make new current text with the current word
curr_text = String::new();
curr_text.push_str(&word2);
curr_text.push_str(“ “);
looper.current_bottom += looper.current.rect.height;
looper.extents.height += looper.current.rect.height;
looper.adjust_current_line_vertical();
looper.adjust_current_line_horizontal();
looper.start_new_line();
looper.current_end += w;
} else {
looper.current_end += w;
curr_text.push_str(&word2);
}
}
let bx = RenderInlineBoxType::Text(RenderTextBox{
rect: Rect {
x: looper.current_start,
y: looper.current_bottom,
width: looper.current_end - looper.current_start,
height: line_height,
},
text: curr_text,
color: Some(color.clone()),
background_color: looper.style_node.color(“background-color”),
font_size,
font_family,
link: link.clone(),
font_weight,
font_style,
valign: vertical_align.clone(),
text_decoration_line: looper.style_node.lookup_text_decoration_line(),
});
// println!(“added text box {:#?}”,bx);
looper.add_box_to_current_line(bx);
}
There’s a lot in this function, but the core is in three parts. First it looks up the font_family, weight, size, style, and vertical alignment. Next it splits the text by whitespace, since we can only break words at the whitespace bounds. For each word it adds it to the current line and measures it using calculate_word_length. If the new line of text would be too long for the available space then it creates a text box for the existing text, adds it to the current line box (looper.add_box_to_current_line(bx)) then starts a new line with looper.start_new_line(). If the new word will fit on the current line, then it just adds it to the text and increments looper.current_end with the extra width.
Once it runs out of text to measure it adds whatever is left to the final line box, then returns.
The code actually looks a lot more complicated than it is. That’s because there are a ton of properties that need to be copied around for the font size, color, style, etc. If you want something simpler take a look at do_pre_layout which doesn’t split text by measuring. Instead it just splits the text by newlines and creates a line box for each.
Conclusion
Okay. We’ve gotten through possibly the hardest part: layout. I didn’t cover everything like table layout or styling lists, but those are pretty easy to understand once you’ve mastered the standard inline layout.
I didn’t dive into how horizontal and vertical alignment are handled. Those are done in the adjust_current_line_vertical and adjust_current_line_horizontal functions on the lineboxes. Essentially after a line is composed it shifts the elements around to match the requested alignment. The code should be pretty easy to understand.
Another thing my code doesn’t handle at all is positioned layout. Things like absolute and fixed position, or flex box and grid, add a whole new layer of complexity that I didn’t want to tackle with this project.
Everything we did today is about turning StyleNodes into LayoutBoxes, then into RenderBoxes. Next time we’ll cover how to actually draw the render boxes on the screen.
Be safe, everyone!