vim-patch:partial:9.1.1179: too many strlen() calls in misc2.c

Problem:  too many strlen() calls in misc2.c
Solution: refactor misc2.c and use bsearch() instead of a linear search
          to find matches in the key_names_table array (John Marriott).

This commit changes misc2.c to use bsearch() to perform string searches of
the key_names_table array.

Implementation detail:
- Some entries in this array have alternate names. Add field alt_name to
  point to the alternate name.
- Some entries in this array are only available if a given feature is
  defined. Keep them in the array, but add a boolean field enabled to
  indicate if the record can be used or not. If the feature is not
  available, the corresponding enabled field is set to FALSE.

In my measurements running the test suite on a huge non-gui build on
linux, the number of string comparisons in get_special_key_code():
Before (linear search): 2,214,957
After (binary search): 297,770

A side effect of this is 1477 calls to STRLEN() in
get_special_key_name() for the same test run are no longer necessary.

closes: vim/vim#16788

https://github.com/vim/vim/commit/4a1e6dacbb2cc833353983bea7eac38191c9d3b4

Skip the mouse shape changes.

Co-authored-by: John Marriott <basilisk@internode.on.net>

2 files changed, 92 insertions, 27 deletions

diff --git a/src/gen/gen_keycodes.lua b/src/gen/gen_keycodes.lua
index fff5b59396..118eac2579 100644
--- a/src/gen/gen_keycodes.lua
+++ b/src/gen/gen_keycodes.lua
@@ -1,19 +1,49 @@
 local names_file = arg[1]
 
 local keycodes = require('nvim.keycodes')
-local keycode_names = keycodes.names
 
 local names_tgt = assert(io.open(names_file, 'w'))
 
+--- @type [string, string, integer][]
+local keycode_names = {}
+for i, keycode in ipairs(keycodes.names) do
+  table.insert(keycode_names, { keycode[1], keycode[2], i })
+end
+table.sort(keycode_names, function(keycode_a, keycode_b)
+  return keycode_a[2]:lower() < keycode_b[2]:lower()
+end)
+
+--- @type table<string,integer>
+local alt_name_idx = {}
+for i, keycode in ipairs(keycode_names) do
+  local key = keycode[1]
+  local alt_idx = alt_name_idx[key]
+  if alt_idx == nil or keycode_names[alt_idx][3] > keycode[3] then
+    alt_name_idx[key] = i
+  end
+end
+
 names_tgt:write([[
 static const struct key_name_entry {
-  int key;           ///< Special key code or ascii value
-  const char *name;  ///< Name of key
+  int key;                 ///< Special key code or ascii value
+  String name;             ///< Name of key
+  const String *alt_name;  ///< Pointer to alternative key name
+                           ///< (may be NULL or point to the name in another entry)
 } key_names_table[] = {]])
 
-for _, keycode in ipairs(keycode_names) do
-  names_tgt:write(('\n  {%s, "%s"},'):format(keycode[1], keycode[2]))
+for i, keycode in ipairs(keycode_names) do
+  local key = keycode[1]
+  local name = keycode[2]
+  local alt_idx = alt_name_idx[key]
+  names_tgt:write(
+    ('\n  {%s, {"%s", %d}, %s},'):format(
+      key,
+      name,
+      #name,
+      alt_idx == i and 'NULL' or ('&key_names_table[%d].name'):format(alt_idx - 1)
+    )
+  )
 end
 
-names_tgt:write('\n  {0, NULL},\n};\n')
+names_tgt:write('\n};\n')
 names_tgt:close()
diff --git a/src/nvim/keycodes.c b/src/nvim/keycodes.c
index ff5b036817..5ab6a718ef 100644
--- a/src/nvim/keycodes.c
+++ b/src/nvim/keycodes.c
@@ -6,6 +6,7 @@
 #include <string.h>
 #include <uv.h>
 
+#include "nvim/api/private/defs.h"
 #include "nvim/ascii_defs.h"
 #include "nvim/charset.h"
 #include "nvim/errors.h"
@@ -337,15 +338,18 @@ char *get_special_key_name(int c, int modifiers)
       }
     }
   } else {            // use name of special key
-    size_t len = strlen(key_names_table[table_idx].name);
+    const String *s = key_names_table[table_idx].alt_name != NULL
+                      ? key_names_table[table_idx].alt_name
+                      : &key_names_table[table_idx].name;
 
-    if ((int)len + idx + 2 <= MAX_KEY_NAME_LEN) {
-      STRCPY(string + idx, key_names_table[table_idx].name);
-      idx += (int)len;
+    if ((int)s->size + idx + 2 <= MAX_KEY_NAME_LEN) {
+      STRCPY(string + idx, s->data);
+      idx += (int)s->size;
     }
   }
   string[idx++] = '>';
   string[idx] = NUL;
+
   return string;
 }
 
@@ -588,17 +592,51 @@ static int extract_modifiers(int key, int *modp, const bool simplify, bool *cons
 /// @return  the index when found, -1 when not found.
 int find_special_key_in_table(int c)
 {
-  int i;
-
-  for (i = 0; key_names_table[i].name != NULL; i++) {
+  for (int i = 0; i < (int)ARRAY_SIZE(key_names_table); i++) {
     if (c == key_names_table[i].key) {
+      return i;
+    }
+  }
+
+  return -1;
+}
+
+/// Compare two 'struct key_name_entry' structures.
+/// Note that the target string (p1) may contain additional trailing characters
+/// that should not factor into the comparison. Example:
+/// 'LeftMouse>", "<LeftMouse>"] ...'
+/// should match with
+/// 'LeftMouse'.
+/// These characters are identified by ascii_isident().
+static int cmp_key_name_entry(const void *a, const void *b)
+{
+  const char *p1 = ((struct key_name_entry *)a)->name.data;
+  const char *p2 = ((struct key_name_entry *)b)->name.data;
+  int result = 0;
+
+  if (p1 == p2) {
+    return 0;
+  }
+
+  while (ascii_isident(*p1) && *p2 != NUL) {
+    if ((result = TOLOWER_ASC(*p1) - TOLOWER_ASC(*p2)) != 0) {
       break;
     }
+    p1++;
+    p2++;
   }
-  if (key_names_table[i].name == NULL) {
-    i = -1;
+
+  if (result == 0) {
+    if (*p2 == NUL) {
+      if (ascii_isident(*p1)) {
+        result = 1;
+      }
+    } else {
+      result = -1;
+    }
   }
-  return i;
+
+  return result;
 }
 
 /// Find the special key with the given name
@@ -616,17 +654,14 @@ int get_special_key_code(const char *name)
     return TERMCAP2KEY((uint8_t)name[2], (uint8_t)name[3]);
   }
 
-  for (int i = 0; key_names_table[i].name != NULL; i++) {
-    const char *const table_name = key_names_table[i].name;
-    int j;
-    for (j = 0; ascii_isident((uint8_t)name[j]) && table_name[j] != NUL; j++) {
-      if (TOLOWER_ASC(table_name[j]) != TOLOWER_ASC((uint8_t)name[j])) {
-        break;
-      }
-    }
-    if (!ascii_isident((uint8_t)name[j]) && table_name[j] == NUL) {
-      return key_names_table[i].key;
-    }
+  struct key_name_entry target = { .name.data = (char *)name };
+  struct key_name_entry *entry = bsearch(&target,
+                                         &key_names_table,
+                                         ARRAY_SIZE(key_names_table),
+                                         sizeof(key_names_table[0]),
+                                         cmp_key_name_entry);
+  if (entry != NULL) {
+    return entry->key;
   }
 
   return 0;