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)
36 static 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 */
71 struct 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
80 private int node_trav(EditLine *, key_node_t *, char *,
81 key_value_t *);
82 private int node__try(EditLine *, key_node_t *, const char *,
83 key_value_t *, int);
84 private key_node_t *node__get(int);
85 private void node__free(key_node_t *);
86 private void node__put(EditLine *, key_node_t *);
87 private int node__delete(EditLine *, key_node_t **, const char *);
88 private int node_lookup(EditLine *, const char *, key_node_t *,
89 size_t);
90 private 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 */
98 protected int
key_init(EditLine * el)99 key_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 */
113 protected void
key_end(EditLine * el)114 key_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 */
126 protected key_value_t *
key_map_cmd(EditLine * el,int cmd)127 key_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 */
138 protected key_value_t *
key_map_str(EditLine * el,char * str)139 key_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 */
152 protected void
key_reset(EditLine * el)153 key_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 */
170 protected int
key_get(EditLine * el,char * ch,key_value_t * val)171 key_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 */
184 protected void
key_add(EditLine * el,const char * key,key_value_t * val,int ntype)185 key_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 */
212 protected void
key_clear(EditLine * el,el_action_t * map,const char * in)213 key_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 */
229 protected int
key_delete(EditLine * el,const char * key)230 key_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 */
250 protected void
key_print(EditLine * el,const char * key)251 key_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 */
271 private int
node_trav(EditLine * el,key_node_t * ptr,char * ch,key_value_t * val)272 node_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 */
308 private int
node__try(EditLine * el,key_node_t * ptr,const char * str,key_value_t * val,int ntype)309 node__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 */
370 private int
node__delete(EditLine * el,key_node_t ** inptr,const char * str)371 node__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 */
418 private void
node__put(EditLine * el,key_node_t * ptr)419 node__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 */
450 private key_node_t *
node__get(int ch)451 node__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
466 private void
node__free(key_node_t * k)467 node__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 */
480 private int
node_lookup(EditLine * el,const char * str,key_node_t * ptr,size_t cnt)481 node_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 */
530 private int
node_enum(EditLine * el,key_node_t * ptr,size_t cnt)531 node_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 */
572 protected void
key_kprint(EditLine * el,const char * key,key_value_t * val,int ntype)573 key_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 */
619 protected size_t
key__decode_char(char * buf,size_t cnt,size_t off,int ch)620 key__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 */
659 protected size_t
key__decode_str(const char * str,char * buf,size_t len,const char * sep)660 key__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 }
701 done:
702 ADDC('\0');
703 if ((size_t)(b - buf) >= len)
704 buf[len - 1] = '\0';
705 return (size_t)(b - buf);
706 }
707