{"thread":{"id":"42041","subject":"[RFC PATCH, WAS: \"weird diff output?\" v3 0/2] implement empty line diff chunk heuristic","startedAt":"2016-04-15T22:57:16Z","lastAt":"2016-04-15T22:57:18Z","messageCount":3,"participants":["Jacob Keller"],"isPatch":true,"patchVersion":3,"patchTotal":2},"messages":[{"id":"283614","messageId":"20160415225718.13610-1-jacob.e.keller@intel.com","threadId":"42041","inReplyTo":null,"subject":"[RFC PATCH, WAS: \"weird diff output?\" v3 0/2] implement empty line diff chunk heuristic","fromName":"Jacob Keller","fromEmail":"jacob.e.keller@intel.com","sentAt":"2016-04-15T22:57:16Z","receivedAt":"2016-04-15T22:57:16Z","isPatch":true,"sender":{"key":"jacob.e.keller@intel.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"From: Jacob Keller <jacob.keller@gmail.com>\n\nThird version of my series with a few more minor fixups. I left the\ndiff command line and configuration option alone for now, suspecting\nthat long term we either (a) remove it or (b) use a gitattribute, so\nthere is no reason to bikeshed the name or its contents right now.\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* figure out how to make is_emptyline CRLF aware\n\nChanges since my v2:\n* fixed is_emptylines in the wrong patch\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\nThe interdiff between v2 and v3 is very small:\n\ndiff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\nindex 9436ad735243..dd93e6781e8b 100644\n--- a/xdiff/xdiffi.c\n+++ b/xdiff/xdiffi.c\n@@ -485,6 +485,7 @@ 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+\n \t\t\t\temptylines += is_emptyline(recs[ix]->ptr);\n \n \t\t\t\trchg[ixs++] = 0;\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                 | 41 +++++++++++++++++++++++++++++++++++++----\n 5 files changed, 62 insertions(+), 4 deletions(-)\n\n-- \n2.8.1.369.geae769a\n"},{"id":"283615","messageId":"20160415225718.13610-2-jacob.e.keller@intel.com","threadId":"42041","inReplyTo":"20160415225718.13610-1-jacob.e.keller@intel.com","subject":"[RFC PATCH, WAS: \"weird diff output?\" v3 1/2] xdiff: add recs_match helper function","fromName":"Jacob Keller","fromEmail":"jacob.e.keller@intel.com","sentAt":"2016-04-15T22:57:17Z","receivedAt":"2016-04-15T22:57:17Z","isPatch":true,"sender":{"key":"jacob.e.keller@intel.com","avatar":"https://avatars.githubusercontent.com/u/874719?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>\n---\n xdiff/xdiffi.c | 15 +++++++++++----\n 1 file changed, 11 insertions(+), 4 deletions(-)\n\ndiff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\nindex 2358a2d6326e..b56c1e24593c 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,8 @@ 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+\n \t\t\t\trchg[ixs++] = 0;\n \t\t\t\trchg[ix++] = 1;\n \n-- \n2.8.1.369.geae769a\n"},{"id":"283616","messageId":"20160415225718.13610-3-jacob.e.keller@intel.com","threadId":"42041","inReplyTo":"20160415225718.13610-1-jacob.e.keller@intel.com","subject":"[RFC PATCH, WAS: \"weird diff output?\" v3 2/2] xdiff: implement empty line chunk heuristic","fromName":"Jacob Keller","fromEmail":"jacob.e.keller@intel.com","sentAt":"2016-04-15T22:57:18Z","receivedAt":"2016-04-15T22:57:18Z","isPatch":true,"sender":{"key":"jacob.e.keller@intel.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"From: Stefan Beller <sbeller@google.com>\n\nIn 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, 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>\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                 | 26 ++++++++++++++++++++++++++\n 5 files changed, 51 insertions(+)\n\ndiff --git a/Documentation/diff-config.txt b/Documentation/diff-config.txt\nindex edba56522bce..9265d60d9571 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.emptyLineHeuristic::\n+\tSet this option to true to enable the empty line chunk heuristic when\n+\tproducing diff output. This heuristic will attempt to shift hunks such\n+\tthat the last common empty 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 4b0318e2ac15..6c1cd8b35584 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+--empty-line-heuristic::\n+--no-empty-line-heuristic::\n+\tWhen possible, shift common empty lines in diff hunks below the hunk\n+\tsuch that the last common empty 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 4dfe6609d059..8ab9a492928d 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_empty_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.emptylineheuristic\")) {\n+\t\tdiff_empty_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_empty_line_heuristic)\n+\t\tDIFF_XDL_SET(options, EMPTY_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, \"--empty-line-heuristic\"))\n+\t\tDIFF_XDL_SET(options, EMPTY_LINE_HEURISTIC);\n+\telse if (!strcmp(arg, \"--no-empty-line-heuristic\"))\n+\t\tDIFF_XDL_CLR(options, EMPTY_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 4fb7e79410c2..9195a5c0e958 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_EMPTY_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 b56c1e24593c..dd93e6781e8b 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_emptyline(const char *recs)\n+{\n+\treturn recs[0] == '\\n'; /* CRLF not covered here */\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 emptylines;\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\temptylines = 0;\n \n \t\t\t/*\n \t\t\t * If the line before the current change group, is equal to\n@@ -479,6 +486,8 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n \t\t\t */\n \t\t\twhile (ix < nrec && recs_match(recs, ixs, ix, flags)) {\n \n+\t\t\t\temptylines += is_emptyline(recs[ix]->ptr);\n+\n \t\t\t\trchg[ixs++] = 0;\n \t\t\t\trchg[ix++] = 1;\n \n@@ -505,6 +514,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_EMPTY_LINE_HEURISTIC) && emptylines) {\n+\t\t\twhile (ixs > 0 &&\n+\t\t\t       !is_emptyline(recs[ix - 1]->ptr) &&\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.369.geae769a\n"}]}