thodg/libgit2

diff --git a/src/xdiff/xdiffi.c b/src/xdiff/xdiffi.c
index f83e0c0..f2f962f 100644
--- a/src/xdiff/xdiffi.c
+++ b/src/xdiff/xdiffi.c
@@ -412,104 +412,211 @@ static int recs_match(xrecord_t *rec1, xrecord_t *rec2, long flags)
 			     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;
-	xrecord_t **recs = xdf->recs;
+/*
+ * Represent a group of changed lines in an xdfile_t (i.e., a contiguous group
+ * of lines that was inserted or deleted from the corresponding version of the
+ * file). We consider there to be such a group at the beginning of the file, at
+ * the end of the file, and between any two unchanged lines, though most such
+ * groups will usually be empty.
+ *
+ * If the first line in a group is equal to the line following the group, then
+ * the group can be slid down. Similarly, if the last line in a group is equal
+ * to the line preceding the group, then the group can be slid up. See
+ * group_slide_down() and group_slide_up().
+ *
+ * Note that loops that are testing for changed lines in xdf->rchg do not need
+ * index bounding since the array is prepared with a zero at position -1 and N.
+ */
+struct group {
+	/*
+	 * The index of the first changed line in the group, or the index of
+	 * the unchanged line above which the (empty) group is located.
+	 */
+	long start;
 
 	/*
-	 * This is the same of what GNU diff does. Move back and forward
-	 * change groups for a consistent and pretty diff output. This also
-	 * helps in finding joinable change groups and reduce the diff size.
+	 * The index of the first unchanged line after the group. For an empty
+	 * group, end is equal to start.
 	 */
-	for (ix = ixo = 0;;) {
-		/*
-		 * Find the first changed line in the to-be-compacted file.
-		 * We need to keep track of both indexes, so if we find a
-		 * changed lines group on the other file, while scanning the
-		 * to-be-compacted file, we need to skip it properly. Note
-		 * that loops that are testing for changed lines on rchg* do
-		 * not need index bounding since the array is prepared with
-		 * a zero at position -1 and N.
-		 */
-		for (; ix < nrec && !rchg[ix]; ix++)
-			while (rchgo[ixo++]);
-		if (ix == nrec)
-			break;
+	long end;
+};
+
+/*
+ * Initialize g to point at the first group in xdf.
+ */
+static void group_init(xdfile_t *xdf, struct group *g)
+{
+	g->start = g->end = 0;
+	while (xdf->rchg[g->end])
+		g->end++;
+}
+
+/*
+ * Move g to describe the next (possibly empty) group in xdf and return 0. If g
+ * is already at the end of the file, do nothing and return -1.
+ */
+static inline int group_next(xdfile_t *xdf, struct group *g)
+{
+	if (g->end == xdf->nrec)
+		return -1;
+
+	g->start = g->end + 1;
+	for (g->end = g->start; xdf->rchg[g->end]; g->end++)
+		;
+
+	return 0;
+}
+
+/*
+ * Move g to describe the previous (possibly empty) group in xdf and return 0.
+ * If g is already at the beginning of the file, do nothing and return -1.
+ */
+static inline int group_previous(xdfile_t *xdf, struct group *g)
+{
+	if (g->start == 0)
+		return -1;
+
+	g->end = g->start - 1;
+	for (g->start = g->end; xdf->rchg[g->start - 1]; g->start--)
+		;
+
+	return 0;
+}
+
+/*
+ * If g can be slid toward the end of the file, do so, and if it bumps into a
+ * following group, expand this group to include it. Return 0 on success or -1
+ * if g cannot be slid down.
+ */
+static int group_slide_down(xdfile_t *xdf, struct group *g, long flags)
+{
+	if (g->end < xdf->nrec &&
+	    recs_match(xdf->recs[g->start], xdf->recs[g->end], flags)) {
+		xdf->rchg[g->start++] = 0;
+		xdf->rchg[g->end++] = 1;
+
+		while (xdf->rchg[g->end])
+			g->end++;
+
+		return 0;
+	} else {
+		return -1;
+	}
+}
+
+/*
+ * If g can be slid toward the beginning of the file, do so, and if it bumps
+ * into a previous group, expand this group to include it. Return 0 on success
+ * or -1 if g cannot be slid up.
+ */
+static int group_slide_up(xdfile_t *xdf, struct group *g, long flags)
+{
+	if (g->start > 0 &&
+	    recs_match(xdf->recs[g->start - 1], xdf->recs[g->end - 1], flags)) {
+		xdf->rchg[--g->start] = 1;
+		xdf->rchg[--g->end] = 0;
+
+		while (xdf->rchg[g->start - 1])
+			g->start--;
+
+		return 0;
+	} else {
+		return -1;
+	}
+}
+
+static void xdl_bug(const char *msg)
+{
+	fprintf(stderr, "BUG: %s\n", msg);
+	exit(1);
+}
+
+/*
+ * Move back and forward change groups for a consistent and pretty diff output.
+ * This also helps in finding joinable change groups and reducing the diff
+ * size.
+ */
+int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
+	struct group g, go;
+	long earliest_end, end_matching_other;
+	long groupsize;
+
+	group_init(xdf, &g);
+	group_init(xdfo, &go);
+
+	while (1) {
+		/* If the group is empty in the to-be-compacted file, skip it: */
+		if (g.end == g.start)
+			goto next;
 
 		/*
-		 * Record the start of a changed-group in the to-be-compacted file
-		 * and find the end of it, on both to-be-compacted and other file
-		 * indexes (ix and ixo).
+		 * Now shift the change up and then down as far as possible in
+		 * each direction. If it bumps into any other changes, merge them.
 		 */
-		ixs = ix;
-		for (ix++; rchg[ix]; ix++);
-		for (; rchgo[ixo]; ixo++);
-
 		do {
-			grpsiz = ix - ixs;
+			groupsize = g.end - g.start;
 
 			/*
-			 * If the line before the current change group, is equal to
-			 * the last line of the current change group, shift backward
-			 * the group.
+			 * Keep track of the last "end" index that causes this
+			 * group to align with a group of changed lines in the
+			 * other file. -1 indicates that we haven't found such
+			 * a match yet:
 			 */
-			while (ixs > 0 && recs_match(recs[ixs - 1], recs[ix - 1], flags)) {
-				rchg[--ixs] = 1;
-				rchg[--ix] = 0;
-
-				/*
-				 * This change might have joined two change groups,
-				 * so we try to take this scenario in account by moving
-				 * the start index accordingly (and so the other-file
-				 * end-of-group index).
-				 */
-				for (; rchg[ixs - 1]; ixs--);
-				while (rchgo[--ixo]);
-			}
+			end_matching_other = -1;
+
+			/* Shift the group backward as much as possible: */
+			while (!group_slide_up(xdf, &g, flags))
+				if (group_previous(xdfo, &go))
+					xdl_bug("group sync broken sliding up");
 
 			/*
-			 * Record the end-of-group position in case we are matched
-			 * with a group of changes in the other file (that is, the
-			 * change record before the end-of-group index in the other
-			 * file is set).
+			 * This is this highest that this group can be shifted.
+			 * Record its end index:
 			 */
-			ixref = rchgo[ixo - 1] ? ix: nrec;
+			earliest_end = g.end;
+
+			if (go.end > go.start)
+				end_matching_other = g.end;
 
+			/* Now shift the group forward as far as possible: */
+			while (1) {
+				if (group_slide_down(xdf, &g, flags))
+					break;
+				if (group_next(xdfo, &go))
+					xdl_bug("group sync broken sliding down");
+
+				if (go.end > go.start)
+					end_matching_other = g.end;
+			}
+		} while (groupsize != g.end - g.start);
+
+		if (g.end == earliest_end) {
+			/* no shifting was possible */
+		} else if (end_matching_other != -1) {
 			/*
-			 * If the first line of the current change group, is equal to
-			 * the line next of the current change group, shift forward
-			 * the group.
+			 * Move the possibly merged group of changes back to line
+			 * up with the last group of changes from the other file
+			 * that it can align with.
 			 */
-			while (ix < nrec && recs_match(recs[ixs], recs[ix], flags)) {
-				rchg[ixs++] = 0;
-				rchg[ix++] = 1;
-
-				/*
-				 * This change might have joined two change groups,
-				 * so we try to take this scenario in account by moving
-				 * the start index accordingly (and so the other-file
-				 * end-of-group index). Keep tracking the reference
-				 * index in case we are shifting together with a
-				 * corresponding group of changes in the other file.
-				 */
-				for (; rchg[ix]; ix++);
-				while (rchgo[++ixo])
-					ixref = ix;
+			while (go.end == go.start) {
+				if (group_slide_up(xdf, &g, flags))
+					xdl_bug("match disappeared");
+				if (group_previous(xdfo, &go))
+					xdl_bug("group sync broken sliding to match");
 			}
-		} while (grpsiz != ix - ixs);
-
-		/*
-		 * Try to move back the possibly merged group of changes, to match
-		 * the recorded position in the other file.
-		 */
-		while (ixref < ix) {
-			rchg[--ixs] = 1;
-			rchg[--ix] = 0;
-			while (rchgo[--ixo]);
 		}
+
+	next:
+		/* Move past the just-processed group: */
+		if (group_next(xdf, &g))
+			break;
+		if (group_next(xdfo, &go))
+			xdl_bug("group sync broken moving to next group");
 	}
 
+	if (!group_next(xdfo, &go))
+		xdl_bug("group sync broken at end of file");
+
 	return 0;
 }