{"thread":{"id":"42042","subject":"[PATCH 1/2] xdiff: add recs_match helper function","startedAt":"2016-04-15T23:01:44Z","lastAt":"2016-04-18T19:33:39Z","messageCount":11,"participants":["Stefan Beller","Jacob Keller","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"283618","messageId":"1460761306-18794-1-git-send-email-sbeller@google.com","threadId":"42042","inReplyTo":null,"subject":"[RFC PATCH, WAS: \"weird diff output?\" v3a 0/2] implement shortest line diff chunk heuristic","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-04-15T23:01:44Z","receivedAt":"2016-04-15T23:01:44Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"This is a version based on Jacobs v2, with the same fixes as in his v3 (hopefully),\nchanging the heuristic, such that CRLF confusion might be gone.\n\nTODO:\n* add some tests\n* think about whether we need a git attribute or not (I did some\n  thinking, and if we do need to configure this at all, this is where I\n  would put it)\n  \nLater on we want to have git attributes I'd think. For now let's just keep\nthe `git config diff.shortestlineheuristic true` config option for testing?\n  \nChanges since Jacobs v2:\n * s/empty line/shortest line/g\n   That new heuristic is a superset of the empty line heuristic as empty lines\n   are shortest lines.  This solves the \"What is an empty line?\" question\n   (Think of CRLF vs LF)\n * fixed Jacobs rebase mistake (which is also fixed in Jacobs v3)\n\nChanges since my v1:\n* rename xdl_hash_and_recmatch to recs_match\n* remove counting empty lines in the first section of the looping\n\nChanges since Stefan's v1:\n* Added a patch to implement xdl_hash_and_recmatch as Junio suggested.\n* Fixed a segfault in Stefan's patch\n* Added XDL flag to configure the behavior\n* Used an int and counted empty lines via += instead of |=\n* Renamed starts_with_emptyline to is_emptyline\n* Added diff command line and config options\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  |  6 ++++++\n Documentation/diff-options.txt |  6 ++++++\n diff.c                         | 11 +++++++++++\n xdiff/xdiff.h                  |  2 ++\n xdiff/xdiffi.c                 | 43 ++++++++++++++++++++++++++++++++++++++----\n 5 files changed, 64 insertions(+), 4 deletions(-)\n\n-- \n2.8.1.189.gd13d43c\n"},{"id":"283617","messageId":"1460761306-18794-2-git-send-email-sbeller@google.com","threadId":"42042","inReplyTo":"1460761306-18794-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-15T23:01:45Z","receivedAt":"2016-04-15T23:01:45Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"From: Jacob Keller <jacob.keller@gmail.com>\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 <jacob.e.keller@intel.com>\nSigned-off-by: Stefan Beller <sbeller@google.com>\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.1.189.gd13d43c\n"},{"id":"283619","messageId":"1460761306-18794-3-git-send-email-sbeller@google.com","threadId":"42042","inReplyTo":"1460761306-18794-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-15T23:01:46Z","receivedAt":"2016-04-15T23:01:46Z","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\nOriginal discussion and testing found the following heuristic to be\nproducing the desired 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\nThis heuristic appears to resolve the above example and several other\ncommon issues without producing significantly weird results. When\nimplementing this heuristic the handling of empty lines was awkward as\nit is unclear what an empty line is. ('\\n' or do we include \"\\r\\n\" as it\nis common on Windows?) Instead we implement a slightly different heuristic:\n\n  If there are diff chunks which can be shifted around, find the shortest\n  line in the overlapping parts. Use the line with the shortest length that\n  occurs last as the last line of the chunk with the rest\n  of the context above.\n\nHowever, as with any heuristic it is not really known whether this will\nalways be more optimal. Thus, leave the heuristic disabled by default.\n\nAdd an XDIFF flag to enable this heuristic only conditionally. Add\na diff command line option and diff configuration option to allow users\nto enable this option when desired.\n\nTODO:\n* Add tests\n* Add better/more documentation explaining the heuristic, possibly with\n  examples(?)\n* better name(?)\n\nSigned-off-by: Stefan Beller <sbeller@google.com>\nSigned-off-by: Jacob Keller <jacob.e.keller@intel.com>\nSigned-off-by: Stefan Beller <sbeller@google.com>\n---\n Documentation/diff-config.txt  |  6 ++++++\n Documentation/diff-options.txt |  6 ++++++\n diff.c                         | 11 +++++++++++\n xdiff/xdiff.h                  |  2 ++\n xdiff/xdiffi.c                 | 29 +++++++++++++++++++++++++++++\n 5 files changed, 54 insertions(+)\n\ndiff --git a/Documentation/diff-config.txt b/Documentation/diff-config.txt\nindex edba565..3d99a90 100644\n--- a/Documentation/diff-config.txt\n+++ b/Documentation/diff-config.txt\n@@ -170,6 +170,12 @@ diff.tool::\n \n include::mergetools-diff.txt[]\n \n+diff.shortestLineHeuristic::\n+\tSet this option to true to enable the shortest line chunk heuristic when\n+\tproducing diff output. This heuristic will attempt to shift hunks such\n+\tthat the last shortest common line occurs below the hunk with the rest of\n+\tthe context above it.\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..b1ca83d 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+--shortest-line-heuristic::\n+--no-shortest-line-heuristic::\n+\tWhen possible, shift common shortest line in diff hunks below the hunk\n+\tsuch that the last common shortest line for each hunk is below, with the\n+\trest of the context above the hunk.\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..a02aff9 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_shortest_line_heuristic = 0;\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.shortestlineheuristic\")) {\n+\t\tdiff_shortest_line_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_shortest_line_heuristic)\n+\t\tDIFF_XDL_SET(options, SHORTEST_LINE_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, \"--shortest-line-heuristic\"))\n+\t\tDIFF_XDL_SET(options, SHORTEST_LINE_HEURISTIC);\n+\telse if (!strcmp(arg, \"--no-shortest-line-heuristic\"))\n+\t\tDIFF_XDL_CLR(options, SHORTEST_LINE_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..e1f8ec0 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_SHORTEST_LINE_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..7d15b26 100644\n--- a/xdiff/xdiffi.c\n+++ b/xdiff/xdiffi.c\n@@ -400,6 +400,12 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,\n }\n \n \n+static int line_length(const char *recs)\n+{\n+\tchar *s = strchr(recs, '\\n');\n+\treturn s ? s - recs : strlen(recs);\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 +417,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 shortest_line;\n \txrecord_t **recs = xdf->recs;\n \n \t/*\n@@ -444,6 +451,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\tshortest_line = UINT_MAX;\n \n \t\t\t/*\n \t\t\t * If the line before the current change group, is equal to\n@@ -478,6 +486,10 @@ 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\tint l = line_length(recs[ix]->ptr);\n+\t\t\t\tif (l < shortest_line)\n+\t\t\t\t\tshortest_line = l;\n+\n \t\t\t\trchg[ixs++] = 0;\n \t\t\t\trchg[ix++] = 1;\n \n@@ -504,6 +516,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 * empty line in the moving space. If there is an empty line,\n+\t\t * make sure the last empty line is the end of the group.\n+\t\t *\n+\t\t * As we shifted the group forward as far as possible, we only\n+\t\t * need to shift it back if at all.\n+\t\t */\n+\t\tif ((flags & XDF_SHORTEST_LINE_HEURISTIC)) {\n+\t\t\twhile (ixs > 0 &&\n+\t\t\t       line_length(recs[ix - 1]->ptr) > shortest_line &&\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.1.189.gd13d43c\n"},{"id":"283620","messageId":"CA+P7+xq-njse8TKWExwKWx=6ynVNwM1ODHnTij6pdQNejvKT=g@mail.gmail.com","threadId":"42042","inReplyTo":"1460761306-18794-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-15T23:05:30Z","receivedAt":"2016-04-15T23:05:30Z","isPatch":true,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Fri, Apr 15, 2016 at 4:01 PM, Stefan Beller <sbeller@google.com> 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> Original discussion and testing found the following heuristic to be\n> producing the desired 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. When\n> implementing this heuristic the handling of empty lines was awkward as\n> it is unclear what an empty line is. ('\\n' or do we include \"\\r\\n\" as it\n> is common on Windows?) Instead we implement a slightly different heuristic:\n>\n>   If there are diff chunks which can be shifted around, find the shortest\n>   line in the overlapping parts. Use the line with the shortest length that\n>   occurs last as the last line of the chunk with the rest\n>   of the context above.\n>\n> However, as with any heuristic it is not really known whether this will\n> always be more optimal. Thus, leave the heuristic disabled by default.\n>\n> Add an XDIFF flag to enable this heuristic only conditionally. Add\n> a diff command line option and diff configuration option to allow users\n> to enable this option when desired.\n>\n> TODO:\n> * Add tests\n> * Add better/more documentation explaining the heuristic, possibly with\n>   examples(?)\n> * better name(?)\n>\n\nThere's a few places that will need cleaning up (comments and such)\nthat mention empty line still, but that's not surprising. I am going\nto test this for a bit on my local repos, and see if it makes any\ndifference to the old heuristic as well.\n\nThanks,\nJake\n\n> Signed-off-by: Stefan Beller <sbeller@google.com>\n> Signed-off-by: Jacob Keller <jacob.e.keller@intel.com>\n> Signed-off-by: Stefan Beller <sbeller@google.com>\n> ---\n>  Documentation/diff-config.txt  |  6 ++++++\n>  Documentation/diff-options.txt |  6 ++++++\n>  diff.c                         | 11 +++++++++++\n>  xdiff/xdiff.h                  |  2 ++\n>  xdiff/xdiffi.c                 | 29 +++++++++++++++++++++++++++++\n>  5 files changed, 54 insertions(+)\n>\n> diff --git a/Documentation/diff-config.txt b/Documentation/diff-config.txt\n> index edba565..3d99a90 100644\n> --- a/Documentation/diff-config.txt\n> +++ b/Documentation/diff-config.txt\n> @@ -170,6 +170,12 @@ diff.tool::\n>\n>  include::mergetools-diff.txt[]\n>\n> +diff.shortestLineHeuristic::\n> +       Set this option to true to enable the shortest line chunk heuristic when\n> +       producing diff output. This heuristic will attempt to shift hunks such\n> +       that the last shortest common line occurs below the hunk with the rest of\n> +       the context above it.\n> +\n>  diff.algorithm::\n>         Choose a diff algorithm.  The variants are as follows:\n>  +\n> diff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\n> index 4b0318e..b1ca83d 100644\n> --- a/Documentation/diff-options.txt\n> +++ b/Documentation/diff-options.txt\n> @@ -63,6 +63,12 @@ ifndef::git-format-patch[]\n>         Synonym for `-p --raw`.\n>  endif::git-format-patch[]\n>\n> +--shortest-line-heuristic::\n> +--no-shortest-line-heuristic::\n> +       When possible, shift common shortest line in diff hunks below the hunk\n> +       such that the last common shortest line for each hunk is below, with the\n> +       rest of the context above the hunk.\n> +\n>  --minimal::\n>         Spend extra time to make sure the smallest possible\n>         diff is produced.\n> diff --git a/diff.c b/diff.c\n> index 4dfe660..a02aff9 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_shortest_line_heuristic = 0;\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>                 diff_detect_rename_default = git_config_rename(var, value);\n>                 return 0;\n>         }\n> +       if (!strcmp(var, \"diff.shortestlineheuristic\")) {\n> +               diff_shortest_line_heuristic = git_config_bool(var, value);\n> +               return 0;\n> +       }\n>         if (!strcmp(var, \"diff.autorefreshindex\")) {\n>                 diff_auto_refresh_index = git_config_bool(var, value);\n>                 return 0;\n> @@ -3278,6 +3283,8 @@ void diff_setup(struct diff_options *options)\n>         options->use_color = diff_use_color_default;\n>         options->detect_rename = diff_detect_rename_default;\n>         options->xdl_opts |= diff_algorithm;\n> +       if (diff_shortest_line_heuristic)\n> +               DIFF_XDL_SET(options, SHORTEST_LINE_HEURISTIC);\n>\n>         options->orderfile = diff_order_file_cfg;\n>\n> @@ -3798,6 +3805,10 @@ int diff_opt_parse(struct diff_options *options,\n>                 DIFF_XDL_SET(options, IGNORE_WHITESPACE_AT_EOL);\n>         else if (!strcmp(arg, \"--ignore-blank-lines\"))\n>                 DIFF_XDL_SET(options, IGNORE_BLANK_LINES);\n> +       else if (!strcmp(arg, \"--shortest-line-heuristic\"))\n> +               DIFF_XDL_SET(options, SHORTEST_LINE_HEURISTIC);\n> +       else if (!strcmp(arg, \"--no-shortest-line-heuristic\"))\n> +               DIFF_XDL_CLR(options, SHORTEST_LINE_HEURISTIC);\n>         else if (!strcmp(arg, \"--patience\"))\n>                 options->xdl_opts = DIFF_WITH_ALG(options, PATIENCE_DIFF);\n>         else if (!strcmp(arg, \"--histogram\"))\n> diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h\n> index 4fb7e79..e1f8ec0 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_SHORTEST_LINE_HEURISTIC (1 << 8)\n> +\n>  #define XDL_EMIT_FUNCNAMES (1 << 0)\n>  #define XDL_EMIT_FUNCCONTEXT (1 << 2)\n>\n> diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\n> index 748eeb9..7d15b26 100644\n> --- a/xdiff/xdiffi.c\n> +++ b/xdiff/xdiffi.c\n> @@ -400,6 +400,12 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,\n>  }\n>\n>\n> +static int line_length(const char *recs)\n> +{\n> +       char *s = strchr(recs, '\\n');\n> +       return s ? s - recs : strlen(recs);\n> +}\n> +\n>  static int recs_match(xrecord_t **recs, long ixs, long ix, long flags)\n>  {\n>         return (recs[ixs]->ha == recs[ix]->ha &&\n> @@ -411,6 +417,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>         long ix, ixo, ixs, ixref, grpsiz, nrec = xdf->nrec;\n>         char *rchg = xdf->rchg, *rchgo = xdfo->rchg;\n> +       unsigned int shortest_line;\n>         xrecord_t **recs = xdf->recs;\n>\n>         /*\n> @@ -444,6 +451,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n>\n>                 do {\n>                         grpsiz = ix - ixs;\n> +                       shortest_line = UINT_MAX;\n>\n>                         /*\n>                          * If the line before the current change group, is equal to\n> @@ -478,6 +486,10 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n>                          * the group.\n>                          */\n>                         while (ix < nrec && recs_match(recs, ixs, ix, flags)) {\n> +                               int l = line_length(recs[ix]->ptr);\n> +                               if (l < shortest_line)\n> +                                       shortest_line = l;\n> +\n>                                 rchg[ixs++] = 0;\n>                                 rchg[ix++] = 1;\n>\n> @@ -504,6 +516,23 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n>                         rchg[--ix] = 0;\n>                         while (rchgo[--ixo]);\n>                 }\n> +\n> +               /*\n> +                * If a group can be moved back and forth, see if there is an\n> +                * empty line in the moving space. If there is an empty line,\n> +                * make sure the last empty line is the end of the group.\n> +                *\n> +                * As we shifted the group forward as far as possible, we only\n> +                * need to shift it back if at all.\n> +                */\n> +               if ((flags & XDF_SHORTEST_LINE_HEURISTIC)) {\n> +                       while (ixs > 0 &&\n> +                              line_length(recs[ix - 1]->ptr) > shortest_line &&\n> +                              recs_match(recs, ixs - 1, ix - 1, flags)) {\n> +                               rchg[--ixs] = 1;\n> +                               rchg[--ix] = 0;\n> +                       }\n> +               }\n>         }\n>\n>         return 0;\n> --\n> 2.8.1.189.gd13d43c\n>\n"},{"id":"283621","messageId":"CA+P7+xoMVzYwWv3=7hTUM7gMjm4i7Vv74aoyw17T_CbToZTVaA@mail.gmail.com","threadId":"42042","inReplyTo":"CA+P7+xq-njse8TKWExwKWx=6ynVNwM1ODHnTij6pdQNejvKT=g@mail.gmail.com","subject":"Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2016-04-15T23:32:30Z","receivedAt":"2016-04-15T23:32:30Z","isPatch":true,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Fri, Apr 15, 2016 at 4:05 PM, Jacob Keller <jacob.keller@gmail.com> wrote:\n> There's a few places that will need cleaning up (comments and such)\n> that mention empty line still, but that's not surprising. I am going\n> to test this for a bit on my local repos, and see if it makes any\n> difference to the old heuristic as well.\n>\n> Thanks,\n> Jake\n>\n\nI ran this heuristic on git.git and it produces tons of false positive\ntransforms which are much lease readable (to me at least), far more\nthan those produced by the newline/blank link heuristic did.\n\nI think we should stick with the empty line heuristic instead of this\nversion, even if it's easier to implement this version.\n\nWe still would need to figure out how to handle CRLF properly but it's\nworth resolving that than this heuristic is.\n\nThanks,\nJake\n"},{"id":"283622","messageId":"CAGZ79kbja85_wMVZwy9i--8F0e=iboaZuOjgbhMmF+8xuks7mA@mail.gmail.com","threadId":"42042","inReplyTo":"CA+P7+xoMVzYwWv3=7hTUM7gMjm4i7Vv74aoyw17T_CbToZTVaA@mail.gmail.com","subject":"Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-04-15T23:45:03Z","receivedAt":"2016-04-15T23:45:03Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Fri, Apr 15, 2016 at 4:32 PM, Jacob Keller <jacob.keller@gmail.com> wrote:\n> On Fri, Apr 15, 2016 at 4:05 PM, Jacob Keller <jacob.keller@gmail.com> wrote:\n>> There's a few places that will need cleaning up (comments and such)\n>> that mention empty line still, but that's not surprising. I am going\n>> to test this for a bit on my local repos, and see if it makes any\n>> difference to the old heuristic as well.\n>>\n>> Thanks,\n>> Jake\n>>\n>\n> I ran this heuristic on git.git and it produces tons of false positive\n> transforms which are much lease readable (to me at least), far more\n> than those produced by the newline/blank link heuristic did.\n>\n> I think we should stick with the empty line heuristic instead of this\n> version, even if it's easier to implement this version.\n\nI agree. The heuristic is worse as we often have these 50:50 chances\nof messing stuff up.\n\n>\n> We still would need to figure out how to handle CRLF properly but it's\n> worth resolving that than this heuristic is.\n>\n> Thanks,\n> Jake\n"},{"id":"283631","messageId":"xmqqd1pq74ys.fsf@gitster.mtv.corp.google.com","threadId":"42042","inReplyTo":"1460761306-18794-3-git-send-email-sbeller@google.com","subject":"Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-04-16T00:49:31Z","receivedAt":"2016-04-16T00:49:31Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller <sbeller@google.com> writes:\n\n> +static int line_length(const char *recs)\n> +{\n> +\tchar *s = strchr(recs, '\\n');\n> +\treturn s ? s - recs : strlen(recs);\n> +}\n\nIt seems that you guys are discarding this \"number of bytes on a\nline, no matter what these bytes are\" idea, so this may be moot, but\nis there a guarantee that reading through recs until you happen to\nsee a NUL is safe?\n\nShouldn't the code that accesses a \"line\" be using the same \"from\nhere to there\", i.e. recs[]->ptr, recs[]->size, interface to avoid\nhaving to scan the underlying string in an unbounded way?\n"},{"id":"283636","messageId":"CAGZ79kY2u_X2xmm=+wvA13bnD57+o1br7vhAL0-Rf6K_1PeXTA@mail.gmail.com","threadId":"42042","inReplyTo":"xmqqd1pq74ys.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-04-16T00:59:34Z","receivedAt":"2016-04-16T00:59:34Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Fri, Apr 15, 2016 at 5:49 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> Stefan Beller <sbeller@google.com> writes:\n>\n>> +static int line_length(const char *recs)\n>> +{\n>> +     char *s = strchr(recs, '\\n');\n>> +     return s ? s - recs : strlen(recs);\n>> +}\n>\n> It seems that you guys are discarding this \"number of bytes on a\n> line, no matter what these bytes are\" idea, so this may be moot, but\n> is there a guarantee that reading through recs until you happen to\n> see a NUL is safe?\n\nWe discarded this idea as it produces to many errors.\n(We'd be back at the 50:50 case, \"is it really worth it?\")\n\nWe will go back to the \"empty line\" heuristic, which will be solved\nvia xdl_blankline(rec[i]->ptr, rec[i]->size, flags); which could be inlined.\nThat will solve the CRLF issue as a CR is covered as a whitespace\n(with CRLF you'd have to specify diff to ignore white spaces).\n\nFor the safety I assumed\n* there is always a \\n even on the last line by convention.\n* in case it is not, the string is null terminated, hence\n  strchr and strlen for the rescue.\n\n>\n> Shouldn't the code that accesses a \"line\" be using the same \"from\n> here to there\", i.e. recs[]->ptr, recs[]->size, interface to avoid\n> having to scan the underlying string in an unbounded way?\n\nxdl_blankline will use ->size, so we'll be holding it right.\n\nThanks,\nStefan\n\n>\n>\n"},{"id":"283637","messageId":"CA+P7+xq_Uei_ybEjJ=PPWtruk5uB5Dp2KajA=5G6TSWU0_g2kw@mail.gmail.com","threadId":"42042","inReplyTo":"xmqqd1pq74ys.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2016-04-16T01:07:54Z","receivedAt":"2016-04-16T01:07:54Z","isPatch":true,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Fri, Apr 15, 2016 at 5:49 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> Stefan Beller <sbeller@google.com> writes:\n>\n>> +static int line_length(const char *recs)\n>> +{\n>> +     char *s = strchr(recs, '\\n');\n>> +     return s ? s - recs : strlen(recs);\n>> +}\n>\n> It seems that you guys are discarding this \"number of bytes on a\n> line, no matter what these bytes are\" idea, so this may be moot, but\n> is there a guarantee that reading through recs until you happen to\n> see a NUL is safe?\n>\n> Shouldn't the code that accesses a \"line\" be using the same \"from\n> here to there\", i.e. recs[]->ptr, recs[]->size, interface to avoid\n> having to scan the underlying string in an unbounded way?\n>\n>\n\nI think we're going to make use of xdl_blankline instead of this or\nour own \"is_emptyline\"\n\nThanks,\nJake\n"},{"id":"283743","messageId":"xmqq60ve67sc.fsf@gitster.mtv.corp.google.com","threadId":"42042","inReplyTo":"CA+P7+xq_Uei_ybEjJ=PPWtruk5uB5Dp2KajA=5G6TSWU0_g2kw@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-18T19:22:59Z","receivedAt":"2016-04-18T19:22:59Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jacob Keller <jacob.keller@gmail.com> writes:\n\n> I think we're going to make use of xdl_blankline instead of this or\n> our own \"is_emptyline\"\n\nOK, so perhaps either of you two can do a final version people can\nstart having fun with?\n\nBy the way, I really do not want to see something this low-level to\nbe end-user tweakable with \"one bit enable/disable\"; the end users\nshouldn't have to bother [1].  I left it in but renamed after \"what\"\nit enables/disables, not \"how\" the enabled thing works, to clarify\nthat we have this only as a developers' aid.\n\n*1* I am fine with --compaction-heuristic=(shortest|blank|...) that\nallows a choice among many as a developers' aid, but I do not think\nthis topic is there yet.\n\n Documentation/diff-config.txt  |  9 ++++-----\n Documentation/diff-options.txt | 10 +++++-----\n diff.c                         | 18 +++++++++---------\n xdiff/xdiff.h                  |  2 +-\n xdiff/xdiffi.c                 | 22 ++++++++++------------\n 5 files changed, 29 insertions(+), 32 deletions(-)\n\ndiff --git a/Documentation/diff-config.txt b/Documentation/diff-config.txt\nindex c62745b..9bf3e92 100644\n--- a/Documentation/diff-config.txt\n+++ b/Documentation/diff-config.txt\n@@ -166,11 +166,10 @@ diff.tool::\n \n include::mergetools-diff.txt[]\n \n-diff.shortestLineHeuristic::\n-\tSet this option to true to enable the shortest line chunk heuristic when\n-\tproducing diff output. This heuristic will attempt to shift hunks such\n-\tthat the last shortest common line occurs below the hunk with the rest of\n-\tthe context above it.\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:\ndiff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\nindex 238f39c..b513023 100644\n--- a/Documentation/diff-options.txt\n+++ b/Documentation/diff-options.txt\n@@ -63,11 +63,11 @@ ifndef::git-format-patch[]\n \tSynonym for `-p --raw`.\n endif::git-format-patch[]\n \n---shortest-line-heuristic::\n---no-shortest-line-heuristic::\n-\tWhen possible, shift common shortest line in diff hunks below the hunk\n-\tsuch that the last common shortest line for each hunk is below, with the\n-\trest of the context above the hunk.\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\ndiff --git a/diff.c b/diff.c\nindex 276174c..02c75c3 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -25,7 +25,7 @@\n #endif\n \n static int diff_detect_rename_default;\n-static int diff_shortest_line_heuristic = 0;\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@@ -184,8 +184,8 @@ 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.shortestlineheuristic\")) {\n-\t\tdiff_shortest_line_heuristic = git_config_bool(var, value);\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@@ -3240,8 +3240,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_shortest_line_heuristic)\n-\t\tDIFF_XDL_SET(options, SHORTEST_LINE_HEURISTIC);\n+\tif (diff_compaction_heuristic)\n+\t\tDIFF_XDL_SET(options, COMPACTION_HEURISTIC);\n \n \toptions->orderfile = diff_order_file_cfg;\n \n@@ -3719,10 +3719,10 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac)\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, \"--shortest-line-heuristic\"))\n-\t\tDIFF_XDL_SET(options, SHORTEST_LINE_HEURISTIC);\n-\telse if (!strcmp(arg, \"--no-shortest-line-heuristic\"))\n-\t\tDIFF_XDL_CLR(options, SHORTEST_LINE_HEURISTIC);\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 968ac62..d1dbb27 100644\n--- a/xdiff/xdiff.h\n+++ b/xdiff/xdiff.h\n@@ -41,7 +41,7 @@ extern \"C\" {\n \n #define XDF_IGNORE_BLANK_LINES (1 << 7)\n \n-#define XDF_SHORTEST_LINE_HEURISTIC (1 << 8)\n+#define XDF_COMPACTION_HEURISTIC (1 << 8)\n \n #define XDL_EMIT_FUNCNAMES (1 << 0)\n #define XDL_EMIT_COMMON (1 << 1)\ndiff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\nindex 7d15b26..1ec46e0 100644\n--- a/xdiff/xdiffi.c\n+++ b/xdiff/xdiffi.c\n@@ -400,10 +400,9 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,\n }\n \n \n-static int line_length(const char *recs)\n+static int is_blank_line(xrecord_t **recs, long ix, long flags)\n {\n-\tchar *s = strchr(recs, '\\n');\n-\treturn s ? s - recs : strlen(recs);\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@@ -417,7 +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 shortest_line;\n+\tunsigned int blank_lines;\n \txrecord_t **recs = xdf->recs;\n \n \t/*\n@@ -451,7 +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\tshortest_line = UINT_MAX;\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@@ -486,9 +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\tint l = line_length(recs[ix]->ptr);\n-\t\t\t\tif (l < shortest_line)\n-\t\t\t\t\tshortest_line = l;\n+\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@@ -519,15 +517,15 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n \n \t\t/*\n \t\t * If a group can be moved back and forth, see if there is an\n-\t\t * empty line in the moving space. If there is an empty line,\n-\t\t * make sure the last empty line is the end of the group.\n+\t\t * 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_SHORTEST_LINE_HEURISTIC)) {\n+\t\tif ((flags & XDF_COMPACTION_HEURISTIC)) {\n \t\t\twhile (ixs > 0 &&\n-\t\t\t       line_length(recs[ix - 1]->ptr) > shortest_line &&\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-- \n2.8.1-399-g96b3b3a\n"},{"id":"283745","messageId":"CAGZ79kZDg9a=xr1gYa=kooYvk-ufyGAVubqbRoRpOnC38FzLSg@mail.gmail.com","threadId":"42042","inReplyTo":"xmqq60ve67sc.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-04-18T19:33:39Z","receivedAt":"2016-04-18T19:33:39Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Mon, Apr 18, 2016 at 12:22 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> Jacob Keller <jacob.keller@gmail.com> writes:\n>\n>> I think we're going to make use of xdl_blankline instead of this or\n>> our own \"is_emptyline\"\n>\n> OK, so perhaps either of you two can do a final version people can\n> start having fun with?\n\nJunios proposal seems to be on top of my latest series sent out,\nI'll squash it in and send it out as a final version if you don't mind\n(though I'll do it later today; currently diving into Gerrits Java)\n\n>\n> By the way, I really do not want to see something this low-level to\n> be end-user tweakable with \"one bit enable/disable\"; the end users\n> shouldn't have to bother [1].\n\nOk. Thanks for fixing that mistake.\n\n> I left it in but renamed after \"what\"\n> it enables/disables, not \"how\" the enabled thing works, to clarify\n> that we have this only as a developers' aid.\n\n\n>\n> *1* I am fine with --compaction-heuristic=(shortest|blank|...) that\n> allows a choice among many as a developers' aid, but I do not think\n> this topic is there yet.\n\nThis doesn't bode well with\n    > +--compaction-heuristic::\n    > +--no-compaction-heuristic::\n\nin the future? I'd rather have\n    +--compaction-heuristic=none\n    +--compaction-heuristic=lastEmptyLine\nsuch that we don't have to worry about further experiments (or matured\nheuristics) later?\n"}]}