vim-patch:8.2.4483: command completion makes two rounds to collect matches (#21857)

Problem:    Command completion makes two rounds to collect matches.
Solution:   Use a growarray to collect matches. (Yegappan Lakshmanan,
            closes vim/vim#9860)

https://github.com/vim/vim/commit/5de4c4372d4366bc85cb66efb3e373439b9471c5

Co-authored-by: Yegappan Lakshmanan <yegappan@yahoo.com>

5 files changed, 195 insertions, 190 deletions

diff --git a/src/nvim/buffer.c b/src/nvim/buffer.c
index 9dd5fdaea5..3f93d85624 100644
--- a/src/nvim/buffer.c
+++ b/src/nvim/buffer.c
@@ -2415,31 +2415,34 @@ int ExpandBufnames(char *pat, int *num_file, char ***file, int options)
           }
         }
 
-        if (p != NULL) {
-          if (round == 1) {
+        if (p == NULL) {
+          continue;
+        }
+
+        if (round == 1) {
+          count++;
+          continue;
+        }
+
+        if (options & WILD_HOME_REPLACE) {
+          p = home_replace_save(buf, p);
+        } else {
+          p = xstrdup(p);
+        }
+
+        if (!fuzzy) {
+          if (matches != NULL) {
+            matches[count].buf = buf;
+            matches[count].match = p;
             count++;
           } else {
-            if (options & WILD_HOME_REPLACE) {
-              p = home_replace_save(buf, p);
-            } else {
-              p = xstrdup(p);
-            }
-
-            if (!fuzzy) {
-              if (matches != NULL) {
-                matches[count].buf = buf;
-                matches[count].match = p;
-                count++;
-              } else {
-                (*file)[count++] = p;
-              }
-            } else {
-              fuzmatch[count].idx = count;
-              fuzmatch[count].str = p;
-              fuzmatch[count].score = score;
-              count++;
-            }
+            (*file)[count++] = p;
           }
+        } else {
+          fuzmatch[count].idx = count;
+          fuzmatch[count].str = p;
+          fuzmatch[count].score = score;
+          count++;
         }
       }
       if (count == 0) {         // no match found, break here
diff --git a/src/nvim/cmdexpand.c b/src/nvim/cmdexpand.c
index 21b9eb1f56..4f6936958f 100644
--- a/src/nvim/cmdexpand.c
+++ b/src/nvim/cmdexpand.c
@@ -2757,48 +2757,19 @@ static void ExpandGeneric(const char *const pat, expand_T *xp, regmatch_T *regma
                           char ***matches, int *numMatches, CompleteListItemGetter func,
                           int escaped)
 {
-  int i;
-  size_t count = 0;
-  char *str;
-
   const bool fuzzy = cmdline_fuzzy_complete(pat);
+  *matches = NULL;
+  *numMatches = 0;
 
-  // count the number of matching names
-  for (i = 0;; i++) {
-    str = (*func)(xp, i);
-    if (str == NULL) {  // end of list
-      break;
-    }
-    if (*str == NUL) {  // skip empty strings
-      continue;
-    }
-
-    bool match;
-    if (!fuzzy) {
-      match = vim_regexec(regmatch, str, (colnr_T)0);
-    } else {
-      match = fuzzy_match_str(str, pat) != 0;
-    }
-    if (match) {
-      count++;
-    }
-  }
-  if (count == 0) {
-    return;
-  }
-  assert(count < INT_MAX);
-  *numMatches = (int)count;
-  fuzmatch_str_T *fuzmatch = NULL;
-  if (fuzzy) {
-    fuzmatch = xmalloc(count * sizeof(fuzmatch_str_T));
+  garray_T ga;
+  if (!fuzzy) {
+    ga_init(&ga, sizeof(char *), 30);
   } else {
-    *matches = xmalloc(count * sizeof(char *));
+    ga_init(&ga, sizeof(fuzmatch_str_T), 30);
   }
 
-  // copy the matching names into allocated memory
-  count = 0;
-  for (i = 0;; i++) {
-    str = (*func)(xp, i);
+  for (int i = 0;; i++) {
+    char *str = (*func)(xp, i);
     if (str == NULL) {  // End of list.
       break;
     }
@@ -2808,11 +2779,15 @@ static void ExpandGeneric(const char *const pat, expand_T *xp, regmatch_T *regma
 
     bool match;
     int score = 0;
-    if (!fuzzy) {
-      match = vim_regexec(regmatch, str, (colnr_T)0);
+    if (xp->xp_pattern[0] != NUL) {
+      if (!fuzzy) {
+        match = vim_regexec(regmatch, str, (colnr_T)0);
+      } else {
+        score = fuzzy_match_str(str, pat);
+        match = (score != 0);
+      }
     } else {
-      score = fuzzy_match_str(str, pat);
-      match = (score != 0);
+      match = true;
     }
 
     if (!match) {
@@ -2824,14 +2799,17 @@ static void ExpandGeneric(const char *const pat, expand_T *xp, regmatch_T *regma
     } else {
       str = xstrdup(str);
     }
+
     if (fuzzy) {
-      fuzmatch[count].idx = (int)count;
-      fuzmatch[count].str = str;
-      fuzmatch[count].score = score;
+      GA_APPEND(fuzmatch_str_T, &ga, ((fuzmatch_str_T){
+        .idx = ga.ga_len,
+        .str = str,
+        .score = score,
+      }));
     } else {
-      (*matches)[count] = str;
+      GA_APPEND(char *, &ga, str);
     }
-    count++;
+
     if (func == get_menu_names) {
       // Test for separator added by get_menu_names().
       str += strlen(str) - 1;
@@ -2841,31 +2819,42 @@ static void ExpandGeneric(const char *const pat, expand_T *xp, regmatch_T *regma
     }
   }
 
+  if (ga.ga_len == 0) {
+    return;
+  }
+
   // Sort the results.  Keep menu's in the specified order.
-  bool funcsort = false;
-  if (xp->xp_context != EXPAND_MENUNAMES && xp->xp_context != EXPAND_MENUS) {
+  if (!fuzzy && xp->xp_context != EXPAND_MENUNAMES && xp->xp_context != EXPAND_MENUS) {
     if (xp->xp_context == EXPAND_EXPRESSION
         || xp->xp_context == EXPAND_FUNCTIONS
         || xp->xp_context == EXPAND_USER_FUNC) {
       // <SNR> functions should be sorted to the end.
-      funcsort = true;
-      if (!fuzzy) {
-        qsort(*matches, (size_t)(*numMatches), sizeof(char *), sort_func_compare);
-      }
+      qsort(ga.ga_data, (size_t)ga.ga_len, sizeof(char *), sort_func_compare);
     } else {
-      if (!fuzzy) {
-        sort_strings(*matches, *numMatches);
-      }
+      sort_strings(ga.ga_data, ga.ga_len);
+    }
+  }
+
+  if (!fuzzy) {
+    *matches = ga.ga_data;
+    *numMatches = ga.ga_len;
+  } else {
+    bool funcsort = false;
+
+    if (xp->xp_context == EXPAND_EXPRESSION
+        || xp->xp_context == EXPAND_FUNCTIONS
+        || xp->xp_context == EXPAND_USER_FUNC) {
+      // <SNR> functions should be sorted to the end.
+      funcsort = true;
     }
+
+    fuzzymatches_to_strmatches(ga.ga_data, matches, ga.ga_len, funcsort);
+    *numMatches = ga.ga_len;
   }
 
   // Reset the variables used for special highlight names expansion, so that
   // they don't show up when getting normal highlight names by ID.
   reset_expand_highlight();
-
-  if (fuzzy) {
-    fuzzymatches_to_strmatches(fuzmatch, matches, (int)count, funcsort);
-  }
 }
 
 /// Expand shell command matches in one directory of $PATH.
@@ -3047,27 +3036,23 @@ static void *call_user_expand_func(user_expand_func_T user_expand_func, expand_T
 static int ExpandUserDefined(const char *const pat, expand_T *xp, regmatch_T *regmatch,
                              char ***matches, int *numMatches)
 {
-  char *e;
-  garray_T ga;
-
   const bool fuzzy = cmdline_fuzzy_complete(pat);
-
   *matches = NULL;
   *numMatches = 0;
-  char *const retstr = call_user_expand_func((user_expand_func_T)call_func_retstr, xp);
 
+  char *const retstr = call_user_expand_func((user_expand_func_T)call_func_retstr, xp);
   if (retstr == NULL) {
     return FAIL;
   }
 
+  garray_T ga;
   if (!fuzzy) {
     ga_init(&ga, (int)sizeof(char *), 3);
   } else {
     ga_init(&ga, (int)sizeof(fuzmatch_str_T), 3);
   }
 
-  int count = 0;
-  for (char *s = retstr; *s != NUL; s = e) {
+  for (char *s = retstr, *e; *s != NUL; s = e) {
     e = vim_strchr(s, '\n');
     if (e == NULL) {
       e = s + strlen(s);
@@ -3077,7 +3062,7 @@ static int ExpandUserDefined(const char *const pat, expand_T *xp, regmatch_T *re
 
     bool match;
     int score = 0;
-    if (xp->xp_pattern[0] || fuzzy) {
+    if (xp->xp_pattern[0] != NUL) {
       if (!fuzzy) {
         match = vim_regexec(regmatch, s, (colnr_T)0);
       } else {
@@ -3095,12 +3080,11 @@ static int ExpandUserDefined(const char *const pat, expand_T *xp, regmatch_T *re
         GA_APPEND(char *, &ga, xstrnsave(s, (size_t)(e - s)));
       } else {
         GA_APPEND(fuzmatch_str_T, &ga, ((fuzmatch_str_T){
-          .idx = count,
+          .idx = ga.ga_len,
           .str = xstrnsave(s, (size_t)(e - s)),
           .score = score,
         }));
       }
-      count++;
     }
 
     if (*e != NUL) {
@@ -3109,12 +3093,16 @@ static int ExpandUserDefined(const char *const pat, expand_T *xp, regmatch_T *re
   }
   xfree(retstr);
 
+  if (ga.ga_len == 0) {
+    return OK;
+  }
+
   if (!fuzzy) {
     *matches = ga.ga_data;
     *numMatches = ga.ga_len;
   } else {
-    fuzzymatches_to_strmatches(ga.ga_data, matches, count, false);
-    *numMatches = count;
+    fuzzymatches_to_strmatches(ga.ga_data, matches, ga.ga_len, false);
+    *numMatches = ga.ga_len;
   }
   return OK;
 }
diff --git a/src/nvim/garray.h b/src/nvim/garray.h
index 3e2650b410..1623c4db7b 100644
--- a/src/nvim/garray.h
+++ b/src/nvim/garray.h
@@ -27,7 +27,8 @@ typedef struct growarray {
 #define GA_APPEND(item_type, gap, item) \
   do { \
     ga_grow(gap, 1); \
-    ((item_type *)(gap)->ga_data)[(gap)->ga_len++] = (item); \
+    ((item_type *)(gap)->ga_data)[(gap)->ga_len] = (item); \
+    (gap)->ga_len++; \
   } while (0)
 
 #define GA_APPEND_VIA_PTR(item_type, gap) \
diff --git a/src/nvim/mapping.c b/src/nvim/mapping.c
index 1785f41a37..29c6bb6723 100644
--- a/src/nvim/mapping.c
+++ b/src/nvim/mapping.c
@@ -1272,41 +1272,82 @@ char_u *set_context_in_map_cmd(expand_T *xp, char *cmd, char *arg, bool forceit,
 /// @return OK if matches found, FAIL otherwise.
 int ExpandMappings(char *pat, regmatch_T *regmatch, int *numMatches, char ***matches)
 {
-  mapblock_T *mp;
-  int hash;
-  int count;
-  int round;
-  char *p;
-  int i;
-
-  fuzmatch_str_T *fuzmatch = NULL;
   const bool fuzzy = cmdline_fuzzy_complete(pat);
 
   *numMatches = 0;                    // return values in case of FAIL
   *matches = NULL;
 
-  // round == 1: Count the matches.
-  // round == 2: Build the array to keep the matches.
-  for (round = 1; round <= 2; round++) {
-    count = 0;
-
-    // First search in map modifier arguments
-    for (i = 0; i < 7; i++) {
-      if (i == 0) {
-        p = "<silent>";
-      } else if (i == 1) {
-        p = "<unique>";
-      } else if (i == 2) {
-        p = "<script>";
-      } else if (i == 3) {
-        p = "<expr>";
-      } else if (i == 4 && !expand_buffer) {
-        p = "<buffer>";
-      } else if (i == 5) {
-        p = "<nowait>";
-      } else if (i == 6) {
-        p = "<special>";
-      } else {
+  garray_T ga;
+  if (!fuzzy) {
+    ga_init(&ga, sizeof(char *), 3);
+  } else {
+    ga_init(&ga, sizeof(fuzmatch_str_T), 3);
+  }
+
+  // First search in map modifier arguments
+  for (int i = 0; i < 7; i++) {
+    char *p;
+    if (i == 0) {
+      p = "<silent>";
+    } else if (i == 1) {
+      p = "<unique>";
+    } else if (i == 2) {
+      p = "<script>";
+    } else if (i == 3) {
+      p = "<expr>";
+    } else if (i == 4 && !expand_buffer) {
+      p = "<buffer>";
+    } else if (i == 5) {
+      p = "<nowait>";
+    } else if (i == 6) {
+      p = "<special>";
+    } else {
+      continue;
+    }
+
+    bool match;
+    int score = 0;
+    if (!fuzzy) {
+      match = vim_regexec(regmatch, p, (colnr_T)0);
+    } else {
+      score = fuzzy_match_str(p, pat);
+      match = (score != 0);
+    }
+
+    if (!match) {
+      continue;
+    }
+
+    if (fuzzy) {
+      GA_APPEND(fuzmatch_str_T, &ga, ((fuzmatch_str_T){
+        .idx = ga.ga_len,
+        .str = xstrdup(p),
+        .score = score,
+      }));
+    } else {
+      GA_APPEND(char *, &ga, xstrdup(p));
+    }
+  }
+
+  for (int hash = 0; hash < 256; hash++) {
+    mapblock_T *mp;
+    if (expand_isabbrev) {
+      if (hash > 0) {    // only one abbrev list
+        break;  // for (hash)
+      }
+      mp = first_abbr;
+    } else if (expand_buffer) {
+      mp = curbuf->b_maphash[hash];
+    } else {
+      mp = maphash[hash];
+    }
+    for (; mp; mp = mp->m_next) {
+      if (!(mp->m_mode & expand_mapmodes)) {
+        continue;
+      }
+
+      char *p = (char *)translate_mapping((char_u *)mp->m_keys, CPO_TO_CPO_FLAGS);
+      if (p == NULL) {
         continue;
       }
 
@@ -1320,81 +1361,35 @@ int ExpandMappings(char *pat, regmatch_T *regmatch, int *numMatches, char ***mat
       }
 
       if (!match) {
+        xfree(p);
         continue;
       }
 
-      if (round == 2) {
-        if (fuzzy) {
-          fuzmatch[count].idx = count;
-          fuzmatch[count].str = xstrdup(p);
-          fuzmatch[count].score = score;
-        } else {
-          (*matches)[count] = xstrdup(p);
-        }
-      }
-      count++;
-    }
-
-    for (hash = 0; hash < 256; hash++) {
-      if (expand_isabbrev) {
-        if (hash > 0) {    // only one abbrev list
-          break;           // for (hash)
-        }
-        mp = first_abbr;
-      } else if (expand_buffer) {
-        mp = curbuf->b_maphash[hash];
-      } else {
-        mp = maphash[hash];
-      }
-      for (; mp; mp = mp->m_next) {
-        if (mp->m_mode & expand_mapmodes) {
-          p = (char *)translate_mapping((char_u *)mp->m_keys, CPO_TO_CPO_FLAGS);
-          if (p != NULL) {
-            bool match;
-            int score = 0;
-            if (!fuzzy) {
-              match = vim_regexec(regmatch, p, (colnr_T)0);
-            } else {
-              score = fuzzy_match_str(p, pat);
-              match = (score != 0);
-            }
-
-            if (match) {
-              if (round == 2) {
-                if (fuzzy) {
-                  fuzmatch[count].idx = count;
-                  fuzmatch[count].str = p;
-                  fuzmatch[count].score = score;
-                } else {
-                  (*matches)[count] = p;
-                }
-                p = NULL;
-              }
-              count++;
-            }
-          }
-          xfree(p);
-        }
-      }       // for (mp)
-    }     // for (hash)
-
-    if (count == 0) {  // no match found
-      break;       // for (round)
-    }
-
-    if (round == 1) {
       if (fuzzy) {
-        fuzmatch = xmalloc((size_t)count * sizeof(fuzmatch_str_T));
+        GA_APPEND(fuzmatch_str_T, &ga, ((fuzmatch_str_T){
+          .idx = ga.ga_len,
+          .str = p,
+          .score = score,
+        }));
       } else {
-        *matches = xmalloc((size_t)count * sizeof(char *));
+        GA_APPEND(char *, &ga, p);
       }
-    }
-  }   // for (round)
+    }  // for (mp)
+  }  // for (hash)
 
-  if (fuzzy) {
-    fuzzymatches_to_strmatches(fuzmatch, matches, count, false);
+  if (ga.ga_len == 0) {
+    return FAIL;
+  }
+
+  if (!fuzzy) {
+    *matches = ga.ga_data;
+    *numMatches = ga.ga_len;
+  } else {
+    fuzzymatches_to_strmatches(ga.ga_data, matches, ga.ga_len, false);
+    *numMatches = ga.ga_len;
   }
 
+  int count = *numMatches;
   if (count > 1) {
     // Sort the matches
     // Fuzzy matching already sorts the matches
diff --git a/src/nvim/testdir/test_cmdline.vim b/src/nvim/testdir/test_cmdline.vim
index 210c2774f2..ea7bfae639 100644
--- a/src/nvim/testdir/test_cmdline.vim
+++ b/src/nvim/testdir/test_cmdline.vim
@@ -2876,6 +2876,24 @@ func Test_fuzzy_completion_userdefined_func()
   set wildoptions&
 endfunc
 
+" <SNR> functions should be sorted to the end
+func Test_fuzzy_completion_userdefined_snr_func()
+  func s:Sendmail()
+  endfunc
+  func SendSomemail()
+  endfunc
+  func S1e2n3dmail()
+  endfunc
+  set wildoptions=fuzzy
+  call feedkeys(":call sendmail\<C-A>\<C-B>\"\<CR>", 'tx')
+  call assert_equal('"call SendSomemail() S1e2n3dmail() '
+        \ .. expand("<SID>") .. 'Sendmail()', @:)
+  set wildoptions&
+  delfunc s:Sendmail
+  delfunc SendSomemail
+  delfunc S1e2n3dmail
+endfunc
+
 " user defined command name completion
 func Test_fuzzy_completion_userdefined_cmd()
   set wildoptions&