From 344923fe9a4d4966a8faf48d2767bfed181925c5 Mon Sep 17 00:00:00 2001 From: glepnir Date: Thu, 28 Nov 2024 13:54:59 +0800 Subject: vim-patch:9.1.0867: ins_compl_add() has too many args Problem: ins_compl_add() has too many args Solution: refactor it and use an int array instead of 2 separate int args (glepnir) closes: vim/vim#16062 https://github.com/vim/vim/commit/5c66e23c624717216d380d938d0bba5d34a004fe Co-authored-by: glepnir --- src/nvim/insexpand.c | 26 ++++++++++++-------------- 1 file changed, 12 insertions(+), 14 deletions(-) (limited to 'src/nvim') diff --git a/src/nvim/insexpand.c b/src/nvim/insexpand.c index d3517667fb..154a142c74 100644 --- a/src/nvim/insexpand.c +++ b/src/nvim/insexpand.c @@ -758,7 +758,7 @@ int ins_compl_add_infercase(char *str_arg, int len, bool icase, char *fname, Dir flags |= CP_ICASE; } - int res = ins_compl_add(str, len, fname, NULL, false, NULL, dir, flags, false, -1, -1); + int res = ins_compl_add(str, len, fname, NULL, false, NULL, dir, flags, false, NULL); xfree(tofree); return res; } @@ -798,7 +798,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 user_abbr_hlattr, int user_kind_hlattr) + int flags_arg, const bool adup, int *extra_hl) FUNC_ATTR_NONNULL_ARG(1) { compl_T *match; @@ -864,8 +864,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 = user_abbr_hlattr; - match->cp_user_kind_hlattr = user_kind_hlattr; + match->cp_user_abbr_hlattr = extra_hl ? extra_hl[0] : -1; + match->cp_user_kind_hlattr = extra_hl ? extra_hl[1] : -1; if (cptext != NULL) { int i; @@ -999,7 +999,7 @@ static void ins_compl_add_matches(int num_matches, char **matches, int icase) for (int i = 0; i < num_matches && add_r != FAIL; i++) { if ((add_r = ins_compl_add(matches[i], -1, NULL, NULL, false, NULL, dir, CP_FAST | (icase ? CP_ICASE : 0), - false, -1, -1)) == OK) { + false, NULL)) == OK) { // If dir was BACKWARD then honor it just once. dir = FORWARD; } @@ -2573,9 +2573,8 @@ static int ins_compl_add_tv(typval_T *const tv, const Direction dir, bool fast) int flags = fast ? CP_FAST : 0; char *(cptext[CPT_COUNT]); char *user_abbr_hlname = NULL; - int user_abbr_hlattr = -1; char *user_kind_hlname = NULL; - int user_kind_hlattr = -1; + int extra_hl[2] = { -1, -1 }; typval_T user_data; user_data.v_type = VAR_UNKNOWN; @@ -2587,10 +2586,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); - user_abbr_hlattr = get_user_highlight_attr(user_abbr_hlname); + extra_hl[0] = get_user_highlight_attr(user_abbr_hlname); user_kind_hlname = tv_dict_get_string(tv->vval.v_dict, "kind_hlgroup", false); - user_kind_hlattr = get_user_highlight_attr(user_kind_hlname); + extra_hl[1] = get_user_highlight_attr(user_kind_hlname); tv_dict_get_tv(tv->vval.v_dict, "user_data", &user_data); @@ -2613,8 +2612,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, - user_abbr_hlattr, user_kind_hlattr); + &user_data, dir, flags, dup, extra_hl); if (status != OK) { tv_clear(&user_data); } @@ -2707,7 +2705,7 @@ static void set_completion(colnr_T startcol, list_T *list) flags |= CP_ICASE; } if (ins_compl_add(compl_orig_text, -1, NULL, NULL, false, NULL, 0, - flags | CP_FAST, false, -1, -1) != OK) { + flags | CP_FAST, false, NULL) != OK) { return; } @@ -3452,7 +3450,7 @@ static void get_next_bufname_token(void) char *tail = path_tail(b->b_sfname); if (strncmp(tail, compl_orig_text, strlen(compl_orig_text)) == 0) { ins_compl_add(tail, (int)strlen(tail), NULL, NULL, false, NULL, 0, - p_ic ? CP_ICASE : 0, false, -1, -1); + p_ic ? CP_ICASE : 0, false, NULL); } } } @@ -4490,7 +4488,7 @@ static int ins_compl_start(void) flags |= CP_ICASE; } if (ins_compl_add(compl_orig_text, -1, NULL, NULL, false, NULL, 0, - flags, false, -1, -1) != OK) { + flags, false, NULL) != OK) { XFREE_CLEAR(compl_pattern); compl_patternlen = 0; XFREE_CLEAR(compl_orig_text); -- cgit From d512479115296a2df246ef7afbfa55f057fecae2 Mon Sep 17 00:00:00 2001 From: glepnir Date: Thu, 28 Nov 2024 14:34:38 +0800 Subject: 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 --- src/nvim/insexpand.c | 145 ++++++++++++++++++++++++++------------------------- 1 file changed, 75 insertions(+), 70 deletions(-) (limited to 'src/nvim') 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); } -- cgit From 1af1e918d30c062dfcb7d4ce2f4cfbca1d11e2ab Mon Sep 17 00:00:00 2001 From: glepnir Date: Sat, 30 Nov 2024 18:24:31 +0800 Subject: vim-patch:9.1.0896: completion list wrong after v9.1.0891 Problem: completion list wrong after v9.1.0891 Solution: update compl_mach_array after leader change (glepnir) compl_shown_match update not correct after refactoring in v9.1.0891 Unfortunately, this regressed what item is selected after leader change. So generate compl_match_array before updating compl_shown_match range, and split generate compl_match_array into range match_head fixes: https://github.com/vim/vim/issues/16128 closes: https://github.com/vim/vim/pull/16129 https://github.com/vim/vim/commit/a49c077a883b2566882df9069385ed1e1277ca64 --- src/nvim/insexpand.c | 136 +++++++++++++++++++++++---------------------------- 1 file changed, 62 insertions(+), 74 deletions(-) (limited to 'src/nvim') diff --git a/src/nvim/insexpand.c b/src/nvim/insexpand.c index 6a45a06fb9..820647df97 100644 --- a/src/nvim/insexpand.c +++ b/src/nvim/insexpand.c @@ -1176,6 +1176,20 @@ static int ins_compl_build_pum(void) 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; + + // If the current match is the original text don't find the first + // match after it, don't highlight anything. + bool shown_match_ok = match_at_original_text(compl_shown_match); + + if (strequal(compl_leader, compl_orig_text) && !shown_match_ok) { + compl_shown_match = compl_no_select ? compl_first_match : compl_first_match->cp_next; + } + + bool did_find_shown_match = false; + compl_T *shown_compl = NULL; + int i = 0; + int cur = -1; + do { // When 'completeopt' contains "fuzzy" and leader is not NULL or empty, // set the cp_score for later comparisons. @@ -1194,6 +1208,53 @@ static int ins_compl_build_pum(void) match_tail->cp_match_next = comp; } match_tail = comp; + 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; + } + } + if (!shown_match_ok && comp == compl_shown_match && !compl_no_select) { + cur = i; + shown_match_ok = true; + } + } + i++; + } + + if (comp == compl_shown_match && !compl_fuzzy_match) { + did_find_shown_match = true; + // When the original text is the shown match don't set + // compl_shown_match. + if (match_at_original_text(comp)) { + shown_match_ok = true; + } + if (!shown_match_ok && shown_compl != NULL) { + // The shown match isn't displayed, set it to the + // previously displayed match. + compl_shown_match = shown_compl; + shown_match_ok = true; + } } comp = comp->cp_next; } while (comp != NULL && !is_first_match(comp)); @@ -1205,65 +1266,9 @@ static int ins_compl_build_pum(void) assert(compl_match_arraysize >= 0); compl_match_array = xcalloc((size_t)compl_match_arraysize, sizeof(pumitem_T)); - // If the current match is the original text don't find the first - // match after it, don't highlight anything. - bool shown_match_ok = match_at_original_text(compl_shown_match); - - if (strequal(compl_leader, compl_orig_text) && !shown_match_ok) { - compl_shown_match = compl_no_select ? compl_first_match : compl_first_match->cp_next; - } - - compl_T *shown_compl = NULL; - bool did_find_shown_match = match_head == match_tail ? true : false; - int cur = -1; - int i = 0; + i = 0; 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; - } - } - - 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 (comp->cp_text[CPT_ABBR] != NULL) { compl_match_array[i].pum_text = comp->cp_text[CPT_ABBR]; } else { @@ -1279,23 +1284,6 @@ static int ins_compl_build_pum(void) } else { compl_match_array[i++].pum_extra = comp->cp_fname; } - - if (comp == compl_shown_match && !compl_fuzzy_match) { - did_find_shown_match = true; - - // When the original text is the shown match don't set - // compl_shown_match. - if (match_at_original_text(comp)) { - shown_match_ok = true; - } - - if (!shown_match_ok && shown_compl != NULL) { - // The shown match isn't displayed, set it to the - // previously displayed match. - compl_shown_match = shown_compl; - shown_match_ok = true; - } - } compl_T *match_next = comp->cp_match_next; comp->cp_match_next = NULL; comp = match_next; -- cgit