Blame


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 ca6fcbdc 2020-10-20 neels 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 3b0f3d61 2020-01-22 neels
352 44cf4950 2020-09-20 neels static int
353 0d27172a 2020-05-06 neels diff_atoms_swallow_identical_neighbors(struct diff_data *left,
354 0d27172a 2020-05-06 neels struct diff_data *right,
355 61a7b578 2020-05-06 neels unsigned int *unique_in_both_count)
356 bb7fb738 2020-01-27 neels {
357 0d27172a 2020-05-06 neels debug("trivially combine identical lines"
358 0d27172a 2020-05-06 neels " around unique_in_both lines\n");
359 3b0f3d61 2020-01-22 neels
360 bb7fb738 2020-01-27 neels unsigned int l_idx;
361 bb7fb738 2020-01-27 neels unsigned int next_l_idx;
362 ae2763e9 2020-10-24 neels /* Only checking against identical-line overlaps on the left; overlaps
363 ae2763e9 2020-10-24 neels * on the right are tolerated and ironed out later. See also the other
364 ae2763e9 2020-10-24 neels * place marked with (1). */
365 bb7fb738 2020-01-27 neels unsigned int l_min = 0;
366 bb7fb738 2020-01-27 neels for (l_idx = 0; l_idx < left->atoms.len; l_idx = next_l_idx) {
367 bb7fb738 2020-01-27 neels next_l_idx = l_idx + 1;
368 bb7fb738 2020-01-27 neels struct diff_atom *l = &left->atoms.head[l_idx];
369 9f9e0ab4 2020-10-24 neels struct diff_atom *r;
370 bb7fb738 2020-01-27 neels
371 6c8c5d3f 2020-10-12 neels if (!PATIENCE(l).unique_in_both)
372 bb7fb738 2020-01-27 neels continue;
373 bb7fb738 2020-01-27 neels
374 10ae3a65 2020-10-24 neels debug("check identical lines around\n");
375 10ae3a65 2020-10-24 neels debug(" L "); debug_dump_atom(left, right, l);
376 bb7fb738 2020-01-27 neels
377 6c8c5d3f 2020-10-12 neels unsigned int r_idx = diff_atom_idx(right, PATIENCE(l).pos_in_other);
378 9f9e0ab4 2020-10-24 neels r = &right->atoms.head[r_idx];
379 10ae3a65 2020-10-24 neels debug(" R "); debug_dump_atom(right, left, r);
380 bb7fb738 2020-01-27 neels
381 d362ea2e 2020-07-25 stsp struct diff_range identical_l;
382 d362ea2e 2020-07-25 stsp struct diff_range identical_r;
383 bb7fb738 2020-01-27 neels
384 bb7fb738 2020-01-27 neels /* Swallow upwards.
385 0d27172a 2020-05-06 neels * Each common-unique line swallows identical lines upwards and
386 0d27172a 2020-05-06 neels * downwards.
387 a5de2633 2020-10-24 neels * Will never hit another identical common-unique line above on
388 a5de2633 2020-10-24 neels * the left, because those would already have swallowed this
389 a5de2633 2020-10-24 neels * common-unique line in a previous iteration.
390 a5de2633 2020-10-24 neels */
391 bb7fb738 2020-01-27 neels for (identical_l.start = l_idx, identical_r.start = r_idx;
392 67157248 2020-11-06 neels identical_l.start > (l_min+1) && identical_r.start > 0;
393 b3fb4686 2020-09-20 neels identical_l.start--, identical_r.start--) {
394 b3fb4686 2020-09-20 neels bool same;
395 ca1af245 2020-10-24 neels int rc = diff_atom_same(&same,
396 0d27172a 2020-05-06 neels &left->atoms.head[identical_l.start - 1],
397 0d27172a 2020-05-06 neels &right->atoms.head[identical_r.start - 1]);
398 ca1af245 2020-10-24 neels if (rc)
399 ca1af245 2020-10-24 neels return rc;
400 b3fb4686 2020-09-20 neels if (!same)
401 b3fb4686 2020-09-20 neels break;
402 b3fb4686 2020-09-20 neels }
403 bb7fb738 2020-01-27 neels
404 a5de2633 2020-10-24 neels /* Swallow downwards. Join any common-unique lines in a block of
405 a5de2633 2020-10-24 neels * matching L/R lines with this one. */
406 bb7fb738 2020-01-27 neels for (identical_l.end = l_idx + 1, identical_r.end = r_idx + 1;
407 bb7fb738 2020-01-27 neels identical_l.end < left->atoms.len
408 b3fb4686 2020-09-20 neels && identical_r.end < right->atoms.len;
409 bb7fb738 2020-01-27 neels identical_l.end++, identical_r.end++,
410 bb7fb738 2020-01-27 neels next_l_idx++) {
411 0d27172a 2020-05-06 neels struct diff_atom *l_end;
412 0d27172a 2020-05-06 neels struct diff_atom *r_end;
413 b3fb4686 2020-09-20 neels bool same;
414 ca1af245 2020-10-24 neels int rc = diff_atom_same(&same,
415 b3fb4686 2020-09-20 neels &left->atoms.head[identical_l.end],
416 b3fb4686 2020-09-20 neels &right->atoms.head[identical_r.end]);
417 ca1af245 2020-10-24 neels if (rc)
418 ca1af245 2020-10-24 neels return rc;
419 b3fb4686 2020-09-20 neels if (!same)
420 b3fb4686 2020-09-20 neels break;
421 0d27172a 2020-05-06 neels l_end = &left->atoms.head[identical_l.end];
422 ab699b5c 2020-05-12 stsp r_end = &right->atoms.head[identical_r.end];
423 6c8c5d3f 2020-10-12 neels if (!PATIENCE(l_end).unique_in_both)
424 0d27172a 2020-05-06 neels continue;
425 a5de2633 2020-10-24 neels /* A unique_in_both atom is joined with a preceding
426 a5de2633 2020-10-24 neels * unique_in_both atom, remove the joined atom from
427 a5de2633 2020-10-24 neels * listing of unique_in_both atoms */
428 6c8c5d3f 2020-10-12 neels PATIENCE(l_end).unique_in_both = false;
429 6c8c5d3f 2020-10-12 neels PATIENCE(r_end).unique_in_both = false;
430 0d27172a 2020-05-06 neels (*unique_in_both_count)--;
431 bb7fb738 2020-01-27 neels }
432 bb7fb738 2020-01-27 neels
433 6c8c5d3f 2020-10-12 neels PATIENCE(l).identical_lines = identical_l;
434 9f9e0ab4 2020-10-24 neels PATIENCE(r).identical_lines = identical_r;
435 bb7fb738 2020-01-27 neels
436 bb7fb738 2020-01-27 neels l_min = identical_l.end;
437 bb7fb738 2020-01-27 neels
438 6c8c5d3f 2020-10-12 neels if (!diff_range_empty(&PATIENCE(l).identical_lines)) {
439 0d27172a 2020-05-06 neels debug("common-unique line at l=%u r=%u swallowed"
440 0d27172a 2020-05-06 neels " identical lines l=%u-%u r=%u-%u\n",
441 bb7fb738 2020-01-27 neels l_idx, r_idx,
442 bb7fb738 2020-01-27 neels identical_l.start, identical_l.end,
443 bb7fb738 2020-01-27 neels identical_r.start, identical_r.end);
444 bb7fb738 2020-01-27 neels }
445 bb7fb738 2020-01-27 neels debug("next_l_idx = %u\n", next_l_idx);
446 bb7fb738 2020-01-27 neels }
447 44cf4950 2020-09-20 neels return 0;
448 bb7fb738 2020-01-27 neels }
449 bb7fb738 2020-01-27 neels
450 0d27172a 2020-05-06 neels /* binary search to find the stack to put this atom "card" on. */
451 0d27172a 2020-05-06 neels static int
452 0d27172a 2020-05-06 neels find_target_stack(struct diff_atom *atom,
453 0d27172a 2020-05-06 neels struct diff_atom **patience_stacks,
454 0d27172a 2020-05-06 neels unsigned int patience_stacks_count)
455 0d27172a 2020-05-06 neels {
456 0d27172a 2020-05-06 neels unsigned int lo = 0;
457 0d27172a 2020-05-06 neels unsigned int hi = patience_stacks_count;
458 0d27172a 2020-05-06 neels while (lo < hi) {
459 0d27172a 2020-05-06 neels unsigned int mid = (lo + hi) >> 1;
460 0d27172a 2020-05-06 neels
461 6c8c5d3f 2020-10-12 neels if (PATIENCE(patience_stacks[mid]).pos_in_other
462 6c8c5d3f 2020-10-12 neels < PATIENCE(atom).pos_in_other)
463 0d27172a 2020-05-06 neels lo = mid + 1;
464 0d27172a 2020-05-06 neels else
465 0d27172a 2020-05-06 neels hi = mid;
466 0d27172a 2020-05-06 neels }
467 0d27172a 2020-05-06 neels return lo;
468 0d27172a 2020-05-06 neels }
469 0d27172a 2020-05-06 neels
470 0d27172a 2020-05-06 neels /* Among the lines that appear exactly once in each side, find the longest
471 0d27172a 2020-05-06 neels * streak that appear in both files in the same order (with other stuff allowed
472 0d27172a 2020-05-06 neels * to interleave). Use patience sort for that, as in the Patience Diff
473 0d27172a 2020-05-06 neels * algorithm.
474 0d27172a 2020-05-06 neels * See https://bramcohen.livejournal.com/73318.html and, for a much more
475 0d27172a 2020-05-06 neels * detailed explanation,
476 3b0f3d61 2020-01-22 neels * https://blog.jcoglan.com/2017/09/19/the-patience-diff-algorithm/ */
477 3e6cba3a 2020-08-13 stsp int
478 0d27172a 2020-05-06 neels diff_algo_patience(const struct diff_algo_config *algo_config,
479 0d27172a 2020-05-06 neels struct diff_state *state)
480 3b0f3d61 2020-01-22 neels {
481 44cf4950 2020-09-20 neels int rc;
482 3b0f3d61 2020-01-22 neels struct diff_data *left = &state->left;
483 3b0f3d61 2020-01-22 neels struct diff_data *right = &state->right;
484 6c8c5d3f 2020-10-12 neels struct atom_patience *atom_patience_left =
485 6c8c5d3f 2020-10-12 neels calloc(left->atoms.len, sizeof(struct atom_patience));
486 6c8c5d3f 2020-10-12 neels struct atom_patience *atom_patience_right =
487 6c8c5d3f 2020-10-12 neels calloc(right->atoms.len, sizeof(struct atom_patience));
488 3b0f3d61 2020-01-22 neels unsigned int unique_in_both_count;
489 6c8c5d3f 2020-10-12 neels struct diff_atom **lcs = NULL;
490 3b0f3d61 2020-01-22 neels
491 3b0f3d61 2020-01-22 neels debug("\n** %s\n", __func__);
492 3b0f3d61 2020-01-22 neels
493 6c8c5d3f 2020-10-12 neels left->root->current = left;
494 6c8c5d3f 2020-10-12 neels right->root->current = right;
495 6c8c5d3f 2020-10-12 neels left->algo_data = atom_patience_left;
496 6c8c5d3f 2020-10-12 neels right->algo_data = atom_patience_right;
497 6c8c5d3f 2020-10-12 neels
498 0d27172a 2020-05-06 neels /* Find those lines that appear exactly once in 'left' and exactly once
499 0d27172a 2020-05-06 neels * in 'right'. */
500 12c5bde7 2020-10-16 stsp rc = diff_atoms_mark_unique_in_both(left, right, &unique_in_both_count);
501 44cf4950 2020-09-20 neels if (rc)
502 6c8c5d3f 2020-10-12 neels goto free_and_exit;
503 3b0f3d61 2020-01-22 neels
504 3b0f3d61 2020-01-22 neels debug("unique_in_both_count %u\n", unique_in_both_count);
505 3b0f3d61 2020-01-22 neels debug("left:\n");
506 3b0f3d61 2020-01-22 neels debug_dump(left);
507 3b0f3d61 2020-01-22 neels debug("right:\n");
508 3b0f3d61 2020-01-22 neels debug_dump(right);
509 3b0f3d61 2020-01-22 neels
510 3b0f3d61 2020-01-22 neels if (!unique_in_both_count) {
511 0d27172a 2020-05-06 neels /* Cannot apply Patience, tell the caller to use fallback_algo
512 0d27172a 2020-05-06 neels * instead. */
513 6c8c5d3f 2020-10-12 neels rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK;
514 6c8c5d3f 2020-10-12 neels goto free_and_exit;
515 3b0f3d61 2020-01-22 neels }
516 3b0f3d61 2020-01-22 neels
517 44cf4950 2020-09-20 neels rc = diff_atoms_swallow_identical_neighbors(left, right,
518 44cf4950 2020-09-20 neels &unique_in_both_count);
519 44cf4950 2020-09-20 neels if (rc)
520 6c8c5d3f 2020-10-12 neels goto free_and_exit;
521 bb7fb738 2020-01-27 neels debug("After swallowing identical neighbors: unique_in_both = %u\n",
522 bb7fb738 2020-01-27 neels unique_in_both_count);
523 bb7fb738 2020-01-27 neels
524 44cf4950 2020-09-20 neels rc = ENOMEM;
525 44cf4950 2020-09-20 neels
526 0d27172a 2020-05-06 neels /* An array of Longest Common Sequence is the result of the below
527 0d27172a 2020-05-06 neels * subscope: */
528 3b0f3d61 2020-01-22 neels unsigned int lcs_count = 0;
529 3b0f3d61 2020-01-22 neels struct diff_atom *lcs_tail = NULL;
530 3b0f3d61 2020-01-22 neels
531 3b0f3d61 2020-01-22 neels {
532 0d27172a 2020-05-06 neels /* This subscope marks the lifetime of the atom_pointers
533 0d27172a 2020-05-06 neels * allocation */
534 3b0f3d61 2020-01-22 neels
535 3b0f3d61 2020-01-22 neels /* One chunk of storage for atom pointers */
536 0d27172a 2020-05-06 neels struct diff_atom **atom_pointers;
537 0d27172a 2020-05-06 neels atom_pointers = recallocarray(NULL, 0, unique_in_both_count * 2,
538 0d27172a 2020-05-06 neels sizeof(struct diff_atom*));
539 b229234e 2020-10-17 stsp if (atom_pointers == NULL)
540 b229234e 2020-10-17 stsp return ENOMEM;
541 0d27172a 2020-05-06 neels /* Half for the list of atoms that still need to be put on
542 0d27172a 2020-05-06 neels * stacks */
543 3b0f3d61 2020-01-22 neels struct diff_atom **uniques = atom_pointers;
544 3b0f3d61 2020-01-22 neels
545 0d27172a 2020-05-06 neels /* Half for the patience sort state's "card stacks" -- we
546 0d27172a 2020-05-06 neels * remember only each stack's topmost "card" */
547 0d27172a 2020-05-06 neels struct diff_atom **patience_stacks;
548 0d27172a 2020-05-06 neels patience_stacks = atom_pointers + unique_in_both_count;
549 3b0f3d61 2020-01-22 neels unsigned int patience_stacks_count = 0;
550 3b0f3d61 2020-01-22 neels
551 3b0f3d61 2020-01-22 neels /* Take all common, unique items from 'left' ... */
552 3b0f3d61 2020-01-22 neels
553 3b0f3d61 2020-01-22 neels struct diff_atom *atom;
554 3b0f3d61 2020-01-22 neels struct diff_atom **uniques_end = uniques;
555 3b0f3d61 2020-01-22 neels diff_data_foreach_atom(atom, left) {
556 6c8c5d3f 2020-10-12 neels if (!PATIENCE(atom).unique_in_both)
557 3b0f3d61 2020-01-22 neels continue;
558 3b0f3d61 2020-01-22 neels *uniques_end = atom;
559 3b0f3d61 2020-01-22 neels uniques_end++;
560 3b0f3d61 2020-01-22 neels }
561 3b0f3d61 2020-01-22 neels
562 3b0f3d61 2020-01-22 neels /* ...and sort them to the order found in 'right'.
563 0d27172a 2020-05-06 neels * The idea is to find the leftmost stack that has a higher line
564 0d27172a 2020-05-06 neels * number and add it to the stack's top.
565 0d27172a 2020-05-06 neels * If there is no such stack, open a new one on the right. The
566 0d27172a 2020-05-06 neels * line number is derived from the atom*, which are array items
567 0d27172a 2020-05-06 neels * and hence reflect the relative position in the source file.
568 0d27172a 2020-05-06 neels * So we got the common-uniques from 'left' and sort them
569 6c8c5d3f 2020-10-12 neels * according to PATIENCE(atom).pos_in_other. */
570 3b0f3d61 2020-01-22 neels unsigned int i;
571 3b0f3d61 2020-01-22 neels for (i = 0; i < unique_in_both_count; i++) {
572 3b0f3d61 2020-01-22 neels atom = uniques[i];
573 3b0f3d61 2020-01-22 neels unsigned int target_stack;
574 0d27172a 2020-05-06 neels target_stack = find_target_stack(atom, patience_stacks,
575 0d27172a 2020-05-06 neels patience_stacks_count);
576 3b0f3d61 2020-01-22 neels assert(target_stack <= patience_stacks_count);
577 3b0f3d61 2020-01-22 neels patience_stacks[target_stack] = atom;
578 3b0f3d61 2020-01-22 neels if (target_stack == patience_stacks_count)
579 3b0f3d61 2020-01-22 neels patience_stacks_count++;
580 3b0f3d61 2020-01-22 neels
581 0d27172a 2020-05-06 neels /* Record a back reference to the next stack on the
582 0d27172a 2020-05-06 neels * left, which will form the final longest sequence
583 3b0f3d61 2020-01-22 neels * later. */
584 6c8c5d3f 2020-10-12 neels PATIENCE(atom).prev_stack = target_stack ?
585 0d27172a 2020-05-06 neels patience_stacks[target_stack - 1] : NULL;
586 3b0f3d61 2020-01-22 neels
587 10ae3a65 2020-10-24 neels {
588 10ae3a65 2020-10-24 neels int xx;
589 10ae3a65 2020-10-24 neels for (xx = 0; xx < patience_stacks_count; xx++) {
590 10ae3a65 2020-10-24 neels debug(" %s%d",
591 10ae3a65 2020-10-24 neels (xx == target_stack) ? ">" : "",
592 10ae3a65 2020-10-24 neels diff_atom_idx(right,
593 10ae3a65 2020-10-24 neels PATIENCE(patience_stacks[xx]).pos_in_other));
594 10ae3a65 2020-10-24 neels }
595 10ae3a65 2020-10-24 neels debug("\n");
596 10ae3a65 2020-10-24 neels }
597 3b0f3d61 2020-01-22 neels }
598 3b0f3d61 2020-01-22 neels
599 0d27172a 2020-05-06 neels /* backtrace through prev_stack references to form the final
600 0d27172a 2020-05-06 neels * longest common sequence */
601 3b0f3d61 2020-01-22 neels lcs_tail = patience_stacks[patience_stacks_count - 1];
602 3b0f3d61 2020-01-22 neels lcs_count = patience_stacks_count;
603 3b0f3d61 2020-01-22 neels
604 0d27172a 2020-05-06 neels /* uniques and patience_stacks are no longer needed.
605 6c8c5d3f 2020-10-12 neels * Backpointers are in PATIENCE(atom).prev_stack */
606 3b0f3d61 2020-01-22 neels free(atom_pointers);
607 3b0f3d61 2020-01-22 neels }
608 3b0f3d61 2020-01-22 neels
609 3b0f3d61 2020-01-22 neels lcs = recallocarray(NULL, 0, lcs_count, sizeof(struct diff_atom*));
610 3b0f3d61 2020-01-22 neels struct diff_atom **lcs_backtrace_pos = &lcs[lcs_count - 1];
611 3b0f3d61 2020-01-22 neels struct diff_atom *atom;
612 6c8c5d3f 2020-10-12 neels for (atom = lcs_tail; atom; atom = PATIENCE(atom).prev_stack, lcs_backtrace_pos--) {
613 3b0f3d61 2020-01-22 neels assert(lcs_backtrace_pos >= lcs);
614 3b0f3d61 2020-01-22 neels *lcs_backtrace_pos = atom;
615 3b0f3d61 2020-01-22 neels }
616 3b0f3d61 2020-01-22 neels
617 3b0f3d61 2020-01-22 neels unsigned int i;
618 3b0f3d61 2020-01-22 neels if (DEBUG) {
619 3b0f3d61 2020-01-22 neels debug("\npatience LCS:\n");
620 3b0f3d61 2020-01-22 neels for (i = 0; i < lcs_count; i++) {
621 10ae3a65 2020-10-24 neels debug("\n L "); debug_dump_atom(left, right, lcs[i]);
622 10ae3a65 2020-10-24 neels debug(" R "); debug_dump_atom(right, left,
623 10ae3a65 2020-10-24 neels PATIENCE(lcs[i]).pos_in_other);
624 3b0f3d61 2020-01-22 neels }
625 3b0f3d61 2020-01-22 neels }
626 3b0f3d61 2020-01-22 neels
627 3b0f3d61 2020-01-22 neels
628 0d27172a 2020-05-06 neels /* TODO: For each common-unique line found (now listed in lcs), swallow
629 0d27172a 2020-05-06 neels * lines upwards and downwards that are identical on each side. Requires
630 0d27172a 2020-05-06 neels * a way to represent atoms being glued to adjacent atoms. */
631 3b0f3d61 2020-01-22 neels
632 3b0f3d61 2020-01-22 neels debug("\ntraverse LCS, possibly recursing:\n");
633 3b0f3d61 2020-01-22 neels
634 0d27172a 2020-05-06 neels /* Now we have pinned positions in both files at which it makes sense to
635 0d27172a 2020-05-06 neels * divide the diff problem into smaller chunks. Go into the next round:
636 0d27172a 2020-05-06 neels * look at each section in turn, trying to again find common-unique
637 0d27172a 2020-05-06 neels * lines in those smaller sections. As soon as no more are found, the
638 0d27172a 2020-05-06 neels * remaining smaller sections are solved by Myers. */
639 a5de2633 2020-10-24 neels /* left_pos and right_pos are indexes in left/right->atoms.head until
640 a5de2633 2020-10-24 neels * which the atoms are already handled (added to result chunks). */
641 3b0f3d61 2020-01-22 neels unsigned int left_pos = 0;
642 3b0f3d61 2020-01-22 neels unsigned int right_pos = 0;
643 3b0f3d61 2020-01-22 neels for (i = 0; i <= lcs_count; i++) {
644 3b0f3d61 2020-01-22 neels struct diff_atom *atom;
645 bb7fb738 2020-01-27 neels struct diff_atom *atom_r;
646 a5de2633 2020-10-24 neels /* left_idx and right_idx are indexes of the start of this
647 a5de2633 2020-10-24 neels * section of identical lines on both sides.
648 a5de2633 2020-10-24 neels * left_pos marks the index of the first still unhandled line,
649 a5de2633 2020-10-24 neels * left_idx is the start of an identical section some way
650 a5de2633 2020-10-24 neels * further down, and this loop adds an unsolved chunk of
651 a5de2633 2020-10-24 neels * [left_pos..left_idx[ and a solved chunk of
652 a5de2633 2020-10-24 neels * [left_idx..identical_lines.end[. */
653 3b0f3d61 2020-01-22 neels unsigned int left_idx;
654 3b0f3d61 2020-01-22 neels unsigned int right_idx;
655 ab378e1f 2020-11-07 stsp int already_done_count = 0;
656 3b0f3d61 2020-01-22 neels
657 10ae3a65 2020-10-24 neels debug("iteration %u of %u left_pos %u right_pos %u\n",
658 10ae3a65 2020-10-24 neels i, lcs_count, left_pos, right_pos);
659 10ae3a65 2020-10-24 neels
660 3b0f3d61 2020-01-22 neels if (i < lcs_count) {
661 3b0f3d61 2020-01-22 neels atom = lcs[i];
662 6c8c5d3f 2020-10-12 neels atom_r = PATIENCE(atom).pos_in_other;
663 2a1b94d0 2020-09-26 stsp debug("lcs[%u] = left[%u] = right[%u]\n", i,
664 bb7fb738 2020-01-27 neels diff_atom_idx(left, atom), diff_atom_idx(right, atom_r));
665 6c8c5d3f 2020-10-12 neels left_idx = PATIENCE(atom).identical_lines.start;
666 6c8c5d3f 2020-10-12 neels right_idx = PATIENCE(atom_r).identical_lines.start;
667 bb7fb738 2020-01-27 neels debug(" identical lines l %u-%u r %u-%u\n",
668 6c8c5d3f 2020-10-12 neels PATIENCE(atom).identical_lines.start, PATIENCE(atom).identical_lines.end,
669 6c8c5d3f 2020-10-12 neels PATIENCE(atom_r).identical_lines.start, PATIENCE(atom_r).identical_lines.end);
670 3b0f3d61 2020-01-22 neels } else {
671 a5de2633 2020-10-24 neels /* There are no more identical lines until the end of
672 a5de2633 2020-10-24 neels * left and right. */
673 3b0f3d61 2020-01-22 neels atom = NULL;
674 bb7fb738 2020-01-27 neels atom_r = NULL;
675 3b0f3d61 2020-01-22 neels left_idx = left->atoms.len;
676 3b0f3d61 2020-01-22 neels right_idx = right->atoms.len;
677 ae2763e9 2020-10-24 neels }
678 ae2763e9 2020-10-24 neels
679 ae2763e9 2020-10-24 neels if (right_idx < right_pos) {
680 ae2763e9 2020-10-24 neels /* This may happen if common-unique lines were in a
681 ae2763e9 2020-10-24 neels * different order on the right, and then ended up
682 ae2763e9 2020-10-24 neels * consuming the same identical atoms around a pair of
683 ae2763e9 2020-10-24 neels * common-unique atoms more than once.
684 ae2763e9 2020-10-24 neels * See also marker the other place marked with (1). */
685 ab378e1f 2020-11-07 stsp already_done_count = right_pos - right_idx;
686 ae2763e9 2020-10-24 neels left_idx += already_done_count;
687 ae2763e9 2020-10-24 neels right_idx += already_done_count;
688 ae2763e9 2020-10-24 neels /* Paranoia: make sure we're skipping just an
689 ae2763e9 2020-10-24 neels * additionally joined identical line around it, and not
690 ae2763e9 2020-10-24 neels * the common-unique line itself. */
691 ae2763e9 2020-10-24 neels assert(left_idx <= diff_atom_idx(left, atom));
692 3b0f3d61 2020-01-22 neels }
693 3b0f3d61 2020-01-22 neels
694 a5de2633 2020-10-24 neels /* 'atom' (if not NULL) now marks an atom that matches on both
695 a5de2633 2020-10-24 neels * sides according to patience-diff (a common-unique identical
696 a5de2633 2020-10-24 neels * atom in both files).
697 0d27172a 2020-05-06 neels * Handle the section before and the atom itself; the section
698 0d27172a 2020-05-06 neels * after will be handled by the next loop iteration -- note that
699 0d27172a 2020-05-06 neels * i loops to last element + 1 ("i <= lcs_count"), so that there
700 0d27172a 2020-05-06 neels * will be another final iteration to pick up the last remaining
701 0d27172a 2020-05-06 neels * items after the last LCS atom.
702 a5de2633 2020-10-24 neels */
703 3b0f3d61 2020-01-22 neels
704 0d27172a 2020-05-06 neels debug("iteration %u left_pos %u left_idx %u"
705 0d27172a 2020-05-06 neels " right_pos %u right_idx %u\n",
706 3b0f3d61 2020-01-22 neels i, left_pos, left_idx, right_pos, right_idx);
707 3b0f3d61 2020-01-22 neels
708 3b0f3d61 2020-01-22 neels /* Section before the matching atom */
709 3b0f3d61 2020-01-22 neels struct diff_atom *left_atom = &left->atoms.head[left_pos];
710 3b0f3d61 2020-01-22 neels unsigned int left_section_len = left_idx - left_pos;
711 3b0f3d61 2020-01-22 neels
712 3b0f3d61 2020-01-22 neels struct diff_atom *right_atom = &(right->atoms.head[right_pos]);
713 3b0f3d61 2020-01-22 neels unsigned int right_section_len = right_idx - right_pos;
714 3b0f3d61 2020-01-22 neels
715 3b0f3d61 2020-01-22 neels if (left_section_len && right_section_len) {
716 0d27172a 2020-05-06 neels /* Record an unsolved chunk, the caller will apply
717 0d27172a 2020-05-06 neels * inner_algo() on this chunk. */
718 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, false,
719 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
720 0d27172a 2020-05-06 neels right_atom,
721 0d27172a 2020-05-06 neels right_section_len))
722 6c8c5d3f 2020-10-12 neels goto free_and_exit;
723 3b0f3d61 2020-01-22 neels } else if (left_section_len && !right_section_len) {
724 0d27172a 2020-05-06 neels /* Only left atoms and none on the right, they form a
725 0d27172a 2020-05-06 neels * "minus" chunk, then. */
726 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
727 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
728 3b0f3d61 2020-01-22 neels right_atom, 0))
729 6c8c5d3f 2020-10-12 neels goto free_and_exit;
730 3b0f3d61 2020-01-22 neels } else if (!left_section_len && right_section_len) {
731 0d27172a 2020-05-06 neels /* No left atoms, only atoms on the right, they form a
732 0d27172a 2020-05-06 neels * "plus" chunk, then. */
733 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
734 3b0f3d61 2020-01-22 neels left_atom, 0,
735 3b0f3d61 2020-01-22 neels right_atom, right_section_len))
736 6c8c5d3f 2020-10-12 neels goto free_and_exit;
737 3b0f3d61 2020-01-22 neels }
738 0d27172a 2020-05-06 neels /* else: left_section_len == 0 and right_section_len == 0, i.e.
739 0d27172a 2020-05-06 neels * nothing here. */
740 3b0f3d61 2020-01-22 neels
741 0d27172a 2020-05-06 neels /* The atom found to match on both sides forms a chunk of equals
742 0d27172a 2020-05-06 neels * on each side. In the very last iteration of this loop, there
743 0d27172a 2020-05-06 neels * is no matching atom, we were just cleaning out the remaining
744 0d27172a 2020-05-06 neels * lines. */
745 3b0f3d61 2020-01-22 neels if (atom) {
746 0d27172a 2020-05-06 neels void *ok;
747 ab378e1f 2020-11-07 stsp unsigned int left_start = PATIENCE(atom).identical_lines.start;
748 ab378e1f 2020-11-07 stsp unsigned int left_len = diff_range_len(&PATIENCE(atom).identical_lines);
749 ab378e1f 2020-11-07 stsp unsigned int right_start = PATIENCE(atom_r).identical_lines.start;
750 ab378e1f 2020-11-07 stsp unsigned int right_len = diff_range_len(&PATIENCE(atom_r).identical_lines);
751 ab378e1f 2020-11-07 stsp
752 ab378e1f 2020-11-07 stsp left_start += already_done_count;
753 ab378e1f 2020-11-07 stsp left_len -= already_done_count;
754 ab378e1f 2020-11-07 stsp right_start += already_done_count;
755 ab378e1f 2020-11-07 stsp right_len -= already_done_count;
756 ab378e1f 2020-11-07 stsp
757 0d27172a 2020-05-06 neels ok = diff_state_add_chunk(state, true,
758 ab378e1f 2020-11-07 stsp left->atoms.head + left_start, left_len,
759 ab378e1f 2020-11-07 stsp right->atoms.head + right_start, right_len);
760 0d27172a 2020-05-06 neels if (!ok)
761 6c8c5d3f 2020-10-12 neels goto free_and_exit;
762 6c8c5d3f 2020-10-12 neels left_pos = PATIENCE(atom).identical_lines.end;
763 6c8c5d3f 2020-10-12 neels right_pos = PATIENCE(atom_r).identical_lines.end;
764 bb7fb738 2020-01-27 neels } else {
765 bb7fb738 2020-01-27 neels left_pos = left_idx + 1;
766 bb7fb738 2020-01-27 neels right_pos = right_idx + 1;
767 3b0f3d61 2020-01-22 neels }
768 0d27172a 2020-05-06 neels debug("end of iteration %u left_pos %u left_idx %u"
769 0d27172a 2020-05-06 neels " right_pos %u right_idx %u\n",
770 bb7fb738 2020-01-27 neels i, left_pos, left_idx, right_pos, right_idx);
771 3b0f3d61 2020-01-22 neels }
772 3b0f3d61 2020-01-22 neels debug("** END %s\n", __func__);
773 3b0f3d61 2020-01-22 neels
774 3b0f3d61 2020-01-22 neels rc = DIFF_RC_OK;
775 3b0f3d61 2020-01-22 neels
776 6c8c5d3f 2020-10-12 neels free_and_exit:
777 6c8c5d3f 2020-10-12 neels left->root->current = NULL;
778 6c8c5d3f 2020-10-12 neels right->root->current = NULL;
779 6c8c5d3f 2020-10-12 neels free(atom_patience_left);
780 6c8c5d3f 2020-10-12 neels free(atom_patience_right);
781 6c8c5d3f 2020-10-12 neels if (lcs)
782 6c8c5d3f 2020-10-12 neels free(lcs);
783 3b0f3d61 2020-01-22 neels return rc;
784 3b0f3d61 2020-01-22 neels }