1 /* Implementation of the Patience Diff algorithm invented by Bram Cohen:
2  * Divide a diff problem into smaller chunks by an LCS (Longest Common Sequence)
3  * of common-unique lines. */
4 /*
5  * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
6  *
7  * Permission to use, copy, modify, and distribute this software for any
8  * purpose with or without fee is hereby granted, provided that the above
9  * copyright notice and this permission notice appear in all copies.
10  *
11  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18  */
19 
20 #include <assert.h>
21 #include <errno.h>
22 #include <stdbool.h>
23 #include <stdint.h>
24 #include <stdio.h>
25 #include <stdlib.h>
26 
27 #include <arraylist.h>
28 #include <diff_main.h>
29 
30 #include "diff_internal.h"
31 #include "diff_debug.h"
32 
33 /* Algorithm to find unique lines:
34  * 0: stupidly iterate atoms
35  * 1: qsort
36  * 2: mergesort
37  */
38 #define UNIQUE_STRATEGY 1
39 
40 /* Per-atom state for the Patience Diff algorithm */
41 struct atom_patience {
42 #if UNIQUE_STRATEGY == 0
43 	bool unique_here;
44 #endif
45 	bool unique_in_both;
46 	struct diff_atom *pos_in_other;
47 	struct diff_atom *prev_stack;
48 	struct diff_range identical_lines;
49 };
50 
51 /* A diff_atom has a backpointer to the root diff_data. That points to the
52  * current diff_data, a possibly smaller section of the root. That current
53  * diff_data->algo_data is a pointer to an array of struct atom_patience. The
54  * atom's index in current diff_data gives the index in the atom_patience array.
55  */
56 #define PATIENCE(ATOM) \
57 	(((struct atom_patience*)((ATOM)->root->current->algo_data))\
58 	 [diff_atom_idx((ATOM)->root->current, ATOM)])
59 
60 #if UNIQUE_STRATEGY == 0
61 
62 /* Stupid iteration and comparison of all atoms */
63 static int
64 diff_atoms_mark_unique(struct diff_data *d, unsigned int *unique_count)
65 {
66 	struct diff_atom *i;
67 	unsigned int count = 0;
68 	diff_data_foreach_atom(i, d) {
69 		PATIENCE(i).unique_here = true;
70 		PATIENCE(i).unique_in_both = true;
71 		count++;
72 	}
73 	diff_data_foreach_atom(i, d) {
74 		struct diff_atom *j;
75 
76 		if (!PATIENCE(i).unique_here)
77 			continue;
78 
79 		diff_data_foreach_atom_from(i + 1, j, d) {
80 			bool same;
81 			int r = diff_atom_same(&same, i, j);
82 			if (r)
83 				return r;
84 			if (!same)
85 				continue;
86 			if (PATIENCE(i).unique_here) {
87 				PATIENCE(i).unique_here = false;
88 				PATIENCE(i).unique_in_both = false;
89 				count--;
90 			}
91 			PATIENCE(j).unique_here = false;
92 			PATIENCE(j).unique_in_both = false;
93 			count--;
94 		}
95 	}
96 	if (unique_count)
97 		*unique_count = count;
98 	return 0;
99 }
100 
101 /* Mark those lines as PATIENCE(atom).unique_in_both = true that appear exactly
102  * once in each side. */
103 static int
104 diff_atoms_mark_unique_in_both(struct diff_data *left, struct diff_data *right,
105 			       unsigned int *unique_in_both_count)
106 {
107 	/* Derive the final unique_in_both count without needing an explicit
108 	 * iteration. So this is just some optimiziation to save one iteration
109 	 * in the end. */
110 	unsigned int unique_in_both;
111 	int r;
112 
113 	r = diff_atoms_mark_unique(left, &unique_in_both);
114 	if (r)
115 		return r;
116 	r = diff_atoms_mark_unique(right, NULL);
117 	if (r)
118 		return r;
119 
120 	debug("unique_in_both %u\n", unique_in_both);
121 
122 	struct diff_atom *i;
123 	diff_data_foreach_atom(i, left) {
124 		if (!PATIENCE(i).unique_here)
125 			continue;
126 		struct diff_atom *j;
127 		int found_in_b = 0;
128 		diff_data_foreach_atom(j, right) {
129 			bool same;
130 			int r = diff_atom_same(&same, i, j);
131 			if (r)
132 				return r;
133 			if (!same)
134 				continue;
135 			if (!PATIENCE(j).unique_here) {
136 				found_in_b = 2; /* or more */
137 				break;
138 			} else {
139 				found_in_b = 1;
140 				PATIENCE(j).pos_in_other = i;
141 				PATIENCE(i).pos_in_other = j;
142 			}
143 		}
144 
145 		if (found_in_b == 0 || found_in_b > 1) {
146 			PATIENCE(i).unique_in_both = false;
147 			unique_in_both--;
148 			debug("unique_in_both %u  (%d) ", unique_in_both,
149 			      found_in_b);
150 			debug_dump_atom(left, NULL, i);
151 		}
152 	}
153 
154 	/* Still need to unmark right[*]->patience.unique_in_both for atoms that
155 	 * don't exist in left */
156 	diff_data_foreach_atom(i, right) {
157 		if (!PATIENCE(i).unique_here
158 		    || !PATIENCE(i).unique_in_both)
159 			continue;
160 		struct diff_atom *j;
161 		bool found_in_a = false;
162 		diff_data_foreach_atom(j, left) {
163 			bool same;
164 			int r;
165 			if (!PATIENCE(j).unique_in_both)
166 				continue;
167 			r = diff_atom_same(&same, i, j);
168 			if (r)
169 				return r;
170 			if (!same)
171 				continue;
172 			found_in_a = true;
173 			break;
174 		}
175 
176 		if (!found_in_a)
177 			PATIENCE(i).unique_in_both = false;
178 	}
179 
180 	if (unique_in_both_count)
181 		*unique_in_both_count = unique_in_both;
182 	return 0;
183 }
184 
185 #else /* UNIQUE_STRATEGY != 0 */
186 
187 /* Use an optimized sorting algorithm (qsort, mergesort) to find unique lines */
188 
189 int diff_atoms_compar(const void *_a, const void *_b)
190 {
191 	const struct diff_atom *a = *(struct diff_atom**)_a;
192 	const struct diff_atom *b = *(struct diff_atom**)_b;
193 	int cmp;
194 	int rc = 0;
195 
196 	/* If there's been an error (e.g. I/O error) in a previous compar, we
197 	 * have no way to abort the sort but just report the rc and stop
198 	 * comparing. Make sure to catch errors on either side. If atoms are
199 	 * from more than one diff_data, make sure the error, if any, spreads
200 	 * to all of them, so we can cut short all future comparisons. */
201 	if (a->root->err)
202 		rc = a->root->err;
203 	if (b->root->err)
204 		rc = b->root->err;
205 	if (rc) {
206 		a->root->err = rc;
207 		b->root->err = rc;
208 		/* just return 'equal' to not swap more positions */
209 		return 0;
210 	}
211 
212 	/* Sort by the simplistic hash */
213 	if (a->hash < b->hash)
214 		return -1;
215 	if (a->hash > b->hash)
216 		return 1;
217 
218 	/* If hashes are the same, the lines may still differ. Do a full cmp. */
219 	rc = diff_atom_cmp(&cmp, a, b);
220 
221 	if (rc) {
222 		/* Mark the I/O error so that the caller can find out about it.
223 		 * For the case atoms are from more than one diff_data, mark in
224 		 * both. */
225 		a->root->err = rc;
226 		if (a->root != b->root)
227 			b->root->err = rc;
228 		return 0;
229 	}
230 
231 	return cmp;
232 }
233 
234 /* Sort an array of struct diff_atom* in-place. */
235 static int diff_atoms_sort(struct diff_atom *atoms[],
236 			   size_t atoms_count)
237 {
238 #if UNIQUE_STRATEGY == 1
239 	qsort(atoms, atoms_count, sizeof(struct diff_atom*), diff_atoms_compar);
240 #else
241 	mergesort(atoms, atoms_count, sizeof(struct diff_atom*),
242 		  diff_atoms_compar);
243 #endif
244 	return atoms[0]->root->err;
245 }
246 
247 static int
248 diff_atoms_mark_unique_in_both(struct diff_data *left, struct diff_data *right,
249 			       unsigned int *unique_in_both_count_p)
250 {
251 	struct diff_atom *a;
252 	struct diff_atom *b;
253 	struct diff_atom **all_atoms;
254 	unsigned int len = 0;
255 	unsigned int i;
256 	unsigned int unique_in_both_count = 0;
257 	int rc;
258 
259 	all_atoms = calloc(left->atoms.len + right->atoms.len,
260 	    sizeof(struct diff_atom *));
261 	if (all_atoms == NULL)
262 		return ENOMEM;
263 
264 	left->err = 0;
265 	right->err = 0;
266 	left->root->err = 0;
267 	right->root->err = 0;
268 	diff_data_foreach_atom(a, left) {
269 		all_atoms[len++] = a;
270 	}
271 	diff_data_foreach_atom(b, right) {
272 		all_atoms[len++] = b;
273 	}
274 
275 	rc = diff_atoms_sort(all_atoms, len);
276 	if (rc)
277 		goto free_and_exit;
278 
279 	/* Now we have a sorted array of atom pointers. All similar lines are
280 	 * adjacent. Walk through the array and mark those that are unique on
281 	 * each side, but exist once in both sources. */
282 	for (i = 0; i < len; i++) {
283 		bool same;
284 		unsigned int next_differing_i;
285 		unsigned int last_identical_i;
286 		unsigned int j;
287 		unsigned int count_first_side = 1;
288 		unsigned int count_other_side = 0;
289 		a = all_atoms[i];
290 		debug("a: ");
291 		debug_dump_atom(a->root, NULL, a);
292 
293 		/* Do as few diff_atom_cmp() as possible: first walk forward
294 		 * only using the cheap hash as indicator for differing atoms;
295 		 * then walk backwards until hitting an identical atom. */
296 		for (next_differing_i = i + 1; next_differing_i < len;
297 		     next_differing_i++) {
298 			b = all_atoms[next_differing_i];
299 			if (a->hash != b->hash)
300 				break;
301 		}
302 		for (last_identical_i = next_differing_i - 1;
303 		     last_identical_i > i;
304 		     last_identical_i--) {
305 			b = all_atoms[last_identical_i];
306 			rc = diff_atom_same(&same, a, b);
307 			if (rc)
308 				goto free_and_exit;
309 			if (same)
310 				break;
311 		}
312 		next_differing_i = last_identical_i + 1;
313 
314 		for (j = i+1; j < next_differing_i; j++) {
315 			b = all_atoms[j];
316 			/* A following atom is the same. See on which side the
317 			 * repetition counts. */
318 			if (a->root == b->root)
319 				count_first_side ++;
320 			else
321 				count_other_side ++;
322 			debug("b: ");
323 			debug_dump_atom(b->root, NULL, b);
324 			debug("   count_first_side=%d count_other_side=%d\n",
325 			      count_first_side, count_other_side);
326 		}
327 
328 		/* Counted a section of similar atoms, put the results back to
329 		 * the atoms. */
330 		if ((count_first_side == 1)
331 		    && (count_other_side == 1)) {
332 			b = all_atoms[i+1];
333 			PATIENCE(a).unique_in_both = true;
334 			PATIENCE(a).pos_in_other = b;
335 			PATIENCE(b).unique_in_both = true;
336 			PATIENCE(b).pos_in_other = a;
337 			unique_in_both_count++;
338 		}
339 
340 		/* j now points at the first atom after 'a' that is not
341 		 * identical to 'a'. j is always > i. */
342 		i = j - 1;
343 	}
344 	*unique_in_both_count_p = unique_in_both_count;
345 	rc = 0;
346 free_and_exit:
347 	free(all_atoms);
348 	return rc;
349 }
350 #endif /* UNIQUE_STRATEGY != 0 */
351 
352 static int
353 diff_atoms_swallow_identical_neighbors(struct diff_data *left,
354 				       struct diff_data *right,
355 				       unsigned int *unique_in_both_count)
356 {
357 	debug("trivially combine identical lines"
358 	      " around unique_in_both lines\n");
359 
360 	unsigned int l_idx;
361 	unsigned int next_l_idx;
362 	/* Only checking against identical-line overlaps on the left; overlaps
363 	 * on the right are tolerated and ironed out later. See also the other
364 	 * place marked with (1). */
365 	unsigned int l_min = 0;
366 	for (l_idx = 0; l_idx < left->atoms.len; l_idx = next_l_idx) {
367 		next_l_idx = l_idx + 1;
368 		struct diff_atom *l = &left->atoms.head[l_idx];
369 		struct diff_atom *r;
370 
371 		if (!PATIENCE(l).unique_in_both)
372 			continue;
373 
374 		debug("check identical lines around\n");
375 		debug(" L "); debug_dump_atom(left, right, l);
376 
377 		unsigned int r_idx = diff_atom_idx(right, PATIENCE(l).pos_in_other);
378 		r = &right->atoms.head[r_idx];
379 		debug(" R "); debug_dump_atom(right, left, r);
380 
381 		struct diff_range identical_l;
382 		struct diff_range identical_r;
383 
384 		/* Swallow upwards.
385 		 * Each common-unique line swallows identical lines upwards and
386 		 * downwards.
387 		 * Will never hit another identical common-unique line above on
388 		 * the left, because those would already have swallowed this
389 		 * common-unique line in a previous iteration.
390 		 */
391 		for (identical_l.start = l_idx, identical_r.start = r_idx;
392 		     identical_l.start > (l_min+1) && identical_r.start > 0;
393 		     identical_l.start--, identical_r.start--) {
394 			bool same;
395 			int rc = diff_atom_same(&same,
396 				&left->atoms.head[identical_l.start - 1],
397 				&right->atoms.head[identical_r.start - 1]);
398 			if (rc)
399 				return rc;
400 			if (!same)
401 				break;
402 		}
403 
404 		/* Swallow downwards. Join any common-unique lines in a block of
405 		 * matching L/R lines with this one. */
406 		for (identical_l.end = l_idx + 1, identical_r.end = r_idx + 1;
407 		     identical_l.end < left->atoms.len
408 			 && identical_r.end < right->atoms.len;
409 		     identical_l.end++, identical_r.end++,
410 		     next_l_idx++) {
411 			struct diff_atom *l_end;
412 			struct diff_atom *r_end;
413 			bool same;
414 			int rc = diff_atom_same(&same,
415 					&left->atoms.head[identical_l.end],
416 					&right->atoms.head[identical_r.end]);
417 			if (rc)
418 				return rc;
419 			if (!same)
420 				break;
421 			l_end = &left->atoms.head[identical_l.end];
422 			r_end = &right->atoms.head[identical_r.end];
423 			if (!PATIENCE(l_end).unique_in_both)
424 				continue;
425 			/* A unique_in_both atom is joined with a preceding
426 			 * unique_in_both atom, remove the joined atom from
427 			 * listing of unique_in_both atoms */
428 			PATIENCE(l_end).unique_in_both = false;
429 			PATIENCE(r_end).unique_in_both = false;
430 			(*unique_in_both_count)--;
431 		}
432 
433 		PATIENCE(l).identical_lines = identical_l;
434 		PATIENCE(r).identical_lines = identical_r;
435 
436 		l_min = identical_l.end;
437 
438 		if (!diff_range_empty(&PATIENCE(l).identical_lines)) {
439 			debug("common-unique line at l=%u r=%u swallowed"
440 			      " identical lines l=%u-%u r=%u-%u\n",
441 			      l_idx, r_idx,
442 			      identical_l.start, identical_l.end,
443 			      identical_r.start, identical_r.end);
444 		}
445 		debug("next_l_idx = %u\n", next_l_idx);
446 	}
447 	return 0;
448 }
449 
450 /* binary search to find the stack to put this atom "card" on. */
451 static int
452 find_target_stack(struct diff_atom *atom,
453 		  struct diff_atom **patience_stacks,
454 		  unsigned int patience_stacks_count)
455 {
456 	unsigned int lo = 0;
457 	unsigned int hi = patience_stacks_count;
458 	while (lo < hi) {
459 		unsigned int mid = (lo + hi) >> 1;
460 
461 		if (PATIENCE(patience_stacks[mid]).pos_in_other
462 		    < PATIENCE(atom).pos_in_other)
463 			lo = mid + 1;
464 		else
465 			hi = mid;
466 	}
467 	return lo;
468 }
469 
470 /* Among the lines that appear exactly once in each side, find the longest
471  * streak that appear in both files in the same order (with other stuff allowed
472  * to interleave). Use patience sort for that, as in the Patience Diff
473  * algorithm.
474  * See https://bramcohen.livejournal.com/73318.html and, for a much more
475  * detailed explanation,
476  * https://blog.jcoglan.com/2017/09/19/the-patience-diff-algorithm/ */
477 int
478 diff_algo_patience(const struct diff_algo_config *algo_config,
479 		   struct diff_state *state)
480 {
481 	int rc;
482 	struct diff_data *left = &state->left;
483 	struct diff_data *right = &state->right;
484 	struct atom_patience *atom_patience_left =
485 		calloc(left->atoms.len, sizeof(struct atom_patience));
486 	struct atom_patience *atom_patience_right =
487 		calloc(right->atoms.len, sizeof(struct atom_patience));
488 	unsigned int unique_in_both_count;
489 	struct diff_atom **lcs = NULL;
490 
491 	debug("\n** %s\n", __func__);
492 
493 	left->root->current = left;
494 	right->root->current = right;
495 	left->algo_data = atom_patience_left;
496 	right->algo_data = atom_patience_right;
497 
498 	/* Find those lines that appear exactly once in 'left' and exactly once
499 	 * in 'right'. */
500 	rc = diff_atoms_mark_unique_in_both(left, right, &unique_in_both_count);
501 	if (rc)
502 		goto free_and_exit;
503 
504 	debug("unique_in_both_count %u\n", unique_in_both_count);
505 	debug("left:\n");
506 	debug_dump(left);
507 	debug("right:\n");
508 	debug_dump(right);
509 
510 	if (!unique_in_both_count) {
511 		/* Cannot apply Patience, tell the caller to use fallback_algo
512 		 * instead. */
513 		rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK;
514 		goto free_and_exit;
515 	}
516 
517 	rc = diff_atoms_swallow_identical_neighbors(left, right,
518 						    &unique_in_both_count);
519 	if (rc)
520 		goto free_and_exit;
521 	debug("After swallowing identical neighbors: unique_in_both = %u\n",
522 	      unique_in_both_count);
523 
524 	rc = ENOMEM;
525 
526 	/* An array of Longest Common Sequence is the result of the below
527 	 * subscope: */
528 	unsigned int lcs_count = 0;
529 	struct diff_atom *lcs_tail = NULL;
530 
531 	{
532 		/* This subscope marks the lifetime of the atom_pointers
533 		 * allocation */
534 
535 		/* One chunk of storage for atom pointers */
536 		struct diff_atom **atom_pointers;
537 		atom_pointers = recallocarray(NULL, 0, unique_in_both_count * 2,
538 					      sizeof(struct diff_atom*));
539 		if (atom_pointers == NULL)
540 			return ENOMEM;
541 		/* Half for the list of atoms that still need to be put on
542 		 * stacks */
543 		struct diff_atom **uniques = atom_pointers;
544 
545 		/* Half for the patience sort state's "card stacks" -- we
546 		 * remember only each stack's topmost "card" */
547 		struct diff_atom **patience_stacks;
548 		patience_stacks = atom_pointers + unique_in_both_count;
549 		unsigned int patience_stacks_count = 0;
550 
551 		/* Take all common, unique items from 'left' ... */
552 
553 		struct diff_atom *atom;
554 		struct diff_atom **uniques_end = uniques;
555 		diff_data_foreach_atom(atom, left) {
556 			if (!PATIENCE(atom).unique_in_both)
557 				continue;
558 			*uniques_end = atom;
559 			uniques_end++;
560 		}
561 
562 		/* ...and sort them to the order found in 'right'.
563 		 * The idea is to find the leftmost stack that has a higher line
564 		 * number and add it to the stack's top.
565 		 * If there is no such stack, open a new one on the right. The
566 		 * line number is derived from the atom*, which are array items
567 		 * and hence reflect the relative position in the source file.
568 		 * So we got the common-uniques from 'left' and sort them
569 		 * according to PATIENCE(atom).pos_in_other. */
570 		unsigned int i;
571 		for (i = 0; i < unique_in_both_count; i++) {
572 			atom = uniques[i];
573 			unsigned int target_stack;
574 			target_stack = find_target_stack(atom, patience_stacks,
575 							 patience_stacks_count);
576 			assert(target_stack <= patience_stacks_count);
577 			patience_stacks[target_stack] = atom;
578 			if (target_stack == patience_stacks_count)
579 				patience_stacks_count++;
580 
581 			/* Record a back reference to the next stack on the
582 			 * left, which will form the final longest sequence
583 			 * later. */
584 			PATIENCE(atom).prev_stack = target_stack ?
585 				patience_stacks[target_stack - 1] : NULL;
586 
587 			{
588 				int xx;
589 				for (xx = 0; xx < patience_stacks_count; xx++) {
590 					debug(" %s%d",
591 					      (xx == target_stack) ? ">" : "",
592 					      diff_atom_idx(right,
593 							    PATIENCE(patience_stacks[xx]).pos_in_other));
594 				}
595 				debug("\n");
596 			}
597 		}
598 
599 		/* backtrace through prev_stack references to form the final
600 		 * longest common sequence */
601 		lcs_tail = patience_stacks[patience_stacks_count - 1];
602 		lcs_count = patience_stacks_count;
603 
604 		/* uniques and patience_stacks are no longer needed.
605 		 * Backpointers are in PATIENCE(atom).prev_stack */
606 		free(atom_pointers);
607 	}
608 
609 	lcs = recallocarray(NULL, 0, lcs_count, sizeof(struct diff_atom*));
610 	struct diff_atom **lcs_backtrace_pos = &lcs[lcs_count - 1];
611 	struct diff_atom *atom;
612 	for (atom = lcs_tail; atom; atom = PATIENCE(atom).prev_stack, lcs_backtrace_pos--) {
613 		assert(lcs_backtrace_pos >= lcs);
614 		*lcs_backtrace_pos = atom;
615 	}
616 
617 	unsigned int i;
618 	if (DEBUG) {
619 		debug("\npatience LCS:\n");
620 		for (i = 0; i < lcs_count; i++) {
621 			debug("\n L "); debug_dump_atom(left, right, lcs[i]);
622 			debug(" R "); debug_dump_atom(right, left,
623 						      PATIENCE(lcs[i]).pos_in_other);
624 		}
625 	}
626 
627 
628 	/* TODO: For each common-unique line found (now listed in lcs), swallow
629 	 * lines upwards and downwards that are identical on each side. Requires
630 	 * a way to represent atoms being glued to adjacent atoms. */
631 
632 	debug("\ntraverse LCS, possibly recursing:\n");
633 
634 	/* Now we have pinned positions in both files at which it makes sense to
635 	 * divide the diff problem into smaller chunks. Go into the next round:
636 	 * look at each section in turn, trying to again find common-unique
637 	 * lines in those smaller sections. As soon as no more are found, the
638 	 * remaining smaller sections are solved by Myers. */
639 	/* left_pos and right_pos are indexes in left/right->atoms.head until
640 	 * which the atoms are already handled (added to result chunks). */
641 	unsigned int left_pos = 0;
642 	unsigned int right_pos = 0;
643 	for (i = 0; i <= lcs_count; i++) {
644 		struct diff_atom *atom;
645 		struct diff_atom *atom_r;
646 		/* left_idx and right_idx are indexes of the start of this
647 		 * section of identical lines on both sides.
648 		 * left_pos marks the index of the first still unhandled line,
649 		 * left_idx is the start of an identical section some way
650 		 * further down, and this loop adds an unsolved chunk of
651 		 * [left_pos..left_idx[ and a solved chunk of
652 		 * [left_idx..identical_lines.end[. */
653 		unsigned int left_idx;
654 		unsigned int right_idx;
655 		int already_done_count = 0;
656 
657 		debug("iteration %u of %u  left_pos %u  right_pos %u\n",
658 		      i, lcs_count, left_pos, right_pos);
659 
660 		if (i < lcs_count) {
661 			atom = lcs[i];
662 			atom_r = PATIENCE(atom).pos_in_other;
663 			debug("lcs[%u] = left[%u] = right[%u]\n", i,
664 			      diff_atom_idx(left, atom), diff_atom_idx(right, atom_r));
665 			left_idx = PATIENCE(atom).identical_lines.start;
666 			right_idx = PATIENCE(atom_r).identical_lines.start;
667 			debug(" identical lines l %u-%u  r %u-%u\n",
668 			      PATIENCE(atom).identical_lines.start, PATIENCE(atom).identical_lines.end,
669 			      PATIENCE(atom_r).identical_lines.start, PATIENCE(atom_r).identical_lines.end);
670 		} else {
671 			/* There are no more identical lines until the end of
672 			 * left and right. */
673 			atom = NULL;
674 			atom_r = NULL;
675 			left_idx = left->atoms.len;
676 			right_idx = right->atoms.len;
677 		}
678 
679 		if (right_idx < right_pos) {
680 			/* This may happen if common-unique lines were in a
681 			 * different order on the right, and then ended up
682 			 * consuming the same identical atoms around a pair of
683 			 * common-unique atoms more than once.
684 			 * See also marker the other place marked with (1). */
685 			already_done_count = right_pos - right_idx;
686 			left_idx += already_done_count;
687 			right_idx += already_done_count;
688 			/* Paranoia: make sure we're skipping just an
689 			 * additionally joined identical line around it, and not
690 			 * the common-unique line itself. */
691 			assert(left_idx <= diff_atom_idx(left, atom));
692 		}
693 
694 		/* 'atom' (if not NULL) now marks an atom that matches on both
695 		 * sides according to patience-diff (a common-unique identical
696 		 * atom in both files).
697 		 * Handle the section before and the atom itself; the section
698 		 * after will be handled by the next loop iteration -- note that
699 		 * i loops to last element + 1 ("i <= lcs_count"), so that there
700 		 * will be another final iteration to pick up the last remaining
701 		 * items after the last LCS atom.
702 		 */
703 
704 		debug("iteration %u  left_pos %u  left_idx %u"
705 		      "  right_pos %u  right_idx %u\n",
706 		      i, left_pos, left_idx, right_pos, right_idx);
707 
708 		/* Section before the matching atom */
709 		struct diff_atom *left_atom = &left->atoms.head[left_pos];
710 		unsigned int left_section_len = left_idx - left_pos;
711 
712 		struct diff_atom *right_atom = &(right->atoms.head[right_pos]);
713 		unsigned int right_section_len = right_idx - right_pos;
714 
715 		if (left_section_len && right_section_len) {
716 			/* Record an unsolved chunk, the caller will apply
717 			 * inner_algo() on this chunk. */
718 			if (!diff_state_add_chunk(state, false,
719 						  left_atom, left_section_len,
720 						  right_atom,
721 						  right_section_len))
722 				goto free_and_exit;
723 		} else if (left_section_len && !right_section_len) {
724 			/* Only left atoms and none on the right, they form a
725 			 * "minus" chunk, then. */
726 			if (!diff_state_add_chunk(state, true,
727 						  left_atom, left_section_len,
728 						  right_atom, 0))
729 				goto free_and_exit;
730 		} else if (!left_section_len && right_section_len) {
731 			/* No left atoms, only atoms on the right, they form a
732 			 * "plus" chunk, then. */
733 			if (!diff_state_add_chunk(state, true,
734 						  left_atom, 0,
735 						  right_atom, right_section_len))
736 				goto free_and_exit;
737 		}
738 		/* else: left_section_len == 0 and right_section_len == 0, i.e.
739 		 * nothing here. */
740 
741 		/* The atom found to match on both sides forms a chunk of equals
742 		 * on each side. In the very last iteration of this loop, there
743 		 * is no matching atom, we were just cleaning out the remaining
744 		 * lines. */
745 		if (atom) {
746 			void *ok;
747 			unsigned int left_start = PATIENCE(atom).identical_lines.start;
748 			unsigned int left_len = diff_range_len(&PATIENCE(atom).identical_lines);
749 			unsigned int right_start = PATIENCE(atom_r).identical_lines.start;
750 			unsigned int right_len = diff_range_len(&PATIENCE(atom_r).identical_lines);
751 
752 			left_start += already_done_count;
753 			left_len -= already_done_count;
754 			right_start += already_done_count;
755 			right_len -= already_done_count;
756 
757 			ok = diff_state_add_chunk(state, true,
758 				left->atoms.head + left_start, left_len,
759 				right->atoms.head + right_start, right_len);
760 			if (!ok)
761 				goto free_and_exit;
762 			left_pos = PATIENCE(atom).identical_lines.end;
763 			right_pos = PATIENCE(atom_r).identical_lines.end;
764 		} else {
765 			left_pos = left_idx + 1;
766 			right_pos = right_idx + 1;
767 		}
768 		debug("end of iteration %u  left_pos %u  left_idx %u"
769 		      "  right_pos %u  right_idx %u\n",
770 		      i, left_pos, left_idx, right_pos, right_idx);
771 	}
772 	debug("** END %s\n", __func__);
773 
774 	rc = DIFF_RC_OK;
775 
776 free_and_exit:
777 	left->root->current = NULL;
778 	right->root->current = NULL;
779 	free(atom_patience_left);
780 	free(atom_patience_right);
781 	if (lcs)
782 		free(lcs);
783 	return rc;
784 }