eval: Use generated hash to look up function list

Problems:
- Disables cross-compiling (alternative: keeps two hash implementations which
  need to be synchronized with each other).
- Puts code-specific name literals into CMakeLists.txt.
- Workaround for lua’s absence of bidirectional pipe communication is rather
  ugly.

5 files changed, 204 insertions, 88 deletions

diff --git a/scripts/geneval.lua b/scripts/geneval.lua
index 1f8a14d27b..c9533d7908 100644
--- a/scripts/geneval.lua
+++ b/scripts/geneval.lua
@@ -15,28 +15,20 @@ end
 package.path = nvimsrcdir .. '/?.lua;' .. package.path
 
 local funcsfname = autodir .. '/funcs.generated.h'
-local funcsfile = io.open(funcsfname, 'w')
+
+local funcspipe = io.open(funcsfname .. '.hsh', 'w')
 
 local funcs = require('eval')
 
-local sorted_funcs = {}
 for name, def in pairs(funcs.funcs) do
-  def.name = name
-  def.args = def.args or 0
-  if type(def.args) == 'number' then
-    def.args = {def.args, def.args}
-  elseif #def.args == 1 then
-    def.args[2] = 'MAX_FUNC_ARGS'
+  args = def.args or 0
+  if type(args) == 'number' then
+    args = {args, args}
+  elseif #args == 1 then
+    args[2] = 'MAX_FUNC_ARGS'
   end
-  def.func = def.func or ('f_' .. def.name)
-  sorted_funcs[#sorted_funcs + 1] = def
-end
-table.sort(sorted_funcs, function(a, b) return a.name < b.name end)
-
-funcsfile:write('static const VimLFuncDef functions[] = {\n')
-for _, def in ipairs(sorted_funcs) do
-  funcsfile:write(('  { "%s", %s, %s, &%s },\n'):format(
-      def.name, def.args[1], def.args[2], def.func
-  ))
+  func = def.func or ('f_' .. name)
+  local val = ('{ %s, %s, &%s }'):format(args[1], args[2], func)
+  funcspipe:write(name .. '\n' .. val .. '\n')
 end
-funcsfile:write('};\n')
+funcspipe:close()
diff --git a/src/genhash.c b/src/genhash.c
new file mode 100644
index 0000000000..649b8deb2e
--- /dev/null
+++ b/src/genhash.c
@@ -0,0 +1,106 @@
+// Program used to generate static hashes
+//
+// Uses hashes from khash.h macros library.
+
+#include <string.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <errno.h>
+
+#define USE_LIBC_ALLOCATOR
+#include "nvim/lib/khash.h"
+
+KHASH_MAP_INIT_STR(hash, char *)
+
+#define CHECK_FAIL(cond, ...) \
+    do { \
+      if (cond) { \
+        fprintf(stderr, __VA_ARGS__); \
+        putc('\n', stderr); \
+        return 1; \
+      } \
+    } while (0)
+
+int main(int argc, char **argv)
+{
+  if (argc == 2 && strcmp(argv[1], "--help") == 0) {
+    puts("Usage:");
+    puts("  genhash SOURCE TARGET TYPE NAME VALTYPE NULLVAL");
+    puts("Transforms keys and values in a form \"key\\nval\\n\" into a hash");
+    puts("literal.");
+    puts("");
+    puts("SOURCE is the file name to read keys and values from.");
+    puts("TARGET is the file name to write to.");
+    puts("TYPE is the name of the hash type (khash_t argument).");
+    puts("NAME is the name of the generated hash.");
+    puts("VALTYPE is the name of the value type.");
+    puts("NULLVAL is the value used when no value is available.");
+    return 0;
+  }
+
+  CHECK_FAIL(argc != 7, "Expecting six arguments, got %i.", argc);
+
+  const char *const source = argv[1];
+  const char *const target = argv[2];
+  const char *const type = argv[3];
+  const char *const name = argv[4];
+  const char *const valtype = argv[5];
+  const char *const nullval = argv[6];
+
+  FILE *fin = fopen(source, "r");
+  CHECK_FAIL(!fin, "Failed to open source: %s.", strerror(errno));
+
+  char keybuf[80];
+  char valbuf[4096];
+  khash_t(hash) hash = KHASH_EMPTY_TABLE(hash);
+  while (fgets(keybuf, sizeof(keybuf), fin) != NULL) {
+    CHECK_FAIL(ferror(fin), "Failed to read key %i from source: %s",
+               (int) kh_size(&hash), strerror(ferror(fin)));
+    keybuf[strlen(keybuf) - 1] = 0;
+    CHECK_FAIL(!fgets(valbuf, sizeof(valbuf), fin),
+               "Failed to read value for key %i (%s): %s",
+               (int) kh_size(&hash), keybuf, (ferror(fin)
+                                              ? strerror(ferror(fin))
+                                              : "EOF found"));
+    valbuf[strlen(valbuf) - 1] = 0;
+    char *const key_copy = strdup(keybuf);
+    CHECK_FAIL(!key_copy, "Failed to allocate memory for a key");
+    int put_ret;
+    const khiter_t k = kh_put(hash, &hash, key_copy, &put_ret);
+    CHECK_FAIL(put_ret != 1, "Expecting unused non-empty bucket for key %s",
+               key_copy);
+    kh_value(&hash, k) = strdup(valbuf);
+    CHECK_FAIL(!kh_value(&hash, k), "Failed to allocate memory for a value");
+  }
+  CHECK_FAIL(fclose(fin), "Failed to close source: %s", strerror(errno));
+
+  FILE *f = fopen(target, "w");
+  CHECK_FAIL(!f, strerror(errno));
+  fprintf(f,     "static const khash_t(%s) %s = {", type, name);
+  fprintf(f,     "  .n_buckets = %i,\n", (int) hash.n_buckets);
+  fprintf(f,     "  .size = %i,\n", (int) hash.size);
+  fprintf(f,     "  .n_occupied = %i,\n", (int) hash.n_occupied);
+  fprintf(f,     "  .upper_bound = %i,\n", (int) hash.upper_bound);
+  fprintf(f,     "  .flags = (khint32_t[]) {\n");
+  for (khint_t i = 0; i < kh_end(&hash); i++) {
+    fprintf(f,   "    %i,\n", (int) hash.flags[i]);
+  }
+  fprintf(f,     "  },\n");
+  fprintf(f,     "  .keys = (const char*[]) {\n");
+  for (khint_t i = 0; i < kh_end(&hash); i++) {
+    if (kh_exist(&hash, i)) {
+      fprintf(f, "    \"%s\",\n", hash.keys[i]);
+    } else {
+      fprintf(f, "    NULL,\n");
+    }
+  }
+  fprintf(f,     "  },\n");
+  fprintf(f,     "  .vals = (%s[]) {\n", valtype);
+  for (khint_t i = 0; i < kh_end(&hash); i++) {
+    fprintf(f,   "    %s,\n", (kh_exist(&hash, i) ? hash.vals[i] : nullval));
+  }
+  fprintf(f,     "  },\n");
+  fprintf(f,     "};\n");
+  fclose(f);
+  return 0;
+}
diff --git a/src/nvim/CMakeLists.txt b/src/nvim/CMakeLists.txt
index 3ff34122f0..3385c0e462 100644
--- a/src/nvim/CMakeLists.txt
+++ b/src/nvim/CMakeLists.txt
@@ -19,6 +19,7 @@ set(HEADER_GENERATOR ${PROJECT_SOURCE_DIR}/scripts/gendeclarations.lua)
 set(GENERATED_INCLUDES_DIR ${PROJECT_BINARY_DIR}/include)
 set(GENERATED_EX_CMDS_ENUM ${GENERATED_INCLUDES_DIR}/ex_cmds_enum.generated.h)
 set(GENERATED_EX_CMDS_DEFS ${GENERATED_DIR}/ex_cmds_defs.generated.h)
+set(GENERATED_FUNCS_HASH_INPUT ${GENERATED_DIR}/funcs.generated.h.hsh)
 set(GENERATED_FUNCS ${GENERATED_DIR}/funcs.generated.h)
 set(GENERATED_EVENTS_ENUM ${GENERATED_INCLUDES_DIR}/auevents_enum.generated.h)
 set(GENERATED_EVENTS_NAMES_MAP ${GENERATED_DIR}/auevents_name_map.generated.h)
@@ -37,6 +38,7 @@ set(UNICODEDATA_FILE ${UNICODE_DIR}/UnicodeData.txt)
 set(CASEFOLDING_FILE ${UNICODE_DIR}/CaseFolding.txt)
 set(EASTASIANWIDTH_FILE ${UNICODE_DIR}/EastAsianWidth.txt)
 set(GENERATED_UNICODE_TABLES ${GENERATED_DIR}/unicode_tables.generated.h)
+set(GENHASH_SOURCE ${PROJECT_SOURCE_DIR}/src/genhash.c)
 
 include_directories(${GENERATED_DIR})
 include_directories(${GENERATED_INCLUDES_DIR})
@@ -214,8 +216,10 @@ add_custom_command(OUTPUT ${GENERATED_EX_CMDS_ENUM} ${GENERATED_EX_CMDS_DEFS}
 
 add_custom_command(OUTPUT ${GENERATED_FUNCS}
   COMMAND ${LUA_PRG} ${FUNCS_GENERATOR}
-      ${PROJECT_SOURCE_DIR}/src/nvim ${GENERATED_DIR}
-  DEPENDS ${FUNCS_GENERATOR} ${EVAL_DEFS_FILE}
+    ${PROJECT_SOURCE_DIR}/src/nvim ${GENERATED_DIR}
+  COMMAND $<TARGET_FILE:genhash>
+    ${GENERATED_FUNCS_HASH_INPUT} ${GENERATED_FUNCS} functions functions VimLFuncDef "NOFUNC"
+  DEPENDS ${FUNCS_GENERATOR} ${EVAL_DEFS_FILE} genhash
 )
 
 add_custom_command(OUTPUT ${GENERATED_EVENTS_ENUM} ${GENERATED_EVENTS_NAMES_MAP}
@@ -284,6 +288,8 @@ if(WIN32)
     DESTINATION ${CMAKE_INSTALL_BINDIR})
 endif()
 
+add_executable(genhash ${GENHASH_SOURCE} ${NEOVIM_HEADERS})
+
 if(CLANG_ASAN_UBSAN)
   message(STATUS "Enabling Clang address sanitizer and undefined behavior sanitizer for nvim.")
   check_c_compiler_flag(-fno-sanitize-recover=all SANITIZE_RECOVER_ALL)
diff --git a/src/nvim/eval.c b/src/nvim/eval.c
index 64f85a2fe5..c5b5866f56 100644
--- a/src/nvim/eval.c
+++ b/src/nvim/eval.c
@@ -90,6 +90,8 @@
 #include "nvim/os/dl.h"
 #include "nvim/os/input.h"
 #include "nvim/event/loop.h"
+#include "nvim/lib/kvec.h"
+#include "nvim/lib/khash.h"
 #include "nvim/lib/queue.h"
 #include "nvim/eval/typval_encode.h"
 
@@ -442,6 +444,18 @@ typedef struct {
   ufunc_T *callback;
 } timer_T;
 
+/// Prototype of C function that implements VimL function
+typedef void (*VimLFunc)(typval_T *args, typval_T *rvar);
+
+/// Structure holding VimL function definition
+typedef struct fst {
+  uint8_t min_argc;  ///< Minimal number of arguments.
+  uint8_t max_argc;  ///< Maximal number of arguments.
+  VimLFunc func;     ///< Function implementation.
+} VimLFuncDef;
+
+KHASH_MAP_INIT_STR(functions, VimLFuncDef)
+
 #ifdef INCLUDE_GENERATED_DECLARATIONS
 # include "eval.c.generated.h"
 #endif
@@ -6681,17 +6695,7 @@ static int get_env_tv(char_u **arg, typval_T *rettv, int evaluate)
   return OK;
 }
 
-/// Prototype of C function that implements VimL function
-typedef void (*VimLFunc)(typval_T *args, typval_T *rvar);
-
-/// Structure holding VimL function definition
-typedef struct fst {
-  char *f_name;        ///< Function name.
-  uint8_t f_min_argc;  ///< Minimal number of arguments.
-  uint8_t f_max_argc;  ///< Maximal number of arguments.
-  VimLFunc f_func;     ///< Function implementation.
-} VimLFuncDef;
-
+#define NOFUNC { 0, 0, NULL }
 #ifdef INCLUDE_GENERATED_DECLARATIONS
 # include "funcs.generated.h"
 #endif
@@ -6713,15 +6717,25 @@ char_u *get_function_name(expand_T *xp, int idx)
     if (name != NULL)
       return name;
   }
-  if (++intidx < (int)ARRAY_SIZE(functions)) {
-    STRCPY(IObuff, functions[intidx].f_name);
-    STRCAT(IObuff, "(");
-    if (functions[intidx].f_max_argc == 0)
-      STRCAT(IObuff, ")");
-    return IObuff;
+  while ((khiter_t) ++intidx < kh_end(&functions)
+         && !kh_exist(&functions, (khiter_t) intidx)) {
   }
 
-  return NULL;
+  if ((khiter_t) intidx >= kh_end(&functions)) {
+    return NULL;
+  }
+
+  const char *const key = kh_key(&functions, (khiter_t) intidx);
+  const size_t key_len = strlen(key);
+  memcpy(IObuff, key, key_len);
+  IObuff[key_len] = '(';
+  if (kh_val(&functions, (khiter_t) intidx).max_argc == 0) {
+    IObuff[key_len + 1] = ')';
+    IObuff[key_len + 2] = NUL;
+  } else {
+    IObuff[key_len + 1] = NUL;
+  }
+  return IObuff;
 }
 
 /*
@@ -6746,32 +6760,16 @@ char_u *get_expr_name(expand_T *xp, int idx)
 
 
 
-/*
- * Find internal function in table above.
- * Return index, or -1 if not found
- */
-static int 
-find_internal_func (
-    char_u *name              /* name of the function */
-)
+/// Find internal function in hash functions
+///
+/// @param[in]  name  Name of the function.
+///
+/// Returns pointer to the function definition or NULL if not found.
+static VimLFuncDef *find_internal_func(const char *const name)
+  FUNC_ATTR_WARN_UNUSED_RESULT FUNC_ATTR_PURE FUNC_ATTR_NONNULL_ALL
 {
-  int first = 0;
-  int last = (int)ARRAY_SIZE(functions) - 1;
-
-  /*
-   * Find the function name in the table. Binary search.
-   */
-  while (first <= last) {
-    int x = first + ((unsigned)(last - first)) / 2;
-    int cmp = STRCMP(name, functions[x].f_name);
-    if (cmp < 0)
-      last = x - 1;
-    else if (cmp > 0)
-      first = x + 1;
-    else
-      return x;
-  }
-  return -1;
+  const khiter_t k = kh_get(functions, &functions, name);
+  return (k == kh_end(&functions) ? NULL : &kh_val(&functions, k));
 }
 
 /*
@@ -6889,7 +6887,6 @@ call_func (
 #define ERROR_NONE      5
 #define ERROR_OTHER     6
   int error = ERROR_NONE;
-  int i;
   int llen;
   ufunc_T     *fp;
 #define FLEN_FIXED 40
@@ -6911,7 +6908,7 @@ call_func (
     fname_buf[0] = K_SPECIAL;
     fname_buf[1] = KS_EXTRA;
     fname_buf[2] = (int)KE_SNR;
-    i = 3;
+    int i = 3;
     if (eval_fname_sid(name)) {         /* "<SID>" or "s:" */
       if (current_SID <= 0)
         error = ERROR_SCRIPT;
@@ -6983,18 +6980,16 @@ call_func (
         }
       }
     } else {
-      /*
-       * Find the function name in the table, call its implementation.
-       */
-      i = find_internal_func(fname);
-      if (i >= 0) {
-        if (argcount < functions[i].f_min_argc)
+      // Find the function name in the table, call its implementation.
+      VimLFuncDef *const fdef = find_internal_func((char *) fname);
+      if (fdef != NULL) {
+        if (argcount < fdef->min_argc) {
           error = ERROR_TOOFEW;
-        else if (argcount > functions[i].f_max_argc)
+        } else if (argcount > fdef->max_argc) {
           error = ERROR_TOOMANY;
-        else {
+        } else {
           argvars[argcount].v_type = VAR_UNKNOWN;
-          functions[i].f_func(argvars, rettv);
+          fdef->func(argvars, rettv);
           error = ERROR_NONE;
         }
       }
@@ -20120,7 +20115,7 @@ void free_all_functions(void)
 int translated_function_exists(char_u *name)
 {
   if (builtin_function(name, -1)) {
-    return find_internal_func(name) >= 0;
+    return find_internal_func((char *) name) != NULL;
   }
   return find_func(name) != NULL;
 }
diff --git a/src/nvim/lib/khash.h b/src/nvim/lib/khash.h
index 8287cb14da..f8530be79a 100644
--- a/src/nvim/lib/khash.h
+++ b/src/nvim/lib/khash.h
@@ -130,7 +130,9 @@ int main() {
 #include <limits.h>
 #include <stdint.h>
 
-#include "nvim/memory.h"
+#ifndef USE_LIBC_ALLOCATOR
+# include "nvim/memory.h"
+#endif
 
 #include "nvim/func_attr.h"
 
@@ -171,17 +173,32 @@ typedef khint_t khiter_t;
 #define kroundup32(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x))
 #endif
 
-#ifndef kcalloc
-#define kcalloc(N,Z) xcalloc(N,Z)
-#endif
-#ifndef kmalloc
-#define kmalloc(Z) xmalloc(Z)
-#endif
-#ifndef krealloc
-#define krealloc(P,Z) xrealloc(P,Z)
-#endif
-#ifndef kfree
-#define kfree(P) xfree(P)
+#ifdef USE_LIBC_ALLOCATOR
+# ifndef kcalloc
+#  define kcalloc(N,Z) calloc(N,Z)
+# endif
+# ifndef kmalloc
+#  define kmalloc(Z) malloc(Z)
+# endif
+# ifndef krealloc
+#  define krealloc(P,Z) realloc(P,Z)
+# endif
+# ifndef kfree
+#  define kfree(P) free(P)
+# endif
+#else
+# ifndef kcalloc
+#  define kcalloc(N,Z) xcalloc(N,Z)
+# endif
+# ifndef kmalloc
+#  define kmalloc(Z) xmalloc(Z)
+# endif
+# ifndef krealloc
+#  define krealloc(P,Z) xrealloc(P,Z)
+# endif
+# ifndef kfree
+#  define kfree(P) xfree(P)
+# endif
 #endif
 
 #define __ac_HASH_UPPER 0.77