core-keymap.c

   1 /*
   2  * Copyright Neil Brown ©2015-2019 <neil@brown.name>
   3  * May be distributed under terms of GPLv2 - see file:COPYING
   4  *
   5  * Keymaps for edlib.
   6  *
   7  * A keymap maps a key to a command.
   8  * Keys are ordered for fast binary-search lookup.
   9  * A "key" is an arbitrary string which typically contains
  10  * some 'mode' prefix and some specific tail.
  11  * e.g emacs:M:C-x is Meta-Control-X in emacs mode.
  12  * As far as the map is concerned, it is just a lexically order string.
  13  *
  14  * A 'command' is a struct provided by any of various
  15  * modules.
  16  *
  17  * A range can be stored by setting the lsb of the command pointer at
  18  * the start of the range.
  19  * When searching for a key we find the first entry that is not less
  20  * than the target.  If it is an exact match, use it.  If previous entry
  21  * exists and has the lsb set, then use that command.
  22  *
  23  * So to add a range, the start is entered with lsb set, and the end it
  24  * entered with lsb clear.
  25  *
  26  * If a key is registered a second time, the new over-rides the old.
  27  * This is particularly useful for registering a range, and then some
  28  * exceptions.
  29  * To delete a key from a range we need to make two ranges, one that ends
  30  * just before the new key, one that starts just after.
  31  * The 'ends just before' is easy - we just add the new key or range.
  32  * The 'starts just after' is managed by entering the same key twice.
  33  * The first instance of the key has a 'lsb clear' command and is used for
  34  * exact matches.  The second instance has 'lsb set' and is used for everything
  35  * after.
  36  *
  37  * A 'prefix' can be registered which creates a command which temporarily
  38  * enabled the given prefix.  It is applied to the next command, but is
  39  * discarded after that.  This is just a convenience function.
  40  *
  41  */
  42
  43 #include <unistd.h>
  44 #include <stdlib.h>
  45 #include <memory.h>
  46
  47 #include "core.h"
  48 #include "misc.h"
  49
  50 inline static int qhash(char key, unsigned int start)
  51 {
  52         return (start ^ key) * 0x61C88647U;
  53 }
  54
  55 struct map {
  56         unsigned long bloom[256 / (sizeof(long)*8) ];
  57         short   changed;
  58         short   prefix_len;
  59         int     size;
  60         struct map *chain;
  61         char    * safe *keys safe;
  62         struct command * safe *comms safe;
  63 };
  64
  65 static inline struct command * safe GETCOMM(struct command *c safe)
  66 {
  67         return (struct command * safe)(((unsigned long)c) & ~1UL);
  68 }
  69
  70 static inline int IS_RANGE(struct command *c)
  71 {
  72         return ((unsigned long)c) & 1;
  73 }
  74
  75 static inline struct command *SET_RANGE(struct command *c)
  76 {
  77         return (struct command *)(((unsigned long)c) | 1UL);
  78 }
  79
  80 static int size2alloc(int size)
  81 {
  82         /* Alway multiple of 8. */
  83         return ((size-1) | 7) + 1;
  84 }
  85
  86 struct map *safe key_alloc(void)
  87 {
  88         struct map *m = calloc(1, sizeof(*m));
  89
  90         m->prefix_len = -1;
  91         return m;
  92 }
  93
  94 void key_free(struct map *m safe)
  95 {
  96         int i;
  97         for (i = 0; i < m->size; i++) {
  98                 free(m->keys[i]);
  99                 command_put(GETCOMM(m->comms[i]));
 100         }
 101         free(m->keys);
 102         free(m->comms);
 103         free(m);
 104 }
 105
 106 static int hash_str(char *key safe, int len)
 107 {
 108         int i;
 109         int h = 0;
 110         for (i = 0; (len < 0 || i < len) && key[i]; i++)
 111                 h = qhash(key[i], h);
 112         return h;
 113 }
 114
 115 inline static void set_bit(unsigned long *set safe, int bit)
 116 {
 117         set[bit/(sizeof(unsigned long)*8)] |=
 118                 1UL << (bit % (sizeof(unsigned long)*8));
 119 }
 120
 121 inline static int test_bit(unsigned long *set safe, int bit)
 122 {
 123         return !! (set[bit/(sizeof(unsigned long)*8)] &
 124                    (1UL << (bit % (sizeof(unsigned long)*8))));
 125 }
 126
 127
 128 static int key_present(struct map *map safe, const char *key, int klen,
 129                        unsigned int *hashp safe)
 130 {
 131         int hash;
 132
 133         if (map->changed) {
 134                 int i;
 135                 for (i = 0; i < map->size; i++) {
 136                         hash = hash_str(map->keys[i], map->prefix_len);
 137                         set_bit(map->bloom, hash&0xff);
 138                         set_bit(map->bloom, (hash>>8)&0xff);
 139                         set_bit(map->bloom, (hash>>16)&0xff);
 140                 }
 141                 map->changed = 0;
 142         }
 143         if (map->prefix_len < 0 || klen <= map->prefix_len)
 144                 hash = hashp[0];
 145         else
 146                 hash = hashp[map->prefix_len];
 147         return (test_bit(map->bloom, hash&0xff) &&
 148                 test_bit(map->bloom, (hash>>8)&0xff) &&
 149                 test_bit(map->bloom, (hash>>16)&0xff));
 150 }
 151
 152 /* Find first entry >= k */
 153 static int key_find_len(struct map *map safe, const char *k safe, int len)
 154 {
 155         int lo = 0;
 156         int hi = map->size;
 157
 158         /* all entries before 'lo' are < k.
 159          * all entries at 'hi' or later are >= k.
 160          * So when lo==hi, hi is the answer.
 161          */
 162         while (hi > lo) {
 163                 int mid = (hi + lo)/ 2;
 164                 int cmp = strncmp(map->keys[mid], k, len);
 165                 if (cmp < 0)
 166                         lo = mid+1;
 167                 else
 168                         hi = mid;
 169         }
 170         return hi;
 171 }
 172
 173 static int key_find(struct map *map safe, const char *k safe)
 174 {
 175         return key_find_len(map, k, strlen(k));
 176 }
 177
 178 void key_add(struct map *map safe, const char *k safe, struct command *comm)
 179 {
 180         int size;
 181         int pos;
 182         struct command *comm2 = NULL;
 183         int ins_cnt;
 184
 185         if (!comm)
 186                 return;
 187
 188         pos = key_find(map, k);
 189         /* cases:
 190          * 1/ match start of range: insert before
 191          * 2/ match non-range start: replace
 192          * 3/ not in range: insert before like 1
 193          * 4/ in a range: insert match and range start.
 194          */
 195         if (pos >= map->size) {
 196                 /* Insert k,comm - default action */
 197         } else if (strcmp(k, map->keys[pos]) == 0) {
 198                 /* match: need to check if range-start */
 199                 if (IS_RANGE(map->comms[pos])) {
 200                         /* Changing the start of a range,
 201                          * insert an exact match */
 202                 } else {
 203                         /* replace a non-range */
 204                         command_put(map->comms[pos]);
 205                         map->comms[pos] = command_get(comm);
 206                         return;
 207                 }
 208         } else if (pos > 0 && IS_RANGE(map->comms[pos-1])) {
 209                 /* insert within a range.
 210                  * Add given command as non-range match, and old command
 211                  * as new range start
 212                  */
 213                 comm2 = map->comms[pos-1];
 214         } else {
 215                 /* Not in a range, simple insert */
 216         }
 217
 218         ins_cnt = comm2 ? 2 : 1;
 219         size = size2alloc(map->size + ins_cnt);
 220
 221         if (size2alloc(map->size) != size) {
 222                 map->keys = realloc(map->keys, size * sizeof(map->keys[0]));
 223                 map->comms = realloc(map->comms,
 224                                      size * sizeof(struct command *));
 225         }
 226
 227         memmove(map->keys+pos+ins_cnt, map->keys+pos,
 228                 (map->size - pos) * sizeof(map->keys[0]));
 229         memmove(map->comms+pos+ins_cnt, map->comms+pos,
 230                 (map->size - pos) * sizeof(struct command *));
 231         map->keys[pos] = strdup(k);
 232         map->comms[pos] = command_get(comm);
 233         if (comm2) {
 234                 map->keys[pos+1] = strdup(k);
 235                 map->comms[pos+1] = SET_RANGE(command_get(GETCOMM(comm2)));
 236         }
 237         map->size += ins_cnt;
 238         map->changed = 1;
 239 }
 240
 241 void key_add_range(struct map *map safe,
 242                    const char *first safe, const char *last safe,
 243                    struct command *comm)
 244 {
 245         int size, move_size;
 246         int pos, pos2;
 247         int prefix;
 248         int i;
 249
 250         if (!comm || strcmp(first, last) >= 0)
 251                 return;
 252
 253         /* Add the first entry using key_add */
 254         key_add(map, first, comm);
 255         pos = key_find(map, first);
 256         pos2 = key_find(map, last);
 257
 258         /* Now 'pos' is a stand-alone entry for 'first'.
 259          * If the entry before pos2 is a range start, update to start at 'last',
 260          * else discard it, and discard everything else between pos and pos2.
 261          * Then insert a stand-alone for 'last' and update 'pos' to be a
 262          * range-start.
 263          */
 264         if (pos2 - 1 > pos && IS_RANGE(map->comms[pos2-1])) {
 265                 free(map->keys[pos2-1]);
 266                 map->keys[pos2-1] = strdup(last);
 267                 pos2 -= 1;
 268         }
 269         /* Need to insert 'last', and remove extras. so +1 and -(pos2-pos-1); */
 270         move_size = 1 - (pos2 - pos - 1);
 271         size = size2alloc(map->size + move_size);
 272         if (size2alloc(map->size) < size) {
 273                 map->keys = realloc(map->keys, size * sizeof(map->keys[0]));
 274                 map->comms = realloc(map->comms,
 275                                      size * sizeof(struct command *));
 276         }
 277         for (i = pos + 1; i < pos2; i++) {
 278                 free(map->keys[i]);
 279                 command_put(GETCOMM(map->comms[i]));
 280         }
 281         memmove(map->keys+pos2 + move_size, map->keys+pos2,
 282                 (map->size - pos2) * sizeof(map->keys[0]));
 283         memmove(map->comms+pos2+ move_size, map->comms+pos2,
 284                 (map->size - pos2) * sizeof(struct command *));
 285
 286         map->comms[pos] = SET_RANGE(comm);
 287         map->keys[pos+1] = strdup(last);
 288         map->comms[pos+1] = command_get(comm);
 289         map->size += move_size;
 290         map->changed = 1;
 291         for (prefix = 0;
 292              first[prefix] && first[prefix+1] == last[prefix+1];
 293              prefix += 1)
 294                 ;
 295         if (map->prefix_len < 0 || map->prefix_len > prefix)
 296                 map->prefix_len = prefix;
 297 }
 298
 299 void key_add_chain(struct map *map safe, struct map *chain)
 300 {
 301         while (map->chain)
 302                 map = map->chain;
 303         map->chain = chain;
 304 }
 305
 306
 307 #if 0
 308 void key_del(struct map *map, wint_t k)
 309 {
 310         int pos;
 311
 312         pos = key_find(map, k, -1);
 313         if (pos >= map->size || strcmp(map->keys[pos], k) == 0)
 314                 return;
 315
 316         memmove(map->keys+pos, map->keys+pos+1,
 317                 (map->size-pos-1) * sizeof(map->keys[0]));
 318         memmove(map->comms+pos, map->comms+pos+1,
 319                 (map->size-pos-1) * sizeof(struct command *));
 320         map->size -= 1;
 321         map->changed = 1;
 322 }
 323 #endif
 324
 325 int key_pfx_func(const struct cmd_info *ci safe)
 326 {
 327         struct pfx_cmd *m = container_of(ci->comm, struct pfx_cmd, c);
 328
 329         call("Mode:set-all", ci->focus, ci->num, NULL, m->pfx, ci->num2);
 330         return 1;
 331 }
 332
 333 struct command *key_lookup_cmd(struct map *m safe, const char *c safe,
 334                                const char **cret, unsigned int *lenret)
 335 {
 336         /* If 'k' contains an ASCII US (Unit Separator, 0o37 0x1f 31),
 337          * it represents multiple keys.
 338          * Call key_find() on each of them until success.
 339          */
 340         while (*c) {
 341                 const char *end = strchr(c, '\037');
 342                 int pos;
 343
 344                 if (!end)
 345                         end = c + strlen(c);
 346                 pos = key_find_len(m, c, end - c);
 347
 348                 if (pos >= m->size)
 349                         ;
 350                 else if (strncmp(m->keys[pos], c, end - c) == 0 &&
 351                          m->keys[pos][end - c] == '\0') {
 352                         /* Exact match - use this entry */
 353                         if (cret)
 354                                 *cret = c;
 355                         if (lenret)
 356                                 *lenret = end - c;
 357                         return GETCOMM(m->comms[pos]);
 358                 } else if (pos > 0 && IS_RANGE(m->comms[pos-1])) {
 359                         /* In a range, use previous */
 360                         if (cret)
 361                                 *cret = c;
 362                         if (lenret)
 363                                 *lenret = end - c;
 364                         return GETCOMM(m->comms[pos-1]);
 365                 }
 366                 c = end;
 367                 while (*c == '\037')
 368                         c++;
 369         }
 370         return NULL;
 371 }
 372
 373 int key_lookup(struct map *m safe, const struct cmd_info *ci safe)
 374 {
 375         struct command *comm;
 376         const char *key;
 377         unsigned
 378                 int len;
 379
 380         if (ci->hash && !key_present(m, ci->key, strlen(ci->key), ci->hash)) {
 381                 stat_count("bloom-miss");
 382                 return Efallthrough;
 383         }
 384
 385         comm = key_lookup_cmd(m, ci->key, &key, &len);
 386         if (comm == NULL || key == NULL) {
 387                 stat_count("bloom-hit-bad");
 388                 return Efallthrough;
 389         } else {
 390                 /* This is message, but when there are multiple
 391                  * keys, we need to pass down the one that was matched.
 392                  */
 393                 int ret;
 394                 const char *oldkey = ci->key;
 395                 char ktmp[40], *k2 = NULL;
 396
 397                 stat_count("bloom-hit-good");
 398                 if (key[len] == 0) {
 399                         ((struct cmd_info*)ci)->key = key;
 400                 } else if (len >= sizeof(ktmp)) {
 401                         k2 = strndup(key, len);
 402                         ((struct cmd_info*)ci)->key = k2;
 403                 } else {
 404                         strncpy(ktmp, key, len);
 405                         ktmp[len] = 0;
 406                         ((struct cmd_info*)ci)->key = ktmp;
 407                 }
 408                 ((struct cmd_info*)ci)->comm = comm;
 409                 ret = comm->func(ci);
 410                 ((struct cmd_info*)ci)->key = oldkey;
 411                 free(k2);
 412                 return ret;
 413         }
 414 }
 415
 416 int key_lookup_prefix(struct map *m safe, const struct cmd_info *ci safe)
 417 {
 418         int pos = key_find(m, ci->key);
 419         struct command *comm, *prev = NULL;
 420         int len = strlen(ci->key);
 421         const char *k = ci->key;
 422
 423         while (pos < m->size && strncmp(m->keys[pos], k, len) == 0) {
 424                 comm = GETCOMM(m->comms[pos]);
 425                 if (comm && comm != prev) {
 426                         int ret;
 427                         ((struct cmd_info*)ci)->comm = comm;
 428                         ((struct cmd_info*)ci)->key = m->keys[pos];
 429                         ret = comm->func(ci);
 430                         ASSERT(ret >= 0 || ret < Eunused);
 431                         if (ret)
 432                                 return ret;
 433                         prev = comm;
 434                 }
 435                 pos += 1;
 436         }
 437         ((struct cmd_info*)ci)->key = k;
 438         return 0;
 439 }
 440
 441 int key_lookup_cmd_func(const struct cmd_info *ci safe)
 442 {
 443         struct lookup_cmd *l = container_of(ci->comm, struct lookup_cmd, c);
 444         struct map *m = safe_cast *l->m;
 445         int ret = key_lookup(m, ci);
 446
 447         while (!ret && m->chain) {
 448                 m = m->chain;
 449                 ret = key_lookup(m, ci);
 450         }
 451         return ret;
 452 }
 453
 454 /* key_handle.  Search towards root for the pane which handles the command.
 455  */
 456 int key_handle(const struct cmd_info *ci safe)
 457 {
 458         struct cmd_info *vci = (struct cmd_info*)ci;
 459         struct pane *p;
 460         unsigned int hash[30];
 461         int h= 0;
 462         int i;
 463
 464         time_start_key(ci->key);
 465         if ((void*) ci->comm) {
 466                 int ret = ci->comm->func(ci);
 467                 time_stop_key(ci->key);
 468                 return ret;
 469         }
 470
 471         for (i = 0; i < 30 && ci->key[i]; i++) {
 472                 h = qhash(ci->key[i], h);
 473                 if (i+1 < 30)
 474                         hash[i+1] = h;
 475                 if (ci->key[i] == '\037')
 476                         // Disable hash for multi-keys
 477                         i = 30;
 478         }
 479         hash[0] = h;
 480         if (i < 30)
 481                 vci->hash = hash;
 482
 483         /* If 'home' is set, search from there, else search
 484          * from focus
 485          */
 486         p = ci->home;
 487         if (!p)
 488                 p = ci->focus;
 489
 490         while (p) {
 491                 int ret = 0;
 492                 if (p->handle && !(p->damaged & DAMAGED_DEAD)) {
 493                         vci->home = p;
 494                         vci->comm = p->handle;
 495                         ret = p->handle->func(ci);
 496                 }
 497                 if (ret) {
 498                         time_stop_key(ci->key);
 499                         /* 'p' might have been destroyed */
 500                         return ret;
 501                 }
 502                 if (p == p->parent)
 503                         p = NULL;
 504                 else
 505                         p = p->parent;
 506         }
 507         time_stop_key(ci->key);
 508         return 0;
 509 }