source: heimdal/trunk/lib/libedit/src/key.c

Last change on this file was 1, checked in by Paul Smedley, 10 years ago

Initial commit of Heimdal 1.5.3
File size: 15.9 KB
Line 
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
Note: See TracBrowser for help on using the repository browser.