source-1241995759.txt

   1 Working on jgit diff
   2
   3 Shawn did so many useful things that I use on a daily basis that I felt really
   4 awful when I realized just how _long_ I had promised to clean up that diff
   5 implementation I wrote for JGit.
   6
   7 Alas, it appears that the thing turned out to be almost a complete rewrite, as
   8 the original implementation walked the edit graph in a rather inefficient way.
   9
  10 A little background: Myers' algorithm to generate "an edit script" works on
  11 the ''edit graph'': imagine you have all lines of file ''A'' as columns and
  12 all lines of file ''B'' as rows, then the ''edit graph'' is a connection of
  13 the upper left corner to the lower right corner, containing only horizontal,
  14 vertical or diagonal elements, where diagonal elements are only allowed when
  15 the lines of both files agree at that point:
  16
  17 <pre>
  18  H E L L O , W O R L D
  19  ----
  20 L    \
  21       ---
  22 O        \
  23           ---
  24 W            \
  25               --------
  26 </pre>
  27
  28 The ''shortest'' edit path minimizes the number of non-diagonal elements.
  29
  30 Myers' idea is to develop forward and backward paths at the same time
  31 (increasing the number of non-diagonal elements uniformly), storing
  32 only the latest end points.  Once the paths meet, divide and conquer.
  33
  34 In theory, it would be quicker to store _all_ end points and then just
  35 reconstruct the shortest paths, alas, this takes way too much memory.
  36
  37 My first implementation did not remember start or end of the non-diagonal
  38 parts, and had to recurse way more often than really necessary (in the end,
  39 we will order the non-diagonal parts into horizontal and vertical parts
  40 anyway, so start and end are sufficient).
  41
  42 The current progress can be seen <a href=http://repo.or.cz/w/egit/dscho.git/>
  43 here</a>.