core-keymap.c

   1 /*
   2  * Copyright Neil Brown <neil@brown.name> 2015
   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] = 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         bool    transient;
 235         struct command comm;
 236 };
 237
 238 static int key_prefix(struct cmd_info *ci)
 239 {
 240         struct modmap *m = container_of(ci->comm, struct modmap, comm);
 241
 242         pane_set_mode(ci->home, m->name, m->transient);
 243         return 1;
 244 }
 245
 246 struct command *key_register_prefix(char *name)
 247 {
 248         struct modmap *mm = malloc(sizeof(*mm));
 249
 250         mm->name = strdup(name);
 251         mm->transient = 1;
 252         mm->comm.func = key_prefix;
 253         return &mm->comm;
 254 }
 255
 256 struct command *key_lookup_cmd(struct map *m, char *c)
 257 {
 258         int pos = key_find(m, c);
 259
 260         if (pos >= m->size)
 261                 return NULL;
 262         if (strcmp(m->keys[pos], c) == 0) {
 263                 /* Exact match - use this entry */
 264                 return GETCOMM(m->comms[pos]);
 265         } else if (pos > 0 && IS_RANGE(m->comms[pos-1])) {
 266                 /* In a range, use previous */
 267                 return GETCOMM(m->comms[pos-1]);
 268         } else
 269                 return NULL;
 270 }
 271
 272 int key_lookup(struct map *m, struct cmd_info *ci)
 273 {
 274         int pos = key_find(m, ci->key);
 275         struct command *comm;
 276
 277         if (pos >= m->size)
 278                 return 0;
 279         if (strcmp(m->keys[pos], ci->key) == 0) {
 280                 /* Exact match - use this entry */
 281                 comm = GETCOMM(m->comms[pos]);
 282         } else if (pos > 0 && IS_RANGE(m->comms[pos-1])) {
 283                 /* In a range, use previous */
 284                 comm = GETCOMM(m->comms[pos-1]);
 285         } else
 286                 return 0;
 287         ci->comm = comm;
 288         return comm->func(ci);
 289 }
 290
 291 int key_lookup_cmd_func(struct cmd_info *ci)
 292 {
 293         struct lookup_cmd *l = container_of(ci->comm, struct lookup_cmd, c);
 294         return key_lookup(*l->m, ci);
 295 }
 296
 297 int key_handle(struct cmd_info *ci)
 298 {
 299         struct pane *p = ci->focus;
 300         int ret = 0;
 301
 302         if (ci->comm)
 303                 return ci->comm->func(ci);
 304
 305         ci->hx = ci->x;
 306         ci->hy = ci->y;
 307         if (!ci->pointp) {
 308                 struct pane *p2 = p;
 309                 while (p2 && !p2->point)
 310                         p2 = p2->parent;
 311                 if (p2)
 312                         ci->pointp = &p2->point;
 313         }
 314         while (ret == 0 && p) {
 315                 if (p->handle) {
 316                         ci->home = p;
 317                         ci->comm = p->handle;
 318                         ret = p->handle->func(ci);
 319                 }
 320                 if (ret)
 321                         /* 'p' might have been destroyed */
 322                         break;
 323                 if (ci->hx >= 0) {
 324                         ci->hx += p->x;
 325                         ci->hy += p->y;
 326                 }
 327                 p = p->parent;
 328         }
 329         return ret;
 330 }
 331
 332 int key_handle_focus(struct cmd_info *ci)
 333 {
 334         /* Handle this in the focus pane, so x,y are irrelevant */
 335         struct pane *p = ci->focus;
 336         ci->x = -1;
 337         ci->y = -1;
 338         while (p->focus) {
 339                 if (p->point && !ci->pointp)
 340                         ci->pointp = &p->point;
 341                 p = p->focus;
 342         }
 343         ci->focus = p;
 344         ci->comm = NULL;
 345         return key_handle(ci);
 346 }
 347
 348 int key_handle_xy(struct cmd_info *ci)
 349 {
 350         /* Handle this in child with x,y co-ords */
 351         struct pane *p = ci->focus;
 352         int x = ci->x;
 353         int y = ci->y;
 354
 355         while (1) {
 356                 struct pane *t, *chld = NULL;
 357
 358                 if (p->point)
 359                         ci->pointp = &p->point;
 360
 361                 list_for_each_entry(t, &p->children, siblings) {
 362                         if (x < t->x || x >= t->x + t->w)
 363                                 continue;
 364                         if (y < t->y || y >= t->y + t->h)
 365                                 continue;
 366                         if (chld == NULL || t->z > chld->z)
 367                                 chld = t;
 368                 }
 369                 /* descend into chld */
 370                 if (!chld)
 371                         break;
 372                 x -= chld->x;
 373                 y -= chld->y;
 374                 p = chld;
 375         }
 376         ci->x = x;
 377         ci->y = y;
 378         ci->focus = p;
 379         ci->comm = NULL;
 380         return key_handle(ci);
 381 }