1 /* Generic infrastructure to implement various diff algorithms (implementation). */
3 * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
19 #include <sys/queue.h>
32 #include <diff/arraylist.h>
33 #include <diff/diff_main.h>
35 #include "diff_debug.h"
38 read_at(int fd, int at_pos, unsigned char *buf, size_t len)
41 if (lseek(fd, at_pos, SEEK_SET) == -1)
43 r = read(fd, buf, len);
52 buf_cmp(const unsigned char *left, size_t left_len,
53 const unsigned char *right, size_t right_len,
54 bool ignore_whitespace)
58 if (ignore_whitespace) {
60 while (il < left_len && ir < right_len) {
61 unsigned char cl = left[il];
62 unsigned char cr = right[ir];
64 if (isspace(cl) && il < left_len) {
68 if (isspace(cr) && ir < right_len) {
80 while (il < left_len) {
81 unsigned char cl = left[il++];
85 while (ir < right_len) {
86 unsigned char cr = right[ir++];
94 cmp = memcmp(left, right, MIN(left_len, right_len));
97 if (left_len == right_len)
99 return (left_len > right_len) ? 1 : -1;
103 diff_atom_cmp(int *cmp,
104 const struct diff_atom *left,
105 const struct diff_atom *right)
107 off_t remain_left, remain_right;
108 bool ignore_whitespace;
110 ignore_whitespace = (left->d->root->ignore_whitespace ||
111 right->d->root->ignore_whitespace);
113 if (!ignore_whitespace) {
114 if (!left->len && !right->len) {
128 if (left->at != NULL && right->at != NULL) {
129 *cmp = buf_cmp(left->at, left->len, right->at, right->len,
134 remain_left = left->len;
135 remain_right = right->len;
136 while (remain_left > 0 || remain_right > 0) {
137 const size_t chunksz = 8192;
138 unsigned char buf_left[chunksz], buf_right[chunksz];
139 const uint8_t *p_left, *p_right;
140 off_t n_left, n_right;
152 n_left = MIN(chunksz, remain_left);
153 n_right = MIN(chunksz, remain_right);
155 if (left->at == NULL) {
156 r = read_at(left->d->root->fd,
157 left->pos + (left->len - remain_left),
165 p_left = left->at + (left->len - remain_left);
168 if (right->at == NULL) {
169 r = read_at(right->d->root->fd,
170 right->pos + (right->len - remain_right),
178 p_right = right->at + (right->len - remain_right);
181 r = buf_cmp(p_left, n_left, p_right, n_right,
188 remain_left -= n_left;
189 remain_right -= n_right;
197 diff_atom_same(bool *same,
198 const struct diff_atom *left,
199 const struct diff_atom *right)
202 int r = diff_atom_cmp(&cmp, left, right);
211 /* Even if a left or right side is empty, diff output may need to know the
212 * position in that file.
213 * So left_start or right_start must never be NULL -- pass left_count or
214 * right_count as zero to indicate staying at that position without consuming
217 diff_state_add_chunk(struct diff_state *state, bool solved,
218 struct diff_atom *left_start, unsigned int left_count,
219 struct diff_atom *right_start, unsigned int right_count)
221 diff_chunk_arraylist_t *result = NULL;
222 struct diff_chunk *new_chunk;
223 struct diff_chunk chunk = {
225 .left_start = left_start,
226 .left_count = left_count,
227 .right_start = right_start,
228 .right_count = right_count,
230 enum diff_chunk_type last_t;
231 enum diff_chunk_type prev_last_t;
232 enum diff_chunk_type new_t;
234 if (!solved || state->temp_result.len) {
235 /* Append to temp_result */
236 result = &state->temp_result;
237 } else if (!state->result->chunks.len) {
238 /* Append to final result */
239 result = &state->result->chunks;
242 ARRAYLIST_ADD(new_chunk, *result);
249 /* Append to solved chunks; make sure that adjacent chunks of same type are combined, and that a minus chunk
250 * never directly follows a plus chunk. */
251 result = &state->result->chunks;
253 prev_last_t = result->len > 1 ?
254 diff_chunk_type(&result->head[result->len - 2]) : CHUNK_EMPTY;
255 last_t = diff_chunk_type(&result->head[result->len - 1]);
256 new_t = diff_chunk_type(&chunk);
258 if (new_t == last_t) {
259 new_chunk = &result->head[result->len - 1];
260 new_chunk->left_count += chunk.left_count;
261 new_chunk->right_count += chunk.right_count;
262 } else if (last_t == CHUNK_PLUS && new_t == CHUNK_MINUS) {
263 /* If a minus-chunk follows a plus-chunk, place it above the plus-chunk.
264 * Is the one before that also a minus? combine. */
265 if (prev_last_t == CHUNK_MINUS) {
266 new_chunk = &result->head[result->len - 2];
267 new_chunk->left_count += chunk.left_count;
268 new_chunk->right_count += chunk.right_count;
270 ARRAYLIST_INSERT(new_chunk, *result, result->len - 2);
276 ARRAYLIST_ADD(new_chunk, *result);
284 debug("Add %s chunk:\n", new_chunk->solved ? "solved" : "UNSOLVED");
286 debug_dump_atoms(&state->left, new_chunk->left_start, new_chunk->left_count);
288 debug_dump_atoms(&state->right, new_chunk->right_start, new_chunk->right_count);
293 diff_data_init_root(struct diff_data *d, int fd, const uint8_t *data,
294 unsigned long long len, bool ignore_whitespace)
296 *d = (struct diff_data){
302 .ignore_whitespace = ignore_whitespace,
307 diff_data_init_subsection(struct diff_data *d, struct diff_data *parent,
308 struct diff_atom *from_atom, unsigned int atoms_count)
310 struct diff_atom *last_atom = from_atom + atoms_count - 1;
311 *d = (struct diff_data){
313 .pos = from_atom->pos,
314 .data = from_atom->at,
315 .len = (last_atom->pos + last_atom->len) - from_atom->pos,
316 .root = parent->root,
317 .atoms.head = from_atom,
318 .atoms.len = atoms_count,
321 debug("subsection:\n");
326 diff_data_free(struct diff_data *diff_data)
330 if (diff_data->atoms.allocated)
331 ARRAYLIST_FREE(diff_data->atoms);
335 diff_algo_none(const struct diff_algo_config *algo_config,
336 struct diff_state *state)
338 debug("\n** %s\n", __func__);
340 debug_dump(&state->left);
342 debug_dump(&state->right);
343 debug_dump_myers_graph(&state->left, &state->right, NULL, NULL, 0, NULL,
346 /* Add a chunk of equal lines, if any */
347 unsigned int equal_atoms = 0;
348 while (equal_atoms < state->left.atoms.len
349 && equal_atoms < state->right.atoms.len) {
352 r = diff_atom_same(&same, &state->left.atoms.head[equal_atoms],
353 &state->right.atoms.head[equal_atoms]);
361 if (!diff_state_add_chunk(state, true,
362 &state->left.atoms.head[0],
364 &state->right.atoms.head[0],
369 /* Add a "minus" chunk with all lines from the left. */
370 if (equal_atoms < state->left.atoms.len) {
371 if (!diff_state_add_chunk(state, true,
372 &state->left.atoms.head[equal_atoms],
373 state->left.atoms.len - equal_atoms,
378 /* Add a "plus" chunk with all lines from the right. */
379 if (equal_atoms < state->right.atoms.len) {
380 if (!diff_state_add_chunk(state, true,
382 &state->right.atoms.head[equal_atoms],
383 state->right.atoms.len - equal_atoms))
390 diff_run_algo(const struct diff_algo_config *algo_config,
391 struct diff_state *state)
394 ARRAYLIST_FREE(state->temp_result);
396 if (!algo_config || !algo_config->impl
397 || !state->recursion_depth_left) {
398 debug("MAX RECURSION REACHED, just dumping diff chunks\n");
399 return diff_algo_none(algo_config, state);
402 ARRAYLIST_INIT(state->temp_result, DIFF_RESULT_ALLOC_BLOCKSIZE);
403 rc = algo_config->impl(algo_config, state);
405 case DIFF_RC_USE_DIFF_ALGO_FALLBACK:
406 debug("Got DIFF_RC_USE_DIFF_ALGO_FALLBACK (%p)\n",
407 algo_config->fallback_algo);
408 rc = diff_run_algo(algo_config->fallback_algo, state);
416 /* some error happened */
420 /* Pick up any diff chunks that are still unsolved and feed to
421 * inner_algo. inner_algo will solve unsolved chunks and append to
422 * result, and subsequent solved chunks on this level are then appended
423 * to result afterwards. */
425 for (i = 0; i < state->temp_result.len; i++) {
426 struct diff_chunk *c = &state->temp_result.head[i];
428 struct diff_chunk *final_c;
429 ARRAYLIST_ADD(final_c, state->result->chunks);
438 /* c is an unsolved chunk, feed to inner_algo */
439 struct diff_state inner_state = {
440 .result = state->result,
441 .recursion_depth_left = state->recursion_depth_left - 1,
443 diff_data_init_subsection(&inner_state.left, &state->left,
444 c->left_start, c->left_count);
445 diff_data_init_subsection(&inner_state.right, &state->right,
446 c->right_start, c->right_count);
448 rc = diff_run_algo(algo_config->inner_algo, &inner_state);
450 if (rc != DIFF_RC_OK)
456 ARRAYLIST_FREE(state->temp_result);
461 diff_main(const struct diff_config *config,
462 int left_fd, const uint8_t *left_data, off_t left_len,
463 int right_fd, const uint8_t *right_data, off_t right_len,
464 bool ignore_whitespace)
466 struct diff_result *result = malloc(sizeof(struct diff_result));
470 *result = (struct diff_result){};
471 diff_data_init_root(&result->left, left_fd, left_data, left_len,
473 diff_data_init_root(&result->right, right_fd, right_data, right_len,
476 if (!config->atomize_func) {
481 result->rc = config->atomize_func(config->atomize_func_data,
482 &result->left, &result->right);
483 if (result->rc != DIFF_RC_OK)
486 struct diff_state state = {
488 .recursion_depth_left = config->max_recursion_depth ? : 32,
490 diff_data_init_subsection(&state.left, &result->left,
491 result->left.atoms.head,
492 result->left.atoms.len);
493 diff_data_init_subsection(&state.right, &result->right,
494 result->right.atoms.head,
495 result->right.atoms.len);
497 result->rc = diff_run_algo(config->algo, &state);
503 diff_result_free(struct diff_result *result)
507 diff_data_free(&result->left);
508 diff_data_free(&result->right);
509 ARRAYLIST_FREE(result->chunks);