In this episode of reinventing the wheel, I will show how to write a layout engine from scratch in TypeScript. The goal is to achieve something closely resembling Yoga by Facebook.
But why
Maybe before we start, it's worth answering this simple question. Putting aside the problem of whether or not we should be writing our own layout engine, when would we need one in the first place?
The layout engine is practical when we need to orchestrate views around the screen. Which usually means that we either don't have one at hand or need to achieve some specific behavior. Examples: GPU APIs like WebGL, and WebGPU, where there are no higher level APIs provided, or React Native, where the CSS-like flexbox layout is used to achieve cross-platform consistency.
Prior art
As already mentioned, there's Yoga by Facebook, mainly known for being used in React Native, but for example, layout engine in Unity uses it as well (Documentation – The Layout Engine). It is written in C++. Up until recently hasn't seen much development, but it changed with the addition of gap (PR #1116).
There is also Stretch, written in Rust by Emil Sjölander, a key contributor to Yoga between 2016 and 2018. Unfortunately hasn't seen new commits in the past 3 years.
Another important mention is Taffy. Also written in Rust. Started as a fork of Stretch (source) Implements block, flexbox and grid layout algorithms, making it the most feature-rich layout engine I know of. Used in Dioxus and Bevy engine.
Google's official Android flexbox layout implementation: FlexboxLayout. Has support for most properties, but doesn't mention for example gap.
NativeScript's has a TypeScript-based flexbox algorithm for iOS UIKit: source.
Even though nowadays it's not a problem to run other compiled languages code in WASM (in fact, Satori from Vercel is running Yoga using asm.js and it also supports WASM loading), it would still be a bit simpler and easier to use a native JavaScript implementation.
Another aspect where we can be looking for some improvements is code size. Yoga implementation is 8280 lines of code (find . -name "*.h" -o -name "*.cpp" | xargs wc -l inside yoga/yoga directory of the repository). I am not suggesting that all this code is not necessary. Actually, I have all reasons to believe that this difference to what we are going to create is what makes Yoga a production-grade product. But also it gives us plenty of room for simplifications.
Requirements
I will outline a list of requirements I have in mind. A layout engine can be something truly simple or as complex as a CSS layout with multiple modes that can coexist. It's important to decide where we draw the line.
- We want to implement the flexbox layout. We are not interested in other CSS modes; we do not plan to support
gridorfloat. - Styles are not cascading, i.e., each element has its own style and does not inherit from its parent or propagate to its children. This is the same as in React Native.
- The user provides the style of each element as an object which uses predefined TypeScript types (also the same as in React Native).
- The user declares a tree of components using JSX (or equivalent nested function calls, which I will use; also same as in…).
- Width or height can be expressed either as a number (pixels) or
${number}%(percentage). top,left,right, andbottombehave the same way as in Yoga, which might be slightly different to CSS:- If the view is positioned
absolutely, those properties are used to define its position relative to the parent view. - If the view is
relative, an offset is calculated from the resolved layout position and then applied to the view, without affecting sibling views. - If
widthis not defined and bothleftandrightare, then the element will stretch to fill the space between the two offsets. The same applies toheightandtop/bottom.
- If the view is positioned
- For now, we are not going deep into flex calculations. We will calculate available space inside a parent and then use the
flexvalues of children to decide how to divide it.flexShrinkandflexGrowcan be added later on.
The concept
What exactly does a layout engine do? The way I see it, the layout engine takes a tree of elements with their user-applied styling and returns a copy tree with absolute positions and sizes resolved for each element.
The biggest challenge involves dynamic calculations. Let's imagine a view somewhere in the middle of the layout tree. It has a width of 100% and a left of 10. How do we calculate its width? We need to know the width of its parent, but we don't know it yet, because we are still in the middle of the tree. We need to go up the tree, calculate the width of the parent, and then go back down to the view and calculate its width. Then we know how much space we have available for children, and we can go down the tree and calculate their sizes.
This sounds like a recursive process, right? Thankfully, it is possible to resolve it in just three passes of the tree. I will explain that in the next section.
As we are here I'd like to mention that this is possible thanks to the simplification of the layout we are using here. If conforming to the W3C specification (and supporting min/max sizes), it would be 1 to N passes (source).
It's also worth noting that for some elements it's possible to do it in a single pass (idea) (implementation in Taffy).
Traversing happens in level order, i.e. we go to the root, then all children of the root, then all children of those children etc. We can do it by using a queue. We visit a node, add all its children to the queue, and then visit the next node in the queue. This way we will visit all nodes in level order.
Three passes
So how exactly do we resolve the layout in a finite number of passes? Here is the algorithm I am going to use:
- In the first pass, I traverse the tree in level order top-down and generate a queue for the next pass.
- In the second pass, bottom-up, I resolve the automatic size of elements that wrap their children (usually text nodes, their parents, parents of those parents and all the way up to the root). This indeed sounds like something that can be done in one go if we start from the bottom of the tree. In many UIs, there are very few nodes with user-defined
widthandheight, but actually all the text nodes have implicitly defined size. - In the third pass, top-down again, I resolve all flex values, and apply
top,left,right,bottomproperties.alignSelf, sizes using percentage,justifyContent,alignItems. At this point we have all the information about fixed sizes, user-defined or dictated by text nodes, and we can calculate the available space for automatically-sized elements.
And this is pretty much it.
Basics
I will be dealing with trees a lot, so I will need a tree class. Here is a simple implementation:
export class Tree<T> {
next: Tree<T> | null = null;
prev: Tree<T> | null = null;
firstChild: Tree<T> | null = null;
lastChild: Tree<T> | null = null;
parent: Tree<T> | null = null;
constructor(public readonly value: T) {
this.next = null;
this.prev = null;
this.firstChild = null;
this.lastChild = null;
this.parent = null;
}
addChild(node: Tree<T>): Tree<T> {
node.parent = this;
if (this.firstChild === null) {
this.firstChild = node;
this.lastChild = node;
} else {
if (this.lastChild === null) {
throw new Error("Last child must be set.");
}
node.prev = this.lastChild;
this.lastChild.next = node;
this.lastChild = node;
}
return node;
}
}
As you can see it's very minimal, it only supports adding children, but that's all we need.
Also for tree traversal, I will be using a queue structure. Here's one:
interface QueueNode<T> {
data: T;
prev: QueueNode<T> | null;
next: QueueNode<T> | null;
}
export class Queue<T> {
private start: QueueNode<T> | null = null;
private end: QueueNode<T> | null = null;
private size = 0;
enqueue(value: T): void {
const node: QueueNode<T> = {
data: value,
next: null,
prev: null,
};
if (this.end) {
this.end.next = node;
node.prev = this.end;
} else {
this.start = node;
}
this.end = node;
this.size += 1;
}
dequeue(): T | null {
const node = this.start;
if (node === null) {
return null;
}
if (node.next) {
this.start = node.next;
} else {
this.start = null;
this.end = null;
}
this.size -= 1;
return node.data;
}
dequeueFront(): T | null {
const node = this.end;
if (node === null) {
return null;
}
if (node.prev) {
this.end = node.prev;
} else {
this.start = null;
this.end = null;
}
this.size -= 1;
return node.data;
}
isEmpty(): boolean {
return this.size === 0;
}
}
Types
This is a list of all properties that we are going to support. Note that we are not interested in styling capabilities for now, so I will skip border radius and so on.
type ViewStyle = {
width?: number | `${number}%` | undefined;
height?: number | `${number}%` | undefined;
flexDirection?: "row" | "column";
justifyContent?:
| "flex-start"
| "center"
| "flex-end"
| "space-between"
| "space-around"
| "space-evenly";
alignItems?: "flex-start" | "center" | "flex-end" | "stretch";
alignSelf?: "flex-start" | "center" | "flex-end" | "stretch";
flex?: number;
position?: "absolute" | "relative";
gap?: number;
zIndex?: number;
display?: "flex" | "none";
top?: number;
left?: number;
right?: number;
bottom?: number;
padding?: number;
paddingHorizontal?: number;
paddingVertical?: number;
paddingLeft?: number;
paddingRight?: number;
paddingTop?: number;
paddingBottom?: number;
margin?: number;
marginHorizontal?: number;
marginVertical?: number;
marginLeft?: number;
marginRight?: number;
marginTop?: number;
marginBottom?: number;
backgroundColor?: string; // The only value not related to layout.
};
Similar to React Native, I am adding aliases for horizontal and vertical padding and margin.
When resolving padding or margin values, the priority goes (in reverse order):
marginmarginHorizontal/marginVerticalmarginLeft/marginRight/marginTop/marginBottom
So view with styles:
{
margin: 10,
marginVertical: 20,
marginTop: 30,
}
will resolve to:
{
marginLeft: 10,
marginRight: 10,
marginTop: 30,
marginBottom: 20,
}
Text
Although the text itself is not a concern of a layout engine, it will be very handy to have some basic text support. Also, text is probably the most common case which surfaces the need for dynamic sizing of parents wrapping their children. It is so common to have buttons which have sizes based on the text inside it plus some defined padding.
Type for text style, much simpler than the ViewStyle:
type TextStyle = {
text: string;
fontSize: number;
color: string;
};
Renderer
To be able to see results of the layout engine, we need some kind of renderer. I will use HTML Canvas API for this.
import { Queue } from "./Queue";
import { Tree } from "./Tree";
import type { FixedView } from "./types";
const canvas = document.createElement("canvas");
export const ctx = canvas.getContext("2d");
canvas.width = window.innerWidth * window.devicePixelRatio;
canvas.height = window.innerHeight * window.devicePixelRatio;
canvas.setAttribute("style", "display: block");
document.body.appendChild(canvas);
export function renderToCanvas(node: Tree<FixedView>) {
if (ctx === null) {
throw new Error("Context should not be null.");
}
// Of course can be other color / you can make it customizable /
// you can skip this part.
ctx.fillStyle = "#000000";
ctx.fillRect(0, 0, canvas.width, canvas.height);
const list: FixedView[] = [];
// Traverse the tree in DFS order to respect local order of
// components (unlike in level order traversal that will be used
// for resolving positions and sizes of elements of the tree).
// This allows for zIndex to properly work.
const queue = new Queue<Tree<FixedView>>();
queue.enqueue(node);
while (!queue.isEmpty()) {
const node = queue.dequeueFront();
if (node === null) {
throw new Error("Node should not be null.");
}
list.push(node.value);
let p = node.lastChild;
while (p) {
if (p.value.input.display === "none") {
p = p.prev;
continue;
}
queue.enqueue(p);
p = p.prev;
}
}
// Respect zIndex.
list.sort((a, b) => a.zIndex - b.zIndex);
// The actual rendering happens here.
for (const view of list) {
if ("text" in view.input) {
ctx.font = view.input.fontSize + "px sans-serif";
ctx.fillStyle = view.input.color;
// Because by default in Canvas API Y is the baseline of the
// text, we need to calculate the height of the text and then
// offset it by that amount.
const metrics = ctx.measureText(view.input.text);
const height =
metrics.actualBoundingBoxAscent + metrics.actualBoundingBoxDescent;
ctx.fillText(view.input.text, view.x, view.y + height);
} else if (view.backgroundColor !== "transparent") {
ctx.fillStyle = view.backgroundColor;
ctx.fillRect(view.x, view.y, view.width, view.height);
}
}
}
Now let's put together all the code we have so far and test that it works. You can play with the code inside or press Open Sandbox to run it in full editor in a new tab.
As you can see, nesting children currently does not do anything special. This will the be job of the layout engine to read input styles and apply changes to x, y, width and height properties.
Layout calculation
NOTETo save precious screen space from repetitive code, I will be omitting some straightforward parts of the code i.e. if there is some calculation for
flexDirection: "column"and the one forrowlook identical but with flipped identifiers, I will omit that and leaveTODOthere. Those TODOs are not meant to be filled in some future versions, they are crucial for layout calculation to work. You can either figure them out yourself or just find them in the interactive playground at the bottom of the post.
Now the challenge is to write a function, let's call it calculate(), which will take in a tree of views (with styles) and return the same tree but with resolved absolute positions and sizes.
For that, I will use a type that briefly made a presence in the interactive example above:
type FixedView = {
input: ViewStyle | TextStyle;
x: number;
y: number;
width: number;
height: number;
zIndex: number;
backgroundColor: string;
};
Now back to the three-pass rendering, the structure can look roughly like this.
First pass
It will actually mostly just serve to prepare the queues for next passes.
export function calculate(tree: Tree<FixedView>) {
const firstPass = new Queue<Tree<FixedView>>();
const secondPass = new Queue<Tree<FixedView>>();
const forwardQueue = new Queue<Tree<FixedView>>();
// Traverse node tree in level order and generate the reverse
// queue. In this pass we basically just prepare the queues that
// we will use in later passes.
firstPass.enqueue(root);
while (!firstPass.isEmpty()) {
const element = firstPass.dequeue();
if (element === null) {
throw new Error("Empty queue.");
}
let p = element.firstChild;
while (p !== null) {
firstPass.enqueue(p);
secondPass.enqueue(p);
p = p.next;
}
}
// ...
Second pass
Second phase is for calculating sizes of parents that are dictated by children: like width and height of views wrapping text (including paddings and margins).
// ...
while (!secondPass.isEmpty()) {
const element = secondPass.dequeueFront();
if (element === null) {
throw new Error("Empty queue.");
}
// Enqueue for the third pass.
forwardQueue.enqueue(element);
// TODO: fill with implementation.
}
// ...
Calculating size of parents
As we are traversing tree from the bottom to the top, we can resolve values of widths and heights of parents that didn't have them set explicitly.
const input = element.value.input as ResolvedInput;
// If input contains fixed value for width/height, we can apply it
// now.
if (typeof input.width === "number") {
element.value.width = input.width;
}
if (typeof input.height === "number") {
element.value.height = input.height;
}
if (input.width === undefined) {
let childrenCount = 0;
let p = element.firstChild;
while (p) {
const childInput = p.value.input as ResolvedInput;
// The parent doesn't have width set, but maybe the child has.
if (p.value.width || typeof childInput.width === "number") {
// The parent can grow horizontall only if it has
// "flexDirection" set to "row" and given child has "position"
// set to "relative" (otherwise it wouldn't take part in the
// layout calculation with "absolute" position).
if (input.flexDirection === "row" && childInput.position === "relative") {
// There is a helper function for resolving values of
// margins and paddings, so at this point "marginLeft" is
// the final value that takes into account "margin",
// "marginHorizontal" and "marginLeft", in order of
// priority, if set.
element.value.width +=
p.value.width + childInput.marginLeft + childInput.marginRight;
}
// Alternatively, the parent with direction "column" will have
// width equal to the widest child.
if (
input.flexDirection === "column" &&
childInput.position === "relative"
) {
element.value.width = Math.max(
element.value.width,
p.value.width + childInput.marginLeft + childInput.marginRight,
);
}
}
if (p.value.input.position === "relative") {
childrenCount += 1;
}
p = p.next;
}
// After expanding size by the value of children, parent's padding
// and gap values need to be added.
element.value.width +=
input.paddingLeft +
input.paddingRight +
(input.flexDirection === "row" ? (childrenCount - 1) * input.gap : 0);
}
And everything analogously for height (remember to flip flexDirections as well).
Third pass
In this phase we will:
- Apply
top,left,bottom,right. - Calculate
alignSelf. - Calculate available space for
flexexpansion. - Apply
justifyContentandalignItems.
// ...
// Final traverse.
while (!forwardQueue.isEmpty()) {
const element = forwardQueue.dequeueFront();
if (element === null) {
throw new Error("Empty queue.");
}
}
}
Resolving flex properties
A small util function to resolve percentage values. I didn't want to add regex validation to avoid slowing it down. If it's meant to break, it will explode in the next line anyway. But feel free to expand your function if you want to.
export function toPercentage(value: string): number {
if (!value.endsWith("%")) {
throw new Error("Value must be a percentage.");
}
return Number(value.replace("%", "")) / 100;
}
(drop it somewhere in the module scope or in a separate file).
Now, onto calculating flex values. Some setup first:
let totalFlex = 0;
let childrenCount = 0;
const parent = element.parent;
// Undefined is ruled out by the previous pass.
const parentWidth = parent?.value.width ?? 0;
const parentHeight = parent?.value.height ?? 0;
const input = element.value.input as ResolvedInput;
const parentInput = parent?.value.input as ResolvedInput;
if (input?.flex < 0) {
throw new Error("Flex cannot be negative.");
}
Now we will handle the logic mentioned before, that if width is not defined and left and right are, then they define how the element should be stretched (and analogously for height and top and bottom).
if (typeof input.width === "string") {
element.value.width = toPercentage(input.width) * parentWidth;
}
if (
input.left !== undefined &&
input.right !== undefined &&
input.width === undefined
) {
element.value.x = (parent?.value.x ?? 0) + input.left;
element.value.width = parentWidth - input.left - input.right;
} else if (input.left !== undefined) {
if (input.position === "absolute") {
element.value.x = (parent?.value.x ?? 0) + input.left;
} else {
element.value.x += input.left;
}
} else if (input.right !== undefined) {
if (input.position === "absolute") {
element.value.x =
(parent?.value.x ?? 0) + parentWidth - input.right - element.value.width;
} else {
element.value.x = (parent?.value.x ?? 0) - input.right;
}
} else if (input.position === "absolute") {
// If position is "absolute" but offsets are not specified, set
// position to parent's top left corner.
element.value.x = parent?.value.x ?? 0;
}
// TODO: same for the analogous directions.
Align self
As a reminder: alignSelf is a property that allows overriding parent's alignItems for the current element.
Until I wrote this renderer, I never really used it and I considered it as one of those weird CSS hacks that I have to google once a year and never bother to understand what they do. Now alignSelf: "stretch" is my go-to way of making the child stretch to the parent's size along the secondary axis.
// Apply align self.
if (element.value.input.position !== "absolute" && parent) {
if (parentInput.flexDirection === "row") {
if (input.alignSelf === "center") {
element.value.y =
element.value.y + element.value.height / 2 - element.value.height / 2;
}
if (input.alignSelf === "flex-end") {
element.value.y =
element.value.y +
parent.value.height -
element.value.height -
parentInput.paddingBottom -
parentInput.paddingTop;
}
if (input.alignSelf === "stretch") {
element.value.height =
parent.value.height -
parentInput.paddingBottom -
parentInput.paddingTop;
}
}
// TODO: same for direction "column".
}
Set percentage sizes
Set sizes for children that use percentages.
let p = element.firstChild;
while (p) {
if (typeof p.value.input.width === "string") {
p.value.width = toPercentage(p.value.input.width) * element.value.width;
}
if (typeof p.value.input.height === "string") {
p.value.height = toPercentage(p.value.input.height) * element.value.height;
}
p = p.next;
}
Set zIndex
Take zIndex from parent if not set on the element. This is the only property that actually propagates from parent to children in this model.
element.value.zIndex = input.zIndex ?? parent?.value.zIndex ?? 0;
Distribute available space
Now we will calculate how much space is available for flex children to expand. We will also count how many children are there and what is the total flex value.
let availableWidth = element.value.width;
let availableHeight = element.value.height;
// Count children and total flex value.
p = element.firstChild;
while (p) {
if (p.value.input.position === "relative") {
childrenCount += 1;
}
if (
input.flexDirection === "row" &&
p.value.input.flex === undefined &&
p.value.input.position === "relative"
) {
availableWidth -= p.value.width;
}
if (
input.flexDirection === "column" &&
p.value.input.flex === undefined &&
p.value.input.position === "relative"
) {
availableHeight -= p.value.height;
}
// Calculate how many views will be splitting the available space.
if (input.flexDirection === "row" && p.value.input.flex !== undefined) {
totalFlex += p.value.input.flex;
}
if (input.flexDirection === "column" && p.value.input.flex !== undefined) {
totalFlex += p.value.input.flex;
}
p = p.next;
}
availableWidth -=
input.paddingLeft +
input.paddingRight +
(input.flexDirection === "row" &&
input.justifyContent !== "space-between" &&
input.justifyContent !== "space-around" &&
input.justifyContent !== "space-evenly"
? (childrenCount - 1) * input.gap
: 0);
// TODO: analogously for "availableHeight".
// Apply sizes.
p = element.firstChild;
while (p) {
if (input.flexDirection === "row") {
if (
p.value.input.flex !== undefined &&
input.justifyContent !== "space-between" &&
input.justifyContent !== "space-evenly" &&
input.justifyContent !== "space-around"
) {
p.value.width = (p.value.input.flex / totalFlex) * availableWidth;
}
}
// TODO: same for direction "column".
p = p.next;
}
element.value.x += input.marginLeft;
element.value.y += input.marginTop;
// Determine positions.
let x = element.value.x + input.paddingLeft;
let y = element.value.y + input.paddingTop;
Justify content
There are a couple of cases to handle here.
Starting with a simple center and flex-end:
NOTEHandling
flex-startis not necessary as this is the default if no changes are made.
if (input.flexDirection === "row") {
if (input.justifyContent === "center") {
x += availableWidth / 2;
}
if (input.justifyContent === "flex-end") {
x += availableWidth;
}
}
Do the same for flexDirection: "column".
Now the overall similar but differing in details, space-between, space-around and space-evenly:
space-between, space-around and space-evenly essentially differ in how many elements are splitting the available space.
if (
input.justifyContent === "space-between" ||
input.justifyContent === "space-around" ||
input.justifyContent === "space-evenly"
) {
const count =
childrenCount +
(input.justifyContent === "space-between"
? -1
: input.justifyContent === "space-evenly"
? 1
: 0);
const horizontalGap = availableWidth / count;
const verticalGap = availableHeight / count;
p = element.firstChild;
while (p) {
p.value.x =
x +
(input.justifyContent === "space-between"
? 0
: input.justifyContent === "space-around"
? horizontalGap / 2
: horizontalGap);
p.value.y =
y +
(input.justifyContent === "space-between"
? 0
: input.justifyContent === "space-around"
? verticalGap / 2
: verticalGap);
if (input.flexDirection === "row") {
x += p.value.width + horizontalGap;
}
if (input.flexDirection === "column") {
y += p.value.height + verticalGap;
}
p = p.next;
}
} else {
p = element.firstChild;
while (p) {
if (
p.value.input.position === "absolute" ||
p.value.input.display === "none"
) {
p = p.next;
continue;
}
if (input.flexDirection === "row") {
p.value.x = x;
x += p.value.width;
x += input.gap;
} else {
p.value.x = x + p.value.x;
}
if (input.flexDirection === "column") {
p.value.y = y;
y += p.value.height;
y += input.gap;
} else {
p.value.y = y + p.value.y;
}
p = p.next;
}
}
Align items
Supported values are flex-start, center, flex-end and stretch.
p = element.firstChild;
while (p) {
if (p.value.input.position === "absolute") {
p = p.next;
continue;
}
if (input.flexDirection === "row") {
if (input.alignItems === "center") {
p.value.y =
element.value.y + element.value.height / 2 - p.value.height / 2;
}
if (input.alignItems === "flex-end") {
p.value.y =
element.value.y +
element.value.height -
p.value.height -
input.paddingBottom;
}
if (input.alignItems === "stretch" && p.value.input.height === undefined) {
p.value.height =
element.value.height - input.paddingTop - input.paddingBottom;
}
}
// TODO: same for direction "column".
p = p.next;
}
The end
Finally, we will round sizes to whole pixels to avoid aliasing issues.
element.value.x = Math.round(element.value.x);
element.value.y = Math.round(element.value.y);
element.value.width = Math.round(element.value.width);
element.value.height = Math.round(element.value.height);
Playground
This is the final, interactive example. If you manage to break anything – let me know on Twitter and I will fix it.
Next steps
What we ended up with is quite feature-complete and could be used to recreate many UIs that use Yoga. However, there are some (big) things missing that would be required to make it a fully viable alternative:
- Wrapping text – for now, the text is rendered as a single line. This requires taking into account line heights, and text alignment (left, center, right and justify).
- Scroll view – quite essential. Unfortunately, it's more complex and requires the layout engine to have 'opinions' about how the scrollbar should look and how it should handle mouse and keyboard events.
flexWrap,flexGrow,flexShrink. Quite likely the easiest of the mentioned, requiring just small adjustments to the existing code.
This, but as a library
If you are interested in taking this idea further, I once made a library you can check on GitHub. I don't maintain it as I don't really have daily use for it, but the code still might be useful!
Conclusions
I hope I convinced you that layout engines are not magic and it takes quite little code to implement one. Less than 600 lines of code to unlock almost all flexbox features.
Imagine what possibilities it brings. We are not limited anymore but what is usually a platform's responsibility. We don't need HTML, we don't need React Native. We can create our UIs, on any platform, with just a bunch of rendering primitives.
If you like the idea of making things from scratch, check out my other articles: Understanding React by Implementing It or Making Our Own Tiny Google Maps.
Special thanks to Jamie Birch for proofreading this article and providing valuable feedback!