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