feat(diff): grouping optimization for linematch algorithm

2 files changed, 253 insertions, 50 deletions

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 <assert.h>
+#include <math.h>
 #include <stdbool.h>
 #include <stddef.h>
 #include <string.h>
@@ -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];
 }
diff --git a/test/functional/ui/linematch_spec.lua b/test/functional/ui/linematch_spec.lua
index 697677aa67..76197bc7e0 100644
--- a/test/functional/ui/linematch_spec.lua
+++ b/test/functional/ui/linematch_spec.lua
@@ -779,6 +779,192 @@ something
 
     end)
   end)
+  describe('setup a diff with 2 files and set linematch:30', function()
+    before_each(function()
+      feed(':set diffopt+=linematch:30<cr>')
+      local f1 = [[
+// abc d
+// d
+// d
+      ]]
+      local f2 = [[
+
+abc d
+d
+      ]]
+      write_file(fname, f1, false)
+      write_file(fname_2, f2, false)
+      reread()
+    end)
+
+    it('display results', function()
+      screen:expect([[
+      {1:  }{10:  1 }{4:^                                           }│{1:  }{10:    }{2:--------------------------------------------}|
+      {1:  }{10:  2 }{9:abc d                                      }│{1:  }{10:  1 }{8:// }{9:abc d                                    }|
+      {1:  }{10:  3 }{9:d                                          }│{1:  }{10:  2 }{8:// }{9:d                                        }|
+      {1:  }{10:    }{2:-------------------------------------------}│{1:  }{10:  3 }{4:// d                                        }|
+      {1:  }{10:  4 }                                           │{1:  }{10:  4 }                                            |
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {7:Xtest-functional-diff-screen-1.2                  }{3:Xtest-functional-diff-screen-1                    }|
+      :e                                                                                                  |
+      ]])
+    end)
+  end)
+  describe('setup a diff with 2 files and set linematch:30, with ignore white', function()
+    before_each(function()
+      feed(':set diffopt+=linematch:30<cr>:set diffopt+=iwhiteall<cr>')
+      local f1 = [[
+void testFunction () {
+  for (int i = 0; i < 10; i++) {
+    for (int j = 0; j < 10; j++) {
+    }
+  }
+}
+      ]]
+      local f2 = [[
+void testFunction () {
+  // for (int j = 0; j < 10; i++) {
+  // }
+}
+      ]]
+      write_file(fname, f1, false)
+      write_file(fname_2, f2, false)
+      reread()
+    end)
+
+    it('display results', function()
+      screen:expect([[
+      {1:  }{10:  1 }^void testFunction () {                     │{1:  }{10:  1 }void testFunction () {                      |
+      {1:  }{10:    }{2:-------------------------------------------}│{1:  }{10:  2 }{4:  for (int i = 0; i < 10; i++) {            }|
+      {1:  }{10:  2 }{9:  }{8:// for (int j = 0; j < 10; i}{9:++) {        }│{1:  }{10:  3 }{9:    }{8:for (int j = 0; j < 10; j}{9:++) {          }|
+      {1:  }{10:  3 }{9:  }{8:// }{9:}                                     }│{1:  }{10:  4 }{9:    }                                       }|
+      {1:  }{10:    }{2:-------------------------------------------}│{1:  }{10:  5 }{4:  }                                         }|
+      {1:  }{10:  4 }}                                          │{1:  }{10:  6 }}                                           |
+      {1:  }{10:  5 }                                           │{1:  }{10:  7 }                                            |
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {7:Xtest-functional-diff-screen-1.2                  }{3:Xtest-functional-diff-screen-1                    }|
+      :e                                                                                                  |
+      ]])
+    end)
+  end)
+  describe('a diff that would result in multiple groups before grouping optimization', function()
+    before_each(function()
+      feed(':set diffopt+=linematch:30<cr>')
+      local f1 = [[
+!A
+!B
+!C
+      ]]
+      local f2 = [[
+?Z
+?A
+?B
+?C
+?A
+?B
+?B
+?C
+      ]]
+      write_file(fname, f1, false)
+      write_file(fname_2, f2, false)
+      reread()
+    end)
+
+    it('display results', function()
+      screen:expect([[
+      {1:  }{10:  1 }{4:^?Z                                         }│{1:  }{10:    }{2:--------------------------------------------}|
+      {1:  }{10:  2 }{8:?}{9:A                                         }│{1:  }{10:  1 }{8:!}{9:A                                          }|
+      {1:  }{10:  3 }{8:?}{9:B                                         }│{1:  }{10:  2 }{8:!}{9:B                                          }|
+      {1:  }{10:  4 }{8:?}{9:C                                         }│{1:  }{10:  3 }{8:!}{9:C                                          }|
+      {1:  }{10:  5 }{4:?A                                         }│{1:  }{10:    }{2:--------------------------------------------}|
+      {1:  }{10:  6 }{4:?B                                         }│{1:  }{10:    }{2:--------------------------------------------}|
+      {1:  }{10:  7 }{4:?B                                         }│{1:  }{10:    }{2:--------------------------------------------}|
+      {1:  }{10:  8 }{4:?C                                         }│{1:  }{10:    }{2:--------------------------------------------}|
+      {1:  }{10:  9 }                                           │{1:  }{10:  4 }                                            |
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {7:Xtest-functional-diff-screen-1.2                  }{3:Xtest-functional-diff-screen-1                    }|
+      :e                                                                                                  |
+      ]])
+    end)
+  end)
+  describe('a diff that would result in multiple groups before grouping optimization', function()
+    before_each(function()
+      feed(':set diffopt+=linematch:30<cr>')
+      local f1 = [[
+!A
+!B
+!C
+      ]]
+      local f2 = [[
+?A
+?Z
+?B
+?C
+?A
+?B
+?C
+?C
+      ]]
+      write_file(fname, f1, false)
+      write_file(fname_2, f2, false)
+      reread()
+    end)
+
+    it('display results', function()
+      screen:expect([[
+      {1:  }{10:  1 }{4:^?A                                         }│{1:  }{10:    }{2:--------------------------------------------}|
+      {1:  }{10:  2 }{4:?Z                                         }│{1:  }{10:    }{2:--------------------------------------------}|
+      {1:  }{10:  3 }{4:?B                                         }│{1:  }{10:    }{2:--------------------------------------------}|
+      {1:  }{10:  4 }{4:?C                                         }│{1:  }{10:    }{2:--------------------------------------------}|
+      {1:  }{10:  5 }{8:?}{9:A                                         }│{1:  }{10:  1 }{8:!}{9:A                                          }|
+      {1:  }{10:  6 }{8:?}{9:B                                         }│{1:  }{10:  2 }{8:!}{9:B                                          }|
+      {1:  }{10:  7 }{8:?}{9:C                                         }│{1:  }{10:  3 }{8:!}{9:C                                          }|
+      {1:  }{10:  8 }{4:?C                                         }│{1:  }{10:    }{2:--------------------------------------------}|
+      {1:  }{10:  9 }                                           │{1:  }{10:  4 }                                            |
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {6:~                                                }│{6:~                                                 }|
+      {7:Xtest-functional-diff-screen-1.2                  }{3:Xtest-functional-diff-screen-1                    }|
+      :e                                                                                                  |
+      ]])
+    end)
+  end)
   describe('setup a diff with 2 files and set linematch:10', function()
     before_each(function()
       feed(':set diffopt+=linematch:10<cr>')