{"thread":{"id":"42632","subject":"[PATCH] diff compaction heuristic: favor shortest neighboring blank lines","startedAt":"2016-06-16T17:46:37Z","lastAt":"2016-07-04T14:34:06Z","messageCount":15,"participants":["Stefan Beller","Junio C Hamano","Michael Haggerty","Jeff King","Jakub Narębski"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"289374","messageId":"20160616174620.1011-1-sbeller@google.com","threadId":"42632","inReplyTo":null,"subject":"[PATCH] diff compaction heuristic: favor shortest neighboring blank lines","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-06-16T17:46:20Z","receivedAt":"2016-06-16T17:46:37Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"The compaction heuristic for diffs was deemed quite good, but in 5580b27\nwe have an example demonstrates a common case, that fails with the existing\nheuristic. That is why we disabled the heuristic in the v2.9.0 release.\n\nWith this patch a diff looks like:\n\n def bar\n do_bar_stuff()\n\n common_ending()\n end\n\n+ def bal\n+ do_bal_stuff()\n+\n+ common_ending()\n+ end\n+\n def baz\n do_baz_stuff()\n\n common_ending()\n end\n\nwhereas before we had:\n\n WIP (TODO: ask peff to provide an example that actually triggers, I seem to be\n unable to write one, though I thought the above was one)\n\n\nThe way we do it, is by inspecting the neighboring lines and see how\nmuch indent there is and we choose the line that has the shortest amount\nof blanks in the neighboring lines.\n\n(TODO: update comments in the file)\n\nSigned-off-by: Stefan Beller \n---\n\nHi Jeff, hi Michael,\n\nthanks for pointing out the flaw in this ruby code base before the 2.9 release.\nI think this patch would fix your finding, though I cannot reproduce it.\nCan you provide an example repo/patch that looks ugly on current origin/master,\nso I can be sure this fixes the issue?\n\nThis can also be a start of a discussion if this is a too short-sighted enhancement\nof the heuristic. Essentially we'd want to prefer \n\n+ end\n+\n+ def bal\n\nover:\n\n+ do_bal_stuff()\n+\n+ common_ending()\n\nbecause there is less space between line start and {end, def bal}\nthan for {do_bal_stuff, common_ending}.\n\nThanks,\nStefan\n\n xdiff/xdiffi.c | 41 +++++++++++++++++++++++++++++++++++++++--\n 1 file changed, 39 insertions(+), 2 deletions(-)\n\ndiff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\nindex b3c6848..58adc74 100644\n--- a/xdiff/xdiffi.c\n+++ b/xdiff/xdiffi.c\n@@ -405,6 +405,35 @@ static int is_blank_line(xrecord_t **recs, long ix, long flags)\n \treturn xdl_blankline(recs[ix]->ptr, recs[ix]->size, flags);\n }\n \n+static unsigned int leading_blank(const char *line)\n+{\n+\tunsigned int ret = 0;\n+\twhile (*line) {\n+\t\tif (*line == '\\t')\n+\t\t\tret += 8;\n+\t\telse if (*line == ' ')\n+\t\t\tret ++;\n+\t\telse\n+\t\t\tbreak;\n+\t\tline++;\n+\t}\n+\treturn ret;\n+}\n+\n+static unsigned int surrounding_leading_blank(xrecord_t **recs, long ix,\n+\t\tlong flags, long nrec)\n+{\n+\tunsigned int i, ret = UINT_MAX;\n+\tif (ix > 0)\n+\t\tret = leading_blank(recs[ix - 1]->ptr);\n+\tif (ix < nrec - 1) {\n+\t\ti = leading_blank(recs[ix + 1]->ptr);\n+\t\tif (i < ret)\n+\t\t\tret = i;\n+\t}\n+\treturn ret;\n+}\n+\n static int recs_match(xrecord_t **recs, long ixs, long ix, long flags)\n {\n \treturn (recs[ixs]->ha == recs[ix]->ha &&\n@@ -416,7 +445,7 @@ static int recs_match(xrecord_t **recs, long ixs, long ix, long flags)\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 int blank_lines;\n+\tunsigned int blank_lines, min_bl_neigh_indent;\n \txrecord_t **recs = xdf->recs;\n \n \t/*\n@@ -451,6 +480,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n \t\tdo {\n \t\t\tgrpsiz = ix - ixs;\n \t\t\tblank_lines = 0;\n+\t\t\tmin_bl_neigh_indent = UINT_MAX;\n \n \t\t\t/*\n \t\t\t * If the line before the current change group, is equal to\n@@ -485,7 +515,13 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n \t\t\t * the group.\n \t\t\t */\n \t\t\twhile (ix < nrec && recs_match(recs, ixs, ix, flags)) {\n-\t\t\t\tblank_lines += is_blank_line(recs, ix, flags);\n+\t\t\t\tif (is_blank_line(recs, ix, flags)) {\n+\t\t\t\t\tunsigned int bl_neigh_indent =\n+\t\t\t\t\t\tsurrounding_leading_blank(recs, ix, flags, nrec);\n+\t\t\t\t\tif (min_bl_neigh_indent > bl_neigh_indent)\n+\t\t\t\t\t\tmin_bl_neigh_indent = min_bl_neigh_indent;\n+\t\t\t\t\tblank_lines++;\n+\t\t\t\t}\n \n \t\t\t\trchg[ixs++] = 0;\n \t\t\t\trchg[ix++] = 1;\n@@ -525,6 +561,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n \t\tif ((flags & XDF_COMPACTION_HEURISTIC) && blank_lines) {\n \t\t\twhile (ixs > 0 &&\n \t\t\t !is_blank_line(recs, ix - 1, flags) &&\n+\t\t\t surrounding_leading_blank(recs, ix - 1, flags, nrec) > min_bl_neigh_indent &&\n \t\t\t recs_match(recs, ixs - 1, ix - 1, flags)) {\n \t\t\t\trchg[--ixs] = 1;\n \t\t\t\trchg[--ix] = 0;\n-- \n2.9.0.8.gb6cbe66\n\n"},{"id":"289397","messageId":"xmqqlh24516i.fsf@gitster.mtv.corp.google.com","threadId":"42632","inReplyTo":"20160616174620.1011-1-sbeller@google.com","subject":"Re: [PATCH] diff compaction heuristic: favor shortest neighboring blank lines","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-06-16T20:27:49Z","receivedAt":"2016-06-16T20:27:57Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller writes:\n\n> + def bal\n> + do_bal_stuff()\n> +\n> + common_ending()\n> + end\n> +\n> def baz\n> do_baz_stuff()\n>\n> common_ending()\n> end\n>\n> whereas before we had:\n>\n> WIP (TODO: ask peff to provide an example that actually triggers, I seem to be\n> unable to write one, though I thought the above was one)\n>\n>\n> The way we do it, is by inspecting the neighboring lines and see how\n> much indent there is and we choose the line that has the shortest amount\n> of blanks in the neighboring lines.\n> ...\n> because there is less space between line start and {end, def bal}\n> than for {do_bal_stuff, common_ending}.\n\nI haven't thought this carefully yet, but would this equally work\nwell for Python, where it does not have the \"end\" or does the lack\nof \"end\" pose a problem? You'll still find \"def bal\" is a good\nboundary (but you cannot tell if it is the beginning or the end of a\nblock, unless you understand the language), though.\n\n> +static unsigned int leading_blank(const char *line)\n> +{\n> +\tunsigned int ret = 0;\n> +\twhile (*line) {\n> +\t\tif (*line == '\\t')\n> +\t\t\tret += 8;\n\nThis will be broken with a line with space-before-tab whitespace\nbreakage, I suspect...\n\n> +\t\telse if (*line == ' ')\n> +\t\t\tret ++;\n> +\t\telse\n> +\t\t\tbreak;\n> +\t\tline++;\n> +\t}\n> +\treturn ret;\n> +}\n> +\n> +static unsigned int surrounding_leading_blank(xrecord_t **recs, long ix,\n> +\t\tlong flags, long nrec)\n> +{\n> +\tunsigned int i, ret = UINT_MAX;\n> +\tif (ix > 0)\n> +\t\tret = leading_blank(recs[ix - 1]->ptr);\n> +\tif (ix < nrec - 1) {\n> +\t\ti = leading_blank(recs[ix + 1]->ptr);\n> +\t\tif (i < ret)\n> +\t\t\tret = i;\n> +\t}\n> +\treturn ret;\n> +}\n> +\n> static int recs_match(xrecord_t **recs, long ixs, long ix, long flags)\n> {\n> \treturn (recs[ixs]->ha == recs[ix]->ha &&\n> @@ -416,7 +445,7 @@ static int recs_match(xrecord_t **recs, long ixs, long ix, long flags)\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 int blank_lines;\n> +\tunsigned int blank_lines, min_bl_neigh_indent;\n> \txrecord_t **recs = xdf->recs;\n> \n> \t/*\n> @@ -451,6 +480,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n> \t\tdo {\n> \t\t\tgrpsiz = ix - ixs;\n> \t\t\tblank_lines = 0;\n> +\t\t\tmin_bl_neigh_indent = UINT_MAX;\n> \n> \t\t\t/*\n> \t\t\t * If the line before the current change group, is equal to\n> @@ -485,7 +515,13 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n> \t\t\t * the group.\n> \t\t\t */\n> \t\t\twhile (ix < nrec && recs_match(recs, ixs, ix, flags)) {\n> -\t\t\t\tblank_lines += is_blank_line(recs, ix, flags);\n> +\t\t\t\tif (is_blank_line(recs, ix, flags)) {\n> +\t\t\t\t\tunsigned int bl_neigh_indent =\n> +\t\t\t\t\t\tsurrounding_leading_blank(recs, ix, flags, nrec);\n> +\t\t\t\t\tif (min_bl_neigh_indent > bl_neigh_indent)\n> +\t\t\t\t\t\tmin_bl_neigh_indent = min_bl_neigh_indent;\n> +\t\t\t\t\tblank_lines++;\n> +\t\t\t\t}\n> \n> \t\t\t\trchg[ixs++] = 0;\n> \t\t\t\trchg[ix++] = 1;\n> @@ -525,6 +561,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n> \t\tif ((flags & XDF_COMPACTION_HEURISTIC) && blank_lines) {\n> \t\t\twhile (ixs > 0 &&\n> \t\t\t !is_blank_line(recs, ix - 1, flags) &&\n> +\t\t\t surrounding_leading_blank(recs, ix - 1, flags, nrec) > min_bl_neigh_indent &&\n> \t\t\t recs_match(recs, ixs - 1, ix - 1, flags)) {\n> \t\t\t\trchg[--ixs] = 1;\n> \t\t\t\trchg[--ix] = 0;\n"},{"id":"289406","messageId":"CAGZ79kYHO8q_CmePBxFUYxmhY6V_dS4M3djxCOrz5iJx_vFC-Q@mail.gmail.com","threadId":"42632","inReplyTo":"xmqqlh24516i.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] diff compaction heuristic: favor shortest neighboring blank lines","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-06-16T21:06:40Z","receivedAt":"2016-06-16T21:06:46Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Thu, Jun 16, 2016 at 1:27 PM, Junio C Hamano wrote:\n>> ...\n>> because there is less space between line start and {end, def bal}\n>> than for {do_bal_stuff, common_ending}.\n>\n> I haven't thought this carefully yet, but would this equally work\n> well for Python, where it does not have the \"end\" or does the lack\n> of \"end\" pose a problem? You'll still find \"def bal\" is a good\n> boundary (but you cannot tell if it is the beginning or the end of a\n> block, unless you understand the language), though.\n\nGood point. I found a flaw in my implementation\n(as it doesn't match my mental model, not necessarily a bad thing)\n\nWe take the minimum of the two neighbors, i.e.\n\n+ do_bal_stuff()\n+\n+ common_ending()\n\nis preferrable to\n\n+ do_bal_stuff()\n+\n+ common_ending()\n\nand in python the example would look like:\n\n def foo():\n do_foo()\n\n common_thing()\n\n+ def baz():\n+ do_baz()\n+\n+ common_thing()\n+\n def bar():\n do_bar()\n\n common_thing()\n\nand breaking between\n\n common_thing()\n\n def bar():\n\nis more favorable than between\n\n do_baz()\n\n common_thing()\n\nbecause in the first former the count of\nwhite space in front of \"def bar():\" is smaller\nthan for any of \"do_baz()\" and \"common_thing()\"\n\n\n>\n>> +static unsigned int leading_blank(const char *line)\n>> +{\n>> + unsigned int ret = 0;\n>> + while (*line) {\n>> + if (*line == '\\t')\n>> + ret += 8;\n>\n> This will be broken with a line with space-before-tab whitespace\n> breakage, I suspect...\n\nHow so? We inspect each character on its own and then move on later\nby line++. (I am not seeing how this could cause trouble, so please\nhelp me?)\n\nGoing back to python, this may become a problem when you have a code like:\n\n def baz():\n\n do_baz()\n\n common_thing()\n\n def bar():\n\n+ do_bal()\n+\n+ common_thing()\n+\n+def bar():\n+\n do_bar()\n\n common_thing()\n\n\nbut this was fabricated with a typo (the first definition of bar\nshould have been bal),\n(Also it doesn't worsen the diff, as it is same without the heuristic)\n\nonce that typo is fixed we get:\n(both with and without the heuristic)\n\n do_foo()\n\n common_thing()\n\n def baz():\n do_baz()\n\n common_thing()\n\n+def bal():\n+\n+ do_bal()\n+\n+ common_thing()\n+\n def bar():\n\n do_bar()\n\n common_thing()\n\nClearly it can also be intentional to have 2 methods with the same\ncode for historical reasons, (even without the blank line after the\nfunction definition this produces the same result)\n\nWhen playing around with various diffs I could not find a thing that\nthis patch makes worse, it only fixes the actual issue.\n(I realized Peff actually attached a script to produce a bad diff, which\nis gone with this patch)\n\nThanks,\nStefan\n"},{"id":"289407","messageId":"576315E1.2050405@alum.mit.edu","threadId":"42632","inReplyTo":"20160616174620.1011-1-sbeller@google.com","subject":"Re: [PATCH] diff compaction heuristic: favor shortest neighboring blank lines","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2016-06-16T21:10:57Z","receivedAt":"2016-06-16T21:11:16Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 06/16/2016 07:46 PM, Stefan Beller wrote:\n> The compaction heuristic for diffs was deemed quite good, but in 5580b27\n> we have an example demonstrates a common case, that fails with the existing\n> heuristic. That is why we disabled the heuristic in the v2.9.0 release.\n> \n> With this patch a diff looks like:\n> \n> def bar\n> do_bar_stuff()\n> \n> common_ending()\n> end\n> \n> + def bal\n> + do_bal_stuff()\n> +\n> + common_ending()\n> + end\n> +\n> def baz\n> do_baz_stuff()\n> \n> common_ending()\n> end\n> \n> whereas before we had:\n> \n> WIP (TODO: ask peff to provide an example that actually triggers, I seem to be\n> unable to write one, though I thought the above was one)\n> \n> \n> The way we do it, is by inspecting the neighboring lines and see how\n> much indent there is and we choose the line that has the shortest amount\n> of blanks in the neighboring lines.\n> \n> (TODO: update comments in the file)\n> \n> Signed-off-by: Stefan Beller \n> ---\n> \n> Hi Jeff, hi Michael,\n> \n> thanks for pointing out the flaw in this ruby code base before the 2.9 release.\n> I think this patch would fix your finding, though I cannot reproduce it.\n> Can you provide an example repo/patch that looks ugly on current origin/master,\n> so I can be sure this fixes the issue?\n> \n> This can also be a start of a discussion if this is a too short-sighted enhancement\n> of the heuristic. Essentially we'd want to prefer \n> \n> + end\n> +\n> + def bal\n> \n> over:\n> \n> + do_bal_stuff()\n> +\n> + common_ending()\n> \n> because there is less space between line start and {end, def bal}\n> than for {do_bal_stuff, common_ending}.\n\nIt's really cool that you are trying to implement the indentation\nheuristic. I'm curious how it works in practice (something we can\nprobably only determine by applying it to a corpus of diffs to see how\noften it outperforms/underperforms the other possible approaches).\n\nThe heuristic I proposed was\n\n* Prefer to start and end hunks *following* lines with the least\n indentation.\n\n* Define the \"indentation\" of a blank line to be the indentation of\n the previous non-blank line minus epsilon.\n\n* In the case of a tie, prefer to slide the hunk down as far as\n possible.\n\nIf that's what you are trying to implement, then notice that the first\nrule says that the hunk should start *following* the line with the least\nindentation. So the \"score\" for\n\n> + end\n> +\n> + def bal\n\nwould be the indentation of the line preceding \"end\", which is larger\nthan the indentation of \"end\". And the score for\n\n> + do_bal_stuff()\n> +\n> + common_ending()\n\nwould come from the line preceding \"do_bal_stuff()\", namely \"def bal()\",\nwhich is indented the same as \"end\". So the latter would be preferred.\n\nBut actually, I don't understand how your example is meaningful. I think\nthis heuristic is only used to slide hunks around; i.e., when the line\nfollowing the hunk is the same as the first lines of the hunk, or when\nthe line preceding the hunk is the same as the last line of the hunk.\nRight? So your snippets would never compete against each other. Let's\ntake the full example. The five possible placements for the `+`\ncharacters are marked with the digits 1 through 5 here:\n\n> def bar\n> do_bar_stuff()\n> 1\n> 12 common_ending()\n> 123 end\n> 1234\n> 12345 def bal\n> 12345 do_bal_stuff()\n> 2345\n> 345 common_ending()\n> 45 end\n> 5\n> def baz\n> do_baz_stuff()\n>\n> common_ending()\n> end\n\nOf the lines preceding the candidate hunks, the blank line preceding the\nhunk marked \"5\" has the smallest indent, namely \"epsilon\" less than the\nindentation of the \"end\" line preceding it. So placement \"5\" would be\nchosen.\n\nI don't know enough about this area of the code to review your patch in\ndetail, but I did note below a typo that jumped out at me.\n\nMichael\n\n> xdiff/xdiffi.c | 41 +++++++++++++++++++++++++++++++++++++++--\n> 1 file changed, 39 insertions(+), 2 deletions(-)\n> \n> diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\n> index b3c6848..58adc74 100644\n> --- a/xdiff/xdiffi.c\n> +++ b/xdiff/xdiffi.c\n> [...]\n> @@ -485,7 +515,13 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n> \t\t\t * the group.\n> \t\t\t */\n> \t\t\twhile (ix < nrec && recs_match(recs, ixs, ix, flags)) {\n> -\t\t\t\tblank_lines += is_blank_line(recs, ix, flags);\n> +\t\t\t\tif (is_blank_line(recs, ix, flags)) {\n> +\t\t\t\t\tunsigned int bl_neigh_indent =\n> +\t\t\t\t\t\tsurrounding_leading_blank(recs, ix, flags, nrec);\n> +\t\t\t\t\tif (min_bl_neigh_indent > bl_neigh_indent)\n> +\t\t\t\t\t\tmin_bl_neigh_indent = min_bl_neigh_indent;\n\nThe line above has no effect (same variable on both sides of the =).\n\n> +\t\t\t\t\tblank_lines++;\n> +\t\t\t\t}\n> \n> \t\t\t\trchg[ixs++] = 0;\n> \t\t\t\trchg[ix++] = 1;\n> @@ -525,6 +561,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n> \t\tif ((flags & XDF_COMPACTION_HEURISTIC) && blank_lines) {\n> \t\t\twhile (ixs > 0 &&\n> \t\t\t !is_blank_line(recs, ix - 1, flags) &&\n> +\t\t\t surrounding_leading_blank(recs, ix - 1, flags, nrec) > min_bl_neigh_indent &&\n> \t\t\t recs_match(recs, ixs - 1, ix - 1, flags)) {\n> \t\t\t\trchg[--ixs] = 1;\n> \t\t\t\trchg[--ix] = 0;\n> \n\n"},{"id":"289410","messageId":"CAGZ79kbr03yVT3SZXZTpE=Pdh11Ge5TP3LF_7r9_wP=CZM3SXg@mail.gmail.com","threadId":"42632","inReplyTo":"576315E1.2050405@alum.mit.edu","subject":"Re: [PATCH] diff compaction heuristic: favor shortest neighboring blank lines","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-06-16T21:36:12Z","receivedAt":"2016-06-16T21:36:39Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":">\n> The heuristic I proposed was\n>\n> * Prefer to start and end hunks *following* lines with the least\n> indentation.\n>\n> * Define the \"indentation\" of a blank line to be the indentation of\n> the previous non-blank line minus epsilon.\n>\n> * In the case of a tie, prefer to slide the hunk down as far as\n> possible.\n>\n> If that's what you are trying to implement, then notice that the first\n> rule says that the hunk should start *following* the line with the least\n> indentation. So the \"score\" for\n\nI did not try to implement that heuristic.\n\n> * Prefer to start and end hunks *following* lines with the least\n> indentation.\n\nWe had this alone as a heuristic and it turned out badly. (More\nfalse positives than the current \"empty line only\" thing)\n\nIt may however be a good starting block when combined with the other\nconditions, as blank lines are assigned a longer virtual length than\nwhat they have.\n\n> * In the case of a tie, prefer to slide the hunk down as far as\n> possible.\n>\n\nThis is what the current implementation does as well. (i.e. if there is\nmore than one blank line, we have a tie, so choose the last one as the\nend of the hunk)\n\n\nSo what I am proposing in this patch:\n\n * Prefer to start and end hunks *following* lines with an empty line.\n (as implemented currently)\n\n * In the case of a tie, make use of a second tier heuristic.\n\n * Define the \"length\" of a blank line to be the\n minimum of the amount of white space in the line before and after\n\n * Choose that empty line (first tier) that has the shortest length\n(second tier)\n\n * In the case of a tie, prefer to slide the hunk down as far as\n possible.\n\nI would be really interested how these two heuristics compare in practice.\n\n>\n>> + end\n>> +\n>> + def bal\n>\n> would be the indentation of the line preceding \"end\", which is larger\n> than the indentation of \"end\". And the score for\n>\n>> + do_bal_stuff()\n>> +\n>> + common_ending()\n>\n> would come from the line preceding \"do_bal_stuff()\", namely \"def bal()\",\n> which is indented the same as \"end\". So the latter would be preferred.\n>\n> But actually, I don't understand how your example is meaningful. I think\n> this heuristic is only used to slide hunks around; i.e., when the line\n> following the hunk is the same as the first lines of the hunk, or when\n> the line preceding the hunk is the same as the last line of the hunk.\n\nRight.\n\n> Right? So your snippets would never compete against each other.\n\nright, I was using that to show why some parts are more favorable to\nput a break in (i.e. the transisiton from \"+ lines\" to surrounding lines.\nI was not clear enough there. :(\n\n> Let's\n> take the full example. The five possible placements for the `+`\n> characters are marked with the digits 1 through 5 here:\n>\n>> def bar\n>> do_bar_stuff()\n>> 1\n>> 12 common_ending()\n>> 123 end\n>> 1234\n>> 12345 def bal\n>> 12345 do_bal_stuff()\n>> 2345\n>> 345 common_ending()\n>> 45 end\n>> 5\n>> def baz\n>> do_baz_stuff()\n>>\n>> common_ending()\n>> end\n>\n> Of the lines preceding the candidate hunks, the blank line preceding the\n> hunk marked \"5\" has the smallest indent, namely \"epsilon\" less than the\n> indentation of the \"end\" line preceding it. So placement \"5\" would be\n> chosen.\n\nI agree 5 is the best here, but for other reasons.\n\nImagine /s/end/long final boilerplate code/, and it may be more clear.\nWhat I am trying to say is, that you \"indentation\" of the blank line is not\nreaching until the end of the \"end\" line, but rather to the front of \"end\".\n\n(If you don't care of white spaces in the git history and have an editor, that\nmakes fancy white space stuff, i.e. your text editor cursor is in the \"end\" line\nand you press \"enter\" to get to the next line, it is most likely indented to\nstrlen (\"\") - strlen(\"end\"), as that is how much indentation we had\nin the preceding line?\n\n>\n> I don't know enough about this area of the code to review your patch in\n> detail, but I did note below a typo that jumped out at me.\n\nI did not know the code either before writing the patch. :)\n\n\n>> + if (min_bl_neigh_indent > bl_neigh_indent)\n>> + min_bl_neigh_indent = min_bl_neigh_indent;\n>\n> The line above has no effect (same variable on both sides of the =).\n\nThanks!\n\nI had the feeling something was off judging from behavior,\nbut could not tell what exactly. This is it.\n\nIt should be\n\n min_bl_neigh_indent = bl_neigh_indent;\n\ni.e. the minimum of the existing and newly computed surrounding line\nstarting blanks.\n\nJunio writes:\n> Now, on what column does 'd' sit on the example below?\n>\n> def foo\n>\n> I typed SP SP HT 'd' 'e' 'f'; it still is indented by 8 places.\n\nI see, so for the TAB case we would need to do a\n\n ret += (8 - ret%8);\n\nThanks!\nStefan\n"},{"id":"289446","messageId":"20160617153637.GA9314@sigill.intra.peff.net","threadId":"42632","inReplyTo":"20160616174620.1011-1-sbeller@google.com","subject":"Re: [PATCH] diff compaction heuristic: favor shortest neighboring blank lines","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-06-17T15:36:38Z","receivedAt":"2016-06-17T15:37:10Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jun 16, 2016 at 10:46:20AM -0700, Stefan Beller wrote:\n\n> The compaction heuristic for diffs was deemed quite good, but in 5580b27\n> we have an example demonstrates a common case, that fails with the existing\n> heuristic. That is why we disabled the heuristic in the v2.9.0 release.\n> \n> With this patch a diff looks like:\n> \n> def bar\n> do_bar_stuff()\n> \n> common_ending()\n> end\n> \n> + def bal\n> + do_bal_stuff()\n> +\n> + common_ending()\n> + end\n> +\n> def baz\n> do_baz_stuff()\n> \n> common_ending()\n> end\n> \n> whereas before we had:\n> \n> WIP (TODO: ask peff to provide an example that actually triggers, I seem to be\n> unable to write one, though I thought the above was one)\n\nDid you want something that triggers the \"bad\" case with the existing\ncompaction heuristic?\n\nI gave one in:\n\n http://article.gmane.org/gmane.comp.version-control.git/296947\n\nI think the difference is that in my example, the diff (before\ncompaction) has the blank line at the top (because we are adding a new\nentry at the bottom), whereas in yours, the blank line is at the bottom.\n\nThis patch does make my \"bad\" case look better. Unfortunately, it\nre-breaks another case:\n\n\tcat >file.rb <<\\EOF\n\t##\n\t# This is the foo function.\n\tdef foo\n\t foo stuff\n\tend\n\n\t##\n\t# This is the bar function.\n\tdef bar\n\t bar stuff\n\tend\n\n\t##\n\t# This is the baz function.\n\tdef baz\n\t baz stuff\n\tend\n\tEOF\n\n\tgit init\n\tgit add file.rb\n\tsed -i 7,12d file.rb\n\tgit diff\n\nThat goes back to the original, pre-compaction-heuristic diff:\n\n\tdiff --git a/file.rb b/file.rb\n\tindex 0b31fb6..ee25d63 100644\n\t--- a/file.rb\n\t+++ b/file.rb\n\t@@ -5,12 +5,6 @@ def foo\n\t end\n\t \n\t ##\n\t-# This is the bar function.\n\t-def bar\n\t- bar stuff\n\t-end\n\t-\n\t-##\n\t # This is the baz function.\n\t def baz\n\t baz stuff\n\n-Peff\n"},{"id":"289451","messageId":"CAGZ79kZgdbqnWW9uqeBHNDbyGVfc0x5gTJbyD0Nyi1i3SNvENQ@mail.gmail.com","threadId":"42632","inReplyTo":"20160617153637.GA9314@sigill.intra.peff.net","subject":"Re: [PATCH] diff compaction heuristic: favor shortest neighboring blank lines","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-06-17T16:09:46Z","receivedAt":"2016-06-17T16:09:52Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Fri, Jun 17, 2016 at 8:36 AM, Jeff King wrote:\n>\n> Did you want something that triggers the \"bad\" case with the existing\n> compaction heuristic?\n>\n> I gave one in:\n>\n> http://article.gmane.org/gmane.comp.version-control.git/296947\n\nI found that out after sending the initial patch. Thanks for pointing out!\n\n\n>\n> I think the difference is that in my example, the diff (before\n> compaction) has the blank line at the top (because we are adding a new\n> entry at the bottom), whereas in yours, the blank line is at the bottom.\n>\n> This patch does make my \"bad\" case look better. Unfortunately, it\n> re-breaks another case:\n\nI think before spending more time on discussing and implementing new\n(hopefully better) heuristics, I'd want to step back and try to be a bit more\nsystematic, i.e. I'll want to collect lots of test cases in different languages\nand use cases. A mini test suite, maybe?\n\nI think I'll include these examples in there, too.\n\nThanks,\nStefan\n"},{"id":"289969","messageId":"576C1803.5050905@alum.mit.edu","threadId":"42632","inReplyTo":"CAGZ79kZgdbqnWW9uqeBHNDbyGVfc0x5gTJbyD0Nyi1i3SNvENQ@mail.gmail.com","subject":"Re: [PATCH] diff compaction heuristic: favor shortest neighboring blank lines","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2016-06-23T17:10:27Z","receivedAt":"2016-06-23T17:10:54Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 06/17/2016 06:09 PM, Stefan Beller wrote:\n> I think before spending more time on discussing and implementing new\n> (hopefully better) heuristics, I'd want to step back and try to be a bit more\n> systematic, i.e. I'll want to collect lots of test cases in different languages\n> and use cases. A mini test suite, maybe?\n\nStefan,\n\nI've also been playing around with diff heuristics and also trying to\nfind some good test data. Have you put together some test cases yet?\n\nIn case you are interested, the current iteration of my heuristic\nconsiders six things to determine a \"score\" for breaking a diff above a\nparticular line:\n\n* `blank` -- is the line blank?\n* `indent` -- the indentation of the line (if it is not blank)\n* `pre_blank` -- is the preceding line blank?\n* `pre_indent` -- the indentation of the closest preceding non-blank\n line\n* `post_blank` -- is the following line blank?\n* `post_indent` -- the indentation of the closest following non-blank\n line\n\nThe meat of the scoring algorithm is below. I compute the score for the\nbeginning and the end of the insert/delete block for each candidate\nshift of an insertion/deletion hunk, then choose the one that has the\nlowest score.\n\nThere are some adjustable \"bonus\" values below. The values shown give\nquite good results for C, shell, Python, XML, Ruby, CSS, YAML, and HTML\nin the couple of projects that I've tried it on. But I haven't done\nenough systematic testing over a large enough corpus to know whether the\nparameters could be improved or whether there are types of code that it\nperforms really terribly on.\n\nRight now my program doesn't output diffs in the usual format, but\nrather as a diff notated with various information. So it's not in a form\nthat other people could use so easily. Here's an example:\n\n> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n> *\n> * Default behaviour is to initialize the notes tree from the tree object\n> * specified by the given (or default) notes ref.\n> */\n> #define NOTES_INIT_EMPTY 1\n> | -4 \n> | -6 + /*\n> || 28 + + * By default, the notes tree is only readable, and the notes ref can be\n> || + + * any treeish. The notes tree can however be made writable with this flag,\n> || + + * in which case only strict ref names can be used.\n> || + + */\n> || + +#define NOTES_INIT_WRITABLE 2\n> | + +\n> | +/*\n> * Initialize the given notes_tree with the notes tree structure at the given\n> * ref. If given ref is NULL, the value of the $GIT_NOTES_REF environment\n> * variable is used, and if that is missing, the default notes ref is used\n> * (\"refs/notes/commits\").\n> *\n> * If you need to re-initialize a notes_tree structure (e.g. when switching from\n> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nThe two columns of vertical bars show the highest and lowest range of\nlines that this insertion block can be shifted to. The numbers show the\nscore for breaking the diff above that line. The first column of +/- is\nwhere this version of the heuristic would place the diff, and the second\ncolumn is where the master version of Git would place it.\n\nMy program can also search for and output \"slideable\" insertion/deletion\nblocks, so it can be used to find diffs that are theoretically capable\nof being optimized, even if they don't happen to be handled differently\nby two different algorithms.\n\nLet me know if you want to collaborate on this somehow.\n\nMichael\n\nScoring heuristic:\n\n> # A place to accumulate bonus factors (positive makes this\n> # index more favored):\n> bonus = 0\n> \n> # Bonuses based on the location of blank lines:\n> if pre_blank and not blank:\n> bonus += 3\n> elif blank and not pre_blank:\n> bonus += 2\n> elif blank and pre_blank:\n> bonus += 1\n> \n> # Now fill in missing indent values:\n> if pre_indent is None:\n> pre_indent = 0\n> \n> if post_indent is None:\n> post_indent = 0\n> \n> if blank:\n> indent = post_indent\n> \n> if indent > pre_indent:\n> # The line is indented more than its predecessor. It is\n> # preferable to keep these lines together, so we score it\n> # based on the larger indent:\n> score = indent\n> bonus -= 4\n> \n> elif indent < pre_indent:\n> # The line is indented less than its predecessor. It could\n> # be that this line is the start of a new block (e.g., of\n> # an \"else\" block, or of a block without a block\n> # terminator) or it could be the end of the previous\n> # block.\n> if indent < post_indent:\n> # The following line is indented more. So it is likely\n> # that this line is the start of a block. It's a\n> # pretty good place to split, so score it based on the\n> # smaller indent:\n> score = indent\n> bonus += 2\n> else:\n> # This was probably the end of a block. We score based\n> # on the line's own indent:\n> score = indent\n> \n> else:\n> # The line has the same indentation level as its\n> # predecessor. We score it based on its own indent:\n> score = indent\n> \n> return 10 * score - bonus\n\n"},{"id":"289970","messageId":"CAGZ79katU2w-aDcoyPtyESu33FFzVUv2+V=rq2pNcxZJG9NSng@mail.gmail.com","threadId":"42632","inReplyTo":"576C1803.5050905@alum.mit.edu","subject":"Re: [PATCH] diff compaction heuristic: favor shortest neighboring blank lines","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-06-23T17:25:15Z","receivedAt":"2016-06-23T17:25:20Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Thu, Jun 23, 2016 at 10:10 AM, Michael Haggerty wrote:\n> On 06/17/2016 06:09 PM, Stefan Beller wrote:\n>> I think before spending more time on discussing and implementing new\n>> (hopefully better) heuristics, I'd want to step back and try to be a bit more\n>> systematic, i.e. I'll want to collect lots of test cases in different languages\n>> and use cases. A mini test suite, maybe?\n>\n> Stefan,\n>\n> I've also been playing around with diff heuristics and also trying to\n> find some good test data. Have you put together some test cases yet?\n\nI started with that and had 2 or 3 test cases written out, but the\ndiffs of diffs\nconfused me and then I got distracted, so I am stalling on putting together\na mini test suite. You'll find my attempt at [1] as an integration of our\ntest suite. Maybe we don't need to have these tests in tree, but once we're\ndone developing the heuristic, we can put the test suite in the commit message\nof that commit? (Assuming the tests are short and as for a heuristic there is\nno right and wrong, but only a better or worse)\n\n[1] https://github.com/stefanbeller/git/tree/diff_heuristic_improvements\n\n\n>\n> In case you are interested, the current iteration of my heuristic\n> considers six things to determine a \"score\" for breaking a diff above a\n> particular line:\n>\n> * `blank` -- is the line blank?\n> * `indent` -- the indentation of the line (if it is not blank)\n> * `pre_blank` -- is the preceding line blank?\n> * `pre_indent` -- the indentation of the closest preceding non-blank\n> line\n> * `post_blank` -- is the following line blank?\n> * `post_indent` -- the indentation of the closest following non-blank\n> line\n>\n> The meat of the scoring algorithm is below. I compute the score for the\n> beginning and the end of the insert/delete block for each candidate\n> shift of an insertion/deletion hunk, then choose the one that has the\n> lowest score.\n>\n> There are some adjustable \"bonus\" values below. The values shown give\n> quite good results for C, shell, Python, XML, Ruby, CSS, YAML, and HTML\n> in the couple of projects that I've tried it on. But I haven't done\n> enough systematic testing over a large enough corpus to know whether the\n> parameters could be improved or whether there are types of code that it\n> performs really terribly on.\n\nI think the corpus doesn't have to be large, but rather diverse.\n\nThe current heuristic was tested by Jacob and Jeff over the history of the\nlinux kernel, (and some other C projects), which I consider a large corpus --\nBut it's all well formed C, i.e a well known coding style. [2]\n\n[2] don't read this too seriously:\nhttp://codegolf.stackexchange.com/questions/42510/reverse-indentation\n\n>\n> Right now my program doesn't output diffs in the usual format, but\n> rather as a diff notated with various information. So it's not in a form\n> that other people could use so easily. Here's an example:\n>\n>> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n>> *\n>> * Default behaviour is to initialize the notes tree from the tree object\n>> * specified by the given (or default) notes ref.\n>> */\n>> #define NOTES_INIT_EMPTY 1\n>> | -4\n>> | -6 + /*\n>> || 28 + + * By default, the notes tree is only readable, and the notes ref can be\n>> || + + * any treeish. The notes tree can however be made writable with this flag,\n>> || + + * in which case only strict ref names can be used.\n>> || + + */\n>> || + +#define NOTES_INIT_WRITABLE 2\n>> | + +\n>> | +/*\n>> * Initialize the given notes_tree with the notes tree structure at the given\n>> * ref. If given ref is NULL, the value of the $GIT_NOTES_REF environment\n>> * variable is used, and if that is missing, the default notes ref is used\n>> * (\"refs/notes/commits\").\n>> *\n>> * If you need to re-initialize a notes_tree structure (e.g. when switching from\n>> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n>\n> The two columns of vertical bars show the highest and lowest range of\n> lines that this insertion block can be shifted to. The numbers show the\n> score for breaking the diff above that line. The first column of +/- is\n> where this version of the heuristic would place the diff, and the second\n> column is where the master version of Git would place it.\n\nThis is very valuable for understanding and testing different\npatterns! Great work!\n\n>\n> My program can also search for and output \"slideable\" insertion/deletion\n> blocks, so it can be used to find diffs that are theoretically capable\n> of being optimized, even if they don't happen to be handled differently\n> by two different algorithms.\n\nOh right, that is what we can use to find good examples to test on.\n\nI wondered if we could \"machine learn\" the coefficients for these 6\nparameters that you outline above to bring the best matches in most of the time.\n\n>\n> Let me know if you want to collaborate on this somehow.\n\nI am interested, but I dropped the ball last week. I'll pick it up again. :)\n\nStefan\n\n>\n> Michael\n>\n> Scoring heuristic:\n>\n>> # A place to accumulate bonus factors (positive makes this\n>> # index more favored):\n>> bonus = 0\n>>\n>> # Bonuses based on the location of blank lines:\n>> if pre_blank and not blank:\n>> bonus += 3\n>> elif blank and not pre_blank:\n>> bonus += 2\n>> elif blank and pre_blank:\n>> bonus += 1\n>>\n>> # Now fill in missing indent values:\n>> if pre_indent is None:\n>> pre_indent = 0\n>>\n>> if post_indent is None:\n>> post_indent = 0\n>>\n>> if blank:\n>> indent = post_indent\n>>\n>> if indent > pre_indent:\n>> # The line is indented more than its predecessor. It is\n>> # preferable to keep these lines together, so we score it\n>> # based on the larger indent:\n>> score = indent\n>> bonus -= 4\n>>\n>> elif indent < pre_indent:\n>> # The line is indented less than its predecessor. It could\n>> # be that this line is the start of a new block (e.g., of\n>> # an \"else\" block, or of a block without a block\n>> # terminator) or it could be the end of the previous\n>> # block.\n>> if indent < post_indent:\n>> # The following line is indented more. So it is likely\n>> # that this line is the start of a block. It's a\n>> # pretty good place to split, so score it based on the\n>> # smaller indent:\n>> score = indent\n>> bonus += 2\n>> else:\n>> # This was probably the end of a block. We score based\n>> # on the line's own indent:\n>> score = indent\n>>\n>> else:\n>> # The line has the same indentation level as its\n>> # predecessor. We score it based on its own indent:\n>> score = indent\n>>\n>> return 10 * score - bonus\n>\n"},{"id":"289976","messageId":"xmqq1t3nkdrm.fsf@gitster.mtv.corp.google.com","threadId":"42632","inReplyTo":"576C1803.5050905@alum.mit.edu","subject":"Re: [PATCH] diff compaction heuristic: favor shortest neighboring blank lines","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-06-23T17:37:17Z","receivedAt":"2016-06-23T17:37:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty writes:\n\n> Scoring heuristic:\n>\n>> # A place to accumulate bonus factors (positive makes this\n>> # index more favored):\n>> bonus = 0\n>> \n>> # Bonuses based on the location of blank lines:\n>> if pre_blank and not blank:\n>> bonus += 3\n>> elif blank and not pre_blank:\n>> bonus += 2\n>> elif blank and pre_blank:\n>> bonus += 1\n>> \n>> # Now fill in missing indent values:\n>> if pre_indent is None:\n>> pre_indent = 0\n>> \n>> if post_indent is None:\n>> post_indent = 0\n\nThese \"missing\" are to handle the lines at the boundary of shiftable\nblock, or do you have pre_indent if a line is the earliest possible\none that could be included in the hunk by shifting, as long as it is\nnot at the beginning of the file?\n\nI think \"this is indented deeper than the previous, and it wants to\nstay with the previous if possible\" is an excellent heuristic, which\nyou have below. I wonder if \"however, the previous cannot be\nincluded in the hunk by shifting, hence we try to keep this together\nwith it by favouring its exclusion from the hunk\" could be part of\nthe same heuristics, if you do have pre_indent value for a line at\nthe boundary of shiftable block.\n\nAlso I am wondering if 0 is a sensible thing to use as the fallback\nvalue. When pre_indent is not definable, turning it to 0 and\ndeclaring that our indented line is indented deeper than the\nprevious line and penalizing with \"bonus -= 4\" (which you do) feels\njust as fishy as turning the undefined pre_indent to maxint and\ndeclaring that our indented line is indented shallower than the\nprevious line (which you don't, but is just as justifiable, I would\nthink).\n\nThanks.\n\n>> if blank:\n>> indent = post_indent\n>> \n>> if indent > pre_indent:\n>> # The line is indented more than its predecessor. It is\n>> # preferable to keep these lines together, so we score it\n>> # based on the larger indent:\n>> score = indent\n>> bonus -= 4\n>> \n>> elif indent < pre_indent:\n>> # The line is indented less than its predecessor. It could\n>> # be that this line is the start of a new block (e.g., of\n>> # an \"else\" block, or of a block without a block\n>> # terminator) or it could be the end of the previous\n>> # block.\n>> if indent < post_indent:\n>> # The following line is indented more. So it is likely\n>> # that this line is the start of a block. It's a\n>> # pretty good place to split, so score it based on the\n>> # smaller indent:\n>> score = indent\n>> bonus += 2\n>> else:\n>> # This was probably the end of a block. We score based\n>> # on the line's own indent:\n>> score = indent\n>> \n>> else:\n>> # The line has the same indentation level as its\n>> # predecessor. We score it based on its own indent:\n>> score = indent\n>> \n>> return 10 * score - bonus\n"},{"id":"289996","messageId":"576C42EF.80400@alum.mit.edu","threadId":"42632","inReplyTo":"xmqq1t3nkdrm.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] diff compaction heuristic: favor shortest neighboring blank lines","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2016-06-23T20:13:35Z","receivedAt":"2016-06-23T20:13:46Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 06/23/2016 07:37 PM, Junio C Hamano wrote:\n> Michael Haggerty writes:\n> \n>> Scoring heuristic:\n>>\n>>> # A place to accumulate bonus factors (positive makes this\n>>> # index more favored):\n>>> bonus = 0\n>>>\n>>> # Bonuses based on the location of blank lines:\n>>> if pre_blank and not blank:\n>>> bonus += 3\n>>> elif blank and not pre_blank:\n>>> bonus += 2\n>>> elif blank and pre_blank:\n>>> bonus += 1\n>>>\n>>> # Now fill in missing indent values:\n>>> if pre_indent is None:\n>>> pre_indent = 0\n>>>\n>>> if post_indent is None:\n>>> post_indent = 0\n> \n> These \"missing\" are to handle the lines at the boundary of shiftable\n> block, or do you have pre_indent if a line is the earliest possible\n> one that could be included in the hunk by shifting, as long as it is\n> not at the beginning of the file?\n\nThe missing values are meant to handle the case where there are only\nblank lines between the add/delete block and the beginning/end of the\nfile. Though currently (due to a limitation of the prototype) I only\npass context up to the next add/delete line, so that fallback also kicks\nin if there are only blank lines between this add/delete block and the\nnext added/deleted line. When that is fixed, I think it might help to\ngive beginning/end of file a little bit more bonus.\n\nThis isn't all implemented yet, but I think the best score for an\nadd/delete block positioning would be the sum of three values. Let's\ntake the following \"complete file\" diff as an example, and consider an\nadd block with the following positioning:\n\n> diff --git a/file.txt b/file.txt\n> index 9405325..6a6b95c 100644\n> --- a/file.txt\n> +++ b/file.txt\n> @@ -1,5 +1,7 @@\n> a\n> b\n> c\n> +x\n> +c\n> d\n> e\n\nThe score for splitting the old version of the file between\n\"bc\" and \"de\", plus\n\nthe score for splitting the new version of the file between\n\"bc\" and \"xc\", plus\n\nthe score for splitting the new version of the file between\n\"xc\" and \"de\".\n\n> I think \"this is indented deeper than the previous, and it wants to\n> stay with the previous if possible\" is an excellent heuristic, which\n> you have below. I wonder if \"however, the previous cannot be\n> included in the hunk by shifting, hence we try to keep this together\n> with it by favouring its exclusion from the hunk\" could be part of\n> the same heuristics, if you do have pre_indent value for a line at\n> the boundary of shiftable block.\n\nThat's automatic, isn't it? If splitting between two lines is assigned a\nhigh cost, then the algorithm will avoid splitting there *either* by\nincluding both lines in the hunk *or* by omitting both lines.\n\n> Also I am wondering if 0 is a sensible thing to use as the fallback\n> value. When pre_indent is not definable, turning it to 0 and\n> declaring that our indented line is indented deeper than the\n> previous line and penalizing with \"bonus -= 4\" (which you do) feels\n> just as fishy as turning the undefined pre_indent to maxint and\n> declaring that our indented line is indented shallower than the\n> previous line (which you don't, but is just as justifiable, I would\n> think).\n\nOnce the algorithm is fixed to consider the whole file, then the\nfallback value will only be used at the beginning and end of the file,\nwhere an indent of 0 seems like the natural thing to do. As I mentioned\nabove, it might even help to give beginning/end of file a little more\nbonus than that.\n\nBut really, testing against real-world diffs will be the best basis for\nadjusting the heuristic.\n\nMichael\n\n"},{"id":"290594","messageId":"57752478.1000302@alum.mit.edu","threadId":"42632","inReplyTo":"576C1803.5050905@alum.mit.edu","subject":"Re: [PATCH] diff compaction heuristic: favor shortest neighboring blank lines","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2016-06-30T13:54:00Z","receivedAt":"2016-06-30T13:59:20Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 06/23/2016 07:10 PM, Michael Haggerty wrote:\n> On 06/17/2016 06:09 PM, Stefan Beller wrote:\n>> I think before spending more time on discussing and implementing new\n>> (hopefully better) heuristics, I'd want to step back and try to be a bit more\n>> systematic, i.e. I'll want to collect lots of test cases in different languages\n>> and use cases. A mini test suite, maybe?\n> \n> Stefan,\n> \n> I've also been playing around with diff heuristics and also trying to\n> find some good test data. Have you put together some test cases yet?\n\nI put quite of work into tooling to evaluate diff heuristics, and just\npublished it on GitHub:\n\n https://github.com/mhagger/diff-slider-tools\n\nThe README there is hopefully enough to let people get started using it\nto test their own favorite heuristics.\n\n!!!\nPlease be careful! The scripts are not hardened against strangely-named\nfiles!\n!!!\n\nI've run a bunch of tests of the heuristic that I described in the\nprevious email against a bunch of repositories (to try to get a sampling\nof popular languages): ant, bugzilla, couchdb, docker, git, ipython,\njunit, nodejs, phpmyadmin, test-more, test-unit, xmonad.\n\nI haven't done a lot of systematic analysis yet, nor tried to optimize\nthe heuristic systematically, but by eye the results look very good.\nSome constructs (C preprocessor directives, Shell here documents)\nsometimes confuse it because of their weird indentation, and of course\ncode with inconsistent indentation or strangely-placed blank lines\ndoesn't get the best results. But in a large majority of cases where it\ndisagrees with the standard Git or with `git --compaction-heuristic`, it\ndoes a better job.\n\nBelow are a few examples to show off some typical results. I promise I\ntried not to cherry pick only flattering examples.\n\nIn the output below, `|` mark the highest and lowest possible\npositioning of the \"slider\" (a group of added or deleted lines whose\nexact identity is ambiguous). Current Git, by default, always chooses\nthe lowest positioning. \"c\" is where Git master with\n`--compaction-heuristic` chooses to position the slider, and `i` is the\nchoice of my indentation-based algorithm. The numbers are just the shift\nrelative to the standard shift.\n\nMichael\n\nThe algorithm does pretty well with XML and HTML:\n\n> fef3ea39f8bd474add292bb6437df6cbd22e1ba7:contributors.xml a394a0bdf8e6240dc09023a8260059c57c158a00:contributors.xml + 1624\n> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n> > Toni\n> > \n> > \n> > Vincent\n> > Legoll\n> -2 | > \n> -1 | i > \n> 0 || ci > Vincent\n> || ci > Privat\n> | ci > \n> | c > \n> > Vimil\n> > Saju\n> > \n> > \n> > Vitold\n> > Sedyshev\n> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\n> 789422e131b6c2c003d94f394169a64297e986c6:manual/Tasks/signjar.html 7f51882300a8e40ff675867e055061867ba6c8bd:manual/Tasks/signjar.html + 151\n> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n> > \n> > \n> > tsacert\n> > alias in the keystore for a timestamp authority for\n> > timestamped JAR files in Java1.5+\n> -3 | > No\n> -2 | > \n> -1 | i > \n> 0 || ci > tsaproxyhost\n> || ci > proxy host to be used when connecting to TSA server\n> || ci > No\n> || ci > \n> || ci > \n> || ci > getTsaproxyport\n> || ci > proxy port to be used when connecting to TSA server\n> | ci > No\n> | ci > \n> | c > \n> > executable\n> > Specify a particular jarsigner executable\n> > to use in place of the default binary (found in the same JDK as\n> > Apache Ant is running in).
\n> > Must support the same command line options as the Sun JDK\n> > jarsigner command.\n> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nJava:\n\n> de5b4058b9bb039cdb17082fc543098de598ece2:src/main/org/apache/tools/ant/taskdefs/optional/ssh/AbstractSshMessage.java 3fe363e2120342f6de2b219c3bd74efe9aea2803:src/main/org/apache/tools/ant/taskdefs/optional/ssh/AbstractSshMessage.java + 208\n> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n> > * @return true if the verbose attribute is set\n> > * @since Ant 1.6.2\n> > */\n> > protected final boolean getVerbose() {\n> > return verbose;\n> -3 | > }\n> -2 | >\n> -1 | ci > /**\n> 0 || ci > * Is the compressed attribute set.\n> || ci > * @return true if the compressed attribute is set\n> || ci > * @since Ant 1.9.8\n> || ci > */\n> || ci > protected final boolean getCompressed() {\n> || ci > return compressed;\n> | ci > }\n> | ci >\n> | > /**\n> > * Track progress every 10% if 100kb < filesize < 1mb. For larger\n> > * files track progress for every percent transmitted.\n> > * @param filesize the size of the file been transmitted\n> > * @param totalLength the total transmission size\n> > * @param percentTransmitted the current percent transmitted\n> > * @return the percent that the file is of the total\n> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\n> cd1ff3566ed915392041314eb583a638bcb1eb64:src/main/org/apache/tools/ant/taskdefs/optional/ejb/WeblogicDeploymentTool.java a8d6367ddc214b4956b2a7d6b779930df5e43515:src/main/org/apache/tools/ant/taskdefs/optional/ejb/WeblogicDeploymentTool.java - 888\n> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n> > // empty\n> > }\n> > }\n> >\n> > if (newJarStream != null) {\n> -1 | i > try {\n> 0 || ci > newJarStream.close();\n> || ci > } catch (IOException closeException) {\n> || ci > // empty\n> || ci > }\n> || ci >\n> | c > try {\n> > FILE_UTILS.rename(newWLJarFile, weblogicJarFile);\n> > } catch (IOException renameException) {\n> > log(renameException.getMessage(), Project.MSG_WARN);\n> > rebuild = true;\n> > }\n> > }\n> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nPerl:\n\n> bb18f8a6d560fa141f812dddcf6f6d8fe8b49dbb:Bugzilla/DB.pm 16f1833e572297edd89faddb69364e09efecdfdb:Bugzilla/DB.pm + 98\n> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n> ># PostgreSQL, and hopefully will get us as much Unicode support as possible,\n> ># depending on how well the regexp engines of the various databases support\n> ># Unicode.\n> >use constant WORD_START => '(^|[^[:alnum:]])';\n> >use constant WORD_END => '($|[^[:alnum:]])';\n> -2 | >\n> -1 | ci >#####################################################################\n> 0 || ci ># Overridden Superclass Methods \n> || ci >#####################################################################\n> || ci >\n> || ci >sub quote {\n> || ci > my $self = shift;\n> || ci > my $retval = $self->SUPER::quote(@_);\n> || ci > trick_taint($retval) if defined $retval;\n> || ci > return $retval;\n> || ci >}\n> | ci >\n> | >#####################################################################\n> ># Connection Methods\n> >#####################################################################\n> >\n> >sub connect_shadow {\n> > my $params = Bugzilla->params;\n> > die \"Tried to connect to non-existent shadowdb\" \n> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\n> dbfd6207290d1eee53fddec4c7c3b4aac0b2d47a:Bugzilla/Install/Requirements.pm 3c7ab8316f97fe84222ccacf0d1b4be9cd43e9f8:Bugzilla/Install/Requirements.pm - 338\n> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n> > feature => ['rest']\n> > },\n> > {\n> > package => 'HTTP-Response',\n> > module => 'HTTP::Response',\n> -4 | > version => 0,\n> -3 | > feature => ['rest']\n> -2 | > },\n> -1 | i > {\n> 0 || ci > package => 'URI-Escape',\n> || ci > module => 'URI::Escape',\n> | ci > version => 0,\n> | ci > feature => ['rest']\n> | ci > },\n> | c > {\n> > # We need the 'utf8_mode' method of HTML::Parser, for HTML::Scrubber.\n> > package => 'HTML-Parser',\n> > module => 'HTML::Parser',\n> > version => ($^V >= v5.13.3) ? '3.67' : '3.40',\n> > feature => ['html_desc'],\n> > },\n> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nErlang:\n\n> 56f969b3c49375c5321eb3cceb0fe346f8535c22:src/couchdb/couch_httpd.erl b90e40212663474e873fde6cab343c31c1e635e7:src/couchdb/couch_httpd.erl + 332\n> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n> > case couch_httpd_cors:is_preflight_request(HttpReq) of\n> > #httpd{} ->\n> > case authenticate_request(HttpReq, AuthHandlers) of\n> > #httpd{} = Req ->\n> > HandlerFun(Req);\n> -2 | i > Response ->\n> -1 | i > Response\n> 0 || ci > end;\n> | c > Response ->\n> | c > Response\n> > end\n> > catch\n> > throw:{http_head_abort, Resp0} ->\n> > {ok, Resp0};\n> > throw:{invalid_json, S} ->\n> > ?LOG_ERROR(\"attempted upload of invalid JSON (set log_level to debug to log it)\", []),\n> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nGo:\n\n> 7b2b4eb40cfd907f3aa20b630cc2feeb8460404a:opts/hosts.go fb3eb1c27ef5520571c599ead8a72b343748db39:opts/hosts.go + 132\n> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n> >\tu, err := url.Parse(\"tcp://\" + addr)\n> >\tif err != nil {\n> >\t\treturn \"\", err\n> >\t}\n> >\thost, port, err := net.SplitHostPort(u.Host)\n> -1 | i >\tif err != nil {\n> 0 || ci >\t\t// try port addition once\n> || ci >\t\thost, port, err = net.SplitHostPort(net.JoinHostPort(u.Host, defaultPort))\n> || ci >\t}\n> | c >\tif err != nil {\n> >\t\treturn \"\", fmt.Errorf(\"Invalid bind address format: %s\", tryAddr)\n> >\t}\n> >\n> >\tif host == \"\" {\n> >\t\thost = defaultHost\n> >\t}\n> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\ngettext source:\n\n> aef18cc6063106075afeb3a78ec72656b19c8bde:po/de.po b0e098ce46ce7f8ecd975720ccec8d0eb7787e50:po/de.po - 12954\n> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n> >#~ msgid \"unmerged: %s\"\n> >#~ msgstr \"nicht zusammengeführt: %s\"\n> >\n> >#~ msgid \"input paths are terminated by a null character\"\n> >#~ msgstr \"Eingabepfade sind durch ein NUL Zeichen abgeschlossen\"\n> -2 | >\n> -1 | ci >#~ msgid \"\"\n> 0 || ci >#~ \"The following untracked files would NOT be saved but need to be removed \"\n> || ci >#~ \"by stash save:\"\n> || ci >#~ msgstr \"\"\n> || ci >#~ \"Die folgenden unbeobachteten Dateien würden NICHT gespeichert werden,\\n\"\n> || ci >#~ \"müssen aber durch \\\"stash save\\\" entfernt werden:\"\n> | ci >\n> | >#~ msgid \"\"\n> >#~ \"Aborting. Consider using either the --force or --include-untracked option.\"\n> >#~ msgstr \"\"\n> >#~ \"Abgebrochen. Benutzen Sie entweder die Option --force oder --include-\"\n> >#~ \"untracked.\"\n> >\n> >#~ msgid \" (fix conflicts and then run \\\"git am --resolved\\\")\"\n> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nC:\n\n> eeff891ac756fd97a05476446f15269b714ce4cc:grep.c 79a77109d3d0d364910ff7fa8c605c554dc4c3e0:grep.c + 1133\n> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n> >\t\tregmatch_t match;\n> >\t\tenum grep_context ctx = GREP_CONTEXT_BODY;\n> >\t\tint ch = *eol;\n> >\t\tint eflags = 0;\n> >\n> -1 | i >\t\tif (sign == ':')\n> 0 || ci >\t\t\tmatch_color = opt->color_match_selected;\n> || ci >\t\telse\n> || ci >\t\t\tmatch_color = opt->color_match_context;\n> | c >\t\tif (sign == ':')\n> >\t\t\tline_color = opt->color_selected;\n> >\t\telse if (sign == '-')\n> >\t\t\tline_color = opt->color_context;\n> >\t\telse if (sign == '=')\n> >\t\t\tline_color = opt->color_function;\n> >\t\t*eol = '\\0';\n> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nTcl:\n\n> a9ae14a1c50a9b5bd051be629dba0fb04b6fd67a:git-gui.sh 25476c63e7d3357f955b44dd6a7c825aba819987:git-gui.sh - 3158\n> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n> >\n> ># -- Diff Body Context Menu\n> >#\n> >\n> >proc create_common_diff_popup {ctxm} {\n> -1 | i >\t$ctxm add command \\\n> 0 || ci >\t\t-label [mc \"Show Less Context\"] \\\n> || ci >\t\t-command show_less_context\n> || ci >\tlappend diff_actions [list $ctxm entryconf [$ctxm index last] -state]\n> || ci >\t$ctxm add command \\\n> || ci >\t\t-label [mc \"Show More Context\"] \\\n> || ci >\t\t-command show_more_context\n> || ci >\tlappend diff_actions [list $ctxm entryconf [$ctxm index last] -state]\n> || ci >\t$ctxm add separator\n> | c >\t$ctxm add command \\\n> >\t\t-label [mc Refresh] \\\n> >\t\t-command reshow_diff\n> >\tlappend diff_actions [list $ctxm entryconf [$ctxm index last] -state]\n> >\t$ctxm add command \\\n> >\t\t-label [mc Copy] \\\n> >\t\t-command {tk_textCopy $ui_diff}\n> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nShell:\n\n> 34a82bda7766f000ef646130ed3f6af58ca23aa2:git-subtree.sh 942dce5578c8eb03fdc7f9109c8418d499e931ff:git-subtree.sh + 40\n> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n> >rejoin=\n> >ignore_joins=\n> >annotate=\n> >\n> >debug()\n> -1 | i >{\n> 0 || ci >\tif [ -n \"$debug\" ]; then\n> || ci >\t\techo \"$@\" >&2\n> || ci >\tfi\n> || ci >}\n> || ci >\n> || ci >say()\n> | c >{\n> >\tif [ -z \"$quiet\" ]; then\n> >\t\techo \"$@\" >&2\n> >\tfi\n> >}\n> >\n> >assert()\n> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nPython:\n\n> 9ccc64b8ea94a9083038b079a8e2691ae94591fe:IPython/html/base/handlers.py db6ce120fc0bc0a4b29969f43af98e4841d5e1be:IPython/html/base/handlers.py - 90\n> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n> > def cookie_name(self):\n> > default_cookie_name = non_alphanum.sub('-', 'username-{}'.format(\n> > self.request.host\n> > ))\n> > return self.settings.get('cookie_name', default_cookie_name)\n> -2 | > \n> -1 | i > @property\n> 0 || ci > def password(self):\n> || ci > \"\"\"our password\"\"\"\n> || ci > return self.settings.get('password', '')\n> | ci > \n> | c > @property\n> > def logged_in(self):\n> > \"\"\"Is a user currently logged in?\n> >\n> > \"\"\"\n> > user = self.get_current_user()\n> > return (user and not user == 'anonymous')\n> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\njavascript (and JSON):\n\n> d3c3a928c3a2f9e961881b47ef0796e57ae8d429:tools/eslint/lib/rules/no-arrow-condition.js d7aa8fa088f3b8a31c7d85c6d71824c8c60e7c17:tools/eslint/lib/rules/no-confusing-arrow.js - 58\n> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n> >//------------------------------------------------------------------------------\n> >// Rule Definition\n> >//------------------------------------------------------------------------------\n> >\n> >module.exports = function(context) {\n> -1 | i > /**\n> 0 || ci > * Reports if a conditional statement is an arrow function.\n> || ci > * @param {ASTNode} node - A node to check and report.\n> || ci > * @returns {void}\n> || ci > */\n> || ci > function checkCondition(node) {\n> || ci > if (isArrowFunction(node)) {\n> || ci > context.report(node, \"Arrow function `=>` used inside {{statementType}} instead of comparison operator.\", {statementType: node.type});\n> || ci > }\n> || ci > }\n> || ci >\n> | c > /**\n> > * Reports if an arrow function contains an ambiguous conditional.\n> > * @param {ASTNode} node - A node to check and report.\n> > * @returns {void}\n> > */\n> > function checkArrowFunc(node) {\n> > if (isConditional(node)) {\n> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nPHP:\n\n> cc9550579c02d652686bdc574bc91fb982f7d95b:libraries/ThemeManager.php ca5eb903b04035f78819ae1e14ff888155bd3e32:libraries/ThemeManager.php + 20\n> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n> > *\n> > * @package PhpMyAdmin\n> > */\n> >class ThemeManager\n> >{\n> -1 | i > /**\n> 0 || ci > * ThemeManager instance\n> || ci > *\n> || ci > * @access private\n> || ci > * @static\n> || ci > * @var ThemeManager\n> || ci > */\n> || ci > private static $_instance;\n> || ci >\n> | c > /**\n> > * @var string path to theme folder\n> > * @access protected\n> > */\n> > private $_themes_path = './themes/';\n> >\n> > /**\n> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nRuby:\n\n> 0ae3800be7ca632c47c089d527b53a8f66960c60:test/test_assertions.rb c35d9e2de60441cae592a300dae1460b45562cce:test/test_assertions.rb - 120\n> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n> > end\n> > \n> > def test_assert_equal\n> > check_nothing_fails {\n> > assert_equal(\"string1\", \"string1\")\n> -2 | > }\n> -1 | i > check_nothing_fails {\n> 0 || ci > assert_equal( \"string1\", \"string1\", \"successful assert_equal\")\n> | ci > }\n> | c > check_nothing_fails {\n> > assert_equal(\"string1\", \"string1\", \"successful assert_equal\")\n> > }\n> >\n> > message = <<-EOM.chomp\n> ><\"string1\"> expected but was\n> ><\"string2\">.\n> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\n\nIt often fails to get C preprocessor directives right:\n\n> a08595f76159b09d57553e37a5123f1091bb13e7:http.c aeff8a61216bf6e0d663c08c583bc8552fa3c344:http.c + 429\n> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n> >\t\tcurl_easy_setopt(result, CURLOPT_SSLKEY, ssl_key);\n> >#endif\n> >#if LIBCURL_VERSION_NUM >= 0x070908\n> >\tif (ssl_capath != NULL)\n> >\t\tcurl_easy_setopt(result, CURLOPT_CAPATH, ssl_capath);\n> -1 | i >#endif\n> 0 || ci >#if LIBCURL_VERSION_NUM >= 0x072c00\n> || ci >\tif (ssl_pinnedkey != NULL)\n> || ci >\t\tcurl_easy_setopt(result, CURLOPT_PINNEDPUBLICKEY, ssl_pinnedkey);\n> | c >#endif\n> >\tif (ssl_cainfo != NULL)\n> >\t\tcurl_easy_setopt(result, CURLOPT_CAINFO, ssl_cainfo);\n> >\n> >\tif (curl_low_speed_limit > 0 && curl_low_speed_time > 0) {\n> >\t\tcurl_easy_setopt(result, CURLOPT_LOW_SPEED_LIMIT,\n> >\t\t\t\t curl_low_speed_limit);\n> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nAnd it gets confused by unusual blank line placement:\n\n> ed55169834a3ce16a271def9630c858626ded34d:tools/eslint/node_modules/doctrine/lib/doctrine.js 2d441493a4a46a511ba1bdf93e442c3288fbe92d:tools/eslint/node_modules/doctrine/lib/doctrine.js + 330\n> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n> > name === 'external' ||\n> > name === 'event')) {\n> > name += advance();\n> > name += scanIdentifier(last);\n> >\n> -1 | i > }\n> 0 || ci > if(source.charCodeAt(index) === 0x5B /* '[' */ && source.charCodeAt(index + 1) === 0x5D /* ']' */){\n> || ci > name += advance();\n> || ci > name += advance();\n> | c > }\n> > while (source.charCodeAt(index) === 0x2E /* '.' */ ||\n> > source.charCodeAt(index) === 0x23 /* '#' */ ||\n> > source.charCodeAt(index) === 0x7E /* '~' */) {\n> > name += advance();\n> > name += scanIdentifier(last);\n> > }\n> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nor inconsistent indentation:\n\n> 1768d08d029dc3bf1ab88e26df0a9b40ae61227f:src/main/java/org/junit/internal/runners/statements/FailOnTimeout.java 5ca9da987a7d4dc00e082aaf552cbd8ee8c7bd33:src/main/java/org/junit/internal/runners/statements/FailOnTimeout.java + 136\n> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n> > maxCpuTime = threadCpuTime;\n> > }\n> > \t\t} \t\t\t\n> > \t}\n> > \treturn (stuckThread == mainThread) ? null : stuckThread;\n> -2 | i > }\n> -1 | i >\n> 0 || ci > /**\n> || ci > * Returns the CPU time used by a thread, if possible.\n> || ci > * @param thr The thread to query.\n> || ci > * @return The CPU time used by {@code thr}, or 0 if it cannot be determined.\n> || ci > */\n> || ci > private long cpuTime (Thread thr) {\n> || ci >\t\tThreadMXBean mxBean = ManagementFactory.getThreadMXBean();\n> || ci > if (mxBean.isThreadCpuTimeSupported()) {\n> || ci > try {\n> || ci > return mxBean.getThreadCpuTime(thr.getId());\n> || ci > } catch (UnsupportedOperationException e) {\n> || ci > }\n> || ci > }\n> || ci > return 0;\n> | c > }\n> | c >\n> >\tprivate class CallableStatement implements Callable {\n> > public Throwable call() throws Exception {\n> > try {\n> > fOriginalStatement.evaluate();\n> > } catch (Exception e) {\n> > throw e;\n> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\n"},{"id":"290681","messageId":"5776A29F.4020609@alum.mit.edu","threadId":"42632","inReplyTo":"57752478.1000302@alum.mit.edu","subject":"diff heuristics dramatically improved by considering line indentation and blank lines","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2016-07-01T17:04:31Z","receivedAt":"2016-07-01T17:05:02Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 06/30/2016 03:54 PM, Michael Haggerty wrote:\n> On 06/23/2016 07:10 PM, Michael Haggerty wrote:\n>> On 06/17/2016 06:09 PM, Stefan Beller wrote:\n>>> I think before spending more time on discussing and implementing new\n>>> (hopefully better) heuristics, I'd want to step back and try to be a bit more\n>>> systematic, i.e. I'll want to collect lots of test cases in different languages\n>>> and use cases. A mini test suite, maybe?\n>>\n>> Stefan,\n>>\n>> I've also been playing around with diff heuristics and also trying to\n>> find some good test data. Have you put together some test cases yet?\n> \n> I put quite of work into tooling to evaluate diff heuristics, and just\n> published it on GitHub:\n> \n> https://github.com/mhagger/diff-slider-tools\n\nToday I hand-optimized about 2700 diff sliders in 12 different\nrepositories and used that as a reference corpus against which I tested\nthe accuracy of four different algorithms. The tools and the\nhand-optimized values are now in the GitHub repository mentioned above.\nSee also this pull request [1].\n\nIf I didn't make any mistakes, the number of errors (i.e., cases where\nthe algorithm choose a different slider shift than the one I picked by\nhand) look like this:\n\n> | repository | default | compaction | indent | indent-favor-edges |\n> | -------------------- | ------- | ---------- | ------ | ------------------ |\n> | ant | 225 | 102 | 7 | 7 |\n> | bugzilla | 208 | 81 | 14 | 14 |\n> | couchdb | 44 | 24 | 13 | 10 |\n> | docker | 180 | 160 | 29 | 18 |\n> | git | 446 | 59 | 27 | 19 |\n> | ipython | 358 | 163 | 61 | 11 |\n> | junit | 146 | 67 | 5 | 5 |\n> | nodejs | 489 | 78 | 12 | 12 |\n> | phpmyadmin | 330 | 49 | 1 | 0 |\n> | test-more | 15 | 2 | 2 | 0 |\n> | test-unit | 33 | 13 | 4 | 4 |\n> | -------------------- | ------- | ---------- | ------ | ------------------ |\n> | totals | 2474 | 798 | 175 | 100 |\n\nThe algorithms are:\n\n* default -- the default behavior `git diff` on the current master\n* compaction -- `git diff --compaction-heuristic`\n* indent -- the indent-based algorithm as reported earlier in\n this thread\n* indent-favor-edges -- the indent-based algorithm, with some\n improved heuristics regarding sliders near the begin/end of file\n and probably one or two fixes\n\nI encourage other people to run the tests against some code samples in\ntheir favorite programming languages so that the testing can cover a\nwider range of inputs, and submit your data to the GitHub project. Also\nfeel free to tweak the heuristic (there's probably still room for\nimprovement). All the tools and raw data for my experiments are already\nthere.\n\nI'll be going on vacation for the next two weeks so I probably can't\nfollow up on this for a while. But I think we should build an algorithm\nlike this into Git!\n\nMichael\n\n[1] https://github.com/mhagger/diff-slider-tools/pull/1\n\n"},{"id":"290689","messageId":"xmqq8txlz19e.fsf@gitster.mtv.corp.google.com","threadId":"42632","inReplyTo":"57752478.1000302@alum.mit.edu","subject":"Re: [PATCH] diff compaction heuristic: favor shortest neighboring blank lines","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-07-01T18:01:01Z","receivedAt":"2016-07-01T18:01:15Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty writes:\n\n> I put quite of work into tooling to evaluate diff heuristics, and just\n> published it on GitHub:\n>\n> https://github.com/mhagger/diff-slider-tools\n>\n> The README there is hopefully enough to let people get started using it\n> to test their own favorite heuristics.\n\nIntereting. A fair TL;DR of this would be that what we write and\nwant to diff have the structure where things often are ordered in an\ninherent hierarchy, and things at the higher level are highlighted\nby being less indented, and the indent-based heuristics exploit that\nwell to choose a slide that breaks at the higher-level boundary, e.g.\n\n> The algorithm does pretty well with XML and HTML:\n>\n>> fef3ea39f8bd474add292bb6437df6cbd22e1ba7:contributors.xml a394a0bdf8e6240dc09023a8260059c57c158a00:contributors.xml + 1624\n>> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n>> > Toni\n>> > \n>> > \n>> > Vincent\n>> > Legoll\n>> -2 | > \n>> -1 | i > \n>> 0 || ci > Vincent\n>> || ci > Privat\n>> | ci > \n>> | c > \n\nAnd that trait is shared among common programming languages (Java,\nPerl, Go, C, etc.).\n\nThe only case I can think of offhand that does not follow \"higher\nlevel heading is less indented\" pattern is an already typeset book,\nwhere chapter headers are often centered on the page while section\nheaders may be at the left edge. But we are not likely to be\ninterested to get that case right anyway, so it is OK.\n\n> gettext source:\n>\n>> aef18cc6063106075afeb3a78ec72656b19c8bde:po/de.po b0e098ce46ce7f8ecd975720ccec8d0eb7787e50:po/de.po - 12954\n>> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n>> >#~ msgid \"unmerged: %s\"\n>> >#~ msgstr \"nicht zusammengeführt: %s\"\n>> >\n>> >#~ msgid \"input paths are terminated by a null character\"\n>> >#~ msgstr \"Eingabepfade sind durch ein NUL Zeichen abgeschlossen\"\n>> -2 | >\n>> -1 | ci >#~ msgid \"\"\n>> 0 || ci >#~ \"The following untracked files would NOT be saved but need to be removed \"\n>> || ci >#~ \"by stash save:\"\n>> || ci >#~ msgstr \"\"\n>> || ci >#~ \"Die folgenden unbeobachteten Dateien würden NICHT gespeichert werden,\\n\"\n>> || ci >#~ \"müssen aber durch \\\"stash save\\\" entfernt werden:\"\n>> | ci >\n\nThis is an interesting example of \"have only a single level\nhierarchy. A line is either in one block or a blank between\nblocks\".\n\n> It often fails to get C preprocessor directives right:\n>\n>> a08595f76159b09d57553e37a5123f1091bb13e7:http.c aeff8a61216bf6e0d663c08c583bc8552fa3c344:http.c + 429\n>> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n>> >\t\tcurl_easy_setopt(result, CURLOPT_SSLKEY, ssl_key);\n>> >#endif\n>> >#if LIBCURL_VERSION_NUM >= 0x070908\n>> >\tif (ssl_capath != NULL)\n>> >\t\tcurl_easy_setopt(result, CURLOPT_CAPATH, ssl_capath);\n>> -1 | i >#endif\n>> 0 || ci >#if LIBCURL_VERSION_NUM >= 0x072c00\n>> || ci >\tif (ssl_pinnedkey != NULL)\n>> || ci >\t\tcurl_easy_setopt(result, CURLOPT_PINNEDPUBLICKEY, ssl_pinnedkey);\n>> | c >#endif\n\nYes, this is \"non-human do not know 'end' is likely to be at the end\nof a logical block\".\n\n> And it gets confused by unusual blank line placement:\n>\n>> ed55169834a3ce16a271def9630c858626ded34d:tools/eslint/node_modules/doctrine/lib/doctrine.js 2d441493a4a46a511ba1bdf93e442c3288fbe92d:tools/eslint/node_modules/doctrine/lib/doctrine.js + 330\n>> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n>> > name === 'external' ||\n>> > name === 'event')) {\n>> > name += advance();\n>> > name += scanIdentifier(last);\n>> >\n>> -1 | i > }\n>> 0 || ci > if(source.charCodeAt(index) === 0x5B /* '[' */ && source.charCodeAt(index + 1) === 0x5D /* ']' */){\n>> || ci > name += advance();\n>> || ci > name += advance();\n>> | c > }\n\nLikewise, this is showing that a \"non-human not knowing } is a closing\nand { is an opening token\".\n\nBy the way, I no longer remember what indent level your\n\"indent-only\" heuristics gives to a blank line. Does the closing\nbrace we see above (marked with -1) count as increasing the\nindentation level from the previous empty-line at indent 0, or does it\ncount as dedenting from the previous empty-line that has virtually\nat the same indent level as \"name += scanIdentifier(last);\" line?\n\n"},{"id":"290789","messageId":"577A73CC.1050200@gmail.com","threadId":"42632","inReplyTo":"xmqq8txlz19e.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] diff compaction heuristic: favor shortest neighboring blank lines","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2016-07-04T14:33:48Z","receivedAt":"2016-07-04T14:34:06Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"W dniu 2016-07-01 o 20:01, Junio C Hamano pisze:\n> Michael Haggerty writes:\n\n>> It often fails to get C preprocessor directives right:\n>>\n>>> a08595f76159b09d57553e37a5123f1091bb13e7:http.c aeff8a61216bf6e0d663c08c583bc8552fa3c344:http.c + 429\n>>> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n>>> >\t\tcurl_easy_setopt(result, CURLOPT_SSLKEY, ssl_key);\n>>> >#endif\n>>> >#if LIBCURL_VERSION_NUM >= 0x070908\n>>> >\tif (ssl_capath != NULL)\n>>> >\t\tcurl_easy_setopt(result, CURLOPT_CAPATH, ssl_capath);\n>>> -1 | i >#endif\n>>> 0 || ci >#if LIBCURL_VERSION_NUM >= 0x072c00\n>>> || ci >\tif (ssl_pinnedkey != NULL)\n>>> || ci >\t\tcurl_easy_setopt(result, CURLOPT_PINNEDPUBLICKEY, ssl_pinnedkey);\n>>> | c >#endif\n> \n> Yes, this is \"non-human do not know 'end' is likely to be at the end\n> of a logical block\".\n\nI wonder if taking into account xfuncname match to adjust heuristics\n(or to change \"slider\") would help there. I think good heuristic\nwould be to break before xfuncname match (before new section).\n \n>> And it gets confused by unusual blank line placement:\n>>\n>>> ed55169834a3ce16a271def9630c858626ded34d:tools/eslint/node_modules/doctrine/lib/doctrine.js 2d441493a4a46a511ba1bdf93e442c3288fbe92d:tools/eslint/node_modules/doctrine/lib/doctrine.js + 330\n>>> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n>>> > name === 'external' ||\n>>> > name === 'event')) {\n>>> > name += advance();\n>>> > name += scanIdentifier(last);\n>>> >\n>>> -1 | i > }\n>>> 0 || ci > if(source.charCodeAt(index) === 0x5B /* '[' */ && source.charCodeAt(index + 1) === 0x5D /* ']' */){\n>>> || ci > name += advance();\n>>> || ci > name += advance();\n>>> | c > }\n> \n> Likewise, this is showing that a \"non-human not knowing } is a closing\n> and { is an opening token\".\n\nIf not encoding heuristic that [,{,( are opening token, and ],},) are\nclosing token into heuristics, perhaps length of the line could be\na consideration about where to start a diff chunk?\n\n-- \nJakub Narębski\n\n\n"}]}