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.
20 #include <diff/diff_main.h>
24 /* Set unique_here = true for all atoms that exist exactly once in this list. */
25 static void diff_atoms_mark_unique(struct diff_data *d, unsigned int *unique_count)
28 unsigned int count = 0;
29 diff_data_foreach_atom(i, d) {
30 i->patience.unique_here = true;
31 i->patience.unique_in_both = true;
34 diff_data_foreach_atom(i, d) {
37 if (!i->patience.unique_here)
40 diff_data_foreach_atom_from(i + 1, j, d) {
41 if (diff_atom_same(i, j)) {
42 if (i->patience.unique_here) {
43 i->patience.unique_here = false;
44 i->patience.unique_in_both = false;
47 j->patience.unique_here = false;
48 j->patience.unique_in_both = false;
54 *unique_count = count;
57 /* Mark those lines as atom->patience.unique_in_both = true that appear exactly once in each side. */
58 static void diff_atoms_mark_unique_in_both(struct diff_data *left, struct diff_data *right,
59 unsigned int *unique_in_both_count)
61 /* Derive the final unique_in_both count without needing an explicit iteration. So this is just some
62 * optimiziation to save one iteration in the end. */
63 unsigned int unique_in_both;
65 diff_atoms_mark_unique(left, &unique_in_both);
66 diff_atoms_mark_unique(right, NULL);
68 debug("unique_in_both %u\n", unique_in_both);
71 diff_data_foreach_atom(i, left) {
72 if (!i->patience.unique_here)
76 diff_data_foreach_atom(j, right) {
77 if (!diff_atom_same(i, j))
79 if (!j->patience.unique_here) {
80 found_in_b = 2; /* or more */
84 j->patience.pos_in_other = i;
85 i->patience.pos_in_other = j;
89 if (found_in_b == 0 || found_in_b > 1) {
90 i->patience.unique_in_both = false;
92 debug("unique_in_both %u (%d) ", unique_in_both, found_in_b);
93 debug_dump_atom(left, NULL, i);
97 /* Still need to unmark right[*]->patience.unique_in_both for atoms that don't exist in left */
98 diff_data_foreach_atom(i, right) {
99 if (!i->patience.unique_here
100 || !i->patience.unique_in_both)
103 bool found_in_a = false;
104 diff_data_foreach_atom(j, left) {
105 if (!j->patience.unique_in_both)
107 if (!diff_atom_same(i, j))
114 i->patience.unique_in_both = false;
117 if (unique_in_both_count)
118 *unique_in_both_count = unique_in_both;
121 static void diff_atoms_swallow_identical_neighbors(struct diff_data *left, struct diff_data *right,
122 unsigned int *unique_in_both_count)
124 debug("trivially combine identical lines arount unique_in_both lines\n");
127 unsigned int next_l_idx;
128 unsigned int l_min = 0;
129 unsigned int r_min = 0;
130 for (l_idx = 0; l_idx < left->atoms.len; l_idx = next_l_idx) {
131 next_l_idx = l_idx + 1;
132 struct diff_atom *l = &left->atoms.head[l_idx];
134 if (!l->patience.unique_in_both)
137 debug("check identical lines around ");
138 debug_dump_atom(left, right, l);
140 unsigned int r_idx = diff_atom_idx(right, l->patience.pos_in_other);
142 struct range identical_l;
143 struct range identical_r;
146 * Each common-unique line swallows identical lines upwards and downwards.
147 * All common-unique lines that were part of the identical lines following below were already swallowed
148 * in the previous iteration, so we will never hit another common-unique line above. */
149 for (identical_l.start = l_idx, identical_r.start = r_idx;
150 identical_l.start > l_min
151 && identical_r.start > r_min
152 && diff_atom_same(&left->atoms.head[identical_l.start - 1],
153 &right->atoms.head[identical_r.start - 1]);
154 identical_l.start--, identical_r.start--);
156 /* Swallow downwards */
157 for (identical_l.end = l_idx + 1, identical_r.end = r_idx + 1;
158 identical_l.end < left->atoms.len
159 && identical_r.end < right->atoms.len
160 && diff_atom_same(&left->atoms.head[identical_l.end],
161 &right->atoms.head[identical_r.end]);
162 identical_l.end++, identical_r.end++,
164 if (left->atoms.head[identical_l.end].patience.unique_in_both) {
165 /* Part of a chunk of identical lines, remove from listing of unique_in_both lines */
166 left->atoms.head[identical_l.end].patience.unique_in_both = false;
167 right->atoms.head[identical_r.end].patience.unique_in_both = false;
168 (*unique_in_both_count)--;
172 l->patience.identical_lines = identical_l;
173 l->patience.pos_in_other->patience.identical_lines = identical_r;
175 l_min = identical_l.end;
176 r_min = identical_r.end;
178 if (!range_empty(&l->patience.identical_lines)) {
179 debug("common-unique line at l=%u r=%u swallowed identical lines l=%u-%u r=%u-%u\n",
181 identical_l.start, identical_l.end,
182 identical_r.start, identical_r.end);
184 debug("next_l_idx = %u\n", next_l_idx);
188 /* Among the lines that appear exactly once in each side, find the longest streak that appear in both files in the same
189 * order (with other stuff allowed to interleave). Use patience sort for that, as in the Patience Diff algorithm.
190 * See https://bramcohen.livejournal.com/73318.html and, for a much more detailed explanation,
191 * https://blog.jcoglan.com/2017/09/19/the-patience-diff-algorithm/ */
192 enum diff_rc diff_algo_patience(const struct diff_algo_config *algo_config, struct diff_state *state)
194 enum diff_rc rc = DIFF_RC_ENOMEM;
196 struct diff_data *left = &state->left;
197 struct diff_data *right = &state->right;
199 unsigned int unique_in_both_count;
201 debug("\n** %s\n", __func__);
203 /* Find those lines that appear exactly once in 'left' and exactly once in 'right'. */
204 diff_atoms_mark_unique_in_both(left, right, &unique_in_both_count);
206 debug("unique_in_both_count %u\n", unique_in_both_count);
212 if (!unique_in_both_count) {
213 /* Cannot apply Patience, tell the caller to use fallback_algo instead. */
214 return DIFF_RC_USE_DIFF_ALGO_FALLBACK;
217 diff_atoms_swallow_identical_neighbors(left, right, &unique_in_both_count);
218 debug("After swallowing identical neighbors: unique_in_both = %u\n",
219 unique_in_both_count);
221 /* An array of Longest Common Sequence is the result of the below subscope: */
222 unsigned int lcs_count = 0;
223 struct diff_atom **lcs = NULL;
224 struct diff_atom *lcs_tail = NULL;
227 /* This subscope marks the lifetime of the atom_pointers allocation */
229 /* One chunk of storage for atom pointers */
230 struct diff_atom **atom_pointers = recallocarray(NULL, 0, unique_in_both_count * 2, sizeof(struct diff_atom*));
232 /* Half for the list of atoms that still need to be put on stacks */
233 struct diff_atom **uniques = atom_pointers;
235 /* Half for the patience sort state's "card stacks" -- we remember only each stack's topmost "card" */
236 struct diff_atom **patience_stacks = atom_pointers + unique_in_both_count;
237 unsigned int patience_stacks_count = 0;
239 /* Take all common, unique items from 'left' ... */
241 struct diff_atom *atom;
242 struct diff_atom **uniques_end = uniques;
243 diff_data_foreach_atom(atom, left) {
244 if (!atom->patience.unique_in_both)
250 /* ...and sort them to the order found in 'right'.
251 * The idea is to find the leftmost stack that has a higher line number and add it to the stack's top.
252 * If there is no such stack, open a new one on the right. The line number is derived from the atom*,
253 * which are array items and hence reflect the relative position in the source file. So we got the
254 * common-uniques from 'left' and sort them according to atom->patience.pos_in_other. */
256 for (i = 0; i < unique_in_both_count; i++) {
258 unsigned int target_stack;
260 if (!patience_stacks_count)
263 /* binary search to find the stack to put this atom "card" on. */
265 unsigned int hi = patience_stacks_count;
267 unsigned int mid = (lo + hi) >> 1;
268 if (patience_stacks[mid]->patience.pos_in_other < atom->patience.pos_in_other)
277 assert(target_stack <= patience_stacks_count);
278 patience_stacks[target_stack] = atom;
279 if (target_stack == patience_stacks_count)
280 patience_stacks_count++;
282 /* Record a back reference to the next stack on the left, which will form the final longest sequence
284 atom->patience.prev_stack = target_stack ? patience_stacks[target_stack - 1] : NULL;
288 /* backtrace through prev_stack references to form the final longest common sequence */
289 lcs_tail = patience_stacks[patience_stacks_count - 1];
290 lcs_count = patience_stacks_count;
292 /* uniques and patience_stacks are no longer needed. Backpointers are in atom->patience.prev_stack */
296 lcs = recallocarray(NULL, 0, lcs_count, sizeof(struct diff_atom*));
297 struct diff_atom **lcs_backtrace_pos = &lcs[lcs_count - 1];
298 struct diff_atom *atom;
299 for (atom = lcs_tail; atom; atom = atom->patience.prev_stack, lcs_backtrace_pos--) {
300 assert(lcs_backtrace_pos >= lcs);
301 *lcs_backtrace_pos = atom;
306 debug("\npatience LCS:\n");
307 for (i = 0; i < lcs_count; i++) {
308 debug_dump_atom(left, right, lcs[i]);
313 /* TODO: For each common-unique line found (now listed in lcs), swallow lines upwards and downwards that are
314 * identical on each side. Requires a way to represent atoms being glued to adjacent atoms. */
316 debug("\ntraverse LCS, possibly recursing:\n");
318 /* Now we have pinned positions in both files at which it makes sense to divide the diff problem into smaller
319 * chunks. Go into the next round: look at each section in turn, trying to again find common-unique lines in
320 * those smaller sections. As soon as no more are found, the remaining smaller sections are solved by Myers. */
321 unsigned int left_pos = 0;
322 unsigned int right_pos = 0;
323 for (i = 0; i <= lcs_count; i++) {
324 struct diff_atom *atom;
325 struct diff_atom *atom_r;
326 unsigned int left_idx;
327 unsigned int right_idx;
331 atom_r = atom->patience.pos_in_other;
332 debug("lcs[%u] = left[%ld] = right[%ld]\n", i,
333 diff_atom_idx(left, atom), diff_atom_idx(right, atom_r));
334 left_idx = atom->patience.identical_lines.start;
335 right_idx = atom_r->patience.identical_lines.start;
336 debug(" identical lines l %u-%u r %u-%u\n",
337 atom->patience.identical_lines.start, atom->patience.identical_lines.end,
338 atom_r->patience.identical_lines.start, atom_r->patience.identical_lines.end);
342 left_idx = left->atoms.len;
343 right_idx = right->atoms.len;
346 /* 'atom' now marks an atom that matches on both sides according to patience-diff
347 * (a common-unique identical atom in both files).
348 * Handle the section before and the atom itself; the section after will be handled by the next loop
349 * iteration -- note that i loops to last element + 1 ("i <= lcs_count"), so that there will be another
350 * final iteration to pick up the last remaining items after the last LCS atom.
351 * The sections before might also be empty on left and/or right.
352 * left_pos and right_pos mark the indexes of the first atoms that have not yet been handled in the
353 * previous loop iteration.
354 * left_idx and right_idx mark the indexes of the matching atom on left and right, respectively. */
356 debug("iteration %u left_pos %u left_idx %u right_pos %u right_idx %u\n",
357 i, left_pos, left_idx, right_pos, right_idx);
359 /* Section before the matching atom */
360 struct diff_atom *left_atom = &left->atoms.head[left_pos];
361 unsigned int left_section_len = left_idx - left_pos;
363 struct diff_atom *right_atom = &(right->atoms.head[right_pos]);
364 unsigned int right_section_len = right_idx - right_pos;
366 if (left_section_len && right_section_len) {
367 /* Record an unsolved chunk, the caller will apply inner_algo() on this chunk. */
368 if (!diff_state_add_chunk(state, false,
369 left_atom, left_section_len,
370 right_atom, right_section_len))
372 } else if (left_section_len && !right_section_len) {
373 /* Only left atoms and none on the right, they form a "minus" chunk, then. */
374 if (!diff_state_add_chunk(state, true,
375 left_atom, left_section_len,
378 } else if (!left_section_len && right_section_len) {
379 /* No left atoms, only atoms on the right, they form a "plus" chunk, then. */
380 if (!diff_state_add_chunk(state, true,
382 right_atom, right_section_len))
385 /* else: left_section_len == 0 and right_section_len == 0, i.e. nothing here. */
387 /* The atom found to match on both sides forms a chunk of equals on each side. In the very last
388 * iteration of this loop, there is no matching atom, we were just cleaning out the remaining lines. */
390 if (!diff_state_add_chunk(state, true,
391 left->atoms.head + atom->patience.identical_lines.start,
392 range_len(&atom->patience.identical_lines),
393 right->atoms.head + atom_r->patience.identical_lines.start,
394 range_len(&atom_r->patience.identical_lines)))
396 left_pos = atom->patience.identical_lines.end;
397 right_pos = atom_r->patience.identical_lines.end;
399 left_pos = left_idx + 1;
400 right_pos = right_idx + 1;
402 debug("end of iteration %u left_pos %u left_idx %u right_pos %u right_idx %u\n",
403 i, left_pos, left_idx, right_pos, right_idx);
405 debug("** END %s\n", __func__);
