commit 50198b5f2f9c8dd7d1deefed0fa25cabbf2af92f from: Neels Hofmeyr date: Tue May 05 05:00:47 2020 UTC 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. commit - 09c9539493a3f69ab1c1e259ef4c8ea22e57f906 commit + 50198b5f2f9c8dd7d1deefed0fa25cabbf2af92f 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: *