lib/libedit/key.c

   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  * @(#)key.c    8.1 (Berkeley) 6/4/93
  33  * $NetBSD: key.c,v 1.19 2006/03/23 20:22:51 christos Exp $
  34  * $DragonFly: src/lib/libedit/key.c,v 1.6 2007/05/05 00:27:39 pavalos Exp $
  35  */
  36
  37 #include "config.h"
  38
  39 /*
  40  * key.c: This module contains the procedures for maintaining
  41  *        the extended-key map.
  42  *
  43  *      An extended-key (key) is a sequence of keystrokes introduced
  44  *      with a sequence introducer and consisting of an arbitrary
  45  *      number of characters.  This module maintains a map (the el->el_key.map)
  46  *      to convert these extended-key sequences into input strs
  47  *      (XK_STR), editor functions (XK_CMD), or unix commands (XK_EXE).
  48  *
  49  *      Warning:
  50  *        If key is a substr of some other keys, then the longer
  51  *        keys are lost!!  That is, if the keys "abcd" and "abcef"
  52  *        are in el->el_key.map, adding the key "abc" will cause the first two
  53  *        definitions to be lost.
  54  *
  55  *      Restrictions:
  56  *      -------------
  57  *      1) It is not possible to have one key that is a
  58  *         substr of another.
  59  */
  60 #include <string.h>
  61 #include <stdlib.h>
  62
  63 #include "el.h"
  64
  65 /*
  66  * The Nodes of the el->el_key.map.  The el->el_key.map is a linked list
  67  * of these node elements
  68  */
  69 struct key_node_t {
  70         char            ch;             /* single character of key       */
  71         int             type;           /* node type                     */
  72         key_value_t     val;            /* command code or pointer to str,  */
  73                                         /* if this is a leaf             */
  74         struct key_node_t *next;        /* ptr to next char of this key  */
  75         struct key_node_t *sibling;     /* ptr to another key with same prefix*/
  76 };
  77
  78 private int              node_trav(EditLine *, key_node_t *, char *,
  79     key_value_t *);
  80 private int              node__try(EditLine *, key_node_t *, const char *,
  81     key_value_t *, int);
  82 private key_node_t      *node__get(int);
  83 private void             node__free(key_node_t *);
  84 private void             node__put(EditLine *, key_node_t *);
  85 private int              node__delete(EditLine *, key_node_t **, const char *);
  86 private int              node_lookup(EditLine *, const char *, key_node_t *,
  87     int);
  88 private int              node_enum(EditLine *, key_node_t *, int);
  89
  90 #define KEY_BUFSIZ      EL_BUFSIZ
  91
  92
  93 /* key_init():
  94  *      Initialize the key maps
  95  */
  96 protected int
  97 key_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  */
 111 protected void
 112 key_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  */
 124 protected key_value_t *
 125 key_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  */
 136 protected key_value_t *
 137 key_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  */
 150 protected void
 151 key_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  */
 168 protected int
 169 key_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  */
 182 protected void
 183 key_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  */
 210 protected void
 211 key_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  */
 227 protected int
 228 key_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  */
 248 protected void
 249 key_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  */
 269 private int
 270 node_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  */
 306 private int
 307 node__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  */
 368 private int
 369 node__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  */
 416 private void
 417 node__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  */
 448 private key_node_t *
 449 node__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
 464 private void
 465 node__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  */
 478 private int
 479 node_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, KEY_BUFSIZ, 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  */
 527 private int
 528 node_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, KEY_BUFSIZ, cnt,
 549             (unsigned char)ptr->ch);
 550         if (ptr->next == NULL) {
 551                 /* print this key and function */
 552                 el->el_key.buf[ncnt + 1] = '"';
 553                 el->el_key.buf[ncnt + 2] = '\0';
 554                 key_kprint(el, el->el_key.buf, &ptr->val, ptr->type);
 555         } else
 556                 (void) node_enum(el, ptr->next, ncnt + 1);
 557
 558         /* go to sibling if there is one */
 559         if (ptr->sibling)
 560                 (void) node_enum(el, ptr->sibling, cnt);
 561         return (0);
 562 }
 563
 564
 565 /* key_kprint():
 566  *      Print the specified key and its associated
 567  *      function specified by val
 568  */
 569 protected void
 570 key_kprint(EditLine *el, const char *key, key_value_t *val, int ntype)
 571 {
 572         el_bindings_t *fp;
 573         char unparsbuf[EL_BUFSIZ];
 574         static const char fmt[] = "%-15s->  %s\n";
 575
 576         if (val != NULL)
 577                 switch (ntype) {
 578                 case XK_STR:
 579                 case XK_EXE:
 580                         (void) key__decode_str(val->str, unparsbuf,
 581                             sizeof(unparsbuf),
 582                             ntype == XK_STR ? "\"\"" : "[]");
 583                         (void) fprintf(el->el_outfile, fmt, key, unparsbuf);
 584                         break;
 585                 case XK_CMD:
 586                         for (fp = el->el_map.help; fp->name; fp++)
 587                                 if (val->cmd == fp->func) {
 588                                         (void) fprintf(el->el_outfile, fmt,
 589                                             key, fp->name);
 590                                         break;
 591                                 }
 592 #ifdef DEBUG_KEY
 593                         if (fp->name == NULL)
 594                                 (void) fprintf(el->el_outfile,
 595                                     "BUG! Command not found.\n");
 596 #endif
 597
 598                         break;
 599                 default:
 600                         EL_ABORT((el->el_errfile, "Bad XK_ type %d\n", ntype));
 601                         break;
 602                 }
 603         else
 604                 (void) fprintf(el->el_outfile, fmt, key, "no input");
 605 }
 606
 607
 608 #define ADDC(c) \
 609         if (b < eb) \
 610                 *b++ = c; \
 611         else \
 612                 b++
 613 /* key__decode_char():
 614  *      Put a printable form of char in buf.
 615  */
 616 protected int
 617 key__decode_char(char *buf, int cnt, int off, int ch)
 618 {
 619         char *sb = buf + off;
 620         char *eb = buf + cnt;
 621         char *b = sb;
 622         if (ch == 0) {
 623                 ADDC('^');
 624                 ADDC('@');
 625                 return b - sb;
 626         }
 627         if (iscntrl(ch)) {
 628                 ADDC('^');
 629                 if (ch == '\177')
 630                         ADDC('?');
 631                 else
 632                         ADDC(ch | 0100);
 633         } else if (ch == '^') {
 634                 ADDC('\\');
 635                 ADDC('^');
 636         } else if (ch == '\\') {
 637                 ADDC('\\');
 638                 ADDC('\\');
 639         } else if (ch == ' ' || (isprint(ch) && !isspace(ch))) {
 640                 ADDC(ch);
 641         } else {
 642                 ADDC('\\');
 643                 ADDC((((unsigned int) ch >> 6) & 7) + '0');
 644                 ADDC((((unsigned int) ch >> 3) & 7) + '0');
 645                 ADDC((ch & 7) + '0');
 646         }
 647         return b - sb;
 648 }
 649
 650
 651 /* key__decode_str():
 652  *      Make a printable version of the ey
 653  */
 654 protected int
 655 key__decode_str(const char *str, char *buf, int len, const char *sep)
 656 {
 657         char *b = buf, *eb = b + len;
 658         const char *p;
 659
 660         b = buf;
 661         if (sep[0] != '\0') {
 662                 ADDC(sep[0]);
 663         }
 664         if (*str == '\0') {
 665                 ADDC('^');
 666                 ADDC('@');
 667                 if (sep[0] != '\0' && sep[1] != '\0') {
 668                         ADDC(sep[1]);
 669                 }
 670                 goto done;
 671         }
 672         for (p = str; *p != 0; p++) {
 673                 if (iscntrl((unsigned char) *p)) {
 674                         ADDC('^');
 675                         if (*p == '\177') {
 676                                 ADDC('?');
 677                         } else {
 678                                 ADDC(*p | 0100);
 679                         }
 680                 } else if (*p == '^' || *p == '\\') {
 681                         ADDC('\\');
 682                         ADDC(*p);
 683                 } else if (*p == ' ' || (isprint((unsigned char) *p) &&
 684                         !isspace((unsigned char) *p))) {
 685                         ADDC(*p);
 686                 } else {
 687                         ADDC('\\');
 688                         ADDC((((unsigned int) *p >> 6) & 7) + '0');
 689                         ADDC((((unsigned int) *p >> 3) & 7) + '0');
 690                         ADDC((*p & 7) + '0');
 691                 }
 692         }
 693         if (sep[0] != '\0' && sep[1] != '\0') {
 694                 ADDC(sep[1]);
 695         }
 696 done:
 697         ADDC('\0');
 698         if (b - buf >= len)
 699             buf[len - 1] = '\0';
 700         return b - buf;
 701 }