Re: JGIT: discuss: diff/patch implementation

From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: Nov 10, 2008, 19:46 UTC
Message-ID: <alpine.DEB.1.00.0811102030180.30769@pacific.mpi-cbg.de>
In-Reply-To: <200811101522.13558.fg@one2team.net>

Hi,

On Mon, 10 Nov 2008, Francis Galiegue wrote:

Show 7 quoted lines

> A very nice git feature, without even going as far as merges, is the 
> cherry pick feature.
> 
> For this to be doable from within the Eclipse Git plugin, a diff/patch 
> implementation needs to be found, in a license compatible with the 
> current JGit license (3-clause BSD, as far as I can tell). Or a new 
> implementation can be rewritten from scratch, of course.

Do not forget creating efficient packs. They also need an efficient diff engine.

> I found this:
> 
> http://code.google.com/p/google-diff-match-patch

Nice.

As was pointed out already, it is more meant to work on text than I'd like to, and it also seems to have cute DWIMery for HTML.

I did not find any implementation, so I started implementing my own version of Gene Myers' algorithm, with the plan to extend it with a patience diff option.

My code so far can generate a diff between two files, but does not use O(D) space (where D is the number of differences), but O(D^2), as I did not have enough time (a conference, and traveling around the world can do that to you).

Having looked at the source code of diff-patch-match, I admit that I do not understand enough of the algorithm with so little documentation, so I will continue my fun project.

Ciao, Dscho