[PATCH 0/3] Teach Git about the patience diff algorithm

Nothing fancy, really, just a straight-forward implementation of the heavily under-documented and under-analyzed paience diff algorithm.

One thing is a bit ugly: the libxdiff interface does not allow to calculate diffs of ranges of lines. So instead of reusing an initialized environment (with line hashes and all), the simple structure of mmfile_t is exploited to fake an mmfile_t of a file _part_, reusing the file's buffer.

And this mmfile_t pair gets a new environment, recalculating hashes and all.

Davide, I think it would be easier to refactor xdl_do_diff() to take line ranges, and use that interface both in xpatience.c and in xmerge.c. (Although I do not know if you took xmerge.c at all; you seemed a bit reluctant about it back when I sent it to you.)

For those interested in studying the code, I suggest starting with the short comment at the beginning of xpatience.c and then working yourself up from the end (i.e. xdl_do_patience_diff()).

It might be a good idea to think about using this code in our merging code once it is well reviewed and tested, as it might help a substantial number of otherwise non-trivial merge conflicts.

Oh, and the bash completions are so trivial I did not even bother to test them.

Happy new year.

Johannes Schindelin (3):
  Implement the patience diff algorithm
  Introduce the diff option '--patience'
  bash completions: Add the --patience option

 Documentation/diff-options.txt         |    3 +
 Makefile                               |    2 +-
 contrib/completion/git-completion.bash |    2 +
 diff.c                                 |    2 +
 t/t4033-diff-patience.sh               |  168 ++++++++++++++
 xdiff/xdiff.h                          |    1 +
 xdiff/xdiffi.c                         |    3 +
 xdiff/xdiffi.h                         |    2 +
 xdiff/xpatience.c                      |  374 ++++++++++++++++++++++++++++++++
 9 files changed, 556 insertions(+), 1 deletions(-)
 create mode 100755 t/t4033-diff-patience.sh
 create mode 100644 xdiff/xpatience.c