commit a45330b1527e02e1627af02b55831f4cdf8794b4
from: Neels Hofmeyr <neels@hofmeyr.de>
date: Tue May 05 05:04:21 2020 UTC

fix myers divide: properly trigger division on single midpoints

commit - b47897f387d8f7e9152f0b0e1b1d5548c7bab6f2
commit + a45330b1527e02e1627af02b55831f4cdf8794b4
blob - eb67565c358300506376e716dea9b9c42a2ed8a1
blob + 7a7f5de552270024ae0e6d69c930aa56b5e0a24e
--- lib/diff_myers.c
+++ lib/diff_myers.c
@@ -185,7 +185,7 @@ struct diff_box {
  *    For d == 0, kd_forward[0] is initialized, i.e. the first invocation should be for d == 0.
  * meeting_snake: resulting meeting point, if any.
  */
-static void diff_divide_myers_forward(struct diff_data *left, struct diff_data *right,
+static bool diff_divide_myers_forward(struct diff_data *left, struct diff_data *right,
 				      int *kd_forward, int *kd_backward, int d,
 				      struct diff_box *meeting_snake)
 {
@@ -404,12 +404,13 @@ static void diff_divide_myers_forward(struct diff_data
 				      meeting_snake->left_end,
 				      meeting_snake->right_end);
 				debug_dump_myers_graph(left, right, NULL, kd_forward, d, kd_backward, d-1);
-				return;
+				return true;
 			}
 		}
 	}
 
 	debug_dump_myers_graph(left, right, NULL, kd_forward, d, kd_backward, d-1);
+	return false;
 }
 
 /* Do one backwards step in the "divide and conquer" graph traversal.
@@ -427,7 +428,7 @@ static void diff_divide_myers_forward(struct diff_data
  *    The first invocation will be for d == 1.
  * meeting_snake: resulting meeting point, if any.
  */
-static void diff_divide_myers_backward(struct diff_data *left, struct diff_data *right,
+static bool diff_divide_myers_backward(struct diff_data *left, struct diff_data *right,
 				       int *kd_forward, int *kd_backward, int d,
 				       struct diff_box *meeting_snake)
 {
@@ -633,12 +634,13 @@ static void diff_divide_myers_backward(struct diff_dat
 					      meeting_snake->left_end,
 					      meeting_snake->right_end);
 					debug_dump_myers_graph(left, right, NULL, kd_forward, d, kd_backward, d);
-					return;
+					return true;
 				}
 			}
 		}
 	}
 	debug_dump_myers_graph(left, right, NULL, kd_forward, d, kd_backward, d);
+	return false;
 }
 
 /* Myers "Divide et Impera": tracing forwards from the start and backwards from the end to find a midpoint that divides
@@ -676,17 +678,18 @@ enum diff_rc diff_algo_myers_divide(const struct diff_
 
 	int d;
 	struct diff_box mid_snake = {};
+	bool found_midpoint = false;
 	for (d = 0; d <= (max/2); d++) {
 		debug("-- d=%d\n", d);
-		diff_divide_myers_forward(left, right, kd_forward, kd_backward, d, &mid_snake);
-		if (!diff_box_empty(&mid_snake))
+		found_midpoint = diff_divide_myers_forward(left, right, kd_forward, kd_backward, d, &mid_snake);
+		if (found_midpoint)
 			break;
-		diff_divide_myers_backward(left, right, kd_forward, kd_backward, d, &mid_snake);
-		if (!diff_box_empty(&mid_snake))
+		found_midpoint = diff_divide_myers_backward(left, right, kd_forward, kd_backward, d, &mid_snake);
+		if (found_midpoint)
 			break;
 	}
 
-	if (diff_box_empty(&mid_snake)) {
+	if (!found_midpoint) {
 		/* Divide and conquer failed to find a meeting point. Use the fallback_algo defined in the algo_config
 		 * (leave this to the caller). This is just paranoia/sanity, we normally should always find a midpoint.
 		 */
@@ -727,14 +730,17 @@ enum diff_rc diff_algo_myers_divide(const struct diff_
 		}
 		/* else: left_section_len == 0 and right_section_len == 0, i.e. nothing before the mid-snake. */
 
-		/* the mid-snake, identical data on both sides: */
-		debug("the mid-snake\n");
-		if (!diff_state_add_chunk(state, true,
-					  &left->atoms.head[mid_snake.left_start],
-					  mid_snake.left_end - mid_snake.left_start,
-					  &right->atoms.head[mid_snake.right_start],
-					  mid_snake.right_end - mid_snake.right_start))
-			goto return_rc;
+		if (!diff_box_empty(&mid_snake)) {
+			/* The midpoint is a "snake", i.e. on a section of identical data on both sides: that
+			 * section immediately becomes a solved diff chunk. */
+			debug("the mid-snake\n");
+			if (!diff_state_add_chunk(state, true,
+						  &left->atoms.head[mid_snake.left_start],
+						  mid_snake.left_end - mid_snake.left_start,
+						  &right->atoms.head[mid_snake.right_start],
+						  mid_snake.right_end - mid_snake.right_start))
+				goto return_rc;
+		}
 
 		/* Section after the mid-snake. */
 		debug("Section after the mid-snake\n");