core-keymap.c

   1 /*
   2  * Copyright Neil Brown ©2015 <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 struct map {
  49         int     size;
  50         char    **keys;
  51         struct command **comms;
  52 };
  53
  54 static inline struct command *GETCOMM(struct command *c)
  55 {
  56         return (struct command *)(((unsigned long)c) & ~1UL);
  57 }
  58
  59 static inline int IS_RANGE(struct command *c)
  60 {
  61         return ((unsigned long)c) & 1;
  62 }
  63
  64 static inline struct command *SET_RANGE(struct command *c)
  65 {
  66         return (struct command *)(((unsigned long)c) | 1UL);
  67 }
  68
  69 static int size2alloc(int size)
  70 {
  71         /* Alway multiple of 8. */
  72         return ((size-1) | 7) + 1;
  73 }
  74
  75 struct map *key_alloc(void)
  76 {
  77         struct map *m = malloc(sizeof(*m));
  78         memset(m, 0, sizeof(*m));
  79         return m;
  80 }
  81
  82 void key_free(struct map *m)
  83 {
  84         free(m->keys);
  85         free(m->comms);
  86         free(m);
  87 }
  88
  89 /* Find first entry >= k */
  90 static int key_find(struct map *map, char *k)
  91 {
  92         int lo = 0;
  93         int hi = map->size;
  94
  95         /* all entries before 'lo' are < k.
  96          * all entries at 'hi' or later are >= k.
  97          * So when lo==hi, hi is the answer.
  98          */
  99         while (hi > lo) {
 100                 int mid = (hi + lo)/ 2;
 101                 if (strcmp(map->keys[mid], k) < 0)
 102                         lo = mid+1;
 103                 else
 104                         hi = mid;
 105         }
 106         return hi;
 107 }
 108
 109 void key_add(struct map *map, char *k, struct command *comm)
 110 {
 111         int size;
 112         int pos;
 113         struct command *comm2 = NULL;
 114         int ins_cnt;
 115
 116         if (!comm)
 117                 return;
 118
 119         pos = key_find(map, k);
 120         /* cases:
 121          * 1/ match start of range: insert before
 122          * 2/ match non-range start: replace
 123          * 3/ not in range: insert before like 1
 124          * 4/ in a range: insert match and range start.
 125          */
 126         if (pos >= map->size) {
 127                 /* Insert k,comm - default action */
 128         } else if (strcmp(k, map->keys[pos]) == 0) {
 129                 /* match: need to check if range-start */
 130                 if (IS_RANGE(map->comms[pos])) {
 131                         /* Changing the start of a range, insert and exact match */
 132                 } else {
 133                         /* replace a non-range */
 134                         /* FIXME do I need to release the old command */
 135                         map->comms[pos] = comm;
 136                         return;
 137                 }
 138         } else if (pos > 0 && IS_RANGE(map->comms[pos-1])) {
 139                 /* insert within a range.
 140                  * Add given command as non-range match, and old command
 141                  * as new range start
 142                  */
 143                 comm2 = map->comms[pos-1];
 144         } else {
 145                 /* Not in a range, simple insert */
 146         }
 147
 148         ins_cnt = comm2 ? 2 : 1;
 149         size = size2alloc(map->size + ins_cnt);
 150
 151
 152         if (size2alloc(map->size) != size) {
 153                 map->keys = realloc(map->keys, size * sizeof(map->keys[0]));
 154                 map->comms = realloc(map->comms,
 155                                      size * sizeof(struct command *));
 156         }
 157
 158         memmove(map->keys+pos+ins_cnt, map->keys+pos,
 159                 (map->size - pos) * sizeof(map->keys[0]));
 160         memmove(map->comms+pos+ins_cnt, map->comms+pos,
 161                 (map->size - pos) * sizeof(struct command *));
 162         map->keys[pos] = strdup(k);
 163         map->comms[pos] = comm;
 164         if (comm2) {
 165                 map->keys[pos+1] = k;
 166                 map->comms[pos+1] = comm2;
 167         }
 168         map->size += ins_cnt;
 169 }
 170
 171 void key_add_range(struct map *map, char *first, char *last,
 172                    struct command *comm)
 173 {
 174         int size, move_size;
 175         int pos, pos2;
 176
 177         if (!comm || strcmp(first, last) >= 0)
 178                 return;
 179
 180         /* Add the first entry using key_add */
 181         key_add(map, first, comm);
 182         pos = key_find(map, first);
 183         pos2 = key_find(map, last);
 184
 185         /* Now 'pos' is a stand-alone entry for 'first'.
 186          * If the entry before pos2 is a range start, update to start at 'last',
 187          * else discard it, and discard everything else between pos and pos2.
 188          * Then insert a stand-alone for 'last' and update 'pos' to be a range-start.
 189          */
 190         if (pos2 - 1 > pos && IS_RANGE(map->comms[pos2-1])) {
 191                 map->keys[pos2-1] = last;
 192                 pos2 -= 1;
 193         }
 194         /* Need to insert 'last', and remove extras. so +1 and -(pos2-pos-1); */
 195         move_size = 1 - (pos2 - pos - 1);
 196         size = size2alloc(map->size + move_size);
 197         if (size2alloc(map->size) < size) {
 198                 map->keys = realloc(map->keys, size * sizeof(map->keys[0]));
 199                 map->comms = realloc(map->comms,
 200                                      size * sizeof(struct command *));
 201         }
 202
 203         memmove(map->keys+pos2 + move_size, map->keys+pos2,
 204                 (map->size - pos2) * sizeof(map->keys[0]));
 205         memmove(map->comms+pos2+ move_size, map->comms+pos2,
 206                 (map->size - pos2) * sizeof(struct command *));
 207
 208         map->comms[pos] = SET_RANGE(comm);
 209         map->keys[pos+1] = last;
 210         map->comms[pos+1] = comm;
 211         map->size += move_size;
 212         return;
 213 }
 214
 215 #if 0
 216 void key_del(struct map *map, wint_t k)
 217 {
 218         int pos;
 219
 220         pos = key_find(map, k);
 221         if (pos >= map->size || strcmp(map->keys[pos], k) == 0)
 222                 return;
 223
 224         memmove(map->keys+pos, map->keys+pos+1,
 225                 (map->size-pos-1) * sizeof(map->keys[0]));
 226         memmove(map->comms+pos, map->comms+pos+1,
 227                 (map->size-pos-1) * sizeof(struct command *));
 228         map->size -= 1;
 229 }
 230 #endif
 231
 232 struct modmap {
 233         char    *name;
 234         struct command comm;
 235 };
 236
 237 static int key_prefix(const struct cmd_info *ci)
 238 {
 239         struct modmap *m = container_of(ci->comm, struct modmap, comm);
 240
 241         pane_set_mode(ci->focus, m->name);
 242         return 1;
 243 }
 244
 245 struct command *key_register_prefix(char *name)
 246 {
 247         struct modmap *mm = malloc(sizeof(*mm));
 248
 249         mm->name = strdup(name);
 250         mm->comm.func = key_prefix;
 251         return &mm->comm;
 252 }
 253
 254 struct command *key_lookup_cmd(struct map *m, char *c)
 255 {
 256         int pos = key_find(m, c);
 257
 258         if (pos >= m->size)
 259                 return NULL;
 260         if (strcmp(m->keys[pos], c) == 0) {
 261                 /* Exact match - use this entry */
 262                 return GETCOMM(m->comms[pos]);
 263         } else if (pos > 0 && IS_RANGE(m->comms[pos-1])) {
 264                 /* In a range, use previous */
 265                 return GETCOMM(m->comms[pos-1]);
 266         } else
 267                 return NULL;
 268 }
 269
 270 int key_lookup(struct map *m, const struct cmd_info *ci)
 271 {
 272         int pos = key_find(m, ci->key);
 273         struct command *comm;
 274
 275         if (pos >= m->size)
 276                 return 0;
 277         if (strcmp(m->keys[pos], ci->key) == 0) {
 278                 /* Exact match - use this entry */
 279                 comm = GETCOMM(m->comms[pos]);
 280         } else if (pos > 0 && IS_RANGE(m->comms[pos-1])) {
 281                 /* In a range, use previous */
 282                 comm = GETCOMM(m->comms[pos-1]);
 283         } else
 284                 return 0;
 285         ((struct cmd_info*)ci)->comm = comm;
 286         return comm->func(ci);
 287 }
 288
 289 int key_lookup_prefix(struct map *m, const struct cmd_info *ci)
 290 {
 291         int pos = key_find(m, ci->key);
 292         struct command *comm, *prev = NULL;
 293         int len = strlen(ci->key);
 294
 295         while (pos < m->size && strncmp(m->keys[pos], ci->key, len) == 0) {
 296                 comm = GETCOMM(m->comms[pos]);
 297                 if (comm && comm != prev) {
 298                         int ret;
 299                         ((struct cmd_info*)ci)->comm = comm;
 300                         ret = comm->func(ci);
 301                         if (ret)
 302                                 return ret;
 303                         prev = comm;
 304                 }
 305         }
 306         return 0;
 307 }
 308
 309 int key_lookup_cmd_func(const struct cmd_info *ci)
 310 {
 311         struct lookup_cmd *l = container_of(ci->comm, struct lookup_cmd, c);
 312         int ret = key_lookup(*l->m, ci);
 313
 314         if (!ret && l->dflt && *l->dflt)
 315                 ret = key_lookup(*l->dflt, ci);
 316         return ret;
 317 }
 318
 319 /* key_handle.  Search towards root for the pane which handles the command.
 320  */
 321 int key_handle(const struct cmd_info *ci)
 322 {
 323         struct cmd_info *vci = (struct cmd_info*)ci;
 324         struct pane *p;
 325
 326         if (ci->comm)
 327                 return ci->comm->func(ci);
 328
 329         /* If 'home' is set, search from there, else search
 330          * from focus
 331          */
 332         p = ci->home;
 333         if (!p)
 334                 p = ci->focus;
 335
 336         while (p) {
 337                 int ret = 0;
 338                 if (p->handle) {
 339                         vci->home = p;
 340                         vci->comm = p->handle;
 341                         ret = p->handle->func(ci);
 342                 }
 343                 if (ret)
 344                         /* 'p' might have been destroyed */
 345                         return ret;
 346                 p = p->parent;
 347         }
 348         return 0;
 349 }