Layout is one of the hardest problems in UI toolkit design because there are so many different ways to design a layout. Creating a system that supports them all is practically impossible. Even creating a system that merely makes them all possible to implement (even if difficult) is a challenge. And making the layout fast is even harder. However, given that we are targeting embedded systems, rather than general purpose interfaces (ex: no resizable windows), we should be able to narrow down the scope to something usable. Let’s dig in.

This post is about my new untitled embedded rust GUI toolkit.

The layout system needs to support the following cases:

• A panel expands to fill the screen
• A tabbed panel has a top area where a toggle group should expand horizontally to fill the width and the panel children of the content area should expand to fill the content in both directions.
• A parent that allocates part of i’s area to one child, then gives the rest to the second child.
• A flexbox vertical box with three children where the first and last children use their default height, but the second child is made to expand to all of the leftover space.

All of the above cases requires communication back and forth between the parents and children. A parent’s size might not depend on its children, but how much it gives to one child could depend on how much it gives to another child. And this can vary between layouts. Thus, the parent is intimately involved in how it’s children are sized.

There’s a few approaches we can take:

Outside In

Outside In is where the parent always does its own layout first, then it provides available space to its children. This is typically good for embedded where parents take up all available space and divide it among their children, but it does rule out certain layouts. What if a row panel wants to be as wide as it’s parent but only as tall as needed for its own children? Then it needs to ask the children for their heights first. Outside In won’t work in this case.

Inside Out

Inside Out means the children choose their own size based on their contents and the parent only positions them. A parent can shrink itself to fit the size of the children (as in the row example above), but children cannot expand to fill all of the parent’s space. However, this does result in a very fast and deterministic system. We only need to traverse the tree once and parents always have a pre-sized children.

Two Phase Layout

The parent passes available space to the children and the child sizes itself. This lets a child expand itself to fill the available space if it wants to. But how does the parent know how much space it has available? It gets it from its parent, like in the Outside In layout. But it also might shrink the available size before handing it to its children. This requires two phases of layout. The children’s minimum sizes are measured, then parent calculates how to distribute the space, then the children size themselves using that space. This is the classic layout in many UI toolkits but results in an exponential cost algorithm. At each layer we are doubling the number of calls. If a child needs to look at its own children to determine it's minimum size then we have at least an O(N^2) algorithm. Not good.

Fixed Layout

Simply have the developer manually size and position everything. This is actually the fastest. Now our layout algorithm is O(1)!. It's actually pretty common on embedded systems since there usually are resizable windows. However, it requires the developer to do more work and doesn’t handle cases where the content itself changes, which is likely with any Internet connected device. Imagine a button that doesn’t become bigger if the text is longer? We can do better.

Flutter

I really don’t like any of these solutions.

Flutter’s algorithm is pretty good and sub-linear in many cases. Flutter has the parent provide constraints and the child returns its preferred size. For something like a vertical box with flexible children the parent must lay out the non-flex children first to find the leftover size and then lay out the flex children. In order to remain non-exponential we need a way for the children to indicate they are flex without actually calling the child’s layout method. Flutter handles this by actually doing two passes and agressively caching results so that the common case is sub-linear even if the worst case is exponential.

The Compromise

Unfortunately, we can’t use Flutter’s system directly. It was optimized by many talented engineers over many years. It also uses extra memory for the caching. We don’t really have that option for a tiny open source library targeting embedded. So I came up with a compromise. Instead of calling a child method to get its preferred behavior we the child has flags for flex and alignment. The parent can check these flags without invoking an entire layout pass on the child. This gives us most (but not all) of the behavior of Flutter’s system without caching and being reasonably simple to use. There are some cases it doesn’t handle gracefully, but it works well for the most common ones so I think this is a reasonable tradeoff.

The New Layout Proposal

So here is how the new system works.

• A view has h_flex and v_flex attributes set to Flex::Intrinsic or Flex::Resize.
• a view has h_align and v_align attributes set to Align::Start, Align::Center, or Align::End.
• These flags are set before layout begins.
• Children set their size but their parents set their position.

Layout processed as a single pass tree traversal. A parent:

• izes itself based on available space passed into it.
• for all Intrinsic flex children, calls child.layout(space) to have the child determine it’s size.
• calculates the remaining space and divides it by the number of Resize flex children.
• for all Resize flex children, calls child.layout(remaining) to have the child determine it’s size.
• set the position of all children using their alignment.

For complex parents like vertical and horizontal flex boxes they will perform all the steps above. For simple views like buttons and labels they will set their flex to Intrinsic and calculate their size based on the font and title text.

So far (barring unfixed bugs) the above system handles everything I’ve thrown at it and works quickly with no exponential layout explosion. It even worked for a simplified CSS grid layout where the developer can define rows and columns and assign children to different cells with different alignments.

Next Steps

Now that the new layout system is merged from a branch I’m getting close to a 0.1 release. I still need to:

• Document the event loop.
• Document how to create a custom view.
• Pick a better project name.

If you have any questions for feature requests, please get in touch: josh@josh.earth.

Project Repo