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