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