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