vim-patch:9.1.0891: building the completion list array is inefficient

Problem:  building the completion list array is inefficient
Solution: refactor and improve ins_compl_build_pum() func
          (glepnir)

current time complexity is O(n^2). I guess garray is not used here to save memory and avoid efficiency
is caused by heap memory allocation. A simple way is to add an extra pointer as a single linked list
to store the matching compl_T, and traverse this single linked list to generate compl_match_array.
The time complexity is O(n x m). The worst case is m=n, but we can still get a little improvement.
Because the if condition does not need to be run at one time. This should be a good solution for now.
Later we may be able to complete it in O(lgn) time. But this requires more reconstruction. So this is
the first step.

closes: #16125

https://github.com/vim/vim/commit/80b662009c0fe8f1728a3f3a2c8013b7eebf6745

1 files changed, 75 insertions, 70 deletions

diff --git a/src/nvim/insexpand.c b/src/nvim/insexpand.c
index 154a142c74..6a45a06fb9 100644
--- a/src/nvim/insexpand.c
+++ b/src/nvim/insexpand.c
@@ -156,6 +156,7 @@ typedef struct compl_S compl_T;
 struct compl_S {
   compl_T *cp_next;
   compl_T *cp_prev;
+  compl_T *cp_match_next;        ///< matched next compl_T
   char *cp_str;                  ///< matched text
   char *(cp_text[CPT_COUNT]);    ///< text for the menu
   typval_T cp_user_data;
@@ -789,6 +790,7 @@ static inline void free_cptext(char *const *const cptext)
 /// @param[in]  cdir       match direction. If 0, use "compl_direction".
 /// @param[in]  flags_arg  match flags (cp_flags)
 /// @param[in]  adup       accept this match even if it is already present.
+/// @param[in]  user_hl    list of extra highlight attributes for abbr kind.
 ///
 /// If "cdir" is FORWARD, then the match is added after the current match.
 /// Otherwise, it is added before the current match.
@@ -798,7 +800,7 @@ static inline void free_cptext(char *const *const cptext)
 ///         returned in case of error.
 static int ins_compl_add(char *const str, int len, char *const fname, char *const *const cptext,
                          const bool cptext_allocated, typval_T *user_data, const Direction cdir,
-                         int flags_arg, const bool adup, int *extra_hl)
+                         int flags_arg, const bool adup, const int *user_hl)
   FUNC_ATTR_NONNULL_ARG(1)
 {
   compl_T *match;
@@ -864,8 +866,8 @@ static int ins_compl_add(char *const str, int len, char *const fname, char *cons
     match->cp_fname = NULL;
   }
   match->cp_flags = flags;
-  match->cp_user_abbr_hlattr = extra_hl ? extra_hl[0] : -1;
-  match->cp_user_kind_hlattr = extra_hl ? extra_hl[1] : -1;
+  match->cp_user_abbr_hlattr = user_hl ? user_hl[0] : -1;
+  match->cp_user_kind_hlattr = user_hl ? user_hl[1] : -1;
 
   if (cptext != NULL) {
     int i;
@@ -1173,7 +1175,7 @@ static int ins_compl_build_pum(void)
   unsigned cur_cot_flags = get_cot_flags();
   bool compl_no_select = (cur_cot_flags & kOptCotFlagNoselect) != 0;
   bool compl_fuzzy_match = (cur_cot_flags & kOptCotFlagFuzzy) != 0;
-
+  compl_T *match_head = NULL, *match_tail = NULL;
   do {
     // When 'completeopt' contains "fuzzy" and leader is not NULL or empty,
     // set the cp_score for later comparisons.
@@ -1186,6 +1188,12 @@ static int ins_compl_build_pum(void)
             || ins_compl_equal(comp, compl_leader, (size_t)lead_len)
             || (compl_fuzzy_match && comp->cp_score > 0))) {
       compl_match_arraysize++;
+      if (match_head == NULL) {
+        match_head = comp;
+      } else {
+        match_tail->cp_match_next = comp;
+      }
+      match_tail = comp;
     }
     comp = comp->cp_next;
   } while (comp != NULL && !is_first_match(comp));
@@ -1206,75 +1214,70 @@ static int ins_compl_build_pum(void)
   }
 
   compl_T *shown_compl = NULL;
-  bool did_find_shown_match = false;
+  bool did_find_shown_match = match_head == match_tail ? true : false;
   int cur = -1;
   int i = 0;
-  comp = compl_first_match;
-  do {
-    if (!match_at_original_text(comp)
-        && (compl_leader == NULL
-            || ins_compl_equal(comp, compl_leader, (size_t)lead_len)
-            || (compl_fuzzy_match && comp->cp_score > 0))) {
-      if (!shown_match_ok && !compl_fuzzy_match) {
-        if (comp == compl_shown_match || did_find_shown_match) {
-          // This item is the shown match or this is the
-          // first displayed item after the shown match.
+  comp = match_head;
+  while (comp != NULL) {
+    if (!shown_match_ok && !compl_fuzzy_match) {
+      if (comp == compl_shown_match || did_find_shown_match) {
+        // This item is the shown match or this is the
+        // first displayed item after the shown match.
+        compl_shown_match = comp;
+        did_find_shown_match = true;
+        shown_match_ok = true;
+      } else {
+        // Remember this displayed match for when the
+        // shown match is just below it.
+        shown_compl = comp;
+      }
+      cur = i;
+    } else if (compl_fuzzy_match) {
+      if (i == 0) {
+        shown_compl = comp;
+      }
+      // Update the maximum fuzzy score and the shown match
+      // if the current item's score is higher
+      if (comp->cp_score > max_fuzzy_score) {
+        did_find_shown_match = true;
+        max_fuzzy_score = comp->cp_score;
+        if (!compl_no_select) {
           compl_shown_match = comp;
-          did_find_shown_match = true;
-          shown_match_ok = true;
-        } else {
-          // Remember this displayed match for when the
-          // shown match is just below it.
-          shown_compl = comp;
-        }
-        cur = i;
-      } else if (compl_fuzzy_match) {
-        if (i == 0) {
-          shown_compl = comp;
-        }
-        // Update the maximum fuzzy score and the shown match
-        // if the current item's score is higher
-        if (comp->cp_score > max_fuzzy_score) {
-          did_find_shown_match = true;
-          max_fuzzy_score = comp->cp_score;
-          if (!compl_no_select) {
-            compl_shown_match = comp;
-          }
         }
+      }
 
-        if (!shown_match_ok && comp == compl_shown_match && !compl_no_select) {
-          cur = i;
-          shown_match_ok = true;
-        }
+      if (!shown_match_ok && comp == compl_shown_match && !compl_no_select) {
+        cur = i;
+        shown_match_ok = true;
+      }
 
-        // If there is no "no select" condition and the max fuzzy
-        // score is positive, or there is no completion leader or the
-        // leader length is zero, mark the shown match as valid and
-        // reset the current index.
-        if (!compl_no_select
-            && (max_fuzzy_score > 0
-                || (compl_leader == NULL || lead_len == 0))) {
-          if (match_at_original_text(compl_shown_match)) {
-            compl_shown_match = shown_compl;
-          }
+      // If there is no "no select" condition and the max fuzzy
+      // score is positive, or there is no completion leader or the
+      // leader length is zero, mark the shown match as valid and
+      // reset the current index.
+      if (!compl_no_select
+          && (max_fuzzy_score > 0
+              || (compl_leader == NULL || lead_len == 0))) {
+        if (match_at_original_text(compl_shown_match)) {
+          compl_shown_match = shown_compl;
         }
       }
+    }
 
-      if (comp->cp_text[CPT_ABBR] != NULL) {
-        compl_match_array[i].pum_text = comp->cp_text[CPT_ABBR];
-      } else {
-        compl_match_array[i].pum_text = comp->cp_str;
-      }
-      compl_match_array[i].pum_kind = comp->cp_text[CPT_KIND];
-      compl_match_array[i].pum_info = comp->cp_text[CPT_INFO];
-      compl_match_array[i].pum_score = comp->cp_score;
-      compl_match_array[i].pum_user_abbr_hlattr = comp->cp_user_abbr_hlattr;
-      compl_match_array[i].pum_user_kind_hlattr = comp->cp_user_kind_hlattr;
-      if (comp->cp_text[CPT_MENU] != NULL) {
-        compl_match_array[i++].pum_extra = comp->cp_text[CPT_MENU];
-      } else {
-        compl_match_array[i++].pum_extra = comp->cp_fname;
-      }
+    if (comp->cp_text[CPT_ABBR] != NULL) {
+      compl_match_array[i].pum_text = comp->cp_text[CPT_ABBR];
+    } else {
+      compl_match_array[i].pum_text = comp->cp_str;
+    }
+    compl_match_array[i].pum_kind = comp->cp_text[CPT_KIND];
+    compl_match_array[i].pum_info = comp->cp_text[CPT_INFO];
+    compl_match_array[i].pum_score = comp->cp_score;
+    compl_match_array[i].pum_user_abbr_hlattr = comp->cp_user_abbr_hlattr;
+    compl_match_array[i].pum_user_kind_hlattr = comp->cp_user_kind_hlattr;
+    if (comp->cp_text[CPT_MENU] != NULL) {
+      compl_match_array[i++].pum_extra = comp->cp_text[CPT_MENU];
+    } else {
+      compl_match_array[i++].pum_extra = comp->cp_fname;
     }
 
     if (comp == compl_shown_match && !compl_fuzzy_match) {
@@ -1293,8 +1296,10 @@ static int ins_compl_build_pum(void)
         shown_match_ok = true;
       }
     }
-    comp = comp->cp_next;
-  } while (comp != NULL && !is_first_match(comp));
+    compl_T *match_next = comp->cp_match_next;
+    comp->cp_match_next = NULL;
+    comp = match_next;
+  }
 
   if (compl_fuzzy_match && compl_leader != NULL && lead_len > 0) {
     for (i = 0; i < compl_match_arraysize; i++) {
@@ -2574,7 +2579,7 @@ static int ins_compl_add_tv(typval_T *const tv, const Direction dir, bool fast)
   char *(cptext[CPT_COUNT]);
   char *user_abbr_hlname = NULL;
   char *user_kind_hlname = NULL;
-  int extra_hl[2] = { -1, -1 };
+  int user_hl[2] = { -1, -1 };
   typval_T user_data;
 
   user_data.v_type = VAR_UNKNOWN;
@@ -2586,10 +2591,10 @@ static int ins_compl_add_tv(typval_T *const tv, const Direction dir, bool fast)
     cptext[CPT_INFO] = tv_dict_get_string(tv->vval.v_dict, "info", true);
 
     user_abbr_hlname = tv_dict_get_string(tv->vval.v_dict, "abbr_hlgroup", false);
-    extra_hl[0] = get_user_highlight_attr(user_abbr_hlname);
+    user_hl[0] = get_user_highlight_attr(user_abbr_hlname);
 
     user_kind_hlname = tv_dict_get_string(tv->vval.v_dict, "kind_hlgroup", false);
-    extra_hl[1] = get_user_highlight_attr(user_kind_hlname);
+    user_hl[1] = get_user_highlight_attr(user_kind_hlname);
 
     tv_dict_get_tv(tv->vval.v_dict, "user_data", &user_data);
 
@@ -2612,7 +2617,7 @@ static int ins_compl_add_tv(typval_T *const tv, const Direction dir, bool fast)
     return FAIL;
   }
   int status = ins_compl_add((char *)word, -1, NULL, cptext, true,
-                             &user_data, dir, flags, dup, extra_hl);
+                             &user_data, dir, flags, dup, user_hl);
   if (status != OK) {
     tv_clear(&user_data);
   }