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