commit b5a3e4d3220d54590de58ecf5a2199285e3f9263 from: Martin Pieuchot date: Tue Feb 11 14:03:16 2020 UTC KNF commit - 76670af02746b4cc2a4a26dca93072a682d48232 commit + b5a3e4d3220d54590de58ecf5a2199285e3f9263 blob - 587e4a52f34ec4f3ac54347a4b14c7d44c2d746a blob + 8128ea1989ba2ca2f9365f3c7489680e23224221 --- diff.c +++ diff.c @@ -35,7 +35,8 @@ /* stupid shims to compile and test on linux */ #define __dead -static const char *getprogname() +static const char * +getprogname() { return "diff"; } blob - 55afd5ecfacb851e300d78ee07208d3c74eab483 blob + 390cfdd8fbe95702abda85e6d3570c726f457856 --- diff_atomize_text.c +++ diff_atomize_text.c @@ -20,7 +20,8 @@ #include "diff_main.h" -static int diff_data_atomize_text_lines(struct diff_data *d) +static int +diff_data_atomize_text_lines(struct diff_data *d) { const uint8_t *pos = d->data; const uint8_t *end = pos + d->len; @@ -68,7 +69,8 @@ static int diff_data_atomize_text_lines(struct diff_da return DIFF_RC_OK; } -enum diff_rc diff_atomize_text_by_line(void *func_data, struct diff_data *left, struct diff_data *right) +enum diff_rc +diff_atomize_text_by_line(void *func_data, struct diff_data *left, struct diff_data *right) { enum diff_rc rc; rc = diff_data_atomize_text_lines(left); blob - c88a63887cb245a60bbcc098d918ccffaad0ce64 blob + 7c15435737542abfcf505d0f0e0909552752c0ee --- diff_main.c +++ diff_main.c @@ -34,10 +34,10 @@ /* Even if a left or right side is empty, diff output may need to know the position in that file. * So left_start or right_start must never be NULL -- pass left_count or right_count as zero to indicate staying at that * position without consuming any lines. */ -struct diff_chunk *diff_state_add_chunk(struct diff_state *state, bool solved, - struct diff_atom *left_start, unsigned int left_count, - struct diff_atom *right_start, unsigned int right_count) -{ +struct diff_chunk * +diff_state_add_chunk(struct diff_state *state, bool solved, + struct diff_atom *left_start, unsigned int left_count, + struct diff_atom *right_start, unsigned int right_count) { struct diff_chunk *chunk; struct diff_chunk_arraylist *result; @@ -65,7 +65,8 @@ struct diff_chunk *diff_state_add_chunk(struct diff_st return chunk; } -void diff_data_init_root(struct diff_data *d, const uint8_t *data, size_t len) +void +diff_data_init_root(struct diff_data *d, const uint8_t *data, size_t len) { *d = (struct diff_data){ .data = data, @@ -74,9 +75,9 @@ void diff_data_init_root(struct diff_data *d, const ui }; } -void diff_data_init_subsection(struct diff_data *d, struct diff_data *parent, - struct diff_atom *from_atom, unsigned int atoms_count) -{ +void +diff_data_init_subsection(struct diff_data *d, struct diff_data *parent, + struct diff_atom *from_atom, unsigned int atoms_count) { struct diff_atom *last_atom = from_atom + atoms_count - 1; *d = (struct diff_data){ .data = from_atom->at, @@ -90,7 +91,8 @@ void diff_data_init_subsection(struct diff_data *d, st debug_dump(d); } -void diff_data_free(struct diff_data *diff_data) +void +diff_data_free(struct diff_data *diff_data) { if (!diff_data) return; @@ -98,7 +100,8 @@ void diff_data_free(struct diff_data *diff_data) ARRAYLIST_FREE(diff_data->atoms); } -enum diff_rc diff_algo_none(const struct diff_algo_config *algo_config, struct diff_state *state) +enum diff_rc +diff_algo_none(const struct diff_algo_config *algo_config, struct diff_state *state) { debug("\n** %s\n", __func__); debug("left:\n"); @@ -109,37 +112,38 @@ enum diff_rc diff_algo_none(const struct diff_algo_con /* Add a chunk of equal lines, if any */ unsigned int equal_atoms = 0; - while (equal_atoms < state->left.atoms.len && equal_atoms < state->right.atoms.len - && diff_atom_same(&state->left.atoms.head[equal_atoms], &state->right.atoms.head[equal_atoms])) + while (equal_atoms < state->left.atoms.len && equal_atoms < state->right.atoms.len && + diff_atom_same(&state->left.atoms.head[equal_atoms], &state->right.atoms.head[equal_atoms])) equal_atoms++; if (equal_atoms) { if (!diff_state_add_chunk(state, true, - &state->left.atoms.head[0], equal_atoms, - &state->right.atoms.head[0], equal_atoms)) + &state->left.atoms.head[0], equal_atoms, + &state->right.atoms.head[0], equal_atoms)) return DIFF_RC_ENOMEM; } /* Add a "minus" chunk with all lines from the left. */ if (equal_atoms < state->left.atoms.len) { if (!diff_state_add_chunk(state, true, - &state->left.atoms.head[equal_atoms], - state->left.atoms.len - equal_atoms, - NULL, 0)) - return DIFF_RC_ENOMEM; + &state->left.atoms.head[equal_atoms], + state->left.atoms.len - equal_atoms, + NULL, 0)) + return DIFF_RC_ENOMEM; } /* Add a "plus" chunk with all lines from the right. */ if (equal_atoms < state->right.atoms.len) { if (!diff_state_add_chunk(state, true, - NULL, 0, - &state->right.atoms.head[equal_atoms], - state->right.atoms.len - equal_atoms)) - return DIFF_RC_ENOMEM; + NULL, 0, + &state->right.atoms.head[equal_atoms], + state->right.atoms.len - equal_atoms)) + return DIFF_RC_ENOMEM; } return DIFF_RC_OK; } -enum diff_rc diff_run_algo(const struct diff_algo_config *algo_config, struct diff_state *state) +enum diff_rc +diff_run_algo(const struct diff_algo_config *algo_config, struct diff_state *state) { enum diff_rc rc; ARRAYLIST_FREE(state->temp_result); @@ -203,9 +207,10 @@ return_rc: return rc; } -struct diff_result *diff_main(const struct diff_config *config, - const uint8_t *left_data, size_t left_len, - const uint8_t *right_data, size_t right_len) +struct diff_result * +diff_main(const struct diff_config *config, + const uint8_t *left_data, size_t left_len, + const uint8_t *right_data, size_t right_len) { struct diff_result *result = malloc(sizeof(struct diff_result)); if (!result) @@ -236,7 +241,8 @@ struct diff_result *diff_main(const struct diff_config return result; } -void diff_result_free(struct diff_result *result) +void +diff_result_free(struct diff_result *result) { if (!result) return; blob - a0e5f510d94462154ff83dee18b5962775f93c56 blob + 2da3c7ce58e3cfa51fbd38642d8a07affc38587c --- diff_myers.c +++ diff_myers.c @@ -189,10 +189,10 @@ 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, - int *kd_forward, int *kd_backward, int d, - struct diff_box *meeting_snake) -{ +static void +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) { int delta = (int)right->atoms.len - (int)left->atoms.len; int prev_x; int prev_y; @@ -244,9 +244,9 @@ static void diff_divide_myers_forward(struct diff_data * If k == d, there is no k + 1 and k - 1 is the only option. * If k < d, use k + 1 in case that yields a larger x. Also use k + 1 if k - 1 is outside the graph. */ - else if (k > -d && (k == d - || (k - 1 >= -(int)right->atoms.len - && kd_forward[k - 1] >= kd_forward[k + 1]))) { + else if (k > -d && (k == d || + (k - 1 >= -(int)right->atoms.len && + kd_forward[k - 1] >= kd_forward[k + 1]))) { /* Advance from k - 1. * From position prev_k, step to the right in the Myers graph: x += 1. */ @@ -267,9 +267,9 @@ static void diff_divide_myers_forward(struct diff_data } /* Slide down any snake that we might find here. */ - while (x < left->atoms.len && xk_to_y(x, k) < right->atoms.len - && diff_atom_same(&left->atoms.head[x], &right->atoms.head[xk_to_y(x, k)])) - x++; + while (x < left->atoms.len && xk_to_y(x, k) < right->atoms.len && + diff_atom_same(&left->atoms.head[x], &right->atoms.head[xk_to_y(x, k)])) + x++; kd_forward[k] = x; if (DEBUG) { @@ -289,8 +289,8 @@ static void diff_divide_myers_forward(struct diff_data } } - if (x < 0 || x > left->atoms.len - || xk_to_y(x, k) < 0 || xk_to_y(x, k) > right->atoms.len) + if (x < 0 || x > left->atoms.len || + xk_to_y(x, k) < 0 || xk_to_y(x, k) > right->atoms.len) continue; /* Figured out a new forwards traversal, see if this has gone onto or even past a preceding backwards @@ -335,7 +335,7 @@ static void diff_divide_myers_forward(struct diff_data * * So in the forward path, we can only match up diagonals when the delta is odd. */ - /* Forwards is done first, so the backwards one was still at d - 1. Can't do this for d == 0. */ + /* Forwards is done first, so the backwards one was still at d - 1. Can't do this for d == 0. */ int backwards_d = d - 1; if ((delta & 1) && (backwards_d >= 0)) { debug("backwards_d = %d\n", backwards_d); @@ -377,9 +377,9 @@ 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)); - if (prev_x <= backward_x && prev_y <= backward_y - && x >= backward_x) { + prev_x, prev_y, c, backward_x, backward_y, k, x, xk_to_y(x, k)); + if (prev_x <= backward_x && prev_y <= backward_y && + x >= backward_x) { *meeting_snake = (struct diff_box){ .left_start = backward_x, .left_end = x, @@ -387,10 +387,10 @@ static void diff_divide_myers_forward(struct diff_data .right_end = xk_to_y(x, k), }; debug("HIT x=(%u,%u) - y=(%u,%u)\n", - meeting_snake->left_start, - meeting_snake->right_start, - meeting_snake->left_end, - meeting_snake->right_end); + meeting_snake->left_start, + meeting_snake->right_start, + meeting_snake->left_end, + meeting_snake->right_end); return; } } @@ -413,10 +413,10 @@ 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, - int *kd_forward, int *kd_backward, int d, - struct diff_box *meeting_snake) -{ +static void +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) { int delta = (int)right->atoms.len - (int)left->atoms.len; int prev_x; int prev_y; @@ -470,9 +470,9 @@ static void diff_divide_myers_backward(struct diff_dat * If c == d, there is no c + 1 and c - 1 is the only option. * If c < d, use c + 1 in case that yields a larger x. Also use c + 1 if c - 1 is outside the graph. */ - else if (c > -d && (c == d - || (c - 1 >= -(int)right->atoms.len - && kd_backward[c - 1] <= kd_backward[c + 1]))) { + else if (c > -d && (c == d || + (c - 1 >= -(int)right->atoms.len && + kd_backward[c - 1] <= kd_backward[c + 1]))) { /* A top one. * From position prev_c, step upwards in the Myers graph: y -= 1. * Decrementing y is achieved by incrementing c while keeping the same x. @@ -500,16 +500,16 @@ static void diff_divide_myers_backward(struct diff_dat 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]); } - 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--; + 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--; kd_backward[c] = x; if (DEBUG) { int fi; for (fi = d; fi >= c; fi--) { debug("kd_backward[%d] = (%d, %d)\n", fi, kd_backward[fi], - kd_backward[fi] - fi + delta); + kd_backward[fi] - fi + delta); /* if (kd_backward[fi] >= 0 && kd_backward[fi] < left->atoms.len) debug_dump_atom(left, right, &left->atoms.head[kd_backward[fi]]); @@ -523,8 +523,8 @@ static void diff_divide_myers_backward(struct diff_dat } } - if (x < 0 || x > left->atoms.len - || xc_to_y(x, c, delta) < 0 || xc_to_y(x, c, delta) > right->atoms.len) + if (x < 0 || x > left->atoms.len || + xc_to_y(x, c, delta) < 0 || xc_to_y(x, c, delta) > right->atoms.len) continue; /* Figured out a new backwards traversal, see if this has gone onto or even past a preceding forwards @@ -573,10 +573,10 @@ static void diff_divide_myers_backward(struct diff_dat 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)); - if (forward_x <= prev_x && forward_y <= prev_y - && forward_x >= x) { + forward_x, x, k, + 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){ .left_start = x, .left_end = forward_x, @@ -584,10 +584,10 @@ static void diff_divide_myers_backward(struct diff_dat .right_end = xk_to_y(forward_x, k), }; debug("HIT x=%u,%u - y=%u,%u\n", - meeting_snake->left_start, - meeting_snake->right_start, - meeting_snake->left_end, - meeting_snake->right_end); + meeting_snake->left_start, + meeting_snake->right_start, + meeting_snake->left_end, + meeting_snake->right_end); return; } } @@ -597,7 +597,8 @@ static void diff_divide_myers_backward(struct diff_dat /* Myers "Divide et Impera": tracing forwards from the start and backwards from the end to find a midpoint that divides * the problem into smaller chunks. Requires only linear amounts of memory. */ -enum diff_rc diff_algo_myers_divide(const struct diff_algo_config *algo_config, struct diff_state *state) +enum diff_rc +diff_algo_myers_divide(const struct diff_algo_config *algo_config, struct diff_state *state) { enum diff_rc rc = DIFF_RC_ENOMEM; struct diff_data *left = &state->left; @@ -649,8 +650,8 @@ enum diff_rc diff_algo_myers_divide(const struct diff_ goto return_rc; } else { debug(" mid snake L: %u to %u of %u R: %u to %u of %u\n", - mid_snake.left_start, mid_snake.left_end, left->atoms.len, - mid_snake.right_start, mid_snake.right_end, right->atoms.len); + mid_snake.left_start, mid_snake.left_end, left->atoms.len, + mid_snake.right_start, mid_snake.right_end, right->atoms.len); /* Section before the mid-snake. */ debug("Section before the mid-snake\n"); @@ -663,20 +664,20 @@ enum diff_rc diff_algo_myers_divide(const struct diff_ if (left_section_len && right_section_len) { /* Record an unsolved chunk, the caller will apply inner_algo() on this chunk. */ if (!diff_state_add_chunk(state, false, - left_atom, left_section_len, - right_atom, right_section_len)) + left_atom, left_section_len, + right_atom, right_section_len)) goto return_rc; } else if (left_section_len && !right_section_len) { /* Only left atoms and none on the right, they form a "minus" chunk, then. */ if (!diff_state_add_chunk(state, true, - left_atom, left_section_len, - right_atom, 0)) + left_atom, left_section_len, + right_atom, 0)) goto return_rc; } else if (!left_section_len && right_section_len) { /* No left atoms, only atoms on the right, they form a "plus" chunk, then. */ if (!diff_state_add_chunk(state, true, - left_atom, 0, - right_atom, right_section_len)) + left_atom, 0, + right_atom, right_section_len)) goto return_rc; } /* else: left_section_len == 0 and right_section_len == 0, i.e. nothing before the mid-snake. */ @@ -684,10 +685,10 @@ enum diff_rc diff_algo_myers_divide(const struct diff_ /* 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)) + &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. */ @@ -702,20 +703,20 @@ enum diff_rc diff_algo_myers_divide(const struct diff_ if (left_section_len && right_section_len) { /* Record an unsolved chunk, the caller will apply inner_algo() on this chunk. */ if (!diff_state_add_chunk(state, false, - left_atom, left_section_len, - right_atom, right_section_len)) + left_atom, left_section_len, + right_atom, right_section_len)) goto return_rc; } else if (left_section_len && !right_section_len) { /* Only left atoms and none on the right, they form a "minus" chunk, then. */ if (!diff_state_add_chunk(state, true, - left_atom, left_section_len, - right_atom, 0)) + left_atom, left_section_len, + right_atom, 0)) goto return_rc; } else if (!left_section_len && right_section_len) { /* No left atoms, only atoms on the right, they form a "plus" chunk, then. */ if (!diff_state_add_chunk(state, true, - left_atom, 0, - right_atom, right_section_len)) + left_atom, 0, + right_atom, right_section_len)) goto return_rc; } /* else: left_section_len == 0 and right_section_len == 0, i.e. nothing after the mid-snake. */ @@ -731,7 +732,8 @@ return_rc: /* Myers Diff tracing from the start all the way through to the end, requiring quadratic amounts of memory. This can * fail if the required space surpasses algo_config->permitted_state_size. */ -enum diff_rc diff_algo_myers(const struct diff_algo_config *algo_config, struct diff_state *state) +enum diff_rc +diff_algo_myers(const struct diff_algo_config *algo_config, struct diff_state *state) { /* do a diff_divide_myers_forward() without a _backward(), so that it walks forward across the entire * files to reach the end. Keep each run's state, and do a final backtrace. */ @@ -751,10 +753,10 @@ enum diff_rc diff_algo_myers(const struct diff_algo_co size_t kd_len = max + 1 + max; size_t kd_buf_size = kd_len * kd_len; 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) { + if (kd_buf_size < kd_len /* overflow? */ || + kd_buf_size * sizeof(int) > 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_buf_size, algo_config->permitted_state_size); return DIFF_RC_USE_DIFF_ALGO_FALLBACK; } @@ -825,9 +827,9 @@ enum diff_rc diff_algo_myers(const struct diff_algo_co * If k == d, there is no k + 1 and k - 1 is the only option. * If k < d, use k + 1 in case that yields a larger x. Also use k + 1 if k - 1 is outside the graph. */ - if (k > -d && (k == d - || (k - 1 >= -(int)right->atoms.len - && kd_prev_column[k - 1] >= kd_prev_column[k + 1]))) { + if (k > -d && (k == d || + (k - 1 >= -(int)right->atoms.len && + kd_prev_column[k - 1] >= kd_prev_column[k + 1]))) { /* Advance from k - 1. * From position prev_k, step to the right in the Myers graph: x += 1. */ @@ -847,14 +849,14 @@ enum diff_rc diff_algo_myers(const struct diff_algo_co } /* Slide down any snake that we might find here. */ - while (x < left->atoms.len && xk_to_y(x, k) < right->atoms.len - && diff_atom_same(&left->atoms.head[x], &right->atoms.head[xk_to_y(x, k)])) - x++; + while (x < left->atoms.len && xk_to_y(x, k) < right->atoms.len && + diff_atom_same(&left->atoms.head[x], &right->atoms.head[xk_to_y(x, k)])) + x++; kd_column[k] = x; if (DEBUG) { int fi; - for (fi = d; fi >= k; fi-=2) { + for (fi = d; fi >= k; fi -= 2) { debug("kd_column[%d] = (%d, %d)\n", fi, kd_column[fi], kd_column[fi] - fi); #if 0 if (kd_column[fi] >= 0 && kd_column[fi] < left->atoms.len) @@ -874,7 +876,7 @@ enum diff_rc diff_algo_myers(const struct diff_algo_co backtrack_d = d; backtrack_k = k; debug("Reached the end at d = %d, k = %d\n", - backtrack_d, backtrack_k); + backtrack_d, backtrack_k); break; } } @@ -917,7 +919,7 @@ enum diff_rc diff_algo_myers(const struct diff_algo_co kd_column[0] = x; kd_column[1] = y; debug("Backtrack d=%d: xy=(%d, %d)\n", - d, kd_column[0], kd_column[1]); + d, kd_column[0], kd_column[1]); /* Don't access memory before kd_buf */ if (d == 0) @@ -944,17 +946,17 @@ enum diff_rc diff_algo_myers(const struct diff_algo_co * | x == 0 */ debug("prev[k-1] = %d,%d prev[k+1] = %d,%d\n", - kd_prev_column[k-1], xk_to_y(kd_prev_column[k-1],k-1), - kd_prev_column[k+1], xk_to_y(kd_prev_column[k+1],k+1)); - if (y == 0 - || (x > 0 && kd_prev_column[k - 1] >= kd_prev_column[k + 1])) { + kd_prev_column[k - 1], xk_to_y(kd_prev_column[k - 1], k - 1), + kd_prev_column[k + 1], xk_to_y(kd_prev_column[k + 1], k + 1)); + if (y == 0 || + (x > 0 && kd_prev_column[k - 1] >= kd_prev_column[k + 1])) { k = k - 1; debug("prev k=k-1=%d x=%d y=%d\n", - k, kd_prev_column[k], xk_to_y(kd_prev_column[k], k)); + k, kd_prev_column[k], xk_to_y(kd_prev_column[k], k)); } else { k = k + 1; debug("prev k=k+1=%d x=%d y=%d\n", - k, kd_prev_column[k], xk_to_y(kd_prev_column[k], k)); + k, kd_prev_column[k], xk_to_y(kd_prev_column[k], k)); } kd_column = kd_prev_column; } @@ -969,7 +971,7 @@ enum diff_rc diff_algo_myers(const struct diff_algo_co int next_x = kd_column[0]; int next_y = kd_column[1]; debug("Forward track from xy(%d,%d) to xy(%d,%d)\n", - x, y, next_x, next_y); + x, y, next_x, next_y); struct diff_atom *left_atom = &left->atoms.head[x]; int left_section_len = next_x - x; @@ -998,15 +1000,15 @@ enum diff_rc diff_algo_myers(const struct diff_algo_co * the right before sliding down the snake. */ if (left_section_len == right_section_len + 1) { if (!diff_state_add_chunk(state, true, - left_atom, 1, - right_atom, 0)) + left_atom, 1, + right_atom, 0)) goto return_rc; left_atom++; left_section_len--; } else if (right_section_len == left_section_len + 1) { if (!diff_state_add_chunk(state, true, - left_atom, 0, - right_atom, 1)) + left_atom, 0, + right_atom, 1)) goto return_rc; right_atom++; right_section_len--; @@ -1017,20 +1019,20 @@ enum diff_rc diff_algo_myers(const struct diff_algo_co } if (!diff_state_add_chunk(state, true, - left_atom, left_section_len, - right_atom, right_section_len)) + left_atom, left_section_len, + right_atom, right_section_len)) goto return_rc; } else if (left_section_len && !right_section_len) { /* Only left atoms and none on the right, they form a "minus" chunk, then. */ if (!diff_state_add_chunk(state, true, - left_atom, left_section_len, - right_atom, 0)) + left_atom, left_section_len, + right_atom, 0)) goto return_rc; } else if (!left_section_len && right_section_len) { /* No left atoms, only atoms on the right, they form a "plus" chunk, then. */ if (!diff_state_add_chunk(state, true, - left_atom, 0, - right_atom, right_section_len)) + left_atom, 0, + right_atom, right_section_len)) goto return_rc; } blob - 675b13bbbe632cb8d2c5f0026e3daaec4ad06f9e blob + 9e92df1e83b5f18049b7152922d5f0d9e0f98f71 --- diff_output.c +++ diff_output.c @@ -20,7 +20,8 @@ #include "diff_main.h" -void diff_output_lines(FILE *dest, const char *prefix, struct diff_atom *start_atom, unsigned int count) +void +diff_output_lines(FILE *dest, const char *prefix, struct diff_atom *start_atom, unsigned int count) { struct diff_atom *atom; foreach_diff_atom(atom, start_atom, count) { @@ -44,12 +45,13 @@ void diff_output_lines(FILE *dest, const char *prefix, } } -enum diff_rc diff_output_info(FILE *dest, const struct diff_input_info *info) +enum diff_rc +diff_output_info(FILE *dest, const struct diff_input_info *info) { if (info->arbitrary_info && *info->arbitrary_info) fprintf(dest, "%s", info->arbitrary_info); fprintf(dest, "--- %s\n+++ %s\n", - info->left_path ? : "a", - info->right_path ? : "b"); - return DIFF_RC_OK; + info->left_path ? : "a", + info->right_path ? : "b"); + return DIFF_RC_OK; } blob - e6a2e514bdda6357e454d60b3218d611eea63930 blob + 34916d08db89aba7a95acf281e681c11b69bbd4d --- diff_output_plain.c +++ diff_output_plain.c @@ -20,9 +20,9 @@ #include "diff_main.h" -enum diff_rc diff_output_plain(FILE *dest, const struct diff_input_info *info, - const struct diff_result *result) -{ +enum diff_rc +diff_output_plain(FILE *dest, const struct diff_input_info *info, + const struct diff_result *result) { if (!result) return DIFF_RC_EINVAL; if (result->rc != DIFF_RC_OK) @@ -43,9 +43,10 @@ enum diff_rc diff_output_plain(FILE *dest, const struc return DIFF_RC_OK; } -enum diff_rc diff_plain(FILE *dest, const struct diff_config *diff_config, - const struct diff_input_info *info, - const char *left, int left_len, const char *right, int right_len) +enum diff_rc +diff_plain(FILE *dest, const struct diff_config *diff_config, + const struct diff_input_info *info, + const char *left, int left_len, const char *right, int right_len) { enum diff_rc rc; left_len = left_len < 0 ? strlen(left) : left_len; blob - 6f150d8601b10ca343db402cf0a6192d675025ae blob + 4596ed14265a10e54dedc012c92f82780602e409 --- diff_output_unidiff.c +++ diff_output_unidiff.c @@ -23,13 +23,14 @@ enum chunk_type { CHUNK_EMPTY, - CHUNK_PLUS, - CHUNK_MINUS, - CHUNK_SAME, - CHUNK_WEIRD, + CHUNK_PLUS, + CHUNK_MINUS, + CHUNK_SAME, + CHUNK_WEIRD, }; -static inline enum chunk_type chunk_type(const struct diff_chunk *chunk) +static inline enum chunk_type +chunk_type(const struct diff_chunk *chunk) { if (!chunk->left_count && !chunk->right_count) return CHUNK_EMPTY; @@ -49,13 +50,15 @@ struct chunk_context { struct range left, right; }; -static bool chunk_context_empty(const struct chunk_context *cc) +static bool +chunk_context_empty(const struct chunk_context *cc) { return range_empty(&cc->chunk); } -static void chunk_context_get(struct chunk_context *cc, const struct diff_result *r, int chunk_idx, - int context_lines) +static void +chunk_context_get(struct chunk_context *cc, const struct diff_result *r, int chunk_idx, + int context_lines) { const struct diff_chunk *c = &r->chunks.head[chunk_idx]; int left_start = diff_atom_root_idx(&r->left, c->left_start); @@ -77,23 +80,25 @@ static void chunk_context_get(struct chunk_context *cc }; } -static bool chunk_contexts_touch(const struct chunk_context *cc, const struct chunk_context *other) +static bool +chunk_contexts_touch(const struct chunk_context *cc, const struct chunk_context *other) { - return ranges_touch(&cc->chunk, &other->chunk) - || ranges_touch(&cc->left, &other->left) - || ranges_touch(&cc->right, &other->right); + return ranges_touch(&cc->chunk, &other->chunk) || + ranges_touch(&cc->left, &other->left) || + ranges_touch(&cc->right, &other->right); } -static void chunk_contexts_merge(struct chunk_context *cc, const struct chunk_context *other) +static void +chunk_contexts_merge(struct chunk_context *cc, const struct chunk_context *other) { ranges_merge(&cc->chunk, &other->chunk); ranges_merge(&cc->left, &other->left); ranges_merge(&cc->right, &other->right); } -static void diff_output_unidiff_chunk(FILE *dest, bool *info_printed, const struct diff_input_info *info, - const struct diff_result *result, const struct chunk_context *cc) -{ +static void +diff_output_unidiff_chunk(FILE *dest, bool *info_printed, const struct diff_input_info *info, + const struct diff_result *result, const struct chunk_context *cc) { if (range_empty(&cc->left) && range_empty(&cc->right)) return; @@ -103,8 +108,8 @@ static void diff_output_unidiff_chunk(FILE *dest, bool } fprintf(dest, "@@ -%d,%d +%d,%d @@\n", - cc->left.start + 1, cc->left.end - cc->left.start, - cc->right.start + 1, cc->right.end - cc->right.start); + cc->left.start + 1, cc->left.end - cc->left.start, + cc->right.start + 1, cc->right.end - cc->right.start); /* Got the absolute line numbers where to start printing, and the index of the interesting (non-context) chunk. * To print context lines above the interesting chunk, nipping on the previous chunk index may be necessary. @@ -113,7 +118,7 @@ static void diff_output_unidiff_chunk(FILE *dest, bool int chunk_start_line = diff_atom_root_idx(&result->left, first_chunk->left_start); if (cc->left.start < chunk_start_line) diff_output_lines(dest, " ", &result->left.atoms.head[cc->left.start], - chunk_start_line - cc->left.start); + chunk_start_line - cc->left.start); /* Now write out all the joined chunks and contexts between them */ int c_idx; @@ -133,12 +138,12 @@ static void diff_output_unidiff_chunk(FILE *dest, bool int chunk_end_line = diff_atom_root_idx(&result->left, last_chunk->left_start + last_chunk->left_count); if (cc->left.end > chunk_end_line) diff_output_lines(dest, " ", &result->left.atoms.head[chunk_end_line], - cc->left.end - chunk_end_line); + cc->left.end - chunk_end_line); } -enum diff_rc diff_output_unidiff(FILE *dest, const struct diff_input_info *info, - const struct diff_result *result, unsigned int context_lines) -{ +enum diff_rc +diff_output_unidiff(FILE *dest, const struct diff_input_info *info, + const struct diff_result *result, unsigned int context_lines) { if (!result) return DIFF_RC_EINVAL; if (result->rc != DIFF_RC_OK) @@ -159,30 +164,30 @@ enum diff_rc diff_output_unidiff(FILE *dest, const str * unidiff chunk by context lines or by being directly adjacent. */ chunk_context_get(&cc, result, i, context_lines); debug("new chunk to be printed: chunk %d-%d left %d-%d right %d-%d\n", - cc.chunk.start, cc.chunk.end, - cc.left.start, cc.left.end, cc.right.start, cc.right.end); + cc.chunk.start, cc.chunk.end, + cc.left.start, cc.left.end, cc.right.start, cc.right.end); } else { /* There already is a previous chunk noted down for being printed. * Does it join up with this one? */ struct chunk_context next; chunk_context_get(&next, result, i, context_lines); debug("new chunk to be printed: chunk %d-%d left %d-%d right %d-%d\n", - next.chunk.start, next.chunk.end, - next.left.start, next.left.end, next.right.start, next.right.end); + next.chunk.start, next.chunk.end, + next.left.start, next.left.end, next.right.start, next.right.end); if (chunk_contexts_touch(&cc, &next)) { /* This next context touches or overlaps the previous one, join. */ chunk_contexts_merge(&cc, &next); debug("new chunk to be printed touches previous chunk, now: left %d-%d right %d-%d\n", - cc.left.start, cc.left.end, cc.right.start, cc.right.end); + cc.left.start, cc.left.end, cc.right.start, cc.right.end); } else { /* No touching, so the previous context is complete with a gap between it and * this next one. Print the previous one and start fresh here. */ debug("new chunk to be printed does not touch previous chunk; print left %d-%d right %d-%d\n", - cc.left.start, cc.left.end, cc.right.start, cc.right.end); + cc.left.start, cc.left.end, cc.right.start, cc.right.end); diff_output_unidiff_chunk(dest, &info_printed, info, result, &cc); cc = next; debug("new unprinted chunk is left %d-%d right %d-%d\n", - cc.left.start, cc.left.end, cc.right.start, cc.right.end); + cc.left.start, cc.left.end, cc.right.start, cc.right.end); } } } @@ -194,10 +199,11 @@ enum diff_rc diff_output_unidiff(FILE *dest, const str return DIFF_RC_OK; } -enum diff_rc diff_unidiff(FILE *dest, const struct diff_config *diff_config, - const struct diff_input_info *info, - const char *left, int left_len, const char *right, int right_len, - unsigned int context_lines) +enum diff_rc +diff_unidiff(FILE *dest, const struct diff_config *diff_config, + const struct diff_input_info *info, + const char *left, int left_len, const char *right, int right_len, + unsigned int context_lines) { enum diff_rc rc; left_len = left_len < 0 ? strlen(left) : left_len; blob - 908e47103b700ab6e429185daa412f3c818239eb blob + f0221d93269d0ae66aec497b9729efe8687aac83 --- diff_patience.c +++ diff_patience.c @@ -27,7 +27,8 @@ #include "debug.h" /* Set unique_here = true for all atoms that exist exactly once in this list. */ -static void diff_atoms_mark_unique(struct diff_data *d, unsigned int *unique_count) +static void +diff_atoms_mark_unique(struct diff_data *d, unsigned int *unique_count) { struct diff_atom *i; unsigned int count = 0; @@ -60,8 +61,9 @@ static void diff_atoms_mark_unique(struct diff_data *d } /* Mark those lines as atom->patience.unique_in_both = true that appear exactly once in each side. */ -static void diff_atoms_mark_unique_in_both(struct diff_data *left, struct diff_data *right, - unsigned int *unique_in_both_count) +static void +diff_atoms_mark_unique_in_both(struct diff_data *left, struct diff_data *right, + unsigned int *unique_in_both_count) { /* Derive the final unique_in_both count without needing an explicit iteration. So this is just some * optimiziation to save one iteration in the end. */ @@ -101,8 +103,8 @@ static void diff_atoms_mark_unique_in_both(struct diff /* Still need to unmark right[*]->patience.unique_in_both for atoms that don't exist in left */ diff_data_foreach_atom(i, right) { - if (!i->patience.unique_here - || !i->patience.unique_in_both) + if (!i->patience.unique_here || + !i->patience.unique_in_both) continue; struct diff_atom *j; bool found_in_a = false; @@ -123,8 +125,9 @@ static void diff_atoms_mark_unique_in_both(struct diff *unique_in_both_count = unique_in_both; } -static void diff_atoms_swallow_identical_neighbors(struct diff_data *left, struct diff_data *right, - unsigned int *unique_in_both_count) +static void +diff_atoms_swallow_identical_neighbors(struct diff_data *left, struct diff_data *right, + unsigned int *unique_in_both_count) { debug("trivially combine identical lines arount unique_in_both lines\n"); @@ -152,20 +155,20 @@ static void diff_atoms_swallow_identical_neighbors(str * All common-unique lines that were part of the identical lines following below were already swallowed * in the previous iteration, so we will never hit another common-unique line above. */ for (identical_l.start = l_idx, identical_r.start = r_idx; - identical_l.start > l_min - && identical_r.start > r_min - && diff_atom_same(&left->atoms.head[identical_l.start - 1], - &right->atoms.head[identical_r.start - 1]); - identical_l.start--, identical_r.start--); + identical_l.start > l_min && + identical_r.start > r_min && + diff_atom_same(&left->atoms.head[identical_l.start - 1], + &right->atoms.head[identical_r.start - 1]); + identical_l.start--, identical_r.start--); /* Swallow downwards */ for (identical_l.end = l_idx + 1, identical_r.end = r_idx + 1; - identical_l.end < left->atoms.len - && identical_r.end < right->atoms.len - && diff_atom_same(&left->atoms.head[identical_l.end], - &right->atoms.head[identical_r.end]); - identical_l.end++, identical_r.end++, - next_l_idx++) { + identical_l.end < left->atoms.len && + identical_r.end < right->atoms.len && + diff_atom_same(&left->atoms.head[identical_l.end], + &right->atoms.head[identical_r.end]); + identical_l.end++, identical_r.end++, + next_l_idx++) { if (left->atoms.head[identical_l.end].patience.unique_in_both) { /* Part of a chunk of identical lines, remove from listing of unique_in_both lines */ left->atoms.head[identical_l.end].patience.unique_in_both = false; @@ -182,9 +185,9 @@ static void diff_atoms_swallow_identical_neighbors(str if (!range_empty(&l->patience.identical_lines)) { debug("common-unique line at l=%u r=%u swallowed identical lines l=%u-%u r=%u-%u\n", - l_idx, r_idx, - identical_l.start, identical_l.end, - identical_r.start, identical_r.end); + l_idx, r_idx, + identical_l.start, identical_l.end, + identical_r.start, identical_r.end); } debug("next_l_idx = %u\n", next_l_idx); } @@ -194,7 +197,8 @@ static void diff_atoms_swallow_identical_neighbors(str * order (with other stuff allowed to interleave). Use patience sort for that, as in the Patience Diff algorithm. * See https://bramcohen.livejournal.com/73318.html and, for a much more detailed explanation, * https://blog.jcoglan.com/2017/09/19/the-patience-diff-algorithm/ */ -enum diff_rc diff_algo_patience(const struct diff_algo_config *algo_config, struct diff_state *state) +enum diff_rc +diff_algo_patience(const struct diff_algo_config *algo_config, struct diff_state *state) { enum diff_rc rc = DIFF_RC_ENOMEM; @@ -221,7 +225,7 @@ enum diff_rc diff_algo_patience(const struct diff_algo diff_atoms_swallow_identical_neighbors(left, right, &unique_in_both_count); debug("After swallowing identical neighbors: unique_in_both = %u\n", - unique_in_both_count); + unique_in_both_count); /* An array of Longest Common Sequence is the result of the below subscope: */ unsigned int lcs_count = 0; @@ -335,12 +339,12 @@ enum diff_rc diff_algo_patience(const struct diff_algo atom = lcs[i]; atom_r = atom->patience.pos_in_other; debug("lcs[%u] = left[%u] = right[%u]\n", i, - diff_atom_idx(left, atom), diff_atom_idx(right, atom_r)); + diff_atom_idx(left, atom), diff_atom_idx(right, atom_r)); left_idx = atom->patience.identical_lines.start; right_idx = atom_r->patience.identical_lines.start; debug(" identical lines l %u-%u r %u-%u\n", - atom->patience.identical_lines.start, atom->patience.identical_lines.end, - atom_r->patience.identical_lines.start, atom_r->patience.identical_lines.end); + atom->patience.identical_lines.start, atom->patience.identical_lines.end, + atom_r->patience.identical_lines.start, atom_r->patience.identical_lines.end); } else { atom = NULL; atom_r = NULL; @@ -359,7 +363,7 @@ enum diff_rc diff_algo_patience(const struct diff_algo * left_idx and right_idx mark the indexes of the matching atom on left and right, respectively. */ debug("iteration %u left_pos %u left_idx %u right_pos %u right_idx %u\n", - i, left_pos, left_idx, right_pos, right_idx); + i, left_pos, left_idx, right_pos, right_idx); struct diff_chunk *chunk; @@ -373,20 +377,20 @@ enum diff_rc diff_algo_patience(const struct diff_algo if (left_section_len && right_section_len) { /* Record an unsolved chunk, the caller will apply inner_algo() on this chunk. */ if (!diff_state_add_chunk(state, false, - left_atom, left_section_len, - right_atom, right_section_len)) + left_atom, left_section_len, + right_atom, right_section_len)) goto return_rc; } else if (left_section_len && !right_section_len) { /* Only left atoms and none on the right, they form a "minus" chunk, then. */ if (!diff_state_add_chunk(state, true, - left_atom, left_section_len, - right_atom, 0)) + left_atom, left_section_len, + right_atom, 0)) goto return_rc; } else if (!left_section_len && right_section_len) { /* No left atoms, only atoms on the right, they form a "plus" chunk, then. */ if (!diff_state_add_chunk(state, true, - left_atom, 0, - right_atom, right_section_len)) + left_atom, 0, + right_atom, right_section_len)) goto return_rc; } /* else: left_section_len == 0 and right_section_len == 0, i.e. nothing here. */ @@ -395,10 +399,10 @@ enum diff_rc diff_algo_patience(const struct diff_algo * iteration of this loop, there is no matching atom, we were just cleaning out the remaining lines. */ if (atom) { if (!diff_state_add_chunk(state, true, - left->atoms.head + atom->patience.identical_lines.start, - range_len(&atom->patience.identical_lines), - right->atoms.head + atom_r->patience.identical_lines.start, - range_len(&atom_r->patience.identical_lines))) + left->atoms.head + atom->patience.identical_lines.start, + range_len(&atom->patience.identical_lines), + right->atoms.head + atom_r->patience.identical_lines.start, + range_len(&atom_r->patience.identical_lines))) goto return_rc; left_pos = atom->patience.identical_lines.end; right_pos = atom_r->patience.identical_lines.end; @@ -407,7 +411,7 @@ enum diff_rc diff_algo_patience(const struct diff_algo right_pos = right_idx + 1; } debug("end of iteration %u left_pos %u left_idx %u right_pos %u right_idx %u\n", - i, left_pos, left_idx, right_pos, right_idx); + i, left_pos, left_idx, right_pos, right_idx); } debug("** END %s\n", __func__);