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
 226         pos = key_find(map, k);
 227         /* cases:
 228          * 1/ match start of range: insert before
 229          * 2/ match non-range start: replace
 230          * 3/ not in range: insert before like 1
 231          * 4/ in a range: insert match and range start.
 232          */
 233         if (pos >= map->size) {
 234                 /* Insert k,comm - default action */
 235         } else if (strcmp(k, map->keys[pos]) == 0) {
 236                 /* match: need to check if range-start */
 237                 if (IS_RANGE(map->comms[pos])) {
 238                         /* Changing the start of a range,
 239                          * insert an exact match */
 240                 } else {
 241                         /* replace a non-range */
 242                         command_put(map->comms[pos]);
 243                         map->comms[pos] = command_get(comm);
 244                         return;
 245                 }
 246         } else if (pos > 0 && IS_RANGE(map->comms[pos-1])) {
 247                 /* insert within a range.
 248                  * Add given command as non-range match, and old command
 249                  * as new range start
 250                  */
 251                 comm2 = map->comms[pos-1];
 252         } else {
 253                 /* Not in a range, simple insert */
 254         }
 255
 256         ins_cnt = comm2 ? 2 : 1;
 257         size = size2alloc(map->size + ins_cnt);
 258
 259         if (size2alloc(map->size) != size) {
 260                 map->keys = realloc(map->keys, size * sizeof(map->keys[0]));
 261                 map->comms = realloc(map->comms,
 262                                      size * sizeof(struct command *));
 263         }
 264
 265         memmove(map->keys+pos+ins_cnt, map->keys+pos,
 266                 (map->size - pos) * sizeof(map->keys[0]));
 267         memmove(map->comms+pos+ins_cnt, map->comms+pos,
 268                 (map->size - pos) * sizeof(struct command *));
 269         map->keys[pos] = strdup(k);
 270         map->comms[pos] = command_get(comm);
 271         if (comm2) {
 272                 map->keys[pos+1] = strdup(k);
 273                 map->comms[pos+1] = SET_RANGE(command_get(GETCOMM(comm2)));
 274         }
 275         map->size += ins_cnt;
 276         map->changed = True;
 277 }
 278
 279 void key_add_range(struct map *map safe,
 280                    const char *first safe, const char *last safe,
 281                    struct command *comm)
 282 {
 283         int size, move_size;
 284         int pos, pos2;
 285         int i;
 286
 287         if (!comm || strcmp(first, last) >= 0)
 288                 return;
 289
 290         /* Add the first entry using key_add */
 291         key_add(map, first, comm);
 292         pos = key_find(map, first);
 293         pos2 = key_find(map, last);
 294
 295         /* Now 'pos' is a stand-alone entry for 'first'.
 296          * If the entry before pos2 is a range start, update to start at 'last',
 297          * else discard it, and discard everything else between pos and pos2.
 298          * Then insert a stand-alone for 'last' and update 'pos' to be a
 299          * range-start.
 300          */
 301         if (pos2 - 1 > pos && IS_RANGE(map->comms[pos2-1])) {
 302                 free(map->keys[pos2-1]);
 303                 map->keys[pos2-1] = strdup(last);
 304                 pos2 -= 1;
 305         }
 306         /* Need to insert 'last', and remove extras. so +1 and -(pos2-pos-1); */
 307         move_size = 1 - (pos2 - pos - 1);
 308         size = size2alloc(map->size + move_size);
 309         if (size2alloc(map->size) < size) {
 310                 map->keys = realloc(map->keys, size * sizeof(map->keys[0]));
 311                 map->comms = realloc(map->comms,
 312                                      size * sizeof(struct command *));
 313         }
 314         for (i = pos + 1; i < pos2; i++) {
 315                 free(map->keys[i]);
 316                 command_put(GETCOMM(map->comms[i]));
 317         }
 318         memmove(map->keys+pos2 + move_size, map->keys+pos2,
 319                 (map->size - pos2) * sizeof(map->keys[0]));
 320         memmove(map->comms+pos2+ move_size, map->comms+pos2,
 321                 (map->size - pos2) * sizeof(struct command *));
 322
 323         map->comms[pos] = SET_RANGE(comm);
 324         map->keys[pos+1] = strdup(last);
 325         map->comms[pos+1] = command_get(comm);
 326         map->size += move_size;
 327         map->changed = True;
 328 }
 329
 330 void key_add_chain(struct map *map safe, struct map *chain)
 331 {
 332         while (map->chain)
 333                 map = map->chain;
 334         map->chain = chain;
 335 }
 336
 337 #if 0
 338 void key_del(struct map *map, wint_t k)
 339 {
 340         int pos;
 341
 342         pos = key_find(map, k, -1);
 343         if (pos >= map->size || strcmp(map->keys[pos], k) == 0)
 344                 return;
 345
 346         memmove(map->keys+pos, map->keys+pos+1,
 347                 (map->size-pos-1) * sizeof(map->keys[0]));
 348         memmove(map->comms+pos, map->comms+pos+1,
 349                 (map->size-pos-1) * sizeof(struct command *));
 350         map->size -= 1;
 351         map->changed = True;
 352 }
 353 #endif
 354
 355 int key_pfx_func(const struct cmd_info *ci safe)
 356 {
 357         struct pfx_cmd *m = container_of(ci->comm, struct pfx_cmd, c);
 358
 359         call("Mode:set-all", ci->focus, ci->num, NULL, m->pfx, ci->num2);
 360         return 1;
 361 }
 362
 363 struct command *key_lookup_cmd(struct map *m safe, const char *c safe)
 364 {
 365         int pos = key_find(m, c);
 366
 367         if (pos >= m->size)
 368                 ;
 369         else if (strcmp(m->keys[pos], c) == 0)
 370                 /* Exact match - use this entry */
 371                 return GETCOMM(m->comms[pos]);
 372         else if (pos > 0 && IS_RANGE(m->comms[pos-1]))
 373                 /* In a range, use previous */
 374                 return GETCOMM(m->comms[pos-1]);
 375
 376         return NULL;
 377 }
 378
 379 /* FIXME this makes lots of things non re-entrant */
 380 static struct backtrace {
 381         struct command *comm safe;
 382         const struct cmd_info *ci safe;
 383         struct backtrace *prev;
 384 } *backtrace;
 385 static int backtrace_depth;
 386
 387 static char *mark_info(struct mark *m)
 388 {
 389         char *ret = NULL;
 390
 391         if (!m) {
 392                 asprintf(&ret, "M-");
 393                 return ret;
 394         }
 395         if (!mark_valid(m)) {
 396                 asprintf(&ret, "M-FREED");
 397                 return ret;
 398         }
 399         ret = pane_call_ret(str, m->owner, "doc:debug:mark",
 400                             m->owner, 0, m);
 401         if (ret)
 402                 return ret;
 403
 404         asprintf(&ret, "M:%d<%p>%d", m->seq, m, m->ref.i);
 405         return ret;
 406 }
 407
 408 void LOG_BT(void)
 409 {
 410         struct backtrace *bt;
 411         LOG("Start Backtrace:");
 412         for (bt = backtrace; bt; bt = bt->prev) {
 413                 const struct cmd_info *ci = bt->ci;
 414                 struct command *h = ci->home->handle;
 415                 struct command *f = ci->focus->handle;
 416                 char *m1 = mark_info(ci->mark);
 417                 char *m2 = mark_info(ci->mark2);
 418
 419                 LOG(" H:%s \"%s\" F:%s: %d %s \"%s\" %d %s \"%s\" (%d,%d) %s",
 420                     h ? h->name : "?",
 421                     ci->key,
 422                     f ? f->name : "?",
 423                     ci->num, m1, ci->str,
 424                     ci->num2, m2, ci->str2,
 425                     ci->x, ci->y,
 426                     ci->comm2 ? ci->comm2->name : "");
 427                 free(m1);
 428                 free(m2);
 429         }
 430         LOG("End Backtrace");
 431 }
 432
 433 static int do_comm_call(struct command *comm safe,
 434                         const struct cmd_info *ci safe)
 435 {
 436         struct backtrace bt;
 437         int ret;
 438
 439         if (times_up_fast(ci->home))
 440                 return Efail;
 441         if (backtrace_depth > 100) {
 442                 backtrace_depth = 0;
 443                 LOG("Recursion limit of 100 reached");
 444                 LOG_BT();
 445                 backtrace_depth = 100;
 446                 pane_root(ci->home)->timestamp = 1;
 447                 return Efail;
 448         }
 449         bt.comm = comm;
 450         bt.ci = ci;
 451         bt.prev = backtrace;
 452         backtrace = &bt;
 453         backtrace_depth += 1;
 454         ret = comm->func(ci);
 455         backtrace = bt.prev;
 456         backtrace_depth -= 1;
 457         return ret;
 458 }
 459
 460 int key_lookup(struct map *m safe, const struct cmd_info *ci safe)
 461 {
 462         struct command *comm;
 463
 464         if (ci->hash && !key_present(m, ci->hash)) {
 465                 stat_count("bloom-miss");
 466                 return Efallthrough;
 467         }
 468
 469         comm = key_lookup_cmd(m, ci->key);
 470         if (comm == NULL) {
 471                 stat_count("bloom-hit-bad");
 472                 return Efallthrough;
 473         } else {
 474                 stat_count("bloom-hit-good");
 475                 ((struct cmd_info*)ci)->comm = comm;
 476
 477                 if (comm->func == keymap_list_func)
 478                         ((struct cmd_info*)ci)->comm = (struct command *safe)m;
 479
 480                 return do_comm_call(comm, ci);
 481         }
 482 }
 483
 484 int key_lookup_prefix(struct map *m safe, const struct cmd_info *ci safe)
 485 {
 486         const char *k = ci->key;
 487         int len = strlen(k);
 488         int pos = key_find(m, k);
 489         struct command *comm, *prev = NULL;
 490         int ret = Efallthrough;
 491         int i;
 492
 493         for (i = 0;
 494              ret == Efallthrough && pos+i < m->size &&
 495              strncmp(m->keys[pos+i], k, len) == 0;
 496              i++) {
 497                 comm = GETCOMM(m->comms[pos+i]);
 498                 if (comm && comm != prev) {
 499                         ((struct cmd_info*)ci)->comm = comm;
 500                         ((struct cmd_info*)ci)->key = m->keys[pos+i];
 501                         ret = do_comm_call(comm, ci);
 502                         ASSERT(ret >= Efallthrough || ret < Eunused);
 503                         prev = comm;
 504                         /* something might have been added, recalc
 505                          * start pos.
 506                          */
 507                         pos = key_find(m, k);
 508                 }
 509         }
 510         ((struct cmd_info*)ci)->key = k;
 511         return ret;
 512 }
 513
 514 int key_lookup_cmd_func(const struct cmd_info *ci safe)
 515 {
 516         struct lookup_cmd *l = container_of(ci->comm, struct lookup_cmd, c);
 517         struct map *m = safe_cast *l->m;
 518         int ret = key_lookup(m, ci);
 519
 520         while (!ret && m->chain) {
 521                 m = m->chain;
 522                 ret = key_lookup(m, ci);
 523         }
 524         return ret;
 525 }
 526
 527 /* key_handle.  Search towards root for the pane which handles the command.
 528  */
 529 int key_handle(const struct cmd_info *ci safe)
 530 {
 531         struct cmd_info *vci = (struct cmd_info*)ci;
 532         struct pane *p;
 533         unsigned int hash[2];
 534
 535         if (ci->mark && !mark_valid(ci->mark))
 536                 return Einval;
 537         if (ci->mark2 && !mark_valid(ci->mark2))
 538                 return Einval;
 539
 540         if (times_up(ci->home))
 541                 return Efail;
 542         time_start_key(ci->key);
 543         if ((void*) ci->comm) {
 544                 int ret = do_comm_call(ci->comm, ci);
 545                 time_stop_key(ci->key);
 546                 return ret;
 547         }
 548
 549         hash_str(ci->key, -1, hash);
 550         vci->hash = hash;
 551
 552         /* If 'home' is set, search from there, else search
 553          * from focus
 554          */
 555         p = ci->home;
 556         if (!p)
 557                 p = ci->focus;
 558
 559         while (p) {
 560                 int ret = Efallthrough;
 561                 if (p->handle && !(p->damaged & DAMAGED_CLOSED)) {
 562                         vci->home = p;
 563                         vci->comm = p->handle;
 564                         /* Don't add this to the call stack as it
 565                          * should simple call the desired function and
 566                          * that will appear on the call stack.
 567                          */
 568                         ret = p->handle->func(ci);
 569                 }
 570                 if (ret != Efallthrough) {
 571                         time_stop_key(ci->key);
 572                         /* 'p' might have been destroyed */
 573                         return ret;
 574                 }
 575                 if (p == p->parent)
 576                         p = NULL;
 577                 else
 578                         p = p->parent;
 579         }
 580         time_stop_key(ci->key);
 581         return Efallthrough;
 582 }