[RFC PATCH, WAS: "weird diff output?"] Implement better chunk heuristics.

[Stefan Beller <sbeller@google.com>]

TODO(sbeller):
* describe the discussion on why this is better
* see if this can be tested?

Signed-off-by: Stefan Beller <sbeller@google.com>
---
 xdiff/xdiffi.c | 39 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 39 insertions(+)

diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
index 2358a2d..24eb9a0 100644
--- a/xdiff/xdiffi.c
+++ b/xdiff/xdiffi.c
@@ -400,9 +400,16 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,
 }
 
 
+static int starts_with_emptyline(const char *recs)
+{
+	return recs[0] == '\n'; /* CRLF not covered here */
+}
+
+
 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;
 	xrecord_t **recs = xdf->recs;
 
 	/*
@@ -436,6 +443,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 
 		do {
 			grpsiz = ix - ixs;
+			has_emptyline = 0;
 
 			/*
 			 * If the line before the current change group, is equal to
@@ -447,6 +455,8 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 				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
@@ -475,6 +485,9 @@ 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
@@ -498,6 +511,32 @@ 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 (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)) {
+				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]);
+				 */
+			}
+		}
 	}
 
 	return 0;
-- 
2.8.1.474.gffdc890.dirty