key.c
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 38 static 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 */ 74 struct 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 83 private int node_trav(EditLine *, key_node_t *, Char *, 84 key_value_t *); 85 private int node__try(EditLine *, key_node_t *, const Char *, 86 key_value_t *, int); 87 private key_node_t *node__get(Int); 88 private void node__free(key_node_t *); 89 private void node__put(EditLine *, key_node_t *); 90 private int node__delete(EditLine *, key_node_t **, const Char *); 91 private int node_lookup(EditLine *, const Char *, key_node_t *, 92 size_t); 93 private 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 */ 101 protected int 102 key_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 */ 116 protected void 117 key_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 */ 129 protected key_value_t * 130 key_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 */ 141 protected key_value_t * 142 key_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 */ 155 protected void 156 key_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 */ 173 protected int 174 key_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 */ 187 protected void 188 key_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 */ 215 protected void 216 key_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 */ 235 protected int 236 key_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 */ 256 protected void 257 key_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 */ 277 private int 278 node_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 */ 314 private int 315 node__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 */ 376 private int 377 node__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 */ 424 private void 425 node__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 */ 456 private key_node_t * 457 node__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 472 private void 473 node__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 */ 486 private int 487 node_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 */ 537 private int 538 node_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 */ 578 protected void 579 key_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 */ 629 protected size_t 630 key__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 } 656 add_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