NLayout Engine

Introduction

This document describes the process of writing the NLayout engine that executes layout for Delphi and how it works.

This part, the layout engine, has been the most difficult part of the Delphi project to date, executing layout with so many variables that interact in so many different ways depending on layout context and such.

The layout engine is in the nlayout module, which, obviously, handles the layout execution.

The Name

NLayout originally meant "New Layout", after the Java class I started writing it in, which was the 2nd version of the layout engine. The first being very primitive, just taking in a layout-direction (Either X or Y) and tiling elements in that direction.

Now, it means "Narcissine Layout", coming from the name Narcissus, because only a narcissist would believe they could mimic web layout standards competently. And clearly, that is what I am.

On top of that, this document describes the 4th version of the engine.

Terminology

Many of the terms here are borrowed from various W3C specifications (Listed in the sources section)

finite/definite size: A size, such as a width, or a height, that is set to an explicit value, such as 14px.
indefinite size: A size that is dependent on an element's child elements. In Delphi, this means any width or height set to auto.
UNSET: A numeric constant with a value of -1.0.
Screen: Delphi elements are displayed on a screen with a set size, think of this like a window on a computer.
Inner size: The content area of an element. Effectively, it's the size of an element, minus the border, padding and outline.
Main axis: The primary axis/direction along which flex items are laid out.
Cross axis: The axis that sits perpendicular to a flexbox container's main axis.
Starting content position: The position of a container where it's layout begins. This position is the container's position, offset by the border, outline and padding, using this formula:
$c_{x} = p_{x} + o_{l} + b_{l} + d_{l}$ $c_{y} = p_{y} - o_{t} - b_{t} - d_{t}$ Where the main variables are c = content starting position, p = element position, o = element outline, b = element border, d = element padding; and the subscripts are: x = Y Axis, y = X Axis, l = left side, t = top side

Layout passes

Layout is divided into 2 parts: Measurement (or rather, Setup) and Layout.

Measurement

This part involves measurement of items, but, because of how it's implemented, and how the functions perform, it may be more accurate to call this the "Setup" pass.

Before measurement can begin, we need a LayoutContext, this keeps track of a stack of Vector2fs (2D vectors, an X and a Y). This is a stack parentSizes. On top of this we also need 2 boolean stacks, a stack for determining if the width of an element is finite, and a stack for determining if the height of an element is finite. These 2 stacks will be used when calculating % lengths, as those can only resolve against finite sizes.

Once measurement begins, we start at the root element of the Layout tree and continue through in a depth first iteration.

At each element, we perform the following steps.

Style Calculation

This is a straight forward process of taking all the CSS values and computing them to actual numerical values. There isn't a lot to say about this step, so here's a link to where the style calculation happens (at time of writing): Link

Determine the current width and height of the layout box

This is done by checking if the node's size is equal to UNSET. If it is, we check if the current element's size is indefinite, if it is, set the node's size to be the size of the screen. If the size is definite, then we use that as the node's size.

Push current element state to LayoutContext

Take the inner size of the current box, and push it to the parentSizes stack. Then push the current width and height's definite vs indefinite state to the two boolean stacks.

Layout mode-dependent measurement

Here, the measurement process is handed over to either the Flow or Flexbox algorithm to complete the measurement and iterate over child nodes.

The processes these modes perform are documented in the following sections.

This, and the following step will repeat until the size of the element and/or it's child nodes stops changing, i.e. when the layout stabilizes.

Box size adjustment

If the node's width is set to an indefinite value, then use the width returned by the previous step. The same goes for the height of the element.

End

Pop the element's state from the parentSizes stack and the 2 boolean stacks, and return if the element's size changed from before the measurement call.

Regular Flow

Conceptually, Flow layout breaks the elements it has to lay out into lines of elements and displays all elements along each line. This section breaks down the steps of how elements are measured in Flow Layout.

Line Division

This step divides elements into lines. Iterate over all elements in the Flow container, if an element has display: block;, place it onto its own line. If the element has display: inline-block;, move to the next line. If the current element can not fit onto the current line, and the current line is not empty, move to the next line.

Note that, when checking if an element can fit on a line, the horizontal left and right margins are included in the check. Depending on the display value, the margins used may differ. For inline elements, only margin-inline-start and margin-inline-end values are used. For others, normal margins are used.

Vertical Margins calculation

Each line has its own top and bottom margins, these margins are created out of the margins of all elements on that line.

Iterate over each item in each line. If vertical margins apply to that item (non display: inline; items). Then use those as the base top and bottom margins.

Next, we determine the actual top and bottom margins of that item. To do that, we get the vertical-align value of the item, and we calculate the amount of free room that item has to move. This is a simply done by subtracting the item's height from the line's height.

To get the actual effective top and bottom margins, we perform the following operation, depending on the aforementioned vertical-align value:

super

Super means item should be displayed as if it was ^{Super text.} Meaning it needs to be halfway above the line's top edge. In order for this to also look halfway decent, we need to increase the top margin by half of the element's height. (The same amount that's poking over the top)

The bottom margin is calculated by subtracting half the element's height from the base bottom margin, and subtracting the free vertical space from it as well.

top

Effective top margin is just the base top margin, while the bottom margin has the free vertical space subtracted from it.

The reasoning for this is because the bottom of the element won't touch the bottom of the line, so the effective margin has to compensate for how much free space is between the bottom of the line, and the bottom of the element.

middle

Both top and bottom margins have half the free vertical space subtracted from them.

bottom

This is the inverse of the top one. In this one, the bottom margin remains unchanged, and the top margin has the free vertical height subtracted from it.

sub

The inverse of super, the top margin has both the free vertical space subtracted from it and half the element's height, while the bottom margin has half the item's height added to it.

With these effective top and bottom margins available, we change the line's top and bottom margins if and only if, the effective margins are greater than the existing margins.

Auto margin calculation

This section is a simple one, we apply margin-left: auto and margin-right: auto values.

This is done, by again, iterating over each line. Auto margin calculation is only done on lines with 1 item with display: block;.

First, set the element's left margin to the difference between the available width and the item's width. Then, if both left and right margins are set to auto, halve the left margin.

FlexBox

Gather Flex Items

Very simple step where all child nodes of the flexbox container are gathered into FlexItems. Children that have display: none; are skipped.

During gathering, we also store the CSS order value, if it's set. If not, use the node's domIndex as the order. We also store the flex-grow and flex-shrink values. If the node has a set align-self, store that, otherwise, use the container's align-items as the item's self alignment value.

Finally, after all items have been collected, sort them by their stored order value.

Calculate base sizes

This step iterates over all flex items, as such, this section describes operations performed on all flex items.

Sidenote: I don't know if this step actually follows the W3C spec, but who cares.

Measure the current item (This is done mostly to cause a recursive measurement call to all the flex item's descendants.) Then, if a flex-basis is set on the item, we use that as the base main size, otherwise use the measured or set size of the item as it's base size.

Calculate main sizes

Oh boy...

First, sum up the main sizes of all flex items and include the relevant gap in the sum (For row, this is column-gap, otherwise use row-gap.)

If the summed size is greater than the available main size, then either wrapping has to occur, or items have to be shrunk, depending on if wrapping is allowed (Set by the flex-wrap CSS property)

If wrapping is not allowed

Since wrapping is not allowed, elements must be shrunk. To find out which elements need to be shrunk, and how much, we do the following:

Sum up all the positive flex-shrink values of all flex items
If the sum is positive, shrink the items with a positive shrink value, using this formula: $M = B - (\frac{S - A}{F}) \cdot f$
In that formula: M = item's main size, B = item's base size, S = summed size of all items, A = available main size, F summed flex shrink value, f is the item's own flex shrink value
That looks complex, but it literally just means, shrink it by how much it's configured to be shrunk (It's also simpler in the code)
If the sum is not positive, all elements must be shrunk equally, so we use this formula:
$M = B - (\frac{S - A}{I})$
For the most part, the variables are the same as in the formula before this one, except for I = amount of flex items in the container.
Finally, regardless of how the shrinking was performed, all the items are collected into a single FlexLine.

If wrapping is allowed

Divide the Flex items into lines, this is simply done by summing up the main size of the items as you go and checking when it becomes greater than the available main size. When it does become greater, move to the next line.

At the end, if flex-wrap is set to wrap-reverse, invert the order of the lines.

After this, flex-grow is applied to all lines (See the Flex Growth Application section)

If the sum of all item's is less than the available main size

Place all flex items onto one line, and then apply flex growth (See the Flex Growth Application section)

Flex Growth Application

This isn't a step, more of a function that can be called.

The handling of flex growth is similar to how flex-shrink is handled, described in the previous section. This function is also only ran if the available main size is greater than the sum of the main sizes of the items passed to it.

First, all positive flex-grow values are summed up.
If the summed value is not greater than 0, the function stops.
Otherwise, the following formula is applied to all flex items that were passed to the function with a positive flex growth value:
$M = B + (\frac{A - S}{G}) \cdot g$
In that formula: M = item's main size, B = item's base size, S = summed size of all items, A = available main size, G = summed flex grow value, g = the item's own flex grow value

Calculate cross sizes

Cross size calculation begins by getting the value of the gap that is applied along the cross axis of the container. For row flex containers, this is row-gap, otherwise, it's column-gap.

Then we iterate over each item in each line, and take that item's cross size and compare it to the line's cross size. If the item's cross size is larger, the line's cross size becomes the item's cross size.

After this, the line's items are iterated over again, to apply stretch item alignment. This is simply done by checking if the effective alignment value is stretch for an item, and if it is, set the item's cross size to the line's cross size.

Finally add up all the lines cross sizes (+ the cross gap) to get the flex box container's used cross size.

Apply sizes

This is simply iterating over each item in each line, and calling the item's algorithm-specific measurement function.

This step is done, because after the previous 2 steps, the element's size may have changed from when it was originally measured, meaning any child nodes of the item may now be incorrectly sized or laid out.

Layout

Layout is performed by Layout algorithms, each executing it differently. At time of writing only Flow and FlexBox are supported.

Regular Flow

First, we create 2 Vector2f variables: pos and offset. The former is the content starting position of the container element. The offset is initialized to 0, 0.

Iterate over each line. First, add the line's top margin to the offset's y-axis. Then begin iterating over each item in the line.

If the item has any left-side margin's, add it to the offset's x-axis. Now we set the item's x position to $p_{x} + o_{x}$ and the y position to $p_{y} - o_{y}$

And here we have to also account for a vertical-align value. We get the amount of free vertical space in the line, by subtracting the item's height from the line's height, we'll store this in f. And finally, we store the item's height in h. In the following expressions, $i_{y}$ is the item's y position

super: The item has already been moved to the top of the line, so we need to move it up by half the size of the item.
$i_{y} = i_{y} + (\frac{h}{2})$
top: Since, we've already aligned the item to the line's top line, so nothing is done.
middle: To move the element to the middle, we need to offset it by half the amount of free space left on the line.
$i_{y} = i_{y} - \frac{f}{2}$
bottom: To move to the bottom of the line, we move the element down by the amount of free space available.
$i_{y} = i_{y} - f$
sub: Sub alignment means it has to be below the line, so we move it down by the amount of available vertical space and by half the item's own height.
$i_{y} = i_{y} - (f + \frac{h}{2})$

Finally, you add the item's width and it's right-side margin to the offset's x-axis. And after all items in a line have been laid out, we add the line's own height and bottom margin to the offset's y-margin. Also, on line breaks, we zero the offset's x-axis.

FlexBox

With all due respect, I'm not describing this. This is way too messy, so here's a link to the implementation (Correct at time of writing): FlexLayoutBox.layout()

NLayout Engine

Table Of Contents

Introduction

The Name

Terminology

Layout passes

Measurement

Regular Flow

Line Division

Vertical Margins calculation

Auto margin calculation

FlexBox

Gather Flex Items

Calculate base sizes

Calculate main sizes

Flex Growth Application

Calculate cross sizes

Apply sizes

Layout

Regular Flow

FlexBox

Sources / Docs / Tutorials