Switch the tty key tree over to an (unbalanced) ternary tree which allows

partial matches to be done (they wait for further data or a timer to expire,
like a naked escape).

Mouse and xterm-style keys still expect to be atomic.

2 files changed, 163 insertions, 88 deletions

diff --git a/usr.bin/tmux/tmux.h b/usr.bin/tmux/tmux.h
index 5b42fce46d9..0c6ebe9ca46 100644
--- a/usr.bin/tmux/tmux.h
+++ b/usr.bin/tmux/tmux.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: tmux.h,v 1.172 2009/11/05 10:44:36 nicm Exp $ */
+/* $OpenBSD: tmux.h,v 1.173 2009/11/05 19:29:41 nicm Exp $ */
 
 /*
  * Copyright (c) 2007 Nicholas Marriott <nicm@users.sourceforge.net>
@@ -936,10 +936,13 @@ ARRAY_DECL(sessions, struct session *);
 
 /* TTY information. */
 struct tty_key {
+	char		 ch;
 	int	 	 key;
-	char		*string;
 
-	RB_ENTRY(tty_key) entry;
+	struct tty_key	*left;
+	struct tty_key	*right;
+
+	struct tty_key	*next;
 };
 
 struct tty_term {
@@ -998,9 +1001,7 @@ struct tty {
 	void		 (*key_callback)(int, struct mouse_event *, void *);
 	void		*key_data;
 	struct event	 key_timer;
-
-	size_t		 ksize;	/* maximum key size */
-	RB_HEAD(tty_keys, tty_key) ktree;
+	struct tty_key	*key_tree;
 };
 
 /* TTY command context and function pointer. */
@@ -1351,8 +1352,6 @@ int		 tty_term_number(struct tty_term *, enum tty_code_code);
 int		 tty_term_flag(struct tty_term *, enum tty_code_code);
 
 /* tty-keys.c */
-int	tty_keys_cmp(struct tty_key *, struct tty_key *);
-RB_PROTOTYPE(tty_keys, tty_key, entry, tty_keys_cmp);
 void	tty_keys_init(struct tty *);
 void	tty_keys_free(struct tty *);
 int	tty_keys_next(struct tty *);
diff --git a/usr.bin/tmux/tty-keys.c b/usr.bin/tmux/tty-keys.c
index 2b766842c7a..68cc01a9957 100644
--- a/usr.bin/tmux/tty-keys.c
+++ b/usr.bin/tmux/tty-keys.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: tty-keys.c,v 1.15 2009/11/05 10:44:36 nicm Exp $ */
+/* $OpenBSD: tty-keys.c,v 1.16 2009/11/05 19:29:41 nicm Exp $ */
 
 /*
  * Copyright (c) 2007 Nicholas Marriott <nicm@users.sourceforge.net>
@@ -26,12 +26,19 @@
 #include "tmux.h"
 
 /*
- * Handle keys input from the outside terminal.
+ * Handle keys input from the outside terminal. tty_keys[] is a base table of
+ * supported keys which are looked up in terminfo(5) and translated into a
+ * ternary tree (a binary tree of binary trees).
  */
 
-void	tty_keys_add(struct tty *, const char *, int);
-void	tty_keys_callback(int, short, void *);
-int	tty_keys_mouse(char *, size_t, size_t *, struct mouse_event *);
+void		tty_keys_add1(struct tty_key **, const char *, int);
+void		tty_keys_add(struct tty *, const char *, int);
+void		tty_keys_free1(struct tty_key *);
+struct tty_key *tty_keys_find1(
+    		    struct tty_key *, const char *, size_t, size_t *);
+struct tty_key *tty_keys_find(struct tty *, const char *, size_t, size_t *);
+void		tty_keys_callback(int, short, void *);
+int		tty_keys_mouse(char *, size_t, size_t *, struct mouse_event *);
 
 struct tty_key_ent {
 	enum tty_code_code	code;
@@ -43,6 +50,11 @@ struct tty_key_ent {
 #define TTYKEY_RAW 0x2
 };
 
+/* 
+ * Default key tables. Those flagged with TTYKEY_RAW are inserted directly,
+ * otherwise they are looked up in terminfo(5). Any keys marked TTYKEY_CTRL
+ * have their last byte twiddled and are inserted as a Ctrl key as well.
+ */
 struct tty_key_ent tty_keys[] = {
 	/* Function keys. */
 	{ TTYC_KF1,	NULL,		KEYC_F1,		TTYKEY_CTRL },
@@ -186,37 +198,56 @@ struct tty_key_ent tty_keys[] = {
 	{ TTYC_KUP7,	NULL,		KEYC_UP|KEYC_ESCAPE|KEYC_CTRL, 0 },
 };
 
-RB_GENERATE(tty_keys, tty_key, entry, tty_keys_cmp);
-
-struct tty_key *tty_keys_find(struct tty *, char *, size_t, size_t *);
-
-int
-tty_keys_cmp(struct tty_key *k1, struct tty_key *k2)
+void
+tty_keys_add(struct tty *tty, const char *s, int key)
 {
-	return (strcmp(k1->string, k2->string));
+	size_t	size;
+
+	if (tty_keys_find(tty, s, strlen(s), &size) == NULL) {
+		log_debug("new key 0x%x: %s", key, s);
+		tty_keys_add1(&tty->key_tree, s, key);
+	}
 }
 
+/* Add next node to the tree. */
 void
-tty_keys_add(struct tty *tty, const char *s, int key)
+tty_keys_add1(struct tty_key **tkp, const char *s, int key)
 {
-	struct tty_key	*tk, *tl;
+	struct tty_key	*tk;
 
-	tk = xmalloc(sizeof *tk);
-	tk->string = xstrdup(s);
-	tk->key = key;
+	/* Allocate a tree entry if there isn't one already. */
+	tk = *tkp;
+	if (tk == NULL) {
+		tk = *tkp = xcalloc(1, sizeof *tk);
+		tk->ch = *s;
+		tk->key = KEYC_NONE;
+	}
+
+	/* Find the next entry. */
+	if (*s == tk->ch) {
+		/* Move forward in string. */
+		s++;
 
-	if ((tl = RB_INSERT(tty_keys, &tty->ktree, tk)) != NULL) {
-		xfree(tk->string);
-		xfree(tk);
-		log_debug("key exists: %s (old %x, new %x)", s, tl->key, key);
- 		return;
+		/* If this is the end of the string, no more is necessary. */
+		if (*s == '\0') {
+			tk->key = key;
+			return;
+		}
+
+		/* Use the child tree for the next character. */
+		tkp = &tk->next;
+	} else { 
+		if (*s < tk->ch)
+			tkp = &tk->left;
+		else if (*s > tk->ch)
+			tkp = &tk->right;
 	}
 
-	if (strlen(tk->string) > tty->ksize)
-		tty->ksize = strlen(tk->string);
-	log_debug("new key %x: size now %zu (%s)", key, tty->ksize, tk->string);
+	/* And recurse to add it. */
+	tty_keys_add1(tkp, s, key);
 }
 
+/* Initialise a key tree from the table. */
 void
 tty_keys_init(struct tty *tty)
 {
@@ -225,9 +256,7 @@ tty_keys_init(struct tty *tty)
 	const char		*s;
 	char			 tmp[64];
 
-	RB_INIT(&tty->ktree);
-
-	tty->ksize = 0;
+	tty->key_tree = NULL;
 	for (i = 0; i < nitems(tty_keys); i++) {
 		tke = &tty_keys[i];
 
@@ -237,12 +266,12 @@ tty_keys_init(struct tty *tty)
 			if (!tty_term_has(tty->term, tke->code))
 				continue;
 			s = tty_term_string(tty->term, tke->code);
-			if (s[0] != '\033' || s[1] == '\0')
-				continue;
 		}
+		if (s[0] != '\033' || s[1] == '\0')
+			continue;
 
 		tty_keys_add(tty, s + 1, tke->key);
-		if (tke->flags & TTYKEY_CTRL) {
+		if (!(tke->flags & TTYKEY_CTRL)) {
 			if (strlcpy(tmp, s, sizeof tmp) >= sizeof tmp)
 				continue;
 			tmp[strlen(tmp) - 1] ^= 0x20;
@@ -251,61 +280,80 @@ tty_keys_init(struct tty *tty)
 	}
 }
 
+/* Free the entire key tree. */
 void
 tty_keys_free(struct tty *tty)
 {
-	struct tty_key	*tk;
+	tty_keys_free1(tty->key_tree);
+}
 
-	while (!RB_EMPTY(&tty->ktree)) {
-		tk = RB_ROOT(&tty->ktree);
-		RB_REMOVE(tty_keys, &tty->ktree, tk);
-		xfree(tk->string);
-		xfree(tk);
-	}
+/* Free a single key. */
+void
+tty_keys_free1(struct tty_key *tk)
+{
+	if (tk->next != NULL)
+		tty_keys_free1(tk->next);
+	if (tk->left != NULL)
+		tty_keys_free1(tk->left);
+	if (tk->right != NULL)
+		tty_keys_free1(tk->right);
+	xfree(tk);
+	
 }
 
+/* Lookup a key in the tree. */
 struct tty_key *
-tty_keys_find(struct tty *tty, char *buf, size_t len, size_t *size)
+tty_keys_find(struct tty *tty, const char *buf, size_t len, size_t *size)
 {
-	struct tty_key	*tk, tl;
-	char		*s;
+	*size = 0;
+	return (tty_keys_find1(tty->key_tree, buf, len, size));
+}
 
-	if (len == 0)
+/* Find the next node. */
+struct tty_key *
+tty_keys_find1(struct tty_key *tk, const char *buf, size_t len, size_t *size)
+{
+	/* If the node is NULL, this is the end of the tree. No match. */
+	if (tk == NULL)
 		return (NULL);
 
-	s = xmalloc(tty->ksize + 1);
-	for (*size = tty->ksize; (*size) > 0; (*size)--) {
-		if ((*size) > len)
-			continue;
-		memcpy(s, buf, *size);
-		s[*size] = '\0';
-
-		log_debug2("looking for key: %s", s);
+	/* Pick the next in the sequence. */
+	if (tk->ch == *buf) {
+		/* Move forward in the string. */
+		buf++; len--;
+		(*size)++;
 
-		tl.string = s;
-		tk = RB_FIND(tty_keys, &tty->ktree, &tl);
-		if (tk != NULL) {
-			log_debug2("got key: 0x%x", tk->key);
-			xfree(s);
+		/* At the end of the string, return the current node. */
+		if (len == 0)
 			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;
 	}
-	xfree(s);
 
-	return (NULL);
+	/* Move to the next in the tree. */
+	return (tty_keys_find1(tk, buf, len, size));
 }
 
+/*
+ * Process at least one key in the buffer and invoke tty->key_callback. Return
+ * 1 if there are no further keys, or 0 if there is more in the buffer.
+ */
 int
 tty_keys_next(struct tty *tty)
 {
 	struct tty_key		*tk;
 	struct timeval		 tv;
 	struct mouse_event	 mouse;
-	char			*buf;
+	char			*buf, *ptr;
 	size_t			 len, size;
 	cc_t			 bspace;
 	int			 key;
-	u_char			 ch;
 
 	buf = EVBUFFER_DATA(tty->event->input);
 	len = EVBUFFER_LENGTH(tty->event->input);
@@ -315,8 +363,8 @@ tty_keys_next(struct tty *tty)
 
 	/* If a normal key, return it. */
 	if (*buf != '\033') {
-		bufferevent_read(tty->event, &ch, 1);
-		key = ch;
+		key = *buf;
+		evbuffer_drain(tty->event->input, 1);
 
 		/*
 		 * Check for backspace key using termios VERASE - the terminfo
@@ -326,29 +374,28 @@ tty_keys_next(struct tty *tty)
 		bspace = tty->tio.c_cc[VERASE];
 		if (bspace != _POSIX_VDISABLE && key == bspace)
 			key = KEYC_BSPACE;
-		goto found;
+		goto handle_key;
 	}
 
 	/* Look for matching key string and return if found. */
 	tk = tty_keys_find(tty, buf + 1, len - 1, &size);
 	if (tk != NULL) {
-		evbuffer_drain(tty->event->input, size + 1);
 		key = tk->key;
-		goto found;
+		goto found_key;
 	}
 
 	/* Not found. Is this a mouse key press? */
 	key = tty_keys_mouse(buf, len, &size, &mouse);
 	if (key != KEYC_NONE) {
 		evbuffer_drain(tty->event->input, size);
-		goto found;
+		goto handle_key;
 	}
 
 	/* Not found. Try to parse a key with an xterm-style modifier. */
 	key = xterm_keys_find(buf, len, &size);
 	if (key != KEYC_NONE) {
 		evbuffer_drain(tty->event->input, size);
-		goto found;
+		goto handle_key;
 	}
 
 	/* Skip the escape. */
@@ -357,32 +404,37 @@ tty_keys_next(struct tty *tty)
 
 	/* Is there a normal key following? */
 	if (len != 0 && *buf != '\033') {
-		evbuffer_drain(tty->event->input, 1);
-		bufferevent_read(tty->event, &ch, 1);
-		key = ch | KEYC_ESCAPE;
-		goto found;
+		key = *buf | KEYC_ESCAPE;
+		evbuffer_drain(tty->event->input, 2);
+		goto handle_key;
 	}
 
 	/* Or a key string? */
 	if (len > 1) {
 		tk = tty_keys_find(tty, buf + 1, len - 1, &size);
 		if (tk != NULL) {
-			evbuffer_drain(tty->event->input, size + 2);
 			key = tk->key | KEYC_ESCAPE;
-			goto found;
+			size++;	/* include escape */
+			goto found_key;
 		}
 	}
 
+	/* Escape and then nothing useful - fall through. */
+
+partial_key:
 	/*
-	 * Escape but no key string. If have, already seen an escape, then the
+	 * Escape but no key string. If have already seen an escape, then the
 	 * timer must have expired, so give up waiting and send the escape.
 	 */
 	if (tty->flags & TTY_ESCAPE) {
 		evbuffer_drain(tty->event->input, 1);
 		key = '\033';
-		goto found;
+		goto handle_key;
 	}
 
+	/* Fall through to start the timer. */
+
+start_timer:
 	/* Start the timer and wait for expiry or more data. */
 	tv.tv_sec = 0;
 	tv.tv_usec = ESCAPE_PERIOD * 1000L;
@@ -394,22 +446,45 @@ tty_keys_next(struct tty *tty)
 	tty->flags |= TTY_ESCAPE;
 	return (0);
 
-found:
-	evtimer_del(&tty->key_timer);
+found_key:
+	if (tk->next != NULL) {
+		/* Partial key. Start the timer if not already expired. */
+		if (!(tty->flags & TTY_ESCAPE))
+			goto start_timer;
+
+		/* Otherwise, if no key, send the escape alone. */
+		if (tk->key == KEYC_NONE)
+			goto partial_key;
+
+		/* Or fall through to send the partial key found. */
+	}
+	evbuffer_drain(tty->event->input, size + 1);
+
+	goto handle_key;
+
+handle_key:
+ 	evtimer_del(&tty->key_timer);
+
 	tty->key_callback(key, &mouse, tty->key_data);
+
 	tty->flags &= ~TTY_ESCAPE;
 	return (1);
 }
 
+/* Key timer callback. */
 void
 tty_keys_callback(unused int fd, unused short events, void *data)
 {
 	struct tty	*tty = data;
 
-	if (tty->flags & TTY_ESCAPE)
-		tty_keys_next(tty);
+	if (!(tty->flags & TTY_ESCAPE))
+		return;
+
+	while (tty_keys_next(tty))
+		;
 }
 
+/* Handle mouse key input. */
 int
 tty_keys_mouse(char *buf, size_t len, size_t *size, struct mouse_event *m)
 {
@@ -418,11 +493,12 @@ tty_keys_mouse(char *buf, size_t len, size_t *size, struct mouse_event *m)
 	 * buttons, X and Y, all based at 32 with 1,1 top-left.
 	 */
 
-	log_debug("mouse input is: %.*s", (int) len, buf);
 	if (len != 6 || memcmp(buf, "\033[M", 3) != 0)
 		return (KEYC_NONE);
 	*size = 6;
 
+	log_debug("mouse input is: %.*s", (int) len, buf);
+
 	m->b = buf[3];
 	m->x = buf[4];
 	m->y = buf[5];