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