patch 9.1.0463: no fuzzy-matching support for insert-completionv9.1.0463

Problem:  no fuzzy-matching support for insert-completion
Solution: enable insert-mode completion with fuzzy-matching
          using :set completopt+=fuzzy (glepnir).

closes: #14878

Signed-off-by: glepnir <glephunter@gmail.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>

8 files changed, 191 insertions, 31 deletions

diff --git a/runtime/doc/options.txt b/runtime/doc/options.txt
index cae3e5433a..e28244f111 100644
--- a/runtime/doc/options.txt
+++ b/runtime/doc/options.txt
@@ -1,4 +1,4 @@
-*options.txt*	For Vim version 9.1.  Last change: 2024 Jun 01
+*options.txt*	For Vim version 9.1.  Last change: 2024 Jun 03
 
 
 		  VIM REFERENCE MANUAL	  by Bram Moolenaar
@@ -2143,6 +2143,11 @@ A jump table for the options with a short description can be found at |Q_op|.
 		    select one from the menu. Only works in combination with
 		    "menu" or "menuone".
 
+	   fuzzy    Enable |fuzzy-matching| for completion candidates. This
+		    allows for more flexible and intuitive matching, where
+		    characters can be skipped and matches can be found even
+		    if the exact sequence is not typed.
+
 					*'completepopup'* *'cpp'*
 'completepopup' 'cpp'	string (default empty)
 			global
diff --git a/runtime/doc/pattern.txt b/runtime/doc/pattern.txt
index f16e7d2d6b..183806a968 100644
--- a/runtime/doc/pattern.txt
+++ b/runtime/doc/pattern.txt
@@ -1,4 +1,4 @@
-*pattern.txt*   For Vim version 9.1.  Last change: 2024 Apr 26
+*pattern.txt*   For Vim version 9.1.  Last change: 2024 Jun 03
 
 
 		  VIM REFERENCE MANUAL    by Bram Moolenaar
@@ -1513,5 +1513,7 @@ the matching positions and the fuzzy match scores.
 
 The "f" flag of `:vimgrep` enables fuzzy matching.
 
+To enable fuzzy matching for |ins-completion|, add the "fuzzy" value to the
+'completeopt' option.
 
  vim:tw=78:ts=8:noet:ft=help:norl:
diff --git a/runtime/doc/version9.txt b/runtime/doc/version9.txt
index 1c5a29f200..3473d796fe 100644
--- a/runtime/doc/version9.txt
+++ b/runtime/doc/version9.txt
@@ -1,4 +1,4 @@
-*version9.txt*  For Vim version 9.1.  Last change: 2024 May 17
+*version9.txt*  For Vim version 9.1.  Last change: 2024 Jun 03
 
 
 		  VIM REFERENCE MANUAL    by Bram Moolenaar
@@ -31711,12 +31711,12 @@ in |vim9-class|.  The following features are supported:
 
 Support for creating a type alias for an existing type is added.
 
-Virtual text
+Virtual text ~
 ------------
 Support for adding |virtual-text| to a buffer is added.  This is useful for
 language server features (e.g. inlay hints)
 
-Smooth Scroll
+Smooth Scroll ~
 -------------
 Support for scrolling text using screen lines instead of file lines is added.
 Refer to the 'smoothscroll' option.
@@ -31726,7 +31726,8 @@ The EditorConfig (|editorconfig-install|) and the JSON formatting
 
 OpenVMS x86_64 platform port: http://www.polarhome.com/vim/
 
-Other improvements				*new-other-9.1*
+						*new-other-9.1*
+Other improvements ~
 ------------------
 - Support for undercurl (|t_Ce|), double underline (|t_Us|), dotted underline
   (|t_ds|) and dashed underline (|t_Ds|) termcap entries and
@@ -31783,7 +31784,8 @@ Other improvements				*new-other-9.1*
 - xxd: reversing a bit dump (xxd -r).
 - xxd: customize the variable name used in the C include output (xxd -n).
 
-Changed						*changed-9.1*
+							*changed-9.1*
+Changed ~
 -------
 - The features |++builtin_terms|, |+cmdline_info|, |+cmdwin|, |+file_in_path|,
   |+float|, |+path_extra|, |+textobjects|, |+wildignore| and |+wildmenu| are
@@ -31815,7 +31817,8 @@ Changed						*changed-9.1*
 - Migrate to autoconf 2.71.
 - Start using C99 feature (declare variable in for loops).
 
-Added						*added-9.1*
+						*added-9.1*
+Added ~
 -----
 
 Various syntax, indent and other plugins were added.
@@ -41541,30 +41544,31 @@ VERSION 9.2				*version-9.2* *version9.2* *vim-9.2*
 This section is about improvements made between version 9.1 and 9.2
 and is a work in progress.
 
-Support for Wayland UI.
-
-Support for the XDG Desktop Specification |xdg-base-dir|
-
-Vim9 script
+Vim9 script ~
 -----------
 Add support for internal builtin functions with vim9 objects, see
 |builtin-object-methods|
 
 Enum support for Vim9 script |:enum|
 
-Other improvements				*new-other-9.2*
+							*new-other-9.2*
+Other new features ~
 ------------------
 The comment plugin |comment-install| is included.
 
-Changed						*changed-9.2*
--------
+Support for Wayland UI.
 
+Support for the XDG Desktop Specification |xdg-base-dir|
+
+							*changed-9.2*
+Changed~
+-------
 - use 'smoothscroll' logic for CTRL-F and CTRL-B for pagewise scrolling
 - use 'smoothscroll' logic for CTRL-D and CTRL-U for half-pagewise scrolling
 
-Added						*added-9.2*
+							*added-9.2*
+Added ~
 -----
-
 Various syntax, indent and other plugins were added.
 
 Functions: ~
@@ -41598,6 +41602,7 @@ Options: ~
 
 'winfixbuf'		Keep buffer focused in a window
 't_xo'			Terminal uses XON/XOFF handshaking (e.g. vt420)
+'t_CF'			Support for alternate font highlighting terminal code
 
 ==============================================================================
 INCOMPATIBLE CHANGES				*incompatible-9.2*
@@ -41606,22 +41611,22 @@ Improved/Different MS-Windows mapping support
 |w32-experimental-keycode-trans-strategy|
 
 ==============================================================================
-IMPROVEMENTS					*improvements-9.2*
+IMPROVEMENTS						*improvements-9.2*
 
 Support for command-line completion of 'keymap' option values.
 
 Support for compiling all the methods in a Vim9 class using |:defcompile|.
 
-Support for alternate font highlighting using |t_CF| terminal code.
-
 Support for Super key mappings in GTK using <D-Key>.
 
 Improved visual highlighting.
 
 Python3 support in OpenVMS.
 
+Support |fuzzy-matching| during |ins-completion| with "fuzzy" item for 'completeopt'
+
 ==============================================================================
-COMPILE TIME CHANGES				*compile-changes-9.2*
+COMPILE TIME CHANGES					*compile-changes-9.2*
 
 Support for building with Ruby 3.3.
 
diff --git a/src/insexpand.c b/src/insexpand.c
index 897c3b5870..c6bf681677 100644
--- a/src/insexpand.c
+++ b/src/insexpand.c
@@ -113,6 +113,7 @@ struct compl_S
 				// cp_flags has CP_FREE_FNAME
     int		cp_flags;	// CP_ values
     int		cp_number;	// sequence number
+    int		cp_score;	// fuzzy match score
 };
 
 // values for cp_flags
@@ -153,6 +154,7 @@ static int	  compl_no_select = FALSE;	// FALSE: select & insert
 						// TRUE: noselect
 static int	  compl_longest = FALSE;	// FALSE: insert full match
 						// TRUE: insert longest prefix
+static int	  compl_fuzzy_match = FALSE;	// True: fuzzy match enabled
 
 // Selected one of the matches.  When FALSE the match was edited or using the
 // longest common string.
@@ -207,6 +209,8 @@ static int	  compl_cont_status = 0;
 static int	  compl_opt_refresh_always = FALSE;
 static int	  compl_opt_suppress_empty = FALSE;
 
+static int	  compl_selected_item = -1;
+
 static int ins_compl_add(char_u *str, int len, char_u *fname, char_u **cptext, typval_T *user_data, int cdir, int flags, int adup);
 static void ins_compl_longest_match(compl_T *match);
 static void ins_compl_del_pum(void);
@@ -1059,12 +1063,15 @@ completeopt_was_set(void)
     compl_no_insert = FALSE;
     compl_no_select = FALSE;
     compl_longest = FALSE;
+    compl_fuzzy_match = FALSE;
     if (strstr((char *)p_cot, "noselect") != NULL)
 	compl_no_select = TRUE;
     if (strstr((char *)p_cot, "noinsert") != NULL)
 	compl_no_insert = TRUE;
     if (strstr((char *)p_cot, "longest") != NULL)
 	compl_longest = TRUE;
+    if (strstr((char *)p_cot, "fuzzy") != NULL)
+	compl_fuzzy_match = TRUE;
 }
 
 
@@ -1213,6 +1220,17 @@ trigger_complete_changed_event(int cur)
 #endif
 
 /*
+ * pumitem qsort compare func
+ */
+    static int
+ins_compl_fuzzy_sort(const void *a, const void *b)
+{
+    const int sa = (*(pumitem_T *)a).pum_score;
+    const int sb = (*(pumitem_T *)b).pum_score;
+    return sa == sb ? 0 : sa < sb ? 1 : -1;
+}
+
+/*
  * Build a popup menu to show the completion matches.
  * Returns the popup menu entry that should be selected. Returns -1 if nothing
  * should be selected.
@@ -1227,6 +1245,7 @@ ins_compl_build_pum(void)
     int		i;
     int		cur = -1;
     int		lead_len = 0;
+    int		max_fuzzy_score = 0;
 
     // Need to build the popup menu list.
     compl_match_arraysize = 0;
@@ -1236,9 +1255,15 @@ ins_compl_build_pum(void)
 
     do
     {
+	// when completeopt include fuzzy option and leader is not null or empty
+	// set the cp_score for after compare.
+	if (compl_fuzzy_match && compl_leader != NULL && lead_len > 0)
+	    compl->cp_score = fuzzy_match_str(compl->cp_str, compl_leader);
+
 	if (!match_at_original_text(compl)
 		&& (compl_leader == NULL
-		    || ins_compl_equal(compl, compl_leader, lead_len)))
+		    || ins_compl_equal(compl, compl_leader, lead_len)
+		    || (compl_fuzzy_match && compl->cp_score > 0)))
 	    ++compl_match_arraysize;
 	compl = compl->cp_next;
     } while (compl != NULL && !is_first_match(compl));
@@ -1267,9 +1292,10 @@ ins_compl_build_pum(void)
     {
 	if (!match_at_original_text(compl)
 		&& (compl_leader == NULL
-		    || ins_compl_equal(compl, compl_leader, lead_len)))
+		    || ins_compl_equal(compl, compl_leader, lead_len)
+		    || (compl_fuzzy_match && compl->cp_score > 0)))
 	{
-	    if (!shown_match_ok)
+	    if (!shown_match_ok && !compl_fuzzy_match)
 	    {
 		if (compl == compl_shown_match || did_find_shown_match)
 		{
@@ -1285,6 +1311,24 @@ ins_compl_build_pum(void)
 		    shown_compl = compl;
 		cur = i;
 	    }
+	    else if (compl_fuzzy_match)
+	    {
+		if (compl->cp_score > max_fuzzy_score)
+		{
+		    did_find_shown_match = TRUE;
+		    max_fuzzy_score = compl->cp_score;
+		    compl_shown_match = compl;
+		    shown_match_ok = TRUE;
+		}
+
+		if (!compl_no_select
+			&& (max_fuzzy_score > 0
+				|| (compl_leader == NULL || lead_len == 0)))
+		{
+		    shown_match_ok = TRUE;
+		    cur = 0;
+		}
+	    }
 
 	    if (compl->cp_text[CPT_ABBR] != NULL)
 		compl_match_array[i].pum_text =
@@ -1293,6 +1337,7 @@ ins_compl_build_pum(void)
 		compl_match_array[i].pum_text = compl->cp_str;
 	    compl_match_array[i].pum_kind = compl->cp_text[CPT_KIND];
 	    compl_match_array[i].pum_info = compl->cp_text[CPT_INFO];
+	    compl_match_array[i].pum_score = compl->cp_score;
 	    if (compl->cp_text[CPT_MENU] != NULL)
 		compl_match_array[i++].pum_extra =
 		    compl->cp_text[CPT_MENU];
@@ -1300,7 +1345,7 @@ ins_compl_build_pum(void)
 		compl_match_array[i++].pum_extra = compl->cp_fname;
 	}
 
-	if (compl == compl_shown_match)
+	if (compl == compl_shown_match && !compl_fuzzy_match)
 	{
 	    did_find_shown_match = TRUE;
 
@@ -1320,6 +1365,10 @@ ins_compl_build_pum(void)
 	compl = compl->cp_next;
     } while (compl != NULL && !is_first_match(compl));
 
+    if (compl_fuzzy_match && compl_leader != NULL && lead_len > 0)
+	// sort by the largest score of fuzzy match
+	qsort(compl_match_array, (size_t)compl_match_arraysize, sizeof(pumitem_T), ins_compl_fuzzy_sort);
+
     if (!shown_match_ok)    // no displayed match at all
 	cur = -1;
 
@@ -1376,6 +1425,7 @@ ins_compl_show_pum(void)
     // Use the cursor to get all wrapping and other settings right.
     col = curwin->w_cursor.col;
     curwin->w_cursor.col = compl_col;
+    compl_selected_item = cur;
     pum_display(compl_match_array, compl_match_arraysize, cur);
     curwin->w_cursor.col = col;
 
@@ -4025,6 +4075,40 @@ ins_compl_show_filename(void)
     redraw_cmdline = FALSE;	    // don't overwrite!
 }
 
+    static compl_T *
+find_comp_when_fuzzy(void)
+{
+    int		score;
+    char_u*	str;
+    int		target_idx = -1;
+    int		is_forward = compl_shows_dir_forward();
+    int		is_backward = compl_shows_dir_backward();
+    compl_T	*comp = NULL;
+
+    if (compl_match_array == NULL ||
+	    (is_forward && compl_selected_item == compl_match_arraysize - 1)
+	    || (is_backward && compl_selected_item == 0))
+	return compl_first_match;
+
+    if (is_forward)
+	target_idx = compl_selected_item + 1;
+    else if (is_backward)
+      target_idx = compl_selected_item == -1 ? compl_match_arraysize - 1
+					    : compl_selected_item - 1;
+
+    score = compl_match_array[target_idx].pum_score;
+    str = compl_match_array[target_idx].pum_text;
+
+    comp = compl_first_match;
+    do {
+      if (comp->cp_score == score && (str == comp->cp_str || str == comp->cp_text[CPT_ABBR]))
+	  return comp;
+      comp = comp->cp_next;
+    } while (comp != NULL && !is_first_match(comp));
+
+    return NULL;
+}
+
 /*
  * Find the next set of matches for completion. Repeat the completion "todo"
  * times.  The number of matches found is returned in 'num_matches'.
@@ -4052,7 +4136,8 @@ find_next_completion_match(
     {
 	if (compl_shows_dir_forward() && compl_shown_match->cp_next != NULL)
 	{
-	    compl_shown_match = compl_shown_match->cp_next;
+	    compl_shown_match = !compl_fuzzy_match ? compl_shown_match->cp_next
+						: find_comp_when_fuzzy();
 	    found_end = (compl_first_match != NULL
 		    && (is_first_match(compl_shown_match->cp_next)
 			|| is_first_match(compl_shown_match)));
@@ -4061,7 +4146,8 @@ find_next_completion_match(
 		&& compl_shown_match->cp_prev != NULL)
 	{
 	    found_end = is_first_match(compl_shown_match);
-	    compl_shown_match = compl_shown_match->cp_prev;
+	    compl_shown_match = !compl_fuzzy_match ? compl_shown_match->cp_prev
+						   : find_comp_when_fuzzy();
 	    found_end |= is_first_match(compl_shown_match);
 	}
 	else
@@ -4111,7 +4197,8 @@ find_next_completion_match(
 	if (!match_at_original_text(compl_shown_match)
 		&& compl_leader != NULL
 		&& !ins_compl_equal(compl_shown_match,
-		    compl_leader, (int)STRLEN(compl_leader)))
+		    compl_leader, (int)STRLEN(compl_leader))
+		&& !(compl_fuzzy_match && compl_shown_match->cp_score > 0))
 	    ++todo;
 	else
 	    // Remember a matching item.
@@ -4167,7 +4254,9 @@ ins_compl_next(
     if (compl_shown_match == NULL)
 	return -1;
 
-    if (compl_leader != NULL && !match_at_original_text(compl_shown_match))
+    if (compl_leader != NULL
+	    && !match_at_original_text(compl_shown_match)
+	    && !compl_fuzzy_match)
 	// Update "compl_shown_match" to the actually shown match
 	ins_compl_update_shown_match();
 
diff --git a/src/optionstr.c b/src/optionstr.c
index 45f126ff6b..6b59b68085 100644
--- a/src/optionstr.c
+++ b/src/optionstr.c
@@ -118,7 +118,7 @@ static char *(p_fdm_values[]) = {"manual", "expr", "marker", "indent", "syntax",
 				NULL};
 static char *(p_fcl_values[]) = {"all", NULL};
 #endif
-static char *(p_cot_values[]) = {"menu", "menuone", "longest", "preview", "popup", "popuphidden", "noinsert", "noselect", NULL};
+static char *(p_cot_values[]) = {"menu", "menuone", "longest", "preview", "popup", "popuphidden", "noinsert", "noselect", "fuzzy", NULL};
 #ifdef BACKSLASH_IN_FILENAME
 static char *(p_csl_values[]) = {"slash", "backslash", NULL};
 #endif
diff --git a/src/structs.h b/src/structs.h
index 804581bf1b..bd6977ef80 100644
--- a/src/structs.h
+++ b/src/structs.h
@@ -4468,6 +4468,7 @@ typedef struct
     char_u	*pum_kind;	// extra kind text (may be truncated)
     char_u	*pum_extra;	// extra menu text (may be truncated)
     char_u	*pum_info;	// extra info
+    int		 pum_score;	// fuzzy match score
 } pumitem_T;
 
 /*
diff --git a/src/testdir/test_ins_complete.vim b/src/testdir/test_ins_complete.vim
index d1b96099b1..1cd7d347c0 100644
--- a/src/testdir/test_ins_complete.vim
+++ b/src/testdir/test_ins_complete.vim
@@ -2451,4 +2451,60 @@ func Test_completefunc_first_call_complete_add()
   bwipe!
 endfunc
 
+func Test_complete_fuzzy_match()
+  func OnPumChange()
+    let g:item = get(v:event, 'completed_item', {})
+    let g:word = get(g:item, 'word', v:null)
+  endfunction
+
+  augroup AAAAA_Group
+    au!
+    autocmd CompleteChanged * :call OnPumChange()
+  augroup END
+
+  func Omni_test(findstart, base)
+    if a:findstart
+      return col(".")
+    endif
+    return [#{word: "foo"}, #{word: "foobar"}, #{word: "fooBaz"}, #{word: "foobala"}]
+  endfunc
+  new
+  set omnifunc=Omni_test
+  set completeopt+=noinsert,fuzzy
+  call feedkeys("Gi\<C-x>\<C-o>", 'tx')
+  call assert_equal('foo', g:word)
+  call feedkeys("S\<C-x>\<C-o>fb", 'tx')
+  call assert_equal('fooBaz', g:word)
+  call feedkeys("S\<C-x>\<C-o>fa", 'tx')
+  call assert_equal('foobar', g:word)
+  " select next
+  call feedkeys("S\<C-x>\<C-o>fb\<C-n>", 'tx')
+  call assert_equal('foobar', g:word)
+  " can circly select next
+  call feedkeys("S\<C-x>\<C-o>fb\<C-n>\<C-n>\<C-n>", 'tx')
+  call assert_equal(v:null, g:word)
+  " select prev
+  call feedkeys("S\<C-x>\<C-o>fb\<C-p>", 'tx')
+  call assert_equal(v:null, g:word)
+  " can circly select prev
+  call feedkeys("S\<C-x>\<C-o>fb\<C-p>\<C-p>\<C-p>\<C-p>", 'tx')
+  call assert_equal('fooBaz', g:word)
+
+  " respect noselect
+  set completeopt+=noselect
+  call feedkeys("S\<C-x>\<C-o>fb", 'tx')
+  call assert_equal(v:null, g:word)
+  call feedkeys("S\<C-x>\<C-o>fb\<C-n>", 'tx')
+  call assert_equal('fooBaz', g:word)
+
+  " clean up
+  set omnifunc=
+  bw!
+  set complete& completeopt&
+  autocmd! AAAAA_Group
+  augroup! AAAAA_Group
+  delfunc OnPumChange
+  delfunc Omni_test
+endfunc
+
 " vim: shiftwidth=2 sts=2 expandtab nofoldenable
diff --git a/src/version.c b/src/version.c
index 55282ab82b..ea1071e6cf 100644
--- a/src/version.c
+++ b/src/version.c
@@ -705,6 +705,8 @@ static char *(features[]) =
 static int included_patches[] =
 {   /* Add new patch number below this line */
 /**/
+    463,
+/**/
     462,
 /**/
     461,