Skip to content

The engine room

Adapted from A Hacker’s Guide to NCURSES, by Eric S. Raymond.

All ncurses input funnels through the function wgetch(), defined in lib_getch.c. This function is tricky; it has to poll for keyboard and mouse events and do a running match of incoming input against the set of defined special keys.

The central data structure in this module is a FIFO queue, used to match multiple-character input sequences against special-key capabilities; also to implement pushback via ungetch().

The wgetch() code distinguishes between function key sequences and the same sequences typed manually by doing a timed wait after each input character that could lead a function key sequence. If the next character of the sequence arrives within ESCDELAY milliseconds (1000 by default), the sequence is assumed to have been generated by a function key press.

Hackers bruised by previous encounters with variant select(2) calls may find the code in lib_twait.c interesting. It deals with the problem that some BSD selects don’t return a reliable time-left value. The function _nc_timed_wait() effectively simulates a System V select.

If the mouse interface is active, wgetch() polls for mouse events each call, before it goes to the keyboard for input. It is up to lib_mouse.c how the polling is accomplished; it may vary for different devices.

Under xterm, however, mouse event notifications come in via the keyboard input stream. They are recognized by having the kmous capability as a prefix. This is kind of klugey, but trying to wire in recognition of a mouse key prefix without going through the function-key machinery would be just too painful, and this turns out to imply having the prefix somewhere in the function-key capabilities at terminal-type initialization.

This kluge only works because kmous isn’t actually used by any historic terminal type or curses implementation we know of. Best guess is it’s a relic of some forgotten experiment in-house at Bell Labs that didn’t leave any traces in the publicly-distributed System V terminfo files. If System V or XPG4 ever gets serious about using it again, this kluge may have to change.

Here are some more details about mouse event handling.

The code in lib_mouse.c is logically split into a lower level that accepts event reports in a device-dependent format and an upper level that parses mouse gestures and filters events. The mediating data structure is a circular queue of event structures.

Functionally, the lower level’s job is to pick up primitive events and put them on the circular queue. This can happen in one of two ways: either (a) _nc_mouse_event() detects a series of incoming mouse reports and queues them, or (b) code in lib_getch.c detects the kmous prefix in the keyboard input stream and calls _nc_mouse_inline() to queue up a series of adjacent mouse reports.

In either case, _nc_mouse_parse() should be called after the series is accepted to parse the digested mouse reports (low-level events) into a gesture (a high-level or composite event).

With the single exception of character echoes during a wgetnstr() call (which simulates cooked-mode line editing in an ncurses window), the library normally does all its output at refresh time.

The main job is to go from the current state of the screen (as represented in the curscr window structure) to the desired new state (as represented in the newscr window structure), while doing as little I/O as possible.

The brains of this operation are the modules hashmap.c, hardscroll.c and tty_update.c; the latter two use lib_mvcur.c. Essentially, what happens looks like this:

  • The hashmap.c module tries to detect vertical motion changes between the real and virtual screens. This information is represented by the oldindex members in the newscr structure. These are modified by vertical-motion and clear operations, and both are re-initialized after each update. To this change-journalling information, the hashmap code adds deductions made using a modified Heckel algorithm on hash values generated from the line contents.
  • The hardscroll.c module computes an optimum set of scroll, insertion, and deletion operations to make the indices match. It calls _nc_scrolln() in tty_update.c to do those motions.
  • Then tty_update.c goes to work. Its job is to do line-by-line transformations of curscr lines to newscr lines. Its main tool is the routine mvcur() in lib_mvcur.c. This routine does cursor-movement optimization, attempting to get from given screen location A to given location B in the fewest output characters possible.

If you want to work on screen optimizations, you should use the fact that (in the trace-enabled version of the library) enabling the TRACE_TIMES trace level causes a report to be emitted after each screen update giving the elapsed time and a count of characters emitted during the update. You can use this to tell when an update optimization improves efficiency.

In the trace-enabled version of the library, it is also possible to disable and re-enable various optimizations at runtime by tweaking the variable _nc_optimize_enable. See the file include/curses.tail for mask values.