Perhaps the most complex task a visual browser has to perform (certainly the one which is taking the most effort from me) is deciding where to place everything onscreen! In my hypothetical hardware-browser I designed a domain-specific programming language to simplify this, with specialized hardware for it to run on. Where we specify formulas to convert the CSS units, keywords, strings, functions, etc into drawing operations for a Compositing Co-Processor. A topological sort & implicit loops would help a lot!
Psuedocode in that DSL is provided throughout to make these concepts more concrete, even if it’d rely heavily on compiler-intelligence. And to tie these discussions into the broader hypothetical.
CSS Box Model
To start the CSS Box Model defines padding, margins, & borders whose widths need to be summed into these layout computations. There’s various units for those lengths, whose conversion might be sourced from parent properties or the selected font. These produce content, padding, border, & margin boxes any of which might be fed into the output. With the area between the padding & border boxes being split into 4 trapagons to optionally include in the output with specified colour & style.
Then we have the box-sizing: border-box property to resurrect old Internet Explorer which wasn’t standards-compliant at the time. Now some webdevs want it, & we need to add conditions to handle it!
Box Model pseudocode
*width : $box.content.width.$0; # The "*" captures min/max variants.
*height : $box.content.height.$0;
box-sizing.border-box { width : $box.margin.width; height : $box.margin.height }
width > max-width { width = max-width } height > max-height { height = max-height }
width < min-width { width = min-width } height < min-height { height = min-height }
$box.border.top = $box.margin.top + margin-top; $box.border.left = $box.margin.left + margin-left;
$box.padding.top = $box.border.top + border-top-width; $box.padding.left = $box.border.left + border-left-width;
$box.content.top = $box.padding.top + padding-top; $box.content.left = $box.padding.left + padding-left;
$box.content.bottom = $box.content.top + $box.content.height; $box.content.right = $box.content.left + $box.content.width;
$box.padding.bottom = $box.content.bottom + padding-bottom; $box.padding.right = $box.content.right + padding-right;
$box.border.bottom = $box.padding.bottom + border-bottom-width; $box.border.right = $box.padding.right + border-right-width;
$box.margin.bottom = $box.border.bottom + margin-bottom; $box.margin.right = $box.border.right + margin-right;
width, min-width, max-width, height, min-height, max-height,
margin-top, margin-right, margin-bottom, margin-left,
border-top-width, border-right-width, border-bottom-width, border-left-width,
padding-top, padding-right, padding-bottom, padding-left : :length;
:length#px = $scale;
:length#em = font-size;
:length#rem = 1^rem;
:length#rem = font-size; # For root
:length#% = 0.01em;
:length#ch = $font['GPOS']['0'].advance-width;
:length#vh = 1^vh;
:length#vh = $box.margin.width; # For root
:length#vh > :length#vw { :length#vmax = 1vh }
:length#vmax = 1vw;
*width#% = ^$0-width/100;
*height#% = ^$0-height/100;
# etc...
** { $0 = ^$0; $0 = initial } # If we refer to a property during its own computation, refer to parent's value instead!
Block Layout
The most basic layout formula is block. Once runs of inlines have been extracted to be handled using a different formula (Which deserves its own page!) is fairly straightforward. Until you meet multilingual people, or the Japanese. Or mix it with other layouts. Usually computing width: auto involves traversing children to find the max-width. height: auto is a running-sum.
The caveats there relates to the fact that some languages are traditionally written vertically, though usually those can also be written horizontally. Also there’s a couple diagonal languages few computing systems yet support. Final width is computed by filling all the parent’s width it can & clamping it to the min/max width. Which also need to be computed. Height is clamped to min & max values as well.
Inline-runs (for latinate languages, amongst others) compute height from width.
Percentage-sizing was surprisingly the tricky bit about implementing this in that if the parent is auto-sized based widths based on the widths of its children… That’s a cyclic dependency conflict! I specifically mentioned that I’d include syntax for handling this in the DSL I designed for implementing CSS.
Also visually-contiguous margins need to be collapsed into the larger one…
Block pseudocode
# NOTE: The magic happens upon laying out inline text.
display.block {
*width.auto = @[$0-width > ~$0-width].width;
width.auto = ^width # Fill available space
*height.auto = @{ $height = $0-height { $box.margin.top = ~$box.margin.bottom } }.$box.margin.height;
}
margin-top >= ~margin-bottom { ~margin-bottom = 0 }
margin-top < ~margin-bottom { margin-top = 0 }
Grid Layout & Tables
An advantage of 2D displays is that we can align fragments of text along both dimensions to clearly communicate complex information, making the relationships between them visible at a glance. On the web this is the concept behind <table>s & more recently CSS3 Grids! This involves maintaining a per-axis list of the size of each row/column to align all the children to, sharing the same logic for both axes.
Preprocessing CSS3 Grids to determine where these grid cells should land involves resolving names, allocating implicit locations along the specified axis, making implicit tracks explicit, etc. For
After that each axis is computed by sizing each column to the maximum ideal size of the children solely in that column. Followed by some postprocessing to ensure everything fits (as well as resolve e.g. fr units) before sizing rows the exact same way. Newly-allocated collections gathers sizing of each column/row for that postprocessing & to use the information to inform the positioning/sizing of all its children. Taking into account desired alignment.
Grid core pseudocode
:@track {
size!: :length;
size#fr { .size#fr = 0 }
size#fr = ^width - (@[ ^ + size ] - .gap*|@[size.fr]-1|)/|@[size.fr]|;
size.auto = .^@[grid-$axis-start == # && grid-$axis-start == grid-$axis-end][~$axis2 > $axis2 ? ~$axis2 : $axis2].$axis2
.gap : :length;
$axis, $axis2 : @property;
}
grid-template-columns : @track;
grid-template-columns.gap = grid-spacing.0;
grid-template-columns.$axis = columns;
grid-template-columns.$axis2 = width;
grid-template-rows : @track;
# TODO: Initialize grid-template-rows properties...
display.grid {
*width.auto = grid-columns[^ + size];
*height.auto = grid-columns[^ + auto];
grid-template-columns[~ + size] < width {
# Evaluate growth properties
}
grid-template-columns[~ + size] > width {
# Evaluate shrink properties
}
# Same for rows...
}
^display.grid {
$box.outer.left = ^grid-template-column[# < grid-column-start][~ + size];
$box.outer.right = ^grid-template-column[# <= grid-column-end][~ + size];
$box.outer.top = ^grid-template-rows[# < grid-row-start][~ + size];
$box.outer.bottom = ^grid-template-rows[# <= grid-row-end][~ + size];
$box.outer : $box.margin; # TODO: Add alignment...
}
Also tables may use an alternate “fixed” layout formula consulting just the first row of cells for widths.
Flexbox
A recent CSS layout technology is FlexBox, which arranges its stable-sorted children along a given axis. With or without wrapping it to a given width/height. Then there’s postprocessing reallocating excess space, or downsizing elements to fit in the available width.
Also excess space on both axes are reallocated to support alignment. This is very straightforward compared to the other layout modes, & doesn’t get in webdesigners’ way.
The bulk of the logic is a running-sum (an operation appearing all over CSS layout). Which may or may not be combined with conditionals checking when an element overflows the current row/column & should wrap over to the next one.
For the postprocessing I’d want to auto-generate implicit flexbox nodes for each row/column (depending on orientation), where wrapping is enabled. Within and between each of those rows/columns there’s some trivial arithmetic, involving division-by-count. Also inline layout may report their “baselines” for FlexBox to align those!
Flexbox Layout
display.flex {
flex-direction.row { $axis = x; $cross = y; $reverse = false }
flex-direction.row-reverse { $axis = x; $cross = y; $reverse = true }
flex-direction.column { $axis = y; $cross = y; $cross = x; $reverse = false }
flex-direction.column-reverse { $axis = y; $cross = x; $reverse = true }
# Sorting & reversing drops down an abstraction to pure-functional layer
# Sorting can't be implemented in the higher-level DSL.
@(sortBy: order)[$box.margin.$axis.start = ~$box.margin.$axis.end]
flex-wrap.no-wrap { @ = "".@ = @ }
flex-wrap.wrap { @[[$box.margin.$axis.end > ^$box.content.size.$axis] ? $box.margin.$axis.start = 0] }
flex-wrap.wrap-reverse { @[[$box.margin.$axis.end > ^$box.content.size.$axis] > $box.margin.$axis.start = 0](reverse) }
$reverse.true { @{ @(reverse) } }
# Add grow/shrink & alignment.
}
Masonry Layout
An interesting new layout algorithm coming to browsers is “masonry layout” (what Pinterest uses), which gracefully degrades to grid layout. Its great for media!
It involves tracking a “skyline” to place each subsequent child in the topmost available slot in which it fits. Same as I’d use for constructing “atlases” when optimizing image compositing.
I’m keen to use this myself…
Masonry layout
grid-template-rows.masonry, display.grid {
@{
$box.margin.top = @~skyline[y <= ~y].y;
$box.margin.left = @~skyline[y <= ~y; x <= ~x].x;
@skyline = @~skyline[$box.margin.left...$box.margin.right]{ x = ^$box.margin.left; y = ^$box.margin.top}
}
}
Floats
I don’t know whether CSS float’s unique features makes it worth implementing or to complex to do so. So how does it work?
We track 2 lists of floated elements: 1 for the left side, 1 for the right side. And we linearly-iterate over the elements to add or remove floated elements from these lists, whilst consulting to help determine where text wraps or where elements are positioned. This is tracked on the closest ancestor which is floated or positioned.
The catch is that this defeats any parallelising of layout computation. To parallelise float layout, we compute approximate layout in a first pass & slightly-pessimistically determine which elements might have their sizing impacted by each float.
Left-Float layout
@left-float = ^@left-float-inherited;
@left-float-inherited = @left-float; #
position.fixed { @left-float-inherited = "" }
position.absolute { @left-float-inherited = "" }
position.relative { @left-float-inherited = "" }
# etc...
float.left {
$box.margin.left = @left-float(widthAtY: $box.margin.top);
@left-float = $box, @left-float;
@left-float-inherited = ""
}
# FIXME: Wrap text around @left-float, & @right-float
# Similar logic for float: right
clear.left {
$box.margin.top = @left-float[margin.bottom > ~margin.bottom].margin.bottom;
}
Position
The CSS position property is a quite a raw layout mode, telling the browser where exactly to render an element onscreen. The complexity comes in when deciding the drawing order & in deciding which element it should be positioned relative to. We webdevs didn’t use to have better tools.
Nowadays I personally see this as causing more legibility-harm than good (especially if I’m not supporting JS) on the web & as such I do not plan to support it in my browser engine! And as such I won’t write pseudocode here.
Lists
Lists are a powerful way to make textual sequences more digistable, even better than Wizard Quoth’s caramel!
The way I’ve implemented this is by having a preprocessing step restructuring the document to insert ::marker pseudoelements with the given bullet. Possibly lowering to Flexbox for marker-position: outside (adding an additional parent element).
When this sequence is ordered, we use counters. Counters start by incrementing or (re)setting counters to render. Then rendering in the various ways we render list counters in the west (let alone the rest of the world!) takes most of the effort.
Most but not all of these notations involve integral divides-with-remainder. The details here are looked-up in a @counter-style collection. I ensured the hypothetical DSL supports concatenating text & consulting collections.
Counters pseudocode
counter-set(name : @ident, val : ##)...;
@counters = counter-set, ^@counters;
counter-increment($name : @ident, $x : ##)... {
@counters[name == $name].val += x
}
counter-set($name : @ident, $x : ##)... {
@counters[name == $name].val = x
}
**.counter($name : @ident, $style : @ident) {
render-counter(style, @counters[name == $name].val)
}
render-counter($style : @ident, $x : $style.range) {
render-counter(@counter-style[name == $style], $x)
}
render-counter($style { .system.numeric }, $x : $style.range) {
$style.symbols @ $x%|$style.symbols|, render-counter($style, $x/|$style.symbols|)
}
render-counter($style { .system.cyclic }, $x : $style.range) {
$style.symbols @ $x%|$style.symbols|
}
render-counter($style { .system.symbolic }, $x : $style.range) {
repeat($style.symbols @ $x%|$style.symbols|, $x/|$style.symbols|)
}
# TODO: Define a few more...
render-counter($style {.negative }, $x : ..0) {
$style.negative , render-counter($style, -$x)
}
render-counter($style {.pad.l > render-counter($style, $x) }, $x : ##) {
$txt = render-counter($style, $x);
repeat($style.pad.ch, $style.pad.l - |$txt|) , $txt
}
repeat($item, $x : ##) {
$item , $x - 1
}
@counter-style {
system : numeric, cyclic, symbolic, alpabetic, additive;
system.extends($name : @ident) {
** |= @counter-style[name == $name].$0
}
symbols : @text...;
additive-symbols : (val : ##, ch : @text)...;
prefix : @text;
suffix : @text;
range : (start : ##, end : ##)...;
pad : (ch : @text, l : 0..);
fallback($name : @ident) = @counter-style[name == $name];
fallback.initial = "decimal";
}
List pseudocode
::marker.content = list-style-type.prefix, render-counter(list-style-type, @counters[$name == "list-item"]) , list-style-type.suffix;
display.list-item, list-item-position.inside {
@ = ::marker , @;
display = .block;
}
display.list-item, list-item-position.outside {
@ = ::marker , { display = .block, @ = @};
display = .flex;
}
list-style-type($name : @ident) = @counter-style[name == $name];
list-style-type($sym : @text) = { .system = .cyclic, .symbols = $sym }
list-style-type.symbols($type, $syms) = { .system = $type, .symbols = $syms }
list-style-image($sym : @img) { list-style-type = $sym } # For most uses, @img would naturally be a subtype of @text.
Pagination
For some mediums, the output (or occasionally input) places a limit on how tall the rendered can be. Often this can be addressed by adding a scrollbar, but not always. In those cases we need to split the webpage into what I call (to avoid confusion) “screenfulls”. Where we find which element overflows the available space & recursively split it. Handling inline text specially.
The same strategy can be repurposed to split an element into multiple columns! Multicolumn layout calculates initial sizing ignoring these properties, then it calculates the size of each of the columns, paginate children beneath them, & positions those columns. Paginating each layout formula I’m describing may involve different strategies.
Pagination pseudocode
$box.border.bottom > $remaining-height {
~ = ~ , { ** = $0, @ = @[..$page-break.true] };
$page-break = true;
@ = @[$page-break.true...];
}
$remaining-height = ^$remaining-height - ^$box.content.top; # FIXME: Are coordinate-spaces right?
# TODO: Specialize pagination for different values of display, e.g. "inline".