JGIT: discuss: diff/patch implementation

Hello,

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.

I found this:

http://code.google.com/p/google-diff-match-patch

Its license is the Apache 2.0 license. It implements the same algorithm than 
git's internal diff engine ("An O(ND) Difference Algorithm and its 
Variations", by Eugene Myers), and as far as I can tell so far (IANAL, far 
from it), it is compatible with JGit's current license.

Could this be a viable candidate?

-- 
fge

måndag 10 november 2008 15:22:13 skrev Francis Galiegue:

Hello,

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.

I found this:

http://code.google.com/p/google-diff-match-patch

Its license is the Apache 2.0 license. It implements the same algorithm than 
git's internal diff engine ("An O(ND) Difference Algorithm and its 
Variations", by Eugene Myers), and as far as I can tell so far (IANAL, far 
from it), it is compatible with JGit's current license.

Could this be a viable candidate?

Our approach was to do just that, for the very reasons you mention. 
I'll have a look. Thanks for doing some research for us. That project was
unknown to me..

-- robin

Le Monday 10 November 2008 16:56:35 Robin Rosenberg, vous avez écrit :
[...]

quoted

I found this:

http://code.google.com/p/google-diff-match-patch

Its license is the Apache 2.0 license. It implements the same algorithm
than git's internal diff engine ("An O(ND) Difference Algorithm and its
Variations", by Eugene Myers), and as far as I can tell so far (IANAL,
far from it), it is compatible with JGit's current license.

Could this be a viable candidate?

Our approach was to do just that, for the very reasons you mention.
I'll have a look. Thanks for doing some research for us. That project was
unknown to me..

-- robin

Well, this API has a problem from the get go, since it does... Char by char 
comparison. Ouch.

I'll try and hack it so that it does line by line, but given my Java skills, 
uh...

-- 
fge

måndag 10 november 2008 17:16:28 skrev Francis Galiegue:

Le Monday 10 November 2008 16:56:35 Robin Rosenberg, vous avez écrit :
[...]

quoted

quoted

I found this:

http://code.google.com/p/google-diff-match-patch

Its license is the Apache 2.0 license. It implements the same algorithm
than git's internal diff engine ("An O(ND) Difference Algorithm and its
Variations", by Eugene Myers), and as far as I can tell so far (IANAL,
far from it), it is compatible with JGit's current license.

Could this be a viable candidate?

Our approach was to do just that, for the very reasons you mention.
I'll have a look. Thanks for doing some research for us. That project was
unknown to me..

-- robin

Well, this API has a problem from the get go, since it does... Char by char 
comparison. Ouch.

I'll try and hack it so that it does line by line, but given my Java skills, 
uh...

We might want a byte-oriented version. Converting to char first is way 
too slow.

-- robin

Le Monday 10 November 2008 17:59:03 Robin Rosenberg, vous avez écrit :
[Sorry if this is offtopic for the git mailing list...]

quoted

Well, this API has a problem from the get go, since it does... Char by
char comparison. Ouch.

I'll try and hack it so that it does line by line, but given my Java
skills, uh...

We might want a byte-oriented version. Converting to char first is way
too slow.

Well, AFAICT, here is how the current git code detects whether a file is 
binary or not:

----
#define FIRST_FEW_BYTES 8000
int buffer_is_binary(const char *ptr, unsigned long size)
{
	if (FIRST_FEW_BYTES < size)
		size = FIRST_FEW_BYTES;
	return !!memchr(ptr, 0, size);
}
----

Easy enough to be coded in Java, hey, even I could do it :p

So, provided binary files are dealt with already, what penalty is left for 
Java to deal with?

-- 
fge

Hi,

On Mon, 10 Nov 2008, Francis Galiegue wrote:

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

Le Monday 10 November 2008 20:46:02 Johannes Schindelin, vous avez écrit :

Hi,

On Mon, 10 Nov 2008, Francis Galiegue wrote:

quoted

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 wasn't even thinking about this, honestly :p

Let's say that as far as IDE users are concerned, they do have disk space, and 
having the ability to cherry-pick is more of a priority than packs ;) Even a 
less efficient but "to the point" engine will be good enough for the time 
being, or at least, this is what I think.

I understand way too little about the algorithm myself to tell whether it's 
also efficient for such a purpose. Maybe it is...

-- 
fge

Francis Galiegue wrote:

Hello,

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.

Shouldn't Eclipse already *have* a diff/patch implementation, for its 
other "team work" plugins?

Rogan

Rogan Dawes [off-list ref] wrote:

Francis Galiegue wrote:

quoted

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.

Shouldn't Eclipse already *have* a diff/patch implementation, for its  
other "team work" plugins?

Err, uhm, sort of.

Eclipse has patch available as an internal API, but it is exposed
in the UI for any team provider (or no team provider at all) to
use to apply patches to a project in the workspace.

The team provider API assumes the VCS implementation has its own
diff, and therefore the diff implementation inside Eclipse is only
used for the native Compare view

I've dug around that part of the text compare plugin and its mostly
internal APIs, and mostly still low-level LCS generation from
arbitrary object input.  It doesn't seem well suited to producing
fast diffs of text.

Its under the EPL.  We could take the code and simplify it down,
but I think by that point we'd mostly just want to rewrite it, or
use a different library anyway.  At which point we wouldn't want
to bring in the EPL baggage if we can have a BSD implementation.

So yea, there's some implementation in there, but its not easy to
use or get to...

-- 
Shawn.