Layout Engine

Figuring out what goes where in a web page

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 piece of software took some text and some layout instructions and decided where each character and image was going to go. A tool that does that is called a layout engine, and in this chapter we will build a small one 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. To keep things simple we will create our own classes for 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.

How can we size rows and columns?

Let's start on easy mode without margins, padding, line-wrapping, or other complications. We define a cell as a row, a column, or a block. A block has a fixed width and height (hence the name):

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

  getWidth () {
    return this.width
  }

  getHeight () {
    return this.height
  }
}

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
  }
}

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
  }
}

We represent a tree of cells as a collection of nested objects and recalculate the width and height of each cell each time they're needed. This is simple but inefficient: we could calculate both width and height at the same time and cache calculated values to avoid recalculation, but it's called "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 (5ms)

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 just place it there. If the cell is a row, on the other hand, we gets 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. 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
    ]
  }
}

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]
      ]
    )
  })

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

> 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 (6ms)

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 ().

Making our pretend screen is a simple matter of creating an array of arrays:

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 'a', while its children will be '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:

import {
  PlacedBlock,
  PlacedCol,
  PlacedRow
} from './placed.js'

// <keep>
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
    }
  }
}
// </keep>

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 this code for real, we would go back and create a class called Cell with this render method, then derive our original easy-mode Block, Row, and Col classes from that.

Once we have rendering in place, our simpler tests are a little easier to read, though we still had to draw things on graph 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')
    )
  })

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 this to our layout engine, suppose we fix the width of a row. (For now, we will assume all of the row's children are less than or equal to this width; we will look at what happens when they're not in the exercises.) 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.

Our layout engine manages this 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 row is replaced with a row containing a single column with one or more rows, each of which is one "line" of wrapped cells (). 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, which should produce the same answers as before, 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 (9ms)

What subset of CSS will we support?

It's now time to do something a little more realistic. Our final subset of HTML includes 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 while the length of the longest line determines its width.

Rows and columns can have attributes just as they can in real HTML. Each attribute must have a single quoted value, and rows no longer take a fixed width: our little subset of CSS will handle that. 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 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

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)]
}

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 then types of nodes via their element name ().

We keep track of these precedences 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 has a DOM selector of the form #name and matches HTML of the form <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 has a DOM selector of the form .kind and matches HTML of the form <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 are identified by having just the name of the type of node they apply to:

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 write yet another parser to read a subset of CSS and convert it to objects, but it's simpler to store the CSS as JSON:

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
  }
}

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 to go on, we would override the cells' getWidth and getHeight methods to pay attention to styles. But what about nodes that don't have a style? We could use a default, base it on the needs of the child nodes, or flag it as an error. We will explore these possibilities in the exercises.

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.

Padding elements

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.

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

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, <row><col>left</col><col>right</col></row> is rendered as:

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