Merge pull request #3299 from ethomson/xdiff_update

Don't add unnecessary trailing newline during file merge

14 files changed, 188 insertions, 86 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);
diff --git a/tests/merge/files.c b/tests/merge/files.c
index 7f461abff..2fd90d066 100644
--- a/tests/merge/files.c
+++ b/tests/merge/files.c
@@ -249,3 +249,42 @@ void test_merge_files__automerge_whitespace_change(void)
 
 	git_merge_file_result_free(&result);
 }
+
+void test_merge_files__doesnt_add_newline(void)
+{
+	git_merge_file_input ancestor = GIT_MERGE_FILE_INPUT_INIT,
+		ours = GIT_MERGE_FILE_INPUT_INIT,
+		theirs = GIT_MERGE_FILE_INPUT_INIT;
+	git_merge_file_options opts = GIT_MERGE_FILE_OPTIONS_INIT;
+	git_merge_file_result result = {0};
+	const char *expected = "Zero\n1\n2\n3\n4\n5 XXX\n6 YYY\n7\n8\n9\nTen";
+
+	ancestor.ptr = "0\n1\n2\n3\n4\n5 XXX\n6YYY\n7\n8\n9\n10";
+	ancestor.size = strlen(ancestor.ptr);
+	ancestor.path = "testfile.txt";
+	ancestor.mode = 0100755;
+
+	ours.ptr = "Zero\n1\n2\n3\n4\n5 XXX\n6 YYY\n7\n8\n9\n10";
+	ours.size = strlen(ours.ptr);
+	ours.path = "testfile.txt";
+	ours.mode = 0100755;
+
+	theirs.ptr = "0\n1\n2\n3\n4\n5 XXX\n6  YYY\n7\n8\n9\nTen";
+	theirs.size = strlen(theirs.ptr);
+	theirs.path = "testfile.txt";
+	theirs.mode = 0100755;
+
+	opts.flags |= GIT_MERGE_FILE_IGNORE_WHITESPACE_CHANGE;
+	cl_git_pass(git_merge_file(&result, &ancestor, &ours, &theirs, &opts));
+
+	cl_assert_equal_i(1, result.automergeable);
+
+	cl_assert_equal_s("testfile.txt", result.path);
+	cl_assert_equal_i(0100755, result.mode);
+
+	cl_assert_equal_i(strlen(expected), result.len);
+	cl_assert_equal_strn(expected, result.ptr, result.len);
+
+	git_merge_file_result_free(&result);
+}
+
diff --git a/tests/revert/workdir.c b/tests/revert/workdir.c
index 7ccf0f937..9f83bd842 100644
--- a/tests/revert/workdir.c
+++ b/tests/revert/workdir.c
@@ -334,16 +334,18 @@ void test_revert_workdir__again_after_edit_two(void)
 	cl_assert(merge_test_index(repo_index, merge_index_entries, 3));
 
 	cl_git_pass(git_futils_readbuffer(&diff_buf, "revert/file.txt"));
-	cl_assert(strcmp(diff_buf.ptr,	"a\n" \
-		"<<<<<<< HEAD\n" \
-		"=======\n" \
-		"a\n" \
-		">>>>>>> parent of 97e52d5... Revert me\n" \
-		"a\n" \
-		"a\n" \
-		"a\n" \
-		"a\n" \
-		"ab\n") == 0);
+	cl_assert_equal_s(
+			"a\n" \
+			"<<<<<<< HEAD\n" \
+			"=======\n" \
+			"a\n" \
+			">>>>>>> parent of 97e52d5... Revert me\n" \
+			"a\n" \
+			"a\n" \
+			"a\n" \
+			"a\n" \
+			"ab",
+		diff_buf.ptr);
 
 	git_commit_free(revert_commit);
 	git_commit_free(head_commit);