{"thread":{"id":"17098","subject":"[JGIT] Blame functionality for jgit","startedAt":"2009-01-11T20:23:16Z","lastAt":"2009-01-12T21:55:16Z","messageCount":4,"participants":["Manuel Woelker","Shawn O. Pearce"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"99998","messageId":"3d045c7e0901111223j43a69402s28a59612212943f3@mail.gmail.com","threadId":"17098","inReplyTo":null,"subject":"[JGIT] Blame functionality for jgit","fromName":"Manuel Woelker","fromEmail":"manuel.woelker@gmail.com","sentAt":"2009-01-11T20:23:16Z","receivedAt":"2009-01-11T20:23:16Z","isPatch":false,"sender":{"key":"manuel.woelker@gmail.com","avatar":null},"body":"Hello there,\n\nOver the weekend I have been hacking the jgit sources a little to see\nif I can add blame/praise/annotate functionality to it. The results\ncan be found at http://github.com/manuel-woelker/egit/tree/blame . All\nwork is in the blame branch in org.spearce.jgit.blame package.\n\nI largely ported the cgit blame algorithm described here\nhttps://kerneltrap.org/mailarchive/git/2006/10/12/224187 , the\nrelevant file is builtin-blame.c cf.\nhttp://repo.or.cz/w/git.git?a=blob;f=builtin-blame.c;hb=HEAD\n\nThe structure has been kept largely intact, but I have tried to\ntranslate the concepts to idiomatic java, with the bulk of the logic\nnow in the Scoreboard class\n\nThe blame algorithm needs to use a diff algorithm to find common parts\nin files. AFAICT there is no diff implementation in jgit at the\nmoment. I used the incava java-diff library, (see\nhttp://www.incava.org/projects/java/java-diff ), but I introduced an\ninterface that should make it possible to swap implementations with a\nminimum of effort. To compile I just create a new eclipse project with\nthe java-diff sources.\n\nCurrently renames, copies etc. are not supported, so only files with\nthe same name can receive the blame. Unmodified renames and copies\nshould be fairly simple to implement. Modified renames and copies\nmight prove to be a little bit harder, so that would have to wait\nuntil jgit can follow history across renames/copies.\n\nThere are some simple unit tests to check the basic functionality. I\nalso \"blamed\" SUBMITTING_PATCHES in the egit repo, and got the same\nresults as cgit. I am certain that there a some bugs lurking in the\ncode, but overall it looks quite promising.\n\nI would like to hear your thoughts on a couple of topics:\n - Merge/patch/diff/blame functionality needs a diff implementation,\nwhat are our options within technical and license constraints?\n - What is the roadmap for these features?\n - Can you see this blame effort getting integrated upstream?\n\nI would love to contribute more effort to egit and the blame\nfunctionality in particular. To me, \"blame\" is one of the killer\nfeatures of modern SCMs.\n\nLast no least, kudos to the git and egit teams for their hard work on\nmaking git such a great piece of software.\n - Manuel Woelker\n"},{"id":"100141","messageId":"20090112174232.GJ10179@spearce.org","threadId":"17098","inReplyTo":"3d045c7e0901111223j43a69402s28a59612212943f3@mail.gmail.com","subject":"Re: [JGIT] Blame functionality for jgit","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-01-12T17:42:32Z","receivedAt":"2009-01-12T17:42:32Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Manuel Woelker <manuel.woelker@gmail.com> wrote:\n> Over the weekend I have been hacking the jgit sources a little to see\n> if I can add blame/praise/annotate functionality to it. The results\n> can be found at http://github.com/manuel-woelker/egit/tree/blame . All\n> work is in the blame branch in org.spearce.jgit.blame package.\n\nInteresting.\n \n> I largely ported the cgit blame algorithm described here\n> https://kerneltrap.org/mailarchive/git/2006/10/12/224187 , the\n> relevant file is builtin-blame.c cf.\n> http://repo.or.cz/w/git.git?a=blob;f=builtin-blame.c;hb=HEAD\n\nOK.  Fortunately Junio has largely given his blessing to this code\nbeing converted to Java under the BSD license.\n\n> The blame algorithm needs to use a diff algorithm to find common parts\n> in files. AFAICT there is no diff implementation in jgit at the\n> moment. I used the incava java-diff library, (see\n> http://www.incava.org/projects/java/java-diff ), but I introduced an\n> interface that should make it possible to swap implementations with a\n> minimum of effort. To compile I just create a new eclipse project with\n> the java-diff sources.\n\nUnfortunately I can't reach incava.org to download java-diff, but\nits entry on sourceforge says it uses an LGPL license.  Within JGit\nwe do want to stick to BSD and BSD dependencies, so bringing in\njava-diff as a new dependency isn't something we really want to do.\n\nFortunately Dscho has been working on a Java diff implementation for\nJGit, and is considering releasing it under a BSD license so we can\ninclude it.\n\nThe interface is still to be decided, but in general we have\nfound that running against a byte[] is much faster than running\nagainst String.  We're probably going to want the diff library to\ntake a byte[] and an IntList (as created by RawParseUtils.lineMap)\nand let it work against the byte array ranges directly, without any\nadditional allocations, except where it needs to build up its hash\nof records.\n \n> I would like to hear your thoughts on a couple of topics:\n>  - Merge/patch/diff/blame functionality needs a diff implementation,\n> what are our options within technical and license constraints?\n\nI'm open to a plugin interface like you have done with the IDiff\nAPI to hide java-diff, but for that to work we cannot have the\njava-diff code as part of the JGit classpath.  It needs to be\nsomething added externally by the user, in a different context,\nso the user can easily load their preferred diff implementation.\n\nIf that happents to be the LGPL java-diff, that's the user's choice.\nWe can provide the shim needed to get it to load, and the adapter,\nbut IMHO we shouldn't distribute the LGPL code, and we shouldn't\nmake it required in order to make the library compile or work.\n\nEclipes has its own LCS implementation, we should also be able\nto have the Eclipse plugin provide its own shim to link to the\nEclipse EPL licensed LCS, so Eclipse can avoid java-diff entirely.\nI'm not sure if NetBeans has an LCS available that the NetBeans\nplugin could easily link to.  It probably does.\n\nI think eventually we'll have a BSD licensed LCS that will come with\nJGit, which would eliminate the need for such a shim.  I'd like\nto see that happen before blame gets added, but if blame is ready\nand the shim is reasonably well done, I'm inclined to bring blame\nin early.\n\n>  - What is the roadmap for these features?\n\nThere isn't one.  Its whatever gets contributed in a state that is\nready for inclusion.  :-)\n\nSince you are submitting this work, I'd say its on you to get\nblame added.\n\n>  - Can you see this blame effort getting integrated upstream?\n\nYes.\n \n> I would love to contribute more effort to egit and the blame\n> functionality in particular. To me, \"blame\" is one of the killer\n> features of modern SCMs.\n\nI agree, I use git blame fairly often myself...\n\n> Last no least, kudos to the git and egit teams for their hard work on\n> making git such a great piece of software.\n\nThanks.\n\nNow for some comments about your blame branch.\n\n- Don't use @author tags, we don't use them anywhere else.\n\n- Please include copyright headers on all new files.\n\n- I think the IDiff, IDifference should be in a \".diff\" package so\nwe can reuse them for other diff applications.  Especially if we\nwind up using a shim to link to different LCS implementations.\n\n- I think the API for BlameEngine should be more like:\n\n  public class BlameEngine {\n    private final RevWalk rw;\n\n    public BlameEngine(final Repository repo) {\n      this(new RevWalk(repo));\n    }\n\n    public BlameEngine(final RevWalk walk) {\n      rw = walk;\n    }\n\n    public RevWalk getRevWalk() {\n      return rw;\n    }\n\n    public List<BlameEntry> blame(RevCommit c, String path);\n  }\n\n  One reason for this style of API is we can have the engine cache\n  blame records.  This can make a GUI navigator much more efficient\n  as it jumps around between commits and asks for blames over the\n  same data.\n\n- Internally you should *always* use RevCommit, not Commit.\nThe RevCommit class can be orders of magnitude faster than Commit.\n\n- Internally you should always use RevTree and TreeWalk to locate\nblob IDs.  Its orders of magnitude faster than Tree and TreeEntry.\n\n- Don't use new String(loader.getBytes()) (e.g. in Origin.getData)\nto get the data for a file.  We want to do raw diffs, so that the\ncharacter encoding is considered as part of the blame.  E.g. if\na file switches character encodings, the blame has to go to the\ncommit that introduced the new encoding.  This is a huge reason\nto use byte[] and IntList over an array of String.\n\n- RawParseUtils.lineMap will be faster than a Pattern of \"^(.*)$\".\n\n\nOtherwise, I'm finding your code to be quite clear, and converted\nrather nicely from C.  I'd love to see this integrated into the\nJGit project.\n\n-- \nShawn.\n"},{"id":"100161","messageId":"3d045c7e0901121317j4ccd9515vbc7a44abc8ae5356@mail.gmail.com","threadId":"17098","inReplyTo":"20090112174232.GJ10179@spearce.org","subject":"Re: [JGIT] Blame functionality for jgit","fromName":"Manuel Woelker","fromEmail":"manuel.woelker@gmail.com","sentAt":"2009-01-12T21:17:47Z","receivedAt":"2009-01-12T21:17:47Z","isPatch":false,"sender":{"key":"manuel.woelker@gmail.com","avatar":null},"body":"On Mon, Jan 12, 2009 at 6:42 PM, Shawn O. Pearce <spearce@spearce.org> wrote:\n>\n>> I largely ported the cgit blame algorithm described here\n>> https://kerneltrap.org/mailarchive/git/2006/10/12/224187 , the\n>> relevant file is builtin-blame.c cf.\n>> http://repo.or.cz/w/git.git?a=blob;f=builtin-blame.c;hb=HEAD\n>\n> OK.  Fortunately Junio has largely given his blessing to this code\n> being converted to Java under the BSD license.\n\nGlad to hear that, Dscho already mentioned that a port like this might\nraise license concerns. So I hope Junio would be okay with that.\n\n> Unfortunately I can't reach incava.org to download java-diff, but\n> its entry on sourceforge says it uses an LGPL license.  Within JGit\n> we do want to stick to BSD and BSD dependencies, so bringing in\n> java-diff as a new dependency isn't something we really want to do.\n>\n> Fortunately Dscho has been working on a Java diff implementation for\n> JGit, and is considering releasing it under a BSD license so we can\n> include it.\n>\n> The interface is still to be decided, but in general we have\n> found that running against a byte[] is much faster than running\n> against String.  We're probably going to want the diff library to\n> take a byte[] and an IntList (as created by RawParseUtils.lineMap)\n> and let it work against the byte array ranges directly, without any\n> additional allocations, except where it needs to build up its hash\n> of records.\n\nThat sounds like a good plan. For now I am not all that concerned\nabout performance myself (premature optimization and all that), but in\nthe long run - and especially with rename/copy detection that will\ndefinitely a factor for usability. We could adopt the interface to\nallow for a \"fast\" implementation, and have existing diff\nimplementations adapted to that. I'd be very interested to see Dscho's\ndiff work, and maybe we can get something going on that front. A\npatience diff implementation would be rather neat too, and all my\ngoogling hasn't turned up anything.\n\n> I think eventually we'll have a BSD licensed LCS that will come with\n> JGit, which would eliminate the need for such a shim.  I'd like\n> to see that happen before blame gets added, but if blame is ready\n> and the shim is reasonably well done, I'm inclined to bring blame\n> in early.\n\nWhile trying to look up the Myers diff algorithm I found a diff\nimplementation in Apache wicket (cf.\nhttp://wicket.sourceforge.net/apidocs/wicket/util/diff/myers/package-summary.html\n). This one is under an Apache license, is that any better? It's truly\nkind of sad that you need a degree in law these days to get any work\ndone in this license jungle. I just happen to strongly oppose the\nreinvention of circular transportation-enabling devices...\n\n> - Don't use @author tags, we don't use them anywhere else.\n>\n> - Please include copyright headers on all new files.\n>\n> - I think the IDiff, IDifference should be in a \".diff\" package so\n> we can reuse them for other diff applications.  Especially if we\n> wind up using a shim to link to different LCS implementations.\n>\n> - I think the API for BlameEngine should be more like:\n>\n>  public class BlameEngine {\n>    private final RevWalk rw;\n>\n>    public BlameEngine(final Repository repo) {\n>      this(new RevWalk(repo));\n>    }\n>\n>    public BlameEngine(final RevWalk walk) {\n>      rw = walk;\n>    }\n>\n>    public RevWalk getRevWalk() {\n>      return rw;\n>    }\n>\n>    public List<BlameEntry> blame(RevCommit c, String path);\n>  }\n>\n>  One reason for this style of API is we can have the engine cache\n>  blame records.  This can make a GUI navigator much more efficient\n>  as it jumps around between commits and asks for blames over the\n>  same data.\n>\n> - Internally you should *always* use RevCommit, not Commit.\n> The RevCommit class can be orders of magnitude faster than Commit.\n>\n> - Internally you should always use RevTree and TreeWalk to locate\n> blob IDs.  Its orders of magnitude faster than Tree and TreeEntry.\n>\n> - Don't use new String(loader.getBytes()) (e.g. in Origin.getData)\n> to get the data for a file.  We want to do raw diffs, so that the\n> character encoding is considered as part of the blame.  E.g. if\n> a file switches character encodings, the blame has to go to the\n> commit that introduced the new encoding.  This is a huge reason\n> to use byte[] and IntList over an array of String.\n>\n> - RawParseUtils.lineMap will be faster than a Pattern of \"^(.*)$\".\n>\nThanks for the comments. This first version was basically just a\nproof-of-concept to see if and how it could work. I didn't want to\npour too much effort into, before knowing if this project was viable\nat all. This input is very valuable and I will try to incorporate the\nsuggestions into future revisions.\n\nI'll keep you posted on new developments\n - Manuel\n"},{"id":"100177","messageId":"20090112215516.GN10179@spearce.org","threadId":"17098","inReplyTo":"3d045c7e0901121317j4ccd9515vbc7a44abc8ae5356@mail.gmail.com","subject":"Re: [JGIT] Blame functionality for jgit","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-01-12T21:55:16Z","receivedAt":"2009-01-12T21:55:16Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Manuel Woelker <manuel.woelker@gmail.com> wrote:\n> On Mon, Jan 12, 2009 at 6:42 PM, Shawn O. Pearce <spearce@spearce.org> wrote:\n> \n> That sounds like a good plan. For now I am not all that concerned\n> about performance myself (premature optimization and all that), but in\n> the long run - and especially with rename/copy detection that will\n> definitely a factor for usability.\n\nYea, I know.  Premature optimization is the root of all evil.\nBut we've also learned the hard way that Java is slow as snot\ncompared to C git.  The only way we can even stay close is to\noptimize the hell out of the tight inner sections, and very often\nthat means using byte[] and avoiding upconverting to String to as\nlate as we possibly can.\n\nPerformance *is* a feature in Git.  Its not a \"nice to have\",\nits a requirement.  The old history view for example was too damn\nslow using Commit, requiring minutes on one of my systems to render\negit.git history.  Using RevCommit its subsecond response time.\n\nI just wanted to point out that we care quite a bit about speed, and\nthat given our input (raw byte[] from the pack) we need to be able\nto quickly make decisions without upconverting to String, otherwise\nblame performance will be so bad that its completely unusable.\n\n> > I think eventually we'll have a BSD licensed LCS [...]\n> \n> While trying to look up the Myers diff algorithm I found a diff\n> implementation in Apache wicket (cf.\n> http://wicket.sourceforge.net/apidocs/wicket/util/diff/myers/package-summary.html\n> ). This one is under an Apache license, is that any better? It's truly\n> kind of sad that you need a degree in law these days to get any work\n> done in this license jungle. I just happen to strongly oppose the\n> reinvention of circular transportation-enabling devices...\n\nYea, even the ASF has trouble deciding if the Apache License and\nthe GPL can get along:\n\n  \"The Apache Software Foundation is still trying to determine if\n  this version of the Apache License is compatible with the GPL.\"\n\n  http://www.apache.org/licenses/\n\nThe Apache License doesn't play nice with GPLv2 apparently, but is\nOK with GPLv2, at least according to the FSF.\n\nAnyway.  The Apache License is roughly the new style BSD, but with\npatent protection clauses built in.  I think we can consume code\nunder the Apache License and redistribute it without any trouble\nfor us, our any of our downstream consumers.\n\n> I'll keep you posted on new developments\n\nLooking forward to it.\n\n-- \nShawn.\n"}]}