key.c revision 108470
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. All advertising materials mentioning features or use of this software 17 * must display the following acknowledgement: 18 * This product includes software developed by the University of 19 * California, Berkeley and its contributors. 20 * 4. Neither the name of the University nor the names of its contributors 21 * may be used to endorse or promote products derived from this software 22 * without specific prior written permission. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 * 36 * $NetBSD: key.c,v 1.11 2001/01/23 15:55:30 jdolecek Exp $ 37 */ 38 39#if !defined(lint) && !defined(SCCSID) 40static char sccsid[] = "@(#)key.c 8.1 (Berkeley) 6/4/93"; 41#endif /* not lint && not SCCSID */ 42#include <sys/cdefs.h> 43__FBSDID("$FreeBSD: head/lib/libedit/key.c 108470 2002-12-30 21:18:15Z schweikh $"); 44 45/* 46 * key.c: This module contains the procedures for maintaining 47 * the extended-key map. 48 * 49 * An extended-key (key) is a sequence of keystrokes introduced 50 * with a sequence introducer and consisting of an arbitrary 51 * number of characters. This module maintains a map (the el->el_key.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_key.map, adding the key "abc" will cause the first two 59 * 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 "sys.h" 67#include <string.h> 68#include <stdlib.h> 69 70#include "el.h" 71 72/* 73 * The Nodes of the el->el_key.map. The el->el_key.map is a linked list 74 * of these node elements 75 */ 76struct key_node_t { 77 char ch; /* single character of key */ 78 int type; /* node type */ 79 key_value_t val; /* command code or pointer to str, */ 80 /* if this is a leaf */ 81 struct key_node_t *next; /* ptr to next char of this key */ 82 struct key_node_t *sibling; /* ptr to another key with same prefix*/ 83}; 84 85private int node_trav(EditLine *, key_node_t *, char *, 86 key_value_t *); 87private int node__try(EditLine *, key_node_t *, const char *, 88 key_value_t *, int); 89private key_node_t *node__get(int); 90private void node__put(EditLine *, key_node_t *); 91private int node__delete(EditLine *, key_node_t **, char *); 92private int node_lookup(EditLine *, char *, key_node_t *, int); 93private int node_enum(EditLine *, key_node_t *, int); 94private int key__decode_char(char *, int, int); 95 96#define KEY_BUFSIZ EL_BUFSIZ 97 98 99/* key_init(): 100 * Initialize the key maps 101 */ 102protected int 103key_init(EditLine *el) 104{ 105 106 el->el_key.buf = (char *) el_malloc(KEY_BUFSIZ); 107 if (el->el_key.buf == NULL) 108 return (-1); 109 el->el_key.map = NULL; 110 key_reset(el); 111 return (0); 112} 113 114 115/* key_end(): 116 * Free the key maps 117 */ 118protected void 119key_end(EditLine *el) 120{ 121 122 el_free((ptr_t) el->el_key.buf); 123 el->el_key.buf = NULL; 124 /* XXX: provide a function to clear the keys */ 125 el->el_key.map = NULL; 126} 127 128 129/* key_map_cmd(): 130 * Associate cmd with a key value 131 */ 132protected key_value_t * 133key_map_cmd(EditLine *el, int cmd) 134{ 135 136 el->el_key.val.cmd = (el_action_t) cmd; 137 return (&el->el_key.val); 138} 139 140 141/* key_map_str(): 142 * Associate str with a key value 143 */ 144protected key_value_t * 145key_map_str(EditLine *el, char *str) 146{ 147 148 el->el_key.val.str = str; 149 return (&el->el_key.val); 150} 151 152 153/* key_reset(): 154 * Takes all nodes on el->el_key.map and puts them on free list. Then 155 * initializes el->el_key.map with arrow keys 156 * [Always bind the ansi arrow keys?] 157 */ 158protected void 159key_reset(EditLine *el) 160{ 161 162 node__put(el, el->el_key.map); 163 el->el_key.map = NULL; 164 return; 165} 166 167 168/* key_get(): 169 * Calls the recursive function with entry point el->el_key.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 177key_get(EditLine *el, char *ch, key_value_t *val) 178{ 179 180 return (node_trav(el, el->el_key.map, ch, val)); 181} 182 183 184/* key_add(): 185 * Adds key to the el->el_key.map and associates the value in val with it. 186 * If key is already is in el->el_key.map, the new code is applied to the 187 * existing key. Ntype specifies if code is a command, an 188 * out str or a unix command. 189 */ 190protected void 191key_add(EditLine *el, const char *key, key_value_t *val, int ntype) 192{ 193 194 if (key[0] == '\0') { 195 (void) fprintf(el->el_errfile, 196 "key_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 "key_add: sequence-lead-in command not allowed\n"); 202 return; 203 } 204 if (el->el_key.map == NULL) 205 /* tree is initially empty. Set up new node to match key[0] */ 206 el->el_key.map = node__get(key[0]); 207 /* it is properly initialized */ 208 209 /* Now recurse through el->el_key.map */ 210 (void) node__try(el, el->el_key.map, key, val, ntype); 211 return; 212} 213 214 215/* key_clear(): 216 * 217 */ 218protected void 219key_clear(EditLine *el, el_action_t *map, char *in) 220{ 221 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, 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, 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 \"%s\"\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 (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 ptr->val.str = strdup(val->str); 357 break; 358 default: 359 EL_ABORT((el->el_errfile, "Bad XK_ type %d\n", ntype)); 360 break; 361 } 362 } else { 363 /* still more chars to go */ 364 if (ptr->next == NULL) 365 ptr->next = node__get(*str); /* setup new node */ 366 (void) node__try(el, ptr->next, str, val, ntype); 367 } 368 return (0); 369} 370 371 372/* node__delete(): 373 * Delete node that matches str 374 */ 375private int 376node__delete(EditLine *el, key_node_t **inptr, char *str) 377{ 378 key_node_t *ptr; 379 key_node_t *prev_ptr = NULL; 380 381 ptr = *inptr; 382 383 if (ptr->ch != *str) { 384 key_node_t *xm; 385 386 for (xm = ptr; xm->sibling != NULL; xm = xm->sibling) 387 if (xm->sibling->ch == *str) 388 break; 389 if (xm->sibling == NULL) 390 return (0); 391 prev_ptr = xm; 392 ptr = xm->sibling; 393 } 394 if (*++str == '\0') { 395 /* we're there */ 396 if (prev_ptr == NULL) 397 *inptr = ptr->sibling; 398 else 399 prev_ptr->sibling = ptr->sibling; 400 ptr->sibling = NULL; 401 node__put(el, ptr); 402 return (1); 403 } else if (ptr->next != NULL && 404 node__delete(el, &ptr->next, str) == 1) { 405 if (ptr->next != NULL) 406 return (0); 407 if (prev_ptr == NULL) 408 *inptr = ptr->sibling; 409 else 410 prev_ptr->sibling = ptr->sibling; 411 ptr->sibling = NULL; 412 node__put(el, ptr); 413 return (1); 414 } else { 415 return (0); 416 } 417} 418 419 420/* node__put(): 421 * Puts a tree of nodes onto free list using free(3). 422 */ 423private void 424node__put(EditLine *el, key_node_t *ptr) 425{ 426 if (ptr == NULL) 427 return; 428 429 if (ptr->next != NULL) { 430 node__put(el, ptr->next); 431 ptr->next = NULL; 432 } 433 node__put(el, ptr->sibling); 434 435 switch (ptr->type) { 436 case XK_CMD: 437 case XK_NOD: 438 break; 439 case XK_EXE: 440 case XK_STR: 441 if (ptr->val.str != NULL) 442 el_free((ptr_t) ptr->val.str); 443 break; 444 default: 445 EL_ABORT((el->el_errfile, "Bad XK_ type %d\n", ptr->type)); 446 break; 447 } 448 el_free((ptr_t) ptr); 449} 450 451 452/* node__get(): 453 * Returns pointer to a key_node_t for ch. 454 */ 455private key_node_t * 456node__get(int ch) 457{ 458 key_node_t *ptr; 459 460 ptr = (key_node_t *) el_malloc((size_t) sizeof(key_node_t)); 461 if (ptr == NULL) 462 return NULL; 463 ptr->ch = ch; 464 ptr->type = XK_NOD; 465 ptr->val.str = NULL; 466 ptr->next = NULL; 467 ptr->sibling = NULL; 468 return (ptr); 469} 470 471 472 473/* node_lookup(): 474 * look for the str starting at node ptr. 475 * Print if last node 476 */ 477private int 478node_lookup(EditLine *el, char *str, key_node_t *ptr, int cnt) 479{ 480 int ncnt; 481 482 if (ptr == NULL) 483 return (-1); /* cannot have null ptr */ 484 485 if (*str == 0) { 486 /* no more chars in str. node_enum from here. */ 487 (void) node_enum(el, ptr, cnt); 488 return (0); 489 } else { 490 /* If match put this char into el->el_key.buf. Recurse */ 491 if (ptr->ch == *str) { 492 /* match found */ 493 ncnt = key__decode_char(el->el_key.buf, cnt, 494 (unsigned char) ptr->ch); 495 if (ptr->next != NULL) 496 /* not yet at leaf */ 497 return (node_lookup(el, str + 1, ptr->next, 498 ncnt + 1)); 499 else { 500 /* next node is null so key should be complete */ 501 if (str[1] == 0) { 502 el->el_key.buf[ncnt + 1] = '"'; 503 el->el_key.buf[ncnt + 2] = '\0'; 504 key_kprint(el, el->el_key.buf, 505 &ptr->val, ptr->type); 506 return (0); 507 } else 508 return (-1); 509 /* mismatch -- str still has chars */ 510 } 511 } else { 512 /* no match found try sibling */ 513 if (ptr->sibling) 514 return (node_lookup(el, str, ptr->sibling, 515 cnt)); 516 else 517 return (-1); 518 } 519 } 520} 521 522 523/* node_enum(): 524 * Traverse the node printing the characters it is bound in buffer 525 */ 526private int 527node_enum(EditLine *el, key_node_t *ptr, int cnt) 528{ 529 int ncnt; 530 531 if (cnt >= KEY_BUFSIZ - 5) { /* buffer too small */ 532 el->el_key.buf[++cnt] = '"'; 533 el->el_key.buf[++cnt] = '\0'; 534 (void) fprintf(el->el_errfile, 535 "Some extended keys too long for internal print buffer"); 536 (void) fprintf(el->el_errfile, " \"%s...\"\n", el->el_key.buf); 537 return (0); 538 } 539 if (ptr == NULL) { 540#ifdef DEBUG_EDIT 541 (void) fprintf(el->el_errfile, 542 "node_enum: BUG!! Null ptr passed\n!"); 543#endif 544 return (-1); 545 } 546 /* put this char at end of str */ 547 ncnt = key__decode_char(el->el_key.buf, cnt, (unsigned char) ptr->ch); 548 if (ptr->next == NULL) { 549 /* print this key and function */ 550 el->el_key.buf[ncnt + 1] = '"'; 551 el->el_key.buf[ncnt + 2] = '\0'; 552 key_kprint(el, el->el_key.buf, &ptr->val, ptr->type); 553 } else 554 (void) node_enum(el, ptr->next, ncnt + 1); 555 556 /* go to sibling if there is one */ 557 if (ptr->sibling) 558 (void) node_enum(el, ptr->sibling, cnt); 559 return (0); 560} 561 562 563/* key_kprint(): 564 * Print the specified key and its associated 565 * function specified by val 566 */ 567protected void 568key_kprint(EditLine *el, char *key, key_value_t *val, int ntype) 569{ 570 el_bindings_t *fp; 571 char unparsbuf[EL_BUFSIZ]; 572 static const char fmt[] = "%-15s-> %s\n"; 573 574 if (val != NULL) 575 switch (ntype) { 576 case XK_STR: 577 case XK_EXE: 578 (void) fprintf(el->el_outfile, fmt, key, 579 key__decode_str(val->str, unparsbuf, 580 ntype == XK_STR ? "\"\"" : "[]")); 581 break; 582 case XK_CMD: 583 for (fp = el->el_map.help; fp->name; fp++) 584 if (val->cmd == fp->func) { 585 (void) fprintf(el->el_outfile, fmt, 586 key, fp->name); 587 break; 588 } 589#ifdef DEBUG_KEY 590 if (fp->name == NULL) 591 (void) fprintf(el->el_outfile, 592 "BUG! Command not found.\n"); 593#endif 594 595 break; 596 default: 597 EL_ABORT((el->el_errfile, "Bad XK_ type %d\n", ntype)); 598 break; 599 } 600 else 601 (void) fprintf(el->el_outfile, fmt, key, "no input"); 602} 603 604 605/* key__decode_char(): 606 * Put a printable form of char in buf. 607 */ 608private int 609key__decode_char(char *buf, int cnt, int ch) 610{ 611 ch = (unsigned char)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 == 0177) 621 buf[cnt] = '?'; 622 else 623 buf[cnt] = toascii(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/* key__decode_str(): 642 * Make a printable version of the ey 643 */ 644protected char * 645key__decode_str(char *str, char *buf, char *sep) 646{ 647 char *b, *p; 648 649 b = buf; 650 if (sep[0] != '\0') 651 *b++ = sep[0]; 652 if (*str == 0) { 653 *b++ = '^'; 654 *b++ = '@'; 655 if (sep[0] != '\0' && sep[1] != '\0') 656 *b++ = sep[1]; 657 *b++ = 0; 658 return (buf); 659 } 660 for (p = str; *p != 0; p++) { 661 if (iscntrl((unsigned char) *p)) { 662 *b++ = '^'; 663 if (*p == '\177') 664 *b++ = '?'; 665 else 666 *b++ = toascii(*p) | 0100; 667 } else if (*p == '^' || *p == '\\') { 668 *b++ = '\\'; 669 *b++ = *p; 670 } else if (*p == ' ' || (isprint((unsigned char) *p) && 671 !isspace((unsigned char) *p))) { 672 *b++ = *p; 673 } else { 674 *b++ = '\\'; 675 *b++ = (((unsigned int) *p >> 6) & 7) + '0'; 676 *b++ = (((unsigned int) *p >> 3) & 7) + '0'; 677 *b++ = (*p & 7) + '0'; 678 } 679 } 680 if (sep[0] != '\0' && sep[1] != '\0') 681 *b++ = sep[1]; 682 *b++ = 0; 683 return (buf); /* should check for overflow */ 684} 685