commit ae2763e9e2c27e22c7ab84b7250a49c2fd3dd9f6
from: Neels Hofmeyr <neels@hofmeyr.de>
date: Sat Oct 24 01:38:35 2020 UTC

fix patience crash: iron out overlapping identical-blocks on the right

commit - 46093fc37f745d0bcbf997d84fbc676fd3f468d5
commit + ae2763e9e2c27e22c7ab84b7250a49c2fd3dd9f6
blob - 59a3e8cf1f6c1e498736f533ee0626f00d2af123
blob + a845cbd14cd84545c0356b938d9ecc930f7f9890
--- lib/diff_patience.c
+++ lib/diff_patience.c
@@ -359,8 +359,10 @@ diff_atoms_swallow_identical_neighbors(struct diff_dat
 
 	unsigned int l_idx;
 	unsigned int next_l_idx;
+	/* Only checking against identical-line overlaps on the left; overlaps
+	 * on the right are tolerated and ironed out later. See also the other
+	 * place marked with (1). */
 	unsigned int l_min = 0;
-	unsigned int r_min = 0;
 	for (l_idx = 0; l_idx < left->atoms.len; l_idx = next_l_idx) {
 		next_l_idx = l_idx + 1;
 		struct diff_atom *l = &left->atoms.head[l_idx];
@@ -387,7 +389,7 @@ diff_atoms_swallow_identical_neighbors(struct diff_dat
 		 * common-unique line in a previous iteration.
 		 */
 		for (identical_l.start = l_idx, identical_r.start = r_idx;
-		     identical_l.start > l_min && identical_r.start > r_min;
+		     identical_l.start > l_min && identical_r.start > 0;
 		     identical_l.start--, identical_r.start--) {
 			bool same;
 			int rc = diff_atom_same(&same,
@@ -432,7 +434,6 @@ diff_atoms_swallow_identical_neighbors(struct diff_dat
 		PATIENCE(r).identical_lines = identical_r;
 
 		l_min = identical_l.end;
-		r_min = identical_r.end;
 
 		if (!diff_range_empty(&PATIENCE(l).identical_lines)) {
 			debug("common-unique line at l=%u r=%u swallowed"
@@ -672,6 +673,21 @@ diff_algo_patience(const struct diff_algo_config *algo
 			atom_r = NULL;
 			left_idx = left->atoms.len;
 			right_idx = right->atoms.len;
+		}
+
+		if (right_idx < right_pos) {
+			/* This may happen if common-unique lines were in a
+			 * different order on the right, and then ended up
+			 * consuming the same identical atoms around a pair of
+			 * common-unique atoms more than once.
+			 * See also marker the other place marked with (1). */
+			int already_done_count = right_pos - right_idx;
+			left_idx += already_done_count;
+			right_idx += already_done_count;
+			/* Paranoia: make sure we're skipping just an
+			 * additionally joined identical line around it, and not
+			 * the common-unique line itself. */
+			assert(left_idx <= diff_atom_idx(left, atom));
 		}
 
 		/* 'atom' (if not NULL) now marks an atom that matches on both