{"thread":{"id":"5911","subject":"On blame/pickaxe","startedAt":"2006-10-13T01:43:46Z","lastAt":"2006-10-21T03:20:38Z","messageCount":12,"participants":["Junio C Hamano","Petr Baudis","Josef Weidendorfer","Andy Whitcroft","Luben Tuikov"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"28710","messageId":"7vr6xddm7h.fsf@assigned-by-dhcp.cox.net","threadId":"5911","inReplyTo":null,"subject":"On blame/pickaxe","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-10-13T01:43:46Z","receivedAt":"2006-10-13T01:43:46Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I have something that is tentatively called pickaxe, but that is\ndifferent from \"diff -S<pickaxe>\".  The name will need to\nchange, perhaps to git-blame.\n\nIt's quite a while since the original algorithm sketch that led\nto the current git-blame was posted here; I suspect that most of\nthe people recently joined the list haven't seen it.  The idea\nin there still applies, though...\n\nHere is a re-drawn sketch of how the 'pickaxe' edition of the\nalgorithm works.\n\n0. Outline.\n\nWe track range of lines from a path in one revision.  That's\nwhat \"-L n,m\", \"path\", and \"commit\" parameters to the command\nare about.\n\nWhen the program starts, the commit given on the command line is\nsuspected to be responsible for all lines in the given range.\nBut being a suspect and determined to be the guilty party are\ndifferent things.\n\nThe name of the game is \"not taking responsibility but passing\nthe blame to your parents\".  In other words, \"that's not a new\nproblem I introduced -- it was there before my patch was\napplied\".  You are exonerated for those lines that you can\nsuccessfully pass blame to your parent, making that parent a new\nsuspect for the lines.  There will remain lines you cannot pass\nblame to anybody else -- you will be determined to be the guilty\nparty for them.  When nobody can pass any more blame to anybody\nelse, the dance stops and we will know who is guilty for every\nline of the input.\n\n\n1. Data structure.\n\nWe keep track of who the current suspect for each line is in the\nstructure called 'scoreboard'.  It is a collection of ranges,\ncalled 'blame_entry'.\n\nEach blame_entry describes which lines (in the final image) it\nis about, who the current suspect for the range is, if the\nsuspect is already known to be guilty, where in the suspected\ncommit the lines came from (path and line number).\n\nIn the 'blame' implementation, a suspect is represented by a\ncommit object with one path hanging to its util field.\n'pickaxe' edition introduces the concept of 'origin', which is a\npair of <commit,path>.  We currently do not use more than one\npath per commit, but hopefully we will soon.\n\n\n2. Operation.\n\nFirst the scoreboard is initialized with a single blame_entry\nthat makes the path in the commit on the command line the\nsuspect for all lines.\n\nThen, we repeatedly pick one entry from the scoreboard, and give\na chance to the suspect to exonerate himself, by calling\npass_blame().  The suspect passes the blame to its parents by\nupdating the scoreboard, removing his name from ranges of lines\nhe can prove that came from his parent and instead writing that\nsuspected parent's name.  Inside pass_blame(), just before it\nreturns, if the suspect cannot pass blame for some lines to\nanybody else, it becomes guilty for them.\n\nWhen there is no blame_entry in the scoreboard whose truly\nguilty party is still undetermined, we have fully blamed the\ninput, and the loop finishes.\n\n\n3. Passing the blame.\n\nYou (a <commit,path> tuple) are suspected for introducing\ncertain lines, and you would want to pass blame to your parent.\nHow would you do that?\n\nFirst, you find if your parent has the same path; if not, you\nfind if between your parent and you there was a rename and find\nthe original path in the parent.  If you are a merge, you do so\nfor all your parents.  The path in the parent and your path may\nhave many common lines, and if the lines you are the suspect are\nthe same as the ones in the parent, you can pass the blame,\nbecause these lines were there before you touched them.\n\nHow would you find what's common?  We run \"diff\" (diff -u0).\nUnified context-0 diff would give something like:\n\n        @@ -n,m +l,k @@\n        -removed\n        +added\n        ...\n\nIn this application, we are not interested in the diff text\nitself at all.  In fact, we are interested in what's outside the\ndiff.  If the above is output from parent to you, what it tells\nus is that lines before your line \"l\" are the same as lines\nbefore parent's \"n\", so if the above is the first hunk, you can\nsay your lines 1..(l-1) came from your parent and you are not\nresponsible for them.  The above hunk also tells us that in your\npath, lines after (l+k) are the same as the lines in parent's\nlines (n+m); we will know how many such same lines there are\n(could be zero) by inspecting the next hunk.\n\nFor efficiency reasons, inside pass_blame(), we run just one\ndiff between the parent and you, and scan the blame_entry for\nthe same <commit,path> in the scoreboard, and check overlap with\neach of them.  Suppose we are suspected for these lines:\n\n                <---- e ----->\n\nand by looking the diff, we determined the range from one parent\nis like this:\n\n                   <--p--->\n\nThen we can split the blame_entry into three parts:\n\n                <-><--p---><->\n\nYou are still suspected for the first and the last part of the\noriginal entry, but for the mid-part you successfully passed the\nblame to that parent.  Depending on how the ranges overlap, this\nmay split into two, or parent may take blame for the whole range\n(i.e. no split).  This is computed in blame_overlap().\n\nWhen done with one parent, if you are a merge, you will then try\nto pass the blame on the remaining part that you are still\nsuspected for to other parents.\n\nThe classic 'blame' algorithm stops here, and the current\npickaxe does the same; you take responsibility for the\nremainder.\n\n\n4. Passing more blame.\n\nInstead of taking responsibility for the remainder, there are\nother ways to find other people to pass blame on.  That's what\nthe \"NEEDSWORK\" comment in pass_blame() is about.\n\nA typical example is a change that moves one static C function\nfrom lower part of the file to upper part of the same file,\nbecause you added a new caller in the middle.  The path in your\nparent and the path in you would look like this:\n\n        parent                          you\n\n        A                               static foo() {\n        B                               }\n        C                               A\n        D                               B\n        E                               C\n        F                               D\n        G                               ... call foo();\n        static foo() {                  E\n        }                               F\n        I                               G\n        J                               I\n\nWith the common part finding code with diff, you will be able to\npass blames for lines A B C D E F G I J to your parent.  You are\ntruly guilty for introducing \"... call foo();\".  The problem\nhere is that in addition, you will be blamed for the lines that\nimplement \"static foo() { ... }\" at the beginning of your file.\n\nTo blame the implementation of foo() to the parent, we could do\nsomething like this:\n\n        for each blame_entry that you are still suspected for,\n        diff those lines (and only those lines) with the parent,\n        to see if you find a copy.  If there is a copy, you can\n        pass the blame to the parent.\n\nThis needs to be limited for non-trivial changes only, though.\nFor example, one of the typical things you would do is to add one\n\"else if\" clause to a sequence of already existing \"if .. else if\n..\" chain, like this:\n\n        if (foo) {\n                ...\n        }\n        else if (bar) {\n                ...\n+       }\n+       else if (baz) {\n+               ...\n        }\n\nYou are suspected for these three lines; if the \"find copies\nagain\" is allowed to find any insignificant copy, the first line\n(closing brace) you introduced could easily be blamed to an\nunrelated line anywhere in the parent that match /^\\t\\}$/.  To\nprevent such nonsense from happening, we need to limit such\n\"find copies\" attempt to say minimum of N lines (and minimum of\nM tokens that consist of non-whitespace, non-punctuation\nletters).  Also we probably would not want to find a match in\nthe whole parent but only in the part of the parent that is\nremoved in the parent-to-you diff.\n\nAnother typical example is a code restructuring to move one\nfunction from a file to another file.  The same \"find copies\"\nprinciple, and caveat for small and insignificant copies, apply\nto this situation as well.  If it is a code movement, the file\nthat the function moved from needs to be identified, which can\nbe done by running diff-tree between parent and you -- anything\nthat was modified or removed is a good candidate to look for\nsuch copies.  Again, we probably need to limit the copy-finding\nsource to the part that was removed from the parent in the diff\nto you.\n\nAfter the operation 3 (Passing the blame) runs, if movement of\nlines from another file is detected as in the above sketch, we\nwill pass blame to an unrelated path in the parent.  Some lines\nare blamed on the file we started tracking in the parent, and\nsome other lines are blamed on a different file in the parent.\nThis is why 'pickaxe' uses <commit,path> tuple (aka 'origin') to\nrepresent a suspect.\n\nAll of this sounds quite simple and not so difficult to code,\nalthough rejecting insignificant copies would involve fair\namount of heuristic tweaking like I needed to do while working\non the rename detection.\n"},{"id":"28716","messageId":"7vu028d51r.fsf@assigned-by-dhcp.cox.net","threadId":"5911","inReplyTo":"7vr6xddm7h.fsf@assigned-by-dhcp.cox.net","subject":"Re: On blame/pickaxe","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-10-13T07:54:24Z","receivedAt":"2006-10-13T07:54:24Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"In an earlier message, I talked about pickaxe data structure\nthat has potential for blaming more than one paths in a single\nrevision.\n\nI was talking about the future enhancements, but it turns out\nthat there is a corner case that the feature is already needed\nusing the classic blame algorithm, and running blame shows its\nlimitation through.\n\nThe scenario is like this:\n\n - initial has two files A and B\n - branch left renames A to C and adds stuff at the top.\n - branch right renames B to C and adds stuff at the bottom.\n - left and right is merged and leaves one file, C, by taking\n   what both branches did.\n - annotate C from the top.\n\nThe parts that came from A and B in the initial revision should\nbe assigned to these files in the initial commit.  If you look\nat the blame output, you will see it fails to do so.  pickaxe\ngives what is expected.\n\n-- >8 --\n#!/bin/sh\n\nif test -d .git\nthen\n        echo 'please run this in a fresh empty directory'\n\texit\nfi\n\ngit init-db\n\nfor i in 1 2 3 4 5 6 7 8 9 ; do echo line line line $i ; done >A\nfor i in A B C D E F G H I ; do echo line line line $i ; done >B\n\ngit add A B\ngit commit --author='Initial <initial@author>' -m initial\n\ngit branch right\ngit branch left\n\n# Left\ngit checkout left\nfor i in 1 2 3; do echo added by left; done >C\ncat A >>C\nrm -f A B\ngit update-index --add --remove A B C\ngit commit --author='Left <left@branch>' -m Left\n\n# Right\ngit checkout right\ncat B >C\nfor i in 1 2 3; do echo added by right; done >>C\nrm -f A B\ngit update-index --add --remove A B C\ngit commit --author='Right <right@branch>' -m Right\n\n# Merge them; this should fail which is expected\ngit pull . left\n{\n\tgit cat-file blob :3:C\n\tgit cat-file blob :2:C\n} >C\ngit update-index C\ngit commit --author='Merge <merge@branch>' -m 'Changes are merged.'\nrm -f C~*\n\necho blame\ngit blame -f -n -t C\n\necho pickaxe\ngit pickaxe -f -n -t C\n"},{"id":"28756","messageId":"7vwt739org.fsf@assigned-by-dhcp.cox.net","threadId":"5911","inReplyTo":"7vr6xddm7h.fsf@assigned-by-dhcp.cox.net","subject":"Re: On blame/pickaxe","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-10-14T10:26:43Z","receivedAt":"2006-10-14T10:26:43Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <junkio@cox.net> writes:\n\n> 4. Passing more blame.\n>\n> Instead of taking responsibility for the remainder, there are\n> other ways to find other people to pass blame on.  That's what\n> the \"NEEDSWORK\" comment in pass_blame() is about.\n\nI've spent a few hours tonight to further work (eh, \"have fun\")\non this.  The version at the tip of \"pu\" implements detection of\na case like this:\n\n> A typical example is a change that moves one static C function\n> from lower part of the file to upper part of the same file,\n> because you added a new caller in the middle.  The path in your\n> parent and the path in you would look like this:\n>\n>         parent                          you\n>\n>         A                               static foo() {\n>         B                               }\n>         C                               A\n>         D                               B\n>         E                               C\n>         F                               D\n>         G                               ... call foo();\n>         static foo() {                  E\n>         }                               F\n>         I                               G\n>         J                               I\n>\n> With the common part finding code with diff, you will be able to\n> pass blames for lines A B C D E F G I J to your parent.  You are\n> truly guilty for introducing \"... call foo();\".  The problem\n> here is that in addition, you will be blamed for the lines that\n> implement \"static foo() { ... }\" at the beginning of your file.\n\nYou can use the pickaxe on its source itself, like this:\n\n\tgit pickaxe -n master..pu builtin-pickaxe.c\n\nIf you compare this with output from:\n\n\tgit log --pretty=short -p master..pu builtin-pickaxe.c\n\nyou will notice the line-movement detection in action.\n\nDuring the course of development, I had to move quite a few\nstatic functions around so that they are defined before their\nfirst call site.  This is partly because I am very bad at\ninitial planning (who is?) and this still being in experimental\nstage I did not bother declaring static functions upfront as\nforward declarations.\n\nFor example, commit db3f0f2 introduces find_last_in_target()\nfunction, but it was moved up by commit b5c0e4f (near the tip of\n\"pu\").  pickaxe blames the implementation of it to db3f0f20, and\nalso notices that the bulk of its logic was actually copied from\nthe implementation of pass_blame_to_parent() function in commit\nb14dc9ef (the initial commit that introduced builtin-pickaxe.c).\n\nWhat _ought_ to come next is to detect line movement across\nfiles, but I'll go to bed for now.\n"},{"id":"28779","messageId":"7vfydq79ae.fsf@assigned-by-dhcp.cox.net","threadId":"5911","inReplyTo":"7vwt739org.fsf@assigned-by-dhcp.cox.net","subject":"Re: On blame/pickaxe","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-10-14T23:43:53Z","receivedAt":"2006-10-14T23:43:53Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <junkio@cox.net> writes:\n\n> Junio C Hamano <junkio@cox.net> writes:\n>\n>> 4. Passing more blame.\n>>\n>> Instead of taking responsibility for the remainder, there are\n>> other ways to find other people to pass blame on.  That's what\n>> the \"NEEDSWORK\" comment in pass_blame() is about.\n>\n> I've spent a few hours tonight to further work (eh, \"have fun\")\n> on this.  The version at the tip of \"pu\" implements detection of\n> a case like this:\n> ...\n> You can use the pickaxe on its source itself, like this:\n>\n> \tgit pickaxe -n master..pu builtin-pickaxe.c\n>\n> If you compare this with output from:\n>\n> \tgit log --pretty=short -p master..pu builtin-pickaxe.c\n>\n> you will notice the line-movement detection in action.\n>\n> During the course of development, I had to move quite a few\n> static functions around so that they are defined before their\n> first call site.  This is partly because I am very bad at\n> initial planning (who is?) and this still being in experimental\n> stage I did not bother declaring static functions upfront as\n> forward declarations.\n>\n> For example, commit db3f0f2 introduces find_last_in_target()\n> function, but it was moved up by commit b5c0e4f (near the tip of\n> \"pu\").  pickaxe blames the implementation of it to db3f0f20, and\n> also notices that the bulk of its logic was actually copied from\n> the implementation of pass_blame_to_parent() function in commit\n> b14dc9ef (the initial commit that introduced builtin-pickaxe.c).\n>\n> What _ought_ to come next is to detect line movement across\n> files, but I'll go to bed for now.\n\nAnd this implements it.  After testing it some more, I'll have\nit near the tip of \"pu\" sometime tonight.\n\nI have to admit that I am becoming quite fond of the name\n\"pickaxe\", by the way.\n\nI consider that the \"following the changed lines and see where\nit came from\" you described in the ancient message:\n\n    http://thread.gmane.org/gmane.comp.version-control.git/27/focus=217\n\nthe holy grail of software archaeology.  Once we have it, I\nwould feel I am pretty much _done_ with git.  It will have\neverything I want it to do.\n\nMy \"diff -S\" (where the \"pickaxe\" name started) was a crude\nfirst step to achieve that goal.  The way I envisioned it was\nthat you would feed the lines 50-89 as a single -S parameter to\n\"git whatchanged\" and the tool finds the commit that touched\nthat area, and the Porcelain would either figure out what the\ncorresponding lines in the previous commit look like or ask the\nuser to highlight what to dig deeper interactively, and restart\nanother \"whatchanged\" with adjusted value for -S.  Unfortunately\nnobody wrote such a Porcelain command.\n\nI think the command with this patch gets us closer to that goal;\nalthough it still does not have a way to detect \"oh these five\ncopies were consolidated into one\" (I'd imagine we _could_ do\nthat in find_copy_in_parent() function if we really wanted to --\nbut that would be a tad expensive).  In any case, I think this\nis going in the right direction.\n\nBefore anybody asks, the example Daniel Barkalow gave on date.c\nis far trickier and even this version would not catch it.  It\nrequires digging random, distant, ancestors in order to look for\nlines that were lost by an earlier removal.\n\n-- >8 --\ngit-pickaxe: blame cut-and-paste lines.\n\nThis completes the initial round of git-pickaxe.  In addition to\nthe line movement the previous round implements, this finds new\nlines that were created by moving or cutting-and-pasting lines\nfrom different path in the parent.\n\nWith this,\n\n\tgit pickaxe -f -n v1.4.0 -- revision.c\n\nfinds that major part of that file actually came from rev-list.c\nwhen Linus split the latter at commit ae563642 and blames them\nto earlier commits that touches rev-list.c.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n builtin-pickaxe.c |   71 +++++++++++++++++++++++++++++++++++------------------\n 1 files changed, 47 insertions(+), 24 deletions(-)\n\ndiff --git a/builtin-pickaxe.c b/builtin-pickaxe.c\nindex 3f9f679..1124919 100644\n--- a/builtin-pickaxe.c\n+++ b/builtin-pickaxe.c\n@@ -638,39 +638,16 @@ static int find_copy_in_blob(struct scor\n \treturn 0;\n }\n \n-static int find_copy_in_parent(struct scoreboard *sb,\n-\t\t\t       struct origin *target,\n-\t\t\t       struct commit *parent,\n-\t\t\t       struct origin *porigin)\n-{\n-\tint last_in_target;\n-\n-\tlast_in_target = find_last_in_target(sb, target);\n-\tif (last_in_target < 0)\n-\t\treturn 1; /* nothing remains for this target */\n-\n-\t/* NEEDSWORK: run diff-tree between target->commit with parent\n-\t * to find the paths that were modified from parent, and find\n-\t * copies in the parent; if we find any we can pass blame to it.\n-\t * We have checked path in porigin so do not bother checking it\n-\t * again (but porigin might be NULL).\n-\t */\n-\n-\treturn 0;\n-}\n-\n static int find_move_in_parent(struct scoreboard *sb,\n \t\t\t       struct origin *target,\n \t\t\t       struct origin *parent)\n {\n-\tint last_in_target;\n \tstruct blame_entry *ent;\n \tmmfile_t file_p;\n \tchar type[10];\n \tchar *blob_p;\n \n-\tlast_in_target = find_last_in_target(sb, target);\n-\tif (last_in_target < 0)\n+\tif (find_last_in_target(sb, target) < 0)\n \t\treturn 1; /* nothing remains for this target */\n \n \tblob_p = read_sha1_file(parent->blob_sha1, type,\n@@ -690,6 +667,52 @@ static int find_move_in_parent(struct sc\n \treturn 0;\n }\n \n+static int find_copy_in_parent(struct scoreboard *sb,\n+\t\t\t       struct origin *target,\n+\t\t\t       struct commit *parent,\n+\t\t\t       struct origin *porigin)\n+{\n+\tstruct diff_options diff_opts;\n+\tconst char *paths[1];\n+\tint no_more, i;\n+\n+\tif (find_last_in_target(sb, target) < 0)\n+\t\treturn 1; /* nothing remains for this target */\n+\n+\tdiff_setup(&diff_opts);\n+\tdiff_opts.recursive = 1;\n+\tdiff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;\n+\n+\t/* Try \"find copies harder\" on new path */\n+\tif (!porigin || strcmp(target->path, porigin->path)) {\n+\t\tdiff_opts.detect_rename = DIFF_DETECT_COPY;\n+\t\tdiff_opts.find_copies_harder = 1;\n+\t}\n+\tpaths[0] = NULL;\n+\tdiff_tree_setup_paths(paths, &diff_opts);\n+\tif (diff_setup_done(&diff_opts) < 0)\n+\t\tdie(\"diff-setup\");\n+\tdiff_tree_sha1(parent->tree->object.sha1,\n+\t\t       target->commit->tree->object.sha1,\n+\t\t       \"\", &diff_opts);\n+\tdiffcore_std(&diff_opts);\n+\n+\tfor (i = no_more = 0; !no_more && i < diff_queued_diff.nr; i++) {\n+\t\tstruct diff_filepair *p = diff_queued_diff.queue[i];\n+\t\tstruct origin *new_porigin;\n+\t\tif (!DIFF_FILE_VALID(p->one))\n+\t\t\tcontinue; /* does not exist in parent */\n+\t\tif (porigin && !strcmp(p->one->path, porigin->path))\n+\t\t\tcontinue; /* find_move already checked this path */\n+\n+\t\tnew_porigin = find_origin(sb, parent, p->one->path);\n+\t\tno_more = find_move_in_parent(sb, target, new_porigin);\n+\t}\n+\tdiff_flush(&diff_opts);\n+\n+\treturn no_more;\n+}\n+\n #define MAXPARENT 16\n static void pass_blame(struct scoreboard *sb, struct origin *origin)\n {\n-- \n1.4.3.rc2.g195ab\n"},{"id":"28829","messageId":"20061016022159.GZ20017@pasky.or.cz","threadId":"5911","inReplyTo":"7vfydq79ae.fsf@assigned-by-dhcp.cox.net","subject":"Re: On blame/pickaxe","fromName":"Petr Baudis","fromEmail":"pasky@suse.cz","sentAt":"2006-10-16T02:21:59Z","receivedAt":"2006-10-16T02:21:59Z","isPatch":false,"sender":{"key":"pasky@ucw.cz","avatar":"https://avatars.githubusercontent.com/u/18439?v=4"},"body":"  Thanks for the nice writeup!\n\nDear diary, on Fri, Oct 13, 2006 at 03:43:46AM CEST, I got a letter\nwhere Junio C Hamano <junkio@cox.net> said that...\n> When done with one parent, if you are a merge, you will then try\n> to pass the blame on the remaining part that you are still\n> suspected for to other parents.\n\n  (This got me nervous but I guess it actually makes sense - if only one\nparent modified a line, it's right to pass the blame up; else if you\ntook one parent's version verbatim, it's right to pass the blame up as\nwell (I think); else you've already got the blame assigned to the merge\ncommit and everything is all right.)\n\n> To blame the implementation of foo() to the parent, we could do\n> something like this:\n> \n>         for each blame_entry that you are still suspected for,\n>         diff those lines (and only those lines) with the parent,\n>         to see if you find a copy.  If there is a copy, you can\n>         pass the blame to the parent.\n\n  Now, this is very nifty and so for moving functions around, but I\nthink it is very dangerous for anything where ordering matters - large\narrays definitions, patch series files, etc. In that case, you've\ncompletely ommitted the fact that the movement occured, which can be\ncrucial and based on the current behaviour of the tools, I think people\nexpect this now. To put it shortly, \"who wrote this line\" vs \"who put\nthis line here\".\n\n  I would prefer to stay more conservative here by default. Graphical\ntools could solve this by some nice presentation like\n\n\t3fea1 int moved()                         -.\n\t3fea1 {                                    |\n\t28abc \twatch(more + anime);               | 17d50\n\t17d50 \treturn !hypno;                     |\n\t3fea1 }                                   -'\n\t\n\nDear diary, on Sun, Oct 15, 2006 at 01:43:53AM CEST, I got a letter\nwhere Junio C Hamano <junkio@cox.net> said that...\n> I have to admit that I am becoming quite fond of the name\n> \"pickaxe\", by the way.\n\n  Gaah, please don't. ;-)\n\n-- \n\t\t\t\tPetr \"Pasky\" Baudis\nStuff: http://pasky.or.cz/\n#!/bin/perl -sp0777i<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<j]dsj\n$/=unpack('H*',$_);$_=`echo 16dio\\U$k\"SK$/SM$n\\EsN0p[lN*1\nlK[d2%Sa2/d0$^Ixp\"|dc`;s/\\W//g;$_=pack('H*',/((..)*)$/)\n"},{"id":"28837","messageId":"7v8xjgvjys.fsf@assigned-by-dhcp.cox.net","threadId":"5911","inReplyTo":"20061016022159.GZ20017@pasky.or.cz","subject":"Re: On blame/pickaxe","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-10-16T06:43:55Z","receivedAt":"2006-10-16T06:43:55Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Petr Baudis <pasky@suse.cz> writes:\n\n>   Thanks for the nice writeup!\n>\n> Dear diary, on Fri, Oct 13, 2006 at 03:43:46AM CEST, I got a letter\n> where Junio C Hamano <junkio@cox.net> said that...\n>> When done with one parent, if you are a merge, you will then try\n>> to pass the blame on the remaining part that you are still\n>> suspected for to other parents.\n>\n>   (This got me nervous but I guess it actually makes sense - if only one\n> parent modified a line, it's right to pass the blame up; else if you\n> took one parent's version verbatim, it's right to pass the blame up as\n> well (I think); else you've already got the blame assigned to the merge\n> commit and everything is all right.)\n\nWell, this part is the classic blame algorithm.  The beauty of\nit is that a merge case falls out as a natural consequence of\nthe one-parent case and you do not have to do anything special.\nYou either inherited a line from your parent (or one or more of\nyour parents) or you created the line yourself.  If you subtract\nwhat you can blame your parents for, the remainder is what you\nintroduced.  The number of parents you have does not have any\neffect on that logic.\n\n>   Now, this is very nifty and so for moving functions around, but I\n> think it is very dangerous for anything where ordering matters - large\n> arrays definitions, patch series files, etc. In that case, you've\n> completely ommitted the fact that the movement occured, which can be\n> crucial and based on the current behaviour of the tools, I think people\n> expect this now. To put it shortly, \"who wrote this line\" vs \"who put\n> this line here\".\n\nThat's exactly why we have -f and -n options, so that the\nprogram that reads from blame output can tell where things came\nfrom.  It is not about \"who wrote it\" vs \"who put it here\";\npickaxe gives a lot more than that: \"where did this originally\ncome from\", i.e. \"by whom in which file at what line number was\nthe line created\".\n\nIf the user is not prepared to see code movement, pickaxe can be\nrun without -M nor -C to get the classic blame output.\n\nBy the way, We would not want to do the code movement (or\ncopying from unrelated file) for very trivial lines.  E.g. you\nwould not want to blame the following three lines:\n\n        +\t}\n        +}\n        +#endif\n\nto a random file that happens to have the exact copy of the\nabove that is not related at all.  Something like the above can\nhappen almost anywhere.  The current implementation of -M/-C\ndoes not do this very well.  find_copy_in_blob() currently\npasses blame to the parent when it finds nontrivial copies, but\ninstead it should inspect the patch and return a score, and the\ncaller should take the parent with the best match and assign\nblame to it.\n"},{"id":"28845","messageId":"200610161602.49811.Josef.Weidendorfer@gmx.de","threadId":"5911","inReplyTo":"7v8xjgvjys.fsf@assigned-by-dhcp.cox.net","subject":"Re: On blame/pickaxe","fromName":"Josef Weidendorfer","fromEmail":"josef.weidendorfer@gmx.de","sentAt":"2006-10-16T14:02:49Z","receivedAt":"2006-10-16T14:02:49Z","isPatch":false,"sender":{"key":"josef.weidendorfer@gmx.de","avatar":null},"body":"Hi,\n\nthis blame-passing thing really looks very promising and powerful.\n\nOn Monday 16 October 2006 08:43, you wrote:\n> If the user is not prepared to see code movement, pickaxe can be\n> run without -M nor -C to get the classic blame output.\n\nAnother blame-passing heuristic would be very interesting for code:\n\"Ignore white-space changes\".\nThis way, commits which only do some reindentations simply are skipped.\n\nIt looks like such a thing would just be a matter of passing \"-b\" to\nexecutions of \"diff\" in the blame-passing algorithm.\n\nJosef\n"},{"id":"28847","messageId":"453393E5.3020203@shadowen.org","threadId":"5911","inReplyTo":"200610161602.49811.Josef.Weidendorfer@gmx.de","subject":"Re: On blame/pickaxe","fromName":"Andy Whitcroft","fromEmail":"apw@shadowen.org","sentAt":"2006-10-16T14:15:01Z","receivedAt":"2006-10-16T14:15:01Z","isPatch":false,"sender":{"key":"apw@shadowen.org","avatar":"https://gravatar.com/avatar/d3088262854661a913ef35cc40fedcc270142d4461791142bc1ea0b2a4e2e147?d=mp&s=160"},"body":"Josef Weidendorfer wrote:\n> Hi,\n> \n> this blame-passing thing really looks very promising and powerful.\n> \n> On Monday 16 October 2006 08:43, you wrote:\n>> If the user is not prepared to see code movement, pickaxe can be\n>> run without -M nor -C to get the classic blame output.\n> \n> Another blame-passing heuristic would be very interesting for code:\n> \"Ignore white-space changes\".\n> This way, commits which only do some reindentations simply are skipped.\n> \n> It looks like such a thing would just be a matter of passing \"-b\" to\n> executions of \"diff\" in the blame-passing algorithm.\n\nI am thinking that that is probabally going to need to be optional, for\nexample python the indentation is everything to the meaning of the code.\n\n-apw\n"},{"id":"28882","messageId":"20061016234547.21649.qmail@web31809.mail.mud.yahoo.com","threadId":"5911","inReplyTo":"7vr6xddm7h.fsf@assigned-by-dhcp.cox.net","subject":"Re: On blame/pickaxe","fromName":"Luben Tuikov","fromEmail":"ltuikov@yahoo.com","sentAt":"2006-10-16T23:45:47Z","receivedAt":"2006-10-16T23:45:47Z","isPatch":false,"sender":{"key":"ltuikov@yahoo.com","avatar":null},"body":"Junio,\n\nExcellent write up.  Comments inline:\n\n--- Junio C Hamano <junkio@cox.net> wrote:\n> I have something that is tentatively called pickaxe, but that is\n> different from \"diff -S<pickaxe>\".  The name will need to\n> change, perhaps to git-blame.\n> \n> It's quite a while since the original algorithm sketch that led\n> to the current git-blame was posted here; I suspect that most of\n> the people recently joined the list haven't seen it.  The idea\n> in there still applies, though...\n> \n> Here is a re-drawn sketch of how the 'pickaxe' edition of the\n> algorithm works.\n> \n> 0. Outline.\n> \n> We track range of lines from a path in one revision.  That's\n> what \"-L n,m\", \"path\", and \"commit\" parameters to the command\n> are about.\n> \n> When the program starts, the commit given on the command line is\n> suspected to be responsible for all lines in the given range.\n> But being a suspect and determined to be the guilty party are\n> different things.\n> \n> The name of the game is \"not taking responsibility but passing\n> the blame to your parents\".  In other words, \"that's not a new\n> problem I introduced -- it was there before my patch was\n> applied\".  You are exonerated for those lines that you can\n> successfully pass blame to your parent, making that parent a new\n> suspect for the lines.  There will remain lines you cannot pass\n> blame to anybody else -- you will be determined to be the guilty\n> party for them.  When nobody can pass any more blame to anybody\n> else, the dance stops and we will know who is guilty for every\n> line of the input.\n\nStopping early -- that's good.\n\n> 1. Data structure.\n> \n> We keep track of who the current suspect for each line is in the\n> structure called 'scoreboard'.  It is a collection of ranges,\n> called 'blame_entry'.\n> \n> Each blame_entry describes which lines (in the final image) it\n> is about, who the current suspect for the range is, if the\n> suspect is already known to be guilty, where in the suspected\n> commit the lines came from (path and line number).\n> \n> In the 'blame' implementation, a suspect is represented by a\n> commit object with one path hanging to its util field.\n> 'pickaxe' edition introduces the concept of 'origin', which is a\n> pair of <commit,path>.  We currently do not use more than one\n> path per commit, but hopefully we will soon.\n> \n> \n> 2. Operation.\n> \n> First the scoreboard is initialized with a single blame_entry\n> that makes the path in the commit on the command line the\n> suspect for all lines.\n> \n> Then, we repeatedly pick one entry from the scoreboard, and give\n> a chance to the suspect to exonerate himself, by calling\n> pass_blame().  The suspect passes the blame to its parents by\n> updating the scoreboard, removing his name from ranges of lines\n> he can prove that came from his parent and instead writing that\n> suspected parent's name.  Inside pass_blame(), just before it\n> returns, if the suspect cannot pass blame for some lines to\n> anybody else, it becomes guilty for them.\n> \n> When there is no blame_entry in the scoreboard whose truly\n> guilty party is still undetermined, we have fully blamed the\n> input, and the loop finishes.\n> \n> \n> 3. Passing the blame.\n> \n> You (a <commit,path> tuple) are suspected for introducing\n> certain lines, and you would want to pass blame to your parent.\n> How would you do that?\n> \n> First, you find if your parent has the same path; if not, you\n> find if between your parent and you there was a rename and find\n> the original path in the parent.  If you are a merge, you do so\n> for all your parents.  The path in the parent and your path may\n> have many common lines, and if the lines you are the suspect are\n> the same as the ones in the parent, you can pass the blame,\n> because these lines were there before you touched them.\n\nDo you handle the case where a merge had a conflict and\nthe user changed the code (resolved) and then committed?\nIn this case some lines will have to be blamed on the\nmerge commit itself.\n\n> How would you find what's common?  We run \"diff\" (diff -u0).\n> Unified context-0 diff would give something like:\n> \n>         @@ -n,m +l,k @@\n>         -removed\n>         +added\n>         ...\n> \n> In this application, we are not interested in the diff text\n> itself at all.  In fact, we are interested in what's outside the\n> diff.  If the above is output from parent to you, what it tells\n> us is that lines before your line \"l\" are the same as lines\n> before parent's \"n\", so if the above is the first hunk, you can\n> say your lines 1..(l-1) came from your parent and you are not\n> responsible for them.  The above hunk also tells us that in your\n> path, lines after (l+k) are the same as the lines in parent's\n> lines (n+m); we will know how many such same lines there are\n> (could be zero) by inspecting the next hunk.\n> \n> For efficiency reasons, inside pass_blame(), we run just one\n> diff between the parent and you, and scan the blame_entry for\n> the same <commit,path> in the scoreboard, and check overlap with\n> each of them.  Suppose we are suspected for these lines:\n> \n>                 <---- e ----->\n> \n> and by looking the diff, we determined the range from one parent\n> is like this:\n> \n>                    <--p--->\n> \n> Then we can split the blame_entry into three parts:\n> \n>                 <-><--p---><->\n> \n> You are still suspected for the first and the last part of the\n> original entry, but for the mid-part you successfully passed the\n> blame to that parent.  Depending on how the ranges overlap, this\n> may split into two, or parent may take blame for the whole range\n> (i.e. no split).  This is computed in blame_overlap().\n> \n> When done with one parent, if you are a merge, you will then try\n> to pass the blame on the remaining part that you are still\n> suspected for to other parents.\n> \n> The classic 'blame' algorithm stops here, and the current\n> pickaxe does the same; you take responsibility for the\n> remainder.\n> \n> \n> 4. Passing more blame.\n> \n> Instead of taking responsibility for the remainder, there are\n> other ways to find other people to pass blame on.  That's what\n> the \"NEEDSWORK\" comment in pass_blame() is about.\n> \n> A typical example is a change that moves one static C function\n> from lower part of the file to upper part of the same file,\n> because you added a new caller in the middle.  The path in your\n> parent and the path in you would look like this:\n> \n>         parent                          you\n> \n>         A                               static foo() {\n>         B                               }\n>         C                               A\n>         D                               B\n>         E                               C\n>         F                               D\n>         G                               ... call foo();\n>         static foo() {                  E\n>         }                               F\n>         I                               G\n>         J                               I\n> \n> With the common part finding code with diff, you will be able to\n> pass blames for lines A B C D E F G I J to your parent.  You are\n> truly guilty for introducing \"... call foo();\".  The problem\n> here is that in addition, you will be blamed for the lines that\n> implement \"static foo() { ... }\" at the beginning of your file.\n\nHow about move-and-edit scenario?  Wouldn't that make the algorithm\nsomewhat complicated if we wanted to properly describe (blame)\nmove-and-edit?  Or are you going to detect only simple hunk-moves?\n\n> To blame the implementation of foo() to the parent, we could do\n> something like this:\n> \n>         for each blame_entry that you are still suspected for,\n>         diff those lines (and only those lines) with the parent,\n>         to see if you find a copy.  If there is a copy, you can\n>         pass the blame to the parent.\n> \n> This needs to be limited for non-trivial changes only, though.\n> For example, one of the typical things you would do is to add one\n> \"else if\" clause to a sequence of already existing \"if .. else if\n> ..\" chain, like this:\n> \n>         if (foo) {\n>                 ...\n>         }\n>         else if (bar) {\n>                 ...\n> +       }\n> +       else if (baz) {\n> +               ...\n>         }\n> \n> You are suspected for these three lines; if the \"find copies\n> again\" is allowed to find any insignificant copy, the first line\n> (closing brace) you introduced could easily be blamed to an\n> unrelated line anywhere in the parent that match /^\\t\\}$/.  To\n> prevent such nonsense from happening, we need to limit such\n> \"find copies\" attempt to say minimum of N lines (and minimum of\n> M tokens that consist of non-whitespace, non-punctuation\n> letters).  Also we probably would not want to find a match in\n> the whole parent but only in the part of the parent that is\n> removed in the parent-to-you diff.\n> \n> Another typical example is a code restructuring to move one\n> function from a file to another file.  The same \"find copies\"\n> principle, and caveat for small and insignificant copies, apply\n> to this situation as well.  If it is a code movement, the file\n> that the function moved from needs to be identified, which can\n> be done by running diff-tree between parent and you -- anything\n> that was modified or removed is a good candidate to look for\n> such copies.  Again, we probably need to limit the copy-finding\n> source to the part that was removed from the parent in the diff\n> to you.\n\nHere I see a lot of _arbitration_ in the form of \"choose a good\nvalue for N and a good value for M\".\n\nIs it possible that we do away with such \"user\" arbitration,\nand instead find an algorithm that solves every case...? Even\nif we have to go back to a simpler \"blame\".\n\nI'm concerned that with \"user\" arbitration, there would always\nbe at least one corner case for which the \"setting-on-the-knobs\"\nwould fail.\n\n> After the operation 3 (Passing the blame) runs, if movement of\n> lines from another file is detected as in the above sketch, we\n> will pass blame to an unrelated path in the parent.  Some lines\n> are blamed on the file we started tracking in the parent, and\n> some other lines are blamed on a different file in the parent.\n> This is why 'pickaxe' uses <commit,path> tuple (aka 'origin') to\n> represent a suspect.\n> \n> All of this sounds quite simple and not so difficult to code,\n> although rejecting insignificant copies would involve fair\n> amount of heuristic tweaking like I needed to do while working\n> on the rename detection.\n\nIndeed.\n\n    Luben\n"},{"id":"28893","messageId":"20061017004429.GC20017@pasky.or.cz","threadId":"5911","inReplyTo":"453393E5.3020203@shadowen.org","subject":"Re: On blame/pickaxe","fromName":"Petr Baudis","fromEmail":"pasky@suse.cz","sentAt":"2006-10-17T00:44:29Z","receivedAt":"2006-10-17T00:44:29Z","isPatch":false,"sender":{"key":"pasky@ucw.cz","avatar":"https://avatars.githubusercontent.com/u/18439?v=4"},"body":"Dear diary, on Mon, Oct 16, 2006 at 04:15:01PM CEST, I got a letter\nwhere Andy Whitcroft <apw@shadowen.org> said that...\n> Josef Weidendorfer wrote:\n> > Hi,\n> > \n> > this blame-passing thing really looks very promising and powerful.\n> > \n> > On Monday 16 October 2006 08:43, you wrote:\n> >> If the user is not prepared to see code movement, pickaxe can be\n> >> run without -M nor -C to get the classic blame output.\n\nOk, so in this case -M and -C does not mean just looking for\ncopies/movements in other files but inside the same file as well.\n\nPerhaps we might want to differentiate those two cases since searching\nin all files might be significantly slower.\n\n> > Another blame-passing heuristic would be very interesting for code:\n> > \"Ignore white-space changes\".\n> > This way, commits which only do some reindentations simply are skipped.\n> > \n> > It looks like such a thing would just be a matter of passing \"-b\" to\n> > executions of \"diff\" in the blame-passing algorithm.\n> \n> I am thinking that that is probabally going to need to be optional, for\n> example python the indentation is everything to the meaning of the code.\n\n(OTOH, just today I was retrieving some code from deep inside a script\nto a common function, which of course caused massive indentation shift.\nSo it is very desirable in order to catch these. But more we get\ninvolved in this, the more we will probably want to know about the\nsyntax of the content we are digging in.)\n\n-- \n\t\t\t\tPetr \"Pasky\" Baudis\nStuff: http://pasky.or.cz/\n#!/bin/perl -sp0777i<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<j]dsj\n$/=unpack('H*',$_);$_=`echo 16dio\\U$k\"SK$/SM$n\\EsN0p[lN*1\nlK[d2%Sa2/d0$^Ixp\"|dc`;s/\\W//g;$_=pack('H*',/((..)*)$/)\n"},{"id":"28922","messageId":"7vwt6zjoum.fsf@assigned-by-dhcp.cox.net","threadId":"5911","inReplyTo":"20061016234547.21649.qmail@web31809.mail.mud.yahoo.com","subject":"Re: On blame/pickaxe","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-10-17T09:03:45Z","receivedAt":"2006-10-17T09:03:45Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Luben Tuikov <ltuikov@yahoo.com> writes:\n\n>> 3. Passing the blame.\n>> \n>> You (a <commit,path> tuple) are suspected for introducing\n>> certain lines, and you would want to pass blame to your parent.\n>> How would you do that?\n>> \n>> First, you find if your parent has the same path; if not, you\n>> find if between your parent and you there was a rename and find\n>> the original path in the parent.  If you are a merge, you do so\n>> for all your parents.  The path in the parent and your path may\n>> have many common lines, and if the lines you are the suspect are\n>> the same as the ones in the parent, you can pass the blame,\n>> because these lines were there before you touched them.\n>\n> Do you handle the case where a merge had a conflict and\n> the user changed the code (resolved) and then committed?\n> In this case some lines will have to be blamed on the\n> merge commit itself.\n\nWorking on a small example by hand is a good way to convince\nyourself.  The whole point of \"try to pass the blame, and take\nthe blame yourself only when you can't pass to anybody\" is\nprecisely to handle the merges sanely.  The answer to your later\nquestion also would become crystal clear with that exercise.\n\nSuppose that we are looking at a merge that would give this in\nits \"git show\" output:\n\ndiff --cc hello.c\nindex 3c27792,db3fdef..cec80d2\n--- a/hello.c\n+++ b/hello.c\n@@@ -1,4 -1,6 +1,6 @@@\n  int main(int ac, char **av)\n  {\n-       printf(\"hello, world.\\n\");\n -      const char *msg = \"hello, world\";\n++      const char *msg = \"hello, world.\";\n+ \n+       printf(\"%s\\n\", msg);\n  }\n\nFirst, we inspect the diff from the first parent:\n\n        diff --git a/hello.c b/hello.c\n        index 3c27792..cec80d2 100644\n        --- a/hello.c\n        +++ b/hello.c\n        @@ -1,4 +1,6 @@\n1        int main(int ac, char **av)\n2        {\n        -       printf(\"hello, world.\\n\");\n3       +       const char *msg = \"hello, world.\";\n4       +\n5       +       printf(\"%s\\n\", msg);\n6        }\n\nThat would find that lines 1, 2 and 6 came from the first parent\n(line numbers are of the postimage; e.g. line 6 is the closing\nbrace).\n\nWe are still left with lines 3, 4, and 5.  So we will see the\ndifference from the second parent:\n\n        diff --git a/hello.c b/hello.c\n        index db3fdef..cec80d2 100644\n        --- a/hello.c\n        +++ b/hello.c\n        @@ -1,6 +1,6 @@\n1        int main(int ac, char **av)\n2        {\n        -       const char *msg = \"hello, world\";\n3       +       const char *msg = \"hello, world.\";\n4\n5               printf(\"%s\\n\", msg);\n6        }\n\nIt shows that lines 1, 2, 4, 5 and 6 are the same as the second\nparent (again, line numbers are of the postimage).  This means\nthat we _could_ attribute line 1, 2 and 6 to the second parent\nif we wanted to, but we have already passed blame for 1, 2 and 6\nto the first parent [*1*] and only lines 4 and 5 are assigned to\nthe second parent.\n\nAt this point, we have no more parents to pass blame on and are\nstill left with line 3.  So we end up taking the blame for that\nline ourselves.  The final blame output reflects that.\n\nIf you are interested, prepare an example repository using the\nattached script, and try annotating E, like this:\n\n\tgit pickaxe --not right~2 left -- E\n\nThis demonstrates the example in this message (first parent is\nRight and the second is Left).\n\nAnnotating C with blame and pickaxe (use \"-n -f\" for clarity)\nshows the limitation of the original 'blame' that can use only\none path per commit.  This is a corner case where two files\noriginally different in the common ancestor were later merged\ninto one.  pickaxe handles this case without -M.\n\n\tgit blame -n -f C\n        git pickaxe -n -f C\n\nAnnotating D with pickaxe with and without -M illustrates how\nline movement is handled.\n\n\tgit pickaxe -M D\n\nHave fun.\n\n\n[*1*] The really core part of git does not have any preference\namong parents, but typically a merge commit is made with the\ncurrent branch head as its first parent and the other branch as\nits second parent, so favoring the earlier parent over the later\nones makes a lot of sense in practice.  This is in line with\nother parts of git, including the merge simplification done by\ngit-log.\n\n-- 8< --\n#!/bin/sh\n\ntest -d .git || {\n\techo Run me in an empty directory.\n\texit\n}\ngit init-db\n\nfor i in 1 2 3 4 5 6 7 8 9 ; do echo line from initial $i ; done >A\nfor i in A B C D E F G H I ; do echo line from initial $i ; done >B\ncp A D\ncat >E <<EOF\nint main(int ac, char **av)\n{\n\tprintf(\"hello, world\\n\");\n}\nEOF\n\ngit add A B D E\ngit commit --author='Initial <initial@author>' -m initial\n\ngit branch right\ngit branch left\n\n# Left\ngit checkout left\nfor i in 1 2 3; do echo added by left; done >C\ncat A >>C\nrm -f A B\ncat >E <<EOF\nint main(int ac, char **av)\n{\n\tconst char *msg = \"hello, world\";\n\n\tprintf(\"%s\\n\", msg);\n}\nEOF\ngit update-index --add --remove A B C E\ngit commit --author='Left <left@branch>' -m Left\n\n# Right\ngit checkout right\ncat B >C\nfor i in 1 2 3; do echo added by right; done >>C\nrm -f A B\ncat >E <<EOF\nint main(int ac, char **av)\n{\n\tprintf(\"hello, world.\\n\");\n}\nEOF\ngit update-index --add --remove A B C E\ngit commit --author='Right <right@branch>' -m Right\n\necho \"Merge -- this should fail which is expected and scripts fixes it up\"\necho \"Do not get alarmed with the error message.\"\ngit pull . left\necho \"Fixing up...\"\n{\n\tgit cat-file blob :3:C\n\techo line by evil merge\n\tgit cat-file blob :2:C\n} >C\ncat >E <<EOF\nint main(int ac, char **av)\n{\n\tconst char *msg = \"hello, world.\";\n\n\tprintf(\"%s\\n\", msg);\n}\nEOF\ngit update-index C E\ngit commit --author='Merge <merge@branch>' -m 'Changes are merged.'\nrm -f C~*\n\n{\n\tfor i in 5 6 7; do echo line from initial $i ; done\n\techo line modified while swapping 8\n\tfor i in 9 1 2 3 4 ; do echo line from initial $i ; done\n} >D\n\ngit update-index D\ngit commit --author='Swap <swap@branch>' -m 'Lines are swapped.'\n\necho \"Now try annotating C, D and E with various options.\"\n"},{"id":"29461","messageId":"7vods6icc9.fsf@assigned-by-dhcp.cox.net","threadId":"5911","inReplyTo":"20061017004429.GC20017@pasky.or.cz","subject":"Re: On blame/pickaxe","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-10-21T03:20:38Z","receivedAt":"2006-10-21T03:20:38Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Petr Baudis <pasky@suse.cz> writes:\n\n>> >> If the user is not prepared to see code movement, pickaxe can be\n>> >> run without -M nor -C to get the classic blame output.\n>\n> Ok, so in this case -M and -C does not mean just looking for\n> copies/movements in other files but inside the same file as well.\n>\n> Perhaps we might want to differentiate those two cases since searching\n> in all files might be significantly slower.\n\nI do not personally worry about people confusing -M/-C to\npickaxe with -M/-C given to diff (to pickaxe, use of diff is\npurely an internal implementation issue), and reused -M and -C\nto mean quite different things.  -M is to detect line movement\ninside a file (it is not strictly limited to \"line movement\",\nthough. It _is_ about \"copies and moves within the same file\").\nOn the other hand, -C (and its stronger form -C -C) is to detect\ncopies and moves across file boundaries (but wholesale \"file\nrename\" comes as part of the basic algorithm so you do not have\nto ask for it with -M nor -C).  So in that sense pronouncing M\n\"move\" and C \"copy\" is not accurate.  Their differences is\nalready what you said \"we might want\".\n\nHowever they match the cost expectation people are used to in\ndiff options pretty well.  -M is not so expensive and -C is\nsomewhat.  -C -C is like find-copies-harder and is quite\nexpensive.\n\nAlso currently the code does not do \"move\" detection at all.\nContrary to intuition, move detection is more expensive than\ncopy detection in this case.\n"}]}