patch 9.1.0598: fuzzy completion does not work with default completionv9.1.0598

Problem:  fuzzy completion does not work with default completion
Solution: Make it work (glepnir)

closes: #15193

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

7 files changed, 323 insertions, 20 deletions

diff --git a/src/insexpand.c b/src/insexpand.c
index 21b53d1e3e..fa4ac7dd3f 100644
--- a/src/insexpand.c
+++ b/src/insexpand.c
@@ -203,6 +203,8 @@ static int	  compl_opt_suppress_empty = FALSE;
 
 static int	  compl_selected_item = -1;
 
+static int	  *compl_fuzzy_scores;
+
 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);
@@ -3322,7 +3324,8 @@ typedef struct
 process_next_cpt_value(
 	ins_compl_next_state_T *st,
 	int		*compl_type_arg,
-	pos_T		*start_match_pos)
+	pos_T		*start_match_pos,
+	int		in_fuzzy)
 {
     int	    compl_type = -1;
     int	    status = INS_COMPL_CPT_OK;
@@ -3338,7 +3341,7 @@ process_next_cpt_value(
 	st->first_match_pos = *start_match_pos;
 	// Move the cursor back one character so that ^N can match the
 	// word immediately after the cursor.
-	if (ctrl_x_mode_normal() && dec(&st->first_match_pos) < 0)
+	if (ctrl_x_mode_normal() && (!in_fuzzy && dec(&st->first_match_pos) < 0))
 	{
 	    // Move the cursor to after the last character in the
 	    // buffer, so that word at start of buffer is found
@@ -3506,6 +3509,18 @@ get_next_tag_completion(void)
 }
 
 /*
+ * Compare function for qsort
+ */
+static int compare_scores(const void *a, const void *b)
+{
+    int idx_a = *(const int *)a;
+    int idx_b = *(const int *)b;
+    int score_a = compl_fuzzy_scores[idx_a];
+    int score_b = compl_fuzzy_scores[idx_b];
+    return (score_a > score_b) ? -1 : (score_a < score_b) ? 1 : 0;
+}
+
+/*
  * Get the next set of filename matching "compl_pattern".
  */
     static void
@@ -3513,6 +3528,21 @@ get_next_filename_completion(void)
 {
     char_u	**matches;
     int		num_matches;
+    char_u	*ptr;
+    garray_T	fuzzy_indices;
+    int		i;
+    int		score;
+    char_u	*leader = ins_compl_leader();
+    int		leader_len = STRLEN(leader);
+    int		in_fuzzy = ((get_cot_flags() & COT_FUZZY) != 0 && leader_len > 0);
+    char_u	**sorted_matches;
+    int		*fuzzy_indices_data;
+
+    if (in_fuzzy)
+    {
+	vim_free(compl_pattern);
+	compl_pattern = vim_strsave((char_u *)"*");
+    }
 
     if (expand_wildcards(1, &compl_pattern, &num_matches, &matches,
 		EW_FILE|EW_DIR|EW_ADDSLASH|EW_SILENT) != OK)
@@ -3523,12 +3553,9 @@ get_next_filename_completion(void)
 #ifdef BACKSLASH_IN_FILENAME
     if (curbuf->b_p_csl[0] != NUL)
     {
-	int	    i;
-
 	for (i = 0; i < num_matches; ++i)
 	{
-	    char_u	*ptr = matches[i];
-
+	    ptr = matches[i];
 	    while (*ptr != NUL)
 	    {
 		if (curbuf->b_p_csl[0] == 's' && *ptr == '\\')
@@ -3540,6 +3567,41 @@ get_next_filename_completion(void)
 	}
     }
 #endif
+
+    if (in_fuzzy)
+    {
+	ga_init2(&fuzzy_indices, sizeof(int), 10);
+	compl_fuzzy_scores = (int *)alloc(sizeof(int) * num_matches);
+
+	for (i = 0; i < num_matches; i++)
+	{
+	    ptr = matches[i];
+	    score = fuzzy_match_str(ptr, leader);
+	    if (score > 0)
+	    {
+		if (ga_grow(&fuzzy_indices, 1) == OK)
+		{
+		    ((int *)fuzzy_indices.ga_data)[fuzzy_indices.ga_len] = i;
+		    compl_fuzzy_scores[i] = score;
+		    fuzzy_indices.ga_len++;
+		}
+	    }
+	}
+
+	fuzzy_indices_data = (int *)fuzzy_indices.ga_data;
+	qsort(fuzzy_indices_data, fuzzy_indices.ga_len, sizeof(int), compare_scores);
+
+	sorted_matches = (char_u **)alloc(sizeof(char_u *) * fuzzy_indices.ga_len);
+	for (i = 0; i < fuzzy_indices.ga_len; ++i)
+	    sorted_matches[i] = vim_strsave(matches[fuzzy_indices_data[i]]);
+
+	FreeWild(num_matches, matches);
+	matches = sorted_matches;
+	num_matches = fuzzy_indices.ga_len;
+	vim_free(compl_fuzzy_scores);
+	ga_clear(&fuzzy_indices);
+    }
+
     ins_compl_add_matches(num_matches, matches, p_fic || p_wic);
 }
 
@@ -3687,8 +3749,10 @@ get_next_default_completion(ins_compl_next_state_T *st, pos_T *start_pos)
     int		save_p_scs;
     int		save_p_ws;
     int		looped_around = FALSE;
-    char_u	*ptr;
-    int		len;
+    char_u	*ptr = NULL;
+    int		len = 0;
+    int		in_fuzzy = (get_cot_flags() & COT_FUZZY) != 0 && compl_length > 0;
+    char_u	*leader = ins_compl_leader();
 
     // If 'infercase' is set, don't use 'smartcase' here
     save_p_scs = p_scs;
@@ -3702,7 +3766,7 @@ get_next_default_completion(ins_compl_next_state_T *st, pos_T *start_pos)
     save_p_ws = p_ws;
     if (st->ins_buf != curbuf)
 	p_ws = FALSE;
-    else if (*st->e_cpt == '.')
+    else if (*st->e_cpt == '.' && !in_fuzzy)
 	p_ws = TRUE;
     looped_around = FALSE;
     for (;;)
@@ -3713,9 +3777,13 @@ get_next_default_completion(ins_compl_next_state_T *st, pos_T *start_pos)
 
 	// ctrl_x_mode_line_or_eval() || word-wise search that
 	// has added a word that was at the beginning of the line
-	if (ctrl_x_mode_line_or_eval() || (compl_cont_status & CONT_SOL))
+	if ((ctrl_x_mode_whole_line() && !in_fuzzy) || ctrl_x_mode_eval() || (compl_cont_status & CONT_SOL))
 	    found_new_match = search_for_exact_line(st->ins_buf,
 			    st->cur_match_pos, compl_direction, compl_pattern);
+	else if (in_fuzzy)
+	     found_new_match = search_for_fuzzy_match(st->ins_buf,
+			    st->cur_match_pos, leader, compl_direction,
+			    start_pos, &len, &ptr, ctrl_x_mode_whole_line());
 	else
 	    found_new_match = searchit(NULL, st->ins_buf, st->cur_match_pos,
 				NULL, compl_direction, compl_pattern, compl_patternlen,
@@ -3764,8 +3832,9 @@ get_next_default_completion(ins_compl_next_state_T *st, pos_T *start_pos)
 		&& start_pos->col  == st->cur_match_pos->col)
 	    continue;
 
-	ptr = ins_compl_get_next_word_or_line(st->ins_buf, st->cur_match_pos,
-							   &len, &cont_s_ipos);
+	if (!in_fuzzy)
+	    ptr = ins_compl_get_next_word_or_line(st->ins_buf, st->cur_match_pos,
+							       &len, &cont_s_ipos);
 	if (ptr == NULL)
 	    continue;
 
@@ -3864,6 +3933,7 @@ ins_compl_get_exp(pos_T *ini)
     int		i;
     int		found_new_match;
     int		type = ctrl_x_mode;
+    int		in_fuzzy = (get_cot_flags() & COT_FUZZY) != 0;
 
     if (!compl_started)
     {
@@ -3889,8 +3959,11 @@ ins_compl_get_exp(pos_T *ini)
 	st.ins_buf = curbuf;  // In case the buffer was wiped out.
 
     compl_old_match = compl_curr_match;	// remember the last current match
-    st.cur_match_pos = (compl_dir_forward())
-				? &st.last_match_pos : &st.first_match_pos;
+    if (in_fuzzy)
+	st.cur_match_pos = (compl_dir_forward())
+				    ? &st.last_match_pos : &st.first_match_pos;
+    else
+	st.cur_match_pos = &st.last_match_pos;
 
     // For ^N/^P loop over all the flags/windows/buffers in 'complete'.
     for (;;)
@@ -3904,7 +3977,7 @@ ins_compl_get_exp(pos_T *ini)
 	if ((ctrl_x_mode_normal() || ctrl_x_mode_line_or_eval())
 					&& (!compl_started || st.found_all))
 	{
-	    int status = process_next_cpt_value(&st, &type, ini);
+	    int status = process_next_cpt_value(&st, &type, ini, in_fuzzy);
 
 	    if (status == INS_COMPL_CPT_END)
 		break;
diff --git a/src/proto/search.pro b/src/proto/search.pro
index 08526c80f2..866599409c 100644
--- a/src/proto/search.pro
+++ b/src/proto/search.pro
@@ -41,6 +41,7 @@ void f_matchfuzzy(typval_T *argvars, typval_T *rettv);
 void f_matchfuzzypos(typval_T *argvars, typval_T *rettv);
 int fuzzy_match_str(char_u *str, char_u *pat);
 garray_T *fuzzy_match_str_with_pos(char_u *str, char_u *pat);
+int search_for_fuzzy_match(buf_T *buf, pos_T *pos, char_u *pattern, int dir, pos_T *start_pos, int *len, char_u **ptr, int whole_line);
 void fuzmatch_str_free(fuzmatch_str_T *fuzmatch, int count);
 int fuzzymatches_to_strmatches(fuzmatch_str_T *fuzmatch, char_u ***matches, int count, int funcsort);
 /* vim: set ft=c : */
diff --git a/src/search.c b/src/search.c
index d1eb5007d2..f7aab7b5eb 100644
--- a/src/search.c
+++ b/src/search.c
@@ -53,6 +53,7 @@ static int fuzzy_match_str_compare(const void *s1, const void *s2);
 static void fuzzy_match_str_sort(fuzmatch_str_T *fm, int sz);
 static int fuzzy_match_func_compare(const void *s1, const void *s2);
 static void fuzzy_match_func_sort(fuzmatch_str_T *fm, int sz);
+static int fuzzy_match_str_in_line(char_u **ptr, char_u *pat, int *len, pos_T *current_pos);
 
 #define SEARCH_STAT_DEF_TIMEOUT 40L
 #define SEARCH_STAT_DEF_MAX_COUNT 99
@@ -5140,6 +5141,169 @@ fuzzy_match_str_with_pos(char_u *str UNUSED, char_u *pat UNUSED)
 }
 
 /*
+ * This function searches for a fuzzy match of the pattern `pat` within the
+ * line pointed to by `*ptr`. It splits the line into words, performs fuzzy
+ * matching on each word, and returns the length and position of the first
+ * matched word.
+ */
+    static int
+fuzzy_match_str_in_line(char_u **ptr, char_u *pat, int *len, pos_T *current_pos)
+{
+    char_u	*str = *ptr;
+    char_u	*strBegin = str;
+    char_u	*end = NULL;
+    char_u	*start = NULL;
+    int		found = FALSE;
+    int		result;
+    char	save_end;
+
+    if (str == NULL || pat == NULL)
+        return found;
+
+    while (*str != NUL)
+    {
+	// Skip non-word characters
+	start = find_word_start(str);
+	if (*start == NUL)
+	    break;
+	end = find_word_end(start);
+
+	// Extract the word from start to end
+	save_end = *end;
+	*end = NUL;
+
+	// Perform fuzzy match
+	result = fuzzy_match_str(start, pat);
+	*end = save_end;
+
+	if (result > 0)
+	{
+	    *len = (int)(end - start);
+	    current_pos->col += (int)(end - strBegin);
+	    found = TRUE;
+	    *ptr = start;
+	    break;
+	}
+
+	// Move to the end of the current word for the next iteration
+	str = end;
+	// Ensure we continue searching after the current word
+	while (*str != NUL && !vim_iswordp(str))
+	    MB_PTR_ADV(str);
+    }
+
+    return found;
+}
+
+/*
+ * Search for the next fuzzy match in the specified buffer.
+ * This function attempts to find the next occurrence of the given pattern
+ * in the buffer, starting from the current position. It handles line wrapping
+ * and direction of search.
+ *
+ * Return TRUE if a match is found, otherwise FALSE.
+ */
+    int
+search_for_fuzzy_match(
+    buf_T	*buf,
+    pos_T	*pos,
+    char_u	*pattern,
+    int		dir,
+    pos_T	*start_pos,
+    int		*len,
+    char_u	**ptr,
+    int		whole_line)
+{
+    pos_T	current_pos = *pos;
+    pos_T	circly_end;
+    int		found_new_match = FAIL;
+    int		looped_around = FALSE;
+
+    if (whole_line)
+	current_pos.lnum += dir;
+
+    do {
+	if (buf == curbuf)
+	    circly_end = *start_pos;
+	else
+	{
+	    circly_end.lnum = buf->b_ml.ml_line_count;
+	    circly_end.col = 0;
+	    circly_end.coladd = 0;
+	}
+
+	// Check if looped around and back to start position
+	if (looped_around && EQUAL_POS(current_pos, circly_end))
+	    break;
+
+	// Ensure current_pos is valid
+	if (current_pos.lnum >= 1 && current_pos.lnum <= buf->b_ml.ml_line_count)
+	{
+	    // Get the current line buffer
+	    *ptr = ml_get_buf(buf, current_pos.lnum, FALSE);
+	    // If ptr is end of line is reached, move to next line
+	    // or previous line based on direction
+	    if (**ptr != NUL)
+	    {
+		if (!whole_line)
+		{
+		    *ptr += current_pos.col;
+		    // Try to find a fuzzy match in the current line starting from current position
+		    found_new_match = fuzzy_match_str_in_line(ptr, pattern, len, &current_pos);
+		    if (found_new_match)
+		    {
+			*pos = current_pos;
+			break;
+		    }
+		}
+		else
+		{
+		    if (fuzzy_match_str(*ptr, pattern) > 0)
+		    {
+			found_new_match = TRUE;
+			*pos = current_pos;
+			*len = STRLEN(*ptr);
+			break;
+		    }
+		}
+	    }
+	}
+
+	// Move to the next line or previous line based on direction
+	if (dir == FORWARD)
+	{
+	    if (++current_pos.lnum > buf->b_ml.ml_line_count)
+	    {
+		if (p_ws)
+		{
+		    current_pos.lnum = 1;
+		    looped_around = TRUE;
+		}
+		else
+		    break;
+	    }
+	}
+	else
+	{
+	    if (--current_pos.lnum < 1)
+	    {
+		if (p_ws)
+		{
+		    current_pos.lnum = buf->b_ml.ml_line_count;
+		    looped_around = TRUE;
+		}
+		else
+		    break;
+
+	    }
+	}
+	current_pos.col = 0;
+    } while (TRUE);
+
+    return found_new_match;
+}
+
+/*
  * Free an array of fuzzy string matches "fuzmatch[count]".
  */
     void
diff --git a/src/testdir/dumps/Test_pum_highlights_10.dump b/src/testdir/dumps/Test_pum_highlights_10.dump
index 5db4e59e4d..790b028b9c 100644
--- a/src/testdir/dumps/Test_pum_highlights_10.dump
+++ b/src/testdir/dumps/Test_pum_highlights_10.dump
@@ -1,7 +1,7 @@
-| +0&#ffffff0|h|e|l@1|o| |h|e|l|i|o| |h|e|r|o| |h|e|r|o> @52
-|~+0#4040ff13&| @15| +0#0000001#ffd7ff255|h+0#0000e05&|e+0#0000001&|l@1|o| @9| +0#4040ff13#ffffff0@41
+| +0&#ffffff0|h|e|l@1|o| |h|e|l|i|o| |h|e|r|o| |h|e|l@1|o> @51
+|~+0#4040ff13&| @15| +0#0000001#ffd7ff255|h+0#0000e05&|e+0#0000001&|r|o| @10| +0#4040ff13#ffffff0@41
 |~| @15| +0#0000001#ffd7ff255|h+0#0000e05&|e+0#0000001&|l|i|o| @9| +0#4040ff13#ffffff0@41
-|~| @15| +0#0000001#e0e0e08|h+0#00e0e07&|e+0#0000001&|r|o| @10| +0#4040ff13#ffffff0@41
+|~| @15| +0#0000001#e0e0e08|h+0#00e0e07&|e+0#0000001&|l@1|o| @9| +0#4040ff13#ffffff0@41
 |~| @73
 |~| @73
 |~| @73
diff --git a/src/testdir/dumps/Test_pum_highlights_11.dump b/src/testdir/dumps/Test_pum_highlights_11.dump
index 720d839fae..ef75a89ed3 100644
--- a/src/testdir/dumps/Test_pum_highlights_11.dump
+++ b/src/testdir/dumps/Test_pum_highlights_11.dump
@@ -1,7 +1,7 @@
 | +0&#ffffff0|h|e|l@1|o| |h|e|l|i|o| |h|e|r|o| |h|e|l|i|o> @51
-|~+0#4040ff13&| @15| +0#0000001#ffd7ff255|h+0#0000e05&|e+0#0000001&|l@1|o| @9| +0#4040ff13#ffffff0@41
+|~+0#4040ff13&| @15| +0#0000001#ffd7ff255|h+0#0000e05&|e+0#0000001&|r|o| @10| +0#4040ff13#ffffff0@41
 |~| @15| +0#0000001#e0e0e08|h+0#00e0e07&|e+0#0000001&|l|i|o| @9| +0#4040ff13#ffffff0@41
-|~| @15| +0#0000001#ffd7ff255|h+0#0000e05&|e+0#0000001&|r|o| @10| +0#4040ff13#ffffff0@41
+|~| @15| +0#0000001#ffd7ff255|h+0#0000e05&|e+0#0000001&|l@1|o| @9| +0#4040ff13#ffffff0@41
 |~| @73
 |~| @73
 |~| @73
diff --git a/src/testdir/test_ins_complete.vim b/src/testdir/test_ins_complete.vim
index 48589ce188..e9f9c9e54b 100644
--- a/src/testdir/test_ins_complete.vim
+++ b/src/testdir/test_ins_complete.vim
@@ -2586,9 +2586,72 @@ func Test_complete_fuzzy_match()
   call feedkeys("A\<C-X>\<C-N>\<Esc>0", 'tx!')
   call assert_equal('hello help hero h', getline('.'))
 
+  set completeopt-=noinsert
+  call setline(1, ['xyz  yxz  x'])
+  call feedkeys("A\<C-X>\<C-N>\<Esc>0", 'tx!')
+  call assert_equal('xyz  yxz  xyz', getline('.'))
+  " can fuzzy get yxz when use Ctrl-N twice
+  call setline(1, ['xyz  yxz  x'])
+  call feedkeys("A\<C-X>\<C-N>\<C-N>\<Esc>0", 'tx!')
+  call assert_equal('xyz  yxz  yxz', getline('.'))
+
+  call setline(1, ['你好 你'])
+  call feedkeys("A\<C-X>\<C-N>\<Esc>0", 'tx!')
+  call assert_equal('你好 你好', getline('.'))
+  call setline(1, ['你的 我的 的'])
+  call feedkeys("A\<C-X>\<C-N>\<Esc>0", 'tx!')
+  call assert_equal('你的 我的 你的', getline('.'))
+  " can fuzzy get multiple-byte word when use Ctrl-N twice
+  call setline(1, ['你的 我的 的'])
+  call feedkeys("A\<C-X>\<C-N>\<C-N>\<Esc>0", 'tx!')
+  call assert_equal('你的 我的 我的', getline('.'))
+
+  " respect wrapscan
+  set nowrapscan
+  call setline(1, ["xyz", "yxz", ""])
+  call cursor(3, 1)
+  call feedkeys("Sy\<C-X>\<C-N>\<Esc>0", 'tx!')
+  call assert_equal('y', getline('.'))
+  set wrapscan
+  call feedkeys("Sy\<C-X>\<C-N>\<Esc>0", 'tx!')
+  call assert_equal('xyz', getline('.'))
+
+  " fuzzy on file
+  call writefile([''], 'fobar', 'D')
+  call writefile([''], 'foobar', 'D')
+  call setline(1, ['fob'])
+  call cursor(1, 1)
+  call feedkeys("A\<C-X>\<C-f>\<Esc>0", 'tx!')
+  call assert_equal('fobar', getline('.'))
+  call feedkeys("Sfob\<C-X>\<C-f>\<C-N>\<Esc>0", 'tx!')
+  call assert_equal('foobar', getline('.'))
+
+  " can get completion from other buffer
+  set completeopt=fuzzy,menu,menuone
+  vnew
+  call setline(1, ["completeness,", "compatibility", "Composite", "Omnipotent"])
+  wincmd p
+  call feedkeys("Somp\<C-N>\<Esc>0", 'tx!')
+  call assert_equal('completeness', getline('.'))
+  call feedkeys("Somp\<C-N>\<C-N>\<Esc>0", 'tx!')
+  call assert_equal('compatibility', getline('.'))
+  call feedkeys("Somp\<C-P>\<Esc>0", 'tx!')
+  call assert_equal('Omnipotent', getline('.'))
+  call feedkeys("Somp\<C-P>\<C-P>\<Esc>0", 'tx!')
+  call assert_equal('Composite', getline('.'))
+
+  " fuzzy on whole line completion
+  call setline(1, ["world is on fire", "no one can save me but you", 'user can execute', ''])
+  call cursor(4, 1)
+  call feedkeys("Swio\<C-X>\<C-L>\<Esc>0", 'tx!')
+  call assert_equal('world is on fire', getline('.'))
+  call feedkeys("Su\<C-X>\<C-L>\<C-P>\<Esc>0", 'tx!')
+  call assert_equal('no one can save me but you', getline('.'))
+
   " clean up
   set omnifunc=
   bw!
+  bw!
   set complete& completeopt&
   autocmd! AAAAA_Group
   augroup! AAAAA_Group
diff --git a/src/version.c b/src/version.c
index e22fe614fb..acb4badaef 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 */
 /**/
+    598,
+/**/
     597,
 /**/
     596,