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