vim-patch:9.1.0598: fuzzy completion does not work with default completion

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

closes: vim/vim#15193

https://github.com/vim/vim/commit/8159fb18a92e9a9f5e35201bd92bf651f4d5835c

Cherry-pick insexpand.c changes from patch 9.1.0608.

N/A patch:
vim-patch:9.1.0632: MS-Windows: Compiler Warnings

Co-authored-by: glepnir <glephunter@gmail.com>

4 files changed, 284 insertions, 13 deletions

diff --git a/src/nvim/insexpand.c b/src/nvim/insexpand.c
index 1be4f601bc..7a123898a5 100644
--- a/src/nvim/insexpand.c
+++ b/src/nvim/insexpand.c
@@ -284,6 +284,8 @@ static size_t spell_bad_len = 0;   // length of located bad word
 
 static int compl_selected_item = -1;
 
+static int *compl_fuzzy_scores;
+
 // "compl_match_array" points the currently displayed list of entries in the
 // popup menu.  It is NULL when there is no popup menu.
 static pumitem_T *compl_match_array = NULL;
@@ -3141,7 +3143,7 @@ enum {
 ///          the "st->e_cpt" option value and process the next matching source.
 ///          INS_COMPL_CPT_END if all the values in "st->e_cpt" are processed.
 static int process_next_cpt_value(ins_compl_next_state_T *st, int *compl_type_arg,
-                                  pos_T *start_match_pos)
+                                  pos_T *start_match_pos, bool in_fuzzy)
 {
   int compl_type = -1;
   int status = INS_COMPL_CPT_OK;
@@ -3157,7 +3159,7 @@ static int process_next_cpt_value(ins_compl_next_state_T *st, int *compl_type_ar
     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
       // correctly.
@@ -3297,11 +3299,30 @@ static void get_next_tag_completion(void)
   p_ic = save_p_ic;
 }
 
+/// 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 get_next_filename_completion(void)
 {
   char **matches;
   int num_matches;
+  char *leader = ins_compl_leader();
+  size_t leader_len = strlen(leader);
+  bool in_fuzzy = ((get_cot_flags() & kOptCotFlagFuzzy) != 0 && leader_len > 0);
+
+  if (in_fuzzy) {
+    API_CLEAR_STRING(compl_pattern);
+    compl_pattern = cbuf_to_string("*", 1);
+  }
+
   if (expand_wildcards(1, &compl_pattern.data, &num_matches, &matches,
                        EW_FILE|EW_DIR|EW_ADDSLASH|EW_SILENT) != OK) {
     return;
@@ -3324,6 +3345,40 @@ static void get_next_filename_completion(void)
     }
   }
 #endif
+
+  if (in_fuzzy) {
+    garray_T fuzzy_indices;
+    ga_init(&fuzzy_indices, sizeof(int), 10);
+    compl_fuzzy_scores = (int *)xmalloc(sizeof(int) * (size_t)num_matches);
+
+    for (int i = 0; i < num_matches; i++) {
+      char *ptr = matches[i];
+      int score = fuzzy_match_str(ptr, leader);
+      if (score > 0) {
+        GA_APPEND(int, &fuzzy_indices, i);
+        compl_fuzzy_scores[i] = score;
+      }
+    }
+
+    // prevent qsort from deref NULL pointer
+    if (fuzzy_indices.ga_len > 0) {
+      int *fuzzy_indices_data = (int *)fuzzy_indices.ga_data;
+      qsort(fuzzy_indices_data, (size_t)fuzzy_indices.ga_len, sizeof(int), compare_scores);
+
+      char **sorted_matches = (char **)xmalloc(sizeof(char *) * (size_t)fuzzy_indices.ga_len);
+      for (int i = 0; i < fuzzy_indices.ga_len; i++) {
+        sorted_matches[i] = xstrdup(matches[fuzzy_indices_data[i]]);
+      }
+
+      FreeWild(num_matches, matches);
+      matches = sorted_matches;
+      num_matches = fuzzy_indices.ga_len;
+    }
+
+    xfree(compl_fuzzy_scores);
+    ga_clear(&fuzzy_indices);
+  }
+
   ins_compl_add_matches(num_matches, matches, p_fic || p_wic);
 }
 
@@ -3447,6 +3502,11 @@ static char *ins_compl_get_next_word_or_line(buf_T *ins_buf, pos_T *cur_match_po
 /// @return  OK if a new next match is found, otherwise FAIL.
 static int get_next_default_completion(ins_compl_next_state_T *st, pos_T *start_pos)
 {
+  char *ptr = NULL;
+  int len = 0;
+  bool in_fuzzy = (get_cot_flags() & kOptCotFlagFuzzy) != 0 && compl_length > 0;
+  char *leader = ins_compl_leader();
+
   // If 'infercase' is set, don't use 'smartcase' here
   const int save_p_scs = p_scs;
   assert(st->ins_buf);
@@ -3461,7 +3521,7 @@ static int get_next_default_completion(ins_compl_next_state_T *st, pos_T *start_
   const int 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;
   }
   bool looped_around = false;
@@ -3472,9 +3532,14 @@ static int get_next_default_completion(ins_compl_next_state_T *st, pos_T *start_
     msg_silent++;  // Don't want messages for wrapscan.
     // 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.data);
+    } 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.data,
@@ -3521,13 +3586,16 @@ static int get_next_default_completion(ins_compl_next_state_T *st, pos_T *start_
         && start_pos->col == st->cur_match_pos->col) {
       continue;
     }
-    int len;
-    char *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
         || (ins_compl_has_preinsert() && strcmp(ptr, compl_pattern.data) == 0)) {
       continue;
     }
+
     if (ins_compl_add_infercase(ptr, len, p_ic,
                                 st->ins_buf == curbuf ? NULL : st->ins_buf->b_sfname,
                                 0, cont_s_ipos) != NOTDONE) {
@@ -3628,6 +3696,7 @@ static int ins_compl_get_exp(pos_T *ini)
   static bool st_cleared = false;
   int found_new_match;
   int type = ctrl_x_mode;
+  bool in_fuzzy = (get_cot_flags() & kOptCotFlagFuzzy) != 0;
 
   assert(curbuf != NULL);
 
@@ -3652,7 +3721,11 @@ static int ins_compl_get_exp(pos_T *ini)
   assert(st.ins_buf != NULL);
 
   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'
   while (true) {
@@ -3664,7 +3737,7 @@ static int ins_compl_get_exp(pos_T *ini)
     // entries from 'complete' that look in loaded buffers.
     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/nvim/search.c b/src/nvim/search.c
index 04f33b9445..30653cbe63 100644
--- a/src/nvim/search.c
+++ b/src/nvim/search.c
@@ -3620,6 +3620,141 @@ garray_T *fuzzy_match_str_with_pos(char *const str, const char *const pat)
   return match_positions;
 }
 
+/// 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 bool fuzzy_match_str_in_line(char **ptr, char *pat, int *len, pos_T *current_pos)
+{
+  char *str = *ptr;
+  char *strBegin = str;
+  char *end = NULL;
+  char *start = NULL;
+  bool found = false;
+
+  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
+    char save_end = *end;
+    *end = NUL;
+
+    // Perform fuzzy match
+    int 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.
+bool search_for_fuzzy_match(buf_T *buf, pos_T *pos, char *pattern, int dir, pos_T *start_pos,
+                            int *len, char **ptr, bool whole_line)
+{
+  pos_T current_pos = *pos;
+  pos_T circly_end;
+  bool found_new_match = false;
+  bool looped_around = false;
+
+  if (whole_line) {
+    current_pos.lnum += dir;
+  }
+
+  while (true) {
+    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 && equalpos(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);
+      // 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 = (int)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;
+  }
+
+  return found_new_match;
+}
+
 /// 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,
diff --git a/test/functional/ui/popupmenu_spec.lua b/test/functional/ui/popupmenu_spec.lua
index 728f8ed3d0..e41df13088 100644
--- a/test/functional/ui/popupmenu_spec.lua
+++ b/test/functional/ui/popupmenu_spec.lua
@@ -6938,9 +6938,9 @@ describe('builtin popupmenu', function()
         feed('S hello helio hero h<C-X><C-P>')
         screen:expect([[
            hello helio hero h^             |
-          {1:~                }{n: }{mn:h}{n:ello        }{1: }|
+          {1:~                }{n: }{mn:h}{n:ero         }{1: }|
           {1:~                }{n: }{mn:h}{n:elio        }{1: }|
-          {1:~                }{s: }{ms:h}{s:ero         }{1: }|
+          {1:~                }{s: }{ms:h}{s:ello        }{1: }|
           {1:~                               }|*15
           {2:-- }{5:match 1 of 3}                 |
         ]])
@@ -6948,9 +6948,9 @@ describe('builtin popupmenu', function()
         feed('<Esc>S hello helio hero h<C-X><C-P><C-P>')
         screen:expect([[
            hello helio hero h^             |
-          {1:~                }{n: }{mn:h}{n:ello        }{1: }|
-          {1:~                }{s: }{ms:h}{s:elio        }{1: }|
           {1:~                }{n: }{mn:h}{n:ero         }{1: }|
+          {1:~                }{s: }{ms:h}{s:elio        }{1: }|
+          {1:~                }{n: }{mn:h}{n:ello        }{1: }|
           {1:~                               }|*15
           {2:-- }{5:match 2 of 3}                 |
         ]])
diff --git a/test/old/testdir/test_ins_complete.vim b/test/old/testdir/test_ins_complete.vim
index a08d0bd252..9b123a65b6 100644
--- a/test/old/testdir/test_ins_complete.vim
+++ b/test/old/testdir/test_ins_complete.vim
@@ -2832,6 +2832,68 @@ 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('.'))
+
   " issue #15526
   set completeopt=fuzzy,menuone,menu,noselect
   call setline(1, ['Text', 'ToText', ''])
@@ -2884,6 +2946,7 @@ func Test_complete_fuzzy_match()
   " clean up
   set omnifunc=
   bw!
+  bw!
   set complete& completeopt&
   autocmd! AAAAA_Group
   augroup! AAAAA_Group