core-keymap.c

   1 /*
   2  * Copyright Neil Brown ©2015-2020 <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:A:C-X is Alt-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 #define _GNU_SOURCE /*  for asprintf */
  44 #include <unistd.h>
  45 #include <stdlib.h>
  46 #include <memory.h>
  47 #include <stdio.h>
  48
  49 #include "core.h"
  50 #include "misc.h"
  51
  52 inline static int qhash(char key, unsigned int start)
  53 {
  54         return (start ^ key) * 0x61C88647U;
  55 }
  56
  57 struct map {
  58         unsigned long   bloom[256 / (sizeof(unsigned long)*8) ];
  59         short           changed;
  60         short           size;
  61         struct map      *chain;
  62         char            * safe *keys safe;
  63         struct command  * safe *comms safe;
  64 };
  65
  66 static inline struct command * safe GETCOMM(struct command *c safe)
  67 {
  68         return (struct command * safe)(((unsigned long)c) & ~1UL);
  69 }
  70
  71 static inline int IS_RANGE(struct command *c)
  72 {
  73         return ((unsigned long)c) & 1;
  74 }
  75
  76 static inline struct command *SET_RANGE(struct command *c)
  77 {
  78         return (struct command *)(((unsigned long)c) | 1UL);
  79 }
  80
  81 DEF_CMD(keymap_list)
  82 {
  83         struct map *m;
  84         int len = ci->str ? strlen(ci->str) : 0;
  85         int i;
  86
  87         if (ci->comm == &keymap_list)
  88                 /* should be impossible */
  89                 return Efallthrough;
  90         /* ci->comm MUST be the keymap */
  91         m = (struct map* safe)ci->comm;
  92
  93         for (i = 0; i < m->size; i++)
  94                 if (!len || strncmp(ci->str, m->keys[i], len) == 0)
  95                         if (comm_call(ci->comm2, "cb", ci->focus,
  96                                       IS_RANGE(m->comms[i]), NULL, m->keys[i]) <= 0)
  97                                 break;
  98         return Efallthrough;
  99 }
 100
 101 static int size2alloc(int size)
 102 {
 103         /* Alway multiple of 8. */
 104         return ((size-1) | 7) + 1;
 105 }
 106
 107 struct map *safe key_alloc(void)
 108 {
 109         struct map *m = calloc(1, sizeof(*m));
 110
 111         key_add(m, "keymap:list", &keymap_list);
 112         return m;
 113 }
 114
 115 void key_free(struct map *m safe)
 116 {
 117         int i;
 118         for (i = 0; i < m->size; i++) {
 119                 free(m->keys[i]);
 120                 command_put(GETCOMM(m->comms[i]));
 121         }
 122         free(m->keys);
 123         free(m->comms);
 124         free(m);
 125 }
 126
 127 static void hash_str(const char *key safe, int len, unsigned int *hashes safe)
 128 {
 129         int i;
 130         int h = 0;
 131
 132         for (i = 0; (len < 0 || i < len) && key[i]; i++) {
 133                 h = qhash(key[i], h);
 134                 if (key[i] == '-' || key[i] == ':')
 135                         break;
 136         }
 137         hashes[1] = h;
 138         for (; (len < 0 || i < len) && key[i]; i++)
 139                 h = qhash(key[i], h);
 140         hashes[0] = h;
 141 }
 142
 143 inline static void set_bit(unsigned long *set safe, int bit)
 144 {
 145         set[bit/(sizeof(unsigned long)*8)] |=
 146                 1UL << (bit % (sizeof(unsigned long)*8));
 147 }
 148
 149 inline static int test_bit(unsigned long *set safe, int bit)
 150 {
 151         return !! (set[bit/(sizeof(unsigned long)*8)] &
 152                    (1UL << (bit % (sizeof(unsigned long)*8))));
 153 }
 154
 155 static bool key_present(struct map *map safe, unsigned int *hashes safe)
 156 {
 157         if (map->changed) {
 158                 int i;
 159                 for (i = 0; i < map->size; i++) {
 160                         unsigned int h[2];
 161                         hash_str(map->keys[i], -1, h);
 162                         if (IS_RANGE(map->comms[i])) {
 163                                 set_bit(map->bloom, h[1]&0xff);
 164                                 set_bit(map->bloom, (h[1]>>8)&0xff);
 165                                 set_bit(map->bloom, (h[1]>>16)&0xff);
 166                         } else {
 167                                 set_bit(map->bloom, h[0]&0xff);
 168                                 set_bit(map->bloom, (h[0]>>8)&0xff);
 169                                 set_bit(map->bloom, (h[0]>>16)&0xff);
 170                         }
 171                 }
 172                 map->changed = 0;
 173         }
 174
 175         if (test_bit(map->bloom, hashes[0]&0xff) &&
 176             test_bit(map->bloom, (hashes[0]>>8)&0xff) &&
 177             test_bit(map->bloom, (hashes[0]>>16)&0xff))
 178                 return True;
 179         if (test_bit(map->bloom, hashes[1]&0xff) &&
 180             test_bit(map->bloom, (hashes[1]>>8)&0xff) &&
 181             test_bit(map->bloom, (hashes[1]>>16)&0xff))
 182                 return True;
 183         return False;
 184 }
 185
 186 /* Find first entry >= k */
 187 static int key_find(struct map *map safe, const char *k safe)
 188 {
 189         int lo = 0;
 190         int hi = map->size;
 191
 192         /* all entries before 'lo' are < k.
 193          * all entries at 'hi' or later are >= k.
 194          * So when lo==hi, hi is the answer.
 195          */
 196         while (hi > lo) {
 197                 int mid = (hi + lo)/ 2;
 198                 if (strcmp(map->keys[mid], k) < 0)
 199                         lo = mid+1;
 200                 else
 201                         hi = mid;
 202         }
 203         return hi;
 204 }
 205
 206 void key_add(struct map *map safe, const char *k safe, struct command *comm)
 207 {
 208         int size;
 209         int pos;
 210         struct command *comm2 = NULL;
 211         int ins_cnt;
 212
 213         if (!comm)
 214                 return;
 215
 216         pos = key_find(map, k);
 217         /* cases:
 218          * 1/ match start of range: insert before
 219          * 2/ match non-range start: replace
 220          * 3/ not in range: insert before like 1
 221          * 4/ in a range: insert match and range start.
 222          */
 223         if (pos >= map->size) {
 224                 /* Insert k,comm - default action */
 225         } else if (strcmp(k, map->keys[pos]) == 0) {
 226                 /* match: need to check if range-start */
 227                 if (IS_RANGE(map->comms[pos])) {
 228                         /* Changing the start of a range,
 229                          * insert an exact match */
 230                 } else {
 231                         /* replace a non-range */
 232                         command_put(map->comms[pos]);
 233                         map->comms[pos] = command_get(comm);
 234                         return;
 235                 }
 236         } else if (pos > 0 && IS_RANGE(map->comms[pos-1])) {
 237                 /* insert within a range.
 238                  * Add given command as non-range match, and old command
 239                  * as new range start
 240                  */
 241                 comm2 = map->comms[pos-1];
 242         } else {
 243                 /* Not in a range, simple insert */
 244         }
 245
 246         ins_cnt = comm2 ? 2 : 1;
 247         size = size2alloc(map->size + ins_cnt);
 248
 249         if (size2alloc(map->size) != size) {
 250                 map->keys = realloc(map->keys, size * sizeof(map->keys[0]));
 251                 map->comms = realloc(map->comms,
 252                                      size * sizeof(struct command *));
 253         }
 254
 255         memmove(map->keys+pos+ins_cnt, map->keys+pos,
 256                 (map->size - pos) * sizeof(map->keys[0]));
 257         memmove(map->comms+pos+ins_cnt, map->comms+pos,
 258                 (map->size - pos) * sizeof(struct command *));
 259         map->keys[pos] = strdup(k);
 260         map->comms[pos] = command_get(comm);
 261         if (comm2) {
 262                 map->keys[pos+1] = strdup(k);
 263                 map->comms[pos+1] = SET_RANGE(command_get(GETCOMM(comm2)));
 264         }
 265         map->size += ins_cnt;
 266         map->changed = 1;
 267 }
 268
 269 void key_add_range(struct map *map safe,
 270                    const char *first safe, const char *last safe,
 271                    struct command *comm)
 272 {
 273         int size, move_size;
 274         int pos, pos2;
 275         int i;
 276
 277         if (!comm || strcmp(first, last) >= 0)
 278                 return;
 279
 280         /* Add the first entry using key_add */
 281         key_add(map, first, comm);
 282         pos = key_find(map, first);
 283         pos2 = key_find(map, last);
 284
 285         /* Now 'pos' is a stand-alone entry for 'first'.
 286          * If the entry before pos2 is a range start, update to start at 'last',
 287          * else discard it, and discard everything else between pos and pos2.
 288          * Then insert a stand-alone for 'last' and update 'pos' to be a
 289          * range-start.
 290          */
 291         if (pos2 - 1 > pos && IS_RANGE(map->comms[pos2-1])) {
 292                 free(map->keys[pos2-1]);
 293                 map->keys[pos2-1] = strdup(last);
 294                 pos2 -= 1;
 295         }
 296         /* Need to insert 'last', and remove extras. so +1 and -(pos2-pos-1); */
 297         move_size = 1 - (pos2 - pos - 1);
 298         size = size2alloc(map->size + move_size);
 299         if (size2alloc(map->size) < size) {
 300                 map->keys = realloc(map->keys, size * sizeof(map->keys[0]));
 301                 map->comms = realloc(map->comms,
 302                                      size * sizeof(struct command *));
 303         }
 304         for (i = pos + 1; i < pos2; i++) {
 305                 free(map->keys[i]);
 306                 command_put(GETCOMM(map->comms[i]));
 307         }
 308         memmove(map->keys+pos2 + move_size, map->keys+pos2,
 309                 (map->size - pos2) * sizeof(map->keys[0]));
 310         memmove(map->comms+pos2+ move_size, map->comms+pos2,
 311                 (map->size - pos2) * sizeof(struct command *));
 312
 313         map->comms[pos] = SET_RANGE(comm);
 314         map->keys[pos+1] = strdup(last);
 315         map->comms[pos+1] = command_get(comm);
 316         map->size += move_size;
 317         map->changed = 1;
 318 }
 319
 320 void key_add_chain(struct map *map safe, struct map *chain)
 321 {
 322         while (map->chain)
 323                 map = map->chain;
 324         map->chain = chain;
 325 }
 326
 327
 328 #if 0
 329 void key_del(struct map *map, wint_t k)
 330 {
 331         int pos;
 332
 333         pos = key_find(map, k, -1);
 334         if (pos >= map->size || strcmp(map->keys[pos], k) == 0)
 335                 return;
 336
 337         memmove(map->keys+pos, map->keys+pos+1,
 338                 (map->size-pos-1) * sizeof(map->keys[0]));
 339         memmove(map->comms+pos, map->comms+pos+1,
 340                 (map->size-pos-1) * sizeof(struct command *));
 341         map->size -= 1;
 342         map->changed = 1;
 343 }
 344 #endif
 345
 346 int key_pfx_func(const struct cmd_info *ci safe)
 347 {
 348         struct pfx_cmd *m = container_of(ci->comm, struct pfx_cmd, c);
 349
 350         call("Mode:set-all", ci->focus, ci->num, NULL, m->pfx, ci->num2);
 351         return 1;
 352 }
 353
 354 struct command *key_lookup_cmd(struct map *m safe, const char *c safe)
 355 {
 356         int pos = key_find(m, c);
 357
 358         if (pos >= m->size)
 359                 ;
 360         else if (strcmp(m->keys[pos], c) == 0)
 361                 /* Exact match - use this entry */
 362                 return GETCOMM(m->comms[pos]);
 363         else if (pos > 0 && IS_RANGE(m->comms[pos-1]))
 364                 /* In a range, use previous */
 365                 return GETCOMM(m->comms[pos-1]);
 366
 367         return NULL;
 368 }
 369
 370 /* FIXME this makes lots of things non re-entrant */
 371 static struct backtrace {
 372         struct command *comm safe;
 373         const struct cmd_info *ci safe;
 374         struct backtrace *prev;
 375 } *backtrace;
 376
 377 static char *mark_info(struct mark *m)
 378 {
 379         char *ret = NULL;
 380
 381         if (!m) {
 382                 asprintf(&ret, "M-");
 383                 return ret;
 384         }
 385         if (!mark_valid(m)) {
 386                 asprintf(&ret, "M-FREED");
 387                 return ret;
 388         }
 389         ret = pane_call_ret(str, m->owner, "doc:debug:mark",
 390                             m->owner, 0, m);
 391         if (ret)
 392                 return ret;
 393
 394         asprintf(&ret, "M:%x<%p>", m->seq, m);
 395         return ret;
 396 }
 397
 398 void LOG_BT(void)
 399 {
 400         struct backtrace *bt;
 401         LOG("Start Backtrace:");
 402         for (bt = backtrace; bt; bt = bt->prev) {
 403                 const struct cmd_info *ci = bt->ci;
 404                 struct command *h = ci->home->handle;
 405                 struct command *f = ci->focus->handle;
 406                 char *m1 = mark_info(ci->mark);
 407                 char *m2 = mark_info(ci->mark2);
 408
 409                 LOG(" H:%s \"%s\" F:%s: %d %s \"%s\" %d %s \"%s\" (%d,%d) %s",
 410                     h ? h->name : "?",
 411                     ci->key,
 412                     f ? f->name : "?",
 413                     ci->num, m1, ci->str,
 414                     ci->num2, m2, ci->str2,
 415                     ci->x, ci->y,
 416                     ci->comm2 ? ci->comm2->name : "");
 417                 free(m1);
 418                 free(m2);
 419         }
 420         LOG("End Backtrace");
 421 }
 422
 423 static int do_comm_call(struct command *comm safe,
 424                         const struct cmd_info *ci safe)
 425 {
 426         struct backtrace bt;
 427         int ret;
 428
 429         bt.comm = comm;
 430         bt.ci = ci;
 431         bt.prev = backtrace;
 432         backtrace = &bt;
 433         ret = comm->func(ci);
 434         backtrace = bt.prev;
 435         return ret;
 436 }
 437
 438 int key_lookup(struct map *m safe, const struct cmd_info *ci safe)
 439 {
 440         struct command *comm;
 441
 442         if (ci->hash && !key_present(m, ci->hash)) {
 443                 stat_count("bloom-miss");
 444                 return Efallthrough;
 445         }
 446
 447         comm = key_lookup_cmd(m, ci->key);
 448         if (comm == NULL) {
 449                 stat_count("bloom-hit-bad");
 450                 return Efallthrough;
 451         } else {
 452                 stat_count("bloom-hit-good");
 453                 ((struct cmd_info*)ci)->comm = comm;
 454
 455                 if (comm->func == keymap_list_func)
 456                         ((struct cmd_info*)ci)->comm = (struct command *safe)m;
 457
 458                 return do_comm_call(comm, ci);
 459         }
 460 }
 461
 462 int key_lookup_prefix(struct map *m safe, const struct cmd_info *ci safe)
 463 {
 464         int pos = key_find(m, ci->key);
 465         struct command *comm, *prev = NULL;
 466         int len = strlen(ci->key);
 467         const char *k = ci->key;
 468         int ret = 0;
 469
 470         while (ret == 0 && pos < m->size &&
 471                strncmp(m->keys[pos], k, len) == 0) {
 472                 comm = GETCOMM(m->comms[pos]);
 473                 if (comm && comm != prev) {
 474                         ((struct cmd_info*)ci)->comm = comm;
 475                         ((struct cmd_info*)ci)->key = m->keys[pos];
 476                         ret = do_comm_call(comm, ci);
 477                         ASSERT(ret >= 0 || ret < Eunused);
 478                         prev = comm;
 479                 }
 480                 pos += 1;
 481         }
 482         ((struct cmd_info*)ci)->key = k;
 483         return ret;
 484 }
 485
 486 int key_lookup_cmd_func(const struct cmd_info *ci safe)
 487 {
 488         struct lookup_cmd *l = container_of(ci->comm, struct lookup_cmd, c);
 489         struct map *m = safe_cast *l->m;
 490         int ret = key_lookup(m, ci);
 491
 492         while (!ret && m->chain) {
 493                 m = m->chain;
 494                 ret = key_lookup(m, ci);
 495         }
 496         return ret;
 497 }
 498
 499 /* key_handle.  Search towards root for the pane which handles the command.
 500  */
 501 int key_handle(const struct cmd_info *ci safe)
 502 {
 503         struct cmd_info *vci = (struct cmd_info*)ci;
 504         struct pane *p;
 505         unsigned int hash[2];
 506
 507         time_start_key(ci->key);
 508         if ((void*) ci->comm) {
 509                 int ret = do_comm_call(ci->comm, ci);
 510                 time_stop_key(ci->key);
 511                 return ret;
 512         }
 513
 514         hash_str(ci->key, -1, hash);
 515         vci->hash = hash;
 516
 517         /* If 'home' is set, search from there, else search
 518          * from focus
 519          */
 520         p = ci->home;
 521         if (!p)
 522                 p = ci->focus;
 523
 524         while (p) {
 525                 int ret = Efallthrough;
 526                 if (p->handle && !(p->damaged & DAMAGED_DEAD)) {
 527                         vci->home = p;
 528                         vci->comm = p->handle;
 529                         /* Don't add this to the call stack as it
 530                          * should simple call the desired function and
 531                          * that will appear on the call stack.
 532                          */
 533                         ret = p->handle->func(ci);
 534                 }
 535                 if (ret != Efallthrough) {
 536                         time_stop_key(ci->key);
 537                         /* 'p' might have been destroyed */
 538                         return ret;
 539                 }
 540                 if (p == p->parent)
 541                         p = NULL;
 542                 else
 543                         p = p->parent;
 544         }
 545         time_stop_key(ci->key);
 546         return Efallthrough;
 547 }