# Chapter 11: Layout Engine

You might be reading this as an HTML page, an e-book (which is basically the same thing), or on the printed page. In all three cases, a layout engine took some text and some layout instructions and decided where to put each character and image. We will build a small layout engine in this chapter based on Matt Brubeck’s tutorial to explore how browsers decide what to put where.

Our inputs will be a very small subset of HTML and an equally small subset of CSS. We will create our own classes to represent these instead of using those provided by various Node libraries; to translate the combination of HTML and CSS into text on the screen, we will label each node in the DOM tree with the appropriate styles, walk that tree to figure out where each visible element belongs, and then draw the result as text on the screen.

### Upside down

The coordinate systems for screens puts (0, 0) in the upper left corner instead of the lower left. X increases to the right as usual, but Y increases as we go down, rather than up (Figure 11.1). This convention is a holdover from the days of teletype terminals that printed lines on rolls of paper; as Mike Hoye has repeatedly observed, the past is all around us.

## Section 11.2: How can we size rows and columns?

Let’s start on easy mode without margins, padding, line-wrapping, or other complications. Everything we can put on the screen is represented as a rectangular cell, and every cell is either a row, a column, or a block. A block has a fixed width and height:

export class Block {
constructor (width, height) {
this.width = width
this.height = height
}

getWidth () {
return this.width
}

getHeight () {
return this.height
}
}


A row arranges one or more cells horizontally; its width is the sum of the widths of its children, while its height is the height of its tallest child (Figure 11.2):

export class Row {
constructor (...children) {
this.children = children
}

getWidth () {
let result = 0
for (const child of this.children) {
result += child.getWidth()
}
return result
}

getHeight () {
let result = 0
for (const child of this.children) {
result = Math.max(result, child.getHeight())
}
return result
}
}


Finally, a column arranges one or more cells vertically; its width is the width of its widest child and its height is the sum of the heights of its children. (Here and elsewhere we use the abbreviation col when referring to columns.)

export class Col {
constructor (...children) {
this.children = children
}

getWidth () {
let result = 0
for (const child of this.children) {
result = Math.max(result, child.getWidth())
}
return result
}

getHeight () {
let result = 0
for (const child of this.children) {
result += child.getHeight()
}
return result
}
}


Rows and columns nest inside one another: a row cannot span two or more columns, and a column cannot cross the boundary between two rows. Any time we have a structure with that property we can represent it as a tree of nested objects. Given such a tree, we can calculate the width and height of each cell every time we need to. This is simple but inefficient: we could calculate both width and height at the same time and cache those values to avoid recalculation, but we called this “easy mode” for a reason.

As simple as it is, this code could still contain errors (and did during development), so we write some Mocha tests to check that it works as desired before trying to build anything more complicated:

import assert from 'assert'

import {
Block,
Row,
Col
} from '../easy-mode.js'

describe('lays out in easy mode', () => {
it('lays out a single unit block', async () => {
const fixture = new Block(1, 1)
assert.strictEqual(fixture.getWidth(), 1)
assert.strictEqual(fixture.getHeight(), 1)
})

it('lays out a large block', async () => {
const fixture = new Block(3, 4)
assert.strictEqual(fixture.getWidth(), 3)
assert.strictEqual(fixture.getHeight(), 4)
})

it('lays out a row of two blocks', async () => {
const fixture = new Row(
new Block(1, 1),
new Block(2, 4)
)
assert.strictEqual(fixture.getWidth(), 3)
assert.strictEqual(fixture.getHeight(), 4)
})

it('lays out a column of two blocks', async () => {
const fixture = new Col(
new Block(1, 1),
new Block(2, 4)
)
assert.strictEqual(fixture.getWidth(), 2)
assert.strictEqual(fixture.getHeight(), 5)
})

it('lays out a grid of rows of columns', async () => {
const fixture = new Col(
new Row(
new Block(1, 2),
new Block(3, 4)
),
new Row(
new Block(5, 6),
new Col(
new Block(7, 8),
new Block(9, 10)
)
)
)
assert.strictEqual(fixture.getWidth(), 14)
assert.strictEqual(fixture.getHeight(), 22)
})
})

> stjs@1.0.0 test /u/stjs
> mocha */test/test-*.js "-g" "easy mode"

lays out in easy mode
✓ lays out a single unit block
✓ lays out a large block
✓ lays out a row of two blocks
✓ lays out a column of two blocks
✓ lays out a grid of rows of columns

5 passing (7ms)


## Section 11.3: How can we position rows and columns?

Now that we know how big each cell is we can figure out where to put it. Suppose we start with the upper left corner of the browser: upper because we lay out the page top-to-bottom and left because we are doing left-to-right layout. If the cell is a block, we place it there. If the cell is a row, on the other hand, we get its height and then calculate its lower edge as y1 = y0 + height. We then place the first child’s lower-left corner at (x0, y1), the second child’s at (x0 + width0, y1), and so on (Figure 11.3). Similarly, if the cell is a column we place the first child at (x0, y0), the next at (x0, y0 + height0), and so on.

To save ourselves some testing we will derive the classes that know how to do layout from the classes we wrote before. Our blocks are:

export class PlacedBlock extends Block {
constructor (width, height) {
super(width, height)
this.x0 = null
this.y0 = null
}

place (x0, y0) {
this.x0 = x0
this.y0 = y0
}

report () {
return [
'block', this.x0, this.y0,
this.x0 + this.width,
this.y0 + this.height
]
}
}


while our columns are:

export class PlacedCol extends Col {
constructor (...children) {
super(...children)
this.x0 = null
this.y1 = null
}

place (x0, y0) {
this.x0 = x0
this.y0 = y0
let yCurrent = this.y0
this.children.forEach(child => {
child.place(x0, yCurrent)
yCurrent += child.getHeight()
})
}

report () {
return [
'col', this.x0, this.y0,
this.x0 + this.getWidth(),
this.y0 + this.getHeight(),
...this.children.map(child => child.report())
]
}
}


and our rows are:

export class PlacedRow extends Row {
constructor (...children) {
super(...children)
this.x0 = null
this.y0 = null
}

place (x0, y0) {
this.x0 = x0
this.y0 = y0
const y1 = this.y0 + this.getHeight()
let xCurrent = x0
this.children.forEach(child => {
const childY = y1 - child.getHeight()
child.place(xCurrent, childY)
xCurrent += child.getWidth()
})
}

report () {
return [
'row', this.x0, this.y0,
this.x0 + this.getWidth(),
this.y0 + this.getHeight(),
...this.children.map(child => child.report())
]
}
}


Once again, we write and run some tests to check that everything is doing what it’s supposed to:

import assert from 'assert'

import {
PlacedBlock as Block,
PlacedCol as Col,
PlacedRow as Row
} from '../placed.js'

describe('places blocks', () => {
it('places a single unit block', async () => {
const fixture = new Block(1, 1)
fixture.place(0, 0)
assert.deepStrictEqual(
fixture.report(),
['block', 0, 0, 1, 1]
)
})

it('places a large block', async () => {
const fixture = new Block(3, 4)
fixture.place(0, 0)
assert.deepStrictEqual(
fixture.report(),
['block', 0, 0, 3, 4]
)
})

it('places a row of two blocks', async () => {
const fixture = new Row(
new Block(1, 1),
new Block(2, 4)
)
fixture.place(0, 0)
assert.deepStrictEqual(
fixture.report(),
['row', 0, 0, 3, 4,
['block', 0, 3, 1, 4],
['block', 1, 0, 3, 4]
]
)
})

})

> stjs@1.0.0 test /u/stjs
> mocha */test/test-*.js "-g" "places blocks"

places blocks
✓ places a single unit block
✓ places a large block
✓ places a row of two blocks
✓ places a column of two blocks
✓ places a grid of rows of columns

5 passing (8ms)


## Section 11.4: How can we render elements?

We drew the blocks on a piece of graph paper in order to figure out the expected answers for the tests shown above. We can do something similar in software by creating a “screen” of space characters and then having each block draw itself in the right place. If we do this starting at the root of the tree, child blocks will overwrite the markings made by their parents, which will automatically produce the right appearance (Figure 11.4). (A more sophisticated version of this called z-buffering keeps track of the visual depth of each pixel in order to draw things in three dimensions.)

Our pretended screen is just an array of arrays of characters:

const makeScreen = (width, height) => {
const screen = []
for (let i = 0; i < height; i += 1) {
screen.push(new Array(width).fill(' '))
}
return screen
}


We will use successive lower-case characters to show each block, i.e., the root block will draw itself using the letter a, while its children will use b, c, and so on.

const draw = (screen, node, fill = null) => {
fill = nextFill(fill)
node.render(screen, fill)
if ('children' in node) {
node.children.forEach(child => {
fill = draw(screen, child, fill)
})
}
return fill
}

const nextFill = (fill) => {
return (fill === null)
? 'a'
: String.fromCharCode(fill.charCodeAt() + 1)
}


To teach each kind of cell how to render itself, we have to derive a new class from each of the ones we have and give the new class a render method with the same signature:

export class RenderedBlock extends PlacedBlock {
render (screen, fill) {
drawBlock(screen, this, fill)
}
}

export class RenderedCol extends PlacedCol {
render (screen, fill) {
drawBlock(screen, this, fill)
}
}

export class RenderedRow extends PlacedRow {
render (screen, fill) {
drawBlock(screen, this, fill)
}
}

const drawBlock = (screen, node, fill) => {
for (let ix = 0; ix < node.getWidth(); ix += 1) {
for (let iy = 0; iy < node.getHeight(); iy += 1) {
screen[node.y0 + iy][node.x0 + ix] = fill
}
}
}


These render methods do exactly the same thing, so we have each one call a shared function that does the actual work. If we were building a real layout engine, a cleaner solution would be to go back and create a class called Cell with this render method, then derive our Block, Row, and Col classes from that. In general, if two or more classes need to be able to do something, we should add a method to do that to their lowest common ancestor.

Our simpler tests are a little easier to read once we have rendering in place, though we still had to draw things on paper to figure out our complex ones:

  it('renders a grid of rows of columns', async () => {
const fixture = new Col(
new Row(
new Block(1, 2),
new Block(3, 4)
),
new Row(
new Block(1, 2),
new Col(
new Block(3, 4),
new Block(2, 3)
)
)
)
fixture.place(0, 0)
assert.deepStrictEqual(
render(fixture),
[
'bddd',
'bddd',
'cddd',
'cddd',
'ehhh',
'ehhh',
'ehhh',
'ehhh',
'eiig',
'fiig',
'fiig'
].join('\n')
)
})


The fact that we find our own tests difficult to understand is a sign that we should do more testing. It would be very easy for us to get a wrong result and convince ourselves that it was actually correct; confirmation bias of this kind is very common in software development.

## Section 11.5: How can we wrap elements to fit?

One of the biggest differences between a browser and a printed page is that the text in the browser wraps itself automatically as the window is resized. (The other, these days, is that the printed page doesn’t spy on us, though someone is undoubtedly working on that.)

To add wrapping to our layout engine, suppose we fix the width of a row. If the total width of the children is greater than the row’s width, the layout engine needs to wrap the children around. This assumes that columns can be made as big as they need to be, i.e., that we can grow vertically to make up for limited space horizontally. It also assumes that all of the row’s children are no wider than the width of the row; we will look at what happens when they’re not in the exercises.

Our layout engine manages wrapping by transforming the tree. The height and width of blocks are fixed, so they become themselves. Columns become themselves as well, but since they have children that might need to wrap, the class representing columns needs a new method:

export class WrappedBlock extends PlacedBlock {
wrap () {
return this
}
}

export class WrappedCol extends PlacedCol {
wrap () {
const children = this.children.map(child => child.wrap())
return new PlacedCol(...children)
}
}


Rows do all the hard work. Each original row is replaced with a new row that contains a single column with one or more rows, each of which is one “line” of wrapped cells (Figure 11.5). This replacement is unnecessary when everything will fit on a single row, but it’s easiest to write the code that does it every time; we will look at making this more efficient in the exercises.

Our new wrappable row’s constructor takes a fixed width followed by the children and returns that fixed width when asked for its size:

export class WrappedRow extends PlacedRow {
constructor (width, ...children) {
super(...children)
assert(width >= 0,
'Need non-negative width')
this.width = width
}

getWidth () {
return this.width
}

}


Wrapping puts the row’s children into buckets, then converts the buckets to a row of a column of rows:

  wrap () {
const children = this.children.map(child => child.wrap())
const rows = []
let currentRow = []
let currentX = 0

children.forEach(child => {
const childWidth = child.getWidth()
if ((currentX + childWidth) <= this.width) {
currentRow.push(child)
currentX += childWidth
} else {
rows.push(currentRow)
currentRow = [child]
currentX = childWidth
}
})
rows.push(currentRow)

const newRows = rows.map(row => new PlacedRow(...row))
const newCol = new PlacedCol(...newRows)
return new PlacedRow(newCol)
}


Once again we bring forward all the previous tests and write some new ones to test the functionality we’ve added:

  it('wrap a row of two blocks that do not fit on one row', async () => {
const fixture = new Row(
3,
new Block(2, 1),
new Block(2, 1)
)
const wrapped = fixture.wrap()
wrapped.place(0, 0)
assert.deepStrictEqual(
wrapped.report(),
['row', 0, 0, 2, 2,
['col', 0, 0, 2, 2,
['row', 0, 0, 2, 1,
['block', 0, 0, 2, 1]
],
['row', 0, 1, 2, 2,
['block', 0, 1, 2, 2]
]
]
]
)
})

> stjs@1.0.0 test /u/stjs
> mocha */test/test-*.js "-g" "wraps blocks"

wraps blocks
✓ wraps a single unit block
✓ wraps a large block
✓ wrap a row of two blocks that fit on one row
✓ wraps a column of two blocks
✓ wraps a grid of rows of columns that all fit on their row
✓ wrap a row of two blocks that do not fit on one row
✓ wrap multiple blocks that do not fit on one row

7 passing (10ms)


### The Liskov Substitution Principle

We are able to re-use tests like this because of the Liskov Substitution Principle, which states that it should be possible to replace objects in a program with objects of derived classes without breaking anything. In order to satisfy this principle, new code must handle the same set of inputs as the old code, though it may be able to process more inputs as well. Conversely, its output must be a subset of what the old code produced so that whatever is downstream from it won’t be surprised. Thinking in these terms leads to a methodology called design by contract.

## Section 11.6: What subset of CSS will we support?

It’s finally time to style pages that contain text. Our final subset of HTML has rows, columns, and text blocks as before. Each text block has one or more lines of text; the number of lines determines the block’s height and the length of the longest line determines its width.

Rows and columns can have attributes just as they can in real HTML, and each attribute must have a single value in quotes. Rows no longer take a fixed width: instead, we will specify that with our little subset of CSS. Together, these three classes are just over 40 lines of code:

export class DomBlock extends WrappedBlock {
constructor (lines) {
super(
Math.max(...lines.split('\n').map(line => line.length)),
lines.length
)
this.lines = lines
this.tag = 'text'
this.rules = null
}

findRules (css) {
this.rules = css.findRules(this)
}
}

export class DomCol extends WrappedCol {
constructor (attributes, ...children) {
super(...children)
this.attributes = attributes
this.tag = 'col'
this.rules = null
}

findRules (css) {
this.rules = css.findRules(this)
this.children.forEach(child => child.findRules(css))
}
}

export class DomRow extends WrappedRow {
constructor (attributes, ...children) {
super(0, ...children)
this.attributes = attributes
this.tag = 'row'
this.rules = null
}

findRules (css) {
this.rules = css.findRules(this)
this.children.forEach(child => child.findRules(css))
}
}


We will use regular expressions to parse HTML (though as we explained in Chapter 8, this is a sin). The main body of our parser is:

import assert from 'assert'

import {
DomBlock,
DomCol,
DomRow
} from './micro-dom.js'

const TEXT_AND_TAG = /^([^<]*)(<[^]+?>)(.*)$/ms const TAG_AND_ATTR = /<(\w+)([^>]*)>/ const KEY_AND_VALUE = /\s*(\w+)="([^"]*)"\s*/g const parseHTML = (text) => { const chunks = chunkify(text.trim()) assert(isElement(chunks[0]), 'Must have enclosing outer node') const [node, remainder] = makeNode(chunks) assert(remainder.length === 0, 'Cannot have dangling content') return node } const chunkify = (text) => { const raw = [] while (text) { const matches = text.match(TEXT_AND_TAG) if (!matches) { break } raw.push(matches[1]) raw.push(matches[2]) text = matches[3] } if (text) { raw.push(text) } const nonEmpty = raw.filter(chunk => (chunk.length > 0)) return nonEmpty } const isElement = (chunk) => { return chunk && (chunk[0] === '<') } export default parseHTML  while the two functions that do most of the work are: const makeNode = (chunks) => { assert(chunks.length > 0, 'Cannot make nodes without chunks') if (!isElement(chunks[0])) { return [new DomBlock(chunks[0]), chunks.slice(1)] } const node = makeOpening(chunks[0]) const closing = </${node.tag}>

let remainder = chunks.slice(1)
let child = null
while (remainder && (remainder[0] !== closing)) {
[child, remainder] = makeNode(remainder)
node.children.push(child)
}

assert(remainder && (remainder[0] === closing),
Node with tag ${node.tag} not closed) return [node, remainder.slice(1)] }  and: const makeOpening = (chunk) => { const outer = chunk.match(TAG_AND_ATTR) const tag = outer[1] const attributes = [...outer[2].trim().matchAll(KEY_AND_VALUE)] .reduce((obj, [all, key, value]) => { obj[key] = value return obj }, {}) let Cls = null if (tag === 'col') { Cls = DomCol } else if (tag === 'row') { Cls = DomRow } assert(Cls !== null, Unrecognized tag name${tag})
return new Cls(attributes)
}


The next step is to define a generic class for CSS rules with a subclass for each type of rule. From highest precedence to lowest, the three types of rules we support identify specific nodes via their ID, classes of nodes via their class attribute, and types of nodes via their element name. We keep track of which rules take precedence over which through the simple expedient of numbering the classes:

export class CssRule {
constructor (order, selector, styles) {
this.order = order
this.selector = selector
this.styles = styles
}
}


An ID rule’s query selector is written as #name and matches HTML like <tag id="name">...</tag> (where tag is row or col):

export class IdRule extends CssRule {
constructor (selector, styles) {
assert(selector.startsWith('#') && (selector.length > 1),
ID rule ${selector} must start with # and have a selector) super(IdRule.ORDER, selector.slice(1), styles) } match (node) { return ('attributes' in node) && ('id' in node.attributes) && (node.attributes.id === this.selector) } } IdRule.ORDER = 0  A class rule’s query selector is written as .kind and matches HTML like <tag class="kind">...</tag>. Unlike real CSS, we only allow one class per node: export class ClassRule extends CssRule { constructor (selector, styles) { assert(selector.startsWith('.') && (selector.length > 1), Class rule${selector} must start with . and have a selector)
super(ClassRule.ORDER, selector.slice(1), styles)
}

match (node) {
return ('attributes' in node) &&
('class' in node.attributes) &&
(node.attributes.class === this.selector)
}
}
ClassRule.ORDER = 1


Finally, tag rules just have the name of the type of node they apply to without any punctuation:

export class TagRule extends CssRule {
constructor (selector, styles) {
super(TagRule.ORDER, selector, styles)
}

match (node) {
return this.selector === node.tag
}
}
TagRule.ORDER = 2


We could build yet another parser to read a subset of CSS and convert it to objects, but this chapter is long enough, so we will write our rules as JSON:

{
'row': { width: 20 },
'.kind': { width: 5 },
'#name': { height: 10 }
}


and build a class that converts this representation to a set of objects:

export class CssRuleSet {
constructor (json, mergeDefaults = true) {
this.rules = this.jsonToRules(json)
}

jsonToRules (json) {
return Object.keys(json).map(selector => {
assert((typeof selector === 'string') && (selector.length > 0),
'Require non-empty string as selector')
if (selector.startsWith('#')) {
return new IdRule(selector, json[selector])
}
if (selector.startsWith('.')) {
return new ClassRule(selector, json[selector])
}
return new TagRule(selector, json[selector])
})
}

findRules (node) {
const matches = this.rules.filter(rule => rule.match(node))
const sorted = matches.sort((left, right) => left.order - right.order)
return sorted
}
}


Our CSS ruleset class also has a method for finding the rules for a given DOM node. This method relies on the precedence values we defined for our classes in order to sort them so that we can find the most specific.

Here’s our final set of tests:

  it('styles a tree of nodes with multiple rules', async () => {
const html = [
'<col id="name">',
'<row class="kind">first\nsecond</row>',
'<row>third\nfourth</row>',
'</col>'
]
const dom = parseHTML(html.join(''))
const rules = new CssRuleSet({
'.kind': { height: 3 },
'#name': { height: 5 },
row: { width: 10 }
})
dom.findRules(rules)
assert.deepStrictEqual(dom.rules, [
new IdRule('#name', { height: 5 })
])
assert.deepStrictEqual(dom.children[0].rules, [
new ClassRule('.kind', { height: 3 }),
new TagRule('row', { width: 10 })
])
assert.deepStrictEqual(dom.children[1].rules, [
new TagRule('row', { width: 10 })
])
})


If we were going on, we would override the cells’ getWidth and getHeight methods to pay attention to styles. We would also decide what to do with cells that don’t have any styles defined: use a default, flag it as an error, or make a choice based on the contents of the child nodes. We will explore these possibilities in the exercises.

### Where it all started

This chapter’s topic was one of the seeds from which this entire book grew (the other being debuggers discussed in Chapter 20). After struggling with CSS for several years, I began wondering whether it really had to be so complicated. That question led to others, which eventually led to all of this. The moral is, be careful what you ask.

## Section 11.7: Exercises

### Refactoring the node classes

Refactor the classes used to represent blocks, rows, and columns so that:

1. They all derive from a common parent.

2. All common behavior is defined in that parent (if only with placeholder methods).

### Handling rule conflicts

Modify the rule lookup mechanism so that if two conflicting rules are defined, the one that is defined second takes precedence. For example, if there are two definitions for row.bold, whichever comes last in the JSON representation of the CSS wins.

### Handling arbitrary tags

Modify the existing code to handle arbitrary HTML elements.

1. The parser should recognize <anyTag>...</anyTag>.

2. Instead of separate classes for rows and columns, there should be one class Node whose tag attribute identifies its type.

### Recycling nodes

Modify the wrapping code so that new rows and columns are only created if needed. For example, if a row of width 10 contains a text node with the string “fits”, a new row and column are not inserted.

### Rendering a clear background

Modify the rendering code so that only the text in block nodes is shown, i.e., so that the empty space in rows and columns is rendered as spaces.

### Clipping text

1. Modify the wrapping and rendering so that if a block of text is too wide for the available space the extra characters are clipped. For example, if a column of width 5 contains a line “unfittable”, only “unfit” appears.

2. Extend your solution to break lines on spaces as needed in order to avoid clipping.

### Bidirectional rendering

Modify the existing software to do either left-to-right or right-to-left rendering upon request.

### Equal sizing

Modify the existing code to support elastic columns, i.e., so that all of the columns in a row are automatically sized to have the same width. If the number of columns does not divide evenly into the width of the row, allocate the extra space as equally as possible from left to right.

Modify the existing code so that:

1. Authors can define a padding attribute for row and column elements.

2. When the node is rendered, that many blank spaces are added on all four sides of the contents.

For example, the HTML <row>text</row> would render as:

+------+
|      |
| text |
|      |
+------+


where the lines show the outer border of the rendering.

### Drawing borders

1. Modify the existing code so that elements may specify border: true or border: false (with the latter being the default). If an element’s border property is true, it is drawn with a dashed border. For example, if the border property of row is true, then <row>text</row> is rendered as:

+----+
|text|
+----+

2. Extend your solution so that if two adjacent cells both have borders, only a single border is drawn. For example, if the border property of col is true, then:

<row><col>left</col><col>right</col></row>


is rendered as:

+----+-----+
|left|right|
+----+-----+