Merge pull request #21850 from zeertzjq/vim-8.2.4463

vim-patch:8.2.{4463,4465,4475,4477,4478,4479,4608}: fuzzy cmdline builtin completion

1 files changed, 147 insertions, 38 deletions

diff --git a/src/nvim/cmdexpand.c b/src/nvim/cmdexpand.c
index ca19d6de95..4559e83e20 100644
--- a/src/nvim/cmdexpand.c
+++ b/src/nvim/cmdexpand.c
@@ -91,6 +91,38 @@ static int compl_selected;
 
 #define SHOW_MATCH(m) (showtail ? showmatches_gettail(matches[m], false) : matches[m])
 
+/// Returns true if fuzzy completion is supported for a given cmdline completion
+/// context.
+static bool cmdline_fuzzy_completion_supported(const expand_T *const xp)
+  FUNC_ATTR_WARN_UNUSED_RESULT FUNC_ATTR_NONNULL_ALL FUNC_ATTR_PURE
+{
+  return (wop_flags & WOP_FUZZY)
+         && xp->xp_context != EXPAND_BOOL_SETTINGS
+         && xp->xp_context != EXPAND_COLORS
+         && xp->xp_context != EXPAND_COMPILER
+         && xp->xp_context != EXPAND_DIRECTORIES
+         && xp->xp_context != EXPAND_FILES
+         && xp->xp_context != EXPAND_FILES_IN_PATH
+         && xp->xp_context != EXPAND_FILETYPE
+         && xp->xp_context != EXPAND_HELP
+         && xp->xp_context != EXPAND_OLD_SETTING
+         && xp->xp_context != EXPAND_OWNSYNTAX
+         && xp->xp_context != EXPAND_PACKADD
+         && xp->xp_context != EXPAND_SHELLCMD
+         && xp->xp_context != EXPAND_TAGS
+         && xp->xp_context != EXPAND_TAGS_LISTFILES
+         && xp->xp_context != EXPAND_USER_DEFINED
+         && xp->xp_context != EXPAND_USER_LIST;
+}
+
+/// Returns true if fuzzy completion for cmdline completion is enabled and
+/// "fuzzystr" is not empty.
+bool cmdline_fuzzy_complete(const char *const fuzzystr)
+  FUNC_ATTR_WARN_UNUSED_RESULT FUNC_ATTR_NONNULL_ALL FUNC_ATTR_PURE
+{
+  return (wop_flags & WOP_FUZZY) && *fuzzystr != NUL;
+}
+
 /// Sort function for the completion matches.
 /// <SNR> functions should be sorted to the end.
 static int sort_func_compare(const void *s1, const void *s2)
@@ -223,8 +255,13 @@ int nextwild(expand_T *xp, int type, int options, bool escape)
     // Get next/previous match for a previous expanded pattern.
     p2 = ExpandOne(xp, NULL, NULL, 0, type);
   } else {
+    if (cmdline_fuzzy_completion_supported(xp)) {
+      // If fuzzy matching, don't modify the search string
+      p1 = xstrdup(xp->xp_pattern);
+    } else {
+      p1 = addstar(xp->xp_pattern, xp->xp_pattern_len, xp->xp_context);
+    }
     // Translate string into pattern and expand it.
-    p1 = addstar(xp->xp_pattern, xp->xp_pattern_len, xp->xp_context);
     const int use_options = (options
                              | WILD_HOME_REPLACE
                              | WILD_ADD_SLASH
@@ -1335,13 +1372,16 @@ static const char *set_cmd_index(const char *cmd, exarg_T *eap, expand_T *xp, in
 {
   const char *p = NULL;
   size_t len = 0;
+  const bool fuzzy = cmdline_fuzzy_complete(cmd);
 
   // Isolate the command and search for it in the command table.
   // Exceptions:
-  // - the 'k' command can directly be followed by any character, but
-  //   do accept "keepmarks", "keepalt" and "keepjumps".
+  // - the 'k' command can directly be followed by any character, but do
+  // accept "keepmarks", "keepalt" and "keepjumps". As fuzzy matching can
+  // find matches anywhere in the command name, do this only for command
+  // expansion based on regular expression and not for fuzzy matching.
   // - the 's' command can be followed directly by 'c', 'g', 'i', 'I' or 'r'
-  if (*cmd == 'k' && cmd[1] != 'e') {
+  if (!fuzzy && (*cmd == 'k' && cmd[1] != 'e')) {
     eap->cmdidx = CMD_k;
     p = cmd + 1;
   } else {
@@ -1375,7 +1415,9 @@ static const char *set_cmd_index(const char *cmd, exarg_T *eap, expand_T *xp, in
 
     eap->cmdidx = excmd_get_cmdidx(cmd, len);
 
-    if (cmd[0] >= 'A' && cmd[0] <= 'Z') {
+    // User defined commands support alphanumeric characters.
+    // Also when doing fuzzy expansion, support alphanumeric characters.
+    if ((cmd[0] >= 'A' && cmd[0] <= 'Z') || (fuzzy && *p != NUL)) {
       while (ASCII_ISALNUM(*p) || *p == '*') {  // Allow * wild card
         p++;
       }
@@ -2330,7 +2372,12 @@ int expand_cmdline(expand_T *xp, const char *str, int col, int *matchcount, char
   // add star to file name, or convert to regexp if not exp. files.
   assert((str + col) - xp->xp_pattern >= 0);
   xp->xp_pattern_len = (size_t)((str + col) - xp->xp_pattern);
-  file_str = addstar(xp->xp_pattern, xp->xp_pattern_len, xp->xp_context);
+  if (cmdline_fuzzy_completion_supported(xp)) {
+    // If fuzzy matching, don't modify the search string
+    file_str = xstrdup(xp->xp_pattern);
+  } else {
+    file_str = addstar(xp->xp_pattern, xp->xp_pattern_len, xp->xp_context);
+  }
 
   if (p_wic) {
     options += WILD_ICASE;
@@ -2490,7 +2537,7 @@ static char *get_healthcheck_names(expand_T *xp FUNC_ATTR_UNUSED, int idx)
 }
 
 /// Do the expansion based on xp->xp_context and "rmp".
-static int ExpandOther(expand_T *xp, regmatch_T *rmp, char ***matches, int *numMatches)
+static int ExpandOther(char *pat, expand_T *xp, regmatch_T *rmp, char ***matches, int *numMatches)
 {
   typedef CompleteListItemGetter ExpandFunc;
   static struct expgen {
@@ -2538,10 +2585,16 @@ static int ExpandOther(expand_T *xp, regmatch_T *rmp, char ***matches, int *numM
   // right function to do the expansion.
   for (int i = 0; i < (int)ARRAY_SIZE(tab); i++) {
     if (xp->xp_context == tab[i].context) {
+      // Use fuzzy matching if 'wildoptions' has "fuzzy".
+      // If no search pattern is supplied, then don't use fuzzy
+      // matching and return all the found items.
+      const bool fuzzy = cmdline_fuzzy_complete(pat);
+
       if (tab[i].ic) {
         rmp->rm_ic = true;
       }
-      ExpandGeneric(xp, rmp, matches, numMatches, tab[i].func, tab[i].escaped);
+      ExpandGeneric(xp, rmp, matches, numMatches, tab[i].func, tab[i].escaped,
+                    fuzzy ? pat : NULL);
       ret = OK;
       break;
     }
@@ -2581,9 +2634,11 @@ static int map_wildopts_to_ewflags(int options)
 /// @param options  WILD_ flags
 static int ExpandFromContext(expand_T *xp, char *pat, char ***matches, int *numMatches, int options)
 {
-  regmatch_T regmatch;
+  regmatch_T regmatch = { .rm_ic = false };
   int ret;
   int flags = map_wildopts_to_ewflags(options);
+  const bool fuzzy = cmdline_fuzzy_complete(pat)
+                     && cmdline_fuzzy_completion_supported(xp);
 
   if (xp->xp_context == EXPAND_FILES
       || xp->xp_context == EXPAND_DIRECTORIES
@@ -2664,26 +2719,30 @@ static int ExpandFromContext(expand_T *xp, char *pat, char ***matches, int *numM
     return nlua_expand_pat(xp, pat, numMatches, matches);
   }
 
-  regmatch.regprog = vim_regcomp(pat, magic_isset() ? RE_MAGIC : 0);
-  if (regmatch.regprog == NULL) {
-    return FAIL;
-  }
+  if (!fuzzy) {
+    regmatch.regprog = vim_regcomp(pat, magic_isset() ? RE_MAGIC : 0);
+    if (regmatch.regprog == NULL) {
+      return FAIL;
+    }
 
-  // set ignore-case according to p_ic, p_scs and pat
-  regmatch.rm_ic = ignorecase(pat);
+    // set ignore-case according to p_ic, p_scs and pat
+    regmatch.rm_ic = ignorecase(pat);
+  }
 
   if (xp->xp_context == EXPAND_SETTINGS
       || xp->xp_context == EXPAND_BOOL_SETTINGS) {
-    ret = ExpandSettings(xp, &regmatch, numMatches, matches);
+    ret = ExpandSettings(xp, &regmatch, pat, numMatches, matches);
   } else if (xp->xp_context == EXPAND_MAPPINGS) {
-    ret = ExpandMappings(&regmatch, numMatches, matches);
+    ret = ExpandMappings(pat, &regmatch, numMatches, matches);
   } else if (xp->xp_context == EXPAND_USER_DEFINED) {
     ret = ExpandUserDefined(xp, &regmatch, matches, numMatches);
   } else {
-    ret = ExpandOther(xp, &regmatch, matches, numMatches);
+    ret = ExpandOther(pat, xp, &regmatch, matches, numMatches);
   }
 
-  vim_regfree(regmatch.regprog);
+  if (!fuzzy) {
+    vim_regfree(regmatch.regprog);
+  }
   xfree(tofree);
 
   return ret;
@@ -2695,13 +2754,17 @@ static int ExpandFromContext(expand_T *xp, char *pat, char ***matches, int *numM
 /// obtain strings, one by one.  The strings are matched against a regexp
 /// program.  Matching strings are copied into an array, which is returned.
 ///
+/// If "fuzzystr" is not NULL, then fuzzy matching is used. Otherwise,
+/// regex matching is used.
+///
 /// @param func  returns a string from the list
 static void ExpandGeneric(expand_T *xp, regmatch_T *regmatch, char ***matches, int *numMatches,
-                          CompleteListItemGetter func, int escaped)
+                          CompleteListItemGetter func, int escaped, const char *const fuzzystr)
 {
   int i;
   size_t count = 0;
   char *str;
+  const bool fuzzy = fuzzystr != NULL;
 
   // count the number of matching names
   for (i = 0;; i++) {
@@ -2712,7 +2775,14 @@ static void ExpandGeneric(expand_T *xp, regmatch_T *regmatch, char ***matches, i
     if (*str == NUL) {  // skip empty strings
       continue;
     }
-    if (vim_regexec(regmatch, str, (colnr_T)0)) {
+
+    bool match;
+    if (!fuzzy) {
+      match = vim_regexec(regmatch, str, (colnr_T)0);
+    } else {
+      match = fuzzy_match_str(str, fuzzystr) != 0;
+    }
+    if (match) {
       count++;
     }
   }
@@ -2721,7 +2791,12 @@ static void ExpandGeneric(expand_T *xp, regmatch_T *regmatch, char ***matches, i
   }
   assert(count < INT_MAX);
   *numMatches = (int)count;
-  *matches = xmalloc(count * sizeof(char *));
+  fuzmatch_str_T *fuzmatch = NULL;
+  if (fuzzy) {
+    fuzmatch = xmalloc(count * sizeof(fuzmatch_str_T));
+  } else {
+    *matches = xmalloc(count * sizeof(char *));
+  }
 
   // copy the matching names into allocated memory
   count = 0;
@@ -2733,38 +2808,66 @@ static void ExpandGeneric(expand_T *xp, regmatch_T *regmatch, char ***matches, i
     if (*str == NUL) {  // Skip empty strings.
       continue;
     }
-    if (vim_regexec(regmatch, str, (colnr_T)0)) {
-      if (escaped) {
-        str = vim_strsave_escaped(str, " \t\\.");
-      } else {
-        str = xstrdup(str);
-      }
-      (*matches)[count++] = str;
-      if (func == get_menu_names) {
-        // Test for separator added by get_menu_names().
-        str += strlen(str) - 1;
-        if (*str == '\001') {
-          *str = '.';
-        }
+
+    bool match;
+    int score = 0;
+    if (!fuzzy) {
+      match = vim_regexec(regmatch, str, (colnr_T)0);
+    } else {
+      score = fuzzy_match_str(str, fuzzystr);
+      match = (score != 0);
+    }
+    if (!match) {
+      continue;
+    }
+
+    if (escaped) {
+      str = vim_strsave_escaped(str, " \t\\.");
+    } else {
+      str = xstrdup(str);
+    }
+    if (fuzzy) {
+      fuzmatch[count].idx = (int)count;
+      fuzmatch[count].str = str;
+      fuzmatch[count].score = score;
+    } else {
+      (*matches)[count] = str;
+    }
+    count++;
+    if (func == get_menu_names) {
+      // Test for separator added by get_menu_names().
+      str += strlen(str) - 1;
+      if (*str == '\001') {
+        *str = '.';
       }
     }
   }
 
   // Sort the results.  Keep menu's in the specified order.
+  bool funcsort = false;
   if (xp->xp_context != EXPAND_MENUNAMES && xp->xp_context != EXPAND_MENUS) {
     if (xp->xp_context == EXPAND_EXPRESSION
         || xp->xp_context == EXPAND_FUNCTIONS
         || xp->xp_context == EXPAND_USER_FUNC) {
       // <SNR> functions should be sorted to the end.
-      qsort((void *)(*matches), (size_t)(*numMatches), sizeof(char *), sort_func_compare);
+      funcsort = true;
+      if (!fuzzy) {
+        qsort(*matches, (size_t)(*numMatches), sizeof(char *), sort_func_compare);
+      }
     } else {
-      sort_strings(*matches, *numMatches);
+      if (!fuzzy) {
+        sort_strings(*matches, *numMatches);
+      }
     }
   }
 
   // Reset the variables used for special highlight names expansion, so that
   // they don't show up when getting normal highlight names by ID.
   reset_expand_highlight();
+
+  if (fuzzy) {
+    fuzzymatches_to_strmatches(fuzmatch, matches, (int)count, funcsort);
+  }
 }
 
 /// Expand shell command matches in one directory of $PATH.
@@ -3369,7 +3472,13 @@ void f_getcompletion(typval_T *argvars, typval_T *rettv, EvalFuncData fptr)
   }
 
 theend:
-  pat = addstar(xpc.xp_pattern, xpc.xp_pattern_len, xpc.xp_context);
+  if (cmdline_fuzzy_completion_supported(&xpc)) {
+    // when fuzzy matching, don't modify the search string
+    pat = xstrdup(xpc.xp_pattern);
+  } else {
+    pat = addstar(xpc.xp_pattern, xpc.xp_pattern_len, xpc.xp_context);
+  }
+
   ExpandOne(&xpc, pat, NULL, options, WILD_ALL_KEEP);
   tv_list_alloc_ret(rettv, xpc.xp_numfiles);