core-keymap.c

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