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 732e8ee0 2020-09-20 stsp #include <ctype.h>
21 e10a628a 2020-09-16 stsp #include <errno.h>
22 3b0f3d61 2020-01-22 neels #include <stdint.h>
23 3b0f3d61 2020-01-22 neels #include <stdlib.h>
24 3b0f3d61 2020-01-22 neels #include <stdbool.h>
25 3b0f3d61 2020-01-22 neels #include <stdio.h>
26 3b0f3d61 2020-01-22 neels #include <string.h>
27 3b0f3d61 2020-01-22 neels #include <limits.h>
28 c6eecea3 2020-07-26 stsp #include <unistd.h>
30 3b0f3d61 2020-01-22 neels #include <assert.h>
32 1dfba055 2020-10-07 stsp #include <arraylist.h>
33 1dfba055 2020-10-07 stsp #include <diff_main.h>
35 85ab4559 2020-09-22 stsp #include "diff_internal.h"
36 2a1b94d0 2020-09-26 stsp #include "diff_debug.h"
39 7a54ad3a 2020-09-20 stsp read_at(FILE *f, off_t at_pos, unsigned char *buf, size_t len)
42 7a54ad3a 2020-09-20 stsp if (fseeko(f, at_pos, SEEK_SET) == -1)
43 b3fb4686 2020-09-20 neels return errno;
44 7a54ad3a 2020-09-20 stsp r = fread(buf, sizeof(char), len, f);
45 7a54ad3a 2020-09-20 stsp if ((r == 0 || r < len) && ferror(f))
46 b3fb4686 2020-09-20 neels return errno;
47 b3fb4686 2020-09-20 neels if (r != len)
48 b3fb4686 2020-09-20 neels return EIO;
53 b3fb4686 2020-09-20 neels buf_cmp(const unsigned char *left, size_t left_len,
54 732e8ee0 2020-09-20 stsp const unsigned char *right, size_t right_len,
55 732e8ee0 2020-09-20 stsp bool ignore_whitespace)
59 732e8ee0 2020-09-20 stsp if (ignore_whitespace) {
60 732e8ee0 2020-09-20 stsp int il = 0, ir = 0;
61 732e8ee0 2020-09-20 stsp while (il < left_len && ir < right_len) {
62 732e8ee0 2020-09-20 stsp unsigned char cl = left[il];
63 732e8ee0 2020-09-20 stsp unsigned char cr = right[ir];
65 732e8ee0 2020-09-20 stsp if (isspace(cl) && il < left_len) {
69 732e8ee0 2020-09-20 stsp if (isspace(cr) && ir < right_len) {
74 732e8ee0 2020-09-20 stsp if (cl > cr)
76 732e8ee0 2020-09-20 stsp if (cr > cl)
81 732e8ee0 2020-09-20 stsp while (il < left_len) {
82 732e8ee0 2020-09-20 stsp unsigned char cl = left[il++];
83 732e8ee0 2020-09-20 stsp if (!isspace(cl))
86 732e8ee0 2020-09-20 stsp while (ir < right_len) {
87 732e8ee0 2020-09-20 stsp unsigned char cr = right[ir++];
88 732e8ee0 2020-09-20 stsp if (!isspace(cr))
95 732e8ee0 2020-09-20 stsp cmp = memcmp(left, right, MIN(left_len, right_len));
97 b3fb4686 2020-09-20 neels return cmp;
98 b3fb4686 2020-09-20 neels if (left_len == right_len)
100 b3fb4686 2020-09-20 neels return (left_len > right_len) ? 1 : -1;
104 b3fb4686 2020-09-20 neels diff_atom_cmp(int *cmp,
105 b3fb4686 2020-09-20 neels const struct diff_atom *left,
106 b3fb4686 2020-09-20 neels const struct diff_atom *right)
108 c6eecea3 2020-07-26 stsp off_t remain_left, remain_right;
109 ad5b3f85 2020-10-12 neels int flags = (left->root->diff_flags | right->root->diff_flags);
110 00d5652b 2020-09-22 stsp bool ignore_whitespace = (flags & DIFF_FLAG_IGNORE_WHITESPACE);
112 74ad6a69 2020-10-22 neels if (!left->len && !right->len) {
116 732e8ee0 2020-09-20 stsp if (!ignore_whitespace) {
117 732e8ee0 2020-09-20 stsp if (!right->len) {
121 732e8ee0 2020-09-20 stsp if (!left->len) {
127 b3fb4686 2020-09-20 neels if (left->at != NULL && right->at != NULL) {
128 732e8ee0 2020-09-20 stsp *cmp = buf_cmp(left->at, left->len, right->at, right->len,
129 732e8ee0 2020-09-20 stsp ignore_whitespace);
133 c6eecea3 2020-07-26 stsp remain_left = left->len;
134 c6eecea3 2020-07-26 stsp remain_right = right->len;
135 c6eecea3 2020-07-26 stsp while (remain_left > 0 || remain_right > 0) {
136 c6eecea3 2020-07-26 stsp const size_t chunksz = 8192;
137 c6eecea3 2020-07-26 stsp unsigned char buf_left[chunksz], buf_right[chunksz];
138 c6eecea3 2020-07-26 stsp const uint8_t *p_left, *p_right;
139 c6eecea3 2020-07-26 stsp off_t n_left, n_right;
142 b3fb4686 2020-09-20 neels if (!remain_right) {
146 b3fb4686 2020-09-20 neels if (!remain_left) {
147 b3fb4686 2020-09-20 neels *cmp = -1;
151 c6eecea3 2020-07-26 stsp n_left = MIN(chunksz, remain_left);
152 c6eecea3 2020-07-26 stsp n_right = MIN(chunksz, remain_right);
154 c6eecea3 2020-07-26 stsp if (left->at == NULL) {
155 ad5b3f85 2020-10-12 neels r = read_at(left->root->f,
156 b3fb4686 2020-09-20 neels left->pos + (left->len - remain_left),
157 b3fb4686 2020-09-20 neels buf_left, n_left);
162 c6eecea3 2020-07-26 stsp p_left = buf_left;
164 c6eecea3 2020-07-26 stsp p_left = left->at + (left->len - remain_left);
167 c6eecea3 2020-07-26 stsp if (right->at == NULL) {
168 ad5b3f85 2020-10-12 neels r = read_at(right->root->f,
169 b3fb4686 2020-09-20 neels right->pos + (right->len - remain_right),
170 b3fb4686 2020-09-20 neels buf_right, n_right);
175 c6eecea3 2020-07-26 stsp p_right = buf_right;
177 c6eecea3 2020-07-26 stsp p_right = right->at + (right->len - remain_right);
180 732e8ee0 2020-09-20 stsp r = buf_cmp(p_left, n_left, p_right, n_right,
181 732e8ee0 2020-09-20 stsp ignore_whitespace);
187 c6eecea3 2020-07-26 stsp remain_left -= n_left;
188 c6eecea3 2020-07-26 stsp remain_right -= n_right;
196 b3fb4686 2020-09-20 neels diff_atom_same(bool *same,
197 b3fb4686 2020-09-20 neels const struct diff_atom *left,
198 b3fb4686 2020-09-20 neels const struct diff_atom *right)
202 2fa08c64 2020-10-22 neels if (left->hash != right->hash) {
203 2fa08c64 2020-10-22 neels *same = false;
206 2fa08c64 2020-10-22 neels r = diff_atom_cmp(&cmp, left, right);
208 b3fb4686 2020-09-20 neels *same = true;
211 b3fb4686 2020-09-20 neels *same = (cmp == 0);
215 93f8150a 2020-10-11 neels static struct diff_chunk *
216 93f8150a 2020-10-11 neels diff_state_add_solved_chunk(struct diff_state *state,
217 93f8150a 2020-10-11 neels const struct diff_chunk *chunk)
219 93f8150a 2020-10-11 neels diff_chunk_arraylist_t *result;
220 8546b045 2020-09-20 neels struct diff_chunk *new_chunk;
221 8546b045 2020-09-20 neels enum diff_chunk_type last_t;
222 8546b045 2020-09-20 neels enum diff_chunk_type new_t;
224 8546b045 2020-09-20 neels /* Append to solved chunks; make sure that adjacent chunks of same type are combined, and that a minus chunk
225 8546b045 2020-09-20 neels * never directly follows a plus chunk. */
226 8546b045 2020-09-20 neels result = &state->result->chunks;
228 8546b045 2020-09-20 neels last_t = diff_chunk_type(&result->head[result->len - 1]);
229 93f8150a 2020-10-11 neels new_t = diff_chunk_type(chunk);
231 93f8150a 2020-10-11 neels debug("Add %s chunk:\n", chunk->solved ? "solved" : "UNSOLVED");
232 93f8150a 2020-10-11 neels debug("L\n");
233 93f8150a 2020-10-11 neels debug_dump_atoms(&state->left, chunk->left_start, chunk->left_count);
234 93f8150a 2020-10-11 neels debug("R\n");
235 93f8150a 2020-10-11 neels debug_dump_atoms(&state->right, chunk->right_start, chunk->right_count);
237 8546b045 2020-09-20 neels if (new_t == last_t) {
238 8546b045 2020-09-20 neels new_chunk = &result->head[result->len - 1];
239 93f8150a 2020-10-11 neels new_chunk->left_count += chunk->left_count;
240 93f8150a 2020-10-11 neels new_chunk->right_count += chunk->right_count;
241 bb867e68 2020-10-11 neels debug(" - added chunk touches previous one of same type, joined:\n");
242 bb867e68 2020-10-11 neels debug("L\n");
243 bb867e68 2020-10-11 neels debug_dump_atoms(&state->left, new_chunk->left_start, new_chunk->left_count);
244 bb867e68 2020-10-11 neels debug("R\n");
245 bb867e68 2020-10-11 neels debug_dump_atoms(&state->right, new_chunk->right_start, new_chunk->right_count);
246 8546b045 2020-09-20 neels } else if (last_t == CHUNK_PLUS && new_t == CHUNK_MINUS) {
247 93f8150a 2020-10-11 neels enum diff_chunk_type prev_last_t =
248 93f8150a 2020-10-11 neels result->len > 1 ?
249 93f8150a 2020-10-11 neels diff_chunk_type(&result->head[result->len - 2])
250 93f8150a 2020-10-11 neels : CHUNK_EMPTY;
251 93f8150a 2020-10-11 neels /* If a minus-chunk follows a plus-chunk, place it above the plus-chunk->
252 8546b045 2020-09-20 neels * Is the one before that also a minus? combine. */
253 8546b045 2020-09-20 neels if (prev_last_t == CHUNK_MINUS) {
254 8546b045 2020-09-20 neels new_chunk = &result->head[result->len - 2];
255 93f8150a 2020-10-11 neels new_chunk->left_count += chunk->left_count;
256 93f8150a 2020-10-11 neels new_chunk->right_count += chunk->right_count;
258 bb867e68 2020-10-11 neels debug(" - added minus-chunk follows plus-chunk,"
259 bb867e68 2020-10-11 neels " put before that plus-chunk and joined"
260 bb867e68 2020-10-11 neels " with preceding minus-chunk:\n");
261 bb867e68 2020-10-11 neels debug("L\n");
262 bb867e68 2020-10-11 neels debug_dump_atoms(&state->left, new_chunk->left_start, new_chunk->left_count);
263 bb867e68 2020-10-11 neels debug("R\n");
264 bb867e68 2020-10-11 neels debug_dump_atoms(&state->right, new_chunk->right_start, new_chunk->right_count);
266 724967e9 2020-10-11 neels ARRAYLIST_INSERT(new_chunk, *result, result->len - 1);
267 8546b045 2020-09-20 neels if (!new_chunk)
268 8546b045 2020-09-20 neels return NULL;
269 93f8150a 2020-10-11 neels *new_chunk = *chunk;
271 bb867e68 2020-10-11 neels debug(" - added minus-chunk follows plus-chunk,"
272 bb867e68 2020-10-11 neels " put before that plus-chunk\n");
275 8546b045 2020-09-20 neels ARRAYLIST_ADD(new_chunk, *result);
276 8546b045 2020-09-20 neels if (!new_chunk)
277 8546b045 2020-09-20 neels return NULL;
278 93f8150a 2020-10-11 neels *new_chunk = *chunk;
280 93f8150a 2020-10-11 neels return new_chunk;
283 93f8150a 2020-10-11 neels /* Even if a left or right side is empty, diff output may need to know the
284 93f8150a 2020-10-11 neels * position in that file.
285 93f8150a 2020-10-11 neels * So left_start or right_start must never be NULL -- pass left_count or
286 93f8150a 2020-10-11 neels * right_count as zero to indicate staying at that position without consuming
287 93f8150a 2020-10-11 neels * any lines. */
288 93f8150a 2020-10-11 neels struct diff_chunk *
289 93f8150a 2020-10-11 neels diff_state_add_chunk(struct diff_state *state, bool solved,
290 93f8150a 2020-10-11 neels struct diff_atom *left_start, unsigned int left_count,
291 93f8150a 2020-10-11 neels struct diff_atom *right_start, unsigned int right_count)
293 93f8150a 2020-10-11 neels diff_chunk_arraylist_t *result = NULL;
294 93f8150a 2020-10-11 neels struct diff_chunk *new_chunk;
295 93f8150a 2020-10-11 neels struct diff_chunk chunk = {
296 93f8150a 2020-10-11 neels .solved = solved,
297 93f8150a 2020-10-11 neels .left_start = left_start,
298 93f8150a 2020-10-11 neels .left_count = left_count,
299 93f8150a 2020-10-11 neels .right_start = right_start,
300 93f8150a 2020-10-11 neels .right_count = right_count,
303 93f8150a 2020-10-11 neels if (!solved || state->temp_result.len) {
304 93f8150a 2020-10-11 neels /* Append to temp_result */
305 93f8150a 2020-10-11 neels debug("append to temp_result\n");
306 93f8150a 2020-10-11 neels result = &state->temp_result;
307 93f8150a 2020-10-11 neels } else if (!state->result->chunks.len) {
308 93f8150a 2020-10-11 neels /* Append to final result */
309 93f8150a 2020-10-11 neels result = &state->result->chunks;
310 acfce337 2020-10-12 neels debug("Add first chunk:\n");
311 acfce337 2020-10-12 neels debug("L\n");
312 acfce337 2020-10-12 neels debug_dump_atoms(&state->left, left_start, left_count);
313 acfce337 2020-10-12 neels debug("R\n");
314 acfce337 2020-10-12 neels debug_dump_atoms(&state->right, right_start, right_count);
316 93f8150a 2020-10-11 neels if (result) {
317 93f8150a 2020-10-11 neels ARRAYLIST_ADD(new_chunk, *result);
318 93f8150a 2020-10-11 neels if (!new_chunk)
319 93f8150a 2020-10-11 neels return NULL;
320 8546b045 2020-09-20 neels *new_chunk = chunk;
321 93f8150a 2020-10-11 neels return new_chunk;
324 93f8150a 2020-10-11 neels return diff_state_add_solved_chunk(state, &chunk);
328 7a54ad3a 2020-09-20 stsp diff_data_init_root(struct diff_data *d, FILE *f, const uint8_t *data,
329 00d5652b 2020-09-22 stsp unsigned long long len, int diff_flags)
331 3b0f3d61 2020-01-22 neels *d = (struct diff_data){
334 3b0f3d61 2020-01-22 neels .data = data,
335 3b0f3d61 2020-01-22 neels .len = len,
336 3b0f3d61 2020-01-22 neels .root = d,
337 00d5652b 2020-09-22 stsp .diff_flags = diff_flags,
342 61a7b578 2020-05-06 neels diff_data_init_subsection(struct diff_data *d, struct diff_data *parent,
343 61a7b578 2020-05-06 neels struct diff_atom *from_atom, unsigned int atoms_count)
345 05b5f01f 2020-09-21 stsp struct diff_atom *last_atom;
347 05b5f01f 2020-09-21 stsp if (atoms_count == 0) {
348 05b5f01f 2020-09-21 stsp *d = (struct diff_data){
351 34570dbe 2020-10-16 stsp .data = NULL,
353 05b5f01f 2020-09-21 stsp .root = parent->root,
354 05b5f01f 2020-09-21 stsp .atoms.head = NULL,
355 05b5f01f 2020-09-21 stsp .atoms.len = atoms_count,
361 05b5f01f 2020-09-21 stsp last_atom = from_atom + atoms_count - 1;
362 3b0f3d61 2020-01-22 neels *d = (struct diff_data){
364 c6eecea3 2020-07-26 stsp .pos = from_atom->pos,
365 3b0f3d61 2020-01-22 neels .data = from_atom->at,
366 c6eecea3 2020-07-26 stsp .len = (last_atom->pos + last_atom->len) - from_atom->pos,
367 3b0f3d61 2020-01-22 neels .root = parent->root,
368 3b0f3d61 2020-01-22 neels .atoms.head = from_atom,
369 3b0f3d61 2020-01-22 neels .atoms.len = atoms_count,
372 3b0f3d61 2020-01-22 neels debug("subsection:\n");
373 3b0f3d61 2020-01-22 neels debug_dump(d);
377 61a7b578 2020-05-06 neels diff_data_free(struct diff_data *diff_data)
379 3b0f3d61 2020-01-22 neels if (!diff_data)
381 3b0f3d61 2020-01-22 neels if (diff_data->atoms.allocated)
382 3b0f3d61 2020-01-22 neels ARRAYLIST_FREE(diff_data->atoms);
386 0d27172a 2020-05-06 neels diff_algo_none(const struct diff_algo_config *algo_config,
387 0d27172a 2020-05-06 neels struct diff_state *state)
389 3b0f3d61 2020-01-22 neels debug("\n** %s\n", __func__);
390 3b0f3d61 2020-01-22 neels debug("left:\n");
391 3b0f3d61 2020-01-22 neels debug_dump(&state->left);
392 3b0f3d61 2020-01-22 neels debug("right:\n");
393 3b0f3d61 2020-01-22 neels debug_dump(&state->right);
394 0d27172a 2020-05-06 neels debug_dump_myers_graph(&state->left, &state->right, NULL, NULL, 0, NULL,
397 3b0f3d61 2020-01-22 neels /* Add a chunk of equal lines, if any */
398 467a993d 2020-10-11 neels struct diff_atom *l = state->left.atoms.head;
399 467a993d 2020-10-11 neels unsigned int l_len = state->left.atoms.len;
400 467a993d 2020-10-11 neels struct diff_atom *r = state->right.atoms.head;
401 467a993d 2020-10-11 neels unsigned int r_len = state->right.atoms.len;
402 41ff30f3 2020-10-11 neels unsigned int equal_atoms_start = 0;
403 2146cf12 2020-10-11 neels unsigned int equal_atoms_end = 0;
404 13497fff 2020-10-11 neels unsigned int l_idx = 0;
405 13497fff 2020-10-11 neels unsigned int r_idx = 0;
407 41ff30f3 2020-10-11 neels while (equal_atoms_start < l_len
408 41ff30f3 2020-10-11 neels && equal_atoms_start < r_len) {
410 b3fb4686 2020-09-20 neels bool same;
411 41ff30f3 2020-10-11 neels err = diff_atom_same(&same, &l[equal_atoms_start],
412 e5447b81 2020-10-12 neels &r[equal_atoms_start]);
414 467a993d 2020-10-11 neels return err;
415 b3fb4686 2020-09-20 neels if (!same)
417 41ff30f3 2020-10-11 neels equal_atoms_start++;
419 2146cf12 2020-10-11 neels while (equal_atoms_end < (l_len - equal_atoms_start)
420 2146cf12 2020-10-11 neels && equal_atoms_end < (r_len - equal_atoms_start)) {
422 2146cf12 2020-10-11 neels bool same;
423 2146cf12 2020-10-11 neels err = diff_atom_same(&same, &l[l_len - 1 - equal_atoms_end],
424 2146cf12 2020-10-11 neels &r[r_len - 1 - equal_atoms_end]);
426 2146cf12 2020-10-11 neels return err;
427 2146cf12 2020-10-11 neels if (!same)
429 2146cf12 2020-10-11 neels equal_atoms_end++;
432 2146cf12 2020-10-11 neels /* Add a chunk of equal lines at the start */
433 41ff30f3 2020-10-11 neels if (equal_atoms_start) {
434 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
435 e5447b81 2020-10-12 neels l, equal_atoms_start,
436 e5447b81 2020-10-12 neels r, equal_atoms_start))
437 3e6cba3a 2020-08-13 stsp return ENOMEM;
438 13497fff 2020-10-11 neels l_idx += equal_atoms_start;
439 13497fff 2020-10-11 neels r_idx += equal_atoms_start;
442 3b0f3d61 2020-01-22 neels /* Add a "minus" chunk with all lines from the left. */
443 2146cf12 2020-10-11 neels if (equal_atoms_start + equal_atoms_end < l_len) {
444 13497fff 2020-10-11 neels unsigned int add_len = l_len - equal_atoms_start - equal_atoms_end;
445 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
446 13497fff 2020-10-11 neels &l[l_idx], add_len,
447 13497fff 2020-10-11 neels &r[r_idx], 0))
448 13497fff 2020-10-11 neels return ENOMEM;
449 13497fff 2020-10-11 neels l_idx += add_len;
452 3b0f3d61 2020-01-22 neels /* Add a "plus" chunk with all lines from the right. */
453 2146cf12 2020-10-11 neels if (equal_atoms_start + equal_atoms_end < r_len) {
454 13497fff 2020-10-11 neels unsigned int add_len = r_len - equal_atoms_start - equal_atoms_end;
455 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
456 9dc0554f 2020-10-12 neels &l[l_idx], 0,
457 9dc0554f 2020-10-12 neels &r[r_idx], add_len))
458 13497fff 2020-10-11 neels return ENOMEM;
459 13497fff 2020-10-11 neels r_idx += add_len;
462 2146cf12 2020-10-11 neels /* Add a chunk of equal lines at the end */
463 2146cf12 2020-10-11 neels if (equal_atoms_end) {
464 2146cf12 2020-10-11 neels if (!diff_state_add_chunk(state, true,
465 13497fff 2020-10-11 neels &l[l_idx], equal_atoms_end,
466 13497fff 2020-10-11 neels &r[r_idx], equal_atoms_end))
467 2146cf12 2020-10-11 neels return ENOMEM;
470 3b0f3d61 2020-01-22 neels return DIFF_RC_OK;
474 0d27172a 2020-05-06 neels diff_run_algo(const struct diff_algo_config *algo_config,
475 0d27172a 2020-05-06 neels struct diff_state *state)
479 0d27172a 2020-05-06 neels if (!algo_config || !algo_config->impl
480 746d94df 2020-10-12 neels || !state->recursion_depth_left
481 746d94df 2020-10-12 neels || !state->left.atoms.len || !state->right.atoms.len) {
482 746d94df 2020-10-12 neels debug("Fall back to diff_algo_none():%s%s%s\n",
483 746d94df 2020-10-12 neels (!algo_config || !algo_config->impl) ? " no-cfg" : "",
484 746d94df 2020-10-12 neels (!state->recursion_depth_left) ? " max-depth" : "",
485 746d94df 2020-10-12 neels (!state->left.atoms.len || !state->right.atoms.len)?
486 746d94df 2020-10-12 neels " trivial" : "");
487 3b0f3d61 2020-01-22 neels return diff_algo_none(algo_config, state);
490 746d94df 2020-10-12 neels ARRAYLIST_FREE(state->temp_result);
491 3b0f3d61 2020-01-22 neels ARRAYLIST_INIT(state->temp_result, DIFF_RESULT_ALLOC_BLOCKSIZE);
492 3b0f3d61 2020-01-22 neels rc = algo_config->impl(algo_config, state);
493 3b0f3d61 2020-01-22 neels switch (rc) {
494 3b0f3d61 2020-01-22 neels case DIFF_RC_USE_DIFF_ALGO_FALLBACK:
495 0d27172a 2020-05-06 neels debug("Got DIFF_RC_USE_DIFF_ALGO_FALLBACK (%p)\n",
496 0d27172a 2020-05-06 neels algo_config->fallback_algo);
497 3b0f3d61 2020-01-22 neels rc = diff_run_algo(algo_config->fallback_algo, state);
498 3b0f3d61 2020-01-22 neels goto return_rc;
500 3b0f3d61 2020-01-22 neels case DIFF_RC_OK:
501 3b0f3d61 2020-01-22 neels /* continue below */
505 3b0f3d61 2020-01-22 neels /* some error happened */
506 3b0f3d61 2020-01-22 neels goto return_rc;
509 0d27172a 2020-05-06 neels /* Pick up any diff chunks that are still unsolved and feed to
510 0d27172a 2020-05-06 neels * inner_algo. inner_algo will solve unsolved chunks and append to
511 0d27172a 2020-05-06 neels * result, and subsequent solved chunks on this level are then appended
512 0d27172a 2020-05-06 neels * to result afterwards. */
514 3b0f3d61 2020-01-22 neels for (i = 0; i < state->temp_result.len; i++) {
515 3b0f3d61 2020-01-22 neels struct diff_chunk *c = &state->temp_result.head[i];
516 3b0f3d61 2020-01-22 neels if (c->solved) {
517 93f8150a 2020-10-11 neels diff_state_add_solved_chunk(state, c);
521 3b0f3d61 2020-01-22 neels /* c is an unsolved chunk, feed to inner_algo */
522 3b0f3d61 2020-01-22 neels struct diff_state inner_state = {
523 3b0f3d61 2020-01-22 neels .result = state->result,
524 3b0f3d61 2020-01-22 neels .recursion_depth_left = state->recursion_depth_left - 1,
525 8be88dfa 2020-10-21 stsp .kd_buf = state->kd_buf,
526 8be88dfa 2020-10-21 stsp .kd_buf_size = state->kd_buf_size,
528 0d27172a 2020-05-06 neels diff_data_init_subsection(&inner_state.left, &state->left,
529 0d27172a 2020-05-06 neels c->left_start, c->left_count);
530 0d27172a 2020-05-06 neels diff_data_init_subsection(&inner_state.right, &state->right,
531 0d27172a 2020-05-06 neels c->right_start, c->right_count);
533 3b0f3d61 2020-01-22 neels rc = diff_run_algo(algo_config->inner_algo, &inner_state);
534 8be88dfa 2020-10-21 stsp state->kd_buf = inner_state.kd_buf;
535 8be88dfa 2020-10-21 stsp state->kd_buf_size = inner_state.kd_buf_size;
536 3b0f3d61 2020-01-22 neels if (rc != DIFF_RC_OK)
537 3b0f3d61 2020-01-22 neels goto return_rc;
540 3b0f3d61 2020-01-22 neels rc = DIFF_RC_OK;
541 3b0f3d61 2020-01-22 neels return_rc:
542 3b0f3d61 2020-01-22 neels ARRAYLIST_FREE(state->temp_result);
543 3b0f3d61 2020-01-22 neels return rc;
547 c16dde50 2020-10-22 stsp diff_atomize_file(struct diff_data *d,
548 c16dde50 2020-10-22 stsp const struct diff_config *config,
549 c16dde50 2020-10-22 stsp FILE *f, const uint8_t *data, off_t len, int diff_flags)
551 c16dde50 2020-10-22 stsp if (!config->atomize_func)
552 c16dde50 2020-10-22 stsp return EINVAL;
554 c16dde50 2020-10-22 stsp diff_data_init_root(d, f, data, len, diff_flags);
556 c16dde50 2020-10-22 stsp return config->atomize_func(config->atomize_func_data, d);
560 61a7b578 2020-05-06 neels struct diff_result *
561 c16dde50 2020-10-22 stsp diff_main(const struct diff_config *config, struct diff_data *left,
562 c16dde50 2020-10-22 stsp struct diff_data *right)
564 3b0f3d61 2020-01-22 neels struct diff_result *result = malloc(sizeof(struct diff_result));
565 3b0f3d61 2020-01-22 neels if (!result)
566 3b0f3d61 2020-01-22 neels return NULL;
568 3b0f3d61 2020-01-22 neels *result = (struct diff_result){};
569 c16dde50 2020-10-22 stsp result->left = left;
570 c16dde50 2020-10-22 stsp result->right = right;
572 3b0f3d61 2020-01-22 neels struct diff_state state = {
573 3b0f3d61 2020-01-22 neels .result = result,
574 00961134 2020-09-20 stsp .recursion_depth_left = config->max_recursion_depth ? : 32,
575 8be88dfa 2020-10-21 stsp .kd_buf = NULL,
576 8be88dfa 2020-10-21 stsp .kd_buf_size = 0,
578 c16dde50 2020-10-22 stsp diff_data_init_subsection(&state.left, left,
579 c16dde50 2020-10-22 stsp left->atoms.head,
580 c16dde50 2020-10-22 stsp left->atoms.len);
581 c16dde50 2020-10-22 stsp diff_data_init_subsection(&state.right, right,
582 c16dde50 2020-10-22 stsp right->atoms.head,
583 c16dde50 2020-10-22 stsp right->atoms.len);
585 3b0f3d61 2020-01-22 neels result->rc = diff_run_algo(config->algo, &state);
586 8be88dfa 2020-10-21 stsp free(state.kd_buf);
588 3b0f3d61 2020-01-22 neels return result;
592 61a7b578 2020-05-06 neels diff_result_free(struct diff_result *result)
594 3b0f3d61 2020-01-22 neels if (!result)
596 3b0f3d61 2020-01-22 neels ARRAYLIST_FREE(result->chunks);
597 3b0f3d61 2020-01-22 neels free(result);