Teach diff about -b and -w flags

This adds -b (--ignore-space-change) and -w (--ignore-all-space) flags to
diff. The main part of the patch is teaching libxdiff about it.

[jc: renamed xdl_line_match() to xdl_recmatch() since the former is used
 for different purposes in xpatchi.c which is in the parts of the upstream
 source we do not use.]

Signed-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>
Signed-off-by: Junio C Hamano <junkio@cox.net>

7 files changed, 71 insertions, 16 deletions

diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h
index 2540e8a2cc..2ce10b4c0d 100644
--- a/xdiff/xdiff.h
+++ b/xdiff/xdiff.h
@@ -29,6 +29,9 @@ extern "C" {
 
 
 #define XDF_NEED_MINIMAL (1 << 1)
+#define XDF_IGNORE_WHITESPACE (1 << 2)
+#define XDF_IGNORE_WHITESPACE_CHANGE (1 << 3)
+#define XDF_WHITESPACE_FLAGS (XDF_IGNORE_WHITESPACE | XDF_IGNORE_WHITESPACE_CHANGE)
 
 #define XDL_PATCH_NORMAL '-'
 #define XDL_PATCH_REVERSE '+'
diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
index b95ade2c1b..ed7ad2041c 100644
--- a/xdiff/xdiffi.c
+++ b/xdiff/xdiffi.c
@@ -45,7 +45,7 @@ static long xdl_split(unsigned long const *ha1, long off1, long lim1,
 		      long *kvdf, long *kvdb, int need_min, xdpsplit_t *spl,
 		      xdalgoenv_t *xenv);
 static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, long chg2);
-static int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo);
+static int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags);
 
 
 
@@ -397,7 +397,7 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,
 }
 
 
-static int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo) {
+static 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;
 	xrecord_t **recs = xdf->recs;
@@ -440,7 +440,7 @@ static int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo) {
 			 * the group.
 			 */
 			while (ixs > 0 && recs[ixs - 1]->ha == recs[ix - 1]->ha &&
-			       XDL_RECMATCH(recs[ixs - 1], recs[ix - 1])) {
+			       xdl_recmatch(recs[ixs - 1]->ptr, recs[ixs - 1]->size, recs[ix - 1]->ptr, recs[ix - 1]->size, flags)) {
 				rchg[--ixs] = 1;
 				rchg[--ix] = 0;
 
@@ -468,7 +468,7 @@ static int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo) {
 			 * the group.
 			 */
 			while (ix < nrec && recs[ixs]->ha == recs[ix]->ha &&
-			       XDL_RECMATCH(recs[ixs], recs[ix])) {
+			       xdl_recmatch(recs[ixs]->ptr, recs[ixs]->size, recs[ix]->ptr, recs[ix]->size, flags)) {
 				rchg[ixs++] = 0;
 				rchg[ix++] = 1;
 
@@ -546,8 +546,8 @@ int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
 
 		return -1;
 	}
-	if (xdl_change_compact(&xe.xdf1, &xe.xdf2) < 0 ||
-	    xdl_change_compact(&xe.xdf2, &xe.xdf1) < 0 ||
+	if (xdl_change_compact(&xe.xdf1, &xe.xdf2, xpp->flags) < 0 ||
+	    xdl_change_compact(&xe.xdf2, &xe.xdf1, xpp->flags) < 0 ||
 	    xdl_build_script(&xe, &xscr) < 0) {
 
 		xdl_free_env(&xe);
diff --git a/xdiff/xdiffi.h b/xdiff/xdiffi.h
index dd8f3c986b..d3b72716b5 100644
--- a/xdiff/xdiffi.h
+++ b/xdiff/xdiffi.h
@@ -55,6 +55,5 @@ void xdl_free_script(xdchange_t *xscr);
 int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
 		  xdemitconf_t const *xecfg);
 
-
 #endif /* #if !defined(XDIFFI_H) */
 
diff --git a/xdiff/xmacros.h b/xdiff/xmacros.h
index 78f02603b8..4c2fde80c1 100644
--- a/xdiff/xmacros.h
+++ b/xdiff/xmacros.h
@@ -33,7 +33,6 @@
 #define XDL_ISDIGIT(c) ((c) >= '0' && (c) <= '9')
 #define XDL_HASHLONG(v, b) (((unsigned long)(v) * GR_PRIME) >> ((CHAR_BIT * sizeof(unsigned long)) - (b)))
 #define XDL_PTRFREE(p) do { if (p) { xdl_free(p); (p) = NULL; } } while (0)
-#define XDL_RECMATCH(r1, r2) ((r1)->size == (r2)->size && memcmp((r1)->ptr, (r2)->ptr, (r1)->size) == 0)
 #define XDL_LE32_PUT(p, v) \
 do { \
 	unsigned char *__p = (unsigned char *) (p); \
diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c
index add5a75c77..1be7b31950 100644
--- a/xdiff/xprepare.c
+++ b/xdiff/xprepare.c
@@ -43,12 +43,13 @@ typedef struct s_xdlclassifier {
 	xdlclass_t **rchash;
 	chastore_t ncha;
 	long count;
+	long flags;
 } xdlclassifier_t;
 
 
 
 
-static int xdl_init_classifier(xdlclassifier_t *cf, long size);
+static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags);
 static void xdl_free_classifier(xdlclassifier_t *cf);
 static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned int hbits,
 			       xrecord_t *rec);
@@ -63,9 +64,11 @@ static int xdl_optimize_ctxs(xdfile_t *xdf1, xdfile_t *xdf2);
 
 
 
-static int xdl_init_classifier(xdlclassifier_t *cf, long size) {
+static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) {
 	long i;
 
+	cf->flags = flags;
+
 	cf->hbits = xdl_hashbits((unsigned int) size);
 	cf->hsize = 1 << cf->hbits;
 
@@ -103,8 +106,9 @@ static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned
 	line = rec->ptr;
 	hi = (long) XDL_HASHLONG(rec->ha, cf->hbits);
 	for (rcrec = cf->rchash[hi]; rcrec; rcrec = rcrec->next)
-		if (rcrec->ha == rec->ha && rcrec->size == rec->size &&
-		    !memcmp(line, rcrec->line, rec->size))
+		if (rcrec->ha == rec->ha &&
+				xdl_recmatch(rcrec->line, rcrec->size,
+					rec->ptr, rec->size, cf->flags))
 			break;
 
 	if (!rcrec) {
@@ -173,7 +177,7 @@ static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,
 				top = blk + bsize;
 			}
 			prev = cur;
-			hav = xdl_hash_record(&cur, top);
+			hav = xdl_hash_record(&cur, top, xpp->flags);
 			if (nrec >= narec) {
 				narec *= 2;
 				if (!(rrecs = (xrecord_t **) xdl_realloc(recs, narec * sizeof(xrecord_t *)))) {
@@ -268,7 +272,7 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
 	enl1 = xdl_guess_lines(mf1) + 1;
 	enl2 = xdl_guess_lines(mf2) + 1;
 
-	if (xdl_init_classifier(&cf, enl1 + enl2 + 1) < 0) {
+	if (xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) {
 
 		return -1;
 	}
diff --git a/xdiff/xutils.c b/xdiff/xutils.c
index f91b403475..f7bdd395ad 100644
--- a/xdiff/xutils.c
+++ b/xdiff/xutils.c
@@ -186,12 +186,61 @@ long xdl_guess_lines(mmfile_t *mf) {
 	return nl + 1;
 }
 
+int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)
+{
+	int i1, i2;
+
+	if (flags & XDF_IGNORE_WHITESPACE) {
+		for (i1 = i2 = 0; i1 < s1 && i2 < s2; i1++, i2++) {
+			if (isspace(l1[i1]))
+				while (isspace(l1[i1]) && i1 < s1)
+					i1++;
+			else if (isspace(l2[i2]))
+				while (isspace(l2[i2]) && i2 < s2)
+					i2++;
+			else if (l1[i1] != l2[i2])
+				return l2[i2] - l1[i1];
+		}
+		if (i1 >= s1)
+			return 1;
+		else if (i2 >= s2)
+			return -1;
+	} else if (flags & XDF_IGNORE_WHITESPACE_CHANGE) {
+		for (i1 = i2 = 0; i1 < s1 && i2 < s2; i1++, i2++) {
+			if (isspace(l1[i1])) {
+				if (!isspace(l2[i2]))
+					return -1;
+				while (isspace(l1[i1]) && i1 < s1)
+					i1++;
+				while (isspace(l2[i2]) && i2 < s2)
+					i2++;
+			} else if (l1[i1] != l2[i2])
+				return l2[i2] - l1[i1];
+		}
+		if (i1 >= s1)
+			return 1;
+		else if (i2 >= s2)
+			return -1;
+	} else
+		return s1 == s2 && !memcmp(l1, l2, s1);
+
+	return 0;
+}
 
-unsigned long xdl_hash_record(char const **data, char const *top) {
+unsigned long xdl_hash_record(char const **data, char const *top, long flags) {
 	unsigned long ha = 5381;
 	char const *ptr = *data;
 
 	for (; ptr < top && *ptr != '\n'; ptr++) {
+		if (isspace(*ptr) && (flags & XDF_WHITESPACE_FLAGS)) {
+			while (ptr < top && isspace(*ptr) && ptr[1] != '\n')
+				ptr++;
+			if (flags & XDF_IGNORE_WHITESPACE_CHANGE) {
+				ha += (ha << 5);
+				ha ^= (unsigned long) ' ';
+			}
+			continue;
+		}
 		ha += (ha << 5);
 		ha ^= (unsigned long) *ptr;
 	}
diff --git a/xdiff/xutils.h b/xdiff/xutils.h
index 08691a2447..70d8b9838a 100644
--- a/xdiff/xutils.h
+++ b/xdiff/xutils.h
@@ -34,7 +34,8 @@ 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);
-unsigned long xdl_hash_record(char const **data, char const *top);
+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);
 int xdl_num_out(char *out, long val);
 long xdl_atol(char const *str, char const **next);