[RFC PATCH, WAS: "weird diff output?" v3a 0/2] implement shortest line diff chunk heuristic

[RFC PATCH, WAS: "weird diff output?" v3a 0/2] implement shortest line diff chunk heuristic

[Stefan Beller]

This is a version based on Jacobs v2, with the same fixes as in his v3 (hopefully),
changing the heuristic, such that CRLF confusion might be gone.

TODO:
* add some tests
* think about whether we need a git attribute or not (I did some
  thinking, and if we do need to configure this at all, this is where I
  would put it)
  
Later on we want to have git attributes I'd think. For now let's just keep
the `git config diff.shortestlineheuristic true` config option for testing?
  
Changes since Jacobs v2:
 * s/empty line/shortest line/g
   That new heuristic is a superset of the empty line heuristic as empty lines
   are shortest lines.  This solves the "What is an empty line?" question
   (Think of CRLF vs LF)
 * fixed Jacobs rebase mistake (which is also fixed in Jacobs v3)

Changes since my v1:
* rename xdl_hash_and_recmatch to recs_match
* remove counting empty lines in the first section of the looping

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

Jacob Keller (1):
  xdiff: add recs_match 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                 | 43 ++++++++++++++++++++++++++++++++++++++----
 5 files changed, 64 insertions(+), 4 deletions(-)

-- 
2.8.1.189.gd13d43c

[PATCH 1/2] xdiff: add recs_match helper function

[Stefan Beller]

From: Jacob Keller <jacob.keller@gmail.com>

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 recs_match which performs both checks to increase
code readability.

Signed-off-by: Jacob Keller <jacob.e.keller@intel.com>
Signed-off-by: Stefan Beller <sbeller@google.com>
---
 xdiff/xdiffi.c | 14 ++++++++++----
 1 file changed, 10 insertions(+), 4 deletions(-)

diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
index 2358a2d..748eeb9 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 recs_match(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 && recs_match(recs, ixs - 1, ix - 1, flags)) {
 				rchg[--ixs] = 1;
 				rchg[--ix] = 0;
 
@@ -470,8 +477,7 @@ 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 && recs_match(recs, ixs, ix, flags)) {
 				rchg[ixs++] = 0;
 				rchg[ix++] = 1;
 
-- 
2.8.1.189.gd13d43c

[PATCH 2/2] xdiff: implement empty line chunk heuristic

[Stefan Beller]

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

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

Original discussion and testing found the following heuristic to be
producing 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. When
implementing this heuristic the handling of empty lines was awkward as
it is unclear what an empty line is. ('\n' or do we include "\r\n" as it
is common on Windows?) Instead we implement a slightly different heuristic:

  If there are diff chunks which can be shifted around, find the shortest
  line in the overlapping parts. Use the line with the shortest length that
  occurs last as the last line of the chunk with the rest
  of the context above.

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 <sbeller@google.com>
Signed-off-by: Jacob Keller <jacob.e.keller@intel.com>
Signed-off-by: Stefan Beller <sbeller@google.com>
---
 Documentation/diff-config.txt  |  6 ++++++
 Documentation/diff-options.txt |  6 ++++++
 diff.c                         | 11 +++++++++++
 xdiff/xdiff.h                  |  2 ++
 xdiff/xdiffi.c                 | 29 +++++++++++++++++++++++++++++
 5 files changed, 54 insertions(+)

diff --git a/Documentation/diff-config.txt b/Documentation/diff-config.txt
index edba565..3d99a90 100644
--- a/Documentation/diff-config.txt
+++ b/Documentation/diff-config.txt
@@ -170,6 +170,12 @@ diff.tool::
 
 include::mergetools-diff.txt[]
 
+diff.shortestLineHeuristic::
+	Set this option to true to enable the shortest line chunk heuristic when
+	producing diff output. This heuristic will attempt to shift hunks such
+	that the last shortest common 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 4b0318e..b1ca83d 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[]
 
+--shortest-line-heuristic::
+--no-shortest-line-heuristic::
+	When possible, shift common shortest line in diff hunks below the hunk
+	such that the last common shortest 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 4dfe660..a02aff9 100644
--- a/diff.c
+++ b/diff.c
@@ -26,6 +26,7 @@
 #endif
 
 static int diff_detect_rename_default;
+static int diff_shortest_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.shortestlineheuristic")) {
+		diff_shortest_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_shortest_line_heuristic)
+		DIFF_XDL_SET(options, SHORTEST_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, "--shortest-line-heuristic"))
+		DIFF_XDL_SET(options, SHORTEST_LINE_HEURISTIC);
+	else if (!strcmp(arg, "--no-shortest-line-heuristic"))
+		DIFF_XDL_CLR(options, SHORTEST_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 4fb7e79..e1f8ec0 100644
--- a/xdiff/xdiff.h
+++ b/xdiff/xdiff.h
@@ -41,6 +41,8 @@ extern "C" {
 
 #define XDF_IGNORE_BLANK_LINES (1 << 7)
 
+#define XDF_SHORTEST_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 748eeb9..7d15b26 100644
--- a/xdiff/xdiffi.c
+++ b/xdiff/xdiffi.c
@@ -400,6 +400,12 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,
 }
 
 
+static int line_length(const char *recs)
+{
+	char *s = strchr(recs, '\n');
+	return s ? s - recs : strlen(recs);
+}
+
 static int recs_match(xrecord_t **recs, long ixs, long ix, long flags)
 {
 	return (recs[ixs]->ha == recs[ix]->ha &&
@@ -411,6 +417,7 @@ static int recs_match(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 shortest_line;
 	xrecord_t **recs = xdf->recs;
 
 	/*
@@ -444,6 +451,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 
 		do {
 			grpsiz = ix - ixs;
+			shortest_line = UINT_MAX;
 
 			/*
 			 * If the line before the current change group, is equal to
@@ -478,6 +486,10 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 			 * the group.
 			 */
 			while (ix < nrec && recs_match(recs, ixs, ix, flags)) {
+				int l = line_length(recs[ix]->ptr);
+				if (l < shortest_line)
+					shortest_line = l;
+
 				rchg[ixs++] = 0;
 				rchg[ix++] = 1;
 
@@ -504,6 +516,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_SHORTEST_LINE_HEURISTIC)) {
+			while (ixs > 0 &&
+			       line_length(recs[ix - 1]->ptr) > shortest_line &&
+			       recs_match(recs, ixs - 1, ix - 1, flags)) {
+				rchg[--ixs] = 1;
+				rchg[--ix] = 0;
+			}
+		}
 	}
 
 	return 0;
-- 
2.8.1.189.gd13d43c

Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic

[Jacob Keller]

On Fri, Apr 15, 2016 at 4:01 PM, Stefan Beller <sbeller@google.com> wrote:
> 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
>
> ...
> +/*
> + *
> + *
> + */
> +
>  /*
> ...
>
> Original discussion and testing found the following heuristic to be
> producing 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. When
> implementing this heuristic the handling of empty lines was awkward as
> it is unclear what an empty line is. ('\n' or do we include "\r\n" as it
> is common on Windows?) Instead we implement a slightly different heuristic:
>
>   If there are diff chunks which can be shifted around, find the shortest
>   line in the overlapping parts. Use the line with the shortest length that
>   occurs last as the last line of the chunk with the rest
>   of the context above.
>
> 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(?)
>

There's a few places that will need cleaning up (comments and such)
that mention empty line still, but that's not surprising. I am going
to test this for a bit on my local repos, and see if it makes any
difference to the old heuristic as well.

Thanks,
Jake

> Signed-off-by: Stefan Beller <sbeller@google.com>
> Signed-off-by: Jacob Keller <jacob.e.keller@intel.com>
> Signed-off-by: Stefan Beller <sbeller@google.com>
> ---
>  Documentation/diff-config.txt  |  6 ++++++
>  Documentation/diff-options.txt |  6 ++++++
>  diff.c                         | 11 +++++++++++
>  xdiff/xdiff.h                  |  2 ++
>  xdiff/xdiffi.c                 | 29 +++++++++++++++++++++++++++++
>  5 files changed, 54 insertions(+)
>
> diff --git a/Documentation/diff-config.txt b/Documentation/diff-config.txt
> index edba565..3d99a90 100644
> --- a/Documentation/diff-config.txt
> +++ b/Documentation/diff-config.txt
> @@ -170,6 +170,12 @@ diff.tool::
>
>  include::mergetools-diff.txt[]
>
> +diff.shortestLineHeuristic::
> +       Set this option to true to enable the shortest line chunk heuristic when
> +       producing diff output. This heuristic will attempt to shift hunks such
> +       that the last shortest common 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 4b0318e..b1ca83d 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[]
>
> +--shortest-line-heuristic::
> +--no-shortest-line-heuristic::
> +       When possible, shift common shortest line in diff hunks below the hunk
> +       such that the last common shortest 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 4dfe660..a02aff9 100644
> --- a/diff.c
> +++ b/diff.c
> @@ -26,6 +26,7 @@
>  #endif
>
>  static int diff_detect_rename_default;
> +static int diff_shortest_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.shortestlineheuristic")) {
> +               diff_shortest_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_shortest_line_heuristic)
> +               DIFF_XDL_SET(options, SHORTEST_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, "--shortest-line-heuristic"))
> +               DIFF_XDL_SET(options, SHORTEST_LINE_HEURISTIC);
> +       else if (!strcmp(arg, "--no-shortest-line-heuristic"))
> +               DIFF_XDL_CLR(options, SHORTEST_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 4fb7e79..e1f8ec0 100644
> --- a/xdiff/xdiff.h
> +++ b/xdiff/xdiff.h
> @@ -41,6 +41,8 @@ extern "C" {
>
>  #define XDF_IGNORE_BLANK_LINES (1 << 7)
>
> +#define XDF_SHORTEST_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 748eeb9..7d15b26 100644
> --- a/xdiff/xdiffi.c
> +++ b/xdiff/xdiffi.c
> @@ -400,6 +400,12 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,
>  }
>
>
> +static int line_length(const char *recs)
> +{
> +       char *s = strchr(recs, '\n');
> +       return s ? s - recs : strlen(recs);
> +}
> +
>  static int recs_match(xrecord_t **recs, long ixs, long ix, long flags)
>  {
>         return (recs[ixs]->ha == recs[ix]->ha &&
> @@ -411,6 +417,7 @@ static int recs_match(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 shortest_line;
>         xrecord_t **recs = xdf->recs;
>
>         /*
> @@ -444,6 +451,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
>
>                 do {
>                         grpsiz = ix - ixs;
> +                       shortest_line = UINT_MAX;
>
>                         /*
>                          * If the line before the current change group, is equal to
> @@ -478,6 +486,10 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
>                          * the group.
>                          */
>                         while (ix < nrec && recs_match(recs, ixs, ix, flags)) {
> +                               int l = line_length(recs[ix]->ptr);
> +                               if (l < shortest_line)
> +                                       shortest_line = l;
> +
>                                 rchg[ixs++] = 0;
>                                 rchg[ix++] = 1;
>
> @@ -504,6 +516,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_SHORTEST_LINE_HEURISTIC)) {
> +                       while (ixs > 0 &&
> +                              line_length(recs[ix - 1]->ptr) > shortest_line &&
> +                              recs_match(recs, ixs - 1, ix - 1, flags)) {
> +                               rchg[--ixs] = 1;
> +                               rchg[--ix] = 0;
> +                       }
> +               }
>         }
>
>         return 0;
> --
> 2.8.1.189.gd13d43c
>

Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic

[Jacob Keller]

On Fri, Apr 15, 2016 at 4:05 PM, Jacob Keller <jacob.keller@gmail.com> wrote:
> There's a few places that will need cleaning up (comments and such)
> that mention empty line still, but that's not surprising. I am going
> to test this for a bit on my local repos, and see if it makes any
> difference to the old heuristic as well.
>
> Thanks,
> Jake
>

I ran this heuristic on git.git and it produces tons of false positive
transforms which are much lease readable (to me at least), far more
than those produced by the newline/blank link heuristic did.

I think we should stick with the empty line heuristic instead of this
version, even if it's easier to implement this version.

We still would need to figure out how to handle CRLF properly but it's
worth resolving that than this heuristic is.

Thanks,
Jake

Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic

[Stefan Beller]

On Fri, Apr 15, 2016 at 4:32 PM, Jacob Keller <jacob.keller@gmail.com> wrote:
> On Fri, Apr 15, 2016 at 4:05 PM, Jacob Keller <jacob.keller@gmail.com> wrote:
>> There's a few places that will need cleaning up (comments and such)
>> that mention empty line still, but that's not surprising. I am going
>> to test this for a bit on my local repos, and see if it makes any
>> difference to the old heuristic as well.
>>
>> Thanks,
>> Jake
>>
>
> I ran this heuristic on git.git and it produces tons of false positive
> transforms which are much lease readable (to me at least), far more
> than those produced by the newline/blank link heuristic did.
>
> I think we should stick with the empty line heuristic instead of this
> version, even if it's easier to implement this version.

I agree. The heuristic is worse as we often have these 50:50 chances
of messing stuff up.

>
> We still would need to figure out how to handle CRLF properly but it's
> worth resolving that than this heuristic is.
>
> Thanks,
> Jake

Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic

[Junio C Hamano]

Stefan Beller <sbeller@google.com> writes:

> +static int line_length(const char *recs)
> +{
> +	char *s = strchr(recs, '\n');
> +	return s ? s - recs : strlen(recs);
> +}

It seems that you guys are discarding this "number of bytes on a
line, no matter what these bytes are" idea, so this may be moot, but
is there a guarantee that reading through recs until you happen to
see a NUL is safe?

Shouldn't the code that accesses a "line" be using the same "from
here to there", i.e. recs[]->ptr, recs[]->size, interface to avoid
having to scan the underlying string in an unbounded way?

Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic

[Stefan Beller]

On Fri, Apr 15, 2016 at 5:49 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Stefan Beller <sbeller@google.com> writes:
>
>> +static int line_length(const char *recs)
>> +{
>> +     char *s = strchr(recs, '\n');
>> +     return s ? s - recs : strlen(recs);
>> +}
>
> It seems that you guys are discarding this "number of bytes on a
> line, no matter what these bytes are" idea, so this may be moot, but
> is there a guarantee that reading through recs until you happen to
> see a NUL is safe?

We discarded this idea as it produces to many errors.
(We'd be back at the 50:50 case, "is it really worth it?")

We will go back to the "empty line" heuristic, which will be solved
via xdl_blankline(rec[i]->ptr, rec[i]->size, flags); which could be inlined.
That will solve the CRLF issue as a CR is covered as a whitespace
(with CRLF you'd have to specify diff to ignore white spaces).

For the safety I assumed
* there is always a \n even on the last line by convention.
* in case it is not, the string is null terminated, hence
  strchr and strlen for the rescue.

>
> Shouldn't the code that accesses a "line" be using the same "from
> here to there", i.e. recs[]->ptr, recs[]->size, interface to avoid
> having to scan the underlying string in an unbounded way?

xdl_blankline will use ->size, so we'll be holding it right.

Thanks,
Stefan

>
>

Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic

[Jacob Keller]

On Fri, Apr 15, 2016 at 5:49 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Stefan Beller <sbeller@google.com> writes:
>
>> +static int line_length(const char *recs)
>> +{
>> +     char *s = strchr(recs, '\n');
>> +     return s ? s - recs : strlen(recs);
>> +}
>
> It seems that you guys are discarding this "number of bytes on a
> line, no matter what these bytes are" idea, so this may be moot, but
> is there a guarantee that reading through recs until you happen to
> see a NUL is safe?
>
> Shouldn't the code that accesses a "line" be using the same "from
> here to there", i.e. recs[]->ptr, recs[]->size, interface to avoid
> having to scan the underlying string in an unbounded way?
>
>

I think we're going to make use of xdl_blankline instead of this or
our own "is_emptyline"

Thanks,
Jake

Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic

[Junio C Hamano]

Jacob Keller <jacob.keller@gmail.com> writes:

> I think we're going to make use of xdl_blankline instead of this or
> our own "is_emptyline"

OK, so perhaps either of you two can do a final version people can
start having fun with?

By the way, I really do not want to see something this low-level to
be end-user tweakable with "one bit enable/disable"; the end users
shouldn't have to bother [1].  I left it in but renamed after "what"
it enables/disables, not "how" the enabled thing works, to clarify
that we have this only as a developers' aid.

*1* I am fine with --compaction-heuristic=(shortest|blank|...) that
allows a choice among many as a developers' aid, but I do not think
this topic is there yet.

 Documentation/diff-config.txt  |  9 ++++-----
 Documentation/diff-options.txt | 10 +++++-----
 diff.c                         | 18 +++++++++---------
 xdiff/xdiff.h                  |  2 +-
 xdiff/xdiffi.c                 | 22 ++++++++++------------
 5 files changed, 29 insertions(+), 32 deletions(-)

diff --git a/Documentation/diff-config.txt b/Documentation/diff-config.txt
index c62745b..9bf3e92 100644
--- a/Documentation/diff-config.txt
+++ b/Documentation/diff-config.txt
@@ -166,11 +166,10 @@ diff.tool::
 
 include::mergetools-diff.txt[]
 
-diff.shortestLineHeuristic::
-	Set this option to true to enable the shortest line chunk heuristic when
-	producing diff output. This heuristic will attempt to shift hunks such
-	that the last shortest common line occurs below the hunk with the rest of
-	the context above it.
+diff.compactionHeuristic::
+	Set this option to enable an experimental heuristic that
+	shifts the hunk boundary in an attempt to make the resulting
+	patch easier to read.
 
 diff.algorithm::
 	Choose a diff algorithm.  The variants are as follows:
diff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt
index 238f39c..b513023 100644
--- a/Documentation/diff-options.txt
+++ b/Documentation/diff-options.txt
@@ -63,11 +63,11 @@ ifndef::git-format-patch[]
 	Synonym for `-p --raw`.
 endif::git-format-patch[]
 
---shortest-line-heuristic::
---no-shortest-line-heuristic::
-	When possible, shift common shortest line in diff hunks below the hunk
-	such that the last common shortest line for each hunk is below, with the
-	rest of the context above the hunk.
+--compaction-heuristic::
+--no-compaction-heuristic::
+	These are to help debugging and tuning an experimental
+	heuristic that shifts the hunk boundary in an attempt to
+	make the resulting patch easier to read.
 
 --minimal::
 	Spend extra time to make sure the smallest possible
diff --git a/diff.c b/diff.c
index 276174c..02c75c3 100644
--- a/diff.c
+++ b/diff.c
@@ -25,7 +25,7 @@
 #endif
 
 static int diff_detect_rename_default;
-static int diff_shortest_line_heuristic = 0;
+static int diff_compaction_heuristic = 1;
 static int diff_rename_limit_default = 400;
 static int diff_suppress_blank_empty;
 static int diff_use_color_default = -1;
@@ -184,8 +184,8 @@ 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.shortestlineheuristic")) {
-		diff_shortest_line_heuristic = git_config_bool(var, value);
+	if (!strcmp(var, "diff.compactionheuristic")) {
+		diff_compaction_heuristic = git_config_bool(var, value);
 		return 0;
 	}
 	if (!strcmp(var, "diff.autorefreshindex")) {
@@ -3240,8 +3240,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_shortest_line_heuristic)
-		DIFF_XDL_SET(options, SHORTEST_LINE_HEURISTIC);
+	if (diff_compaction_heuristic)
+		DIFF_XDL_SET(options, COMPACTION_HEURISTIC);
 
 	options->orderfile = diff_order_file_cfg;
 
@@ -3719,10 +3719,10 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac)
 		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, "--shortest-line-heuristic"))
-		DIFF_XDL_SET(options, SHORTEST_LINE_HEURISTIC);
-	else if (!strcmp(arg, "--no-shortest-line-heuristic"))
-		DIFF_XDL_CLR(options, SHORTEST_LINE_HEURISTIC);
+	else if (!strcmp(arg, "--compaction-heuristic"))
+		DIFF_XDL_SET(options, COMPACTION_HEURISTIC);
+	else if (!strcmp(arg, "--no-compaction-heuristic"))
+		DIFF_XDL_CLR(options, COMPACTION_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 968ac62..d1dbb27 100644
--- a/xdiff/xdiff.h
+++ b/xdiff/xdiff.h
@@ -41,7 +41,7 @@ extern "C" {
 
 #define XDF_IGNORE_BLANK_LINES (1 << 7)
 
-#define XDF_SHORTEST_LINE_HEURISTIC (1 << 8)
+#define XDF_COMPACTION_HEURISTIC (1 << 8)
 
 #define XDL_EMIT_FUNCNAMES (1 << 0)
 #define XDL_EMIT_COMMON (1 << 1)
diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
index 7d15b26..1ec46e0 100644
--- a/xdiff/xdiffi.c
+++ b/xdiff/xdiffi.c
@@ -400,10 +400,9 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,
 }
 
 
-static int line_length(const char *recs)
+static int is_blank_line(xrecord_t **recs, long ix, long flags)
 {
-	char *s = strchr(recs, '\n');
-	return s ? s - recs : strlen(recs);
+	return xdl_blankline(recs[ix]->ptr, recs[ix]->size, flags);
 }
 
 static int recs_match(xrecord_t **recs, long ixs, long ix, long flags)
@@ -417,7 +416,7 @@ static int recs_match(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 shortest_line;
+	unsigned int blank_lines;
 	xrecord_t **recs = xdf->recs;
 
 	/*
@@ -451,7 +450,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 
 		do {
 			grpsiz = ix - ixs;
-			shortest_line = UINT_MAX;
+			blank_lines = 0;
 
 			/*
 			 * If the line before the current change group, is equal to
@@ -486,9 +485,8 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 			 * the group.
 			 */
 			while (ix < nrec && recs_match(recs, ixs, ix, flags)) {
-				int l = line_length(recs[ix]->ptr);
-				if (l < shortest_line)
-					shortest_line = l;
+
+				blank_lines += is_blank_line(recs, ix, flags);
 
 				rchg[ixs++] = 0;
 				rchg[ix++] = 1;
@@ -519,15 +517,15 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 
 		/*
 		 * 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.
+		 * blank line in the moving space. If there is a blank line,
+		 * make sure the last blank 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_SHORTEST_LINE_HEURISTIC)) {
+		if ((flags & XDF_COMPACTION_HEURISTIC)) {
 			while (ixs > 0 &&
-			       line_length(recs[ix - 1]->ptr) > shortest_line &&
+			       !is_blank_line(recs, ix - 1, flags) &&
 			       recs_match(recs, ixs - 1, ix - 1, flags)) {
 				rchg[--ixs] = 1;
 				rchg[--ix] = 0;
-- 
2.8.1-399-g96b3b3a

Re: [PATCH 2/2] xdiff: implement empty line chunk heuristic

[Stefan Beller]

On Mon, Apr 18, 2016 at 12:22 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Jacob Keller <jacob.keller@gmail.com> writes:
>
>> I think we're going to make use of xdl_blankline instead of this or
>> our own "is_emptyline"
>
> OK, so perhaps either of you two can do a final version people can
> start having fun with?

Junios proposal seems to be on top of my latest series sent out,
I'll squash it in and send it out as a final version if you don't mind
(though I'll do it later today; currently diving into Gerrits Java)

>
> By the way, I really do not want to see something this low-level to
> be end-user tweakable with "one bit enable/disable"; the end users
> shouldn't have to bother [1].

Ok. Thanks for fixing that mistake.

> I left it in but renamed after "what"
> it enables/disables, not "how" the enabled thing works, to clarify
> that we have this only as a developers' aid.


>
> *1* I am fine with --compaction-heuristic=(shortest|blank|...) that
> allows a choice among many as a developers' aid, but I do not think
> this topic is there yet.

This doesn't bode well with
    > +--compaction-heuristic::
    > +--no-compaction-heuristic::

in the future? I'd rather have
    +--compaction-heuristic=none
    +--compaction-heuristic=lastEmptyLine
such that we don't have to worry about further experiments (or matured
heuristics) later?

[PATCH 1/2] xdiff: add recs_match helper function

[Stefan Beller]

From: Jacob Keller <jacob.keller@gmail.com>

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 recs_match which performs both checks to increase
code readability.

Signed-off-by: Jacob Keller <jacob.e.keller@intel.com>
Signed-off-by: Stefan Beller <sbeller@google.com>
---
 xdiff/xdiffi.c | 14 ++++++++++----
 1 file changed, 10 insertions(+), 4 deletions(-)

diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
index 2358a2d..748eeb9 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 recs_match(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 && recs_match(recs, ixs - 1, ix - 1, flags)) {
 				rchg[--ixs] = 1;
 				rchg[--ix] = 0;
 
@@ -470,8 +477,7 @@ 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 && recs_match(recs, ixs, ix, flags)) {
 				rchg[ixs++] = 0;
 				rchg[ix++] = 1;
 
-- 
2.8.0.26.gba39a1b.dirty

[PATCH 1/2] xdiff: add recs_match helper function

[Stefan Beller]

From: Jacob Keller <jacob.keller@gmail.com>

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 recs_match which performs both checks to increase
code readability.

Signed-off-by: Jacob Keller <jacob.e.keller@intel.com>
Signed-off-by: Stefan Beller <sbeller@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 xdiff/xdiffi.c | 14 ++++++++++----
 1 file changed, 10 insertions(+), 4 deletions(-)

diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
index 2358a2d..748eeb9 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 recs_match(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 && recs_match(recs, ixs - 1, ix - 1, flags)) {
 				rchg[--ixs] = 1;
 				rchg[--ix] = 0;
 
@@ -470,8 +477,7 @@ 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 && recs_match(recs, ixs, ix, flags)) {
 				rchg[ixs++] = 0;
 				rchg[ix++] = 1;
 
-- 
2.4.11.2.g96ed4e5.dirty