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