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) 36static 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 */ 71struct 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 80private int node_trav(EditLine *, key_node_t *, char *, 81 key_value_t *); 82private int node__try(EditLine *, key_node_t *, const char *, 83 key_value_t *, int); 84private key_node_t *node__get(int); 85private void node__free(key_node_t *); 86private void node__put(EditLine *, key_node_t *); 87private int node__delete(EditLine *, key_node_t **, const char *); 88private int node_lookup(EditLine *, const char *, key_node_t *, 89 size_t); 90private 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 */ 98protected int 99key_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 */ 113protected void 114key_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 */ 126protected key_value_t * 127key_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 */ 138protected key_value_t * 139key_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 */ 152protected void 153key_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 */ 170protected int 171key_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 */ 184protected void 185key_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 */ 212protected void 213key_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 */ 229protected int 230key_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 */ 250protected void 251key_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 */ 271private int 272node_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 */ 308private int 309node__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 */ 370private int 371node__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 */ 418private void 419node__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 */ 450private key_node_t * 451node__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 466private void 467node__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 */ 480private int 481node_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 */ 530private int 531node_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 */ 572protected void 573key_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 */ 619protected size_t 620key__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 */ 659protected size_t 660key__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 } 701done: 702 ADDC('\0'); 703 if ((size_t)(b - buf) >= len) 704 buf[len - 1] = '\0'; 705 return (size_t)(b - buf); 706} 707