Laying out embedded GUIs

At work we've got a little layout problem. There's an embedded application with a GUI, made mostly by someone who left the company a while ago. Now I'm trying to make some changes to it, to add scrolling of too long texts and such. While doing that I exposed some bugs in the size and positions of various parts of the GUI, so now I need to do something about that too.

There's just one small problem: all the sizes and positions are hard coded, and they're not even named constants. It's just lots of "foo.width = 204" etc, and you're apparently supposed to know how wide something can be without colliding with something else. It's possible to figure out, of course, but it's just not a good solution to the problem. Then there's a different problem that the current solution just doesn't handle: limiting the total width of label + value but not the width of either part. Now I need to add a safety margin to both parts, but they cannot use the unused space in each other.

If this application was made in something a bit higher level than "C plus undebuggable Lua on an ARM7" it's likely the GUI would be created using something better suited to the task, like XAML or whatever the widget system in Android is called. Something that takes a bunch of constraints and turns that into a suitable set of coordinates. Since we didn't have that, I went shopping for solutions: this problem has obviously been solved many times before.

Half a day later I had found nothing that suited our needs. On the open source side there's Cassowary, famously used by Apple in Auto Layout. Too bad it's 8k lines of C++, said to be on the slow side, and we're already a bit tight on Flash space. There are a number of commercial offerings, but they tend to both cost a fortune (or even "contact us for an offer…", which is a direct "no") and also try to copy Win95. I don't know why they're so fond of a 20 year old GUI, but they are. We've already got widgets and rendering code, so we're only in need of the layout engine.

So what's a coder to do? Code, of course. Not too many hours later I have 400 lines of C code that can handle most of what's needed and turn a bunch of min/max values into a fancy layout without hardcoding sizes! Being a serious developer (ehm…), I started out by listing the requirements for the layout code, and after a couple of hours of on-and-off thinking about the problem I ended up with this:

• Lib should determine sizes and positions of a set of boxes.
• Boxes can contain child boxes.
• A child box is limited to the content area of its parent box.
• Child boxes are laid out according to a selected algorithm.
• A box can have only one algo, but its children can have different algos as needed.
  • Algo: Horizontal stack layout
  • Algo: Vertical stack layout
• A box can have padding.
• A box has a minimum size, a maximum size, and a preferred size.
• A box can present a virtual size to its children, e.g. a scrollable list box would have an unlimited size in either the horizontal or vertical direction
• If the preferred size is smaller then the actual size, the content of the box can be placed according to a selected alignment.
• Horizontal and vertical alignment are selected separately
• Possible alignments:
  • start (left/top)
  • center
  • end (right/bottom).
• A box has padding, and content area.
  • The padding is subtracted from the total size, yielding the content area.
  • Child boxes are placed in the content area, not in padding.
• A box can be resized, causing reevaluation of sizes of other boxes as needed (parent, siblings and up?)
• Resizes are batched to minimize recalculations

In the initial version, there's no support for preferred sizes or alignments, but in our application I think that min sizes will do well enough. One missing thing that we do need is support for is scrollable boxes: it's just a matter of keeping track of which boxes need this and setting the available space to infinity - then it's up to the renderer to draw just a part of the box as needed.

Note that I don't include any requirements for the rendering parts here. The layout code should have no dependency on the rendering code, since layout is done way before rendering takes place. In the repo there's a bunch of requirements on the rendering code listed as well, but it's just preparation for the next step and has nothing to do with layout.

The layout code work this way:

• First you create a structure of box descriptions that define the layout
• Describe the available screen space for the layout
• Then you call layout_update() , and your box structure is updated and ready for rendering

Child's play. Each box is described by a layout_box_t struct:

struct layout_box_t {
    const char* name;

    layout_box_t *parent;
    layout_box_t *sibling;
    layout_box_t *children;

    layout_algorithm_t algo;

    layout_size_t size;
    layout_padding_t padding;

    layout_render_data_t render;
};

The name is just for debug printouts. Then there's a couple of pointers to parent box (unless this is the root box), next sibling, and first child. The children are stored in a linked list where each box points to its next sibling. It's nor very practical, but it works.

Then we've got the algorithm for laying out children, a size struct, and some padding. The final render struct is defined by the application and contains what's needed by the render system to render the box to screen. It might contain a pointer to a bitmap, some view-dependent data or whatever fits the needs of the render system. The layout code don't care what it contains, but we do care about its size so we can compile the layout code.

The layout_size_t struct is larger than actually needed, because it looks like this:

struct layout_rect_t {
    int32_t x;
    int32_t y;
    int32_t width;
    int32_t height;
};

struct layout_size_t {
    layout_rect_t min;
    layout_rect_t max;

    layout_rect_t calculated;

    layout_rect_t actual;
};

Note that the x and y coordinates are only actually needed by the actual struct, the others care only about the width and height. Maybe I'll fix that some day, but it was easier to reuse the same type for all sizes. min and max are filled in before running the layout code, then calculated is used internally before actual is filled in with the resulting position and size of the box. The position is in global coordinates, since that likely makes our rendering code easier. In the example application the resulting boxes are "rendered" by outputting a bunch of HTML DIVs. Have a look here, it's very pretty .

As for the algorithm used for laying things out, it's also rather basic. It's a two step process: first we apply the size of the root box, then recursively divide that size among its children, before we finally calculate the positions of everything. We apply the size this way:

• Set the actual size of the current box
• If it has no children, we're done
• Calculate the min size of the children
• Determine how much space is left to divide
• While there's still space left and there are children smaller than their max sizes, divide space proportionally among children not at max size

The calculation of the min size of the children is a bit inefficient as it is now, since it doesn't cache size calculations and instead re-calculates everything every time we ask for it. But since we have so few boxes, it's ok. The slightly tricky bit is that we need to loop until there's no space left to divide or until the children are maximally large. We need to do this since we try to give the children an proportionate bit of the remaining space depending on their relative sizes, but if some child can't use its full portion we need to divide that among the remaining siblings.

If you're interested, have a look at the example code that I put up on Bitbucket: https://bitbucket.org/tlabwest/liblayout . This will generate fancy HTML like the example above, and can be adapted for use in your own embedded projects. If you're not quite as embedded as we are, you're probably better off using something more complicated like HTML, Android or some such, but sometimes you don't need to make things more complicated than they really need to be.