{"thread":{"id":"41853","subject":"weird diff output?","startedAt":"2016-03-29T00:26:35Z","lastAt":"2016-04-15T03:33:54Z","messageCount":27,"participants":["Jacob Keller","Stefan Beller","Junio C Hamano","Jeff King","Davide Libenzi"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"282016","messageId":"CA+P7+xoiFUiBwDU2Wo9nVukchBvJSknON2XN572b6rSHnOSWaQ@mail.gmail.com","threadId":"41853","inReplyTo":null,"subject":"weird diff output?","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2016-03-29T00:26:35Z","receivedAt":"2016-03-29T00:26:35Z","isPatch":false,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Mon, Mar 28, 2016 at 4:28 PM, Stefan Beller wrote:\n> cat > expect < +Entering '../nested1'\n> +Entering '../nested1/nested2'\n> +Entering '../nested1/nested2/nested3'\n> +Entering '../nested1/nested2/nested3/submodule'\n> +Entering '../sub1'\n> +Entering '../sub2'\n> +Entering '../sub3'\n> +EOF\n> +\n> +test_expect_failure 'test messages from \"foreach --recursive\" from subdirectory' '\n> + (\n> + cd clone2 &&\n> + mkdir untracked &&\n> + cd untracked &&\n> + git submodule foreach --recursive >../../actual\n> + ) &&\n> + test_i18ncmp expect actual\n> +'\n> +\n> +cat > expect < nested1-nested1\n> nested2-nested2\n> nested3-nested3\n\nComplete tangent here. The diff above looks like\n\n\n+\n+\n+\n+\n+\n\nis it possible to get diff output that would look more like\n\n+\n+\n+\n+\n+\n+\n\n\ninstead? This is one of those huge readability issues with diff\nformatting that seems like both are completely correct, but the second\nway is much easier in general to read what was added.\n\nI don't understand why diff algorithms result in the former instead of\nthe latter, and am curious if anyone knows whether this has ever been\nthought about or solved by someone.\n\nI've tried using various diffing algorithms (histogram, etc) and they\nalways produce the same result above, and never what I would prefer.\n\nRegards,\nJake\n"},{"id":"282074","messageId":"CAGZ79ka4ad5dQMWANJUDx-0+kV3qR=HttOJni2XfhFzjMKfcPw@mail.gmail.com","threadId":"41853","inReplyTo":"CA+P7+xoiFUiBwDU2Wo9nVukchBvJSknON2XN572b6rSHnOSWaQ@mail.gmail.com","subject":"Re: weird diff output?","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-03-29T17:37:38Z","receivedAt":"2016-03-29T17:37:38Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Mon, Mar 28, 2016 at 5:26 PM, Jacob Keller wrote:\n> On Mon, Mar 28, 2016 at 4:28 PM, Stefan Beller wrote:\n>> cat > expect <> +Entering '../nested1'\n>> +Entering '../nested1/nested2'\n>> +Entering '../nested1/nested2/nested3'\n>> +Entering '../nested1/nested2/nested3/submodule'\n>> +Entering '../sub1'\n>> +Entering '../sub2'\n>> +Entering '../sub3'\n>> +EOF\n>> +\n>> +test_expect_failure 'test messages from \"foreach --recursive\" from subdirectory' '\n>> + (\n>> + cd clone2 &&\n>> + mkdir untracked &&\n>> + cd untracked &&\n>> + git submodule foreach --recursive >../../actual\n>> + ) &&\n>> + test_i18ncmp expect actual\n>> +'\n>> +\n>> +cat > expect <> nested1-nested1\n>> nested2-nested2\n>> nested3-nested3\n>\n> Complete tangent here. The diff above looks like\n>\n> \n> +\n> +\n> +\n> +\n> +\n>\n> is it possible to get diff output that would look more like\n>\n> +\n> +\n> +\n> +\n> +\n> +\n> \n>\n> instead? This is one of those huge readability issues with diff\n> formatting that seems like both are completely correct, but the second\n> way is much easier in general to read what was added.\n>\n> I don't understand why diff algorithms result in the former instead of\n> the latter, and am curious if anyone knows whether this has ever been\n> thought about or solved by someone.\n\nI thought this is an optimization for C code where you have a diff like:\n\n int existingStuff1(..) {\n ...\n }\n +\n + int foo(..) {\n +...\n +}\n\n int existingStuff2(...) {\n ...\n\nNote that the closing '}' could be taken from the method existingStuff1 instead\nof correctly closing foo. So the correct heuristic really depends on\nwhat kind of text\nwe are diffing.\n\nMaybe we need the opposite of the 'patience' algorithm in format-patch?\n\nAnother heuristic would be to check for empty lines and use that as a\nstrong hint,\nwhether to use the first or last line. (Rule: Try to use that last or\nfirst line such that\nthe lines at the edges of the diff are empty lines, it needs to be\nformalized a bit more)\n\n>\n> I've tried using various diffing algorithms (histogram, etc) and they\n> always produce the same result above, and never what I would prefer.\n>\n> Regards,\n> Jake\n\nThanks,\nStefan\n"},{"id":"282075","messageId":"xmqqzithxj8l.fsf@gitster.mtv.corp.google.com","threadId":"41853","inReplyTo":"CAGZ79ka4ad5dQMWANJUDx-0+kV3qR=HttOJni2XfhFzjMKfcPw@mail.gmail.com","subject":"Re: weird diff output?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-03-29T17:54:34Z","receivedAt":"2016-03-29T17:54:34Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller writes:\n\n> I thought this is an optimization for C code where you have a diff like:\n>\n> int existingStuff1(..) {\n> ...\n> }\n> +\n> + int foo(..) {\n> +...\n> +}\n>\n> int existingStuff2(...) {\n> ...\n>\n> Note that the closing '}' could be taken from the method existingStuff1 instead\n> of correctly closing foo.\n\nThat is a less optimal output. Another possible output would be\nlike so:\n\n int existingStuff1(..) {\n ...\n }\n \n + int foo(..) {\n +...\n +}\n +\n int existingStuff2(...) {\n\nAll three are valid output, and ...\n\n> So the correct heuristic really depends on what kind of text we\n> are diffing.\n\n... this realization is correct.\n\nI have a feeling that any heuristic would be correct half of the\ntime, including the ehuristic implemented in the current code. The\nreaders of patches have inherent bias. They do not notice when the\nhunk is formed to match their expectation, but they will notice and\nremember when they see something less optimal.\n"},{"id":"282077","messageId":"CAGZ79kZiiOgxh6vMDnaJ_b+VVGrFBfGzZukTN6OEBxUV9-2vQw@mail.gmail.com","threadId":"41853","inReplyTo":"xmqqzithxj8l.fsf@gitster.mtv.corp.google.com","subject":"Re: weird diff output?","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-03-29T18:16:57Z","receivedAt":"2016-03-29T18:16:57Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Tue, Mar 29, 2016 at 10:54 AM, Junio C Hamano wrote:\n> Stefan Beller writes:\n>\n>> I thought this is an optimization for C code where you have a diff like:\n>>\n>> int existingStuff1(..) {\n>> ...\n>> }\n>> +\n>> + int foo(..) {\n>> +...\n>> +}\n>>\n>> int existingStuff2(...) {\n>> ...\n>>\n>> Note that the closing '}' could be taken from the method existingStuff1 instead\n>> of correctly closing foo.\n>\n> That is a less optimal output. Another possible output would be\n> like so:\n>\n> int existingStuff1(..) {\n> ...\n> }\n>\n> + int foo(..) {\n> +...\n> +}\n> +\n> int existingStuff2(...) {\n>\n> All three are valid output, and ...\n>\n>> So the correct heuristic really depends on what kind of text we\n>> are diffing.\n>\n> ... this realization is correct.\n>\n> I have a feeling that any heuristic would be correct half of the\n> time, including the ehuristic implemented in the current code. The\n> readers of patches have inherent bias. They do not notice when the\n> hunk is formed to match their expectation, but they will notice and\n> remember when they see something less optimal.\n>\n\nWe have 3 possible diffs:\n1) closing brace and newline before the chunk\n2) newline before, closing brace after the chunk\n3) closing brace and newline after the chunk\n\nFor C code we may want to conclude that 3) is best. (appeals the bias of\nmost people) 2 is slightly worse, whereas 1) is absolutely worst.\n\nNow looking at the code Jacob found strange:\n\n> cat > expect < + expected results ...\n> + EOF\n> +test_expect_failure ... '\n> + ...\n> + '\n> +\n> +cat > expect < expect < expect < }\n>\n> + int foo(..) {\n> +...\n> +}\n> +\n> int existingStuff2(...) {\n\n> test_expect_failure ... '\n> existing test ...\n> '\n>\n> + cat > expect < + expected results ...\n> + EOF\n> +test_expect_failure ... '\n> + ...\n> + '\n> +\n> cat > expect < wrote:\n> On Tue, Mar 29, 2016 at 10:54 AM, Junio C Hamano wrote:\n>> Stefan Beller writes:\n>>\n>>> I thought this is an optimization for C code where you have a diff like:\n>>>\n>>> int existingStuff1(..) {\n>>> ...\n>>> }\n>>> +\n>>> + int foo(..) {\n>>> +...\n>>> +}\n>>>\n>>> int existingStuff2(...) {\n>>> ...\n>>>\n>>> Note that the closing '}' could be taken from the method existingStuff1 instead\n>>> of correctly closing foo.\n>>\n>> That is a less optimal output. Another possible output would be\n>> like so:\n>>\n>> int existingStuff1(..) {\n>> ...\n>> }\n>>\n>> + int foo(..) {\n>> +...\n>> +}\n>> +\n>> int existingStuff2(...) {\n>>\n>> All three are valid output, and ...\n>>\n>>> So the correct heuristic really depends on what kind of text we\n>>> are diffing.\n>>\n>> ... this realization is correct.\n>>\n>> I have a feeling that any heuristic would be correct half of the\n>> time, including the ehuristic implemented in the current code. The\n>> readers of patches have inherent bias. They do not notice when the\n>> hunk is formed to match their expectation, but they will notice and\n>> remember when they see something less optimal.\n>>\n>\n> We have 3 possible diffs:\n> 1) closing brace and newline before the chunk\n> 2) newline before, closing brace after the chunk\n> 3) closing brace and newline after the chunk\n>\n> For C code we may want to conclude that 3) is best. (appeals the bias of\n> most people) 2 is slightly worse, whereas 1) is absolutely worst.\n>\n> Now looking at the code Jacob found strange:\n>\n>> cat > expect <> + expected results ...\n>> + EOF\n>> +test_expect_failure ... '\n>> + ...\n>> + '\n>> +\n>> +cat > expect <\n> This can be written in two ways:\n>\n> 1) \"cat > expect < 2) \"cat > expect <\n> We claim 1) is better than 2).\n> This is different from the C code as now we want to have the\n> same lines before not after.\n>\n> To find a heuristic, which appeals both the C code\n> and the shell code, we could take the empty line\n> as a strong hint for the divider:\n>\n> 1) determine the amount of diff which is ambiguous, i.e. can\n> go before or after the chunk.\n> 2) Does the ambiguous part contain an empty line?\n> 3) If not, I have no offer for you, stop.\n> 4) divide the ambiguous chunk by the empty line,\n> 5) put the lines *after* the empty line in front of the chunk\n> 6) put the part before (including) the empty line after the\n> chunk\n> 7) Observe output:\n>\n>> }\n>>\n>> + int foo(..) {\n>> +...\n>> +}\n>> +\n>> int existingStuff2(...) {\n>\n>> test_expect_failure ... '\n>> existing test ...\n>> '\n>>\n>> + cat > expect <> + expected results ...\n>> + EOF\n>> +test_expect_failure ... '\n>> + ...\n>> + '\n>> +\n>> cat > expect <\n> This is what we want in both cases.\n> And I would argue it would appease many other kinds of text as well, because\n> an empty line is usually a strong indicator for any text that a\n> different thing comes along.\n> (Other programming languages, such as Java, C++ and any other C like\n> language behaves\n> that way; even when writing latex figures you'd rather want to break\n> at new lines?)\n>\n> Thanks,\n> Stefan\n\nThis seems like a good heuristic. Can we think of any examples where\nit would produce wildly confusing diffs? I don't think it necessarily\nneeds to be default but just a possible option when formatting diffs,\nmuch like we already have today.\n\nThanks,\nJake\n"},{"id":"282153","messageId":"xmqqbn5wvnix.fsf@gitster.mtv.corp.google.com","threadId":"41853","inReplyTo":"CA+P7+xoLZhKzHf6khQfT_pZ2=CQAp8Nmhc9B8+10+9=YYUZH3w@mail.gmail.com","subject":"Re: weird diff output?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-03-30T00:04:54Z","receivedAt":"2016-03-30T00:04:54Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jacob Keller writes:\n\n> On Tue, Mar 29, 2016 at 11:16 AM, Stefan Beller wrote:\n>> ...\n>> To find a heuristic, which appeals both the C code\n>> and the shell code, we could take the empty line\n>> as a strong hint for the divider:\n>\n> This seems like a good heuristic. Can we think of any examples where\n> it would produce wildly confusing diffs? I don't think it necessarily\n> needs to be default but just a possible option when formatting diffs,\n> much like we already have today.\n\nI earlier said \"50% of the time it is correct, you just do not\nremember\", but such an option with configuration variable would let\nsomebody interested set it permanently for his daily use of Git, and\nit would help him to find out (1) if he sees a \"Huh?\" division less\n(or more) often than he used to, and (2) if it gives a better\ndivision for the same change to view the diff with the plain-vanilla\nheuristic.\n"},{"id":"282191","messageId":"20160330045554.GA11007@sigill.intra.peff.net","threadId":"41853","inReplyTo":"CA+P7+xoLZhKzHf6khQfT_pZ2=CQAp8Nmhc9B8+10+9=YYUZH3w@mail.gmail.com","subject":"Re: weird diff output?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-03-30T04:55:55Z","receivedAt":"2016-03-30T04:55:55Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Mar 29, 2016 at 04:05:57PM -0700, Jacob Keller wrote:\n\n> > This is what we want in both cases.\n> > And I would argue it would appease many other kinds of text as well, because\n> > an empty line is usually a strong indicator for any text that a\n> > different thing comes along.\n> > (Other programming languages, such as Java, C++ and any other C like\n> > language behaves\n> > that way; even when writing latex figures you'd rather want to break\n> > at new lines?)\n> >\n> > Thanks,\n> > Stefan\n> \n> This seems like a good heuristic. Can we think of any examples where\n> it would produce wildly confusing diffs? I don't think it necessarily\n> needs to be default but just a possible option when formatting diffs,\n> much like we already have today.\n\nOne thing I like to do when playing with new diff ideas is to pipe all\nof \"log -p\" for a real project through it and see what differences it\nproduces.\n\nBelow is a perl script that implements Stefan's heuristic. I checked its\noutput on git.git with:\n\n git log --format='commit %H' -p >old\n perl /path/to/script new\n diff -F ^commit -u old new | less\n\nwhich shows the differences, with the commit id in the hunk header\n(which makes it easy to \"git show $commit | perl /path/to/script\" to\nsee the new diff with more context.\n\nIn addition to the cases discussed, it seems to improve C comments by\nturning:\n\n /*\n + * new function\n + */\n +void foo(void);\n +\n +/*\n * old function\n ...\n\ninto:\n\n +/*\n + * my function\n + */\n +void foo(void);\n +\n /*\n * old function\n ...\n\nSee 47fe3f6e for an example.\n\nIt also seems to do OK with shell scripts. Commit e6bb5f78 is an example\nwhere it improves a here-doc, as in the motivating example from this\nthread. Similarly, the headers in 4df1e79 are much improved (though I'm\nconfused why the final one in that diff doesn't seem to have been\ncaught).\n\nI also ran into an interesting case in 86d26f24, where we have:\n\n + test_expect_success '\n + foo\n +\n +'\n +\n\nand there are _two_ blank lines to choose from. It looks really terrible\nif you use the first one, but the second one looks good (and the script\nbelow chooses the second, as it's closest to the hunk boundary). There\nmay be cases where that's bad, though.\n\nThis is just a proof of concept. I guess we'd want to somehow integrate\nthe heuristic into git.\n\n-- >8 --\n#!/usr/bin/perl\n\nuse strict;\nuse warnings 'all';\n\nuse constant {\n STATE_NONE => 0,\n STATE_LEADING_CONTEXT => 1,\n STATE_IN_CHUNK => 2,\n};\nmy $state = STATE_NONE;\nmy @hunk;\nwhile(<>) {\n if ($state == STATE_NONE) {\n print;\n if (/^@/) {\n $state = STATE_LEADING_CONTEXT;\n }\n } else {\n if (/^ /) {\n flush_hunk() if $state != STATE_LEADING_CONTEXT;\n push @hunk, $_;\n } elsif(/^[-+]/) {\n push @hunk, $_;\n $state = STATE_IN_CHUNK;\n } else {\n flush_hunk();\n $state = STATE_NONE;\n print;\n }\n }\n}\nflush_hunk();\n\nsub flush_hunk {\n my $context_len = 0;\n while ($context_len < @hunk && $hunk[$context_len] =~ /^ /) {\n $context_len++;\n }\n\n # Find the length of the ambiguous portion.\n # Assumes our hunks have context first, and ambiguous additions at the end,\n # which is how git generates them\n my $ambig_len = 0;\n while ($ambig_len < $context_len) {\n my $i = $context_len - $ambig_len - 1;\n my $j = @hunk - $ambig_len - 1;\n if ($hunk[$j] =~ /^\\+/ && substr($hunk[$i], 1) eq substr($hunk[$j], 1)) {\n $ambig_len++;\n } else {\n last;\n }\n }\n\n # Now look for an empty line in the ambiguous portion (we can just look in\n # the context side, as it is equivalent to the addition side at the end).\n # We count down, though, as we prefer to use the line closest to the\n # hunk as the cutoff.\n my $empty;\n for (my $i = $context_len - 1; $i >= $context_len - $ambig_len; $i--) {\n if (length($hunk[$i]) == 2) {\n $empty = $i;\n last;\n }\n }\n\n if (defined $empty) {\n # move empty lines after the chunk to be part of it\n for (my $i = $empty + 1; $i < $context_len; $i++) {\n $hunk[$i] =~ s/^ /+/;\n $hunk[@hunk - $context_len + $i] =~ s/^\\+/ /;\n }\n }\n\n print @hunk;\n @hunk = ();\n}\n"},{"id":"282195","messageId":"CAGZ79kZgyFVzTRpP1k7kj8GVCPBukS_muhd=Xs4gxcA3maW0fw@mail.gmail.com","threadId":"41853","inReplyTo":"20160330045554.GA11007@sigill.intra.peff.net","subject":"Re: weird diff output?","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-03-30T06:05:09Z","receivedAt":"2016-03-30T06:05:09Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Tue, Mar 29, 2016 at 9:55 PM, Jeff King wrote:\n> On Tue, Mar 29, 2016 at 04:05:57PM -0700, Jacob Keller wrote:\n>\n>> > This is what we want in both cases.\n>> > And I would argue it would appease many other kinds of text as well, because\n>> > an empty line is usually a strong indicator for any text that a\n>> > different thing comes along.\n>> > (Other programming languages, such as Java, C++ and any other C like\n>> > language behaves\n>> > that way; even when writing latex figures you'd rather want to break\n>> > at new lines?)\n>> >\n>> > Thanks,\n>> > Stefan\n>>\n>> This seems like a good heuristic. Can we think of any examples where\n>> it would produce wildly confusing diffs? I don't think it necessarily\n>> needs to be default but just a possible option when formatting diffs,\n>> much like we already have today.\n>\n> One thing I like to do when playing with new diff ideas is to pipe all\n> of \"log -p\" for a real project through it and see what differences it\n> produces.\n>\n> Below is a perl script that implements Stefan's heuristic. I checked its\n> output on git.git with:\n>\n> git log --format='commit %H' -p >old\n> perl /path/to/script new\n> diff -F ^commit -u old new | less\n\nWow, that's amazing! I'll toy around with it tomorrow. :)\n\n>\n> which shows the differences, with the commit id in the hunk header\n> (which makes it easy to \"git show $commit | perl /path/to/script\" to\n> see the new diff with more context.\n>\n> In addition to the cases discussed, it seems to improve C comments by\n> turning:\n>\n> /*\n> + * new function\n> + */\n> +void foo(void);\n> +\n> +/*\n> * old function\n> ...\n>\n> into:\n>\n> +/*\n> + * my function\n> + */\n> +void foo(void);\n> +\n> /*\n> * old function\n> ...\n>\n> See 47fe3f6e for an example.\n>\n> It also seems to do OK with shell scripts. Commit e6bb5f78 is an example\n> where it improves a here-doc, as in the motivating example from this\n> thread. Similarly, the headers in 4df1e79 are much improved (though I'm\n> confused why the final one in that diff doesn't seem to have been\n> caught).\n>\n> I also ran into an interesting case in 86d26f24, where we have:\n>\n> + test_expect_success '\n> + foo\n> +\n> +'\n> +\n\nThat's an interesting case :)\nI was trying to generalize my thoughts on it. (How is an empty line special?)\n\nInstead of empty line we could go with the line with the least amount\nof characters\nin the lines which can be shifted up or down instead as well. Why so?\n\n The more characters are in a line, the more interesting the line is.\n (the more information is in there). Assuming one patch carries information\n that is highly relevant in itself, but may not be relevant to the surrounding\n (think adding a new function to a C file. The surrounding functions are not\n interesting for the diff, but rather you want to have all \"relevant\"\ninformation\n bundled into that one diff reasonably.\n\n Going by the rule of splitting at the shortest line instead of just\nat empty lines,\n is a generalization of\n\nSo instead of looking at\n\n> + test_expect_success '\n> + foo\n> +\n> +'\n> +\n\nwe rather want to look at the string lengths of each line:\n\n> 21\n> 5\n> 0\n> 1\n> 0\n\nand then take the minimum (so instead of only acting on the 'last 0'\nas shown by Jeff,\nwe'd go to the minimum of those numbers.)\n\nNow on tie breaking (i.e two empty lines):\n\nWe need to understand the \"pattern\" of whether the lonely 1 char line\nbelongs above\nor below the chunk. I do not think we can do that just from the diff alone.\n\n* We either need to check the file (\"Does the file start with the 0 1 0 pattern\nor does it end with that?\" That would be a strong hint on whether to\nput the 1 line\nabove or below the chunk.) However a typical file has noise at the top\nand bottom,\nso this heuristic is not often applicable. With noise I mean license headers or\na java class or namespace ending with another brace or such. So probably\nthis second order heuristic on which of the empty lines to pick for\nbreaking needs more thoughts.\n\n* Go through the history of the file and check for occurrences (how\nwas such a pattern\nadded in the past? Ideally we want to find the first time such a\npattern is added and\nthen decide based on that whether to break at the first or second empty line)\n\nI guess both ways are expensive. Probably too expensive.\n\nSo for now we can just go with \"take first or last empty line (shortest line) of\noverlapping lines\" and inspect that further.\n\n\n\n\n\n\n>\n> and there are _two_ blank lines to choose from. It looks really terrible\n> if you use the first one, but the second one looks good (and the script\n> below chooses the second, as it's closest to the hunk boundary). There\n> may be cases where that's bad, though.\n>\n> This is just a proof of concept. I guess we'd want to somehow integrate\n> the heuristic into git.\n>\n> -- >8 --\n> #!/usr/bin/perl\n>\n> use strict;\n> use warnings 'all';\n>\n> use constant {\n> STATE_NONE => 0,\n> STATE_LEADING_CONTEXT => 1,\n> STATE_IN_CHUNK => 2,\n> };\n> my $state = STATE_NONE;\n> my @hunk;\n> while(<>) {\n> if ($state == STATE_NONE) {\n> print;\n> if (/^@/) {\n> $state = STATE_LEADING_CONTEXT;\n> }\n> } else {\n> if (/^ /) {\n> flush_hunk() if $state != STATE_LEADING_CONTEXT;\n> push @hunk, $_;\n> } elsif(/^[-+]/) {\n> push @hunk, $_;\n> $state = STATE_IN_CHUNK;\n> } else {\n> flush_hunk();\n> $state = STATE_NONE;\n> print;\n> }\n> }\n> }\n> flush_hunk();\n>\n> sub flush_hunk {\n> my $context_len = 0;\n> while ($context_len < @hunk && $hunk[$context_len] =~ /^ /) {\n> $context_len++;\n> }\n>\n> # Find the length of the ambiguous portion.\n> # Assumes our hunks have context first, and ambiguous additions at the end,\n> # which is how git generates them\n> my $ambig_len = 0;\n> while ($ambig_len < $context_len) {\n> my $i = $context_len - $ambig_len - 1;\n> my $j = @hunk - $ambig_len - 1;\n> if ($hunk[$j] =~ /^\\+/ && substr($hunk[$i], 1) eq substr($hunk[$j], 1)) {\n> $ambig_len++;\n> } else {\n> last;\n> }\n> }\n>\n> # Now look for an empty line in the ambiguous portion (we can just look in\n> # the context side, as it is equivalent to the addition side at the end).\n> # We count down, though, as we prefer to use the line closest to the\n> # hunk as the cutoff.\n> my $empty;\n> for (my $i = $context_len - 1; $i >= $context_len - $ambig_len; $i--) {\n> if (length($hunk[$i]) == 2) {\n> $empty = $i;\n> last;\n> }\n> }\n>\n> if (defined $empty) {\n> # move empty lines after the chunk to be part of it\n> for (my $i = $empty + 1; $i < $context_len; $i++) {\n> $hunk[$i] =~ s/^ /+/;\n> $hunk[@hunk - $context_len + $i] =~ s/^\\+/ /;\n> }\n> }\n>\n> print @hunk;\n> @hunk = ();\n> }\n"},{"id":"282196","messageId":"CA+P7+xqskf6Ti3tVwMrOAaj3EDykRLKiXG5EbbzkjRsZP0s_7w@mail.gmail.com","threadId":"41853","inReplyTo":"20160330045554.GA11007@sigill.intra.peff.net","subject":"Re: weird diff output?","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2016-03-30T06:05:41Z","receivedAt":"2016-03-30T06:05:41Z","isPatch":false,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Tue, Mar 29, 2016 at 9:55 PM, Jeff King wrote:\n> One thing I like to do when playing with new diff ideas is to pipe all\n> of \"log -p\" for a real project through it and see what differences it\n> produces.\n>\n\nGreat idea!\n\n> Below is a perl script that implements Stefan's heuristic. I checked its\n> output on git.git with:\n>\n> git log --format='commit %H' -p >old\n> perl /path/to/script new\n> diff -F ^commit -u old new | less\n>\n> which shows the differences, with the commit id in the hunk header\n> (which makes it easy to \"git show $commit | perl /path/to/script\" to\n> see the new diff with more context.\n>\n\nI'll try to run this against my projects and see what it looks like\nto see if I can spot (m)any counter examples, which would indicate\nit's a bad idea. I may have some time in the next few days to see how\nhard it would be to fully integrate it into the diff machinery too.\n\nThanks for the help!\n\nRegards,\nJake\n\n> In addition to the cases discussed, it seems to improve C comments by\n> turning:\n>\n> /*\n> + * new function\n> + */\n> +void foo(void);\n> +\n> +/*\n> * old function\n> ...\n>\n> into:\n>\n> +/*\n> + * my function\n> + */\n> +void foo(void);\n> +\n> /*\n> * old function\n> ...\n>\n> See 47fe3f6e for an example.\n>\n> It also seems to do OK with shell scripts. Commit e6bb5f78 is an example\n> where it improves a here-doc, as in the motivating example from this\n> thread. Similarly, the headers in 4df1e79 are much improved (though I'm\n> confused why the final one in that diff doesn't seem to have been\n> caught).\n>\n> I also ran into an interesting case in 86d26f24, where we have:\n>\n> + test_expect_success '\n> + foo\n> +\n> +'\n> +\n>\n> and there are _two_ blank lines to choose from. It looks really terrible\n> if you use the first one, but the second one looks good (and the script\n> below chooses the second, as it's closest to the hunk boundary). There\n> may be cases where that's bad, though.\n>\n> This is just a proof of concept. I guess we'd want to somehow integrate\n> the heuristic into git.\n>\n> -- >8 --\n> #!/usr/bin/perl\n>\n> use strict;\n> use warnings 'all';\n>\n> use constant {\n> STATE_NONE => 0,\n> STATE_LEADING_CONTEXT => 1,\n> STATE_IN_CHUNK => 2,\n> };\n> my $state = STATE_NONE;\n> my @hunk;\n> while(<>) {\n> if ($state == STATE_NONE) {\n> print;\n> if (/^@/) {\n> $state = STATE_LEADING_CONTEXT;\n> }\n> } else {\n> if (/^ /) {\n> flush_hunk() if $state != STATE_LEADING_CONTEXT;\n> push @hunk, $_;\n> } elsif(/^[-+]/) {\n> push @hunk, $_;\n> $state = STATE_IN_CHUNK;\n> } else {\n> flush_hunk();\n> $state = STATE_NONE;\n> print;\n> }\n> }\n> }\n> flush_hunk();\n>\n> sub flush_hunk {\n> my $context_len = 0;\n> while ($context_len < @hunk && $hunk[$context_len] =~ /^ /) {\n> $context_len++;\n> }\n>\n> # Find the length of the ambiguous portion.\n> # Assumes our hunks have context first, and ambiguous additions at the end,\n> # which is how git generates them\n> my $ambig_len = 0;\n> while ($ambig_len < $context_len) {\n> my $i = $context_len - $ambig_len - 1;\n> my $j = @hunk - $ambig_len - 1;\n> if ($hunk[$j] =~ /^\\+/ && substr($hunk[$i], 1) eq substr($hunk[$j], 1)) {\n> $ambig_len++;\n> } else {\n> last;\n> }\n> }\n>\n> # Now look for an empty line in the ambiguous portion (we can just look in\n> # the context side, as it is equivalent to the addition side at the end).\n> # We count down, though, as we prefer to use the line closest to the\n> # hunk as the cutoff.\n> my $empty;\n> for (my $i = $context_len - 1; $i >= $context_len - $ambig_len; $i--) {\n> if (length($hunk[$i]) == 2) {\n> $empty = $i;\n> last;\n> }\n> }\n>\n> if (defined $empty) {\n> # move empty lines after the chunk to be part of it\n> for (my $i = $empty + 1; $i < $context_len; $i++) {\n> $hunk[$i] =~ s/^ /+/;\n> $hunk[@hunk - $context_len + $i] =~ s/^\\+/ /;\n> }\n> }\n>\n> print @hunk;\n> @hunk = ();\n> }\n"},{"id":"282260","messageId":"CA+P7+xp+oT2zMBZqR8zvXKm8Zp5btaNyoOWFTts29HMwX+2o=Q@mail.gmail.com","threadId":"41853","inReplyTo":"CA+P7+xqskf6Ti3tVwMrOAaj3EDykRLKiXG5EbbzkjRsZP0s_7w@mail.gmail.com","subject":"Re: weird diff output?","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2016-03-30T19:14:26Z","receivedAt":"2016-03-30T19:14:26Z","isPatch":false,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Tue, Mar 29, 2016 at 11:05 PM, Jacob Keller wrote:\n> On Tue, Mar 29, 2016 at 9:55 PM, Jeff King wrote:\n>> One thing I like to do when playing with new diff ideas is to pipe all\n>> of \"log -p\" for a real project through it and see what differences it\n>> produces.\n>>\n>\n> Great idea!\n>\n>> Below is a perl script that implements Stefan's heuristic. I checked its\n>> output on git.git with:\n>>\n>> git log --format='commit %H' -p >old\n>> perl /path/to/script new\n>> diff -F ^commit -u old new | less\n>>\n>> which shows the differences, with the commit id in the hunk header\n>> (which makes it easy to \"git show $commit | perl /path/to/script\" to\n>> see the new diff with more context.\n>>\n>\n> I'll try to run this against my projects and see what it looks like\n> to see if I can spot (m)any counter examples, which would indicate\n> it's a bad idea. I may have some time in the next few days to see how\n> hard it would be to fully integrate it into the diff machinery too.\n>\n> Thanks for the help!\n>\n> Regards,\n> Jake\n>\n\nI ran this on a few of my local projects and it doesn't seem to\nproduce any false positives so far. Everything looks good. Of course\nthis is with just traditional C code. I am currently trying to run\nthis against the history of Linux as well and see if I can find\nanything that seems bad there.\n\nThanks,\nJake\n"},{"id":"282264","messageId":"CA+P7+xrbNQqGhR_EoVe7zou_g6oVFGN_v+q+tyHguv1BCMcimQ@mail.gmail.com","threadId":"41853","inReplyTo":"CA+P7+xp+oT2zMBZqR8zvXKm8Zp5btaNyoOWFTts29HMwX+2o=Q@mail.gmail.com","subject":"Re: weird diff output?","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2016-03-30T19:31:30Z","receivedAt":"2016-03-30T19:31:30Z","isPatch":false,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Wed, Mar 30, 2016 at 12:14 PM, Jacob Keller wrote:\n> I ran this on a few of my local projects and it doesn't seem to\n> produce any false positives so far. Everything looks good. Of course\n> this is with just traditional C code. I am currently trying to run\n> this against the history of Linux as well and see if I can find\n> anything that seems bad there.\n>\n> Thanks,\n> Jake\n\nSo far I've only found a single location that ends up looking worse\nwithin the Linux kernel. Diffs of some Kbuild settings result in\nsomething like\n\nbefore:\n\n If unsure, say Y.\n+\n+config RMI4_I2C\n+ tristate \"RMI4 I2C Support\"\n+ depends on RMI4_CORE && I2C\n+ help\n+ Say Y here if you want to support RMI4 devices connected to an I2C\n+ bus.\n+\n+ If unsure, say Y.\n\nafter:\n\n required for all RMI4 device support.\n\n+ If unsure, say Y.\n+\n+config RMI4_I2C\n+ tristate \"RMI4 I2C Support\"\n+ depends on RMI4_CORE && I2C\n+ help\n+ Say Y here if you want to support RMI4 devices connected to an I2C\n+ bus.\n+\n If unsure, say Y.\n\nSo in this particular instance which has multiple blank lines and is a\nsimilar issue as with Stefan's note above, this is where the heuristic\nfalls apart. At least for C code this is basically vanishingly small\ncompared to the number of comment header fix ups.\n\nI think it may be that Stefan's suggestions above may be on the right\ntrack to resolve that too.\n\nRegards,\nJake\n"},{"id":"282265","messageId":"CAGZ79kbk5T5SdSzfZ8Q6TQmXgiG+ZSUYc5E7_95KtariDU8MHQ@mail.gmail.com","threadId":"41853","inReplyTo":"CA+P7+xrbNQqGhR_EoVe7zou_g6oVFGN_v+q+tyHguv1BCMcimQ@mail.gmail.com","subject":"Re: weird diff output?","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-03-30T19:40:42Z","receivedAt":"2016-03-30T19:40:42Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Wed, Mar 30, 2016 at 12:31 PM, Jacob Keller wrote:\n>\n> If unsure, say Y.\n> +\n> +config RMI4_I2C\n> + tristate \"RMI4 I2C Support\"\n> + depends on RMI4_CORE && I2C\n> + help\n> + Say Y here if you want to support RMI4 devices connected to an I2C\n> + bus.\n> +\n> + If unsure, say Y.\n>\n> after:\n>\n> required for all RMI4 device support.\n>\n> + If unsure, say Y.\n> +\n> +config RMI4_I2C\n> + tristate \"RMI4 I2C Support\"\n> + depends on RMI4_CORE && I2C\n> + help\n> + Say Y here if you want to support RMI4 devices connected to an I2C\n> + bus.\n> +\n> If unsure, say Y.\n\nThe optimum would be:\n\n >\n > If unsure, say Y.\n >\n > +config RMI4_I2C\n > + tristate \"RMI4 I2C Support\"\n > + depends on RMI4_CORE && I2C\n > + help\n > + Say Y here if you want to support RMI4 devices connected to an I2C\n > + bus.\n > +\n > + If unsure, say Y.\n > +\n > config BLA_I2C\n\nThe overlapping lines:\n > +\n > + If unsure, say Y.\n > +\n\nHowever that broke the lines at the first empty line, not the last\nas Jeff claimed it. (Could there be a problem in the perl script when\nempty lines are at the first or last overlapping line?)\n\nThanks for going through examples!\n(I would, too. But fixing a submodule regression is more important\nnow; I only develop new features when there are no known regressions\ncaused by me)\n\nThanks,\nStefan\n\n>\n> So in this particular instance which has multiple blank lines and is a\n> similar issue as with Stefan's note above, this is where the heuristic\n> falls apart. At least for C code this is basically vanishingly small\n> compared to the number of comment header fix ups.\n>\n> I think it may be that Stefan's suggestions above may be on the right\n> track to resolve that too.\n>\n> Regards,\n> Jake\n"},{"id":"282303","messageId":"20160331134750.GA29790@sigill.intra.peff.net","threadId":"41853","inReplyTo":"CA+P7+xrbNQqGhR_EoVe7zou_g6oVFGN_v+q+tyHguv1BCMcimQ@mail.gmail.com","subject":"Re: weird diff output?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-03-31T13:47:50Z","receivedAt":"2016-03-31T13:47:50Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Mar 30, 2016 at 12:31:30PM -0700, Jacob Keller wrote:\n\n> So far I've only found a single location that ends up looking worse\n> within the Linux kernel. Diffs of some Kbuild settings result in\n> something like\n> \n> before:\n> \n> If unsure, say Y.\n> +\n> +config RMI4_I2C\n> + tristate \"RMI4 I2C Support\"\n> + depends on RMI4_CORE && I2C\n> + help\n> + Say Y here if you want to support RMI4 devices connected to an I2C\n> + bus.\n> +\n> + If unsure, say Y.\n> \n> after:\n> \n> required for all RMI4 device support.\n> \n> + If unsure, say Y.\n> +\n> +config RMI4_I2C\n> + tristate \"RMI4 I2C Support\"\n> + depends on RMI4_CORE && I2C\n> + help\n> + Say Y here if you want to support RMI4 devices connected to an I2C\n> + bus.\n> +\n> If unsure, say Y.\n> \n> So in this particular instance which has multiple blank lines and is a\n> similar issue as with Stefan's note above, this is where the heuristic\n> falls apart. At least for C code this is basically vanishingly small\n> compared to the number of comment header fix ups.\n> \n> I think it may be that Stefan's suggestions above may be on the right\n> track to resolve that too.\n\nThis is a tricky one. There _aren't_ actually multiple blank lines in\nthe ambiguous area, because this particular example comes at the very\nend of the file. Try:\n\n git show 8d99758dee3 drivers/input/rmi4/Kconfig\n\nwhich adds a block in the middle of the file. It looks good both before\nand after running through the script. Now look at this example:\n\n git show fdf51604f10 drivers/input/rmi4/Kconfig\n\nwhich looks like:\n\ndiff --git a/drivers/input/rmi4/Kconfig b/drivers/input/rmi4/Kconfig\nindex 5ea60e3..cc3f7c5 100644\n--- a/drivers/input/rmi4/Kconfig\n+++ b/drivers/input/rmi4/Kconfig\n@@ -8,3 +8,12 @@ config RMI4_CORE\n required for all RMI4 device support.\n \n If unsure, say Y.\n+\n+config RMI4_I2C\n+ tristate \"RMI4 I2C Support\"\n+ depends on RMI4_CORE && I2C\n+ help\n+ Say Y here if you want to support RMI4 devices connected to an I2C\n+ bus.\n+\n+ If unsure, say Y.\n\n\nNote that there is no trailing context, as we're adding at the end of\nthe file. So the ambiguous portion consists of only two lines: an empty\nline, and \"If unsure...\". And we bump the latter to the top, per the\nheuristic (it's the exact opposite of every other case, where the blank\nline is a true delimiter).\n\nAs a human, I think the indentation here is the real syntactic clue. But\ngetting into indentation heuristics is probably insane.\n\nThe script could probably make this work by disabling itself if the hunk\nis at the end of the diffed file (i.e., we don't see more context lines\nafterward). That covers any case like this where newline _is_ a\ndelimiter, but we just have some internal newlines, too. It wouldn't\ncover the case where we had internal newlines but used some other\nparagraph delimiter, but based on the results so far, that seems rather\nrare.\n\nSomething like this:\n\n--- foo.pl.orig\t2016-03-31 09:44:44.281232230 -0400\n+++ foo.pl\t2016-03-31 09:44:34.901232632 -0400\n@@ -24,13 +24,15 @@\n push @hunk, $_;\n $state = STATE_IN_CHUNK;\n } else {\n- flush_hunk();\n+ print @hunk;\n+ @hunk = ();\n $state = STATE_NONE;\n print;\n }\n }\n }\n-flush_hunk();\n+print @hunk;\n+@hunk = ();\n \n sub flush_hunk {\n my $context_len = 0;\n\n-Peff\n"},{"id":"282497","messageId":"xmqqbn5ti219.fsf@gitster.mtv.corp.google.com","threadId":"41853","inReplyTo":"CAGZ79kbk5T5SdSzfZ8Q6TQmXgiG+ZSUYc5E7_95KtariDU8MHQ@mail.gmail.com","subject":"Re: weird diff output?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-04-01T19:04:18Z","receivedAt":"2016-04-01T19:04:18Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller writes:\n\n> Thanks for going through examples!\n> (I would, too. But fixing a submodule regression is more important\n> now; I only develop new features when there are no known regressions\n> caused by me)\n\nThis is a tangent but perhaps as an experiment perhaps we can try it\nas the rule for everybody to adopt for one cycle, and see if that\nimproves the quality of the end-user experience?\n"},{"id":"282782","messageId":"CA+P7+xpX_xR9wVdRPgymXe0wRjDY2USRx2PyWJMKTjAepWpP+A@mail.gmail.com","threadId":"41853","inReplyTo":"20160331134750.GA29790@sigill.intra.peff.net","subject":"Re: weird diff output?","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2016-04-06T17:47:31Z","receivedAt":"2016-04-06T17:47:31Z","isPatch":false,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Thu, Mar 31, 2016 at 6:47 AM, Jeff King wrote:\n> On Wed, Mar 30, 2016 at 12:31:30PM -0700, Jacob Keller wrote:\n>\n>> So far I've only found a single location that ends up looking worse\n>> within the Linux kernel. Diffs of some Kbuild settings result in\n>> something like\n>>\n>> before:\n>>\n>> If unsure, say Y.\n>> +\n>> +config RMI4_I2C\n>> + tristate \"RMI4 I2C Support\"\n>> + depends on RMI4_CORE && I2C\n>> + help\n>> + Say Y here if you want to support RMI4 devices connected to an I2C\n>> + bus.\n>> +\n>> + If unsure, say Y.\n>>\n>> after:\n>>\n>> required for all RMI4 device support.\n>>\n>> + If unsure, say Y.\n>> +\n>> +config RMI4_I2C\n>> + tristate \"RMI4 I2C Support\"\n>> + depends on RMI4_CORE && I2C\n>> + help\n>> + Say Y here if you want to support RMI4 devices connected to an I2C\n>> + bus.\n>> +\n>> If unsure, say Y.\n>>\n>> So in this particular instance which has multiple blank lines and is a\n>> similar issue as with Stefan's note above, this is where the heuristic\n>> falls apart. At least for C code this is basically vanishingly small\n>> compared to the number of comment header fix ups.\n>>\n>> I think it may be that Stefan's suggestions above may be on the right\n>> track to resolve that too.\n>\n> This is a tricky one. There _aren't_ actually multiple blank lines in\n> the ambiguous area, because this particular example comes at the very\n> end of the file. Try:\n>\n> git show 8d99758dee3 drivers/input/rmi4/Kconfig\n>\n> which adds a block in the middle of the file. It looks good both before\n> and after running through the script. Now look at this example:\n>\n> git show fdf51604f10 drivers/input/rmi4/Kconfig\n>\n> which looks like:\n>\n> diff --git a/drivers/input/rmi4/Kconfig b/drivers/input/rmi4/Kconfig\n> index 5ea60e3..cc3f7c5 100644\n> --- a/drivers/input/rmi4/Kconfig\n> +++ b/drivers/input/rmi4/Kconfig\n> @@ -8,3 +8,12 @@ config RMI4_CORE\n> required for all RMI4 device support.\n>\n> If unsure, say Y.\n> +\n> +config RMI4_I2C\n> + tristate \"RMI4 I2C Support\"\n> + depends on RMI4_CORE && I2C\n> + help\n> + Say Y here if you want to support RMI4 devices connected to an I2C\n> + bus.\n> +\n> + If unsure, say Y.\n>\n>\n> Note that there is no trailing context, as we're adding at the end of\n> the file. So the ambiguous portion consists of only two lines: an empty\n> line, and \"If unsure...\". And we bump the latter to the top, per the\n> heuristic (it's the exact opposite of every other case, where the blank\n> line is a true delimiter).\n>\n> As a human, I think the indentation here is the real syntactic clue. But\n> getting into indentation heuristics is probably insane.\n>\n> The script could probably make this work by disabling itself if the hunk\n> is at the end of the diffed file (i.e., we don't see more context lines\n> afterward). That covers any case like this where newline _is_ a\n> delimiter, but we just have some internal newlines, too. It wouldn't\n> cover the case where we had internal newlines but used some other\n> paragraph delimiter, but based on the results so far, that seems rather\n> rare.\n>\n> Something like this:\n>\n> --- foo.pl.orig 2016-03-31 09:44:44.281232230 -0400\n> +++ foo.pl 2016-03-31 09:44:34.901232632 -0400\n> @@ -24,13 +24,15 @@\n> push @hunk, $_;\n> $state = STATE_IN_CHUNK;\n> } else {\n> - flush_hunk();\n> + print @hunk;\n> + @hunk = ();\n> $state = STATE_NONE;\n> print;\n> }\n> }\n> }\n> -flush_hunk();\n> +print @hunk;\n> +@hunk = ();\n>\n> sub flush_hunk {\n> my $context_len = 0;\n>\n> -Peff\n\nI started attempting to implement this heuristic within xdiff, but I\nam at a loss as to how xdiff actually works. I suspect this would go\nin xdi_change_compact or after it, but I really don't understand how\nxdiff represents the diffs at all...\n\nThanks,\nJake\n"},{"id":"283212","messageId":"CAGZ79kZ+JgVNSvJ+tZwGqP-L-NVUv8hmd1jsbh71F08F5AqsjA@mail.gmail.com","threadId":"41853","inReplyTo":"CA+P7+xpX_xR9wVdRPgymXe0wRjDY2USRx2PyWJMKTjAepWpP+A@mail.gmail.com","subject":"Re: weird diff output?","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-04-12T19:34:21Z","receivedAt":"2016-04-12T19:34:21Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Wed, Apr 6, 2016 at 10:47 AM, Jacob Keller wrote:\n>\n> I started attempting to implement this heuristic within xdiff, but I\n> am at a loss as to how xdiff actually works. I suspect this would go\n> in xdi_change_compact or after it, but I really don't understand how\n> xdiff represents the diffs at all...\n\nI agree that this seems like the right place.\n\nOn the off chance that David, the author of xdiff remembers that\npart, I cc'd him. (The whole discussion on better diffs is found at\nhttp://thread.gmane.org/gmane.comp.version-control.git/290093)\n\nThanks,\nStefan\n\n\n\n>\n> Thanks,\n> Jake\n"},{"id":"283446","messageId":"alpine.DEB.2.10.1604140639230.8340@zino","threadId":"41853","inReplyTo":"CAGZ79kZ+JgVNSvJ+tZwGqP-L-NVUv8hmd1jsbh71F08F5AqsjA@mail.gmail.com","subject":"Re: weird diff output?","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2016-04-14T13:56:39Z","receivedAt":"2016-04-14T13:56:39Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Tue, 12 Apr 2016, Stefan Beller wrote:\n\n> On Wed, Apr 6, 2016 at 10:47 AM, Jacob Keller wrote:\n> >\n> > I started attempting to implement this heuristic within xdiff, but I\n> > am at a loss as to how xdiff actually works. I suspect this would go\n> > in xdi_change_compact or after it, but I really don't understand how\n> > xdiff represents the diffs at all...\n> \n> I agree that this seems like the right place.\n> \n> On the off chance that David, the author of xdiff remembers that\n> part, I cc'd him. (The whole discussion on better diffs is found at\n> http://thread.gmane.org/gmane.comp.version-control.git/290093)\n\nThat was a zillions of years ago :) , but from a quick look at email \nthread, if you want to do it within xdiff, xdi_change_compact would be the \nplace.\nThe issue is knowing in which situations one diff look better than \nanother, and embedding an if-tis-do-tat logic deep into the core diff \nmachinery.\nIn theory one could implement the same thing higher up, working with the \nunified diff text format, where maybe a user can provide its own diff \npost-process hook script.\nIn any case, that still leaves open the issue on what to shift in the diff \nchunks, and in which cases. Which is likely going to be language/format \ndependent. IMHO, it gets nasty pretty quickly.\n"},{"id":"283478","messageId":"20160414183405.GE22068@sigill.intra.peff.net","threadId":"41853","inReplyTo":"alpine.DEB.2.10.1604140639230.8340@zino","subject":"Re: weird diff output?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-04-14T18:34:06Z","receivedAt":"2016-04-14T18:34:06Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Apr 14, 2016 at 06:56:39AM -0700, Davide Libenzi wrote:\n\n> That was a zillions of years ago :) , but from a quick look at email\n> thread, if you want to do it within xdiff, xdi_change_compact would be\n> the place. The issue is knowing in which situations one diff look\n> better than another, and embedding an if-tis-do-tat logic deep into\n> the core diff machinery. In theory one could implement the same thing\n> higher up, working with the unified diff text format, where maybe a\n> user can provide its own diff post-process hook script. In any case,\n> that still leaves open the issue on what to shift in the diff chunks,\n> and in which cases. Which is likely going to be language/format\n> dependent. IMHO, it gets nasty pretty quickly.\n\nThanks, that's helpful. Stefan already came up with a heuristic that I\nimplemented as a post-processing script in perl. It _seems_ to work\npretty well in practice across multiple languages, so our next step was\nto implement it in an actual usable and efficient way. :)\n\nLooking over the code, I agree that xdl_change_compact() is the place we\nwould want to put it. We'd probably tie it to a command-line option and\nlet people play around with it, and then consider making it the default\nif there's widespread approval.\n\n-Peff\n"},{"id":"283488","messageId":"CAGZ79ka8pgPNZKaVWnsa_S07esxkN9nJfhcMZvCfd5U6MtsrYQ@mail.gmail.com","threadId":"41853","inReplyTo":"20160414183405.GE22068@sigill.intra.peff.net","subject":"Re: weird diff output?","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-04-14T21:05:03Z","receivedAt":"2016-04-14T21:05:03Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Thu, Apr 14, 2016 at 11:34 AM, Jeff King wrote:\n> On Thu, Apr 14, 2016 at 06:56:39AM -0700, Davide Libenzi wrote:\n>\n>> That was a zillions of years ago :) , but from a quick look at email\n>> thread, if you want to do it within xdiff, xdi_change_compact would be\n>> the place. The issue is knowing in which situations one diff look\n>> better than another, and embedding an if-tis-do-tat logic deep into\n>> the core diff machinery. In theory one could implement the same thing\n>> higher up, working with the unified diff text format, where maybe a\n>> user can provide its own diff post-process hook script. In any case,\n>> that still leaves open the issue on what to shift in the diff chunks,\n>> and in which cases. Which is likely going to be language/format\n>> dependent. IMHO, it gets nasty pretty quickly.\n>\n> Thanks, that's helpful. Stefan already came up with a heuristic that I\n> implemented as a post-processing script in perl. It _seems_ to work\n> pretty well in practice across multiple languages, so our next step was\n> to implement it in an actual usable and efficient way. :)\n\nTo reiterate the heuristic for Davide (so you can avoid reading the\nwhole thread):\n\n If there are diff chunks, which can be shifted around, shift it such that\n the last empty line is below the chunk and the rest above.\n\nExample:\n(indented, shiftable part marked with Xs)\n\n diff --git a/test.c b/test.c\n index 2d7f343..2a14d36 100644\n --- a/test.c\n +++ b/test.c\n @@ -8,6 +8,14 @@ void A()\n }\n\n /**\n + * This is text.\n + */\n +void B()\n +{\n + text text\nX1 +}\nX2 +\nX3 +/**\n * This does 'foo foo'.\n */\n void C()\n\nThe last empty line is X2, so that's where we wrap:\n(X2 is the last line of the diff)\n\n diff --git a/test.c b/test.c\n index 2d7f343..2a14d36 100644\n --- a/test.c\n +++ b/test.c\n @@ -8,6 +8,14 @@ void A()\n }\n\nX3 +/**\n + * This is text.\n + */\n +void B()\n +{\n + text text\nX1 +}\nX2 +\n /**\n * This does 'foo foo'.\n */\n void C()\n\n\n>\n> Looking over the code, I agree that xdl_change_compact() is the place we\n> would want to put it. We'd probably tie it to a command-line option and\n> let people play around with it, and then consider making it the default\n> if there's widespread approval.\n\nI just stumbled upon\nhttp://blog.scoutapp.com/articles/2016/04/12/3-git-productivity-hacks\nwhich advertises git config --global pager.diff \"diff-so-fancy | less\n--tabs=4 -RFX\"\n\nWould you consider your perl script good enough to put that instead of\ndiff-so-fancy?\n\n>\n> -Peff\n"},{"id":"283504","messageId":"20160415000730.26446-1-sbeller@google.com","threadId":"41853","inReplyTo":"CAGZ79ka8pgPNZKaVWnsa_S07esxkN9nJfhcMZvCfd5U6MtsrYQ@mail.gmail.com","subject":"[RFC PATCH, WAS: \"weird diff output?\"] Implement better chunk heuristics.","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-04-15T00:07:30Z","receivedAt":"2016-04-15T00:07:30Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"TODO(sbeller):\n* describe the discussion on why this is better\n* see if this can be tested?\n\nSigned-off-by: Stefan Beller \n---\n xdiff/xdiffi.c | 39 +++++++++++++++++++++++++++++++++++++++\n 1 file changed, 39 insertions(+)\n\ndiff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\nindex 2358a2d..24eb9a0 100644\n--- a/xdiff/xdiffi.c\n+++ b/xdiff/xdiffi.c\n@@ -400,9 +400,16 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,\n }\n \n \n+static int starts_with_emptyline(const char *recs)\n+{\n+\treturn recs[0] == '\\n'; /* CRLF not covered here */\n+}\n+\n+\n int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n \tlong ix, ixo, ixs, ixref, grpsiz, nrec = xdf->nrec;\n \tchar *rchg = xdf->rchg, *rchgo = xdfo->rchg;\n+\tunsigned char has_emptyline;\n \txrecord_t **recs = xdf->recs;\n \n \t/*\n@@ -436,6 +443,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n \n \t\tdo {\n \t\t\tgrpsiz = ix - ixs;\n+\t\t\thas_emptyline = 0;\n \n \t\t\t/*\n \t\t\t * If the line before the current change group, is equal to\n@@ -447,6 +455,8 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n \t\t\t\trchg[--ixs] = 1;\n \t\t\t\trchg[--ix] = 0;\n \n+\t\t\t\thas_emptyline |=\n+\t\t\t\t\tstarts_with_emptyline(recs[ix]->ptr);\n \t\t\t\t/*\n \t\t\t\t * This change might have joined two change groups,\n \t\t\t\t * so we try to take this scenario in account by moving\n@@ -475,6 +485,9 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n \t\t\t\trchg[ixs++] = 0;\n \t\t\t\trchg[ix++] = 1;\n \n+\t\t\t\thas_emptyline |=\n+\t\t\t\t\tstarts_with_emptyline(recs[ix]->ptr);\n+\n \t\t\t\t/*\n \t\t\t\t * This change might have joined two change groups,\n \t\t\t\t * so we try to take this scenario in account by moving\n@@ -498,6 +511,32 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n \t\t\trchg[--ix] = 0;\n \t\t\twhile (rchgo[--ixo]);\n \t\t}\n+\n+\t\t/*\n+\t\t * If a group can be moved back and forth, see if there is an\n+\t\t * empty line in the moving space. If there is an empty line,\n+\t\t * make sure the last empty line is the end of the group.\n+\t\t *\n+\t\t * As we shifted the group forward as far as possible, we only\n+\t\t * need to shift it back if at all.\n+\t\t */\n+\t\tif (has_emptyline) {\n+\t\t\twhile (ixs > 0 && recs[ixs - 1]->ha == recs[ix - 1]->ha &&\n+\t\t\t xdl_recmatch(recs[ixs - 1]->ptr, recs[ixs - 1]->size, recs[ix - 1]->ptr, recs[ix - 1]->size, flags) &&\n+\t\t\t !starts_with_emptyline(recs[ix - 1]->ptr)) {\n+\t\t\t\trchg[--ixs] = 1;\n+\t\t\t\trchg[--ix] = 0;\n+\n+\t\t\t\t/*\n+\t\t\t\t * This change did not join two change groups,\n+\t\t\t\t * as we did that before already, so there is no\n+\t\t\t\t * need to adapt the other-file, i.e.\n+\t\t\t\t * running\n+\t\t\t\t * for (; rchg[ixs - 1]; ixs--);\n+\t\t\t\t * while (rchgo[--ixo]);\n+\t\t\t\t */\n+\t\t\t}\n+\t\t}\n \t}\n \n \treturn 0;\n-- \n2.8.1.474.gffdc890.dirty\n"},{"id":"283506","messageId":"CA+P7+xrs-Jy-enrZvt32UcmQ+1LY2i+gxH2irBVs7NRHY40R8A@mail.gmail.com","threadId":"41853","inReplyTo":"CAGZ79ka8pgPNZKaVWnsa_S07esxkN9nJfhcMZvCfd5U6MtsrYQ@mail.gmail.com","subject":"Re: weird diff output?","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2016-04-15T00:21:12Z","receivedAt":"2016-04-15T00:21:12Z","isPatch":false,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Thu, Apr 14, 2016 at 2:05 PM, Stefan Beller wrote:\n> On Thu, Apr 14, 2016 at 11:34 AM, Jeff King wrote:\n>> On Thu, Apr 14, 2016 at 06:56:39AM -0700, Davide Libenzi wrote:\n>>\n>>> That was a zillions of years ago :) , but from a quick look at email\n>>> thread, if you want to do it within xdiff, xdi_change_compact would be\n>>> the place. The issue is knowing in which situations one diff look\n>>> better than another, and embedding an if-tis-do-tat logic deep into\n>>> the core diff machinery. In theory one could implement the same thing\n>>> higher up, working with the unified diff text format, where maybe a\n>>> user can provide its own diff post-process hook script. In any case,\n>>> that still leaves open the issue on what to shift in the diff chunks,\n>>> and in which cases. Which is likely going to be language/format\n>>> dependent. IMHO, it gets nasty pretty quickly.\n>>\n>> Thanks, that's helpful. Stefan already came up with a heuristic that I\n>> implemented as a post-processing script in perl. It _seems_ to work\n>> pretty well in practice across multiple languages, so our next step was\n>> to implement it in an actual usable and efficient way. :)\n>\n> To reiterate the heuristic for Davide (so you can avoid reading the\n> whole thread):\n>\n> If there are diff chunks, which can be shifted around, shift it such that\n> the last empty line is below the chunk and the rest above.\n>\n> Example:\n> (indented, shiftable part marked with Xs)\n>\n> diff --git a/test.c b/test.c\n> index 2d7f343..2a14d36 100644\n> --- a/test.c\n> +++ b/test.c\n> @@ -8,6 +8,14 @@ void A()\n> }\n>\n> /**\n> + * This is text.\n> + */\n> +void B()\n> +{\n> + text text\n> X1 +}\n> X2 +\n> X3 +/**\n> * This does 'foo foo'.\n> */\n> void C()\n>\n> The last empty line is X2, so that's where we wrap:\n> (X2 is the last line of the diff)\n>\n> diff --git a/test.c b/test.c\n> index 2d7f343..2a14d36 100644\n> --- a/test.c\n> +++ b/test.c\n> @@ -8,6 +8,14 @@ void A()\n> }\n>\n> X3 +/**\n> + * This is text.\n> + */\n> +void B()\n> +{\n> + text text\n> X1 +}\n> X2 +\n> /**\n> * This does 'foo foo'.\n> */\n> void C()\n>\n>\n>>\n>> Looking over the code, I agree that xdl_change_compact() is the place we\n>> would want to put it. We'd probably tie it to a command-line option and\n>> let people play around with it, and then consider making it the default\n>> if there's widespread approval.\n>\n> I just stumbled upon\n> http://blog.scoutapp.com/articles/2016/04/12/3-git-productivity-hacks\n> which advertises git config --global pager.diff \"diff-so-fancy | less\n> --tabs=4 -RFX\"\n>\n> Would you consider your perl script good enough to put that instead of\n> diff-so-fancy?\n>\n\nInteresting. I'll play around with that for a bit and see how fast it appears.\n\nThanks,\nJake\n\n>>\n>> -Peff\n"},{"id":"283507","messageId":"CA+P7+xqEPq=G_PMA-=h6jzWaUP=6hmWXcLzxbogs2PyuAZcn4g@mail.gmail.com","threadId":"41853","inReplyTo":"20160415000730.26446-1-sbeller@google.com","subject":"Re: [RFC PATCH, WAS: \"weird diff output?\"] Implement better chunk heuristics.","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2016-04-15T00:26:52Z","receivedAt":"2016-04-15T00:26:52Z","isPatch":true,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Thu, Apr 14, 2016 at 5:07 PM, Stefan Beller wrote:\n> TODO(sbeller):\n> * describe the discussion on why this is better\n> * see if this can be tested?\n>\n\nThanks for taking time to do this! It looks like a few things are\nstill missing, CRLF obviously, and making it a configuration option.\n\n> Signed-off-by: Stefan Beller \n> ---\n> xdiff/xdiffi.c | 39 +++++++++++++++++++++++++++++++++++++++\n> 1 file changed, 39 insertions(+)\n>\n> diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\n> index 2358a2d..24eb9a0 100644\n> --- a/xdiff/xdiffi.c\n> +++ b/xdiff/xdiffi.c\n> @@ -400,9 +400,16 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,\n> }\n>\n>\n> +static int starts_with_emptyline(const char *recs)\n> +{\n> + return recs[0] == '\\n'; /* CRLF not covered here */\n> +}\n> +\n> +\n> int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n> long ix, ixo, ixs, ixref, grpsiz, nrec = xdf->nrec;\n> char *rchg = xdf->rchg, *rchgo = xdfo->rchg;\n> + unsigned char has_emptyline;\n> xrecord_t **recs = xdf->recs;\n>\n> /*\n> @@ -436,6 +443,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n>\n> do {\n> grpsiz = ix - ixs;\n> + has_emptyline = 0;\n>\n> /*\n> * If the line before the current change group, is equal to\n> @@ -447,6 +455,8 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n> rchg[--ixs] = 1;\n> rchg[--ix] = 0;\n>\n> + has_emptyline |=\n> + starts_with_emptyline(recs[ix]->ptr);\n\nI assume you're doing |= so that we don't overwrite the empty line\nsetting each loop here to 0 when it's false? That's a bit subtle, and\nit took me a moment to figure out, since I am used to thinking of it\nas bitwise | and not a boolean or like we're intending here (though\nobviously we're using bitwise to perform that intended behavior).\n\n> /*\n> * This change might have joined two change groups,\n> * so we try to take this scenario in account by moving\n> @@ -475,6 +485,9 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n> rchg[ixs++] = 0;\n> rchg[ix++] = 1;\n>\n> + has_emptyline |=\n> + starts_with_emptyline(recs[ix]->ptr);\n> +\n> /*\n> * This change might have joined two change groups,\n> * so we try to take this scenario in account by moving\n> @@ -498,6 +511,32 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n> rchg[--ix] = 0;\n> while (rchgo[--ixo]);\n> }\n> +\n> + /*\n> + * If a group can be moved back and forth, see if there is an\n> + * empty line in the moving space. If there is an empty line,\n> + * make sure the last empty line is the end of the group.\n> + *\n> + * As we shifted the group forward as far as possible, we only\n> + * need to shift it back if at all.\n> + */\n> + if (has_emptyline) {\n> + while (ixs > 0 && recs[ixs - 1]->ha == recs[ix - 1]->ha &&\n> + xdl_recmatch(recs[ixs - 1]->ptr, recs[ixs - 1]->size, recs[ix - 1]->ptr, recs[ix - 1]->size, flags) &&\n> + !starts_with_emptyline(recs[ix - 1]->ptr)) {\n> + rchg[--ixs] = 1;\n> + rchg[--ix] = 0;\n> +\n> + /*\n> + * This change did not join two change groups,\n> + * as we did that before already, so there is no\n> + * need to adapt the other-file, i.e.\n> + * running\n> + * for (; rchg[ixs - 1]; ixs--);\n> + * while (rchgo[--ixo]);\n> + */\n> + }\n> + }\n> }\n\nAnd this was the more difficult part which I wasn't able to fully\nunderstand how to do. It seems pretty reasonable. I think we can make\nit configurable by using a new XDIFF flag similar to how we handle\nvarious diff options like the different diff algorithms, and then we\ncould add tests specific to ensure that the flag enables the behavior\nwe want on some known test cases.\n\nI am not really sure how to thoroughly test it beyond that though.\n\nRegards,\nJake\n\n>\n> return 0;\n> --\n> 2.8.1.474.gffdc890.dirty\n>\n"},{"id":"283509","messageId":"CAGZ79kZzb-4J82xONKX1RiAeLdJ7pGF1rBD4fJRyjbdZcPnkVA@mail.gmail.com","threadId":"41853","inReplyTo":"CA+P7+xqEPq=G_PMA-=h6jzWaUP=6hmWXcLzxbogs2PyuAZcn4g@mail.gmail.com","subject":"Re: [RFC PATCH, WAS: \"weird diff output?\"] Implement better chunk heuristics.","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-04-15T00:43:14Z","receivedAt":"2016-04-15T00:43:14Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Thu, Apr 14, 2016 at 5:26 PM, Jacob Keller wrote:\n> On Thu, Apr 14, 2016 at 5:07 PM, Stefan Beller wrote:\n>> TODO(sbeller):\n>> * describe the discussion on why this is better\n>> * see if this can be tested?\n>>\n>\n> Thanks for taking time to do this! It looks like a few things are\n> still missing, CRLF obviously, and making it a configuration option.\n\nI mainly wanted to get this out in the world quickly as it took me a while to\nunderstand the code. Do you know the feeling when you stare at code\nfor hours and debug it and read headers to make sense of these\ncryptic variables and then after intensive thinking a clear image emerges?\n\nI put comments into the loop to convey my thought process on why that\nis enough code doing the job. So I'd be happy about a critical review. :)\n\n>\n>> Signed-off-by: Stefan Beller \n>> ---\n>> xdiff/xdiffi.c | 39 +++++++++++++++++++++++++++++++++++++++\n>> 1 file changed, 39 insertions(+)\n>>\n>> diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\n>> index 2358a2d..24eb9a0 100644\n>> --- a/xdiff/xdiffi.c\n>> +++ b/xdiff/xdiffi.c\n>> @@ -400,9 +400,16 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,\n>> }\n>>\n>>\n>> +static int starts_with_emptyline(const char *recs)\n>> +{\n>> + return recs[0] == '\\n'; /* CRLF not covered here */\n>> +}\n>> +\n>> +\n>> int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n>> long ix, ixo, ixs, ixref, grpsiz, nrec = xdf->nrec;\n>> char *rchg = xdf->rchg, *rchgo = xdfo->rchg;\n>> + unsigned char has_emptyline;\n>> xrecord_t **recs = xdf->recs;\n>>\n>> /*\n>> @@ -436,6 +443,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n>>\n>> do {\n>> grpsiz = ix - ixs;\n>> + has_emptyline = 0;\n>>\n>> /*\n>> * If the line before the current change group, is equal to\n>> @@ -447,6 +455,8 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n>> rchg[--ixs] = 1;\n>> rchg[--ix] = 0;\n>>\n>> + has_emptyline |=\n>> + starts_with_emptyline(recs[ix]->ptr);\n>\n> I assume you're doing |= so that we don't overwrite the empty line\n> setting each loop here to 0 when it's false? That's a bit subtle, and\n> it took me a moment to figure out, since I am used to thinking of it\n> as bitwise | and not a boolean or like we're intending here (though\n> obviously we're using bitwise to perform that intended behavior).\n\nHere are my thoughts:\n* this loop shifts the group back and forth, \"collecting\" adjacent groups\n until no more groups are eaten.\n* That is why the last iteration of the loop will shift around most\nand completely\n cover the relevant area. we could do this in the last iteration\nonly of this loop.\n But we do not know when the last iteration will be, so do it every time.\n\n We could also have an extra loop after this loop to do a back and\nforth once to look\n for empty lines.\n\n* Yes, the |= should convey:\n\n if (starts_with_emptyline(...)\n has_emptyline = 1;\n\nWe could do += as well. (Then we'd get the count which is still good enough.)\n\n* We do not want to overwrite the has_emptyline for non empty lines in\nthe inner loop.\n\n* The outer loop doesn't matter as we reset has_emptyline to 0 each\ntime as explained\n above. Technically we could \"has_emptyline = 0;\" before the do{ }\nwhile loop, to save\n a little bit of instructions.\n\n* I assumed starts_with_emptyline returns a boolean (though it is int)\n In this code I use unsigned char, which should probably be int as well?\n\n>\n>> /*\n>> * This change might have joined two change groups,\n>> * so we try to take this scenario in account by moving\n>> @@ -475,6 +485,9 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n>> rchg[ixs++] = 0;\n>> rchg[ix++] = 1;\n>>\n>> + has_emptyline |=\n>> + starts_with_emptyline(recs[ix]->ptr);\n>> +\n>> /*\n>> * This change might have joined two change groups,\n>> * so we try to take this scenario in account by moving\n>> @@ -498,6 +511,32 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n>> rchg[--ix] = 0;\n>> while (rchgo[--ixo]);\n>> }\n>> +\n>> + /*\n>> + * If a group can be moved back and forth, see if there is an\n>> + * empty line in the moving space. If there is an empty line,\n>> + * make sure the last empty line is the end of the group.\n>> + *\n>> + * As we shifted the group forward as far as possible, we only\n>> + * need to shift it back if at all.\n>> + */\n>> + if (has_emptyline) {\n>> + while (ixs > 0 && recs[ixs - 1]->ha == recs[ix - 1]->ha &&\n>> + xdl_recmatch(recs[ixs - 1]->ptr, recs[ixs - 1]->size, recs[ix - 1]->ptr, recs[ix - 1]->size, flags) &&\n>> + !starts_with_emptyline(recs[ix - 1]->ptr)) {\n>> + rchg[--ixs] = 1;\n>> + rchg[--ix] = 0;\n>> +\n>> + /*\n>> + * This change did not join two change groups,\n>> + * as we did that before already, so there is no\n>> + * need to adapt the other-file, i.e.\n>> + * running\n>> + * for (; rchg[ixs - 1]; ixs--);\n>> + * while (rchgo[--ixo]);\n>> + */\n>> + }\n>> + }\n>> }\n>\n> And this was the more difficult part which I wasn't able to fully\n> understand how to do. It seems pretty reasonable. I think we can make\n> it configurable by using a new XDIFF flag similar to how we handle\n> various diff options like the different diff algorithms, and then we\n> could add tests specific to ensure that the flag enables the behavior\n> we want on some known test cases.\n\nOk I'll look into adding a flag for that.\n\nI have no idea what the \"recs->ha\" is, though (short for hash?),\nso I am not quite sure about the condition in the while loop. It was mainly\ncopied from above where we shift the group backward.\n\n>\n> I am not really sure how to thoroughly test it beyond that though.\n\nThanks for the review!\nIn case you want to pick it up (partially), feel free to do so. :)\n\nStefan\n\n>\n> Regards,\n> Jake\n>\n>>\n>> return 0;\n>> --\n>> 2.8.1.474.gffdc890.dirty\n>>\n"},{"id":"283514","messageId":"CA+P7+xrx8+q3Tn=9a1RmU9hSS+HFb5y6QLvvZfb1PqYrKVivcw@mail.gmail.com","threadId":"41853","inReplyTo":"CAGZ79kZzb-4J82xONKX1RiAeLdJ7pGF1rBD4fJRyjbdZcPnkVA@mail.gmail.com","subject":"Re: [RFC PATCH, WAS: \"weird diff output?\"] Implement better chunk heuristics.","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2016-04-15T02:07:10Z","receivedAt":"2016-04-15T02:07:10Z","isPatch":true,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Thu, Apr 14, 2016 at 5:43 PM, Stefan Beller wrote:\n> On Thu, Apr 14, 2016 at 5:26 PM, Jacob Keller wrote:\n>> On Thu, Apr 14, 2016 at 5:07 PM, Stefan Beller wrote:\n>>> TODO(sbeller):\n>>> * describe the discussion on why this is better\n>>> * see if this can be tested?\n>>>\n>>\n>> Thanks for taking time to do this! It looks like a few things are\n>> still missing, CRLF obviously, and making it a configuration option.\n>\n> I mainly wanted to get this out in the world quickly as it took me a while to\n> understand the code. Do you know the feeling when you stare at code\n> for hours and debug it and read headers to make sense of these\n> cryptic variables and then after intensive thinking a clear image emerges?\n>\n> I put comments into the loop to convey my thought process on why that\n> is enough code doing the job. So I'd be happy about a critical review. :)\n>\n\nYes, I am glad you got it out here in the world. I'll do my best to\nreview it sometime early tomorrow. I know that feeling, and I tried to\ndo that for this code and started getting a headache so I stopped for\na bit.\n\nI like the comments they help understand the process.\n\n>>\n>>> Signed-off-by: Stefan Beller \n>>> ---\n>>> xdiff/xdiffi.c | 39 +++++++++++++++++++++++++++++++++++++++\n>>> 1 file changed, 39 insertions(+)\n>>>\n>>> diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\n>>> index 2358a2d..24eb9a0 100644\n>>> --- a/xdiff/xdiffi.c\n>>> +++ b/xdiff/xdiffi.c\n>>> @@ -400,9 +400,16 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,\n>>> }\n>>>\n>>>\n>>> +static int starts_with_emptyline(const char *recs)\n>>> +{\n>>> + return recs[0] == '\\n'; /* CRLF not covered here */\n>>> +}\n>>> +\n>>> +\n>>> int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n>>> long ix, ixo, ixs, ixref, grpsiz, nrec = xdf->nrec;\n>>> char *rchg = xdf->rchg, *rchgo = xdfo->rchg;\n>>> + unsigned char has_emptyline;\n>>> xrecord_t **recs = xdf->recs;\n>>>\n>>> /*\n>>> @@ -436,6 +443,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n>>>\n>>> do {\n>>> grpsiz = ix - ixs;\n>>> + has_emptyline = 0;\n>>>\n>>> /*\n>>> * If the line before the current change group, is equal to\n>>> @@ -447,6 +455,8 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n>>> rchg[--ixs] = 1;\n>>> rchg[--ix] = 0;\n>>>\n>>> + has_emptyline |=\n>>> + starts_with_emptyline(recs[ix]->ptr);\n>>\n>> I assume you're doing |= so that we don't overwrite the empty line\n>> setting each loop here to 0 when it's false? That's a bit subtle, and\n>> it took me a moment to figure out, since I am used to thinking of it\n>> as bitwise | and not a boolean or like we're intending here (though\n>> obviously we're using bitwise to perform that intended behavior).\n>\n> Here are my thoughts:\n> * this loop shifts the group back and forth, \"collecting\" adjacent groups\n> until no more groups are eaten.\n> * That is why the last iteration of the loop will shift around most\n> and completely\n> cover the relevant area. we could do this in the last iteration\n> only of this loop.\n> But we do not know when the last iteration will be, so do it every time.\n>\n\nYa I think this makes sense, and I think it's better to do it here\nthan having to do it as a separate loop after the fact.\n\n> We could also have an extra loop after this loop to do a back and\n> forth once to look\n> for empty lines.\n>\n\nI think it's better to do it here.\n\n> * Yes, the |= should convey:\n>\n> if (starts_with_emptyline(...)\n> has_emptyline = 1;\n>\n> We could do += as well. (Then we'd get the count which is still good enough.)\n>\n\nWe might do a += and rename the variable or something so that it's a\nbit more clear what wer'e doing.\n\n> * We do not want to overwrite the has_emptyline for non empty lines in\n> the inner loop.\n>\n\nRight.\n\n> * The outer loop doesn't matter as we reset has_emptyline to 0 each\n> time as explained\n\nYes.\n\n> above. Technically we could \"has_emptyline = 0;\" before the do{ }\n> while loop, to save\n> a little bit of instructions.\n>\n> * I assumed starts_with_emptyline returns a boolean (though it is int)\n> In this code I use unsigned char, which should probably be int as well?\n>\n\nI think the int is better, ya.\n\n> Ok I'll look into adding a flag for that.\n>\n> I have no idea what the \"recs->ha\" is, though (short for hash?),\n> so I am not quite sure about the condition in the while loop. It was mainly\n> copied from above where we shift the group backward.\n>\n\nI don't really know either.\n\n>>\n>> I am not really sure how to thoroughly test it beyond that though.\n>\n> Thanks for the review!\n> In case you want to pick it up (partially), feel free to do so. :)\n>\n\nI'll probably pick it up sometime tomorrow and try to see how it works and see\n\n> Stefan\n>\n>>\n\nThanks again!\nJake\n"},{"id":"283515","messageId":"xmqqbn5bei7x.fsf@gitster.mtv.corp.google.com","threadId":"41853","inReplyTo":"20160415000730.26446-1-sbeller@google.com","subject":"Re: [RFC PATCH, WAS: \"weird diff output?\"] Implement better chunk heuristics.","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-04-15T02:09:06Z","receivedAt":"2016-04-15T02:09:06Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller writes:\n\n> \n> +static int starts_with_emptyline(const char *recs)\n> +{\n> +\treturn recs[0] == '\\n'; /* CRLF not covered here */\n> +}\n> +\n> +\n\nThat's \"is-empty-line\", not \"starts-with\" ;-)\n\n> +\n> +\t\t/*\n> +\t\t * If a group can be moved back and forth, see if there is an\n> +\t\t * empty line in the moving space. If there is an empty line,\n> +\t\t * make sure the last empty line is the end of the group.\n> +\t\t *\n> +\t\t * As we shifted the group forward as far as possible, we only\n> +\t\t * need to shift it back if at all.\n> +\t\t */\n\nSounds sensible.\n\n> +\t\tif (has_emptyline) {\n> +\t\t\twhile (ixs > 0 && recs[ixs - 1]->ha == recs[ix - 1]->ha &&\n> +\t\t\t xdl_recmatch(recs[ixs - 1]->ptr, recs[ixs - 1]->size, recs[ix - 1]->ptr, recs[ix - 1]->size, flags) &&\n> +\t\t\t !starts_with_emptyline(recs[ix - 1]->ptr)) {\n\nYou probably want to wrap the \"hash compares equal and recmatch does\nsay they are the same\" into a helper function (to be automatically\ninlined by the compiler) to make it more readable here. I think\nis-empty is a lot cheaper than the recmatch so that should probably\nbe done earlier in the && chain.\n\n> +\t\t\t\trchg[--ixs] = 1;\n> +\t\t\t\trchg[--ix] = 0;\n> +\n> +\t\t\t\t/*\n> +\t\t\t\t * This change did not join two change groups,\n> +\t\t\t\t * as we did that before already, so there is no\n\nSorry, cannot quite parse the part before \"already\".\n\n> +\t\t\t\t * need to adapt the other-file, i.e.\n> +\t\t\t\t * running\n> +\t\t\t\t * for (; rchg[ixs - 1]; ixs--);\n> +\t\t\t\t * while (rchgo[--ixo]);\n> +\t\t\t\t */\n> +\t\t\t}\n> +\t\t}\n> \t}\n> \n> \treturn 0;\n"},{"id":"283518","messageId":"20160415021829.GD22112@sigill.intra.peff.net","threadId":"41853","inReplyTo":"CAGZ79ka8pgPNZKaVWnsa_S07esxkN9nJfhcMZvCfd5U6MtsrYQ@mail.gmail.com","subject":"Re: weird diff output?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-04-15T02:18:29Z","receivedAt":"2016-04-15T02:18:29Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Apr 14, 2016 at 02:05:03PM -0700, Stefan Beller wrote:\n\n> > Looking over the code, I agree that xdl_change_compact() is the place we\n> > would want to put it. We'd probably tie it to a command-line option and\n> > let people play around with it, and then consider making it the default\n> > if there's widespread approval.\n> \n> I just stumbled upon\n> http://blog.scoutapp.com/articles/2016/04/12/3-git-productivity-hacks\n> which advertises git config --global pager.diff \"diff-so-fancy | less\n> --tabs=4 -RFX\"\n> \n> Would you consider your perl script good enough to put that instead of\n> diff-so-fancy?\n\nFor some definition of \"good enough\". I don't plan to run it myself. And\nI don't use diff-so-fancy. But I think diff-so-fancy folks also tend to\nrun contrib/diff-highlight, which is written in perl and quite similar\nin structure to what I posted earlier (unsurprisingly, since I wrote\nit).\n\nSo I think it works, and the performance hit from piping through perl\ngenerally isn't bad enough to be a problem (and by definition it's only\nrunning when you would run an interactive pager in the first place).\n\nI don't think that this particular heuristic is in quite the same class\nas diff-highlight and diff-so-fancy, though. Those ones transform the\ndiff away from something that can be applied, so you really do just want\nthem for human viewing. But this new heuristic is something that you'd\nprobably want as part of format-patch, for example, and we don't\ngenerally kick in the pager there. So I think it would be much more\nnatural inside of the diff generation.\n\n-Peff\n"},{"id":"283521","messageId":"CAGZ79kbgYkjbpnk8LTOyHPRPAKi2s0p+iRk6FkWCN2KpHELgVA@mail.gmail.com","threadId":"41853","inReplyTo":"xmqqbn5bei7x.fsf@gitster.mtv.corp.google.com","subject":"Re: [RFC PATCH, WAS: \"weird diff output?\"] Implement better chunk heuristics.","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-04-15T03:33:54Z","receivedAt":"2016-04-15T03:33:54Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Thu, Apr 14, 2016 at 7:09 PM, Junio C Hamano wrote:\n> Stefan Beller writes:\n>\n>>\n>> +static int starts_with_emptyline(const char *recs)\n>> +{\n>> + return recs[0] == '\\n'; /* CRLF not covered here */\n>> +}\n>> +\n>> +\n>\n> That's \"is-empty-line\", not \"starts-with\" ;-)\n\nheh, ok.\nTo understand the code, I was debugging it and looking at the\npointers `recs[ix - 1]->ptr` which is pointing into the text file,\ni.e. when printing it in the debugger it would read\n\n '\\n\\tbla\\n\\nfoo\\n ...'\n\nso I found that a proper description at the time.\n\n\n>\n>> +\n>> + /*\n>> + * If a group can be moved back and forth, see if there is an\n>> + * empty line in the moving space. If there is an empty line,\n>> + * make sure the last empty line is the end of the group.\n>> + *\n>> + * As we shifted the group forward as far as possible, we only\n>> + * need to shift it back if at all.\n>> + */\n>\n> Sounds sensible.\n>\n>> + if (has_emptyline) {\n>> + while (ixs > 0 && recs[ixs - 1]->ha == recs[ix - 1]->ha &&\n>> + xdl_recmatch(recs[ixs - 1]->ptr, recs[ixs - 1]->size, recs[ix - 1]->ptr, recs[ix - 1]->size, flags) &&\n>> + !starts_with_emptyline(recs[ix - 1]->ptr)) {\n>\n> You probably want to wrap the \"hash compares equal and recmatch does\n> say they are the same\" into a helper function (to be automatically\n> inlined by the compiler) to make it more readable here. I think\n> is-empty is a lot cheaper than the recmatch so that should probably\n> be done earlier in the && chain.\n\nok, will do. Given that xdiff upstream and our code diverged over the years,\nI could apply this helper function at other places in the code as well.\n\n\n>\n>> + rchg[--ixs] = 1;\n>> + rchg[--ix] = 0;\n>> +\n>> + /*\n>> + * This change did not join two change groups,\n>> + * as we did that before already, so there is no\n>\n> Sorry, cannot quite parse the part before \"already\".\n\nI think to drop this comment in the final version of this patch.\nAs I `wrote` this loop by copying it from above, I tried justifying\neach change to it. (More to prove to myself I understood the code)\n\nwill drop this comment.\n\n>\n>> + * need to adapt the other-file, i.e.\n>> + * running\n>> + * for (; rchg[ixs - 1]; ixs--);\n>> + * while (rchgo[--ixo]);\n>> + */\n>> + }\n>> + }\n>> }\n>>\n>> return 0;\n"}]}