Blame


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. */
3 3b0f3d61 2020-01-22 neels /*
4 3b0f3d61 2020-01-22 neels * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
5 3b0f3d61 2020-01-22 neels *
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.
9 3b0f3d61 2020-01-22 neels *
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.
17 3b0f3d61 2020-01-22 neels */
18 3b0f3d61 2020-01-22 neels
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>
25 e10a628a 2020-09-16 stsp
26 1dfba055 2020-10-07 stsp #include <arraylist.h>
27 1dfba055 2020-10-07 stsp #include <diff_main.h>
28 3b0f3d61 2020-01-22 neels
29 85ab4559 2020-09-22 stsp #include "diff_internal.h"
30 2a1b94d0 2020-09-26 stsp #include "diff_debug.h"
31 3b0f3d61 2020-01-22 neels
32 60b6e08b 2020-10-12 neels int diff_atoms_qsort_compar(const void *_a, const void *_b)
33 3b0f3d61 2020-01-22 neels {
34 60b6e08b 2020-10-12 neels const struct diff_atom *a = *(struct diff_atom**)_a;
35 60b6e08b 2020-10-12 neels const struct diff_atom *b = *(struct diff_atom**)_b;
36 60b6e08b 2020-10-12 neels int cmp;
37 60b6e08b 2020-10-12 neels int rc;
38 60b6e08b 2020-10-12 neels
39 60b6e08b 2020-10-12 neels if (a->root->err || b->root->err) {
40 60b6e08b 2020-10-12 neels /* If atoms are from more than one diff_data, make sure the
41 60b6e08b 2020-10-12 neels * error, if any, spreads to all of them. */
42 60b6e08b 2020-10-12 neels a->root->err = rc;
43 60b6e08b 2020-10-12 neels b->root->err = rc;
44 60b6e08b 2020-10-12 neels return 0;
45 3b0f3d61 2020-01-22 neels }
46 3b0f3d61 2020-01-22 neels
47 60b6e08b 2020-10-12 neels /* Sort by the simplistic hash */
48 60b6e08b 2020-10-12 neels if (a->hash < b->hash)
49 60b6e08b 2020-10-12 neels return -1;
50 60b6e08b 2020-10-12 neels if (a->hash > b->hash)
51 60b6e08b 2020-10-12 neels return 1;
52 3b0f3d61 2020-01-22 neels
53 60b6e08b 2020-10-12 neels /* If hashes are the same, the lines may still differ. Do a full cmp. */
54 60b6e08b 2020-10-12 neels rc = diff_atom_cmp(&cmp, a, b);
55 60b6e08b 2020-10-12 neels
56 60b6e08b 2020-10-12 neels if (rc) {
57 60b6e08b 2020-10-12 neels /* Mark the I/O error so that the caller can find out about it.
58 60b6e08b 2020-10-12 neels * For the case atoms are from more than one diff_data, mark in
59 60b6e08b 2020-10-12 neels * both. */
60 60b6e08b 2020-10-12 neels a->root->err = rc;
61 60b6e08b 2020-10-12 neels if (a->root != b->root)
62 60b6e08b 2020-10-12 neels b->root->err = rc;
63 60b6e08b 2020-10-12 neels return 0;
64 3b0f3d61 2020-01-22 neels }
65 60b6e08b 2020-10-12 neels
66 60b6e08b 2020-10-12 neels return cmp;
67 3b0f3d61 2020-01-22 neels }
68 3b0f3d61 2020-01-22 neels
69 60b6e08b 2020-10-12 neels /* Sort an array of struct diff_atom* in-place. */
70 60b6e08b 2020-10-12 neels static int diff_atoms_qsort(struct diff_atom *atoms[],
71 60b6e08b 2020-10-12 neels size_t atoms_count)
72 3b0f3d61 2020-01-22 neels {
73 60b6e08b 2020-10-12 neels qsort(atoms, atoms_count, sizeof(struct diff_atom*),
74 60b6e08b 2020-10-12 neels diff_atoms_qsort_compar);
75 60b6e08b 2020-10-12 neels return atoms[0]->root->err;
76 60b6e08b 2020-10-12 neels }
77 3b0f3d61 2020-01-22 neels
78 60b6e08b 2020-10-12 neels static int
79 60b6e08b 2020-10-12 neels diff_atoms_mark_unique_in_both_by_qsort(struct diff_data *left,
80 60b6e08b 2020-10-12 neels struct diff_data *right,
81 60b6e08b 2020-10-12 neels unsigned int *unique_in_both_count_p)
82 60b6e08b 2020-10-12 neels {
83 60b6e08b 2020-10-12 neels struct diff_atom *a;
84 60b6e08b 2020-10-12 neels struct diff_atom *b;
85 60b6e08b 2020-10-12 neels struct diff_atom **all_atoms =
86 60b6e08b 2020-10-12 neels malloc((left->atoms.len + right->atoms.len)
87 60b6e08b 2020-10-12 neels * sizeof(struct diff_atom*));
88 60b6e08b 2020-10-12 neels unsigned int len = 0;
89 60b6e08b 2020-10-12 neels unsigned int i;
90 60b6e08b 2020-10-12 neels unsigned int unique_in_both_count = 0;
91 60b6e08b 2020-10-12 neels int rc;
92 60b6e08b 2020-10-12 neels left->root->err = 0;
93 60b6e08b 2020-10-12 neels right->root->err = 0;
94 60b6e08b 2020-10-12 neels diff_data_foreach_atom(a, left) {
95 60b6e08b 2020-10-12 neels all_atoms[len++] = a;
96 60b6e08b 2020-10-12 neels }
97 60b6e08b 2020-10-12 neels diff_data_foreach_atom(b, right) {
98 60b6e08b 2020-10-12 neels all_atoms[len++] = b;
99 60b6e08b 2020-10-12 neels }
100 60b6e08b 2020-10-12 neels
101 60b6e08b 2020-10-12 neels rc = diff_atoms_qsort(all_atoms, len);
102 60b6e08b 2020-10-12 neels if (rc)
103 60b6e08b 2020-10-12 neels goto free_and_exit;
104 60b6e08b 2020-10-12 neels
105 60b6e08b 2020-10-12 neels /* Now we have a sorted array of atom pointers. All similar lines are
106 60b6e08b 2020-10-12 neels * adjacent. Walk through the array and mark those that are unique on
107 60b6e08b 2020-10-12 neels * each side, but exist once in both sources. */
108 60b6e08b 2020-10-12 neels for (i = 0; i < len; i++) {
109 60b6e08b 2020-10-12 neels bool same;
110 60b6e08b 2020-10-12 neels unsigned int j;
111 60b6e08b 2020-10-12 neels unsigned int count_first_side = 1;
112 60b6e08b 2020-10-12 neels unsigned int count_other_side = 0;
113 60b6e08b 2020-10-12 neels a = all_atoms[i];
114 60b6e08b 2020-10-12 neels
115 60b6e08b 2020-10-12 neels for (j = i+1; j < len; j++) {
116 60b6e08b 2020-10-12 neels b = all_atoms[j];
117 60b6e08b 2020-10-12 neels rc = diff_atom_same(&same, a, b);
118 60b6e08b 2020-10-12 neels if (rc)
119 60b6e08b 2020-10-12 neels goto free_and_exit;
120 60b6e08b 2020-10-12 neels if (!same)
121 3b0f3d61 2020-01-22 neels break;
122 60b6e08b 2020-10-12 neels /* A following atom is the same. See on which side the
123 60b6e08b 2020-10-12 neels * repetition counts. */
124 60b6e08b 2020-10-12 neels if (a->root == b->root)
125 60b6e08b 2020-10-12 neels count_first_side ++;
126 60b6e08b 2020-10-12 neels else
127 60b6e08b 2020-10-12 neels count_other_side ++;
128 3b0f3d61 2020-01-22 neels }
129 3b0f3d61 2020-01-22 neels
130 60b6e08b 2020-10-12 neels /* Counted a section of similar atoms, put the results back to
131 60b6e08b 2020-10-12 neels * the atoms. */
132 60b6e08b 2020-10-12 neels if ((count_first_side == 1)
133 60b6e08b 2020-10-12 neels && (count_other_side == 1)) {
134 60b6e08b 2020-10-12 neels b = all_atoms[i+1];
135 60b6e08b 2020-10-12 neels a->patience.unique_in_both = true;
136 60b6e08b 2020-10-12 neels a->patience.pos_in_other = b;
137 60b6e08b 2020-10-12 neels b->patience.unique_in_both = true;
138 60b6e08b 2020-10-12 neels b->patience.pos_in_other = a;
139 60b6e08b 2020-10-12 neels unique_in_both_count++;
140 3b0f3d61 2020-01-22 neels }
141 3b0f3d61 2020-01-22 neels }
142 60b6e08b 2020-10-12 neels *unique_in_both_count_p = unique_in_both_count;
143 60b6e08b 2020-10-12 neels rc = 0;
144 60b6e08b 2020-10-12 neels free_and_exit:
145 60b6e08b 2020-10-12 neels free(all_atoms);
146 60b6e08b 2020-10-12 neels return rc;
147 3b0f3d61 2020-01-22 neels }
148 3b0f3d61 2020-01-22 neels
149 44cf4950 2020-09-20 neels static int
150 0d27172a 2020-05-06 neels diff_atoms_swallow_identical_neighbors(struct diff_data *left,
151 0d27172a 2020-05-06 neels struct diff_data *right,
152 61a7b578 2020-05-06 neels unsigned int *unique_in_both_count)
153 bb7fb738 2020-01-27 neels {
154 0d27172a 2020-05-06 neels debug("trivially combine identical lines"
155 0d27172a 2020-05-06 neels " around unique_in_both lines\n");
156 3b0f3d61 2020-01-22 neels
157 bb7fb738 2020-01-27 neels unsigned int l_idx;
158 bb7fb738 2020-01-27 neels unsigned int next_l_idx;
159 bb7fb738 2020-01-27 neels unsigned int l_min = 0;
160 bb7fb738 2020-01-27 neels unsigned int r_min = 0;
161 bb7fb738 2020-01-27 neels for (l_idx = 0; l_idx < left->atoms.len; l_idx = next_l_idx) {
162 bb7fb738 2020-01-27 neels next_l_idx = l_idx + 1;
163 bb7fb738 2020-01-27 neels struct diff_atom *l = &left->atoms.head[l_idx];
164 bb7fb738 2020-01-27 neels
165 bb7fb738 2020-01-27 neels if (!l->patience.unique_in_both)
166 bb7fb738 2020-01-27 neels continue;
167 bb7fb738 2020-01-27 neels
168 bb7fb738 2020-01-27 neels debug("check identical lines around ");
169 bb7fb738 2020-01-27 neels debug_dump_atom(left, right, l);
170 bb7fb738 2020-01-27 neels
171 0d27172a 2020-05-06 neels unsigned int r_idx = diff_atom_idx(right,
172 0d27172a 2020-05-06 neels l->patience.pos_in_other);
173 bb7fb738 2020-01-27 neels
174 d362ea2e 2020-07-25 stsp struct diff_range identical_l;
175 d362ea2e 2020-07-25 stsp struct diff_range identical_r;
176 bb7fb738 2020-01-27 neels
177 bb7fb738 2020-01-27 neels /* Swallow upwards.
178 0d27172a 2020-05-06 neels * Each common-unique line swallows identical lines upwards and
179 0d27172a 2020-05-06 neels * downwards.
180 0d27172a 2020-05-06 neels * All common-unique lines that were part of the identical lines
181 0d27172a 2020-05-06 neels * following below were already swallowed in the previous
182 0d27172a 2020-05-06 neels * iteration, so we will never hit another common-unique line
183 0d27172a 2020-05-06 neels * above. */
184 bb7fb738 2020-01-27 neels for (identical_l.start = l_idx, identical_r.start = r_idx;
185 b3fb4686 2020-09-20 neels identical_l.start > l_min && identical_r.start > r_min;
186 b3fb4686 2020-09-20 neels identical_l.start--, identical_r.start--) {
187 b3fb4686 2020-09-20 neels bool same;
188 b3fb4686 2020-09-20 neels int r = diff_atom_same(&same,
189 0d27172a 2020-05-06 neels &left->atoms.head[identical_l.start - 1],
190 0d27172a 2020-05-06 neels &right->atoms.head[identical_r.start - 1]);
191 b3fb4686 2020-09-20 neels if (r)
192 44cf4950 2020-09-20 neels return r;
193 b3fb4686 2020-09-20 neels if (!same)
194 b3fb4686 2020-09-20 neels break;
195 b3fb4686 2020-09-20 neels }
196 bb7fb738 2020-01-27 neels
197 bb7fb738 2020-01-27 neels /* Swallow downwards */
198 bb7fb738 2020-01-27 neels for (identical_l.end = l_idx + 1, identical_r.end = r_idx + 1;
199 bb7fb738 2020-01-27 neels identical_l.end < left->atoms.len
200 b3fb4686 2020-09-20 neels && identical_r.end < right->atoms.len;
201 bb7fb738 2020-01-27 neels identical_l.end++, identical_r.end++,
202 bb7fb738 2020-01-27 neels next_l_idx++) {
203 0d27172a 2020-05-06 neels struct diff_atom *l_end;
204 0d27172a 2020-05-06 neels struct diff_atom *r_end;
205 b3fb4686 2020-09-20 neels bool same;
206 b3fb4686 2020-09-20 neels int r = diff_atom_same(&same,
207 b3fb4686 2020-09-20 neels &left->atoms.head[identical_l.end],
208 b3fb4686 2020-09-20 neels &right->atoms.head[identical_r.end]);
209 b3fb4686 2020-09-20 neels if (r)
210 44cf4950 2020-09-20 neels return r;
211 b3fb4686 2020-09-20 neels if (!same)
212 b3fb4686 2020-09-20 neels break;
213 0d27172a 2020-05-06 neels l_end = &left->atoms.head[identical_l.end];
214 ab699b5c 2020-05-12 stsp r_end = &right->atoms.head[identical_r.end];
215 0d27172a 2020-05-06 neels if (!l_end->patience.unique_in_both)
216 0d27172a 2020-05-06 neels continue;
217 0d27172a 2020-05-06 neels /* Part of a chunk of identical lines, remove from
218 0d27172a 2020-05-06 neels * listing of unique_in_both lines */
219 0d27172a 2020-05-06 neels l_end->patience.unique_in_both = false;
220 0d27172a 2020-05-06 neels r_end->patience.unique_in_both = false;
221 0d27172a 2020-05-06 neels (*unique_in_both_count)--;
222 bb7fb738 2020-01-27 neels }
223 bb7fb738 2020-01-27 neels
224 bb7fb738 2020-01-27 neels l->patience.identical_lines = identical_l;
225 0d27172a 2020-05-06 neels l->patience.pos_in_other->patience.identical_lines =
226 0d27172a 2020-05-06 neels identical_r;
227 bb7fb738 2020-01-27 neels
228 bb7fb738 2020-01-27 neels l_min = identical_l.end;
229 bb7fb738 2020-01-27 neels r_min = identical_r.end;
230 bb7fb738 2020-01-27 neels
231 d362ea2e 2020-07-25 stsp if (!diff_range_empty(&l->patience.identical_lines)) {
232 0d27172a 2020-05-06 neels debug("common-unique line at l=%u r=%u swallowed"
233 0d27172a 2020-05-06 neels " identical lines l=%u-%u r=%u-%u\n",
234 bb7fb738 2020-01-27 neels l_idx, r_idx,
235 bb7fb738 2020-01-27 neels identical_l.start, identical_l.end,
236 bb7fb738 2020-01-27 neels identical_r.start, identical_r.end);
237 bb7fb738 2020-01-27 neels }
238 bb7fb738 2020-01-27 neels debug("next_l_idx = %u\n", next_l_idx);
239 bb7fb738 2020-01-27 neels }
240 44cf4950 2020-09-20 neels return 0;
241 bb7fb738 2020-01-27 neels }
242 bb7fb738 2020-01-27 neels
243 0d27172a 2020-05-06 neels /* binary search to find the stack to put this atom "card" on. */
244 0d27172a 2020-05-06 neels static int
245 0d27172a 2020-05-06 neels find_target_stack(struct diff_atom *atom,
246 0d27172a 2020-05-06 neels struct diff_atom **patience_stacks,
247 0d27172a 2020-05-06 neels unsigned int patience_stacks_count)
248 0d27172a 2020-05-06 neels {
249 0d27172a 2020-05-06 neels unsigned int lo = 0;
250 0d27172a 2020-05-06 neels unsigned int hi = patience_stacks_count;
251 0d27172a 2020-05-06 neels while (lo < hi) {
252 0d27172a 2020-05-06 neels unsigned int mid = (lo + hi) >> 1;
253 0d27172a 2020-05-06 neels
254 0d27172a 2020-05-06 neels if (patience_stacks[mid]->patience.pos_in_other
255 0d27172a 2020-05-06 neels < atom->patience.pos_in_other)
256 0d27172a 2020-05-06 neels lo = mid + 1;
257 0d27172a 2020-05-06 neels else
258 0d27172a 2020-05-06 neels hi = mid;
259 0d27172a 2020-05-06 neels }
260 0d27172a 2020-05-06 neels return lo;
261 0d27172a 2020-05-06 neels }
262 0d27172a 2020-05-06 neels
263 0d27172a 2020-05-06 neels /* Among the lines that appear exactly once in each side, find the longest
264 0d27172a 2020-05-06 neels * streak that appear in both files in the same order (with other stuff allowed
265 0d27172a 2020-05-06 neels * to interleave). Use patience sort for that, as in the Patience Diff
266 0d27172a 2020-05-06 neels * algorithm.
267 0d27172a 2020-05-06 neels * See https://bramcohen.livejournal.com/73318.html and, for a much more
268 0d27172a 2020-05-06 neels * detailed explanation,
269 3b0f3d61 2020-01-22 neels * https://blog.jcoglan.com/2017/09/19/the-patience-diff-algorithm/ */
270 3e6cba3a 2020-08-13 stsp int
271 0d27172a 2020-05-06 neels diff_algo_patience(const struct diff_algo_config *algo_config,
272 0d27172a 2020-05-06 neels struct diff_state *state)
273 3b0f3d61 2020-01-22 neels {
274 44cf4950 2020-09-20 neels int rc;
275 3b0f3d61 2020-01-22 neels
276 3b0f3d61 2020-01-22 neels struct diff_data *left = &state->left;
277 3b0f3d61 2020-01-22 neels struct diff_data *right = &state->right;
278 3b0f3d61 2020-01-22 neels
279 3b0f3d61 2020-01-22 neels unsigned int unique_in_both_count;
280 3b0f3d61 2020-01-22 neels
281 3b0f3d61 2020-01-22 neels debug("\n** %s\n", __func__);
282 3b0f3d61 2020-01-22 neels
283 0d27172a 2020-05-06 neels /* Find those lines that appear exactly once in 'left' and exactly once
284 0d27172a 2020-05-06 neels * in 'right'. */
285 60b6e08b 2020-10-12 neels rc = diff_atoms_mark_unique_in_both_by_qsort(left, right,
286 60b6e08b 2020-10-12 neels &unique_in_both_count);
287 44cf4950 2020-09-20 neels if (rc)
288 44cf4950 2020-09-20 neels return rc;
289 3b0f3d61 2020-01-22 neels
290 3b0f3d61 2020-01-22 neels debug("unique_in_both_count %u\n", unique_in_both_count);
291 3b0f3d61 2020-01-22 neels debug("left:\n");
292 3b0f3d61 2020-01-22 neels debug_dump(left);
293 3b0f3d61 2020-01-22 neels debug("right:\n");
294 3b0f3d61 2020-01-22 neels debug_dump(right);
295 3b0f3d61 2020-01-22 neels
296 3b0f3d61 2020-01-22 neels if (!unique_in_both_count) {
297 0d27172a 2020-05-06 neels /* Cannot apply Patience, tell the caller to use fallback_algo
298 0d27172a 2020-05-06 neels * instead. */
299 3b0f3d61 2020-01-22 neels return DIFF_RC_USE_DIFF_ALGO_FALLBACK;
300 3b0f3d61 2020-01-22 neels }
301 3b0f3d61 2020-01-22 neels
302 44cf4950 2020-09-20 neels rc = diff_atoms_swallow_identical_neighbors(left, right,
303 44cf4950 2020-09-20 neels &unique_in_both_count);
304 44cf4950 2020-09-20 neels if (rc)
305 44cf4950 2020-09-20 neels return rc;
306 bb7fb738 2020-01-27 neels debug("After swallowing identical neighbors: unique_in_both = %u\n",
307 bb7fb738 2020-01-27 neels unique_in_both_count);
308 bb7fb738 2020-01-27 neels
309 44cf4950 2020-09-20 neels rc = ENOMEM;
310 44cf4950 2020-09-20 neels
311 0d27172a 2020-05-06 neels /* An array of Longest Common Sequence is the result of the below
312 0d27172a 2020-05-06 neels * subscope: */
313 3b0f3d61 2020-01-22 neels unsigned int lcs_count = 0;
314 3b0f3d61 2020-01-22 neels struct diff_atom **lcs = NULL;
315 3b0f3d61 2020-01-22 neels struct diff_atom *lcs_tail = NULL;
316 3b0f3d61 2020-01-22 neels
317 3b0f3d61 2020-01-22 neels {
318 0d27172a 2020-05-06 neels /* This subscope marks the lifetime of the atom_pointers
319 0d27172a 2020-05-06 neels * allocation */
320 3b0f3d61 2020-01-22 neels
321 3b0f3d61 2020-01-22 neels /* One chunk of storage for atom pointers */
322 0d27172a 2020-05-06 neels struct diff_atom **atom_pointers;
323 0d27172a 2020-05-06 neels atom_pointers = recallocarray(NULL, 0, unique_in_both_count * 2,
324 0d27172a 2020-05-06 neels sizeof(struct diff_atom*));
325 3b0f3d61 2020-01-22 neels
326 0d27172a 2020-05-06 neels /* Half for the list of atoms that still need to be put on
327 0d27172a 2020-05-06 neels * stacks */
328 3b0f3d61 2020-01-22 neels struct diff_atom **uniques = atom_pointers;
329 3b0f3d61 2020-01-22 neels
330 0d27172a 2020-05-06 neels /* Half for the patience sort state's "card stacks" -- we
331 0d27172a 2020-05-06 neels * remember only each stack's topmost "card" */
332 0d27172a 2020-05-06 neels struct diff_atom **patience_stacks;
333 0d27172a 2020-05-06 neels patience_stacks = atom_pointers + unique_in_both_count;
334 3b0f3d61 2020-01-22 neels unsigned int patience_stacks_count = 0;
335 3b0f3d61 2020-01-22 neels
336 3b0f3d61 2020-01-22 neels /* Take all common, unique items from 'left' ... */
337 3b0f3d61 2020-01-22 neels
338 3b0f3d61 2020-01-22 neels struct diff_atom *atom;
339 3b0f3d61 2020-01-22 neels struct diff_atom **uniques_end = uniques;
340 3b0f3d61 2020-01-22 neels diff_data_foreach_atom(atom, left) {
341 3b0f3d61 2020-01-22 neels if (!atom->patience.unique_in_both)
342 3b0f3d61 2020-01-22 neels continue;
343 3b0f3d61 2020-01-22 neels *uniques_end = atom;
344 3b0f3d61 2020-01-22 neels uniques_end++;
345 3b0f3d61 2020-01-22 neels }
346 3b0f3d61 2020-01-22 neels
347 3b0f3d61 2020-01-22 neels /* ...and sort them to the order found in 'right'.
348 0d27172a 2020-05-06 neels * The idea is to find the leftmost stack that has a higher line
349 0d27172a 2020-05-06 neels * number and add it to the stack's top.
350 0d27172a 2020-05-06 neels * If there is no such stack, open a new one on the right. The
351 0d27172a 2020-05-06 neels * line number is derived from the atom*, which are array items
352 0d27172a 2020-05-06 neels * and hence reflect the relative position in the source file.
353 0d27172a 2020-05-06 neels * So we got the common-uniques from 'left' and sort them
354 0d27172a 2020-05-06 neels * according to atom->patience.pos_in_other. */
355 3b0f3d61 2020-01-22 neels unsigned int i;
356 3b0f3d61 2020-01-22 neels for (i = 0; i < unique_in_both_count; i++) {
357 3b0f3d61 2020-01-22 neels atom = uniques[i];
358 3b0f3d61 2020-01-22 neels unsigned int target_stack;
359 0d27172a 2020-05-06 neels target_stack = find_target_stack(atom, patience_stacks,
360 0d27172a 2020-05-06 neels patience_stacks_count);
361 3b0f3d61 2020-01-22 neels assert(target_stack <= patience_stacks_count);
362 3b0f3d61 2020-01-22 neels patience_stacks[target_stack] = atom;
363 3b0f3d61 2020-01-22 neels if (target_stack == patience_stacks_count)
364 3b0f3d61 2020-01-22 neels patience_stacks_count++;
365 3b0f3d61 2020-01-22 neels
366 0d27172a 2020-05-06 neels /* Record a back reference to the next stack on the
367 0d27172a 2020-05-06 neels * left, which will form the final longest sequence
368 3b0f3d61 2020-01-22 neels * later. */
369 0d27172a 2020-05-06 neels atom->patience.prev_stack = target_stack ?
370 0d27172a 2020-05-06 neels patience_stacks[target_stack - 1] : NULL;
371 3b0f3d61 2020-01-22 neels
372 3b0f3d61 2020-01-22 neels }
373 3b0f3d61 2020-01-22 neels
374 0d27172a 2020-05-06 neels /* backtrace through prev_stack references to form the final
375 0d27172a 2020-05-06 neels * longest common sequence */
376 3b0f3d61 2020-01-22 neels lcs_tail = patience_stacks[patience_stacks_count - 1];
377 3b0f3d61 2020-01-22 neels lcs_count = patience_stacks_count;
378 3b0f3d61 2020-01-22 neels
379 0d27172a 2020-05-06 neels /* uniques and patience_stacks are no longer needed.
380 0d27172a 2020-05-06 neels * Backpointers are in atom->patience.prev_stack */
381 3b0f3d61 2020-01-22 neels free(atom_pointers);
382 3b0f3d61 2020-01-22 neels }
383 3b0f3d61 2020-01-22 neels
384 3b0f3d61 2020-01-22 neels lcs = recallocarray(NULL, 0, lcs_count, sizeof(struct diff_atom*));
385 3b0f3d61 2020-01-22 neels struct diff_atom **lcs_backtrace_pos = &lcs[lcs_count - 1];
386 3b0f3d61 2020-01-22 neels struct diff_atom *atom;
387 3b0f3d61 2020-01-22 neels for (atom = lcs_tail; atom; atom = atom->patience.prev_stack, lcs_backtrace_pos--) {
388 3b0f3d61 2020-01-22 neels assert(lcs_backtrace_pos >= lcs);
389 3b0f3d61 2020-01-22 neels *lcs_backtrace_pos = atom;
390 3b0f3d61 2020-01-22 neels }
391 3b0f3d61 2020-01-22 neels
392 3b0f3d61 2020-01-22 neels unsigned int i;
393 3b0f3d61 2020-01-22 neels if (DEBUG) {
394 3b0f3d61 2020-01-22 neels debug("\npatience LCS:\n");
395 3b0f3d61 2020-01-22 neels for (i = 0; i < lcs_count; i++) {
396 3b0f3d61 2020-01-22 neels debug_dump_atom(left, right, lcs[i]);
397 3b0f3d61 2020-01-22 neels }
398 3b0f3d61 2020-01-22 neels }
399 3b0f3d61 2020-01-22 neels
400 3b0f3d61 2020-01-22 neels
401 0d27172a 2020-05-06 neels /* TODO: For each common-unique line found (now listed in lcs), swallow
402 0d27172a 2020-05-06 neels * lines upwards and downwards that are identical on each side. Requires
403 0d27172a 2020-05-06 neels * a way to represent atoms being glued to adjacent atoms. */
404 3b0f3d61 2020-01-22 neels
405 3b0f3d61 2020-01-22 neels debug("\ntraverse LCS, possibly recursing:\n");
406 3b0f3d61 2020-01-22 neels
407 0d27172a 2020-05-06 neels /* Now we have pinned positions in both files at which it makes sense to
408 0d27172a 2020-05-06 neels * divide the diff problem into smaller chunks. Go into the next round:
409 0d27172a 2020-05-06 neels * look at each section in turn, trying to again find common-unique
410 0d27172a 2020-05-06 neels * lines in those smaller sections. As soon as no more are found, the
411 0d27172a 2020-05-06 neels * remaining smaller sections are solved by Myers. */
412 3b0f3d61 2020-01-22 neels unsigned int left_pos = 0;
413 3b0f3d61 2020-01-22 neels unsigned int right_pos = 0;
414 3b0f3d61 2020-01-22 neels for (i = 0; i <= lcs_count; i++) {
415 3b0f3d61 2020-01-22 neels struct diff_atom *atom;
416 bb7fb738 2020-01-27 neels struct diff_atom *atom_r;
417 3b0f3d61 2020-01-22 neels unsigned int left_idx;
418 3b0f3d61 2020-01-22 neels unsigned int right_idx;
419 3b0f3d61 2020-01-22 neels
420 3b0f3d61 2020-01-22 neels if (i < lcs_count) {
421 3b0f3d61 2020-01-22 neels atom = lcs[i];
422 bb7fb738 2020-01-27 neels atom_r = atom->patience.pos_in_other;
423 2a1b94d0 2020-09-26 stsp debug("lcs[%u] = left[%u] = right[%u]\n", i,
424 bb7fb738 2020-01-27 neels diff_atom_idx(left, atom), diff_atom_idx(right, atom_r));
425 bb7fb738 2020-01-27 neels left_idx = atom->patience.identical_lines.start;
426 bb7fb738 2020-01-27 neels right_idx = atom_r->patience.identical_lines.start;
427 bb7fb738 2020-01-27 neels debug(" identical lines l %u-%u r %u-%u\n",
428 bb7fb738 2020-01-27 neels atom->patience.identical_lines.start, atom->patience.identical_lines.end,
429 bb7fb738 2020-01-27 neels atom_r->patience.identical_lines.start, atom_r->patience.identical_lines.end);
430 3b0f3d61 2020-01-22 neels } else {
431 3b0f3d61 2020-01-22 neels atom = NULL;
432 bb7fb738 2020-01-27 neels atom_r = NULL;
433 3b0f3d61 2020-01-22 neels left_idx = left->atoms.len;
434 3b0f3d61 2020-01-22 neels right_idx = right->atoms.len;
435 3b0f3d61 2020-01-22 neels }
436 3b0f3d61 2020-01-22 neels
437 0d27172a 2020-05-06 neels /* 'atom' now marks an atom that matches on both sides according
438 0d27172a 2020-05-06 neels * to patience-diff (a common-unique identical atom in both
439 0d27172a 2020-05-06 neels * files).
440 0d27172a 2020-05-06 neels * Handle the section before and the atom itself; the section
441 0d27172a 2020-05-06 neels * after will be handled by the next loop iteration -- note that
442 0d27172a 2020-05-06 neels * i loops to last element + 1 ("i <= lcs_count"), so that there
443 0d27172a 2020-05-06 neels * will be another final iteration to pick up the last remaining
444 0d27172a 2020-05-06 neels * items after the last LCS atom.
445 3b0f3d61 2020-01-22 neels * The sections before might also be empty on left and/or right.
446 0d27172a 2020-05-06 neels * left_pos and right_pos mark the indexes of the first atoms
447 0d27172a 2020-05-06 neels * that have not yet been handled in the previous loop
448 0d27172a 2020-05-06 neels * iteration. left_idx and right_idx mark the indexes of the
449 0d27172a 2020-05-06 neels * matching atom on left and right, respectively. */
450 3b0f3d61 2020-01-22 neels
451 0d27172a 2020-05-06 neels debug("iteration %u left_pos %u left_idx %u"
452 0d27172a 2020-05-06 neels " right_pos %u right_idx %u\n",
453 3b0f3d61 2020-01-22 neels i, left_pos, left_idx, right_pos, right_idx);
454 3b0f3d61 2020-01-22 neels
455 3b0f3d61 2020-01-22 neels /* Section before the matching atom */
456 3b0f3d61 2020-01-22 neels struct diff_atom *left_atom = &left->atoms.head[left_pos];
457 3b0f3d61 2020-01-22 neels unsigned int left_section_len = left_idx - left_pos;
458 3b0f3d61 2020-01-22 neels
459 3b0f3d61 2020-01-22 neels struct diff_atom *right_atom = &(right->atoms.head[right_pos]);
460 3b0f3d61 2020-01-22 neels unsigned int right_section_len = right_idx - right_pos;
461 3b0f3d61 2020-01-22 neels
462 3b0f3d61 2020-01-22 neels if (left_section_len && right_section_len) {
463 0d27172a 2020-05-06 neels /* Record an unsolved chunk, the caller will apply
464 0d27172a 2020-05-06 neels * inner_algo() on this chunk. */
465 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, false,
466 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
467 0d27172a 2020-05-06 neels right_atom,
468 0d27172a 2020-05-06 neels right_section_len))
469 3b0f3d61 2020-01-22 neels goto return_rc;
470 3b0f3d61 2020-01-22 neels } else if (left_section_len && !right_section_len) {
471 0d27172a 2020-05-06 neels /* Only left atoms and none on the right, they form a
472 0d27172a 2020-05-06 neels * "minus" chunk, then. */
473 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
474 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
475 3b0f3d61 2020-01-22 neels right_atom, 0))
476 3b0f3d61 2020-01-22 neels goto return_rc;
477 3b0f3d61 2020-01-22 neels } else if (!left_section_len && right_section_len) {
478 0d27172a 2020-05-06 neels /* No left atoms, only atoms on the right, they form a
479 0d27172a 2020-05-06 neels * "plus" chunk, then. */
480 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
481 3b0f3d61 2020-01-22 neels left_atom, 0,
482 3b0f3d61 2020-01-22 neels right_atom, right_section_len))
483 3b0f3d61 2020-01-22 neels goto return_rc;
484 3b0f3d61 2020-01-22 neels }
485 0d27172a 2020-05-06 neels /* else: left_section_len == 0 and right_section_len == 0, i.e.
486 0d27172a 2020-05-06 neels * nothing here. */
487 3b0f3d61 2020-01-22 neels
488 0d27172a 2020-05-06 neels /* The atom found to match on both sides forms a chunk of equals
489 0d27172a 2020-05-06 neels * on each side. In the very last iteration of this loop, there
490 0d27172a 2020-05-06 neels * is no matching atom, we were just cleaning out the remaining
491 0d27172a 2020-05-06 neels * lines. */
492 3b0f3d61 2020-01-22 neels if (atom) {
493 0d27172a 2020-05-06 neels void *ok;
494 0d27172a 2020-05-06 neels ok = diff_state_add_chunk(state, true,
495 0d27172a 2020-05-06 neels left->atoms.head
496 0d27172a 2020-05-06 neels + atom->patience.identical_lines.start,
497 d362ea2e 2020-07-25 stsp diff_range_len(&atom->patience.identical_lines),
498 0d27172a 2020-05-06 neels right->atoms.head
499 0d27172a 2020-05-06 neels + atom_r->patience.identical_lines.start,
500 d362ea2e 2020-07-25 stsp diff_range_len(&atom_r->patience.identical_lines));
501 0d27172a 2020-05-06 neels if (!ok)
502 3b0f3d61 2020-01-22 neels goto return_rc;
503 bb7fb738 2020-01-27 neels left_pos = atom->patience.identical_lines.end;
504 bb7fb738 2020-01-27 neels right_pos = atom_r->patience.identical_lines.end;
505 bb7fb738 2020-01-27 neels } else {
506 bb7fb738 2020-01-27 neels left_pos = left_idx + 1;
507 bb7fb738 2020-01-27 neels right_pos = right_idx + 1;
508 3b0f3d61 2020-01-22 neels }
509 0d27172a 2020-05-06 neels debug("end of iteration %u left_pos %u left_idx %u"
510 0d27172a 2020-05-06 neels " right_pos %u right_idx %u\n",
511 bb7fb738 2020-01-27 neels i, left_pos, left_idx, right_pos, right_idx);
512 3b0f3d61 2020-01-22 neels }
513 3b0f3d61 2020-01-22 neels debug("** END %s\n", __func__);
514 3b0f3d61 2020-01-22 neels
515 3b0f3d61 2020-01-22 neels rc = DIFF_RC_OK;
516 3b0f3d61 2020-01-22 neels
517 3b0f3d61 2020-01-22 neels return_rc:
518 3b0f3d61 2020-01-22 neels free(lcs);
519 3b0f3d61 2020-01-22 neels return rc;
520 3b0f3d61 2020-01-22 neels }