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
  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, 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, 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, char *k safe)
 174 {
 175         return key_find_len(map, k, strlen(k));
 176 }
 177
 178 void key_add(struct map *map safe, 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, char *first safe, char *last safe,
 242                    struct command *comm)
 243 {
 244         int size, move_size;
 245         int pos, pos2;
 246         int prefix;
 247         int i;
 248
 249         if (!comm || strcmp(first, last) >= 0)
 250                 return;
 251
 252         /* Add the first entry using key_add */
 253         key_add(map, first, comm);
 254         pos = key_find(map, first);
 255         pos2 = key_find(map, last);
 256
 257         /* Now 'pos' is a stand-alone entry for 'first'.
 258          * If the entry before pos2 is a range start, update to start at 'last',
 259          * else discard it, and discard everything else between pos and pos2.
 260          * Then insert a stand-alone for 'last' and update 'pos' to be a
 261          * range-start.
 262          */
 263         if (pos2 - 1 > pos && IS_RANGE(map->comms[pos2-1])) {
 264                 free(map->keys[pos2-1]);
 265                 map->keys[pos2-1] = strdup(last);
 266                 pos2 -= 1;
 267         }
 268         /* Need to insert 'last', and remove extras. so +1 and -(pos2-pos-1); */
 269         move_size = 1 - (pos2 - pos - 1);
 270         size = size2alloc(map->size + move_size);
 271         if (size2alloc(map->size) < size) {
 272                 map->keys = realloc(map->keys, size * sizeof(map->keys[0]));
 273                 map->comms = realloc(map->comms,
 274                                      size * sizeof(struct command *));
 275         }
 276         for (i = pos + 1; i < pos2; i++) {
 277                 free(map->keys[i]);
 278                 command_put(GETCOMM(map->comms[i]));
 279         }
 280         memmove(map->keys+pos2 + move_size, map->keys+pos2,
 281                 (map->size - pos2) * sizeof(map->keys[0]));
 282         memmove(map->comms+pos2+ move_size, map->comms+pos2,
 283                 (map->size - pos2) * sizeof(struct command *));
 284
 285         map->comms[pos] = SET_RANGE(comm);
 286         map->keys[pos+1] = strdup(last);
 287         map->comms[pos+1] = command_get(comm);
 288         map->size += move_size;
 289         map->changed = 1;
 290         for (prefix = 0;
 291              first[prefix] && first[prefix+1] == last[prefix+1];
 292              prefix += 1)
 293                 ;
 294         if (map->prefix_len < 0 || map->prefix_len > prefix)
 295                 map->prefix_len = prefix;
 296 }
 297
 298 void key_add_chain(struct map *map safe, struct map *chain)
 299 {
 300         while (map->chain)
 301                 map = map->chain;
 302         map->chain = chain;
 303 }
 304
 305
 306 #if 0
 307 void key_del(struct map *map, wint_t k)
 308 {
 309         int pos;
 310
 311         pos = key_find(map, k, -1);
 312         if (pos >= map->size || strcmp(map->keys[pos], k) == 0)
 313                 return;
 314
 315         memmove(map->keys+pos, map->keys+pos+1,
 316                 (map->size-pos-1) * sizeof(map->keys[0]));
 317         memmove(map->comms+pos, map->comms+pos+1,
 318                 (map->size-pos-1) * sizeof(struct command *));
 319         map->size -= 1;
 320         map->changed = 1;
 321 }
 322 #endif
 323
 324 int key_pfx_func(const struct cmd_info *ci safe)
 325 {
 326         struct pfx_cmd *m = container_of(ci->comm, struct pfx_cmd, c);
 327
 328         call("Mode:set-mode", ci->focus, 0, NULL, m->pfx);
 329         call("Mode:set-num", ci->focus, ci->num);
 330         call("Mode:set-num2", ci->focus, ci->num2);
 331         return 1;
 332 }
 333
 334 struct command *key_lookup_cmd(struct map *m safe, char *c safe,
 335                                char **cret, int *lenret)
 336 {
 337         /* If 'k' contains an ASCII US (Unit Separator, 0o37 0x1f 31),
 338          * it represents multiple keys.
 339          * Call key_find() on each of them until success.
 340          */
 341         while (*c) {
 342                 char *end = strchr(c, '\037');
 343                 int pos;
 344
 345                 if (!end)
 346                         end = c + strlen(c);
 347                 pos = key_find_len(m, c, end - c);
 348
 349                 if (pos >= m->size)
 350                         ;
 351                 else if (strncmp(m->keys[pos], c, end - c) == 0 &&
 352                          m->keys[pos][end - c] == '\0') {
 353                         /* Exact match - use this entry */
 354                         if (cret)
 355                                 *cret = c;
 356                         if (lenret)
 357                                 *lenret = end - c;
 358                         return GETCOMM(m->comms[pos]);
 359                 } else if (pos > 0 && IS_RANGE(m->comms[pos-1])) {
 360                         /* In a range, use previous */
 361                         if (cret)
 362                                 *cret = c;
 363                         if (lenret)
 364                                 *lenret = end - c;
 365                         return GETCOMM(m->comms[pos-1]);
 366                 }
 367                 c = end;
 368                 while (*c == '\037')
 369                         c++;
 370         }
 371         return NULL;
 372 }
 373
 374 int key_lookup(struct map *m safe, const struct cmd_info *ci safe)
 375 {
 376         struct command *comm;
 377         char *key;
 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                 char *oldkey = ci->key;
 395                 char tail = key[len];
 396
 397                 stat_count("bloom-hit-good");
 398                 if (key[len])
 399                         key[len] = 0;
 400                 ((struct cmd_info*)ci)->comm = comm;
 401                 ((struct cmd_info*)ci)->key = key;
 402                 ret = comm->func(ci);
 403                 ((struct cmd_info*)ci)->key = oldkey;
 404                 if (tail)
 405                         key[len] = tail;
 406                 return ret;
 407         }
 408 }
 409
 410 int key_lookup_prefix(struct map *m safe, const struct cmd_info *ci safe)
 411 {
 412         int pos = key_find(m, ci->key);
 413         struct command *comm, *prev = NULL;
 414         int len = strlen(ci->key);
 415         char *k = ci->key;
 416
 417         while (pos < m->size && strncmp(m->keys[pos], k, len) == 0) {
 418                 comm = GETCOMM(m->comms[pos]);
 419                 if (comm && comm != prev) {
 420                         int ret;
 421                         ((struct cmd_info*)ci)->comm = comm;
 422                         ((struct cmd_info*)ci)->key = m->keys[pos];
 423                         ret = comm->func(ci);
 424                         ASSERT(ret >= 0 || ret < Eunused);
 425                         if (ret)
 426                                 return ret;
 427                         prev = comm;
 428                 }
 429                 pos += 1;
 430         }
 431         ((struct cmd_info*)ci)->key = k;
 432         return 0;
 433 }
 434
 435 int key_lookup_cmd_func(const struct cmd_info *ci safe)
 436 {
 437         struct lookup_cmd *l = container_of(ci->comm, struct lookup_cmd, c);
 438         struct map *m = safe_cast *l->m;
 439         int ret = key_lookup(m, ci);
 440
 441         while (!ret && m->chain) {
 442                 m = m->chain;
 443                 ret = key_lookup(m, ci);
 444         }
 445         return ret;
 446 }
 447
 448 /* key_handle.  Search towards root for the pane which handles the command.
 449  */
 450 int key_handle(const struct cmd_info *ci safe)
 451 {
 452         struct cmd_info *vci = (struct cmd_info*)ci;
 453         struct pane *p;
 454         unsigned int hash[30];
 455         int h= 0;
 456         int i;
 457
 458         time_start_key(ci->key);
 459         if ((void*) ci->comm) {
 460                 int ret = ci->comm->func(ci);
 461                 time_stop_key(ci->key);
 462                 return ret;
 463         }
 464
 465         for (i = 0; i < 30 && ci->key[i]; i++) {
 466                 h = qhash(ci->key[i], h);
 467                 if (i+1 < 30)
 468                         hash[i+1] = h;
 469                 if (ci->key[i] == '\037')
 470                         // Disable hash for multi-keys
 471                         i = 30;
 472         }
 473         hash[0] = h;
 474         if (i < 30)
 475                 vci->hash = hash;
 476
 477         /* If 'home' is set, search from there, else search
 478          * from focus
 479          */
 480         p = ci->home;
 481         if (!p)
 482                 p = ci->focus;
 483
 484         while (p) {
 485                 int ret = 0;
 486                 if (p->handle) {
 487                         vci->home = p;
 488                         vci->comm = p->handle;
 489                         ret = p->handle->func(ci);
 490                 }
 491                 if (ret) {
 492                         time_stop_key(ci->key);
 493                         /* 'p' might have been destroyed */
 494                         return ret;
 495                 }
 496                 p = p->parent;
 497         }
 498         time_stop_key(ci->key);
 499         return 0;
 500 }