viml/parser/expressions: Add support for string parsing

8 files changed, 1938 insertions, 13 deletions

diff --git a/src/nvim/mbyte.h b/src/nvim/mbyte.h
index bf6ccb13a5..fce600d0a9 100644
--- a/src/nvim/mbyte.h
+++ b/src/nvim/mbyte.h
@@ -73,6 +73,8 @@ typedef struct {
 
 extern const uint8_t utf8len_tab_zero[256];
 
+extern const uint8_t utf8len_tab[256];
+
 #ifdef INCLUDE_GENERATED_DECLARATIONS
 # include "mbyte.h.generated.h"
 #endif
diff --git a/src/nvim/viml/parser/expressions.c b/src/nvim/viml/parser/expressions.c
index 0613cc66d5..3f30fe2a0e 100644
--- a/src/nvim/viml/parser/expressions.c
+++ b/src/nvim/viml/parser/expressions.c
@@ -915,8 +915,6 @@ static inline void viml_pexpr_debug_print_token(
 //
 // NVimIdentifierKey -> Identifier
 //
-// NVimFigureBrace -> NVimInternalError
-//
 // NVimUnaryPlus -> NVimUnaryOperator
 // NVimBinaryPlus -> NVimBinaryOperator
 // NVimConcat -> NVimBinaryOperator
@@ -929,6 +927,18 @@ static inline void viml_pexpr_debug_print_token(
 // NVimNestingParenthesis -> NVimParenthesis
 // NVimCallingParenthesis -> NVimParenthesis
 //
+// NVimString -> String
+// NVimStringSpecial -> SpecialChar
+// NVimSingleQuote -> NVimString
+// NVimSingleQuotedBody -> NVimString
+// NVimSingleQuotedQuote -> NVimStringSpecial
+// NVimDoubleQuote -> NVimString
+// NVimDoubleQuotedBody -> NVimString
+// NVimDoubleQuotedEscape -> NVimStringSpecial
+// NVimDoubleQuotedUnknownEscape -> NVimInvalid
+//
+// " Note: NVimDoubleQuotedUnknownEscape is not actually invalid
+//
 // NVimInvalidComma -> NVimInvalidDelimiter
 // NVimInvalidSpacing -> NVimInvalid
 // NVimInvalidTernary -> NVimInvalidOperator
@@ -952,6 +962,19 @@ static inline void viml_pexpr_debug_print_token(
 // NVimInvalidList -> NVimInvalidDelimiter
 // NVimInvalidSubscript -> NVimInvalidDelimiter
 // NVimInvalidSubscriptColon -> NVimInvalidSubscript
+// NVimInvalidString -> NVimInvalidValue
+// NVimInvalidStringSpecial -> NVimInvalidString
+// NVimInvalidSingleQuote -> NVimInvalidString
+// NVimInvalidSingleQuotedBody -> NVimInvalidString
+// NVimInvalidSingleQuotedQuote -> NVimInvalidStringSpecial
+// NVimInvalidDoubleQuote -> NVimInvalidString
+// NVimInvalidDoubleQuotedBody -> NVimInvalidString
+// NVimInvalidDoubleQuotedEscape -> NVimInvalidStringSpecial
+// NVimInvalidDoubleQuotedUnknownEscape -> NVimInvalid
+//
+// NVimFigureBrace -> NVimInternalError
+// NVimInvalidSingleQuotedUnknownEscape -> NVimInternalError
+// NVimSingleQuotedUnknownEscape -> NVimInternalError
 
 /// Allocate a new node and set some of the values
 ///
@@ -1402,6 +1425,318 @@ static inline void east_set_error(const ParserState *const pstate,
       } \
     } while (0)
 
+/// Structure used to define “string shifts” necessary to map string
+/// highlighting to actual strings.
+typedef struct {
+  size_t start;  ///< Where special character starts in original string.
+  size_t orig_len;  ///< Length of orininal string (e.g. 4 for "\x80").
+  size_t act_len;  ///< Length of resulting character(s) (e.g. 1 for "\x80").
+  bool escape_not_known;  ///< True if escape sequence in original is not known.
+} StringShift;
+
+/// Parse and highlight single- or double-quoted string
+///
+/// Function is supposed to detect and highlight regular expressions (but does
+/// not do now).
+///
+/// @param[out]  pstate  Parser state which also contains a place where
+///                      highlighting is saved.
+/// @param[out]  node  Node where string parsing results are saved.
+/// @param[in]  token  Token to highlight.
+/// @param[in]  ast_stack  Parser AST stack, used to detect whether current
+///                        string is a regex.
+/// @param[in]  is_invalid  Whether currently processed token is not valid.
+static void parse_quoted_string(ParserState *const pstate,
+                                ExprASTNode *const node,
+                                const LexExprToken token,
+                                const ExprASTStack ast_stack,
+                                const bool is_invalid)
+  FUNC_ATTR_NONNULL_ALL
+{
+  const ParserLine pline = pstate->reader.lines.items[token.start.line];
+  const char *const s = pline.data + token.start.col;
+  const char *const e = s + token.len - token.data.str.closed;
+  const char *p = s + 1;
+  const bool is_double = (token.type == kExprLexDoubleQuotedString);
+  size_t size = token.len - token.data.str.closed - 1;
+  kvec_withinit_t(StringShift, 16) shifts;
+  kvi_init(shifts);
+  if (!is_double) {
+    viml_parser_highlight(pstate, token.start, 1, HL(SingleQuotedString));
+    while (p < e) {
+      const char *const chunk_e = memchr(p, '\'', (size_t)(e - p));
+      if (chunk_e == NULL) {
+        break;
+      }
+      size--;
+      p = chunk_e + 2;
+      if (pstate->colors) {
+        kvi_push(shifts, ((StringShift) {
+            .start = token.start.col + (size_t)(chunk_e - s),
+            .orig_len = 2,
+            .act_len = 1,
+            .escape_not_known = false,
+        }));
+      }
+    }
+    node->data.str.size = size;
+    if (size == 0) {
+      node->data.str.value = NULL;
+    } else {
+      char *v_p;
+      v_p = node->data.str.value = xmalloc(size);
+      p = s + 1;
+      while (p < e) {
+        const char *const chunk_e = memchr(p, '\'', (size_t)(e - p));
+        if (chunk_e == NULL) {
+          memcpy(v_p, p, (size_t)(e - p));
+          break;
+        }
+        memcpy(v_p, p, (size_t)(chunk_e - p));
+        v_p += (size_t)(chunk_e - p) + 1;
+        v_p[-1] = '\'';
+        p = chunk_e + 2;
+      }
+    }
+  } else {
+    viml_parser_highlight(pstate, token.start, 1, HL(DoubleQuotedString));
+    for (p = s + 1; p < e; p++) {
+      if (*p == '\\' && p + 1 < e) {
+        p++;
+        if (p + 1 == e) {
+          size--;
+          break;
+        }
+        switch (*p) {
+          // A "\<x>" form occupies at least 4 characters, and produces up to
+          // 6 characters: reserve space for 2 extra, but do not compute actual
+          // length just now, it would be costy.
+          case '<': {
+            size += 2;
+            break;
+          }
+          // Hexadecimal, always single byte, but at least three bytes each.
+          case 'x': case 'X': {
+            size--;
+            if (ascii_isxdigit(p[1])) {
+              size--;
+              if (p + 2 < e && ascii_isxdigit(p[2])) {
+                size--;
+              }
+            }
+            break;
+          }
+          // Unicode
+          //
+          // \uF takes 1 byte which is 2 bytes less then escape sequence.
+          // \uFF: 2 bytes, 2 bytes less.
+          // \uFFF: 3 bytes, 2 bytes less.
+          // \uFFFF: 3 bytes, 3 bytes less.
+          // \UFFFFF: 4 bytes, 3 bytes less.
+          // \UFFFFFF: 5 bytes, 3 bytes less.
+          // \UFFFFFFF: 6 bytes, 3 bytes less.
+          // \U7FFFFFFF: 6 bytes, 4 bytes less.
+          case 'u': case 'U': {
+            const char *const esc_start = p;
+            size_t n = (*p == 'u' ? 4 : 8);
+            int nr = 0;
+            p++;
+            while (n-- && ascii_isxdigit(p[1])) {
+              p++;
+              nr = (nr << 4) + hex2nr(*p);
+            }
+            // Escape length: (esc_start - 1) points to "\\", esc_start to "u"
+            // or "U", p to the byte after last byte. So escape sequence
+            // occupies p - (esc_start - 1), but it stands for a utf_char2len
+            // bytes.
+            size -= (size_t)((p - (esc_start - 1)) - utf_char2len(nr));
+            p--;
+            break;
+          }
+          // Octal, always single byte, but at least two bytes each.
+          case '0': case '1': case '2': case '3': case '4': case '5': case '6':
+          case '7': {
+            size--;
+            p++;
+            if (*p >= '0' && *p <= '7') {
+              size--;
+              p++;
+              if (*p >= '0' && *p <= '7') {
+                size--;
+                p++;
+              }
+            }
+            break;
+          }
+          default: {
+            size--;
+            break;
+          }
+        }
+      }
+    }
+    if (size == 0) {
+      node->data.str.value = NULL;
+      node->data.str.size = 0;
+    } else {
+      char *v_p;
+      v_p = node->data.str.value = xmalloc(size);
+      p = s + 1;
+      while (p < e) {
+        const char *const chunk_e = memchr(p, '\\', (size_t)(e - p));
+        if (chunk_e == NULL) {
+          memcpy(v_p, p, (size_t)(e - p));
+          v_p += e - p;
+          break;
+        }
+        memcpy(v_p, p, (size_t)(chunk_e - p));
+        v_p += (size_t)(chunk_e - p);
+        p = chunk_e + 1;
+        if (p == e) {
+          *v_p++ = '\\';
+          break;
+        }
+        bool is_unknown = false;
+        const char *const v_p_start = v_p;
+        switch (*p) {
+#define SINGLE_CHAR_ESC(ch, real_ch) \
+          case ch: { \
+            *v_p++ = real_ch; \
+            p++; \
+            break; \
+          }
+          SINGLE_CHAR_ESC('b', BS)
+          SINGLE_CHAR_ESC('e', ESC)
+          SINGLE_CHAR_ESC('f', FF)
+          SINGLE_CHAR_ESC('n', NL)
+          SINGLE_CHAR_ESC('r', CAR)
+          SINGLE_CHAR_ESC('t', TAB)
+          SINGLE_CHAR_ESC('"', '"')
+          SINGLE_CHAR_ESC('\\', '\\')
+#undef SINGLE_CHAR_ESC
+
+          // Hexadecimal or unicode.
+          case 'X': case 'x': case 'u': case 'U': {
+            if (ascii_isxdigit(p[1])) {
+              size_t n;
+              int nr;
+              bool is_hex = (*p == 'x' || *p == 'X');
+
+              if (is_hex) {
+                n = 2;
+              } else if (*p == 'u') {
+                n = 4;
+              } else {
+                n = 8;
+              }
+              nr = 0;
+              while (n-- && ascii_isxdigit(p[1])) {
+                p++;
+                nr = (nr << 4) + hex2nr(*p);
+              }
+              p++;
+              if (is_hex) {
+                *v_p++ = (char)nr;
+              } else {
+                v_p += utf_char2bytes(nr, (char_u *)v_p);
+              }
+            } else {
+              is_unknown = true;
+              *v_p++ = *p;
+              p++;
+            }
+            break;
+          }
+          // Octal: "\1", "\12", "\123".
+          case '0': case '1': case '2': case '3': case '4': case '5': case '6':
+          case '7': {
+            uint8_t ch = (uint8_t)(*p++ - '0');
+            if (*p >= '0' && *p <= '7') {
+              ch = (uint8_t)((ch << 3) + *p++ - '0');
+              if (*p >= '0' && *p <= '7') {
+                ch = (uint8_t)((ch << 3) + *p++ - '0');
+              }
+            }
+            *v_p++ = (char)ch;
+            break;
+          }
+          // Special key, e.g.: "\<C-W>"
+          case '<': {
+            const size_t special_len = (
+                trans_special((const char_u **)&p, (size_t)(e - p),
+                              (char_u *)v_p, true, true));
+            if (special_len != 0) {
+              v_p += special_len;
+            } else {
+              is_unknown = true;
+              mb_copy_char((const char_u **)&p, (char_u **)&v_p);
+            }
+            break;
+          }
+          default: {
+            is_unknown = true;
+            mb_copy_char((const char_u **)&p, (char_u **)&v_p);
+            break;
+          }
+        }
+        if (pstate->colors) {
+          kvi_push(shifts, ((StringShift) {
+              .start = token.start.col + (size_t)(chunk_e - s),
+              .orig_len = (size_t)(p - chunk_e),
+              .act_len = (size_t)(v_p - (char *)v_p_start),
+              .escape_not_known = is_unknown,
+          }));
+        }
+      }
+      node->data.str.size = (size_t)(v_p - node->data.str.value);
+    }
+  }
+  if (pstate->colors) {
+    // TODO(ZyX-I): use ast_stack to determine and highlight regular expressions
+    // TODO(ZyX-I): use ast_stack to determine and highlight printf format str
+    // TODO(ZyX-I): use ast_stack to determine and highlight expression strings
+    size_t next_col = 1;
+    const char *const body_str = (is_double
+                                  ? HL(DoubleQuotedBody)
+                                  : HL(SingleQuotedBody));
+    const char *const esc_str = (is_double
+                                 ? HL(DoubleQuotedEscape)
+                                 : HL(SingleQuotedQuote));
+    const char *const ukn_esc_str = (is_double
+                                     ? HL(DoubleQuotedUnknownEscape)
+                                     : HL(SingleQuotedUnknownEscape));
+    for (size_t i = 0; i < kv_size(shifts); i++) {
+      const StringShift cur_shift = kv_A(shifts, i);
+      if (cur_shift.start > next_col) {
+        viml_parser_highlight(pstate, shifted_pos(token.start, next_col),
+                              cur_shift.start - next_col,
+                              body_str);
+      }
+      viml_parser_highlight(pstate, shifted_pos(token.start, cur_shift.start),
+                            cur_shift.orig_len,
+                            (cur_shift.escape_not_known
+                             ? ukn_esc_str
+                             : esc_str));
+      next_col = cur_shift.start + cur_shift.orig_len;
+    }
+    if (next_col < token.len - token.data.str.closed) {
+      viml_parser_highlight(pstate, shifted_pos(token.start, next_col),
+                            token.len - token.data.str.closed - next_col,
+                            body_str);
+    }
+  }
+  if (token.data.str.closed) {
+    if (is_double) {
+      viml_parser_highlight(pstate, shifted_pos(token.start, token.len - 1),
+                            1, HL(DoubleQuotedString));
+    } else {
+      viml_parser_highlight(pstate, shifted_pos(token.start, token.len - 1),
+                            1, HL(SingleQuotedString));
+    }
+  }
+  kvi_destroy(shifts);
+}
+
 /// Parse one VimL expression
 ///
 /// @param  pstate  Parser state.
@@ -1714,12 +2049,7 @@ viml_pexpr_parse_invalid_comma:
           } else if (eastnode_lvl >= kEOpLvlComma) {
             can_be_ternary = false;
           } else {
-viml_pexpr_parse_invalid_colon:
-            ERROR_FROM_TOKEN_AND_MSG(
-                cur_token,
-                _("E15: Colon outside of dictionary or ternary operator: "
-                  "%.*s"));
-            break;
+            goto viml_pexpr_parse_invalid_colon;
           }
           if (i == kv_size(ast_stack) - 1) {
             goto viml_pexpr_parse_invalid_colon;
@@ -1741,6 +2071,12 @@ viml_pexpr_parse_invalid_colon:
           ADD_OP_NODE(cur_node);
           HL_CUR_TOKEN(SubscriptColon);
         } else {
+          goto viml_pexpr_parse_valid_colon;
+viml_pexpr_parse_invalid_colon:
+          ERROR_FROM_TOKEN_AND_MSG(
+              cur_token,
+              _("E15: Colon outside of dictionary or ternary operator: %.*s"));
+viml_pexpr_parse_valid_colon:
           ADD_VALUE_IF_MISSING(_(EXP_VAL_COLON));
           NEW_NODE_WITH_CUR_POS(cur_node, kExprNodeColon);
           if (is_ternary) {
@@ -2201,6 +2537,30 @@ viml_pexpr_parse_no_paren_closing_error: {}
         kvi_push(ast_stack, &ter_val_node->children);
         break;
       }
+      case kExprLexDoubleQuotedString:
+      case kExprLexSingleQuotedString: {
+        const bool is_double = (tok_type == kExprLexDoubleQuotedString);
+        if (!cur_token.data.str.closed) {
+          // It is weird, but Vim has two identical errors messages with
+          // different error numbers: "E114: Missing quote" and
+          // "E115: Missing quote".
+          ERROR_FROM_TOKEN_AND_MSG(
+              cur_token, (is_double
+                          ? _("E114: Missing double quote: %.*s")
+                          : _("E115: Missing single quote: %.*s")));
+        }
+        if (want_node == kENodeOperator) {
+          OP_MISSING;
+        }
+        NEW_NODE_WITH_CUR_POS(
+            cur_node, (is_double
+                       ? kExprNodeDoubleQuotedString
+                       : kExprNodeSingleQuotedString));
+        *top_node_p = cur_node;
+        parse_quoted_string(pstate, cur_node, cur_token, ast_stack, is_invalid);
+        want_node = kENodeOperator;
+        break;
+      }
     }
 viml_pexpr_parse_cycle_end:
     prev_token = cur_token;
diff --git a/src/nvim/viml/parser/expressions.h b/src/nvim/viml/parser/expressions.h
index 0d496c87ba..a09cdde4c0 100644
--- a/src/nvim/viml/parser/expressions.h
+++ b/src/nvim/viml/parser/expressions.h
@@ -195,6 +195,8 @@ typedef enum {
   kExprNodeConcatOrSubscript = 'S',
   kExprNodeInteger = '0',  ///< Integral number.
   kExprNodeFloat = '1',  ///< Floating-point number.
+  kExprNodeSingleQuotedString = '\'',
+  kExprNodeDoubleQuotedString = '"',
 } ExprASTNodeType;
 
 typedef struct expr_ast_node ExprASTNode;
@@ -249,6 +251,11 @@ struct expr_ast_node {
     struct {
       float_T value;
     } flt;  ///< For kExprNodeFloat.
+    struct {
+      char *value;
+      size_t size;
+    } str;  ///< For kExprNodeSingleQuotedString and
+            ///< kExprNodeDoubleQuotedString.
   } data;
 };
 
diff --git a/test/helpers.lua b/test/helpers.lua
index d5356416af..e7d8c185ba 100644
--- a/test/helpers.lua
+++ b/test/helpers.lua
@@ -330,9 +330,10 @@ format_luav = function(v, indent)
   end
   local ret = ''
   if type(v) == 'string' then
-    ret = '\'' .. tostring(v):gsub('[\'\\]', '\\%0'):gsub('[%z\1-\31]', function(match)
-      return SUBTBL[match:byte()]
-    end) .. '\''
+    ret = tostring(v):gsub('[\'\\]', '\\%0'):gsub('[%z\1-\31]', function(match)
+      return SUBTBL[match:byte() + 1]
+    end)
+    ret = '\'' .. ret .. '\''
   elseif type(v) == 'table' then
     local processed_keys = {}
     ret = '{' .. linesep
diff --git a/test/symbolic/klee/nvim/keymap.c b/test/symbolic/klee/nvim/keymap.c
new file mode 100644
index 0000000000..c59d8d4d6e
--- /dev/null
+++ b/test/symbolic/klee/nvim/keymap.c
@@ -0,0 +1,540 @@
+#include <stdbool.h>
+
+#include "nvim/types.h"
+#include "nvim/keymap.h"
+#include "nvim/eval/typval.h"
+
+#define MOD_KEYS_ENTRY_SIZE 5
+
+static char_u modifier_keys_table[] =
+{
+  MOD_MASK_SHIFT, '&', '9',                   '@', '1',
+  MOD_MASK_SHIFT, '&', '0',                   '@', '2',
+  MOD_MASK_SHIFT, '*', '1',                   '@', '4',
+  MOD_MASK_SHIFT, '*', '2',                   '@', '5',
+  MOD_MASK_SHIFT, '*', '3',                   '@', '6',
+  MOD_MASK_SHIFT, '*', '4',                   'k', 'D',
+  MOD_MASK_SHIFT, '*', '5',                   'k', 'L',
+  MOD_MASK_SHIFT, '*', '7',                   '@', '7',
+  MOD_MASK_CTRL,  KS_EXTRA, (int)KE_C_END,    '@', '7',
+  MOD_MASK_SHIFT, '*', '9',                   '@', '9',
+  MOD_MASK_SHIFT, '*', '0',                   '@', '0',
+  MOD_MASK_SHIFT, '#', '1',                   '%', '1',
+  MOD_MASK_SHIFT, '#', '2',                   'k', 'h',
+  MOD_MASK_CTRL,  KS_EXTRA, (int)KE_C_HOME,   'k', 'h',
+  MOD_MASK_SHIFT, '#', '3',                   'k', 'I',
+  MOD_MASK_SHIFT, '#', '4',                   'k', 'l',
+  MOD_MASK_CTRL,  KS_EXTRA, (int)KE_C_LEFT,   'k', 'l',
+  MOD_MASK_SHIFT, '%', 'a',                   '%', '3',
+  MOD_MASK_SHIFT, '%', 'b',                   '%', '4',
+  MOD_MASK_SHIFT, '%', 'c',                   '%', '5',
+  MOD_MASK_SHIFT, '%', 'd',                   '%', '7',
+  MOD_MASK_SHIFT, '%', 'e',                   '%', '8',
+  MOD_MASK_SHIFT, '%', 'f',                   '%', '9',
+  MOD_MASK_SHIFT, '%', 'g',                   '%', '0',
+  MOD_MASK_SHIFT, '%', 'h',                   '&', '3',
+  MOD_MASK_SHIFT, '%', 'i',                   'k', 'r',
+  MOD_MASK_CTRL,  KS_EXTRA, (int)KE_C_RIGHT,  'k', 'r',
+  MOD_MASK_SHIFT, '%', 'j',                   '&', '5',
+  MOD_MASK_SHIFT, '!', '1',                   '&', '6',
+  MOD_MASK_SHIFT, '!', '2',                   '&', '7',
+  MOD_MASK_SHIFT, '!', '3',                   '&', '8',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_UP,     'k', 'u',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_DOWN,   'k', 'd',
+
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_XF1,    KS_EXTRA, (int)KE_XF1,
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_XF2,    KS_EXTRA, (int)KE_XF2,
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_XF3,    KS_EXTRA, (int)KE_XF3,
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_XF4,    KS_EXTRA, (int)KE_XF4,
+
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F1,     'k', '1',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F2,     'k', '2',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F3,     'k', '3',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F4,     'k', '4',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F5,     'k', '5',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F6,     'k', '6',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F7,     'k', '7',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F8,     'k', '8',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F9,     'k', '9',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F10,    'k', ';',
+
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F11,    'F', '1',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F12,    'F', '2',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F13,    'F', '3',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F14,    'F', '4',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F15,    'F', '5',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F16,    'F', '6',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F17,    'F', '7',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F18,    'F', '8',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F19,    'F', '9',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F20,    'F', 'A',
+
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F21,    'F', 'B',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F22,    'F', 'C',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F23,    'F', 'D',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F24,    'F', 'E',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F25,    'F', 'F',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F26,    'F', 'G',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F27,    'F', 'H',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F28,    'F', 'I',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F29,    'F', 'J',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F30,    'F', 'K',
+
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F31,    'F', 'L',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F32,    'F', 'M',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F33,    'F', 'N',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F34,    'F', 'O',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F35,    'F', 'P',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F36,    'F', 'Q',
+  MOD_MASK_SHIFT, KS_EXTRA, (int)KE_S_F37,    'F', 'R',
+
+  MOD_MASK_SHIFT, 'k', 'B',                   KS_EXTRA, (int)KE_TAB,
+
+  NUL
+};
+
+int simplify_key(const int key, int *modifiers)
+{
+  if (*modifiers & (MOD_MASK_SHIFT | MOD_MASK_CTRL | MOD_MASK_ALT)) {
+    // TAB is a special case.
+    if (key == TAB && (*modifiers & MOD_MASK_SHIFT)) {
+      *modifiers &= ~MOD_MASK_SHIFT;
+      return K_S_TAB;
+    }
+    const int key0 = KEY2TERMCAP0(key);
+    const int key1 = KEY2TERMCAP1(key);
+    for (int i = 0; modifier_keys_table[i] != NUL; i += MOD_KEYS_ENTRY_SIZE) {
+      if (key0 == modifier_keys_table[i + 3]
+          && key1 == modifier_keys_table[i + 4]
+          && (*modifiers & modifier_keys_table[i])) {
+        *modifiers &= ~modifier_keys_table[i];
+        return TERMCAP2KEY(modifier_keys_table[i + 1],
+                           modifier_keys_table[i + 2]);
+      }
+    }
+  }
+  return key;
+}
+
+int handle_x_keys(const int key)
+  FUNC_ATTR_CONST FUNC_ATTR_WARN_UNUSED_RESULT
+{
+  switch (key) {
+    case K_XUP:     return K_UP;
+    case K_XDOWN:   return K_DOWN;
+    case K_XLEFT:   return K_LEFT;
+    case K_XRIGHT:  return K_RIGHT;
+    case K_XHOME:   return K_HOME;
+    case K_ZHOME:   return K_HOME;
+    case K_XEND:    return K_END;
+    case K_ZEND:    return K_END;
+    case K_XF1:     return K_F1;
+    case K_XF2:     return K_F2;
+    case K_XF3:     return K_F3;
+    case K_XF4:     return K_F4;
+    case K_S_XF1:   return K_S_F1;
+    case K_S_XF2:   return K_S_F2;
+    case K_S_XF3:   return K_S_F3;
+    case K_S_XF4:   return K_S_F4;
+  }
+  return key;
+}
+
+static const struct key_name_entry {
+  int key;  ///< Special key code or ASCII value.
+  const char *name;  ///< Name of the key
+} key_names_table[] = {
+  {' ',               "Space"},
+  {TAB,               "Tab"},
+  {K_TAB,             "Tab"},
+  {NL,                "NL"},
+  {NL,                "NewLine"},     // Alternative name
+  {NL,                "LineFeed"},    // Alternative name
+  {NL,                "LF"},          // Alternative name
+  {CAR,               "CR"},
+  {CAR,               "Return"},      // Alternative name
+  {CAR,               "Enter"},       // Alternative name
+  {K_BS,              "BS"},
+  {K_BS,              "BackSpace"},   // Alternative name
+  {ESC,               "Esc"},
+  {CSI,               "CSI"},
+  {K_CSI,             "xCSI"},
+  {'|',               "Bar"},
+  {'\\',              "Bslash"},
+  {K_DEL,             "Del"},
+  {K_DEL,             "Delete"},      // Alternative name
+  {K_KDEL,            "kDel"},
+  {K_UP,              "Up"},
+  {K_DOWN,            "Down"},
+  {K_LEFT,            "Left"},
+  {K_RIGHT,           "Right"},
+  {K_XUP,             "xUp"},
+  {K_XDOWN,           "xDown"},
+  {K_XLEFT,           "xLeft"},
+  {K_XRIGHT,          "xRight"},
+
+  {K_F1,              "F1"},
+  {K_F2,              "F2"},
+  {K_F3,              "F3"},
+  {K_F4,              "F4"},
+  {K_F5,              "F5"},
+  {K_F6,              "F6"},
+  {K_F7,              "F7"},
+  {K_F8,              "F8"},
+  {K_F9,              "F9"},
+  {K_F10,             "F10"},
+
+  {K_F11,             "F11"},
+  {K_F12,             "F12"},
+  {K_F13,             "F13"},
+  {K_F14,             "F14"},
+  {K_F15,             "F15"},
+  {K_F16,             "F16"},
+  {K_F17,             "F17"},
+  {K_F18,             "F18"},
+  {K_F19,             "F19"},
+  {K_F20,             "F20"},
+
+  {K_F21,             "F21"},
+  {K_F22,             "F22"},
+  {K_F23,             "F23"},
+  {K_F24,             "F24"},
+  {K_F25,             "F25"},
+  {K_F26,             "F26"},
+  {K_F27,             "F27"},
+  {K_F28,             "F28"},
+  {K_F29,             "F29"},
+  {K_F30,             "F30"},
+
+  {K_F31,             "F31"},
+  {K_F32,             "F32"},
+  {K_F33,             "F33"},
+  {K_F34,             "F34"},
+  {K_F35,             "F35"},
+  {K_F36,             "F36"},
+  {K_F37,             "F37"},
+
+  {K_XF1,             "xF1"},
+  {K_XF2,             "xF2"},
+  {K_XF3,             "xF3"},
+  {K_XF4,             "xF4"},
+
+  {K_HELP,            "Help"},
+  {K_UNDO,            "Undo"},
+  {K_INS,             "Insert"},
+  {K_INS,             "Ins"},         // Alternative name
+  {K_KINS,            "kInsert"},
+  {K_HOME,            "Home"},
+  {K_KHOME,           "kHome"},
+  {K_XHOME,           "xHome"},
+  {K_ZHOME,           "zHome"},
+  {K_END,             "End"},
+  {K_KEND,            "kEnd"},
+  {K_XEND,            "xEnd"},
+  {K_ZEND,            "zEnd"},
+  {K_PAGEUP,          "PageUp"},
+  {K_PAGEDOWN,        "PageDown"},
+  {K_KPAGEUP,         "kPageUp"},
+  {K_KPAGEDOWN,       "kPageDown"},
+
+  {K_KPLUS,           "kPlus"},
+  {K_KMINUS,          "kMinus"},
+  {K_KDIVIDE,         "kDivide"},
+  {K_KMULTIPLY,       "kMultiply"},
+  {K_KENTER,          "kEnter"},
+  {K_KPOINT,          "kPoint"},
+
+  {K_K0,              "k0"},
+  {K_K1,              "k1"},
+  {K_K2,              "k2"},
+  {K_K3,              "k3"},
+  {K_K4,              "k4"},
+  {K_K5,              "k5"},
+  {K_K6,              "k6"},
+  {K_K7,              "k7"},
+  {K_K8,              "k8"},
+  {K_K9,              "k9"},
+
+  {'<',               "lt"},
+
+  {K_MOUSE,           "Mouse"},
+  {K_LEFTMOUSE,       "LeftMouse"},
+  {K_LEFTMOUSE_NM,    "LeftMouseNM"},
+  {K_LEFTDRAG,        "LeftDrag"},
+  {K_LEFTRELEASE,     "LeftRelease"},
+  {K_LEFTRELEASE_NM,  "LeftReleaseNM"},
+  {K_MIDDLEMOUSE,     "MiddleMouse"},
+  {K_MIDDLEDRAG,      "MiddleDrag"},
+  {K_MIDDLERELEASE,   "MiddleRelease"},
+  {K_RIGHTMOUSE,      "RightMouse"},
+  {K_RIGHTDRAG,       "RightDrag"},
+  {K_RIGHTRELEASE,    "RightRelease"},
+  {K_MOUSEDOWN,       "ScrollWheelUp"},
+  {K_MOUSEUP,         "ScrollWheelDown"},
+  {K_MOUSELEFT,       "ScrollWheelRight"},
+  {K_MOUSERIGHT,      "ScrollWheelLeft"},
+  {K_MOUSEDOWN,       "MouseDown"},  // OBSOLETE: Use ScrollWheelXXX instead
+  {K_MOUSEUP,         "MouseUp"},    // Same
+  {K_X1MOUSE,         "X1Mouse"},
+  {K_X1DRAG,          "X1Drag"},
+  {K_X1RELEASE,       "X1Release"},
+  {K_X2MOUSE,         "X2Mouse"},
+  {K_X2DRAG,          "X2Drag"},
+  {K_X2RELEASE,       "X2Release"},
+  {K_DROP,            "Drop"},
+  {K_ZERO,            "Nul"},
+  {K_SNR,             "SNR"},
+  {K_PLUG,            "Plug"},
+  {K_PASTE,           "Paste"},
+  {K_FOCUSGAINED,     "FocusGained"},
+  {K_FOCUSLOST,       "FocusLost"},
+  {0,                 NULL}
+};
+
+int get_special_key_code(const char_u *name)
+{
+  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; vim_isIDc(name[j]) && table_name[j] != NUL; j++) {
+      if (TOLOWER_ASC(table_name[j]) != TOLOWER_ASC(name[j])) {
+        break;
+      }
+    }
+    if (!vim_isIDc(name[j]) && table_name[j] == NUL) {
+      return key_names_table[i].key;
+    }
+  }
+
+  return 0;
+}
+
+
+static const struct modmasktable {
+  short mod_mask;  ///< Bit-mask for particular key modifier.
+  short mod_flag;  ///< Bit(s) for particular key modifier.
+  char_u name;  ///< Single letter name of modifier.
+} mod_mask_table[] = {
+  {MOD_MASK_ALT,              MOD_MASK_ALT,           (char_u)'M'},
+  {MOD_MASK_META,             MOD_MASK_META,          (char_u)'T'},
+  {MOD_MASK_CTRL,             MOD_MASK_CTRL,          (char_u)'C'},
+  {MOD_MASK_SHIFT,            MOD_MASK_SHIFT,         (char_u)'S'},
+  {MOD_MASK_MULTI_CLICK,      MOD_MASK_2CLICK,        (char_u)'2'},
+  {MOD_MASK_MULTI_CLICK,      MOD_MASK_3CLICK,        (char_u)'3'},
+  {MOD_MASK_MULTI_CLICK,      MOD_MASK_4CLICK,        (char_u)'4'},
+  {MOD_MASK_CMD,              MOD_MASK_CMD,           (char_u)'D'},
+  // 'A' must be the last one
+  {MOD_MASK_ALT,              MOD_MASK_ALT,           (char_u)'A'},
+  {0, 0, NUL}
+};
+
+int name_to_mod_mask(int c)
+{
+  c = TOUPPER_ASC(c);
+  for (size_t i = 0; mod_mask_table[i].mod_mask != 0; i++) {
+    if (c == mod_mask_table[i].name) {
+      return mod_mask_table[i].mod_flag;
+    }
+  }
+  return 0;
+}
+
+static int extract_modifiers(int key, int *modp)
+{
+  int modifiers = *modp;
+
+  if (!(modifiers & MOD_MASK_CMD)) {  // Command-key is special
+    if ((modifiers & MOD_MASK_SHIFT) && ASCII_ISALPHA(key)) {
+      key = TOUPPER_ASC(key);
+      modifiers &= ~MOD_MASK_SHIFT;
+    }
+  }
+  if ((modifiers & MOD_MASK_CTRL)
+      && ((key >= '?' && key <= '_') || ASCII_ISALPHA(key))) {
+    key = Ctrl_chr(key);
+    modifiers &= ~MOD_MASK_CTRL;
+    if (key == 0) {  // <C-@> is <Nul>
+      key = K_ZERO;
+    }
+  }
+
+  *modp = modifiers;
+  return key;
+}
+
+int find_special_key(const char_u **srcp, const size_t src_len, int *const modp,
+                     const bool keycode, const bool keep_x_key,
+                     const bool in_string)
+{
+  const char_u *last_dash;
+  const char_u *end_of_name;
+  const char_u *src;
+  const char_u *bp;
+  const char_u *const end = *srcp + src_len - 1;
+  int modifiers;
+  int bit;
+  int key;
+  uvarnumber_T n;
+  int l;
+
+  if (src_len == 0) {
+    return 0;
+  }
+
+  src = *srcp;
+  if (src[0] != '<') {
+    return 0;
+  }
+
+  // Find end of modifier list
+  last_dash = src;
+  for (bp = src + 1; bp <= end && (*bp == '-' || vim_isIDc(*bp)); bp++) {
+    if (*bp == '-') {
+      last_dash = bp;
+      if (bp + 1 <= end) {
+        l = utfc_ptr2len_len(bp + 1, (int)(end - bp) + 1);
+        // Anything accepted, like <C-?>.
+        // <C-"> or <M-"> are not special in strings as " is
+        // the string delimiter. With a backslash it works: <M-\">
+        if (end - bp > l && !(in_string && bp[1] == '"') && bp[2] == '>') {
+          bp += l;
+        } else if (end - bp > 2 && in_string && bp[1] == '\\'
+                   && bp[2] == '"' && bp[3] == '>') {
+          bp += 2;
+        }
+      }
+    }
+    if (end - bp > 3 && bp[0] == 't' && bp[1] == '_') {
+      bp += 3;  // skip t_xx, xx may be '-' or '>'
+    } else if (end - bp > 4 && STRNICMP(bp, "char-", 5) == 0) {
+      vim_str2nr(bp + 5, NULL, &l, STR2NR_ALL, NULL, NULL, 0);
+      bp += l + 5;
+      break;
+    }
+  }
+
+  if (bp <= end && *bp == '>') {  // found matching '>'
+    end_of_name = bp + 1;
+
+    /* Which modifiers are given? */
+    modifiers = 0x0;
+    for (bp = src + 1; bp < last_dash; bp++) {
+      if (*bp != '-') {
+        bit = name_to_mod_mask(*bp);
+        if (bit == 0x0) {
+          break;                // Illegal modifier name
+        }
+        modifiers |= bit;
+      }
+    }
+
+    // Legal modifier name.
+    if (bp >= last_dash) {
+      if (STRNICMP(last_dash + 1, "char-", 5) == 0
+          && ascii_isdigit(last_dash[6])) {
+        // <Char-123> or <Char-033> or <Char-0x33>
+        vim_str2nr(last_dash + 6, NULL, NULL, STR2NR_ALL, NULL, &n, 0);
+        key = (int)n;
+      } else {
+        int off = 1;
+
+        // Modifier with single letter, or special key name.
+        if (in_string && last_dash[1] == '\\' && last_dash[2] == '"') {
+          off = 2;
+        }
+        l = mb_ptr2len(last_dash + 1);
+        if (modifiers !=