[RFC PATCH, WAS: "weird diff output?" 0/2] implement better chunk heuristics

From: Jacob Keller <redacted>

I took up Stefan's patch, and modified it to resolve a couple issues. I
also tried to implement the suggestions from Junio's review, as well as
the suggestions I had. It appears to produce equivalent output as Jeff's
script. This version is still missing a few things, and it is possible
Stefan is working on a v2 of his own, but I thought I'd submit this.

There's still several TODOs:
* Add some tests
* better name for the heuristic(?)
* better patch description plus documentation
* is_emptyline should be more generic and handle CRLF

Changes since Stefan's v1:
* Added a patch to implement xdl_hash_and_recmatch as Junio suggested.
* Fixed a segfault in Stefan's patch
* Added XDL flag to configure the behavior
* Used an int and counted empty lines via += instead of |=
* Renamed starts_with_emptyline to is_emptyline
* Added diff command line and config options

For reviewer convenience, the interdiff between this and Stefan's version:

diff --git a/Documentation/diff-config.txt b/Documentation/diff-config.txt
index edba56522bce..cebf82702d2a 100644
--- a/Documentation/diff-config.txt
+++ b/Documentation/diff-config.txt

@@ -170,6 +170,12 @@ diff.tool::
 
 include::mergetools-diff.txt[]
 
+diff.emptyLineHeuristic::
+	Set this option to true to enable the empty line chunk heuristic when
+	producing diff output. This heuristic will attempt to shift hunks such
+	that a common empty line occurs below the hunk with the rest of the
+	context above it.
+
 diff.algorithm::
 	Choose a diff algorithm.  The variants are as follows:
 +

diff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt
index 4b0318e2ac15..6c1cd8b35584 100644
--- a/Documentation/diff-options.txt
+++ b/Documentation/diff-options.txt

@@ -63,6 +63,12 @@ ifndef::git-format-patch[]
 	Synonym for `-p --raw`.
 endif::git-format-patch[]
 
+--empty-line-heuristic::
+--no-empty-line-heuristic::
+	When possible, shift common empty lines in diff hunks below the hunk
+	such that the last common empty line for each hunk is below, with the
+	rest of the context above the hunk.
+
 --minimal::
 	Spend extra time to make sure the smallest possible
 	diff is produced.

diff --git a/diff.c b/diff.c
index 4dfe6609d059..8ab9a492928d 100644
--- a/diff.c
+++ b/diff.c

@@ -26,6 +26,7 @@
 #endif
 
 static int diff_detect_rename_default;
+static int diff_empty_line_heuristic = 0;
 static int diff_rename_limit_default = 400;
 static int diff_suppress_blank_empty;
 static int diff_use_color_default = -1;

@@ -189,6 +190,10 @@ int git_diff_ui_config(const char *var, const char *value, void *cb)
 		diff_detect_rename_default = git_config_rename(var, value);
 		return 0;
 	}
+	if (!strcmp(var, "diff.emptylineheuristic")) {
+		diff_empty_line_heuristic = git_config_bool(var, value);
+		return 0;
+	}
 	if (!strcmp(var, "diff.autorefreshindex")) {
 		diff_auto_refresh_index = git_config_bool(var, value);
 		return 0;

@@ -3278,6 +3283,8 @@ void diff_setup(struct diff_options *options)
 	options->use_color = diff_use_color_default;
 	options->detect_rename = diff_detect_rename_default;
 	options->xdl_opts |= diff_algorithm;
+	if (diff_empty_line_heuristic)
+		DIFF_XDL_SET(options, EMPTY_LINE_HEURISTIC);
 
 	options->orderfile = diff_order_file_cfg;
 

@@ -3798,6 +3805,10 @@ int diff_opt_parse(struct diff_options *options,
 		DIFF_XDL_SET(options, IGNORE_WHITESPACE_AT_EOL);
 	else if (!strcmp(arg, "--ignore-blank-lines"))
 		DIFF_XDL_SET(options, IGNORE_BLANK_LINES);
+	else if (!strcmp(arg, "--empty-line-heuristic"))
+		DIFF_XDL_SET(options, EMPTY_LINE_HEURISTIC);
+	else if (!strcmp(arg, "--no-empty-line-heuristic"))
+		DIFF_XDL_CLR(options, EMPTY_LINE_HEURISTIC);
 	else if (!strcmp(arg, "--patience"))
 		options->xdl_opts = DIFF_WITH_ALG(options, PATIENCE_DIFF);
 	else if (!strcmp(arg, "--histogram"))

diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h
index 4fb7e79410c2..9195a5c0e958 100644
--- a/xdiff/xdiff.h
+++ b/xdiff/xdiff.h

@@ -41,6 +41,8 @@ extern "C" {
 
 #define XDF_IGNORE_BLANK_LINES (1 << 7)
 
+#define XDF_EMPTY_LINE_HEURISTIC (1 << 8)
+
 #define XDL_EMIT_FUNCNAMES (1 << 0)
 #define XDL_EMIT_FUNCCONTEXT (1 << 2)
 

diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
index 5f14beb98049..83984b90f82f 100644
--- a/xdiff/xdiffi.c
+++ b/xdiff/xdiffi.c

@@ -400,7 +400,7 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,
 }
 
 
-static int starts_with_emptyline(const char *recs)
+static int is_emptyline(const char *recs)
 {
 	return recs[0] == '\n'; /* CRLF not covered here */
 }

@@ -416,7 +416,7 @@ static int xdl_hash_and_recmatch(xrecord_t **recs, long ixs, long ix, long flags
 int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 	long ix, ixo, ixs, ixref, grpsiz, nrec = xdf->nrec;
 	char *rchg = xdf->rchg, *rchgo = xdfo->rchg;
-	unsigned char has_emptyline;
+	unsigned int emptylines;
 	xrecord_t **recs = xdf->recs;
 
 	/*

@@ -450,7 +450,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 
 		do {
 			grpsiz = ix - ixs;
-			has_emptyline = 0;
+			emptylines = 0;
 
 			/*
 			 * If the line before the current change group, is equal to

@@ -458,11 +458,11 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 			 * the group.
 			 */
 			while (ixs > 0 && xdl_hash_and_recmatch(recs, ixs - 1, ix - 1, flags)) {
+				emptylines += is_emptyline(recs[ix - 1]->ptr);
+
 				rchg[--ixs] = 1;
 				rchg[--ix] = 0;
 
-				has_emptyline |=
-					starts_with_emptyline(recs[ix]->ptr);
 				/*
 				 * This change might have joined two change groups,
 				 * so we try to take this scenario in account by moving

@@ -492,9 +492,6 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 				rchg[ixs++] = 0;
 				rchg[ix++] = 1;
 
-				has_emptyline |=
-					starts_with_emptyline(recs[ix]->ptr);
-
 				/*
 				 * This change might have joined two change groups,
 				 * so we try to take this scenario in account by moving

@@ -527,21 +524,12 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 		 * As we shifted the group forward as far as possible, we only
 		 * need to shift it back if at all.
 		 */
-		if (has_emptyline) {
-			while (ixs > 0 && recs[ixs - 1]->ha == recs[ix - 1]->ha &&
-			       xdl_recmatch(recs[ixs - 1]->ptr, recs[ixs - 1]->size, recs[ix - 1]->ptr, recs[ix - 1]->size, flags) &&
-			       !starts_with_emptyline(recs[ix - 1]->ptr)) {
+		if ((flags & XDF_EMPTY_LINE_HEURISTIC) && emptylines) {
+			while (ixs > 0 &&
+			       !is_emptyline(recs[ix - 1]->ptr) &&
+			       xdl_hash_and_recmatch(recs, ixs - 1, ix - 1, flags)) {
 				rchg[--ixs] = 1;
 				rchg[--ix] = 0;
-
-				/*
-				 * This change did not join two change groups,
-				 * as we did that before already, so there is no
-				 * need to adapt the other-file, i.e.
-				 * running
-				 *     for (; rchg[ixs - 1]; ixs--);
-				 *     while (rchgo[--ixo]);
-				 */
 			}
 		}
 	}

Jacob Keller (1):
  xdiff: add xdl_hash_and_recmatch helper function

Stefan Beller (1):
  xdiff: implement empty line chunk heuristic

 Documentation/diff-config.txt  |  6 ++++++
 Documentation/diff-options.txt |  6 ++++++
 diff.c                         | 11 +++++++++++
 xdiff/xdiff.h                  |  2 ++
 xdiff/xdiffi.c                 | 42 ++++++++++++++++++++++++++++++++++++++----
 5 files changed, 63 insertions(+), 4 deletions(-)

-- 
2.8.1.369.geae769a

From: Jacob Keller <redacted>

It is a common pattern in xdl_change_compact to check that hashes and
strings match. The resulting code to perform this change causes very
long lines and makes it hard to follow the intention. Introduce a helper
function xdl_hash_and_recmatch which performs both checks to increase
code readability.

Signed-off-by: Jacob Keller <jacob.e.keller@intel.com>
---
 xdiff/xdiffi.c | 16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)

diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
index 2358a2d6326e..fff97ac3e3c7 100644
--- a/xdiff/xdiffi.c
+++ b/xdiff/xdiffi.c

@@ -400,6 +400,14 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,
 }
 
 
+static int xdl_hash_and_recmatch(xrecord_t **recs, long ixs, long ix, long flags)
+{
+	return (recs[ixs]->ha == recs[ix]->ha &&
+		xdl_recmatch(recs[ixs]->ptr, recs[ixs]->size,
+			     recs[ix]->ptr, recs[ix]->size,
+			     flags));
+}
+
 int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 	long ix, ixo, ixs, ixref, grpsiz, nrec = xdf->nrec;
 	char *rchg = xdf->rchg, *rchgo = xdfo->rchg;

@@ -442,8 +450,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 			 * the last line of the current change group, shift backward
 			 * the group.
 			 */
-			while (ixs > 0 && recs[ixs - 1]->ha == recs[ix - 1]->ha &&
-			       xdl_recmatch(recs[ixs - 1]->ptr, recs[ixs - 1]->size, recs[ix - 1]->ptr, recs[ix - 1]->size, flags)) {
+			while (ixs > 0 && xdl_hash_and_recmatch(recs, ixs - 1, ix - 1, flags)) {
 				rchg[--ixs] = 1;
 				rchg[--ix] = 0;
 

@@ -470,8 +477,9 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 			 * the line next of the current change group, shift forward
 			 * the group.
 			 */
-			while (ix < nrec && recs[ixs]->ha == recs[ix]->ha &&
-			       xdl_recmatch(recs[ixs]->ptr, recs[ixs]->size, recs[ix]->ptr, recs[ix]->size, flags)) {
+			while (ix < nrec && xdl_hash_and_recmatch(recs, ixs, ix, flags)) {
+				emptylines += is_emptyline(recs[ix]->ptr);
+
 				rchg[ixs++] = 0;
 				rchg[ix++] = 1;
 

-- 
2.8.1.369.geae769a

From: Stefan Beller <redacted>

In order to produce the smallest possible diff and combine several diff
hunks together, we implement a heuristic from GNU Diff which moves diff
hunks forward as far as possible when we find common context above and
below a diff hunk. This sometimes produces less readable diffs when
writing C, Shell, or other programming languages, ie:

...
 /*
+ *
+ *
+ */
+
+/*
...

instead of the more readable equivalent of

...
+/*
+ *
+ *
+ */
+
 /*
...

Implement the following heuristic to (optionally) produce the desired
output.

  If there are diff chunks which can be shifted around, shift each hunk
  such that the last common empty line is below the chunk with the rest
  of the context above.

This heuristic appears to resolve the above example and several other
common issues without producing significantly weird results. However, as
with any heuristic it is not really known whether this will always be
more optimal. Thus, leave the heuristic disabled by default.

Add an XDIFF flag to enable this heuristic only conditionally. Add
a diff command line option and diff configuration option to allow users
to enable this option when desired.

TODO:
* Add tests
* Add better/more documentation explaining the heuristic, possibly with
  examples(?)
* better name(?)

Signed-off-by: Stefan Beller <redacted>
Signed-off-by: Jacob Keller <jacob.e.keller@intel.com>
---
 Documentation/diff-config.txt  |  6 ++++++
 Documentation/diff-options.txt |  6 ++++++
 diff.c                         | 11 +++++++++++
 xdiff/xdiff.h                  |  2 ++
 xdiff/xdiffi.c                 | 26 ++++++++++++++++++++++++++
 5 files changed, 51 insertions(+)

diff --git a/Documentation/diff-config.txt b/Documentation/diff-config.txt
index edba56522bce..cebf82702d2a 100644
--- a/Documentation/diff-config.txt
+++ b/Documentation/diff-config.txt

@@ -170,6 +170,12 @@ diff.tool::
 
 include::mergetools-diff.txt[]
 
+diff.emptyLineHeuristic::
+	Set this option to true to enable the empty line chunk heuristic when
+	producing diff output. This heuristic will attempt to shift hunks such
+	that a common empty line occurs below the hunk with the rest of the
+	context above it.
+
 diff.algorithm::
 	Choose a diff algorithm.  The variants are as follows:
 +

diff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt
index 4b0318e2ac15..6c1cd8b35584 100644
--- a/Documentation/diff-options.txt
+++ b/Documentation/diff-options.txt

@@ -63,6 +63,12 @@ ifndef::git-format-patch[]
 	Synonym for `-p --raw`.
 endif::git-format-patch[]
 
+--empty-line-heuristic::
+--no-empty-line-heuristic::
+	When possible, shift common empty lines in diff hunks below the hunk
+	such that the last common empty line for each hunk is below, with the
+	rest of the context above the hunk.
+
 --minimal::
 	Spend extra time to make sure the smallest possible
 	diff is produced.

diff --git a/diff.c b/diff.c
index 4dfe6609d059..8ab9a492928d 100644
--- a/diff.c
+++ b/diff.c

@@ -26,6 +26,7 @@
 #endif
 
 static int diff_detect_rename_default;
+static int diff_empty_line_heuristic = 0;
 static int diff_rename_limit_default = 400;
 static int diff_suppress_blank_empty;
 static int diff_use_color_default = -1;

@@ -189,6 +190,10 @@ int git_diff_ui_config(const char *var, const char *value, void *cb)
 		diff_detect_rename_default = git_config_rename(var, value);
 		return 0;
 	}
+	if (!strcmp(var, "diff.emptylineheuristic")) {
+		diff_empty_line_heuristic = git_config_bool(var, value);
+		return 0;
+	}
 	if (!strcmp(var, "diff.autorefreshindex")) {
 		diff_auto_refresh_index = git_config_bool(var, value);
 		return 0;

@@ -3278,6 +3283,8 @@ void diff_setup(struct diff_options *options)
 	options->use_color = diff_use_color_default;
 	options->detect_rename = diff_detect_rename_default;
 	options->xdl_opts |= diff_algorithm;
+	if (diff_empty_line_heuristic)
+		DIFF_XDL_SET(options, EMPTY_LINE_HEURISTIC);
 
 	options->orderfile = diff_order_file_cfg;
 

@@ -3798,6 +3805,10 @@ int diff_opt_parse(struct diff_options *options,
 		DIFF_XDL_SET(options, IGNORE_WHITESPACE_AT_EOL);
 	else if (!strcmp(arg, "--ignore-blank-lines"))
 		DIFF_XDL_SET(options, IGNORE_BLANK_LINES);
+	else if (!strcmp(arg, "--empty-line-heuristic"))
+		DIFF_XDL_SET(options, EMPTY_LINE_HEURISTIC);
+	else if (!strcmp(arg, "--no-empty-line-heuristic"))
+		DIFF_XDL_CLR(options, EMPTY_LINE_HEURISTIC);
 	else if (!strcmp(arg, "--patience"))
 		options->xdl_opts = DIFF_WITH_ALG(options, PATIENCE_DIFF);
 	else if (!strcmp(arg, "--histogram"))

diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h
index 4fb7e79410c2..9195a5c0e958 100644
--- a/xdiff/xdiff.h
+++ b/xdiff/xdiff.h

@@ -41,6 +41,8 @@ extern "C" {
 
 #define XDF_IGNORE_BLANK_LINES (1 << 7)
 
+#define XDF_EMPTY_LINE_HEURISTIC (1 << 8)
+
 #define XDL_EMIT_FUNCNAMES (1 << 0)
 #define XDL_EMIT_FUNCCONTEXT (1 << 2)
 

diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
index fff97ac3e3c7..83984b90f82f 100644
--- a/xdiff/xdiffi.c
+++ b/xdiff/xdiffi.c

@@ -400,6 +400,11 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,
 }
 
 
+static int is_emptyline(const char *recs)
+{
+	return recs[0] == '\n'; /* CRLF not covered here */
+}
+
 static int xdl_hash_and_recmatch(xrecord_t **recs, long ixs, long ix, long flags)
 {
 	return (recs[ixs]->ha == recs[ix]->ha &&

@@ -411,6 +416,7 @@ static int xdl_hash_and_recmatch(xrecord_t **recs, long ixs, long ix, long flags
 int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 	long ix, ixo, ixs, ixref, grpsiz, nrec = xdf->nrec;
 	char *rchg = xdf->rchg, *rchgo = xdfo->rchg;
+	unsigned int emptylines;
 	xrecord_t **recs = xdf->recs;
 
 	/*

@@ -444,6 +450,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 
 		do {
 			grpsiz = ix - ixs;
+			emptylines = 0;
 
 			/*
 			 * If the line before the current change group, is equal to

@@ -451,6 +458,8 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 			 * the group.
 			 */
 			while (ixs > 0 && xdl_hash_and_recmatch(recs, ixs - 1, ix - 1, flags)) {
+				emptylines += is_emptyline(recs[ix - 1]->ptr);
+
 				rchg[--ixs] = 1;
 				rchg[--ix] = 0;
 

@@ -506,6 +515,23 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 			rchg[--ix] = 0;
 			while (rchgo[--ixo]);
 		}
+
+		/*
+		 * If a group can be moved back and forth, see if there is an
+		 * empty line in the moving space. If there is an empty line,
+		 * make sure the last empty line is the end of the group.
+		 *
+		 * As we shifted the group forward as far as possible, we only
+		 * need to shift it back if at all.
+		 */
+		if ((flags & XDF_EMPTY_LINE_HEURISTIC) && emptylines) {
+			while (ixs > 0 &&
+			       !is_emptyline(recs[ix - 1]->ptr) &&
+			       xdl_hash_and_recmatch(recs, ixs - 1, ix - 1, flags)) {
+				rchg[--ixs] = 1;
+				rchg[--ix] = 0;
+			}
+		}
 	}
 
 	return 0;

-- 
2.8.1.369.geae769a

On Fri, Apr 15, 2016 at 9:51 AM, Jacob Keller [off-list ref] wrote:

    This heuristic will attempt to shift hunks such that *the last* common
    empty line occurs below the hunk with the rest of the context above it.

maybe?

How is this fixing the segfault bug?
From my understanding ix should have the same value here as ix-1 above.

Or would this fix the segfault bug?
I think we would need to have the check for empty lines
in both loops to be sure to cover the whole movable range.

On Fri, Apr 15, 2016 at 10:02 AM, Stefan Beller [off-list ref] wrote:

quoted

@@ -458,11 +458,11 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
                         * the group.
                         */
                        while (ixs > 0 && xdl_hash_and_recmatch(recs, ixs - 1, ix - 1, flags)) {
+                               emptylines += is_emptyline(recs[ix - 1]->ptr);
+
                                rchg[--ixs] = 1;
                                rchg[--ix] = 0;

-                               has_emptyline |=
-                                       starts_with_emptyline(recs[ix]->ptr);

How is this fixing the segfault bug?
From my understanding ix should have the same value here as ix-1 above.

quoted

                                /*
                                 * This change might have joined two change groups,
                                 * so we try to take this scenario in account by moving

@@ -492,9 +492,6 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
                                rchg[ixs++] = 0;
                                rchg[ix++] = 1;

-                               has_emptyline |=
-                                       starts_with_emptyline(recs[ix]->ptr);
-

Or would this fix the segfault bug?
I think we would need to have the check for empty lines
in both loops to be sure to cover the whole movable range.

Actually we would only need to have the empty line count in the second loop as
the first loop shifted it as much up(backwards) as possible, such that
the hunk sits on one
end of the movable range. The second loop would iterate over the whole
range, so that
would be the only place needed to count.

On Fri, Apr 15, 2016 at 10:02 AM, Stefan Beller [off-list ref] wrote:

On Fri, Apr 15, 2016 at 9:51 AM, Jacob Keller [off-list ref] wrote:

quoted

From: Jacob Keller <redacted>

I took up Stefan's patch, and modified it to resolve a couple issues. I
also tried to implement the suggestions from Junio's review, as well as
the suggestions I had. It appears to produce equivalent output as Jeff's
script. This version is still missing a few things, and it is possible
Stefan is working on a v2 of his own, but I thought I'd submit this.

There's still several TODOs:
* Add some tests
* better name for the heuristic(?)
* better patch description plus documentation
* is_emptyline should be more generic and handle CRLF

Changes since Stefan's v1:
* Added a patch to implement xdl_hash_and_recmatch as Junio suggested.
* Fixed a segfault in Stefan's patch
* Added XDL flag to configure the behavior
* Used an int and counted empty lines via += instead of |=
* Renamed starts_with_emptyline to is_emptyline
* Added diff command line and config options

For reviewer convenience, the interdiff between this and Stefan's version:

diff --git a/Documentation/diff-config.txt b/Documentation/diff-config.txt
index edba56522bce..cebf82702d2a 100644
--- a/Documentation/diff-config.txt
+++ b/Documentation/diff-config.txt

@@ -170,6 +170,12 @@ diff.tool::

 include::mergetools-diff.txt[]

+diff.emptyLineHeuristic::
+       Set this option to true to enable the empty line chunk heuristic when
+       producing diff output. This heuristic will attempt to shift hunks such
+       that a common empty line occurs below the hunk with the rest of the
+       context above it.
+

    This heuristic will attempt to shift hunks such that *the last* common
    empty line occurs below the hunk with the rest of the context above it.

maybe?

That sounds reasonable.

quoted

 diff.algorithm::
        Choose a diff algorithm.  The variants are as follows:
 +

diff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt
index 4b0318e2ac15..6c1cd8b35584 100644
--- a/Documentation/diff-options.txt
+++ b/Documentation/diff-options.txt

@@ -63,6 +63,12 @@ ifndef::git-format-patch[]
        Synonym for `-p --raw`.
 endif::git-format-patch[]

+--empty-line-heuristic::
+--no-empty-line-heuristic::
+       When possible, shift common empty lines in diff hunks below the hunk
+       such that the last common empty line for each hunk is below, with the
+       rest of the context above the hunk.
+
 --minimal::
        Spend extra time to make sure the smallest possible
        diff is produced.

diff --git a/diff.c b/diff.c
index 4dfe6609d059..8ab9a492928d 100644
--- a/diff.c
+++ b/diff.c

@@ -26,6 +26,7 @@
 #endif

 static int diff_detect_rename_default;
+static int diff_empty_line_heuristic = 0;
 static int diff_rename_limit_default = 400;
 static int diff_suppress_blank_empty;
 static int diff_use_color_default = -1;

@@ -189,6 +190,10 @@ int git_diff_ui_config(const char *var, const char *value, void *cb)
                diff_detect_rename_default = git_config_rename(var, value);
                return 0;
        }
+       if (!strcmp(var, "diff.emptylineheuristic")) {
+               diff_empty_line_heuristic = git_config_bool(var, value);
+               return 0;
+       }
        if (!strcmp(var, "diff.autorefreshindex")) {
                diff_auto_refresh_index = git_config_bool(var, value);
                return 0;

@@ -3278,6 +3283,8 @@ void diff_setup(struct diff_options *options)
        options->use_color = diff_use_color_default;
        options->detect_rename = diff_detect_rename_default;
        options->xdl_opts |= diff_algorithm;
+       if (diff_empty_line_heuristic)
+               DIFF_XDL_SET(options, EMPTY_LINE_HEURISTIC);

        options->orderfile = diff_order_file_cfg;

@@ -3798,6 +3805,10 @@ int diff_opt_parse(struct diff_options *options,
                DIFF_XDL_SET(options, IGNORE_WHITESPACE_AT_EOL);
        else if (!strcmp(arg, "--ignore-blank-lines"))
                DIFF_XDL_SET(options, IGNORE_BLANK_LINES);
+       else if (!strcmp(arg, "--empty-line-heuristic"))
+               DIFF_XDL_SET(options, EMPTY_LINE_HEURISTIC);
+       else if (!strcmp(arg, "--no-empty-line-heuristic"))
+               DIFF_XDL_CLR(options, EMPTY_LINE_HEURISTIC);
        else if (!strcmp(arg, "--patience"))
                options->xdl_opts = DIFF_WITH_ALG(options, PATIENCE_DIFF);
        else if (!strcmp(arg, "--histogram"))

diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h
index 4fb7e79410c2..9195a5c0e958 100644
--- a/xdiff/xdiff.h
+++ b/xdiff/xdiff.h

@@ -41,6 +41,8 @@ extern "C" {

 #define XDF_IGNORE_BLANK_LINES (1 << 7)

+#define XDF_EMPTY_LINE_HEURISTIC (1 << 8)
+
 #define XDL_EMIT_FUNCNAMES (1 << 0)
 #define XDL_EMIT_FUNCCONTEXT (1 << 2)

diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
index 5f14beb98049..83984b90f82f 100644
--- a/xdiff/xdiffi.c
+++ b/xdiff/xdiffi.c

@@ -400,7 +400,7 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,
 }


-static int starts_with_emptyline(const char *recs)
+static int is_emptyline(const char *recs)
 {
        return recs[0] == '\n'; /* CRLF not covered here */
 }

@@ -416,7 +416,7 @@ static int xdl_hash_and_recmatch(xrecord_t **recs, long ixs, long ix, long flags
 int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
        long ix, ixo, ixs, ixref, grpsiz, nrec = xdf->nrec;
        char *rchg = xdf->rchg, *rchgo = xdfo->rchg;
-       unsigned char has_emptyline;
+       unsigned int emptylines;
        xrecord_t **recs = xdf->recs;

        /*

@@ -450,7 +450,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {

                do {
                        grpsiz = ix - ixs;
-                       has_emptyline = 0;
+                       emptylines = 0;

                        /*
                         * If the line before the current change group, is equal to

@@ -458,11 +458,11 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
                         * the group.
                         */
                        while (ixs > 0 && xdl_hash_and_recmatch(recs, ixs - 1, ix - 1, flags)) {
+                               emptylines += is_emptyline(recs[ix - 1]->ptr);
+
                                rchg[--ixs] = 1;
                                rchg[--ix] = 0;

-                               has_emptyline |=
-                                       starts_with_emptyline(recs[ix]->ptr);

How is this fixing the segfault bug?
From my understanding ix should have the same value here as ix-1 above.

This change was for style reasons to check for empty lines first
thing, and it matches how we do "ix - 1" into xdl_hash_and_recmatch.
But as per your following comment, I think you're right and we don't
need this.

quoted

                                /*
                                 * This change might have joined two change groups,
                                 * so we try to take this scenario in account by moving

@@ -492,9 +492,6 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
                                rchg[ixs++] = 0;
                                rchg[ix++] = 1;

-                               has_emptyline |=
-                                       starts_with_emptyline(recs[ix]->ptr);
-

Or would this fix the segfault bug?
I think we would need to have the check for empty lines
in both loops to be sure to cover the whole movable range.

This is the real segfault fix, I only changed the other in order to
make it appear consistent.

quoted

                                /*
                                 * This change might have joined two change groups,
                                 * so we try to take this scenario in account by moving

@@ -527,21 +524,12 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
                 * As we shifted the group forward as far as possible, we only
                 * need to shift it back if at all.
                 */
-               if (has_emptyline) {
-                       while (ixs > 0 && recs[ixs - 1]->ha == recs[ix - 1]->ha &&
-                              xdl_recmatch(recs[ixs - 1]->ptr, recs[ixs - 1]->size, recs[ix - 1]->ptr, recs[ix - 1]->size, flags) &&
-                              !starts_with_emptyline(recs[ix - 1]->ptr)) {
+               if ((flags & XDF_EMPTY_LINE_HEURISTIC) && emptylines) {
+                       while (ixs > 0 &&
+                              !is_emptyline(recs[ix - 1]->ptr) &&
+                              xdl_hash_and_recmatch(recs, ixs - 1, ix - 1, flags)) {
                                rchg[--ixs] = 1;
                                rchg[--ix] = 0;
-
-                               /*
-                                * This change did not join two change groups,
-                                * as we did that before already, so there is no
-                                * need to adapt the other-file, i.e.
-                                * running
-                                *     for (; rchg[ixs - 1]; ixs--);
-                                *     while (rchgo[--ixo]);
-                                */
                        }
                }
        }

Jacob Keller (1):
  xdiff: add xdl_hash_and_recmatch helper function

Stefan Beller (1):
  xdiff: implement empty line chunk heuristic

 Documentation/diff-config.txt  |  6 ++++++
 Documentation/diff-options.txt |  6 ++++++
 diff.c                         | 11 +++++++++++
 xdiff/xdiff.h                  |  2 ++
 xdiff/xdiffi.c                 | 42 ++++++++++++++++++++++++++++++++++++++----
 5 files changed, 63 insertions(+), 4 deletions(-)

--
2.8.1.369.geae769a

On Fri, Apr 15, 2016 at 10:10 AM, Stefan Beller [off-list ref] wrote:

On Fri, Apr 15, 2016 at 10:02 AM, Stefan Beller [off-list ref] wrote:

quoted

quoted

@@ -458,11 +458,11 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
                         * the group.
                         */
                        while (ixs > 0 && xdl_hash_and_recmatch(recs, ixs - 1, ix - 1, flags)) {
+                               emptylines += is_emptyline(recs[ix - 1]->ptr);
+
                                rchg[--ixs] = 1;
                                rchg[--ix] = 0;

-                               has_emptyline |=
-                                       starts_with_emptyline(recs[ix]->ptr);

How is this fixing the segfault bug?
From my understanding ix should have the same value here as ix-1 above.

quoted

                                /*
                                 * This change might have joined two change groups,
                                 * so we try to take this scenario in account by moving

@@ -492,9 +492,6 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
                                rchg[ixs++] = 0;
                                rchg[ix++] = 1;

-                               has_emptyline |=
-                                       starts_with_emptyline(recs[ix]->ptr);
-

Or would this fix the segfault bug?
I think we would need to have the check for empty lines
in both loops to be sure to cover the whole movable range.

Actually we would only need to have the empty line count in the second loop as
the first loop shifted it as much up(backwards) as possible, such that
the hunk sits on one
end of the movable range. The second loop would iterate over the whole
range, so that
would be the only place needed to count.

I agree that we can drop the first part and I am testing it now.

Thanks,
Jake

On Fri, Apr 15, 2016 at 9:51 AM, Jacob Keller [off-list ref] wrote:

I was looking at the TODO here and thought about the name:
It should not encode the `emptyLine` into the config option as
it is only one of many heuristics.

It should be something like `diff.heuristic=lastEmptyLine`
The we could add firstEmptyLine, aggressiveUp, aggressiveDown,
breakAtShortestLineLength or other styles as well later on.

I do not quite understand the difference between diff.algorithm
and the newly proposed heuristic as the heuristic is part of
the algorithm? So I guess we'd need to have some documentation
saying how these differ. (fundamental algorithm vs last minute
style fixup?)

On Fri, Apr 15, 2016 at 12:57 PM, Stefan Beller [off-list ref] wrote:

I was looking at the TODO here and thought about the name:
It should not encode the `emptyLine` into the config option as
it is only one of many heuristics.

It should be something like `diff.heuristic=lastEmptyLine`
The we could add firstEmptyLine, aggressiveUp, aggressiveDown,
breakAtShortestLineLength or other styles as well later on.

This sounds better, but how does this handle multiple heuristics?

I do not quite understand the difference between diff.algorithm
and the newly proposed heuristic as the heuristic is part of
the algorithm? So I guess we'd need to have some documentation
saying how these differ. (fundamental algorithm vs last minute
style fixup?)

It is not part of the algorithm. It's applied after the algorithm.
xdl_change_compact is run after the algorithm and run for all
algorithms.

These are last minute style changes, and should probably not use the
term heuristic, but somehow capture "last minute style fixup"

Thanks,
Jake

--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html