1 /* Implementation of the Patience Diff algorithm invented by Bram Cohen:
2  * Divide a diff problem into smaller chunks by an LCS of common-unique lines. */
3 /*
4  * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
5  *
6  * Permission to use, copy, modify, and distribute this software for any
7  * purpose with or without fee is hereby granted, provided that the above
8  * copyright notice and this permission notice appear in all copies.
9  *
10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17  */
18 
19 #include <assert.h>
20 #include <inttypes.h>
21 #include <errno.h>
22 #include <stdbool.h>
23 #include <stdio.h>
24 #include <stdlib.h>
25 
26 #include <arraylist.h>
27 #include <diff_main.h>
28 
29 #include "diff_internal.h"
30 #include "diff_debug.h"
31 
32 /* Per-atom state for the Patience Diff algorithm */
33 struct atom_patience {
34 	bool unique_in_both;
35 	struct diff_atom *pos_in_other;
36 	struct diff_atom *prev_stack;
37 	struct diff_range identical_lines;
38 };
39 
40 /* A diff_atom has a backpointer to the root diff_data. That points to the
41  * current diff_data, a possibly smaller section of the root. That current
42  * diff_data->algo_data is a pointer to an array of struct atom_patience. The
43  * atom's index in current diff_data gives the index in the atom_patience array.
44  */
45 #define PATIENCE(ATOM) \
46 	(((struct atom_patience*)((ATOM)->root->current->algo_data))\
47 	 [diff_atom_idx((ATOM)->root->current, ATOM)])
48 
49 int diff_atoms_mergesort_compar(const void *_a, const void *_b)
50 {
51 	const struct diff_atom *a = *(struct diff_atom**)_a;
52 	const struct diff_atom *b = *(struct diff_atom**)_b;
53 	int cmp;
54 	int rc = 0;
55 
56 	/* If there's been an error (e.g. I/O error) in a previous compar, we
57 	 * have no way to abort the mergesort but just report the rc and stop
58 	 * comparing. Make sure to catch errors on either side. If atoms are
59 	 * from more than one diff_data, make sure the error, if any, spreads
60 	 * to all of them, so we can cut short all future comparisons. */
61 	if (a->root->err)
62 		rc = a->root->err;
63 	if (b->root->err)
64 		rc = b->root->err;
65 	if (rc) {
66 		a->root->err = rc;
67 		b->root->err = rc;
68 		/* just return 'equal' to not swap more positions */
69 		return 0;
70 	}
71 
72 	/* Sort by the simplistic hash */
73 	if (a->hash < b->hash)
74 		return -1;
75 	if (a->hash > b->hash)
76 		return 1;
77 
78 	/* If hashes are the same, the lines may still differ. Do a full cmp. */
79 	rc = diff_atom_cmp(&cmp, a, b);
80 
81 	if (rc) {
82 		/* Mark the I/O error so that the caller can find out about it.
83 		 * For the case atoms are from more than one diff_data, mark in
84 		 * both. */
85 		a->root->err = rc;
86 		if (a->root != b->root)
87 			b->root->err = rc;
88 		return 0;
89 	}
90 
91 	return cmp;
92 }
93 
94 /* Sort an array of struct diff_atom* in-place. */
95 static int diff_atoms_sort(struct diff_atom *atoms[],
96 			    size_t atoms_count)
97 {
98 	/*
99 	 * Use mergesort(3) bcause it provides stable ordering
100 	 * even if two or more elements are equal.
101 	 */
102 	mergesort(atoms, atoms_count, sizeof(struct diff_atom*),
103 	      diff_atoms_mergesort_compar);
104 	return atoms[0]->root->err;
105 }
106 
107 static int
108 diff_atoms_mark_unique_in_both(struct diff_data *left, struct diff_data *right,
109 			       unsigned int *unique_in_both_count_p)
110 {
111 	struct diff_atom *a;
112 	struct diff_atom *b;
113 	struct diff_atom **all_atoms;
114 	unsigned int len = 0;
115 	unsigned int i;
116 	unsigned int unique_in_both_count = 0;
117 	int rc;
118 
119 	all_atoms = calloc(left->atoms.len + right->atoms.len,
120 	    sizeof(struct diff_atom *));
121 	if (all_atoms == NULL)
122 		return ENOMEM;
123 
124 	left->err = 0;
125 	right->err = 0;
126 	left->root->err = 0;
127 	right->root->err = 0;
128 	diff_data_foreach_atom(a, left) {
129 		all_atoms[len++] = a;
130 	}
131 	diff_data_foreach_atom(b, right) {
132 		all_atoms[len++] = b;
133 	}
134 
135 	rc = diff_atoms_sort(all_atoms, len);
136 	if (rc)
137 		goto free_and_exit;
138 
139 	/* Now we have a sorted array of atom pointers. All similar lines are
140 	 * adjacent. Walk through the array and mark those that are unique on
141 	 * each side, but exist once in both sources. */
142 	for (i = 0; i < len; i++) {
143 		bool same;
144 		unsigned int j;
145 		unsigned int count_first_side = 1;
146 		unsigned int count_other_side = 0;
147 		a = all_atoms[i];
148 
149 		for (j = i+1; j < len; j++) {
150 			b = all_atoms[j];
151 			rc = diff_atom_same(&same, a, b);
152 			if (rc)
153 				goto free_and_exit;
154 			if (!same)
155 				break;
156 			/* A following atom is the same. See on which side the
157 			 * repetition counts. */
158 			if (a->root == b->root)
159 				count_first_side ++;
160 			else
161 				count_other_side ++;
162 		}
163 
164 		/* Counted a section of similar atoms, put the results back to
165 		 * the atoms. */
166 		if ((count_first_side == 1)
167 		    && (count_other_side == 1)) {
168 			b = all_atoms[i+1];
169 			PATIENCE(a).unique_in_both = true;
170 			PATIENCE(a).pos_in_other = b;
171 			PATIENCE(b).unique_in_both = true;
172 			PATIENCE(b).pos_in_other = a;
173 			unique_in_both_count++;
174 		}
175 	}
176 	*unique_in_both_count_p = unique_in_both_count;
177 	rc = 0;
178 free_and_exit:
179 	free(all_atoms);
180 	return rc;
181 }
182 
183 static int
184 diff_atoms_swallow_identical_neighbors(struct diff_data *left,
185 				       struct diff_data *right,
186 				       unsigned int *unique_in_both_count)
187 {
188 	debug("trivially combine identical lines"
189 	      " around unique_in_both lines\n");
190 
191 	unsigned int l_idx;
192 	unsigned int next_l_idx;
193 	unsigned int l_min = 0;
194 	unsigned int r_min = 0;
195 	for (l_idx = 0; l_idx < left->atoms.len; l_idx = next_l_idx) {
196 		next_l_idx = l_idx + 1;
197 		struct diff_atom *l = &left->atoms.head[l_idx];
198 
199 		if (!PATIENCE(l).unique_in_both)
200 			continue;
201 
202 		debug("check identical lines around ");
203 		debug_dump_atom(left, right, l);
204 
205 		unsigned int r_idx = diff_atom_idx(right, PATIENCE(l).pos_in_other);
206 
207 		struct diff_range identical_l;
208 		struct diff_range identical_r;
209 
210 		/* Swallow upwards.
211 		 * Each common-unique line swallows identical lines upwards and
212 		 * downwards.
213 		 * All common-unique lines that were part of the identical lines
214 		 * following below were already swallowed in the previous
215 		 * iteration, so we will never hit another common-unique line
216 		 * above. */
217 		for (identical_l.start = l_idx, identical_r.start = r_idx;
218 		     identical_l.start > l_min && identical_r.start > r_min;
219 		     identical_l.start--, identical_r.start--) {
220 			bool same;
221 			int r = diff_atom_same(&same,
222 				&left->atoms.head[identical_l.start - 1],
223 				&right->atoms.head[identical_r.start - 1]);
224 			if (r)
225 				return r;
226 			if (!same)
227 				break;
228 		}
229 
230 		/* Swallow downwards */
231 		for (identical_l.end = l_idx + 1, identical_r.end = r_idx + 1;
232 		     identical_l.end < left->atoms.len
233 			 && identical_r.end < right->atoms.len;
234 		     identical_l.end++, identical_r.end++,
235 		     next_l_idx++) {
236 			struct diff_atom *l_end;
237 			struct diff_atom *r_end;
238 			bool same;
239 			int r = diff_atom_same(&same,
240 					&left->atoms.head[identical_l.end],
241 					&right->atoms.head[identical_r.end]);
242 			if (r)
243 				return r;
244 			if (!same)
245 				break;
246 			l_end = &left->atoms.head[identical_l.end];
247 			r_end = &right->atoms.head[identical_r.end];
248 			if (!PATIENCE(l_end).unique_in_both)
249 				continue;
250 			/* Part of a chunk of identical lines, remove from
251 			 * listing of unique_in_both lines */
252 			PATIENCE(l_end).unique_in_both = false;
253 			PATIENCE(r_end).unique_in_both = false;
254 			(*unique_in_both_count)--;
255 		}
256 
257 		PATIENCE(l).identical_lines = identical_l;
258 		PATIENCE(PATIENCE(l).pos_in_other).identical_lines =
259 			identical_r;
260 
261 		l_min = identical_l.end;
262 		r_min = identical_r.end;
263 
264 		if (!diff_range_empty(&PATIENCE(l).identical_lines)) {
265 			debug("common-unique line at l=%u r=%u swallowed"
266 			      " identical lines l=%u-%u r=%u-%u\n",
267 			      l_idx, r_idx,
268 			      identical_l.start, identical_l.end,
269 			      identical_r.start, identical_r.end);
270 		}
271 		debug("next_l_idx = %u\n", next_l_idx);
272 	}
273 	return 0;
274 }
275 
276 /* binary search to find the stack to put this atom "card" on. */
277 static int
278 find_target_stack(struct diff_atom *atom,
279 		  struct diff_atom **patience_stacks,
280 		  unsigned int patience_stacks_count)
281 {
282 	unsigned int lo = 0;
283 	unsigned int hi = patience_stacks_count;
284 	while (lo < hi) {
285 		unsigned int mid = (lo + hi) >> 1;
286 
287 		if (PATIENCE(patience_stacks[mid]).pos_in_other
288 		    < PATIENCE(atom).pos_in_other)
289 			lo = mid + 1;
290 		else
291 			hi = mid;
292 	}
293 	return lo;
294 }
295 
296 /* Among the lines that appear exactly once in each side, find the longest
297  * streak that appear in both files in the same order (with other stuff allowed
298  * to interleave). Use patience sort for that, as in the Patience Diff
299  * algorithm.
300  * See https://bramcohen.livejournal.com/73318.html and, for a much more
301  * detailed explanation,
302  * https://blog.jcoglan.com/2017/09/19/the-patience-diff-algorithm/ */
303 int
304 diff_algo_patience(const struct diff_algo_config *algo_config,
305 		   struct diff_state *state)
306 {
307 	int rc;
308 	struct diff_data *left = &state->left;
309 	struct diff_data *right = &state->right;
310 	struct atom_patience *atom_patience_left =
311 		calloc(left->atoms.len, sizeof(struct atom_patience));
312 	struct atom_patience *atom_patience_right =
313 		calloc(right->atoms.len, sizeof(struct atom_patience));
314 	unsigned int unique_in_both_count;
315 	struct diff_atom **lcs = NULL;
316 
317 	debug("\n** %s\n", __func__);
318 
319 	left->root->current = left;
320 	right->root->current = right;
321 	left->algo_data = atom_patience_left;
322 	right->algo_data = atom_patience_right;
323 
324 	/* Find those lines that appear exactly once in 'left' and exactly once
325 	 * in 'right'. */
326 	rc = diff_atoms_mark_unique_in_both(left, right, &unique_in_both_count);
327 	if (rc)
328 		goto free_and_exit;
329 
330 	debug("unique_in_both_count %u\n", unique_in_both_count);
331 	debug("left:\n");
332 	debug_dump(left);
333 	debug("right:\n");
334 	debug_dump(right);
335 
336 	if (!unique_in_both_count) {
337 		/* Cannot apply Patience, tell the caller to use fallback_algo
338 		 * instead. */
339 		rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK;
340 		goto free_and_exit;
341 	}
342 
343 	rc = diff_atoms_swallow_identical_neighbors(left, right,
344 						    &unique_in_both_count);
345 	if (rc)
346 		goto free_and_exit;
347 	debug("After swallowing identical neighbors: unique_in_both = %u\n",
348 	      unique_in_both_count);
349 
350 	rc = ENOMEM;
351 
352 	/* An array of Longest Common Sequence is the result of the below
353 	 * subscope: */
354 	unsigned int lcs_count = 0;
355 	struct diff_atom *lcs_tail = NULL;
356 
357 	{
358 		/* This subscope marks the lifetime of the atom_pointers
359 		 * allocation */
360 
361 		/* One chunk of storage for atom pointers */
362 		struct diff_atom **atom_pointers;
363 		atom_pointers = recallocarray(NULL, 0, unique_in_both_count * 2,
364 					      sizeof(struct diff_atom*));
365 
366 		/* Half for the list of atoms that still need to be put on
367 		 * stacks */
368 		struct diff_atom **uniques = atom_pointers;
369 
370 		/* Half for the patience sort state's "card stacks" -- we
371 		 * remember only each stack's topmost "card" */
372 		struct diff_atom **patience_stacks;
373 		patience_stacks = atom_pointers + unique_in_both_count;
374 		unsigned int patience_stacks_count = 0;
375 
376 		/* Take all common, unique items from 'left' ... */
377 
378 		struct diff_atom *atom;
379 		struct diff_atom **uniques_end = uniques;
380 		diff_data_foreach_atom(atom, left) {
381 			if (!PATIENCE(atom).unique_in_both)
382 				continue;
383 			*uniques_end = atom;
384 			uniques_end++;
385 		}
386 
387 		/* ...and sort them to the order found in 'right'.
388 		 * The idea is to find the leftmost stack that has a higher line
389 		 * number and add it to the stack's top.
390 		 * If there is no such stack, open a new one on the right. The
391 		 * line number is derived from the atom*, which are array items
392 		 * and hence reflect the relative position in the source file.
393 		 * So we got the common-uniques from 'left' and sort them
394 		 * according to PATIENCE(atom).pos_in_other. */
395 		unsigned int i;
396 		for (i = 0; i < unique_in_both_count; i++) {
397 			atom = uniques[i];
398 			unsigned int target_stack;
399 			target_stack = find_target_stack(atom, patience_stacks,
400 							 patience_stacks_count);
401 			assert(target_stack <= patience_stacks_count);
402 			patience_stacks[target_stack] = atom;
403 			if (target_stack == patience_stacks_count)
404 				patience_stacks_count++;
405 
406 			/* Record a back reference to the next stack on the
407 			 * left, which will form the final longest sequence
408 			 * later. */
409 			PATIENCE(atom).prev_stack = target_stack ?
410 				patience_stacks[target_stack - 1] : NULL;
411 
412 		}
413 
414 		/* backtrace through prev_stack references to form the final
415 		 * longest common sequence */
416 		lcs_tail = patience_stacks[patience_stacks_count - 1];
417 		lcs_count = patience_stacks_count;
418 
419 		/* uniques and patience_stacks are no longer needed.
420 		 * Backpointers are in PATIENCE(atom).prev_stack */
421 		free(atom_pointers);
422 	}
423 
424 	lcs = recallocarray(NULL, 0, lcs_count, sizeof(struct diff_atom*));
425 	struct diff_atom **lcs_backtrace_pos = &lcs[lcs_count - 1];
426 	struct diff_atom *atom;
427 	for (atom = lcs_tail; atom; atom = PATIENCE(atom).prev_stack, lcs_backtrace_pos--) {
428 		assert(lcs_backtrace_pos >= lcs);
429 		*lcs_backtrace_pos = atom;
430 	}
431 
432 	unsigned int i;
433 	if (DEBUG) {
434 		debug("\npatience LCS:\n");
435 		for (i = 0; i < lcs_count; i++) {
436 			debug_dump_atom(left, right, lcs[i]);
437 		}
438 	}
439 
440 
441 	/* TODO: For each common-unique line found (now listed in lcs), swallow
442 	 * lines upwards and downwards that are identical on each side. Requires
443 	 * a way to represent atoms being glued to adjacent atoms. */
444 
445 	debug("\ntraverse LCS, possibly recursing:\n");
446 
447 	/* Now we have pinned positions in both files at which it makes sense to
448 	 * divide the diff problem into smaller chunks. Go into the next round:
449 	 * look at each section in turn, trying to again find common-unique
450 	 * lines in those smaller sections. As soon as no more are found, the
451 	 * remaining smaller sections are solved by Myers. */
452 	unsigned int left_pos = 0;
453 	unsigned int right_pos = 0;
454 	for (i = 0; i <= lcs_count; i++) {
455 		struct diff_atom *atom;
456 		struct diff_atom *atom_r;
457 		unsigned int left_idx;
458 		unsigned int right_idx;
459 
460 		if (i < lcs_count) {
461 			atom = lcs[i];
462 			atom_r = PATIENCE(atom).pos_in_other;
463 			debug("lcs[%u] = left[%u] = right[%u]\n", i,
464 			      diff_atom_idx(left, atom), diff_atom_idx(right, atom_r));
465 			left_idx = PATIENCE(atom).identical_lines.start;
466 			right_idx = PATIENCE(atom_r).identical_lines.start;
467 			debug(" identical lines l %u-%u  r %u-%u\n",
468 			      PATIENCE(atom).identical_lines.start, PATIENCE(atom).identical_lines.end,
469 			      PATIENCE(atom_r).identical_lines.start, PATIENCE(atom_r).identical_lines.end);
470 		} else {
471 			atom = NULL;
472 			atom_r = NULL;
473 			left_idx = left->atoms.len;
474 			right_idx = right->atoms.len;
475 		}
476 
477 		/* 'atom' now marks an atom that matches on both sides according
478 		 * to patience-diff (a common-unique identical atom in both
479 		 * files).
480 		 * Handle the section before and the atom itself; the section
481 		 * after will be handled by the next loop iteration -- note that
482 		 * i loops to last element + 1 ("i <= lcs_count"), so that there
483 		 * will be another final iteration to pick up the last remaining
484 		 * items after the last LCS atom.
485 		 * The sections before might also be empty on left and/or right.
486 		 * left_pos and right_pos mark the indexes of the first atoms
487 		 * that have not yet been handled in the previous loop
488 		 * iteration.  left_idx and right_idx mark the indexes of the
489 		 * matching atom on left and right, respectively. */
490 
491 		debug("iteration %u  left_pos %u  left_idx %u"
492 		      "  right_pos %u  right_idx %u\n",
493 		      i, left_pos, left_idx, right_pos, right_idx);
494 
495 		/* Section before the matching atom */
496 		struct diff_atom *left_atom = &left->atoms.head[left_pos];
497 		unsigned int left_section_len = left_idx - left_pos;
498 
499 		struct diff_atom *right_atom = &(right->atoms.head[right_pos]);
500 		unsigned int right_section_len = right_idx - right_pos;
501 
502 		if (left_section_len && right_section_len) {
503 			/* Record an unsolved chunk, the caller will apply
504 			 * inner_algo() on this chunk. */
505 			if (!diff_state_add_chunk(state, false,
506 						  left_atom, left_section_len,
507 						  right_atom,
508 						  right_section_len))
509 				goto free_and_exit;
510 		} else if (left_section_len && !right_section_len) {
511 			/* Only left atoms and none on the right, they form a
512 			 * "minus" chunk, then. */
513 			if (!diff_state_add_chunk(state, true,
514 						  left_atom, left_section_len,
515 						  right_atom, 0))
516 				goto free_and_exit;
517 		} else if (!left_section_len && right_section_len) {
518 			/* No left atoms, only atoms on the right, they form a
519 			 * "plus" chunk, then. */
520 			if (!diff_state_add_chunk(state, true,
521 						  left_atom, 0,
522 						  right_atom, right_section_len))
523 				goto free_and_exit;
524 		}
525 		/* else: left_section_len == 0 and right_section_len == 0, i.e.
526 		 * nothing here. */
527 
528 		/* The atom found to match on both sides forms a chunk of equals
529 		 * on each side. In the very last iteration of this loop, there
530 		 * is no matching atom, we were just cleaning out the remaining
531 		 * lines. */
532 		if (atom) {
533 			void *ok;
534 			ok = diff_state_add_chunk(state, true,
535 				left->atoms.head
536 				    + PATIENCE(atom).identical_lines.start,
537 				diff_range_len(&PATIENCE(atom).identical_lines),
538 				right->atoms.head
539 				    + PATIENCE(atom_r).identical_lines.start,
540 				diff_range_len(&PATIENCE(atom_r).identical_lines));
541 			if (!ok)
542 				goto free_and_exit;
543 			left_pos = PATIENCE(atom).identical_lines.end;
544 			right_pos = PATIENCE(atom_r).identical_lines.end;
545 		} else {
546 			left_pos = left_idx + 1;
547 			right_pos = right_idx + 1;
548 		}
549 		debug("end of iteration %u  left_pos %u  left_idx %u"
550 		      "  right_pos %u  right_idx %u\n",
551 		      i, left_pos, left_idx, right_pos, right_idx);
552 	}
553 	debug("** END %s\n", __func__);
554 
555 	rc = DIFF_RC_OK;
556 
557 free_and_exit:
558 	left->root->current = NULL;
559 	right->root->current = NULL;
560 	free(atom_patience_left);
561 	free(atom_patience_right);
562 	if (lcs)
563 		free(lcs);
564 	return rc;
565 }