Outcurses

bling up that terminal

During the development of Growlight and Omphalos, I found myself implementing significant UI code atop ncurses. It's my goal to extract most of this, unify it, and make it available as liboutcurses. Code lives on github.

Why is it called 'outcurses'? Because there's more cursing, duh.

This project led to notcurses.

Palette fades

Back when I was a young software witch, the first cool thing you did on a PC was switch to mode 13h and fade the 6 bits of its 3 color channels using some x86 assembly. The effect still fills me with joy. Now it's available to your text-mode programs! Specify a number of milliseconds through which you wish to fade, and a channel-balanced, delay-adaptive fade will be executed across the palette. The default text color (colorpair -1 in ncurses semantics) is *not* faded.

Metric suffixes

Not ncurses-related, but it's UI, so I stuck it here. Fed a uintmax_t (large enough to represent any unsigned integer type), a buffer, and a base (almost always 1000 or 1024), enmetric renders the number into the buffer such that the characteristic (material to the left of the decimal point) is less than the base. For numbers greater than the base, this means some metric suffix will be employed, and that the displayed number will have a mantissa (e.g. 1234 with a base of 1000 becomes 1.234K). Numbers through 2^89 are properly handled, using the suffixes Y, Z, E, P, T, G, M, and K. Use of base 1024 is necessary to properly employ the metric units of digital information. For instance, a 10 terabyte hard drive typically has 10* 10¹² == 10,000,000,000,000 (ten trillion) bytes aka 10TB, but 10 * 2⁴⁰ == 10 * 1024 * 1024 * 1024 * 1024 is 10,995,116,277,760 bytes aka 10 tibibytes aka 10TiB. A kilobyte is 97.7% of a kibibyte, but a terabyte is only 91% of a tibibyte.

Three characters of mantissa are used for characteristics less than 10; two characters are used for characteristics greater than 9 but less than 100; one character is used for characteristics greater than 99. Note that the most precision is available for the smallest characteristics, which is desirable, since the mantissa represents a greater portion of the total in these cases.

The necessary output buffer is a fixed size for a given base. For 1000, at most 7 chars are necessary:

• 3 for the characteristic (or 1 with 3 chars of mantissa, etc.)
  • 0 <= characteristic < base
• 1 for the decimal point
• 1 for the mantissa (or 2 with 2 chars of characteristic, etc.)
  • 0 <= mantissa <= 0.999 (mantissa range is independent of base)
• 1 for the metric suffix
• 1 for the NUL terminator

An optional universal suffix can be supplied to enmetric; this is printed following the metric suffix. This is intended to support 'i' when the base is 1024. In this maximal case (base > 1000, universal suffix), 9 chars are necessary. Less space than this can always be used; the output will be left-padded with spaces. The minimal output is two bytes (a single digit and a NUL).

If the omitdec boolean is true, no decimal point or mantissa will be printed when said mantissa would be all zeroes.

Panelreels

The Ncurses panels extension (originating in AT&T System V) facilitates management of a deck of possibly-overlapping window objects sharing a screen (there's little point in using panels if windows are strictly tiled among the screen, but not much reason not to, either). The various panels of a screen have a z-ordering, and higher panels obscure panels underneath. Using the panels extension requires linking in the extra library libpanel (or libpanelw for wide character support).

The panelreel is a UI abstraction supported by outcurses in which dynamically-created and -destroyed toplevel entities (referred to as tablets) are arranged in a torus (circular loop), allowing for infinite scrolling (infinite scrolling can be disabled, resulting in a line segment rather than a torus). This works naturally with keyboard navigation, mouse scrolling wheels, trackballs, and touchpads (including the capacitive touchscreens of modern cell phones). The "panel" comes from the underlying ncurses objects (each entity corresponds to a single panel) and the "reel" from slot machines. A panelreel initially has no tablets; at any given time thereafter, it has zero or more tablets, and if there is at least one tablet, one tablet is focused (and on-screen). If the last tablet is removed, no tablet is focused. A tablet can support navigation within the tablet, in which case there is an in-tablet focus for the focused tablet, which can also move among elements within the tablet.

The panelreel object tracks the size of the screen, the size, number, information depth, and order of tablets, and the focuses. It also draws the optional borders around tablets and the optional border of the reel itself. It knows nothing about the actual content of a tablet, save the number of lines it occupies at each information depth. The typical control flow is that an application receives events (from the UI or other event sources), and calls into outcurses saying e.g. "Tablet 2 now has 40 valid lines of information". Outcurses might then call back into the application, asking it to draw some line(s) from some tablet(s) at some particular coordinate of that tablet's panel. Finally, control returns to the application, and the cycle starts anew.

Each tablet might be wholly, partially, or not on-screen. Outcurses always places as much of the focused tablet as is possible on-screen (if the focused tablet has more lines than the actual reel does, it cannot be wholly on-screen. In this case, the focused subelements of the tablet are always on-screen). The placement of the focused tablet depends on how it was reached (when moving to the next tablet, offscreen tablets are brought onscreen at the bottom. When moving to the previous tablet, offscreen tablets are brought onscreen at the top. When moving to an arbitrary tablet which is neither the next nor previous tablet, it will be placed in the center).

The controlling application can, at any time,

• Insert a new tablet somewhere in the reel (possibly off-screen)
• Delete a (possibly off-screen) tablet from the reel
• Change focus to the next or previous tablet, bringing it on-screen if it is off
• Change focus to some arbitrary other tablet, bringing it on-screen if it is off
• Expand or collapse the information depth of a tablet
• Change the content of a tablet, updating it if it is on-screen
  • Remove content from a tablet, possibly resizing it, and possibly changing focus within the tablet
  • Add content to the tablet, possibly resizing it, and possibly creating focus within the tablet
• Navigate within the focused tablet
• Create or destroy new panels atop the panelreel
• Indicate that the screen has been resized or needs be redrawn

A special case arises when moving among the tablets of a reel having multiple tablets, all of which fit entirely on-screen, and infinite scrolling is in use. Normally, upon moving to the next tablet from the bottommost tablet, the (offscreen) next tablet is pulled up into the bottom of the reel (the reverse is true when moving to the previous tablet from the topmost). When all tablets are onscreen with infinite scrolling, there are two possibilities: either the focus scrolls (moving from the bottom tablet to the top tablet, for instance), or the reel scrolls (preserving order among the tablets, but changing their order on-screen). In this latter case, moving to the next tablet from the bottommost tablet results in the tablet which is gaining focus being brought to the bottom of the screen from the top, and all other tablets moving up on the screen. Moving to the previous tablet from the topmost tablet results in the bottommost tablet moving to the top of the screen, and all other tablets moving down. This behavior matches the typical behavior precisely, and avoids a rude UI discontinuity when the tablets grow to fill the entire screen (or shrink to not fill it). If it is not desired, however, scrolling of focus can be configured instead.

Panelreel examples

Let's say we have a screen of 11 lines, and 3 tablets of one line each. Both a screen border and tablet borders are in use. The tablets are A, B, and C. No gap is in use between tablets. Xs indicate focus. If B currently has focus, and the next tablet is selected, the result would be something like:

 -------------                         -------------
 | --------- |                         | --------- |
 | |   A   | |                         | |   A   | |
 | --------- |                         | --------- |
 | --------- | ---- "next tablet" ---> | --------- |
 | |XX B XX| |                         | |   B   | |
 | --------- |                         | --------- |
 | --------- |                         | --------- |
 | |   C   | |                         | |XX C XX| |
 | --------- |                         | --------- |
 -------------                         -------------

If instead the previous tablet had been selected, we would of course get:

 -------------                         -------------
 | --------- |                         | --------- |
 | |   A   | |                         | |XX A XX| |
 | --------- |                         | --------- |
 | --------- | ---- "prev tablet" ---> | --------- |
 | |XX B XX| |                         | |   B   | |
 | --------- |                         | --------- |
 | --------- |                         | --------- |
 | |   C   | |                         | |   C   | |
 | --------- |                         | --------- |
 -------------                         -------------

If A instead has the focus, choosing the "next tablet" is trivial: the tablets do not change, and focus shifts to B. If we choose the "previous tablet", there are three possibilities:

• Finite scrolling: No change. The tablets stay in place. A remains focused.

 -------------                         -------------
 | --------- |                         | --------- |
 | |XX A XX| |                         | |XX A XX| |
 | --------- |                         | --------- |
 | --------- | ---- "prev tablet" ---> | --------- |
 | |   B   | |     (finite scroll)     | |   B   | |
 | --------- |                         | --------- |
 | --------- |                         | --------- |
 | |   C   | |                         | |   C   | |
 | --------- |                         | --------- |
 -------------                         -------------

• Infinite scrolling with rotation: Focus shifts to C, which moves to the top:

 -------------                         -------------
 | --------- |                         | --------- |
 | |XX A XX| |                         | |XX C XX| |
 | --------- |                         | --------- |
 | --------- | ---- "prev tablet" ---> | --------- |
 | |   B   | |  (infinite scroll with  | |   A   | |
 | --------- |        rotation)        | --------- |
 | --------- |                         | --------- |
 | |   C   | |                         | |   B   | |
 | --------- |                         | --------- |
 -------------                         -------------

• Infinite scrolling with focus rotation: Focus shifts to C, and moves to the bottom:

 -------------                         -------------
 | --------- |                         | --------- |
 | |XX A XX| |                         | |   A   | |
 | --------- |                         | --------- |
 | --------- | ---- "prev tablet" ---> | --------- |
 | |   B   | |  (infinite scroll with  | |   B   | |
 | --------- |     focus rotation)     | --------- |
 | --------- |                         | --------- |
 | |   C   | |                         | |XX C XX| |
 | --------- |                         | --------- |
 -------------                         -------------

Now imagine us to have the same 3 tablets, but each is now 4 lines. It is impossible to have two of these tablets wholly onscreen at once, let alone all three. If we started with A focused and at the top, the result after all three tablets have grown will be:

 -------------                         -------------
 | --------- |                         | --------- | A remains at the top, and
 | |XX A XX| |                         | |XXXXXXX| | is wholly on-screen. B is
 | --------- |                         | |XX A XX| | below it, but we can show
 | --------- | ---- "grow tablet" ---> | |XXXXXXX| | only the first two lines.
 | |   B   | |       A (focused)       | |XXXXXXX| | C has been pushed
 | --------- |                         | --------- | off-screen.
 | --------- |                         | --------- |
 | |   C   | |                         | |       | |
 | --------- |                         | |   B   | |
 -------------                         -------------

When a tablet is enlarged, it grows towards the nearest boundary, unless that would result in the focused tablet being moved, in which case the growing tablet instead grows in the other direction (if the tablet is in the middle of the screen exactly, it grows down). There is one exception to this rule: if the tablets are not making full use of the screen, growth is always down (the screen is always filled from the top), even if it moves the focused tablet.

A 12-line screen has three tablets: A (2 lines), B (1 line), C (1 line), filling the screen exactly. B is focused, and grows two lines:

 -------------                         -------------
 | --------- |                         | --------- | B grows down, since it is
 | |   A   | |                         | |   A   | | closer to the bottom (3
 | |       | |                         | |       | | lines) than the top (4
 | --------- | ---- "grow tablet" ---> | --------- | lines). C is pushed almost
 | --------- |       B (focused)       | --------- | entirely off-screen. A is
 | |XX B XX| |                         | |XXXXXXX| | untouched.
 | --------- |                         | |XX B XX| |
 | --------- |                         | |XXXXXXX| |
 | |   C   | |                         | --------- |
 | --------- |                         | --------- |
 -------------                         -------------

Starting with the same situation, A grows by 2 lines instead:

 -------------                         -------------
 | --------- |                         | |       | | A grows up. It would have
 | |   A   | |                         | |   A   | | grown down, but that would
 | |       | |                         | |       | | have moved B, which has
 | --------- | ---- "grow tablet" ---> | --------- | the focus. B and C remain
 | --------- |     A (not focused)     | --------- | where they are; A moves
 | |XX B XX| |                         | |XX B XX| | partially off-screen.
 | --------- |                         | --------- |
 | --------- |                         | --------- |
 | |   C   | |                         | |   C   | |
 | --------- |                         | --------- |
 -------------                         -------------

If we started with the same situation, and B grew by 7 lines, it would first push C entirely off-screen (B would then have four lines of text), and then push A off-screen. B would then have eight lines of text, the maximum on a 12-line screen with both types of borders.

Panelreel usage

create_panelreel() is called with a panelreel_options struct, returning NULL on error. This struct includes:

• WINDOW* w -- the ncurses WINDOW on which this panelreel lives
• int footerlines, headerlines -- how many lines to leave on the top and bottom of the WINDOW
• int leftcolumns, rightcolumns -- how many columns to leave on the left and right of the WINDOW
• bool infinitescroll -- whether the line segment ought be looped into a torus
• bool circular -- set true for reel rotation, false for focus rotation, when panelreel doesn't occupy entire screen
• LineCountCB linecb and DrawLinesCB drawcb -- callbacks, see below
  • It is invalid to set circular but not set infinitescroll. NULL will be returned

Two callbacks must be provided: a LineCountCB and a DrawLinesCB. Most actions on a panelreel can result in these callbacks being called one or more times, possibly in an interleaved fashion. Note that a change in one tablet can result in a change of the position of another tablet, and thus the number and identity of lines displayed in that tablet, so more than one tablet can be the subject of callbacks. Furthermore, note that the screen is a composition of tablets as they stand at some time, so a tablet must not change between the callbacks triggered by a given call.

The natural implication is that, prior to calling a panelreel function, the caller ought take a lock, and this lock ought cover *all material relevant to display, for all tablets*. Only upon return from outcurses can this lock be unlocked. Yes, this is a very coarse locking scheme, with some latency in the critical section. If you need to continue processing events at a high rate while updating the panelreel, collapse them into an intermediate structure, and have your calling thread pull in those data. Or something. The most common effect of failure to do this is empty lines in a tablet.

Panelreel history/design

I implemented panelreels as tightly-interwoven UI code in two projects during the early 2010s: growlight and omphalos. In both projects, the ncurses code ran to thousand of lines, and rapidly became difficult to maintain (I only resolved one bug in growlight's UI late in 2019). The system did, however, seem both performant and useful, with general applications. I resolved to extract the code from both projects, unify it, and make it generally available. Both applications were built around a common core, with pluggable UIs defining distinct applications, each registering callbacks defined by their core's interface. Omphalos defined more callbacks than growlight:

omphalos/ui/ncurses.c 2019-11-06 (0.99.9~pre):

  pctx.iface.packet_read = packet_callback;
  pctx.iface.iface_event = interface_callback;
  pctx.iface.iface_removed = interface_removed_callback;
  pctx.iface.vdiagnostic = vdiag_callback;
  pctx.iface.wireless_event = wireless_callback;
  pctx.iface.srv_event = service_callback;
  pctx.iface.neigh_event = neighbor_callback;
  pctx.iface.host_event = host_callback;
  pctx.iface.network_event = network_callback;

growlight/ncurses.c 2019-11-06 (1.1.3):

  const glightui ui = {
    .vdiag = vdiag,
    .boxinfo = boxinfo,
    .adapter_event = adapter_callback,
    .block_event = block_callback,
    .adapter_free = adapter_free,
    .block_free = block_free,
  };

In growlight, the tablet-level object is the adapter, detailed at the first level by the block device. In omphalos, it is the interface, detailed at the first level by L2 hosts. Both divide callbacks between a removal event and an update, while neither requires a distinct creation event. Both are driven by a combination of external events (resulting in callback of their cores, leading to invocation of one of the registered UI callbacks) and UI events, primarily keypresses. In both cases, a thread is devoted to a wgetch() loop (the main thread in growlight, and a side thread spawned by main() in omphalos). In both cases, almost every key handler and callback lock and unlock a UI-global lock as their first and last actions. Before unlocking, there is almost always a call to update_panels() followed by doupdate(). Most actions do not result in an entire screen redraw from scratch. Instead, they typically redraw at the tablet level (werase() of the tablet's panel followed by full redraw), and move existing tablets around using the panels API.

Both UIs keep O(N) structure corresponding to the N tablets, and further O(N) structure for each sublevel of information used. Growlight's adapterstate and blockobj correspond to (and contain pointers to) the core's controller and device, respectively; omphalos has iface_state and l2obj all the way to l4obj. Both have their own definition of a reelbox which corresponds to the outcurses tablet. In a general design, of course, we cannot assume typed pointers to dynamic program objects, but avoiding a lookup on every UI event remains desirable. We can sacrifice typing with a void pointer, but there is a more fundamental concern of locking.

Imagine that there are two major locks in the program: a UI lock and a core lock (the core's locking might be much more complicated, but from our perspective, a simple BKL we can't directly access is sufficient for modeling). UI events are assumed to take the UI lock as their first action, then modify the UI. Core events are assumed to take the core lock as their first action, and might modify the UI. Modifying the UI requires taking the UI lock. If the UI events thus ever need take the core lock (indirectly, via callbacks into the core), there is a potential classic ABBA deadlock. Unless the UI intends to copy all data it might ever need present, it is likely to require the core lock.

Growlight resolved this by requiring ncurses events to take the core lock before taking the ncurses lock. This requires cooperation from the core and a simplistic locking scheme, and serializes most of the program against the UI, but does resolve the problem. Omphalos appears not to lock the core from within the UI. Instead, the UI carries around significant copied data—enough to establish the number of lines an interface can require at any given time, though not enough to redraw the interface details. At some point, the omphalos UI takes a deep breath and dereferences a pointer into unlocked application-side data. This can be made to work only if the UI copies all metadata necessary for structuring the output, AND can rely on the core neither moving nor deleting data to which the UI points without taking the UI lock. In omphalos, for instance, receipt of an RTM_DELLINK netlink message indicating that an interface has been deleted is handled thus (all in the context of the thread receiving the netlink event):

• processing the RTM_DELLINK to extract the interface index
• acquiring the core's iface lock
• finding the interface specified by this index
• removing the interface from the lookup structure
• acquiring the interface's marshal lock
• cancelling the packet socket thread for this interface
• releasing the interface's marshal lock
• joining the packet socket thread for this interface
• acquiring the UI lock (start of interface_removed_callback)
• removing the iface_state from its circular list of all iface_states
• removing the reelbox from its own circular list of visible reelboxen
• destroying the panel, reelbox, and iface_state
• repairing the screen by filling in this hole, possibly making other ifaces visible
• releasing the UI lock
• releasing the core's iface lock
• destroying the interface

Not only is this a tremendous amount of (possibly blocking!) work done while holding *multiple* locks, but it is complicated for the application programmer (what goes away when?), it is difficult to reason about what needs to be copied into the UI's state (and this process does not self-recover if the two ever diverge), and we waste memory and time with said copies. That marshaling lock could probably be reduced to an atomic, as it's unattached to a condvar. Can we not unlock the iface lock after splicing out the interface from its lookup structure? It would seem so, but verifying it would be more effort than I want to put in at the moment. Finally, I suspect it all to be broken. Who knows. This sucks, and I ought set myself on fire.

For Outcurses and its general-purpose panelreels, we cannot assume deep application assistance. We cannot assume understanding of application internals. We cannot assume that it is possible to cache structure beyond the circular list of top-level objects corresponding to tablets, and we cannot even assume this last to be truly reflected in the application, which might very well not have a concept of ordering among the tablets. Furthermore, it would be a fine thing indeed to wholly decouple screen updates from any locked core code.

Accomplishing this last eliminates almost all of our problems, while introducing a few new ones. Decoupling screen updates from core updates means that UI code cannot be called from any application context holding core locks. This immediately suggests a producer/consumer model where updates are written to a shared, synchronized buffer. In a model where data is copied to the UI state (and thus it needn't lock against the core), these updates might take the form of piecemeal instructions ("iface 2 has added a subelement. iface 3 has received the following packet." etc.), and it would be necessary to process the updates in-order and cumulatively, though actual screen redrawing could be postponed to the end of a batch of updates. Alternatively, the entirety of state could be copied for each update, eliminating complexity in both the UI and core for a price paid in memory and time. Finally, nothing could be published save "iface 2 has changed", requiring a locked call into the core to get the data (and reference counters for data which might be destroyed). Comparing these strategies, we see:

Deadlock-resistant core update strategies

Method	Locked call into core	Unnecessary copies	Limits on core structure	UI complexity
Piecemeal updates	No	Small	Yes	Large
Snapshots	No	Large	No	None
Notifications	Yes	None	No	Small

This would seem strong support for snapshots. The size would theoretically be unbounded (i.e. copy output of the object assuming an infinite tablet), but it seems we could bind it to the total size of the screen. This runs into some details that seem possible to overcome (what if a new, larger display is attached to the machine during runtime, and the window is moved to that screen, and maximized?). The fatal problem in my mind is that these non-trivial (if bounded) copies must be performed for all interfaces, whether on-screen or off-. So far as I can tell, any scheme which avoids copies for off-screen tablets requires a locked callback into the core, since a UI event can bring a tablet on-screen independently of any core event. Since there is an unbounded number of off-screen interfaces needing copies, the overall copying can once more be unbounded, and thus the snapshot approach is unacceptable. Notifications it is, then.

The problem with notifications is primarily that objects can be removed by the core while the UI still holds references to them. The UI blindly invoking these objects will result in catastrophe. We can add a reference count to the objects, at the cost of some application complexity (the application must down the reference counter, and provide a destructor that can be called from UI context). Avoiding this complexity in the application seems to require substantial complexity in outcurses: the application can be allowed to freely destroy its object following posting notification of the deletion if outcurses takes this into consideration when performing other actions. For instance, prior to user keypress selecting the previous tablet, it must be verified that this tablet still exists. If the move pushes some other tablet partially off-screen, it must be verified that this other tablet still exists prior to redrawing it, etc. In the case where the tablet no longer exists, action must be taken to remove it (and fill the void) along all manner of new control flow paths. Alternatively, the callback could require a core lookup each time.

Panel animations

These routines allow a panel to inflate to its target size from a single character, or to minimize away to a single character and disappear. Provide a number of milliseconds for the animation to run. This works for arbitrary panels, including those in a panelreel.

See also

• Thomas Dickey's NCURSES FAQ, which is a delight
• The Python curses.panel module
• My Xcurses project, which went exactly nowhere
• libtickit