diff options
| -rw-r--r-- | runtime/doc/options.txt | 8 | ||||
| -rw-r--r-- | src/nvim/buffer.c | 135 | ||||
| -rw-r--r-- | src/nvim/cmdexpand.c | 104 | ||||
| -rw-r--r-- | src/nvim/option.c | 88 | ||||
| -rw-r--r-- | src/nvim/option_defs.h | 1 | ||||
| -rw-r--r-- | src/nvim/optionstr.c | 2 | ||||
| -rw-r--r-- | src/nvim/search.c | 105 | ||||
| -rw-r--r-- | src/nvim/search.h | 8 | ||||
| -rw-r--r-- | src/nvim/testdir/test_cmdline.vim | 318 |
9 files changed, 693 insertions, 76 deletions
diff --git a/runtime/doc/options.txt b/runtime/doc/options.txt index efeeba983e..0683bb0602 100644 --- a/runtime/doc/options.txt +++ b/runtime/doc/options.txt @@ -7126,6 +7126,14 @@ A jump table for the options with a short description can be found at |Q_op|. global A list of words that change how |cmdline-completion| is done. The following values are supported: + fuzzy Use fuzzy matching to find completion matches. When + this value is specified, wildcard expansion will not + be used for completion. The matches will be sorted by + the "best match" rather than alphabetically sorted. + This will find more matches than the wildcard + expansion. Currently fuzzy matching based completion + is not supported for file and directory names and + instead wildcard expansion is used. pum Display the completion matches using the popup menu in the same style as the |ins-completion-menu|. tagfile When using CTRL-D to list matching tags, the kind of diff --git a/src/nvim/buffer.c b/src/nvim/buffer.c index cd1059eb0d..32e0cf5acf 100644 --- a/src/nvim/buffer.c +++ b/src/nvim/buffer.c @@ -88,6 +88,7 @@ #include "nvim/regexp.h" #include "nvim/runtime.h" #include "nvim/screen.h" +#include "nvim/search.h" #include "nvim/sign.h" #include "nvim/spell.h" #include "nvim/statusline.h" @@ -2337,7 +2338,6 @@ int ExpandBufnames(char *pat, int *num_file, char ***file, int options) int round; char *p; int attempt; - char *patc; bufmatch_T *matches = NULL; *num_file = 0; // return values in case of FAIL @@ -2347,31 +2347,40 @@ int ExpandBufnames(char *pat, int *num_file, char ***file, int options) return FAIL; } - // Make a copy of "pat" and change "^" to "\(^\|[\/]\)". - if (*pat == '^') { - patc = xmalloc(strlen(pat) + 11); - STRCPY(patc, "\\(^\\|[\\/]\\)"); - STRCPY(patc + 11, pat + 1); - } else { - patc = pat; + const bool fuzzy = cmdline_fuzzy_complete(pat); + + char *patc = NULL; + // Make a copy of "pat" and change "^" to "\(^\|[\/]\)" (if doing regular + // expression matching) + if (!fuzzy) { + if (*pat == '^') { + patc = xmalloc(strlen(pat) + 11); + STRCPY(patc, "\\(^\\|[\\/]\\)"); + STRCPY(patc + 11, pat + 1); + } else { + patc = pat; + } } + fuzmatch_str_T *fuzmatch = NULL; // attempt == 0: try match with '\<', match at start of word // attempt == 1: try match without '\<', match anywhere - for (attempt = 0; attempt <= 1; attempt++) { - if (attempt > 0 && patc == pat) { - break; // there was no anchor, no need to try again - } - + for (attempt = 0; attempt <= (fuzzy ? 0 : 1); attempt++) { regmatch_T regmatch; - regmatch.regprog = vim_regcomp(patc + attempt * 11, RE_MAGIC); - if (regmatch.regprog == NULL) { - if (patc != pat) { - xfree(patc); + if (!fuzzy) { + if (attempt > 0 && patc == pat) { + break; // there was no anchor, no need to try again + } + regmatch.regprog = vim_regcomp(patc + attempt * 11, RE_MAGIC); + if (regmatch.regprog == NULL) { + if (patc != pat) { + xfree(patc); + } + return FAIL; } - return FAIL; } + int score = 0; // round == 1: Count the matches. // round == 2: Build the array to keep the matches. for (round = 1; round <= 2; round++) { @@ -2387,7 +2396,23 @@ int ExpandBufnames(char *pat, int *num_file, char ***file, int options) continue; } } - p = buflist_match(®match, buf, p_wic); + + if (!fuzzy) { + p = buflist_match(®match, buf, p_wic); + } else { + p = NULL; + // first try matching with the short file name + if ((score = fuzzy_match_str(buf->b_sfname, pat)) != 0) { + p = buf->b_sfname; + } + if (p == NULL) { + // next try matching with the full path file name + if ((score = fuzzy_match_str(buf->b_ffname, pat)) != 0) { + p = buf->b_ffname; + } + } + } + if (p != NULL) { if (round == 1) { count++; @@ -2397,12 +2422,20 @@ int ExpandBufnames(char *pat, int *num_file, char ***file, int options) } else { p = xstrdup(p); } - if (matches != NULL) { - matches[count].buf = buf; - matches[count].match = p; - count++; + + if (!fuzzy) { + if (matches != NULL) { + matches[count].buf = buf; + matches[count].match = p; + count++; + } else { + (*file)[count++] = p; + } } else { - (*file)[count++] = p; + fuzmatch[count].idx = count; + fuzmatch[count].str = p; + fuzmatch[count].score = score; + count++; } } } @@ -2411,40 +2444,50 @@ int ExpandBufnames(char *pat, int *num_file, char ***file, int options) break; } if (round == 1) { - *file = xmalloc((size_t)count * sizeof(**file)); - - if (options & WILD_BUFLASTUSED) { - matches = xmalloc((size_t)count * sizeof(*matches)); + if (!fuzzy) { + *file = xmalloc((size_t)count * sizeof(**file)); + if (options & WILD_BUFLASTUSED) { + matches = xmalloc((size_t)count * sizeof(*matches)); + } + } else { + fuzmatch = xmalloc((size_t)count * sizeof(fuzmatch_str_T)); } } } - vim_regfree(regmatch.regprog); - if (count) { // match(es) found, break here - break; + + if (!fuzzy) { + vim_regfree(regmatch.regprog); + if (count) { // match(es) found, break here + break; + } } } - if (patc != pat) { + if (!fuzzy && patc != pat) { xfree(patc); } - if (matches != NULL) { - if (count > 1) { - qsort(matches, (size_t)count, sizeof(bufmatch_T), buf_time_compare); - } - - // if the current buffer is first in the list, place it at the end - if (matches[0].buf == curbuf) { - for (int i = 1; i < count; i++) { - (*file)[i - 1] = matches[i].match; + if (!fuzzy) { + if (matches != NULL) { + if (count > 1) { + qsort(matches, (size_t)count, sizeof(bufmatch_T), buf_time_compare); } - (*file)[count - 1] = matches[0].match; - } else { - for (int i = 0; i < count; i++) { - (*file)[i] = matches[i].match; + + // if the current buffer is first in the list, place it at the end + if (matches[0].buf == curbuf) { + for (int i = 1; i < count; i++) { + (*file)[i - 1] = matches[i].match; + } + (*file)[count - 1] = matches[0].match; + } else { + for (int i = 0; i < count; i++) { + (*file)[i] = matches[i].match; + } } + xfree(matches); } - xfree(matches); + } else { + fuzzymatches_to_strmatches(fuzmatch, file, count, false); } *num_file = count; diff --git a/src/nvim/cmdexpand.c b/src/nvim/cmdexpand.c index ca19d6de95..f18869bb1c 100644 --- a/src/nvim/cmdexpand.c +++ b/src/nvim/cmdexpand.c @@ -91,6 +91,39 @@ 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_MAPPINGS + && 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 +256,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 @@ -2330,7 +2368,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 +2533,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 +2581,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; } @@ -2674,13 +2723,13 @@ static int ExpandFromContext(expand_T *xp, char *pat, char ***matches, int *numM if (xp->xp_context == EXPAND_SETTINGS || xp->xp_context == EXPAND_BOOL_SETTINGS) { - ret = ExpandSettings(xp, ®match, numMatches, matches); + ret = ExpandSettings(xp, ®match, pat, numMatches, matches); } else if (xp->xp_context == EXPAND_MAPPINGS) { ret = ExpandMappings(®match, numMatches, matches); } else if (xp->xp_context == EXPAND_USER_DEFINED) { ret = ExpandUserDefined(xp, ®match, matches, numMatches); } else { - ret = ExpandOther(xp, ®match, matches, numMatches); + ret = ExpandOther(pat, xp, ®match, matches, numMatches); } vim_regfree(regmatch.regprog); @@ -2695,13 +2744,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 +2765,8 @@ 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 (vim_regexec(regmatch, str, (colnr_T)0) + || (fuzzy && fuzzy_match_str(str, fuzzystr) != 0)) { count++; } } @@ -2721,7 +2775,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,13 +2792,22 @@ 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)) { + int score; + if (vim_regexec(regmatch, str, (colnr_T)0) + || (fuzzy && ((score = fuzzy_match_str(str, fuzzystr)) != 0))) { if (escaped) { str = vim_strsave_escaped(str, " \t\\."); } else { str = xstrdup(str); } - (*matches)[count++] = 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; @@ -2751,20 +2819,30 @@ static void ExpandGeneric(expand_T *xp, regmatch_T *regmatch, char ***matches, i } // 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. diff --git a/src/nvim/option.c b/src/nvim/option.c index 85725f36ea..aec91a4dc6 100644 --- a/src/nvim/option.c +++ b/src/nvim/option.c @@ -36,6 +36,7 @@ #include "nvim/buffer.h" #include "nvim/change.h" #include "nvim/charset.h" +#include "nvim/cmdexpand.h" #include "nvim/cursor_shape.h" #include "nvim/decoration_provider.h" #include "nvim/diff.h" @@ -81,6 +82,7 @@ #include "nvim/regexp.h" #include "nvim/runtime.h" #include "nvim/screen.h" +#include "nvim/search.h" #include "nvim/sign_defs.h" #include "nvim/spell.h" #include "nvim/spellfile.h" @@ -4698,13 +4700,56 @@ void set_context_in_set_cmd(expand_T *xp, char *arg, int opt_flags) } } -int ExpandSettings(expand_T *xp, regmatch_T *regmatch, int *num_file, char ***file) +/// Returns true if "str" either matches "regmatch" or fuzzy matches "pat". +/// +/// If "test_only" is true and "fuzzy" is false and if "str" matches the regular +/// expression "regmatch", then returns true. Otherwise returns false. +/// +/// If "test_only" is false and "fuzzy" is false and if "str" matches the +/// regular expression "regmatch", then stores the match in matches[idx] and +/// returns true. +/// +/// If "test_only" is true and "fuzzy" is true and if "str" fuzzy matches +/// "fuzzystr", then returns true. Otherwise returns false. +/// +/// If "test_only" is false and "fuzzy" is true and if "str" fuzzy matches +/// "fuzzystr", then stores the match details in fuzmatch[idx] and returns true. +static bool match_str(char *const str, regmatch_T *const regmatch, char **const matches, + const int idx, const bool test_only, const bool fuzzy, + const char *const fuzzystr, fuzmatch_str_T *const fuzmatch) +{ + if (!fuzzy) { + if (vim_regexec(regmatch, str, (colnr_T)0)) { + if (!test_only) { + matches[idx] = xstrdup(str); + } + return true; + } + } else { + const int score = fuzzy_match_str(str, fuzzystr); + if (score != 0) { + if (!test_only) { + fuzmatch[idx].idx = idx; + fuzmatch[idx].str = xstrdup(str); + fuzmatch[idx].score = score; + } + return true; + } + } + return false; +} + +int ExpandSettings(expand_T *xp, regmatch_T *regmatch, char *fuzzystr, int *numMatches, + char ***matches) { int num_normal = 0; // Nr of matching non-term-code settings int count = 0; static char *(names[]) = { "all" }; int ic = regmatch->rm_ic; // remember the ignore-case flag + fuzmatch_str_T *fuzmatch = NULL; + const bool fuzzy = cmdline_fuzzy_complete(fuzzystr); + // do this loop twice: // loop == 0: count the number of matching options // loop == 1: copy the matching options into allocated memory @@ -4714,11 +4759,12 @@ int ExpandSettings(expand_T *xp, regmatch_T *regmatch, int *num_file, char ***fi if (xp->xp_context != EXPAND_BOOL_SETTINGS) { for (match = 0; match < (int)ARRAY_SIZE(names); match++) { - if (vim_regexec(regmatch, names[match], (colnr_T)0)) { + if (match_str(names[match], regmatch, *matches, + count, (loop == 0), fuzzy, fuzzystr, fuzmatch)) { if (loop == 0) { num_normal++; } else { - (*file)[count++] = xstrdup(names[match]); + count++; } } } @@ -4733,33 +4779,45 @@ int ExpandSettings(expand_T *xp, regmatch_T *regmatch, int *num_file, char ***fi && !(options[opt_idx].flags & P_BOOL)) { continue; } - match = false; - if (vim_regexec(regmatch, str, (colnr_T)0) - || (options[opt_idx].shortname != NULL - && vim_regexec(regmatch, - options[opt_idx].shortname, - (colnr_T)0))) { - match = true; - } - if (match) { + if (match_str(str, regmatch, *matches, count, (loop == 0), + fuzzy, fuzzystr, fuzmatch)) { if (loop == 0) { num_normal++; } else { - (*file)[count++] = xstrdup(str); + count++; + } + } else if (!fuzzy && options[opt_idx].shortname != NULL + && vim_regexec(regmatch, options[opt_idx].shortname, (colnr_T)0)) { + // Compare against the abbreviated option name (for regular + // expression match). Fuzzy matching (previous if) already + // matches against both the expanded and abbreviated names. + if (loop == 0) { + num_normal++; + } else { + (*matches)[count++] = xstrdup(str); } } } if (loop == 0) { if (num_normal > 0) { - *num_file = num_normal; + *numMatches = num_normal; } else { return OK; } - *file = xmalloc((size_t)(*num_file) * sizeof(char *)); + if (!fuzzy) { + *matches = xmalloc((size_t)(*numMatches) * sizeof(char *)); + } else { + fuzmatch = xmalloc((size_t)(*numMatches) * sizeof(fuzmatch_str_T)); + } } } + + if (fuzzy) { + fuzzymatches_to_strmatches(fuzmatch, matches, count, false); + } + return OK; } diff --git a/src/nvim/option_defs.h b/src/nvim/option_defs.h index 3ffab71f22..6385d968dd 100644 --- a/src/nvim/option_defs.h +++ b/src/nvim/option_defs.h @@ -795,6 +795,7 @@ EXTERN char *p_wop; // 'wildoptions' EXTERN unsigned wop_flags; #define WOP_TAGFILE 0x01 #define WOP_PUM 0x02 +#define WOP_FUZZY 0x04 EXTERN long p_window; // 'window' EXTERN char *p_wak; // 'winaltkeys' EXTERN char *p_wig; // 'wildignore' diff --git a/src/nvim/optionstr.c b/src/nvim/optionstr.c index 86fd5c9404..a1a5cadd8d 100644 --- a/src/nvim/optionstr.c +++ b/src/nvim/optionstr.c @@ -91,7 +91,7 @@ static char *(p_swb_values[]) = { "useopen", "usetab", "split", "newtab", "vspli static char *(p_spk_values[]) = { "cursor", "screen", "topline", NULL }; static char *(p_tc_values[]) = { "followic", "ignore", "match", "followscs", "smart", NULL }; static char *(p_ve_values[]) = { "block", "insert", "all", "onemore", "none", "NONE", NULL }; -static char *(p_wop_values[]) = { "tagfile", "pum", NULL }; +static char *(p_wop_values[]) = { "tagfile", "pum", "fuzzy", NULL }; static char *(p_wak_values[]) = { "yes", "menu", "no", NULL }; static char *(p_mousem_values[]) = { "extend", "popup", "popup_setpos", "mac", NULL }; static char *(p_sel_values[]) = { "inclusive", "exclusive", "old", NULL }; diff --git a/src/nvim/search.c b/src/nvim/search.c index d46a40c1b4..ee99efed5d 100644 --- a/src/nvim/search.c +++ b/src/nvim/search.c @@ -3111,7 +3111,7 @@ static int fuzzy_match_recursive(const char *fuzpat, const char *str, uint32_t s /// "outScore" and the matching character positions in "matches". bool fuzzy_match(char *const str, const char *const pat_arg, const bool matchseq, int *const outScore, uint32_t *const matches, const int maxMatches) - FUNC_ATTR_NONNULL_ALL FUNC_ATTR_WARN_UNUSED_RESULT + FUNC_ATTR_NONNULL_ALL { const int len = mb_charlen(str); bool complete = false; @@ -3411,6 +3411,109 @@ void f_matchfuzzypos(typval_T *argvars, typval_T *rettv, EvalFuncData fptr) do_fuzzymatch(argvars, rettv, true); } +/// Same as fuzzy_match_item_compare() except for use with a string match +static int fuzzy_match_str_compare(const void *const s1, const void *const s2) + FUNC_ATTR_WARN_UNUSED_RESULT FUNC_ATTR_NONNULL_ALL FUNC_ATTR_PURE +{ + const int v1 = ((fuzmatch_str_T *)s1)->score; + const int v2 = ((fuzmatch_str_T *)s2)->score; + const int idx1 = ((fuzmatch_str_T *)s1)->idx; + const int idx2 = ((fuzmatch_str_T *)s2)->idx; + + return v1 == v2 ? (idx1 - idx2) : v1 > v2 ? -1 : 1; +} + +/// Sort fuzzy matches by score +static void fuzzy_match_str_sort(fuzmatch_str_T *const fm, const int sz) + FUNC_ATTR_NONNULL_ALL +{ + // Sort the list by the descending order of the match score + qsort(fm, (size_t)sz, sizeof(fuzmatch_str_T), fuzzy_match_str_compare); +} + +/// Same as fuzzy_match_item_compare() except for use with a function name +/// string match. <SNR> functions should be sorted to the end. +static int fuzzy_match_func_compare(const void *const s1, const void *const s2) + FUNC_ATTR_WARN_UNUSED_RESULT FUNC_ATTR_NONNULL_ALL FUNC_ATTR_PURE +{ + const int v1 = ((fuzmatch_str_T *)s1)->score; + const int v2 = ((fuzmatch_str_T *)s2)->score; + const int idx1 = ((fuzmatch_str_T *)s1)->idx; + const int idx2 = ((fuzmatch_str_T *)s2)->idx; + const char *const str1 = ((fuzmatch_str_T *)s1)->str; + const char *const str2 = ((fuzmatch_str_T *)s2)->str; + + if (*str1 != '<' && *str2 == '<') { + return -1; + } + if (*str1 == '<' && *str2 != '<') { + return 1; + } + return v1 == v2 ? (idx1 - idx2) : v1 > v2 ? -1 : 1; +} + +/// Sort fuzzy matches of function names by score. +/// <SNR> functions should be sorted to the end. +static void fuzzy_match_func_sort(fuzmatch_str_T *const fm, const int sz) + FUNC_ATTR_NONNULL_ALL +{ + // Sort the list by the descending order of the match score + qsort(fm, (size_t)sz, sizeof(fuzmatch_str_T), fuzzy_match_func_compare); +} + +/// Fuzzy match "pat" in "str". +/// @returns 0 if there is no match. Otherwise, returns the match score. +int fuzzy_match_str(char *const str, const char *const pat) + FUNC_ATTR_WARN_UNUSED_RESULT +{ + if (str == NULL || pat == NULL) { + return 0; + } + + int score = 0; + uint32_t matchpos[MAX_FUZZY_MATCHES]; + fuzzy_match(str, pat, false, &score, matchpos, sizeof(matchpos) / sizeof(matchpos[0])); + + return score; +} + +/// Copy a list of fuzzy matches into a string list after sorting the matches by +/// the fuzzy score. Frees the memory allocated for "fuzmatch". +void fuzzymatches_to_strmatches(fuzmatch_str_T *const fuzmatch, char ***const matches, + const int count, const bool funcsort) + FUNC_ATTR_NONNULL_ARG(2) +{ + if (count <= 0) { + return; + } + + *matches = xmalloc((size_t)count * sizeof(char *)); + + // Sort the list by the descending order of the match score + if (funcsort) { + fuzzy_match_func_sort(fuzmatch, count); + } else { + fuzzy_match_str_sort(fuzmatch, count); + } + + for (int i = 0; i < count; i++) { + (*matches)[i] = fuzmatch[i].str; + } + xfree(fuzmatch); +} + +/// Free a list of fuzzy string matches. +void fuzmatch_str_free(fuzmatch_str_T *const fuzmatch, int count) +{ + if (count <= 0 || fuzmatch == NULL) { + return; + } + while (count--) { + xfree(fuzmatch[count].str); + } + xfree(fuzmatch); +} + /// Get line "lnum" and copy it into "buf[LSIZE]". /// The copy is made because the regexp may make the line invalid when using a /// mark. diff --git a/src/nvim/search.h b/src/nvim/search.h index 092098d5fd..2f140ba840 100644 --- a/src/nvim/search.h +++ b/src/nvim/search.h @@ -99,6 +99,14 @@ typedef struct searchstat { int last_maxcount; // the max count of the last search } searchstat_T; +/// Fuzzy matched string list item. Used for fuzzy match completion. Items are +/// usually sorted by "score". The "idx" member is used for stable-sort. +typedef struct { + int idx; + char *str; + int score; +} fuzmatch_str_T; + #ifdef INCLUDE_GENERATED_DECLARATIONS # include "search.h.generated.h" #endif diff --git a/src/nvim/testdir/test_cmdline.vim b/src/nvim/testdir/test_cmdline.vim index a074263359..e068685164 100644 --- a/src/nvim/testdir/test_cmdline.vim +++ b/src/nvim/testdir/test_cmdline.vim @@ -2654,6 +2654,324 @@ func Test_cmdline_complete_dlist() call assert_equal("\"dlist 10 /pat/ | chistory", @:) endfunc +" Test for 'fuzzy' in 'wildoptions' (fuzzy completion) +func Test_wildoptions_fuzzy() + " argument list (only for :argdel) + argadd change.py count.py charge.py + set wildoptions& + call feedkeys(":argdel cge\<C-A>\<C-B>\"\<CR>", 'tx') + call assert_equal('"argdel cge', @:) + set wildoptions=fuzzy + call feedkeys(":argdel cge\<C-A>\<C-B>\"\<CR>", 'tx') + call assert_equal('"argdel change.py charge.py', @:) + %argdelete + + " autocmd group name fuzzy completion + set wildoptions& + augroup MyFuzzyGroup + augroup END + call feedkeys(":augroup mfg\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"augroup mfg', @:) + call feedkeys(":augroup My*p\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"augroup MyFuzzyGroup', @:) + set wildoptions=fuzzy + call feedkeys(":augroup mfg\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"augroup MyFuzzyGroup', @:) + call feedkeys(":augroup My*p\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"augroup My*p', @:) + augroup! MyFuzzyGroup + + " buffer name fuzzy completion + set wildoptions& + edit SomeFile.txt + enew + call feedkeys(":b SF\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"b SF', @:) + call feedkeys(":b S*File.txt\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"b SomeFile.txt', @:) + set wildoptions=fuzzy + call feedkeys(":b SF\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"b SomeFile.txt', @:) + call feedkeys(":b S*File.txt\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"b S*File.txt', @:) + %bw! + + " buffer name (full path) fuzzy completion + if has('unix') + set wildoptions& + call mkdir('Xcmd/Xstate/Xfile.js', 'p') + edit Xcmd/Xstate/Xfile.js + cd Xcmd/Xstate + enew + call feedkeys(":b CmdStateFile\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"b CmdStateFile', @:) + set wildoptions=fuzzy + call feedkeys(":b CmdStateFile\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_match('Xcmd/Xstate/Xfile.js$', @:) + cd - + call delete('Xcmd', 'rf') + endif + + " :behave suboptions fuzzy completion + set wildoptions& + call feedkeys(":behave xm\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"behave xm', @:) + call feedkeys(":behave xt*m\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"behave xterm', @:) + set wildoptions=fuzzy + call feedkeys(":behave xm\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"behave xterm', @:) + call feedkeys(":behave xt*m\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"behave xt*m', @:) + let g:Sline = '' + call feedkeys(":behave win\<C-D>\<F4>\<C-B>\"\<CR>", 'tx') + call assert_equal('mswin', g:Sline) + call assert_equal('"behave win', @:) + + " colorscheme name fuzzy completion - NOT supported + + " built-in command name fuzzy completion + set wildoptions& + call feedkeys(":sbwin\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"sbwin', @:) + call feedkeys(":sbr*d\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"sbrewind', @:) + set wildoptions=fuzzy + call feedkeys(":sbwin\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"sbrewind', @:) + call feedkeys(":sbr*d\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"sbr*d', @:) + + " compiler name fuzzy completion - NOT supported + + " :cscope suboptions fuzzy completion + if has('cscope') + set wildoptions& + call feedkeys(":cscope ret\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"cscope ret', @:) + call feedkeys(":cscope re*t\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"cscope reset', @:) + set wildoptions=fuzzy + call feedkeys(":cscope ret\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"cscope reset', @:) + call feedkeys(":cscope re*t\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"cscope re*t', @:) + endif + + " :diffget/:diffput buffer name fuzzy completion + new SomeBuffer + diffthis + new OtherBuffer + diffthis + set wildoptions& + call feedkeys(":diffget sbuf\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"diffget sbuf', @:) + call feedkeys(":diffput sbuf\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"diffput sbuf', @:) + set wildoptions=fuzzy + call feedkeys(":diffget sbuf\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"diffget SomeBuffer', @:) + call feedkeys(":diffput sbuf\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"diffput SomeBuffer', @:) + %bw! + + " directory name fuzzy completion - NOT supported + + " environment variable name fuzzy completion + set wildoptions& + call feedkeys(":echo $VUT\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"echo $VUT', @:) + set wildoptions=fuzzy + call feedkeys(":echo $VUT\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"echo $VIMRUNTIME', @:) + + " autocmd event fuzzy completion + set wildoptions& + call feedkeys(":autocmd BWout\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"autocmd BWout', @:) + set wildoptions=fuzzy + call feedkeys(":autocmd BWout\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"autocmd BufWipeout', @:) + + " vim expression fuzzy completion + let g:PerPlaceCount = 10 + set wildoptions& + call feedkeys(":let c = ppc\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"let c = ppc', @:) + set wildoptions=fuzzy + call feedkeys(":let c = ppc\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"let c = PerPlaceCount', @:) + + " file name fuzzy completion - NOT supported + + " files in path fuzzy completion - NOT supported + + " filetype name fuzzy completion - NOT supported + + " user defined function name completion + set wildoptions& + call feedkeys(":call Test_w_fuz\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"call Test_w_fuz', @:) + set wildoptions=fuzzy + call feedkeys(":call Test_w_fuz\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"call Test_wildoptions_fuzzy()', @:) + + " user defined command name completion + set wildoptions& + call feedkeys(":MsFeat\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"MsFeat', @:) + set wildoptions=fuzzy + call feedkeys(":MsFeat\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"MissingFeature', @:) + + " :help tag fuzzy completion - NOT supported + + " highlight group name fuzzy completion + set wildoptions& + call feedkeys(":highlight SKey\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"highlight SKey', @:) + call feedkeys(":highlight Sp*Key\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"highlight SpecialKey', @:) + set wildoptions=fuzzy + call feedkeys(":highlight SKey\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"highlight SpecialKey', @:) + call feedkeys(":highlight Sp*Key\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"highlight Sp*Key', @:) + + " :history suboptions fuzzy completion + set wildoptions& + call feedkeys(":history dg\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"history dg', @:) + call feedkeys(":history se*h\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"history search', @:) + set wildoptions=fuzzy + call feedkeys(":history dg\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"history debug', @:) + call feedkeys(":history se*h\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"history se*h', @:) + + " :language locale name fuzzy completion + if has('unix') + set wildoptions& + call feedkeys(":lang psx\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"lang psx', @:) + set wildoptions=fuzzy + call feedkeys(":lang psx\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"lang POSIX', @:) + endif + + " :mapclear buffer argument fuzzy completion + set wildoptions& + call feedkeys(":mapclear buf\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"mapclear buf', @:) + set wildoptions=fuzzy + call feedkeys(":mapclear buf\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"mapclear <buffer>', @:) + + " map name fuzzy completion - NOT supported + + " menu name fuzzy completion + if has('gui_running') + set wildoptions& + call feedkeys(":menu pup\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"menu pup', @:) + set wildoptions=fuzzy + call feedkeys(":menu pup\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"menu PopUp.', @:) + endif + + " :messages suboptions fuzzy completion + set wildoptions& + call feedkeys(":messages clr\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"messages clr', @:) + set wildoptions=fuzzy + call feedkeys(":messages clr\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"messages clear', @:) + + " :set option name fuzzy completion + set wildoptions& + call feedkeys(":set brkopt\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"set brkopt', @:) + set wildoptions=fuzzy + call feedkeys(":set brkopt\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"set breakindentopt', @:) + set wildoptions& + call feedkeys(":set fixeol\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"set fixendofline', @:) + set wildoptions=fuzzy + call feedkeys(":set fixeol\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"set fixendofline', @:) + + " :set <term_option> + " Nvim does not support term options + " set wildoptions& + " call feedkeys(":set t_E\<Tab>\<C-B>\"\<CR>", 'tx') + " call assert_equal('"set t_EC', @:) + " call feedkeys(":set <t_E\<Tab>\<C-B>\"\<CR>", 'tx') + " call assert_equal('"set <t_EC>', @:) + " set wildoptions=fuzzy + " call feedkeys(":set t_E\<Tab>\<C-B>\"\<CR>", 'tx') + " call assert_equal('"set t_EC', @:) + " call feedkeys(":set <t_E\<Tab>\<C-B>\"\<CR>", 'tx') + " call assert_equal('"set <t_EC>', @:) + + " :packadd directory name fuzzy completion - NOT supported + + " shell command name fuzzy completion - NOT supported + + " :sign suboptions fuzzy completion + set wildoptions& + call feedkeys(":sign ufe\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"sign ufe', @:) + set wildoptions=fuzzy + call feedkeys(":sign ufe\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"sign undefine', @:) + + " :syntax suboptions fuzzy completion + set wildoptions& + call feedkeys(":syntax kwd\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"syntax kwd', @:) + set wildoptions=fuzzy + call feedkeys(":syntax kwd\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"syntax keyword', @:) + + " syntax group name fuzzy completion + set wildoptions& + call feedkeys(":syntax list mpar\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"syntax list mpar', @:) + set wildoptions=fuzzy + call feedkeys(":syntax list mpar\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"syntax list MatchParen', @:) + + " :syntime suboptions fuzzy completion + if has('profile') + set wildoptions& + call feedkeys(":syntime clr\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"syntime clr', @:) + set wildoptions=fuzzy + call feedkeys(":syntime clr\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"syntime clear', @:) + endif + + " tag name fuzzy completion - NOT supported + + " tag name and file fuzzy completion - NOT supported + + " user names fuzzy completion - how to test this functionality? + + " user defined variable name fuzzy completion + let g:SomeVariable=10 + set wildoptions& + call feedkeys(":let SVar\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"let SVar', @:) + set wildoptions=fuzzy + call feedkeys(":let SVar\<Tab>\<C-B>\"\<CR>", 'tx') + call assert_equal('"let SomeVariable', @:) + + set wildoptions& + %bw! +endfunc + " Test for :breakadd argument completion func Test_cmdline_complete_breakadd() call feedkeys(":breakadd \<C-A>\<C-B>\"\<CR>", 'tx') |