vim-patch:9.1.0476: Cannot see matched text in popup menu

Problem:  Cannot see matched text in popup menu
Solution: Introduce 2 new highlighting groups: PmenuMatch and
          PmenuMatchSel (glepnir)

closes: vim/vim#14694

https://github.com/vim/vim/commit/40c1c3317d92f8c2adadf744fab72e4458e2a9fa

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

7 files changed, 172 insertions, 11 deletions

diff --git a/src/nvim/highlight.h b/src/nvim/highlight.h
index 558727fc51..2ba6cf5371 100644
--- a/src/nvim/highlight.h
+++ b/src/nvim/highlight.h
@@ -54,6 +54,8 @@ EXTERN const char *hlf_names[] INIT( = {
   [HLF_SPL] = "SpellLocal",
   [HLF_PNI] = "Pmenu",
   [HLF_PSI] = "PmenuSel",
+  [HLF_PMNI] = "PmenuMatch",
+  [HLF_PMSI] = "PmenuMatchSel",
   [HLF_PNK] = "PmenuKind",
   [HLF_PSK] = "PmenuKindSel",
   [HLF_PNX] = "PmenuExtra",
diff --git a/src/nvim/highlight_defs.h b/src/nvim/highlight_defs.h
index 17e3db04da..e0cce81166 100644
--- a/src/nvim/highlight_defs.h
+++ b/src/nvim/highlight_defs.h
@@ -101,6 +101,8 @@ typedef enum {
   HLF_SPL,        ///< SpellLocal
   HLF_PNI,        ///< popup menu normal item
   HLF_PSI,        ///< popup menu selected item
+  HLF_PMNI,       ///< popup menu matched text in normal item
+  HLF_PMSI,       ///< popup menu matched text in selected item
   HLF_PNK,        ///< popup menu normal item "kind"
   HLF_PSK,        ///< popup menu selected item "kind"
   HLF_PNX,        ///< popup menu normal item "menu" (extra text)
diff --git a/src/nvim/highlight_group.c b/src/nvim/highlight_group.c
index aa98983b63..3c777e7c4d 100644
--- a/src/nvim/highlight_group.c
+++ b/src/nvim/highlight_group.c
@@ -169,6 +169,8 @@ static const char *highlight_init_both[] = {
   "default link PmenuExtraSel    PmenuSel",
   "default link PmenuKind        Pmenu",
   "default link PmenuKindSel     PmenuSel",
+  "default link PmenuMatch       Pmenu",
+  "default link PmenuMatchSel    PmenuSel",
   "default link PmenuSbar        Pmenu",
   "default link Substitute       Search",
   "default link StatusLineTerm   StatusLine",
diff --git a/src/nvim/insexpand.c b/src/nvim/insexpand.c
index 139637b8a1..9b6805404f 100644
--- a/src/nvim/insexpand.c
+++ b/src/nvim/insexpand.c
@@ -1388,6 +1388,12 @@ bool compl_match_curr_select(int selected)
 #define DICT_FIRST      (1)     ///< use just first element in "dict"
 #define DICT_EXACT      (2)     ///< "dict" is the exact name of a file
 
+/// Get current completion leader
+char *ins_compl_leader(void)
+{
+  return compl_leader;
+}
+
 /// Add any identifiers that match the given pattern "pat" in the list of
 /// dictionary files "dict_start" to the list of completions.
 ///
diff --git a/src/nvim/option_vars.h b/src/nvim/option_vars.h
index bd0fe699d9..404e58661c 100644
--- a/src/nvim/option_vars.h
+++ b/src/nvim/option_vars.h
@@ -55,13 +55,13 @@
 #define HIGHLIGHT_INIT \
   "8:SpecialKey,~:EndOfBuffer,z:TermCursor,Z:TermCursorNC,@:NonText,d:Directory,e:ErrorMsg," \
   "i:IncSearch,l:Search,y:CurSearch,m:MoreMsg,M:ModeMsg,n:LineNr,a:LineNrAbove,b:LineNrBelow," \
-  "N:CursorLineNr,G:CursorLineSign,O:CursorLineFold" \
-  "r:Question,s:StatusLine,S:StatusLineNC,c:VertSplit,t:Title,v:Visual,V:VisualNOS,w:WarningMsg," \
-  "W:WildMenu,f:Folded,F:FoldColumn,A:DiffAdd,C:DiffChange,D:DiffDelete,T:DiffText,>:SignColumn," \
-  "-:Conceal,B:SpellBad,P:SpellCap,R:SpellRare,L:SpellLocal,+:Pmenu,=:PmenuSel," \
-  "[:PmenuKind,]:PmenuKindSel,{:PmenuExtra,}:PmenuExtraSel,x:PmenuSbar,X:PmenuThumb," \
-  "*:TabLine,#:TabLineSel,_:TabLineFill,!:CursorColumn,.:CursorLine,o:ColorColumn," \
-  "q:QuickFixLine,g:MsgArea,0:Whitespace,I:NormalNC"
+  "N:CursorLineNr,G:CursorLineSign,O:CursorLineFold,r:Question,s:StatusLine,S:StatusLineNC," \
+  "c:VertSplit,t:Title,v:Visual,V:VisualNOS,w:WarningMsg,W:WildMenu,f:Folded,F:FoldColumn," \
+  "A:DiffAdd,C:DiffChange,D:DiffDelete,T:DiffText,>:SignColumn,-:Conceal,B:SpellBad,P:SpellCap," \
+  "R:SpellRare,L:SpellLocal,+:Pmenu,=:PmenuSel,k:PmenuMatch,<:PmenuMatchSel,[:PmenuKind," \
+  "]:PmenuKindSel,{:PmenuExtra,}:PmenuExtraSel,x:PmenuSbar,X:PmenuThumb,*:TabLine,#:TabLineSel," \
+  "_:TabLineFill,!:CursorColumn,.:CursorLine,o:ColorColumn,q:QuickFixLine,z:StatusLineTerm," \
+  "Z:StatusLineTermNC,g:MsgArea,0:Whitespace,I:NormalNC"
 
 // Default values for 'errorformat'.
 // The "%f|%l| %m" one is used for when the contents of the quickfix window is
diff --git a/src/nvim/popupmenu.c b/src/nvim/popupmenu.c
index 324254a188..a7fdd44ef0 100644
--- a/src/nvim/popupmenu.c
+++ b/src/nvim/popupmenu.c
@@ -25,6 +25,7 @@
 #include "nvim/ex_cmds_defs.h"
 #include "nvim/extmark.h"
 #include "nvim/extmark_defs.h"
+#include "nvim/garray.h"
 #include "nvim/getchar.h"
 #include "nvim/gettext_defs.h"
 #include "nvim/globals.h"
@@ -48,6 +49,7 @@
 #include "nvim/plines.h"
 #include "nvim/popupmenu.h"
 #include "nvim/pos_defs.h"
+#include "nvim/search.h"
 #include "nvim/state_defs.h"
 #include "nvim/strings.h"
 #include "nvim/types_defs.h"
@@ -435,6 +437,74 @@ void pum_display(pumitem_T *array, int size, int selected, bool array_changed, i
   pum_redraw();
 }
 
+/// Displays text on the popup menu with specific attributes.
+static void pum_puts_with_attr(int col, const char *text, int attr)
+{
+  char *leader = ins_compl_leader();
+
+  if ((win_hl_attr(curwin, HLF_PMSI) == win_hl_attr(curwin, HLF_PSI)
+       && win_hl_attr(curwin, HLF_PMNI) == win_hl_attr(curwin, HLF_PNI))) {
+    grid_line_puts(col, text, -1, attr);
+    return;
+  }
+
+  char *rt_leader = NULL;
+  if (leader != NULL && curwin->w_p_rl) {
+    rt_leader = reverse_text(leader);
+  }
+  char *match_leader = rt_leader != NULL ? rt_leader : leader;
+  size_t leader_len = match_leader ? strlen(match_leader) : 0;
+
+  const bool in_fuzzy = (get_cot_flags() & COT_FUZZY) != 0;
+
+  garray_T *ga = NULL;
+  if (match_leader != NULL && leader_len > 0 && in_fuzzy) {
+    ga = fuzzy_match_str_with_pos(text, match_leader);
+  }
+
+  // Render text with proper attributes
+  const char *ptr = text;
+  while (*ptr != NUL) {
+    int char_len = utfc_ptr2len(ptr);
+    int cells = utf_ptr2cells(ptr);
+    int new_attr = attr;
+
+    if (ga != NULL) {
+      // Handle fuzzy matching
+      for (int i = 0; i < ga->ga_len; i++) {
+        int *match_pos = ((int *)ga->ga_data) + i;
+        int actual_char_pos = 0;
+        const char *temp_ptr = text;
+        while (temp_ptr < ptr) {
+          temp_ptr += utfc_ptr2len(temp_ptr);
+          actual_char_pos++;
+        }
+        if (actual_char_pos == match_pos[0]) {
+          new_attr = win_hl_attr(curwin, (attr == win_hl_attr(curwin, HLF_PSI)
+                                          ? HLF_PMSI : HLF_PMNI));
+          break;
+        }
+      }
+    } else if (!in_fuzzy && ptr < text + leader_len
+               && strncmp(text, match_leader, leader_len) == 0) {
+      new_attr = win_hl_attr(curwin, (attr == win_hl_attr(curwin, HLF_PSI)
+                                      ? HLF_PMSI : HLF_PMNI));
+    }
+
+    grid_line_puts(col, ptr, char_len, new_attr);
+    col += cells;
+    ptr += char_len;
+  }
+
+  if (ga != NULL) {
+    ga_clear(ga);
+    xfree(ga);
+  }
+  if (rt_leader) {
+    xfree(rt_leader);
+  }
+}
+
 /// Redraw the popup menu, using "pum_first" and "pum_selected".
 void pum_redraw(void)
 {
@@ -593,13 +663,12 @@ void pum_redraw(void)
                   size++;
                 }
               }
-              grid_line_puts(grid_col - size + 1, rt, -1, attr);
+              pum_puts_with_attr(grid_col - size + 1, rt, attr);
               xfree(rt_start);
               xfree(st);
               grid_col -= width;
             } else {
-              // use grid_line_puts() to truncate the text
-              grid_line_puts(grid_col, st, -1, attr);
+              pum_puts_with_attr(grid_col, st, attr);
               xfree(st);
               grid_col += width;
             }
diff --git a/src/nvim/search.c b/src/nvim/search.c
index bee124e305..fef27dba48 100644
--- a/src/nvim/search.c
+++ b/src/nvim/search.c
@@ -21,12 +21,14 @@
 #include "nvim/errors.h"
 #include "nvim/eval.h"
 #include "nvim/eval/typval.h"
+#include "nvim/eval/typval_defs.h"
 #include "nvim/ex_cmds.h"
 #include "nvim/ex_cmds_defs.h"
 #include "nvim/ex_docmd.h"
 #include "nvim/ex_getln.h"
 #include "nvim/fileio.h"
 #include "nvim/fold.h"
+#include "nvim/garray.h"
 #include "nvim/getchar.h"
 #include "nvim/gettext_defs.h"
 #include "nvim/globals.h"
@@ -3254,7 +3256,7 @@ static void fuzzy_match_in_list(list_T *const l, char *const str, const bool mat
                                 const char *const key, Callback *const item_cb,
                                 const bool retmatchpos, list_T *const fmatchlist,
                                 const int max_matches)
-  FUNC_ATTR_NONNULL_ARG(2, 5, 7)
+  FUNC_ATTR_NONNULL_ARG(2, 7)
 {
   int len = tv_list_len(l);
   if (len == 0) {
@@ -3542,6 +3544,84 @@ int fuzzy_match_str(char *const str, const char *const pat)
   return score;
 }
 
+/// Fuzzy match the position of string "pat" in string "str".
+/// @returns a dynamic array of matching positions. If there is no match, returns NULL.
+garray_T *fuzzy_match_str_with_pos(const char *const str, char *const pat)
+{
+  garray_T *match_positions = xmalloc(sizeof(garray_T));
+
+  ga_init(match_positions, sizeof(int), 10);
+  if (str == NULL || pat == NULL) {
+    ga_clear(match_positions);
+    return NULL;
+  }
+  list_T *l = tv_list_alloc(1);
+
+  typval_T tv_str = {
+    .v_type = VAR_STRING,
+    .vval.v_string = xstrdup(str),
+  };
+  tv_list_append_tv(l, &tv_str);
+
+  list_T *retlist = tv_list_alloc(3);
+  list_T *match_str_list = tv_list_alloc(1);
+  list_T *match_pos_list = tv_list_alloc(1);
+  list_T *match_score_list = tv_list_alloc(1);
+
+  tv_list_append_list(retlist, match_str_list);
+  tv_list_append_list(retlist, match_pos_list);
+  tv_list_append_list(retlist, match_score_list);
+
+  fuzzy_match_in_list(l, pat, false, NULL, NULL, true, retlist, 1);
+
+  varnumber_T score = 0;
+  listitem_T *score_item = tv_list_find(retlist, 2);
+  if (score_item != NULL && TV_LIST_ITEM_TV(score_item)->v_type == VAR_LIST) {
+    list_T *score_list = TV_LIST_ITEM_TV(score_item)->vval.v_list;
+    if (tv_list_len(score_list) > 0) {
+      listitem_T *first_score_item = tv_list_first(score_list);
+      if (first_score_item != NULL && TV_LIST_ITEM_TV(first_score_item)->v_type == VAR_NUMBER) {
+        score = TV_LIST_ITEM_TV(first_score_item)->vval.v_number;
+      }
+    }
+  }
+  if (score == 0) {
+    goto cleanup;
+  }
+
+  listitem_T *positions_item = tv_list_find(retlist, 1);
+  if (positions_item != NULL && TV_LIST_ITEM_TV(positions_item)->v_type == VAR_LIST) {
+    list_T *positions_outer_list = TV_LIST_ITEM_TV(positions_item)->vval.v_list;
+    if (tv_list_len(positions_outer_list) > 0) {
+      listitem_T *outer_li = tv_list_first(positions_outer_list);
+      if (outer_li != NULL && TV_LIST_ITEM_TV(outer_li)->v_type == VAR_LIST) {
+        list_T *positions_inner_list = TV_LIST_ITEM_TV(outer_li)->vval.v_list;
+        TV_LIST_ITER_CONST(positions_inner_list, li, {
+          if (TV_LIST_ITEM_TV(li)->v_type == VAR_NUMBER) {
+            varnumber_T pos = TV_LIST_ITEM_TV(li)->vval.v_number;
+            GA_APPEND(int, match_positions, (int)pos);
+          }
+        });
+      }
+    }
+  }
+
+  xfree(tv_str.vval.v_string);
+  tv_list_free(retlist);
+  tv_list_free(l);
+  return match_positions;
+
+cleanup:
+  xfree(tv_str.vval.v_string);
+  tv_list_free(match_str_list);
+  tv_list_free(match_pos_list);
+  tv_list_free(match_score_list);
+  tv_list_free(retlist);
+  tv_list_free(l);
+  ga_clear(match_positions);
+  return NULL;
+}
+
 /// 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,