1 /* Generic infrastructure to implement various diff algorithms (implementation). */
2 /*
3  * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
4  *
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.
8  *
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.
16  */
17 
18 
19 #include <ctype.h>
20 #include <errno.h>
21 #include <stdint.h>
22 #include <stdlib.h>
23 #include <stdbool.h>
24 #include <stdio.h>
25 #include <string.h>
26 #include <limits.h>
27 #include <unistd.h>
28 
29 #include <assert.h>
30 
31 #include <arraylist.h>
32 #include <diff_main.h>
33 
34 #include "got_compat.h"
35 
36 #include "diff_internal.h"
37 #include "diff_debug.h"
38 
39 static int
40 read_at(FILE *f, off_t at_pos, unsigned char *buf, size_t len)
41 {
42 	int r;
43 	if (fseeko(f, at_pos, SEEK_SET) == -1)
44 		return errno;
45 	r = fread(buf, sizeof(char), len, f);
46 	if ((r == 0 || r < len) && ferror(f))
47 		return errno;
48 	if (r != len)
49 		return EIO;
50 	return 0;
51 }
52 
53 static int
54 buf_cmp(const unsigned char *left, size_t left_len,
55 	const unsigned char *right, size_t right_len,
56 	bool ignore_whitespace)
57 {
58 	int cmp;
59 
60 	if (ignore_whitespace) {
61 		int il = 0, ir = 0;
62 		while (il < left_len && ir < right_len) {
63 			unsigned char cl = left[il];
64 			unsigned char cr = right[ir];
65 
66 			if (isspace(cl) && il < left_len) {
67 				il++;
68 				continue;
69 			}
70 			if (isspace(cr) && ir < right_len) {
71 				ir++;
72 				continue;
73 			}
74 
75 			if (cl > cr)
76 				return 1;
77 			if (cr > cl)
78 				return -1;
79 			il++;
80 			ir++;
81 		}
82 		while (il < left_len) {
83 			unsigned char cl = left[il++];
84 			if (!isspace(cl))
85 				return 1;
86 		}
87 		while (ir < right_len) {
88 			unsigned char cr = right[ir++];
89 			if (!isspace(cr))
90 				return -1;
91 		}
92 
93 		return 0;
94 	}
95 
96 	cmp = memcmp(left, right, MIN(left_len, right_len));
97 	if (cmp)
98 		return cmp;
99 	if (left_len == right_len)
100 		return 0;
101 	return (left_len > right_len) ? 1 : -1;
102 }
103 
104 int
105 diff_atom_cmp(int *cmp,
106 	      const struct diff_atom *left,
107 	      const struct diff_atom *right)
108 {
109 	off_t remain_left, remain_right;
110 	int flags = (left->root->diff_flags | right->root->diff_flags);
111 	bool ignore_whitespace = (flags & DIFF_FLAG_IGNORE_WHITESPACE);
112 
113 	if (!left->len && !right->len) {
114 		*cmp = 0;
115 		return 0;
116 	}
117 	if (!ignore_whitespace) {
118 		if (!right->len) {
119 			*cmp = 1;
120 			return 0;
121 		}
122 		if (!left->len) {
123 			*cmp = -1;
124 			return 0;
125 		}
126 	}
127 
128 	if (left->at != NULL && right->at != NULL) {
129 		*cmp = buf_cmp(left->at, left->len, right->at, right->len,
130 		    ignore_whitespace);
131 		return 0;
132 	}
133 
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;
141 		ssize_t r;
142 
143 		if (!remain_right) {
144 			*cmp = 1;
145 			return 0;
146 		}
147 		if (!remain_left) {
148 			*cmp = -1;
149 			return 0;
150 		}
151 
152 		n_left = MIN(chunksz, remain_left);
153 		n_right = MIN(chunksz, remain_right);
154 
155 		if (left->at == NULL) {
156 			r = read_at(left->root->f,
157 				    left->pos + (left->len - remain_left),
158 				    buf_left, n_left);
159 			if (r) {
160 				*cmp = 0;
161 				return r;
162 			}
163 			p_left = buf_left;
164 		} else {
165 			p_left = left->at + (left->len - remain_left);
166 		}
167 
168 		if (right->at == NULL) {
169 			r = read_at(right->root->f,
170 				    right->pos + (right->len - remain_right),
171 				    buf_right, n_right);
172 			if (r) {
173 				*cmp = 0;
174 				return r;
175 			}
176 			p_right = buf_right;
177 		} else {
178 			p_right = right->at + (right->len - remain_right);
179 		}
180 
181 		r = buf_cmp(p_left, n_left, p_right, n_right,
182 		    ignore_whitespace);
183 		if (r) {
184 			*cmp = r;
185 			return 0;
186 		}
187 
188 		remain_left -= n_left;
189 		remain_right -= n_right;
190 	}
191 
192 	*cmp = 0;
193 	return 0;
194 }
195 
196 int
197 diff_atom_same(bool *same,
198 	       const struct diff_atom *left,
199 	       const struct diff_atom *right)
200 {
201 	int cmp;
202 	int r;
203 	if (left->hash != right->hash) {
204 		*same = false;
205 		return 0;
206 	}
207 	r = diff_atom_cmp(&cmp, left, right);
208 	if (r) {
209 		*same = true;
210 		return r;
211 	}
212 	*same = (cmp == 0);
213 	return 0;
214 }
215 
216 static struct diff_chunk *
217 diff_state_add_solved_chunk(struct diff_state *state,
218 			    const struct diff_chunk *chunk)
219 {
220 	diff_chunk_arraylist_t *result;
221 	struct diff_chunk *new_chunk;
222 	enum diff_chunk_type last_t;
223 	enum diff_chunk_type new_t;
224 	struct diff_chunk *last;
225 
226 	/* Append to solved chunks; make sure that adjacent chunks of same type are combined, and that a minus chunk
227 	 * never directly follows a plus chunk. */
228 	result = &state->result->chunks;
229 
230 	last_t = result->len ? diff_chunk_type(&result->head[result->len - 1])
231 		: CHUNK_EMPTY;
232 	new_t = diff_chunk_type(chunk);
233 
234 	debug("ADD %s chunk #%u:\n", chunk->solved ? "solved" : "UNSOLVED",
235 	      result->len);
236 	debug("L\n");
237 	debug_dump_atoms(&state->left, chunk->left_start, chunk->left_count);
238 	debug("R\n");
239 	debug_dump_atoms(&state->right, chunk->right_start, chunk->right_count);
240 
241 	if (result->len) {
242 		last = &result->head[result->len - 1];
243 		assert(chunk->left_start
244 		       == last->left_start + last->left_count);
245 		assert(chunk->right_start
246 		       == last->right_start + last->right_count);
247 	}
248 
249 	if (new_t == last_t) {
250 		new_chunk = &result->head[result->len - 1];
251 		new_chunk->left_count += chunk->left_count;
252 		new_chunk->right_count += chunk->right_count;
253 		debug("  - added chunk touches previous one of same type, joined:\n");
254 		debug("L\n");
255 		debug_dump_atoms(&state->left, new_chunk->left_start, new_chunk->left_count);
256 		debug("R\n");
257 		debug_dump_atoms(&state->right, new_chunk->right_start, new_chunk->right_count);
258 	} else if (last_t == CHUNK_PLUS && new_t == CHUNK_MINUS) {
259 		enum diff_chunk_type prev_last_t =
260 			result->len > 1 ?
261 				diff_chunk_type(&result->head[result->len - 2])
262 				: CHUNK_EMPTY;
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;
269 
270 			debug("  - added minus-chunk follows plus-chunk,"
271 			      " put before that plus-chunk and joined"
272 			      " with preceding minus-chunk:\n");
273 			debug("L\n");
274 			debug_dump_atoms(&state->left, new_chunk->left_start, new_chunk->left_count);
275 			debug("R\n");
276 			debug_dump_atoms(&state->right, new_chunk->right_start, new_chunk->right_count);
277 		} else {
278 			ARRAYLIST_INSERT(new_chunk, *result, result->len - 1);
279 			if (!new_chunk)
280 				return NULL;
281 			*new_chunk = *chunk;
282 
283 			/* The new minus chunk indicates to which position on
284 			 * the right it corresponds, even though it doesn't add
285 			 * any lines on the right. By moving above a plus chunk,
286 			 * that position on the right has shifted. */
287 			last = &result->head[result->len - 1];
288 			new_chunk->right_start = last->right_start;
289 
290 			debug("  - added minus-chunk follows plus-chunk,"
291 			      " put before that plus-chunk\n");
292 		}
293 
294 		/* That last_t == CHUNK_PLUS indicates to which position on the
295 		 * left it corresponds, even though it doesn't add any lines on
296 		 * the left. By inserting/extending the prev_last_t ==
297 		 * CHUNK_MINUS, that position on the left has shifted. */
298 		last = &result->head[result->len - 1];
299 		last->left_start = new_chunk->left_start
300 			+ new_chunk->left_count;
301 
302 	} else {
303 		ARRAYLIST_ADD(new_chunk, *result);
304 		if (!new_chunk)
305 			return NULL;
306 		*new_chunk = *chunk;
307 	}
308 	return new_chunk;
309 }
310 
311 /* Even if a left or right side is empty, diff output may need to know the
312  * position in that file.
313  * So left_start or right_start must never be NULL -- pass left_count or
314  * right_count as zero to indicate staying at that position without consuming
315  * any lines. */
316 struct diff_chunk *
317 diff_state_add_chunk(struct diff_state *state, bool solved,
318 		     struct diff_atom *left_start, unsigned int left_count,
319 		     struct diff_atom *right_start, unsigned int right_count)
320 {
321 	struct diff_chunk *new_chunk;
322 	struct diff_chunk chunk = {
323 		.solved = solved,
324 		.left_start = left_start,
325 		.left_count = left_count,
326 		.right_start = right_start,
327 		.right_count = right_count,
328 	};
329 
330 	/* An unsolved chunk means store as intermediate result for later
331 	 * re-iteration.
332 	 * If there already are intermediate results, that means even a
333 	 * following solved chunk needs to go to intermediate results, so that
334 	 * it is later put in the final correct position in solved chunks.
335 	 */
336 	if (!solved || state->temp_result.len) {
337 		/* Append to temp_result */
338 		debug("ADD %s chunk to temp result:\n",
339 		      chunk.solved ? "solved" : "UNSOLVED");
340 		debug("L\n");
341 		debug_dump_atoms(&state->left, left_start, left_count);
342 		debug("R\n");
343 		debug_dump_atoms(&state->right, right_start, right_count);
344 		ARRAYLIST_ADD(new_chunk, state->temp_result);
345 		if (!new_chunk)
346 			return NULL;
347 		*new_chunk = chunk;
348 		return new_chunk;
349 	}
350 
351 	return diff_state_add_solved_chunk(state, &chunk);
352 }
353 
354 void
355 diff_data_init_root(struct diff_data *d, FILE *f, const uint8_t *data,
356     unsigned long long len, int diff_flags)
357 {
358 	*d = (struct diff_data){
359 		.f = f,
360 		.pos = 0,
361 		.data = data,
362 		.len = len,
363 		.root = d,
364 		.diff_flags = diff_flags,
365 	};
366 }
367 
368 void
369 diff_data_init_subsection(struct diff_data *d, struct diff_data *parent,
370 			  struct diff_atom *from_atom, unsigned int atoms_count)
371 {
372 	struct diff_atom *last_atom;
373 
374 	debug("diff_data %p  parent %p  from_atom %p  atoms_count %u\n",
375 	      d, parent, from_atom, atoms_count);
376 	debug("  from_atom ");
377 	debug_dump_atom(parent, NULL, from_atom);
378 
379 	if (atoms_count == 0) {
380 		*d = (struct diff_data){
381 			.f = NULL,
382 			.pos = 0,
383 			.data = NULL,
384 			.len = 0,
385 			.root = parent->root,
386 			.atoms.head = NULL,
387 			.atoms.len = atoms_count,
388 		};
389 
390 		return;
391 	}
392 
393 	last_atom = from_atom + atoms_count - 1;
394 	*d = (struct diff_data){
395 		.f = NULL,
396 		.pos = from_atom->pos,
397 		.data = from_atom->at,
398 		.len = (last_atom->pos + last_atom->len) - from_atom->pos,
399 		.root = parent->root,
400 		.atoms.head = from_atom,
401 		.atoms.len = atoms_count,
402 	};
403 
404 	debug("subsection:\n");
405 	debug_dump(d);
406 }
407 
408 void
409 diff_data_free(struct diff_data *diff_data)
410 {
411 	if (!diff_data)
412 		return;
413 	if (diff_data->atoms.allocated)
414 		ARRAYLIST_FREE(diff_data->atoms);
415 }
416 
417 int
418 diff_algo_none(const struct diff_algo_config *algo_config,
419 	       struct diff_state *state)
420 {
421 	debug("\n** %s\n", __func__);
422 	debug("left:\n");
423 	debug_dump(&state->left);
424 	debug("right:\n");
425 	debug_dump(&state->right);
426 	debug_dump_myers_graph(&state->left, &state->right, NULL, NULL, 0, NULL,
427 			       0);
428 
429 	/* Add a chunk of equal lines, if any */
430 	struct diff_atom *l = state->left.atoms.head;
431 	unsigned int l_len = state->left.atoms.len;
432 	struct diff_atom *r = state->right.atoms.head;
433 	unsigned int r_len = state->right.atoms.len;
434 	unsigned int equal_atoms_start = 0;
435 	unsigned int equal_atoms_end = 0;
436 	unsigned int l_idx = 0;
437 	unsigned int r_idx = 0;
438 
439 	while (equal_atoms_start < l_len
440 	       && equal_atoms_start < r_len) {
441 		int err;
442 		bool same;
443 		err = diff_atom_same(&same, &l[equal_atoms_start],
444 				     &r[equal_atoms_start]);
445 		if (err)
446 			return err;
447 		if (!same)
448 			break;
449 		equal_atoms_start++;
450 	}
451 	while (equal_atoms_end < (l_len - equal_atoms_start)
452 	       && equal_atoms_end < (r_len - equal_atoms_start)) {
453 		int err;
454 		bool same;
455 		err = diff_atom_same(&same, &l[l_len - 1 - equal_atoms_end],
456 				   &r[r_len - 1 - equal_atoms_end]);
457 		if (err)
458 			return err;
459 		if (!same)
460 			break;
461 		equal_atoms_end++;
462 	}
463 
464 	/* Add a chunk of equal lines at the start */
465 	if (equal_atoms_start) {
466 		if (!diff_state_add_chunk(state, true,
467 					  l, equal_atoms_start,
468 					  r, equal_atoms_start))
469 			return ENOMEM;
470 		l_idx += equal_atoms_start;
471 		r_idx += equal_atoms_start;
472 	}
473 
474 	/* Add a "minus" chunk with all lines from the left. */
475 	if (equal_atoms_start + equal_atoms_end < l_len) {
476 		unsigned int add_len = l_len - equal_atoms_start - equal_atoms_end;
477 		if (!diff_state_add_chunk(state, true,
478 					  &l[l_idx], add_len,
479 					  &r[r_idx], 0))
480 			return ENOMEM;
481 		l_idx += add_len;
482 	}
483 
484 	/* Add a "plus" chunk with all lines from the right. */
485 	if (equal_atoms_start + equal_atoms_end < r_len) {
486 		unsigned int add_len = r_len - equal_atoms_start - equal_atoms_end;
487 		if (!diff_state_add_chunk(state, true,
488 					  &l[l_idx], 0,
489 					  &r[r_idx], add_len))
490 			return ENOMEM;
491 		r_idx += add_len;
492 	}
493 
494 	/* Add a chunk of equal lines at the end */
495 	if (equal_atoms_end) {
496 		if (!diff_state_add_chunk(state, true,
497 					  &l[l_idx], equal_atoms_end,
498 					  &r[r_idx], equal_atoms_end))
499 			return ENOMEM;
500 	}
501 
502 	return DIFF_RC_OK;
503 }
504 
505 int
506 diff_run_algo(const struct diff_algo_config *algo_config,
507 	      struct diff_state *state)
508 {
509 	int rc;
510 
511 	if (!algo_config || !algo_config->impl
512 	    || !state->recursion_depth_left
513 	    || !state->left.atoms.len || !state->right.atoms.len) {
514 		debug("Fall back to diff_algo_none():%s%s%s\n",
515 		      (!algo_config || !algo_config->impl) ? " no-cfg" : "",
516 		      (!state->recursion_depth_left) ? " max-depth" : "",
517 		      (!state->left.atoms.len || !state->right.atoms.len)?
518 			      " trivial" : "");
519 		return diff_algo_none(algo_config, state);
520 	}
521 
522 	ARRAYLIST_FREE(state->temp_result);
523 	ARRAYLIST_INIT(state->temp_result, DIFF_RESULT_ALLOC_BLOCKSIZE);
524 	rc = algo_config->impl(algo_config, state);
525 	switch (rc) {
526 	case DIFF_RC_USE_DIFF_ALGO_FALLBACK:
527 		debug("Got DIFF_RC_USE_DIFF_ALGO_FALLBACK (%p)\n",
528 		      algo_config->fallback_algo);
529 		rc = diff_run_algo(algo_config->fallback_algo, state);
530 		goto return_rc;
531 
532 	case DIFF_RC_OK:
533 		/* continue below */
534 		break;
535 
536 	default:
537 		/* some error happened */
538 		goto return_rc;
539 	}
540 
541 	/* Pick up any diff chunks that are still unsolved and feed to
542 	 * inner_algo.  inner_algo will solve unsolved chunks and append to
543 	 * result, and subsequent solved chunks on this level are then appended
544 	 * to result afterwards. */
545 	int i;
546 	for (i = 0; i < state->temp_result.len; i++) {
547 		struct diff_chunk *c = &state->temp_result.head[i];
548 		if (c->solved) {
549 			diff_state_add_solved_chunk(state, c);
550 			continue;
551 		}
552 
553 		/* c is an unsolved chunk, feed to inner_algo */
554 		struct diff_state inner_state = {
555 			.result = state->result,
556 			.recursion_depth_left = state->recursion_depth_left - 1,
557 			.kd_buf = state->kd_buf,
558 			.kd_buf_size = state->kd_buf_size,
559 		};
560 		diff_data_init_subsection(&inner_state.left, &state->left,
561 					  c->left_start, c->left_count);
562 		diff_data_init_subsection(&inner_state.right, &state->right,
563 					  c->right_start, c->right_count);
564 
565 		rc = diff_run_algo(algo_config->inner_algo, &inner_state);
566 		state->kd_buf = inner_state.kd_buf;
567 		state->kd_buf_size = inner_state.kd_buf_size;
568 		if (rc != DIFF_RC_OK)
569 			goto return_rc;
570 	}
571 
572 	rc = DIFF_RC_OK;
573 return_rc:
574 	ARRAYLIST_FREE(state->temp_result);
575 	return rc;
576 }
577 
578 int
579 diff_atomize_file(struct diff_data *d,
580 		  const struct diff_config *config,
581 		  FILE *f, const uint8_t *data, off_t len, int diff_flags)
582 {
583 	if (!config->atomize_func)
584 		return EINVAL;
585 
586 	diff_data_init_root(d, f, data, len, diff_flags);
587 
588 	return config->atomize_func(config->atomize_func_data, d);
589 
590 }
591 
592 struct diff_result *
593 diff_main(const struct diff_config *config, struct diff_data *left,
594 	  struct diff_data *right)
595 {
596 	struct diff_result *result = malloc(sizeof(struct diff_result));
597 	if (!result)
598 		return NULL;
599 
600 	*result = (struct diff_result){};
601 	result->left = left;
602 	result->right = right;
603 
604 	struct diff_state state = {
605 		.result = result,
606 		.recursion_depth_left = config->max_recursion_depth ? : UINT_MAX,
607 		.kd_buf = NULL,
608 		.kd_buf_size = 0,
609 	};
610 	diff_data_init_subsection(&state.left, left,
611 				  left->atoms.head,
612 				  left->atoms.len);
613 	diff_data_init_subsection(&state.right, right,
614 				  right->atoms.head,
615 				  right->atoms.len);
616 
617 	result->rc = diff_run_algo(config->algo, &state);
618 	free(state.kd_buf);
619 
620 	return result;
621 }
622 
623 void
624 diff_result_free(struct diff_result *result)
625 {
626 	if (!result)
627 		return;
628 	ARRAYLIST_FREE(result->chunks);
629 	free(result);
630 }