[bug-diffutils] Bug#664795: diffutils: diff: implement "Patience Diff" algorithm

[Samuel Bronson]

Package: diffutils
Version: 1:3.2-2
Severity: wishlist

Dear Maintainers,

I think it would be nice to have support for the "patience diff"
algorithm in GNU diff.

Git's xdiff/xpatience.c summarizes it well:

/*
 * The basic idea of patience diff is to find lines that are unique in
 * both files.  These are intuitively the ones that we want to see as
 * common lines.
 *
 * The maximal ordered sequence of such line pairs (where ordered means
 * that the order in the sequence agrees with the order of the lines in
 * both files) naturally defines an initial set of common lines.
 *
 * Now, the algorithm tries to extend the set of common lines by growing
 * the line ranges where the files have identical lines.
 *
 * Between those common lines, the patience diff algorithm is applied
 * recursively, until no unique line pairs can be found; these line ranges
 * are handled by the well-known Myers algorithm.
 */

The following resources might be helpful:

 * A short write-up in plain language:
   <http://alfedenzo.livejournal.com/170301.html>

 * An explanation of Patience's motivation (including links to
   pathological non-patience diffs) from the creator:
   <http://bramcohen.livejournal.com/73318.html>

 * The algorithm for which it is named:
   
<http://en.wikipedia.org/wiki/Patience_sorting#Algorithm_for_finding_a_longest_increasing_subsequence>

 * The original implementation, as part of Codeville:
   Get the source from <http://snapshot.debian.org/package/codeville>
   and look at Codeville/diff.py and Codeville/lcsmatch.py
   OR see:
   <https://github.com/SamB/debian-codeville/blob/master/Codeville/diff.py>
   <https://github.com/SamB/debian-codeville/blob/master/Codeville/lcsmatch.py>

 * The GNU Bazaar port of the Codeville code, which seems to be where it
   was decided to call this "Patience Diff":
   
<http://bazaar.launchpad.net/~bzr-pqm/bzr/bzr.dev/view/head:/bzrlib/patiencediff.py>
   
<http://bazaar.launchpad.net/~bzr-pqm/bzr/bzr.dev/view/head:/bzrlib/_patiencediff_py.py>
   
<http://bazaar.launchpad.net/~bzr-pqm/bzr/bzr.dev/view/head:/bzrlib/_patiencediff_c.c>

   - Mailing list archives for the relevant time period:
     <https://lists.ubuntu.com/archives/bazaar/2006q2/thread.html>

 * The Git implementation, xdiff/xpatience.c:
   <https://github.com/gitster/git/blob/master/xdiff/xpatience.c>

(Implementations are listed in chronological order.)

-- 
Hi! I'm a .signature virus! Copy me into your ~/.signature to help me spread!