From 98f2df931ad8657f21124d8a6024967c5997fc99 Mon Sep 17 00:00:00 2001 From: Lewis Russell Date: Mon, 6 Mar 2023 16:10:04 +0000 Subject: fix(diff): add NULL check --- src/nvim/linematch.c | 3 +++ 1 file changed, 3 insertions(+) (limited to 'src/nvim/linematch.c') diff --git a/src/nvim/linematch.c b/src/nvim/linematch.c index a9dac40731..a15f41d9a8 100644 --- a/src/nvim/linematch.c +++ b/src/nvim/linematch.c @@ -161,6 +161,9 @@ void fastforward_buf_to_lnum(const char **s, long lnum) { for (long i = 0; i < lnum - 1; i++) { *s = strchr(*s, '\n'); + if (!*s) { + return; + } (*s)++; } } -- cgit From f5530bf566f6617565b5c1f5d1a9acc964199c93 Mon Sep 17 00:00:00 2001 From: Andreas Schneider Date: Fri, 21 Apr 2023 11:15:20 +0200 Subject: fix(linematch): initialize array MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit gsrc/nvim/linematch.c: In function ‘try_possible_paths’: gsrc/nvim/linematch.c:204:35: warning: ‘from_vals’ may be used uninitialized [-Wmaybe-uninitialized] 204 | size_t unwrapped_idx_from = unwrap_indexes(from_vals, diff_len, ndiffs); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --- src/nvim/linematch.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/nvim/linematch.c') diff --git a/src/nvim/linematch.c b/src/nvim/linematch.c index a15f41d9a8..7bde6bb121 100644 --- a/src/nvim/linematch.c +++ b/src/nvim/linematch.c @@ -186,7 +186,7 @@ static void try_possible_paths(const int *df_iters, const size_t *paths, const i { if (path_idx == npaths) { if ((*choice) > 0) { - int from_vals[LN_MAX_BUFS]; + int from_vals[LN_MAX_BUFS] = { 0 }; const int *to_vals = df_iters; const char *current_lines[LN_MAX_BUFS]; for (size_t k = 0; k < ndiffs; k++) { -- cgit From 0381f5af5bdc504f92be35dd89ac1328096eb8e6 Mon Sep 17 00:00:00 2001 From: Jonathon <32371757+jwhite510@users.noreply.github.com> Date: Wed, 7 Jun 2023 08:29:23 -0400 Subject: feat(diff): grouping optimization for linematch algorithm --- src/nvim/linematch.c | 117 +++++++++++++++++++++++++++++---------------------- 1 file changed, 67 insertions(+), 50 deletions(-) (limited to 'src/nvim/linematch.c') diff --git a/src/nvim/linematch.c b/src/nvim/linematch.c index 7bde6bb121..e22cc2d9a1 100644 --- a/src/nvim/linematch.c +++ b/src/nvim/linematch.c @@ -2,6 +2,7 @@ // it. PVS-Studio Static Code Analyzer for C, C++ and C#: http://www.viva64.com #include +#include #include #include #include @@ -10,14 +11,19 @@ #include "nvim/macros.h" #include "nvim/memory.h" +#define LN_MAX_BUFS 8 +#define LN_DECISION_MAX 255 // pow(2, LN_MAX_BUFS(8)) - 1 = 255 + // struct for running the diff linematch algorithm -typedef struct { - int *df_decision; // to keep track of this path traveled +typedef struct diffcmppath_S diffcmppath_T; +struct diffcmppath_S { int df_lev_score; // to keep track of the total score of this path - size_t df_path_idx; // current index of this path -} diffcmppath_T; - -#define LN_MAX_BUFS 8 + size_t df_path_n; // current index of this path + int df_choice_mem[LN_DECISION_MAX + 1]; + int df_choice[LN_DECISION_MAX]; + diffcmppath_T *df_decision[LN_DECISION_MAX]; // to keep track of this path traveled + size_t df_optimal_choice; +}; #ifdef INCLUDE_GENERATED_DECLARATIONS # include "linematch.c.generated.h" @@ -64,26 +70,6 @@ static int matching_chars_iwhite(const char *s1, const char *s2) return matching; } -/// update the path of a point in the diff linematch algorithm -/// @param diffcmppath -/// @param score -/// @param to -/// @param from -/// @param choice -static void update_path_flat(diffcmppath_T *diffcmppath, int score, size_t to, size_t from, - const int choice) -{ - size_t path_idx = diffcmppath[from].df_path_idx; - - for (size_t k = 0; k < path_idx; k++) { - diffcmppath[to].df_decision[k] = diffcmppath[from].df_decision[k]; - } - - diffcmppath[to].df_decision[path_idx] = choice; - diffcmppath[to].df_lev_score = score; - diffcmppath[to].df_path_idx = path_idx + 1; -} - #define MATCH_CHAR_MAX_LEN 800 /// Return matching characters between "s1" and "s2" whilst respecting sequence order. @@ -206,17 +192,14 @@ static void try_possible_paths(const int *df_iters, const size_t *paths, const i int matched_chars = count_n_matched_chars(current_lines, ndiffs, iwhite); int score = diffcmppath[unwrapped_idx_from].df_lev_score + matched_chars; if (score > diffcmppath[unwrapped_idx_to].df_lev_score) { - update_path_flat(diffcmppath, score, unwrapped_idx_to, unwrapped_idx_from, *choice); - } - } else { - // initialize the 0, 0, 0 ... choice - size_t i = 0; - while (i < ndiffs && df_iters[i] == 0) { - i++; - if (i == ndiffs) { - diffcmppath[0].df_lev_score = 0; - diffcmppath[0].df_path_idx = 0; - } + diffcmppath[unwrapped_idx_to].df_path_n = 1; + diffcmppath[unwrapped_idx_to].df_decision[0] = &diffcmppath[unwrapped_idx_from]; + diffcmppath[unwrapped_idx_to].df_choice[0] = *choice; + diffcmppath[unwrapped_idx_to].df_lev_score = score; + } else if (score == diffcmppath[unwrapped_idx_to].df_lev_score) { + size_t k = diffcmppath[unwrapped_idx_to].df_path_n++; + diffcmppath[unwrapped_idx_to].df_decision[k] = &diffcmppath[unwrapped_idx_from]; + diffcmppath[unwrapped_idx_to].df_choice[k] = *choice; } } return; @@ -245,8 +228,7 @@ static size_t unwrap_indexes(const int *values, const int *diff_len, const size_ for (size_t k = 0; k < ndiffs; k++) { num_unwrap_scalar /= (size_t)diff_len[k] + 1; - // (k == 0) space optimization - int n = k == 0 ? values[k] % 2 : values[k]; + int n = values[k]; path_idx += num_unwrap_scalar * (size_t)n; } return path_idx; @@ -354,7 +336,7 @@ size_t linematch_nbuffers(const char **diff_blk, const int *diff_len, const size size_t memsize_decisions = 0; for (size_t i = 0; i < ndiffs; i++) { assert(diff_len[i] >= 0); - memsize *= i == 0 ? 2 : (size_t)(diff_len[i] + 1); + memsize *= (size_t)(diff_len[i] + 1); memsize_decisions += (size_t)diff_len[i]; } @@ -362,7 +344,11 @@ size_t linematch_nbuffers(const char **diff_blk, const int *diff_len, const size diffcmppath_T *diffcmppath = xmalloc(sizeof(diffcmppath_T) * memsize); // allocate memory here for (size_t i = 0; i < memsize; i++) { - diffcmppath[i].df_decision = xmalloc(memsize_decisions * sizeof(int)); + diffcmppath[i].df_lev_score = 0; + diffcmppath[i].df_path_n = 0; + for (size_t j = 0; j < (size_t)pow(2, (double)ndiffs); j++) { + diffcmppath[i].df_choice_mem[j] = -1; + } } // memory for avoiding repetitive calculations of score @@ -370,18 +356,49 @@ size_t linematch_nbuffers(const char **diff_blk, const int *diff_len, const size populate_tensor(df_iters, 0, diffcmppath, diff_len, ndiffs, diff_blk, iwhite); const size_t u = unwrap_indexes(diff_len, diff_len, ndiffs); - const size_t best_path_idx = diffcmppath[u].df_path_idx; - const int *best_path_decisions = diffcmppath[u].df_decision; + diffcmppath_T *startNode = &diffcmppath[u]; - *decisions = xmalloc(sizeof(int) * best_path_idx); - for (size_t i = 0; i < best_path_idx; i++) { - (*decisions)[i] = best_path_decisions[i]; + *decisions = xmalloc(sizeof(int) * memsize_decisions); + size_t n_optimal = 0; + test_charmatch_paths(startNode, 0); + while (startNode->df_path_n > 0) { + size_t j = startNode->df_optimal_choice; + (*decisions)[n_optimal++] = startNode->df_choice[j]; + startNode = startNode->df_decision[j]; } - - for (size_t i = 0; i < memsize; i++) { - xfree(diffcmppath[i].df_decision); + // reverse array + for (size_t i = 0; i < (n_optimal / 2); i++) { + int tmp = (*decisions)[i]; + (*decisions)[i] = (*decisions)[n_optimal - 1 - i]; + (*decisions)[n_optimal - 1 - i] = tmp; } + xfree(diffcmppath); - return best_path_idx; + return n_optimal; +} + +// returns the minimum amount of path changes from start to end +static size_t test_charmatch_paths(diffcmppath_T *node, int lastdecision) +{ + // memoization + if (node->df_choice_mem[lastdecision] == -1) { + if (node->df_path_n == 0) { + // we have reached the end of the tree + node->df_choice_mem[lastdecision] = 0; + } else { + size_t minimum_turns = SIZE_MAX; // the minimum amount of turns required to reach the end + for (size_t i = 0; i < node->df_path_n; i++) { + // recurse + size_t t = test_charmatch_paths(node->df_decision[i], node->df_choice[i]) + + (lastdecision != node->df_choice[i] ? 1 : 0); + if (t < minimum_turns) { + node->df_optimal_choice = i; + minimum_turns = t; + } + } + node->df_choice_mem[lastdecision] = (int)minimum_turns; + } + } + return (size_t)node->df_choice_mem[lastdecision]; } -- cgit From cf8b2c0e74fd5e723b0c15c2ce84e6900fd322d3 Mon Sep 17 00:00:00 2001 From: zeertzjq Date: Sat, 30 Sep 2023 12:05:28 +0800 Subject: build(iwyu): add a few more _defs.h mappings (#25435) --- src/nvim/linematch.c | 1 + 1 file changed, 1 insertion(+) (limited to 'src/nvim/linematch.c') diff --git a/src/nvim/linematch.c b/src/nvim/linematch.c index e22cc2d9a1..897a263bf2 100644 --- a/src/nvim/linematch.c +++ b/src/nvim/linematch.c @@ -5,6 +5,7 @@ #include #include #include +#include #include #include "nvim/linematch.h" -- cgit From 8e932480f61d6101bf8bea1abc07ed93826221fd Mon Sep 17 00:00:00 2001 From: dundargoc Date: Fri, 29 Sep 2023 14:58:48 +0200 Subject: refactor: the long goodbye long is 32 bits on windows, while it is 64 bits on other architectures. This makes the type suboptimal for a codebase meant to be cross-platform. Replace it with more appropriate integer types. --- src/nvim/linematch.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/nvim/linematch.c') diff --git a/src/nvim/linematch.c b/src/nvim/linematch.c index 897a263bf2..01c035a4dd 100644 --- a/src/nvim/linematch.c +++ b/src/nvim/linematch.c @@ -144,9 +144,9 @@ static int count_n_matched_chars(const char **sp, const size_t n, bool iwhite) return matched_chars; } -void fastforward_buf_to_lnum(const char **s, long lnum) +void fastforward_buf_to_lnum(const char **s, linenr_T lnum) { - for (long i = 0; i < lnum - 1; i++) { + for (int i = 0; i < lnum - 1; i++) { *s = strchr(*s, '\n'); if (!*s) { return; -- cgit From 353a4be7e84fdc101318215bdcc8a7e780d737fe Mon Sep 17 00:00:00 2001 From: dundargoc Date: Sun, 12 Nov 2023 13:13:58 +0100 Subject: build: remove PVS We already have an extensive suite of static analysis tools we use, which causes a fair bit of redundancy as we get duplicate warnings. PVS is also prone to give false warnings which creates a lot of work to identify and disable. --- src/nvim/linematch.c | 3 --- 1 file changed, 3 deletions(-) (limited to 'src/nvim/linematch.c') diff --git a/src/nvim/linematch.c b/src/nvim/linematch.c index 01c035a4dd..1524731fab 100644 --- a/src/nvim/linematch.c +++ b/src/nvim/linematch.c @@ -1,6 +1,3 @@ -// This is an open source non-commercial project. Dear PVS-Studio, please check -// it. PVS-Studio Static Code Analyzer for C, C++ and C#: http://www.viva64.com - #include #include #include -- cgit From bb4b4576e384c71890b4df4fa4f1ae76fad3a59d Mon Sep 17 00:00:00 2001 From: zeertzjq Date: Thu, 16 Nov 2023 10:55:54 +0800 Subject: refactor: iwyu (#26062) --- src/nvim/linematch.c | 1 + 1 file changed, 1 insertion(+) (limited to 'src/nvim/linematch.c') diff --git a/src/nvim/linematch.c b/src/nvim/linematch.c index 1524731fab..d835bd5dc1 100644 --- a/src/nvim/linematch.c +++ b/src/nvim/linematch.c @@ -8,6 +8,7 @@ #include "nvim/linematch.h" #include "nvim/macros.h" #include "nvim/memory.h" +#include "nvim/pos.h" #define LN_MAX_BUFS 8 #define LN_DECISION_MAX 255 // pow(2, LN_MAX_BUFS(8)) - 1 = 255 -- cgit From f4aedbae4cb1f206f5b7c6142697b71dd473059b Mon Sep 17 00:00:00 2001 From: dundargoc Date: Mon, 27 Nov 2023 18:39:38 +0100 Subject: build(IWYU): fix includes for undo_defs.h --- src/nvim/linematch.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/nvim/linematch.c') diff --git a/src/nvim/linematch.c b/src/nvim/linematch.c index d835bd5dc1..fca62cfcc8 100644 --- a/src/nvim/linematch.c +++ b/src/nvim/linematch.c @@ -8,7 +8,7 @@ #include "nvim/linematch.h" #include "nvim/macros.h" #include "nvim/memory.h" -#include "nvim/pos.h" +#include "nvim/pos_defs.h" #define LN_MAX_BUFS 8 #define LN_DECISION_MAX 255 // pow(2, LN_MAX_BUFS(8)) - 1 = 255 -- cgit From 79b6ff28ad1204fbb4199b9092f5c578d88cb28e Mon Sep 17 00:00:00 2001 From: dundargoc Date: Tue, 28 Nov 2023 20:31:00 +0100 Subject: refactor: fix headers with IWYU --- src/nvim/linematch.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/nvim/linematch.c') diff --git a/src/nvim/linematch.c b/src/nvim/linematch.c index fca62cfcc8..c34b303193 100644 --- a/src/nvim/linematch.c +++ b/src/nvim/linematch.c @@ -6,7 +6,7 @@ #include #include "nvim/linematch.h" -#include "nvim/macros.h" +#include "nvim/macros_defs.h" #include "nvim/memory.h" #include "nvim/pos_defs.h" -- cgit