17 Sep 2014
Welcome back to my series on building a toy HTML rendering engine:
This article will continue the layout module that we started in Part 5. This time, we'll add the ability to lay out block boxes. These are boxes that are stack vertically, such as headings and paragraphs.
To keep things simple, this code implements only normal flow: no floats, no absolute positioning, and no fixed positioning.
The entry point to this code is the
layout function, which takes a takes a
LayoutBox and calculates its dimensions. We'll break this function into three
cases, and implement only one of them for now:
A block's layout depends on the dimensions of its containing block. For block boxes in normal flow, this is just the box's parent. For the root element, it's the size of the browser window (or "viewport").
You may remember from the previous article that a block's width depends on its parent, while its height depends on its children. This means that our code needs to traverse the tree top-down while calculating widths, so it can lay out the children after their parent's width is known, and traverse bottom-up to calculate heights, so that a parent's height is calculated after its children's.
This function performs a single traversal of the layout tree, doing width calculations on the way down and height calculations on the way back up. A real layout engine might perform several tree traversals, some top-down and some bottom-up.
The width calculation is the first step in the block layout function, and also
the most complicated. I'll walk through it step by step. To start, we need
the values of the CSS
width property and all the left and right edge sizes:
This uses a helper function called
lookup, which just tries a
series of values in sequence. If the first property isn't set, it tries the
second one. If that's not set either, it returns the given default value.
This provides an incomplete (but simple) implementation of shorthand
properties and initial values.
Since a child can't change its parent's width, it needs to make sure its own width fits the parent's. The CSS spec expresses this as a set of constraints and an algorithm for solving them. The following code implements that algorithm.
First we add up the margin, padding, border, and content widths. The
to_px helper method converts lengths to their numerical values. If
a property is set to
'auto', it returns 0 so it doesn't affect the sum.
This is the minimum horizontal space needed for the box. If this isn't equal to the container width, we'll need to adjust something to make it equal.
If the width or margins are set to
'auto', they can expand or contract to
fit the available space. Following the spec, we first check if the box is too
big. If so, we set any expandable margins to zero.
If the box is too large for its container, it overflows the container. If it's too small, it will underflow, leaving extra space. We'll calculate the underflow—the amount of extra space left in the container. (If this number is negative, it is actually an overflow.)
We now follow the spec's algorithm for eliminating any
overflow or underflow by adjusting the expandable dimensions. If there are no
'auto' dimensions, we adjust the right margin. (Yes, this means the
margin may be negative in the case of an overflow!)
At this point, the constraints are met and any
'auto' values have been
converted to lengths. The results are the the used values for
the horizontal box dimensions, which we will store in the layout tree. You
can see the final code in layout.rs.
The next step is simpler. This function looks up the remanining margin/padding/border styles, and uses these along with the containing block dimensions to determine this block's position on the page.
Take a close look at that last statement, which sets the
y position. This
is what gives block layout its distinctive vertical stacking behavior. For
this to work, we'll need to make sure the parent's
content.height is updated
after laying out each child.
Here's the code that recursively lays out the box's contents. As it loops through the child boxes, it keeps track of the total content height. This is used by the positioning code (above) to find the vertical position of the next child.
The total vertical space taken up by each child is the height of its margin box, which we calculate like so:
For simplicity, this does not implement margin collapsing. A real layout engine would allow the bottom margin of one box to overlap the top margin of the next box, rather than placing each margin box completely below the previous one.
By default, the box's height is equal to the height of its contents. But if
'height' property is set to an explicit length, we'll use that instead:
And that concludes the block layout algorithm. You can now call
a styled HTML document, and it will spit out a bunch of rectangles with
widths, heights, margins, etc. Cool, right?
Some extra ideas for the ambitious implementer:
Collapsing vertical margins.
Parallelize the layout process, and measure the effect on performance.
If you try the parallelization project, you may want to separate the width
calculation and the height calculation into two distinct passes. The top-down
traversal for width is easy to parallelize just by spawning a separate task
for each child. The height calculation is a little trickier, since you need
to go back and adjust the
y position of each child after its siblings are
Thank you to everyone who's followed along this far!
These articles are taking longer and longer to write, as I journey further into unfamiliar areas of layout and rendering. There will be a longer hiatus before the next part as I experiment with font and graphics code, but I'll resume the series as soon as I can.
Update: Part 7 is now ready.