{"thread":{"id":"31646","subject":"A generalization of git blame","startedAt":"2012-09-25T18:14:39Z","lastAt":"2012-09-27T06:38:06Z","messageCount":7,"participants":["xmeng@cs.wisc.edu","Philip Oakley","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"199902","messageId":"89ccf5dd776edc648d488c20214e1105.squirrel@webmail.cs.wisc.edu","threadId":"31646","inReplyTo":null,"subject":"A generalization of git blame","fromName":"","fromEmail":"xmeng@cs.wisc.edu","sentAt":"2012-09-25T18:14:39Z","receivedAt":"2012-09-25T18:14:39Z","isPatch":false,"sender":{"key":"xmeng@cs.wisc.edu","avatar":null},"body":"\n\n\nHi,\n\nI have been developing my git tool (based on the git internal API) that\ncan find out all the commits that have changed a line for better\nauthorship.\n\nThe reason is for my binary code authorship research, I use machine\nlearning to classify code authorship. To produce training data, I start\nwith a source code repository with well-known author labels for each line\nand then compiling the project into binary. So, I am able to know the\nauthorship for binary code and then apply some machine learning\ntechniques.\n\nTo get ground truth of authorship for each line, I start with git-blame.\nBut later I find this is not sufficient because the last commit may only\nadd comments or may only change a small part of the line, so that I\nshouldn't attribute the line of code to the last author. Of course, there\nmust be some debates on who can be the representative of a line of code.\nSo what I would like to do is find out all the commits that have ever\nchanged a line, then I can try different approaches to summarize over all\nthese commits to produce my final authorship label (or even tuple).\n\nI was wondering whether there have been similar debates over accurate\nauthorship in this community before and whether there may be other people\ninterested in this work.\n\nThanks\n\n--Xiaozhu\n"},{"id":"199910","messageId":"CC2642CD25C542A18FB55E7BD58F95E5@PhilipOakley","threadId":"31646","inReplyTo":"89ccf5dd776edc648d488c20214e1105.squirrel@webmail.cs.wisc.edu","subject":"Re: A generalization of git blame","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.org","sentAt":"2012-09-25T22:19:54Z","receivedAt":"2012-09-25T22:19:54Z","isPatch":false,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"From: <xmeng@cs.wisc.edu>\n> I have been developing my git tool (based on the git internal API) \n> that\n> can find out all the commits that have changed a line for better\n> authorship.\n>\n> The reason is for my binary code authorship research, I use machine\n> learning to classify code authorship. To produce training data, I \n> start\n> with a source code repository with well-known author labels for each \n> line\n> and then compiling the project into binary. So, I am able to know the\n> authorship for binary code and then apply some machine learning\n> techniques.\n>\n> To get ground truth of authorship for each line, I start with \n> git-blame.\n> But later I find this is not sufficient because the last commit may \n> only\n> add comments or may only change a small part of the line, so that I\n> shouldn't attribute the line of code to the last author.\n\nI would suggest there is:\n- White space adjustment\n- Comment or documentation (assumes you can parse the 'code' to decide \nthat it isn't executable code)\n- word changes within expressions\n- complete replacement of line (whole statement?)\n\nCustom & practice is the likely decider.\n\n>                              Of course, there\n> must be some debates on who can be the representative of a line of \n> code.\n> So what I would like to do is find out all the commits that have ever\n> changed a line, then I can try different approaches to summarize over \n> all\n> these commits to produce my final authorship label (or even tuple).\n>\n> I was wondering whether there have been similar debates over accurate\n> authorship in this community before and whether there may be other \n> people\n> interested in this work.\n\nI'd suggest looking at the various 'diff' formats, such as character \ndiff, word diff, and line diff for discussions.\n\n>\n> Thanks\n>\n> --Xiaozhu\n>\nPhilip \n"},{"id":"199913","messageId":"7vsja5vh2z.fsf@alter.siamese.dyndns.org","threadId":"31646","inReplyTo":"CC2642CD25C542A18FB55E7BD58F95E5@PhilipOakley","subject":"Re: A generalization of git blame","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-09-25T23:05:40Z","receivedAt":"2012-09-25T23:05:40Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Philip Oakley\" <philipoakley@iee.org> writes:\n\n>> To get ground truth of authorship for each line, I start with\n>> git-blame.\n>> But later I find this is not sufficient because the last commit may\n>> only\n>> add comments or may only change a small part of the line, so that I\n>> shouldn't attribute the line of code to the last author.\n>\n> I would suggest there is:\n> - White space adjustment\n> - Comment or documentation (assumes you can parse the 'code' to decide\n> that it isn't executable code)\n> - word changes within expressions\n> - complete replacement of line (whole statement?)\n\nYou are being generous by listing easier cases ;-) I'd add a couple\nmore that are more problematic if your approach does not consider\nsemantics.\n\n - A function gained a new parameter, to which pretty much everbody\n   passes the same default value.\n\n\t-void fn(int a, int b, int c)\n\t+void fn(int a, int b, int c, int d)\n\t {\n\t+\tif (d) {\n\t+\t\t...\n\t+\t\treturn;\n\t+\t}\n\t\t...\n\t }\n\n         void frotz(void)\n\t {\n\t\t...\n        -\tfn(a, b, c);\n        +\tfn(a, b, c, 0);\n        \t...\n        -\tfn(a, b, d);\n        +\tfn(a, b, d, 1);\n        \t...\n\n   The same commit that changed the above call site must have\n   changed the definition of function \"fn\" and defined what the new\n   fourth parameter means.  It is likely that, when the default\n   value most everybody passes (perhaps \"0\") is given, \"fn\" does\n   what it used to do, and a different value may trigger a new\n   behaviour of \"fn\".  It could be argued that the former call\n   should not be blamed for this commit, while the latter callsite\n   should.\n\n - A variable was renamed, and the meaning of a line suddenly\n   changed, even though the text of that line did not change at all.\n\n\t static int foo;\n         ...\n        -int xyzzy(int foo)\n\t+int xyzzy(int bar)\n\t {\n\t\t... some complex computation that\n                ... involves foo and bar, resulting in\n                ... updating of foo comes here ...\n\t\treturn foo * 2;\n \t }\n\n   Whom to blame the behaviour of (i.e. returned value from) the\n   function?  The \"return foo * 2\" never changed with this patch,\n   but the patch _is_ responsible for changing the behaviour.\n\n   As the OP is interested in tracking the origin of the _binary_,\n   this case is even more interesting, as the generated machine code\n   to compute the foo * 2 would likely to be very different before\n   and after the patch.\n"},{"id":"199952","messageId":"72fc15c78ddb6b5c9e95f6b0cd925a26.squirrel@webmail.cs.wisc.edu","threadId":"31646","inReplyTo":"7vsja5vh2z.fsf@alter.siamese.dyndns.org","subject":"Re: A generalization of git blame","fromName":"","fromEmail":"xmeng@cs.wisc.edu","sentAt":"2012-09-26T15:36:46Z","receivedAt":"2012-09-26T15:36:46Z","isPatch":false,"sender":{"key":"xmeng@cs.wisc.edu","avatar":null},"body":"\n> \"Philip Oakley\" <philipoakley@iee.org> writes:\n>\n>>> To get ground truth of authorship for each line, I start with\n>>> git-blame.\n>>> But later I find this is not sufficient because the last commit may\n>>> only\n>>> add comments or may only change a small part of the line, so that I\n>>> shouldn't attribute the line of code to the last author.\n>>\n>> I would suggest there is:\n>> - White space adjustment\n>> - Comment or documentation (assumes you can parse the 'code' to decide\n>> that it isn't executable code)\n>> - word changes within expressions\n>> - complete replacement of line (whole statement?)\n>\n> You are being generous by listing easier cases ;-) I'd add a couple\n> more that are more problematic if your approach does not consider\n> semantics.\n>\n>  - A function gained a new parameter, to which pretty much everbody\n>    passes the same default value.\n>\n> \t-void fn(int a, int b, int c)\n> \t+void fn(int a, int b, int c, int d)\n> \t {\n> \t+\tif (d) {\n> \t+\t\t...\n> \t+\t\treturn;\n> \t+\t}\n> \t\t...\n> \t }\n>\n>          void frotz(void)\n> \t {\n> \t\t...\n>         -\tfn(a, b, c);\n>         +\tfn(a, b, c, 0);\n>         \t...\n>         -\tfn(a, b, d);\n>         +\tfn(a, b, d, 1);\n>         \t...\n>\n>    The same commit that changed the above call site must have\n>    changed the definition of function \"fn\" and defined what the new\n>    fourth parameter means.  It is likely that, when the default\n>    value most everybody passes (perhaps \"0\") is given, \"fn\" does\n>    what it used to do, and a different value may trigger a new\n>    behaviour of \"fn\".  It could be argued that the former call\n>    should not be blamed for this commit, while the latter callsite\n>    should.\n>\n>  - A variable was renamed, and the meaning of a line suddenly\n>    changed, even though the text of that line did not change at all.\n>\n> \t static int foo;\n>          ...\n>         -int xyzzy(int foo)\n> \t+int xyzzy(int bar)\n> \t {\n> \t\t... some complex computation that\n>                 ... involves foo and bar, resulting in\n>                 ... updating of foo comes here ...\n> \t\treturn foo * 2;\n>  \t }\n>\n>    Whom to blame the behaviour of (i.e. returned value from) the\n>    function?  The \"return foo * 2\" never changed with this patch,\n>    but the patch _is_ responsible for changing the behaviour.\n>\n>    As the OP is interested in tracking the origin of the _binary_,\n>    this case is even more interesting, as the generated machine code\n>    to compute the foo * 2 would likely to be very different before\n>    and after the patch.\n>\n>\n\nThanks for both your great suggestions. Current my approach doesn't\nconsider semantics yet and this should be an interesting to do.\n\nAnother question is that is it possible to include my tool as a git\nbuilt-in tool in the future? I know that my tool is still not good for any\nrelease. But I would like to share my work with other people if other\npeople are interested. And if it is possible, I think I will have a\nstronger motivation to make my tool more robust and useful.\n\nThanks\n"},{"id":"199959","messageId":"7vfw64txa1.fsf@alter.siamese.dyndns.org","threadId":"31646","inReplyTo":"72fc15c78ddb6b5c9e95f6b0cd925a26.squirrel@webmail.cs.wisc.edu","subject":"Re: A generalization of git blame","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-09-26T19:11:02Z","receivedAt":"2012-09-26T19:11:02Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"xmeng@cs.wisc.edu writes:\n\n> Another question is that is it possible to include my tool as a git\n> built-in tool in the future?\n\nIt largely depends on how the user would interact with your program,\nwhich is totally unclear as we haven't seen any part of it.  I do\nnot think we have enough information to answer the question at this\npoint.\n\n> I know that my tool is still not good for any release. But I would\n> like to share my work with other people if other people are\n> interested.\n\nIf it is a trivial script that largely depends on what we already\nship, I would not mind carrying it in contrib/.  If it is anything\nsubstantial and substantially useful, however, I would suspect that\nyou are better off not be in in my tree, but rather want to be\nindependent.  Finishing it to be useful for your purpose, publishing\nit somewhere people can take a look at and adding a pointer to\nhttps://git.wiki.kernel.org/index.php/InterfacesFrontendsAndTools is\nprobably where you would want to start.\n\n> And if it is possible, I think I will have a stronger motivation\n> to make my tool more robust and useful.\n\nI've seen from time to time people ask \"I am thinking of doing this;\nwill a patch be accepted?  If so, I'll work on it.\" before showing\nany work, and my response always has been:\n\n (1) We won't know how useful and interesting your contribution be\n     for our audience, until we see it; and\n\n (2) If you truly believe in your work (find it useful, find writing\n     it fun, etc.), that would be incentive enough for you to work\n     on it, whether or not the result will land in my tree.  You\n     should instead aim for something so brilliant that we would\n     come to you begging for your permission to include it in our\n     project.\n\nI think it applies to your inquiry as well.\n"},{"id":"199990","messageId":"a71b0f99366188f023e5bc8a5f704184.squirrel@webmail.cs.wisc.edu","threadId":"31646","inReplyTo":"7vfw64txa1.fsf@alter.siamese.dyndns.org","subject":"Re: A generalization of git blame","fromName":"","fromEmail":"xmeng@cs.wisc.edu","sentAt":"2012-09-27T04:18:10Z","receivedAt":"2012-09-27T04:18:10Z","isPatch":false,"sender":{"key":"xmeng@cs.wisc.edu","avatar":null},"body":"> It largely depends on how the user would interact with your program,\n> which is totally unclear as we haven't seen any part of it.  I do\n> not think we have enough information to answer the question at this\n> point.\n\nDo you mean it largely depends on the diversity of options on input and\noutput formats? Currently I just take a path and output lists like:\n\n53: (1da177e4c3f41524e886b7f1b8a0c1fc7321cac2,Linus Torvalds)\n(201b6264ff3865090747f58f48e087c3a35e0dbc,Christoph Lameter)\n(e2bdb933ab8b7db71c318a4ddcf78a9fffd61ecb,Hugh Dickins)\n54: (7cf9c2c76c1a17b32f2da85b50cd4fe468ed44b5,Nick Piggin)\n(e2bdb933ab8b7db71c318a4ddcf78a9fffd61ecb,Hugh Dickins)\n55: (e2bdb933ab8b7db71c318a4ddcf78a9fffd61ecb,Hugh Dickins)\n56: (1da177e4c3f41524e886b7f1b8a0c1fc7321cac2,Linus Torvalds)\n\nThis shows for all lines in the specified file, all commits that have\nchanged a line.\n\nI know this is not enough for a tool. So this is case, does \"how the user\nwould interact with your program\" mean that I should add more options like\nwhich revision to start, some parameters in the algorithm, choice on\ndifferent diff algorithms, and options for customizing the contents of\noutput?\n\n> If it is a trivial script that largely depends on what we already\n> ship, I would not mind carrying it in contrib/.  If it is anything\n> substantial and substantially useful, however, I would suspect that\n> you are better off not be in in my tree, but rather want to be\n> independent.  Finishing it to be useful for your purpose, publishing\n> it somewhere people can take a look at and adding a pointer to\n> https://git.wiki.kernel.org/index.php/InterfacesFrontendsAndTools is\n> probably where you would want to start.\n\nI think it would be helpful for our discussion if I first briefly\nintroduce my approach. It starts at the current head and tracks all the\nlines in the specified file. It then goes along the commit graph\ntopologically. For any two commits A and B connected by an edge from A to\nB (commit B is the parent of commit A) and if A is not a merge commit, it\nfirst calls the tree-diff interface to get the added lines  in A and\ndeleted lines in B, and detect renaming. Then it applies ldiff algorithm\n(http://sourceforge.net/projects/ldiff/ . It is in perl. I adapt it into c\nin my program) to match the added lines and deleted lines. The result is\nthat now we have some added lines, some deleted lines and some changed\nlines. For added lines, I know the this commit is the last one to change\nit. For changed lines, I add this commit to the final result and keep\ntracking them. Currently I ignore those deleted lines. But if A is a merge\ncommit, it doesn't change authorship except for merge conflicts.\n\nI did start with implementing my approach with python. The script keeps\ncalling git-log to get the diff and then apply ldiff. The problem is I\ncannot store whole git-log result in the memory. Even the diff contents of\na specified file can explode my memory. So then I only query for a small\namount of commits each time. This makes my program extremely slow. It\ntakes about half hour to analyze a file in a project with 15000 commits.\n\nThen I refactor my code based on git internal api. It turns out to work\nvery well. Now the program can finish in 10sec instead of half hour. And\nnow I can also apply my tool to larger project like linux kernel.\n\nSo if I want other people to use my tool, I firstly add an entry on the\nwebpage, and then other interested people can get my tool by cloning from\nmy git branch?\n\n\n>  (1) We won't know how useful and interesting your contribution be\n>      for our audience, until we see it; and\n>\n>  (2) If you truly believe in your work (find it useful, find writing\n>      it fun, etc.), that would be incentive enough for you to work\n>      on it, whether or not the result will land in my tree.  You\n>      should instead aim for something so brilliant that we would\n>      come to you begging for your permission to include it in our\n>      project.\n>\n> I think it applies to your inquiry as well.\n\nYou are definitely right. Actually I have spent a lot of time on my tool.\nI just want to know if there are some issues that I should know, otherwise\nit will prevent me from publishing it or prevent it from becoming a\nstandard git built-in tool.\n\nThanks\n"},{"id":"199994","messageId":"7vobksrmwh.fsf@alter.siamese.dyndns.org","threadId":"31646","inReplyTo":"a71b0f99366188f023e5bc8a5f704184.squirrel@webmail.cs.wisc.edu","subject":"Re: A generalization of git blame","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-09-27T06:38:06Z","receivedAt":"2012-09-27T06:38:06Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"xmeng@cs.wisc.edu writes:\n\n>> It largely depends on how the user would interact with your program,\n>> which is totally unclear as we haven't seen any part of it.  I do\n>> not think we have enough information to answer the question at this\n>> point.\n>\n> Do you mean it largely depends on the diversity of options on input and\n> output formats? ...\n> ... I know this is not enough for a tool. So this is case, does \"how the user\n> would interact with your program\" mean that I should add ...\n\nI am not saying anything about what you should or should not do. It\nis your program, and we haven't seen anything about it, other than\nhandwaving, what good it will do to its users, so I am not qualified\nto make such a comment on it yet.  What I meant by \"how the users\nwould interact with...\" are things like this:\n\n - Why users would want to use it in the first place?  What are\n   missing from existing tool set?\n\n - What kind of questions do users ask to the program and how do\n   they ask them?\n\n - How are the answers to these questions presented by the program\n   to the users?\n\n - How do users interpret and use these answers in what way?\n\nNotice that I didn't include \"How do you compute the answers?\"  When\nwe are initially evaluating a feature at \"how do they interact\" level,\nwe are not interested in the implementation at all.\n"}]}