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