Gotweb

Commit Diff

Commit:: 223979a920a4be072343306ca1c3a34efb036f31
From:: Neels Hofmeyr <neels@hofmeyr.de>
Date:: Tue May 5 04:49:37 2020 UTC
Message:: debug: myers graph dump tweaks In debug output: fix some indents, fix printing of max state size, in myers graph, limit x axis labels to 2 digits, print colored markers of current myers graph positions, also print myers-divide positions in myers graph.
Actions:: Patch | Tree
commit - 0ea9501aa02aa4bbaed4bd7e2818bf946b01cfa6
commit + 223979a920a4be072343306ca1c3a34efb036f31
blob - ec47f65416456d6fa54228e53e8ccea1fd888fba
blob + d3a560ca65443972ce10f241d3345d036bf04e7f
--- lib/debug.h
+++ lib/debug.h
@@ -72,22 +72,31 @@ static inline void dump(struct diff_data *d)
 	dump_atoms(d, d->atoms.head, d->atoms.len);
 }
 
+/* kd is a quadratic space myers matrix from the original Myers algorithm.
+ * kd_forward and kd_backward are linear slices of a myers matrix from the Myers Divide algorithm.
+ */
 static inline void dump_myers_graph(const struct diff_data *l, const struct diff_data *r,
-				    int *kd)
+				    int *kd, int *kd_forward, int kd_forward_d, int *kd_backward, int kd_backward_d)
 {
+	#define COLOR_YELLOW "\033[1;33m"
+	#define COLOR_GREEN "\033[1;32m"
+	#define COLOR_BLUE "\033[1;34m"
+	#define COLOR_RED "\033[1;31m"
+	#define COLOR_END "\033[0;m"
 	int x;
 	int y;
-	print("  ");
+	print("   ");
 	for (x = 0; x <= l->atoms.len; x++)
-		print("%2d", x);
+		print("%2d", x % 100);
 	print("\n");
 
 	for (y = 0; y <= r->atoms.len; y++) {
-		print("%2d ", y);
+		print("%3d ", y);
 		for (x = 0; x <= l->atoms.len; x++) {
 
 			/* print d advancements from kd, if any. */
-			int d = -1;
+			char label = 'o';
+			char *color = NULL;
 			if (kd) {
 				int max = l->atoms.len + r->atoms.len;
 				size_t kd_len = max + 1 + max;
@@ -97,29 +106,69 @@ static inline void dump_myers_graph(const struct diff_
 				for (di = 0; di < max; di++) {
 					int ki;
 					for (ki = di; ki >= -di; ki -= 2) {
-						if (x == kd_pos[ki]
-						    && y == xk_to_y(x, ki)) {
-							d = di;
-							break;
-						}
+						if (x != kd_pos[ki]
+						    || y != xk_to_y(x, ki))
+							continue;
+						label = '0' + (di % 10);
+						color = COLOR_YELLOW;
+						break;
 					}
-					if (d >= 0)
+					if (label != 'o')
 						break;
 					kd_pos += kd_len;
 				}
 			}
-			if (d >= 0)
-				print("%d", d);
-			else
-				print("o");
-			if (x < l->atoms.len && d < 10)
+			if (kd_forward && kd_forward_d >= 0) {
+				int max = l->atoms.len + r->atoms.len;
+				size_t kd_len = max + 1 + max;
+				int di;
+#define xc_to_y(X, C, DELTA) ((X) - (C) + (DELTA))
+				int delta = (int)r->atoms.len - (int)l->atoms.len;
+				int ki;
+				for (ki = kd_forward_d; ki >= -kd_forward_d; ki -= 2) {
+					if (x != kd_forward[ki])
+						continue;
+					if (y != xk_to_y(x, ki))
+						continue;
+					label = 'F';
+					color = COLOR_GREEN;
+					break;
+				}
+			}
+			if (kd_backward && kd_backward_d >= 0) {
+				int max = l->atoms.len + r->atoms.len;
+				size_t kd_len = max + 1 + max;
+				int di;
+				int delta = (int)r->atoms.len - (int)l->atoms.len;
+				int ki;
+				for (ki = kd_backward_d; ki >= -kd_backward_d; ki -= 2) {
+					if (x != kd_backward[ki])
+						continue;
+					if (y != xc_to_y(x, ki, delta))
+						continue;
+					if (label == 'o') {
+						label = 'B';
+						color = COLOR_BLUE;
+					} else {
+						label = 'X';
+						color = COLOR_RED;
+					}
+					break;
+				}
+			}
+			if (color)
+				print("%s", color);
+			print("%c", label);
+			if (color)
+				print("%s", COLOR_END);
+			if (x < l->atoms.len)
 				print("-");
 		}
 		print("\n");
 		if (y == r->atoms.len)
 			break;
 
-		print("   ");
+		print("    ");
 		for (x = 0; x < l->atoms.len; x++) {
 			if (diff_atom_same(&l->atoms.head[x], &r->atoms.head[y]))
 				print("|\\");
@@ -131,11 +180,11 @@ static inline void dump_myers_graph(const struct diff_
 }
 
 static inline void debug_dump_myers_graph(const struct diff_data *l, const struct diff_data *r,
-				    int *kd)
+				    int *kd, int *kd_forward, int kd_forward_d, int *kd_backward, int kd_backward_d)
 {
 	if (l->atoms.len > 99 || r->atoms.len > 99)
 		return;
-	dump_myers_graph(l, r, kd);
+	dump_myers_graph(l, r, kd, kd_forward, kd_forward_d, kd_backward, kd_backward_d);
 }
 
 #else
blob - 285bd40d5941fe84c5d9a9bd437a4a9f981ead13
blob + 46c7fc63654f51755c1bde729244e679a0fa7c6c
--- lib/diff_main.c
+++ lib/diff_main.c
@@ -104,7 +104,7 @@ enum diff_rc diff_algo_none(const struct diff_algo_con
 	debug_dump(&state->left);
 	debug("right:\n");
 	debug_dump(&state->right);
-	debug_dump_myers_graph(&state->left, &state->right, NULL);
+	debug_dump_myers_graph(&state->left, &state->right, NULL, NULL, 0, NULL, 0);
 
 	/* Add a chunk of equal lines, if any */
 	unsigned int equal_atoms = 0;
blob - a77e578fed2a1e759424a3853d595bb888a4ecc8
blob + 111366765d59948fc0ea91555be00ef59b425b15
--- lib/diff_myers.c
+++ lib/diff_myers.c
@@ -196,7 +196,6 @@ static void diff_divide_myers_forward(struct diff_data
 	int x;
 
 	debug("-- %s d=%d\n", __func__, d);
-	debug_dump_myers_graph(left, right, NULL);
 
 	for (k = d; k >= -d; k -= 2) {
 		if (k < -(int)right->atoms.len || k > (int)left->atoms.len) {
@@ -376,8 +375,8 @@ static void diff_divide_myers_forward(struct diff_data
 			 */
 			int backward_x = kd_backward[c];
 			int backward_y = xc_to_y(backward_x, c, delta);
-			debug(" prev_x,y = (%d,%d)  c%d:backward_x,y = (%d,%d)  k%d:x,y = (%d,%d)\n",
-			      prev_x, prev_y, c, backward_x, backward_y, k, x, xk_to_y(x, k));
+			debug("Compare:  k=%d c=%d  is (%d,%d) >= (%d,%d)?\n",
+			      k, c, x, xk_to_y(x, k), backward_x, xc_to_y(backward_x, c, delta));
 			if (prev_x <= backward_x && prev_y <= backward_y
 			    && x >= backward_x) {
 				*meeting_snake = (struct diff_box){
@@ -391,10 +390,13 @@ static void diff_divide_myers_forward(struct diff_data
 				      meeting_snake->right_start,
 				      meeting_snake->left_end,
 				      meeting_snake->right_end);
+				debug_dump_myers_graph(left, right, NULL, kd_forward, d, kd_backward, d-1);
 				return;
 			}
 		}
 	}
+
+	debug_dump_myers_graph(left, right, NULL, kd_forward, d, kd_backward, d-1);
 }
 
 /* Do one backwards step in the "divide and conquer" graph traversal.
@@ -423,7 +425,6 @@ static void diff_divide_myers_backward(struct diff_dat
 	int x;
 
 	debug("-- %s d=%d\n", __func__, d);
-	debug_dump_myers_graph(left, right, NULL);
 
 	for (c = d; c >= -d; c -= 2) {
 		if (c < -(int)left->atoms.len || c > (int)right->atoms.len) {
@@ -497,11 +498,11 @@ static void diff_divide_myers_backward(struct diff_dat
 			debug("  l="); debug_dump_atom(left, right, &left->atoms.head[x-1]);
 		}
 		if (xc_to_y(x, c, delta) > 0) {
-			debug("   r="); debug_dump_atom(right, left, &right->atoms.head[xc_to_y(x, c, delta)-1]);
+			debug("  r="); debug_dump_atom(right, left, &right->atoms.head[xc_to_y(x, c, delta)-1]);
 		}
 		while (x > 0 && xc_to_y(x, c, delta) > 0
 		       && diff_atom_same(&left->atoms.head[x-1], &right->atoms.head[xc_to_y(x, c, delta)-1]))
-		       x--;
+			x--;
 		kd_backward[c] = x;
 
 		if (DEBUG) {
@@ -571,9 +572,8 @@ static void diff_divide_myers_backward(struct diff_dat
 				 * mid-box. */
 				int forward_x = kd_forward[k];
 				int forward_y = xk_to_y(forward_x, k);
-				debug("Compare %d to %d  k=%d  (x=%d,y=%d) to (x=%d,y=%d)\n",
-				      forward_x, x, k,
-				      forward_x, xk_to_y(forward_x, k), x, xc_to_y(x, c, delta));
+				debug("Compare:  k=%d c=%d  is (%d,%d) >= (%d,%d)?\n",
+				      k, c, forward_x, xk_to_y(forward_x, k), x, xc_to_y(x, c, delta));
 				if (forward_x <= prev_x && forward_y <= prev_y
 				    && forward_x >= x) {
 					*meeting_snake = (struct diff_box){
@@ -587,11 +587,13 @@ static void diff_divide_myers_backward(struct diff_dat
 					      meeting_snake->right_start,
 					      meeting_snake->left_end,
 					      meeting_snake->right_end);
+					debug_dump_myers_graph(left, right, NULL, kd_forward, d, kd_backward, d);
 					return;
 				}
 			}
 		}
 	}
+	debug_dump_myers_graph(left, right, NULL, kd_forward, d, kd_backward, d);
 }
 
 /* Myers "Divide et Impera": tracing forwards from the start and backwards from the end to find a midpoint that divides
@@ -607,7 +609,7 @@ enum diff_rc diff_algo_myers_divide(const struct diff_
 	debug_dump(left);
 	debug("right:\n");
 	debug_dump(right);
-	debug_dump_myers_graph(left, right, NULL);
+	debug_dump_myers_graph(left, right, NULL, NULL, 0, NULL, 0);
 
 	/* Allocate two columns of a Myers graph, one for the forward and one for the backward traversal. */
 	unsigned int max = left->atoms.len + right->atoms.len;
@@ -743,17 +745,18 @@ enum diff_rc diff_algo_myers(const struct diff_algo_co
 	debug_dump(left);
 	debug("right:\n");
 	debug_dump(right);
-	debug_dump_myers_graph(left, right, NULL);
+	debug_dump_myers_graph(left, right, NULL, NULL, 0, NULL, 0);
 
 	/* Allocate two columns of a Myers graph, one for the forward and one for the backward traversal. */
 	unsigned int max = left->atoms.len + right->atoms.len;
 	size_t kd_len = max + 1 + max;
 	size_t kd_buf_size = kd_len * kd_len;
+	size_t kd_state_size = kd_buf_size * sizeof(int);
 	debug("state size: %zu\n", kd_buf_size);
 	if (kd_buf_size < kd_len /* overflow? */
-	    || kd_buf_size * sizeof(int) > algo_config->permitted_state_size) {
+	    || kd_state_size > algo_config->permitted_state_size) {
 		debug("state size %zu > permitted_state_size %zu, use fallback_algo\n",
-		      kd_buf_size, algo_config->permitted_state_size);
+		      kd_state_size, algo_config->permitted_state_size);
 		return DIFF_RC_USE_DIFF_ALGO_FALLBACK;
 	}
 
@@ -882,7 +885,7 @@ enum diff_rc diff_algo_myers(const struct diff_algo_co
 			break;
 	}
 
-	debug_dump_myers_graph(left, right, kd_origin);
+	debug_dump_myers_graph(left, right, kd_origin, NULL, 0, NULL, 0);
 
 	/* backtrack. A matrix spanning from start to end of the file is ready:
 	 *