1 3b0f3d61 2020-01-22 neels /* Implementation of the Patience Diff algorithm invented by Bram Cohen:
2 3b0f3d61 2020-01-22 neels * Divide a diff problem into smaller chunks by an LCS of common-unique lines. */
4 3b0f3d61 2020-01-22 neels * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
6 3b0f3d61 2020-01-22 neels * Permission to use, copy, modify, and distribute this software for any
7 3b0f3d61 2020-01-22 neels * purpose with or without fee is hereby granted, provided that the above
8 3b0f3d61 2020-01-22 neels * copyright notice and this permission notice appear in all copies.
10 3b0f3d61 2020-01-22 neels * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 3b0f3d61 2020-01-22 neels * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 3b0f3d61 2020-01-22 neels * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 3b0f3d61 2020-01-22 neels * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 3b0f3d61 2020-01-22 neels * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 3b0f3d61 2020-01-22 neels * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 3b0f3d61 2020-01-22 neels * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
19 3b0f3d61 2020-01-22 neels #include <assert.h>
20 e10a628a 2020-09-16 stsp #include <inttypes.h>
21 e10a628a 2020-09-16 stsp #include <errno.h>
22 e10a628a 2020-09-16 stsp #include <stdbool.h>
23 e10a628a 2020-09-16 stsp #include <stdio.h>
24 e10a628a 2020-09-16 stsp #include <stdlib.h>
26 e10a628a 2020-09-16 stsp #include <diff/arraylist.h>
27 3b0f3d61 2020-01-22 neels #include <diff/diff_main.h>
29 3b0f3d61 2020-01-22 neels #include "debug.h"
31 3b0f3d61 2020-01-22 neels /* Set unique_here = true for all atoms that exist exactly once in this list. */
32 61a7b578 2020-05-06 neels static void
33 61a7b578 2020-05-06 neels diff_atoms_mark_unique(struct diff_data *d, unsigned int *unique_count)
35 3b0f3d61 2020-01-22 neels struct diff_atom *i;
36 3b0f3d61 2020-01-22 neels unsigned int count = 0;
37 3b0f3d61 2020-01-22 neels diff_data_foreach_atom(i, d) {
38 3b0f3d61 2020-01-22 neels i->patience.unique_here = true;
39 3b0f3d61 2020-01-22 neels i->patience.unique_in_both = true;
42 3b0f3d61 2020-01-22 neels diff_data_foreach_atom(i, d) {
43 3b0f3d61 2020-01-22 neels struct diff_atom *j;
45 3b0f3d61 2020-01-22 neels if (!i->patience.unique_here)
48 3b0f3d61 2020-01-22 neels diff_data_foreach_atom_from(i + 1, j, d) {
50 b3fb4686 2020-09-20 neels int r = diff_atom_same(&same, i, j);
52 b3fb4686 2020-09-20 neels abort(); // TODO: error handling
55 b3fb4686 2020-09-20 neels if (i->patience.unique_here) {
56 b3fb4686 2020-09-20 neels i->patience.unique_here = false;
57 b3fb4686 2020-09-20 neels i->patience.unique_in_both = false;
60 b3fb4686 2020-09-20 neels j->patience.unique_here = false;
61 b3fb4686 2020-09-20 neels j->patience.unique_in_both = false;
65 3b0f3d61 2020-01-22 neels if (unique_count)
66 3b0f3d61 2020-01-22 neels *unique_count = count;
69 0d27172a 2020-05-06 neels /* Mark those lines as atom->patience.unique_in_both = true that appear exactly
70 0d27172a 2020-05-06 neels * once in each side. */
71 61a7b578 2020-05-06 neels static void
72 61a7b578 2020-05-06 neels diff_atoms_mark_unique_in_both(struct diff_data *left, struct diff_data *right,
73 61a7b578 2020-05-06 neels unsigned int *unique_in_both_count)
75 0d27172a 2020-05-06 neels /* Derive the final unique_in_both count without needing an explicit
76 0d27172a 2020-05-06 neels * iteration. So this is just some optimiziation to save one iteration
77 0d27172a 2020-05-06 neels * in the end. */
78 3b0f3d61 2020-01-22 neels unsigned int unique_in_both;
80 3b0f3d61 2020-01-22 neels diff_atoms_mark_unique(left, &unique_in_both);
81 3b0f3d61 2020-01-22 neels diff_atoms_mark_unique(right, NULL);
83 3b0f3d61 2020-01-22 neels debug("unique_in_both %u\n", unique_in_both);
85 3b0f3d61 2020-01-22 neels struct diff_atom *i;
86 3b0f3d61 2020-01-22 neels diff_data_foreach_atom(i, left) {
87 3b0f3d61 2020-01-22 neels if (!i->patience.unique_here)
89 3b0f3d61 2020-01-22 neels struct diff_atom *j;
90 3b0f3d61 2020-01-22 neels int found_in_b = 0;
91 3b0f3d61 2020-01-22 neels diff_data_foreach_atom(j, right) {
93 b3fb4686 2020-09-20 neels int r = diff_atom_same(&same, i, j);
95 b3fb4686 2020-09-20 neels abort(); // TODO: error handling
98 3b0f3d61 2020-01-22 neels if (!j->patience.unique_here) {
99 3b0f3d61 2020-01-22 neels found_in_b = 2; /* or more */
102 3b0f3d61 2020-01-22 neels found_in_b = 1;
103 3b0f3d61 2020-01-22 neels j->patience.pos_in_other = i;
104 3b0f3d61 2020-01-22 neels i->patience.pos_in_other = j;
108 3b0f3d61 2020-01-22 neels if (found_in_b == 0 || found_in_b > 1) {
109 3b0f3d61 2020-01-22 neels i->patience.unique_in_both = false;
110 3b0f3d61 2020-01-22 neels unique_in_both--;
111 0d27172a 2020-05-06 neels debug("unique_in_both %u (%d) ", unique_in_both,
112 0d27172a 2020-05-06 neels found_in_b);
113 3b0f3d61 2020-01-22 neels debug_dump_atom(left, NULL, i);
117 0d27172a 2020-05-06 neels /* Still need to unmark right[*]->patience.unique_in_both for atoms that
118 0d27172a 2020-05-06 neels * don't exist in left */
119 3b0f3d61 2020-01-22 neels diff_data_foreach_atom(i, right) {
120 3b0f3d61 2020-01-22 neels if (!i->patience.unique_here
121 3b0f3d61 2020-01-22 neels || !i->patience.unique_in_both)
123 3b0f3d61 2020-01-22 neels struct diff_atom *j;
124 3b0f3d61 2020-01-22 neels bool found_in_a = false;
125 3b0f3d61 2020-01-22 neels diff_data_foreach_atom(j, left) {
126 b3fb4686 2020-09-20 neels bool same;
128 3b0f3d61 2020-01-22 neels if (!j->patience.unique_in_both)
130 b3fb4686 2020-09-20 neels r = diff_atom_same(&same, i, j);
132 b3fb4686 2020-09-20 neels abort(); // TODO: error handling
133 b3fb4686 2020-09-20 neels if (!same)
135 3b0f3d61 2020-01-22 neels found_in_a = true;
139 3b0f3d61 2020-01-22 neels if (!found_in_a)
140 3b0f3d61 2020-01-22 neels i->patience.unique_in_both = false;
143 3b0f3d61 2020-01-22 neels if (unique_in_both_count)
144 3b0f3d61 2020-01-22 neels *unique_in_both_count = unique_in_both;
147 61a7b578 2020-05-06 neels static void
148 0d27172a 2020-05-06 neels diff_atoms_swallow_identical_neighbors(struct diff_data *left,
149 0d27172a 2020-05-06 neels struct diff_data *right,
150 61a7b578 2020-05-06 neels unsigned int *unique_in_both_count)
152 0d27172a 2020-05-06 neels debug("trivially combine identical lines"
153 0d27172a 2020-05-06 neels " around unique_in_both lines\n");
155 bb7fb738 2020-01-27 neels unsigned int l_idx;
156 bb7fb738 2020-01-27 neels unsigned int next_l_idx;
157 bb7fb738 2020-01-27 neels unsigned int l_min = 0;
158 bb7fb738 2020-01-27 neels unsigned int r_min = 0;
159 bb7fb738 2020-01-27 neels for (l_idx = 0; l_idx < left->atoms.len; l_idx = next_l_idx) {
160 bb7fb738 2020-01-27 neels next_l_idx = l_idx + 1;
161 bb7fb738 2020-01-27 neels struct diff_atom *l = &left->atoms.head[l_idx];
163 bb7fb738 2020-01-27 neels if (!l->patience.unique_in_both)
166 bb7fb738 2020-01-27 neels debug("check identical lines around ");
167 bb7fb738 2020-01-27 neels debug_dump_atom(left, right, l);
169 0d27172a 2020-05-06 neels unsigned int r_idx = diff_atom_idx(right,
170 0d27172a 2020-05-06 neels l->patience.pos_in_other);
172 d362ea2e 2020-07-25 stsp struct diff_range identical_l;
173 d362ea2e 2020-07-25 stsp struct diff_range identical_r;
175 bb7fb738 2020-01-27 neels /* Swallow upwards.
176 0d27172a 2020-05-06 neels * Each common-unique line swallows identical lines upwards and
177 0d27172a 2020-05-06 neels * downwards.
178 0d27172a 2020-05-06 neels * All common-unique lines that were part of the identical lines
179 0d27172a 2020-05-06 neels * following below were already swallowed in the previous
180 0d27172a 2020-05-06 neels * iteration, so we will never hit another common-unique line
181 0d27172a 2020-05-06 neels * above. */
182 bb7fb738 2020-01-27 neels for (identical_l.start = l_idx, identical_r.start = r_idx;
183 b3fb4686 2020-09-20 neels identical_l.start > l_min && identical_r.start > r_min;
184 b3fb4686 2020-09-20 neels identical_l.start--, identical_r.start--) {
185 b3fb4686 2020-09-20 neels bool same;
186 b3fb4686 2020-09-20 neels int r = diff_atom_same(&same,
187 0d27172a 2020-05-06 neels &left->atoms.head[identical_l.start - 1],
188 0d27172a 2020-05-06 neels &right->atoms.head[identical_r.start - 1]);
190 b3fb4686 2020-09-20 neels abort(); // TODO: error handling
191 b3fb4686 2020-09-20 neels if (!same)
195 bb7fb738 2020-01-27 neels /* Swallow downwards */
196 bb7fb738 2020-01-27 neels for (identical_l.end = l_idx + 1, identical_r.end = r_idx + 1;
197 bb7fb738 2020-01-27 neels identical_l.end < left->atoms.len
198 b3fb4686 2020-09-20 neels && identical_r.end < right->atoms.len;
199 bb7fb738 2020-01-27 neels identical_l.end++, identical_r.end++,
200 bb7fb738 2020-01-27 neels next_l_idx++) {
201 0d27172a 2020-05-06 neels struct diff_atom *l_end;
202 0d27172a 2020-05-06 neels struct diff_atom *r_end;
203 b3fb4686 2020-09-20 neels bool same;
204 b3fb4686 2020-09-20 neels int r = diff_atom_same(&same,
205 b3fb4686 2020-09-20 neels &left->atoms.head[identical_l.end],
206 b3fb4686 2020-09-20 neels &right->atoms.head[identical_r.end]);
208 b3fb4686 2020-09-20 neels abort(); // TODO: error handling
209 b3fb4686 2020-09-20 neels if (!same)
211 0d27172a 2020-05-06 neels l_end = &left->atoms.head[identical_l.end];
212 ab699b5c 2020-05-12 stsp r_end = &right->atoms.head[identical_r.end];
213 0d27172a 2020-05-06 neels if (!l_end->patience.unique_in_both)
215 0d27172a 2020-05-06 neels /* Part of a chunk of identical lines, remove from
216 0d27172a 2020-05-06 neels * listing of unique_in_both lines */
217 0d27172a 2020-05-06 neels l_end->patience.unique_in_both = false;
218 0d27172a 2020-05-06 neels r_end->patience.unique_in_both = false;
219 0d27172a 2020-05-06 neels (*unique_in_both_count)--;
222 bb7fb738 2020-01-27 neels l->patience.identical_lines = identical_l;
223 0d27172a 2020-05-06 neels l->patience.pos_in_other->patience.identical_lines =
224 0d27172a 2020-05-06 neels identical_r;
226 bb7fb738 2020-01-27 neels l_min = identical_l.end;
227 bb7fb738 2020-01-27 neels r_min = identical_r.end;
229 d362ea2e 2020-07-25 stsp if (!diff_range_empty(&l->patience.identical_lines)) {
230 0d27172a 2020-05-06 neels debug("common-unique line at l=%u r=%u swallowed"
231 0d27172a 2020-05-06 neels " identical lines l=%u-%u r=%u-%u\n",
232 bb7fb738 2020-01-27 neels l_idx, r_idx,
233 bb7fb738 2020-01-27 neels identical_l.start, identical_l.end,
234 bb7fb738 2020-01-27 neels identical_r.start, identical_r.end);
236 bb7fb738 2020-01-27 neels debug("next_l_idx = %u\n", next_l_idx);
240 0d27172a 2020-05-06 neels /* binary search to find the stack to put this atom "card" on. */
241 0d27172a 2020-05-06 neels static int
242 0d27172a 2020-05-06 neels find_target_stack(struct diff_atom *atom,
243 0d27172a 2020-05-06 neels struct diff_atom **patience_stacks,
244 0d27172a 2020-05-06 neels unsigned int patience_stacks_count)
246 0d27172a 2020-05-06 neels unsigned int lo = 0;
247 0d27172a 2020-05-06 neels unsigned int hi = patience_stacks_count;
248 0d27172a 2020-05-06 neels while (lo < hi) {
249 0d27172a 2020-05-06 neels unsigned int mid = (lo + hi) >> 1;
251 0d27172a 2020-05-06 neels if (patience_stacks[mid]->patience.pos_in_other
252 0d27172a 2020-05-06 neels < atom->patience.pos_in_other)
253 0d27172a 2020-05-06 neels lo = mid + 1;
257 0d27172a 2020-05-06 neels return lo;
260 0d27172a 2020-05-06 neels /* Among the lines that appear exactly once in each side, find the longest
261 0d27172a 2020-05-06 neels * streak that appear in both files in the same order (with other stuff allowed
262 0d27172a 2020-05-06 neels * to interleave). Use patience sort for that, as in the Patience Diff
263 0d27172a 2020-05-06 neels * algorithm.
264 0d27172a 2020-05-06 neels * See https://bramcohen.livejournal.com/73318.html and, for a much more
265 0d27172a 2020-05-06 neels * detailed explanation,
266 3b0f3d61 2020-01-22 neels * https://blog.jcoglan.com/2017/09/19/the-patience-diff-algorithm/ */
268 0d27172a 2020-05-06 neels diff_algo_patience(const struct diff_algo_config *algo_config,
269 0d27172a 2020-05-06 neels struct diff_state *state)
271 3e6cba3a 2020-08-13 stsp int rc = ENOMEM;
273 3b0f3d61 2020-01-22 neels struct diff_data *left = &state->left;
274 3b0f3d61 2020-01-22 neels struct diff_data *right = &state->right;
276 3b0f3d61 2020-01-22 neels unsigned int unique_in_both_count;
278 3b0f3d61 2020-01-22 neels debug("\n** %s\n", __func__);
280 0d27172a 2020-05-06 neels /* Find those lines that appear exactly once in 'left' and exactly once
281 0d27172a 2020-05-06 neels * in 'right'. */
282 3b0f3d61 2020-01-22 neels diff_atoms_mark_unique_in_both(left, right, &unique_in_both_count);
284 3b0f3d61 2020-01-22 neels debug("unique_in_both_count %u\n", unique_in_both_count);
285 3b0f3d61 2020-01-22 neels debug("left:\n");
286 3b0f3d61 2020-01-22 neels debug_dump(left);
287 3b0f3d61 2020-01-22 neels debug("right:\n");
288 3b0f3d61 2020-01-22 neels debug_dump(right);
290 3b0f3d61 2020-01-22 neels if (!unique_in_both_count) {
291 0d27172a 2020-05-06 neels /* Cannot apply Patience, tell the caller to use fallback_algo
292 0d27172a 2020-05-06 neels * instead. */
293 3b0f3d61 2020-01-22 neels return DIFF_RC_USE_DIFF_ALGO_FALLBACK;
296 0d27172a 2020-05-06 neels diff_atoms_swallow_identical_neighbors(left, right,
297 0d27172a 2020-05-06 neels &unique_in_both_count);
298 bb7fb738 2020-01-27 neels debug("After swallowing identical neighbors: unique_in_both = %u\n",
299 bb7fb738 2020-01-27 neels unique_in_both_count);
301 0d27172a 2020-05-06 neels /* An array of Longest Common Sequence is the result of the below
302 0d27172a 2020-05-06 neels * subscope: */
303 3b0f3d61 2020-01-22 neels unsigned int lcs_count = 0;
304 3b0f3d61 2020-01-22 neels struct diff_atom **lcs = NULL;
305 3b0f3d61 2020-01-22 neels struct diff_atom *lcs_tail = NULL;
308 0d27172a 2020-05-06 neels /* This subscope marks the lifetime of the atom_pointers
309 0d27172a 2020-05-06 neels * allocation */
311 3b0f3d61 2020-01-22 neels /* One chunk of storage for atom pointers */
312 0d27172a 2020-05-06 neels struct diff_atom **atom_pointers;
313 0d27172a 2020-05-06 neels atom_pointers = recallocarray(NULL, 0, unique_in_both_count * 2,
314 0d27172a 2020-05-06 neels sizeof(struct diff_atom*));
316 0d27172a 2020-05-06 neels /* Half for the list of atoms that still need to be put on
317 0d27172a 2020-05-06 neels * stacks */
318 3b0f3d61 2020-01-22 neels struct diff_atom **uniques = atom_pointers;
320 0d27172a 2020-05-06 neels /* Half for the patience sort state's "card stacks" -- we
321 0d27172a 2020-05-06 neels * remember only each stack's topmost "card" */
322 0d27172a 2020-05-06 neels struct diff_atom **patience_stacks;
323 0d27172a 2020-05-06 neels patience_stacks = atom_pointers + unique_in_both_count;
324 3b0f3d61 2020-01-22 neels unsigned int patience_stacks_count = 0;
326 3b0f3d61 2020-01-22 neels /* Take all common, unique items from 'left' ... */
328 3b0f3d61 2020-01-22 neels struct diff_atom *atom;
329 3b0f3d61 2020-01-22 neels struct diff_atom **uniques_end = uniques;
330 3b0f3d61 2020-01-22 neels diff_data_foreach_atom(atom, left) {
331 3b0f3d61 2020-01-22 neels if (!atom->patience.unique_in_both)
333 3b0f3d61 2020-01-22 neels *uniques_end = atom;
334 3b0f3d61 2020-01-22 neels uniques_end++;
337 3b0f3d61 2020-01-22 neels /* ...and sort them to the order found in 'right'.
338 0d27172a 2020-05-06 neels * The idea is to find the leftmost stack that has a higher line
339 0d27172a 2020-05-06 neels * number and add it to the stack's top.
340 0d27172a 2020-05-06 neels * If there is no such stack, open a new one on the right. The
341 0d27172a 2020-05-06 neels * line number is derived from the atom*, which are array items
342 0d27172a 2020-05-06 neels * and hence reflect the relative position in the source file.
343 0d27172a 2020-05-06 neels * So we got the common-uniques from 'left' and sort them
344 0d27172a 2020-05-06 neels * according to atom->patience.pos_in_other. */
345 3b0f3d61 2020-01-22 neels unsigned int i;
346 3b0f3d61 2020-01-22 neels for (i = 0; i < unique_in_both_count; i++) {
347 3b0f3d61 2020-01-22 neels atom = uniques[i];
348 3b0f3d61 2020-01-22 neels unsigned int target_stack;
349 0d27172a 2020-05-06 neels target_stack = find_target_stack(atom, patience_stacks,
350 0d27172a 2020-05-06 neels patience_stacks_count);
351 3b0f3d61 2020-01-22 neels assert(target_stack <= patience_stacks_count);
352 3b0f3d61 2020-01-22 neels patience_stacks[target_stack] = atom;
353 3b0f3d61 2020-01-22 neels if (target_stack == patience_stacks_count)
354 3b0f3d61 2020-01-22 neels patience_stacks_count++;
356 0d27172a 2020-05-06 neels /* Record a back reference to the next stack on the
357 0d27172a 2020-05-06 neels * left, which will form the final longest sequence
358 3b0f3d61 2020-01-22 neels * later. */
359 0d27172a 2020-05-06 neels atom->patience.prev_stack = target_stack ?
360 0d27172a 2020-05-06 neels patience_stacks[target_stack - 1] : NULL;
364 0d27172a 2020-05-06 neels /* backtrace through prev_stack references to form the final
365 0d27172a 2020-05-06 neels * longest common sequence */
366 3b0f3d61 2020-01-22 neels lcs_tail = patience_stacks[patience_stacks_count - 1];
367 3b0f3d61 2020-01-22 neels lcs_count = patience_stacks_count;
369 0d27172a 2020-05-06 neels /* uniques and patience_stacks are no longer needed.
370 0d27172a 2020-05-06 neels * Backpointers are in atom->patience.prev_stack */
371 3b0f3d61 2020-01-22 neels free(atom_pointers);
374 3b0f3d61 2020-01-22 neels lcs = recallocarray(NULL, 0, lcs_count, sizeof(struct diff_atom*));
375 3b0f3d61 2020-01-22 neels struct diff_atom **lcs_backtrace_pos = &lcs[lcs_count - 1];
376 3b0f3d61 2020-01-22 neels struct diff_atom *atom;
377 3b0f3d61 2020-01-22 neels for (atom = lcs_tail; atom; atom = atom->patience.prev_stack, lcs_backtrace_pos--) {
378 3b0f3d61 2020-01-22 neels assert(lcs_backtrace_pos >= lcs);
379 3b0f3d61 2020-01-22 neels *lcs_backtrace_pos = atom;
382 3b0f3d61 2020-01-22 neels unsigned int i;
383 3b0f3d61 2020-01-22 neels if (DEBUG) {
384 3b0f3d61 2020-01-22 neels debug("\npatience LCS:\n");
385 3b0f3d61 2020-01-22 neels for (i = 0; i < lcs_count; i++) {
386 3b0f3d61 2020-01-22 neels debug_dump_atom(left, right, lcs[i]);
391 0d27172a 2020-05-06 neels /* TODO: For each common-unique line found (now listed in lcs), swallow
392 0d27172a 2020-05-06 neels * lines upwards and downwards that are identical on each side. Requires
393 0d27172a 2020-05-06 neels * a way to represent atoms being glued to adjacent atoms. */
395 3b0f3d61 2020-01-22 neels debug("\ntraverse LCS, possibly recursing:\n");
397 0d27172a 2020-05-06 neels /* Now we have pinned positions in both files at which it makes sense to
398 0d27172a 2020-05-06 neels * divide the diff problem into smaller chunks. Go into the next round:
399 0d27172a 2020-05-06 neels * look at each section in turn, trying to again find common-unique
400 0d27172a 2020-05-06 neels * lines in those smaller sections. As soon as no more are found, the
401 0d27172a 2020-05-06 neels * remaining smaller sections are solved by Myers. */
402 3b0f3d61 2020-01-22 neels unsigned int left_pos = 0;
403 3b0f3d61 2020-01-22 neels unsigned int right_pos = 0;
404 3b0f3d61 2020-01-22 neels for (i = 0; i <= lcs_count; i++) {
405 3b0f3d61 2020-01-22 neels struct diff_atom *atom;
406 bb7fb738 2020-01-27 neels struct diff_atom *atom_r;
407 3b0f3d61 2020-01-22 neels unsigned int left_idx;
408 3b0f3d61 2020-01-22 neels unsigned int right_idx;
410 3b0f3d61 2020-01-22 neels if (i < lcs_count) {
411 3b0f3d61 2020-01-22 neels atom = lcs[i];
412 bb7fb738 2020-01-27 neels atom_r = atom->patience.pos_in_other;
413 15ac50e2 2020-05-05 neels debug("lcs[%u] = left[%ld] = right[%ld]\n", i,
414 bb7fb738 2020-01-27 neels diff_atom_idx(left, atom), diff_atom_idx(right, atom_r));
415 bb7fb738 2020-01-27 neels left_idx = atom->patience.identical_lines.start;
416 bb7fb738 2020-01-27 neels right_idx = atom_r->patience.identical_lines.start;
417 bb7fb738 2020-01-27 neels debug(" identical lines l %u-%u r %u-%u\n",
418 bb7fb738 2020-01-27 neels atom->patience.identical_lines.start, atom->patience.identical_lines.end,
419 bb7fb738 2020-01-27 neels atom_r->patience.identical_lines.start, atom_r->patience.identical_lines.end);
421 3b0f3d61 2020-01-22 neels atom = NULL;
422 bb7fb738 2020-01-27 neels atom_r = NULL;
423 3b0f3d61 2020-01-22 neels left_idx = left->atoms.len;
424 3b0f3d61 2020-01-22 neels right_idx = right->atoms.len;
427 0d27172a 2020-05-06 neels /* 'atom' now marks an atom that matches on both sides according
428 0d27172a 2020-05-06 neels * to patience-diff (a common-unique identical atom in both
430 0d27172a 2020-05-06 neels * Handle the section before and the atom itself; the section
431 0d27172a 2020-05-06 neels * after will be handled by the next loop iteration -- note that
432 0d27172a 2020-05-06 neels * i loops to last element + 1 ("i <= lcs_count"), so that there
433 0d27172a 2020-05-06 neels * will be another final iteration to pick up the last remaining
434 0d27172a 2020-05-06 neels * items after the last LCS atom.
435 3b0f3d61 2020-01-22 neels * The sections before might also be empty on left and/or right.
436 0d27172a 2020-05-06 neels * left_pos and right_pos mark the indexes of the first atoms
437 0d27172a 2020-05-06 neels * that have not yet been handled in the previous loop
438 0d27172a 2020-05-06 neels * iteration. left_idx and right_idx mark the indexes of the
439 0d27172a 2020-05-06 neels * matching atom on left and right, respectively. */
441 0d27172a 2020-05-06 neels debug("iteration %u left_pos %u left_idx %u"
442 0d27172a 2020-05-06 neels " right_pos %u right_idx %u\n",
443 3b0f3d61 2020-01-22 neels i, left_pos, left_idx, right_pos, right_idx);
445 3b0f3d61 2020-01-22 neels /* Section before the matching atom */
446 3b0f3d61 2020-01-22 neels struct diff_atom *left_atom = &left->atoms.head[left_pos];
447 3b0f3d61 2020-01-22 neels unsigned int left_section_len = left_idx - left_pos;
449 3b0f3d61 2020-01-22 neels struct diff_atom *right_atom = &(right->atoms.head[right_pos]);
450 3b0f3d61 2020-01-22 neels unsigned int right_section_len = right_idx - right_pos;
452 3b0f3d61 2020-01-22 neels if (left_section_len && right_section_len) {
453 0d27172a 2020-05-06 neels /* Record an unsolved chunk, the caller will apply
454 0d27172a 2020-05-06 neels * inner_algo() on this chunk. */
455 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, false,
456 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
457 0d27172a 2020-05-06 neels right_atom,
458 0d27172a 2020-05-06 neels right_section_len))
459 3b0f3d61 2020-01-22 neels goto return_rc;
460 3b0f3d61 2020-01-22 neels } else if (left_section_len && !right_section_len) {
461 0d27172a 2020-05-06 neels /* Only left atoms and none on the right, they form a
462 0d27172a 2020-05-06 neels * "minus" chunk, then. */
463 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
464 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
465 3b0f3d61 2020-01-22 neels right_atom, 0))
466 3b0f3d61 2020-01-22 neels goto return_rc;
467 3b0f3d61 2020-01-22 neels } else if (!left_section_len && right_section_len) {
468 0d27172a 2020-05-06 neels /* No left atoms, only atoms on the right, they form a
469 0d27172a 2020-05-06 neels * "plus" chunk, then. */
470 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
471 3b0f3d61 2020-01-22 neels left_atom, 0,
472 3b0f3d61 2020-01-22 neels right_atom, right_section_len))
473 3b0f3d61 2020-01-22 neels goto return_rc;
475 0d27172a 2020-05-06 neels /* else: left_section_len == 0 and right_section_len == 0, i.e.
476 0d27172a 2020-05-06 neels * nothing here. */
478 0d27172a 2020-05-06 neels /* The atom found to match on both sides forms a chunk of equals
479 0d27172a 2020-05-06 neels * on each side. In the very last iteration of this loop, there
480 0d27172a 2020-05-06 neels * is no matching atom, we were just cleaning out the remaining
481 0d27172a 2020-05-06 neels * lines. */
482 3b0f3d61 2020-01-22 neels if (atom) {
484 0d27172a 2020-05-06 neels ok = diff_state_add_chunk(state, true,
485 0d27172a 2020-05-06 neels left->atoms.head
486 0d27172a 2020-05-06 neels + atom->patience.identical_lines.start,
487 d362ea2e 2020-07-25 stsp diff_range_len(&atom->patience.identical_lines),
488 0d27172a 2020-05-06 neels right->atoms.head
489 0d27172a 2020-05-06 neels + atom_r->patience.identical_lines.start,
490 d362ea2e 2020-07-25 stsp diff_range_len(&atom_r->patience.identical_lines));
492 3b0f3d61 2020-01-22 neels goto return_rc;
493 bb7fb738 2020-01-27 neels left_pos = atom->patience.identical_lines.end;
494 bb7fb738 2020-01-27 neels right_pos = atom_r->patience.identical_lines.end;
496 bb7fb738 2020-01-27 neels left_pos = left_idx + 1;
497 bb7fb738 2020-01-27 neels right_pos = right_idx + 1;
499 0d27172a 2020-05-06 neels debug("end of iteration %u left_pos %u left_idx %u"
500 0d27172a 2020-05-06 neels " right_pos %u right_idx %u\n",
501 bb7fb738 2020-01-27 neels i, left_pos, left_idx, right_pos, right_idx);
503 3b0f3d61 2020-01-22 neels debug("** END %s\n", __func__);
505 3b0f3d61 2020-01-22 neels rc = DIFF_RC_OK;
507 3b0f3d61 2020-01-22 neels return_rc:
508 3b0f3d61 2020-01-22 neels free(lcs);
509 3b0f3d61 2020-01-22 neels return rc;
