xdiff: upgrade to core git 2.4.5

Upgrade xdiff to version used in core git 2.4.5 (0df0541).

Corrects an issue where an LF is added at EOF while applying
an unrelated change (ba31180), cleans up some unused code (be89977 and
e5b0662), and provides an improved callback to avoid leaking internal
(to xdiff) structures (467d348).

This also adds some additional functionality that we do not yet take
advantage of, namely the ability to ignore changes whose lines are
all blank (36617af).

12 files changed, 137 insertions, 76 deletions

diff --git a/src/blame_git.c b/src/blame_git.c
index e863efe2e..f481426aa 100644
--- a/src/blame_git.c
+++ b/src/blame_git.c
@@ -304,21 +304,16 @@ static void blame_chunk(
 }
 
 static int my_emit(
-		xdfenv_t *xe,
-		xdchange_t *xscr,
-		xdemitcb_t *ecb,
-		xdemitconf_t const *xecfg)
+	long start_a, long count_a,
+	long start_b, long count_b,
+	void *cb_data)
 {
-	xdchange_t *xch = xscr;
-	GIT_UNUSED(xe);
-	GIT_UNUSED(xecfg);
-	while (xch) {
-		blame_chunk_cb_data *d = ecb->priv;
-		blame_chunk(d->blame, d->tlno, d->plno, xch->i2, d->target, d->parent);
-		d->plno = xch->i1 + xch->chg1;
-		d->tlno = xch->i2 + xch->chg2;
-		xch = xch->next;
-	}
+	blame_chunk_cb_data *d = (blame_chunk_cb_data *)cb_data;
+
+	blame_chunk(d->blame, d->tlno, d->plno, start_b, d->target, d->parent);
+	d->plno = start_a + count_a;
+	d->tlno = start_b + count_b;
+	
 	return 0;
 }
 
@@ -352,7 +347,7 @@ static int diff_hunks(mmfile_t file_a, mmfile_t file_b, void *cb_data)
 	xdemitconf_t xecfg = {0};
 	xdemitcb_t ecb = {0};
 
-	xecfg.emit_func = (void(*)(void))my_emit;
+	xecfg.hunk_func = my_emit;
 	ecb.priv = cb_data;
 
 	trim_common_tail(&file_a, &file_b, 0);
diff --git a/src/xdiff/xdiff.h b/src/xdiff/xdiff.h
index cb8b235b5..e2f1e892b 100644
--- a/src/xdiff/xdiff.h
+++ b/src/xdiff/xdiff.h
@@ -32,14 +32,14 @@ extern "C" {
 #define XDF_IGNORE_WHITESPACE (1 << 2)
 #define XDF_IGNORE_WHITESPACE_CHANGE (1 << 3)
 #define XDF_IGNORE_WHITESPACE_AT_EOL (1 << 4)
+#define XDF_WHITESPACE_FLAGS (XDF_IGNORE_WHITESPACE | XDF_IGNORE_WHITESPACE_CHANGE | XDF_IGNORE_WHITESPACE_AT_EOL)
+
 #define XDF_PATIENCE_DIFF (1 << 5)
 #define XDF_HISTOGRAM_DIFF (1 << 6)
-#define XDF_WHITESPACE_FLAGS (XDF_IGNORE_WHITESPACE | XDF_IGNORE_WHITESPACE_CHANGE | XDF_IGNORE_WHITESPACE_AT_EOL)
+#define XDF_DIFF_ALGORITHM_MASK (XDF_PATIENCE_DIFF | XDF_HISTOGRAM_DIFF)
+#define XDF_DIFF_ALG(x) ((x) & XDF_DIFF_ALGORITHM_MASK)
 
-#define XDL_PATCH_NORMAL '-'
-#define XDL_PATCH_REVERSE '+'
-#define XDL_PATCH_MODEMASK ((1 << 8) - 1)
-#define XDL_PATCH_IGNOREBSPACE (1 << 8)
+#define XDF_IGNORE_BLANK_LINES (1 << 7)
 
 #define XDL_EMIT_FUNCNAMES (1 << 0)
 #define XDL_EMIT_COMMON (1 << 1)
@@ -88,13 +88,17 @@ typedef struct s_xdemitcb {
 
 typedef long (*find_func_t)(const char *line, long line_len, char *buffer, long buffer_size, void *priv);
 
+typedef int (*xdl_emit_hunk_consume_func_t)(long start_a, long count_a,
+					    long start_b, long count_b,
+					    void *cb_data);
+
 typedef struct s_xdemitconf {
 	long ctxlen;
 	long interhunkctxlen;
 	unsigned long flags;
 	find_func_t find_func;
 	void *find_func_priv;
-	void (*emit_func)(void);
+	xdl_emit_hunk_consume_func_t hunk_func;
 } xdemitconf_t;
 
 typedef struct s_bdiffparam {
diff --git a/src/xdiff/xdiffi.c b/src/xdiff/xdiffi.c
index 84aa0fcfe..2358a2d63 100644
--- a/src/xdiff/xdiffi.c
+++ b/src/xdiff/xdiffi.c
@@ -328,10 +328,10 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
 	xdalgoenv_t xenv;
 	diffdata_t dd1, dd2;
 
-	if (xpp->flags & XDF_PATIENCE_DIFF)
+	if (XDF_DIFF_ALG(xpp->flags) == XDF_PATIENCE_DIFF)
 		return xdl_do_patience_diff(mf1, mf2, xpp, xe);
 
-	if (xpp->flags & XDF_HISTOGRAM_DIFF)
+	if (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF)
 		return xdl_do_histogram_diff(mf1, mf2, xpp, xe);
 
 	if (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) {
@@ -394,6 +394,7 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,
 	xch->i2 = i2;
 	xch->chg1 = chg1;
 	xch->chg2 = chg2;
+	xch->ignore = 0;
 
 	return xch;
 }
@@ -538,13 +539,49 @@ void xdl_free_script(xdchange_t *xscr) {
 	}
 }
 
+static int xdl_call_hunk_func(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
+			      xdemitconf_t const *xecfg)
+{
+	xdchange_t *xch, *xche;
+
+	for (xch = xscr; xch; xch = xche->next) {
+		xche = xdl_get_hunk(&xch, xecfg);
+		if (!xch)
+			break;
+		if (xecfg->hunk_func(xch->i1, xche->i1 + xche->chg1 - xch->i1,
+				     xch->i2, xche->i2 + xche->chg2 - xch->i2,
+				     ecb->priv) < 0)
+			return -1;
+	}
+	return 0;
+}
+
+static void xdl_mark_ignorable(xdchange_t *xscr, xdfenv_t *xe, long flags)
+{
+	xdchange_t *xch;
+
+	for (xch = xscr; xch; xch = xch->next) {
+		int ignore = 1;
+		xrecord_t **rec;
+		long i;
+
+		rec = &xe->xdf1.recs[xch->i1];
+		for (i = 0; i < xch->chg1 && ignore; i++)
+			ignore = xdl_blankline(rec[i]->ptr, rec[i]->size, flags);
+
+		rec = &xe->xdf2.recs[xch->i2];
+		for (i = 0; i < xch->chg2 && ignore; i++)
+			ignore = xdl_blankline(rec[i]->ptr, rec[i]->size, flags);
+
+		xch->ignore = ignore;
+	}
+}
 
 int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
 	     xdemitconf_t const *xecfg, xdemitcb_t *ecb) {
 	xdchange_t *xscr;
 	xdfenv_t xe;
-	emit_func_t ef = xecfg->emit_func ?
-		(emit_func_t)xecfg->emit_func : xdl_emit_diff;
+	emit_func_t ef = xecfg->hunk_func ? xdl_call_hunk_func : xdl_emit_diff;
 
 	if (xdl_do_diff(mf1, mf2, xpp, &xe) < 0) {
 
@@ -558,6 +595,9 @@ int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
 		return -1;
 	}
 	if (xscr) {
+		if (xpp->flags & XDF_IGNORE_BLANK_LINES)
+			xdl_mark_ignorable(xscr, &xe, xpp->flags);
+
 		if (ef(&xe, xscr, ecb, xecfg) < 0) {
 
 			xdl_free_script(xscr);
diff --git a/src/xdiff/xdiffi.h b/src/xdiff/xdiffi.h
index 7a92ea9c4..8b81206c9 100644
--- a/src/xdiff/xdiffi.h
+++ b/src/xdiff/xdiffi.h
@@ -41,6 +41,7 @@ typedef struct s_xdchange {
 	struct s_xdchange *next;
 	long i1, i2;
 	long chg1, chg2;
+	int ignore;
 } xdchange_t;
 
 
diff --git a/src/xdiff/xemit.c b/src/xdiff/xemit.c
index e3e63d902..750a97294 100644
--- a/src/xdiff/xemit.c
+++ b/src/xdiff/xemit.c
@@ -56,16 +56,51 @@ static int xdl_emit_record(xdfile_t *xdf, long ri, char const *pre, xdemitcb_t *
 /*
  * Starting at the passed change atom, find the latest change atom to be included
  * inside the differential hunk according to the specified configuration.
+ * Also advance xscr if the first changes must be discarded.
  */
-xdchange_t *xdl_get_hunk(xdchange_t *xscr, xdemitconf_t const *xecfg) {
-	xdchange_t *xch, *xchp;
+xdchange_t *xdl_get_hunk(xdchange_t **xscr, xdemitconf_t const *xecfg)
+{
+	xdchange_t *xch, *xchp, *lxch;
 	long max_common = 2 * xecfg->ctxlen + xecfg->interhunkctxlen;
+	long max_ignorable = xecfg->ctxlen;
+	unsigned long ignored = 0; /* number of ignored blank lines */
+
+	/* remove ignorable changes that are too far before other changes */
+	for (xchp = *xscr; xchp && xchp->ignore; xchp = xchp->next) {
+		xch = xchp->next;
+
+		if (xch == NULL ||
+		    xch->i1 - (xchp->i1 + xchp->chg1) >= max_ignorable)
+			*xscr = xch;
+	}
+
+	if (*xscr == NULL)
+		return NULL;
+
+	lxch = *xscr;
 
-	for (xchp = xscr, xch = xscr->next; xch; xchp = xch, xch = xch->next)
-		if (xch->i1 - (xchp->i1 + xchp->chg1) > max_common)
+	for (xchp = *xscr, xch = xchp->next; xch; xchp = xch, xch = xch->next) {
+		long distance = xch->i1 - (xchp->i1 + xchp->chg1);
+		if (distance > max_common)
 			break;
 
-	return xchp;
+		if (distance < max_ignorable && (!xch->ignore || lxch == xchp)) {
+			lxch = xch;
+			ignored = 0;
+		} else if (distance < max_ignorable && xch->ignore) {
+			ignored += xch->chg2;
+		} else if (lxch != xchp &&
+			   xch->i1 + ignored - (lxch->i1 + lxch->chg1) > max_common) {
+			break;
+		} else if (!xch->ignore) {
+			lxch = xch;
+			ignored = 0;
+		} else {
+			ignored += xch->chg2;
+		}
+	}
+
+	return lxch;
 }
 
 
@@ -144,7 +179,9 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
 		return xdl_emit_common(xe, xscr, ecb, xecfg);
 
 	for (xch = xscr; xch; xch = xche->next) {
-		xche = xdl_get_hunk(xch, xecfg);
+		xche = xdl_get_hunk(&xch, xecfg);
+		if (!xch)
+			break;
 
 		s1 = XDL_MAX(xch->i1 - xecfg->ctxlen, 0);
 		s2 = XDL_MAX(xch->i2 - xecfg->ctxlen, 0);
diff --git a/src/xdiff/xemit.h b/src/xdiff/xemit.h
index c2e2e8302..d29710770 100644
--- a/src/xdiff/xemit.h
+++ b/src/xdiff/xemit.h
@@ -27,7 +27,7 @@
 typedef int (*emit_func_t)(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
 			   xdemitconf_t const *xecfg);
 
-xdchange_t *xdl_get_hunk(xdchange_t *xscr, xdemitconf_t const *xecfg);
+xdchange_t *xdl_get_hunk(xdchange_t **xscr, xdemitconf_t const *xecfg);
 int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
 		  xdemitconf_t const *xecfg);
 
diff --git a/src/xdiff/xhistogram.c b/src/xdiff/xhistogram.c
index c84812893..500d8112a 100644
--- a/src/xdiff/xhistogram.c
+++ b/src/xdiff/xhistogram.c
@@ -258,7 +258,7 @@ static int fall_back_to_classic_diff(struct histindex *index,
 		int line1, int count1, int line2, int count2)
 {
 	xpparam_t xpp;
-	xpp.flags = index->xpp->flags & ~XDF_HISTOGRAM_DIFF;
+	xpp.flags = index->xpp->flags & ~XDF_DIFF_ALGORITHM_MASK;
 
 	return xdl_fall_back_diff(index->env, &xpp,
 				  line1, count1, line2, count2);
diff --git a/src/xdiff/xmerge.c b/src/xdiff/xmerge.c
index 84e424672..b11e59817 100644
--- a/src/xdiff/xmerge.c
+++ b/src/xdiff/xmerge.c
@@ -245,11 +245,11 @@ static int xdl_fill_merge_buffer(xdfenv_t *xe1, const char *name1,
 					      dest ? dest + size : NULL);
 			/* Postimage from side #1 */
 			if (m->mode & 1)
-				size += xdl_recs_copy(xe1, m->i1, m->chg1, 1,
+				size += xdl_recs_copy(xe1, m->i1, m->chg1, (m->mode & 2),
 						      dest ? dest + size : NULL);
 			/* Postimage from side #2 */
 			if (m->mode & 2)
-				size += xdl_recs_copy(xe2, m->i2, m->chg2, 1,
+				size += xdl_recs_copy(xe2, m->i2, m->chg2, 0,
 						      dest ? dest + size : NULL);
 		} else
 			continue;
diff --git a/src/xdiff/xpatience.c b/src/xdiff/xpatience.c
index fdd7d0263..04e1a1ab2 100644
--- a/src/xdiff/xpatience.c
+++ b/src/xdiff/xpatience.c
@@ -288,7 +288,7 @@ static int fall_back_to_classic_diff(struct hashmap *map,
 		int line1, int count1, int line2, int count2)
 {
 	xpparam_t xpp;
-	xpp.flags = map->xpp->flags & ~XDF_PATIENCE_DIFF;
+	xpp.flags = map->xpp->flags & ~XDF_DIFF_ALGORITHM_MASK;
 
 	return xdl_fall_back_diff(map->env, &xpp,
 				  line1, count1, line2, count2);
diff --git a/src/xdiff/xprepare.c b/src/xdiff/xprepare.c
index e419f4f72..63a22c630 100644
--- a/src/xdiff/xprepare.c
+++ b/src/xdiff/xprepare.c
@@ -181,7 +181,7 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_
 	if (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *))))
 		goto abort;
 
-	if (xpp->flags & XDF_HISTOGRAM_DIFF)
+	if (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF)
 		hbits = hsize = 0;
 	else {
 		hbits = xdl_hashbits((unsigned int) narec);
@@ -209,8 +209,8 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_
 			crec->ha = hav;
 			recs[nrec++] = crec;
 
-			if (!(xpp->flags & XDF_HISTOGRAM_DIFF) &&
-				xdl_classify_record(pass, cf, rhash, hbits, crec) < 0)
+			if ((XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) &&
+			    xdl_classify_record(pass, cf, rhash, hbits, crec) < 0)
 				goto abort;
 		}
 	}
@@ -273,16 +273,15 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
 	 * (nrecs) will be updated correctly anyway by
 	 * xdl_prepare_ctx().
 	 */
-	sample = xpp->flags & XDF_HISTOGRAM_DIFF ? XDL_GUESS_NLINES2 : XDL_GUESS_NLINES1;
+	sample = (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF
+		  ? XDL_GUESS_NLINES2 : XDL_GUESS_NLINES1);
 
 	enl1 = xdl_guess_lines(mf1, sample) + 1;
 	enl2 = xdl_guess_lines(mf2, sample) + 1;
 
-	if (!(xpp->flags & XDF_HISTOGRAM_DIFF) &&
-		xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) {
-
+	if (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF &&
+	    xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0)
 		return -1;
-	}
 
 	if (xdl_prepare_ctx(1, mf1, enl1, xpp, &cf, &xe->xdf1) < 0) {
 
@@ -296,9 +295,9 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
 		return -1;
 	}
 
-	if (!(xpp->flags & XDF_PATIENCE_DIFF) &&
-			!(xpp->flags & XDF_HISTOGRAM_DIFF) &&
-			xdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) {
+	if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) &&
+	    (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) &&
+	    xdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) {
 
 		xdl_free_ctx(&xe->xdf2);
 		xdl_free_ctx(&xe->xdf1);
diff --git a/src/xdiff/xutils.c b/src/xdiff/xutils.c
index bb7bdee49..30f2a30ac 100644
--- a/src/xdiff/xutils.c
+++ b/src/xdiff/xutils.c
@@ -120,35 +120,6 @@ void *xdl_cha_alloc(chastore_t *cha) {
 	return data;
 }
 
-
-void *xdl_cha_first(chastore_t *cha) {
-	chanode_t *sncur;
-
-	if (!(cha->sncur = sncur = cha->head))
-		return NULL;
-
-	cha->scurr = 0;
-
-	return (char *) sncur + sizeof(chanode_t) + cha->scurr;
-}
-
-
-void *xdl_cha_next(chastore_t *cha) {
-	chanode_t *sncur;
-
-	if (!(sncur = cha->sncur))
-		return NULL;
-	cha->scurr += cha->isize;
-	if (cha->scurr == sncur->icurr) {
-		if (!(sncur = cha->sncur = sncur->next))
-			return NULL;
-		cha->scurr = 0;
-	}
-
-	return (char *) sncur + sizeof(chanode_t) + cha->scurr;
-}
-
-
 long xdl_guess_lines(mmfile_t *mf, long sample) {
 	long nl = 0, size, tsize = 0;
 	char const *data, *cur, *top;
@@ -170,6 +141,19 @@ long xdl_guess_lines(mmfile_t *mf, long sample) {
 	return nl + 1;
 }
 
+int xdl_blankline(const char *line, long size, long flags)
+{
+	long i;
+
+	if (!(flags & XDF_WHITESPACE_FLAGS))
+		return (size <= 1);
+
+	for (i = 0; i < size && XDL_ISSPACE(line[i]); i++)
+		;
+
+	return (i == size);
+}
+
 int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)
 {
 	int i1, i2;
diff --git a/src/xdiff/xutils.h b/src/xdiff/xutils.h
index 714719a89..8f952a8e6 100644
--- a/src/xdiff/xutils.h
+++ b/src/xdiff/xutils.h
@@ -34,6 +34,7 @@ void *xdl_cha_alloc(chastore_t *cha);
 void *xdl_cha_first(chastore_t *cha);
 void *xdl_cha_next(chastore_t *cha);
 long xdl_guess_lines(mmfile_t *mf, long sample);
+int xdl_blankline(const char *line, long size, long flags);
 int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags);
 unsigned long xdl_hash_record(char const **data, char const *top, long flags);
 unsigned int xdl_hashbits(unsigned int size);