commit - 76670af02746b4cc2a4a26dca93072a682d48232
commit + b5a3e4d3220d54590de58ecf5a2199285e3f9263
blob - 587e4a52f34ec4f3ac54347a4b14c7d44c2d746a
blob + 8128ea1989ba2ca2f9365f3c7489680e23224221
--- diff.c
+++ diff.c
/* 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
#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;
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
/* 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;
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,
};
}
-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,
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;
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");
/* 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);
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)
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
* 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;
* 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.
*/
}
/* 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) {
}
}
- 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
*
* 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);
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,
.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;
}
}
* 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;
* 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.
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]]);
}
}
- 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
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,
.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;
}
}
/* 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;
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");
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. */
/* 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. */
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. */
/* 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. */
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;
}
* 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.
*/
}
/* 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)
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;
}
}
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)
* | 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;
}
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;
* 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--;
}
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
#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) {
}
}
-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
#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)
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
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;
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);
};
}
-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;
}
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.
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;
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)
* 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);
}
}
}
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
#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;
}
/* 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. */
/* 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;
*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");
* 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;
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);
}
* 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;
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;
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;
* 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;
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. */
* 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;
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__);
