1/*-
2 * Copyright (c) 1992, 1993
3 *	The Regents of the University of California.  All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Christos Zoulas of Cornell University.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 *    notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 *    notice, this list of conditions and the following disclaimer in the
15 *    documentation and/or other materials provided with the distribution.
16 * 3. Neither the name of the University nor the names of its contributors
17 *    may be used to endorse or promote products derived from this software
18 *    without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 *
32 *	$NetBSD: key.c,v 1.20 2009/02/15 21:55:23 christos Exp $
33 */
34
35#if !defined(lint) && !defined(SCCSID)
36static char sccsid[] = "@(#)key.c	8.1 (Berkeley) 6/4/93";
37#endif /* not lint && not SCCSID */
38#include <sys/cdefs.h>
39__FBSDID("$FreeBSD$");
40
41/*
42 * key.c: This module contains the procedures for maintaining
43 *	  the extended-key map.
44 *
45 *      An extended-key (key) is a sequence of keystrokes introduced
46 *	with a sequence introducer and consisting of an arbitrary
47 *	number of characters.  This module maintains a map (the el->el_key.map)
48 *	to convert these extended-key sequences into input strs
49 *	(XK_STR), editor functions (XK_CMD), or unix commands (XK_EXE).
50 *
51 *      Warning:
52 *	  If key is a substr of some other keys, then the longer
53 *	  keys are lost!!  That is, if the keys "abcd" and "abcef"
54 *	  are in el->el_key.map, adding the key "abc" will cause the first two
55 *	  definitions to be lost.
56 *
57 *      Restrictions:
58 *      -------------
59 *      1) It is not possible to have one key that is a
60 *	   substr of another.
61 */
62#include <string.h>
63#include <stdlib.h>
64
65#include "el.h"
66
67/*
68 * The Nodes of the el->el_key.map.  The el->el_key.map is a linked list
69 * of these node elements
70 */
71struct key_node_t {
72	char		ch;		/* single character of key 	 */
73	int		type;		/* node type			 */
74	key_value_t	val;		/* command code or pointer to str,  */
75					/* if this is a leaf 		 */
76	struct key_node_t *next;	/* ptr to next char of this key  */
77	struct key_node_t *sibling;	/* ptr to another key with same prefix*/
78};
79
80private int		 node_trav(EditLine *, key_node_t *, char *,
81    key_value_t *);
82private int		 node__try(EditLine *, key_node_t *, const char *,
83    key_value_t *, int);
84private key_node_t	*node__get(int);
85private void		 node__free(key_node_t *);
86private void		 node__put(EditLine *, key_node_t *);
87private int		 node__delete(EditLine *, key_node_t **, const char *);
88private int		 node_lookup(EditLine *, const char *, key_node_t *,
89    size_t);
90private int		 node_enum(EditLine *, key_node_t *, size_t);
91
92#define	KEY_BUFSIZ	EL_BUFSIZ
93
94
95/* key_init():
96 *	Initialize the key maps
97 */
98protected int
99key_init(EditLine *el)
100{
101
102	el->el_key.buf = (char *) el_malloc(KEY_BUFSIZ);
103	if (el->el_key.buf == NULL)
104		return (-1);
105	el->el_key.map = NULL;
106	key_reset(el);
107	return (0);
108}
109
110/* key_end():
111 *	Free the key maps
112 */
113protected void
114key_end(EditLine *el)
115{
116
117	el_free((ptr_t) el->el_key.buf);
118	el->el_key.buf = NULL;
119	node__free(el->el_key.map);
120}
121
122
123/* key_map_cmd():
124 *	Associate cmd with a key value
125 */
126protected key_value_t *
127key_map_cmd(EditLine *el, int cmd)
128{
129
130	el->el_key.val.cmd = (el_action_t) cmd;
131	return (&el->el_key.val);
132}
133
134
135/* key_map_str():
136 *	Associate str with a key value
137 */
138protected key_value_t *
139key_map_str(EditLine *el, char *str)
140{
141
142	el->el_key.val.str = str;
143	return (&el->el_key.val);
144}
145
146
147/* key_reset():
148 *	Takes all nodes on el->el_key.map and puts them on free list.  Then
149 *	initializes el->el_key.map with arrow keys
150 *	[Always bind the ansi arrow keys?]
151 */
152protected void
153key_reset(EditLine *el)
154{
155
156	node__put(el, el->el_key.map);
157	el->el_key.map = NULL;
158	return;
159}
160
161
162/* key_get():
163 *	Calls the recursive function with entry point el->el_key.map
164 *      Looks up *ch in map and then reads characters until a
165 *      complete match is found or a mismatch occurs. Returns the
166 *      type of the match found (XK_STR, XK_CMD, or XK_EXE).
167 *      Returns NULL in val.str and XK_STR for no match.
168 *      The last character read is returned in *ch.
169 */
170protected int
171key_get(EditLine *el, char *ch, key_value_t *val)
172{
173
174	return (node_trav(el, el->el_key.map, ch, val));
175}
176
177
178/* key_add():
179 *      Adds key to the el->el_key.map and associates the value in val with it.
180 *      If key is already is in el->el_key.map, the new code is applied to the
181 *      existing key. Ntype specifies if code is a command, an
182 *      out str or a unix command.
183 */
184protected void
185key_add(EditLine *el, const char *key, key_value_t *val, int ntype)
186{
187
188	if (key[0] == '\0') {
189		(void) fprintf(el->el_errfile,
190		    "key_add: Null extended-key not allowed.\n");
191		return;
192	}
193	if (ntype == XK_CMD && val->cmd == ED_SEQUENCE_LEAD_IN) {
194		(void) fprintf(el->el_errfile,
195		    "key_add: sequence-lead-in command not allowed\n");
196		return;
197	}
198	if (el->el_key.map == NULL)
199		/* tree is initially empty.  Set up new node to match key[0] */
200		el->el_key.map = node__get(key[0]);
201			/* it is properly initialized */
202
203	/* Now recurse through el->el_key.map */
204	(void) node__try(el, el->el_key.map, key, val, ntype);
205	return;
206}
207
208
209/* key_clear():
210 *
211 */
212protected void
213key_clear(EditLine *el, el_action_t *map, const char *in)
214{
215
216	if ((map[(unsigned char)*in] == ED_SEQUENCE_LEAD_IN) &&
217	    ((map == el->el_map.key &&
218	    el->el_map.alt[(unsigned char)*in] != ED_SEQUENCE_LEAD_IN) ||
219	    (map == el->el_map.alt &&
220	    el->el_map.key[(unsigned char)*in] != ED_SEQUENCE_LEAD_IN)))
221		(void) key_delete(el, in);
222}
223
224
225/* key_delete():
226 *      Delete the key and all longer keys staring with key, if
227 *      they exists.
228 */
229protected int
230key_delete(EditLine *el, const char *key)
231{
232
233	if (key[0] == '\0') {
234		(void) fprintf(el->el_errfile,
235		    "key_delete: Null extended-key not allowed.\n");
236		return (-1);
237	}
238	if (el->el_key.map == NULL)
239		return (0);
240
241	(void) node__delete(el, &el->el_key.map, key);
242	return (0);
243}
244
245
246/* key_print():
247 *	Print the binding associated with key key.
248 *	Print entire el->el_key.map if null
249 */
250protected void
251key_print(EditLine *el, const char *key)
252{
253
254	/* do nothing if el->el_key.map is empty and null key specified */
255	if (el->el_key.map == NULL && *key == 0)
256		return;
257
258	el->el_key.buf[0] = '"';
259	if (node_lookup(el, key, el->el_key.map, 1) <= -1)
260		/* key is not bound */
261		(void) fprintf(el->el_errfile, "Unbound extended key \"%s\"\n",
262		    key);
263	return;
264}
265
266
267/* node_trav():
268 *	recursively traverses node in tree until match or mismatch is
269 * 	found.  May read in more characters.
270 */
271private int
272node_trav(EditLine *el, key_node_t *ptr, char *ch, key_value_t *val)
273{
274
275	if (ptr->ch == *ch) {
276		/* match found */
277		if (ptr->next) {
278			/* key not complete so get next char */
279			if (el_getc(el, ch) != 1) {	/* if EOF or error */
280				val->cmd = ED_END_OF_FILE;
281				return (XK_CMD);
282				/* PWP: Pretend we just read an end-of-file */
283			}
284			return (node_trav(el, ptr->next, ch, val));
285		} else {
286			*val = ptr->val;
287			if (ptr->type != XK_CMD)
288				*ch = '\0';
289			return (ptr->type);
290		}
291	} else {
292		/* no match found here */
293		if (ptr->sibling) {
294			/* try next sibling */
295			return (node_trav(el, ptr->sibling, ch, val));
296		} else {
297			/* no next sibling -- mismatch */
298			val->str = NULL;
299			return (XK_STR);
300		}
301	}
302}
303
304
305/* node__try():
306 * 	Find a node that matches *str or allocate a new one
307 */
308private int
309node__try(EditLine *el, key_node_t *ptr, const char *str, key_value_t *val, int ntype)
310{
311
312	if (ptr->ch != *str) {
313		key_node_t *xm;
314
315		for (xm = ptr; xm->sibling != NULL; xm = xm->sibling)
316			if (xm->sibling->ch == *str)
317				break;
318		if (xm->sibling == NULL)
319			xm->sibling = node__get(*str);	/* setup new node */
320		ptr = xm->sibling;
321	}
322	if (*++str == '\0') {
323		/* we're there */
324		if (ptr->next != NULL) {
325			node__put(el, ptr->next);
326				/* lose longer keys with this prefix */
327			ptr->next = NULL;
328		}
329		switch (ptr->type) {
330		case XK_CMD:
331		case XK_NOD:
332			break;
333		case XK_STR:
334		case XK_EXE:
335			if (ptr->val.str)
336				el_free((ptr_t) ptr->val.str);
337			break;
338		default:
339			EL_ABORT((el->el_errfile, "Bad XK_ type %d\n",
340			    ptr->type));
341			break;
342		}
343
344		switch (ptr->type = ntype) {
345		case XK_CMD:
346			ptr->val = *val;
347			break;
348		case XK_STR:
349		case XK_EXE:
350			if ((ptr->val.str = el_strdup(val->str)) == NULL)
351				return -1;
352			break;
353		default:
354			EL_ABORT((el->el_errfile, "Bad XK_ type %d\n", ntype));
355			break;
356		}
357	} else {
358		/* still more chars to go */
359		if (ptr->next == NULL)
360			ptr->next = node__get(*str);	/* setup new node */
361		(void) node__try(el, ptr->next, str, val, ntype);
362	}
363	return (0);
364}
365
366
367/* node__delete():
368 *	Delete node that matches str
369 */
370private int
371node__delete(EditLine *el, key_node_t **inptr, const char *str)
372{
373	key_node_t *ptr;
374	key_node_t *prev_ptr = NULL;
375
376	ptr = *inptr;
377
378	if (ptr->ch != *str) {
379		key_node_t *xm;
380
381		for (xm = ptr; xm->sibling != NULL; xm = xm->sibling)
382			if (xm->sibling->ch == *str)
383				break;
384		if (xm->sibling == NULL)
385			return (0);
386		prev_ptr = xm;
387		ptr = xm->sibling;
388	}
389	if (*++str == '\0') {
390		/* we're there */
391		if (prev_ptr == NULL)
392			*inptr = ptr->sibling;
393		else
394			prev_ptr->sibling = ptr->sibling;
395		ptr->sibling = NULL;
396		node__put(el, ptr);
397		return (1);
398	} else if (ptr->next != NULL &&
399	    node__delete(el, &ptr->next, str) == 1) {
400		if (ptr->next != NULL)
401			return (0);
402		if (prev_ptr == NULL)
403			*inptr = ptr->sibling;
404		else
405			prev_ptr->sibling = ptr->sibling;
406		ptr->sibling = NULL;
407		node__put(el, ptr);
408		return (1);
409	} else {
410		return (0);
411	}
412}
413
414
415/* node__put():
416 *	Puts a tree of nodes onto free list using free(3).
417 */
418private void
419node__put(EditLine *el, key_node_t *ptr)
420{
421	if (ptr == NULL)
422		return;
423
424	if (ptr->next != NULL) {
425		node__put(el, ptr->next);
426		ptr->next = NULL;
427	}
428	node__put(el, ptr->sibling);
429
430	switch (ptr->type) {
431	case XK_CMD:
432	case XK_NOD:
433		break;
434	case XK_EXE:
435	case XK_STR:
436		if (ptr->val.str != NULL)
437			el_free((ptr_t) ptr->val.str);
438		break;
439	default:
440		EL_ABORT((el->el_errfile, "Bad XK_ type %d\n", ptr->type));
441		break;
442	}
443	el_free((ptr_t) ptr);
444}
445
446
447/* node__get():
448 *	Returns pointer to a key_node_t for ch.
449 */
450private key_node_t *
451node__get(int ch)
452{
453	key_node_t *ptr;
454
455	ptr = (key_node_t *) el_malloc((size_t) sizeof(key_node_t));
456	if (ptr == NULL)
457		return NULL;
458	ptr->ch = ch;
459	ptr->type = XK_NOD;
460	ptr->val.str = NULL;
461	ptr->next = NULL;
462	ptr->sibling = NULL;
463	return (ptr);
464}
465
466private void
467node__free(key_node_t *k)
468{
469	if (k == NULL)
470		return;
471	node__free(k->sibling);
472	node__free(k->next);
473	el_free((ptr_t) k);
474}
475
476/* node_lookup():
477 *	look for the str starting at node ptr.
478 *	Print if last node
479 */
480private int
481node_lookup(EditLine *el, const char *str, key_node_t *ptr, size_t cnt)
482{
483	size_t ncnt;
484
485	if (ptr == NULL)
486		return (-1);	/* cannot have null ptr */
487
488	if (*str == 0) {
489		/* no more chars in str.  node_enum from here. */
490		(void) node_enum(el, ptr, cnt);
491		return (0);
492	} else {
493		/* If match put this char into el->el_key.buf.  Recurse */
494		if (ptr->ch == *str) {
495			/* match found */
496			ncnt = key__decode_char(el->el_key.buf,
497			    (size_t)KEY_BUFSIZ, cnt,
498			    (unsigned char) ptr->ch);
499			if (ptr->next != NULL)
500				/* not yet at leaf */
501				return (node_lookup(el, str + 1, ptr->next,
502				    ncnt + 1));
503			else {
504			    /* next node is null so key should be complete */
505				if (str[1] == 0) {
506					el->el_key.buf[ncnt + 1] = '"';
507					el->el_key.buf[ncnt + 2] = '\0';
508					key_kprint(el, el->el_key.buf,
509					    &ptr->val, ptr->type);
510					return (0);
511				} else
512					return (-1);
513					/* mismatch -- str still has chars */
514			}
515		} else {
516			/* no match found try sibling */
517			if (ptr->sibling)
518				return (node_lookup(el, str, ptr->sibling,
519				    cnt));
520			else
521				return (-1);
522		}
523	}
524}
525
526
527/* node_enum():
528 *	Traverse the node printing the characters it is bound in buffer
529 */
530private int
531node_enum(EditLine *el, key_node_t *ptr, size_t cnt)
532{
533	size_t ncnt;
534
535	if (cnt >= KEY_BUFSIZ - 5) {	/* buffer too small */
536		el->el_key.buf[++cnt] = '"';
537		el->el_key.buf[++cnt] = '\0';
538		(void) fprintf(el->el_errfile,
539		    "Some extended keys too long for internal print buffer");
540		(void) fprintf(el->el_errfile, " \"%s...\"\n", el->el_key.buf);
541		return (0);
542	}
543	if (ptr == NULL) {
544#ifdef DEBUG_EDIT
545		(void) fprintf(el->el_errfile,
546		    "node_enum: BUG!! Null ptr passed\n!");
547#endif
548		return (-1);
549	}
550	/* put this char at end of str */
551	ncnt = key__decode_char(el->el_key.buf, (size_t)KEY_BUFSIZ, cnt,
552	    (unsigned char)ptr->ch);
553	if (ptr->next == NULL) {
554		/* print this key and function */
555		el->el_key.buf[ncnt + 1] = '"';
556		el->el_key.buf[ncnt + 2] = '\0';
557		key_kprint(el, el->el_key.buf, &ptr->val, ptr->type);
558	} else
559		(void) node_enum(el, ptr->next, ncnt + 1);
560
561	/* go to sibling if there is one */
562	if (ptr->sibling)
563		(void) node_enum(el, ptr->sibling, cnt);
564	return (0);
565}
566
567
568/* key_kprint():
569 *	Print the specified key and its associated
570 *	function specified by val
571 */
572protected void
573key_kprint(EditLine *el, const char *key, key_value_t *val, int ntype)
574{
575	el_bindings_t *fp;
576	char unparsbuf[EL_BUFSIZ];
577	static const char fmt[] = "%-15s->  %s\n";
578
579	if (val != NULL)
580		switch (ntype) {
581		case XK_STR:
582		case XK_EXE:
583			(void) key__decode_str(val->str, unparsbuf,
584			    sizeof(unparsbuf),
585			    ntype == XK_STR ? "\"\"" : "[]");
586			(void) fprintf(el->el_outfile, fmt, key, unparsbuf);
587			break;
588		case XK_CMD:
589			for (fp = el->el_map.help; fp->name; fp++)
590				if (val->cmd == fp->func) {
591					(void) fprintf(el->el_outfile, fmt,
592					    key, fp->name);
593					break;
594				}
595#ifdef DEBUG_KEY
596			if (fp->name == NULL)
597				(void) fprintf(el->el_outfile,
598				    "BUG! Command not found.\n");
599#endif
600
601			break;
602		default:
603			EL_ABORT((el->el_errfile, "Bad XK_ type %d\n", ntype));
604			break;
605		}
606	else
607		(void) fprintf(el->el_outfile, fmt, key, "no input");
608}
609
610
611#define ADDC(c) \
612	if (b < eb) \
613		*b++ = c; \
614	else \
615		b++
616/* key__decode_char():
617 *	Put a printable form of char in buf.
618 */
619protected size_t
620key__decode_char(char *buf, size_t cnt, size_t off, int ch)
621{
622	char *sb = buf + off;
623	char *eb = buf + cnt;
624	char *b = sb;
625
626	ch = (unsigned char)ch;
627	if (ch == 0) {
628		ADDC('^');
629		ADDC('@');
630		return (int)(b - sb);
631	}
632	if (iscntrl(ch)) {
633		ADDC('^');
634		if (ch == '\177')
635			ADDC('?');
636		else
637			ADDC(toascii(ch) | 0100);
638	} else if (ch == '^') {
639		ADDC('\\');
640		ADDC('^');
641	} else if (ch == '\\') {
642		ADDC('\\');
643		ADDC('\\');
644	} else if (ch == ' ' || (isprint(ch) && !isspace(ch))) {
645		ADDC(ch);
646	} else {
647		ADDC('\\');
648		ADDC((((unsigned int) ch >> 6) & 7) + '0');
649		ADDC((((unsigned int) ch >> 3) & 7) + '0');
650		ADDC((ch & 7) + '0');
651	}
652	return (size_t)(b - sb);
653}
654
655
656/* key__decode_str():
657 *	Make a printable version of the ey
658 */
659protected size_t
660key__decode_str(const char *str, char *buf, size_t len, const char *sep)
661{
662	char *b = buf, *eb = b + len;
663	const char *p;
664
665	b = buf;
666	if (sep[0] != '\0') {
667		ADDC(sep[0]);
668	}
669	if (*str == '\0') {
670		ADDC('^');
671		ADDC('@');
672		if (sep[0] != '\0' && sep[1] != '\0') {
673			ADDC(sep[1]);
674		}
675		goto done;
676	}
677	for (p = str; *p != 0; p++) {
678		if (iscntrl((unsigned char) *p)) {
679			ADDC('^');
680			if (*p == '\177') {
681				ADDC('?');
682			} else {
683				ADDC(toascii(*p) | 0100);
684			}
685		} else if (*p == '^' || *p == '\\') {
686			ADDC('\\');
687			ADDC(*p);
688		} else if (*p == ' ' || (isprint((unsigned char) *p) &&
689			!isspace((unsigned char) *p))) {
690			ADDC(*p);
691		} else {
692			ADDC('\\');
693			ADDC((((unsigned int) *p >> 6) & 7) + '0');
694			ADDC((((unsigned int) *p >> 3) & 7) + '0');
695			ADDC((*p & 7) + '0');
696		}
697	}
698	if (sep[0] != '\0' && sep[1] != '\0') {
699		ADDC(sep[1]);
700	}
701done:
702	ADDC('\0');
703	if ((size_t)(b - buf) >= len)
704	    buf[len - 1] = '\0';
705	return (size_t)(b - buf);
706}
707