1 /* Implementation of the Patience Diff algorithm invented by Bram Cohen:
2 * Divide a diff problem into smaller chunks by an LCS of common-unique lines. */
4 * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
6 * Permission to use, copy, modify, and distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
26 #include <arraylist.h>
27 #include <diff_main.h>
29 #include "diff_internal.h"
30 #include "diff_debug.h"
32 /* Per-atom state for the Patience Diff algorithm */
33 struct atom_patience {
35 struct diff_atom *pos_in_other;
36 struct diff_atom *prev_stack;
37 struct diff_range identical_lines;
40 /* A diff_atom has a backpointer to the root diff_data. That points to the
41 * current diff_data, a possibly smaller section of the root. That current
42 * diff_data->algo_data is a pointer to an array of struct atom_patience. The
43 * atom's index in current diff_data gives the index in the atom_patience array.
45 #define PATIENCE(ATOM) \
46 (((struct atom_patience*)((ATOM)->root->current->algo_data))\
47 [diff_atom_idx((ATOM)->root->current, ATOM)])
49 int diff_atoms_mergesort_compar(const void *_a, const void *_b)
51 const struct diff_atom *a = *(struct diff_atom**)_a;
52 const struct diff_atom *b = *(struct diff_atom**)_b;
56 /* If there's been an error (e.g. I/O error) in a previous compar, we
57 * have no way to abort the mergesort but just report the rc and stop
58 * comparing. Make sure to catch errors on either side. If atoms are
59 * from more than one diff_data, make sure the error, if any, spreads
60 * to all of them, so we can cut short all future comparisons. */
68 /* just return 'equal' to not swap more positions */
72 /* Sort by the simplistic hash */
73 if (a->hash < b->hash)
75 if (a->hash > b->hash)
78 /* If hashes are the same, the lines may still differ. Do a full cmp. */
79 rc = diff_atom_cmp(&cmp, a, b);
82 /* Mark the I/O error so that the caller can find out about it.
83 * For the case atoms are from more than one diff_data, mark in
86 if (a->root != b->root)
94 /* Sort an array of struct diff_atom* in-place. */
95 static int diff_atoms_sort(struct diff_atom *atoms[],
99 * Use mergesort(3) bcause it provides stable ordering
100 * even if two or more elements are equal.
102 mergesort(atoms, atoms_count, sizeof(struct diff_atom*),
103 diff_atoms_mergesort_compar);
104 return atoms[0]->root->err;
108 diff_atoms_mark_unique_in_both(struct diff_data *left, struct diff_data *right,
109 unsigned int *unique_in_both_count_p)
113 struct diff_atom **all_atoms;
114 unsigned int len = 0;
116 unsigned int unique_in_both_count = 0;
119 all_atoms = calloc(left->atoms.len + right->atoms.len,
120 sizeof(struct diff_atom *));
121 if (all_atoms == NULL)
127 right->root->err = 0;
128 diff_data_foreach_atom(a, left) {
129 all_atoms[len++] = a;
131 diff_data_foreach_atom(b, right) {
132 all_atoms[len++] = b;
135 rc = diff_atoms_sort(all_atoms, len);
139 /* Now we have a sorted array of atom pointers. All similar lines are
140 * adjacent. Walk through the array and mark those that are unique on
141 * each side, but exist once in both sources. */
142 for (i = 0; i < len; i++) {
145 unsigned int count_first_side = 1;
146 unsigned int count_other_side = 0;
149 for (j = i+1; j < len; j++) {
151 rc = diff_atom_same(&same, a, b);
156 /* A following atom is the same. See on which side the
157 * repetition counts. */
158 if (a->root == b->root)
164 /* Counted a section of similar atoms, put the results back to
166 if ((count_first_side == 1)
167 && (count_other_side == 1)) {
169 PATIENCE(a).unique_in_both = true;
170 PATIENCE(a).pos_in_other = b;
171 PATIENCE(b).unique_in_both = true;
172 PATIENCE(b).pos_in_other = a;
173 unique_in_both_count++;
176 *unique_in_both_count_p = unique_in_both_count;
184 diff_atoms_swallow_identical_neighbors(struct diff_data *left,
185 struct diff_data *right,
186 unsigned int *unique_in_both_count)
188 debug("trivially combine identical lines"
189 " around unique_in_both lines\n");
192 unsigned int next_l_idx;
193 unsigned int l_min = 0;
194 unsigned int r_min = 0;
195 for (l_idx = 0; l_idx < left->atoms.len; l_idx = next_l_idx) {
196 next_l_idx = l_idx + 1;
197 struct diff_atom *l = &left->atoms.head[l_idx];
199 if (!PATIENCE(l).unique_in_both)
202 debug("check identical lines around ");
203 debug_dump_atom(left, right, l);
205 unsigned int r_idx = diff_atom_idx(right, PATIENCE(l).pos_in_other);
207 struct diff_range identical_l;
208 struct diff_range identical_r;
211 * Each common-unique line swallows identical lines upwards and
213 * All common-unique lines that were part of the identical lines
214 * following below were already swallowed in the previous
215 * iteration, so we will never hit another common-unique line
217 for (identical_l.start = l_idx, identical_r.start = r_idx;
218 identical_l.start > l_min && identical_r.start > r_min;
219 identical_l.start--, identical_r.start--) {
221 int r = diff_atom_same(&same,
222 &left->atoms.head[identical_l.start - 1],
223 &right->atoms.head[identical_r.start - 1]);
230 /* Swallow downwards */
231 for (identical_l.end = l_idx + 1, identical_r.end = r_idx + 1;
232 identical_l.end < left->atoms.len
233 && identical_r.end < right->atoms.len;
234 identical_l.end++, identical_r.end++,
236 struct diff_atom *l_end;
237 struct diff_atom *r_end;
239 int r = diff_atom_same(&same,
240 &left->atoms.head[identical_l.end],
241 &right->atoms.head[identical_r.end]);
246 l_end = &left->atoms.head[identical_l.end];
247 r_end = &right->atoms.head[identical_r.end];
248 if (!PATIENCE(l_end).unique_in_both)
250 /* Part of a chunk of identical lines, remove from
251 * listing of unique_in_both lines */
252 PATIENCE(l_end).unique_in_both = false;
253 PATIENCE(r_end).unique_in_both = false;
254 (*unique_in_both_count)--;
257 PATIENCE(l).identical_lines = identical_l;
258 PATIENCE(PATIENCE(l).pos_in_other).identical_lines =
261 l_min = identical_l.end;
262 r_min = identical_r.end;
264 if (!diff_range_empty(&PATIENCE(l).identical_lines)) {
265 debug("common-unique line at l=%u r=%u swallowed"
266 " identical lines l=%u-%u r=%u-%u\n",
268 identical_l.start, identical_l.end,
269 identical_r.start, identical_r.end);
271 debug("next_l_idx = %u\n", next_l_idx);
276 /* binary search to find the stack to put this atom "card" on. */
278 find_target_stack(struct diff_atom *atom,
279 struct diff_atom **patience_stacks,
280 unsigned int patience_stacks_count)
283 unsigned int hi = patience_stacks_count;
285 unsigned int mid = (lo + hi) >> 1;
287 if (PATIENCE(patience_stacks[mid]).pos_in_other
288 < PATIENCE(atom).pos_in_other)
296 /* Among the lines that appear exactly once in each side, find the longest
297 * streak that appear in both files in the same order (with other stuff allowed
298 * to interleave). Use patience sort for that, as in the Patience Diff
300 * See https://bramcohen.livejournal.com/73318.html and, for a much more
301 * detailed explanation,
302 * https://blog.jcoglan.com/2017/09/19/the-patience-diff-algorithm/ */
304 diff_algo_patience(const struct diff_algo_config *algo_config,
305 struct diff_state *state)
308 struct diff_data *left = &state->left;
309 struct diff_data *right = &state->right;
310 struct atom_patience *atom_patience_left =
311 calloc(left->atoms.len, sizeof(struct atom_patience));
312 struct atom_patience *atom_patience_right =
313 calloc(right->atoms.len, sizeof(struct atom_patience));
314 unsigned int unique_in_both_count;
315 struct diff_atom **lcs = NULL;
317 debug("\n** %s\n", __func__);
319 left->root->current = left;
320 right->root->current = right;
321 left->algo_data = atom_patience_left;
322 right->algo_data = atom_patience_right;
324 /* Find those lines that appear exactly once in 'left' and exactly once
326 rc = diff_atoms_mark_unique_in_both(left, right, &unique_in_both_count);
330 debug("unique_in_both_count %u\n", unique_in_both_count);
336 if (!unique_in_both_count) {
337 /* Cannot apply Patience, tell the caller to use fallback_algo
339 rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK;
343 rc = diff_atoms_swallow_identical_neighbors(left, right,
344 &unique_in_both_count);
347 debug("After swallowing identical neighbors: unique_in_both = %u\n",
348 unique_in_both_count);
352 /* An array of Longest Common Sequence is the result of the below
354 unsigned int lcs_count = 0;
355 struct diff_atom *lcs_tail = NULL;
358 /* This subscope marks the lifetime of the atom_pointers
361 /* One chunk of storage for atom pointers */
362 struct diff_atom **atom_pointers;
363 atom_pointers = recallocarray(NULL, 0, unique_in_both_count * 2,
364 sizeof(struct diff_atom*));
366 /* Half for the list of atoms that still need to be put on
368 struct diff_atom **uniques = atom_pointers;
370 /* Half for the patience sort state's "card stacks" -- we
371 * remember only each stack's topmost "card" */
372 struct diff_atom **patience_stacks;
373 patience_stacks = atom_pointers + unique_in_both_count;
374 unsigned int patience_stacks_count = 0;
376 /* Take all common, unique items from 'left' ... */
378 struct diff_atom *atom;
379 struct diff_atom **uniques_end = uniques;
380 diff_data_foreach_atom(atom, left) {
381 if (!PATIENCE(atom).unique_in_both)
387 /* ...and sort them to the order found in 'right'.
388 * The idea is to find the leftmost stack that has a higher line
389 * number and add it to the stack's top.
390 * If there is no such stack, open a new one on the right. The
391 * line number is derived from the atom*, which are array items
392 * and hence reflect the relative position in the source file.
393 * So we got the common-uniques from 'left' and sort them
394 * according to PATIENCE(atom).pos_in_other. */
396 for (i = 0; i < unique_in_both_count; i++) {
398 unsigned int target_stack;
399 target_stack = find_target_stack(atom, patience_stacks,
400 patience_stacks_count);
401 assert(target_stack <= patience_stacks_count);
402 patience_stacks[target_stack] = atom;
403 if (target_stack == patience_stacks_count)
404 patience_stacks_count++;
406 /* Record a back reference to the next stack on the
407 * left, which will form the final longest sequence
409 PATIENCE(atom).prev_stack = target_stack ?
410 patience_stacks[target_stack - 1] : NULL;
414 /* backtrace through prev_stack references to form the final
415 * longest common sequence */
416 lcs_tail = patience_stacks[patience_stacks_count - 1];
417 lcs_count = patience_stacks_count;
419 /* uniques and patience_stacks are no longer needed.
420 * Backpointers are in PATIENCE(atom).prev_stack */
424 lcs = recallocarray(NULL, 0, lcs_count, sizeof(struct diff_atom*));
425 struct diff_atom **lcs_backtrace_pos = &lcs[lcs_count - 1];
426 struct diff_atom *atom;
427 for (atom = lcs_tail; atom; atom = PATIENCE(atom).prev_stack, lcs_backtrace_pos--) {
428 assert(lcs_backtrace_pos >= lcs);
429 *lcs_backtrace_pos = atom;
434 debug("\npatience LCS:\n");
435 for (i = 0; i < lcs_count; i++) {
436 debug_dump_atom(left, right, lcs[i]);
441 /* TODO: For each common-unique line found (now listed in lcs), swallow
442 * lines upwards and downwards that are identical on each side. Requires
443 * a way to represent atoms being glued to adjacent atoms. */
445 debug("\ntraverse LCS, possibly recursing:\n");
447 /* Now we have pinned positions in both files at which it makes sense to
448 * divide the diff problem into smaller chunks. Go into the next round:
449 * look at each section in turn, trying to again find common-unique
450 * lines in those smaller sections. As soon as no more are found, the
451 * remaining smaller sections are solved by Myers. */
452 unsigned int left_pos = 0;
453 unsigned int right_pos = 0;
454 for (i = 0; i <= lcs_count; i++) {
455 struct diff_atom *atom;
456 struct diff_atom *atom_r;
457 unsigned int left_idx;
458 unsigned int right_idx;
462 atom_r = PATIENCE(atom).pos_in_other;
463 debug("lcs[%u] = left[%u] = right[%u]\n", i,
464 diff_atom_idx(left, atom), diff_atom_idx(right, atom_r));
465 left_idx = PATIENCE(atom).identical_lines.start;
466 right_idx = PATIENCE(atom_r).identical_lines.start;
467 debug(" identical lines l %u-%u r %u-%u\n",
468 PATIENCE(atom).identical_lines.start, PATIENCE(atom).identical_lines.end,
469 PATIENCE(atom_r).identical_lines.start, PATIENCE(atom_r).identical_lines.end);
473 left_idx = left->atoms.len;
474 right_idx = right->atoms.len;
477 /* 'atom' now marks an atom that matches on both sides according
478 * to patience-diff (a common-unique identical atom in both
480 * Handle the section before and the atom itself; the section
481 * after will be handled by the next loop iteration -- note that
482 * i loops to last element + 1 ("i <= lcs_count"), so that there
483 * will be another final iteration to pick up the last remaining
484 * items after the last LCS atom.
485 * The sections before might also be empty on left and/or right.
486 * left_pos and right_pos mark the indexes of the first atoms
487 * that have not yet been handled in the previous loop
488 * iteration. left_idx and right_idx mark the indexes of the
489 * matching atom on left and right, respectively. */
491 debug("iteration %u left_pos %u left_idx %u"
492 " right_pos %u right_idx %u\n",
493 i, left_pos, left_idx, right_pos, right_idx);
495 /* Section before the matching atom */
496 struct diff_atom *left_atom = &left->atoms.head[left_pos];
497 unsigned int left_section_len = left_idx - left_pos;
499 struct diff_atom *right_atom = &(right->atoms.head[right_pos]);
500 unsigned int right_section_len = right_idx - right_pos;
502 if (left_section_len && right_section_len) {
503 /* Record an unsolved chunk, the caller will apply
504 * inner_algo() on this chunk. */
505 if (!diff_state_add_chunk(state, false,
506 left_atom, left_section_len,
510 } else if (left_section_len && !right_section_len) {
511 /* Only left atoms and none on the right, they form a
512 * "minus" chunk, then. */
513 if (!diff_state_add_chunk(state, true,
514 left_atom, left_section_len,
517 } else if (!left_section_len && right_section_len) {
518 /* No left atoms, only atoms on the right, they form a
519 * "plus" chunk, then. */
520 if (!diff_state_add_chunk(state, true,
522 right_atom, right_section_len))
525 /* else: left_section_len == 0 and right_section_len == 0, i.e.
528 /* The atom found to match on both sides forms a chunk of equals
529 * on each side. In the very last iteration of this loop, there
530 * is no matching atom, we were just cleaning out the remaining
534 ok = diff_state_add_chunk(state, true,
536 + PATIENCE(atom).identical_lines.start,
537 diff_range_len(&PATIENCE(atom).identical_lines),
539 + PATIENCE(atom_r).identical_lines.start,
540 diff_range_len(&PATIENCE(atom_r).identical_lines));
543 left_pos = PATIENCE(atom).identical_lines.end;
544 right_pos = PATIENCE(atom_r).identical_lines.end;
546 left_pos = left_idx + 1;
547 right_pos = right_idx + 1;
549 debug("end of iteration %u left_pos %u left_idx %u"
550 " right_pos %u right_idx %u\n",
551 i, left_pos, left_idx, right_pos, right_idx);
553 debug("** END %s\n", __func__);
558 left->root->current = NULL;
559 right->root->current = NULL;
560 free(atom_patience_left);
561 free(atom_patience_right);