{"thread":{"id":"16249","subject":"JGIT: discuss: diff/patch implementation","startedAt":"2008-11-10T14:22:13Z","lastAt":"2008-11-11T17:31:13Z","messageCount":16,"participants":["Francis Galiegue","Robin Rosenberg","Johannes Schindelin","Junio C Hamano","Shawn O. Pearce","Rogan Dawes","Raimund Bauer","Sverre Rabbelier"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"95337","messageId":"200811101522.13558.fg@one2team.net","threadId":"16249","inReplyTo":null,"subject":"JGIT: discuss: diff/patch implementation","fromName":"Francis Galiegue","fromEmail":"fg@one2team.net","sentAt":"2008-11-10T14:22:13Z","receivedAt":"2008-11-10T14:22:13Z","isPatch":false,"sender":{"key":"fg@one2team.net","avatar":null},"body":"Hello,\n\nA very nice git feature, without even going as far as merges, is the cherry \npick feature.\n\nFor this to be doable from within the Eclipse Git plugin, a diff/patch \nimplementation needs to be found, in a license compatible with the current \nJGit license (3-clause BSD, as far as I can tell). Or a new implementation \ncan be rewritten from scratch, of course.\n\nI found this:\n\nhttp://code.google.com/p/google-diff-match-patch\n\nIts license is the Apache 2.0 license. It implements the same algorithm than \ngit's internal diff engine (\"An O(ND) Difference Algorithm and its \nVariations\", by Eugene Myers), and as far as I can tell so far (IANAL, far \nfrom it), it is compatible with JGit's current license.\n\nCould this be a viable candidate?\n\n-- \nfge\n"},{"id":"95340","messageId":"200811101656.35887.robin.rosenberg@dewire.com","threadId":"16249","inReplyTo":"200811101522.13558.fg@one2team.net","subject":"Re: JGIT: discuss: diff/patch implementation","fromName":"Robin Rosenberg","fromEmail":"robin.rosenberg@dewire.com","sentAt":"2008-11-10T15:56:35Z","receivedAt":"2008-11-10T15:56:35Z","isPatch":false,"sender":{"key":"robin.rosenberg@dewire.com","avatar":"https://avatars.githubusercontent.com/u/46357?v=4"},"body":"måndag 10 november 2008 15:22:13 skrev Francis Galiegue:\n> Hello,\n> \n> A very nice git feature, without even going as far as merges, is the cherry \n> pick feature.\n> \n> For this to be doable from within the Eclipse Git plugin, a diff/patch \n> implementation needs to be found, in a license compatible with the current \n> JGit license (3-clause BSD, as far as I can tell). Or a new implementation \n> can be rewritten from scratch, of course.\n> \n> I found this:\n> \n> http://code.google.com/p/google-diff-match-patch\n> \n> Its license is the Apache 2.0 license. It implements the same algorithm than \n> git's internal diff engine (\"An O(ND) Difference Algorithm and its \n> Variations\", by Eugene Myers), and as far as I can tell so far (IANAL, far \n> from it), it is compatible with JGit's current license.\n> \n> Could this be a viable candidate?\n\nOur approach was to do just that, for the very reasons you mention. \nI'll have a look. Thanks for doing some research for us. That project was\nunknown to me..\n\n-- robin\n"},{"id":"95343","messageId":"200811101716.29029.fg@one2team.net","threadId":"16249","inReplyTo":"200811101656.35887.robin.rosenberg@dewire.com","subject":"Re: JGIT: discuss: diff/patch implementation","fromName":"Francis Galiegue","fromEmail":"fg@one2team.net","sentAt":"2008-11-10T16:16:28Z","receivedAt":"2008-11-10T16:16:28Z","isPatch":false,"sender":{"key":"fg@one2team.net","avatar":null},"body":"Le Monday 10 November 2008 16:56:35 Robin Rosenberg, vous avez écrit :\n[...]\n> >\n> > I found this:\n> >\n> > http://code.google.com/p/google-diff-match-patch\n> >\n> > Its license is the Apache 2.0 license. It implements the same algorithm\n> > than git's internal diff engine (\"An O(ND) Difference Algorithm and its\n> > Variations\", by Eugene Myers), and as far as I can tell so far (IANAL,\n> > far from it), it is compatible with JGit's current license.\n> >\n> > Could this be a viable candidate?\n>\n> Our approach was to do just that, for the very reasons you mention.\n> I'll have a look. Thanks for doing some research for us. That project was\n> unknown to me..\n>\n> -- robin\n\nWell, this API has a problem from the get go, since it does... Char by char \ncomparison. Ouch.\n\nI'll try and hack it so that it does line by line, but given my Java skills, \nuh...\n\n-- \nfge\n"},{"id":"95345","messageId":"200811101759.03864.robin.rosenberg@dewire.com","threadId":"16249","inReplyTo":"200811101716.29029.fg@one2team.net","subject":"Re: JGIT: discuss: diff/patch implementation","fromName":"Robin Rosenberg","fromEmail":"robin.rosenberg@dewire.com","sentAt":"2008-11-10T16:59:03Z","receivedAt":"2008-11-10T16:59:03Z","isPatch":false,"sender":{"key":"robin.rosenberg@dewire.com","avatar":"https://avatars.githubusercontent.com/u/46357?v=4"},"body":"måndag 10 november 2008 17:16:28 skrev Francis Galiegue:\n> Le Monday 10 November 2008 16:56:35 Robin Rosenberg, vous avez écrit :\n> [...]\n> > >\n> > > I found this:\n> > >\n> > > http://code.google.com/p/google-diff-match-patch\n> > >\n> > > Its license is the Apache 2.0 license. It implements the same algorithm\n> > > than git's internal diff engine (\"An O(ND) Difference Algorithm and its\n> > > Variations\", by Eugene Myers), and as far as I can tell so far (IANAL,\n> > > far from it), it is compatible with JGit's current license.\n> > >\n> > > Could this be a viable candidate?\n> >\n> > Our approach was to do just that, for the very reasons you mention.\n> > I'll have a look. Thanks for doing some research for us. That project was\n> > unknown to me..\n> >\n> > -- robin\n> \n> Well, this API has a problem from the get go, since it does... Char by char \n> comparison. Ouch.\n> \n> I'll try and hack it so that it does line by line, but given my Java skills, \n> uh...\n> \nWe might want a byte-oriented version. Converting to char first is way \ntoo slow.\n\n-- robin\n"},{"id":"95354","messageId":"200811101911.19603.fg@one2team.net","threadId":"16249","inReplyTo":"200811101759.03864.robin.rosenberg@dewire.com","subject":"Re: JGIT: discuss: diff/patch implementation","fromName":"Francis Galiegue","fromEmail":"fg@one2team.net","sentAt":"2008-11-10T18:11:19Z","receivedAt":"2008-11-10T18:11:19Z","isPatch":false,"sender":{"key":"fg@one2team.net","avatar":null},"body":"Le Monday 10 November 2008 17:59:03 Robin Rosenberg, vous avez écrit :\n[Sorry if this is offtopic for the git mailing list...]\n\n> >\n> > Well, this API has a problem from the get go, since it does... Char by\n> > char comparison. Ouch.\n> >\n> > I'll try and hack it so that it does line by line, but given my Java\n> > skills, uh...\n>\n> We might want a byte-oriented version. Converting to char first is way\n> too slow.\n>\n\nWell, AFAICT, here is how the current git code detects whether a file is \nbinary or not:\n\n----\n#define FIRST_FEW_BYTES 8000\nint buffer_is_binary(const char *ptr, unsigned long size)\n{\n\tif (FIRST_FEW_BYTES < size)\n\t\tsize = FIRST_FEW_BYTES;\n\treturn !!memchr(ptr, 0, size);\n}\n----\n\nEasy enough to be coded in Java, hey, even I could do it :p\n\nSo, provided binary files are dealt with already, what penalty is left for \nJava to deal with?\n\n-- \nfge\n"},{"id":"95362","messageId":"alpine.DEB.1.00.0811102030180.30769@pacific.mpi-cbg.de","threadId":"16249","inReplyTo":"200811101522.13558.fg@one2team.net","subject":"Re: JGIT: discuss: diff/patch implementation","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-11-10T19:46:02Z","receivedAt":"2008-11-10T19:46:02Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 10 Nov 2008, Francis Galiegue wrote:\n\n> A very nice git feature, without even going as far as merges, is the \n> cherry pick feature.\n> \n> For this to be doable from within the Eclipse Git plugin, a diff/patch \n> implementation needs to be found, in a license compatible with the \n> current JGit license (3-clause BSD, as far as I can tell). Or a new \n> implementation can be rewritten from scratch, of course.\n\nDo not forget creating efficient packs. They also need an efficient diff \nengine.\n\n> I found this:\n> \n> http://code.google.com/p/google-diff-match-patch\n\nNice.\n\nAs was pointed out already, it is more meant to work on text than I'd like \nto, and it also seems to have cute DWIMery for HTML.\n\nI did not find any implementation, so I started implementing my own \nversion of Gene Myers' algorithm, with the plan to extend it with a \npatience diff option.\n\nMy code so far can generate a diff between two files, but does not use \nO(D) space (where D is the number of differences), but O(D^2), as I did \nnot have enough time (a conference, and traveling around the world can do \nthat to you).\n\nHaving looked at the source code of diff-patch-match, I admit that I do \nnot understand enough of the algorithm with so little documentation, so I \nwill continue my fun project.\n\nCiao,\nDscho\n"},{"id":"95371","messageId":"200811102121.17835.fg@one2team.net","threadId":"16249","inReplyTo":"alpine.DEB.1.00.0811102030180.30769@pacific.mpi-cbg.de","subject":"Re: JGIT: discuss: diff/patch implementation","fromName":"Francis Galiegue","fromEmail":"fg@one2team.net","sentAt":"2008-11-10T20:21:17Z","receivedAt":"2008-11-10T20:21:17Z","isPatch":false,"sender":{"key":"fg@one2team.net","avatar":null},"body":"Le Monday 10 November 2008 20:46:02 Johannes Schindelin, vous avez écrit :\n> Hi,\n>\n> On Mon, 10 Nov 2008, Francis Galiegue wrote:\n> > A very nice git feature, without even going as far as merges, is the\n> > cherry pick feature.\n> >\n> > For this to be doable from within the Eclipse Git plugin, a diff/patch\n> > implementation needs to be found, in a license compatible with the\n> > current JGit license (3-clause BSD, as far as I can tell). Or a new\n> > implementation can be rewritten from scratch, of course.\n>\n> Do not forget creating efficient packs. They also need an efficient diff\n> engine.\n>\n\nI wasn't even thinking about this, honestly :p\n\nLet's say that as far as IDE users are concerned, they do have disk space, and \nhaving the ability to cherry-pick is more of a priority than packs ;) Even a \nless efficient but \"to the point\" engine will be good enough for the time \nbeing, or at least, this is what I think.\n\nI understand way too little about the algorithm myself to tell whether it's \nalso efficient for such a purpose. Maybe it is...\n\n-- \nfge\n"},{"id":"95384","messageId":"7v63mv5mro.fsf@gitster.siamese.dyndns.org","threadId":"16249","inReplyTo":"200811101522.13558.fg@one2team.net","subject":"Re: JGIT: discuss: diff/patch implementation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-11-10T20:50:03Z","receivedAt":"2008-11-10T20:50:03Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Francis Galiegue writes:\n\n> A very nice git feature, without even going as far as merges, is the cherry \n> pick feature.\n\nI thought cherry-picking needs to be done in terms of 3-way merge, not\ndiff piped to patch, for correctness's sake.\n"},{"id":"95385","messageId":"20081110205242.GH2932@spearce.org","threadId":"16249","inReplyTo":"7v63mv5mro.fsf@gitster.siamese.dyndns.org","subject":"Re: JGIT: discuss: diff/patch implementation","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-11-10T20:52:42Z","receivedAt":"2008-11-10T20:52:42Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> Francis Galiegue writes:\n> \n> > A very nice git feature, without even going as far as merges, is the cherry \n> > pick feature.\n> \n> I thought cherry-picking needs to be done in terms of 3-way merge, not\n> diff piped to patch, for correctness's sake.\n\nYea, the 3-way merge cherry-pick is better. But in a pinch you\ncan (usually) get correct results from a \"diff | patch\" pipeline.\nOf course that doesn't always work, resulting in patches that don't\napply cleanly, or worse, that apply at the wrong place silently.\n\n-- \nShawn.\n"},{"id":"95391","messageId":"200811102231.31263.fg@one2team.net","threadId":"16249","inReplyTo":"20081110205242.GH2932@spearce.org","subject":"Re: JGIT: discuss: diff/patch implementation","fromName":"Francis Galiegue","fromEmail":"fg@one2team.net","sentAt":"2008-11-10T21:31:30Z","receivedAt":"2008-11-10T21:31:30Z","isPatch":false,"sender":{"key":"fg@one2team.net","avatar":null},"body":"Le Monday 10 November 2008 21:52:42 Shawn O. Pearce, vous avez écrit :\n> Junio C Hamano wrote:\n> > Francis Galiegue writes:\n> > > A very nice git feature, without even going as far as merges, is the\n> > > cherry pick feature.\n> >\n> > I thought cherry-picking needs to be done in terms of 3-way merge, not\n> > diff piped to patch, for correctness's sake.\n>\n> Yea, the 3-way merge cherry-pick is better. But in a pinch you\n> can (usually) get correct results from a \"diff | patch\" pipeline.\n> Of course that doesn't always work, resulting in patches that don't\n> apply cleanly, or worse, that apply at the wrong place silently.\n\nWell, in this case, I'd say it's a case of a bottle being \"half full\" or \"half \nempty\".\n\nThe availability of even a simple diff|patch in jgit, and its being available \nin egit, would generally be seen as a \"half full\" bottle, and would, imho, \nGREATLY increase the appeal factor of egit, all the more that you have plenty \nof undo/redo ability in Eclipse... And, dare I say it, of git in general as \nan SCM to be used in many environments where Eclipse is the de facto IDE.\n\nI know, I may sound irritating, but...\n\n-- \nfge\n"},{"id":"95402","messageId":"alpine.DEB.1.00.0811110031510.30769@pacific.mpi-cbg.de","threadId":"16249","inReplyTo":"7v63mv5mro.fsf@gitster.siamese.dyndns.org","subject":"Re: JGIT: discuss: diff/patch implementation","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-11-10T23:37:02Z","receivedAt":"2008-11-10T23:37:02Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 10 Nov 2008, Junio C Hamano wrote:\n\n> Francis Galiegue writes:\n> \n> > A very nice git feature, without even going as far as merges, is the \n> > cherry pick feature.\n> \n> I thought cherry-picking needs to be done in terms of 3-way merge, not \n> diff piped to patch, for correctness's sake.\n\nI haven't checked how RCS merge does it, but I know how xdiff/xmerge.c \ndoes it ;-)\n\nBasically, it takes the two diffs relative to the base file and works on \nthe overlapping hunks (i.e. on hunks where the ranges in the base file \noverlap).\n\nSo we need a diff algorithm very much if we were to imitate that code in \nJGit, which I very much plan to do.\n\nCiao,\nDscho\n"},{"id":"95440","messageId":"491933DF.3060307@dawes.za.net","threadId":"16249","inReplyTo":"200811101522.13558.fg@one2team.net","subject":"Re: JGIT: discuss: diff/patch implementation","fromName":"Rogan Dawes","fromEmail":"lists@dawes.za.net","sentAt":"2008-11-11T07:27:27Z","receivedAt":"2008-11-11T07:27:27Z","isPatch":false,"sender":{"key":"lists@dawes.za.net","avatar":null},"body":"Francis Galiegue wrote:\n> Hello,\n> \n> A very nice git feature, without even going as far as merges, is the cherry \n> pick feature.\n> \n> For this to be doable from within the Eclipse Git plugin, a diff/patch \n> implementation needs to be found, in a license compatible with the current \n> JGit license (3-clause BSD, as far as I can tell). Or a new implementation \n> can be rewritten from scratch, of course.\n\nShouldn't Eclipse already *have* a diff/patch implementation, for its \nother \"team work\" plugins?\n\nRogan\n"},{"id":"95447","messageId":"1226398000.7541.11.camel@minastirith.xtradesoft.lan","threadId":"16249","inReplyTo":"7v63mv5mro.fsf@gitster.siamese.dyndns.org","subject":"Re: JGIT: discuss: diff/patch implementation","fromName":"Raimund Bauer","fromEmail":"ray007@gmx.net","sentAt":"2008-11-11T10:06:40Z","receivedAt":"2008-11-11T10:06:40Z","isPatch":false,"sender":{"key":"ray007@gmx.net","avatar":null},"body":"\nOn Mon, 2008-11-10 at 12:50 -0800, Junio C Hamano wrote:\n> Francis Galiegue writes:\n> \n> > A very nice git feature, without even going as far as merges, is the cherry \n> > pick feature.\n> \n> I thought cherry-picking needs to be done in terms of 3-way merge, not\n> diff piped to patch, for correctness's sake.\n\nWhat about http://sourceforge.net/projects/jlibdiff ?\nMaybe a bit old, but claims to have diff3 and is under LGPL.\n\nbest regards,\nRay\n"},{"id":"95467","messageId":"20081111171342.GJ2932@spearce.org","threadId":"16249","inReplyTo":"491933DF.3060307@dawes.za.net","subject":"Re: JGIT: discuss: diff/patch implementation","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-11-11T17:13:42Z","receivedAt":"2008-11-11T17:13:42Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Rogan Dawes wrote:\n> Francis Galiegue wrote:\n>>\n>> For this to be doable from within the Eclipse Git plugin, a diff/patch \n>> implementation needs to be found, in a license compatible with the \n>> current JGit license (3-clause BSD, as far as I can tell). Or a new \n>> implementation can be rewritten from scratch, of course.\n>\n> Shouldn't Eclipse already *have* a diff/patch implementation, for its \n> other \"team work\" plugins?\n\nErr, uhm, sort of.\n\nEclipse has patch available as an internal API, but it is exposed\nin the UI for any team provider (or no team provider at all) to\nuse to apply patches to a project in the workspace.\n\nThe team provider API assumes the VCS implementation has its own\ndiff, and therefore the diff implementation inside Eclipse is only\nused for the native Compare view\n\nI've dug around that part of the text compare plugin and its mostly\ninternal APIs, and mostly still low-level LCS generation from\narbitrary object input. It doesn't seem well suited to producing\nfast diffs of text.\n\nIts under the EPL. We could take the code and simplify it down,\nbut I think by that point we'd mostly just want to rewrite it, or\nuse a different library anyway. At which point we wouldn't want\nto bring in the EPL baggage if we can have a BSD implementation.\n\nSo yea, there's some implementation in there, but its not easy to\nuse or get to...\n\n-- \nShawn.\n"},{"id":"95469","messageId":"20081111171816.GK2932@spearce.org","threadId":"16249","inReplyTo":"1226398000.7541.11.camel@minastirith.xtradesoft.lan","subject":"Re: JGIT: discuss: diff/patch implementation","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-11-11T17:18:16Z","receivedAt":"2008-11-11T17:18:16Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Raimund Bauer wrote:\n> On Mon, 2008-11-10 at 12:50 -0800, Junio C Hamano wrote:\n> > Francis Galiegue writes:\n> > \n> > > A very nice git feature, without even going as far as merges, is the cherry \n> > > pick feature.\n> > \n> > I thought cherry-picking needs to be done in terms of 3-way merge, not\n> > diff piped to patch, for correctness's sake.\n> \n> What about http://sourceforge.net/projects/jlibdiff ?\n> Maybe a bit old, but claims to have diff3 and is under LGPL.\n\nI hadn't looked at that library before.\n\nWe've generally tried to avoid LGPL diff implementations, but partly\nbecause any I found were ports from a GPL C based code tree to Java,\nbut then the guy who did the port went and changed the license\nto LGPL. Slightly dubious if you ask me. ;-)\n\nLGPL plays nicely with BSD, especially in Java where runtime\nrelinking is possible. But it does screw with jgit.pgm's little\nidea of \"shove *everything* into a single shell script\", as then\nits not runtime re-linkable by the user.\n\nI don't know how the Eclipse foundation feels about distributing\nLGPL in the IDE. One of our major reasons for going with a BSD\nlicense on JGit was so the Eclipse Git team provider plugin could be\ndistributed alongside the CVS team provider, as part of the basic IDE\nteam provider package. We're clearly not ready for that wide of a\ndistribution, but it was a goal Robin and I set out for the project.\n\n-- \nShawn.\n"},{"id":"95472","messageId":"bd6139dc0811110931g6a04335dp925dd09f2afaee03@mail.gmail.com","threadId":"16249","inReplyTo":"20081111171816.GK2932@spearce.org","subject":"Re: JGIT: discuss: diff/patch implementation","fromName":"Sverre Rabbelier","fromEmail":"alturin@gmail.com","sentAt":"2008-11-11T17:31:13Z","receivedAt":"2008-11-11T17:31:13Z","isPatch":false,"sender":{"key":"alturin@gmail.com","avatar":null},"body":"On Tue, Nov 11, 2008 at 18:18, Shawn O. Pearce wrote:\n> I don't know how the Eclipse foundation feels about distributing\n> LGPL in the IDE. One of our major reasons for going with a BSD\n> license on JGit was so the Eclipse Git team provider plugin could be\n> distributed alongside the CVS team provider, as part of the basic IDE\n> team provider package. We're clearly not ready for that wide of a\n> distribution, but it was a goal Robin and I set out for the project.\n\nWhy not keep that as a goall? For now, you can stick with one of the\nexisting LGPL implementations, later, when you want to have JGit\ndistributed with Eclipse, you (or Johanness Schindelin when he has the\ntime) write up your own Java version of it and license it BSD\n\n-- \nCheers,\n\nSverre Rabbelier\n"}]}