1 3b0f3d61 2020-01-22 neels /* Generic infrastructure to implement various diff algorithms (implementation). */
3 3b0f3d61 2020-01-22 neels * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
5 3b0f3d61 2020-01-22 neels * Permission to use, copy, modify, and distribute this software for any
6 3b0f3d61 2020-01-22 neels * purpose with or without fee is hereby granted, provided that the above
7 3b0f3d61 2020-01-22 neels * copyright notice and this permission notice appear in all copies.
9 3b0f3d61 2020-01-22 neels * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 3b0f3d61 2020-01-22 neels * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 3b0f3d61 2020-01-22 neels * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 3b0f3d61 2020-01-22 neels * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 3b0f3d61 2020-01-22 neels * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 3b0f3d61 2020-01-22 neels * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 3b0f3d61 2020-01-22 neels * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
19 3b0f3d61 2020-01-22 neels #include <sys/queue.h>
20 e10a628a 2020-09-16 stsp #include <errno.h>
21 3b0f3d61 2020-01-22 neels #include <stdint.h>
22 3b0f3d61 2020-01-22 neels #include <stdlib.h>
23 3b0f3d61 2020-01-22 neels #include <stdbool.h>
24 3b0f3d61 2020-01-22 neels #include <stdio.h>
25 3b0f3d61 2020-01-22 neels #include <string.h>
26 3b0f3d61 2020-01-22 neels #include <limits.h>
27 c6eecea3 2020-07-26 stsp #include <unistd.h>
29 3b0f3d61 2020-01-22 neels #include <assert.h>
31 e10a628a 2020-09-16 stsp #include <diff/arraylist.h>
32 3b0f3d61 2020-01-22 neels #include <diff/diff_main.h>
34 3b0f3d61 2020-01-22 neels #include "debug.h"
37 b3fb4686 2020-09-20 neels read_at(int fd, int at_pos, unsigned char *buf, size_t len)
40 b3fb4686 2020-09-20 neels if (lseek(fd, at_pos, SEEK_SET) == -1)
41 b3fb4686 2020-09-20 neels return errno;
42 b3fb4686 2020-09-20 neels r = read(fd, buf, len);
43 b3fb4686 2020-09-20 neels if (r == -1)
44 b3fb4686 2020-09-20 neels return errno;
45 b3fb4686 2020-09-20 neels if (r != len)
46 b3fb4686 2020-09-20 neels return EIO;
51 b3fb4686 2020-09-20 neels buf_cmp(const unsigned char *left, size_t left_len,
52 b3fb4686 2020-09-20 neels const unsigned char *right, size_t right_len)
54 b3fb4686 2020-09-20 neels int cmp = memcmp(left, right, MIN(left_len, right_len));
56 b3fb4686 2020-09-20 neels return cmp;
57 b3fb4686 2020-09-20 neels if (left_len == right_len)
59 b3fb4686 2020-09-20 neels return (left_len > right_len) ? 1 : -1;
63 b3fb4686 2020-09-20 neels diff_atom_cmp(int *cmp,
64 b3fb4686 2020-09-20 neels const struct diff_atom *left,
65 b3fb4686 2020-09-20 neels const struct diff_atom *right)
67 c6eecea3 2020-07-26 stsp off_t remain_left, remain_right;
69 b3fb4686 2020-09-20 neels if (!left->len && !right->len) {
73 b3fb4686 2020-09-20 neels if (!right->len) {
77 b3fb4686 2020-09-20 neels if (!left->len) {
82 b3fb4686 2020-09-20 neels if (left->at != NULL && right->at != NULL) {
83 b3fb4686 2020-09-20 neels *cmp = buf_cmp(left->at, left->len, right->at, right->len);
87 c6eecea3 2020-07-26 stsp remain_left = left->len;
88 c6eecea3 2020-07-26 stsp remain_right = right->len;
89 c6eecea3 2020-07-26 stsp while (remain_left > 0 || remain_right > 0) {
90 c6eecea3 2020-07-26 stsp const size_t chunksz = 8192;
91 c6eecea3 2020-07-26 stsp unsigned char buf_left[chunksz], buf_right[chunksz];
92 c6eecea3 2020-07-26 stsp const uint8_t *p_left, *p_right;
93 c6eecea3 2020-07-26 stsp off_t n_left, n_right;
96 b3fb4686 2020-09-20 neels if (!remain_right) {
100 b3fb4686 2020-09-20 neels if (!remain_left) {
101 b3fb4686 2020-09-20 neels *cmp = -1;
105 c6eecea3 2020-07-26 stsp n_left = MIN(chunksz, remain_left);
106 c6eecea3 2020-07-26 stsp n_right = MIN(chunksz, remain_right);
108 c6eecea3 2020-07-26 stsp if (left->at == NULL) {
109 b3fb4686 2020-09-20 neels r = read_at(left->d->root->fd,
110 b3fb4686 2020-09-20 neels left->pos + (left->len - remain_left),
111 b3fb4686 2020-09-20 neels buf_left, n_left);
116 c6eecea3 2020-07-26 stsp p_left = buf_left;
118 c6eecea3 2020-07-26 stsp p_left = left->at + (left->len - remain_left);
121 c6eecea3 2020-07-26 stsp if (right->at == NULL) {
122 b3fb4686 2020-09-20 neels r = read_at(right->d->root->fd,
123 b3fb4686 2020-09-20 neels right->pos + (right->len - remain_right),
124 b3fb4686 2020-09-20 neels buf_right, n_right);
129 c6eecea3 2020-07-26 stsp p_right = buf_right;
131 c6eecea3 2020-07-26 stsp p_right = right->at + (right->len - remain_right);
134 b3fb4686 2020-09-20 neels r = buf_cmp(p_left, n_left, p_right, n_right);
140 c6eecea3 2020-07-26 stsp remain_left -= n_left;
141 c6eecea3 2020-07-26 stsp remain_right -= n_right;
149 b3fb4686 2020-09-20 neels diff_atom_same(bool *same,
150 b3fb4686 2020-09-20 neels const struct diff_atom *left,
151 b3fb4686 2020-09-20 neels const struct diff_atom *right)
154 b3fb4686 2020-09-20 neels int r = diff_atom_cmp(&cmp, left, right);
156 b3fb4686 2020-09-20 neels *same = true;
159 b3fb4686 2020-09-20 neels *same = (cmp == 0);
163 0d27172a 2020-05-06 neels /* Even if a left or right side is empty, diff output may need to know the
164 0d27172a 2020-05-06 neels * position in that file.
165 0d27172a 2020-05-06 neels * So left_start or right_start must never be NULL -- pass left_count or
166 0d27172a 2020-05-06 neels * right_count as zero to indicate staying at that position without consuming
167 0d27172a 2020-05-06 neels * any lines. */
168 61a7b578 2020-05-06 neels struct diff_chunk *
169 61a7b578 2020-05-06 neels diff_state_add_chunk(struct diff_state *state, bool solved,
170 61a7b578 2020-05-06 neels struct diff_atom *left_start, unsigned int left_count,
171 61a7b578 2020-05-06 neels struct diff_atom *right_start, unsigned int right_count)
173 8546b045 2020-09-20 neels diff_chunk_arraylist_t *result = NULL;
174 8546b045 2020-09-20 neels struct diff_chunk *new_chunk;
175 8546b045 2020-09-20 neels struct diff_chunk chunk = {
176 3b0f3d61 2020-01-22 neels .solved = solved,
177 3b0f3d61 2020-01-22 neels .left_start = left_start,
178 3b0f3d61 2020-01-22 neels .left_count = left_count,
179 3b0f3d61 2020-01-22 neels .right_start = right_start,
180 3b0f3d61 2020-01-22 neels .right_count = right_count,
182 8546b045 2020-09-20 neels enum diff_chunk_type last_t;
183 8546b045 2020-09-20 neels enum diff_chunk_type prev_last_t;
184 8546b045 2020-09-20 neels enum diff_chunk_type new_t;
186 8546b045 2020-09-20 neels if (!solved || state->temp_result.len) {
187 8546b045 2020-09-20 neels /* Append to temp_result */
188 8546b045 2020-09-20 neels result = &state->temp_result;
189 8546b045 2020-09-20 neels } else if (!state->result->chunks.len) {
190 8546b045 2020-09-20 neels /* Append to final result */
191 8546b045 2020-09-20 neels result = &state->result->chunks;
193 8546b045 2020-09-20 neels if (result) {
194 8546b045 2020-09-20 neels ARRAYLIST_ADD(new_chunk, *result);
195 8546b045 2020-09-20 neels if (!new_chunk)
196 8546b045 2020-09-20 neels return NULL;
197 8546b045 2020-09-20 neels *new_chunk = chunk;
198 8546b045 2020-09-20 neels goto chunk_added;
201 8546b045 2020-09-20 neels /* Append to solved chunks; make sure that adjacent chunks of same type are combined, and that a minus chunk
202 8546b045 2020-09-20 neels * never directly follows a plus chunk. */
203 8546b045 2020-09-20 neels result = &state->result->chunks;
205 8546b045 2020-09-20 neels prev_last_t = result->len > 1 ?
206 8546b045 2020-09-20 neels diff_chunk_type(&result->head[result->len - 2]) : CHUNK_EMPTY;
207 8546b045 2020-09-20 neels last_t = diff_chunk_type(&result->head[result->len - 1]);
208 8546b045 2020-09-20 neels new_t = diff_chunk_type(&chunk);
210 8546b045 2020-09-20 neels if (new_t == last_t) {
211 8546b045 2020-09-20 neels new_chunk = &result->head[result->len - 1];
212 8546b045 2020-09-20 neels new_chunk->left_count += chunk.left_count;
213 8546b045 2020-09-20 neels new_chunk->right_count += chunk.right_count;
214 8546b045 2020-09-20 neels } else if (last_t == CHUNK_PLUS && new_t == CHUNK_MINUS) {
215 8546b045 2020-09-20 neels /* If a minus-chunk follows a plus-chunk, place it above the plus-chunk.
216 8546b045 2020-09-20 neels * Is the one before that also a minus? combine. */
217 8546b045 2020-09-20 neels if (prev_last_t == CHUNK_MINUS) {
218 8546b045 2020-09-20 neels new_chunk = &result->head[result->len - 2];
219 8546b045 2020-09-20 neels new_chunk->left_count += chunk.left_count;
220 8546b045 2020-09-20 neels new_chunk->right_count += chunk.right_count;
222 8546b045 2020-09-20 neels ARRAYLIST_INSERT(new_chunk, *result, result->len - 2);
223 8546b045 2020-09-20 neels if (!new_chunk)
224 8546b045 2020-09-20 neels return NULL;
225 8546b045 2020-09-20 neels *new_chunk = chunk;
228 8546b045 2020-09-20 neels ARRAYLIST_ADD(new_chunk, *result);
229 8546b045 2020-09-20 neels if (!new_chunk)
230 8546b045 2020-09-20 neels return NULL;
231 8546b045 2020-09-20 neels *new_chunk = chunk;
232 8546b045 2020-09-20 neels goto chunk_added;
235 8546b045 2020-09-20 neels chunk_added:
236 8546b045 2020-09-20 neels debug("Add %s chunk:\n", new_chunk->solved ? "solved" : "UNSOLVED");
237 8546b045 2020-09-20 neels debug("L\n");
238 8546b045 2020-09-20 neels debug_dump_atoms(&state->left, new_chunk->left_start, new_chunk->left_count);
239 3b0f3d61 2020-01-22 neels debug("R\n");
240 8546b045 2020-09-20 neels debug_dump_atoms(&state->right, new_chunk->right_start, new_chunk->right_count);
241 8546b045 2020-09-20 neels return new_chunk;
245 c6eecea3 2020-07-26 stsp diff_data_init_root(struct diff_data *d, int fd, const uint8_t *data,
246 c6eecea3 2020-07-26 stsp unsigned long long len)
248 3b0f3d61 2020-01-22 neels *d = (struct diff_data){
251 3b0f3d61 2020-01-22 neels .data = data,
252 3b0f3d61 2020-01-22 neels .len = len,
253 3b0f3d61 2020-01-22 neels .root = d,
258 61a7b578 2020-05-06 neels diff_data_init_subsection(struct diff_data *d, struct diff_data *parent,
259 61a7b578 2020-05-06 neels struct diff_atom *from_atom, unsigned int atoms_count)
261 3b0f3d61 2020-01-22 neels struct diff_atom *last_atom = from_atom + atoms_count - 1;
262 3b0f3d61 2020-01-22 neels *d = (struct diff_data){
264 c6eecea3 2020-07-26 stsp .pos = from_atom->pos,
265 3b0f3d61 2020-01-22 neels .data = from_atom->at,
266 c6eecea3 2020-07-26 stsp .len = (last_atom->pos + last_atom->len) - from_atom->pos,
267 3b0f3d61 2020-01-22 neels .root = parent->root,
268 3b0f3d61 2020-01-22 neels .atoms.head = from_atom,
269 3b0f3d61 2020-01-22 neels .atoms.len = atoms_count,
272 3b0f3d61 2020-01-22 neels debug("subsection:\n");
273 3b0f3d61 2020-01-22 neels debug_dump(d);
277 61a7b578 2020-05-06 neels diff_data_free(struct diff_data *diff_data)
279 3b0f3d61 2020-01-22 neels if (!diff_data)
281 3b0f3d61 2020-01-22 neels if (diff_data->atoms.allocated)
282 3b0f3d61 2020-01-22 neels ARRAYLIST_FREE(diff_data->atoms);
286 0d27172a 2020-05-06 neels diff_algo_none(const struct diff_algo_config *algo_config,
287 0d27172a 2020-05-06 neels struct diff_state *state)
289 3b0f3d61 2020-01-22 neels debug("\n** %s\n", __func__);
290 3b0f3d61 2020-01-22 neels debug("left:\n");
291 3b0f3d61 2020-01-22 neels debug_dump(&state->left);
292 3b0f3d61 2020-01-22 neels debug("right:\n");
293 3b0f3d61 2020-01-22 neels debug_dump(&state->right);
294 0d27172a 2020-05-06 neels debug_dump_myers_graph(&state->left, &state->right, NULL, NULL, 0, NULL,
297 3b0f3d61 2020-01-22 neels /* Add a chunk of equal lines, if any */
298 3b0f3d61 2020-01-22 neels unsigned int equal_atoms = 0;
299 0d27172a 2020-05-06 neels while (equal_atoms < state->left.atoms.len
300 b3fb4686 2020-09-20 neels && equal_atoms < state->right.atoms.len) {
302 b3fb4686 2020-09-20 neels bool same;
303 b3fb4686 2020-09-20 neels r = diff_atom_same(&same, &state->left.atoms.head[equal_atoms],
304 b3fb4686 2020-09-20 neels &state->right.atoms.head[equal_atoms]);
307 b3fb4686 2020-09-20 neels if (!same)
309 3b0f3d61 2020-01-22 neels equal_atoms++;
311 3b0f3d61 2020-01-22 neels if (equal_atoms) {
312 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
313 0d27172a 2020-05-06 neels &state->left.atoms.head[0],
314 0d27172a 2020-05-06 neels equal_atoms,
315 0d27172a 2020-05-06 neels &state->right.atoms.head[0],
316 0d27172a 2020-05-06 neels equal_atoms))
317 3e6cba3a 2020-08-13 stsp return ENOMEM;
320 3b0f3d61 2020-01-22 neels /* Add a "minus" chunk with all lines from the left. */
321 3b0f3d61 2020-01-22 neels if (equal_atoms < state->left.atoms.len) {
322 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
323 3b0f3d61 2020-01-22 neels &state->left.atoms.head[equal_atoms],
324 3b0f3d61 2020-01-22 neels state->left.atoms.len - equal_atoms,
326 3e6cba3a 2020-08-13 stsp return ENOMEM;
329 3b0f3d61 2020-01-22 neels /* Add a "plus" chunk with all lines from the right. */
330 3b0f3d61 2020-01-22 neels if (equal_atoms < state->right.atoms.len) {
331 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
333 3b0f3d61 2020-01-22 neels &state->right.atoms.head[equal_atoms],
334 3b0f3d61 2020-01-22 neels state->right.atoms.len - equal_atoms))
335 3e6cba3a 2020-08-13 stsp return ENOMEM;
337 3b0f3d61 2020-01-22 neels return DIFF_RC_OK;
341 0d27172a 2020-05-06 neels diff_run_algo(const struct diff_algo_config *algo_config,
342 0d27172a 2020-05-06 neels struct diff_state *state)
345 3b0f3d61 2020-01-22 neels ARRAYLIST_FREE(state->temp_result);
347 0d27172a 2020-05-06 neels if (!algo_config || !algo_config->impl
348 0d27172a 2020-05-06 neels || !state->recursion_depth_left) {
349 3b0f3d61 2020-01-22 neels debug("MAX RECURSION REACHED, just dumping diff chunks\n");
350 3b0f3d61 2020-01-22 neels return diff_algo_none(algo_config, state);
353 3b0f3d61 2020-01-22 neels ARRAYLIST_INIT(state->temp_result, DIFF_RESULT_ALLOC_BLOCKSIZE);
354 3b0f3d61 2020-01-22 neels rc = algo_config->impl(algo_config, state);
355 3b0f3d61 2020-01-22 neels switch (rc) {
356 3b0f3d61 2020-01-22 neels case DIFF_RC_USE_DIFF_ALGO_FALLBACK:
357 0d27172a 2020-05-06 neels debug("Got DIFF_RC_USE_DIFF_ALGO_FALLBACK (%p)\n",
358 0d27172a 2020-05-06 neels algo_config->fallback_algo);
359 3b0f3d61 2020-01-22 neels rc = diff_run_algo(algo_config->fallback_algo, state);
360 3b0f3d61 2020-01-22 neels goto return_rc;
362 3b0f3d61 2020-01-22 neels case DIFF_RC_OK:
363 3b0f3d61 2020-01-22 neels /* continue below */
367 3b0f3d61 2020-01-22 neels /* some error happened */
368 3b0f3d61 2020-01-22 neels goto return_rc;
371 0d27172a 2020-05-06 neels /* Pick up any diff chunks that are still unsolved and feed to
372 0d27172a 2020-05-06 neels * inner_algo. inner_algo will solve unsolved chunks and append to
373 0d27172a 2020-05-06 neels * result, and subsequent solved chunks on this level are then appended
374 0d27172a 2020-05-06 neels * to result afterwards. */
376 3b0f3d61 2020-01-22 neels for (i = 0; i < state->temp_result.len; i++) {
377 3b0f3d61 2020-01-22 neels struct diff_chunk *c = &state->temp_result.head[i];
378 3b0f3d61 2020-01-22 neels if (c->solved) {
379 3b0f3d61 2020-01-22 neels struct diff_chunk *final_c;
380 3b0f3d61 2020-01-22 neels ARRAYLIST_ADD(final_c, state->result->chunks);
381 3b0f3d61 2020-01-22 neels if (!final_c) {
382 3e6cba3a 2020-08-13 stsp rc = ENOMEM;
383 3b0f3d61 2020-01-22 neels goto return_rc;
385 3b0f3d61 2020-01-22 neels *final_c = *c;
389 3b0f3d61 2020-01-22 neels /* c is an unsolved chunk, feed to inner_algo */
390 3b0f3d61 2020-01-22 neels struct diff_state inner_state = {
391 3b0f3d61 2020-01-22 neels .result = state->result,
392 3b0f3d61 2020-01-22 neels .recursion_depth_left = state->recursion_depth_left - 1,
394 0d27172a 2020-05-06 neels diff_data_init_subsection(&inner_state.left, &state->left,
395 0d27172a 2020-05-06 neels c->left_start, c->left_count);
396 0d27172a 2020-05-06 neels diff_data_init_subsection(&inner_state.right, &state->right,
397 0d27172a 2020-05-06 neels c->right_start, c->right_count);
399 3b0f3d61 2020-01-22 neels rc = diff_run_algo(algo_config->inner_algo, &inner_state);
401 3b0f3d61 2020-01-22 neels if (rc != DIFF_RC_OK)
402 3b0f3d61 2020-01-22 neels goto return_rc;
405 3b0f3d61 2020-01-22 neels rc = DIFF_RC_OK;
406 3b0f3d61 2020-01-22 neels return_rc:
407 3b0f3d61 2020-01-22 neels ARRAYLIST_FREE(state->temp_result);
408 3b0f3d61 2020-01-22 neels return rc;
411 61a7b578 2020-05-06 neels struct diff_result *
412 61a7b578 2020-05-06 neels diff_main(const struct diff_config *config,
413 c6eecea3 2020-07-26 stsp int left_fd, const uint8_t *left_data, off_t left_len,
414 c6eecea3 2020-07-26 stsp int right_fd, const uint8_t *right_data, off_t right_len)
416 3b0f3d61 2020-01-22 neels struct diff_result *result = malloc(sizeof(struct diff_result));
417 3b0f3d61 2020-01-22 neels if (!result)
418 3b0f3d61 2020-01-22 neels return NULL;
420 3b0f3d61 2020-01-22 neels *result = (struct diff_result){};
421 c6eecea3 2020-07-26 stsp diff_data_init_root(&result->left, left_fd, left_data, left_len);
422 c6eecea3 2020-07-26 stsp diff_data_init_root(&result->right, right_fd, right_data, right_len);
424 3b0f3d61 2020-01-22 neels if (!config->atomize_func) {
425 3e6cba3a 2020-08-13 stsp result->rc = EINVAL;
426 3b0f3d61 2020-01-22 neels return result;
429 0d27172a 2020-05-06 neels result->rc = config->atomize_func(config->atomize_func_data,
430 0d27172a 2020-05-06 neels &result->left, &result->right);
431 3b0f3d61 2020-01-22 neels if (result->rc != DIFF_RC_OK)
432 3b0f3d61 2020-01-22 neels return result;
434 3b0f3d61 2020-01-22 neels struct diff_state state = {
435 3b0f3d61 2020-01-22 neels .result = result,
436 3b0f3d61 2020-01-22 neels .recursion_depth_left = config->max_recursion_depth ? : 1024,
438 0d27172a 2020-05-06 neels diff_data_init_subsection(&state.left, &result->left,
439 0d27172a 2020-05-06 neels result->left.atoms.head,
440 0d27172a 2020-05-06 neels result->left.atoms.len);
441 0d27172a 2020-05-06 neels diff_data_init_subsection(&state.right, &result->right,
442 0d27172a 2020-05-06 neels result->right.atoms.head,
443 0d27172a 2020-05-06 neels result->right.atoms.len);
445 3b0f3d61 2020-01-22 neels result->rc = diff_run_algo(config->algo, &state);
447 3b0f3d61 2020-01-22 neels return result;
451 61a7b578 2020-05-06 neels diff_result_free(struct diff_result *result)
453 3b0f3d61 2020-01-22 neels if (!result)
455 3b0f3d61 2020-01-22 neels diff_data_free(&result->left);
456 3b0f3d61 2020-01-22 neels diff_data_free(&result->right);
457 3b0f3d61 2020-01-22 neels ARRAYLIST_FREE(result->chunks);
458 3b0f3d61 2020-01-22 neels free(result);