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