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