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 /* Set unique_here = true for all atoms that exist exactly once in this list. */
33 static int
34 diff_atoms_mark_unique(struct diff_data *d, unsigned int *unique_count)
35 {
36 	struct diff_atom *i;
37 	unsigned int count = 0;
38 	diff_data_foreach_atom(i, d) {
39 		i->patience.unique_here = true;
40 		i->patience.unique_in_both = true;
41 		count++;
42 	}
43 	diff_data_foreach_atom(i, d) {
44 		struct diff_atom *j;
45 
46 		if (!i->patience.unique_here)
47 			continue;
48 
49 		diff_data_foreach_atom_from(i + 1, j, d) {
50 			bool same;
51 			int r = diff_atom_same(&same, i, j);
52 			if (r)
53 				return r;
54 			if (!same)
55 				continue;
56 			if (i->patience.unique_here) {
57 				i->patience.unique_here = false;
58 				i->patience.unique_in_both = false;
59 				count--;
60 			}
61 			j->patience.unique_here = false;
62 			j->patience.unique_in_both = false;
63 			count--;
64 		}
65 	}
66 	if (unique_count)
67 		*unique_count = count;
68 	return 0;
69 }
70 
71 /* Mark those lines as atom->patience.unique_in_both = true that appear exactly
72  * once in each side. */
73 static int
74 diff_atoms_mark_unique_in_both(struct diff_data *left, struct diff_data *right,
75 			       unsigned int *unique_in_both_count)
76 {
77 	/* Derive the final unique_in_both count without needing an explicit
78 	 * iteration. So this is just some optimiziation to save one iteration
79 	 * in the end. */
80 	unsigned int unique_in_both;
81 	int r;
82 
83 	r = diff_atoms_mark_unique(left, &unique_in_both);
84 	if (r)
85 		return r;
86 	r = diff_atoms_mark_unique(right, NULL);
87 	if (r)
88 		return r;
89 
90 	debug("unique_in_both %u\n", unique_in_both);
91 
92 	struct diff_atom *i;
93 	diff_data_foreach_atom(i, left) {
94 		if (!i->patience.unique_here)
95 			continue;
96 		struct diff_atom *j;
97 		int found_in_b = 0;
98 		diff_data_foreach_atom(j, right) {
99 			bool same;
100 			int r = diff_atom_same(&same, i, j);
101 			if (r)
102 				return r;
103 			if (!same)
104 				continue;
105 			if (!j->patience.unique_here) {
106 				found_in_b = 2; /* or more */
107 				break;
108 			} else {
109 				found_in_b = 1;
110 				j->patience.pos_in_other = i;
111 				i->patience.pos_in_other = j;
112 			}
113 		}
114 
115 		if (found_in_b == 0 || found_in_b > 1) {
116 			i->patience.unique_in_both = false;
117 			unique_in_both--;
118 			debug("unique_in_both %u  (%d) ", unique_in_both,
119 			      found_in_b);
120 			debug_dump_atom(left, NULL, i);
121 		}
122 	}
123 
124 	/* Still need to unmark right[*]->patience.unique_in_both for atoms that
125 	 * don't exist in left */
126 	diff_data_foreach_atom(i, right) {
127 		if (!i->patience.unique_here
128 		    || !i->patience.unique_in_both)
129 			continue;
130 		struct diff_atom *j;
131 		bool found_in_a = false;
132 		diff_data_foreach_atom(j, left) {
133 			bool same;
134 			int r;
135 			if (!j->patience.unique_in_both)
136 				continue;
137 			r = diff_atom_same(&same, i, j);
138 			if (r)
139 				return r;
140 			if (!same)
141 				continue;
142 			found_in_a = true;
143 			break;
144 		}
145 
146 		if (!found_in_a)
147 			i->patience.unique_in_both = false;
148 	}
149 
150 	if (unique_in_both_count)
151 		*unique_in_both_count = unique_in_both;
152 	return 0;
153 }
154 
155 static int
156 diff_atoms_swallow_identical_neighbors(struct diff_data *left,
157 				       struct diff_data *right,
158 				       unsigned int *unique_in_both_count)
159 {
160 	debug("trivially combine identical lines"
161 	      " around unique_in_both lines\n");
162 
163 	unsigned int l_idx;
164 	unsigned int next_l_idx;
165 	unsigned int l_min = 0;
166 	unsigned int r_min = 0;
167 	for (l_idx = 0; l_idx < left->atoms.len; l_idx = next_l_idx) {
168 		next_l_idx = l_idx + 1;
169 		struct diff_atom *l = &left->atoms.head[l_idx];
170 
171 		if (!l->patience.unique_in_both)
172 			continue;
173 
174 		debug("check identical lines around ");
175 		debug_dump_atom(left, right, l);
176 
177 		unsigned int r_idx = diff_atom_idx(right,
178 						   l->patience.pos_in_other);
179 
180 		struct diff_range identical_l;
181 		struct diff_range identical_r;
182 
183 		/* Swallow upwards.
184 		 * Each common-unique line swallows identical lines upwards and
185 		 * downwards.
186 		 * All common-unique lines that were part of the identical lines
187 		 * following below were already swallowed in the previous
188 		 * iteration, so we will never hit another common-unique line
189 		 * above. */
190 		for (identical_l.start = l_idx, identical_r.start = r_idx;
191 		     identical_l.start > l_min && identical_r.start > r_min;
192 		     identical_l.start--, identical_r.start--) {
193 			bool same;
194 			int r = diff_atom_same(&same,
195 				&left->atoms.head[identical_l.start - 1],
196 				&right->atoms.head[identical_r.start - 1]);
197 			if (r)
198 				return r;
199 			if (!same)
200 				break;
201 		}
202 
203 		/* Swallow downwards */
204 		for (identical_l.end = l_idx + 1, identical_r.end = r_idx + 1;
205 		     identical_l.end < left->atoms.len
206 			 && identical_r.end < right->atoms.len;
207 		     identical_l.end++, identical_r.end++,
208 		     next_l_idx++) {
209 			struct diff_atom *l_end;
210 			struct diff_atom *r_end;
211 			bool same;
212 			int r = diff_atom_same(&same,
213 					&left->atoms.head[identical_l.end],
214 					&right->atoms.head[identical_r.end]);
215 			if (r)
216 				return r;
217 			if (!same)
218 				break;
219 			l_end = &left->atoms.head[identical_l.end];
220 			r_end = &right->atoms.head[identical_r.end];
221 			if (!l_end->patience.unique_in_both)
222 				continue;
223 			/* Part of a chunk of identical lines, remove from
224 			 * listing of unique_in_both lines */
225 			l_end->patience.unique_in_both = false;
226 			r_end->patience.unique_in_both = false;
227 			(*unique_in_both_count)--;
228 		}
229 
230 		l->patience.identical_lines = identical_l;
231 		l->patience.pos_in_other->patience.identical_lines =
232 			identical_r;
233 
234 		l_min = identical_l.end;
235 		r_min = identical_r.end;
236 
237 		if (!diff_range_empty(&l->patience.identical_lines)) {
238 			debug("common-unique line at l=%u r=%u swallowed"
239 			      " identical lines l=%u-%u r=%u-%u\n",
240 			      l_idx, r_idx,
241 			      identical_l.start, identical_l.end,
242 			      identical_r.start, identical_r.end);
243 		}
244 		debug("next_l_idx = %u\n", next_l_idx);
245 	}
246 	return 0;
247 }
248 
249 /* binary search to find the stack to put this atom "card" on. */
250 static int
251 find_target_stack(struct diff_atom *atom,
252 		  struct diff_atom **patience_stacks,
253 		  unsigned int patience_stacks_count)
254 {
255 	unsigned int lo = 0;
256 	unsigned int hi = patience_stacks_count;
257 	while (lo < hi) {
258 		unsigned int mid = (lo + hi) >> 1;
259 
260 		if (patience_stacks[mid]->patience.pos_in_other
261 		    < atom->patience.pos_in_other)
262 			lo = mid + 1;
263 		else
264 			hi = mid;
265 	}
266 	return lo;
267 }
268 
269 /* Among the lines that appear exactly once in each side, find the longest
270  * streak that appear in both files in the same order (with other stuff allowed
271  * to interleave). Use patience sort for that, as in the Patience Diff
272  * algorithm.
273  * See https://bramcohen.livejournal.com/73318.html and, for a much more
274  * detailed explanation,
275  * https://blog.jcoglan.com/2017/09/19/the-patience-diff-algorithm/ */
276 int
277 diff_algo_patience(const struct diff_algo_config *algo_config,
278 		   struct diff_state *state)
279 {
280 	int rc;
281 
282 	struct diff_data *left = &state->left;
283 	struct diff_data *right = &state->right;
284 
285 	unsigned int unique_in_both_count;
286 
287 	debug("\n** %s\n", __func__);
288 
289 	/* Find those lines that appear exactly once in 'left' and exactly once
290 	 * in 'right'. */
291 	rc = diff_atoms_mark_unique_in_both(left, right, &unique_in_both_count);
292 	if (rc)
293 		return rc;
294 
295 	debug("unique_in_both_count %u\n", unique_in_both_count);
296 	debug("left:\n");
297 	debug_dump(left);
298 	debug("right:\n");
299 	debug_dump(right);
300 
301 	if (!unique_in_both_count) {
302 		/* Cannot apply Patience, tell the caller to use fallback_algo
303 		 * instead. */
304 		return DIFF_RC_USE_DIFF_ALGO_FALLBACK;
305 	}
306 
307 	rc = diff_atoms_swallow_identical_neighbors(left, right,
308 						    &unique_in_both_count);
309 	if (rc)
310 		return rc;
311 	debug("After swallowing identical neighbors: unique_in_both = %u\n",
312 	      unique_in_both_count);
313 
314 	rc = ENOMEM;
315 
316 	/* An array of Longest Common Sequence is the result of the below
317 	 * subscope: */
318 	unsigned int lcs_count = 0;
319 	struct diff_atom **lcs = NULL;
320 	struct diff_atom *lcs_tail = NULL;
321 
322 	{
323 		/* This subscope marks the lifetime of the atom_pointers
324 		 * allocation */
325 
326 		/* One chunk of storage for atom pointers */
327 		struct diff_atom **atom_pointers;
328 		atom_pointers = recallocarray(NULL, 0, unique_in_both_count * 2,
329 					      sizeof(struct diff_atom*));
330 
331 		/* Half for the list of atoms that still need to be put on
332 		 * stacks */
333 		struct diff_atom **uniques = atom_pointers;
334 
335 		/* Half for the patience sort state's "card stacks" -- we
336 		 * remember only each stack's topmost "card" */
337 		struct diff_atom **patience_stacks;
338 		patience_stacks = atom_pointers + unique_in_both_count;
339 		unsigned int patience_stacks_count = 0;
340 
341 		/* Take all common, unique items from 'left' ... */
342 
343 		struct diff_atom *atom;
344 		struct diff_atom **uniques_end = uniques;
345 		diff_data_foreach_atom(atom, left) {
346 			if (!atom->patience.unique_in_both)
347 				continue;
348 			*uniques_end = atom;
349 			uniques_end++;
350 		}
351 
352 		/* ...and sort them to the order found in 'right'.
353 		 * The idea is to find the leftmost stack that has a higher line
354 		 * number and add it to the stack's top.
355 		 * If there is no such stack, open a new one on the right. The
356 		 * line number is derived from the atom*, which are array items
357 		 * and hence reflect the relative position in the source file.
358 		 * So we got the common-uniques from 'left' and sort them
359 		 * according to atom->patience.pos_in_other. */
360 		unsigned int i;
361 		for (i = 0; i < unique_in_both_count; i++) {
362 			atom = uniques[i];
363 			unsigned int target_stack;
364 			target_stack = find_target_stack(atom, patience_stacks,
365 							 patience_stacks_count);
366 			assert(target_stack <= patience_stacks_count);
367 			patience_stacks[target_stack] = atom;
368 			if (target_stack == patience_stacks_count)
369 				patience_stacks_count++;
370 
371 			/* Record a back reference to the next stack on the
372 			 * left, which will form the final longest sequence
373 			 * later. */
374 			atom->patience.prev_stack = target_stack ?
375 				patience_stacks[target_stack - 1] : NULL;
376 
377 		}
378 
379 		/* backtrace through prev_stack references to form the final
380 		 * longest common sequence */
381 		lcs_tail = patience_stacks[patience_stacks_count - 1];
382 		lcs_count = patience_stacks_count;
383 
384 		/* uniques and patience_stacks are no longer needed.
385 		 * Backpointers are in atom->patience.prev_stack */
386 		free(atom_pointers);
387 	}
388 
389 	lcs = recallocarray(NULL, 0, lcs_count, sizeof(struct diff_atom*));
390 	struct diff_atom **lcs_backtrace_pos = &lcs[lcs_count - 1];
391 	struct diff_atom *atom;
392 	for (atom = lcs_tail; atom; atom = atom->patience.prev_stack, lcs_backtrace_pos--) {
393 		assert(lcs_backtrace_pos >= lcs);
394 		*lcs_backtrace_pos = atom;
395 	}
396 
397 	unsigned int i;
398 	if (DEBUG) {
399 		debug("\npatience LCS:\n");
400 		for (i = 0; i < lcs_count; i++) {
401 			debug_dump_atom(left, right, lcs[i]);
402 		}
403 	}
404 
405 
406 	/* TODO: For each common-unique line found (now listed in lcs), swallow
407 	 * lines upwards and downwards that are identical on each side. Requires
408 	 * a way to represent atoms being glued to adjacent atoms. */
409 
410 	debug("\ntraverse LCS, possibly recursing:\n");
411 
412 	/* Now we have pinned positions in both files at which it makes sense to
413 	 * divide the diff problem into smaller chunks. Go into the next round:
414 	 * look at each section in turn, trying to again find common-unique
415 	 * lines in those smaller sections. As soon as no more are found, the
416 	 * remaining smaller sections are solved by Myers. */
417 	unsigned int left_pos = 0;
418 	unsigned int right_pos = 0;
419 	for (i = 0; i <= lcs_count; i++) {
420 		struct diff_atom *atom;
421 		struct diff_atom *atom_r;
422 		unsigned int left_idx;
423 		unsigned int right_idx;
424 
425 		if (i < lcs_count) {
426 			atom = lcs[i];
427 			atom_r = atom->patience.pos_in_other;
428 			debug("lcs[%u] = left[%u] = right[%u]\n", i,
429 			      diff_atom_idx(left, atom), diff_atom_idx(right, atom_r));
430 			left_idx = atom->patience.identical_lines.start;
431 			right_idx = atom_r->patience.identical_lines.start;
432 			debug(" identical lines l %u-%u  r %u-%u\n",
433 			      atom->patience.identical_lines.start, atom->patience.identical_lines.end,
434 			      atom_r->patience.identical_lines.start, atom_r->patience.identical_lines.end);
435 		} else {
436 			atom = NULL;
437 			atom_r = NULL;
438 			left_idx = left->atoms.len;
439 			right_idx = right->atoms.len;
440 		}
441 
442 		/* 'atom' now marks an atom that matches on both sides according
443 		 * to patience-diff (a common-unique identical atom in both
444 		 * files).
445 		 * Handle the section before and the atom itself; the section
446 		 * after will be handled by the next loop iteration -- note that
447 		 * i loops to last element + 1 ("i <= lcs_count"), so that there
448 		 * will be another final iteration to pick up the last remaining
449 		 * items after the last LCS atom.
450 		 * The sections before might also be empty on left and/or right.
451 		 * left_pos and right_pos mark the indexes of the first atoms
452 		 * that have not yet been handled in the previous loop
453 		 * iteration.  left_idx and right_idx mark the indexes of the
454 		 * matching atom on left and right, respectively. */
455 
456 		debug("iteration %u  left_pos %u  left_idx %u"
457 		      "  right_pos %u  right_idx %u\n",
458 		      i, left_pos, left_idx, right_pos, right_idx);
459 
460 		/* Section before the matching atom */
461 		struct diff_atom *left_atom = &left->atoms.head[left_pos];
462 		unsigned int left_section_len = left_idx - left_pos;
463 
464 		struct diff_atom *right_atom = &(right->atoms.head[right_pos]);
465 		unsigned int right_section_len = right_idx - right_pos;
466 
467 		if (left_section_len && right_section_len) {
468 			/* Record an unsolved chunk, the caller will apply
469 			 * inner_algo() on this chunk. */
470 			if (!diff_state_add_chunk(state, false,
471 						  left_atom, left_section_len,
472 						  right_atom,
473 						  right_section_len))
474 				goto return_rc;
475 		} else if (left_section_len && !right_section_len) {
476 			/* Only left atoms and none on the right, they form a
477 			 * "minus" chunk, then. */
478 			if (!diff_state_add_chunk(state, true,
479 						  left_atom, left_section_len,
480 						  right_atom, 0))
481 				goto return_rc;
482 		} else if (!left_section_len && right_section_len) {
483 			/* No left atoms, only atoms on the right, they form a
484 			 * "plus" chunk, then. */
485 			if (!diff_state_add_chunk(state, true,
486 						  left_atom, 0,
487 						  right_atom, right_section_len))
488 				goto return_rc;
489 		}
490 		/* else: left_section_len == 0 and right_section_len == 0, i.e.
491 		 * nothing here. */
492 
493 		/* The atom found to match on both sides forms a chunk of equals
494 		 * on each side. In the very last iteration of this loop, there
495 		 * is no matching atom, we were just cleaning out the remaining
496 		 * lines. */
497 		if (atom) {
498 			void *ok;
499 			ok = diff_state_add_chunk(state, true,
500 				left->atoms.head
501 				    + atom->patience.identical_lines.start,
502 				diff_range_len(&atom->patience.identical_lines),
503 				right->atoms.head
504 				    + atom_r->patience.identical_lines.start,
505 				diff_range_len(&atom_r->patience.identical_lines));
506 			if (!ok)
507 				goto return_rc;
508 			left_pos = atom->patience.identical_lines.end;
509 			right_pos = atom_r->patience.identical_lines.end;
510 		} else {
511 			left_pos = left_idx + 1;
512 			right_pos = right_idx + 1;
513 		}
514 		debug("end of iteration %u  left_pos %u  left_idx %u"
515 		      "  right_pos %u  right_idx %u\n",
516 		      i, left_pos, left_idx, right_pos, right_idx);
517 	}
518 	debug("** END %s\n", __func__);
519 
520 	rc = DIFF_RC_OK;
521 
522 return_rc:
523 	free(lcs);
524 	return rc;
525 }