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