{"thread":{"id":"42065","subject":"[PATCH 1/2] xdiff: add recs_match helper function","startedAt":"2016-04-18T21:12:28Z","lastAt":"2016-04-20T16:17:17Z","messageCount":20,"participants":["Stefan Beller","Junio C Hamano","Jacob Keller","Jeff King","Michael S. Tsirkin"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"283750","messageId":"1461013950-12503-1-git-send-email-sbeller@google.com","threadId":"42065","inReplyTo":null,"subject":"[PATCH 0/2 v4] xdiff: implement empty line chunk heuristic","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-04-18T21:12:28Z","receivedAt":"2016-04-18T21:12:28Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"> OK, so perhaps either of you two can do a final version people can\n> start having fun with?\n\nHere we go. I squashed in your patch, although with a minor change:\n\n- if ((flags & XDF_SHORTEST_LINE_HEURISTIC)) {\n+ if ((flags & XDF_COMPACTION_HEURISTIC) && blank_lines) {\n\nWe did not need that in the \"shortest line\" heuristic as we know\na line with the shortest line length must exist. We do not know about\nempty lines though.\n\nThanks,\nStefan\n\nJacob Keller (1):\n xdiff: add recs_match helper function\n\nStefan Beller (1):\n xdiff: implement empty line chunk heuristic\n\n Documentation/diff-config.txt | 5 +++++\n Documentation/diff-options.txt | 6 ++++++\n diff.c | 11 +++++++++++\n xdiff/xdiff.h | 2 ++\n xdiff/xdiffi.c | 40 ++++++++++++++++++++++++++++++++++++----\n 5 files changed, 60 insertions(+), 4 deletions(-)\n\n-- \n2.8.0.26.gba39a1b.dirty\n"},{"id":"283749","messageId":"1461013950-12503-2-git-send-email-sbeller@google.com","threadId":"42065","inReplyTo":"1461013950-12503-1-git-send-email-sbeller@google.com","subject":"[PATCH 1/2] xdiff: add recs_match helper function","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-04-18T21:12:29Z","receivedAt":"2016-04-18T21:12:29Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"From: Jacob Keller \n\nIt is a common pattern in xdl_change_compact to check that hashes and\nstrings match. The resulting code to perform this change causes very\nlong lines and makes it hard to follow the intention. Introduce a helper\nfunction recs_match which performs both checks to increase\ncode readability.\n\nSigned-off-by: Jacob Keller \nSigned-off-by: Stefan Beller \n---\n xdiff/xdiffi.c | 14 ++++++++++----\n 1 file changed, 10 insertions(+), 4 deletions(-)\n\ndiff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\nindex 2358a2d..748eeb9 100644\n--- a/xdiff/xdiffi.c\n+++ b/xdiff/xdiffi.c\n@@ -400,6 +400,14 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,\n }\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+\t\txdl_recmatch(recs[ixs]->ptr, recs[ixs]->size,\n+\t\t\t recs[ix]->ptr, recs[ix]->size,\n+\t\t\t flags));\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@@ -442,8 +450,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n \t\t\t * the last line of the current change group, shift backward\n \t\t\t * the group.\n \t\t\t */\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\twhile (ixs > 0 && recs_match(recs, ixs - 1, ix - 1, flags)) {\n \t\t\t\trchg[--ixs] = 1;\n \t\t\t\trchg[--ix] = 0;\n \n@@ -470,8 +477,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n \t\t\t * the line next of the current change group, shift forward\n \t\t\t * the group.\n \t\t\t */\n-\t\t\twhile (ix < nrec && recs[ixs]->ha == recs[ix]->ha &&\n-\t\t\t xdl_recmatch(recs[ixs]->ptr, recs[ixs]->size, recs[ix]->ptr, recs[ix]->size, flags)) {\n+\t\t\twhile (ix < nrec && recs_match(recs, ixs, ix, flags)) {\n \t\t\t\trchg[ixs++] = 0;\n \t\t\t\trchg[ix++] = 1;\n \n-- \n2.8.0.26.gba39a1b.dirty\n"},{"id":"283751","messageId":"1461013950-12503-3-git-send-email-sbeller@google.com","threadId":"42065","inReplyTo":"1461013950-12503-1-git-send-email-sbeller@google.com","subject":"[PATCH 2/2] xdiff: implement empty line chunk heuristic","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-04-18T21:12:30Z","receivedAt":"2016-04-18T21:12:30Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"In order to produce the smallest possible diff and combine several diff\nhunks together, we implement a heuristic from GNU Diff which moves diff\nhunks forward as far as possible when we find common context above and\nbelow a diff hunk. This sometimes produces less readable diffs when\nwriting C, Shell, or other programming languages, ie:\n\n...\n /*\n+ *\n+ *\n+ */\n+\n+/*\n...\n\ninstead of the more readable equivalent of\n\n...\n+/*\n+ *\n+ *\n+ */\n+\n /*\n...\n\nImplement the following heuristic to (optionally) produce the desired\noutput.\n\n If there are diff chunks which can be shifted around, shift each hunk\n such that the last common empty line is below the chunk with the rest\n of the context above.\n\nThis heuristic appears to resolve the above example and several other\ncommon issues without producing significantly weird results. However, as\nwith any heuristic it is not really known whether this will always be\nmore optimal. Thus, it can be disabled via diff.compactionHeuristic.\n\nSigned-off-by: Stefan Beller \nSigned-off-by: Jacob Keller \nSigned-off-by: Stefan Beller \n---\n Documentation/diff-config.txt | 5 +++++\n Documentation/diff-options.txt | 6 ++++++\n diff.c | 11 +++++++++++\n xdiff/xdiff.h | 2 ++\n xdiff/xdiffi.c | 26 ++++++++++++++++++++++++++\n 5 files changed, 50 insertions(+)\n\ndiff --git a/Documentation/diff-config.txt b/Documentation/diff-config.txt\nindex edba565..a9f4b57 100644\n--- a/Documentation/diff-config.txt\n+++ b/Documentation/diff-config.txt\n@@ -170,6 +170,11 @@ diff.tool::\n \n include::mergetools-diff.txt[]\n \n+diff.compactionHeuristic::\n+\tSet this option to enable an experimental heuristic that\n+\tshifts the hunk boundary in an attempt to make the resulting\n+\tpatch easier to read.\n+\n diff.algorithm::\n \tChoose a diff algorithm. The variants are as follows:\n +\ndiff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\nindex 4b0318e..0993742 100644\n--- a/Documentation/diff-options.txt\n+++ b/Documentation/diff-options.txt\n@@ -63,6 +63,12 @@ ifndef::git-format-patch[]\n \tSynonym for `-p --raw`.\n endif::git-format-patch[]\n \n+--compaction-heuristic::\n+--no-compaction-heuristic::\n+\tThese are to help debugging and tuning an experimental\n+\theuristic that shifts the hunk boundary in an attempt to\n+\tmake the resulting patch easier to read.\n+\n --minimal::\n \tSpend extra time to make sure the smallest possible\n \tdiff is produced.\ndiff --git a/diff.c b/diff.c\nindex 4dfe660..d3734d3 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -26,6 +26,7 @@\n #endif\n \n static int diff_detect_rename_default;\n+static int diff_compaction_heuristic = 1;\n static int diff_rename_limit_default = 400;\n static int diff_suppress_blank_empty;\n static int diff_use_color_default = -1;\n@@ -189,6 +190,10 @@ int git_diff_ui_config(const char *var, const char *value, void *cb)\n \t\tdiff_detect_rename_default = git_config_rename(var, value);\n \t\treturn 0;\n \t}\n+\tif (!strcmp(var, \"diff.compactionheuristic\")) {\n+\t\tdiff_compaction_heuristic = git_config_bool(var, value);\n+\t\treturn 0;\n+\t}\n \tif (!strcmp(var, \"diff.autorefreshindex\")) {\n \t\tdiff_auto_refresh_index = git_config_bool(var, value);\n \t\treturn 0;\n@@ -3278,6 +3283,8 @@ void diff_setup(struct diff_options *options)\n \toptions->use_color = diff_use_color_default;\n \toptions->detect_rename = diff_detect_rename_default;\n \toptions->xdl_opts |= diff_algorithm;\n+\tif (diff_compaction_heuristic)\n+\t\tDIFF_XDL_SET(options, COMPACTION_HEURISTIC);\n \n \toptions->orderfile = diff_order_file_cfg;\n \n@@ -3798,6 +3805,10 @@ int diff_opt_parse(struct diff_options *options,\n \t\tDIFF_XDL_SET(options, IGNORE_WHITESPACE_AT_EOL);\n \telse if (!strcmp(arg, \"--ignore-blank-lines\"))\n \t\tDIFF_XDL_SET(options, IGNORE_BLANK_LINES);\n+\telse if (!strcmp(arg, \"--compaction-heuristic\"))\n+\t\tDIFF_XDL_SET(options, COMPACTION_HEURISTIC);\n+\telse if (!strcmp(arg, \"--no-compaction-heuristic\"))\n+\t\tDIFF_XDL_CLR(options, COMPACTION_HEURISTIC);\n \telse if (!strcmp(arg, \"--patience\"))\n \t\toptions->xdl_opts = DIFF_WITH_ALG(options, PATIENCE_DIFF);\n \telse if (!strcmp(arg, \"--histogram\"))\ndiff --git a/xdiff/xdiff.h b/xdiff/xdiff.h\nindex 4fb7e79..7423f77 100644\n--- a/xdiff/xdiff.h\n+++ b/xdiff/xdiff.h\n@@ -41,6 +41,8 @@ extern \"C\" {\n \n #define XDF_IGNORE_BLANK_LINES (1 << 7)\n \n+#define XDF_COMPACTION_HEURISTIC (1 << 8)\n+\n #define XDL_EMIT_FUNCNAMES (1 << 0)\n #define XDL_EMIT_FUNCCONTEXT (1 << 2)\n \ndiff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\nindex 748eeb9..5a02b15 100644\n--- a/xdiff/xdiffi.c\n+++ b/xdiff/xdiffi.c\n@@ -400,6 +400,11 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,\n }\n \n \n+static int is_blank_line(xrecord_t **recs, long ix, long flags)\n+{\n+\treturn xdl_blankline(recs[ix]->ptr, recs[ix]->size, flags);\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@@ -411,6 +416,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 \txrecord_t **recs = xdf->recs;\n \n \t/*\n@@ -444,6 +450,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\tblank_lines = 0;\n \n \t\t\t/*\n \t\t\t * If the line before the current change group, is equal to\n@@ -478,6 +485,8 @@ 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+\n \t\t\t\trchg[ixs++] = 0;\n \t\t\t\trchg[ix++] = 1;\n \n@@ -504,6 +513,23 @@ 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 * blank line in the moving space. If there is a blank line,\n+\t\t * make sure the last blank 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 ((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 recs_match(recs, ixs - 1, ix - 1, flags)) {\n+\t\t\t\trchg[--ixs] = 1;\n+\t\t\t\trchg[--ix] = 0;\n+\t\t\t}\n+\t\t}\n \t}\n \n \treturn 0;\n-- \n2.8.0.26.gba39a1b.dirty\n"},{"id":"283753","messageId":"xmqqbn564noq.fsf@gitster.mtv.corp.google.com","threadId":"42065","inReplyTo":"1461013950-12503-1-git-send-email-sbeller@google.com","subject":"Re: [PATCH 0/2 v4] xdiff: implement empty line chunk heuristic","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-04-18T21:22:29Z","receivedAt":"2016-04-18T21:22:29Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller writes:\n\n>> OK, so perhaps either of you two can do a final version people can\n>> start having fun with?\n>\n> Here we go. I squashed in your patch, although with a minor change:\n>\n> - if ((flags & XDF_SHORTEST_LINE_HEURISTIC)) {\n> + if ((flags & XDF_COMPACTION_HEURISTIC) && blank_lines) {\n>\n> We did not need that in the \"shortest line\" heuristic as we know\n> a line with the shortest line length must exist. We do not know about\n> empty lines though.\n\nMakes sense. The last hunk of\n\n$ git show 9614b8dcf -- update-cache.c\n\ngives an unexpected result without \"&& blank_lines\" above. Lack of\n\"&& blank_lines\" happens to make the result slightly easier to read,\nbut at the cost of having an extra line in the hunk.\n\nThanks.\n"},{"id":"283755","messageId":"CA+P7+xrisA0qqQ01GoSUdNm+O85NN9H7arovzqDD2e5GUv2GAw@mail.gmail.com","threadId":"42065","inReplyTo":"1461013950-12503-3-git-send-email-sbeller@google.com","subject":"Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2016-04-18T22:04:18Z","receivedAt":"2016-04-18T22:04:18Z","isPatch":true,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Mon, Apr 18, 2016 at 2:12 PM, Stefan Beller wrote:\n> In order to produce the smallest possible diff and combine several diff\n> hunks together, we implement a heuristic from GNU Diff which moves diff\n> hunks forward as far as possible when we find common context above and\n> below a diff hunk. This sometimes produces less readable diffs when\n> writing C, Shell, or other programming languages, ie:\n>\n> ...\n> /*\n> + *\n> + *\n> + */\n> +\n> +/*\n> ...\n>\n> instead of the more readable equivalent of\n>\n> ...\n> +/*\n> + *\n> + *\n> + */\n> +\n> /*\n> ...\n>\n> Implement the following heuristic to (optionally) produce the desired\n> output.\n>\n> If there are diff chunks which can be shifted around, shift each hunk\n> such that the last common empty line is below the chunk with the rest\n> of the context above.\n>\n> This heuristic appears to resolve the above example and several other\n> common issues without producing significantly weird results. However, as\n> with any heuristic it is not really known whether this will always be\n> more optimal. Thus, it can be disabled via diff.compactionHeuristic.\n>\n> Signed-off-by: Stefan Beller \n> Signed-off-by: Jacob Keller \n> Signed-off-by: Stefan Beller \n> ---\n\nThanks Stephan and Junio, this looks pretty good. I think before it's\nmerged we'd probably want to implement some sort of attributes which\nallows per-path configuration, incase it needs to be configured at\nall.\n\nI've got it applied to my local git, and I'm going to try to run a\ndiff between enabled vs disabled on a large section of the Linux\nkernel history and a few other projects to see if I spot anything odd.\n\nThanks,\nJake\n"},{"id":"283756","messageId":"xmqq7ffu4ktu.fsf@gitster.mtv.corp.google.com","threadId":"42065","inReplyTo":"CA+P7+xrisA0qqQ01GoSUdNm+O85NN9H7arovzqDD2e5GUv2GAw@mail.gmail.com","subject":"Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-04-18T22:24:13Z","receivedAt":"2016-04-18T22:24:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jacob Keller writes:\n\n> Thanks Stephan and Junio, this looks pretty good. I think before it's\n> merged we'd probably want to implement some sort of attributes which\n> allows per-path configuration, incase it needs to be configured at\n> all.\n\nMy take on it is that we'd want to make sure that the shift with\nblank line heuristics is \"good enough\", i.e. there is no need for\nend-user configuration or attributes, and then remove the tentative\noption, configuration and its documentation, before this is merged.\n\nIf we really want to add knobs to handle different kind of payloads\nin vastly different way, the right place to do so is to add a set of\nbits \"use this and that heuristics\" to userdiff driver, I would say,\nbut in the compaction codepath it does not seem to be enough room to\nhave that many knobs to be tweaked in the first place to me.\n\n> I've got it applied to my local git, and I'm going to try to run a\n> diff between enabled vs disabled on a large section of the Linux\n> kernel history and a few other projects to see if I spot anything odd.\n\nThanks.\n"},{"id":"283761","messageId":"CAGZ79kZXAtLVdQkU=RJqDrFRvCvPTXjANQ=GPja+NRSn57twAQ@mail.gmail.com","threadId":"42065","inReplyTo":"xmqqbn564noq.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 0/2 v4] xdiff: implement empty line chunk heuristic","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-04-18T23:53:43Z","receivedAt":"2016-04-18T23:53:43Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Mon, Apr 18, 2016 at 2:22 PM, Junio C Hamano wrote:\n> Stefan Beller writes:\n>\n>>> OK, so perhaps either of you two can do a final version people can\n>>> start having fun with?\n>>\n>> Here we go. I squashed in your patch, although with a minor change:\n>>\n>> - if ((flags & XDF_SHORTEST_LINE_HEURISTIC)) {\n>> + if ((flags & XDF_COMPACTION_HEURISTIC) && blank_lines) {\n>>\n>> We did not need that in the \"shortest line\" heuristic as we know\n>> a line with the shortest line length must exist. We do not know about\n>> empty lines though.\n>\n> Makes sense. The last hunk of\n>\n> $ git show 9614b8dcf -- update-cache.c\n>\n> gives an unexpected result without \"&& blank_lines\" above. Lack of\n> \"&& blank_lines\" happens to make the result slightly easier to read,\n> but at the cost of having an extra line in the hunk.\n\nSo without the blank_lines check you get (A):\n @@ -271,15 +279,14 @@ int main(int argc, char **argv)\n if (!verify_path(path)) {\n fprintf(stderr, \"Ignoring path %s\\n\", argv[i]);\n continue;\n - }\n - if (add_file_to_cache(path)) {\n - fprintf(stderr, \"Unable to add %s to\ndatabase\\n\", path);\n - goto out;\n }\n + if (add_file_to_cache(path))\n + usage(\"Unable to add %s to database\", path);\n }\n ...\n\nand with the heuristic you get (B):\n\n@@ -272,14 +280,13 @@ int main(int argc, char **argv)\n @@ -272,14 +280,13 @@ int main(int argc, char **argv)\n fprintf(stderr, \"Ignoring path %s\\n\", argv[i]);\n continue;\n }\n - if (add_file_to_cache(path)) {\n - fprintf(stderr, \"Unable to add %s to\ndatabase\\n\", path);\n - goto out;\n - }\n + if (add_file_to_cache(path))\n + usage(\"Unable to add %s to database\", path);\n }\n ...\n\nIn case of (A) the compaction heuristic tries to shift the hunk upwards,\nstopping at the first empty line or when lines miss match.\nAs there is no blank line, it goes until the miss match.\n\nPersonally I'd find it less readable, because the intent was not to remove\n\n - }\n - if (add_file_to_cache(path)) {\n - fprintf(stderr, \"Unable to add %s to\ndatabase\\n\", path);\n - goto out;\n\nbut rather remove\n\n - if (add_file_to_cache(path)) {\n - fprintf(stderr, \"Unable to add %s to\ndatabase\\n\", path);\n - goto out;\n - }\n\nas that is the logic unit I'd think.\n\nAlthough you find this instance easier to read the behavior without the\nblank_lines check would result in\n\n Shift hunk upward as much as possible, stop at the first empty line.\n\nFor hunks without empty line this just becomes\n\n Shift hunk upward as much as possible.\n\nwhich is 50:50 for looking good, so we kept the old behavior as\nthat is just as good.\n\nThanks,\nStefan\n\n\n>\n> Thanks.\n"},{"id":"283765","messageId":"20160419050342.GA19439@sigill.intra.peff.net","threadId":"42065","inReplyTo":"1461013950-12503-3-git-send-email-sbeller@google.com","subject":"Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-04-19T05:03:42Z","receivedAt":"2016-04-19T05:03:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Apr 18, 2016 at 02:12:30PM -0700, Stefan Beller wrote:\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 * blank line in the moving space. If there is a blank line,\n> +\t\t * make sure the last blank line is the end of the group.\n\ns/an/a/ on the first line\n\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\nMaybe because I'm reading it as a diff that only contains this hunk and\nnot the whole rest of the function, but the \"we\" here confused me. You\nmean the earlier, existing loop in xdl_change_compact, right?\n\nMaybe something like:\n\n As we already shifted the group forward as far as possible in the\n earlier loop...\n\nwould help.\n\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 recs_match(recs, ixs - 1, ix - 1, flags)) {\n> +\t\t\t\trchg[--ixs] = 1;\n> +\t\t\t\trchg[--ix] = 0;\n> +\t\t\t}\n> +\t\t}\n\nThis turned out to be delightfully simple (especially compared to the\nperl monstrosity).\n\nI tried comparing the output to the perl one, but it's not quite the\nsame. In that one we had to work with the existing hunks and context\nlines, so any hunk that got shifted ended up with extra context on one\nside, and too little on the other. But here, we can actually bump the\ncontext lines to give the correct amount on both sides, which is good.\n\nI guess this will invalidate old patch-ids, but there's not much to be\ndone about that.\n\n-Peff\n"},{"id":"283768","messageId":"CAGZ79kaD3kyWdbT-PhR9XPV_qmYpQipZwvfYYcVvwk62+x5qnw@mail.gmail.com","threadId":"42065","inReplyTo":"20160419050342.GA19439@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-04-19T06:47:52Z","receivedAt":"2016-04-19T06:47:52Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Mon, Apr 18, 2016 at 10:03 PM, Jeff King wrote:\n> On Mon, Apr 18, 2016 at 02:12:30PM -0700, Stefan Beller wrote:\n>\n>> +\n>> + /*\n>> + * If a group can be moved back and forth, see if there is an\n>> + * blank line in the moving space. If there is a blank line,\n>> + * make sure the last blank line is the end of the group.\n>\n> s/an/a/ on the first line\n\nSo it looks like I'll be resending another version for this series tomorrow.\nThanks for pointing this out!\n\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> Maybe because I'm reading it as a diff that only contains this hunk and\n> not the whole rest of the function, but the \"we\" here confused me. You\n> mean the earlier, existing loop in xdl_change_compact, right?\n>\n> Maybe something like:\n>\n> As we already shifted the group forward as far as possible in the\n> earlier loop...\n>\n> would help.\n\nI'll see to get rid of the 'we', otherwise I'll stick with your suggestion.\n\n>\n>> + if ((flags & XDF_COMPACTION_HEURISTIC) && blank_lines) {\n>> + while (ixs > 0 &&\n>> + !is_blank_line(recs, ix - 1, flags) &&\n>> + recs_match(recs, ixs - 1, ix - 1, flags)) {\n>> + rchg[--ixs] = 1;\n>> + rchg[--ix] = 0;\n>> + }\n>> + }\n>\n> This turned out to be delightfully simple (especially compared to the\n> perl monstrosity).\n>\n> I tried comparing the output to the perl one, but it's not quite the\n> same. In that one we had to work with the existing hunks and context\n> lines, so any hunk that got shifted ended up with extra context on one\n> side, and too little on the other. But here, we can actually bump the\n> context lines to give the correct amount on both sides, which is good.\n>\n> I guess this will invalidate old patch-ids, but there's not much to be\n> done about that.\n\nFor the record:\nI thought about \"optimal hunk separation\" for a while, specially during my\nbike commute. And while this heuristic seems to be a good fit for most of\nthe cases inspected, we can do better (in the future).\n\nI am convinced the better way to do it is like this:\n\n Calculate the entropy for each line and take the last line with the\n lowest entropy as the last line of the hunk.\n\nThat heuristic requires more compute though as it will be hard to compute\nthe entropy for the line. To do that I would imagine, we'd need to loop over\nthe whole file and count the occurrences for each char (byte) and then\ntake the negative log of (#number of that byte / #number of bytes in file) [1].\n\nThis would model our actual goal a bit more closely to split at parts, where\nthere is low information density (the definition of entropy).\n\nOne example Jacob pointed out was a thing like\n\n/**\n * Comment here. Over\n * more lines.\n *\n+ * Add line here with a blank line\n+ *\n+ * in between and a trailing blank after.\n+ *\n */\n\nI think we had cases like this in the kernel tree and else where,\nand for a human it is clear to break after the last \"empty line\"\n(which for comments starts with \" * \"). To detect those we can use\nthe entropy as it doesn't convey lots of information.\n(git show e1f7037167323461c0415447676262dcb)\n\nIt also keeps the false positives out, Jacob pointed at\n85ed2f32064b82e541fc7dcf2b0049a05 IIRC, which was bad with\nthe shortest lines only, but I'd imagine the entropy based\nheuristic will do better there.\n\n[1] https://en.wikipedia.org/wiki/Entropy_(information_theory)\n\nThanks for the review,\nStefan\n\n>\n> -Peff\n"},{"id":"283769","messageId":"20160419070001.GA21875@sigill.intra.peff.net","threadId":"42065","inReplyTo":"CAGZ79kaD3kyWdbT-PhR9XPV_qmYpQipZwvfYYcVvwk62+x5qnw@mail.gmail.com","subject":"Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-04-19T07:00:01Z","receivedAt":"2016-04-19T07:00:01Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Apr 18, 2016 at 11:47:52PM -0700, Stefan Beller wrote:\n\n> I am convinced the better way to do it is like this:\n> \n> Calculate the entropy for each line and take the last line with the\n> lowest entropy as the last line of the hunk.\n\nI'll be curious to see the results, but I think sometimes predictable\nand stupid may be the best route with these sorts of things. In\nparticular, I'd worry that a content-independent measure of entropy\nmight miss some subtleties of a particular language (e.g., that \"*\" is\nmore or less meaningful than some other character). But we'll see. :)\n\n-Peff\n"},{"id":"283770","messageId":"CAGZ79kaJxgMCUSp3dVJt4=nPVi=p_HFY+OATh1wXthdKKGpmjA@mail.gmail.com","threadId":"42065","inReplyTo":"20160419070001.GA21875@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-04-19T07:05:56Z","receivedAt":"2016-04-19T07:05:56Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Tue, Apr 19, 2016 at 12:00 AM, Jeff King wrote:\n> On Mon, Apr 18, 2016 at 11:47:52PM -0700, Stefan Beller wrote:\n>\n>> I am convinced the better way to do it is like this:\n>>\n>> Calculate the entropy for each line and take the last line with the\n>> lowest entropy as the last line of the hunk.\n>\n> I'll be curious to see the results, but I think sometimes predictable\n> and stupid may be the best route with these sorts of things. In\n> particular, I'd worry that a content-independent measure of entropy\n> might miss some subtleties of a particular language (e.g., that \"*\" is\n> more or less meaningful than some other character). But we'll see. :)\n\nI would assume that the \"*\" would have little entropy when there are lots\nof comments, i.e. it just \"feels\" like an empty line.\nIf there are no \"*\", then the entropy is high as it is unusual. And\nunusual things\nshould not be at the border of a hunk I would assume.\nSo m prediction is that the 'subtleties of a particular language' correlate\nhighly with the actual use of characters.\n\nAnyway, the experiment can be carried out later. :)\n\nThanks,\nStefan\n\n>\n> -Peff\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n"},{"id":"283796","messageId":"CAGZ79kbzg7SmJHFpxeJNKmLaEEw+irCxUedo45jGx8G8fmPtKg@mail.gmail.com","threadId":"42065","inReplyTo":"20160419050342.GA19439@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-04-19T15:17:38Z","receivedAt":"2016-04-19T15:17:38Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Mon, Apr 18, 2016 at 10:03 PM, Jeff King wrote:\n\n> I guess this will invalidate old patch-ids, but there's not much to be\n> done about that.\n\nWhat do you mean by that? (What consequences do you imagine?)\nI think diffs with any kind of heuristic can still be applied, no?\n\nThanks,\nStefan\n\n>\n> -Peff\n"},{"id":"283803","messageId":"xmqqbn5535l5.fsf@gitster.mtv.corp.google.com","threadId":"42065","inReplyTo":"20160419050342.GA19439@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-04-19T16:51:02Z","receivedAt":"2016-04-19T16:51:02Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> I guess this will invalidate old patch-ids, but there's not much to be\n> done about that.\n\nIf we really cared, we could disable this (and any future) change to\nthe compaction logic to \"patch-id --[un]stable\" option.\n\nI am not sure if it is worth the effort, though ;-)\n"},{"id":"283806","messageId":"20160419170624.GA3999@sigill.intra.peff.net","threadId":"42065","inReplyTo":"CAGZ79kbzg7SmJHFpxeJNKmLaEEw+irCxUedo45jGx8G8fmPtKg@mail.gmail.com","subject":"Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-04-19T17:06:25Z","receivedAt":"2016-04-19T17:06:25Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Apr 19, 2016 at 08:17:38AM -0700, Stefan Beller wrote:\n\n> On Mon, Apr 18, 2016 at 10:03 PM, Jeff King wrote:\n> \n> > I guess this will invalidate old patch-ids, but there's not much to be\n> > done about that.\n> \n> What do you mean by that? (What consequences do you imagine?)\n> I think diffs with any kind of heuristic can still be applied, no?\n\nI mean that if you save any old patch-ids from \"git patch-id\", they\nwon't match up when compared with new versions of git. We can probably\nignore it, though. This isn't the first time that patch-ids might have\nchanged, and I think the advice is already that one should not count on\nthem to be stable in the long term.\n\n-Peff\n"},{"id":"283871","messageId":"CA+P7+xp60r6Tsv0_=Qy6Wo39MmXMbCba7g5goPQD-e8FNaaEjw@mail.gmail.com","threadId":"42065","inReplyTo":"20160419170624.GA3999@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2016-04-19T23:02:55Z","receivedAt":"2016-04-19T23:02:55Z","isPatch":true,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Tue, Apr 19, 2016 at 10:06 AM, Jeff King wrote:\n> On Tue, Apr 19, 2016 at 08:17:38AM -0700, Stefan Beller wrote:\n>\n>> On Mon, Apr 18, 2016 at 10:03 PM, Jeff King wrote:\n>>\n>> > I guess this will invalidate old patch-ids, but there's not much to be\n>> > done about that.\n>>\n>> What do you mean by that? (What consequences do you imagine?)\n>> I think diffs with any kind of heuristic can still be applied, no?\n>\n> I mean that if you save any old patch-ids from \"git patch-id\", they\n> won't match up when compared with new versions of git. We can probably\n> ignore it, though. This isn't the first time that patch-ids might have\n> changed, and I think the advice is already that one should not count on\n> them to be stable in the long term.\n>\n> -Peff\n\nPlus they'll be stable within a version of Git, it's only recorded\npatch ids that change, which hopefully isn't done very much if at all.\n\nThanks,\nJake\n"},{"id":"283872","messageId":"xmqqoa95xknc.fsf@gitster.mtv.corp.google.com","threadId":"42065","inReplyTo":"CA+P7+xp60r6Tsv0_=Qy6Wo39MmXMbCba7g5goPQD-e8FNaaEjw@mail.gmail.com","subject":"Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-04-19T23:07:35Z","receivedAt":"2016-04-19T23:07:35Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jacob Keller writes:\n\n> On Tue, Apr 19, 2016 at 10:06 AM, Jeff King wrote:\n>> On Tue, Apr 19, 2016 at 08:17:38AM -0700, Stefan Beller wrote:\n>>\n>>> On Mon, Apr 18, 2016 at 10:03 PM, Jeff King wrote:\n>>>\n>>> > I guess this will invalidate old patch-ids, but there's not much to be\n>>> > done about that.\n>>>\n>>> What do you mean by that? (What consequences do you imagine?)\n>>> I think diffs with any kind of heuristic can still be applied, no?\n>>\n>> I mean that if you save any old patch-ids from \"git patch-id\", they\n>> won't match up when compared with new versions of git. We can probably\n>> ignore it, though. This isn't the first time that patch-ids might have\n>> changed, and I think the advice is already that one should not count on\n>> them to be stable in the long term.\n>>\n>> -Peff\n>\n> Plus they'll be stable within a version of Git, it's only recorded\n> patch ids that change, which hopefully isn't done very much if at all.\n>\n> Thanks,\n> Jake\n\nSome people, like those who did things like 30e12b92 (patch-id: make\nit stable against hunk reordering, 2014-04-27), _may_ care.\n"},{"id":"283906","messageId":"xmqqfuugyg3y.fsf@gitster.mtv.corp.google.com","threadId":"42065","inReplyTo":"20160419170624.GA3999@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-04-20T06:00:17Z","receivedAt":"2016-04-20T06:00:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> I mean that if you save any old patch-ids from \"git patch-id\", they\n> won't match up when compared with new versions of git. We can probably\n> ignore it, though. This isn't the first time that patch-ids might have\n> changed, and I think the advice is already that one should not count on\n> them to be stable in the long term.\n\nAnother thing that this *will* break is the patch signature upload\nprotocol k.org uses to allow Linus, Greg, et al. on the road with\nlimited hotel wifi bandwidth to prepare patch-X-test1.gz and\npatch-X-test1.sign file. They can locally tag X-test1, prepare\n\"git diff X X-test1 | gzip -n >patch-X-test1.gz\" and sign the\nresult, and upload _only_ the detached signature after pushing.\n\nThey can tell k.org, when uploading the detached signature, to\nrecreate the patchfile by running the same \"git diff\" to save the\nbandwidth of sending the same thing twice (as they have to \"push\"\nanyway, having to send the generated patch is a pure overhead).\n\nHaving said all that, kup(1) users are already warned that the\ntextual diff produced by \"git diff-tree -p\" (which is mentioned in\nthe documentation of the tool) varies across versions of Git and\nthe above \"optimization\" would not work unless both ends have the\nsame version of Git, so it may not be too big an issue for them.\nThey have already been burned once when we corrected \"git archive\"\noutput in the past (they obviously have the same optimization to\nsign tarballs, and the kup(1) mechanism relies to have byte-for-byte\nidentical output).\n"},{"id":"283932","messageId":"20160420161028-mutt-send-email-mst@redhat.com","threadId":"42065","inReplyTo":"xmqqoa95xknc.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic","fromName":"Michael S. Tsirkin","fromEmail":"mst@redhat.com","sentAt":"2016-04-20T13:12:08Z","receivedAt":"2016-04-20T13:12:08Z","isPatch":true,"sender":{"key":"mst@kernel.org","avatar":null},"body":"On Tue, Apr 19, 2016 at 04:07:35PM -0700, Junio C Hamano wrote:\n> Jacob Keller writes:\n> \n> > On Tue, Apr 19, 2016 at 10:06 AM, Jeff King wrote:\n> >> On Tue, Apr 19, 2016 at 08:17:38AM -0700, Stefan Beller wrote:\n> >>\n> >>> On Mon, Apr 18, 2016 at 10:03 PM, Jeff King wrote:\n> >>>\n> >>> > I guess this will invalidate old patch-ids, but there's not much to be\n> >>> > done about that.\n> >>>\n> >>> What do you mean by that? (What consequences do you imagine?)\n> >>> I think diffs with any kind of heuristic can still be applied, no?\n> >>\n> >> I mean that if you save any old patch-ids from \"git patch-id\", they\n> >> won't match up when compared with new versions of git. We can probably\n> >> ignore it, though. This isn't the first time that patch-ids might have\n> >> changed, and I think the advice is already that one should not count on\n> >> them to be stable in the long term.\n> >>\n> >> -Peff\n> >\n> > Plus they'll be stable within a version of Git, it's only recorded\n> > patch ids that change, which hopefully isn't done very much if at all.\n> >\n> > Thanks,\n> > Jake\n> \n> Some people, like those who did things like 30e12b92 (patch-id: make\n> it stable against hunk reordering, 2014-04-27), _may_ care.\n> \n\nFWIW IIRC what that commit is about is ability to reorder the chunks in\na patch without changing patch-id. Not about keeping id stable across\ngit revisions.\n\n-- \nMST\n"},{"id":"283958","messageId":"xmqqpotkw9bi.fsf@gitster.mtv.corp.google.com","threadId":"42065","inReplyTo":"20160420161028-mutt-send-email-mst@redhat.com","subject":"Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-04-20T16:09:53Z","receivedAt":"2016-04-20T16:09:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Michael S. Tsirkin\" writes:\n\n> FWIW IIRC what that commit is about is ability to reorder the chunks in\n> a patch without changing patch-id. Not about keeping id stable across\n> git revisions.\n\nOK, but \"reorder the chunks\" is not meant to stay to be the _ONLY_\npurpose for an option whose name is a broad \"--[un]stable\", but\nmerely one (and only) possible cause of patch-id instability that\nhappened to be noticed as an issue back then and was dealt with that\ncommit, no? In other words, the intent of the \"--stable\" feature is\nto give a stable ID that is not affected by random end-user settings\n(e.g. diff.orderfile) and if somebody invents a new configurable knob\nin the future, they are supposed to pay attention to the \"--stable\"\nfeature or existing users who do use \"--stable\" will be broken, no?\n\nI can still buy \"--stable is not about stability across versions of\nGit\"--it makes our job easier ;-) I just want to make sure that\n\"--stable is about stability inside a single version of Git that\npatch ID for the same commit will stay the same and unaffected by\nrandom end-user configuration knobs\".\n\nWhich in turn would mean that we won't have to worry about this\noption in patch-id as long as we remove the diff.compactionheuristic\nconfiguration and command line option once the developers are done\nexperimenting with their heuristics code.\n"},{"id":"283961","messageId":"20160420161716.GA11459@sigill.intra.peff.net","threadId":"42065","inReplyTo":"xmqqpotkw9bi.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-04-20T16:17:17Z","receivedAt":"2016-04-20T16:17:17Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Apr 20, 2016 at 09:09:53AM -0700, Junio C Hamano wrote:\n\n> \"Michael S. Tsirkin\" writes:\n> \n> > FWIW IIRC what that commit is about is ability to reorder the chunks in\n> > a patch without changing patch-id. Not about keeping id stable across\n> > git revisions.\n> \n> OK, but \"reorder the chunks\" is not meant to stay to be the _ONLY_\n> purpose for an option whose name is a broad \"--[un]stable\", but\n> merely one (and only) possible cause of patch-id instability that\n> happened to be noticed as an issue back then and was dealt with that\n> commit, no? In other words, the intent of the \"--stable\" feature is\n> to give a stable ID that is not affected by random end-user settings\n> (e.g. diff.orderfile) and if somebody invents a new configurable knob\n> in the future, they are supposed to pay attention to the \"--stable\"\n> feature or existing users who do use \"--stable\" will be broken, no?\n\nI forgot that we added \"--stable\". Evne if it is not meant to be about\nstability across versions, is there any reason _not_ to turn off\nthis heuristic for --stable (or for patch-ids in general)?\n\nI guess maybe that creates some inconsistency between generating a\npatch-id directly, and making one from a diff given on stdin (though I\ndon't know that we can promise much about the latter in the general\ncase; we can fix file ordering, but we don't have enough information to\ntweak other aspects).\n\n-Peff\n"}]}