tmux Parses Escape Sequences Fast

The single hottest path in tmux is not the redraw — it is the parser. Every byte that any program in any pane produces goes through tmux’s own VT parser, and a yes or a cat of a large file will push megabytes through it per second.

This article is about how that parser is built: a range-compressed state machine with a one-entry transition cache, a binary search over the CSI command table, a character trie for the other direction (terminal key sequences), and a Unicode width cache.

The parser: a state machine with tables

input.c is about 3800 lines, and the core of it is a table-driven state machine in the style of a real VT parser. There are ten states: ground, escape enter, escape intermediate, CSI enter, CSI parameter, CSI intermediate, OSC, DCS, APC, and the string-consumption states.

Each state has a list of transitions, and each transition is a range of bytes:

    c
    
  
struct input_transition {
	int			first;
	int			last;

	const struct input_state	*state;
	int			(*handler)(struct input_ctx *ictx);
};

The reason for ranges rather than a 256-entry table per state is memory: a transition is {int, int, pointer, pointer} — 24 bytes on 64-bit — and a full table would be 6 KB per state. With ranges, a state might have five transitions.

The parser core:

    c
    
  
/* Parse data. */
static void
input_parse(struct input_ctx *ictx, const u_char *buf, size_t len)
{
	struct screen_write_ctx		*sctx = &ictx->ctx;
	const struct input_state	*state = NULL;
	const struct input_transition	*itr = NULL;
	size_t				 off = 0;

	/* Parse the input. */
	while (off < len) {
		ictx->ch = buf[off++];

		/* Find the transition. */
		if (ictx->state != state ||
		    itr == NULL ||
		    ictx->ch < itr->first ||
		    ictx->ch > itr->last) {
			itr = ictx->state->transitions;
			while (itr->first != -1 && itr->last != -1) {
				if (ictx->ch >= itr->first &&
				    ictx->ch <= itr->last)
					break;
				itr++;
			}
			if (itr->first == -1 || itr->last == -1) {
				/* No transition? Eh? */
				fatalx("no transition from state");
			}
		}
		state = ictx->state;

The trick is the itr cache. The state machine remembers the transition it used last time, and only rescans the table if:

the state changed, or
the character is outside the range of the cached transition.

For a run of printable ASCII in the ground state, the first character scans the table and every subsequent character hits the cached transition. The scan is a linear walk over ranges, which for the ground state is a handful of comparisons.

The collect-buffer optimisation

The comment above screen_write_collect_end() is a nice piece of engineering honesty:

    c
    
  
		/*
		 * Any state except print stops the current collection. This is
		 * an optimization to avoid checking if the attributes have
		 * changed for every character. It will stop unnecessarily for
		 * sequences that don't make a terminal change, but they should
		 * be the minority.
		 */
		if (itr->handler != input_print)
			screen_write_collect_end(sctx);

The idea: tmux batches consecutive printable characters into a “collect buffer” so that they can be written to the grid in one go. But collecting requires checking, for each character, whether the attributes have changed — which is the expensive part.

Instead of checking, the parser uses a proxy: if the transition is not the plain input_print handler, then the sequence is doing something (setting a colour, moving the cursor) and the collection is ended. That is a conservative over-approximation — a sequence that does not actually change attributes still ends the collection — but plain text is by far the common case, so the fast path stays fast.

Binary search over the CSI table

Once the parser reaches the CSI dispatch point, it has a final byte and a parameter string, and it needs to find the handler. The table is sorted and searched with bsearch():

    c
    
  
	entry = bsearch(ictx, input_csi_table, nitems(input_csi_table),
	    sizeof input_csi_table[0], input_table_compare);
	if (entry == NULL) {
		log_debug("%s: unknown '%c'", __func__, ictx->ch);
		return (0);
	}

with the comparator:

    c
    
  
static int
input_table_compare(const void *key, const void *value)
{
	const struct input_ctx		*ictx = key;
	const struct input_table_entry	*entry = value;
	if (ictx->ch != entry->ch)
		return (ictx->ch - entry->ch);
	return (strcmp(ictx->interm_buf, entry->interm));
}

The comparison is by final byte first, then by the intermediate string — which is how CSI ? ... h (private mode) is distinguished from CSI ... h (set mode). The same pattern is used for the ESC dispatch table.

Bounded buffers

The parser context has fixed-size scratch buffers for the small parts of a sequence:

    c
    
  
	u_char				interm_buf[4];
	size_t				interm_len;

	u_char				param_buf[64];
	size_t				param_len;

#define INPUT_BUF_START 32
	u_char			       *input_buf;
	size_t				input_len;
	size_t				input_space;
	enum input_end_type		input_end;

	struct input_param		param_list[24];
	u_int				param_list_len;

The intermediate string of an escape sequence is at most 4 bytes and the parameter string at most 64. A sequence that exceeds them is discarded, not buffered — an important denial-of-service defence, since a hostile program inside a pane could otherwise send an endless CSI 111111111... and make tmux allocate without bound.

The one growable buffer is the OSC/DCS payload, and it is bounded too:

    c
    
  
	while (ictx->input_len + 1 >= available) {
		available *= 2;
		if (available > input_buffer_size) {
			ictx->flags |= INPUT_DISCARD;
			return (0);
		}
	}

input_buffer_size defaults to INPUT_BUF_DEFAULT_SIZE (1 MB) and is configurable with the input-buffer-size option. When the buffer is discarded, the parser resets and waits for the next sequence — the rest of the garbage is dropped.

The buffer is also shrunk back when the parser returns to the ground state, so one huge OSC does not permanently inflate memory.

The other direction: terminal key sequences

The parser above handles bytes flowing out of a program. The reverse direction — bytes coming from the user’s terminal, which may be an escape sequence rather than a keystroke — is handled by tty-keys.c.

The difficulty is that the terminal sends a byte stream and tmux has to decide whether ESC [ A is the up arrow, or the Escape key followed by [ and A. The answer depends on timing and on what tmux asked the terminal.

tmux stores terminal key sequences in a character trie, where each node has up to three children:

    c
    
  
/* A key tree entry. */
struct tty_key {
	char		 ch;
	key_code	 key;

	struct tty_key	*left;
	struct tty_key	*right;

	struct tty_key	*next;
};

The lookup is a simple binary-tree walk with a “next” pointer for the sequence continuation:

    c
    
  
/* Find the next node. */
static struct tty_key *
tty_keys_find1(struct tty_key *tk, const char *buf, size_t len, size_t *size)
{
	/* If no data, no match. */
	if (len == 0)
		return (NULL);

	/* If the node is NULL, this is the end of the tree. No match. */
	if (tk == NULL)
		return (NULL);

	/* Pick the next in the sequence. */
	if (tk->ch == *buf) {
		/* Move forward in the string. */
		buf++; len--;
		(*size)++;

		/* At the end of the string, return the current node. */
		if (len == 0 || (tk->next == NULL && tk->key != KEYC_UNKNOWN))
			return (tk);

		/* Move into the next tree for the following character. */
		tk = tk->next;
	} else {
		if (*buf < tk->ch)
			tk = tk->left;
		else if (*buf > tk->ch)
			tk = tk->right;
	}

	/* Move to the next in the tree. */
	return (tty_keys_find1(tk, buf, len, size));
}

The left/right pointers are a binary search tree keyed on the byte; the next pointer continues the sequence to the next trie. So the structure is a tree of trees, and the lookup is O(log n) per byte with no allocation.

Terminal replies (device attributes, colour reports, kitty graphics queries) are matched before the general key tree, via a small table of function pointers:

    c
    
  
/* Terminal replies, in the order they are checked. */
static const struct {
	key_code	key;
	int	      (*fn)(struct tty *, const char *, size_t, size_t *, int);
} tty_keys_replies[] = {
	{ KEYC_REPORT_CLIPBOARD, tty_keys_clipboard },
	{ KEYC_REPORT_SYNC, tty_keys_sync },
	{ KEYC_REPORT_DA, tty_keys_device_attributes },
	{ KEYC_REPORT_DA2, tty_keys_device_attributes2 },
	{ KEYC_REPORT_XDA, tty_keys_extended_device_attributes },
	{ KEYC_REPORT_COLOURS, tty_keys_colours1 },
	{ KEYC_REPORT_PALETTE, tty_keys_palette },
	{ KEYC_REPORT_WINSZ, tty_keys_winsz },

That ordering matters: a device attributes reply is ESC [ ? 6 2 ; 1 6 c, which would otherwise be an unknown key sequence.

The escape timeout

The ambiguity between Escape and a sequence prefix is resolved with a timer, and tmux’s timer is adaptive:

    c
    
  
	/* Get the time period. */
	delay = options_get_number(global_options, "escape-time");
	if (delay == 0)
		delay = 1;
	if ((tty->flags & TTY_BRACKETPASTE) &&
	    tty_keys_partial_paste_end(buf, len)) {
		log_debug("%s: increasing delay (partial paste end)", c->name);
		if (delay < 500)
			delay = 500;
	}
	if (tty->flags & (TTY_WAITFG|TTY_WAITBG) ||
	    tty->flags & (TTY_OSC52QUERY|TTY_WINSIZEQUERY) ||
	    (tty->flags & TTY_ALL_REQUEST_FLAGS) != TTY_ALL_REQUEST_FLAGS ||
	    !TAILQ_EMPTY(&c->input_requests)) {
		log_debug("%s: increasing delay (active query)", c->name);
		if (delay < 500)
			delay = 500;
	}

and then, in two specific situations, the delay is raised to at least 500 ms:

when the buffer ends with a partial bracketed paste end sequence (ESC [ 201 ~), and
when tmux has an outstanding terminal query and is waiting for a reply.

The second case is the interesting one. If tmux has just asked the terminal for its device attributes and the user presses Escape, the reply and the keystroke arrive in the same stream. Waiting a little longer makes it much more likely that the reply is consumed as a reply rather than being misinterpreted as a Meta-prefixed key.

The exponential-ish retry is also handled: when the timer expires without a match, the buffer is re-parsed with “no longer ambiguous” semantics, so a lone Escape eventually arrives as the Escape key.

There is a matching problem on the reply side: an Escape immediately before a terminal reply must not be swallowed as Meta. That has its own regression test (regress/tty-keys-reply-escape.sh).

UTF-8 and the width cache

The last hot path is Unicode. Decoding UTF-8 incrementally is the easy part; the hard part is that wcwidth() is not cheap, and a screen full of emoji would call it thousands of times per second.

tmux keeps a cache of codepoint widths in a red-black tree:

    c
    
  
struct utf8_width_item {
	wchar_t				wc;
	u_int				width;
	int				allocated;

	RB_ENTRY(utf8_width_item)	entry;
};

seeded with a static table of a few hundred known cases:

    c
    
  
static struct utf8_width_item utf8_default_width_cache[] = {
	{ .wc = 0x0270A, .width = 2 },
	{ .wc = 0x0270B, .width = 2 },
	{ .wc = 0x1F1E6, .width = 1 },
	{ .wc = 0x1F1E7, .width = 1 },
	{ .wc = 0x1F1E8, .width = 1 },

The lookup happens before wcwidth() is called at all:

    c
    
  
/* Get width of Unicode character. */
static enum utf8_state
utf8_width(struct utf8_data *ud, int *width)
{
	struct utf8_width_item	*uw;
	wchar_t			 wc;

	if (utf8_towc(ud, &wc) != UTF8_DONE)
		return (UTF8_ERROR);
	uw = utf8_find_in_width_cache(wc);
	if (uw != NULL) {
		*width = uw->width;
		log_debug("cached width for %08X is %d", (u_int)wc, *width);
		return (UTF8_DONE);
	}
#ifdef HAVE_UTF8PROC
	*width = utf8proc_wcwidth(wc);

There are similar caches for the codepoint-to-utf8_data conversion (utf8_data_tree and utf8_index_tree), so a repeated character does not have to be re-decoded.

The width is also packed into the character word itself rather than kept in a separate structure:

    c
    
  
#define UTF8_GET_SIZE(wc) ...
#define UTF8_GET_WIDTH(wc) ...
#define UTF8_SET_SIZE(wc, sz) ...
#define UTF8_SET_WIDTH(wc, wd) ...

so the width is available without dereferencing anything.

Why the widths are so complicated

The width rules are a mess of Unicode special cases, and tmux handles several of them explicitly:

Combining marks (utf8-combined.c) — a combining character is rendered on top of the previous cell, and does not advance the cursor.
Variation selectors — VS16 (U+FE0F) requests the emoji presentation, which is usually double-width. tmux has an option variation-selector-always-wide because the correct behaviour depends on the outer terminal, which tmux cannot always detect.
Regional indicators (flag emoji) — a pair of regional indicator symbols is one flag, so they combine.
Emoji modifiers (skin tones) — combine with the preceding emoji.
Private use area — where Powerline glyphs live, which have “ambiguous” width. The bundled utf8proc shim says:

    c
    
  
	if (cat == UTF8PROC_CATEGORY_CO) {
		/* The private use category is where powerline and similar
		 * codepoints are stored, they have "ambiguous" width - use 1. */
		return (1);
	}

The lesson

There is no clever trick in the tmux parser. It is a state machine with a transition cache, a binary search, a trie, and a width cache — four small, boring optimisations, each of which removes work from the innermost loop.

What makes it worth writing down is the shape of the optimisation. Each one replaces a check with a cheaper check:

Expensive	Cheap replacement
256-entry transition table per state	ranges + a one-entry cache
linear scan of the CSI table	`bsearch()`
`wcwidth()` per character	red-black tree of known widths
linear scan of key sequences	binary search tree per node
attribute check per collected character	“is this the print handler?”

That is the whole story of tmux’s input performance: never do the expensive check when a cheaper one is sufficient, and make the cheap one the default path.