/*
- * Copyright Neil Brown ©2015-2019 <neil@brown.name>
+ * Copyright Neil Brown ©2015-2023 <neil@brown.name>
* May be distributed under terms of GPLv2 - see file:COPYING
*
* Keymaps for edlib.
* Keys are ordered for fast binary-search lookup.
* A "key" is an arbitrary string which typically contains
* some 'mode' prefix and some specific tail.
- * e.g emacs-M-C-Chr-x is Meta-Control-X in emacs mode.
+ * e.g emacs:A:C-X is Alt-Control-X in emacs mode.
* As far as the map is concerned, it is just a lexically order string.
*
* A 'command' is a struct provided by any of various
*
* A range can be stored by setting the lsb of the command pointer at
* the start of the range.
- * When searching for a key we find the first entry that is not less than the target.
- * If it is an exact match, use it.
- * If previous entry exists and has the lsb set, then use that command.
+ * When searching for a key we find the first entry that is not less
+ * than the target. If it is an exact match, use it. If previous entry
+ * exists and has the lsb set, then use that command.
*
- * So to add a range, the start is entered with lsb set, and the end it entered with
- * lsb clear.
+ * So to add a range, the start is entered with lsb set, and the end it
+ * entered with lsb clear.
*
* If a key is registered a second time, the new over-rides the old.
- * This is particularly useful for registering a range, and then some exceptions.
+ * This is particularly useful for registering a range, and then some
+ * exceptions.
* To delete a key from a range we need to make two ranges, one that ends
* just before the new key, one that starts just after.
* The 'ends just before' is easy - we just add the new key or range.
*
*/
+#define _GNU_SOURCE /* for asprintf */
#include <unistd.h>
#include <stdlib.h>
#include <memory.h>
+#include <stdio.h>
#include "core.h"
#include "misc.h"
}
struct map {
- unsigned long bloom[256 / (sizeof(long)*8) ];
- short changed;
- short prefix_len;
- int size;
- struct map *chain;
- char * safe *keys safe;
- struct command * safe *comms safe;
+ unsigned long bloom[256 / (sizeof(unsigned long)*8) ];
+ bool changed;
+ bool check_all;
+ short size;
+ struct map *chain;
+ char * safe *keys safe;
+ struct command * safe *comms safe;
};
static inline struct command * safe GETCOMM(struct command *c safe)
return (struct command *)(((unsigned long)c) | 1UL);
}
+DEF_CMD(keymap_list)
+{
+ struct map *m;
+ int len = ci->str ? strlen(ci->str) : 0;
+ int i;
+
+ if (ci->comm == &keymap_list)
+ /* should be impossible */
+ return Efallthrough;
+ /* ci->comm MUST be the keymap */
+ m = (struct map* safe)ci->comm;
+
+ for (i = 0; i < m->size; i++)
+ if (!len || strncmp(ci->str, m->keys[i], len) == 0)
+ if (comm_call(ci->comm2, "cb", ci->focus,
+ IS_RANGE(m->comms[i]), NULL, m->keys[i]) <= 0)
+ break;
+ return Efallthrough;
+}
+
static int size2alloc(int size)
{
/* Alway multiple of 8. */
{
struct map *m = calloc(1, sizeof(*m));
- m->prefix_len = -1;
+ key_add(m, "keymap:list", &keymap_list);
return m;
}
free(m);
}
-static int hash_str(char *key safe, int len)
+static bool hash_str(const char *key safe, int len, unsigned int *hashes safe)
{
int i;
int h = 0;
- for (i = 0; (len < 0 || i < len) && key[i]; i++)
+ bool prefix = False;
+
+ for (i = 0; (len < 0 || i < len) && key[i]; i++) {
h = qhash(key[i], h);
- return h;
+ if (key[i] == '-' || key[i] == ':') {
+ prefix = True;
+ break;
+ }
+ }
+ hashes[1] = h;
+ for (; (len < 0 || i < len) && key[i]; i++)
+ h = qhash(key[i], h);
+ hashes[0] = h;
+ return prefix;
}
inline static void set_bit(unsigned long *set safe, int bit)
{
- set[bit/(sizeof(unsigned long)*8)] |= 1UL << (bit % (sizeof(unsigned long)*8));
+ set[bit/(sizeof(unsigned long)*8)] |=
+ 1UL << (bit % (sizeof(unsigned long)*8));
}
inline static int test_bit(unsigned long *set safe, int bit)
{
- return !! (set[bit/(sizeof(unsigned long)*8)] & (1UL << (bit % (sizeof(unsigned long)*8))));
+ return !! (set[bit/(sizeof(unsigned long)*8)] &
+ (1UL << (bit % (sizeof(unsigned long)*8))));
}
-
-static int key_present(struct map *map safe, char *key, int klen, unsigned int *hashp safe)
+static bool key_present(struct map *map safe, unsigned int *hashes safe)
{
- int hash;
-
if (map->changed) {
int i;
+ map->check_all = False;
for (i = 0; i < map->size; i++) {
- hash = hash_str(map->keys[i], map->prefix_len);
- set_bit(map->bloom, hash&0xff);
- set_bit(map->bloom, (hash>>8)&0xff);
- set_bit(map->bloom, (hash>>16)&0xff);
+ unsigned int h[2];
+ bool prefix = hash_str(map->keys[i], -1, h);
+ if (IS_RANGE(map->comms[i])) {
+ if (!prefix)
+ map->check_all = True;
+ set_bit(map->bloom, h[1]&0xff);
+ set_bit(map->bloom, (h[1]>>8)&0xff);
+ set_bit(map->bloom, (h[1]>>16)&0xff);
+ } else {
+ set_bit(map->bloom, h[0]&0xff);
+ set_bit(map->bloom, (h[0]>>8)&0xff);
+ set_bit(map->bloom, (h[0]>>16)&0xff);
+ }
}
- map->changed = 0;
+ map->changed = False;
}
- if (map->prefix_len < 0 || klen <= map->prefix_len)
- hash = hashp[0];
- else
- hash = hashp[map->prefix_len];
- return (test_bit(map->bloom, hash&0xff) &&
- test_bit(map->bloom, (hash>>8)&0xff) &&
- test_bit(map->bloom, (hash>>16)&0xff));
+ if (map->check_all)
+ return True;
+
+ if (test_bit(map->bloom, hashes[0]&0xff) &&
+ test_bit(map->bloom, (hashes[0]>>8)&0xff) &&
+ test_bit(map->bloom, (hashes[0]>>16)&0xff))
+ return True;
+ if (test_bit(map->bloom, hashes[1]&0xff) &&
+ test_bit(map->bloom, (hashes[1]>>8)&0xff) &&
+ test_bit(map->bloom, (hashes[1]>>16)&0xff))
+ return True;
+ return False;
}
/* Find first entry >= k */
-static int key_find_len(struct map *map safe, char *k safe, int len)
+static int key_find(struct map *map safe, const char *k safe)
{
int lo = 0;
int hi = map->size;
*/
while (hi > lo) {
int mid = (hi + lo)/ 2;
- int cmp = strncmp(map->keys[mid], k, len);
- if (cmp < 0)
+ if (strcmp(map->keys[mid], k) < 0)
lo = mid+1;
else
hi = mid;
return hi;
}
-static int key_find(struct map *map safe, char *k safe)
-{
- return key_find_len(map, k, strlen(k));
-}
-
-void key_add(struct map *map safe, char *k safe, struct command *comm)
+void key_add(struct map *map safe, const char *k safe, struct command *comm)
{
int size;
int pos;
if (!comm)
return;
+ if (strcmp(k, "Close") == 0 &&
+ !comm->closed_ok) {
+ LOG("WARNING: Command %s registered for \"Close\" but not marked closed_ok",
+ comm->name);
+ }
pos = key_find(map, k);
/* cases:
} else if (strcmp(k, map->keys[pos]) == 0) {
/* match: need to check if range-start */
if (IS_RANGE(map->comms[pos])) {
- /* Changing the start of a range, insert an exact match */
+ /* Changing the start of a range,
+ * insert an exact match */
} else {
/* replace a non-range */
command_put(map->comms[pos]);
map->comms[pos+1] = SET_RANGE(command_get(GETCOMM(comm2)));
}
map->size += ins_cnt;
- map->changed = 1;
+ map->changed = True;
}
-void key_add_range(struct map *map safe, char *first safe, char *last safe,
+void key_add_range(struct map *map safe,
+ const char *first safe, const char *last safe,
struct command *comm)
{
int size, move_size;
int pos, pos2;
- int prefix;
int i;
if (!comm || strcmp(first, last) >= 0)
/* Now 'pos' is a stand-alone entry for 'first'.
* If the entry before pos2 is a range start, update to start at 'last',
* else discard it, and discard everything else between pos and pos2.
- * Then insert a stand-alone for 'last' and update 'pos' to be a range-start.
+ * Then insert a stand-alone for 'last' and update 'pos' to be a
+ * range-start.
*/
if (pos2 - 1 > pos && IS_RANGE(map->comms[pos2-1])) {
free(map->keys[pos2-1]);
map->keys[pos+1] = strdup(last);
map->comms[pos+1] = command_get(comm);
map->size += move_size;
- map->changed = 1;
- for (prefix = 0;
- first[prefix] && first[prefix+1] == last[prefix+1];
- prefix += 1)
- ;
- if (map->prefix_len < 0 || map->prefix_len > prefix)
- map->prefix_len = prefix;
+ map->changed = True;
}
void key_add_chain(struct map *map safe, struct map *chain)
map->chain = chain;
}
-
#if 0
void key_del(struct map *map, wint_t k)
{
memmove(map->comms+pos, map->comms+pos+1,
(map->size-pos-1) * sizeof(struct command *));
map->size -= 1;
- map->changed = 1;
+ map->changed = True;
}
#endif
{
struct pfx_cmd *m = container_of(ci->comm, struct pfx_cmd, c);
- call("Mode:set-mode", ci->focus, 0, NULL, m->pfx);
- call("Mode:set-num", ci->focus, ci->num);
- call("Mode:set-num2", ci->focus, ci->num2);
+ call("Mode:set-all", ci->focus, ci->num, NULL, m->pfx, ci->num2);
return 1;
}
-struct command *key_lookup_cmd(struct map *m safe, char *c safe,
- char **cret, int *lenret)
+struct command *key_lookup_cmd(struct map *m safe, const char *c safe)
{
- /* If 'k' contains an ASCII US (Unit Separator, 0o37 0x1f 31),
- * it represents multiple keys.
- * Call key_find() on each of them until success.
- */
- while (*c) {
- char *end = strchr(c, '\037');
- int pos;
-
- if (!end)
- end = c + strlen(c);
- pos = key_find_len(m, c, end - c);
-
- if (pos >= m->size)
- ;
- else if (strncmp(m->keys[pos], c, end - c) == 0 &&
- m->keys[pos][end - c] == '\0') {
- /* Exact match - use this entry */
- if (cret)
- *cret = c;
- if (lenret)
- *lenret = end - c;
- return GETCOMM(m->comms[pos]);
- } else if (pos > 0 && IS_RANGE(m->comms[pos-1])) {
- /* In a range, use previous */
- if (cret)
- *cret = c;
- if (lenret)
- *lenret = end - c;
- return GETCOMM(m->comms[pos-1]);
- }
- c = end;
- while (*c == '\037')
- c++;
- }
+ int pos = key_find(m, c);
+
+ if (pos >= m->size)
+ ;
+ else if (strcmp(m->keys[pos], c) == 0)
+ /* Exact match - use this entry */
+ return GETCOMM(m->comms[pos]);
+ else if (pos > 0 && IS_RANGE(m->comms[pos-1]))
+ /* In a range, use previous */
+ return GETCOMM(m->comms[pos-1]);
+
return NULL;
}
+/* FIXME this makes lots of things non re-entrant */
+static struct backtrace {
+ struct command *comm safe;
+ const struct cmd_info *ci safe;
+ struct backtrace *prev;
+} *backtrace;
+static int backtrace_depth;
+
+static char *mark_info(struct mark *m)
+{
+ char *ret = NULL;
+
+ if (!m) {
+ asprintf(&ret, "M-");
+ return ret;
+ }
+ if (!mark_valid(m)) {
+ asprintf(&ret, "M-FREED");
+ return ret;
+ }
+ ret = pane_call_ret(str, m->owner, "doc:debug:mark",
+ m->owner, 0, m);
+ if (ret)
+ return ret;
+
+ asprintf(&ret, "M:%d<%p>%d", m->seq, m, m->ref.i);
+ return ret;
+}
+
+void LOG_BT(void)
+{
+ struct backtrace *bt;
+ LOG("Start Backtrace:");
+ for (bt = backtrace; bt; bt = bt->prev) {
+ const struct cmd_info *ci = bt->ci;
+ struct command *h = ci->home->handle;
+ struct command *f = ci->focus->handle;
+ char *m1 = mark_info(ci->mark);
+ char *m2 = mark_info(ci->mark2);
+
+ LOG(" H:%s \"%s\" F:%s: %d %s \"%s\" %d %s \"%s\" (%d,%d) %s",
+ h ? h->name : "?",
+ ci->key,
+ f ? f->name : "?",
+ ci->num, m1, ci->str,
+ ci->num2, m2, ci->str2,
+ ci->x, ci->y,
+ ci->comm2 ? ci->comm2->name : "");
+ free(m1);
+ free(m2);
+ }
+ LOG("End Backtrace");
+}
+
+int do_comm_call(struct command *comm safe, const struct cmd_info *ci safe)
+{
+ struct backtrace bt;
+ int ret;
+
+ if (ci->home->damaged & DAMAGED_DEAD)
+ return Efail;
+ if (times_up_fast(ci->home))
+ return Efail;
+ if ((ci->home->damaged & DAMAGED_CLOSED) &&
+ !comm->closed_ok)
+ return Efallthrough;
+
+ if (backtrace_depth > 100) {
+ backtrace_depth = 0;
+ LOG("Recursion limit of 100 reached");
+ LOG_BT();
+ backtrace_depth = 100;
+ pane_root(ci->home)->timestamp = 1;
+ return Efail;
+ }
+ bt.comm = comm;
+ bt.ci = ci;
+ bt.prev = backtrace;
+ backtrace = &bt;
+ backtrace_depth += 1;
+ ret = comm->func(ci);
+ backtrace = bt.prev;
+ backtrace_depth -= 1;
+ return ret;
+}
+
int key_lookup(struct map *m safe, const struct cmd_info *ci safe)
{
struct command *comm;
- char *key;
- int len;
- if (ci->hash && !key_present(m, ci->key, strlen(ci->key), ci->hash)) {
+ if (ci->hash && !key_present(m, ci->hash)) {
stat_count("bloom-miss");
return Efallthrough;
}
- comm = key_lookup_cmd(m, ci->key, &key, &len);
- if (comm == NULL || key == NULL) {
+ comm = key_lookup_cmd(m, ci->key);
+ if (comm == NULL) {
stat_count("bloom-hit-bad");
return Efallthrough;
} else {
- /* This is message, but when there are multiple
- * keys, we need to pass down the one that was matched.
- */
- int ret;
- char *oldkey = ci->key;
- char tail = key[len];
-
stat_count("bloom-hit-good");
- if (key[len])
- key[len] = 0;
((struct cmd_info*)ci)->comm = comm;
- ((struct cmd_info*)ci)->key = key;
- ret = comm->func(ci);
- ((struct cmd_info*)ci)->key = oldkey;
- if (tail)
- key[len] = tail;
- return ret;
+
+ if (comm->func == keymap_list_func)
+ ((struct cmd_info*)ci)->comm = (struct command *safe)m;
+
+ return do_comm_call(comm, ci);
}
}
-int key_lookup_prefix(struct map *m safe, const struct cmd_info *ci safe)
+int key_lookup_prefix(struct map *m safe, const struct cmd_info *ci safe,
+ bool simple)
{
- int pos = key_find(m, ci->key);
+ /* A "Simple" lookup avoids the backtrace. It is used in
+ * signal handlers.
+ */
+ const char *k = ci->key;
+ int len = strlen(k);
+ int pos = key_find(m, k);
struct command *comm, *prev = NULL;
- int len = strlen(ci->key);
- char *k = ci->key;
+ int ret = Efallthrough;
+ int i;
- while (pos < m->size && strncmp(m->keys[pos], k, len) == 0) {
- comm = GETCOMM(m->comms[pos]);
+ for (i = 0;
+ ret == Efallthrough && pos+i < m->size &&
+ strncmp(m->keys[pos+i], k, len) == 0;
+ i++) {
+ comm = GETCOMM(m->comms[pos+i]);
if (comm && comm != prev) {
- int ret;
((struct cmd_info*)ci)->comm = comm;
- ((struct cmd_info*)ci)->key = m->keys[pos];
- ret = comm->func(ci);
- ASSERT(ret >= 0 || ret < Eunused);
- if (ret)
- return ret;
+ ((struct cmd_info*)ci)->key = m->keys[pos+i];
+ if (simple)
+ ret = comm->func(ci);
+ else
+ ret = do_comm_call(comm, ci);
+ ASSERT(ret >= Efallthrough || ret < Eunused);
prev = comm;
+ /* something might have been added, recalc
+ * start pos.
+ */
+ pos = key_find(m, k);
}
- pos += 1;
}
((struct cmd_info*)ci)->key = k;
- return 0;
+ return ret;
}
int key_lookup_cmd_func(const struct cmd_info *ci safe)
{
struct cmd_info *vci = (struct cmd_info*)ci;
struct pane *p;
- unsigned int hash[30];
- int h= 0;
- int i;
+ unsigned int hash[2];
+ if (ci->mark && !mark_valid(ci->mark))
+ return Einval;
+ if (ci->mark2 && !mark_valid(ci->mark2))
+ return Einval;
+
+ if (times_up(ci->home))
+ return Efail;
time_start_key(ci->key);
if ((void*) ci->comm) {
- int ret = ci->comm->func(ci);
+ int ret = do_comm_call(ci->comm, ci);
time_stop_key(ci->key);
return ret;
}
- for (i = 0; i < 30 && ci->key[i]; i++) {
- h = qhash(ci->key[i], h);
- if (i+1 < 30)
- hash[i+1] = h;
- if (ci->key[i] == '\037')
- // Disable hash for multi-keys
- i = 30;
- }
- hash[0] = h;
- if (i < 30)
- vci->hash = hash;
+ hash_str(ci->key, -1, hash);
+ vci->hash = hash;
/* If 'home' is set, search from there, else search
* from focus
p = ci->focus;
while (p) {
- int ret = 0;
- if (p->handle) {
+ int ret = Efallthrough;
+ if (p->handle &&
+ (p->handle->closed_ok ||
+ !(p->damaged & DAMAGED_CLOSED))) {
vci->home = p;
vci->comm = p->handle;
+ /* Don't add this to the call stack as it
+ * should simply call the desired function and
+ * that will appear on the call stack.
+ */
ret = p->handle->func(ci);
}
- if (ret) {
+ if (ret != Efallthrough) {
time_stop_key(ci->key);
/* 'p' might have been destroyed */
return ret;
}
- p = p->parent;
+ if (p == p->parent)
+ p = NULL;
+ else
+ p = p->parent;
}
time_stop_key(ci->key);
- return 0;
+ return Efallthrough;
}