# JGIT: discuss: diff/patch implementation 16 messages from 2008-11-10 to 2008-11-11. Participants: Francis Galiegue, Robin Rosenberg, Johannes Schindelin, Junio C Hamano, Shawn O. Pearce, Rogan Dawes, Raimund Bauer, Sverre Rabbelier. Thread: https://gitlist.dev/t/16249 ## Francis Galiegue, 2008-11-10 14:22 Subject: JGIT: discuss: diff/patch implementation Message-ID: <200811101522.13558.fg@one2team.net> URL: https://gitlist.dev/e/200811101522.13558.fg%40one2team.net ``` 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 ``` ## Robin Rosenberg, 2008-11-10 15:56 Subject: Re: JGIT: discuss: diff/patch implementation Message-ID: <200811101656.35887.robin.rosenberg@dewire.com> URL: https://gitlist.dev/e/200811101656.35887.robin.rosenberg%40dewire.com In-Reply-To: <200811101522.13558.fg@one2team.net> ``` 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 ``` ## Francis Galiegue, 2008-11-10 16:16 Subject: Re: JGIT: discuss: diff/patch implementation Message-ID: <200811101716.29029.fg@one2team.net> URL: https://gitlist.dev/e/200811101716.29029.fg%40one2team.net In-Reply-To: <200811101656.35887.robin.rosenberg@dewire.com> ``` Le Monday 10 November 2008 16:56:35 Robin Rosenberg, vous avez écrit : [...] > > > > 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 ``` ## Robin Rosenberg, 2008-11-10 16:59 Subject: Re: JGIT: discuss: diff/patch implementation Message-ID: <200811101759.03864.robin.rosenberg@dewire.com> URL: https://gitlist.dev/e/200811101759.03864.robin.rosenberg%40dewire.com In-Reply-To: <200811101716.29029.fg@one2team.net> ``` måndag 10 november 2008 17:16:28 skrev Francis Galiegue: > Le Monday 10 November 2008 16:56:35 Robin Rosenberg, vous avez écrit : > [...] > > > > > > 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 ``` ## Francis Galiegue, 2008-11-10 18:11 Subject: Re: JGIT: discuss: diff/patch implementation Message-ID: <200811101911.19603.fg@one2team.net> URL: https://gitlist.dev/e/200811101911.19603.fg%40one2team.net In-Reply-To: <200811101759.03864.robin.rosenberg@dewire.com> ``` Le Monday 10 November 2008 17:59:03 Robin Rosenberg, vous avez écrit : [Sorry if this is offtopic for the git mailing list...] > > > > 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 ``` ## Johannes Schindelin, 2008-11-10 19:46 Subject: Re: JGIT: discuss: diff/patch implementation Message-ID: URL: https://gitlist.dev/e/alpine.DEB.1.00.0811102030180.30769%40pacific.mpi-cbg.de In-Reply-To: <200811101522.13558.fg@one2team.net> ``` 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 ``` ## Francis Galiegue, 2008-11-10 20:21 Subject: Re: JGIT: discuss: diff/patch implementation Message-ID: <200811102121.17835.fg@one2team.net> URL: https://gitlist.dev/e/200811102121.17835.fg%40one2team.net In-Reply-To: ``` Le Monday 10 November 2008 20:46:02 Johannes Schindelin, vous avez écrit : > 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 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 ``` ## Junio C Hamano, 2008-11-10 20:50 Subject: Re: JGIT: discuss: diff/patch implementation Message-ID: <7v63mv5mro.fsf@gitster.siamese.dyndns.org> URL: https://gitlist.dev/e/7v63mv5mro.fsf%40gitster.siamese.dyndns.org In-Reply-To: <200811101522.13558.fg@one2team.net> ``` Francis Galiegue writes: > A very nice git feature, without even going as far as merges, is the cherry > pick feature. I thought cherry-picking needs to be done in terms of 3-way merge, not diff piped to patch, for correctness's sake. ``` ## Shawn O. Pearce, 2008-11-10 20:52 Subject: Re: JGIT: discuss: diff/patch implementation Message-ID: <20081110205242.GH2932@spearce.org> URL: https://gitlist.dev/e/20081110205242.GH2932%40spearce.org In-Reply-To: <7v63mv5mro.fsf@gitster.siamese.dyndns.org> ``` Junio C Hamano wrote: > Francis Galiegue writes: > > > A very nice git feature, without even going as far as merges, is the cherry > > pick feature. > > I thought cherry-picking needs to be done in terms of 3-way merge, not > diff piped to patch, for correctness's sake. Yea, the 3-way merge cherry-pick is better. But in a pinch you can (usually) get correct results from a "diff | patch" pipeline. Of course that doesn't always work, resulting in patches that don't apply cleanly, or worse, that apply at the wrong place silently. -- Shawn. ``` ## Francis Galiegue, 2008-11-10 21:31 Subject: Re: JGIT: discuss: diff/patch implementation Message-ID: <200811102231.31263.fg@one2team.net> URL: https://gitlist.dev/e/200811102231.31263.fg%40one2team.net In-Reply-To: <20081110205242.GH2932@spearce.org> ``` Le Monday 10 November 2008 21:52:42 Shawn O. Pearce, vous avez écrit : > Junio C Hamano wrote: > > Francis Galiegue writes: > > > A very nice git feature, without even going as far as merges, is the > > > cherry pick feature. > > > > I thought cherry-picking needs to be done in terms of 3-way merge, not > > diff piped to patch, for correctness's sake. > > Yea, the 3-way merge cherry-pick is better. But in a pinch you > can (usually) get correct results from a "diff | patch" pipeline. > Of course that doesn't always work, resulting in patches that don't > apply cleanly, or worse, that apply at the wrong place silently. Well, in this case, I'd say it's a case of a bottle being "half full" or "half empty". The availability of even a simple diff|patch in jgit, and its being available in egit, would generally be seen as a "half full" bottle, and would, imho, GREATLY increase the appeal factor of egit, all the more that you have plenty of undo/redo ability in Eclipse... And, dare I say it, of git in general as an SCM to be used in many environments where Eclipse is the de facto IDE. I know, I may sound irritating, but... -- fge ``` ## Johannes Schindelin, 2008-11-10 23:37 Subject: Re: JGIT: discuss: diff/patch implementation Message-ID: URL: https://gitlist.dev/e/alpine.DEB.1.00.0811110031510.30769%40pacific.mpi-cbg.de In-Reply-To: <7v63mv5mro.fsf@gitster.siamese.dyndns.org> ``` Hi, On Mon, 10 Nov 2008, Junio C Hamano wrote: > Francis Galiegue writes: > > > A very nice git feature, without even going as far as merges, is the > > cherry pick feature. > > I thought cherry-picking needs to be done in terms of 3-way merge, not > diff piped to patch, for correctness's sake. I haven't checked how RCS merge does it, but I know how xdiff/xmerge.c does it ;-) Basically, it takes the two diffs relative to the base file and works on the overlapping hunks (i.e. on hunks where the ranges in the base file overlap). So we need a diff algorithm very much if we were to imitate that code in JGit, which I very much plan to do. Ciao, Dscho ``` ## Rogan Dawes, 2008-11-11 07:27 Subject: Re: JGIT: discuss: diff/patch implementation Message-ID: <491933DF.3060307@dawes.za.net> URL: https://gitlist.dev/e/491933DF.3060307%40dawes.za.net In-Reply-To: <200811101522.13558.fg@one2team.net> ``` 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 ``` ## Raimund Bauer, 2008-11-11 10:06 Subject: Re: JGIT: discuss: diff/patch implementation Message-ID: <1226398000.7541.11.camel@minastirith.xtradesoft.lan> URL: https://gitlist.dev/e/1226398000.7541.11.camel%40minastirith.xtradesoft.lan In-Reply-To: <7v63mv5mro.fsf@gitster.siamese.dyndns.org> ``` On Mon, 2008-11-10 at 12:50 -0800, Junio C Hamano wrote: > Francis Galiegue writes: > > > A very nice git feature, without even going as far as merges, is the cherry > > pick feature. > > I thought cherry-picking needs to be done in terms of 3-way merge, not > diff piped to patch, for correctness's sake. What about http://sourceforge.net/projects/jlibdiff ? Maybe a bit old, but claims to have diff3 and is under LGPL. best regards, Ray ``` ## Shawn O. Pearce, 2008-11-11 17:13 Subject: Re: JGIT: discuss: diff/patch implementation Message-ID: <20081111171342.GJ2932@spearce.org> URL: https://gitlist.dev/e/20081111171342.GJ2932%40spearce.org In-Reply-To: <491933DF.3060307@dawes.za.net> ``` Rogan Dawes wrote: > Francis Galiegue wrote: >> >> 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. ``` ## Shawn O. Pearce, 2008-11-11 17:18 Subject: Re: JGIT: discuss: diff/patch implementation Message-ID: <20081111171816.GK2932@spearce.org> URL: https://gitlist.dev/e/20081111171816.GK2932%40spearce.org In-Reply-To: <1226398000.7541.11.camel@minastirith.xtradesoft.lan> ``` Raimund Bauer wrote: > On Mon, 2008-11-10 at 12:50 -0800, Junio C Hamano wrote: > > Francis Galiegue writes: > > > > > A very nice git feature, without even going as far as merges, is the cherry > > > pick feature. > > > > I thought cherry-picking needs to be done in terms of 3-way merge, not > > diff piped to patch, for correctness's sake. > > What about http://sourceforge.net/projects/jlibdiff ? > Maybe a bit old, but claims to have diff3 and is under LGPL. I hadn't looked at that library before. We've generally tried to avoid LGPL diff implementations, but partly because any I found were ports from a GPL C based code tree to Java, but then the guy who did the port went and changed the license to LGPL. Slightly dubious if you ask me. ;-) LGPL plays nicely with BSD, especially in Java where runtime relinking is possible. But it does screw with jgit.pgm's little idea of "shove *everything* into a single shell script", as then its not runtime re-linkable by the user. I don't know how the Eclipse foundation feels about distributing LGPL in the IDE. One of our major reasons for going with a BSD license on JGit was so the Eclipse Git team provider plugin could be distributed alongside the CVS team provider, as part of the basic IDE team provider package. We're clearly not ready for that wide of a distribution, but it was a goal Robin and I set out for the project. -- Shawn. ``` ## Sverre Rabbelier, 2008-11-11 17:31 Subject: Re: JGIT: discuss: diff/patch implementation Message-ID: URL: https://gitlist.dev/e/bd6139dc0811110931g6a04335dp925dd09f2afaee03%40mail.gmail.com In-Reply-To: <20081111171816.GK2932@spearce.org> ``` On Tue, Nov 11, 2008 at 18:18, Shawn O. Pearce wrote: > I don't know how the Eclipse foundation feels about distributing > LGPL in the IDE. One of our major reasons for going with a BSD > license on JGit was so the Eclipse Git team provider plugin could be > distributed alongside the CVS team provider, as part of the basic IDE > team provider package. We're clearly not ready for that wide of a > distribution, but it was a goal Robin and I set out for the project. Why not keep that as a goall? For now, you can stick with one of the existing LGPL implementations, later, when you want to have JGit distributed with Eclipse, you (or Johanness Schindelin when he has the time) write up your own Java version of it and license it BSD -- Cheers, Sverre Rabbelier ```